# HG changeset patch
# User Thomas Wuerthinger <thomas@wuerthinger.net>
# Date 1306847875 -7200
# Node ID adc4b3ec0a8c90fb3f34d26e26e7da7999ea2888
# Parent  7b5831f0e913f70f39078cbc8aec13c421a96774
Deleted LIR critical edge splitter and replaced with GraalIR edge splitter using Anchor nodes (=> simpler).

diff -r 7b5831f0e913 -r adc4b3ec0a8c graal/GraalCompiler/src/com/oracle/max/graal/schedule/Schedule.java
--- a/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Schedule.java	Tue May 31 13:42:01 2011 +0200
+++ b/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Schedule.java	Tue May 31 15:17:55 2011 +0200
@@ -432,6 +432,9 @@
     }
 
     public static int trueSuccessorCount(Node n) {
+        if (n == null) {
+            return 0;
+        }
         int i = 0;
         for (Node s : n.successors()) {
             if (isCFG(s)) {
@@ -440,4 +443,21 @@
         }
         return i;
     }
+
+    public static int truePredecessorCount(Node n) {
+        if (n == null) {
+            return 0;
+        }
+        int i = 0;
+        for (Node s : n.predecessors()) {
+            if (isCFG(s)) {
+                i++;
+            }
+        }
+
+        if (n instanceof LoopBegin) {
+            i++;
+        }
+        return i;
+    }
 }
diff -r 7b5831f0e913 -r adc4b3ec0a8c graal/GraalCompiler/src/com/sun/c1x/graph/CriticalEdgeFinder.java
--- a/graal/GraalCompiler/src/com/sun/c1x/graph/CriticalEdgeFinder.java	Tue May 31 13:42:01 2011 +0200
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,124 +0,0 @@
-/*
- * Copyright (c) 2009, 2010, 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.sun.c1x.graph;
-
-import java.util.*;
-
-import com.oracle.graal.graph.*;
-import com.sun.c1x.*;
-import com.sun.c1x.debug.*;
-import com.sun.c1x.ir.*;
-import com.sun.c1x.lir.*;
-
-/**
- * This class finds and splits "critical" edges in the control flow graph.
- * An edge between two blocks {@code A} and {@code B} is "critical" if {@code A}
- * has more than one successor and {@code B} has more than one predecessor. Such
- * edges are split by adding a block between the two blocks.
- */
-public class CriticalEdgeFinder {
-
-    private final List<LIRBlock> lirBlocks;
-    private final Graph graph;
-
-    /**
-     * The graph edges represented as a map from source to target nodes.
-     * Using a linked hash map makes compilation tracing more deterministic and thus eases debugging.
-     */
-    private Map<LIRBlock, List<LIRBlock>> edges = C1XOptions.DetailedAsserts ?
-                    new LinkedHashMap<LIRBlock, List<LIRBlock>>() :
-                    new HashMap<LIRBlock, List<LIRBlock>>();
-
-    public CriticalEdgeFinder(List<LIRBlock> lirBlocks, Graph graph) {
-        this.lirBlocks = lirBlocks;
-        this.graph = graph;
-        for (LIRBlock block : lirBlocks) {
-            apply(block);
-        }
-
-    }
-
-    private void apply(LIRBlock block) {
-        if (block.numberOfSux() >= 2) {
-            for (LIRBlock succ : block.blockSuccessors()) {
-                if (succ.numberOfPreds() >= 2) {
-                    // TODO: (tw) probably we don't have to make it a critical edge if succ only contains the _same_ predecessor multiple times.
-                    recordCriticalEdge(block, succ);
-                }
-            }
-        }
-    }
-
-    private void recordCriticalEdge(LIRBlock block, LIRBlock succ) {
-        if (!edges.containsKey(block)) {
-            edges.put(block, new ArrayList<LIRBlock>());
-        }
-
-        edges.get(block).add(succ);
-    }
-
-    public void splitCriticalEdges() {
-        for (Map.Entry<LIRBlock, List<LIRBlock>> entry : edges.entrySet()) {
-            LIRBlock from = entry.getKey();
-            for (LIRBlock to : entry.getValue()) {
-                LIRBlock split = splitEdge(from, to);
-                if (C1XOptions.PrintHIR) {
-                    TTY.println("Split edge between block %d and block %d, creating new block %d", from.blockID(), to.blockID(), split.blockID());
-                }
-            }
-        }
-    }
-
-
-    /**
-     * Creates and inserts a new block between this block and the specified successor,
-     * altering the successor and predecessor lists of involved blocks appropriately.
-     * @param source the source of the edge
-     * @param target the successor before which to insert a block
-     * @return the new block inserted
-     */
-    public LIRBlock splitEdge(LIRBlock source, LIRBlock target) {
-
-        // create new successor and mark it for special block order treatment
-        LIRBlock newSucc = new LIRBlock(lirBlocks.size());
-        lirBlocks.add(newSucc);
-
-        // This goto is not a safepoint.
-        Anchor e = new Anchor(null, graph);
-        Node sourceInstruction = source.lastInstruction();
-        Node targetInstruction = target.firstInstruction();
-        int sourceInstructionPredIndex = targetInstruction.predecessors().indexOf(sourceInstruction);
-        assert sourceInstructionPredIndex != -1 : "must find source instruction " + sourceInstruction + " in predecessor array of target instruction " + targetInstruction;
-        int replacedIndex = targetInstruction.predecessorsIndex().get(sourceInstructionPredIndex);
-        assert replacedIndex != -1 && sourceInstruction.successors().get(replacedIndex) != null;
-        e.successors().setAndClear(1, sourceInstruction, replacedIndex);
-        sourceInstruction.successors().set(replacedIndex, e);
-        newSucc.getInstructions().add(e);
-        assert e.defaultSuccessor() != null;
-        source.substituteSuccessor(target, newSucc);
-        target.substitutePredecessor(source, newSucc);
-        newSucc.blockPredecessors().add(source);
-        newSucc.blockSuccessors().add(target);
-        return newSucc;
-    }
-}
diff -r 7b5831f0e913 -r adc4b3ec0a8c graal/GraalCompiler/src/com/sun/c1x/graph/IR.java
--- a/graal/GraalCompiler/src/com/sun/c1x/graph/IR.java	Tue May 31 13:42:01 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/graph/IR.java	Tue May 31 15:17:55 2011 +0200
@@ -90,7 +90,25 @@
 //        newGraph.addDuplicate(compilation.graph.getNodes(), replacement);
 //        compilation.graph = newGraph;
 
-        Schedule schedule = new Schedule(this.compilation.graph);
+        Graph graph = compilation.graph;
+
+        // Split critical edges.
+        List<Node> nodes = graph.getNodes();
+        for (int i = 0; i < nodes.size(); ++i) {
+            Node n = nodes.get(i);
+            if (Schedule.trueSuccessorCount(n) > 1) {
+                for (int j = 0; j < n.successors().size(); ++j) {
+                    Node succ = n.successors().get(j);
+                    if (Schedule.truePredecessorCount(succ) > 1) {
+                        Anchor a = new Anchor(null, graph);
+                        a.successors().setAndClear(1, n, j);
+                        n.successors().set(j, a);
+                    }
+                }
+            }
+        }
+
+        Schedule schedule = new Schedule(graph);
         List<Block> blocks = schedule.getBlocks();
         List<LIRBlock> lirBlocks = new ArrayList<LIRBlock>();
         Map<Block, LIRBlock> map = new HashMap<Block, LIRBlock>();
@@ -115,9 +133,6 @@
             }
         }
 
-        CriticalEdgeFinder finder = new CriticalEdgeFinder(lirBlocks, compilation.graph);
-        finder.splitCriticalEdges();
-
         orderedBlocks = lirBlocks;
         valueToBlock = new HashMap<Node, LIRBlock>();
         for (LIRBlock b : orderedBlocks) {
@@ -129,14 +144,6 @@
         assert startBlock != null;
         assert startBlock.blockPredecessors().size() == 0;
 
-/*        if (startBlock.blockPredecessors().size() > 0) {
-            LIRBlock oldStartBlock = startBlock;
-            startBlock = new LIRBlock(orderedBlocks.size());
-            startBlock.blockSuccessors().add(oldStartBlock);
-
-            orderedBlocks.add(startBlock);
-        }*/
-
         ComputeLinearScanOrder clso = new ComputeLinearScanOrder(lirBlocks.size(), startBlock);
         orderedBlocks = clso.linearScanOrder();
         this.compilation.stats.loopCount = clso.numLoops();
diff -r 7b5831f0e913 -r adc4b3ec0a8c graal/GraalCompiler/src/com/sun/c1x/lir/LIRBlock.java
--- a/graal/GraalCompiler/src/com/sun/c1x/lir/LIRBlock.java	Tue May 31 13:42:01 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/lir/LIRBlock.java	Tue May 31 15:17:55 2011 +0200
@@ -237,24 +237,6 @@
         instructions = list;
     }
 
-    public void substituteSuccessor(LIRBlock target, LIRBlock newSucc) {
-        for (int i = 0; i < successors.size(); ++i) {
-            if (successors.get(i) == target) {
-                successors.set(i, newSucc);
-                break;
-            }
-        }
-    }
-
-    public void substitutePredecessor(LIRBlock source, LIRBlock newSucc) {
-        for (int i = 0; i < predecessors.size(); ++i) {
-            if (predecessors.get(i) == source) {
-                predecessors.set(i, newSucc);
-                break;
-            }
-        }
-    }
-
     public void setLastState(FrameState fs) {
         lastState = fs;
     }
diff -r 7b5831f0e913 -r adc4b3ec0a8c graal/GraalGraph/src/com/oracle/graal/graph/Graph.java
--- a/graal/GraalGraph/src/com/oracle/graal/graph/Graph.java	Tue May 31 13:42:01 2011 +0200
+++ b/graal/GraalGraph/src/com/oracle/graal/graph/Graph.java	Tue May 31 15:17:55 2011 +0200
@@ -26,6 +26,7 @@
 import java.util.Collection;
 import java.util.Collections;
 import java.util.HashMap;
+import java.util.List;
 import java.util.Map;
 import java.util.Map.Entry;
 
@@ -42,8 +43,8 @@
         end = new EndNode(this);
     }
 
-    public Collection<Node> getNodes() {
-        return Collections.unmodifiableCollection(nodes);
+    public List<Node> getNodes() {
+        return Collections.unmodifiableList(nodes);
     }
 
     int register(Node node) {
diff -r 7b5831f0e913 -r adc4b3ec0a8c rundacapo.sh
--- a/rundacapo.sh	Tue May 31 13:42:01 2011 +0200
+++ b/rundacapo.sh	Tue May 31 15:17:55 2011 +0200
@@ -15,4 +15,4 @@
   echo "DACAPO is not defined. It must point to a Dacapo benchmark directory."
   exit 1;
 fi
-${JDK7}/bin/java -client -d64 -graal -XX:-C1XBailoutIsFatal -XX:+PrintCompilation -C1X:+QuietBailout -Xms1g -Xmx2g -esa -classpath ${DACAPO}/dacapo-9.12-bach.jar Harness --preserve $*
+${JDK7}/bin/java -client -d64 -graal -XX:-C1XBailoutIsFatal -XX:+PrintCompilation -C1X:-QuietBailout -Xms1g -Xmx2g -esa -classpath ${DACAPO}/dacapo-9.12-bach.jar Harness --preserve $*