# HG changeset patch # User Tom Rodriguez # Date 1423526400 28800 # Node ID a7fb05f3d7e18142ff8c3aeee25f7018154db7c4 # Parent ef52cebd40306d413ac8dc876d9783d057ccdc4a Move induction variable detection logic into LoopEx diff -r ef52cebd4030 -r a7fb05f3d7e1 graal/com.oracle.graal.loop/src/com/oracle/graal/loop/InductionVariables.java --- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/InductionVariables.java Mon Feb 09 15:55:00 2015 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,141 +0,0 @@ -/* - * Copyright (c) 2012, 2014, 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 static com.oracle.graal.graph.Node.*; - -import java.util.*; - -import com.oracle.graal.compiler.common.type.*; -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 = newIdentityMap(); - findDerived(findBasic()); - } - - public InductionVariable get(ValueNode v) { - return ivs.get(v); - } - - private Collection findBasic() { - List bivs = new LinkedList<>(); - LoopBeginNode loopBegin = loop.loopBegin(); - AbstractEndNode forwardEnd = loopBegin.forwardEnd(); - for (PhiNode phi : loopBegin.phis().filter(ValuePhiNode.class)) { - ValueNode backValue = phi.singleBackValue(); - if (backValue == PhiNode.MULTIPLE_VALUES) { - continue; - } - ValueNode stride = addSub(backValue, phi); - if (stride != null) { - BasicInductionVariable biv = new BasicInductionVariable(loop, (ValuePhiNode) phi, phi.valueAt(forwardEnd), stride, (BinaryArithmeticNode) 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; - } - if (op.usages().count() == 1 && op.usages().first() == baseIvNode) { - /* - * This is just the base induction variable increment with no other uses so - * don't bother reporting it. - */ - continue; - } - InductionVariable iv = null; - ValueNode offset = addSub(op, baseIvNode); - ValueNode scale; - if (offset != null) { - iv = new DerivedOffsetInductionVariable(loop, baseIv, offset, (BinaryArithmeticNode) 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.stamp() instanceof IntegerStamp && (op instanceof AddNode || op instanceof SubNode)) { - BinaryArithmeticNode aritOp = (BinaryArithmeticNode) op; - if (aritOp.getX() == base && loop.isOutsideLoop(aritOp.getY())) { - return aritOp.getY(); - } else if (aritOp.getY() == base && loop.isOutsideLoop(aritOp.getX())) { - return aritOp.getX(); - } - } - return null; - } - - private ValueNode mul(ValueNode op, ValueNode base) { - if (op instanceof MulNode) { - MulNode mul = (MulNode) op; - if (mul.getX() == base && loop.isOutsideLoop(mul.getY())) { - return mul.getY(); - } else if (mul.getY() == base && loop.isOutsideLoop(mul.getX())) { - return mul.getX(); - } - } - if (op instanceof LeftShiftNode) { - LeftShiftNode shift = (LeftShiftNode) op; - if (shift.getX() == base && shift.getY().isConstant()) { - return ConstantNode.forInt(1 << shift.getY().asJavaConstant().asInt(), base.graph()); - } - } - return null; - } - - /** - * Deletes any nodes created within the scope of this object that have no usages. - */ - public void deleteUnusedNodes() { - for (InductionVariable iv : ivs.values()) { - iv.deleteUnusedNodes(); - } - } -} diff -r ef52cebd4030 -r a7fb05f3d7e1 graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopEx.java --- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopEx.java Mon Feb 09 15:55:00 2015 -0800 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopEx.java Mon Feb 09 16:00:00 2015 -0800 @@ -22,11 +22,14 @@ */ package com.oracle.graal.loop; +import static com.oracle.graal.graph.Node.*; + import java.util.*; import com.oracle.graal.compiler.common.*; import com.oracle.graal.compiler.common.calc.*; import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.compiler.common.type.*; import com.oracle.graal.debug.*; import com.oracle.graal.graph.*; import com.oracle.graal.graph.iterators.*; @@ -44,7 +47,7 @@ private LoopFragmentWhole whole; private CountedLoopInfo counted; // TODO (gd) detect private LoopsData data; - private InductionVariables ivs; + private Map ivs; LoopEx(Loop loop, LoopsData data) { this.loop = loop; @@ -252,19 +255,111 @@ return LoopFragment.computeNodes(point.graph(), blocks, exits); } - public InductionVariables getInductionVariables() { + public Map getInductionVariables() { if (ivs == null) { - ivs = new InductionVariables(this); + ivs = findInductionVariables(this); } return ivs; } /** + * Collect all the basic induction variables for the loop and the find any induction variables + * which are derived from the basic ones. + * + * @param loop + * @return a map from node to induction variable + */ + private static Map findInductionVariables(LoopEx loop) { + Map ivs = newIdentityMap(); + + Queue scanQueue = new LinkedList<>(); + LoopBeginNode loopBegin = loop.loopBegin(); + AbstractEndNode forwardEnd = loopBegin.forwardEnd(); + for (PhiNode phi : loopBegin.phis().filter(ValuePhiNode.class)) { + ValueNode backValue = phi.singleBackValue(); + if (backValue == PhiNode.MULTIPLE_VALUES) { + continue; + } + ValueNode stride = addSub(loop, backValue, phi); + if (stride != null) { + BasicInductionVariable biv = new BasicInductionVariable(loop, (ValuePhiNode) phi, phi.valueAt(forwardEnd), stride, (BinaryArithmeticNode) backValue); + ivs.put(phi, biv); + scanQueue.add(biv); + } + } + + while (!scanQueue.isEmpty()) { + InductionVariable baseIv = scanQueue.remove(); + ValueNode baseIvNode = baseIv.valueNode(); + for (ValueNode op : baseIvNode.usages().filter(ValueNode.class)) { + if (loop.isOutsideLoop(op)) { + continue; + } + if (op.usages().count() == 1 && op.usages().first() == baseIvNode) { + /* + * This is just the base induction variable increment with no other uses so + * don't bother reporting it. + */ + continue; + } + InductionVariable iv = null; + ValueNode offset = addSub(loop, op, baseIvNode); + ValueNode scale; + if (offset != null) { + iv = new DerivedOffsetInductionVariable(loop, baseIv, offset, (BinaryArithmeticNode) op); + } else if (op instanceof NegateNode) { + iv = new DerivedScaledInductionVariable(loop, baseIv, (NegateNode) op); + } else if ((scale = mul(loop, op, baseIvNode)) != null) { + iv = new DerivedScaledInductionVariable(loop, baseIv, scale, op); + } + + if (iv != null) { + ivs.put(op, iv); + scanQueue.offer(iv); + } + } + } + return Collections.unmodifiableMap(ivs); + } + + private static ValueNode addSub(LoopEx loop, ValueNode op, ValueNode base) { + if (op.stamp() instanceof IntegerStamp && (op instanceof AddNode || op instanceof SubNode)) { + BinaryArithmeticNode aritOp = (BinaryArithmeticNode) op; + if (aritOp.getX() == base && loop.isOutsideLoop(aritOp.getY())) { + return aritOp.getY(); + } else if (aritOp.getY() == base && loop.isOutsideLoop(aritOp.getX())) { + return aritOp.getX(); + } + } + return null; + } + + private static ValueNode mul(LoopEx loop, ValueNode op, ValueNode base) { + if (op instanceof MulNode) { + MulNode mul = (MulNode) op; + if (mul.getX() == base && loop.isOutsideLoop(mul.getY())) { + return mul.getY(); + } else if (mul.getY() == base && loop.isOutsideLoop(mul.getX())) { + return mul.getX(); + } + } + if (op instanceof LeftShiftNode) { + LeftShiftNode shift = (LeftShiftNode) op; + if (shift.getX() == base && shift.getY().isConstant()) { + return ConstantNode.forInt(1 << shift.getY().asJavaConstant().asInt(), base.graph()); + } + } + return null; + } + + /** * Deletes any nodes created within the scope of this object that have no usages. */ public void deleteUnusedNodes() { if (ivs != null) { - ivs.deleteUnusedNodes(); + for (InductionVariable iv : ivs.values()) { + iv.deleteUnusedNodes(); + } } } }