# HG changeset patch
# User Gilles Duboscq <duboscq@ssw.jku.at>
# Date 1367345089 -7200
# Node ID 27733a62ba72bc51a95230c197b32c2eb21d461f
# Parent  18906f4dfe773a3eb71623f53693f296aed5df62
Fixes and improvements for induction variables

diff -r 18906f4dfe77 -r 27733a62ba72 graal/com.oracle.graal.loop/src/com/oracle/graal/loop/BasicInductionVariable.java
--- 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();
     }
 }
diff -r 18906f4dfe77 -r 27733a62ba72 graal/com.oracle.graal.loop/src/com/oracle/graal/loop/CountedLoopInfo.java
--- 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;
+    }
 }
diff -r 18906f4dfe77 -r 27733a62ba72 graal/com.oracle.graal.loop/src/com/oracle/graal/loop/DerivedOffsetInductionVariable.java
--- 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
diff -r 18906f4dfe77 -r 27733a62ba72 graal/com.oracle.graal.loop/src/com/oracle/graal/loop/DerivedScaledInductionVariable.java
--- 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
diff -r 18906f4dfe77 -r 27733a62ba72 graal/com.oracle.graal.loop/src/com/oracle/graal/loop/InductionVariable.java
--- 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();
 
diff -r 18906f4dfe77 -r 27733a62ba72 graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopEx.java
--- 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;
+    }
 }
diff -r 18906f4dfe77 -r 27733a62ba72 graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopsData.java
--- 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;
+    }
 }
diff -r 18906f4dfe77 -r 27733a62ba72 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/ConvertNode.java
--- 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);