Mercurial > hg > truffle

changeset 2983:11dfbb40ca69

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
LoopCounter, WIP
author Gilles Duboscq <gilles.duboscq@oracle.com>
date Wed, 15 Jun 2011 16:36:37 +0200
parents 228276b7813b
children f49685081630
files graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/LoopPhase.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64LIRGenerator.java
diffstat 4 files changed, 70 insertions(+), 14 deletions(-) [+]
line wrap: on
line diff
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java	Wed Jun 15 11:31:00 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java	Wed Jun 15 16:36:37 2011 +0200
@@ -225,10 +225,16 @@
         }
 
         if (block.blockPredecessors().size() > 1) {
+            if (GraalOptions.TraceLIRGeneratorLevel >= 2) {
+                TTY.println("STATE RESET");
+            }
             lastState = null;
         }
 
         for (Node instr : block.getInstructions()) {
+            if (GraalOptions.TraceLIRGeneratorLevel >= 3) {
+                TTY.println("LIRGen for " + instr);
+            }
             FrameState stateAfter = null;
             if (instr instanceof Instruction) {
                 stateAfter = ((Instruction) instr).stateAfter();
@@ -277,7 +283,7 @@
     }
 
     private static boolean jumpsToNextBlock(Node node) {
-        return node instanceof BlockEnd || node instanceof Anchor || node instanceof LoopEnd;
+        return node instanceof BlockEnd || node instanceof Anchor;
     }
 
     @Override
@@ -1013,10 +1019,22 @@
                 emitXir(prologue, null, null, null, false);
             }
             FrameState fs = setOperandsForLocals();
+            if (GraalOptions.TraceLIRGeneratorLevel >= 2) {
+                TTY.println("STATE CHANGE (setOperandsForLocals)");
+                if (GraalOptions.TraceLIRGeneratorLevel >= 3) {
+                    TTY.println(fs.toString());
+                }
+            }
             lastState = fs;
         } else if (block.blockPredecessors().size() == 1) {
             FrameState fs = block.blockPredecessors().get(0).lastState();
             assert fs != null;
+            if (GraalOptions.TraceLIRGeneratorLevel >= 2) {
+                TTY.println("STATE CHANGE (singlePred)");
+                if (GraalOptions.TraceLIRGeneratorLevel >= 3) {
+                    TTY.println(fs.toString());
+                }
+            }
             lastState = fs;
         }
     }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/LoopPhase.java	Wed Jun 15 11:31:00 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/LoopPhase.java	Wed Jun 15 16:36:37 2011 +0200
@@ -42,22 +42,58 @@
     }
 
     private void doLoop(LoopBegin loopBegin) {
+        NodeBitMap loopNodes = computeLoopNodes(loopBegin);
+        List<LoopCounter> counters = findLoopCounters(loopBegin, loopNodes);
+        mergeLoopCounters(counters, loopBegin);
+    }
+
+    private void mergeLoopCounters(List<LoopCounter> counters, LoopBegin loopBegin) {
+        Graph graph = loopBegin.graph();
+        LoopCounter[] acounters = counters.toArray(new LoopCounter[counters.size()]);
+        for (int i = 0; i < acounters.length; i++) {
+            LoopCounter c1 = acounters[i];
+            if (c1 == null) {
+                continue;
+            }
+            for (int j = i + 1; j < acounters.length; j++) {
+                LoopCounter c2 = acounters[j];
+                if (c2 != null && c1.stride().valueEqual(c2.stride())) {
+                    acounters[j] = null;
+                    IntegerSub sub = new IntegerSub(c1.kind, c2.init(), c1.init(), graph);
+                    IntegerAdd add = new IntegerAdd(c1.kind, c1, sub, graph);
+                    Phi phi = new Phi(c1.kind, loopBegin, 2, graph); // TODO (gd) assumes order on loppBegin preds
+                    phi.addInput(c2.init());
+                    phi.addInput(add);
+                    c2.replace(phi);
+                    System.out.println("--> merged Loop Counters");
+                }
+            }
+        }
+    }
+
+    private List<LoopCounter> findLoopCounters(LoopBegin loopBegin, NodeBitMap loopNodes) {
         LoopEnd loopEnd = loopBegin.loopEnd();
-        NodeBitMap loopNodes = computeLoopNodes(loopBegin);
         List<Node> usages = new ArrayList<Node>(loopBegin.usages());
+        List<LoopCounter> counters = new LinkedList<LoopCounter>();
         for (Node usage : usages) {
             if (usage instanceof Phi) {
                 Phi phi = (Phi) usage;
-                if (phi.valueCount() == 2) { // TODO (gd) remove predecessor order assumptions
-                    Value backEdge = phi.valueAt(1); //assumes backEdge with pred index 1
+                if (phi.valueCount() == 2) {
+                    Value backEdge = phi.valueAt(1);
                     Value init = phi.valueAt(0);
+                    if (loopNodes.isMarked(init)) {
+                        // try to reverse init/backEdge order
+                        Value tmp = backEdge;
+                        backEdge = init;
+                        init = tmp;
+                    }
                     Value stride = null;
-                    boolean createAfterAddCounter = false;
+                    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 != loopEnd.stateBefore()) {
+                            if (u != loopEnd.stateBefore() && u != phi) {
                                 addUsageCount++;
                             }
                         }
@@ -66,19 +102,20 @@
                         } else if (add.y() == phi) {
                             stride = add.x();
                         }
-                        if (addUsageCount > 1) {
-                            createAfterAddCounter = true;
+                        if (addUsageCount > 0) {
+                            useCounterAfterAdd = true;
                         }
                     }
                     if (stride != null && !loopNodes.isMarked(stride)) {
                         Graph graph = loopBegin.graph();
                         LoopCounter counter = new LoopCounter(init.kind, init, stride, loopBegin, graph);
+                        counters.add(counter);
                         phi.replace(counter);
                         loopEnd.stateBefore().inputs().replace(backEdge, counter);
-                        if (createAfterAddCounter) {
-                            IntegerAdd otherInit = new IntegerAdd(init.kind, init, stride, graph); // would be nice to canonicalize
+                        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);
+                            backEdge.replace(otherCounter);*/
                         } else {
                             backEdge.delete();
                         }
@@ -86,6 +123,7 @@
                 }
             }
         }
+        return counters;
     }
 
     private NodeBitMap computeLoopNodes(LoopBegin loopBegin) {
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java	Wed Jun 15 11:31:00 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java	Wed Jun 15 16:36:37 2011 +0200
@@ -305,7 +305,7 @@
                 if (n == counter.init()) {
                     LoopBegin loopBegin = counter.loopBegin();
                     Block mergeBlock = nodeToBlock.get(loopBegin);
-                    block = getCommonDominator(block, mergeBlock.getPredecessors().get(0)); // TODO (gd) nasty 0 constant
+                    block = getCommonDominator(block, mergeBlock.dominator());
                 }
             } else {
                 block = getCommonDominator(block, assignLatestPossibleBlockToNode(usage));
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64LIRGenerator.java	Wed Jun 15 11:31:00 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64LIRGenerator.java	Wed Jun 15 16:36:37 2011 +0200
@@ -496,8 +496,8 @@
     @Override
     public void visitLoopEnd(LoopEnd x) {
         setNoResult(x);
-        moveToPhi();
-        lir.jump(getLIRBlock(x.loopBegin()));
+        //moveToPhi();
+        //lir.jump(getLIRBlock(x.loopBegin()));
     }
 
     @Override