# HG changeset patch
# User Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
# Date 1424708651 -3600
# Node ID 6bff0b223124b3145123cdb52f2139d888571c12
# Parent  cb7c6ccfff69885e6f2769d43a398878d9575226
Reduce complexity of DCE. We do not need to deal with incoming dead merge branches.

diff -r cb7c6ccfff69 -r 6bff0b223124 graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java	Mon Feb 23 16:29:30 2015 +0100
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java	Mon Feb 23 17:24:11 2015 +0100
@@ -825,8 +825,8 @@
         return true;
     }
 
-    Node getNode(int i) {
-        return nodes[i];
+    public Node getNode(int id) {
+        return nodes[id];
     }
 
     /**
diff -r cb7c6ccfff69 -r 6bff0b223124 graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeBitMap.java
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeBitMap.java	Mon Feb 23 16:29:30 2015 +0100
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeBitMap.java	Mon Feb 23 17:24:11 2015 +0100
@@ -60,6 +60,10 @@
     public boolean isMarked(Node node) {
         assert check(node, false);
         int id = nodeIdAccessor.getNodeId(node);
+        return isMarked(id);
+    }
+
+    public boolean isMarked(int id) {
         return (bits[id >> SHIFT] & (1L << id)) != 0;
     }
 
@@ -67,7 +71,7 @@
         assert check(node, true);
         int id = nodeIdAccessor.getNodeId(node);
         checkGrow(id);
-        return (bits[id >> SHIFT] & (1L << id)) != 0;
+        return isMarked(id);
     }
 
     public void mark(Node node) {
diff -r cb7c6ccfff69 -r 6bff0b223124 graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeFlood.java
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeFlood.java	Mon Feb 23 16:29:30 2015 +0100
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeFlood.java	Mon Feb 23 17:24:11 2015 +0100
@@ -24,10 +24,11 @@
 
 import java.util.*;
 
-public class NodeFlood implements Iterable<Node> {
+public final class NodeFlood implements Iterable<Node> {
 
     private final NodeBitMap visited;
     private final Queue<Node> worklist;
+    private int totalMarkedCount;
 
     public NodeFlood(Graph graph) {
         visited = graph.createNodeBitMap();
@@ -38,15 +39,24 @@
         if (node != null && !visited.isMarked(node)) {
             visited.mark(node);
             worklist.add(node);
+            totalMarkedCount++;
         }
     }
 
+    public int getTotalMarkedCount() {
+        return totalMarkedCount;
+    }
+
     public void addAll(Iterable<? extends Node> nodes) {
         for (Node node : nodes) {
             this.add(node);
         }
     }
 
+    public NodeBitMap getVisited() {
+        return visited;
+    }
+
     public boolean isMarked(Node node) {
         return visited.isMarked(node);
     }
diff -r cb7c6ccfff69 -r 6bff0b223124 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/DeadCodeEliminationPhase.java
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/DeadCodeEliminationPhase.java	Mon Feb 23 16:29:30 2015 +0100
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/DeadCodeEliminationPhase.java	Mon Feb 23 17:24:11 2015 +0100
@@ -24,6 +24,8 @@
 
 import static com.oracle.graal.phases.common.DeadCodeEliminationPhase.Options.*;
 
+import java.util.function.*;
+
 import com.oracle.graal.debug.*;
 import com.oracle.graal.graph.*;
 import com.oracle.graal.nodes.*;
@@ -70,93 +72,51 @@
         if (optional && ReduceDCE.getValue()) {
             return;
         }
+
         NodeFlood flood = graph.createNodeFlood();
-
+        int totalNodeCount = graph.getNodeCount();
         flood.add(graph.start());
-        iterateSuccessors(flood);
-        disconnectCFGNodes(flood, graph);
-        iterateInputs(flood, graph);
+        iterateSuccessorsAndInputs(flood);
+        int totalMarkedCount = flood.getTotalMarkedCount();
+        if (totalNodeCount == totalMarkedCount) {
+            // All nodes are live => nothing more to do.
+            return;
+        } else {
+            // Some nodes are not marked alive and therefore dead => proceed.
+            assert totalNodeCount > totalMarkedCount;
+        }
+
         deleteNodes(flood, graph);
-
-        // remove chained Merges
-        for (AbstractMergeNode merge : graph.getNodes(AbstractMergeNode.TYPE)) {
-            if (merge.forwardEndCount() == 1 && !(merge instanceof LoopBeginNode)) {
-                graph.reduceTrivialMerge(merge);
-            }
-        }
     }
 
-    private static void iterateSuccessors(NodeFlood flood) {
+    private static void iterateSuccessorsAndInputs(NodeFlood flood) {
+        BiConsumer<Node, Node> consumer = (n, succ) -> {
+            flood.add(succ);
+        };
         for (Node current : flood) {
             if (current instanceof AbstractEndNode) {
                 AbstractEndNode end = (AbstractEndNode) current;
                 flood.add(end.merge());
             } else {
-                for (Node successor : current.successors()) {
-                    flood.add(successor);
-                }
-            }
-        }
-    }
-
-    private static void disconnectCFGNodes(NodeFlood flood, StructuredGraph graph) {
-        for (AbstractEndNode node : graph.getNodes(AbstractEndNode.TYPE)) {
-            if (!flood.isMarked(node)) {
-                AbstractMergeNode merge = node.merge();
-                if (merge != null && flood.isMarked(merge)) {
-                    // We are a dead end node leading to a live merge.
-                    merge.removeEnd(node);
-                }
-            }
-        }
-        for (LoopBeginNode loop : graph.getNodes(LoopBeginNode.TYPE)) {
-            if (flood.isMarked(loop)) {
-                boolean reachable = false;
-                for (LoopEndNode end : loop.loopEnds()) {
-                    if (flood.isMarked(end)) {
-                        reachable = true;
-                        break;
-                    }
-                }
-                if (!reachable) {
-                    Debug.log("Removing loop with unreachable end: %s", loop);
-                    for (LoopEndNode end : loop.loopEnds().snapshot()) {
-                        loop.removeEnd(end);
-                    }
-                    graph.reduceDegenerateLoopBegin(loop);
-                }
+                current.acceptSuccessors(consumer);
+                current.acceptInputs(consumer);
             }
         }
     }
 
     private static void deleteNodes(NodeFlood flood, StructuredGraph graph) {
+        BiConsumer<Node, Node> consumer = (n, input) -> {
+            if (input.isAlive() && flood.isMarked(input)) {
+                input.removeUsage(n);
+            }
+        };
+
         for (Node node : graph.getNodes()) {
             if (!flood.isMarked(node)) {
-                node.clearInputs();
-                node.clearSuccessors();
-            }
-        }
-        for (Node node : graph.getNodes()) {
-            if (!flood.isMarked(node)) {
+                node.markDeleted();
+                node.acceptInputs(consumer);
                 metricNodesRemoved.increment();
-                node.safeDelete();
             }
         }
     }
-
-    private static void iterateInputs(NodeFlood flood, StructuredGraph graph) {
-        for (Node node : graph.getNodes()) {
-            if (flood.isMarked(node)) {
-                for (Node input : node.inputs()) {
-                    flood.add(input);
-                }
-            }
-        }
-        for (Node current : flood) {
-            for (Node input : current.inputs()) {
-                flood.add(input);
-            }
-        }
-    }
-
 }