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();
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) |
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
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()) {
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 }
|
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.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
78 public static void peel(LoopEx loop) {
79 loop.inside().duplicate().insertBefore(loop);
80 loop.loopBegin().setLoopFrequency(Math.max(0.0, loop.loopBegin().loopFrequency() - 1));
81 }
82
83 public static void fullUnroll(LoopEx loop, PhaseContext context, CanonicalizerPhase canonicalizer) {
84 // assert loop.isCounted(); //TODO (gd) strengthen : counted with known trip count
85 LoopBeginNode loopBegin = loop.loopBegin();
86 StructuredGraph graph = loopBegin.graph();
87 int initialNodeCount = graph.getNodeCount();
132 ControlSplitNode duplicatedControlSplit = duplicateLoop.getDuplicatedNode(controlSplitNode);
133 if (duplicatedControlSplit.isAlive()) {
134 AbstractBeginNode survivingSuccessor = (AbstractBeginNode) position.get(duplicatedControlSplit);
135 survivingSuccessor.replaceAtUsages(InputType.Guard, newBegin);
136 graph.removeSplitPropagate(duplicatedControlSplit, survivingSuccessor);
137 }
138 }
139 }
140 // original loop is simplified last to avoid deleting controlSplitNode too early
141 for (ControlSplitNode controlSplitNode : controlSplitNodeSet) {
142 if (controlSplitNode.isAlive()) {
143 AbstractBeginNode survivingSuccessor = (AbstractBeginNode) firstPosition.get(controlSplitNode);
144 survivingSuccessor.replaceAtUsages(InputType.Guard, originalLoopBegin);
145 graph.removeSplitPropagate(controlSplitNode, survivingSuccessor);
146 }
147 }
148
149 // TODO (gd) probabilities need some amount of fixup.. (probably also in other transforms)
150 }
151
152 public static void partialUnroll(LoopEx loop, EconomicMap<LoopBeginNode, OpaqueNode> opaqueUnrolledStrides) {
153 assert loop.loopBegin().isMainLoop();
154 loop.loopBegin().graph().getDebug().log("LoopPartialUnroll %s", loop);
155
156 LoopFragmentInside newSegment = loop.inside().duplicate();
157 newSegment.insertWithinAfter(loop, opaqueUnrolledStrides);
158
159 }
160
161 // This function splits candidate loops into pre, main and post loops,
162 // dividing the iteration space to facilitate the majority of iterations
163 // being executed in a main loop, which will have RCE implemented upon it.
164 // The initial loop form is constrained to single entry/exit, but can have
165 // flow. The translation looks like:
166 //
167 // @formatter:off
168 //
169 // (Simple Loop entry) (Pre Loop Entry)
170 // | |
171 // (LoopBeginNode) (LoopBeginNode)
172 // | |
173 // (Loop Control Test)<------ ==> (Loop control Test)<------
174 // / \ \ / \ \
175 // (Loop Exit) (Loop Body) | (Loop Exit) (Loop Body) |
176 // | | | | | |
177 // (continue code) (Loop End) | if (M < length)* (Loop End) |
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
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 }
289 for (SafepointNode safepoint : postLoop.nodes().filter(SafepointNode.class)) {
290 graph.removeFixed(safepoint);
291 }
292 graph.getDebug().dump(DebugContext.DETAILED_LEVEL, graph, "InsertPrePostLoops %s", loop);
293 return mainLoopBegin;
294 }
295
296 /**
297 * Cleanup the merge and remove the predecessors too.
298 */
299 private static void cleanupMerge(AbstractMergeNode mergeNode, AbstractBeginNode landingNode) {
300 for (EndNode end : mergeNode.cfgPredecessors().snapshot()) {
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) {
362 entryCheck = IntegerLessThanNode.create(newLimit, ub, NodeView.DEFAULT);
363 } else {
364 entryCheck = IntegerLessThanNode.create(ub, newLimit, NodeView.DEFAULT);
365 }
366 newLimit = ConditionalNode.create(entryCheck, newLimit, ub, NodeView.DEFAULT);
367 // Re-wire the condition with the new limit
368 CompareNode compareNode = (CompareNode) preCounted.getLimitTest().condition();
369 compareNode.replaceFirstInput(ub, compareNode.graph().addOrUniqueWithInputs(newLimit));
370 }
371
372 public static List<ControlSplitNode> findUnswitchable(LoopEx loop) {
373 List<ControlSplitNode> controls = null;
374 ValueNode invariantValue = null;
375 for (IfNode ifNode : loop.whole().nodes().filter(IfNode.class)) {
376 if (loop.isOutsideLoop(ifNode.condition())) {
377 if (controls == null) {
378 invariantValue = ifNode.condition();
379 controls = new ArrayList<>();
380 controls.add(ifNode);
381 } else if (ifNode.condition() == invariantValue) {
382 controls.add(ifNode);
383 }
384 }
385 }
386 if (controls == null) {
387 SwitchNode firstSwitch = null;
388 for (SwitchNode switchNode : loop.whole().nodes().filter(SwitchNode.class)) {
389 if (switchNode.successors().count() > 1 && loop.isOutsideLoop(switchNode.value())) {
390 if (controls == null) {
391 firstSwitch = switchNode;
392 invariantValue = switchNode.value();
393 controls = new ArrayList<>();
394 controls.add(switchNode);
395 } else if (switchNode.value() == invariantValue && firstSwitch.structureEquals(switchNode)) {
396 // Only collect switches which test the same values in the same order
397 controls.add(switchNode);
398 }
399 }
400 }
401 }
402 return controls;
403 }
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 }
|