Mercurial > hg > truffle
changeset 3521:82266dbf5a5a
WIP : updated loop counter detection, added Basic and Derived induction variable framework
line wrap: on
line diff
--- a/ProblemsIdeas.txt Tue Aug 09 14:43:41 2011 +0200 +++ b/ProblemsIdeas.txt Tue Aug 09 18:53:11 2011 +0200 @@ -11,7 +11,10 @@ * Deopt caused by profiling can interfer with later optimisations - Exmple : have a look to some of the visit methods in avrora.arch.legacy.LegacyInterpreter sometimes if constructs which are used to materialize some booleans have a Deopt branch which prevents us from detecting an opportunity for a MaterilizeNode canonicalization. As long as the MaterializeNode itself doesnt get canonicalized away and in the end translates to jumps in the final assembly this doesnt really matter but it may if we optimise the emitted assembly + Example : have a look to some of the visit methods in avrora.arch.legacy.LegacyInterpreter sometimes if constructs which are used to materialize some booleans have a Deopt branch which prevents us from detecting an opportunity for a MaterilizeNode canonicalization. As long as the MaterializeNode itself doesnt get canonicalized away and in the end translates to jumps in the final assembly this doesnt really matter but it may if we optimise the emitted assembly + +* Canonicalization & DeadCodeElimination should play better together + Somtimes the graph does not get completely canonical after a CanonicalizationPhase followed by a DeadCodeEliminationPhase because DCE can transform some Phi into one of their input value because of the removal of a branch, if this transformation gives a canonicalization opportunity, it will never be used. We could apply Canonicalization followed by BCE until we reach a fixed point but that's probably not very efficient. Ideas =====
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java Tue Aug 09 14:43:41 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java Tue Aug 09 18:53:11 2011 +0200 @@ -1544,25 +1544,6 @@ } } resolver.dispose(); - //TODO (gd) remove that later ? - if (merge instanceof LoopBegin) { - LoopBegin loopBegin = (LoopBegin) merge; - for (LoopCounter counter : loopBegin.counters()) { - if (counter.operand().isIllegal()) { - createResultVariable(counter); - } - if (nextSuccIndex == 0) { - lir.move(operandForInstruction(counter.init()), counter.operand()); - } else { - if (counter.kind == CiKind.Int) { - this.arithmeticOpInt(IADD, counter.operand(), counter.operand(), operandForInstruction(counter.stride()), CiValue.IllegalValue); - } else { - assert counter.kind == CiKind.Long; - this.arithmeticOpLong(LADD, counter.operand(), counter.operand(), operandForInstruction(counter.stride())); - } - } - } - } } /**
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/BasicInductionVariable.java Tue Aug 09 18:53:11 2011 +0200 @@ -0,0 +1,130 @@ +/* + * Copyright (c) 2011, 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.max.graal.compiler.ir; + +import com.oracle.max.graal.compiler.ir.Phi.PhiType; +import com.oracle.max.graal.compiler.phases.CanonicalizerPhase.*; +import com.oracle.max.graal.compiler.phases.LoweringPhase.*; +import com.oracle.max.graal.graph.*; +import com.sun.cri.ci.*; + + +/** + * LinearInductionVariable that is computed in the loops thanks to Phi(init, this + stride). + * This will keep at least one register busy in the whole loop body + */ +public class BasicInductionVariable extends LinearInductionVariable { + public static final BIVLoweringOp LOWERING = new BIVLoweringOp(); + @Input private LoopCounter loopCounter; + + public BasicInductionVariable(CiKind kind, Value init, Value stride, LoopCounter counter, Graph graph) { + super(kind, init, stride, graph); + setLoopCounter(counter); + } + + public LoopCounter loopCounter() { + return loopCounter; + } + + public void setLoopCounter(LoopCounter loopCounter) { + updateUsages(this.loopCounter, loopCounter); + this.loopCounter = loopCounter; + } + + public Value init() { + return a(); + } + + public void setInit(Value init) { + setA(init); + } + + public Value stride() { + return b(); + } + + public void setStride(Value stride) { + setB(stride); + } + + @Override + public LoopBegin loopBegin() { + return loopCounter().loopBegin(); + } + + @Override + public void peelOneIteration() { + this.setInit(IntegerArithmeticNode.add(init(), stride())); + } + + /** + * Will lessen the register pressure but augment the code complexity with a multiplication. + * @return the new DerivedInductionVariable + */ + public DerivedInductionVariable toDerivedInductionVariable() { + DerivedInductionVariable newDIV = new DerivedInductionVariable(kind, init(), stride(), loopCounter(), graph()); + this.replaceAndDelete(newDIV); + return newDIV; + } + + @SuppressWarnings("unchecked") + @Override + public <T extends Op> T lookup(Class<T> clazz) { + if (clazz == LoweringOp.class) { + return (T) LOWERING; + } + if (clazz == CanonicalizerOp.class) { + return (T) CANON; + } + return super.lookup(clazz); + } + + public static class BIVLoweringOp implements LoweringOp { + @Override + public void lower(Node n, CiLoweringTool tool) { + BasicInductionVariable biv = (BasicInductionVariable) n; + Phi phi = this.ivToPhi(biv.loopBegin(), biv.init(), biv.stride(), biv.kind); + biv.replaceAtNonIVUsages(phi); + } + + public Phi ivToPhi(LoopBegin loopBegin, Value init, Value stride, CiKind kind) { + Phi phi = new Phi(kind, loopBegin, PhiType.Value, loopBegin.graph()); + IntegerArithmeticNode after = IntegerArithmeticNode.add(phi, stride); + phi.addInput(init); + phi.addInput(after); + return phi; + } + } + + private static CanonicalizerOp CANON = new CanonicalizerOp() { + @Override + public Node canonical(Node node, NotifyReProcess reProcess) { + BasicInductionVariable biv = (BasicInductionVariable) node; + if (biv.init().isConstant() && biv.init().asConstant().asLong() == 0 + && biv.stride().isConstant() && biv.stride().asConstant().asLong() == 1) { + return biv.loopCounter(); + } + return biv; + } + }; +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/DerivedInductionVariable.java Tue Aug 09 18:53:11 2011 +0200 @@ -0,0 +1,123 @@ +/* + * Copyright (c) 2011, 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.max.graal.compiler.ir; + +import com.oracle.max.graal.compiler.phases.LoweringPhase.LoweringOp; +import com.oracle.max.graal.graph.*; +import com.sun.cri.ci.*; + + +/** + * LinearInductionVariable that is computed in the loops with offset + scale * base. + * This is computed in the loop only when necessary, puts less pressure on registers. + */ +public class DerivedInductionVariable extends LinearInductionVariable { + @Input private InductionVariable base; + + public DerivedInductionVariable(CiKind kind, Value offset, Value scale, InductionVariable base, Graph graph) { + super(kind, offset, scale, graph); + setBase(base); + } + + public InductionVariable base() { + return base; + } + + public void setBase(InductionVariable base) { + updateUsages(this.base, base); + this.base = base; + } + + public Value offset() { + return a(); + } + + public void setOffset(Value offset) { + setA(offset); + } + + public Value scale() { + return b(); + } + + public void setScale(Value scale) { + setB(scale); + } + + @Override + public LoopBegin loopBegin() { + return base().loopBegin(); + } + + @Override + public void peelOneIteration() { + // nop + } + + /** + * This will apply strength reduction to this induction variable but will augment register pressure in the loop. + * @return the new BasicInductionVariable + */ + public BasicInductionVariable toBasicInductionVariable() { + InductionVariable base = base(); + if (base instanceof DerivedInductionVariable) { + base = ((DerivedInductionVariable) base).toBasicInductionVariable(); + } + Value init; + Value stride; + LoopCounter counter; + if (base instanceof BasicInductionVariable) { + BasicInductionVariable basic = (BasicInductionVariable) base; + // let the canonicalizer do its job with this + init = IntegerArithmeticNode.add(offset(), IntegerArithmeticNode.mul(scale(), basic.init())); + stride = IntegerArithmeticNode.mul(scale(), basic.stride()); + counter = basic.loopCounter(); + } else { + assert base instanceof LoopCounter; + init = offset(); + stride = scale(); + counter = (LoopCounter) base; + } + BasicInductionVariable newBIV = new BasicInductionVariable(kind, init, stride, counter, graph()); + this.replaceAndDelete(newBIV); + return newBIV; + } + + @SuppressWarnings("unchecked") + @Override + public <T extends Op> T lookup(Class<T> clazz) { + if (clazz == LoweringOp.class) { + return (T) LOWERING; + } + return super.lookup(clazz); + } + + private static final LoweringOp LOWERING = new LoweringOp() { + @Override + public void lower(Node n, CiLoweringTool tool) { + DerivedInductionVariable div = (DerivedInductionVariable) n; + IntegerArithmeticNode computed = IntegerArithmeticNode.add(div.offset(), IntegerArithmeticNode.mul(div.scale(), div.base())); + div.replaceAtNonIVUsages(computed); + } + }; +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/InductionVariable.java Tue Aug 09 18:53:11 2011 +0200 @@ -0,0 +1,51 @@ +/* + * Copyright (c) 2011, 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.max.graal.compiler.ir; + +import com.oracle.max.graal.graph.*; +import com.sun.cri.ci.*; + +public abstract class InductionVariable extends FloatingNode { + + public InductionVariable(CiKind kind, Graph graph) { + super(kind, graph); + assert kind.isInt() || kind.isLong(); + } + + public abstract LoopBegin loopBegin(); + + public abstract void peelOneIteration(); + + public void replaceAtNonIVUsages(Node other) { + for (Node usage : this.usages().snapshot()) { + if (!(usage instanceof InductionVariable)) { + usage.replaceFirstInput(this, other); + } + } + } + + @Override + public void accept(ValueVisitor v) { + // nop + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LinearInductionVariable.java Tue Aug 09 18:53:11 2011 +0200 @@ -0,0 +1,63 @@ +/* + * Copyright (c) 2011, 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.max.graal.compiler.ir; + +import com.oracle.max.graal.graph.*; +import com.sun.cri.ci.*; + +/** + * InductionVariable of the form a+b*x. + */ +public abstract class LinearInductionVariable extends InductionVariable { + @Input private Value a; + @Input private Value b; + + public LinearInductionVariable(CiKind kind, Value a, Value b, Graph graph) { + super(kind, graph); + setA(a); + setB(b); + } + + protected Value a() { + return a; + } + + protected Value b() { + return b; + } + + protected void setA(Value a) { + updateUsages(this.a, a); + this.a = a; + } + + + protected void setB(Value b) { + updateUsages(this.b, b); + this.b = b; + } + + public boolean isLinearInductionVariableInput(Node n) { + return n == a() || n == b(); + } +}
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LoopBegin.java Tue Aug 09 14:43:41 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LoopBegin.java Tue Aug 09 18:53:11 2011 +0200 @@ -27,6 +27,7 @@ import com.oracle.max.graal.compiler.debug.*; import com.oracle.max.graal.compiler.util.*; import com.oracle.max.graal.graph.*; +import com.sun.cri.ci.*; public class LoopBegin extends Merge { @@ -92,8 +93,8 @@ throw Util.shouldNotReachHere(); } - public Collection<LoopCounter> counters() { - return Util.filter(this.usages(), LoopCounter.class); + public Collection<InductionVariable> inductionVariables() { + return Util.filter(this.usages(), InductionVariable.class); } @Override @@ -105,6 +106,19 @@ return this.endAt(0); } + public LoopCounter loopCounter() { + return loopCounter(CiKind.Long); + } + + public LoopCounter loopCounter(CiKind kind) { + for (Node usage : usages()) { + if (usage instanceof LoopCounter && ((LoopCounter) usage).kind == kind) { + return (LoopCounter) usage; + } + } + return new LoopCounter(kind, this, graph()); + } + @Override public boolean verify() { assertTrue(loopEnd() != null);
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LoopCounter.java Tue Aug 09 14:43:41 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LoopCounter.java Tue Aug 09 18:53:11 2011 +0200 @@ -22,34 +22,18 @@ */ package com.oracle.max.graal.compiler.ir; -import com.oracle.max.graal.compiler.debug.*; +import com.oracle.max.graal.compiler.phases.LoweringPhase.*; import com.oracle.max.graal.graph.*; import com.sun.cri.ci.*; - -public final class LoopCounter extends FloatingNode { - @Input private Value init; - @Input private Value stride; +/** + * Counts loop iterations from 0 to Niter. + * If used directly (and not just by BasicInductionVariables) computed with Phi(0, this + 1) + */ +public final class LoopCounter extends InductionVariable { @Input private LoopBegin loopBegin; - public Value init() { - return init; - } - - public void setInit(Value x) { - updateUsages(init, x); - init = x; - } - - public Value stride() { - return stride; - } - - public void setStride(Value x) { - updateUsages(stride, x); - stride = x; - } - + @Override public LoopBegin loopBegin() { return loopBegin; } @@ -59,21 +43,46 @@ loopBegin = x; } - public LoopCounter(CiKind kind, Value init, Value stride, LoopBegin loop, Graph graph) { + public LoopCounter(CiKind kind, LoopBegin loop, Graph graph) { super(kind, graph); - setInit(init); - setStride(stride); setLoopBegin(loop); } @Override - public void accept(ValueVisitor v) { - // TODO Auto-generated method stub - + public void peelOneIteration() { + BasicInductionVariable biv = null; + for (Node usage : usages()) { + if (!(usage instanceof InductionVariable && ((InductionVariable) usage).loopBegin() == this.loopBegin())) { + if (biv == null) { + biv = createBasicInductionVariable(); + biv.peelOneIteration(); + } + usage.inputs().replace(this, biv); + } + } } + @SuppressWarnings("unchecked") @Override - public void print(LogStream out) { - out.print("loopcounter [").print(init()).print(",+").print(stride()).print("]"); + public <T extends Op> T lookup(Class<T> clazz) { + if (clazz == LoweringOp.class) { + return (T) LOWERING; + } + return super.lookup(clazz); + } + + private BasicInductionVariable createBasicInductionVariable() { + Graph graph = graph(); + return new BasicInductionVariable(kind, Constant.forInt(0, graph), Constant.forInt(1, graph), this, graph); } + + private static final LoweringOp LOWERING = new LoweringOp() { + @Override + public void lower(Node n, CiLoweringTool tool) { + LoopCounter loopCounter = (LoopCounter) n; + Graph graph = n.graph(); + Phi phi = BasicInductionVariable.LOWERING.ivToPhi(loopCounter.loopBegin(), Constant.forInt(0, graph), Constant.forInt(1, graph), loopCounter.kind); + loopCounter.replaceAtNonIVUsages(phi); + } + }; }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/LoopPhase.java Tue Aug 09 14:43:41 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/LoopPhase.java Tue Aug 09 18:53:11 2011 +0200 @@ -26,11 +26,9 @@ import com.oracle.max.graal.compiler.*; import com.oracle.max.graal.compiler.ir.*; -import com.oracle.max.graal.compiler.ir.Phi.PhiType; import com.oracle.max.graal.compiler.observer.*; import com.oracle.max.graal.compiler.util.*; import com.oracle.max.graal.compiler.util.LoopUtil.Loop; -import com.oracle.max.graal.compiler.value.*; import com.oracle.max.graal.graph.*; import com.oracle.max.graal.graph.collections.*; import com.sun.cri.ci.*; @@ -79,120 +77,119 @@ } } - /* for (Loop loop : loops) { - doLoopCounters(loop); - }*/ + findInductionVariables(loop); + } } - private void doLoopCounters(Loop loop) { + private void findInductionVariables(Loop loop) { LoopBegin loopBegin = loop.loopBegin(); - List<LoopCounter> counters = findLoopCounters(loopBegin, loop.nodes()); - mergeLoopCounters(counters, loopBegin); - } - - private void mergeLoopCounters(List<LoopCounter> counters, LoopBegin loopBegin) { - Graph graph = loopBegin.graph(); - FrameState stateAfter = loopBegin.stateAfter(); - LoopCounter[] acounters = counters.toArray(new LoopCounter[counters.size()]); - for (int i = 0; i < acounters.length; i++) { - LoopCounter c1 = acounters[i]; - if (c1 == null) { + NodeBitMap loopNodes = loop.nodes(); + List<Phi> phis = new ArrayList<Phi>(loopBegin.phis()); + int backIndex = loopBegin.phiPredecessorIndex(loopBegin.loopEnd()); + int initIndex = loopBegin.phiPredecessorIndex(loopBegin.forwardEdge()); + for (Phi phi : phis) { + Value init = phi.valueAt(initIndex); + Value backEdge = phi.valueAt(backIndex); + if (loopNodes.isNew(init) || loopNodes.isNew(backEdge)) { continue; } - for (int j = i + 1; j < acounters.length; j++) { - LoopCounter c2 = acounters[j]; - if (c2 != null && c1.stride().valueEqual(c2.stride())) { - boolean c1InCompare = Util.filter(c1.usages(), Compare.class).size() > 0; - boolean c2inCompare = Util.filter(c2.usages(), Compare.class).size() > 0; - if (c2inCompare && !c1InCompare) { - c1 = acounters[j]; - c2 = acounters[i]; - acounters[i] = c2; - acounters[j] = c1; + if (loopNodes.isMarked(backEdge)) { + Binary binary; + if (backEdge instanceof IntegerAdd || backEdge instanceof IntegerSub) { + binary = (Binary) backEdge; + } else { + continue; + } + Value stride; + if (binary.x() == phi) { + stride = binary.y(); + } else if (binary.y() == phi) { + stride = binary.x(); + } else { + continue; + } + if (loopNodes.isNotNewNotMarked(stride)) { + Graph graph = loopBegin.graph(); + if (backEdge instanceof IntegerSub) { + stride = new Negate(stride, graph); } - boolean c2InFramestate = stateAfter != null ? stateAfter.inputs().contains(c2) : false; - acounters[j] = null; - CiKind kind = c1.kind; - if (c2InFramestate) { - IntegerSub sub = new IntegerSub(kind, c2.init(), c1.init(), graph); - IntegerAdd addStride = new IntegerAdd(kind, sub, c1.stride(), graph); - IntegerAdd add = new IntegerAdd(kind, c1, addStride, graph); - Phi phi = new Phi(kind, loopBegin, PhiType.Value, graph); // (gd) assumes order on loopBegin preds - works in collab with graph builder - phi.addInput(c2.init()); - phi.addInput(add); - c2.replaceAndDelete(phi); + CiKind kind = phi.kind; + LoopCounter counter = loopBegin.loopCounter(kind); + BasicInductionVariable biv1 = null; + BasicInductionVariable biv2 = null; + if (phi.usages().size() > 1) { + biv1 = new BasicInductionVariable(kind, init, stride, counter, graph); + phi.replaceAndDelete(biv1); } else { - IntegerSub sub = new IntegerSub(kind, c2.init(), c1.init(), graph); - IntegerAdd add = new IntegerAdd(kind, c1, sub, graph); - c2.replaceAndDelete(add); + phi.replaceFirstInput(binary, null); + phi.delete(); + } + if (backEdge.usages().size() > 0) { + biv2 = new BasicInductionVariable(kind, IntegerArithmeticNode.add(init, stride), stride, counter, graph); + backEdge.replaceAndDelete(biv2); + } else { + backEdge.delete(); + } + if (biv1 != null) { + findDerivedInductionVariable(biv1, kind, loopNodes); + } + if (biv2 != null) { + findDerivedInductionVariable(biv2, kind, loopNodes); } } } } } - - private List<LoopCounter> findLoopCounters(LoopBegin loopBegin, NodeBitMap loopNodes) { - LoopEnd loopEnd = loopBegin.loopEnd(); - FrameState loopEndState = null; - Node loopEndPred = loopEnd.predecessor(); - if (loopEndPred instanceof Merge) { - loopEndState = ((Merge) loopEndPred).stateAfter(); - } - List<LoopCounter> counters = new LinkedList<LoopCounter>(); - for (Node usage : loopBegin.usages().snapshot()) { - if (usage instanceof Phi) { - Phi phi = (Phi) usage; - if (phi.valueCount() == 2) { - Value backEdge = phi.valueAt(1); - Value init = phi.valueAt(0); - if (loopNodes.isNew(init) || loopNodes.isNew(backEdge)) { - continue; - } - if (loopNodes.isMarked(init)) { - // try to reverse init/backEdge order - Value tmp = backEdge; - backEdge = init; - init = tmp; + private void findDerivedInductionVariable(BasicInductionVariable biv, CiKind kind, NodeBitMap loopNodes) { + for (Node usage : biv.usages().snapshot()) { + Value scale = scale(usage, biv, loopNodes); + Value offset = null; + Node node = null; + if (scale == null) { + if (usage instanceof IntegerAdd) { + IntegerAdd add = (IntegerAdd) usage; + if (add.x() == biv || (scale = scale(add.x(), biv, loopNodes)) != null) { + offset = add.y(); + } else if (add.y() == biv || (scale = scale(add.y(), biv, loopNodes)) != null) { + offset = add.x(); } - Value stride = null; - boolean useCounterAfterAdd = false; - if (!loopNodes.isMarked(init) && backEdge instanceof IntegerAdd && loopNodes.isMarked(backEdge)) { - IntegerAdd add = (IntegerAdd) backEdge; - int addUsageCount = 0; - for (Node u : add.usages()) { - if (u != loopEndState && u != phi) { - addUsageCount++; - } - } - if (add.x() == phi) { - stride = add.y(); - } else if (add.y() == phi) { - stride = add.x(); - } - if (addUsageCount > 0) { - useCounterAfterAdd = true; - } - } - if (stride != null && loopNodes.isNotNewNotMarked(stride)) { - Graph graph = loopBegin.graph(); - LoopCounter counter = new LoopCounter(init.kind, init, stride, loopBegin, graph); - counters.add(counter); - phi.replaceAndDelete(counter); - if (loopEndState != null) { - loopEndState.inputs().replace(backEdge, counter); - } - if (useCounterAfterAdd) { - /*IntegerAdd otherInit = new IntegerAdd(init.kind, init, stride, graph); // would be nice to canonicalize - LoopCounter otherCounter = new LoopCounter(init.kind, otherInit, stride, loopBegin, graph); - backEdge.replace(otherCounter);*/ + if (offset != null) { + if (loopNodes.isNotNewNotMarked(offset)) { + node = add; } else { - backEdge.delete(); + offset = null; } } } + } else { + node = usage; + } + if (scale != null || offset != null) { + if (scale == null) { + scale = Constant.forInt(1, biv.graph()); + } else if (offset == null) { + offset = Constant.forInt(0, biv.graph()); + } + DerivedInductionVariable div = new DerivedInductionVariable(kind, offset, scale, biv, biv.graph()); + node.replaceAndDelete(div); } } - return counters; + } + + private Value scale(Node n, BasicInductionVariable biv, NodeBitMap loopNodes) { + if (n instanceof IntegerMul) { + IntegerMul mul = (IntegerMul) n; + Value scale = null; + if (mul.x() == biv) { + scale = mul.y(); + } else if (mul.y() == biv) { + scale = mul.x(); + } + if (scale != null && loopNodes.isNotNewNotMarked(scale)) { + return scale; + } + } + return null; } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/LoweringPhase.java Tue Aug 09 14:43:41 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/LoweringPhase.java Tue Aug 09 18:53:11 2011 +0200 @@ -27,6 +27,7 @@ import com.oracle.max.graal.compiler.ir.*; import com.oracle.max.graal.compiler.schedule.*; import com.oracle.max.graal.graph.*; +import com.oracle.max.graal.graph.collections.*; import com.sun.cri.ci.*; import com.sun.cri.ri.*; @@ -50,13 +51,36 @@ final IdentifyBlocksPhase s = new IdentifyBlocksPhase(false); s.apply(graph); + NodeBitMap processed = graph.createNodeBitMap(); List<Block> blocks = s.getBlocks(); for (final Block b : blocks) { - process(b); + process(b, processed); + } + + processed.negate(); + final CiLoweringTool loweringTool = new CiLoweringTool() { + @Override + public Node getGuardAnchor() { + throw new UnsupportedOperationException(); + } + @Override + public RiRuntime getRuntime() { + return runtime; + } + @Override + public Node createGuard(Node condition) { + throw new UnsupportedOperationException(); + } + }; + for (Node node : processed) { + LoweringOp op = node.lookup(LoweringOp.class); + if (op != null) { + op.lower(node, loweringTool); + } } } - private void process(final Block b) { + private void process(final Block b, NodeBitMap processed) { final Node anchor = b.javaBlock().createAnchor(); final CiLoweringTool loweringTool = new CiLoweringTool() { @@ -83,11 +107,10 @@ // Lower the instructions of this block. for (final Node n : b.getInstructions()) { - if (n instanceof FixedNode) { - LoweringOp op = n.lookup(LoweringOp.class); - if (op != null) { - op.lower(n, loweringTool); - } + processed.mark(n); + LoweringOp op = n.lookup(LoweringOp.class); + if (op != null) { + op.lower(n, loweringTool); } } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java Tue Aug 09 14:43:41 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java Tue Aug 09 18:53:11 2011 +0200 @@ -535,10 +535,10 @@ block = getCommonDominator(block, nodeToBlock.get(pred)); } closure.apply(block); - } else if (usage instanceof LoopCounter) { - LoopCounter counter = (LoopCounter) usage; - if (node == counter.init() || node == counter.stride()) { - LoopBegin loopBegin = counter.loopBegin(); + } else if (usage instanceof LinearInductionVariable) { + LinearInductionVariable liv = (LinearInductionVariable) usage; + if (liv.isLinearInductionVariableInput(node)) { + LoopBegin loopBegin = liv.loopBegin(); Block mergeBlock = nodeToBlock.get(loopBegin); closure.apply(mergeBlock.dominator()); }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/LoopUtil.java Tue Aug 09 14:43:41 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/LoopUtil.java Tue Aug 09 18:53:11 2011 +0200 @@ -347,8 +347,8 @@ } if (from == loopBegin.loopEnd()) { - for (LoopCounter counter : loopBegin.counters()) { - counter.setInit(new IntegerAdd(counter.kind, counter.init(), counter.stride(), graph)); + for (InductionVariable iv : loopBegin.inductionVariables()) { + iv.peelOneIteration(); } } NodeMap<NodeMap<Value>> newExitValues = graph.createNodeMap();