Mercurial > hg > truffle
changeset 9446:27733a62ba72
Fixes and improvements for induction variables
line wrap: on
line diff
--- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/BasicInductionVariable.java Tue Apr 30 19:56:36 2013 +0200 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/BasicInductionVariable.java Tue Apr 30 20:04:49 2013 +0200 @@ -22,9 +22,11 @@ */ package com.oracle.graal.loop; +import com.oracle.graal.api.meta.*; import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.calc.*; +import com.oracle.graal.nodes.calc.ConvertNode.Op; import com.oracle.graal.nodes.type.*; public class BasicInductionVariable extends InductionVariable { @@ -113,8 +115,19 @@ } @Override - public ValueNode extremumNode() { - return IntegerArithmeticNode.add(IntegerArithmeticNode.mul(strideNode(), loop.counted().maxTripCountNode()), init); + public ValueNode extremumNode(boolean assumePositiveTripCount, Kind kind) { + Kind fromKind = phi.kind(); + Graph graph = phi.graph(); + ValueNode stride = strideNode(); + ValueNode maxTripCount = loop.counted().maxTripCountNode(assumePositiveTripCount); + ValueNode initNode = this.initNode(); + if (fromKind != kind) { + Op convertOp = Op.getOp(fromKind, kind); + stride = graph.unique(new ConvertNode(convertOp, stride)); + maxTripCount = graph.unique(new ConvertNode(convertOp, maxTripCount)); + initNode = graph.unique(new ConvertNode(convertOp, initNode)); + } + return IntegerArithmeticNode.add(IntegerArithmeticNode.mul(stride, IntegerArithmeticNode.sub(maxTripCount, ConstantNode.forIntegerKind(kind, 1, graph))), initNode); } @Override @@ -124,6 +137,6 @@ @Override public long constantExtremum() { - return constantStride() * loop.counted().constantMaxTripCount() + constantInit(); + return constantStride() * (loop.counted().constantMaxTripCount() - 1) + constantInit(); } }
--- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/CountedLoopInfo.java Tue Apr 30 19:56:36 2013 +0200 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/CountedLoopInfo.java Tue Apr 30 20:04:49 2013 +0200 @@ -22,9 +22,14 @@ */ package com.oracle.graal.loop; +import static com.oracle.graal.nodes.calc.IntegerArithmeticNode.*; + +import com.oracle.graal.api.code.*; +import com.oracle.graal.api.meta.*; import com.oracle.graal.graph.*; import com.oracle.graal.loop.InductionVariable.Direction; import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.calc.*; public class CountedLoopInfo { @@ -32,19 +37,39 @@ private InductionVariable iv; private ValueNode end; private boolean oneOff; + private ValueNode overflowGuard; + private AbstractBeginNode body; - CountedLoopInfo(LoopEx loop, InductionVariable iv, ValueNode end, boolean oneOff) { + CountedLoopInfo(LoopEx loop, InductionVariable iv, ValueNode end, boolean oneOff, AbstractBeginNode body) { this.loop = loop; this.iv = iv; this.end = end; this.oneOff = oneOff; + this.body = body; } public ValueNode maxTripCountNode() { - // TODO (gd) stuarte and respect oneOff - throw GraalInternalError.unimplemented("division is a fixed node that needs to be inserted into the control flow"); - // return IntegerArithmeticNode.div(IntegerArithmeticNode.sub(end, iv.initNode()), - // iv.strideNode()); + return maxTripCountNode(false); + } + + public ValueNode maxTripCountNode(boolean assumePositive) { + StructuredGraph graph = (StructuredGraph) iv.valueNode().graph(); + Kind kind = iv.valueNode().kind(); + IntegerArithmeticNode range = IntegerArithmeticNode.sub(end, iv.initNode()); + if (oneOff) { + if (iv.direction() == Direction.Up) { + range = IntegerArithmeticNode.add(range, ConstantNode.forIntegerKind(kind, 1, graph)); + } else { + range = IntegerArithmeticNode.sub(range, ConstantNode.forIntegerKind(kind, 1, graph)); + } + } + IntegerDivNode div = graph.add(new IntegerDivNode(kind, range, iv.strideNode())); + graph.addBeforeFixed(loop.entryPoint(), div); + ConstantNode zero = ConstantNode.forIntegerKind(kind, 0, graph); + if (assumePositive) { + return div; + } + return graph.unique(new ConditionalNode(graph.unique(new IntegerLessThanNode(zero, div)), div, zero)); } public boolean isConstantMaxTripCount() { @@ -80,4 +105,49 @@ public String toString() { return "iv=" + iv + " until " + end + (oneOff ? iv.direction() == Direction.Up ? "+1" : "-1" : ""); } + + public ValueNode getLimit() { + return end; + } + + public ValueNode getStart() { + return iv.initNode(); + } + + public boolean isLimitIncluded() { + return oneOff; + } + + public AbstractBeginNode getBody() { + return body; + } + + public Direction getDirection() { + return iv.direction(); + } + + public ValueNode getOverFlowGuard() { + if (overflowGuard == null) { + Kind kind = iv.valueNode().kind(); + Graph graph = iv.valueNode().graph(); + CompareNode cond; // we use a negated guard with a < condition to achieve a >= + ConstantNode one = ConstantNode.forIntegerKind(kind, 1, graph); + if (iv.direction() == Direction.Up) { + IntegerArithmeticNode v1 = sub(ConstantNode.forIntegerKind(kind, kind.getMaxValue(), graph), sub(iv.strideNode(), one)); + if (oneOff) { + v1 = sub(v1, one); + } + cond = graph.unique(new IntegerLessThanNode(v1, end)); + } else { + assert iv.direction() == Direction.Down; + IntegerArithmeticNode v1 = add(ConstantNode.forIntegerKind(kind, kind.getMinValue(), graph), add(iv.strideNode(), one)); + if (oneOff) { + v1 = add(v1, one); + } + cond = graph.unique(new IntegerLessThanNode(end, v1)); + } + overflowGuard = graph.unique(new GuardNode(cond, BeginNode.prevBegin(loop.entryPoint()), DeoptimizationReason.LoopLimitCheck, DeoptimizationAction.InvalidateRecompile, true)); + } + return overflowGuard; + } }
--- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/DerivedOffsetInductionVariable.java Tue Apr 30 19:56:36 2013 +0200 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/DerivedOffsetInductionVariable.java Tue Apr 30 20:04:49 2013 +0200 @@ -22,6 +22,7 @@ */ package com.oracle.graal.loop; +import com.oracle.graal.api.meta.*; import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.calc.*; @@ -86,8 +87,8 @@ } @Override - public ValueNode extremumNode() { - return op(offset, base.extremumNode()); + public ValueNode extremumNode(boolean assumePositiveTripCount, Kind kind) { + return op(base.extremumNode(assumePositiveTripCount, kind), ConvertNode.convert(kind, offset)); } @Override
--- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/DerivedScaledInductionVariable.java Tue Apr 30 19:56:36 2013 +0200 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/DerivedScaledInductionVariable.java Tue Apr 30 20:04:49 2013 +0200 @@ -22,6 +22,7 @@ */ package com.oracle.graal.loop; +import com.oracle.graal.api.meta.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.calc.*; import com.oracle.graal.nodes.type.*; @@ -96,8 +97,8 @@ } @Override - public ValueNode extremumNode() { - return IntegerArithmeticNode.mul(base.extremumNode(), scale); + public ValueNode extremumNode(boolean assumePositiveTripCount, Kind kind) { + return IntegerArithmeticNode.mul(base.extremumNode(assumePositiveTripCount, kind), ConvertNode.convert(kind, scale)); } @Override
--- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/InductionVariable.java Tue Apr 30 19:56:36 2013 +0200 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/InductionVariable.java Tue Apr 30 20:04:49 2013 +0200 @@ -22,6 +22,7 @@ */ package com.oracle.graal.loop; +import com.oracle.graal.api.meta.*; import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; @@ -48,6 +49,10 @@ this.loop = loop; } + public LoopEx getLoop() { + return loop; + } + public abstract Direction direction(); public abstract ValueNode valueNode(); @@ -64,7 +69,11 @@ public abstract long constantStride(); - public abstract ValueNode extremumNode(); + public ValueNode extremumNode() { + return extremumNode(false, valueNode().kind()); + } + + public abstract ValueNode extremumNode(boolean assumePositiveTripCount, Kind kind); public abstract boolean isConstantExtremum();
--- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopEx.java Tue Apr 30 19:56:36 2013 +0200 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopEx.java Tue Apr 30 20:04:49 2013 +0200 @@ -39,6 +39,7 @@ private LoopFragmentWhole whole; private CountedLoopInfo counted; // TODO (gd) detect private LoopsData data; + private InductionVariables ivs; LoopEx(Loop lirLoop, LoopsData data) { this.lirLoop = lirLoop; @@ -169,4 +170,11 @@ } return LoopFragment.computeNodes(point.graph(), blocks, exits); } + + public InductionVariables getInductionVariables() { + if (ivs == null) { + ivs = new InductionVariables(this); + } + return ivs; + } }
--- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopsData.java Tue Apr 30 19:56:36 2013 +0200 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopsData.java Tue Apr 30 20:04:49 2013 +0200 @@ -31,6 +31,7 @@ import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.calc.*; import com.oracle.graal.nodes.cfg.*; +import com.oracle.graal.nodes.extended.*; public class LoopsData { @@ -92,6 +93,9 @@ InductionVariables ivs = new InductionVariables(loop); LoopBeginNode loopBegin = loop.loopBegin(); FixedNode next = loopBegin.next(); + while (next instanceof FixedGuardNode || next instanceof ValueAnchorNode) { + next = ((FixedWithNextNode) next).next(); + } if (next instanceof IfNode) { IfNode ifNode = (IfNode) next; boolean negated = false; @@ -150,7 +154,7 @@ default: throw GraalInternalError.shouldNotReachHere(); } - loop.setCounted(new CountedLoopInfo(loop, iv, limit, oneOff)); + loop.setCounted(new CountedLoopInfo(loop, iv, limit, oneOff, negated ? ifNode.falseSuccessor() : ifNode.trueSuccessor())); } } } @@ -158,4 +162,18 @@ public ControlFlowGraph controlFlowGraph() { return cfg; } + + public InductionVariable getInductionVariable(ValueNode value) { + InductionVariable match = null; + for (LoopEx loop : loops()) { + InductionVariable iv = loop.getInductionVariables().get(value); + if (iv != null) { + if (match != null) { + return null; + } + match = iv; + } + } + return match; + } }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/ConvertNode.java Tue Apr 30 19:56:36 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/ConvertNode.java Tue Apr 30 20:04:49 2013 +0200 @@ -25,6 +25,7 @@ import static com.oracle.graal.api.meta.Kind.*; import com.oracle.graal.api.meta.*; +import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.spi.*; import com.oracle.graal.nodes.type.*; @@ -63,6 +64,63 @@ this.from = from; this.to = to; } + + public static Op getOp(Kind from, Kind to) { + switch (from) { + case Int: + switch (to) { + case Byte: + return I2B; + case Char: + return I2C; + case Short: + return I2S; + case Long: + return I2L; + case Float: + return I2F; + case Double: + return I2D; + default: + throw GraalInternalError.shouldNotReachHere(); + } + case Long: + switch (to) { + case Int: + return L2I; + case Float: + return L2F; + case Double: + return L2D; + default: + throw GraalInternalError.shouldNotReachHere(); + } + case Float: + switch (to) { + case Int: + return F2I; + case Long: + return F2L; + case Double: + return F2D; + default: + throw GraalInternalError.shouldNotReachHere(); + } + case Double: + switch (to) { + case Int: + return D2I; + case Long: + return D2L; + case Float: + return D2F; + default: + throw GraalInternalError.shouldNotReachHere(); + } + default: + throw GraalInternalError.shouldNotReachHere(); + } + } } @Input private ValueNode value; @@ -171,6 +229,14 @@ gen.setResult(this, gen.emitConvert(opcode, gen.operand(value()))); } + public static ValueNode convert(Kind toKind, ValueNode value) { + Kind fromKind = value.kind(); + if (fromKind == toKind) { + return value; + } + return value.graph().unique(new ConvertNode(Op.getOp(fromKind, toKind), value)); + } + @NodeIntrinsic public static native float convert(@ConstantNodeParameter Op op, int value);