1 cananian 1.1.2.1 /*
2 cananian 1.1.2.1 * RegAlloc/Liveness.java
3 cananian 1.1.2.1 * examine flow graph to determine liveness of temporaries.
4 cananian 1.1.2.1 *
5 cananian 1.1.2.1 * ALGORITHM: Worklist-based algorithm utilizing node pre-sorting
6 cananian 1.1.2.1 * with a DFS for speed.
7 cananian 1.1.2.1 *
8 cananian 1.1.2.1 * C. Scott Ananian, cananian@princeton.edu, COS320
9 cananian 1.1.2.1 */
10 cananian 1.1.2.1
11 cananian 1.1.2.2 package harpoon.Backend.CSAHack.RegAlloc;
12 cananian 1.1.2.1
13 cananian 1.1.2.2 import harpoon.Temp.Temp;
14 cananian 1.1.2.2 import harpoon.Temp.TempList;
15 cananian 1.1.2.1
16 cananian 1.1.2.2 import harpoon.Backend.CSAHack.Graph.Node;
17 cananian 1.1.2.2 import harpoon.Backend.CSAHack.Graph.NodeList;
18 cananian 1.1.2.2 import harpoon.Backend.CSAHack.FlowGraph.FlowGraph;
19 cananian 1.1.2.2
20 cananian 1.1.2.5 import harpoon.Util.Collections.WorkSet;
21 cananian 1.1.2.1
22 cananian 1.1.2.1 import java.util.Vector;
23 cananian 1.1.2.1 import java.util.Hashtable;
24 cananian 1.1.2.1 import java.util.Enumeration;
25 cananian 1.1.2.1
26 cananian 1.1.2.1 /**
27 cananian 1.1.2.1 * An interference graph by examination of liveness of nodes
28 cananian 1.1.2.1 * in a flow graph.
29 cananian 1.1.2.1 * @version 1.00, 25 Nov 1996
30 cananian 1.1.2.1 * @author C. Scott Ananian
31 cananian 1.1.2.1 */
32 cananian 1.1.2.1 public class Liveness extends InterferenceGraph {
33 cananian 1.1.2.1 Hashtable temp2node = new Hashtable();
34 cananian 1.1.2.1 Hashtable nodeuses = new Hashtable();
35 cananian 1.1.2.1
36 cananian 1.1.2.1 MoveList movelist = null;
37 cananian 1.1.2.1
38 cananian 1.1.2.1 boolean debug = false; // set to true to dump debug information.
39 cananian 1.1.2.1
40 cananian 1.1.2.1 /**
41 cananian 1.1.2.1 * Construct interference graph from flow graph.
42 cananian 1.1.2.1 */
43 cananian 1.1.2.1 public Liveness(FlowGraph flow) {
44 cananian 1.1.2.1
45 cananian 1.1.2.2 WorkSet worklist = new WorkSet();
46 cananian 1.1.2.4 DFS(flow.nodes().head, worklist); // add some nodes to worklist.
47 cananian 1.1.2.1
48 cananian 1.1.2.1 // create table of TempSets to represent liveIn and liveOut
49 cananian 1.1.2.1 Hashtable liveIn = new Hashtable();
50 cananian 1.1.2.1 Hashtable liveOut= new Hashtable();
51 cananian 1.1.2.1 for (NodeList nl=flow.nodes(); nl!=null; nl=nl.tail) {
52 cananian 1.1.2.1 liveIn.put(nl.head, new TempSet());
53 cananian 1.1.2.1 liveOut.put(nl.head,new TempSet());
54 cananian 1.1.2.1 }
55 cananian 1.1.2.1
56 cananian 1.1.2.1 // Worklist algorithm for computing liveness.
57 cananian 1.1.2.1 while(!worklist.isEmpty()) {
58 cananian 1.1.2.2 Node n = (Node) worklist.pop();
59 cananian 1.1.2.1
60 cananian 1.1.2.1 TempSet out= (TempSet) liveOut.get(n);
61 cananian 1.1.2.1 TempSet in = (TempSet) liveIn.get(n);
62 cananian 1.1.2.1
63 cananian 1.1.2.1 in.resetChange();
64 cananian 1.1.2.1
65 cananian 1.1.2.1 // compute new out set...
66 cananian 1.1.2.1 for (NodeList nl = n.succ(); nl!=null; nl=nl.tail)
67 cananian 1.1.2.1 out.union((TempSet)liveIn.get(nl.head));
68 cananian 1.1.2.1
69 cananian 1.1.2.1 // compute the new in set (in = in union (out - def)
70 cananian 1.1.2.1 TempSet t = new TempSet();
71 cananian 1.1.2.1 t.union(out);
72 cananian 1.1.2.1 t.not(flow.def(n));
73 cananian 1.1.2.1
74 cananian 1.1.2.1 in.union(flow.use(n));
75 cananian 1.1.2.1 in.union(t);
76 cananian 1.1.2.1
77 cananian 1.1.2.1 // if new in set included more members than the old...
78 cananian 1.1.2.1 if (in.hasChanged()) {
79 cananian 1.1.2.1 // add all the predecessors of this node to the worklist.
80 cananian 1.1.2.1 for (NodeList nl = n.pred(); nl!=null; nl=nl.tail)
81 cananian 1.1.2.2 worklist.add(nl.head);
82 cananian 1.1.2.1 }
83 cananian 1.1.2.1 }
84 cananian 1.1.2.1 // done!
85 cananian 1.1.2.1
86 cananian 1.1.2.1 // show me the liveOut sets.
87 cananian 1.1.2.1 if (debug)
88 cananian 1.1.2.1 show_liveOut(flow, liveOut);
89 cananian 1.1.2.1
90 cananian 1.1.2.1 // Make interference graph.
91 cananian 1.1.2.1 createGraph(flow, liveIn, liveOut);
92 cananian 1.1.2.1
93 cananian 1.1.2.1 // assemble movelist.
94 cananian 1.1.2.1 makeMoveList(flow);
95 cananian 1.1.2.1
96 cananian 1.1.2.1 // show(System.out);
97 cananian 1.1.2.1 }
98 cananian 1.1.2.1
99 cananian 1.1.2.1 // dump the live-out sets for debugging.
100 cananian 1.1.2.1 private void show_liveOut(FlowGraph flow, Hashtable liveOut) {
101 cananian 1.1.2.1 for(NodeList nl=flow.nodes(); nl!=null; nl=nl.tail) {
102 cananian 1.1.2.1 System.out.println(nl.head.toString()+":");
103 cananian 1.1.2.1 for (TempList tl=((TempSet)liveOut.get(nl.head)).members();
104 cananian 1.1.2.1 tl!=null; tl=tl.tail)
105 cananian 1.1.2.1 System.out.print(" "+tl.head.toString());
106 cananian 1.1.2.1 System.out.print("\n");
107 cananian 1.1.2.1 }
108 cananian 1.1.2.1 }
109 cananian 1.1.2.1
110 cananian 1.1.2.1 // examine nodes to create move list
111 cananian 1.1.2.1 private void makeMoveList(FlowGraph flow) {
112 cananian 1.1.2.1 for (NodeList nl = flow.nodes(); nl!=null; nl=nl.tail)
113 cananian 1.1.2.1 if (flow.isMove(nl.head))
114 cananian 1.1.2.1 movelist = new MoveList(tnode(flow.use(nl.head).head),
115 cananian 1.1.2.1 tnode(flow.def(nl.head).head),
116 cananian 1.1.2.1 movelist);
117 cananian 1.1.2.1 }
118 cananian 1.1.2.2
119 cananian 1.1.2.2 // add all nodes in (reverse) DFS order.
120 cananian 1.1.2.4 private void DFS(Node n, WorkSet worklist) {
121 cananian 1.1.2.4 WorkSet stack = new WorkSet();
122 cananian 1.1.2.4 stack.add(n);
123 cananian 1.1.2.4 while (!stack.isEmpty()) {
124 cananian 1.1.2.4 Node nn = (Node) stack.pop();
125 cananian 1.1.2.4 worklist.add(nn);
126 cananian 1.1.2.4 for (NodeList nl=nn.succ(); nl!=null; nl=nl.tail)
127 cananian 1.1.2.4 if (!worklist.contains(nl.head))
128 cananian 1.1.2.4 stack.add(nl.head);
129 cananian 1.1.2.1 }
130 cananian 1.1.2.1 }
131 cananian 1.1.2.1
132 cananian 1.1.2.1 // Create nodes and edges of interference graph from the liveness
133 cananian 1.1.2.1 // information.
134 cananian 1.1.2.1 private void createGraph(FlowGraph flow,
135 cananian 1.1.2.1 Hashtable liveIn, Hashtable liveOut) {
136 cananian 1.1.2.1 // for each node in the flow graph
137 cananian 1.1.2.1 for (NodeList nl = flow.nodes(); nl!=null; nl=nl.tail)
138 cananian 1.1.2.1 // for each definition in that node
139 cananian 1.1.2.1 for (TempList dl = flow.def(nl.head); dl!=null; dl=dl.tail)
140 cananian 1.1.2.1 // for each live temporary at that node
141 cananian 1.1.2.1 for (TempList tl = ((TempSet)liveOut.get(nl.head)).members();
142 cananian 1.1.2.1 tl!=null; tl=tl.tail)
143 cananian 1.1.2.1 // add interference edges, conditionally
144 cananian 1.1.2.1 addSomeEdges(flow, nl.head, dl.head, tl.head);
145 cananian 1.1.2.1
146 cananian 1.1.2.1 //-------------------------------------------------------
147 cananian 1.1.2.1
148 cananian 1.1.2.1 // Now count defs and uses of each variable, to aid in the
149 cananian 1.1.2.1 // later computation of spillCost()
150 cananian 1.1.2.1
151 cananian 1.1.2.1 // for each node in the flow graph
152 cananian 1.1.2.1 for (NodeList nl = flow.nodes(); nl!=null; nl=nl.tail) {
153 cananian 1.1.2.1 // for each definition in that node
154 cananian 1.1.2.1 for (TempList dl = flow.def(nl.head); dl!=null; dl=dl.tail) {
155 cananian 1.1.2.1 // increment the nodeuse
156 cananian 1.1.2.1 Node defnode = tnode(dl.head);
157 cananian 1.1.2.1 Integer n = (Integer) nodeuses.get(defnode);
158 cananian 1.1.2.1 if (n==null) n=new Integer(0);
159 cananian 1.1.2.1 nodeuses.put(defnode, new Integer(n.intValue()+1));
160 cananian 1.1.2.1 }
161 cananian 1.1.2.1 // for each use in that node
162 cananian 1.1.2.1 for (TempList dl = flow.use(nl.head); dl!=null; dl=dl.tail) {
163 cananian 1.1.2.1 // increment the nodeuse
164 cananian 1.1.2.1 Node usenode = tnode(dl.head);
165 cananian 1.1.2.1 Integer n = (Integer) nodeuses.get(usenode);
166 cananian 1.1.2.1 if (n==null) n=new Integer(0);
167 cananian 1.1.2.1 nodeuses.put(usenode, new Integer(n.intValue()+1));
168 cananian 1.1.2.1 }
169 cananian 1.1.2.1 }
170 cananian 1.1.2.1 }
171 cananian 1.1.2.1 private void addSomeEdges(FlowGraph flow, Node flownode,
172 cananian 1.1.2.1 Temp deftemp, Temp livetemp) {
173 cananian 1.1.2.1 // if this is a move instruction, maybe we don't want to add this edge
174 cananian 1.1.2.1 if (flow.isMove(flownode))
175 cananian 1.1.2.1 // see if this livetemp is part of the source of this move
176 cananian 1.1.2.1 for (TempList sl = flow.use(flownode); sl!=null; sl=sl.tail)
177 cananian 1.1.2.1 // if so, don't add an edge
178 cananian 1.1.2.1 if (sl.head == livetemp)
179 cananian 1.1.2.1 return;
180 cananian 1.1.2.1
181 cananian 1.1.2.1 // tests okay, add the edge.
182 cananian 1.1.2.1 addEdge(tnode(deftemp), tnode(livetemp));
183 cananian 1.1.2.1 addEdge(tnode(livetemp),tnode(deftemp));
184 cananian 1.1.2.1 }
185 cananian 1.1.2.1
186 cananian 1.1.2.1 /**
187 cananian 1.1.2.1 * @param temp a temporary used in the flow graph
188 cananian 1.1.2.1 * @return the interference graph node corresponding to the temporary.
189 cananian 1.1.2.1 */
190 cananian 1.1.2.1 public Node tnode(Temp temp) {
191 cananian 1.1.2.1 Node n = (Node) temp2node.get(temp);
192 cananian 1.1.2.1 if (n==null)
193 cananian 1.1.2.1 // make new nodes on demand.
194 cananian 1.1.2.1 return newNode(temp);
195 cananian 1.1.2.1 else return n;
196 cananian 1.1.2.1 }
197 cananian 1.1.2.1 /**
198 cananian 1.1.2.1 * @param node a node in the interference graph.
199 cananian 1.1.2.1 * @return the temporary corresponding to the node.
200 cananian 1.1.2.1 */
201 cananian 1.1.2.1 public Temp gtemp(Node node) {
202 cananian 1.1.2.1 if (!(node instanceof TempNode))
203 cananian 1.1.2.1 throw new Error("Node "+node.toString()+" not a member of graph.");
204 cananian 1.1.2.1 else return ((TempNode)node).temp;
205 cananian 1.1.2.1 }
206 cananian 1.1.2.1 /**
207 cananian 1.1.2.1 * @param node a node in the interference graph.
208 cananian 1.1.2.1 * @return an estimate of the cost of spilling this node.
209 cananian 1.1.2.1 */
210 cananian 1.1.2.1 public int spillCost(Node node) {
211 cananian 1.1.2.1 // Our heuristic: the number of uses and defs of this node, divided by
212 cananian 1.1.2.1 // degree (to make more conflicted nodes better to spill).
213 cananian 1.1.2.1 // Scaled by 1000 to accomodate integer division.
214 cananian 1.1.2.1 Integer numuses = (Integer) nodeuses.get(node);
215 cananian 1.1.2.1 return 1000*numuses.intValue()/node.degree();
216 cananian 1.1.2.1 }
217 cananian 1.1.2.1 /**
218 cananian 1.1.2.1 * @return a list of moves found in the flow graph.
219 cananian 1.1.2.1 */
220 cananian 1.1.2.1 public MoveList moves() {
221 cananian 1.1.2.1 return movelist;
222 cananian 1.1.2.1 }
223 cananian 1.1.2.1 public Node newNode(Temp t) {
224 cananian 1.1.2.1 TempNode n = new TempNode(this, t);
225 cananian 1.1.2.1 temp2node.put(t, n);
226 cananian 1.1.2.1 return n;
227 cananian 1.1.2.1 }
228 cananian 1.1.2.1 }
229 cananian 1.1.2.1
230 cananian 1.1.2.1 /**
231 cananian 1.1.2.1 * Sub-class to associate a temporary with a Graph.Node.
232 cananian 1.1.2.2 * @see harpoon.Temp.Temp
233 cananian 1.1.2.1 */
234 cananian 1.1.2.2 class TempNode extends harpoon.Backend.CSAHack.Graph.Node {
235 cananian 1.1.2.1 Temp temp;
236 cananian 1.1.2.2 TempNode(harpoon.Backend.CSAHack.Graph.Graph g, Temp t) {
237 cananian 1.1.2.1 super(g);
238 cananian 1.1.2.1 temp = t;
239 cananian 1.1.2.1 }
240 cananian 1.1.2.1 public String toString() {
241 cananian 1.1.2.1 return temp.toString(); // +"("+super.toString()+")";
242 cananian 1.1.2.1 }
243 cananian 1.1.2.3 public int hashCode() { return temp.hashCode(); }
244 cananian 1.1.2.1 }
245 cananian 1.1.2.1
246 cananian 1.1.2.1 /**
247 cananian 1.1.2.1 * A set of temporaries, based on a hashtable.
248 cananian 1.1.2.1 */
249 cananian 1.1.2.1 class TempSet {
250 cananian 1.1.2.1 boolean dirty = false;
251 cananian 1.1.2.1 Hashtable h = new Hashtable();
252 cananian 1.1.2.1
253 cananian 1.1.2.1 /**
254 cananian 1.1.2.1 * create a new empty set.
255 cananian 1.1.2.1 */
256 cananian 1.1.2.1 TempSet() { }
257 cananian 1.1.2.1 /**
258 cananian 1.1.2.1 * create a new set.
259 cananian 1.1.2.1 * @param tl a list of initial members of the set.
260 cananian 1.1.2.1 */
261 cananian 1.1.2.1 TempSet(TempList tl) { union(tl); }
262 cananian 1.1.2.1
263 cananian 1.1.2.1 /**
264 cananian 1.1.2.1 * add a member to the set, if not previously present.
265 cananian 1.1.2.1 * @param t a temporary to add to the set.
266 cananian 1.1.2.1 */
267 cananian 1.1.2.1 void add(Temp t) {
268 cananian 1.1.2.1 if (!contains(t)) {
269 cananian 1.1.2.1 h.put(t, new Object());
270 cananian 1.1.2.1 dirty=true;
271 cananian 1.1.2.1 }
272 cananian 1.1.2.1 }
273 cananian 1.1.2.1 /**
274 cananian 1.1.2.1 * remove an element, if it is a member of the set.
275 cananian 1.1.2.1 * @param t a temporary to be removed from the set.
276 cananian 1.1.2.1 */
277 cananian 1.1.2.1 void remove(Temp t) {
278 cananian 1.1.2.1 if (contains(t)) {
279 cananian 1.1.2.1 h.remove(t);
280 cananian 1.1.2.1 dirty=true;
281 cananian 1.1.2.1 }
282 cananian 1.1.2.1 }
283 cananian 1.1.2.1 /**
284 cananian 1.1.2.1 * add to this set all the members of another.
285 cananian 1.1.2.1 */
286 cananian 1.1.2.1 void union(TempSet ts) { union(ts.members()); }
287 cananian 1.1.2.1 /**
288 cananian 1.1.2.1 * add a list of temporaries to this set.
289 cananian 1.1.2.1 */
290 cananian 1.1.2.1 void union(TempList tl) {
291 cananian 1.1.2.1 for ( ; tl!=null; tl=tl.tail)
292 cananian 1.1.2.1 add(tl.head);
293 cananian 1.1.2.1 }
294 cananian 1.1.2.1 /**
295 cananian 1.1.2.1 * remove from this set all the members of another.
296 cananian 1.1.2.1 */
297 cananian 1.1.2.1 void not(TempSet ts) { not(ts.members()); }
298 cananian 1.1.2.1 /**
299 cananian 1.1.2.1 * remove a list of temporaries from this set.
300 cananian 1.1.2.1 */
301 cananian 1.1.2.1 void not(TempList tl) {
302 cananian 1.1.2.1 for ( ; tl!=null; tl=tl.tail)
303 cananian 1.1.2.1 remove(tl.head);
304 cananian 1.1.2.1 }
305 cananian 1.1.2.1 /**
306 cananian 1.1.2.1 * Create a list of the members of this set.
307 cananian 1.1.2.1 */
308 cananian 1.1.2.1 TempList members() {
309 cananian 1.1.2.1 TempList m = null;
310 cananian 1.1.2.1 Enumeration e=h.keys();
311 cananian 1.1.2.1 while( e.hasMoreElements() )
312 cananian 1.1.2.1 m = new TempList((Temp)e.nextElement(), m);
313 cananian 1.1.2.1 return m;
314 cananian 1.1.2.1 }
315 cananian 1.1.2.1 /**
316 cananian 1.1.2.1 * @param t a temporary
317 cananian 1.1.2.1 * @return true if t is a member of the set.
318 cananian 1.1.2.1 */
319 cananian 1.1.2.1 boolean contains(Temp t) {
320 cananian 1.1.2.1 return h.get(t)!=null;
321 cananian 1.1.2.1 }
322 cananian 1.1.2.1 void resetChange() { dirty = false; }
323 cananian 1.1.2.1 /**
324 cananian 1.1.2.1 * @return true if members have been added or removed since the last call to resetChange(); false otherwise.
325 cananian 1.1.2.1 */
326 cananian 1.1.2.1 boolean hasChanged() { return dirty; }
327 cananian 1.1.2.1 }
328 cananian 1.2