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