src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.loop.phases/src/org/graalvm/compiler/loop/phases/LoopTransformations.java
/*
* Copyright (c) 2012, 2018, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation.
*
* This code is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
* version 2 for more details (a copy is included in the LICENSE file that
* accompanied this code).
*
* You should have received a copy of the GNU General Public License version
* 2 along with this work; if not, write to the Free Software Foundation,
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
*
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
* or visit www.oracle.com if you need additional information or have any
* questions.
*/
package org.graalvm.compiler.loop.phases;
import static org.graalvm.compiler.core.common.GraalOptions.MaximumDesiredSize;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import jdk.internal.vm.compiler.collections.EconomicMap;
import org.graalvm.compiler.core.common.RetryableBailoutException;
import org.graalvm.compiler.core.common.calc.CanonicalCondition;
import org.graalvm.compiler.debug.DebugContext;
import org.graalvm.compiler.graph.Graph.Mark;
import org.graalvm.compiler.graph.Node;
import org.graalvm.compiler.graph.Position;
import org.graalvm.compiler.loop.CountedLoopInfo;
import org.graalvm.compiler.loop.InductionVariable.Direction;
import org.graalvm.compiler.loop.LoopEx;
import org.graalvm.compiler.loop.LoopFragmentInside;
import org.graalvm.compiler.loop.LoopFragmentWhole;
import org.graalvm.compiler.nodeinfo.InputType;
import org.graalvm.compiler.nodes.AbstractBeginNode;
import org.graalvm.compiler.nodes.AbstractEndNode;
import org.graalvm.compiler.nodes.AbstractMergeNode;
import org.graalvm.compiler.nodes.BeginNode;
import org.graalvm.compiler.nodes.ControlSplitNode;
import org.graalvm.compiler.nodes.EndNode;
import org.graalvm.compiler.nodes.FixedNode;
import org.graalvm.compiler.nodes.FixedWithNextNode;
import org.graalvm.compiler.nodes.IfNode;
import org.graalvm.compiler.nodes.LogicNode;
import org.graalvm.compiler.nodes.LoopBeginNode;
import org.graalvm.compiler.nodes.NodeView;
import org.graalvm.compiler.nodes.PhiNode;
import org.graalvm.compiler.nodes.SafepointNode;
import org.graalvm.compiler.nodes.StructuredGraph;
import org.graalvm.compiler.nodes.ValueNode;
import org.graalvm.compiler.nodes.calc.AddNode;
import org.graalvm.compiler.nodes.calc.CompareNode;
import org.graalvm.compiler.nodes.calc.ConditionalNode;
import org.graalvm.compiler.nodes.extended.OpaqueNode;
import org.graalvm.compiler.nodes.extended.SwitchNode;
import org.graalvm.compiler.nodes.spi.CoreProviders;
import org.graalvm.compiler.nodes.util.IntegerHelper;
import org.graalvm.compiler.phases.common.CanonicalizerPhase;
public abstract class LoopTransformations {
private LoopTransformations() {
// does not need to be instantiated
}
public static void peel(LoopEx loop) {
loop.inside().duplicate().insertBefore(loop);
loop.loopBegin().setLoopFrequency(Math.max(0.0, loop.loopBegin().loopFrequency() - 1));
}
public static void fullUnroll(LoopEx loop, CoreProviders context, CanonicalizerPhase canonicalizer) {
// assert loop.isCounted(); //TODO (gd) strengthen : counted with known trip count
LoopBeginNode loopBegin = loop.loopBegin();
StructuredGraph graph = loopBegin.graph();
int initialNodeCount = graph.getNodeCount();
while (!loopBegin.isDeleted()) {
Mark mark = graph.getMark();
peel(loop);
canonicalizer.applyIncremental(graph, context, mark);
loop.invalidateFragments();
if (graph.getNodeCount() > initialNodeCount + MaximumDesiredSize.getValue(graph.getOptions()) * 2) {
throw new RetryableBailoutException("FullUnroll : Graph seems to grow out of proportion");
}
}
}
public static void unswitch(LoopEx loop, List<ControlSplitNode> controlSplitNodeSet) {
ControlSplitNode firstNode = controlSplitNodeSet.iterator().next();
LoopFragmentWhole originalLoop = loop.whole();
StructuredGraph graph = firstNode.graph();
loop.loopBegin().incrementUnswitches();
// create new control split out of loop
ControlSplitNode newControlSplit = (ControlSplitNode) firstNode.copyWithInputs();
originalLoop.entryPoint().replaceAtPredecessor(newControlSplit);
/*
* The code below assumes that all of the control split nodes have the same successor
* structure, which should have been enforced by findUnswitchable.
*/
Iterator<Position> successors = firstNode.successorPositions().iterator();
assert successors.hasNext();
// original loop is used as first successor
Position firstPosition = successors.next();
AbstractBeginNode originalLoopBegin = BeginNode.begin(originalLoop.entryPoint());
firstPosition.set(newControlSplit, originalLoopBegin);
originalLoopBegin.setNodeSourcePosition(firstPosition.get(firstNode).getNodeSourcePosition());
while (successors.hasNext()) {
Position position = successors.next();
// create a new loop duplicate and connect it.
LoopFragmentWhole duplicateLoop = originalLoop.duplicate();
AbstractBeginNode newBegin = BeginNode.begin(duplicateLoop.entryPoint());
newBegin.setNodeSourcePosition(position.get(firstNode).getNodeSourcePosition());
position.set(newControlSplit, newBegin);
// For each cloned ControlSplitNode, simplify the proper path
for (ControlSplitNode controlSplitNode : controlSplitNodeSet) {
ControlSplitNode duplicatedControlSplit = duplicateLoop.getDuplicatedNode(controlSplitNode);
if (duplicatedControlSplit.isAlive()) {
AbstractBeginNode survivingSuccessor = (AbstractBeginNode) position.get(duplicatedControlSplit);
survivingSuccessor.replaceAtUsages(InputType.Guard, newBegin);
graph.removeSplitPropagate(duplicatedControlSplit, survivingSuccessor);
}
}
}
// original loop is simplified last to avoid deleting controlSplitNode too early
for (ControlSplitNode controlSplitNode : controlSplitNodeSet) {
if (controlSplitNode.isAlive()) {
AbstractBeginNode survivingSuccessor = (AbstractBeginNode) firstPosition.get(controlSplitNode);
survivingSuccessor.replaceAtUsages(InputType.Guard, originalLoopBegin);
graph.removeSplitPropagate(controlSplitNode, survivingSuccessor);
}
}
// TODO (gd) probabilities need some amount of fixup.. (probably also in other transforms)
}
public static void partialUnroll(LoopEx loop, EconomicMap<LoopBeginNode, OpaqueNode> opaqueUnrolledStrides) {
assert loop.loopBegin().isMainLoop();
loop.loopBegin().graph().getDebug().log("LoopPartialUnroll %s", loop);
LoopFragmentInside newSegment = loop.inside().duplicate();
newSegment.insertWithinAfter(loop, opaqueUnrolledStrides);
}
// This function splits candidate loops into pre, main and post loops,
// dividing the iteration space to facilitate the majority of iterations
// being executed in a main loop, which will have RCE implemented upon it.
// The initial loop form is constrained to single entry/exit, but can have
// flow. The translation looks like:
//
// @formatter:off
//
// (Simple Loop entry) (Pre Loop Entry)
// | |
// (LoopBeginNode) (LoopBeginNode)
// | |
// (Loop Control Test)<------ ==> (Loop control Test)<------
// / \ \ / \ \
// (Loop Exit) (Loop Body) | (Loop Exit) (Loop Body) |
// | | | | | |
// (continue code) (Loop End) | if (M < length)* (Loop End) |
// \ / / \ \ /
// -----> / | ----->
// / if ( ... )*
// / / \
// / / \
// / / \
// | / (Main Loop Entry)
// | | |
// | | (LoopBeginNode)
// | | |
// | | (Loop Control Test)<------
// | | / \ \
// | | (Loop Exit) (Loop Body) |
// \ \ | | |
// \ \ | (Loop End) |
// \ \ | \ /
// \ \ | ------>
// \ \ |
// (Main Loop Merge)*
// |
// (Post Loop Entry)
// |
// (LoopBeginNode)
// |
// (Loop Control Test)<-----
// / \ \
// (Loop Exit) (Loop Body) |
// | | |
// (continue code) (Loop End) |
// \ /
// ----->
//
// Key: "*" = optional.
// @formatter:on
//
// The value "M" is the maximal value of the loop trip for the original
// loop. The value of "length" is applicable to the number of arrays found
// in the loop but is reduced if some or all of the arrays are known to be
// the same length as "M". The maximum number of tests can be equal to the
// number of arrays in the loop, where multiple instances of an array are
// subsumed into a single test for that arrays length.
//
// If the optional main loop entry tests are absent, the Pre Loop exit
// connects to the Main loops entry and there is no merge hanging off the
// main loops exit to converge flow from said tests. All split use data
// flow is mitigated through phi(s) in the main merge if present and
// passed through the main and post loop phi(s) from the originating pre
// loop with final phi(s) and data flow patched to the "continue code".
// The pre loop is constrained to one iteration for now and will likely
// be updated to produce vector alignment if applicable.
public static LoopBeginNode insertPrePostLoops(LoopEx loop) {
StructuredGraph graph = loop.loopBegin().graph();
graph.getDebug().log("LoopTransformations.insertPrePostLoops %s", loop);
LoopFragmentWhole preLoop = loop.whole();
CountedLoopInfo preCounted = loop.counted();
LoopBeginNode preLoopBegin = loop.loopBegin();
AbstractBeginNode preLoopExitNode = preCounted.getCountedExit();
assert preLoop.nodes().contains(preLoopBegin);
assert preLoop.nodes().contains(preLoopExitNode);
// Each duplication is inserted after the original, ergo create the post loop first
LoopFragmentWhole mainLoop = preLoop.duplicate();
LoopFragmentWhole postLoop = preLoop.duplicate();
preLoopBegin.incrementSplits();
preLoopBegin.incrementSplits();
preLoopBegin.setPreLoop();
graph.getDebug().dump(DebugContext.VERBOSE_LEVEL, graph, "After duplication");
LoopBeginNode mainLoopBegin = mainLoop.getDuplicatedNode(preLoopBegin);
mainLoopBegin.setMainLoop();
LoopBeginNode postLoopBegin = postLoop.getDuplicatedNode(preLoopBegin);
postLoopBegin.setPostLoop();
AbstractBeginNode postLoopExitNode = postLoop.getDuplicatedNode(preLoopExitNode);
EndNode postEndNode = getBlockEndAfterLoopExit(postLoopExitNode);
AbstractMergeNode postMergeNode = postEndNode.merge();
// Update the main loop phi initialization to carry from the pre loop
for (PhiNode prePhiNode : preLoopBegin.phis()) {
PhiNode mainPhiNode = mainLoop.getDuplicatedNode(prePhiNode);
mainPhiNode.setValueAt(0, prePhiNode);
}
AbstractBeginNode mainLoopExitNode = mainLoop.getDuplicatedNode(preLoopExitNode);
EndNode mainEndNode = getBlockEndAfterLoopExit(mainLoopExitNode);
AbstractMergeNode mainMergeNode = mainEndNode.merge();
AbstractEndNode postEntryNode = postLoopBegin.forwardEnd();
// Exits have been merged, find the continuation below the merge
FixedNode continuationNode = mainMergeNode.next();
// In the case of no Bounds tests, we just flow right into the main loop
AbstractBeginNode mainLandingNode = BeginNode.begin(postEntryNode);
mainLoopExitNode.setNext(mainLandingNode);
preLoopExitNode.setNext(mainLoopBegin.forwardEnd());
// Add and update any phi edges as per merge usage as needed and update usages
processPreLoopPhis(loop, mainLoop, postLoop);
continuationNode.predecessor().clearSuccessors();
postLoopExitNode.setNext(continuationNode);
cleanupMerge(postMergeNode, postLoopExitNode);
cleanupMerge(mainMergeNode, mainLandingNode);
// Change the preLoop to execute one iteration for now
updatePreLoopLimit(preCounted);
preLoopBegin.setLoopFrequency(1);
mainLoopBegin.setLoopFrequency(Math.max(0.0, mainLoopBegin.loopFrequency() - 2));
postLoopBegin.setLoopFrequency(Math.max(0.0, postLoopBegin.loopFrequency() - 1));
// The pre and post loops don't require safepoints at all
for (SafepointNode safepoint : preLoop.nodes().filter(SafepointNode.class)) {
graph.removeFixed(safepoint);
}
for (SafepointNode safepoint : postLoop.nodes().filter(SafepointNode.class)) {
graph.removeFixed(safepoint);
}
graph.getDebug().dump(DebugContext.DETAILED_LEVEL, graph, "InsertPrePostLoops %s", loop);
return mainLoopBegin;
}
/**
* Cleanup the merge and remove the predecessors too.
*/
private static void cleanupMerge(AbstractMergeNode mergeNode, AbstractBeginNode landingNode) {
for (EndNode end : mergeNode.cfgPredecessors().snapshot()) {
mergeNode.removeEnd(end);
end.safeDelete();
}
mergeNode.prepareDelete(landingNode);
mergeNode.safeDelete();
}
private static void processPreLoopPhis(LoopEx preLoop, LoopFragmentWhole mainLoop, LoopFragmentWhole postLoop) {
// process phis for the post loop
LoopBeginNode preLoopBegin = preLoop.loopBegin();
for (PhiNode prePhiNode : preLoopBegin.phis()) {
PhiNode postPhiNode = postLoop.getDuplicatedNode(prePhiNode);
PhiNode mainPhiNode = mainLoop.getDuplicatedNode(prePhiNode);
postPhiNode.setValueAt(0, mainPhiNode);
// Build a work list to update the pre loop phis to the post loops phis
for (Node usage : prePhiNode.usages().snapshot()) {
if (usage == mainPhiNode) {
continue;
}
if (preLoop.isOutsideLoop(usage)) {
usage.replaceFirstInput(prePhiNode, postPhiNode);
}
}
}
for (Node node : preLoop.inside().nodes()) {
for (Node externalUsage : node.usages().snapshot()) {
if (preLoop.isOutsideLoop(externalUsage)) {
Node postUsage = postLoop.getDuplicatedNode(node);
assert postUsage != null;
externalUsage.replaceFirstInput(node, postUsage);
}
}
}
}
/**
* Find the end of the block following the LoopExit.
*/
private static EndNode getBlockEndAfterLoopExit(AbstractBeginNode exit) {
FixedNode node = exit.next();
// Find the last node after the exit blocks starts
return getBlockEnd(node);
}
private static EndNode getBlockEnd(FixedNode node) {
FixedNode curNode = node;
while (curNode instanceof FixedWithNextNode) {
curNode = ((FixedWithNextNode) curNode).next();
}
return (EndNode) curNode;
}
private static void updatePreLoopLimit(CountedLoopInfo preCounted) {
// Update the pre loops limit test
// Make new limit one iteration
ValueNode newLimit = AddNode.add(preCounted.getStart(), preCounted.getCounter().strideNode(), NodeView.DEFAULT);
// Fetch the variable we are not replacing and configure the one we are
ValueNode ub = preCounted.getLimit();
IntegerHelper helper = preCounted.getCounterIntegerHelper();
LogicNode entryCheck;
if (preCounted.getDirection() == Direction.Up) {
entryCheck = helper.createCompareNode(newLimit, ub, NodeView.DEFAULT);
} else {
entryCheck = helper.createCompareNode(ub, newLimit, NodeView.DEFAULT);
}
newLimit = ConditionalNode.create(entryCheck, newLimit, ub, NodeView.DEFAULT);
// Re-wire the condition with the new limit
CompareNode compareNode = (CompareNode) preCounted.getLimitTest().condition();
compareNode.replaceFirstInput(ub, compareNode.graph().addOrUniqueWithInputs(newLimit));
}
public static List<ControlSplitNode> findUnswitchable(LoopEx loop) {
List<ControlSplitNode> controls = null;
ValueNode invariantValue = null;
for (IfNode ifNode : loop.whole().nodes().filter(IfNode.class)) {
if (loop.isOutsideLoop(ifNode.condition())) {
if (controls == null) {
invariantValue = ifNode.condition();
controls = new ArrayList<>();
controls.add(ifNode);
} else if (ifNode.condition() == invariantValue) {
controls.add(ifNode);
}
}
}
if (controls == null) {
SwitchNode firstSwitch = null;
for (SwitchNode switchNode : loop.whole().nodes().filter(SwitchNode.class)) {
if (switchNode.successors().count() > 1 && loop.isOutsideLoop(switchNode.value())) {
if (controls == null) {
firstSwitch = switchNode;
invariantValue = switchNode.value();
controls = new ArrayList<>();
controls.add(switchNode);
} else if (switchNode.value() == invariantValue) {
// Fortify: Suppress Null Dereference false positive
assert firstSwitch != null;
if (firstSwitch.structureEquals(switchNode)) {
// Only collect switches which test the same values in the same order
controls.add(switchNode);
}
}
}
}
}
return controls;
}
public static boolean isUnrollableLoop(LoopEx loop) {
if (!loop.isCounted() || !loop.counted().getCounter().isConstantStride() || !loop.loop().getChildren().isEmpty()) {
return false;
}
assert loop.counted().getDirection() != null;
LoopBeginNode loopBegin = loop.loopBegin();
LogicNode condition = loop.counted().getLimitTest().condition();
if (!(condition instanceof CompareNode)) {
return false;
}
if (((CompareNode) condition).condition() == CanonicalCondition.EQ) {
condition.getDebug().log(DebugContext.VERBOSE_LEVEL, "isUnrollableLoop %s condition unsupported %s ", loopBegin, ((CompareNode) condition).condition());
return false;
}
long stride = loop.counted().getCounter().constantStride();
try {
Math.addExact(stride, stride);
} catch (ArithmeticException ae) {
condition.getDebug().log(DebugContext.VERBOSE_LEVEL, "isUnrollableLoop %s doubling the stride overflows %d", loopBegin, stride);
return false;
}
if (!loop.canDuplicateLoop()) {
return false;
}
if (loopBegin.isMainLoop() || loopBegin.isSimpleLoop()) {
// Flow-less loops to partial unroll for now. 3 blocks corresponds to an if that either
// exits or continues the loop. There might be fixed and floating work within the loop
// as well.
if (loop.loop().getBlocks().size() < 3) {
return true;
}
condition.getDebug().log(DebugContext.VERBOSE_LEVEL, "isUnrollableLoop %s too large to unroll %s ", loopBegin, loop.loop().getBlocks().size());
}
return false;
}
}