# HG changeset patch # User Doug Simon # Date 1339759024 -7200 # Node ID d50c788195a54ac0fc87a1ccd06cf786e22f854a # Parent 60ca7d300b8f9d2005c154b83535725e47c9be66# Parent 62f1fc8c6c9b1727663765b01f5318018a5af9a5 Merge. diff -r 60ca7d300b8f -r d50c788195a5 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/BasicInductionVariable.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/BasicInductionVariable.java Fri Jun 15 13:17:04 2012 +0200 @@ -0,0 +1,129 @@ +/* + * Copyright (c) 2012, 2012, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.compiler.loop; + +import com.oracle.graal.graph.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.calc.*; +import com.oracle.graal.nodes.type.*; + + +public class BasicInductionVariable extends InductionVariable { + private PhiNode phi; + private ValueNode init; + private ValueNode rawStride; + private IntegerArithmeticNode op; + + public BasicInductionVariable(LoopEx loop, PhiNode phi, ValueNode init, ValueNode rawStride, IntegerArithmeticNode op) { + super(loop); + this.phi = phi; + this.init = init; + this.rawStride = rawStride; + this.op = op; + } + + @Override + public Direction direction() { + Stamp stamp = rawStride.stamp(); + if (stamp instanceof IntegerStamp) { + IntegerStamp integerStamp = (IntegerStamp) stamp; + Direction dir = null; + if (integerStamp.lowerBound() > 0) { + dir = Direction.Up; + } else if (integerStamp.upperBound() < 0) { + dir = Direction.Down; + } + if (dir != null) { + if (op instanceof IntegerAddNode) { + return dir; + } else { + assert op instanceof IntegerSubNode; + return dir.opposite(); + } + } + } + return null; + } + + @Override + public PhiNode valueNode() { + return phi; + } + + @Override + public ValueNode initNode() { + return init; + } + + @Override + public ValueNode strideNode() { + if (op instanceof IntegerAddNode) { + return rawStride; + } + if (op instanceof IntegerSubNode) { + return rawStride.graph().unique(new NegateNode(rawStride)); + } + throw GraalInternalError.shouldNotReachHere(); + } + + @Override + public boolean isConstantInit() { + return init.isConstant(); + } + + @Override + public boolean isConstantStride() { + return rawStride.isConstant(); + } + + @Override + public long constantInit() { + return init.asConstant().asLong(); + } + + @Override + public long constantStride() { + if (op instanceof IntegerAddNode) { + return rawStride.asConstant().asLong(); + } + if (op instanceof IntegerSubNode) { + return -rawStride.asConstant().asLong(); + } + throw GraalInternalError.shouldNotReachHere(); + } + + @Override + public ValueNode extremumNode() { + return IntegerArithmeticNode.add(IntegerArithmeticNode.mul(strideNode(), loop.counted().maxTripCountNode()), init); + } + + @Override + public boolean isConstantExtremum() { + return isConstantInit() && isConstantStride() && loop.counted().isConstantMaxTripCount(); + } + + @Override + public long constantExtremum() { + return constantStride() * loop.counted().constantMaxTripCount() + constantInit(); + } +} diff -r 60ca7d300b8f -r d50c788195a5 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/CountedLoopInfo.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/CountedLoopInfo.java Fri Jun 15 13:17:04 2012 +0200 @@ -0,0 +1,69 @@ +/* + * Copyright (c) 2012, 2012, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.compiler.loop; + +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.calc.*; + +public class CountedLoopInfo { + private final LoopEx loop; + private InductionVariable iv; + private ValueNode end; + + CountedLoopInfo(LoopEx loop, InductionVariable iv, ValueNode end) { + this.loop = loop; + this.iv = iv; + this.end = end; + } + + public ValueNode maxTripCountNode() { + return IntegerArithmeticNode.div(IntegerArithmeticNode.sub(end, iv.initNode()), iv.strideNode()); + } + + public boolean isConstantMaxTripCount() { + return end instanceof ConstantNode && iv.isConstantInit() && iv.isConstantStride(); + } + + public long constantMaxTripCount() { + return (((ConstantNode) end).asConstant().asLong() - iv.constantInit()) / iv.constantStride(); + } + + public boolean isExactTripCount() { + return loop.loopBegin().loopExits().count() == 1; + } + + public ValueNode exactTripCountNode() { + assert isExactTripCount(); + return maxTripCountNode(); + } + + public boolean isConstantExactTripCount() { + assert isExactTripCount(); + return isConstantMaxTripCount(); + } + + public long constantExactTripCount() { + assert isExactTripCount(); + return constantMaxTripCount(); + } +} diff -r 60ca7d300b8f -r d50c788195a5 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/DerivedOffsetInductionVariable.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/DerivedOffsetInductionVariable.java Fri Jun 15 13:17:04 2012 +0200 @@ -0,0 +1,132 @@ +/* + * Copyright (c) 2012, 2012, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.compiler.loop; + +import com.oracle.graal.graph.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.calc.*; + + +public class DerivedOffsetInductionVariable extends InductionVariable { + private InductionVariable base; + private ValueNode offset; + private IntegerArithmeticNode value; + + public DerivedOffsetInductionVariable(LoopEx loop, InductionVariable base, ValueNode offset, IntegerArithmeticNode value) { + super(loop); + this.base = base; + this.offset = offset; + this.value = value; + } + + @Override + public Direction direction() { + return base.direction(); + } + + @Override + public ValueNode valueNode() { + return value; + } + + @Override + public boolean isConstantInit() { + return offset.isConstant() && base.isConstantInit(); + } + + @Override + public boolean isConstantStride() { + return base.isConstantStride(); + } + + @Override + public long constantInit() { + return op(base.constantInit(), offset.asConstant().asLong()); + } + + @Override + public long constantStride() { + if (value instanceof IntegerSubNode && base.valueNode() == value.y()) { + return -base.constantStride(); + } + return base.constantStride(); + } + + @Override + public ValueNode initNode() { + return op(base.initNode(), offset); + } + + @Override + public ValueNode strideNode() { + if (value instanceof IntegerSubNode && base.valueNode() == value.y()) { + return value.graph().unique(new NegateNode(base.strideNode())); + } + return base.strideNode(); + } + + @Override + public ValueNode extremumNode() { + return op(offset, base.extremumNode()); + } + + @Override + public boolean isConstantExtremum() { + return offset.isConstant() && base.isConstantExtremum(); + } + + @Override + public long constantExtremum() { + return op(base.constantExtremum(), offset.asConstant().asLong()); + } + + private long op(long b, long o) { + if (value instanceof IntegerAddNode) { + return b + o; + } + if (value instanceof IntegerSubNode) { + if (base.valueNode() == value.x()) { + return b - o; + } else { + assert base.valueNode() == value.y(); + return o - b; + } + } + throw GraalInternalError.shouldNotReachHere(); + } + + private ValueNode op(ValueNode b, ValueNode o) { + if (value instanceof IntegerAddNode) { + return IntegerArithmeticNode.add(b, o); + } + if (value instanceof IntegerSubNode) { + if (base.valueNode() == value.x()) { + return IntegerArithmeticNode.sub(b, o); + } else { + assert base.valueNode() == value.y(); + return IntegerArithmeticNode.sub(o, b); + } + } + throw GraalInternalError.shouldNotReachHere(); + } +} diff -r 60ca7d300b8f -r d50c788195a5 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/DerivedScaledInductionVariable.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/DerivedScaledInductionVariable.java Fri Jun 15 13:17:04 2012 +0200 @@ -0,0 +1,112 @@ +/* + * Copyright (c) 2012, 2012, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.compiler.loop; + +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.calc.*; +import com.oracle.graal.nodes.type.*; + + +public class DerivedScaledInductionVariable extends InductionVariable { + private InductionVariable base; + private ValueNode scale; + private ValueNode value; + + public DerivedScaledInductionVariable(LoopEx loop, InductionVariable base, ValueNode scale, ValueNode value) { + super(loop); + this.base = base; + this.scale = scale; + this.value = value; + } + + public DerivedScaledInductionVariable(LoopEx loop, InductionVariable base, NegateNode value) { + super(loop); + this.base = base; + this.scale = ConstantNode.forInt(-1, value.graph()); + this.value = value; + } + + @Override + public Direction direction() { + Stamp stamp = scale.stamp(); + if (stamp instanceof IntegerStamp) { + IntegerStamp integerStamp = (IntegerStamp) stamp; + if (integerStamp.lowerBound() > 0) { + return base.direction(); + } else if (integerStamp.upperBound() < 0) { + return base.direction().opposite(); + } + } + return null; + } + + @Override + public ValueNode valueNode() { + return value; + } + + @Override + public ValueNode initNode() { + return IntegerArithmeticNode.mul(base.initNode(), scale); + } + + @Override + public ValueNode strideNode() { + return IntegerArithmeticNode.mul(base.strideNode(), scale); + } + + @Override + public boolean isConstantInit() { + return scale.isConstant() && base.isConstantInit(); + } + + @Override + public boolean isConstantStride() { + return scale.isConstant() && base.isConstantStride(); + } + + @Override + public long constantInit() { + return base.constantInit() * scale.asConstant().asLong(); + } + + @Override + public long constantStride() { + return base.constantStride() * scale.asConstant().asLong(); + } + + @Override + public ValueNode extremumNode() { + return IntegerArithmeticNode.mul(base.extremumNode(), scale); + } + + @Override + public boolean isConstantExtremum() { + return scale.isConstant() && base.isConstantExtremum(); + } + + @Override + public long constantExtremum() { + return base.constantExtremum() * scale.asConstant().asLong(); + } +} diff -r 60ca7d300b8f -r d50c788195a5 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/InductionVariable.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/InductionVariable.java Fri Jun 15 13:17:04 2012 +0200 @@ -0,0 +1,64 @@ +/* + * Copyright (c) 2012, 2012, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.compiler.loop; + +import com.oracle.graal.graph.*; +import com.oracle.graal.nodes.*; + + +public abstract class InductionVariable { + public enum Direction { + Up, + Down; + public Direction opposite() { + switch(this) { + case Up: return Down; + case Down: return Up; + default: throw GraalInternalError.shouldNotReachHere(); + } + } + } + + protected final LoopEx loop; + + public InductionVariable(LoopEx loop) { + this.loop = loop; + } + + public abstract Direction direction(); + + public abstract ValueNode valueNode(); + + public abstract ValueNode initNode(); + public abstract ValueNode strideNode(); + + public abstract boolean isConstantInit(); + public abstract boolean isConstantStride(); + + public abstract long constantInit(); + public abstract long constantStride(); + + public abstract ValueNode extremumNode(); + public abstract boolean isConstantExtremum(); + public abstract long constantExtremum(); +} diff -r 60ca7d300b8f -r d50c788195a5 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/InductionVariables.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/InductionVariables.java Fri Jun 15 13:17:04 2012 +0200 @@ -0,0 +1,122 @@ +/* + * Copyright (c) 2012, 2012, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.compiler.loop; + +import java.util.*; + +import com.oracle.graal.graph.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.calc.*; + + +public class InductionVariables { + private final LoopEx loop; + private Map ivs; + + public InductionVariables(LoopEx loop) { + this.loop = loop; + ivs = new IdentityHashMap<>(); + findDerived(findBasic()); + } + + public InductionVariable get(ValueNode v) { + return ivs.get(v); + } + + private Collection findBasic() { + List bivs = new LinkedList<>(); + LoopBeginNode loopBegin = loop.loopBegin(); + EndNode forwardEnd = loopBegin.forwardEnd(); + for (PhiNode phi : loopBegin.phis()) { + ValueNode backValue = phi.singleBackValue(); + if (backValue == null) { + continue; + } + ValueNode stride = addSub(backValue, phi); + if (stride != null) { + BasicInductionVariable biv = new BasicInductionVariable(loop, phi, phi.valueAt(forwardEnd), stride, (IntegerArithmeticNode) backValue); + ivs.put(phi, biv); + bivs.add(biv); + } + } + return bivs; + } + + private void findDerived(Collection bivs) { + Queue scanQueue = new LinkedList(bivs); + while (!scanQueue.isEmpty()) { + InductionVariable baseIv = scanQueue.remove(); + ValueNode baseIvNode = baseIv.valueNode(); + for (ValueNode op : baseIvNode.usages().filter(ValueNode.class)) { + if (loop.isOutsideLoop(op)) { + continue; + } + InductionVariable iv = null; + ValueNode offset = addSub(op, baseIvNode); + ValueNode scale; + if (offset != null) { + iv = new DerivedOffsetInductionVariable(loop, baseIv, offset, (IntegerArithmeticNode) op); + } else if (op instanceof NegateNode) { + iv = new DerivedScaledInductionVariable(loop, baseIv, (NegateNode) op); + } else if ((scale = mul(op, baseIvNode)) != null) { + iv = new DerivedScaledInductionVariable(loop, baseIv, scale, op); + } + + if (iv != null) { + ivs.put(op, iv); + scanQueue.offer(iv); + } + } + } + } + + private ValueNode addSub(ValueNode op, ValueNode base) { + if (op instanceof IntegerAddNode || op instanceof IntegerSubNode) { + IntegerArithmeticNode aritOp = (IntegerArithmeticNode) op; + if (aritOp.x() == base && loop.isOutsideLoop(aritOp.y())) { + return aritOp.y(); + } else if (aritOp.y() == base && loop.isOutsideLoop(aritOp.x())) { + return aritOp.x(); + } + } + return null; + } + + private ValueNode mul(ValueNode op, ValueNode base) { + if (op instanceof IntegerMulNode) { + IntegerMulNode mul = (IntegerMulNode) op; + if (mul.x() == base && loop.isOutsideLoop(mul.y())) { + return mul.y(); + } else if (mul.y() == base && loop.isOutsideLoop(mul.x())) { + return mul.x(); + } + } + if (op instanceof LeftShiftNode) { + LeftShiftNode shift = (LeftShiftNode) op; + if (shift.x() == base && shift.y().isConstant()) { + return ConstantNode.forInt(1 << shift.y().asConstant().asInt(), base.graph()); + } + } + return null; + } +} diff -r 60ca7d300b8f -r d50c788195a5 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopEx.java --- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopEx.java Fri Jun 15 13:16:43 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopEx.java Fri Jun 15 13:17:04 2012 +0200 @@ -30,7 +30,7 @@ private final Loop lirLoop; private LoopFragmentInside inside; private LoopFragmentWhole whole; - private boolean isCounted; //TODO (gd) detect + private CountedLoopInfo counted; //TODO (gd) detect private LoopsData data; LoopEx(Loop lirLoop, LoopsData data) { @@ -68,7 +68,7 @@ return null; } - public boolean isInvariant(Node n) { + public boolean isOutsideLoop(Node n) { return !whole().contains(n); } @@ -85,7 +85,11 @@ } public boolean isCounted() { - return isCounted; + return counted != null; + } + + public CountedLoopInfo counted() { + return counted; } public LoopEx parent() { diff -r 60ca7d300b8f -r d50c788195a5 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopFragment.java --- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopFragment.java Fri Jun 15 13:16:43 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopFragment.java Fri Jun 15 13:17:04 2012 +0200 @@ -156,8 +156,9 @@ } for (BeginNode earlyExit : earlyExits) { FrameState stateAfter = earlyExit.stateAfter(); - assert stateAfter != null; - nodes.mark(stateAfter); + if (stateAfter != null) { + nodes.mark(stateAfter); + } nodes.mark(earlyExit); for (ValueProxyNode proxy : earlyExit.proxies()) { nodes.mark(proxy); diff -r 60ca7d300b8f -r d50c788195a5 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopsData.java --- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopsData.java Fri Jun 15 13:16:43 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopsData.java Fri Jun 15 13:17:04 2012 +0200 @@ -24,8 +24,12 @@ import java.util.*; +import com.oracle.graal.compiler.loop.InductionVariable.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.graph.*; import com.oracle.graal.lir.cfg.*; import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.calc.*; public class LoopsData { private Map lirLoopToEx = new IdentityHashMap<>(); @@ -72,4 +76,72 @@ } return counted; } + + public void detectedCountedLoops() { + for (LoopEx loop : loops()) { + InductionVariables ivs = new InductionVariables(loop); + LoopBeginNode loopBegin = loop.loopBegin(); + FixedNode next = loopBegin.next(); + if (next instanceof IfNode) { + IfNode ifNode = (IfNode) next; + boolean negated = false; + if (!loopBegin.isLoopExit(ifNode.falseSuccessor())) { + if (!loopBegin.isLoopExit(ifNode.trueSuccessor())) { + continue; + } + negated = true; + } + BooleanNode ifTest = ifNode.compare(); + if (!(ifTest instanceof IntegerLessThanNode)) { + if (ifTest instanceof IntegerBelowThanNode) { + Debug.log("Ignored potential Counted loop at %s with |<|", loopBegin); + } + continue; + } + IntegerLessThanNode lessThan = (IntegerLessThanNode) ifTest; + Condition condition = null; + InductionVariable iv = null; + ValueNode limit = null; + if (loop.isOutsideLoop(lessThan.x())) { + iv = ivs.get(lessThan.y()); + if (iv != null) { + condition = lessThan.condition().mirror(); + limit = lessThan.x(); + } + } else if (loop.isOutsideLoop(lessThan.y())) { + iv = ivs.get(lessThan.x()); + if (iv != null) { + condition = lessThan.condition(); + limit = lessThan.y(); + } + } + if (condition == null) { + continue; + } + if (negated) { + condition = condition.negate(); + } + boolean oneOff = false; + switch (condition) { + case LE: + oneOff = true; // fall through + case LT: + if (iv.direction() != Direction.Up) { + continue; + } + break; + case GE: + oneOff = true; // fall through + case GT: + if (iv.direction() != Direction.Down) { + continue; + } + break; + default: throw GraalInternalError.shouldNotReachHere(); + } + // TODO (gd) + Debug.log("absorb %b %s", oneOff, limit); + } + } + } } diff -r 60ca7d300b8f -r d50c788195a5 graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java --- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java Fri Jun 15 13:16:43 2012 +0200 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java Fri Jun 15 13:17:04 2012 +0200 @@ -295,7 +295,7 @@ */ public NodeIterable getNewNodes(int mark) { final int index = mark; - return new NodeIterable() { + return new AbstractNodeIterable() { @Override public Iterator iterator() { return new NodeIterator(index); @@ -308,7 +308,7 @@ * @return an {@link Iterable} providing all the live nodes. */ public NodeIterable getNodes() { - return new NodeIterable() { + return new AbstractNodeIterable() { @Override public Iterator iterator() { return new NodeIterator(); @@ -385,7 +385,7 @@ */ public NodeIterable getNodes(final Class type) { final Node start = getStartNode(type); - return new NodeIterable() { + return new AbstractNodeIterable() { @Override public Iterator iterator() { return new TypedNodeIterator<>(start); diff -r 60ca7d300b8f -r d50c788195a5 graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeBitMap.java --- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeBitMap.java Fri Jun 15 13:16:43 2012 +0200 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeBitMap.java Fri Jun 15 13:17:04 2012 +0200 @@ -28,7 +28,7 @@ -public final class NodeBitMap extends NodeIterable{ +public final class NodeBitMap extends AbstractNodeIterable{ private final boolean autoGrow; private final BitSet bitMap; private final Graph graph; diff -r 60ca7d300b8f -r d50c788195a5 graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeInputsIterable.java --- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeInputsIterable.java Fri Jun 15 13:16:43 2012 +0200 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeInputsIterable.java Fri Jun 15 13:17:04 2012 +0200 @@ -25,7 +25,7 @@ import com.oracle.graal.graph.NodeClass.NodeClassIterator; import com.oracle.graal.graph.iterators.*; -public abstract class NodeInputsIterable extends NodeIterable { +public abstract class NodeInputsIterable extends AbstractNodeIterable { @Override public abstract NodeClassIterator iterator(); } diff -r 60ca7d300b8f -r d50c788195a5 graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeList.java --- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeList.java Fri Jun 15 13:16:43 2012 +0200 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeList.java Fri Jun 15 13:17:04 2012 +0200 @@ -25,13 +25,12 @@ import com.oracle.graal.graph.iterators.*; -public abstract class NodeList extends NodeIterable implements List { +public abstract class NodeList extends AbstractList implements NodeIterable { protected static final Node[] EMPTY_NODE_ARRAY = new Node[0]; protected Node[] nodes; private int size; - private int modCount; protected final int initialSize; protected NodeList() { @@ -327,46 +326,6 @@ } @Override - public boolean addAll(int index, Collection< ? extends T> c) { - throw new UnsupportedOperationException("not implemented"); - } - - @Override - public boolean removeAll(Collection< ? > c) { - throw new UnsupportedOperationException("not implemented"); - } - - @Override - public boolean retainAll(Collection< ? > c) { - throw new UnsupportedOperationException("not implemented"); - } - - @Override - public void add(int index, T element) { - throw new UnsupportedOperationException("not implemented"); - } - - @Override - public int lastIndexOf(Object o) { - throw new UnsupportedOperationException("not implemented"); - } - - @Override - public ListIterator listIterator() { - throw new UnsupportedOperationException("not implemented"); - } - - @Override - public ListIterator listIterator(int index) { - throw new UnsupportedOperationException("not implemented"); - } - - @Override - public List subList(int fromIndex, int toIndex) { - throw new UnsupportedOperationException("not implemented"); - } - - @Override public String toString() { StringBuilder sb = new StringBuilder(); sb.append('['); @@ -379,4 +338,41 @@ sb.append(']'); return sb.toString(); } + + @Override + public NodeIterable until(final T u) { + return new FilteredNodeIterable<>(this).until(u); + } + @Override + public NodeIterable until(final Class clazz) { + return new FilteredNodeIterable<>(this).until(clazz); + } + @Override + @SuppressWarnings("unchecked") + public NodeIterable filter(Class clazz) { + return (NodeIterable) new FilteredNodeIterable<>(this).and(NodePredicates.isA(clazz)); + } + @Override + public NodeIterable filterInterface(Class iface) { + return new FilteredNodeIterable<>(this).and(NodePredicates.isAInterface(iface)); + } + @Override + public FilteredNodeIterable filter(NodePredicate predicate) { + return new FilteredNodeIterable<>(this).and(predicate); + } + @Override + public FilteredNodeIterable nonNull() { + return new FilteredNodeIterable<>(this).and(NodePredicates.isNotNull()); + } + @Override + public NodeIterable distinct() { + return new FilteredNodeIterable<>(this).distinct(); + } + @Override + public T first() { + if (size() > 0) { + return get(0); + } + return null; + } } diff -r 60ca7d300b8f -r d50c788195a5 graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeSuccessorsIterable.java --- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeSuccessorsIterable.java Fri Jun 15 13:16:43 2012 +0200 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeSuccessorsIterable.java Fri Jun 15 13:17:04 2012 +0200 @@ -25,7 +25,7 @@ import com.oracle.graal.graph.NodeClass.NodeClassIterator; import com.oracle.graal.graph.iterators.*; -public abstract class NodeSuccessorsIterable extends NodeIterable { +public abstract class NodeSuccessorsIterable extends AbstractNodeIterable { @Override public abstract NodeClassIterator iterator(); } diff -r 60ca7d300b8f -r d50c788195a5 graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeUsagesList.java --- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeUsagesList.java Fri Jun 15 13:16:43 2012 +0200 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeUsagesList.java Fri Jun 15 13:17:04 2012 +0200 @@ -26,7 +26,7 @@ import com.oracle.graal.graph.iterators.*; -public final class NodeUsagesList extends NodeIterable { +public final class NodeUsagesList extends AbstractNodeIterable { protected static final Node[] EMPTY_NODE_ARRAY = new Node[0]; diff -r 60ca7d300b8f -r d50c788195a5 graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/AbstractNodeIterable.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/AbstractNodeIterable.java Fri Jun 15 13:17:04 2012 +0200 @@ -0,0 +1,97 @@ +/* + * Copyright (c) 2011, 2012, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.graph.iterators; + +import java.util.*; + +import com.oracle.graal.graph.*; + +public abstract class AbstractNodeIterable implements NodeIterable { + @Override + public NodeIterable until(final T u) { + return new FilteredNodeIterable<>(this).until(u); + } + @Override + public NodeIterable until(final Class clazz) { + return new FilteredNodeIterable<>(this).until(clazz); + } + @Override + @SuppressWarnings("unchecked") + public NodeIterable filter(Class clazz) { + return (NodeIterable) new FilteredNodeIterable<>(this).and(NodePredicates.isA(clazz)); + } + @Override + public NodeIterable filterInterface(Class iface) { + return new FilteredNodeIterable<>(this).and(NodePredicates.isAInterface(iface)); + } + @Override + public FilteredNodeIterable filter(NodePredicate predicate) { + return new FilteredNodeIterable<>(this).and(predicate); + } + @Override + public FilteredNodeIterable nonNull() { + return new FilteredNodeIterable<>(this).and(NodePredicates.isNotNull()); + } + @Override + public NodeIterable distinct() { + return new FilteredNodeIterable<>(this).distinct(); + } + @Override + public List snapshot() { + ArrayList list = new ArrayList<>(); + for (T n : this) { + list.add(n); + } + return list; + } + @Override + public T first() { + Iterator iterator = iterator(); + if (iterator.hasNext()) { + return iterator.next(); + } + return null; + } + @Override + public int count() { + int count = 0; + Iterator iterator = iterator(); + while (iterator.hasNext()) { + iterator.next(); + count++; + } + return count; + } + @Override + public boolean isEmpty() { + return !iterator().hasNext(); + } + @Override + public boolean isNotEmpty() { + return iterator().hasNext(); + } + @Override + public boolean contains(T node) { + return this.filter(NodePredicates.equals(node)).isNotEmpty(); + } +} diff -r 60ca7d300b8f -r d50c788195a5 graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/FilteredNodeIterable.java --- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/FilteredNodeIterable.java Fri Jun 15 13:16:43 2012 +0200 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/FilteredNodeIterable.java Fri Jun 15 13:17:04 2012 +0200 @@ -26,7 +26,7 @@ import com.oracle.graal.graph.*; -public class FilteredNodeIterable extends NodeIterable { +public class FilteredNodeIterable extends AbstractNodeIterable { private final NodeIterable nodeIterable; private NodePredicate predicate = NodePredicates.alwaysTrue(); private NodePredicate until = NodePredicates.isNull(); diff -r 60ca7d300b8f -r d50c788195a5 graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/NodeIterable.java --- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/NodeIterable.java Fri Jun 15 13:16:43 2012 +0200 +++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/NodeIterable.java Fri Jun 15 13:17:04 2012 +0200 @@ -1,5 +1,5 @@ /* - * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved. + * Copyright (c) 2011, 2012, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it @@ -26,59 +26,32 @@ import com.oracle.graal.graph.*; -public abstract class NodeIterable implements Iterable { - public NodeIterable until(final T u) { - return new FilteredNodeIterable<>(this).until(u); - } - public NodeIterable until(final Class clazz) { - return new FilteredNodeIterable<>(this).until(clazz); - } - @SuppressWarnings("unchecked") - public NodeIterable filter(Class clazz) { - return (NodeIterable) new FilteredNodeIterable<>(this).and(NodePredicates.isA(clazz)); - } - public NodeIterable filterInterface(Class iface) { - return new FilteredNodeIterable<>(this).and(NodePredicates.isAInterface(iface)); - } - public FilteredNodeIterable filter(NodePredicate predicate) { - return new FilteredNodeIterable<>(this).and(predicate); - } - public FilteredNodeIterable nonNull() { - return new FilteredNodeIterable<>(this).and(NodePredicates.isNotNull()); - } - public NodeIterable distinct() { - return new FilteredNodeIterable<>(this).distinct(); - } - public List snapshot() { - ArrayList list = new ArrayList<>(); - for (T n : this) { - list.add(n); - } - return list; - } - public T first() { - Iterator iterator = iterator(); - if (iterator.hasNext()) { - return iterator.next(); - } - return null; - } - public int count() { - int count = 0; - Iterator iterator = iterator(); - while (iterator.hasNext()) { - iterator.next(); - count++; - } - return count; - } - public boolean isEmpty() { - return !iterator().hasNext(); - } - public boolean isNotEmpty() { - return iterator().hasNext(); - } - public boolean contains(T node) { - return this.filter(NodePredicates.equals(node)).isNotEmpty(); - } +public interface NodeIterable extends Iterable { + + NodeIterable until(T u); + + NodeIterable until(Class< ? extends T> clazz); + + NodeIterable filter(Class clazz); + + NodeIterable filterInterface(Class< ? > iface); + + FilteredNodeIterable filter(NodePredicate predicate); + + FilteredNodeIterable nonNull(); + + NodeIterable distinct(); + + List snapshot(); + + T first(); + + int count(); + + boolean isEmpty(); + + boolean isNotEmpty(); + + boolean contains(T node); + } diff -r 60ca7d300b8f -r d50c788195a5 graal/com.oracle.graal.jtt/src/com/oracle/graal/jtt/optimize/ArrayCopy02.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.jtt/src/com/oracle/graal/jtt/optimize/ArrayCopy02.java Fri Jun 15 13:17:04 2012 +0200 @@ -0,0 +1,124 @@ +/* + * Copyright (c) 2011, 2012, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.jtt.optimize; + +import org.junit.*; + +/* + * Tests calls to the array copy method. + */ +public class ArrayCopy02 { + + public static int[] src = new int[]{0, 1, 2, 3, 4, 5}; + public static int[] dest0 = new int[]{5, 4, 3, 2, 1, 0}; + public static int[] dest = new int[]{5, 4, 3, 2, 1, 0}; + + @Before + public void setUp() { + System.currentTimeMillis(); + for (int i = 0; i < dest.length; i++) { + dest[i] = dest0[i]; + } + } + + public static int[] test(int srcPos, int destPos, int length) { + System.arraycopy(src, srcPos, dest, destPos, length); + return dest; + } + + @Test + public void run0() throws Throwable { + Assert.assertArrayEquals(new int[] {5, 4, 3, 2, 1, 0}, test(0, 0, 0)); + } + + @Test(expected = java.lang.IndexOutOfBoundsException.class) + public void run1() throws Throwable { + test(0, 0, -1); + } + + @Test(expected = java.lang.IndexOutOfBoundsException.class) + public void run2() throws Throwable { + test(-1, 0, 0); + } + + @Test(expected = java.lang.IndexOutOfBoundsException.class) + public void run3() throws Throwable { + test(0, -1, 0); + } + + @Test + public void run4() throws Throwable { + Assert.assertArrayEquals(new int[] {0, 1, 3, 2, 1, 0}, test(0, 0, 2)); + } + + @Test(expected = java.lang.IndexOutOfBoundsException.class) + public void run5() throws Throwable { + test(0, 1, 6); + } + + @Test(expected = java.lang.IndexOutOfBoundsException.class) + public void run6() throws Throwable { + test(1, 0, 6); + } + + @Test(expected = java.lang.IndexOutOfBoundsException.class) + public void run7() throws Throwable { + test(1, 1, -1); + } + + @Test + public void run8() throws Throwable { + Assert.assertArrayEquals(new int[] {5, 0, 1, 2, 1, 0}, test(0, 1, 2)); + } + + @Test + public void run9() throws Throwable { + Assert.assertArrayEquals(new int[] {1, 2, 3, 2, 1, 0}, test(1, 0, 2)); + } + + @Test + public void run10() throws Throwable { + Assert.assertArrayEquals(new int[] {5, 1, 2, 2, 1, 0}, test(1, 1, 2)); + } + + @Test + public void run11() throws Throwable { + Assert.assertArrayEquals(new int[] {0, 1, 2, 3, 4, 5}, test(0, 0, 6)); + } + + @Test + public void run12() throws Throwable { + Assert.assertArrayEquals(new int[] {5, 0, 1, 2, 3, 4}, test(0, 1, 5)); + } + + @Test + public void run13() throws Throwable { + Assert.assertArrayEquals(new int[] {1, 2, 3, 4, 5, 0}, test(1, 0, 5)); + } + + @Test + public void run14() throws Throwable { + Assert.assertArrayEquals(new int[] {5, 1, 2, 3, 4, 5}, test(1, 1, 5)); + } + +} diff -r 60ca7d300b8f -r d50c788195a5 graal/com.oracle.graal.jtt/src/com/oracle/graal/jtt/optimize/ArrayCopy03.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.jtt/src/com/oracle/graal/jtt/optimize/ArrayCopy03.java Fri Jun 15 13:17:04 2012 +0200 @@ -0,0 +1,128 @@ +/* + * Copyright (c) 2011, 2012, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.jtt.optimize; + +import org.junit.*; + +/* + * Tests calls to the array copy method. + */ +public class ArrayCopy03 { + + public static byte[] src = new byte[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; + public static byte[] dest0 = new byte[]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0}; + public static byte[] dest = new byte[]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0}; + + @Before + public void setUp() { + System.currentTimeMillis(); + for (int i = 0; i < dest.length; i++) { + dest[i] = dest0[i]; + } + } + + public static byte[] test(int srcPos, int destPos, int length) { + System.arraycopy(src, srcPos, dest, destPos, length); + return dest; + } + + @Test + public void run0() throws Throwable { + Assert.assertArrayEquals(new byte[] {10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0}, test(0, 0, 0)); + } + + @Test(expected = java.lang.IndexOutOfBoundsException.class) + public void run1() throws Throwable { + test(0, 0, -1); + } + + @Test(expected = java.lang.IndexOutOfBoundsException.class) + public void run2() throws Throwable { + test(-1, 0, 0); + } + + @Test(expected = java.lang.IndexOutOfBoundsException.class) + public void run3() throws Throwable { + test(0, -1, 0); + } + + @Test + public void run4() throws Throwable { + Assert.assertArrayEquals(new byte[] {0, 1, 8, 7, 6, 5, 4, 3, 2, 1, 0}, test(0, 0, 2)); + } + + @Test(expected = java.lang.IndexOutOfBoundsException.class) + public void run5() throws Throwable { + test(0, 1, 11); + } + + @Test(expected = java.lang.IndexOutOfBoundsException.class) + public void run6() throws Throwable { + test(1, 0, 11); + } + + @Test(expected = java.lang.IndexOutOfBoundsException.class) + public void run7() throws Throwable { + test(1, 1, -1); + } + + @Test + public void run8() throws Throwable { + Assert.assertArrayEquals(new byte[] {10, 0, 1, 7, 6, 5, 4, 3, 2, 1, 0}, test(0, 1, 2)); + } + + @Test + public void run9() throws Throwable { + Assert.assertArrayEquals(new byte[] {1, 2, 8, 7, 6, 5, 4, 3, 2, 1, 0}, test(1, 0, 2)); + } + + @Test + public void run10() throws Throwable { + Assert.assertArrayEquals(new byte[] {10, 1, 2, 7, 6, 5, 4, 3, 2, 1, 0}, test(1, 1, 2)); + } + + @Test + public void run11() throws Throwable { + Assert.assertArrayEquals(new byte[] {0, 1, 2, 3, 4, 5, 4, 3, 2, 1, 0}, test(0, 0, 6)); + } + + @Test + public void run12() throws Throwable { + Assert.assertArrayEquals(new byte[] {10, 0, 1, 2, 3, 4, 4, 3, 2, 1, 0}, test(0, 1, 5)); + } + + @Test + public void run13() throws Throwable { + Assert.assertArrayEquals(new byte[] {1, 2, 3, 4, 5, 5, 4, 3, 2, 1, 0}, test(1, 0, 5)); + } + + @Test + public void run14() throws Throwable { + Assert.assertArrayEquals(new byte[] {10, 1, 2, 3, 4, 5, 4, 3, 2, 1, 0}, test(1, 1, 5)); + } + + @Test + public void run15() throws Throwable { + Assert.assertArrayEquals(new byte[] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, test(0, 0, 11)); + } +} diff -r 60ca7d300b8f -r d50c788195a5 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/BeginNode.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/BeginNode.java Fri Jun 15 13:16:43 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/BeginNode.java Fri Jun 15 13:17:04 2012 +0200 @@ -143,7 +143,7 @@ } public NodeIterable getBlockNodes() { - return new NodeIterable() { + return new AbstractNodeIterable() { @Override public Iterator iterator() { return new BlockNodeIterator(BeginNode.this); diff -r 60ca7d300b8f -r d50c788195a5 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/LoopBeginNode.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/LoopBeginNode.java Fri Jun 15 13:16:43 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/LoopBeginNode.java Fri Jun 15 13:17:04 2012 +0200 @@ -155,4 +155,8 @@ public void simplify(SimplifierTool tool) { // nothing yet } + + public boolean isLoopExit(BeginNode begin) { + return begin instanceof LoopExitNode && ((LoopExitNode) begin).loopBegin() == this; + } } diff -r 60ca7d300b8f -r d50c788195a5 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/PhiNode.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/PhiNode.java Fri Jun 15 13:16:43 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/PhiNode.java Fri Jun 15 13:17:04 2012 +0200 @@ -191,6 +191,19 @@ return differentValue; } + public ValueNode singleBackValue() { + assert merge() instanceof LoopBeginNode; + ValueNode differentValue = null; + for (ValueNode n : values().subList(merge().forwardEndCount(), values().size())) { + if (differentValue == null) { + differentValue = n; + } else if (differentValue != n) { + return null; + } + } + return differentValue; + } + @Override public ValueNode canonical(CanonicalizerTool tool) { ValueNode singleValue = singleValue(); diff -r 60ca7d300b8f -r d50c788195a5 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerArithmeticNode.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerArithmeticNode.java Fri Jun 15 13:16:43 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerArithmeticNode.java Fri Jun 15 13:17:04 2012 +0200 @@ -59,4 +59,30 @@ throw ValueNodeUtil.shouldNotReachHere(); } } + + public static IntegerSubNode sub(ValueNode v1, ValueNode v2) { + assert v1.kind() == v2.kind() && v1.graph() == v2.graph(); + Graph graph = v1.graph(); + switch(v1.kind()) { + case Int: + return graph.unique(new IntegerSubNode(Kind.Int, v1, v2)); + case Long: + return graph.unique(new IntegerSubNode(Kind.Long, v1, v2)); + default: + throw ValueNodeUtil.shouldNotReachHere(); + } + } + + public static IntegerDivNode div(ValueNode v1, ValueNode v2) { + assert v1.kind() == v2.kind() && v1.graph() == v2.graph(); + Graph graph = v1.graph(); + switch(v1.kind()) { + case Int: + return graph.unique(new IntegerDivNode(Kind.Int, v1, v2)); + case Long: + return graph.unique(new IntegerDivNode(Kind.Long, v1, v2)); + default: + throw ValueNodeUtil.shouldNotReachHere(); + } + } } diff -r 60ca7d300b8f -r d50c788195a5 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/NegateNode.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/NegateNode.java Fri Jun 15 13:16:43 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/NegateNode.java Fri Jun 15 13:17:04 2012 +0200 @@ -38,12 +38,12 @@ } /** - * Creates new NegateOp instance. + * Creates new NegateNode instance. * * @param x the instruction producing the value that is input to this instruction */ public NegateNode(ValueNode x) { - super(StampFactory.forKind(x.kind())); + super(x.stamp() instanceof IntegerStamp ? StampFactory.negate((IntegerStamp) x.stamp()) : StampFactory.forKind(x.kind())); this.x = x; } diff -r 60ca7d300b8f -r d50c788195a5 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/StampFactory.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/StampFactory.java Fri Jun 15 13:16:43 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/StampFactory.java Fri Jun 15 13:17:04 2012 +0200 @@ -129,6 +129,14 @@ } } + public static Stamp negate(IntegerStamp stamp) { + Kind kind = stamp.kind(); + if (stamp.lowerBound() != kind.minValue()) { + return new IntegerStamp(kind, -stamp.upperBound(), -stamp.lowerBound()); + } + return forKind(kind); + } + public static Stamp object() { return objectStamp; } diff -r 60ca7d300b8f -r d50c788195a5 graal/com.oracle.graal.nodes/src/com/oracle/graal/util/NodeIterators.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/util/NodeIterators.java Fri Jun 15 13:16:43 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/util/NodeIterators.java Fri Jun 15 13:17:04 2012 +0200 @@ -30,7 +30,7 @@ public class NodeIterators { public static NodeIterable dominators(final FixedNode n) { - return new NodeIterable() { + return new AbstractNodeIterable() { @Override public Iterator iterator() { return new NodeIterator(){ diff -r 60ca7d300b8f -r d50c788195a5 hotspot/.cproject --- a/hotspot/.cproject Fri Jun 15 13:16:43 2012 +0200 +++ b/hotspot/.cproject Fri Jun 15 13:17:04 2012 +0200 @@ -43,6 +43,7 @@ +