# HG changeset patch # User Doug Simon # Date 1349611716 -7200 # Node ID c8763a2deb0c12248380891e04ff4d81c192bc61 # Parent c612043278e9d3a5db89365c34734383ab182d36 rename packages in graal.loop to match project name diff -r c612043278e9 -r c8763a2deb0c graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/LoopUnswitchTest.java --- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/LoopUnswitchTest.java Sun Oct 07 12:44:05 2012 +0200 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/LoopUnswitchTest.java Sun Oct 07 14:08:36 2012 +0200 @@ -25,9 +25,9 @@ import org.junit.*; import com.oracle.graal.compiler.phases.*; -import com.oracle.graal.compiler.phases.loop.*; import com.oracle.graal.debug.*; import com.oracle.graal.graph.*; +import com.oracle.graal.loop.phases.*; import com.oracle.graal.nodes.*; public class LoopUnswitchTest extends GraalCompilerTest { diff -r c612043278e9 -r c8763a2deb0c graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java --- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Sun Oct 07 12:44:05 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Sun Oct 07 14:08:36 2012 +0200 @@ -35,13 +35,13 @@ import com.oracle.graal.compiler.phases.PhasePlan.PhasePosition; import com.oracle.graal.compiler.phases.ea.*; import com.oracle.graal.compiler.phases.ea.experimental.*; -import com.oracle.graal.compiler.phases.loop.*; import com.oracle.graal.compiler.schedule.*; import com.oracle.graal.compiler.target.*; import com.oracle.graal.debug.*; import com.oracle.graal.lir.*; import com.oracle.graal.lir.asm.*; import com.oracle.graal.lir.cfg.*; +import com.oracle.graal.loop.phases.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.spi.*; diff -r c612043278e9 -r c8763a2deb0c graal/com.oracle.graal.loop/src/com/oracle/graal/compiler/loop/BasicInductionVariable.java --- a/graal/com.oracle.graal.loop/src/com/oracle/graal/compiler/loop/BasicInductionVariable.java Sun Oct 07 12:44:05 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,129 +0,0 @@ -/* - * 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.isStrictlyPositive()) { - dir = Direction.Up; - } else if (integerStamp.isStrictlyNegative()) { - 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 c612043278e9 -r c8763a2deb0c graal/com.oracle.graal.loop/src/com/oracle/graal/compiler/loop/CountedLoopInfo.java --- a/graal/com.oracle.graal.loop/src/com/oracle/graal/compiler/loop/CountedLoopInfo.java Sun Oct 07 12:44:05 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,80 +0,0 @@ -/* - * 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.compiler.loop.InductionVariable.*; -import com.oracle.graal.nodes.*; -import com.oracle.graal.nodes.calc.*; - -public class CountedLoopInfo { - private final LoopEx loop; - private InductionVariable iv; - private ValueNode end; - private boolean oneOff; - - CountedLoopInfo(LoopEx loop, InductionVariable iv, ValueNode end, boolean oneOff) { - this.loop = loop; - this.iv = iv; - this.end = end; - this.oneOff = oneOff; - } - - public ValueNode maxTripCountNode() { - //TODO (gd) stuarte and respect oneOff - return IntegerArithmeticNode.div(IntegerArithmeticNode.sub(end, iv.initNode()), iv.strideNode()); - } - - public boolean isConstantMaxTripCount() { - return end instanceof ConstantNode && iv.isConstantInit() && iv.isConstantStride(); - } - - public long constantMaxTripCount() { - long off = oneOff ? iv.direction() == Direction.Up ? 1 : -1 : 0; - long max = (((ConstantNode) end).asConstant().asLong() + off - iv.constantInit()) / iv.constantStride(); - return Math.max(0, max); - } - - 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(); - } - - @Override - public String toString() { - return "iv=" + iv + " until " + end + (oneOff ? iv.direction() == Direction.Up ? "+1" : "-1" : ""); - } -} diff -r c612043278e9 -r c8763a2deb0c graal/com.oracle.graal.loop/src/com/oracle/graal/compiler/loop/DerivedOffsetInductionVariable.java --- a/graal/com.oracle.graal.loop/src/com/oracle/graal/compiler/loop/DerivedOffsetInductionVariable.java Sun Oct 07 12:44:05 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,132 +0,0 @@ -/* - * 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 c612043278e9 -r c8763a2deb0c graal/com.oracle.graal.loop/src/com/oracle/graal/compiler/loop/DerivedScaledInductionVariable.java --- a/graal/com.oracle.graal.loop/src/com/oracle/graal/compiler/loop/DerivedScaledInductionVariable.java Sun Oct 07 12:44:05 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,112 +0,0 @@ -/* - * 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.isStrictlyPositive()) { - return base.direction(); - } else if (integerStamp.isStrictlyNegative()) { - 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 c612043278e9 -r c8763a2deb0c graal/com.oracle.graal.loop/src/com/oracle/graal/compiler/loop/InductionVariable.java --- a/graal/com.oracle.graal.loop/src/com/oracle/graal/compiler/loop/InductionVariable.java Sun Oct 07 12:44:05 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,64 +0,0 @@ -/* - * 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 c612043278e9 -r c8763a2deb0c graal/com.oracle.graal.loop/src/com/oracle/graal/compiler/loop/InductionVariables.java --- a/graal/com.oracle.graal.loop/src/com/oracle/graal/compiler/loop/InductionVariables.java Sun Oct 07 12:44:05 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,122 +0,0 @@ -/* - * 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 c612043278e9 -r c8763a2deb0c graal/com.oracle.graal.loop/src/com/oracle/graal/compiler/loop/LoopEx.java --- a/graal/com.oracle.graal.loop/src/com/oracle/graal/compiler/loop/LoopEx.java Sun Oct 07 12:44:05 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,168 +0,0 @@ -/* - * 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.api.meta.*; -import com.oracle.graal.debug.*; -import com.oracle.graal.graph.*; -import com.oracle.graal.graph.iterators.*; -import com.oracle.graal.lir.cfg.*; -import com.oracle.graal.nodes.*; -import com.oracle.graal.nodes.calc.*; - -public class LoopEx { - private final Loop lirLoop; - private LoopFragmentInside inside; - private LoopFragmentWhole whole; - private CountedLoopInfo counted; //TODO (gd) detect - private LoopsData data; - - LoopEx(Loop lirLoop, LoopsData data) { - this.lirLoop = lirLoop; - this.data = data; - } - - public Loop lirLoop() { - return lirLoop; - } - - public LoopFragmentInside inside() { - if (inside == null) { - inside = new LoopFragmentInside(this); - } - return inside; - } - - public LoopFragmentWhole whole() { - if (whole == null) { - whole = new LoopFragmentWhole(this); - } - return whole; - } - - @SuppressWarnings("unused") - public LoopFragmentInsideFrom insideFrom(FixedNode point) { - // TODO (gd) - return null; - } - - @SuppressWarnings("unused") - public LoopFragmentInsideBefore insideBefore(FixedNode point) { - // TODO (gd) - return null; - } - - public boolean isOutsideLoop(Node n) { - return !whole().contains(n); - } - - public LoopBeginNode loopBegin() { - return lirLoop().loopBegin(); - } - - public FixedNode predecessor() { - return (FixedNode) loopBegin().forwardEnd().predecessor(); - } - - public FixedNode entryPoint() { - return loopBegin().forwardEnd(); - } - - public boolean isCounted() { - return counted != null; - } - - public CountedLoopInfo counted() { - return counted; - } - - public LoopEx parent() { - if (lirLoop.parent == null) { - return null; - } - return data.loop(lirLoop.parent); - } - - public int size() { - return whole().nodes().count(); - } - - @Override - public String toString() { - return (isCounted() ? "CountedLoop [" + counted() + "] " : "Loop ") + "(depth=" + lirLoop().depth + ") " + loopBegin(); - } - - private class InvariantPredicate extends NodePredicate { - @Override - public boolean apply(Node n) { - return isOutsideLoop(n); - } - } - - public void reassociateInvariants() { - InvariantPredicate invariant = new InvariantPredicate(); - StructuredGraph graph = (StructuredGraph) loopBegin().graph(); - for (BinaryNode binary : whole().nodes().filter(BinaryNode.class)) { - if (!BinaryNode.canTryReassociate(binary)) { - continue; - } - BinaryNode result = BinaryNode.reassociate(binary, invariant); - if (result != binary) { - Debug.log(MetaUtil.format("%H::%n", Debug.contextLookup(ResolvedJavaMethod.class)) + " : Reassociated %s into %s", binary, result); - graph.replaceFloating(binary, result); - } - } - } - - public void setCounted(CountedLoopInfo countedLoopInfo) { - counted = countedLoopInfo; - } - - public LoopsData loopsData() { - return data; - } - - public NodeBitMap nodesInLoopFrom(BeginNode point, BeginNode until) { - Collection blocks = new LinkedList<>(); - Collection exits = new LinkedList<>(); - Queue work = new LinkedList<>(); - ControlFlowGraph cfg = loopsData().controlFlowGraph(); - work.add(cfg.blockFor(point)); - Block untilBlock = until != null ? cfg.blockFor(until) : null; - while (!work.isEmpty()) { - Block b = work.remove(); - if (b == untilBlock) { - continue; - } - if (lirLoop().exits.contains(b)) { - exits.add(b.getBeginNode()); - } else if (lirLoop().blocks.contains(b)) { - blocks.add(b.getBeginNode()); - work.addAll(b.getDominated()); - } - } - return LoopFragment.computeNodes(point.graph(), blocks, exits); - } -} diff -r c612043278e9 -r c8763a2deb0c graal/com.oracle.graal.loop/src/com/oracle/graal/compiler/loop/LoopFragment.java --- a/graal/com.oracle.graal.loop/src/com/oracle/graal/compiler/loop/LoopFragment.java Sun Oct 07 12:44:05 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,303 +0,0 @@ -/* - * 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.graph.Graph.DuplicationReplacement; -import com.oracle.graal.graph.iterators.*; -import com.oracle.graal.lir.cfg.*; -import com.oracle.graal.nodes.*; -import com.oracle.graal.nodes.PhiNode.PhiType; -import com.oracle.graal.nodes.VirtualState.NodeClosure; -import com.oracle.graal.nodes.VirtualState.VirtualClosure; - - -public abstract class LoopFragment { - private final LoopEx loop; - private final LoopFragment original; - protected NodeBitMap nodes; - protected boolean nodesReady; - private Map duplicationMap; - - public LoopFragment(LoopEx loop) { - this(loop, null); - this.nodesReady = true; - } - - public LoopFragment(LoopEx loop, LoopFragment original) { - this.loop = loop; - this.original = original; - this.nodesReady = false; - } - - public LoopEx loop() { - return loop; - } - - public abstract LoopFragment duplicate(); - - public abstract void insertBefore(LoopEx l); - - public void disconnect() { - // TODO (gd) possibly abstract - } - - public boolean contains(Node n) { - return nodes().contains(n); - } - - @SuppressWarnings("unchecked") - public New getDuplicatedNode(Old n) { - assert isDuplicate(); - return (New) duplicationMap.get(n); - } - - protected void putDuplicatedNode(Old oldNode, New newNode) { - duplicationMap.put(oldNode, newNode); - } - - public boolean isDuplicate() { - return original != null; - } - - public LoopFragment original() { - return original; - } - - public abstract NodeIterable nodes(); - - public StructuredGraph graph() { - LoopEx l; - if (isDuplicate()) { - l = original().loop(); - } else { - l = loop(); - } - return (StructuredGraph) l.loopBegin().graph(); - } - - protected abstract DuplicationReplacement getDuplicationReplacement(); - - protected abstract void finishDuplication(); - - protected void patchNodes(final DuplicationReplacement dataFix) { - if (isDuplicate() && !nodesReady) { - assert !original.isDuplicate(); - final DuplicationReplacement cfgFix = original().getDuplicationReplacement(); - DuplicationReplacement dr; - if (cfgFix == null && dataFix != null) { - dr = dataFix; - } else if (cfgFix != null && dataFix == null) { - dr = cfgFix; - } else if (cfgFix != null && dataFix != null) { - dr = new DuplicationReplacement() { - @Override - public Node replacement(Node o) { - Node r1 = dataFix.replacement(o); - if (r1 != o) { - assert cfgFix.replacement(o) == o; - return r1; - } - Node r2 = cfgFix.replacement(o); - if (r2 != o) { - return r2; - } - return o; - } - }; - } else { - dr = new DuplicationReplacement() { - @Override - public Node replacement(Node o) { - return o; - } - }; - } - duplicationMap = graph().addDuplicates(original().nodes(), dr); - finishDuplication(); - nodesReady = true; - } else { - //TODO (gd) apply fix ? - } - } - - protected static NodeBitMap computeNodes(Graph graph, Collection blocks) { - return computeNodes(graph, blocks, Collections.emptyList()); - } - - protected static NodeBitMap computeNodes(Graph graph, Collection blocks, Collection earlyExits) { - final NodeBitMap nodes = graph.createNodeBitMap(true); - for (BeginNode b : blocks) { - for (Node n : b.getBlockNodes()) { - if (n instanceof Invoke) { - nodes.mark(((Invoke) n).callTarget()); - } - if (n instanceof StateSplit) { - FrameState stateAfter = ((StateSplit) n).stateAfter(); - if (stateAfter != null) { - nodes.mark(stateAfter); - } - } - nodes.mark(n); - } - } - for (BeginNode earlyExit : earlyExits) { - FrameState stateAfter = earlyExit.stateAfter(); - if (stateAfter != null) { - nodes.mark(stateAfter); - stateAfter.applyToVirtual(new VirtualClosure() { - @Override - public void apply(VirtualState node) { - nodes.mark(node); - } - }); - } - nodes.mark(earlyExit); - for (ValueProxyNode proxy : earlyExit.proxies()) { - nodes.mark(proxy); - } - } - - for (BeginNode b : blocks) { - for (Node n : b.getBlockNodes()) { - for (Node usage : n.usages()) { - markFloating(usage, nodes); - } - } - } - - return nodes; - } - - private static boolean markFloating(Node n, NodeBitMap loopNodes) { - if (loopNodes.isMarked(n)) { - return true; - } - if (n instanceof FixedNode) { - return false; - } - boolean mark = false; - if (n instanceof PhiNode) { - PhiNode phi = (PhiNode) n; - mark = loopNodes.isMarked(phi.merge()); - if (mark) { - loopNodes.mark(n); - } else { - return false; - } - } - for (Node usage : n.usages()) { - if (markFloating(usage, loopNodes)) { - mark = true; - } - } - if (mark) { - loopNodes.mark(n); - return true; - } - return false; - } - - public static Collection toHirBlocks(Collection blocks) { - List hir = new ArrayList<>(blocks.size()); - for (Block b : blocks) { - hir.add(b.getBeginNode()); - } - return hir; - } - - /** - * Merges the early exits (i.e. loop exits) that were duplicated as part of this fragment, with the original fragment's exits. - */ - protected void mergeEarlyExits() { - assert isDuplicate(); - StructuredGraph graph = graph(); - for (BeginNode earlyExit : LoopFragment.toHirBlocks(original().loop().lirLoop().exits)) { - FixedNode next = earlyExit.next(); - if (earlyExit.isDeleted() || !this.original().contains(earlyExit)) { - continue; - } - BeginNode newEarlyExit = getDuplicatedNode(earlyExit); - if (newEarlyExit == null) { - continue; - } - MergeNode merge = graph.add(new MergeNode()); - merge.setProbability(next.probability()); - EndNode originalEnd = graph.add(new EndNode()); - EndNode newEnd = graph.add(new EndNode()); - merge.addForwardEnd(originalEnd); - merge.addForwardEnd(newEnd); - earlyExit.setNext(originalEnd); - newEarlyExit.setNext(newEnd); - merge.setNext(next); - - FrameState exitState = earlyExit.stateAfter(); - FrameState newExitState = newEarlyExit.stateAfter(); - FrameState state = null; - if (exitState != null) { - state = exitState.duplicateWithVirtualState(); - merge.setStateAfter(state); - } - - for (Node anchored : earlyExit.anchored().snapshot()) { - anchored.replaceFirstInput(earlyExit, merge); - } - - for (final ValueProxyNode vpn : earlyExit.proxies().snapshot()) { - final ValueNode replaceWith; - ValueProxyNode newVpn = getDuplicatedNode(vpn); - if (newVpn != null) { - PhiNode phi = graph.add(vpn.type() == PhiType.Value ? new PhiNode(vpn.kind(), merge) : new PhiNode(vpn.type(), merge)); - phi.addInput(vpn); - phi.addInput(newVpn); - replaceWith = phi; - } else { - replaceWith = vpn.value(); - } - if (state != null) { - state.applyToNonVirtual(new NodeClosure() { - @Override - public void apply(Node from, ValueNode node) { - if (node == vpn) { - from.replaceFirstInput(vpn, replaceWith); - } - } - }); - } - for (Node usage : vpn.usages().snapshot()) { - if (!merge.isPhiAtMerge(usage)) { - if (usage instanceof VirtualState) { - VirtualState stateUsage = (VirtualState) usage; - if (exitState.isPartOfThisState(stateUsage) || newExitState.isPartOfThisState(stateUsage)) { - continue; - } - } - usage.replaceFirstInput(vpn, replaceWith); - } - } - } - } - } -} diff -r c612043278e9 -r c8763a2deb0c graal/com.oracle.graal.loop/src/com/oracle/graal/compiler/loop/LoopFragmentInside.java --- a/graal/com.oracle.graal.loop/src/com/oracle/graal/compiler/loop/LoopFragmentInside.java Sun Oct 07 12:44:05 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,270 +0,0 @@ -/* - * 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.Graph.DuplicationReplacement; -import com.oracle.graal.graph.*; -import com.oracle.graal.graph.iterators.*; -import com.oracle.graal.nodes.*; -import com.oracle.graal.nodes.PhiNode.PhiType; -import com.oracle.graal.nodes.VirtualState.NodeClosure; -import com.oracle.graal.nodes.util.*; - - -public class LoopFragmentInside extends LoopFragment { - /** mergedInitializers. - * When an inside fragment's (loop)ends are merged to create a unique exit point, - * some phis must be created : they phis together all the back-values of the loop-phis - * These can then be used to update the loop-phis' forward edge value ('initializer') in the peeling case. - * In the unrolling case they will be used as the value that replace the loop-phis of the duplicated inside fragment - */ - private Map mergedInitializers; - private final DuplicationReplacement dataFixBefore = new DuplicationReplacement() { - @Override - public Node replacement(Node oriInput) { - if (!(oriInput instanceof ValueNode)) { - return oriInput; - } - return prim((ValueNode) oriInput); - } - }; - - public LoopFragmentInside(LoopEx loop) { - super(loop); - } - - public LoopFragmentInside(LoopFragmentInside original) { - super(null, original); - } - - @Override - public LoopFragmentInside duplicate() { - assert !isDuplicate(); - return new LoopFragmentInside(this); - } - - @Override - public LoopFragmentInside original() { - return (LoopFragmentInside) super.original(); - } - - @SuppressWarnings("unused") - public void appendInside(LoopEx loop) { - // TODO (gd) - } - - @Override - public LoopEx loop() { - assert !this.isDuplicate(); - return super.loop(); - } - - @Override - public void insertBefore(LoopEx loop) { - assert this.isDuplicate() && this.original().loop() == loop; - - patchNodes(dataFixBefore); - - BeginNode end = mergeEnds(); - - original().patchPeeling(this); - - mergeEarlyExits(); - - BeginNode entry = getDuplicatedNode(loop.loopBegin()); - FrameState state = entry.stateAfter(); - if (state != null) { - entry.setStateAfter(null); - GraphUtil.killWithUnusedFloatingInputs(state); - } - loop.entryPoint().replaceAtPredecessor(entry); - end.setProbability(loop.entryPoint().probability()); - end.setNext(loop.entryPoint()); - } - - @Override - public NodeIterable nodes() { - if (nodes == null) { - LoopFragmentWhole whole = loop().whole(); - whole.nodes(); // init nodes bitmap in whole - nodes = whole.nodes.copy(); - // remove the phis - for (PhiNode phi : loop().loopBegin().phis()) { - nodes.clear(phi); - } - } - return nodes; - } - - @Override - protected DuplicationReplacement getDuplicationReplacement() { - final LoopBeginNode loopBegin = loop().loopBegin(); - final StructuredGraph graph = graph(); - return new DuplicationReplacement() { - @Override - public Node replacement(Node original) { - if (original == loopBegin) { - return graph.add(new BeginNode()); - } - if (original instanceof LoopExitNode && ((LoopExitNode) original).loopBegin() == loopBegin) { - return graph.add(new BeginNode()); - } - if (original instanceof LoopEndNode && ((LoopEndNode) original).loopBegin() == loopBegin) { - return graph.add(new EndNode()); - } - return original; - } - }; - } - - @Override - protected void finishDuplication() { - // TODO (gd) ? - } - - private void patchPeeling(LoopFragmentInside peel) { - LoopBeginNode loopBegin = loop().loopBegin(); - StructuredGraph graph = (StructuredGraph) loopBegin.graph(); - List newPhis = new LinkedList<>(); - for (PhiNode phi : loopBegin.phis().snapshot()) { - ValueNode first; - if (loopBegin.loopEnds().count() == 1) { - ValueNode b = phi.valueAt(loopBegin.loopEnds().first()); // back edge value - first = peel.prim(b); // corresponding value in the peel - } else { - first = peel.mergedInitializers.get(phi); - } - // create a new phi (we don't patch the old one since some usages of the old one may still be valid) - PhiNode newPhi = graph.add(phi.type() == PhiType.Value ? new PhiNode(phi.kind(), loopBegin) : new PhiNode(phi.type(), loopBegin)); - newPhi.addInput(first); - for (LoopEndNode end : loopBegin.orderedLoopEnds()) { - newPhi.addInput(phi.valueAt(end)); - } - peel.putDuplicatedNode(phi, newPhi); - newPhis.add(newPhi); - for (Node usage : phi.usages().snapshot()) { - if (peel.getDuplicatedNode(usage) != null) { // patch only usages that should use the new phi ie usages that were peeled - usage.replaceFirstInput(phi, newPhi); - } - } - } - // check new phis to see if they have as input some old phis, replace those inputs with the new corresponding phis - for (PhiNode phi : newPhis) { - for (int i = 0; i < phi.valueCount(); i++) { - ValueNode v = phi.valueAt(i); - if (loopBegin.isPhiAtMerge(v)) { - PhiNode newV = peel.getDuplicatedNode((PhiNode) v); - if (newV != null) { - phi.setValueAt(i, newV); - } - } - } - } - } - - /** - * Gets the corresponding value in this fragment. - * - * @param b original value - * @return corresponding value in the peel - */ - private ValueNode prim(ValueNode b) { - assert isDuplicate(); - LoopBeginNode loopBegin = original().loop().loopBegin(); - if (loopBegin.isPhiAtMerge(b)) { - PhiNode phi = (PhiNode) b; - return phi.valueAt(loopBegin.forwardEnd()); - } else if (nodesReady) { - ValueNode v = getDuplicatedNode(b); - if (v == null) { - return b; - } - return v; - } else { - return b; - } - } - - private BeginNode mergeEnds() { - assert isDuplicate(); - List endsToMerge = new LinkedList<>(); - Map reverseEnds = new HashMap<>(); // map peel's exit to the corresponding loop exits - LoopBeginNode loopBegin = original().loop().loopBegin(); - for (LoopEndNode le : loopBegin.loopEnds()) { - EndNode duplicate = getDuplicatedNode(le); - if (duplicate != null) { - endsToMerge.add(duplicate); - reverseEnds.put(duplicate, le); - } - } - mergedInitializers = new IdentityHashMap<>(); - BeginNode newExit; - StructuredGraph graph = graph(); - if (endsToMerge.size() == 1) { - EndNode end = endsToMerge.get(0); - assert end.usages().count() == 0; - newExit = graph.add(new BeginNode()); - end.replaceAtPredecessor(newExit); - end.safeDelete(); - } else { - assert endsToMerge.size() > 1; - MergeNode newExitMerge = graph.add(new MergeNode()); - newExit = newExitMerge; - FrameState state = loopBegin.stateAfter(); - FrameState duplicateState = null; - if (state != null) { - duplicateState = state.duplicateWithVirtualState(); - newExitMerge.setStateAfter(duplicateState); - } - for (EndNode end : endsToMerge) { - newExitMerge.addForwardEnd(end); - } - - for (final PhiNode phi : loopBegin.phis().snapshot()) { - final PhiNode firstPhi = graph.add(phi.type() == PhiType.Value ? new PhiNode(phi.kind(), newExitMerge) : new PhiNode(phi.type(), newExitMerge)); - for (EndNode end : newExitMerge.forwardEnds()) { - LoopEndNode loopEnd = reverseEnds.get(end); - ValueNode prim = prim(phi.valueAt(loopEnd)); - assert prim != null; - firstPhi.addInput(prim); - } - ValueNode initializer = firstPhi; - if (duplicateState != null) { - // fix the merge's state after - duplicateState.applyToNonVirtual(new NodeClosure() { - @Override - public void apply(Node from, ValueNode node) { - if (node == phi) { - from.replaceFirstInput(phi, firstPhi); - } - } - }); - } - mergedInitializers.put(phi, initializer); - } - } - return newExit; - } -} diff -r c612043278e9 -r c8763a2deb0c graal/com.oracle.graal.loop/src/com/oracle/graal/compiler/loop/LoopFragmentInsideBefore.java --- a/graal/com.oracle.graal.loop/src/com/oracle/graal/compiler/loop/LoopFragmentInsideBefore.java Sun Oct 07 12:44:05 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,58 +0,0 @@ -/* - * 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.graph.iterators.*; -import com.oracle.graal.nodes.*; - - -public class LoopFragmentInsideBefore extends LoopFragmentInside { - private final FixedNode point; - - public LoopFragmentInsideBefore(LoopEx loop, FixedNode point) { - super(loop); - this.point = point; - } - - // duplicates lazily - public LoopFragmentInsideBefore(LoopFragmentInsideBefore original) { - super(original); - this.point = original.point(); - } - - public FixedNode point() { - return point; - } - - @Override - public LoopFragmentInsideBefore duplicate() { - return new LoopFragmentInsideBefore(this); - } - - @Override - public NodeIterable nodes() { - // TODO Auto-generated method stub - return null; - } -} diff -r c612043278e9 -r c8763a2deb0c graal/com.oracle.graal.loop/src/com/oracle/graal/compiler/loop/LoopFragmentInsideFrom.java --- a/graal/com.oracle.graal.loop/src/com/oracle/graal/compiler/loop/LoopFragmentInsideFrom.java Sun Oct 07 12:44:05 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,58 +0,0 @@ -/* - * 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.graph.iterators.*; -import com.oracle.graal.nodes.*; - - -public class LoopFragmentInsideFrom extends LoopFragmentInside { - private final FixedNode point; - - public LoopFragmentInsideFrom(LoopEx loop, FixedNode point) { - super(loop); - this.point = point; - } - - // duplicates lazily - public LoopFragmentInsideFrom(LoopFragmentInsideFrom original) { - super(original); - this.point = original.point(); - } - - public FixedNode point() { - return point; - } - - @Override - public LoopFragmentInsideFrom duplicate() { - return new LoopFragmentInsideFrom(this); - } - - @Override - public NodeIterable nodes() { - // TODO Auto-generated method stub - return null; - } -} diff -r c612043278e9 -r c8763a2deb0c graal/com.oracle.graal.loop/src/com/oracle/graal/compiler/loop/LoopFragmentWhole.java --- a/graal/com.oracle.graal.loop/src/com/oracle/graal/compiler/loop/LoopFragmentWhole.java Sun Oct 07 12:44:05 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,99 +0,0 @@ -/* - * 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.Graph.DuplicationReplacement; -import com.oracle.graal.graph.*; -import com.oracle.graal.graph.iterators.*; -import com.oracle.graal.lir.cfg.*; -import com.oracle.graal.nodes.*; - - -public class LoopFragmentWhole extends LoopFragment { - - public LoopFragmentWhole(LoopEx loop) { - super(loop); - } - - public LoopFragmentWhole(LoopFragmentWhole original) { - super(null, original); - } - - @Override - public LoopFragmentWhole duplicate() { - LoopFragmentWhole loopFragmentWhole = new LoopFragmentWhole(this); - loopFragmentWhole.reify(); - return loopFragmentWhole; - } - - private void reify() { - assert this.isDuplicate(); - - patchNodes(null); - - mergeEarlyExits(); - } - - @Override - public NodeIterable nodes() { - if (nodes == null) { - Loop lirLoop = loop().lirLoop(); - nodes = LoopFragment.computeNodes(graph(), LoopFragment.toHirBlocks(lirLoop.blocks), LoopFragment.toHirBlocks(lirLoop.exits)); - } - return nodes; - } - - @Override - protected DuplicationReplacement getDuplicationReplacement() { - final FixedNode entry = loop().entryPoint(); - final Graph graph = this.graph(); - return new DuplicationReplacement() { - @Override - public Node replacement(Node o) { - if (o == entry) { - return graph.add(new EndNode()); - } - return o; - } - }; - } - - public FixedNode entryPoint() { - if (isDuplicate()) { - LoopBeginNode newLoopBegin = getDuplicatedNode(original().loop().loopBegin()); - return newLoopBegin.forwardEnd(); - } - return loop().entryPoint(); - } - - @Override - protected void finishDuplication() { - // TODO (gd) ? - } - - @Override - public void insertBefore(LoopEx loop) { - // TODO Auto-generated method stub - - } -} diff -r c612043278e9 -r c8763a2deb0c graal/com.oracle.graal.loop/src/com/oracle/graal/compiler/loop/LoopPolicies.java --- a/graal/com.oracle.graal.loop/src/com/oracle/graal/compiler/loop/LoopPolicies.java Sun Oct 07 12:44:05 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,73 +0,0 @@ -/* - * 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.compiler.*; -import com.oracle.graal.debug.*; -import com.oracle.graal.lir.cfg.*; -import com.oracle.graal.nodes.*; - - -public abstract class LoopPolicies { - private LoopPolicies() { - // does not need to be instantiated - } - - // TODO (gd) change when inversion is available - public static boolean shouldPeel(LoopEx loop) { - LoopBeginNode loopBegin = loop.loopBegin(); - double entryProbability = loopBegin.forwardEnd().probability(); - return entryProbability > GraalOptions.MinimumPeelProbability && loop.size() + loopBegin.graph().getNodeCount() < GraalOptions.MaximumDesiredSize; - } - - public static boolean shouldFullUnroll(LoopEx loop) { - if (!loop.isCounted() || !loop.counted().isConstantMaxTripCount()) { - return false; - } - CountedLoopInfo counted = loop.counted(); - long exactTrips = counted.constantMaxTripCount(); - int maxNodes = (counted.isExactTripCount() && counted.isConstantExactTripCount()) ? GraalOptions.ExactFullUnrollMaxNodes : GraalOptions.FullUnrollMaxNodes; - maxNodes = Math.min(maxNodes, GraalOptions.MaximumDesiredSize - loop.loopBegin().graph().getNodeCount()); - int size = Math.max(1, loop.size() - 1 - loop.loopBegin().phis().count()); - return size * exactTrips <= maxNodes; - } - - public static boolean shouldTryUnswitch(LoopEx loop) { - return loop.loopBegin().unswitches() <= GraalOptions.LoopMaxUnswitch; - } - - public static boolean shouldUnswitch(LoopEx loop, IfNode ifNode) { - Block postDomBlock = loop.loopsData().controlFlowGraph().blockFor(ifNode).getPostdominator(); - BeginNode postDom = postDomBlock != null ? postDomBlock.getBeginNode() : null; - int inTrueBranch = loop.nodesInLoopFrom(ifNode.trueSuccessor(), postDom).cardinality(); - int inFalseBranch = loop.nodesInLoopFrom(ifNode.falseSuccessor(), postDom).cardinality(); - int loopTotal = loop.size(); - int netDiff = loopTotal - (inTrueBranch + inFalseBranch); - double uncertainty = (0.5 - Math.abs(ifNode.probability(IfNode.TRUE_EDGE) - 0.5)) * 2; - int maxDiff = GraalOptions.LoopUnswitchMaxIncrease + (int) (GraalOptions.LoopUnswitchUncertaintyBoost * loop.loopBegin().loopFrequency() * uncertainty); - Debug.log("shouldUnswitch(%s, %s) : delta=%d, max=%d, %.2f%% inside of if", loop, ifNode, netDiff, maxDiff, (double) (inTrueBranch + inFalseBranch) / loopTotal * 100); - return netDiff <= maxDiff; - } - - -} diff -r c612043278e9 -r c8763a2deb0c graal/com.oracle.graal.loop/src/com/oracle/graal/compiler/loop/LoopTransformations.java --- a/graal/com.oracle.graal.loop/src/com/oracle/graal/compiler/loop/LoopTransformations.java Sun Oct 07 12:44:05 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,143 +0,0 @@ -/* - * 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.api.code.*; -import com.oracle.graal.api.meta.*; -import com.oracle.graal.compiler.*; -import com.oracle.graal.compiler.phases.*; -import com.oracle.graal.graph.*; -import com.oracle.graal.nodes.*; -import com.oracle.graal.nodes.spi.*; -import com.oracle.graal.nodes.util.*; - - -public abstract class LoopTransformations { - private static final int UNROLL_LIMIT = GraalOptions.FullUnrollMaxNodes * 2; - private static final SimplifierTool simplifier = new SimplifierTool() { - @Override - public TargetDescription target() { - return null; - } - @Override - public CodeCacheProvider runtime() { - return null; - } - @Override - public boolean isImmutable(Constant objectConstant) { - return false; - } - @Override - public Assumptions assumptions() { - return null; - } - @Override - public void deleteBranch(FixedNode branch) { - branch.predecessor().replaceFirstSuccessor(branch, null); - GraphUtil.killCFG(branch); - } - @Override - public void addToWorkList(Node node) { - } - }; - - private LoopTransformations() { - // does not need to be instantiated - } - - public static void invert(LoopEx loop, FixedNode point) { - LoopFragmentInsideBefore head = loop.insideBefore(point); - LoopFragmentInsideBefore duplicate = head.duplicate(); - head.disconnect(); - head.insertBefore(loop); - duplicate.appendInside(loop); - } - - public static void peel(LoopEx loop) { - loop.inside().duplicate().insertBefore(loop); - } - - public static void fullUnroll(LoopEx loop, MetaAccessProvider runtime) { - //assert loop.isCounted(); //TODO (gd) strenghten : counted with known trip count - int iterations = 0; - LoopBeginNode loopBegin = loop.loopBegin(); - StructuredGraph graph = (StructuredGraph) loopBegin.graph(); - while (!loopBegin.isDeleted()) { - int mark = graph.getMark(); - peel(loop); - new CanonicalizerPhase(null, runtime, null, mark, null).apply(graph); - if (iterations++ > UNROLL_LIMIT || graph.getNodeCount() > GraalOptions.MaximumDesiredSize * 3) { - throw new BailoutException("FullUnroll : Graph seems to grow out of proportion"); - } - } - } - - public static void unswitch(LoopEx loop, IfNode ifNode) { - // duplicate will be true case, original will be false case - loop.loopBegin().incUnswitches(); - LoopFragmentWhole originalLoop = loop.whole(); - LoopFragmentWhole duplicateLoop = originalLoop.duplicate(); - StructuredGraph graph = (StructuredGraph) ifNode.graph(); - BeginNode tempBegin = graph.add(new BeginNode()); - originalLoop.entryPoint().replaceAtPredecessor(tempBegin); - double takenProbability = ifNode.probability(ifNode.blockSuccessorIndex(ifNode.trueSuccessor())); - IfNode newIf = graph.add(new IfNode(ifNode.compare(), duplicateLoop.entryPoint(), originalLoop.entryPoint(), takenProbability, ifNode.leafGraphId())); - tempBegin.setNext(newIf); - ifNode.setCompare(graph.unique(ConstantNode.forBoolean(false, graph))); - IfNode duplicateIf = duplicateLoop.getDuplicatedNode(ifNode); - duplicateIf.setCompare(graph.unique(ConstantNode.forBoolean(true, graph))); - ifNode.simplify(simplifier); - duplicateIf.simplify(simplifier); - // TODO (gd) probabilities need some amount of fixup.. (probably also in other transforms) - } - - public static void unroll(LoopEx loop, int factor) { - assert loop.isCounted(); - if (factor > 0) { - throw new UnsupportedOperationException(); - } - // TODO (gd) implement counted loop - LoopFragmentWhole main = loop.whole(); - LoopFragmentWhole prologue = main.duplicate(); - prologue.insertBefore(loop); - //CountedLoopBeginNode counted = prologue.countedLoop(); - //StructuredGraph graph = (StructuredGraph) counted.graph(); - //ValueNode tripCountPrologue = counted.tripCount(); - //ValueNode tripCountMain = counted.tripCount(); - //graph.replaceFloating(tripCountPrologue, "tripCountPrologue % factor"); - //graph.replaceFloating(tripCountMain, "tripCountMain - (tripCountPrologue % factor)"); - LoopFragmentInside inside = loop.inside(); - for (int i = 0; i < factor; i++) { - inside.duplicate().appendInside(loop); - } - } - - public static IfNode findUnswitchableIf(LoopEx loop) { - for (IfNode ifNode : loop.whole().nodes().filter(IfNode.class)) { - if (loop.isOutsideLoop(ifNode.compare())) { - return ifNode; - } - } - return null; - } -} diff -r c612043278e9 -r c8763a2deb0c graal/com.oracle.graal.loop/src/com/oracle/graal/compiler/loop/LoopsData.java --- a/graal/com.oracle.graal.loop/src/com/oracle/graal/compiler/loop/LoopsData.java Sun Oct 07 12:44:05 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,158 +0,0 @@ -/* - * 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 java.util.concurrent.*; - -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<>(); - private Map loopBeginToEx = new IdentityHashMap<>(); - private ControlFlowGraph cfg; - - public LoopsData(final StructuredGraph graph) { - - cfg = Debug.scope("ControlFlowGraph", new Callable() { - @Override - public ControlFlowGraph call() throws Exception { - return ControlFlowGraph.compute(graph, true, true, true, true); - } - }); - for (Loop lirLoop : cfg.getLoops()) { - LoopEx ex = new LoopEx(lirLoop, this); - lirLoopToEx.put(lirLoop, ex); - loopBeginToEx.put(ex.loopBegin(), ex); - } - } - - public LoopEx loop(Loop lirLoop) { - return lirLoopToEx.get(lirLoop); - } - - public LoopEx loop(LoopBeginNode loopBegin) { - return loopBeginToEx.get(loopBegin); - } - - public Collection loops() { - return lirLoopToEx.values(); - } - - public List outterFirst() { - ArrayList loops = new ArrayList<>(loops()); - Collections.sort(loops, new Comparator() { - @Override - public int compare(LoopEx o1, LoopEx o2) { - return o1.lirLoop().depth - o2.lirLoop().depth; - } - }); - return loops; - } - - public Collection countedLoops() { - List counted = new LinkedList<>(); - for (LoopEx loop : loops()) { - if (loop.isCounted()) { - counted.add(loop); - } - } - 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(); - } - loop.setCounted(new CountedLoopInfo(loop, iv, limit, oneOff)); - } - } - } - - public ControlFlowGraph controlFlowGraph() { - return cfg; - } -} diff -r c612043278e9 -r c8763a2deb0c graal/com.oracle.graal.loop/src/com/oracle/graal/compiler/phases/loop/LoopFullUnrollPhase.java --- a/graal/com.oracle.graal.loop/src/com/oracle/graal/compiler/phases/loop/LoopFullUnrollPhase.java Sun Oct 07 12:44:05 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,62 +0,0 @@ -/* - * 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.phases.loop; - -import com.oracle.graal.compiler.loop.*; -import com.oracle.graal.compiler.phases.*; -import com.oracle.graal.debug.*; -import com.oracle.graal.nodes.*; -import com.oracle.graal.nodes.spi.*; - - -public class LoopFullUnrollPhase extends Phase { - private static final DebugMetric FULLY_UNROLLED_LOOPS = Debug.metric("FullUnrolls"); - private final GraalCodeCacheProvider runtime; - - public LoopFullUnrollPhase(GraalCodeCacheProvider runtime) { - this.runtime = runtime; - } - - @Override - protected void run(StructuredGraph graph) { - if (graph.hasLoops()) { - boolean peeled; - do { - peeled = false; - final LoopsData dataCounted = new LoopsData(graph); - dataCounted.detectedCountedLoops(); - for (LoopEx loop : dataCounted.countedLoops()) { - if (LoopPolicies.shouldFullUnroll(loop)) { - Debug.log("FullUnroll %s", loop); - LoopTransformations.fullUnroll(loop, runtime); - FULLY_UNROLLED_LOOPS.increment(); - Debug.dump(graph, "After fullUnroll %s", loop); - peeled = true; - break; - } - } - } while(peeled); - } - } - -} diff -r c612043278e9 -r c8763a2deb0c graal/com.oracle.graal.loop/src/com/oracle/graal/compiler/phases/loop/LoopTransformHighPhase.java --- a/graal/com.oracle.graal.loop/src/com/oracle/graal/compiler/phases/loop/LoopTransformHighPhase.java Sun Oct 07 12:44:05 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,48 +0,0 @@ -/* - * 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.phases.loop; - -import com.oracle.graal.compiler.*; -import com.oracle.graal.compiler.loop.*; -import com.oracle.graal.compiler.phases.*; -import com.oracle.graal.debug.*; -import com.oracle.graal.nodes.*; - -public class LoopTransformHighPhase extends Phase { - - @Override - protected void run(StructuredGraph graph) { - if (graph.hasLoops()) { - if (GraalOptions.LoopPeeling) { - LoopsData data = new LoopsData(graph); - for (LoopEx loop : data.outterFirst()) { - if (LoopPolicies.shouldPeel(loop)) { - Debug.log("Peeling %s", loop); - LoopTransformations.peel(loop); - Debug.dump(graph, "After peeling %s", loop); - } - } - } - } - } -} diff -r c612043278e9 -r c8763a2deb0c graal/com.oracle.graal.loop/src/com/oracle/graal/compiler/phases/loop/LoopTransformLowPhase.java --- a/graal/com.oracle.graal.loop/src/com/oracle/graal/compiler/phases/loop/LoopTransformLowPhase.java Sun Oct 07 12:44:05 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,70 +0,0 @@ -/* - * 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.phases.loop; - -import com.oracle.graal.compiler.*; -import com.oracle.graal.compiler.loop.*; -import com.oracle.graal.compiler.phases.*; -import com.oracle.graal.debug.*; -import com.oracle.graal.nodes.*; - -public class LoopTransformLowPhase extends Phase { - private static final DebugMetric UNSWITCHED = Debug.metric("Unswitched"); - - @Override - protected void run(StructuredGraph graph) { - if (graph.hasLoops()) { - if (GraalOptions.ReassociateInvariants) { - final LoopsData dataReassociate = new LoopsData(graph); - Debug.scope("ReassociateInvariants", new Runnable() { - @Override - public void run() { - for (LoopEx loop : dataReassociate.loops()) { - loop.reassociateInvariants(); - } - } - }); - } - if (GraalOptions.LoopUnswitch) { - boolean unswitched; - do { - unswitched = false; - final LoopsData dataUnswitch = new LoopsData(graph); - for (LoopEx loop : dataUnswitch.loops()) { - if (LoopPolicies.shouldTryUnswitch(loop)) { - IfNode ifNode = LoopTransformations.findUnswitchableIf(loop); - if (ifNode != null && LoopPolicies.shouldUnswitch(loop, ifNode)) { - Debug.log("Unswitching %s at %s [%f - %f]", loop, ifNode, ifNode.probability(0), ifNode.probability(1)); - LoopTransformations.unswitch(loop, ifNode); - UNSWITCHED.increment(); - Debug.dump(graph, "After unswitch %s", loop); - unswitched = true; - break; - } - } - } - } while(unswitched); - } - } - } -} diff -r c612043278e9 -r c8763a2deb0c graal/com.oracle.graal.loop/src/com/oracle/graal/loop/BasicInductionVariable.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/BasicInductionVariable.java Sun Oct 07 14:08:36 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.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.isStrictlyPositive()) { + dir = Direction.Up; + } else if (integerStamp.isStrictlyNegative()) { + 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 c612043278e9 -r c8763a2deb0c graal/com.oracle.graal.loop/src/com/oracle/graal/loop/CountedLoopInfo.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/CountedLoopInfo.java Sun Oct 07 14:08:36 2012 +0200 @@ -0,0 +1,80 @@ +/* + * 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.loop; + +import com.oracle.graal.loop.InductionVariable.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.calc.*; + +public class CountedLoopInfo { + private final LoopEx loop; + private InductionVariable iv; + private ValueNode end; + private boolean oneOff; + + CountedLoopInfo(LoopEx loop, InductionVariable iv, ValueNode end, boolean oneOff) { + this.loop = loop; + this.iv = iv; + this.end = end; + this.oneOff = oneOff; + } + + public ValueNode maxTripCountNode() { + //TODO (gd) stuarte and respect oneOff + return IntegerArithmeticNode.div(IntegerArithmeticNode.sub(end, iv.initNode()), iv.strideNode()); + } + + public boolean isConstantMaxTripCount() { + return end instanceof ConstantNode && iv.isConstantInit() && iv.isConstantStride(); + } + + public long constantMaxTripCount() { + long off = oneOff ? iv.direction() == Direction.Up ? 1 : -1 : 0; + long max = (((ConstantNode) end).asConstant().asLong() + off - iv.constantInit()) / iv.constantStride(); + return Math.max(0, max); + } + + 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(); + } + + @Override + public String toString() { + return "iv=" + iv + " until " + end + (oneOff ? iv.direction() == Direction.Up ? "+1" : "-1" : ""); + } +} diff -r c612043278e9 -r c8763a2deb0c graal/com.oracle.graal.loop/src/com/oracle/graal/loop/DerivedOffsetInductionVariable.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/DerivedOffsetInductionVariable.java Sun Oct 07 14:08:36 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.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 c612043278e9 -r c8763a2deb0c graal/com.oracle.graal.loop/src/com/oracle/graal/loop/DerivedScaledInductionVariable.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/DerivedScaledInductionVariable.java Sun Oct 07 14:08:36 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.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.isStrictlyPositive()) { + return base.direction(); + } else if (integerStamp.isStrictlyNegative()) { + 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 c612043278e9 -r c8763a2deb0c graal/com.oracle.graal.loop/src/com/oracle/graal/loop/InductionVariable.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/InductionVariable.java Sun Oct 07 14:08:36 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.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 c612043278e9 -r c8763a2deb0c graal/com.oracle.graal.loop/src/com/oracle/graal/loop/InductionVariables.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/InductionVariables.java Sun Oct 07 14:08:36 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.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 c612043278e9 -r c8763a2deb0c graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopEx.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopEx.java Sun Oct 07 14:08:36 2012 +0200 @@ -0,0 +1,168 @@ +/* + * 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.loop; + +import java.util.*; + +import com.oracle.graal.api.meta.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.graph.*; +import com.oracle.graal.graph.iterators.*; +import com.oracle.graal.lir.cfg.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.calc.*; + +public class LoopEx { + private final Loop lirLoop; + private LoopFragmentInside inside; + private LoopFragmentWhole whole; + private CountedLoopInfo counted; //TODO (gd) detect + private LoopsData data; + + LoopEx(Loop lirLoop, LoopsData data) { + this.lirLoop = lirLoop; + this.data = data; + } + + public Loop lirLoop() { + return lirLoop; + } + + public LoopFragmentInside inside() { + if (inside == null) { + inside = new LoopFragmentInside(this); + } + return inside; + } + + public LoopFragmentWhole whole() { + if (whole == null) { + whole = new LoopFragmentWhole(this); + } + return whole; + } + + @SuppressWarnings("unused") + public LoopFragmentInsideFrom insideFrom(FixedNode point) { + // TODO (gd) + return null; + } + + @SuppressWarnings("unused") + public LoopFragmentInsideBefore insideBefore(FixedNode point) { + // TODO (gd) + return null; + } + + public boolean isOutsideLoop(Node n) { + return !whole().contains(n); + } + + public LoopBeginNode loopBegin() { + return lirLoop().loopBegin(); + } + + public FixedNode predecessor() { + return (FixedNode) loopBegin().forwardEnd().predecessor(); + } + + public FixedNode entryPoint() { + return loopBegin().forwardEnd(); + } + + public boolean isCounted() { + return counted != null; + } + + public CountedLoopInfo counted() { + return counted; + } + + public LoopEx parent() { + if (lirLoop.parent == null) { + return null; + } + return data.loop(lirLoop.parent); + } + + public int size() { + return whole().nodes().count(); + } + + @Override + public String toString() { + return (isCounted() ? "CountedLoop [" + counted() + "] " : "Loop ") + "(depth=" + lirLoop().depth + ") " + loopBegin(); + } + + private class InvariantPredicate extends NodePredicate { + @Override + public boolean apply(Node n) { + return isOutsideLoop(n); + } + } + + public void reassociateInvariants() { + InvariantPredicate invariant = new InvariantPredicate(); + StructuredGraph graph = (StructuredGraph) loopBegin().graph(); + for (BinaryNode binary : whole().nodes().filter(BinaryNode.class)) { + if (!BinaryNode.canTryReassociate(binary)) { + continue; + } + BinaryNode result = BinaryNode.reassociate(binary, invariant); + if (result != binary) { + Debug.log(MetaUtil.format("%H::%n", Debug.contextLookup(ResolvedJavaMethod.class)) + " : Reassociated %s into %s", binary, result); + graph.replaceFloating(binary, result); + } + } + } + + public void setCounted(CountedLoopInfo countedLoopInfo) { + counted = countedLoopInfo; + } + + public LoopsData loopsData() { + return data; + } + + public NodeBitMap nodesInLoopFrom(BeginNode point, BeginNode until) { + Collection blocks = new LinkedList<>(); + Collection exits = new LinkedList<>(); + Queue work = new LinkedList<>(); + ControlFlowGraph cfg = loopsData().controlFlowGraph(); + work.add(cfg.blockFor(point)); + Block untilBlock = until != null ? cfg.blockFor(until) : null; + while (!work.isEmpty()) { + Block b = work.remove(); + if (b == untilBlock) { + continue; + } + if (lirLoop().exits.contains(b)) { + exits.add(b.getBeginNode()); + } else if (lirLoop().blocks.contains(b)) { + blocks.add(b.getBeginNode()); + work.addAll(b.getDominated()); + } + } + return LoopFragment.computeNodes(point.graph(), blocks, exits); + } +} diff -r c612043278e9 -r c8763a2deb0c graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragment.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragment.java Sun Oct 07 14:08:36 2012 +0200 @@ -0,0 +1,303 @@ +/* + * 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.loop; + +import java.util.*; + +import com.oracle.graal.graph.*; +import com.oracle.graal.graph.Graph.DuplicationReplacement; +import com.oracle.graal.graph.iterators.*; +import com.oracle.graal.lir.cfg.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.PhiNode.PhiType; +import com.oracle.graal.nodes.VirtualState.NodeClosure; +import com.oracle.graal.nodes.VirtualState.VirtualClosure; + + +public abstract class LoopFragment { + private final LoopEx loop; + private final LoopFragment original; + protected NodeBitMap nodes; + protected boolean nodesReady; + private Map duplicationMap; + + public LoopFragment(LoopEx loop) { + this(loop, null); + this.nodesReady = true; + } + + public LoopFragment(LoopEx loop, LoopFragment original) { + this.loop = loop; + this.original = original; + this.nodesReady = false; + } + + public LoopEx loop() { + return loop; + } + + public abstract LoopFragment duplicate(); + + public abstract void insertBefore(LoopEx l); + + public void disconnect() { + // TODO (gd) possibly abstract + } + + public boolean contains(Node n) { + return nodes().contains(n); + } + + @SuppressWarnings("unchecked") + public New getDuplicatedNode(Old n) { + assert isDuplicate(); + return (New) duplicationMap.get(n); + } + + protected void putDuplicatedNode(Old oldNode, New newNode) { + duplicationMap.put(oldNode, newNode); + } + + public boolean isDuplicate() { + return original != null; + } + + public LoopFragment original() { + return original; + } + + public abstract NodeIterable nodes(); + + public StructuredGraph graph() { + LoopEx l; + if (isDuplicate()) { + l = original().loop(); + } else { + l = loop(); + } + return (StructuredGraph) l.loopBegin().graph(); + } + + protected abstract DuplicationReplacement getDuplicationReplacement(); + + protected abstract void finishDuplication(); + + protected void patchNodes(final DuplicationReplacement dataFix) { + if (isDuplicate() && !nodesReady) { + assert !original.isDuplicate(); + final DuplicationReplacement cfgFix = original().getDuplicationReplacement(); + DuplicationReplacement dr; + if (cfgFix == null && dataFix != null) { + dr = dataFix; + } else if (cfgFix != null && dataFix == null) { + dr = cfgFix; + } else if (cfgFix != null && dataFix != null) { + dr = new DuplicationReplacement() { + @Override + public Node replacement(Node o) { + Node r1 = dataFix.replacement(o); + if (r1 != o) { + assert cfgFix.replacement(o) == o; + return r1; + } + Node r2 = cfgFix.replacement(o); + if (r2 != o) { + return r2; + } + return o; + } + }; + } else { + dr = new DuplicationReplacement() { + @Override + public Node replacement(Node o) { + return o; + } + }; + } + duplicationMap = graph().addDuplicates(original().nodes(), dr); + finishDuplication(); + nodesReady = true; + } else { + //TODO (gd) apply fix ? + } + } + + protected static NodeBitMap computeNodes(Graph graph, Collection blocks) { + return computeNodes(graph, blocks, Collections.emptyList()); + } + + protected static NodeBitMap computeNodes(Graph graph, Collection blocks, Collection earlyExits) { + final NodeBitMap nodes = graph.createNodeBitMap(true); + for (BeginNode b : blocks) { + for (Node n : b.getBlockNodes()) { + if (n instanceof Invoke) { + nodes.mark(((Invoke) n).callTarget()); + } + if (n instanceof StateSplit) { + FrameState stateAfter = ((StateSplit) n).stateAfter(); + if (stateAfter != null) { + nodes.mark(stateAfter); + } + } + nodes.mark(n); + } + } + for (BeginNode earlyExit : earlyExits) { + FrameState stateAfter = earlyExit.stateAfter(); + if (stateAfter != null) { + nodes.mark(stateAfter); + stateAfter.applyToVirtual(new VirtualClosure() { + @Override + public void apply(VirtualState node) { + nodes.mark(node); + } + }); + } + nodes.mark(earlyExit); + for (ValueProxyNode proxy : earlyExit.proxies()) { + nodes.mark(proxy); + } + } + + for (BeginNode b : blocks) { + for (Node n : b.getBlockNodes()) { + for (Node usage : n.usages()) { + markFloating(usage, nodes); + } + } + } + + return nodes; + } + + private static boolean markFloating(Node n, NodeBitMap loopNodes) { + if (loopNodes.isMarked(n)) { + return true; + } + if (n instanceof FixedNode) { + return false; + } + boolean mark = false; + if (n instanceof PhiNode) { + PhiNode phi = (PhiNode) n; + mark = loopNodes.isMarked(phi.merge()); + if (mark) { + loopNodes.mark(n); + } else { + return false; + } + } + for (Node usage : n.usages()) { + if (markFloating(usage, loopNodes)) { + mark = true; + } + } + if (mark) { + loopNodes.mark(n); + return true; + } + return false; + } + + public static Collection toHirBlocks(Collection blocks) { + List hir = new ArrayList<>(blocks.size()); + for (Block b : blocks) { + hir.add(b.getBeginNode()); + } + return hir; + } + + /** + * Merges the early exits (i.e. loop exits) that were duplicated as part of this fragment, with the original fragment's exits. + */ + protected void mergeEarlyExits() { + assert isDuplicate(); + StructuredGraph graph = graph(); + for (BeginNode earlyExit : LoopFragment.toHirBlocks(original().loop().lirLoop().exits)) { + FixedNode next = earlyExit.next(); + if (earlyExit.isDeleted() || !this.original().contains(earlyExit)) { + continue; + } + BeginNode newEarlyExit = getDuplicatedNode(earlyExit); + if (newEarlyExit == null) { + continue; + } + MergeNode merge = graph.add(new MergeNode()); + merge.setProbability(next.probability()); + EndNode originalEnd = graph.add(new EndNode()); + EndNode newEnd = graph.add(new EndNode()); + merge.addForwardEnd(originalEnd); + merge.addForwardEnd(newEnd); + earlyExit.setNext(originalEnd); + newEarlyExit.setNext(newEnd); + merge.setNext(next); + + FrameState exitState = earlyExit.stateAfter(); + FrameState newExitState = newEarlyExit.stateAfter(); + FrameState state = null; + if (exitState != null) { + state = exitState.duplicateWithVirtualState(); + merge.setStateAfter(state); + } + + for (Node anchored : earlyExit.anchored().snapshot()) { + anchored.replaceFirstInput(earlyExit, merge); + } + + for (final ValueProxyNode vpn : earlyExit.proxies().snapshot()) { + final ValueNode replaceWith; + ValueProxyNode newVpn = getDuplicatedNode(vpn); + if (newVpn != null) { + PhiNode phi = graph.add(vpn.type() == PhiType.Value ? new PhiNode(vpn.kind(), merge) : new PhiNode(vpn.type(), merge)); + phi.addInput(vpn); + phi.addInput(newVpn); + replaceWith = phi; + } else { + replaceWith = vpn.value(); + } + if (state != null) { + state.applyToNonVirtual(new NodeClosure() { + @Override + public void apply(Node from, ValueNode node) { + if (node == vpn) { + from.replaceFirstInput(vpn, replaceWith); + } + } + }); + } + for (Node usage : vpn.usages().snapshot()) { + if (!merge.isPhiAtMerge(usage)) { + if (usage instanceof VirtualState) { + VirtualState stateUsage = (VirtualState) usage; + if (exitState.isPartOfThisState(stateUsage) || newExitState.isPartOfThisState(stateUsage)) { + continue; + } + } + usage.replaceFirstInput(vpn, replaceWith); + } + } + } + } + } +} diff -r c612043278e9 -r c8763a2deb0c graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragmentInside.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragmentInside.java Sun Oct 07 14:08:36 2012 +0200 @@ -0,0 +1,270 @@ +/* + * 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.loop; + +import java.util.*; + +import com.oracle.graal.graph.Graph.DuplicationReplacement; +import com.oracle.graal.graph.*; +import com.oracle.graal.graph.iterators.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.PhiNode.PhiType; +import com.oracle.graal.nodes.VirtualState.NodeClosure; +import com.oracle.graal.nodes.util.*; + + +public class LoopFragmentInside extends LoopFragment { + /** mergedInitializers. + * When an inside fragment's (loop)ends are merged to create a unique exit point, + * some phis must be created : they phis together all the back-values of the loop-phis + * These can then be used to update the loop-phis' forward edge value ('initializer') in the peeling case. + * In the unrolling case they will be used as the value that replace the loop-phis of the duplicated inside fragment + */ + private Map mergedInitializers; + private final DuplicationReplacement dataFixBefore = new DuplicationReplacement() { + @Override + public Node replacement(Node oriInput) { + if (!(oriInput instanceof ValueNode)) { + return oriInput; + } + return prim((ValueNode) oriInput); + } + }; + + public LoopFragmentInside(LoopEx loop) { + super(loop); + } + + public LoopFragmentInside(LoopFragmentInside original) { + super(null, original); + } + + @Override + public LoopFragmentInside duplicate() { + assert !isDuplicate(); + return new LoopFragmentInside(this); + } + + @Override + public LoopFragmentInside original() { + return (LoopFragmentInside) super.original(); + } + + @SuppressWarnings("unused") + public void appendInside(LoopEx loop) { + // TODO (gd) + } + + @Override + public LoopEx loop() { + assert !this.isDuplicate(); + return super.loop(); + } + + @Override + public void insertBefore(LoopEx loop) { + assert this.isDuplicate() && this.original().loop() == loop; + + patchNodes(dataFixBefore); + + BeginNode end = mergeEnds(); + + original().patchPeeling(this); + + mergeEarlyExits(); + + BeginNode entry = getDuplicatedNode(loop.loopBegin()); + FrameState state = entry.stateAfter(); + if (state != null) { + entry.setStateAfter(null); + GraphUtil.killWithUnusedFloatingInputs(state); + } + loop.entryPoint().replaceAtPredecessor(entry); + end.setProbability(loop.entryPoint().probability()); + end.setNext(loop.entryPoint()); + } + + @Override + public NodeIterable nodes() { + if (nodes == null) { + LoopFragmentWhole whole = loop().whole(); + whole.nodes(); // init nodes bitmap in whole + nodes = whole.nodes.copy(); + // remove the phis + for (PhiNode phi : loop().loopBegin().phis()) { + nodes.clear(phi); + } + } + return nodes; + } + + @Override + protected DuplicationReplacement getDuplicationReplacement() { + final LoopBeginNode loopBegin = loop().loopBegin(); + final StructuredGraph graph = graph(); + return new DuplicationReplacement() { + @Override + public Node replacement(Node original) { + if (original == loopBegin) { + return graph.add(new BeginNode()); + } + if (original instanceof LoopExitNode && ((LoopExitNode) original).loopBegin() == loopBegin) { + return graph.add(new BeginNode()); + } + if (original instanceof LoopEndNode && ((LoopEndNode) original).loopBegin() == loopBegin) { + return graph.add(new EndNode()); + } + return original; + } + }; + } + + @Override + protected void finishDuplication() { + // TODO (gd) ? + } + + private void patchPeeling(LoopFragmentInside peel) { + LoopBeginNode loopBegin = loop().loopBegin(); + StructuredGraph graph = (StructuredGraph) loopBegin.graph(); + List newPhis = new LinkedList<>(); + for (PhiNode phi : loopBegin.phis().snapshot()) { + ValueNode first; + if (loopBegin.loopEnds().count() == 1) { + ValueNode b = phi.valueAt(loopBegin.loopEnds().first()); // back edge value + first = peel.prim(b); // corresponding value in the peel + } else { + first = peel.mergedInitializers.get(phi); + } + // create a new phi (we don't patch the old one since some usages of the old one may still be valid) + PhiNode newPhi = graph.add(phi.type() == PhiType.Value ? new PhiNode(phi.kind(), loopBegin) : new PhiNode(phi.type(), loopBegin)); + newPhi.addInput(first); + for (LoopEndNode end : loopBegin.orderedLoopEnds()) { + newPhi.addInput(phi.valueAt(end)); + } + peel.putDuplicatedNode(phi, newPhi); + newPhis.add(newPhi); + for (Node usage : phi.usages().snapshot()) { + if (peel.getDuplicatedNode(usage) != null) { // patch only usages that should use the new phi ie usages that were peeled + usage.replaceFirstInput(phi, newPhi); + } + } + } + // check new phis to see if they have as input some old phis, replace those inputs with the new corresponding phis + for (PhiNode phi : newPhis) { + for (int i = 0; i < phi.valueCount(); i++) { + ValueNode v = phi.valueAt(i); + if (loopBegin.isPhiAtMerge(v)) { + PhiNode newV = peel.getDuplicatedNode((PhiNode) v); + if (newV != null) { + phi.setValueAt(i, newV); + } + } + } + } + } + + /** + * Gets the corresponding value in this fragment. + * + * @param b original value + * @return corresponding value in the peel + */ + private ValueNode prim(ValueNode b) { + assert isDuplicate(); + LoopBeginNode loopBegin = original().loop().loopBegin(); + if (loopBegin.isPhiAtMerge(b)) { + PhiNode phi = (PhiNode) b; + return phi.valueAt(loopBegin.forwardEnd()); + } else if (nodesReady) { + ValueNode v = getDuplicatedNode(b); + if (v == null) { + return b; + } + return v; + } else { + return b; + } + } + + private BeginNode mergeEnds() { + assert isDuplicate(); + List endsToMerge = new LinkedList<>(); + Map reverseEnds = new HashMap<>(); // map peel's exit to the corresponding loop exits + LoopBeginNode loopBegin = original().loop().loopBegin(); + for (LoopEndNode le : loopBegin.loopEnds()) { + EndNode duplicate = getDuplicatedNode(le); + if (duplicate != null) { + endsToMerge.add(duplicate); + reverseEnds.put(duplicate, le); + } + } + mergedInitializers = new IdentityHashMap<>(); + BeginNode newExit; + StructuredGraph graph = graph(); + if (endsToMerge.size() == 1) { + EndNode end = endsToMerge.get(0); + assert end.usages().count() == 0; + newExit = graph.add(new BeginNode()); + end.replaceAtPredecessor(newExit); + end.safeDelete(); + } else { + assert endsToMerge.size() > 1; + MergeNode newExitMerge = graph.add(new MergeNode()); + newExit = newExitMerge; + FrameState state = loopBegin.stateAfter(); + FrameState duplicateState = null; + if (state != null) { + duplicateState = state.duplicateWithVirtualState(); + newExitMerge.setStateAfter(duplicateState); + } + for (EndNode end : endsToMerge) { + newExitMerge.addForwardEnd(end); + } + + for (final PhiNode phi : loopBegin.phis().snapshot()) { + final PhiNode firstPhi = graph.add(phi.type() == PhiType.Value ? new PhiNode(phi.kind(), newExitMerge) : new PhiNode(phi.type(), newExitMerge)); + for (EndNode end : newExitMerge.forwardEnds()) { + LoopEndNode loopEnd = reverseEnds.get(end); + ValueNode prim = prim(phi.valueAt(loopEnd)); + assert prim != null; + firstPhi.addInput(prim); + } + ValueNode initializer = firstPhi; + if (duplicateState != null) { + // fix the merge's state after + duplicateState.applyToNonVirtual(new NodeClosure() { + @Override + public void apply(Node from, ValueNode node) { + if (node == phi) { + from.replaceFirstInput(phi, firstPhi); + } + } + }); + } + mergedInitializers.put(phi, initializer); + } + } + return newExit; + } +} diff -r c612043278e9 -r c8763a2deb0c graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragmentInsideBefore.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragmentInsideBefore.java Sun Oct 07 14:08:36 2012 +0200 @@ -0,0 +1,58 @@ +/* + * 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.loop; + +import com.oracle.graal.graph.*; +import com.oracle.graal.graph.iterators.*; +import com.oracle.graal.nodes.*; + + +public class LoopFragmentInsideBefore extends LoopFragmentInside { + private final FixedNode point; + + public LoopFragmentInsideBefore(LoopEx loop, FixedNode point) { + super(loop); + this.point = point; + } + + // duplicates lazily + public LoopFragmentInsideBefore(LoopFragmentInsideBefore original) { + super(original); + this.point = original.point(); + } + + public FixedNode point() { + return point; + } + + @Override + public LoopFragmentInsideBefore duplicate() { + return new LoopFragmentInsideBefore(this); + } + + @Override + public NodeIterable nodes() { + // TODO Auto-generated method stub + return null; + } +} diff -r c612043278e9 -r c8763a2deb0c graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragmentInsideFrom.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragmentInsideFrom.java Sun Oct 07 14:08:36 2012 +0200 @@ -0,0 +1,58 @@ +/* + * 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.loop; + +import com.oracle.graal.graph.*; +import com.oracle.graal.graph.iterators.*; +import com.oracle.graal.nodes.*; + + +public class LoopFragmentInsideFrom extends LoopFragmentInside { + private final FixedNode point; + + public LoopFragmentInsideFrom(LoopEx loop, FixedNode point) { + super(loop); + this.point = point; + } + + // duplicates lazily + public LoopFragmentInsideFrom(LoopFragmentInsideFrom original) { + super(original); + this.point = original.point(); + } + + public FixedNode point() { + return point; + } + + @Override + public LoopFragmentInsideFrom duplicate() { + return new LoopFragmentInsideFrom(this); + } + + @Override + public NodeIterable nodes() { + // TODO Auto-generated method stub + return null; + } +} diff -r c612043278e9 -r c8763a2deb0c graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragmentWhole.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragmentWhole.java Sun Oct 07 14:08:36 2012 +0200 @@ -0,0 +1,99 @@ +/* + * 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.loop; + +import com.oracle.graal.graph.Graph.DuplicationReplacement; +import com.oracle.graal.graph.*; +import com.oracle.graal.graph.iterators.*; +import com.oracle.graal.lir.cfg.*; +import com.oracle.graal.nodes.*; + + +public class LoopFragmentWhole extends LoopFragment { + + public LoopFragmentWhole(LoopEx loop) { + super(loop); + } + + public LoopFragmentWhole(LoopFragmentWhole original) { + super(null, original); + } + + @Override + public LoopFragmentWhole duplicate() { + LoopFragmentWhole loopFragmentWhole = new LoopFragmentWhole(this); + loopFragmentWhole.reify(); + return loopFragmentWhole; + } + + private void reify() { + assert this.isDuplicate(); + + patchNodes(null); + + mergeEarlyExits(); + } + + @Override + public NodeIterable nodes() { + if (nodes == null) { + Loop lirLoop = loop().lirLoop(); + nodes = LoopFragment.computeNodes(graph(), LoopFragment.toHirBlocks(lirLoop.blocks), LoopFragment.toHirBlocks(lirLoop.exits)); + } + return nodes; + } + + @Override + protected DuplicationReplacement getDuplicationReplacement() { + final FixedNode entry = loop().entryPoint(); + final Graph graph = this.graph(); + return new DuplicationReplacement() { + @Override + public Node replacement(Node o) { + if (o == entry) { + return graph.add(new EndNode()); + } + return o; + } + }; + } + + public FixedNode entryPoint() { + if (isDuplicate()) { + LoopBeginNode newLoopBegin = getDuplicatedNode(original().loop().loopBegin()); + return newLoopBegin.forwardEnd(); + } + return loop().entryPoint(); + } + + @Override + protected void finishDuplication() { + // TODO (gd) ? + } + + @Override + public void insertBefore(LoopEx loop) { + // TODO Auto-generated method stub + + } +} diff -r c612043278e9 -r c8763a2deb0c graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopPolicies.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopPolicies.java Sun Oct 07 14:08:36 2012 +0200 @@ -0,0 +1,73 @@ +/* + * 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.loop; + +import com.oracle.graal.compiler.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.lir.cfg.*; +import com.oracle.graal.nodes.*; + + +public abstract class LoopPolicies { + private LoopPolicies() { + // does not need to be instantiated + } + + // TODO (gd) change when inversion is available + public static boolean shouldPeel(LoopEx loop) { + LoopBeginNode loopBegin = loop.loopBegin(); + double entryProbability = loopBegin.forwardEnd().probability(); + return entryProbability > GraalOptions.MinimumPeelProbability && loop.size() + loopBegin.graph().getNodeCount() < GraalOptions.MaximumDesiredSize; + } + + public static boolean shouldFullUnroll(LoopEx loop) { + if (!loop.isCounted() || !loop.counted().isConstantMaxTripCount()) { + return false; + } + CountedLoopInfo counted = loop.counted(); + long exactTrips = counted.constantMaxTripCount(); + int maxNodes = (counted.isExactTripCount() && counted.isConstantExactTripCount()) ? GraalOptions.ExactFullUnrollMaxNodes : GraalOptions.FullUnrollMaxNodes; + maxNodes = Math.min(maxNodes, GraalOptions.MaximumDesiredSize - loop.loopBegin().graph().getNodeCount()); + int size = Math.max(1, loop.size() - 1 - loop.loopBegin().phis().count()); + return size * exactTrips <= maxNodes; + } + + public static boolean shouldTryUnswitch(LoopEx loop) { + return loop.loopBegin().unswitches() <= GraalOptions.LoopMaxUnswitch; + } + + public static boolean shouldUnswitch(LoopEx loop, IfNode ifNode) { + Block postDomBlock = loop.loopsData().controlFlowGraph().blockFor(ifNode).getPostdominator(); + BeginNode postDom = postDomBlock != null ? postDomBlock.getBeginNode() : null; + int inTrueBranch = loop.nodesInLoopFrom(ifNode.trueSuccessor(), postDom).cardinality(); + int inFalseBranch = loop.nodesInLoopFrom(ifNode.falseSuccessor(), postDom).cardinality(); + int loopTotal = loop.size(); + int netDiff = loopTotal - (inTrueBranch + inFalseBranch); + double uncertainty = (0.5 - Math.abs(ifNode.probability(IfNode.TRUE_EDGE) - 0.5)) * 2; + int maxDiff = GraalOptions.LoopUnswitchMaxIncrease + (int) (GraalOptions.LoopUnswitchUncertaintyBoost * loop.loopBegin().loopFrequency() * uncertainty); + Debug.log("shouldUnswitch(%s, %s) : delta=%d, max=%d, %.2f%% inside of if", loop, ifNode, netDiff, maxDiff, (double) (inTrueBranch + inFalseBranch) / loopTotal * 100); + return netDiff <= maxDiff; + } + + +} diff -r c612043278e9 -r c8763a2deb0c graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopTransformations.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopTransformations.java Sun Oct 07 14:08:36 2012 +0200 @@ -0,0 +1,143 @@ +/* + * 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.loop; + +import com.oracle.graal.api.code.*; +import com.oracle.graal.api.meta.*; +import com.oracle.graal.compiler.*; +import com.oracle.graal.compiler.phases.*; +import com.oracle.graal.graph.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.spi.*; +import com.oracle.graal.nodes.util.*; + + +public abstract class LoopTransformations { + private static final int UNROLL_LIMIT = GraalOptions.FullUnrollMaxNodes * 2; + private static final SimplifierTool simplifier = new SimplifierTool() { + @Override + public TargetDescription target() { + return null; + } + @Override + public CodeCacheProvider runtime() { + return null; + } + @Override + public boolean isImmutable(Constant objectConstant) { + return false; + } + @Override + public Assumptions assumptions() { + return null; + } + @Override + public void deleteBranch(FixedNode branch) { + branch.predecessor().replaceFirstSuccessor(branch, null); + GraphUtil.killCFG(branch); + } + @Override + public void addToWorkList(Node node) { + } + }; + + private LoopTransformations() { + // does not need to be instantiated + } + + public static void invert(LoopEx loop, FixedNode point) { + LoopFragmentInsideBefore head = loop.insideBefore(point); + LoopFragmentInsideBefore duplicate = head.duplicate(); + head.disconnect(); + head.insertBefore(loop); + duplicate.appendInside(loop); + } + + public static void peel(LoopEx loop) { + loop.inside().duplicate().insertBefore(loop); + } + + public static void fullUnroll(LoopEx loop, MetaAccessProvider runtime) { + //assert loop.isCounted(); //TODO (gd) strenghten : counted with known trip count + int iterations = 0; + LoopBeginNode loopBegin = loop.loopBegin(); + StructuredGraph graph = (StructuredGraph) loopBegin.graph(); + while (!loopBegin.isDeleted()) { + int mark = graph.getMark(); + peel(loop); + new CanonicalizerPhase(null, runtime, null, mark, null).apply(graph); + if (iterations++ > UNROLL_LIMIT || graph.getNodeCount() > GraalOptions.MaximumDesiredSize * 3) { + throw new BailoutException("FullUnroll : Graph seems to grow out of proportion"); + } + } + } + + public static void unswitch(LoopEx loop, IfNode ifNode) { + // duplicate will be true case, original will be false case + loop.loopBegin().incUnswitches(); + LoopFragmentWhole originalLoop = loop.whole(); + LoopFragmentWhole duplicateLoop = originalLoop.duplicate(); + StructuredGraph graph = (StructuredGraph) ifNode.graph(); + BeginNode tempBegin = graph.add(new BeginNode()); + originalLoop.entryPoint().replaceAtPredecessor(tempBegin); + double takenProbability = ifNode.probability(ifNode.blockSuccessorIndex(ifNode.trueSuccessor())); + IfNode newIf = graph.add(new IfNode(ifNode.compare(), duplicateLoop.entryPoint(), originalLoop.entryPoint(), takenProbability, ifNode.leafGraphId())); + tempBegin.setNext(newIf); + ifNode.setCompare(graph.unique(ConstantNode.forBoolean(false, graph))); + IfNode duplicateIf = duplicateLoop.getDuplicatedNode(ifNode); + duplicateIf.setCompare(graph.unique(ConstantNode.forBoolean(true, graph))); + ifNode.simplify(simplifier); + duplicateIf.simplify(simplifier); + // TODO (gd) probabilities need some amount of fixup.. (probably also in other transforms) + } + + public static void unroll(LoopEx loop, int factor) { + assert loop.isCounted(); + if (factor > 0) { + throw new UnsupportedOperationException(); + } + // TODO (gd) implement counted loop + LoopFragmentWhole main = loop.whole(); + LoopFragmentWhole prologue = main.duplicate(); + prologue.insertBefore(loop); + //CountedLoopBeginNode counted = prologue.countedLoop(); + //StructuredGraph graph = (StructuredGraph) counted.graph(); + //ValueNode tripCountPrologue = counted.tripCount(); + //ValueNode tripCountMain = counted.tripCount(); + //graph.replaceFloating(tripCountPrologue, "tripCountPrologue % factor"); + //graph.replaceFloating(tripCountMain, "tripCountMain - (tripCountPrologue % factor)"); + LoopFragmentInside inside = loop.inside(); + for (int i = 0; i < factor; i++) { + inside.duplicate().appendInside(loop); + } + } + + public static IfNode findUnswitchableIf(LoopEx loop) { + for (IfNode ifNode : loop.whole().nodes().filter(IfNode.class)) { + if (loop.isOutsideLoop(ifNode.compare())) { + return ifNode; + } + } + return null; + } +} diff -r c612043278e9 -r c8763a2deb0c graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopsData.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopsData.java Sun Oct 07 14:08:36 2012 +0200 @@ -0,0 +1,158 @@ +/* + * 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.loop; + +import java.util.*; +import java.util.concurrent.*; + +import com.oracle.graal.debug.*; +import com.oracle.graal.graph.*; +import com.oracle.graal.lir.cfg.*; +import com.oracle.graal.loop.InductionVariable.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.calc.*; + +public class LoopsData { + private Map lirLoopToEx = new IdentityHashMap<>(); + private Map loopBeginToEx = new IdentityHashMap<>(); + private ControlFlowGraph cfg; + + public LoopsData(final StructuredGraph graph) { + + cfg = Debug.scope("ControlFlowGraph", new Callable() { + @Override + public ControlFlowGraph call() throws Exception { + return ControlFlowGraph.compute(graph, true, true, true, true); + } + }); + for (Loop lirLoop : cfg.getLoops()) { + LoopEx ex = new LoopEx(lirLoop, this); + lirLoopToEx.put(lirLoop, ex); + loopBeginToEx.put(ex.loopBegin(), ex); + } + } + + public LoopEx loop(Loop lirLoop) { + return lirLoopToEx.get(lirLoop); + } + + public LoopEx loop(LoopBeginNode loopBegin) { + return loopBeginToEx.get(loopBegin); + } + + public Collection loops() { + return lirLoopToEx.values(); + } + + public List outterFirst() { + ArrayList loops = new ArrayList<>(loops()); + Collections.sort(loops, new Comparator() { + @Override + public int compare(LoopEx o1, LoopEx o2) { + return o1.lirLoop().depth - o2.lirLoop().depth; + } + }); + return loops; + } + + public Collection countedLoops() { + List counted = new LinkedList<>(); + for (LoopEx loop : loops()) { + if (loop.isCounted()) { + counted.add(loop); + } + } + 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(); + } + loop.setCounted(new CountedLoopInfo(loop, iv, limit, oneOff)); + } + } + } + + public ControlFlowGraph controlFlowGraph() { + return cfg; + } +} diff -r c612043278e9 -r c8763a2deb0c graal/com.oracle.graal.loop/src/com/oracle/graal/loop/phases/LoopFullUnrollPhase.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/phases/LoopFullUnrollPhase.java Sun Oct 07 14:08:36 2012 +0200 @@ -0,0 +1,62 @@ +/* + * 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.loop.phases; + +import com.oracle.graal.compiler.phases.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.loop.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.spi.*; + + +public class LoopFullUnrollPhase extends Phase { + private static final DebugMetric FULLY_UNROLLED_LOOPS = Debug.metric("FullUnrolls"); + private final GraalCodeCacheProvider runtime; + + public LoopFullUnrollPhase(GraalCodeCacheProvider runtime) { + this.runtime = runtime; + } + + @Override + protected void run(StructuredGraph graph) { + if (graph.hasLoops()) { + boolean peeled; + do { + peeled = false; + final LoopsData dataCounted = new LoopsData(graph); + dataCounted.detectedCountedLoops(); + for (LoopEx loop : dataCounted.countedLoops()) { + if (LoopPolicies.shouldFullUnroll(loop)) { + Debug.log("FullUnroll %s", loop); + LoopTransformations.fullUnroll(loop, runtime); + FULLY_UNROLLED_LOOPS.increment(); + Debug.dump(graph, "After fullUnroll %s", loop); + peeled = true; + break; + } + } + } while(peeled); + } + } + +} diff -r c612043278e9 -r c8763a2deb0c graal/com.oracle.graal.loop/src/com/oracle/graal/loop/phases/LoopTransformHighPhase.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/phases/LoopTransformHighPhase.java Sun Oct 07 14:08:36 2012 +0200 @@ -0,0 +1,48 @@ +/* + * 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.loop.phases; + +import com.oracle.graal.compiler.*; +import com.oracle.graal.compiler.phases.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.loop.*; +import com.oracle.graal.nodes.*; + +public class LoopTransformHighPhase extends Phase { + + @Override + protected void run(StructuredGraph graph) { + if (graph.hasLoops()) { + if (GraalOptions.LoopPeeling) { + LoopsData data = new LoopsData(graph); + for (LoopEx loop : data.outterFirst()) { + if (LoopPolicies.shouldPeel(loop)) { + Debug.log("Peeling %s", loop); + LoopTransformations.peel(loop); + Debug.dump(graph, "After peeling %s", loop); + } + } + } + } + } +} diff -r c612043278e9 -r c8763a2deb0c graal/com.oracle.graal.loop/src/com/oracle/graal/loop/phases/LoopTransformLowPhase.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/phases/LoopTransformLowPhase.java Sun Oct 07 14:08:36 2012 +0200 @@ -0,0 +1,70 @@ +/* + * 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.loop.phases; + +import com.oracle.graal.compiler.*; +import com.oracle.graal.compiler.phases.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.loop.*; +import com.oracle.graal.nodes.*; + +public class LoopTransformLowPhase extends Phase { + private static final DebugMetric UNSWITCHED = Debug.metric("Unswitched"); + + @Override + protected void run(StructuredGraph graph) { + if (graph.hasLoops()) { + if (GraalOptions.ReassociateInvariants) { + final LoopsData dataReassociate = new LoopsData(graph); + Debug.scope("ReassociateInvariants", new Runnable() { + @Override + public void run() { + for (LoopEx loop : dataReassociate.loops()) { + loop.reassociateInvariants(); + } + } + }); + } + if (GraalOptions.LoopUnswitch) { + boolean unswitched; + do { + unswitched = false; + final LoopsData dataUnswitch = new LoopsData(graph); + for (LoopEx loop : dataUnswitch.loops()) { + if (LoopPolicies.shouldTryUnswitch(loop)) { + IfNode ifNode = LoopTransformations.findUnswitchableIf(loop); + if (ifNode != null && LoopPolicies.shouldUnswitch(loop, ifNode)) { + Debug.log("Unswitching %s at %s [%f - %f]", loop, ifNode, ifNode.probability(0), ifNode.probability(1)); + LoopTransformations.unswitch(loop, ifNode); + UNSWITCHED.increment(); + Debug.dump(graph, "After unswitch %s", loop); + unswitched = true; + break; + } + } + } + } while(unswitched); + } + } + } +} diff -r c612043278e9 -r c8763a2deb0c graal/com.oracle.graal.snippets/src/com/oracle/graal/snippets/SnippetTemplate.java --- a/graal/com.oracle.graal.snippets/src/com/oracle/graal/snippets/SnippetTemplate.java Sun Oct 07 12:44:05 2012 +0200 +++ b/graal/com.oracle.graal.snippets/src/com/oracle/graal/snippets/SnippetTemplate.java Sun Oct 07 14:08:36 2012 +0200 @@ -29,10 +29,10 @@ import com.oracle.graal.api.code.*; import com.oracle.graal.api.meta.*; -import com.oracle.graal.compiler.loop.*; import com.oracle.graal.compiler.phases.*; import com.oracle.graal.debug.*; import com.oracle.graal.graph.*; +import com.oracle.graal.loop.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.calc.*; import com.oracle.graal.nodes.extended.*;