1 /* 2 * Copyright (c) 2012, 2015, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. 8 * 9 * This code is distributed in the hope that it will be useful, but WITHOUT 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12 * version 2 for more details (a copy is included in the LICENSE file that 13 * accompanied this code). 14 * 15 * You should have received a copy of the GNU General Public License version 16 * 2 along with this work; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 */ 23 package org.graalvm.compiler.loop; 24 25 import java.util.Collection; 26 import java.util.LinkedList; 27 import java.util.Queue; 28 29 import org.graalvm.compiler.core.common.calc.Condition; 30 import org.graalvm.compiler.core.common.cfg.Loop; 31 import org.graalvm.compiler.core.common.type.IntegerStamp; 32 import org.graalvm.compiler.debug.DebugContext; 33 import org.graalvm.compiler.debug.GraalError; 34 import org.graalvm.compiler.graph.Node; 35 import org.graalvm.compiler.graph.NodeBitMap; 36 import org.graalvm.compiler.graph.iterators.NodePredicate; 37 import org.graalvm.compiler.loop.InductionVariable.Direction; 38 import org.graalvm.compiler.nodes.AbstractBeginNode; 39 import org.graalvm.compiler.nodes.AbstractEndNode; 40 import org.graalvm.compiler.nodes.ConstantNode; 41 import org.graalvm.compiler.nodes.FixedGuardNode; 42 import org.graalvm.compiler.nodes.FixedNode; 43 import org.graalvm.compiler.nodes.FixedWithNextNode; 44 import org.graalvm.compiler.nodes.FrameState; 45 import org.graalvm.compiler.nodes.FullInfopointNode; 46 import org.graalvm.compiler.nodes.IfNode; 47 import org.graalvm.compiler.nodes.LogicNode; 48 import org.graalvm.compiler.nodes.LoopBeginNode; 49 import org.graalvm.compiler.nodes.PhiNode; 50 import org.graalvm.compiler.nodes.PiNode; 51 import org.graalvm.compiler.nodes.StructuredGraph; 52 import org.graalvm.compiler.nodes.ValueNode; 53 import org.graalvm.compiler.nodes.ValuePhiNode; 54 import org.graalvm.compiler.nodes.calc.AddNode; 55 import org.graalvm.compiler.nodes.calc.BinaryArithmeticNode; 56 import org.graalvm.compiler.nodes.calc.CompareNode; 57 import org.graalvm.compiler.nodes.calc.IntegerBelowNode; 58 import org.graalvm.compiler.nodes.calc.IntegerEqualsNode; 59 import org.graalvm.compiler.nodes.calc.IntegerLessThanNode; 60 import org.graalvm.compiler.nodes.calc.LeftShiftNode; 61 import org.graalvm.compiler.nodes.calc.MulNode; 62 import org.graalvm.compiler.nodes.calc.NegateNode; 63 import org.graalvm.compiler.nodes.calc.SignExtendNode; 64 import org.graalvm.compiler.nodes.calc.SubNode; 65 import org.graalvm.compiler.nodes.calc.ZeroExtendNode; 66 import org.graalvm.compiler.nodes.cfg.Block; 67 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph; 68 import org.graalvm.compiler.nodes.debug.ControlFlowAnchored; 69 import org.graalvm.compiler.nodes.extended.ValueAnchorNode; 70 import org.graalvm.compiler.nodes.util.GraphUtil; 71 import org.graalvm.util.EconomicMap; 72 import org.graalvm.util.EconomicSet; 73 import org.graalvm.util.Equivalence; 74 75 import jdk.vm.ci.code.BytecodeFrame; 76 77 public class LoopEx { 78 private final Loop<Block> loop; 79 private LoopFragmentInside inside; 80 private LoopFragmentWhole whole; 81 private CountedLoopInfo counted; 82 private LoopsData data; 83 private EconomicMap<Node, InductionVariable> ivs; 84 85 LoopEx(Loop<Block> loop, LoopsData data) { 86 this.loop = loop; 87 this.data = data; 88 } 89 90 public Loop<Block> loop() { 91 return loop; 92 } 93 94 public LoopFragmentInside inside() { 95 if (inside == null) { 96 inside = new LoopFragmentInside(this); 97 } 98 return inside; 99 } 100 101 public LoopFragmentWhole whole() { 102 if (whole == null) { 103 whole = new LoopFragmentWhole(this); 104 } 105 return whole; 106 } 107 108 public void invalidateFragments() { 109 inside = null; 110 whole = null; 111 } 112 113 @SuppressWarnings("unused") 114 public LoopFragmentInsideFrom insideFrom(FixedNode point) { 115 // TODO (gd) 116 return null; 117 } 118 119 @SuppressWarnings("unused") 120 public LoopFragmentInsideBefore insideBefore(FixedNode point) { 121 // TODO (gd) 122 return null; 123 } 124 125 public boolean isOutsideLoop(Node n) { 126 return !whole().contains(n); 127 } 128 129 public LoopBeginNode loopBegin() { 130 return (LoopBeginNode) loop().getHeader().getBeginNode(); 131 } 132 133 public FixedNode predecessor() { 134 return (FixedNode) loopBegin().forwardEnd().predecessor(); 135 } 136 137 public FixedNode entryPoint() { 138 return loopBegin().forwardEnd(); 139 } 140 141 public boolean isCounted() { 142 return counted != null; 143 } 144 145 public CountedLoopInfo counted() { 146 return counted; 147 } 148 149 public LoopEx parent() { 150 if (loop.getParent() == null) { 151 return null; 152 } 153 return data.loop(loop.getParent()); 154 } 155 156 public int size() { 157 return whole().nodes().count(); 158 } 159 160 @Override 161 public String toString() { 162 return (isCounted() ? "CountedLoop [" + counted() + "] " : "Loop ") + "(depth=" + loop().getDepth() + ") " + loopBegin(); 163 } 164 165 private class InvariantPredicate implements NodePredicate { 166 167 @Override 168 public boolean apply(Node n) { 169 return isOutsideLoop(n); 170 } 171 } 172 173 public void reassociateInvariants() { 174 InvariantPredicate invariant = new InvariantPredicate(); 175 StructuredGraph graph = loopBegin().graph(); 176 for (BinaryArithmeticNode<?> binary : whole().nodes().filter(BinaryArithmeticNode.class)) { 177 if (!binary.isAssociative()) { 178 continue; 179 } 180 ValueNode result = BinaryArithmeticNode.reassociate(binary, invariant, binary.getX(), binary.getY()); 181 if (result != binary) { 182 DebugContext debug = graph.getDebug(); 183 if (debug.isLogEnabled()) { 184 debug.log("%s : Reassociated %s into %s", graph.method().format("%H::%n"), binary, result); 185 } 186 if (!result.isAlive()) { 187 assert !result.isDeleted(); 188 result = graph.addOrUniqueWithInputs(result); 189 } 190 binary.replaceAtUsages(result); 191 GraphUtil.killWithUnusedFloatingInputs(binary); 192 } 193 } 194 } 195 196 public boolean detectCounted() { 197 LoopBeginNode loopBegin = loopBegin(); 198 FixedNode next = loopBegin.next(); 199 while (next instanceof FixedGuardNode || next instanceof ValueAnchorNode || next instanceof FullInfopointNode) { 200 next = ((FixedWithNextNode) next).next(); 201 } 202 if (next instanceof IfNode) { 203 IfNode ifNode = (IfNode) next; 204 boolean negated = false; 205 if (!loopBegin.isLoopExit(ifNode.falseSuccessor())) { 206 if (!loopBegin.isLoopExit(ifNode.trueSuccessor())) { 207 return false; 208 } 209 negated = true; 210 } 211 LogicNode ifTest = ifNode.condition(); 212 if (!(ifTest instanceof IntegerLessThanNode) && !(ifTest instanceof IntegerEqualsNode)) { 213 if (ifTest instanceof IntegerBelowNode) { 214 ifTest.getDebug().log("Ignored potential Counted loop at %s with |<|", loopBegin); 215 } 216 return false; 217 } 218 CompareNode lessThan = (CompareNode) ifTest; 219 Condition condition = null; 220 InductionVariable iv = null; 221 ValueNode limit = null; 222 if (isOutsideLoop(lessThan.getX())) { 223 iv = getInductionVariables().get(lessThan.getY()); 224 if (iv != null) { 225 condition = lessThan.condition().mirror(); 226 limit = lessThan.getX(); 227 } 228 } else if (isOutsideLoop(lessThan.getY())) { 229 iv = getInductionVariables().get(lessThan.getX()); 230 if (iv != null) { 231 condition = lessThan.condition(); 232 limit = lessThan.getY(); 233 } 234 } 235 if (condition == null) { 236 return false; 237 } 238 if (negated) { 239 condition = condition.negate(); 240 } 241 boolean oneOff = false; 242 switch (condition) { 243 case EQ: 244 return false; 245 case NE: { 246 if (!iv.isConstantStride() || Math.abs(iv.constantStride()) != 1) { 247 return false; 248 } 249 IntegerStamp initStamp = (IntegerStamp) iv.initNode().stamp(); 250 IntegerStamp limitStamp = (IntegerStamp) limit.stamp(); 251 if (iv.direction() == Direction.Up) { 252 if (initStamp.upperBound() > limitStamp.lowerBound()) { 253 return false; 254 } 255 } else if (iv.direction() == Direction.Down) { 256 if (initStamp.lowerBound() < limitStamp.upperBound()) { 257 return false; 258 } 259 } else { 260 return false; 261 } 262 break; 263 } 264 case LE: 265 oneOff = true; 266 if (iv.direction() != Direction.Up) { 267 return false; 268 } 269 break; 270 case LT: 271 if (iv.direction() != Direction.Up) { 272 return false; 273 } 274 break; 275 case GE: 276 oneOff = true; 277 if (iv.direction() != Direction.Down) { 278 return false; 279 } 280 break; 281 case GT: 282 if (iv.direction() != Direction.Down) { 283 return false; 284 } 285 break; 286 default: 287 throw GraalError.shouldNotReachHere(); 288 } 289 counted = new CountedLoopInfo(this, iv, ifNode, limit, oneOff, negated ? ifNode.falseSuccessor() : ifNode.trueSuccessor()); 290 return true; 291 } 292 return false; 293 } 294 295 public LoopsData loopsData() { 296 return data; 297 } 298 299 public void nodesInLoopBranch(NodeBitMap branchNodes, AbstractBeginNode branch) { 300 EconomicSet<AbstractBeginNode> blocks = EconomicSet.create(); 301 Collection<AbstractBeginNode> exits = new LinkedList<>(); 302 Queue<Block> work = new LinkedList<>(); 303 ControlFlowGraph cfg = loopsData().getCFG(); 304 work.add(cfg.blockFor(branch)); 305 while (!work.isEmpty()) { 306 Block b = work.remove(); 307 if (loop().getExits().contains(b)) { 308 assert !exits.contains(b.getBeginNode()); 309 exits.add(b.getBeginNode()); 310 } else if (blocks.add(b.getBeginNode())) { 311 Block d = b.getDominatedSibling(); 312 while (d != null) { 313 if (loop.getBlocks().contains(d)) { 314 work.add(d); 315 } 316 d = d.getDominatedSibling(); 317 } 318 } 319 } 320 LoopFragment.computeNodes(branchNodes, branch.graph(), blocks, exits); 321 } 322 323 public EconomicMap<Node, InductionVariable> getInductionVariables() { 324 if (ivs == null) { 325 ivs = findInductionVariables(this); 326 } 327 return ivs; 328 } 329 330 /** 331 * Collect all the basic induction variables for the loop and the find any induction variables 332 * which are derived from the basic ones. 333 * 334 * @param loop 335 * @return a map from node to induction variable 336 */ 337 private static EconomicMap<Node, InductionVariable> findInductionVariables(LoopEx loop) { 338 EconomicMap<Node, InductionVariable> ivs = EconomicMap.create(Equivalence.IDENTITY); 339 340 Queue<InductionVariable> scanQueue = new LinkedList<>(); 341 LoopBeginNode loopBegin = loop.loopBegin(); 342 AbstractEndNode forwardEnd = loopBegin.forwardEnd(); 343 for (PhiNode phi : loopBegin.valuePhis()) { 344 ValueNode backValue = phi.singleBackValueOrThis(); 345 if (backValue == phi) { 346 continue; 347 } 348 ValueNode stride = addSub(loop, backValue, phi); 349 if (stride != null) { 350 BasicInductionVariable biv = new BasicInductionVariable(loop, (ValuePhiNode) phi, phi.valueAt(forwardEnd), stride, (BinaryArithmeticNode<?>) backValue); 351 ivs.put(phi, biv); 352 scanQueue.add(biv); 353 } 354 } 355 356 while (!scanQueue.isEmpty()) { 357 InductionVariable baseIv = scanQueue.remove(); 358 ValueNode baseIvNode = baseIv.valueNode(); 359 for (ValueNode op : baseIvNode.usages().filter(ValueNode.class)) { 360 if (loop.isOutsideLoop(op)) { 361 continue; 362 } 363 if (op.usages().count() == 1 && op.usages().first() == baseIvNode) { 364 /* 365 * This is just the base induction variable increment with no other uses so 366 * don't bother reporting it. 367 */ 368 continue; 369 } 370 InductionVariable iv = null; 371 ValueNode offset = addSub(loop, op, baseIvNode); 372 ValueNode scale; 373 if (offset != null) { 374 iv = new DerivedOffsetInductionVariable(loop, baseIv, offset, (BinaryArithmeticNode<?>) op); 375 } else if (op instanceof NegateNode) { 376 iv = new DerivedScaledInductionVariable(loop, baseIv, (NegateNode) op); 377 } else if ((scale = mul(loop, op, baseIvNode)) != null) { 378 iv = new DerivedScaledInductionVariable(loop, baseIv, scale, op); 379 } else { 380 boolean isValidConvert = op instanceof PiNode || op instanceof SignExtendNode; 381 if (!isValidConvert && op instanceof ZeroExtendNode) { 382 IntegerStamp inputStamp = (IntegerStamp) ((ZeroExtendNode) op).getValue().stamp(); 383 isValidConvert = inputStamp.isPositive(); 384 } 385 386 if (isValidConvert) { 387 iv = new DerivedConvertedInductionVariable(loop, baseIv, op.stamp(), op); 388 } 389 } 390 391 if (iv != null) { 392 ivs.put(op, iv); 393 scanQueue.offer(iv); 394 } 395 } 396 } 397 return ivs; 398 } 399 400 private static ValueNode addSub(LoopEx loop, ValueNode op, ValueNode base) { 401 if (op.stamp() instanceof IntegerStamp && (op instanceof AddNode || op instanceof SubNode)) { 402 BinaryArithmeticNode<?> aritOp = (BinaryArithmeticNode<?>) op; 403 if (aritOp.getX() == base && loop.isOutsideLoop(aritOp.getY())) { 404 return aritOp.getY(); 405 } else if (aritOp.getY() == base && loop.isOutsideLoop(aritOp.getX())) { 406 return aritOp.getX(); 407 } 408 } 409 return null; 410 } 411 412 private static ValueNode mul(LoopEx loop, ValueNode op, ValueNode base) { 413 if (op instanceof MulNode) { 414 MulNode mul = (MulNode) op; 415 if (mul.getX() == base && loop.isOutsideLoop(mul.getY())) { 416 return mul.getY(); 417 } else if (mul.getY() == base && loop.isOutsideLoop(mul.getX())) { 418 return mul.getX(); 419 } 420 } 421 if (op instanceof LeftShiftNode) { 422 LeftShiftNode shift = (LeftShiftNode) op; 423 if (shift.getX() == base && shift.getY().isConstant()) { 424 return ConstantNode.forIntegerStamp(base.stamp(), 1 << shift.getY().asJavaConstant().asInt(), base.graph()); 425 } 426 } 427 return null; 428 } 429 430 /** 431 * Deletes any nodes created within the scope of this object that have no usages. 432 */ 433 public void deleteUnusedNodes() { 434 if (ivs != null) { 435 for (InductionVariable iv : ivs.getValues()) { 436 iv.deleteUnusedNodes(); 437 } 438 } 439 } 440 441 /** 442 * @return true if all nodes in the loop can be duplicated. 443 */ 444 public boolean canDuplicateLoop() { 445 for (Node node : inside().nodes()) { 446 if (node instanceof ControlFlowAnchored) { 447 return false; 448 } 449 if (node instanceof FrameState) { 450 FrameState frameState = (FrameState) node; 451 if (frameState.bci == BytecodeFrame.AFTER_EXCEPTION_BCI || frameState.bci == BytecodeFrame.UNWIND_BCI) { 452 return false; 453 } 454 } 455 } 456 return true; 457 } 458 }