1 /* 2 * Copyright (c) 2012, 2012, 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 24 25 package org.graalvm.compiler.loop.phases; 26 27 import static org.graalvm.compiler.core.common.GraalOptions.MaximumDesiredSize; 28 import static org.graalvm.compiler.loop.MathUtil.add; 29 import static org.graalvm.compiler.loop.MathUtil.sub; 30 31 import java.util.ArrayList; 32 import java.util.Iterator; 33 import java.util.List; 34 35 import org.graalvm.compiler.core.common.RetryableBailoutException; 36 import org.graalvm.compiler.core.common.calc.CanonicalCondition; 37 import org.graalvm.compiler.debug.DebugContext; 38 import org.graalvm.compiler.debug.GraalError; 39 import org.graalvm.compiler.graph.Graph.Mark; 40 import org.graalvm.compiler.graph.Node; 41 import org.graalvm.compiler.graph.Position; 42 import org.graalvm.compiler.loop.CountedLoopInfo; 43 import org.graalvm.compiler.loop.InductionVariable; 44 import org.graalvm.compiler.loop.InductionVariable.Direction; 45 import org.graalvm.compiler.loop.LoopEx; 46 import org.graalvm.compiler.loop.LoopFragmentInside; 47 import org.graalvm.compiler.loop.LoopFragmentWhole; 48 import org.graalvm.compiler.nodeinfo.InputType; 49 import org.graalvm.compiler.nodes.AbstractBeginNode; 50 import org.graalvm.compiler.nodes.AbstractEndNode; 51 import org.graalvm.compiler.nodes.AbstractMergeNode; 52 import org.graalvm.compiler.nodes.BeginNode; 53 import org.graalvm.compiler.nodes.ConstantNode; 54 import org.graalvm.compiler.nodes.ControlSplitNode; 55 import org.graalvm.compiler.nodes.EndNode; 56 import org.graalvm.compiler.nodes.FixedNode; 57 import org.graalvm.compiler.nodes.FixedWithNextNode; 58 import org.graalvm.compiler.nodes.IfNode; 59 import org.graalvm.compiler.nodes.LogicNode; 60 import org.graalvm.compiler.nodes.LoopBeginNode; 61 import org.graalvm.compiler.nodes.LoopExitNode; 62 import org.graalvm.compiler.nodes.PhiNode; 63 import org.graalvm.compiler.nodes.SafepointNode; 64 import org.graalvm.compiler.nodes.StructuredGraph; 65 import org.graalvm.compiler.nodes.ValueNode; 66 import org.graalvm.compiler.nodes.calc.CompareNode; 67 import org.graalvm.compiler.nodes.calc.ConditionalNode; 68 import org.graalvm.compiler.nodes.calc.IntegerLessThanNode; 69 import org.graalvm.compiler.nodes.extended.SwitchNode; 70 import org.graalvm.compiler.phases.common.CanonicalizerPhase; 71 import org.graalvm.compiler.phases.tiers.PhaseContext; 72 73 public abstract class LoopTransformations { 74 75 private LoopTransformations() { 76 // does not need to be instantiated 77 } 78 79 public static void peel(LoopEx loop) { 80 loop.inside().duplicate().insertBefore(loop); 81 loop.loopBegin().setLoopFrequency(Math.max(0.0, loop.loopBegin().loopFrequency() - 1)); 82 } 83 84 public static void fullUnroll(LoopEx loop, PhaseContext context, CanonicalizerPhase canonicalizer) { 85 // assert loop.isCounted(); //TODO (gd) strengthen : counted with known trip count 86 LoopBeginNode loopBegin = loop.loopBegin(); 87 StructuredGraph graph = loopBegin.graph(); 88 int initialNodeCount = graph.getNodeCount(); 89 while (!loopBegin.isDeleted()) { 90 Mark mark = graph.getMark(); 91 peel(loop); 92 canonicalizer.applyIncremental(graph, context, mark); 93 loop.invalidateFragments(); 94 if (graph.getNodeCount() > initialNodeCount + MaximumDesiredSize.getValue(graph.getOptions()) * 2) { 95 throw new RetryableBailoutException("FullUnroll : Graph seems to grow out of proportion"); 96 } 97 } 98 } 99 100 public static void unswitch(LoopEx loop, List<ControlSplitNode> controlSplitNodeSet) { 101 ControlSplitNode firstNode = controlSplitNodeSet.iterator().next(); 102 LoopFragmentWhole originalLoop = loop.whole(); 103 StructuredGraph graph = firstNode.graph(); 104 105 loop.loopBegin().incrementUnswitches(); 106 107 // create new control split out of loop 108 ControlSplitNode newControlSplit = (ControlSplitNode) firstNode.copyWithInputs(); 109 originalLoop.entryPoint().replaceAtPredecessor(newControlSplit); 110 111 /* 112 * The code below assumes that all of the control split nodes have the same successor 113 * structure, which should have been enforced by findUnswitchable. 114 */ 115 Iterator<Position> successors = firstNode.successorPositions().iterator(); 116 assert successors.hasNext(); 117 // original loop is used as first successor 118 Position firstPosition = successors.next(); 119 AbstractBeginNode originalLoopBegin = BeginNode.begin(originalLoop.entryPoint()); 120 firstPosition.set(newControlSplit, originalLoopBegin); 121 originalLoopBegin.setNodeSourcePosition(firstPosition.get(firstNode).getNodeSourcePosition()); 122 123 while (successors.hasNext()) { 124 Position position = successors.next(); 125 // create a new loop duplicate and connect it. 126 LoopFragmentWhole duplicateLoop = originalLoop.duplicate(); 127 AbstractBeginNode newBegin = BeginNode.begin(duplicateLoop.entryPoint()); 128 newBegin.setNodeSourcePosition(position.get(firstNode).getNodeSourcePosition()); 129 position.set(newControlSplit, newBegin); 130 131 // For each cloned ControlSplitNode, simplify the proper path 132 for (ControlSplitNode controlSplitNode : controlSplitNodeSet) { 133 ControlSplitNode duplicatedControlSplit = duplicateLoop.getDuplicatedNode(controlSplitNode); 134 if (duplicatedControlSplit.isAlive()) { 135 AbstractBeginNode survivingSuccessor = (AbstractBeginNode) position.get(duplicatedControlSplit); 136 survivingSuccessor.replaceAtUsages(InputType.Guard, newBegin); 137 graph.removeSplitPropagate(duplicatedControlSplit, survivingSuccessor); 138 } 139 } 140 } 141 // original loop is simplified last to avoid deleting controlSplitNode too early 142 for (ControlSplitNode controlSplitNode : controlSplitNodeSet) { 143 if (controlSplitNode.isAlive()) { 144 AbstractBeginNode survivingSuccessor = (AbstractBeginNode) firstPosition.get(controlSplitNode); 145 survivingSuccessor.replaceAtUsages(InputType.Guard, originalLoopBegin); 146 graph.removeSplitPropagate(controlSplitNode, survivingSuccessor); 147 } 148 } 149 150 // TODO (gd) probabilities need some amount of fixup.. (probably also in other transforms) 151 } 152 153 public static void partialUnroll(LoopEx loop) { 154 assert loop.loopBegin().isMainLoop(); 155 loop.loopBegin().graph().getDebug().log("LoopPartialUnroll %s", loop); 156 157 LoopFragmentInside newSegment = loop.inside().duplicate(); 158 newSegment.insertWithinAfter(loop); 159 160 } 161 162 // This function splits candidate loops into pre, main and post loops, 163 // dividing the iteration space to facilitate the majority of iterations 164 // being executed in a main loop, which will have RCE implemented upon it. 165 // The initial loop form is constrained to single entry/exit, but can have 166 // flow. The translation looks like: 167 // 168 // @formatter:off 169 // 170 // (Simple Loop entry) (Pre Loop Entry) 171 // | | 172 // (LoopBeginNode) (LoopBeginNode) 173 // | | 174 // (Loop Control Test)<------ ==> (Loop control Test)<------ 175 // / \ \ / \ \ 176 // (Loop Exit) (Loop Body) | (Loop Exit) (Loop Body) | 177 // | | | | | | 178 // (continue code) (Loop End) | if (M < length)* (Loop End) | 179 // \ / / \ \ / 180 // -----> / | -----> 181 // / if ( ... )* 182 // / / \ 183 // / / \ 184 // / / \ 185 // | / (Main Loop Entry) 186 // | | | 187 // | | (LoopBeginNode) 188 // | | | 189 // | | (Loop Control Test)<------ 190 // | | / \ \ 191 // | | (Loop Exit) (Loop Body) | 192 // \ \ | | | 193 // \ \ | (Loop End) | 194 // \ \ | \ / 195 // \ \ | ------> 196 // \ \ | 197 // (Main Loop Merge)* 198 // | 199 // (Post Loop Entry) 200 // | 201 // (LoopBeginNode) 202 // | 203 // (Loop Control Test)<----- 204 // / \ \ 205 // (Loop Exit) (Loop Body) | 206 // | | | 207 // (continue code) (Loop End) | 208 // \ / 209 // -----> 210 // 211 // Key: "*" = optional. 212 // @formatter:on 213 // 214 // The value "M" is the maximal value of the loop trip for the original 215 // loop. The value of "length" is applicable to the number of arrays found 216 // in the loop but is reduced if some or all of the arrays are known to be 217 // the same length as "M". The maximum number of tests can be equal to the 218 // number of arrays in the loop, where multiple instances of an array are 219 // subsumed into a single test for that arrays length. 220 // 221 // If the optional main loop entry tests are absent, the Pre Loop exit 222 // connects to the Main loops entry and there is no merge hanging off the 223 // main loops exit to converge flow from said tests. All split use data 224 // flow is mitigated through phi(s) in the main merge if present and 225 // passed through the main and post loop phi(s) from the originating pre 226 // loop with final phi(s) and data flow patched to the "continue code". 227 // The pre loop is constrained to one iteration for now and will likely 228 // be updated to produce vector alignment if applicable. 229 230 public static LoopBeginNode insertPrePostLoops(LoopEx loop) { 231 StructuredGraph graph = loop.loopBegin().graph(); 232 graph.getDebug().log("LoopTransformations.insertPrePostLoops %s", loop); 233 LoopFragmentWhole preLoop = loop.whole(); 234 CountedLoopInfo preCounted = loop.counted(); 235 IfNode preLimit = preCounted.getLimitTest(); 236 assert preLimit != null; 237 LoopBeginNode preLoopBegin = loop.loopBegin(); 238 InductionVariable preIv = preCounted.getCounter(); 239 LoopExitNode preLoopExitNode = preLoopBegin.getSingleLoopExit(); 240 FixedNode continuationNode = preLoopExitNode.next(); 241 242 // Each duplication is inserted after the original, ergo create the post loop first 243 LoopFragmentWhole mainLoop = preLoop.duplicate(); 244 LoopFragmentWhole postLoop = preLoop.duplicate(); 245 preLoopBegin.incrementSplits(); 246 preLoopBegin.incrementSplits(); 247 preLoopBegin.setPreLoop(); 248 graph.getDebug().dump(DebugContext.VERBOSE_LEVEL, graph, "After duplication"); 249 LoopBeginNode mainLoopBegin = mainLoop.getDuplicatedNode(preLoopBegin); 250 mainLoopBegin.setMainLoop(); 251 LoopBeginNode postLoopBegin = postLoop.getDuplicatedNode(preLoopBegin); 252 postLoopBegin.setPostLoop(); 253 254 EndNode postEndNode = getBlockEndAfterLoopExit(postLoopBegin); 255 AbstractMergeNode postMergeNode = postEndNode.merge(); 256 LoopExitNode postLoopExitNode = postLoopBegin.getSingleLoopExit(); 257 258 // Update the main loop phi initialization to carry from the pre loop 259 for (PhiNode prePhiNode : preLoopBegin.phis()) { 260 PhiNode mainPhiNode = mainLoop.getDuplicatedNode(prePhiNode); 261 mainPhiNode.setValueAt(0, prePhiNode); 262 } 263 264 EndNode mainEndNode = getBlockEndAfterLoopExit(mainLoopBegin); 265 AbstractMergeNode mainMergeNode = mainEndNode.merge(); 266 AbstractEndNode postEntryNode = postLoopBegin.forwardEnd(); 267 268 // In the case of no Bounds tests, we just flow right into the main loop 269 AbstractBeginNode mainLandingNode = BeginNode.begin(postEntryNode); 270 LoopExitNode mainLoopExitNode = mainLoopBegin.getSingleLoopExit(); 271 mainLoopExitNode.setNext(mainLandingNode); 272 preLoopExitNode.setNext(mainLoopBegin.forwardEnd()); 273 274 // Add and update any phi edges as per merge usage as needed and update usages 275 processPreLoopPhis(loop, mainLoop, postLoop); 276 continuationNode.predecessor().clearSuccessors(); 277 postLoopExitNode.setNext(continuationNode); 278 cleanupMerge(postMergeNode, postLoopExitNode); 279 cleanupMerge(mainMergeNode, mainLandingNode); 280 281 // Change the preLoop to execute one iteration for now 282 updateMainLoopLimit(preLimit, preIv, mainLoop); 283 updatePreLoopLimit(preLimit, preIv, preCounted); 284 preLoopBegin.setLoopFrequency(1); 285 mainLoopBegin.setLoopFrequency(Math.max(0.0, mainLoopBegin.loopFrequency() - 2)); 286 postLoopBegin.setLoopFrequency(Math.max(0.0, postLoopBegin.loopFrequency() - 1)); 287 288 // The pre and post loops don't require safepoints at all 289 for (SafepointNode safepoint : preLoop.nodes().filter(SafepointNode.class)) { 290 graph.removeFixed(safepoint); 291 } 292 for (SafepointNode safepoint : postLoop.nodes().filter(SafepointNode.class)) { 293 graph.removeFixed(safepoint); 294 } 295 graph.getDebug().dump(DebugContext.DETAILED_LEVEL, graph, "InsertPrePostLoops %s", loop); 296 return mainLoopBegin; 297 } 298 299 /** 300 * Cleanup the merge and remove the predecessors too. 301 */ 302 private static void cleanupMerge(AbstractMergeNode mergeNode, AbstractBeginNode landingNode) { 303 for (EndNode end : mergeNode.cfgPredecessors().snapshot()) { 304 mergeNode.removeEnd(end); 305 end.safeDelete(); 306 } 307 mergeNode.prepareDelete(landingNode); 308 mergeNode.safeDelete(); 309 } 310 311 private static void processPreLoopPhis(LoopEx preLoop, LoopFragmentWhole mainLoop, LoopFragmentWhole postLoop) { 312 // process phis for the post loop 313 LoopBeginNode preLoopBegin = preLoop.loopBegin(); 314 for (PhiNode prePhiNode : preLoopBegin.phis()) { 315 PhiNode postPhiNode = postLoop.getDuplicatedNode(prePhiNode); 316 PhiNode mainPhiNode = mainLoop.getDuplicatedNode(prePhiNode); 317 postPhiNode.setValueAt(0, mainPhiNode); 318 319 // Build a work list to update the pre loop phis to the post loops phis 320 for (Node usage : prePhiNode.usages().snapshot()) { 321 if (usage == mainPhiNode) { 322 continue; 323 } 324 if (preLoop.isOutsideLoop(usage)) { 325 usage.replaceFirstInput(prePhiNode, postPhiNode); 326 } 327 } 328 } 329 for (Node node : preLoop.inside().nodes()) { 330 for (Node externalUsage : node.usages().snapshot()) { 331 if (preLoop.isOutsideLoop(externalUsage)) { 332 Node postUsage = postLoop.getDuplicatedNode(node); 333 assert postUsage != null; 334 externalUsage.replaceFirstInput(node, postUsage); 335 } 336 } 337 } 338 } 339 340 /** 341 * Find the end of the block following the LoopExit. 342 */ 343 private static EndNode getBlockEndAfterLoopExit(LoopBeginNode curLoopBegin) { 344 FixedNode node = curLoopBegin.getSingleLoopExit().next(); 345 // Find the last node after the exit blocks starts 346 return getBlockEnd(node); 347 } 348 349 private static EndNode getBlockEnd(FixedNode node) { 350 FixedNode curNode = node; 351 while (curNode instanceof FixedWithNextNode) { 352 curNode = ((FixedWithNextNode) curNode).next(); 353 } 354 return (EndNode) curNode; 355 } 356 357 private static void updateMainLoopLimit(IfNode preLimit, InductionVariable preIv, LoopFragmentWhole mainLoop) { 358 // Update the main loops limit test to be different than the post loop 359 StructuredGraph graph = preLimit.graph(); 360 IfNode mainLimit = mainLoop.getDuplicatedNode(preLimit); 361 LogicNode ifTest = mainLimit.condition(); 362 CompareNode compareNode = (CompareNode) ifTest; 363 ValueNode prePhi = preIv.valueNode(); 364 ValueNode mainPhi = mainLoop.getDuplicatedNode(prePhi); 365 ValueNode preStride = preIv.strideNode(); 366 ValueNode mainStride; 367 if (preStride instanceof ConstantNode) { 368 mainStride = preStride; 369 } else { 370 mainStride = mainLoop.getDuplicatedNode(preStride); 371 } 372 // Fetch the bounds to pose lowering the range by one 373 ValueNode ub = null; 374 if (compareNode.getX() == mainPhi) { 375 ub = compareNode.getY(); 376 } else if (compareNode.getY() == mainPhi) { 377 ub = compareNode.getX(); 378 } else { 379 throw GraalError.shouldNotReachHere(); 380 } 381 382 // Preloop always performs at least one iteration, so remove that from the main loop. 383 ValueNode newLimit = sub(graph, ub, mainStride); 384 385 // Re-wire the condition with the new limit 386 compareNode.replaceFirstInput(ub, newLimit); 387 } 388 389 private static void updatePreLoopLimit(IfNode preLimit, InductionVariable preIv, CountedLoopInfo preCounted) { 390 // Update the pre loops limit test 391 StructuredGraph graph = preLimit.graph(); 392 LogicNode ifTest = preLimit.condition(); 393 CompareNode compareNode = (CompareNode) ifTest; 394 ValueNode prePhi = preIv.valueNode(); 395 // Make new limit one iteration 396 ValueNode initIv = preCounted.getStart(); 397 ValueNode newLimit = add(graph, initIv, preIv.strideNode()); 398 399 // Fetch the variable we are not replacing and configure the one we are 400 ValueNode ub; 401 if (compareNode.getX() == prePhi) { 402 ub = compareNode.getY(); 403 } else if (compareNode.getY() == prePhi) { 404 ub = compareNode.getX(); 405 } else { 406 throw GraalError.shouldNotReachHere(); 407 } 408 // Re-wire the condition with the new limit 409 if (preIv.direction() == Direction.Up) { 410 compareNode.replaceFirstInput(ub, graph.unique(new ConditionalNode(graph.unique(new IntegerLessThanNode(newLimit, ub)), newLimit, ub))); 411 } else { 412 compareNode.replaceFirstInput(ub, graph.unique(new ConditionalNode(graph.unique(new IntegerLessThanNode(ub, newLimit)), newLimit, ub))); 413 } 414 } 415 416 public static List<ControlSplitNode> findUnswitchable(LoopEx loop) { 417 List<ControlSplitNode> controls = null; 418 ValueNode invariantValue = null; 419 for (IfNode ifNode : loop.whole().nodes().filter(IfNode.class)) { 420 if (loop.isOutsideLoop(ifNode.condition())) { 421 if (controls == null) { 422 invariantValue = ifNode.condition(); 423 controls = new ArrayList<>(); 424 controls.add(ifNode); 425 } else if (ifNode.condition() == invariantValue) { 426 controls.add(ifNode); 427 } 428 } 429 } 430 if (controls == null) { 431 SwitchNode firstSwitch = null; 432 for (SwitchNode switchNode : loop.whole().nodes().filter(SwitchNode.class)) { 433 if (switchNode.successors().count() > 1 && loop.isOutsideLoop(switchNode.value())) { 434 if (controls == null) { 435 firstSwitch = switchNode; 436 invariantValue = switchNode.value(); 437 controls = new ArrayList<>(); 438 controls.add(switchNode); 439 } else if (switchNode.value() == invariantValue && firstSwitch.structureEquals(switchNode)) { 440 // Only collect switches which test the same values in the same order 441 controls.add(switchNode); 442 } 443 } 444 } 445 } 446 return controls; 447 } 448 449 public static boolean isUnrollableLoop(LoopEx loop) { 450 if (!loop.isCounted() || !loop.counted().getCounter().isConstantStride() || !loop.loop().getChildren().isEmpty()) { 451 return false; 452 } 453 LoopBeginNode loopBegin = loop.loopBegin(); 454 LogicNode condition = loop.counted().getLimitTest().condition(); 455 if (!(condition instanceof CompareNode)) { 456 return false; 457 } 458 if (((CompareNode) condition).condition() == CanonicalCondition.EQ) { 459 condition.getDebug().log(DebugContext.VERBOSE_LEVEL, "isUnrollableLoop %s condition unsupported %s ", loopBegin, ((CompareNode) condition).condition()); 460 return false; 461 } 462 if (loopBegin.isMainLoop() || loopBegin.isSimpleLoop()) { 463 // Flow-less loops to partial unroll for now. 3 blocks corresponds to an if that either 464 // exits or continues the loop. There might be fixed and floating work within the loop 465 // as well. 466 if (loop.loop().getBlocks().size() < 3) { 467 return true; 468 } 469 condition.getDebug().log(DebugContext.VERBOSE_LEVEL, "isUnrollableLoop %s too large to unroll %s ", loopBegin, loop.loop().getBlocks().size()); 470 } 471 return false; 472 } 473 }