< prev index next >
src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.loop/src/org/graalvm/compiler/loop/CountedLoopInfo.java
Print this page
*** 22,54 ****
*/
package org.graalvm.compiler.loop;
! import static org.graalvm.compiler.loop.MathUtil.add;
! import static org.graalvm.compiler.loop.MathUtil.sub;
import static org.graalvm.compiler.loop.MathUtil.unsignedDivBefore;
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;
import org.graalvm.compiler.nodes.AbstractBeginNode;
import org.graalvm.compiler.nodes.ConstantNode;
import org.graalvm.compiler.nodes.GuardNode;
import org.graalvm.compiler.nodes.IfNode;
import org.graalvm.compiler.nodes.NodeView;
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.calc.NegateNode;
import org.graalvm.compiler.nodes.extended.GuardingNode;
- import jdk.vm.ci.code.CodeUtil;
import jdk.vm.ci.meta.DeoptimizationAction;
import jdk.vm.ci.meta.DeoptimizationReason;
import jdk.vm.ci.meta.SpeculationLog;
public class CountedLoopInfo {
--- 22,56 ----
*/
package org.graalvm.compiler.loop;
! 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;
import org.graalvm.compiler.nodes.AbstractBeginNode;
import org.graalvm.compiler.nodes.ConstantNode;
import org.graalvm.compiler.nodes.GuardNode;
import org.graalvm.compiler.nodes.IfNode;
+ 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;
public class CountedLoopInfo {
*** 90,135 ****
*
* This count is exact if {@link #isExactTripCount()} returns true.
*
* THIS VALUE SHOULD BE TREATED AS UNSIGNED.
*
! * @param assumePositive if true the check that the loop is entered at all will be omitted.
*/
! public ValueNode maxTripCountNode(boolean assumePositive) {
StructuredGraph graph = iv.valueNode().graph();
Stamp stamp = iv.valueNode().stamp(NodeView.DEFAULT);
ValueNode max;
ValueNode min;
- ValueNode range;
ValueNode absStride;
if (iv.direction() == Direction.Up) {
absStride = iv.strideNode();
- range = sub(graph, end, iv.initNode());
max = end;
min = iv.initNode();
} else {
assert iv.direction() == Direction.Down;
! absStride = graph.maybeAddOrUnique(NegateNode.create(iv.strideNode(), NodeView.DEFAULT));
! range = sub(graph, iv.initNode(), end);
max = iv.initNode();
min = end;
}
! ConstantNode one = ConstantNode.forIntegerStamp(stamp, 1, graph);
if (oneOff) {
! range = add(graph, range, one);
}
// round-away-from-zero divison: (range + stride -/+ 1) / stride
! ValueNode denominator = add(graph, range, sub(graph, absStride, one));
ValueNode div = unsignedDivBefore(graph, loop.entryPoint(), denominator, absStride, null);
! if (assumePositive) {
! return div;
}
! ConstantNode zero = ConstantNode.forIntegerStamp(stamp, 0, graph);
! return graph.unique(new ConditionalNode(graph.unique(new IntegerLessThanNode(max, min)), zero, div));
}
/**
* @return true if the loop has constant bounds.
*/
--- 92,136 ----
*
* This count is exact if {@link #isExactTripCount()} returns true.
*
* THIS VALUE SHOULD BE TREATED AS UNSIGNED.
*
! * @param assumeLoopEntered if true the check that the loop is entered at all will be omitted.
*/
! public ValueNode maxTripCountNode(boolean assumeLoopEntered) {
StructuredGraph graph = iv.valueNode().graph();
Stamp stamp = iv.valueNode().stamp(NodeView.DEFAULT);
ValueNode max;
ValueNode min;
ValueNode absStride;
if (iv.direction() == Direction.Up) {
absStride = iv.strideNode();
max = end;
min = iv.initNode();
} else {
assert iv.direction() == Direction.Down;
! absStride = NegateNode.create(iv.strideNode(), NodeView.DEFAULT);
max = iv.initNode();
min = end;
}
+ ValueNode range = sub(max, min);
! ConstantNode one = ConstantNode.forIntegerStamp(stamp, 1);
if (oneOff) {
! range = add(range, one);
}
// round-away-from-zero divison: (range + stride -/+ 1) / stride
! ValueNode denominator = add(range, sub(absStride, one));
ValueNode div = unsignedDivBefore(graph, loop.entryPoint(), denominator, absStride, null);
! 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.
*/
*** 171,181 ****
long denominator = range + absStride - 1;
return Long.divideUnsigned(denominator, absStride);
}
public boolean isExactTripCount() {
! return loop.loopBegin().loopExits().count() == 1;
}
public ValueNode exactTripCountNode() {
assert isExactTripCount();
return maxTripCountNode();
--- 172,182 ----
long denominator = range + absStride - 1;
return Long.divideUnsigned(denominator, absStride);
}
public boolean isExactTripCount() {
! return loop.loop().getNaturalExits().size() == 1;
}
public ValueNode exactTripCountNode() {
assert isExactTripCount();
return maxTripCountNode();
*** 214,223 ****
--- 215,233 ----
public AbstractBeginNode getBody() {
return body;
}
+ public AbstractBeginNode getCountedExit() {
+ if (getLimitTest().trueSuccessor() == getBody()) {
+ return getLimitTest().falseSuccessor();
+ } else {
+ assert getLimitTest().falseSuccessor() == getBody();
+ return getLimitTest().trueSuccessor();
+ }
+ }
+
public Direction getDirection() {
return iv.direction();
}
public InductionVariable getCounter() {
*** 226,259 ****
public GuardingNode getOverFlowGuard() {
return loop.loopBegin().getOverflowGuard();
}
@SuppressWarnings("try")
public GuardingNode createOverFlowGuard() {
GuardingNode overflowGuard = getOverFlowGuard();
! if (overflowGuard != null) {
return overflowGuard;
}
try (DebugCloseable position = loop.loopBegin().withNodeSourcePosition()) {
IntegerStamp stamp = (IntegerStamp) iv.valueNode().stamp(NodeView.DEFAULT);
StructuredGraph graph = iv.valueNode().graph();
! CompareNode 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(graph, ConstantNode.forIntegerStamp(stamp, CodeUtil.maxValue(stamp.getBits()), graph), sub(graph, iv.strideNode(), one));
if (oneOff) {
! v1 = sub(graph, v1, one);
}
! cond = graph.unique(new IntegerLessThanNode(v1, end));
} else {
assert iv.direction() == Direction.Down;
! ValueNode v1 = add(graph, ConstantNode.forIntegerStamp(stamp, CodeUtil.minValue(stamp.getBits()), graph), sub(graph, one, iv.strideNode()));
if (oneOff) {
! v1 = add(graph, v1, one);
}
! cond = graph.unique(new IntegerLessThanNode(end, v1));
}
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);
--- 236,287 ----
public GuardingNode getOverFlowGuard() {
return loop.loopBegin().getOverflowGuard();
}
+ public boolean counterNeverOverflows() {
+ if (iv.isConstantStride() && abs(iv.constantStride()) == 1) {
+ return true;
+ }
+ 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")
public GuardingNode createOverFlowGuard() {
GuardingNode overflowGuard = getOverFlowGuard();
! 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);
< prev index next >