Mercurial > hg > truffle

comparison graal/GraalCompiler/src/com/sun/c1x/graph/DeadCodeElimination.java @ 2868:6d24c27902a2

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
turned inlining into a phase, some node cloning fixes, added NodeWorklist
author Lukas Stadler <lukas.stadler@jku.at>
date Tue, 07 Jun 2011 19:19:14 +0200
parents 5c545fef2c81
children
comparison
equal deleted inserted replaced
2867:5c545fef2c81 2868:6d24c27902a2
20 * or visit www.oracle.com if you need additional information or have any 20 * or visit www.oracle.com if you need additional information or have any
21 * questions. 21 * questions.
22 */ 22 */
23 package com.sun.c1x.graph; 23 package com.sun.c1x.graph;
24 24
25 import java.util.*;
26
27 import com.oracle.graal.graph.*; 25 import com.oracle.graal.graph.*;
28 import com.oracle.max.graal.schedule.*;
29 import com.sun.c1x.*; 26 import com.sun.c1x.*;
30 import com.sun.c1x.gen.*; 27 import com.sun.c1x.gen.*;
31 import com.sun.c1x.ir.*; 28 import com.sun.c1x.ir.*;
32 29
33 30
34 public class DeadCodeElimination extends Phase { 31 public class DeadCodeElimination extends Phase {
35 32
36 private NodeBitMap alive; 33 private NodeBitMap alive;
37 private Queue<Node> worklist; 34 private NodeWorklist worklist;
38 private Graph graph; 35 private Graph graph;
39 36
40 public int deletedNodeCount; 37 public int deletedNodeCount;
41 38
42 @Override 39 @Override
43 protected void run(Graph graph) { 40 protected void run(Graph graph) {
44 this.graph = graph; 41 this.graph = graph;
45 this.alive = graph.createNodeBitMap(); 42 this.alive = graph.createNodeBitMap();
46 this.worklist = new ArrayDeque<Node>(); 43 this.worklist = graph.createNodeWorklist();
47 44
48 addToWorklist(graph.start()); 45 worklist.add(graph.start());
49 46
50 iterateSuccessors(); 47 iterateSuccessors();
51 disconnectCFGNodes(); 48 disconnectCFGNodes();
52 49
53 iterateInputs(); 50 iterateInputs();
61 if (C1XOptions.TraceDeadCodeElimination) { 58 if (C1XOptions.TraceDeadCodeElimination) {
62 System.out.printf("dead code elimination: deleted %d nodes\n", deletedNodeCount); 59 System.out.printf("dead code elimination: deleted %d nodes\n", deletedNodeCount);
63 } 60 }
64 } 61 }
65 62
63 private static boolean isCFG(Node n) {
64 return n != null && ((n instanceof Instruction) || n == n.graph().start());
65 }
66
66 private void iterateSuccessors() { 67 private void iterateSuccessors() {
67 Node current; 68 for (Node current : worklist) {
68 while ((current = nextNode()) != null) {
69 for (Node successor : current.successors()) { 69 for (Node successor : current.successors()) {
70 addToWorklist(successor); 70 worklist.add(successor);
71 } 71 }
72 } 72 }
73 } 73 }
74 74
75 private void disconnectCFGNodes() { 75 private void disconnectCFGNodes() {
76 for (Node node : graph.getNodes()) { 76 for (Node node : graph.getNodes()) {
77 if (node != Node.Null && !alive.isMarked(node) && Schedule.isCFG(node)) { 77 if (node != Node.Null && !worklist.isMarked(node) && isCFG(node)) {
78 // iterate backwards so that the predecessor indexes in removePhiPredecessor are correct 78 // iterate backwards so that the predecessor indexes in removePhiPredecessor are correct
79 for (int i = node.successors().size() - 1; i >= 0; i--) { 79 for (int i = node.successors().size() - 1; i >= 0; i--) {
80 Node successor = node.successors().get(i); 80 Node successor = node.successors().get(i);
81 if (successor != Node.Null && alive.isMarked(successor)) { 81 if (successor != Node.Null && worklist.isMarked(successor)) {
82 if (successor instanceof Merge) { 82 if (successor instanceof Merge) {
83 ((Merge) successor).removePhiPredecessor(node); 83 ((Merge) successor).removePhiPredecessor(node);
84 } 84 }
85 } 85 }
86 } 86 }
90 } 90 }
91 } 91 }
92 92
93 private void deleteCFGNodes() { 93 private void deleteCFGNodes() {
94 for (Node node : graph.getNodes()) { 94 for (Node node : graph.getNodes()) {
95 if (node != Node.Null && !alive.isMarked(node) && Schedule.isCFG(node)) { 95 if (node != Node.Null && !worklist.isMarked(node) && isCFG(node)) {
96 node.delete(); 96 node.delete();
97 deletedNodeCount++; 97 deletedNodeCount++;
98 } 98 }
99 } 99 }
100 } 100 }
101 101
102 private void iterateInputs() { 102 private void iterateInputs() {
103 for (Node node : graph.getNodes()) { 103 for (Node node : graph.getNodes()) {
104 if (node != Node.Null && alive.isMarked(node)) { 104 if (node != Node.Null && worklist.isMarked(node)) {
105 for (Node input : node.inputs()) { 105 for (Node input : node.inputs()) {
106 addToWorklist(input); 106 worklist.add(input);
107 } 107 }
108 } 108 }
109 } 109 }
110 Node current; 110 for (Node current : worklist) {
111 while ((current = nextNode()) != null) {
112 for (Node input : current.inputs()) { 111 for (Node input : current.inputs()) {
113 addToWorklist(input); 112 worklist.add(input);
114 } 113 }
115 } 114 }
116 } 115 }
117 116
118 private void disconnectNonCFGNodes() { 117 private void disconnectNonCFGNodes() {
119 for (Node node : graph.getNodes()) { 118 for (Node node : graph.getNodes()) {
120 if (node != Node.Null && !alive.isMarked(node) && !Schedule.isCFG(node)) { 119 if (node != Node.Null && !worklist.isMarked(node) && !isCFG(node)) {
121 node.inputs().clearAll(); 120 node.inputs().clearAll();
122 } 121 }
123 } 122 }
124 } 123 }
125 124
126 private void deleteNonCFGNodes() { 125 private void deleteNonCFGNodes() {
127 for (Node node : graph.getNodes()) { 126 for (Node node : graph.getNodes()) {
128 if (node != Node.Null && !alive.isMarked(node) && !Schedule.isCFG(node)) { 127 if (node != Node.Null && !worklist.isMarked(node) && !isCFG(node)) {
129 node.delete(); 128 node.delete();
130 deletedNodeCount++; 129 deletedNodeCount++;
131 } 130 }
132 } 131 }
133 } 132 }
134
135 private Node nextNode() {
136 return worklist.poll();
137 }
138
139 private void addToWorklist(Node node) {
140 if (node != null && !alive.isMarked(node)) {
141 alive.mark(node);
142 worklist.add(node);
143 }
144 }
145 } 133 }