< prev index next >

src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.loop/src/org/graalvm/compiler/loop/CountedLoopInfo.java

Print this page
rev 56282 : [mq]: graal

*** 27,37 **** import static java.lang.Math.abs; import static org.graalvm.compiler.loop.MathUtil.unsignedDivBefore; import static org.graalvm.compiler.nodes.calc.BinaryArithmeticNode.add; import static org.graalvm.compiler.nodes.calc.BinaryArithmeticNode.sub; - import org.graalvm.compiler.core.common.NumUtil; import org.graalvm.compiler.core.common.type.IntegerStamp; import org.graalvm.compiler.core.common.type.Stamp; import org.graalvm.compiler.core.common.util.UnsignedLong; import org.graalvm.compiler.debug.DebugCloseable; import org.graalvm.compiler.loop.InductionVariable.Direction; --- 27,36 ----
*** 42,55 **** import org.graalvm.compiler.nodes.LogicNode; import org.graalvm.compiler.nodes.NodeView; import org.graalvm.compiler.nodes.StructuredGraph; import org.graalvm.compiler.nodes.ValueNode; import org.graalvm.compiler.nodes.calc.ConditionalNode; - import org.graalvm.compiler.nodes.calc.IntegerLessThanNode; import org.graalvm.compiler.nodes.calc.NegateNode; import org.graalvm.compiler.nodes.extended.GuardingNode; import org.graalvm.compiler.nodes.util.GraphUtil; import jdk.vm.ci.meta.DeoptimizationAction; import jdk.vm.ci.meta.DeoptimizationReason; import jdk.vm.ci.meta.SpeculationLog; --- 41,56 ---- import org.graalvm.compiler.nodes.LogicNode; import org.graalvm.compiler.nodes.NodeView; import org.graalvm.compiler.nodes.StructuredGraph; import org.graalvm.compiler.nodes.ValueNode; import org.graalvm.compiler.nodes.calc.ConditionalNode; import org.graalvm.compiler.nodes.calc.NegateNode; import org.graalvm.compiler.nodes.extended.GuardingNode; import org.graalvm.compiler.nodes.util.GraphUtil; + import org.graalvm.compiler.nodes.util.IntegerHelper; + import org.graalvm.compiler.nodes.util.SignedIntegerHelper; + import org.graalvm.compiler.nodes.util.UnsignedIntegerHelper; import jdk.vm.ci.meta.DeoptimizationAction; import jdk.vm.ci.meta.DeoptimizationReason; import jdk.vm.ci.meta.SpeculationLog;
*** 59,77 **** private InductionVariable iv; private ValueNode end; private boolean oneOff; private AbstractBeginNode body; private IfNode ifNode; ! CountedLoopInfo(LoopEx loop, InductionVariable iv, IfNode ifNode, ValueNode end, boolean oneOff, AbstractBeginNode body) { assert iv.direction() != null; this.loop = loop; this.iv = iv; this.end = end; this.oneOff = oneOff; this.body = body; this.ifNode = ifNode; } /** * Returns a node that computes the maximum trip count of this loop. That is the trip count of * this loop assuming it is not exited by an other exit than the {@linkplain #getLimitTest() --- 60,80 ---- private InductionVariable iv; private ValueNode end; private boolean oneOff; private AbstractBeginNode body; private IfNode ifNode; + private final boolean unsigned; ! CountedLoopInfo(LoopEx loop, InductionVariable iv, IfNode ifNode, ValueNode end, boolean oneOff, AbstractBeginNode body, boolean unsigned) { assert iv.direction() != null; this.loop = loop; this.iv = iv; this.end = end; this.oneOff = oneOff; this.body = body; this.ifNode = ifNode; + this.unsigned = unsigned; } /** * Returns a node that computes the maximum trip count of this loop. That is the trip count of * this loop assuming it is not exited by an other exit than the {@linkplain #getLimitTest()
*** 83,92 **** --- 86,99 ---- */ public ValueNode maxTripCountNode() { return maxTripCountNode(false); } + public boolean isUnsignedCheck() { + return this.unsigned; + } + /** * Returns a node that computes the maximum trip count of this loop. That is the trip count of * this loop assuming it is not exited by an other exit than the {@linkplain #getLimitTest() * count check}. *
*** 125,135 **** if (assumeLoopEntered) { return graph.addOrUniqueWithInputs(div); } ConstantNode zero = ConstantNode.forIntegerStamp(stamp, 0); ! LogicNode noEntryCheck = IntegerLessThanNode.create(max, min, NodeView.DEFAULT); return graph.addOrUniqueWithInputs(ConditionalNode.create(noEntryCheck, zero, div, NodeView.DEFAULT)); } /** * @return true if the loop has constant bounds. --- 132,145 ---- if (assumeLoopEntered) { return graph.addOrUniqueWithInputs(div); } ConstantNode zero = ConstantNode.forIntegerStamp(stamp, 0); ! // This check is "wide": it looks like min <= max ! // That's OK even if the loop is strict (`!isLimitIncluded()`) ! // because in this case, `div` will be zero when min == max ! LogicNode noEntryCheck = getCounterIntegerHelper().createCompareNode(max, min, NodeView.DEFAULT); return graph.addOrUniqueWithInputs(ConditionalNode.create(noEntryCheck, zero, div, NodeView.DEFAULT)); } /** * @return true if the loop has constant bounds.
*** 150,168 **** assert iv.direction() != null; long endValue = end.asJavaConstant().asLong(); long initValue = iv.constantInit(); long range; long absStride; if (iv.direction() == Direction.Up) { ! if (endValue < initValue) { return 0; } range = endValue - iv.constantInit(); absStride = iv.constantStride(); } else { assert iv.direction() == Direction.Down; ! if (initValue < endValue) { return 0; } range = iv.constantInit() - endValue; absStride = -iv.constantStride(); } --- 160,179 ---- assert iv.direction() != null; long endValue = end.asJavaConstant().asLong(); long initValue = iv.constantInit(); long range; long absStride; + IntegerHelper helper = getCounterIntegerHelper(64); if (iv.direction() == Direction.Up) { ! if (helper.compare(endValue, initValue) < 0) { return 0; } range = endValue - iv.constantInit(); absStride = iv.constantStride(); } else { assert iv.direction() == Direction.Down; ! if (helper.compare(initValue, endValue) < 0) { return 0; } range = iv.constantInit() - endValue; absStride = -iv.constantStride(); }
*** 171,180 **** --- 182,206 ---- } long denominator = range + absStride - 1; return Long.divideUnsigned(denominator, absStride); } + public IntegerHelper getCounterIntegerHelper() { + IntegerStamp stamp = (IntegerStamp) iv.valueNode().stamp(NodeView.DEFAULT); + return getCounterIntegerHelper(stamp.getBits()); + } + + public IntegerHelper getCounterIntegerHelper(int bits) { + IntegerHelper helper; + if (isUnsignedCheck()) { + helper = new UnsignedIntegerHelper(bits); + } else { + helper = new SignedIntegerHelper(bits); + } + return helper; + } + public boolean isExactTripCount() { return loop.loop().getNaturalExits().size() == 1; } public ValueNode exactTripCountNode() {
*** 244,259 **** } IntegerStamp endStamp = (IntegerStamp) end.stamp(NodeView.DEFAULT); ValueNode strideNode = iv.strideNode(); IntegerStamp strideStamp = (IntegerStamp) strideNode.stamp(NodeView.DEFAULT); GraphUtil.tryKillUnused(strideNode); if (getDirection() == Direction.Up) { ! long max = NumUtil.maxValue(endStamp.getBits()); ! return endStamp.upperBound() <= max - (strideStamp.upperBound() - 1) - (oneOff ? 1 : 0); } else if (getDirection() == Direction.Down) { ! long min = NumUtil.minValue(endStamp.getBits()); ! return min + (1 - strideStamp.lowerBound()) + (oneOff ? 1 : 0) <= endStamp.lowerBound(); } return false; } @SuppressWarnings("try") --- 270,286 ---- } IntegerStamp endStamp = (IntegerStamp) end.stamp(NodeView.DEFAULT); ValueNode strideNode = iv.strideNode(); IntegerStamp strideStamp = (IntegerStamp) strideNode.stamp(NodeView.DEFAULT); GraphUtil.tryKillUnused(strideNode); + IntegerHelper integerHelper = getCounterIntegerHelper(); if (getDirection() == Direction.Up) { ! long max = integerHelper.maxValue(); ! return integerHelper.compare(endStamp.upperBound(), max - (strideStamp.upperBound() - 1) - (oneOff ? 1 : 0)) <= 0; } else if (getDirection() == Direction.Down) { ! long min = integerHelper.minValue(); ! return integerHelper.compare(min + (1 - strideStamp.lowerBound()) + (oneOff ? 1 : 0), endStamp.lowerBound()) <= 0; } return false; } @SuppressWarnings("try")
*** 262,287 **** if (overflowGuard != null || counterNeverOverflows()) { return overflowGuard; } try (DebugCloseable position = loop.loopBegin().withNodeSourcePosition()) { IntegerStamp stamp = (IntegerStamp) iv.valueNode().stamp(NodeView.DEFAULT); StructuredGraph graph = iv.valueNode().graph(); LogicNode cond; // we use a negated guard with a < condition to achieve a >= ConstantNode one = ConstantNode.forIntegerStamp(stamp, 1, graph); if (iv.direction() == Direction.Up) { ! ValueNode v1 = sub(ConstantNode.forIntegerStamp(stamp, NumUtil.maxValue(stamp.getBits())), sub(iv.strideNode(), one)); if (oneOff) { v1 = sub(v1, one); } ! cond = graph.addOrUniqueWithInputs(IntegerLessThanNode.create(v1, end, NodeView.DEFAULT)); } else { assert iv.direction() == Direction.Down; ! ValueNode v1 = add(ConstantNode.forIntegerStamp(stamp, NumUtil.minValue(stamp.getBits())), sub(one, iv.strideNode())); if (oneOff) { v1 = add(v1, one); } ! cond = graph.addOrUniqueWithInputs(IntegerLessThanNode.create(end, v1, NodeView.DEFAULT)); } assert graph.getGuardsStage().allowsFloatingGuards(); overflowGuard = graph.unique(new GuardNode(cond, AbstractBeginNode.prevBegin(loop.entryPoint()), DeoptimizationReason.LoopLimitCheck, DeoptimizationAction.InvalidateRecompile, true, SpeculationLog.NO_SPECULATION, null)); // TODO gd: use speculation loop.loopBegin().setOverflowGuard(overflowGuard); --- 289,315 ---- if (overflowGuard != null || counterNeverOverflows()) { return overflowGuard; } try (DebugCloseable position = loop.loopBegin().withNodeSourcePosition()) { IntegerStamp stamp = (IntegerStamp) iv.valueNode().stamp(NodeView.DEFAULT); + IntegerHelper integerHelper = getCounterIntegerHelper(); StructuredGraph graph = iv.valueNode().graph(); LogicNode cond; // we use a negated guard with a < condition to achieve a >= ConstantNode one = ConstantNode.forIntegerStamp(stamp, 1, graph); if (iv.direction() == Direction.Up) { ! ValueNode v1 = sub(ConstantNode.forIntegerStamp(stamp, integerHelper.maxValue()), sub(iv.strideNode(), one)); if (oneOff) { v1 = sub(v1, one); } ! cond = graph.addOrUniqueWithInputs(integerHelper.createCompareNode(v1, end, NodeView.DEFAULT)); } else { assert iv.direction() == Direction.Down; ! ValueNode v1 = add(ConstantNode.forIntegerStamp(stamp, integerHelper.minValue()), sub(one, iv.strideNode())); if (oneOff) { v1 = add(v1, one); } ! cond = graph.addOrUniqueWithInputs(integerHelper.createCompareNode(end, v1, NodeView.DEFAULT)); } assert graph.getGuardsStage().allowsFloatingGuards(); overflowGuard = graph.unique(new GuardNode(cond, AbstractBeginNode.prevBegin(loop.entryPoint()), DeoptimizationReason.LoopLimitCheck, DeoptimizationAction.InvalidateRecompile, true, SpeculationLog.NO_SPECULATION, null)); // TODO gd: use speculation loop.loopBegin().setOverflowGuard(overflowGuard);
< prev index next >