Mercurial > hg > truffle

changeset 19192:a7fb05f3d7e1

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Move induction variable detection logic into LoopEx
author Tom Rodriguez <tom.rodriguez@oracle.com>
date Mon, 09 Feb 2015 16:00:00 -0800
parents ef52cebd4030
children e7451826b8c0
files graal/com.oracle.graal.loop/src/com/oracle/graal/loop/InductionVariables.java graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopEx.java
diffstat 2 files changed, 99 insertions(+), 145 deletions(-) [+]
line wrap: on
line diff
--- 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<Node, InductionVariable> ivs;
-
-    public InductionVariables(LoopEx loop) {
-        this.loop = loop;
-        ivs = newIdentityMap();
-        findDerived(findBasic());
-    }
-
-    public InductionVariable get(ValueNode v) {
-        return ivs.get(v);
-    }
-
-    private Collection<BasicInductionVariable> findBasic() {
-        List<BasicInductionVariable> 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<BasicInductionVariable> bivs) {
-        Queue<InductionVariable> 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();
-        }
-    }
-}
--- 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<Node, InductionVariable> ivs;
 
     LoopEx(Loop<Block> loop, LoopsData data) {
         this.loop = loop;
@@ -252,19 +255,111 @@
         return LoopFragment.computeNodes(point.graph(), blocks, exits);
     }
 
-    public InductionVariables getInductionVariables() {
+    public Map<Node, InductionVariable> 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<Node, InductionVariable> findInductionVariables(LoopEx loop) {
+        Map<Node, InductionVariable> ivs = newIdentityMap();
+
+        Queue<InductionVariable> 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();
+            }
         }
     }
 }