< 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 >