1 cananian 1.1.2.1 /*
2 cananian 1.1.2.1 * RegAlloc/Color.java
3 cananian 1.1.2.1 * graph coloring algorithm for register allocation.
4 cananian 1.1.2.1 *
5 cananian 1.1.2.1 * ALGORITHM: Worklist-based algorithm described in
6 cananian 1.1.2.1 * 'Modern Compiler Implementation in Java'
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.Backend.CSAHack.Graph.Node;
14 cananian 1.1.2.2 import harpoon.Backend.CSAHack.Graph.NodeList;
15 cananian 1.1.2.1
16 cananian 1.1.2.3 import harpoon.Backend.CSAHack.RegAlloc.RegWork.Moves;
17 cananian 1.1.2.3 import harpoon.Backend.CSAHack.RegAlloc.RegWork.NodeSet;
18 cananian 1.1.2.3
19 cananian 1.1.2.2 import harpoon.Temp.Temp;
20 cananian 1.1.2.2 import harpoon.Temp.TempList;
21 cananian 1.1.2.2 import harpoon.Temp.TempMap;
22 cananian 1.1.2.1
23 cananian 1.1.2.2 import harpoon.Backend.CSAHack.FlowGraph.FlowGraph;
24 cananian 1.1.2.5 import harpoon.Util.Util;
25 cananian 1.1.2.1
26 cananian 1.1.2.1 import java.util.Vector;
27 cananian 1.1.2.1 import java.util.Hashtable;
28 cananian 1.1.2.1
29 cananian 1.1.2.1 /**
30 cananian 1.1.2.1 * Graph coloring algorithm for register allocation.
31 cananian 1.1.2.1 * @version 1.00, 25 Nov 1996
32 cananian 1.1.2.1 * @author C. Scott Ananian
33 cananian 1.1.2.1 * @see RegAlloc.RegAlloc
34 cananian 1.1.2.1 */
35 cananian 1.1.2.2 class Color implements TempMap {
36 cananian 1.1.2.1 FlowGraph flow;
37 cananian 1.1.2.1 InterferenceGraph ig;
38 cananian 1.1.2.1 TempList registers;
39 cananian 1.1.2.1 TempMap initial;
40 cananian 1.1.2.1 Vector reg = new Vector(); // vector of register temps
41 cananian 1.1.2.1 int K; // number of registers
42 cananian 1.1.2.1
43 cananian 1.1.2.1 boolean debug = false; // en-/dis- able debugging information.
44 cananian 1.1.2.1
45 cananian 1.1.2.1 /**
46 cananian 1.1.2.1 * @return TempList of spilled registers
47 cananian 1.1.2.1 */
48 cananian 1.1.2.1 public TempList spills() {
49 cananian 1.1.2.1 TempList r = null;
50 cananian 1.1.2.1 for (NodeList nl = sets.spilled.nodes(); nl!=null; nl=nl.tail)
51 cananian 1.1.2.1 r = new TempList(ig.gtemp(nl.head), r);
52 cananian 1.1.2.1 return r;
53 cananian 1.1.2.1 }
54 cananian 1.1.2.1
55 cananian 1.1.2.1 /**
56 cananian 1.1.2.1 * Color an interference graph.
57 cananian 1.1.2.1 * @param flow flow graph defining moves able to be coalesced
58 cananian 1.1.2.1 * @param ig interference graph for the temporaries
59 cananian 1.1.2.1 * @param initial Initial coloring of machine registers
60 cananian 1.1.2.1 * @param registers List of pre-colored machine registers.
61 cananian 1.1.2.1 */
62 cananian 1.1.2.1 public Color(FlowGraph flow,
63 cananian 1.1.2.1 InterferenceGraph ig,
64 cananian 1.1.2.1 TempMap initial,
65 cananian 1.1.2.1 TempList registers) {
66 cananian 1.1.2.1 this.flow = flow;
67 cananian 1.1.2.1 this.ig = ig;
68 cananian 1.1.2.1 this.registers = registers;
69 cananian 1.1.2.1 this.initial = initial;
70 cananian 1.1.2.1 // Set K to the number of registers
71 cananian 1.1.2.2 for (TempList tl = registers; tl!=null; tl=tl.tail)
72 cananian 1.1.2.1 reg.addElement(tl.head);
73 cananian 1.1.2.1 K = reg.size();
74 cananian 1.1.2.1
75 cananian 1.1.2.1 main();
76 cananian 1.1.2.1 }
77 cananian 1.1.2.1
78 cananian 1.1.2.1 private void main() {
79 cananian 1.1.2.1 Build();
80 cananian 1.1.2.1 check();
81 cananian 1.1.2.1 MakeWorklist();
82 cananian 1.1.2.1 check();
83 cananian 1.1.2.1
84 cananian 1.1.2.1 do {
85 cananian 1.1.2.1 if (!sets.worklist.simplify.empty()) {Simplify();check();}
86 cananian 1.1.2.1 else if (!moves.worklist.empty()) {Coalesce();check();}
87 cananian 1.1.2.1 else if (!sets.worklist.freeze.empty()) {Freeze(); check();}
88 cananian 1.1.2.1 else if (!sets.worklist.spill.empty()) {SelectSpill();check();}
89 cananian 1.1.2.1 } while (!(sets.worklist.simplify.empty() &&
90 cananian 1.1.2.1 sets.worklist.freeze.empty() &&
91 cananian 1.1.2.1 sets.worklist.spill.empty() &&
92 cananian 1.1.2.1 moves.worklist.empty()));
93 cananian 1.1.2.1
94 cananian 1.1.2.1 check();
95 cananian 1.1.2.1 AssignColors();
96 cananian 1.1.2.1
97 cananian 1.1.2.1 }
98 cananian 1.1.2.1
99 cananian 1.1.2.1 private Moves moves;
100 cananian 1.1.2.1 private NodeSet sets;
101 cananian 1.1.2.1
102 cananian 1.1.2.1 private Hashtable moveList, degree;
103 cananian 1.1.2.1 private Hashtable alias, color;
104 cananian 1.1.2.1
105 cananian 1.1.2.1 void Build() {
106 cananian 1.1.2.1 alias = new Hashtable();
107 cananian 1.1.2.1 sets = new NodeSet(registers, ig);
108 cananian 1.1.2.1 moves = new Moves(flow);
109 cananian 1.1.2.1
110 cananian 1.1.2.1 // Create mapping of interference graph node to the move instruction
111 cananian 1.1.2.1 // nodes it is associated with.
112 cananian 1.1.2.1 moveList = new Hashtable();
113 cananian 1.1.2.1 for (NodeList nl = flow.nodes(); nl!=null; nl=nl.tail) {
114 cananian 1.1.2.1 if (flow.isMove(nl.head)) {
115 cananian 1.1.2.2 for (TempList tl = merge(flow.use(nl.head),flow.def(nl.head));
116 cananian 1.1.2.1 tl!=null; tl=tl.tail) {
117 cananian 1.1.2.2 Node tempnode = ig.tnode(tl.head);
118 cananian 1.1.2.1 // quick error check hack
119 cananian 1.1.2.1 if (tempnode == null) // this should never happen!
120 cananian 1.1.2.1 throw new Error("Interference graph doesn't contain a node "+
121 cananian 1.1.2.1 "for temporary "+tl.head.toString()+", which "+
122 cananian 1.1.2.1 "is use/def in node "+nl.head.toString());
123 cananian 1.1.2.1 moveList.put(tempnode,
124 cananian 1.1.2.1 new NodeList(nl.head,
125 cananian 1.1.2.1 (NodeList) moveList.get(tempnode)));
126 cananian 1.1.2.1 }
127 cananian 1.1.2.1 }
128 cananian 1.1.2.1 }
129 cananian 1.1.2.1 // Initialize degree with computed degree of each node.
130 cananian 1.1.2.1 degree = new Hashtable();
131 cananian 1.1.2.1 for (NodeList nl = ig.nodes(); nl!=null; nl=nl.tail)
132 cananian 1.1.2.1 degree.put(nl.head, new Integer(
133 cananian 1.1.2.1 len(union(nl.head.succ(), nl.head.pred()))));
134 cananian 1.1.2.1 }
135 cananian 1.1.2.1 void MakeWorklist() {
136 cananian 1.1.2.1 while (!sets.initial.empty()) {
137 cananian 1.1.2.1 Node n = sets.initial.head();
138 cananian 1.1.2.1 sets.initial.remove(n);
139 cananian 1.1.2.1
140 cananian 1.1.2.1 if(Degree(n) >= K)
141 cananian 1.1.2.1 sets.worklist.spill.add(n);
142 cananian 1.1.2.1 else if (MoveRelated(n))
143 cananian 1.1.2.1 sets.worklist.freeze.add(n);
144 cananian 1.1.2.1 else
145 cananian 1.1.2.1 sets.worklist.simplify.add(n);
146 cananian 1.1.2.1 }
147 cananian 1.1.2.1 }
148 cananian 1.1.2.1 void Simplify() {
149 cananian 1.1.2.1 Node n = sets.worklist.simplify.head();
150 cananian 1.1.2.1 sets.worklist.simplify.remove(n);
151 cananian 1.1.2.1 sets.selectStack.push(n);
152 cananian 1.1.2.1 for (NodeList nl=Adjacent(n); nl!=null; nl=nl.tail)
153 cananian 1.1.2.7 if (!sets.precolored.contains(nl.head))
154 cananian 1.1.2.7 DecrementDegree(nl.head);
155 cananian 1.1.2.1 }
156 cananian 1.1.2.1 void Coalesce() {
157 cananian 1.1.2.1 Node m = moves.worklist.head();
158 cananian 1.1.2.1
159 cananian 1.1.2.1 if (!flow.isMove(m)) throw new Error("Internal error");
160 cananian 1.1.2.1 TempList use = flow.use(m);
161 cananian 1.1.2.1 TempList def = flow.def(m);
162 cananian 1.1.2.10 if (/*use.tail != null ||*/ def.tail != null)//derived use implies base use
163 cananian 1.1.2.4 throw new Error("Node supposed to be a MOVE: "+m);
164 cananian 1.1.2.1
165 cananian 1.1.2.1 Node x = GetAlias(ig.tnode(def.head));
166 cananian 1.1.2.1 Node y = GetAlias(ig.tnode(use.head));
167 cananian 1.1.2.1 Node u=x,v=y;
168 cananian 1.1.2.1 if (sets.precolored.contains(y)) {
169 cananian 1.1.2.1 u=y; v=x;
170 cananian 1.1.2.1 }
171 cananian 1.1.2.1 moves.worklist.remove(m);
172 cananian 1.1.2.1 if (u==v) {
173 cananian 1.1.2.1 // Coalesce u and v
174 cananian 1.1.2.1 moves.coalesced.add(m);
175 cananian 1.1.2.1 AddWorkList(u);
176 cananian 1.1.2.1 } else if (sets.precolored.contains(v) || u.adj(v)) {
177 cananian 1.1.2.1 // Constrain u
178 cananian 1.1.2.1 moves.constrained.add(m);
179 cananian 1.1.2.1 AddWorkList(u);
180 cananian 1.1.2.1 AddWorkList(v);
181 cananian 1.1.2.1 } else if ((sets.precolored.contains(u) && OK(Adjacent(v),u)) ||
182 cananian 1.1.2.1 ((!sets.precolored.contains(u)) &&
183 cananian 1.1.2.1 Conservative(merge(Adjacent(u), Adjacent(v))))) {
184 cananian 1.1.2.1 // Combine u and v
185 cananian 1.1.2.1 moves.coalesced.add(m);
186 cananian 1.1.2.1 Combine(u,v);
187 cananian 1.1.2.1 AddWorkList(u);
188 cananian 1.1.2.1 } else
189 cananian 1.1.2.1 moves.active.add(m);
190 cananian 1.1.2.1 }
191 cananian 1.1.2.1 void Freeze() {
192 cananian 1.1.2.1 Node u = sets.worklist.freeze.head();
193 cananian 1.1.2.1 sets.worklist.freeze.remove(u);
194 cananian 1.1.2.1 sets.worklist.simplify.add(u);
195 cananian 1.1.2.1 FreezeMoves(u);
196 cananian 1.1.2.1 }
197 cananian 1.1.2.5 void FreezeMoves(Node u) {
198 cananian 1.1.2.5 for (NodeList m = NodeMoves(u); m!=null; m=m.tail) {
199 cananian 1.3.2.1 assert moves.active.contains(m.head);
200 cananian 1.1.2.5 moves.active.remove(m.head);
201 cananian 1.1.2.1 moves.frozen.add(m.head);
202 cananian 1.1.2.1
203 cananian 1.1.2.1 if (!flow.isMove(m.head)) throw new Error("Internal error");
204 cananian 1.1.2.1 TempList use = flow.use(m.head);
205 cananian 1.1.2.1 TempList def = flow.def(m.head);
206 cananian 1.1.2.10 if (/*use.tail != null ||*/ def.tail != null)//derived use implies base use
207 cananian 1.1.2.1 throw new Error("Node supposed to be a MOVE");
208 cananian 1.1.2.1
209 cananian 1.1.2.5 Temp x = def.head, y = use.head;
210 cananian 1.1.2.5 Node v;
211 cananian 1.1.2.5 if (GetAlias(ig.tnode(y))==GetAlias(u))
212 cananian 1.1.2.5 v = GetAlias(ig.tnode(x));
213 cananian 1.1.2.5 else
214 cananian 1.1.2.5 v = GetAlias(ig.tnode(y));
215 cananian 1.1.2.5
216 cananian 1.1.2.7 /** Degree(v) should be >> K for precolored nodes, but we don't
217 cananian 1.1.2.7 * actually keep the adjacency info for precolored nodes around,
218 cananian 1.1.2.7 * so opt out of the test instead. [CSA] */
219 cananian 1.1.2.9 if (!sets.precolored.contains(v) &&
220 cananian 1.1.2.9 (NodeMoves(v)==null) && (Degree(v) < K) ) {
221 cananian 1.3.2.1 assert sets.worklist.freeze.contains(v);
222 cananian 1.1.2.1 sets.worklist.freeze.remove(v);
223 cananian 1.1.2.1 sets.worklist.simplify.add(v);
224 cananian 1.1.2.1 }
225 cananian 1.1.2.1 }
226 cananian 1.1.2.1 }
227 cananian 1.1.2.1 void SelectSpill() {
228 cananian 1.1.2.1 Node bestspill = sets.worklist.spill.head();
229 cananian 1.1.2.1 int bestscore = ig.spillCost(bestspill);
230 cananian 1.1.2.1 for (NodeList nl = sets.worklist.spill.nodes(); nl!=null; nl=nl.tail) {
231 cananian 1.1.2.1 int nodescore = ig.spillCost(nl.head);
232 cananian 1.1.2.1 // bestscore is lowest spillCost
233 cananian 1.1.2.1 if (nodescore < bestscore) {
234 cananian 1.1.2.1 bestspill = nl.head;
235 cananian 1.1.2.1 bestscore = nodescore;
236 cananian 1.1.2.1 }
237 cananian 1.1.2.1 }
238 cananian 1.1.2.1 // OK, spill this guy.
239 cananian 1.1.2.1 //System.out.println("Spilling "+ig.gtemp(bestspill).toString());
240 cananian 1.1.2.1 sets.worklist.spill.remove(bestspill);
241 cananian 1.1.2.1 sets.worklist.simplify.add(bestspill);
242 cananian 1.1.2.1 FreezeMoves(bestspill);
243 cananian 1.1.2.1 }
244 cananian 1.1.2.1 void AssignColors() {
245 cananian 1.1.2.1 color = new Hashtable();
246 cananian 1.1.2.1
247 cananian 1.1.2.7 /* Color precolored nodes. */
248 cananian 1.3.2.1 assert reg.size()==K;
249 cananian 1.1.2.7 for (int i=0; i<reg.size(); i++)
250 cananian 1.1.2.7 color.put(reg.elementAt(i), new Integer(i));
251 cananian 1.1.2.1
252 cananian 1.1.2.1 while(!sets.selectStack.empty()) {
253 cananian 1.1.2.1 Node n = (Node) sets.selectStack.pop();
254 cananian 1.1.2.8 int k;
255 cananian 1.1.2.7 // node should be previously uncolored.
256 cananian 1.3.2.1 assert !color.containsKey(ig.gtemp(n));
257 cananian 1.1.2.1 boolean okColors[] = new boolean[K];
258 cananian 1.1.2.1 for (k=0; k<K; k++)
259 cananian 1.1.2.1 okColors[k]=true;
260 cananian 1.1.2.1 for (NodeList nl = union(n.succ(),n.pred()); nl!=null; nl=nl.tail) {
261 cananian 1.1.2.1 Node w = GetAlias(nl.head);
262 cananian 1.1.2.1 if (sets.colored.contains(w) || sets.precolored.contains(w))
263 cananian 1.1.2.1 okColors[getColor(ig.gtemp(w))]=false;
264 cananian 1.1.2.1 }
265 cananian 1.1.2.1 for (k=0; k<K; k++)
266 cananian 1.1.2.1 if (okColors[k]) {
267 cananian 1.1.2.1 sets.colored.add(n);
268 cananian 1.1.2.1 color.put(ig.gtemp(n), new Integer(k));
269 cananian 1.1.2.1 break;
270 cananian 1.1.2.1 }
271 cananian 1.1.2.1 if (k==K) // no ok colors!
272 cananian 1.1.2.1 sets.spilled.add(n);
273 cananian 1.1.2.1 }
274 cananian 1.1.2.7 for (NodeList nl = sets.coalesced.nodes(); nl!=null; nl=nl.tail) {
275 cananian 1.1.2.7 // node should be previously uncolored.
276 cananian 1.3.2.1 assert !color.containsKey(ig.gtemp(nl.head));
277 cananian 1.1.2.1 color.put(ig.gtemp(nl.head),
278 cananian 1.1.2.1 new Integer(getColor(ig.gtemp(GetAlias(nl.head)))));
279 cananian 1.1.2.7 }
280 cananian 1.1.2.1 // for (java.util.Enumeration e=color.keys(); e.hasMoreElements(); ) {
281 cananian 1.1.2.1 // Temp t = (Temp) e.nextElement();
282 cananian 1.1.2.1 // System.out.println(t.toString()+" <= "+
283 cananian 1.1.2.1 // ((Temp)reg.elementAt(getColor(t))).toString());
284 cananian 1.1.2.1 // }
285 cananian 1.1.2.1 }
286 cananian 1.1.2.1 int getColor(Temp w) {
287 cananian 1.3.2.1 assert color.get(w)!=null : "No color for "+w;
288 cananian 1.1.2.1 return ((Integer)color.get(w)).intValue();
289 cananian 1.1.2.1 }
290 cananian 1.1.2.1
291 cananian 1.1.2.2 public Temp tempMap(Temp t) {
292 cananian 1.3.2.1 assert !reg.contains(t) || // registers should map to themselves
293 cananian 1.3.2.1 (reg.elementAt(getColor(t))==t);
294 cananian 1.1.2.1 return initial.tempMap((Temp)reg.elementAt(getColor(t)));
295 cananian 1.1.2.1 }
296 cananian 1.1.2.1
297 cananian 1.1.2.1 // Utility functions:
298 cananian 1.1.2.1 void AddEdge(Node u, Node v) {
299 cananian 1.1.2.1 if (!u.adj(v) && (u!=v)) {
300 cananian 1.1.2.1 ig.addEdge(u,v);
301 cananian 1.1.2.7 if (!sets.precolored.contains(u))
302 cananian 1.1.2.1 degree.put(u, new Integer(Degree(u)+1));
303 cananian 1.1.2.7 if (!sets.precolored.contains(v))
304 cananian 1.1.2.1 degree.put(v, new Integer(Degree(v)+1));
305 cananian 1.1.2.1 }
306 cananian 1.1.2.1 }
307 cananian 1.1.2.1
308 cananian 1.1.2.1 NodeList Adjacent(Node n) {
309 cananian 1.1.2.7 /* We don't maintain adjacency lists for precolored nodes */
310 cananian 1.3.2.1 assert !sets.precolored.contains(n);
311 cananian 1.1.2.1 NodeList r=null;
312 cananian 1.1.2.1 for (NodeList nl=union(n.succ(),n.pred()); nl!=null; nl=nl.tail)
313 cananian 1.1.2.1 if (!sets.coalesced.contains(nl.head) &&
314 cananian 1.1.2.1 !sets.selectStack.contains(nl.head))
315 cananian 1.1.2.1 r = new NodeList(nl.head, r);
316 cananian 1.1.2.1 return r;
317 cananian 1.1.2.1 }
318 cananian 1.1.2.1 void AddWorkList(Node u) {
319 cananian 1.1.2.1 if ((!sets.precolored.contains(u)) &&
320 cananian 1.1.2.1 (!MoveRelated(u)) &&
321 cananian 1.1.2.1 (Degree(u) < K)) {
322 cananian 1.1.2.1 sets.worklist.freeze.remove(u);
323 cananian 1.1.2.1 sets.worklist.simplify.add(u);
324 cananian 1.1.2.1 }
325 cananian 1.1.2.1 }
326 cananian 1.1.2.1 boolean OK(Node t, Node r) {
327 cananian 1.1.2.7 /* precolored nodes will always have degree >> K, but we don't
328 cananian 1.1.2.7 * actually maintain this info in the array. */
329 cananian 1.1.2.7 return (sets.precolored.contains(t) ||
330 cananian 1.1.2.7 (Degree(t) < K) ||
331 cananian 1.1.2.1 t.adj(r));
332 cananian 1.1.2.1 }
333 cananian 1.1.2.1 boolean OK(NodeList nl, Node r) {
334 cananian 1.1.2.1 for ( ; nl!=null; nl=nl.tail)
335 cananian 1.1.2.1 if (!OK(nl.head, r)) return false;
336 cananian 1.1.2.1 return true;
337 cananian 1.1.2.1 }
338 cananian 1.1.2.1 boolean Conservative(NodeList nl) {
339 cananian 1.1.2.1 int k = 0;
340 cananian 1.1.2.1 for ( ; nl!=null; nl=nl.tail)
341 cananian 1.1.2.7 /* precolored nodes will always have degree >> K, but we don't
342 cananian 1.1.2.7 * actually maintain this info in the array. */
343 cananian 1.1.2.7 if (sets.precolored.contains(nl.head) || Degree(nl.head) >= K)
344 cananian 1.1.2.1 k++;
345 cananian 1.1.2.1 return ( k < K );
346 cananian 1.1.2.1 }
347 cananian 1.1.2.1 Node GetAlias(Node n) {
348 cananian 1.1.2.1 if (sets.coalesced.contains(n))
349 cananian 1.1.2.1 return GetAlias((Node)alias.get(n));
350 cananian 1.1.2.1 else
351 cananian 1.1.2.1 return n;
352 cananian 1.1.2.1 }
353 cananian 1.1.2.1
354 cananian 1.1.2.1 void Combine(Node u, Node v) {
355 cananian 1.1.2.1 if (sets.worklist.freeze.contains(v))
356 cananian 1.1.2.1 sets.worklist.freeze.remove(v);
357 cananian 1.1.2.1 else
358 cananian 1.1.2.1 sets.worklist.spill.remove(v);
359 cananian 1.1.2.1
360 cananian 1.1.2.1 sets.coalesced.add(v);
361 cananian 1.1.2.1 alias.put(v, u);
362 cananian 1.1.2.1
363 cananian 1.1.2.1 moveList.put(u, merge((NodeList)moveList.get(u),
364 cananian 1.1.2.1 (NodeList)moveList.get(v)));
365 cananian 1.1.2.11 // quoting appel, pg 252: When v is coalesced into u, moves associated
366 cananian 1.1.2.11 // with v are added to the move work-list. this will catch other moves
367 cananian 1.1.2.11 // from u to v. [CSA BUGFIX, 31-Mar-2000]
368 cananian 1.1.2.11 EnableMoves(new NodeList(v, null));//BUGFIX.
369 cananian 1.1.2.1 for (NodeList nl = Adjacent(v); nl!=null; nl=nl.tail) {
370 cananian 1.1.2.1 AddEdge(nl.head,u);
371 cananian 1.1.2.7 /* We don't keep degree information for precolored nodes. */
372 cananian 1.1.2.7 if (!sets.precolored.contains(nl.head))
373 cananian 1.1.2.7 DecrementDegree(nl.head);
374 cananian 1.1.2.1 }
375 cananian 1.1.2.7 if (sets.worklist.freeze.contains(u) && Degree(u) >= K) {
376 cananian 1.1.2.1 sets.worklist.freeze.remove(u);
377 cananian 1.1.2.1 sets.worklist.spill.add(u);
378 cananian 1.1.2.1 }
379 cananian 1.1.2.1 }
380 cananian 1.1.2.1
381 cananian 1.1.2.1 int Degree(Node m) {
382 cananian 1.1.2.7 /* We don't keep accurate degree information for precolored nodes. */
383 cananian 1.3.2.1 assert !sets.precolored.contains(m);
384 cananian 1.1.2.1 return ((Integer)degree.get(m)).intValue();
385 cananian 1.1.2.1 }
386 cananian 1.1.2.1 void DecrementDegree(Node m) {
387 cananian 1.1.2.1 int d = Degree(m);
388 cananian 1.1.2.1 degree.put(m, new Integer(d-1));
389 cananian 1.1.2.1 //System.out.println("DecDegree("+ig.gtemp(m).toString()+"), "+d);
390 cananian 1.1.2.1 if (d == K) {
391 cananian 1.1.2.1 if (sets.worklist.spill.contains(m)) {
392 cananian 1.1.2.1 EnableMoves(new NodeList(m, Adjacent(m)));
393 cananian 1.1.2.1 sets.worklist.spill.remove(m);
394 cananian 1.1.2.1 if (MoveRelated(m))
395 cananian 1.1.2.1 sets.worklist.freeze.add(m);
396 cananian 1.1.2.1 else
397 cananian 1.1.2.1 sets.worklist.simplify.add(m);
398 cananian 1.1.2.1 }
399 cananian 1.1.2.1 }
400 cananian 1.1.2.1 }
401 cananian 1.1.2.1 void EnableMoves(NodeList nl) {
402 cananian 1.1.2.1 for ( ; nl!=null; nl=nl.tail)
403 cananian 1.1.2.1 for (NodeList ml=NodeMoves(nl.head); ml!=null; ml=ml.tail)
404 cananian 1.1.2.1 if (moves.active.contains(ml.head)) {
405 cananian 1.1.2.1 moves.active.remove(ml.head);
406 cananian 1.1.2.1 moves.worklist.add(ml.head);
407 cananian 1.1.2.1 }
408 cananian 1.1.2.1 }
409 cananian 1.1.2.1 boolean MoveRelated(Node n) {
410 cananian 1.1.2.1 return NodeMoves(n)!=null;
411 cananian 1.1.2.1 }
412 cananian 1.1.2.1 NodeList NodeMoves(Node n) {
413 cananian 1.1.2.1 NodeList r = null;
414 cananian 1.1.2.1 // Node is an InterferenceGraph node, corresponding to a temp.
415 cananian 1.1.2.1 // loop through move instruction nodes associated with this temp.
416 cananian 1.1.2.1 for (NodeList nl = (NodeList) moveList.get(n); nl!=null; nl=nl.tail)
417 cananian 1.1.2.1 // if this move is on the activeMoves or worklistMoves lists,
418 cananian 1.1.2.1 // then this (interference graph) node is regarded as 'move-related'
419 cananian 1.1.2.1 if (moves.active.contains(nl.head) ||
420 cananian 1.1.2.1 moves.worklist.contains(nl.head))
421 cananian 1.1.2.1 r = new NodeList(nl.head, r);
422 cananian 1.1.2.1 return r;
423 cananian 1.1.2.1 }
424 cananian 1.1.2.1
425 cananian 1.1.2.1 // More utility functions...
426 cananian 1.1.2.1
427 cananian 1.1.2.1 NodeList union(NodeList a, NodeList b) {
428 cananian 1.1.2.1 NodeList r=a;
429 cananian 1.1.2.1 for( ; b!=null; b=b.tail) {
430 cananian 1.1.2.1 NodeList nlp;
431 cananian 1.1.2.1 for (nlp = a; nlp!=null; nlp=nlp.tail)
432 cananian 1.1.2.1 if (b.head == nlp.head) break;
433 cananian 1.1.2.1 if (nlp==null)
434 cananian 1.1.2.1 r = new NodeList(b.head, r);
435 cananian 1.1.2.1 }
436 cananian 1.1.2.1 return r;
437 cananian 1.1.2.1 }
438 cananian 1.1.2.2 TempList merge(TempList a, TempList b) {
439 cananian 1.1.2.2 TempList p, r=null;
440 cananian 1.1.2.1 for (p=a; p!=null; p=p.tail) {
441 cananian 1.1.2.1 r=new TempList(p.head, r);
442 cananian 1.1.2.1 }
443 cananian 1.1.2.1 for (p=b; p!=null; p=p.tail) {
444 cananian 1.1.2.1 r=new TempList(p.head, r);
445 cananian 1.1.2.1 }
446 cananian 1.1.2.1 return r;
447 cananian 1.1.2.1 }
448 cananian 1.1.2.1 NodeList merge(NodeList a, NodeList b) {
449 cananian 1.1.2.1 NodeList p, r=null;
450 cananian 1.1.2.1 for (p=a; p!=null; p=p.tail) {
451 cananian 1.1.2.1 r=new NodeList(p.head, r);
452 cananian 1.1.2.1 }
453 cananian 1.1.2.1 for (p=b; p!=null; p=p.tail) {
454 cananian 1.1.2.1 r=new NodeList(p.head, r);
455 cananian 1.1.2.1 }
456 cananian 1.1.2.1 return r;
457 cananian 1.1.2.1 }
458 cananian 1.1.2.1 int len(TempList tl) {
459 cananian 1.1.2.1 int n=0;
460 cananian 1.1.2.1 for ( ; tl!=null; tl=tl.tail)
461 cananian 1.1.2.1 n++;
462 cananian 1.1.2.1 return n;
463 cananian 1.1.2.1 }
464 cananian 1.1.2.1 int len(NodeList nl) {
465 cananian 1.1.2.1 int n=0;
466 cananian 1.1.2.1 for ( ; nl!=null; nl=nl.tail)
467 cananian 1.1.2.1 n++;
468 cananian 1.1.2.1 return n;
469 cananian 1.1.2.1 }
470 cananian 1.1.2.1 // check that the 'degree' stored in the hashtable matches the adjacency.
471 cananian 1.1.2.1 void check(Node n) {
472 cananian 1.1.2.11 // CSA 31-mar-2000: we punt degree info for precolored nodes, so
473 cananian 1.1.2.11 // we can't do this check on them. we can check all the rest, tho.
474 cananian 1.1.2.11 if ((!sets.precolored.contains(n)) && len(Adjacent(n)) != Degree(n))
475 cananian 1.1.2.1 throw new Error("Inconsistent data for node "+ig.gtemp(n).toString()+
476 cananian 1.1.2.1 ": Adj("+len(Adjacent(n))+") != Degree("+Degree(n)+")");
477 cananian 1.1.2.1 }
478 cananian 1.1.2.1 void check(NodeList nl) {
479 cananian 1.1.2.1 for ( ; nl!=null; nl=nl.tail)
480 cananian 1.1.2.1 if (!sets.coalesced.contains(nl.head) &&
481 cananian 1.1.2.1 !sets.selectStack.contains(nl.head))
482 cananian 1.1.2.1 check(nl.head);
483 cananian 1.1.2.1 }
484 cananian 1.1.2.1 // perform sanity checks on the sets and the interference graph nodes.
485 cananian 1.1.2.1 void check() {
486 cananian 1.1.2.1 if (debug) {
487 cananian 1.1.2.1 sets.check();
488 cananian 1.1.2.1 check(ig.nodes());
489 cananian 1.1.2.5 // check invariants
490 cananian 1.1.2.5 for (NodeList nl=sets.worklist.simplify.nodes(); nl!=null; nl=nl.tail)
491 cananian 1.3.2.1 assert /*(Degree(nl.head) < K) &&*/(NodeMoves(nl.head)==null);
492 cananian 1.1.2.5 for (NodeList nl=sets.worklist.freeze.nodes(); nl!=null; nl=nl.tail)
493 cananian 1.3.2.1 assert (Degree(nl.head) < K) && (NodeMoves(nl.head)!=null);
494 cananian 1.1.2.5 for (NodeList nl=sets.worklist.spill.nodes(); nl!=null; nl=nl.tail)
495 cananian 1.3.2.1 assert Degree(nl.head) >= K;
496 cananian 1.1.2.1 }
497 cananian 1.1.2.1 }
498 cananian 1.2 }