# HG changeset patch # User Gilles Duboscq # Date 1339686579 -7200 # Node ID 9f3250602d691009f8b42e61d2a290caa050c946 # Parent 282e2d94b420ceba6782fc465a1aa25aa3d1d6a8 Preliminary counted loop detection diff -r 282e2d94b420 -r 9f3250602d69 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 Thu Jun 14 17:09:39 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 282e2d94b420 -r 9f3250602d69 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 Thu Jun 14 17:09:39 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 282e2d94b420 -r 9f3250602d69 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 Thu Jun 14 17:09:39 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 282e2d94b420 -r 9f3250602d69 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 Thu Jun 14 17:09:39 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 282e2d94b420 -r 9f3250602d69 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 Thu Jun 14 17:09:39 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 282e2d94b420 -r 9f3250602d69 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 Thu Jun 14 17:09:39 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 282e2d94b420 -r 9f3250602d69 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 Thu Jun 14 14:14:06 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopEx.java Thu Jun 14 17:09:39 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 282e2d94b420 -r 9f3250602d69 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 Thu Jun 14 14:14:06 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopFragment.java Thu Jun 14 17:09:39 2012 +0200 @@ -157,8 +157,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 282e2d94b420 -r 9f3250602d69 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 Thu Jun 14 14:14:06 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopsData.java Thu Jun 14 17:09:39 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,71 @@ } 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(); + } + Debug.log("Counted loop : %s stride %s and limit%s %s", iv.valueNode().kind(), iv.isConstantStride() ? iv.constantStride() : iv.strideNode(), oneOff ? " (oneOff)" : "", limit instanceof ConstantNode ? limit.asConstant().asLong() : limit, loopBegin); + } + } + } } diff -r 282e2d94b420 -r 9f3250602d69 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 Thu Jun 14 14:14:06 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/LoopBeginNode.java Thu Jun 14 17:09:39 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 282e2d94b420 -r 9f3250602d69 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 Thu Jun 14 14:14:06 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/PhiNode.java Thu Jun 14 17:09:39 2012 +0200 @@ -192,6 +192,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();