Mercurial > hg > graal-jvmci-8
changeset 19560:6bff0b223124
Reduce complexity of DCE. We do not need to deal with incoming dead merge branches.
author | Thomas Wuerthinger <thomas.wuerthinger@oracle.com> |
---|---|
date | Mon, 23 Feb 2015 17:24:11 +0100 |
parents | cb7c6ccfff69 |
children | 9b1f8438141a |
files | graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeBitMap.java graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeFlood.java graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/DeadCodeEliminationPhase.java |
diffstat | 4 files changed, 46 insertions(+), 72 deletions(-) [+] |
line wrap: on
line diff
--- 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]; } /**
--- 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) {
--- 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); }
--- 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); - } - } - } - }