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 }