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.LoopExitNode;
58 import org.graalvm.compiler.nodes.NodeView;
59 import org.graalvm.compiler.nodes.PhiNode;
60 import org.graalvm.compiler.nodes.SafepointNode;
61 import org.graalvm.compiler.nodes.StructuredGraph;
62 import org.graalvm.compiler.nodes.ValueNode;
63 import org.graalvm.compiler.nodes.calc.AddNode;
64 import org.graalvm.compiler.nodes.calc.CompareNode;
65 import org.graalvm.compiler.nodes.calc.ConditionalNode;
66 import org.graalvm.compiler.nodes.calc.IntegerLessThanNode;
67 import org.graalvm.compiler.nodes.extended.OpaqueNode;
68 import org.graalvm.compiler.nodes.extended.SwitchNode;
69 import org.graalvm.compiler.phases.common.CanonicalizerPhase;
70 import org.graalvm.compiler.phases.tiers.PhaseContext;
71
72 public abstract class LoopTransformations {
73
74 private LoopTransformations() {
75 // does not need to be instantiated
76 }
77
214 // loop. The value of "length" is applicable to the number of arrays found
215 // in the loop but is reduced if some or all of the arrays are known to be
216 // the same length as "M". The maximum number of tests can be equal to the
217 // number of arrays in the loop, where multiple instances of an array are
218 // subsumed into a single test for that arrays length.
219 //
220 // If the optional main loop entry tests are absent, the Pre Loop exit
221 // connects to the Main loops entry and there is no merge hanging off the
222 // main loops exit to converge flow from said tests. All split use data
223 // flow is mitigated through phi(s) in the main merge if present and
224 // passed through the main and post loop phi(s) from the originating pre
225 // loop with final phi(s) and data flow patched to the "continue code".
226 // The pre loop is constrained to one iteration for now and will likely
227 // be updated to produce vector alignment if applicable.
228
229 public static LoopBeginNode insertPrePostLoops(LoopEx loop) {
230 StructuredGraph graph = loop.loopBegin().graph();
231 graph.getDebug().log("LoopTransformations.insertPrePostLoops %s", loop);
232 LoopFragmentWhole preLoop = loop.whole();
233 CountedLoopInfo preCounted = loop.counted();
234 IfNode preLimit = preCounted.getLimitTest();
235 assert preLimit != null;
236 LoopBeginNode preLoopBegin = loop.loopBegin();
237 LoopExitNode preLoopExitNode = preLoopBegin.getSingleLoopExit();
238 FixedNode continuationNode = preLoopExitNode.next();
239
240 // Each duplication is inserted after the original, ergo create the post loop first
241 LoopFragmentWhole mainLoop = preLoop.duplicate();
242 LoopFragmentWhole postLoop = preLoop.duplicate();
243 preLoopBegin.incrementSplits();
244 preLoopBegin.incrementSplits();
245 preLoopBegin.setPreLoop();
246 graph.getDebug().dump(DebugContext.VERBOSE_LEVEL, graph, "After duplication");
247 LoopBeginNode mainLoopBegin = mainLoop.getDuplicatedNode(preLoopBegin);
248 mainLoopBegin.setMainLoop();
249 LoopBeginNode postLoopBegin = postLoop.getDuplicatedNode(preLoopBegin);
250 postLoopBegin.setPostLoop();
251
252 EndNode postEndNode = getBlockEndAfterLoopExit(postLoopBegin);
253 AbstractMergeNode postMergeNode = postEndNode.merge();
254 LoopExitNode postLoopExitNode = postLoopBegin.getSingleLoopExit();
255
256 // Update the main loop phi initialization to carry from the pre loop
257 for (PhiNode prePhiNode : preLoopBegin.phis()) {
258 PhiNode mainPhiNode = mainLoop.getDuplicatedNode(prePhiNode);
259 mainPhiNode.setValueAt(0, prePhiNode);
260 }
261
262 EndNode mainEndNode = getBlockEndAfterLoopExit(mainLoopBegin);
263 AbstractMergeNode mainMergeNode = mainEndNode.merge();
264 AbstractEndNode postEntryNode = postLoopBegin.forwardEnd();
265
266 // In the case of no Bounds tests, we just flow right into the main loop
267 AbstractBeginNode mainLandingNode = BeginNode.begin(postEntryNode);
268 LoopExitNode mainLoopExitNode = mainLoopBegin.getSingleLoopExit();
269 mainLoopExitNode.setNext(mainLandingNode);
270 preLoopExitNode.setNext(mainLoopBegin.forwardEnd());
271
272 // Add and update any phi edges as per merge usage as needed and update usages
273 processPreLoopPhis(loop, mainLoop, postLoop);
274 continuationNode.predecessor().clearSuccessors();
275 postLoopExitNode.setNext(continuationNode);
276 cleanupMerge(postMergeNode, postLoopExitNode);
277 cleanupMerge(mainMergeNode, mainLandingNode);
278
279 // Change the preLoop to execute one iteration for now
280 updatePreLoopLimit(preCounted);
281 preLoopBegin.setLoopFrequency(1);
282 mainLoopBegin.setLoopFrequency(Math.max(0.0, mainLoopBegin.loopFrequency() - 2));
283 postLoopBegin.setLoopFrequency(Math.max(0.0, postLoopBegin.loopFrequency() - 1));
284
285 // The pre and post loops don't require safepoints at all
286 for (SafepointNode safepoint : preLoop.nodes().filter(SafepointNode.class)) {
287 graph.removeFixed(safepoint);
288 }
320 }
321 if (preLoop.isOutsideLoop(usage)) {
322 usage.replaceFirstInput(prePhiNode, postPhiNode);
323 }
324 }
325 }
326 for (Node node : preLoop.inside().nodes()) {
327 for (Node externalUsage : node.usages().snapshot()) {
328 if (preLoop.isOutsideLoop(externalUsage)) {
329 Node postUsage = postLoop.getDuplicatedNode(node);
330 assert postUsage != null;
331 externalUsage.replaceFirstInput(node, postUsage);
332 }
333 }
334 }
335 }
336
337 /**
338 * Find the end of the block following the LoopExit.
339 */
340 private static EndNode getBlockEndAfterLoopExit(LoopBeginNode curLoopBegin) {
341 FixedNode node = curLoopBegin.getSingleLoopExit().next();
342 // Find the last node after the exit blocks starts
343 return getBlockEnd(node);
344 }
345
346 private static EndNode getBlockEnd(FixedNode node) {
347 FixedNode curNode = node;
348 while (curNode instanceof FixedWithNextNode) {
349 curNode = ((FixedWithNextNode) curNode).next();
350 }
351 return (EndNode) curNode;
352 }
353
354 private static void updatePreLoopLimit(CountedLoopInfo preCounted) {
355 // Update the pre loops limit test
356 // Make new limit one iteration
357 ValueNode newLimit = AddNode.add(preCounted.getStart(), preCounted.getCounter().strideNode(), NodeView.DEFAULT);
358 // Fetch the variable we are not replacing and configure the one we are
359 ValueNode ub = preCounted.getLimit();
360 LogicNode entryCheck;
361 if (preCounted.getDirection() == Direction.Up) {
404
405 public static boolean isUnrollableLoop(LoopEx loop) {
406 if (!loop.isCounted() || !loop.counted().getCounter().isConstantStride() || !loop.loop().getChildren().isEmpty()) {
407 return false;
408 }
409 assert loop.counted().getDirection() != null;
410 LoopBeginNode loopBegin = loop.loopBegin();
411 LogicNode condition = loop.counted().getLimitTest().condition();
412 if (!(condition instanceof CompareNode)) {
413 return false;
414 }
415 if (((CompareNode) condition).condition() == CanonicalCondition.EQ) {
416 condition.getDebug().log(DebugContext.VERBOSE_LEVEL, "isUnrollableLoop %s condition unsupported %s ", loopBegin, ((CompareNode) condition).condition());
417 return false;
418 }
419 long stride = loop.counted().getCounter().constantStride();
420 try {
421 Math.addExact(stride, stride);
422 } catch (ArithmeticException ae) {
423 condition.getDebug().log(DebugContext.VERBOSE_LEVEL, "isUnrollableLoop %s doubling the stride overflows %d", loopBegin, stride);
424 return false;
425 }
426 if (loopBegin.isMainLoop() || loopBegin.isSimpleLoop()) {
427 // Flow-less loops to partial unroll for now. 3 blocks corresponds to an if that either
428 // exits or continues the loop. There might be fixed and floating work within the loop
429 // as well.
430 if (loop.loop().getBlocks().size() < 3) {
431 return true;
432 }
433 condition.getDebug().log(DebugContext.VERBOSE_LEVEL, "isUnrollableLoop %s too large to unroll %s ", loopBegin, loop.loop().getBlocks().size());
434 }
435 return false;
436 }
437 }
|
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.phases.common.CanonicalizerPhase;
69 import org.graalvm.compiler.phases.tiers.PhaseContext;
70
71 public abstract class LoopTransformations {
72
73 private LoopTransformations() {
74 // does not need to be instantiated
75 }
76
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 }
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) {
406
407 public static boolean isUnrollableLoop(LoopEx loop) {
408 if (!loop.isCounted() || !loop.counted().getCounter().isConstantStride() || !loop.loop().getChildren().isEmpty()) {
409 return false;
410 }
411 assert loop.counted().getDirection() != null;
412 LoopBeginNode loopBegin = loop.loopBegin();
413 LogicNode condition = loop.counted().getLimitTest().condition();
414 if (!(condition instanceof CompareNode)) {
415 return false;
416 }
417 if (((CompareNode) condition).condition() == CanonicalCondition.EQ) {
418 condition.getDebug().log(DebugContext.VERBOSE_LEVEL, "isUnrollableLoop %s condition unsupported %s ", loopBegin, ((CompareNode) condition).condition());
419 return false;
420 }
421 long stride = loop.counted().getCounter().constantStride();
422 try {
423 Math.addExact(stride, stride);
424 } catch (ArithmeticException ae) {
425 condition.getDebug().log(DebugContext.VERBOSE_LEVEL, "isUnrollableLoop %s doubling the stride overflows %d", loopBegin, stride);
426 return false;
427 }
428 if (!loop.canDuplicateLoop()) {
429 return false;
430 }
431 if (loopBegin.isMainLoop() || loopBegin.isSimpleLoop()) {
432 // Flow-less loops to partial unroll for now. 3 blocks corresponds to an if that either
433 // exits or continues the loop. There might be fixed and floating work within the loop
434 // as well.
435 if (loop.loop().getBlocks().size() < 3) {
436 return true;
437 }
438 condition.getDebug().log(DebugContext.VERBOSE_LEVEL, "isUnrollableLoop %s too large to unroll %s ", loopBegin, loop.loop().getBlocks().size());
439 }
440 return false;
441 }
442 }
|