< prev index next >
src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.loop.phases/src/org/graalvm/compiler/loop/phases/LoopTransformations.java
Print this page
rev 52509 : [mq]: graal2
*** 23,73 ****
package org.graalvm.compiler.loop.phases;
import static org.graalvm.compiler.core.common.GraalOptions.MaximumDesiredSize;
- import static org.graalvm.compiler.loop.MathUtil.add;
- import static org.graalvm.compiler.loop.MathUtil.sub;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
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.debug.GraalError;
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;
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.ConstantNode;
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.LoopExitNode;
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.CompareNode;
import org.graalvm.compiler.nodes.calc.ConditionalNode;
import org.graalvm.compiler.nodes.calc.IntegerLessThanNode;
import org.graalvm.compiler.nodes.extended.SwitchNode;
import org.graalvm.compiler.phases.common.CanonicalizerPhase;
import org.graalvm.compiler.phases.tiers.PhaseContext;
public abstract class LoopTransformations {
--- 23,72 ----
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.LoopExitNode;
+ 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.calc.IntegerLessThanNode;
+ import org.graalvm.compiler.nodes.extended.OpaqueNode;
import org.graalvm.compiler.nodes.extended.SwitchNode;
import org.graalvm.compiler.phases.common.CanonicalizerPhase;
import org.graalvm.compiler.phases.tiers.PhaseContext;
public abstract class LoopTransformations {
*** 148,163 ****
}
// TODO (gd) probabilities need some amount of fixup.. (probably also in other transforms)
}
! public static void partialUnroll(LoopEx loop) {
assert loop.loopBegin().isMainLoop();
loop.loopBegin().graph().getDebug().log("LoopPartialUnroll %s", loop);
LoopFragmentInside newSegment = loop.inside().duplicate();
! newSegment.insertWithinAfter(loop);
}
// This function splits candidate loops into pre, main and post loops,
// dividing the iteration space to facilitate the majority of iterations
--- 147,162 ----
}
// 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
*** 233,243 ****
LoopFragmentWhole preLoop = loop.whole();
CountedLoopInfo preCounted = loop.counted();
IfNode preLimit = preCounted.getLimitTest();
assert preLimit != null;
LoopBeginNode preLoopBegin = loop.loopBegin();
- InductionVariable preIv = preCounted.getCounter();
LoopExitNode preLoopExitNode = preLoopBegin.getSingleLoopExit();
FixedNode continuationNode = preLoopExitNode.next();
// Each duplication is inserted after the original, ergo create the post loop first
LoopFragmentWhole mainLoop = preLoop.duplicate();
--- 232,241 ----
*** 277,288 ****
postLoopExitNode.setNext(continuationNode);
cleanupMerge(postMergeNode, postLoopExitNode);
cleanupMerge(mainMergeNode, mainLandingNode);
// Change the preLoop to execute one iteration for now
! updateMainLoopLimit(preLimit, preIv, mainLoop);
! updatePreLoopLimit(preLimit, preIv, 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
--- 275,285 ----
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
*** 352,418 ****
curNode = ((FixedWithNextNode) curNode).next();
}
return (EndNode) curNode;
}
! private static void updateMainLoopLimit(IfNode preLimit, InductionVariable preIv, LoopFragmentWhole mainLoop) {
! // Update the main loops limit test to be different than the post loop
! StructuredGraph graph = preLimit.graph();
! IfNode mainLimit = mainLoop.getDuplicatedNode(preLimit);
! LogicNode ifTest = mainLimit.condition();
! CompareNode compareNode = (CompareNode) ifTest;
! ValueNode prePhi = preIv.valueNode();
! ValueNode mainPhi = mainLoop.getDuplicatedNode(prePhi);
! ValueNode preStride = preIv.strideNode();
! ValueNode mainStride;
! if (preStride instanceof ConstantNode) {
! mainStride = preStride;
! } else {
! mainStride = mainLoop.getDuplicatedNode(preStride);
! }
! // Fetch the bounds to pose lowering the range by one
! ValueNode ub = null;
! if (compareNode.getX() == mainPhi) {
! ub = compareNode.getY();
! } else if (compareNode.getY() == mainPhi) {
! ub = compareNode.getX();
! } else {
! throw GraalError.shouldNotReachHere();
! }
!
! // Preloop always performs at least one iteration, so remove that from the main loop.
! ValueNode newLimit = sub(graph, ub, mainStride);
!
! // Re-wire the condition with the new limit
! compareNode.replaceFirstInput(ub, newLimit);
! }
!
! private static void updatePreLoopLimit(IfNode preLimit, InductionVariable preIv, CountedLoopInfo preCounted) {
// Update the pre loops limit test
- StructuredGraph graph = preLimit.graph();
- LogicNode ifTest = preLimit.condition();
- CompareNode compareNode = (CompareNode) ifTest;
- ValueNode prePhi = preIv.valueNode();
// Make new limit one iteration
! ValueNode initIv = preCounted.getStart();
! ValueNode newLimit = add(graph, initIv, preIv.strideNode());
!
// Fetch the variable we are not replacing and configure the one we are
! ValueNode ub;
! if (compareNode.getX() == prePhi) {
! ub = compareNode.getY();
! } else if (compareNode.getY() == prePhi) {
! ub = compareNode.getX();
} else {
! throw GraalError.shouldNotReachHere();
}
// Re-wire the condition with the new limit
! if (preIv.direction() == Direction.Up) {
! compareNode.replaceFirstInput(ub, graph.unique(new ConditionalNode(graph.unique(new IntegerLessThanNode(newLimit, ub)), newLimit, ub)));
! } else {
! compareNode.replaceFirstInput(ub, graph.unique(new ConditionalNode(graph.unique(new IntegerLessThanNode(ub, newLimit)), newLimit, ub)));
! }
}
public static List<ControlSplitNode> findUnswitchable(LoopEx loop) {
List<ControlSplitNode> controls = null;
ValueNode invariantValue = null;
--- 349,374 ----
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();
! LogicNode entryCheck;
! if (preCounted.getDirection() == Direction.Up) {
! entryCheck = IntegerLessThanNode.create(newLimit, ub, NodeView.DEFAULT);
} else {
! entryCheck = IntegerLessThanNode.create(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;
*** 448,466 ****
--- 404,430 ----
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 (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) {
< prev index next >