1 cananian 1.1.2.3 // AppelRegAllocClasses.java, created Tue Jun 5 0:02:27 2001 by pnkfelix
2 cananian 1.1.2.3 // Copyright (C) 2001 Felix S. Klock II <pnkfelix@mit.edu>
3 cananian 1.1.2.3 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 pnkfelix 1.1.2.1 package harpoon.Analysis.Instr;
5 pnkfelix 1.1.2.1
6 pnkfelix 1.1.2.1 import harpoon.IR.Assem.Instr;
7 pnkfelix 1.1.2.1
8 pnkfelix 1.1.2.1 import harpoon.Temp.Temp;
9 pnkfelix 1.1.2.1
10 cananian 1.7 import net.cscott.jutil.BitString;
11 cananian 1.7 import net.cscott.jutil.Default;
12 cananian 1.6 import harpoon.Util.Util;
13 cananian 1.6
14 cananian 1.7 import net.cscott.jutil.LinearSet;
15 cananian 1.7 import net.cscott.jutil.UnmodifiableIterator;
16 pnkfelix 1.1.2.1
17 pnkfelix 1.1.2.1 import java.util.Iterator;
18 pnkfelix 1.1.2.1 import java.util.Collection;
19 pnkfelix 1.1.2.1 import java.util.Collections;
20 pnkfelix 1.1.2.7 import java.util.List;
21 pnkfelix 1.1.2.1 import java.util.ArrayList;
22 pnkfelix 1.1.2.1 import java.util.Set;
23 pnkfelix 1.1.2.1 import java.util.HashSet;
24 pnkfelix 1.1.2.1 import java.util.HashMap;
25 pnkfelix 1.1.2.1
26 pnkfelix 1.1.2.1 /** Collects various data structures used by AppelRegAlloc.
27 cananian 1.1.2.3 * @author Felix S. Klock II <pnkfelix@mit.edu>
28 cananian 1.9 * @version $Id: AppelRegAllocClasses.java,v 1.9 2004/02/08 04:55:22 cananian Exp $
29 pnkfelix 1.1.2.1 */
30 pnkfelix 1.1.2.1 abstract class AppelRegAllocClasses extends RegAlloc {
31 pnkfelix 1.1.2.5 public static final boolean CHECK_INV = false;
32 pnkfelix 1.1.2.8
33 pnkfelix 1.1.2.9 // FSK: debugging ("mul t0, t1, t2" ==> reg(t0) != reg(t1)) assertion failure by snapshotting extra state
34 pnkfelix 1.1.2.9 private static final boolean PAIRSET_IN_SNAPSHOT = true;
35 pnkfelix 1.1.2.5
36 pnkfelix 1.1.2.1 public AppelRegAllocClasses(harpoon.Backend.Generic.Code code) {
37 pnkfelix 1.1.2.1 super(code);
38 pnkfelix 1.1.2.1 }
39 pnkfelix 1.1.2.7
40 pnkfelix 1.1.2.7 private String lastStateString;
41 pnkfelix 1.1.2.7 /** Saves the current state of <code>this</code> for later
42 pnkfelix 1.1.2.7 retrieval using <code>resetState()</code>.
43 pnkfelix 1.1.2.7
44 pnkfelix 1.1.2.7 Note that <code>this</code> only carries <code>Node</code> and
45 cananian 1.4 <code>Move</code> state; additional state added by subclasses
46 pnkfelix 1.1.2.7 will not be checkpointed unless this method and reset state
47 pnkfelix 1.1.2.7 are overridden.
48 pnkfelix 1.1.2.7
49 pnkfelix 1.1.2.7 */
50 pnkfelix 1.1.2.7 protected void checkpointState() {
51 pnkfelix 1.1.2.7 if (CHECK_INV)
52 pnkfelix 1.1.2.7 lastStateString = stateString();
53 pnkfelix 1.1.2.7 saveNodePairSet();
54 pnkfelix 1.1.2.7 saveNodeSets();
55 pnkfelix 1.1.2.7 if (CHECK_INV)
56 cananian 1.3.2.1 assert lastStateString.equals(stateString()) : "\n\n"
57 pnkfelix 1.1.2.7 +"last : "+lastStateString+"\n"
58 cananian 1.3.2.1 +"curr : "+stateString()+"\n";
59 pnkfelix 1.1.2.9
60 pnkfelix 1.1.2.9 // System.out.println(stateString());
61 pnkfelix 1.1.2.7 }
62 pnkfelix 1.1.2.7 /** Restores the state of <code>this</code> to the state it was in
63 pnkfelix 1.1.2.7 on the last call to <code>checkpointState()</code>.
64 pnkfelix 1.1.2.7 */
65 pnkfelix 1.1.2.7 protected void resetState() {
66 pnkfelix 1.1.2.9 // System.out.println(stateString());
67 pnkfelix 1.1.2.7 restoreNodePairSet();
68 pnkfelix 1.1.2.7 restoreNodeSets();
69 pnkfelix 1.1.2.7 resetMoveSets();
70 pnkfelix 1.1.2.7 if (CHECK_INV)
71 cananian 1.3.2.1 assert lastStateString.equals(stateString()) : "\n\n"
72 pnkfelix 1.1.2.7 +"last : "+lastStateString+"\n"
73 cananian 1.3.2.1 +"curr : "+stateString()+"\n";
74 pnkfelix 1.1.2.9 // System.out.println(stateString());
75 pnkfelix 1.1.2.7 }
76 pnkfelix 1.1.2.7
77 pnkfelix 1.1.2.11 protected String stateString() {
78 pnkfelix 1.1.2.7 // FSK: should probably sort lists on index number to ensure
79 pnkfelix 1.1.2.7 // determinism on sets.
80 pnkfelix 1.1.2.7 String igraphString = interferenceGraphString();
81 pnkfelix 1.1.2.7
82 pnkfelix 1.1.2.7 return "\n"+
83 pnkfelix 1.1.2.7 precolored+"\n"+
84 pnkfelix 1.1.2.7 initial+"\n"+
85 pnkfelix 1.1.2.7 simplify_worklist+"\n"+
86 pnkfelix 1.1.2.7 freeze_worklist+"\n"+
87 pnkfelix 1.1.2.7 spill_worklist+"\n"+
88 pnkfelix 1.1.2.7 spilled_nodes+"\n"+
89 pnkfelix 1.1.2.7 coalesced_nodes+"\n"+
90 pnkfelix 1.1.2.7 colored_nodes+"\n"+
91 pnkfelix 1.1.2.7 select_stack+"\n"+
92 pnkfelix 1.1.2.7 "\n\n"+
93 pnkfelix 1.1.2.7 coalesced_moves+"\n"+
94 pnkfelix 1.1.2.7 constrained_moves+"\n"+
95 pnkfelix 1.1.2.7 frozen_moves+"\n"+
96 pnkfelix 1.1.2.7 worklist_moves+"\n"+
97 pnkfelix 1.1.2.7 active_moves+"\n"+
98 pnkfelix 1.1.2.7 "\n\n"+
99 pnkfelix 1.1.2.7 igraphString
100 pnkfelix 1.1.2.7 ;
101 pnkfelix 1.1.2.7 }
102 pnkfelix 1.1.2.7
103 pnkfelix 1.1.2.7 String interferenceGraphString() {
104 pnkfelix 1.1.2.7 StringBuffer sb = new StringBuffer();
105 pnkfelix 1.1.2.7 sb.append("** BEGIN GRAPH **\n");
106 pnkfelix 1.1.2.14 for(Iterator nodes = allNodes(); nodes.hasNext(); ){
107 pnkfelix 1.1.2.7 Node n = (Node) nodes.next();
108 pnkfelix 1.1.2.7 sb.append(n);
109 pnkfelix 1.1.2.7 sb.append(", neighbors:[");
110 pnkfelix 1.1.2.7 for(NodeIter nbors = n.neighbors.iter(); nbors.hasNext();){
111 pnkfelix 1.1.2.7 sb.append( nbors.next().id );
112 pnkfelix 1.1.2.9 sb.append(",");
113 pnkfelix 1.1.2.7 }
114 pnkfelix 1.1.2.7 sb.append("]");
115 pnkfelix 1.1.2.7 sb.append("\n");
116 pnkfelix 1.1.2.7 }
117 pnkfelix 1.1.2.7 sb.append("** END GRAPH **\n");
118 pnkfelix 1.1.2.7
119 pnkfelix 1.1.2.7 sb.append("AdjSet: ");
120 pnkfelix 1.1.2.7 java.util.TreeSet sortedPairs =
121 pnkfelix 1.1.2.7 new java.util.TreeSet( new java.util.Comparator() {
122 pnkfelix 1.1.2.7 public int compare(Object o1, Object o2) {
123 pnkfelix 1.1.2.7 List nl_0 = (List) o1;
124 pnkfelix 1.1.2.7 List nl_1 = (List) o2;
125 pnkfelix 1.1.2.7 Node n00 = (Node) nl_0.get(0);
126 pnkfelix 1.1.2.7 Node n01 = (Node) nl_0.get(1);
127 pnkfelix 1.1.2.7 Node n10 = (Node) nl_1.get(0);
128 pnkfelix 1.1.2.7 Node n11 = (Node) nl_1.get(1);
129 pnkfelix 1.1.2.7
130 pnkfelix 1.1.2.9
131 pnkfelix 1.1.2.9 if (Math.max(n00.id,n01.id) == Math.max(n10.id,n11.id)) {
132 pnkfelix 1.1.2.9 return Math.min(n00.id,n01.id) - Math.min(n10.id,n11.id);
133 pnkfelix 1.1.2.7 } else {
134 pnkfelix 1.1.2.9 return Math.max(n00.id,n01.id) - Math.max(n10.id,n11.id);
135 pnkfelix 1.1.2.7 }
136 pnkfelix 1.1.2.7 }
137 pnkfelix 1.1.2.7 });
138 pnkfelix 1.1.2.12 sortedPairs.addAll( adjSet.pairs() );
139 pnkfelix 1.1.2.7 sb.append( sortedPairs );
140 pnkfelix 1.1.2.7
141 pnkfelix 1.1.2.7 return sb.toString();
142 pnkfelix 1.1.2.7 }
143 pnkfelix 1.1.2.7
144 pnkfelix 1.1.2.7 // Set of <Node, Node> pairs
145 pnkfelix 1.1.2.7 NodePairSet adjSet;
146 pnkfelix 1.1.2.7
147 pnkfelix 1.1.2.1 NodeSet precolored;
148 pnkfelix 1.1.2.1 NodeSet initial;
149 pnkfelix 1.1.2.1 NodeSet simplify_worklist;
150 pnkfelix 1.1.2.1 NodeSet freeze_worklist;
151 pnkfelix 1.1.2.1 NodeSet spill_worklist;
152 pnkfelix 1.1.2.1 NodeSet spilled_nodes;
153 pnkfelix 1.1.2.1 NodeSet coalesced_nodes;
154 pnkfelix 1.1.2.1 NodeSet colored_nodes;
155 pnkfelix 1.1.2.1 NodeSet select_stack;
156 pnkfelix 1.1.2.1
157 pnkfelix 1.1.2.10 protected HashSet dontSpillTheseDefs = new HashSet();
158 pnkfelix 1.1.2.1
159 pnkfelix 1.1.2.10 class Web {
160 pnkfelix 1.1.2.1 Temp temp;
161 pnkfelix 1.1.2.1 Collection defs, uses;
162 pnkfelix 1.1.2.1 Web(Temp temp, Set defs, Set uses) {
163 pnkfelix 1.1.2.1 this.temp = temp;
164 pnkfelix 1.1.2.1 this.defs = new LinearSet(defs);
165 pnkfelix 1.1.2.1 this.uses = new LinearSet(uses);
166 pnkfelix 1.1.2.1 }
167 pnkfelix 1.1.2.10
168 pnkfelix 1.1.2.10 private int spillable = 0; // 0 is dont-know, 1 is yes, -1 is no.
169 pnkfelix 1.1.2.10 protected boolean isSpillable() {
170 pnkfelix 1.1.2.10 switch (spillable) {
171 pnkfelix 1.1.2.10 case 1 : return true;
172 pnkfelix 1.1.2.10 case -1: return false;
173 pnkfelix 1.1.2.10 default:
174 pnkfelix 1.1.2.10 {
175 cananian 1.8 for(Object dO : defs) {
176 cananian 1.8 Instr d = (Instr) dO;
177 pnkfelix 1.1.2.10 if (d instanceof RestoreProxy ||
178 pnkfelix 1.1.2.10 dontSpillTheseDefs.contains(d)) {
179 pnkfelix 1.1.2.10 spillable = -1;
180 pnkfelix 1.1.2.10 return false;
181 pnkfelix 1.1.2.10 }
182 pnkfelix 1.1.2.10 }
183 pnkfelix 1.1.2.10 for(Iterator ui = uses.iterator(); ui.hasNext(); ){
184 pnkfelix 1.1.2.10 if (ui.next() instanceof SpillProxy) {
185 pnkfelix 1.1.2.10 spillable = -1;
186 pnkfelix 1.1.2.10 return false;
187 pnkfelix 1.1.2.10 }
188 pnkfelix 1.1.2.10 }
189 pnkfelix 1.1.2.10 spillable = 1;
190 pnkfelix 1.1.2.10 return true;
191 pnkfelix 1.1.2.10 }
192 pnkfelix 1.1.2.10 }
193 pnkfelix 1.1.2.10
194 pnkfelix 1.1.2.10 }
195 pnkfelix 1.1.2.1 public String toString() {
196 pnkfelix 1.1.2.1 return "Web<"+temp+
197 pnkfelix 1.1.2.1 ", defs:"+defs+
198 pnkfelix 1.1.2.1 ", uses:"+uses+">";
199 pnkfelix 1.1.2.1 }
200 pnkfelix 1.1.2.1 }
201 pnkfelix 1.1.2.1
202 pnkfelix 1.1.2.1
203 pnkfelix 1.1.2.1 void initializeNodeSets() {
204 pnkfelix 1.1.2.14 nextId = 1;
205 pnkfelix 1.1.2.14 allNodes = new ArrayList();
206 pnkfelix 1.1.2.14
207 pnkfelix 1.1.2.14 // these sets collectively partition the space of Nodes
208 pnkfelix 1.1.2.1 precolored = new NodeSet("precolored");
209 pnkfelix 1.1.2.1 initial = new NodeSet("initial");
210 pnkfelix 1.1.2.1 simplify_worklist = new NodeSet("simplify_worklist");
211 pnkfelix 1.1.2.1 freeze_worklist = new NodeSet("freeze_worklist");
212 pnkfelix 1.1.2.1 spill_worklist = new NodeSet("spill_worklist");
213 pnkfelix 1.1.2.1 spilled_nodes = new NodeSet("spilled_nodes");
214 pnkfelix 1.1.2.1 coalesced_nodes = new NodeSet("coalesced_nodes");
215 pnkfelix 1.1.2.1 colored_nodes = new NodeSet("colored_nodes");
216 pnkfelix 1.1.2.1 select_stack = new NodeSet("select_stack");
217 pnkfelix 1.1.2.1 }
218 pnkfelix 1.1.2.1
219 pnkfelix 1.1.2.1 class BackupNodeSetInfo {
220 pnkfelix 1.1.2.1 class BackupNodeInfo {
221 pnkfelix 1.1.2.1 // keeps id/web saved
222 pnkfelix 1.1.2.1 final Node origNode;
223 pnkfelix 1.1.2.1 // don't need to save s_prev/s_next/s_rep
224 pnkfelix 1.1.2.7 final int origDegree;
225 pnkfelix 1.1.2.1 final NodeList origNeighbors;
226 pnkfelix 1.1.2.1 final Node origAlias;
227 pnkfelix 1.1.2.7 final MoveList origMoves; // List<Move>
228 pnkfelix 1.1.2.11 final int[] origColor;
229 pnkfelix 1.1.2.1
230 pnkfelix 1.1.2.1 BackupNodeInfo( Node save ){
231 pnkfelix 1.1.2.1 origNode = save;
232 pnkfelix 1.1.2.7 origDegree = save.degree;
233 pnkfelix 1.1.2.1 origAlias = save.alias;
234 pnkfelix 1.1.2.11 origColor = (int[]) save.color.clone();
235 pnkfelix 1.1.2.7 origMoves = new MoveList(save.moves.toList());
236 pnkfelix 1.1.2.7 origNeighbors = new NodeList( save.neighbors.toList() );
237 pnkfelix 1.1.2.1 }
238 pnkfelix 1.1.2.1
239 pnkfelix 1.1.2.1 void restore() {
240 pnkfelix 1.1.2.7 origNode.degree = origDegree;
241 pnkfelix 1.1.2.1 origNode.alias = origAlias;
242 pnkfelix 1.1.2.11 origNode.color = (int[]) origColor.clone();
243 pnkfelix 1.1.2.7 origNode.moves = new MoveList( origMoves.toList() );
244 pnkfelix 1.1.2.7 origNode.neighbors = new NodeList( origNeighbors.toList() );
245 pnkfelix 1.1.2.1 }
246 pnkfelix 1.1.2.1 }
247 pnkfelix 1.1.2.1
248 pnkfelix 1.1.2.1 final NodeSet origSet;
249 pnkfelix 1.1.2.1 final ArrayList savedState; // List<BackupNodeInfo>
250 pnkfelix 1.1.2.1
251 pnkfelix 1.1.2.1 BackupNodeSetInfo(NodeSet save) {
252 pnkfelix 1.1.2.1 this.origSet = save;
253 pnkfelix 1.1.2.1 savedState = new ArrayList(origSet.size);
254 pnkfelix 1.1.2.1 for(NodeIter nI=save.iter(); nI.hasNext(); ){
255 pnkfelix 1.1.2.1 savedState.add( new BackupNodeInfo( nI.next() ));
256 pnkfelix 1.1.2.1 }
257 pnkfelix 1.1.2.1 }
258 pnkfelix 1.1.2.7
259 pnkfelix 1.1.2.7 private void clearOrig() { origSet.clear(); }
260 pnkfelix 1.1.2.7 private void restore() {
261 pnkfelix 1.1.2.7 for(int i=savedState.size()-1; i>=0; i--){
262 pnkfelix 1.1.2.7 BackupNodeInfo bn = (BackupNodeInfo) savedState.get(i);
263 pnkfelix 1.1.2.7 bn.restore();
264 pnkfelix 1.1.2.7 origSet.add( bn.origNode );
265 pnkfelix 1.1.2.7 }
266 pnkfelix 1.1.2.7 }
267 pnkfelix 1.1.2.1 }
268 pnkfelix 1.1.2.1
269 pnkfelix 1.1.2.1 BackupNodeSetInfo
270 pnkfelix 1.1.2.7 initialI, // wasn't originally in code... was there a reason?
271 pnkfelix 1.1.2.7
272 pnkfelix 1.1.2.1 simplify_worklistI, freeze_worklistI,
273 pnkfelix 1.1.2.1 spill_worklistI, spilled_nodesI,
274 pnkfelix 1.1.2.1 coalesced_nodesI, colored_nodesI,
275 pnkfelix 1.1.2.1 select_stackI;
276 pnkfelix 1.1.2.1
277 pnkfelix 1.1.2.7 private void saveNodeSets() {
278 pnkfelix 1.1.2.7 initialI = new BackupNodeSetInfo( initial );
279 pnkfelix 1.1.2.1 simplify_worklistI = new BackupNodeSetInfo( simplify_worklist );
280 pnkfelix 1.1.2.1 freeze_worklistI = new BackupNodeSetInfo( freeze_worklist );
281 pnkfelix 1.1.2.1 spill_worklistI = new BackupNodeSetInfo( spill_worklist );
282 pnkfelix 1.1.2.1 spilled_nodesI = new BackupNodeSetInfo( spilled_nodes );
283 pnkfelix 1.1.2.1 coalesced_nodesI = new BackupNodeSetInfo( coalesced_nodes );
284 pnkfelix 1.1.2.1 colored_nodesI = new BackupNodeSetInfo( colored_nodes );
285 pnkfelix 1.1.2.1 select_stackI = new BackupNodeSetInfo( select_stack );
286 pnkfelix 1.1.2.1 }
287 pnkfelix 1.1.2.7 private void restoreNodeSets() {
288 pnkfelix 1.1.2.1 // helper array to make traversal code easy
289 pnkfelix 1.1.2.1 BackupNodeSetInfo[] infos = new BackupNodeSetInfo[]{
290 pnkfelix 1.1.2.7 initialI,
291 pnkfelix 1.1.2.1 simplify_worklistI, freeze_worklistI,
292 pnkfelix 1.1.2.1 spill_worklistI, spilled_nodesI,
293 pnkfelix 1.1.2.1 coalesced_nodesI, colored_nodesI,
294 pnkfelix 1.1.2.1 select_stackI
295 pnkfelix 1.1.2.1 };
296 pnkfelix 1.1.2.1
297 pnkfelix 1.1.2.1 // must clear all origSets before restoring them
298 pnkfelix 1.1.2.1 for(int i=0; i<infos.length; i++)
299 pnkfelix 1.1.2.7 infos[i].clearOrig();
300 pnkfelix 1.1.2.1 for(int i=0; i<infos.length; i++)
301 pnkfelix 1.1.2.7 infos[i].restore();
302 pnkfelix 1.1.2.1 }
303 pnkfelix 1.1.2.1
304 pnkfelix 1.1.2.7 NodePairSet lastAdjSet;
305 pnkfelix 1.1.2.8 private void saveNodePairSet() {
306 pnkfelix 1.1.2.8 if (PAIRSET_IN_SNAPSHOT)
307 pnkfelix 1.1.2.8 lastAdjSet = adjSet.copy();
308 pnkfelix 1.1.2.8 }
309 pnkfelix 1.1.2.8 private void restoreNodePairSet() {
310 pnkfelix 1.1.2.8 if (PAIRSET_IN_SNAPSHOT)
311 pnkfelix 1.1.2.8 adjSet = lastAdjSet.copy();
312 pnkfelix 1.1.2.8 }
313 pnkfelix 1.1.2.1
314 pnkfelix 1.1.2.1 abstract static class NodeIter {
315 pnkfelix 1.1.2.1 public abstract boolean hasNext();
316 pnkfelix 1.1.2.1 public abstract Node next();
317 pnkfelix 1.1.2.1 }
318 pnkfelix 1.1.2.1 NodeIter combine(final NodeIter[] iters) {
319 pnkfelix 1.1.2.1 return new NodeIter() {
320 pnkfelix 1.1.2.1 int i=0;
321 pnkfelix 1.1.2.1 public boolean hasNext() {
322 pnkfelix 1.1.2.1 while(i < iters.length) {
323 pnkfelix 1.1.2.1 if (iters[i].hasNext()) {
324 pnkfelix 1.1.2.1 return true;
325 pnkfelix 1.1.2.1 } else {
326 pnkfelix 1.1.2.1 i++;
327 pnkfelix 1.1.2.1 continue;
328 pnkfelix 1.1.2.1 }
329 pnkfelix 1.1.2.1 }
330 pnkfelix 1.1.2.1 return false;
331 pnkfelix 1.1.2.1 }
332 pnkfelix 1.1.2.1 public Node next() {
333 pnkfelix 1.1.2.1 hasNext();
334 pnkfelix 1.1.2.1 return iters[i].next(); }
335 pnkfelix 1.1.2.1 };
336 pnkfelix 1.1.2.1 }
337 pnkfelix 1.1.2.1
338 pnkfelix 1.1.2.1 final class NodeSet {
339 pnkfelix 1.1.2.1 String name; // for debugging
340 pnkfelix 1.1.2.1 int size;
341 pnkfelix 1.1.2.1 Node head; // dummy element
342 pnkfelix 1.1.2.1
343 pnkfelix 1.1.2.4 void checkRep() { if (true) return;
344 cananian 1.3.2.1 assert size >= 0;
345 cananian 1.3.2.1 assert head != null;
346 pnkfelix 1.1.2.1 Node curr = head;
347 pnkfelix 1.1.2.1 int sz = -1;
348 pnkfelix 1.1.2.1 do {
349 cananian 1.3.2.1 assert curr.s_prev.s_next == curr;
350 cananian 1.3.2.1 assert curr.s_next.s_prev == curr;
351 pnkfelix 1.1.2.1 sz++;
352 pnkfelix 1.1.2.1 curr = curr.s_next;
353 pnkfelix 1.1.2.1 } while (curr != head);
354 cananian 1.3.2.1 assert sz == size;
355 pnkfelix 1.1.2.1 }
356 pnkfelix 1.1.2.1
357 pnkfelix 1.1.2.1
358 pnkfelix 1.1.2.1 NodeSet(String s) {
359 pnkfelix 1.1.2.1 name = s;
360 pnkfelix 1.1.2.1 head = new Node(null);
361 pnkfelix 1.1.2.1 size = 0;
362 pnkfelix 1.1.2.1 checkRep();
363 pnkfelix 1.1.2.1 }
364 pnkfelix 1.1.2.1
365 pnkfelix 1.1.2.1 NodeIter iter() {
366 pnkfelix 1.1.2.1 checkRep();
367 pnkfelix 1.1.2.1 return new NodeIter() {
368 pnkfelix 1.1.2.1 Node curr = head;
369 pnkfelix 1.1.2.1 public boolean hasNext() { return curr.s_next != head; }
370 pnkfelix 1.1.2.1 public Node next() { checkRep();
371 cananian 1.3.2.1 assert hasNext();
372 pnkfelix 1.1.2.1 Node ret = curr.s_next; curr = ret;
373 pnkfelix 1.1.2.1 checkRep();
374 pnkfelix 1.1.2.1 return ret;
375 pnkfelix 1.1.2.1 }
376 pnkfelix 1.1.2.1 };
377 pnkfelix 1.1.2.1 }
378 pnkfelix 1.1.2.1
379 pnkfelix 1.1.2.1 Node pop() {
380 pnkfelix 1.1.2.1 checkRep();
381 pnkfelix 1.1.2.1 Node n = head.s_next;
382 pnkfelix 1.1.2.1 remove(n);
383 pnkfelix 1.1.2.1 checkRep();
384 pnkfelix 1.1.2.1 return n;
385 pnkfelix 1.1.2.1 }
386 pnkfelix 1.1.2.1
387 pnkfelix 1.1.2.1 boolean isEmpty() { return size == 0; }
388 pnkfelix 1.1.2.1 void clear() { while( !isEmpty() ) pop(); }
389 pnkfelix 1.1.2.1
390 pnkfelix 1.1.2.1 void remove(Node n) {
391 pnkfelix 1.1.2.1 checkRep();
392 cananian 1.3.2.1 assert this != precolored : "can't remove regs from precolored";
393 cananian 1.3.2.1 assert n.s_rep == this : this.name +
394 pnkfelix 1.1.2.1 " tried to remove a node that is in "+
395 cananian 1.3.2.1 n.s_rep.name;
396 pnkfelix 1.1.2.1
397 cananian 1.3.2.1 assert ! n.locked : "node "+n+" should not be locked";
398 pnkfelix 1.1.2.1
399 pnkfelix 1.1.2.1 n.s_prev.s_next = n.s_next;
400 pnkfelix 1.1.2.1 n.s_next.s_prev = n.s_prev;
401 pnkfelix 1.1.2.1 size--;
402 pnkfelix 1.1.2.1 n.s_next = n;
403 pnkfelix 1.1.2.1 n.s_prev = n;
404 pnkfelix 1.1.2.1 n.s_rep = null;
405 pnkfelix 1.1.2.1
406 pnkfelix 1.1.2.1 checkRep();
407 pnkfelix 1.1.2.1 }
408 pnkfelix 1.1.2.1 void add(Node n) {
409 pnkfelix 1.1.2.1 // If select_stack is going to be implemented as a
410 pnkfelix 1.1.2.1 // NodeSet, .add(..) needs to "push" Nodes on FRONT of
411 pnkfelix 1.1.2.1 // set, not the end.
412 pnkfelix 1.1.2.14
413 pnkfelix 1.1.2.1 checkRep();
414 cananian 1.3.2.1 assert n.s_prev == n;
415 cananian 1.3.2.1 assert n.s_next == n;
416 cananian 1.3.2.1 assert n.s_rep == null;
417 cananian 1.3.2.1 assert n.s_rep != precolored : "can't add regs from precolored";
418 pnkfelix 1.1.2.1
419 cananian 1.3.2.1 assert ! n.locked : "node "+n+" should not be locked";
420 pnkfelix 1.1.2.1
421 pnkfelix 1.1.2.1 head.s_next.s_prev = n;
422 pnkfelix 1.1.2.1 n.s_next = head.s_next;
423 pnkfelix 1.1.2.1 n.s_prev = head;
424 pnkfelix 1.1.2.1 head.s_next = n;
425 pnkfelix 1.1.2.1 n.s_rep = this;
426 pnkfelix 1.1.2.1 size++;
427 pnkfelix 1.1.2.1
428 pnkfelix 1.1.2.1 n.nodeSet_history.addFirst(this);
429 pnkfelix 1.1.2.1
430 pnkfelix 1.1.2.1 checkRep();
431 pnkfelix 1.1.2.1 }
432 pnkfelix 1.1.2.1
433 pnkfelix 1.1.2.1 Set asSet() { return new java.util.AbstractSet() {
434 pnkfelix 1.1.2.1 public int size() { return size; }
435 pnkfelix 1.1.2.1 public Iterator iterator() {
436 pnkfelix 1.1.2.1 final NodeIter ni = iter();
437 cananian 1.6 return new UnmodifiableIterator() {
438 pnkfelix 1.1.2.1 public boolean hasNext() {return ni.hasNext();}
439 pnkfelix 1.1.2.1 public Object next() {return ni.next();}
440 pnkfelix 1.1.2.1 };
441 pnkfelix 1.1.2.1 }
442 pnkfelix 1.1.2.1 };
443 pnkfelix 1.1.2.1 }
444 pnkfelix 1.1.2.7
445 pnkfelix 1.1.2.7 public String toString() {
446 pnkfelix 1.1.2.7 return "NodeSet< "+name+", "+asSet()+" >"; }
447 pnkfelix 1.1.2.1
448 pnkfelix 1.1.2.1 }
449 pnkfelix 1.1.2.1
450 pnkfelix 1.1.2.1 NodeIter adjacent(Node n) {
451 pnkfelix 1.1.2.1 final NodeIter internIter = n.neighbors.iter();
452 pnkfelix 1.1.2.1 // filter out ( selectStack U coalescedNodes )
453 pnkfelix 1.1.2.1 return new NodeIter() {
454 pnkfelix 1.1.2.1 Node next = null;
455 pnkfelix 1.1.2.1 public boolean hasNext() {
456 pnkfelix 1.1.2.1 if (next == null) {
457 pnkfelix 1.1.2.1 while(internIter.hasNext()) {
458 pnkfelix 1.1.2.1 next = internIter.next();
459 pnkfelix 1.1.2.1 if (next.isSelectStack() || next.isCoalesced()) {
460 pnkfelix 1.1.2.1 continue;
461 pnkfelix 1.1.2.1 } else {
462 pnkfelix 1.1.2.1 return true;
463 pnkfelix 1.1.2.1 }
464 pnkfelix 1.1.2.1 }
465 pnkfelix 1.1.2.1 return false;
466 pnkfelix 1.1.2.1 } else {
467 pnkfelix 1.1.2.1 return true;
468 pnkfelix 1.1.2.1 }
469 pnkfelix 1.1.2.1 }
470 pnkfelix 1.1.2.1 public Node next() {
471 pnkfelix 1.1.2.1 hasNext();
472 pnkfelix 1.1.2.1 Node rtrn = next;
473 pnkfelix 1.1.2.1 next = null;
474 pnkfelix 1.1.2.1 return rtrn;
475 pnkfelix 1.1.2.1 }
476 pnkfelix 1.1.2.1 };
477 pnkfelix 1.1.2.1 }
478 pnkfelix 1.1.2.12 /** Factory method to allow easier implementation switching later. */
479 pnkfelix 1.1.2.13 NodePairSet makeNodePairSetOld() {
480 pnkfelix 1.1.2.13 return new NodePairSet__Switching(nextId > 1500);
481 pnkfelix 1.1.2.13 }
482 pnkfelix 1.1.2.12 NodePairSet makeNodePairSet() {
483 pnkfelix 1.1.2.12 return nextId > 2250 ? new NodePairSet__HashBased()
484 pnkfelix 1.1.2.12 : (NodePairSet) new NodePairSet__BitStrBased();
485 pnkfelix 1.1.2.12 }
486 pnkfelix 1.1.2.12
487 pnkfelix 1.1.2.12 static abstract class NodePairSet {
488 pnkfelix 1.1.2.12 public abstract boolean contains(Node a, Node b);
489 pnkfelix 1.1.2.12 public abstract void add(Node a, Node b);
490 pnkfelix 1.1.2.12 public abstract HashSet pairs();
491 pnkfelix 1.1.2.12 public abstract NodePairSet copy();
492 pnkfelix 1.1.2.12 }
493 pnkfelix 1.1.2.12 class NodePairSet__Switching extends NodePairSet {
494 pnkfelix 1.1.2.12 boolean hash;
495 pnkfelix 1.1.2.12 NodePairSet back;
496 pnkfelix 1.1.2.13 // for use by copy only
497 pnkfelix 1.1.2.13 private NodePairSet__Switching() { }
498 pnkfelix 1.1.2.13 private NodePairSet__Switching(boolean startHash) {
499 pnkfelix 1.1.2.13 hash = startHash;
500 pnkfelix 1.1.2.13 if (hash)
501 pnkfelix 1.1.2.13 back = new NodePairSet__HashBased();
502 pnkfelix 1.1.2.13 else
503 pnkfelix 1.1.2.13 back = new NodePairSet__BitStrBased();
504 pnkfelix 1.1.2.12 }
505 pnkfelix 1.1.2.12 public boolean contains(Node a, Node b) { return back.contains(a,b); }
506 pnkfelix 1.1.2.13 public void add(Node a, Node b) {
507 pnkfelix 1.1.2.13 if (hash)
508 pnkfelix 1.1.2.13 checkForSwitch();
509 pnkfelix 1.1.2.13 back.add(a,b);
510 pnkfelix 1.1.2.13 }
511 pnkfelix 1.1.2.13 private void checkForSwitch() {
512 pnkfelix 1.1.2.13 NodePairSet__HashBased h = (NodePairSet__HashBased) back;
513 pnkfelix 1.1.2.13 if ((((double)h.pairs.size()) /
514 pnkfelix 1.1.2.13 ((double)(nextId*nextId))) > 0.008) {
515 pnkfelix 1.1.2.13 hash = false;
516 pnkfelix 1.1.2.13 System.out.println();
517 pnkfelix 1.1.2.13 System.out.print("Switching on "+h.pairs.size()+" edge");
518 pnkfelix 1.1.2.13 back = new NodePairSet__BitStrBased();
519 cananian 1.8 for(Object lO : h.pairs){
520 cananian 1.8 List l = (List) lO;
521 pnkfelix 1.1.2.13 back.add( (Node)l.get(0), (Node)l.get(1) );
522 pnkfelix 1.1.2.13 }
523 pnkfelix 1.1.2.13 System.out.println("!!!");
524 pnkfelix 1.1.2.13 }
525 pnkfelix 1.1.2.13 }
526 pnkfelix 1.1.2.12 public HashSet pairs() { return back.pairs(); }
527 pnkfelix 1.1.2.12 public NodePairSet copy() {
528 pnkfelix 1.1.2.12 NodePairSet__Switching r = new NodePairSet__Switching();
529 pnkfelix 1.1.2.12 r.hash = hash;
530 pnkfelix 1.1.2.12 r.back = back.copy();
531 pnkfelix 1.1.2.12 return r;
532 pnkfelix 1.1.2.12 }
533 pnkfelix 1.1.2.12 }
534 pnkfelix 1.1.2.12 class NodePairSet__BitStrBased extends NodePairSet {
535 pnkfelix 1.1.2.12 int off; BitString bs;
536 pnkfelix 1.1.2.12 private NodePairSet__BitStrBased() {
537 pnkfelix 1.1.2.12 off = nextId;
538 pnkfelix 1.1.2.12 int size = off*off;
539 pnkfelix 1.1.2.12 bs = new BitString( size );
540 pnkfelix 1.1.2.12 }
541 pnkfelix 1.1.2.12 public boolean contains(Node a, Node b) {
542 pnkfelix 1.1.2.12 return bs.get(off*a.id+b.id);
543 pnkfelix 1.1.2.12 }
544 pnkfelix 1.1.2.12 public void add(Node a, Node b) {
545 pnkfelix 1.1.2.12 bs.set(off*a.id+b.id);
546 pnkfelix 1.1.2.12 }
547 pnkfelix 1.1.2.12 public NodePairSet copy() {
548 pnkfelix 1.1.2.12 NodePairSet__BitStrBased c = new NodePairSet__BitStrBased();
549 pnkfelix 1.1.2.12 c.off = off;
550 pnkfelix 1.1.2.12 c.bs = (BitString) bs.clone();
551 pnkfelix 1.1.2.12 return c;
552 pnkfelix 1.1.2.12 }
553 pnkfelix 1.1.2.12 public HashSet pairs() {
554 pnkfelix 1.1.2.12 HashSet prs = new HashSet();
555 pnkfelix 1.1.2.14 for(int i=1; i<off; i++) {
556 pnkfelix 1.1.2.14 for(int j=1; j<off; j++) {
557 pnkfelix 1.1.2.12 if (bs.get(off*i+j)) {
558 pnkfelix 1.1.2.12 prs.add(Default.pair
559 pnkfelix 1.1.2.14 ( getNode(i),
560 pnkfelix 1.1.2.14 getNode(j) ));
561 pnkfelix 1.1.2.12 }
562 pnkfelix 1.1.2.12 }
563 pnkfelix 1.1.2.12 }
564 pnkfelix 1.1.2.12 return prs;
565 pnkfelix 1.1.2.12 }
566 pnkfelix 1.1.2.12 }
567 pnkfelix 1.1.2.12 final class NodePairSet__HashBased extends NodePairSet {
568 pnkfelix 1.1.2.12 HashSet pairs = new HashSet(nextId*20);
569 pnkfelix 1.1.2.12 private NodePairSet__HashBased() { }
570 pnkfelix 1.1.2.1 public boolean contains(Node a, Node b) {
571 pnkfelix 1.1.2.1 return pairs.contains(Default.pair(a,b));
572 pnkfelix 1.1.2.1 }
573 pnkfelix 1.1.2.1 public void add(Node a, Node b) {
574 pnkfelix 1.1.2.1 pairs.add(Default.pair(a, b));
575 pnkfelix 1.1.2.1 }
576 pnkfelix 1.1.2.7 public NodePairSet copy() {
577 pnkfelix 1.1.2.12 NodePairSet__HashBased set = new NodePairSet__HashBased();
578 pnkfelix 1.1.2.7 set.pairs = (HashSet) pairs.clone();
579 pnkfelix 1.1.2.7 return set;
580 pnkfelix 1.1.2.7 }
581 pnkfelix 1.1.2.12 public HashSet pairs() { return (HashSet) pairs.clone(); }
582 pnkfelix 1.1.2.1 }
583 pnkfelix 1.1.2.1
584 pnkfelix 1.1.2.1 final static class NodeList {
585 pnkfelix 1.1.2.1 final static class Cons { Node elem; Cons next; }
586 pnkfelix 1.1.2.1 int size = 0;
587 pnkfelix 1.1.2.1 Cons first, last;
588 pnkfelix 1.1.2.7 NodeList() {}
589 pnkfelix 1.1.2.7 NodeList(List/*Node*/ ns) {
590 pnkfelix 1.1.2.7 for(Iterator i=ns.iterator(); i.hasNext();)
591 pnkfelix 1.1.2.7 add( (Node) i.next() );
592 pnkfelix 1.1.2.7 }
593 pnkfelix 1.1.2.1 void add(Node n) {
594 pnkfelix 1.1.2.1 Cons c = new Cons();
595 pnkfelix 1.1.2.1 c.elem = n;
596 pnkfelix 1.1.2.1 if (first == null) {
597 pnkfelix 1.1.2.1 first = last = c;
598 pnkfelix 1.1.2.1 } else {
599 pnkfelix 1.1.2.1 c.next = first;
600 pnkfelix 1.1.2.1 first = c;
601 pnkfelix 1.1.2.1 }
602 pnkfelix 1.1.2.1 size++;
603 pnkfelix 1.1.2.1 }
604 pnkfelix 1.1.2.1 /** INVALIDATES 'l' */
605 pnkfelix 1.1.2.1 void append(NodeList l) {
606 pnkfelix 1.1.2.1 last.next = l.first;
607 pnkfelix 1.1.2.1 last = l.last;
608 pnkfelix 1.1.2.1 l.first = null; l.last = null;
609 pnkfelix 1.1.2.1 size += l.size;
610 pnkfelix 1.1.2.1 }
611 pnkfelix 1.1.2.1 void checkRep() {
612 cananian 1.3.2.1 assert last.next == null;
613 pnkfelix 1.1.2.1 for(Cons curr = first; curr != last; curr = curr.next )
614 cananian 1.3.2.1 assert curr != null;
615 pnkfelix 1.1.2.1 }
616 pnkfelix 1.1.2.1 NodeIter iter() {
617 pnkfelix 1.1.2.1 return new NodeIter() {
618 pnkfelix 1.1.2.1 Cons c = first;
619 pnkfelix 1.1.2.1 public boolean hasNext() { return c != null; }
620 pnkfelix 1.1.2.1 public Node next() {
621 pnkfelix 1.1.2.1 Node n = c.elem; c = c.next; return n;
622 pnkfelix 1.1.2.1 }
623 pnkfelix 1.1.2.1 };
624 pnkfelix 1.1.2.1 }
625 pnkfelix 1.1.2.7 List toList() {
626 pnkfelix 1.1.2.7 ArrayList l = new ArrayList(size);
627 pnkfelix 1.1.2.7 for(NodeIter i=iter(); i.hasNext();)
628 pnkfelix 1.1.2.7 l.add(i.next());
629 pnkfelix 1.1.2.7 return l;
630 pnkfelix 1.1.2.7 }
631 pnkfelix 1.1.2.7 public String toString() { return "NodeList< "+toList()+" >"; }
632 pnkfelix 1.1.2.9 public String toStringWithIds() {
633 pnkfelix 1.1.2.9 StringBuffer sb = new StringBuffer();
634 pnkfelix 1.1.2.9 sb.append("[");
635 pnkfelix 1.1.2.9 for(NodeIter nbors = this.iter(); nbors.hasNext();){
636 pnkfelix 1.1.2.9 sb.append( nbors.next().id );
637 pnkfelix 1.1.2.9 sb.append(",");
638 pnkfelix 1.1.2.9 }
639 pnkfelix 1.1.2.9 sb.append("]");
640 pnkfelix 1.1.2.9 return sb.toString();
641 pnkfelix 1.1.2.9 }
642 pnkfelix 1.1.2.1 }
643 pnkfelix 1.1.2.1
644 pnkfelix 1.1.2.14 // these are setup in initializeNodeSets()
645 pnkfelix 1.1.2.14 private int nextId;
646 pnkfelix 1.1.2.14 private ArrayList allNodes;
647 pnkfelix 1.1.2.14 protected Node getNode(int i) { return (Node) allNodes.get(i-1); }
648 pnkfelix 1.1.2.14 private void addNode(Node n) { allNodes.add(n); }
649 pnkfelix 1.1.2.14 protected Iterator allNodes() { return allNodes.iterator(); }
650 pnkfelix 1.1.2.14
651 pnkfelix 1.1.2.14 protected final class Node {
652 pnkfelix 1.1.2.1 final int id;
653 pnkfelix 1.1.2.1
654 pnkfelix 1.1.2.1 // prev and next pointers for this node's set
655 pnkfelix 1.1.2.1 Node s_prev, s_next;
656 pnkfelix 1.1.2.1
657 pnkfelix 1.1.2.1 // Set Representative
658 pnkfelix 1.1.2.1 NodeSet s_rep;
659 pnkfelix 1.1.2.1
660 pnkfelix 1.1.2.1 // the degree of this in the interference graph
661 pnkfelix 1.1.2.1 int degree = 0;
662 pnkfelix 1.1.2.1
663 pnkfelix 1.1.2.1 // linked list of neighbors of this in interference graph
664 pnkfelix 1.1.2.1 NodeList neighbors = new NodeList();
665 pnkfelix 1.1.2.1
666 pnkfelix 1.1.2.1 // when a move (u,v) has been coalesced and v put into
667 pnkfelix 1.1.2.1 // coalescedNodes, then v.alias = u
668 pnkfelix 1.1.2.1 Node alias = null;
669 pnkfelix 1.1.2.1
670 pnkfelix 1.1.2.1 // list of moves this node is associated with
671 pnkfelix 1.1.2.1 MoveList moves = new MoveList();
672 pnkfelix 1.1.2.1
673 pnkfelix 1.1.2.11 // color of this, ( forall c in color, 0 <= c < K when assigned )
674 pnkfelix 1.1.2.11 // [ an array because some allocators associate multiple colors
675 pnkfelix 1.1.2.11 // with a node ]
676 pnkfelix 1.1.2.11 int[] color = new int[]{ -1 };
677 pnkfelix 1.1.2.1
678 pnkfelix 1.1.2.1 // Web for this (null if this is dummy header element)
679 pnkfelix 1.1.2.1 final Web web;
680 pnkfelix 1.1.2.1
681 pnkfelix 1.1.2.1 // for debugging purposes: a sequence of the node sets this
682 pnkfelix 1.1.2.1 // has been a member of during its lifetime
683 pnkfelix 1.1.2.1 java.util.LinkedList nodeSet_history = new java.util.LinkedList();
684 pnkfelix 1.1.2.1
685 pnkfelix 1.1.2.1 // special case for dummy nodes (for which 'w == null')
686 pnkfelix 1.1.2.1 public Node(Web w) {
687 pnkfelix 1.1.2.7 id = nextId; nextId++; s_prev = s_next = this; web = w;
688 pnkfelix 1.1.2.14
689 pnkfelix 1.1.2.14 addNode(this);
690 cananian 1.3.2.1 assert getNode(this.id) == this : this;
691 pnkfelix 1.1.2.14 }
692 pnkfelix 1.1.2.1
693 pnkfelix 1.1.2.1 public Node(NodeSet which, Web w) {
694 pnkfelix 1.1.2.1 this(w);
695 pnkfelix 1.1.2.1 which.add(this);
696 pnkfelix 1.1.2.1 }
697 pnkfelix 1.1.2.1
698 pnkfelix 1.1.2.1 boolean locked = false;
699 pnkfelix 1.1.2.1
700 pnkfelix 1.1.2.1 // machine registers, preassigned a color
701 pnkfelix 1.1.2.1 public boolean isPrecolored() {
702 pnkfelix 1.1.2.1 boolean r = s_rep == precolored;
703 cananian 1.3.2.1 if (r) assert color.length == 1 && color[0] != -1;
704 pnkfelix 1.1.2.1 return r;
705 pnkfelix 1.1.2.1 }
706 pnkfelix 1.1.2.1
707 pnkfelix 1.1.2.1 // temporary registers, not precolored and not yet processed
708 pnkfelix 1.1.2.1 public boolean isInitial() { return s_rep == initial; }
709 pnkfelix 1.1.2.1
710 pnkfelix 1.1.2.1 // list of low-degree non-move-related nodes
711 pnkfelix 1.1.2.1 public boolean isSimplifyWorkL() { return s_rep == simplify_worklist;}
712 pnkfelix 1.1.2.1
713 pnkfelix 1.1.2.1 // low-degree move-related nodes
714 pnkfelix 1.1.2.1 public boolean isFreezeWorkL() { return s_rep == freeze_worklist; }
715 pnkfelix 1.1.2.1
716 pnkfelix 1.1.2.1 // high-degree nodes
717 pnkfelix 1.1.2.1 public boolean isSpillWorkL() { return s_rep == spill_worklist; }
718 pnkfelix 1.1.2.1
719 pnkfelix 1.1.2.1 // nodes marked for spilling during this round
720 pnkfelix 1.1.2.1 public boolean isSpilled() { return s_rep == spilled_nodes; }
721 pnkfelix 1.1.2.1
722 pnkfelix 1.1.2.1 // registers that have been coalesced; when u <- v is
723 pnkfelix 1.1.2.1 // coalesced, v is added ot this set and u put back on some
724 pnkfelix 1.1.2.1 // work-list (or vice versa)
725 pnkfelix 1.1.2.1 public boolean isCoalesced() { return s_rep == coalesced_nodes; }
726 pnkfelix 1.1.2.1
727 pnkfelix 1.1.2.1 // nodes successfully colored
728 pnkfelix 1.1.2.1 public boolean isColored() {
729 pnkfelix 1.1.2.1 boolean r = s_rep == colored_nodes;
730 cananian 1.3.2.1 if (r) for(int i=0; i<color.length; i++) assert color[i] != -1;
731 pnkfelix 1.1.2.1 return r;
732 pnkfelix 1.1.2.1 }
733 pnkfelix 1.1.2.1
734 pnkfelix 1.1.2.1 // nodes on select stack
735 pnkfelix 1.1.2.1 public boolean isSelectStack() { return s_rep == select_stack; }
736 pnkfelix 1.1.2.1
737 pnkfelix 1.1.2.1 public String toString() {
738 pnkfelix 1.1.2.1 return "Node<"+
739 pnkfelix 1.1.2.1 "id:"+id+
740 pnkfelix 1.1.2.1 ", deg:"+degree+
741 pnkfelix 1.1.2.1 ", alias:"+alias+
742 pnkfelix 1.1.2.1 ", temp:"+((web==null)?"none":web.temp+"")+
743 pnkfelix 1.1.2.7 // ", history:"+nodeSet_history+
744 pnkfelix 1.1.2.1 ">";
745 pnkfelix 1.1.2.1 }
746 pnkfelix 1.1.2.1 }
747 pnkfelix 1.1.2.1
748 pnkfelix 1.1.2.5
749 pnkfelix 1.1.2.5
750 pnkfelix 1.1.2.5
751 pnkfelix 1.1.2.5 final class Move {
752 pnkfelix 1.1.2.5 Collection dsts() { return Collections.singleton(dst); }
753 pnkfelix 1.1.2.5 Collection srcs() { return Collections.singleton(src); }
754 pnkfelix 1.1.2.5 Node dst, src;
755 pnkfelix 1.1.2.5 Move s_prev, s_next;
756 pnkfelix 1.1.2.5 MoveSet s_rep; // Set Representative
757 pnkfelix 1.1.2.5 Instr instr = null; // null for dummy header Moves
758 pnkfelix 1.1.2.5
759 pnkfelix 1.1.2.5 // dummy ctor
760 pnkfelix 1.1.2.5 Move() { s_prev = s_next = this; }
761 pnkfelix 1.1.2.5
762 pnkfelix 1.1.2.5 Move(Instr i, Node dest, Node source) {
763 pnkfelix 1.1.2.5 this();
764 pnkfelix 1.1.2.5 instr = i;
765 pnkfelix 1.1.2.5 this.dst = dest;
766 pnkfelix 1.1.2.5 this.src = source;
767 pnkfelix 1.1.2.5 }
768 pnkfelix 1.1.2.5 public boolean isCoalesced() { return s_rep == coalesced_moves; }
769 pnkfelix 1.1.2.5 public boolean isConstrained() { return s_rep == constrained_moves; }
770 pnkfelix 1.1.2.5 public boolean isFrozen() { return s_rep == frozen_moves; }
771 pnkfelix 1.1.2.5 public boolean isWorklist() { return s_rep == worklist_moves; }
772 pnkfelix 1.1.2.5 public boolean isActive() { return s_rep == active_moves; }
773 pnkfelix 1.1.2.5
774 pnkfelix 1.1.2.5 public String toString() {
775 pnkfelix 1.1.2.5 // remove package info cruft from identity-based String
776 pnkfelix 1.1.2.5 String s = super.toString();
777 pnkfelix 1.1.2.5 int i = s.indexOf("Move");
778 pnkfelix 1.1.2.5 return
779 pnkfelix 1.1.2.5 s.substring(i)+
780 pnkfelix 1.1.2.9 " set:"+s_rep.name+
781 pnkfelix 1.1.2.5 " instr:"+instr;
782 pnkfelix 1.1.2.5 }
783 pnkfelix 1.1.2.5 }
784 pnkfelix 1.1.2.5
785 pnkfelix 1.1.2.5 MoveSet coalesced_moves;
786 pnkfelix 1.1.2.5 MoveSet constrained_moves;
787 pnkfelix 1.1.2.5 MoveSet frozen_moves;
788 pnkfelix 1.1.2.5 MoveSet worklist_moves;
789 pnkfelix 1.1.2.5 MoveSet active_moves;
790 pnkfelix 1.1.2.5 void checkMoveSets() {
791 pnkfelix 1.1.2.5 if( ! CHECK_INV )
792 pnkfelix 1.1.2.5 return;
793 pnkfelix 1.1.2.5
794 pnkfelix 1.1.2.5 MoveSet[] sets = new MoveSet[]{
795 pnkfelix 1.1.2.5 coalesced_moves,constrained_moves,
796 pnkfelix 1.1.2.5 frozen_moves,worklist_moves,
797 pnkfelix 1.1.2.5 active_moves
798 pnkfelix 1.1.2.5 };
799 pnkfelix 1.1.2.5 for(int i=0; i<sets.length; i++)
800 pnkfelix 1.1.2.5 sets[i].checkRep();
801 pnkfelix 1.1.2.5 }
802 pnkfelix 1.1.2.5
803 pnkfelix 1.1.2.5 // these sets collectively partition the space of Moves
804 pnkfelix 1.1.2.5 void initializeMoveSets() {
805 pnkfelix 1.1.2.5 coalesced_moves = new MoveSet("coalesced_moves");
806 pnkfelix 1.1.2.5 constrained_moves = new MoveSet("constrained_moves");
807 pnkfelix 1.1.2.5 frozen_moves = new MoveSet("frozen_moves");
808 pnkfelix 1.1.2.5 worklist_moves = new MoveSet("worklist_moves");
809 pnkfelix 1.1.2.5 active_moves = new MoveSet("active_moves");
810 pnkfelix 1.1.2.5 }
811 pnkfelix 1.1.2.5
812 pnkfelix 1.1.2.7 private void resetMoveSets() {
813 pnkfelix 1.1.2.5 // all sets except worklist_moves
814 pnkfelix 1.1.2.5 MoveSet[] sets = new MoveSet[]{
815 pnkfelix 1.1.2.5 coalesced_moves,constrained_moves,
816 pnkfelix 1.1.2.5 frozen_moves,active_moves
817 pnkfelix 1.1.2.5 };
818 pnkfelix 1.1.2.5 for(int i=0; i<sets.length; i++)
819 pnkfelix 1.1.2.5 while( ! sets[i].isEmpty() ) {
820 pnkfelix 1.1.2.5 sets[i].checkRep();
821 pnkfelix 1.1.2.5 worklist_moves.add( sets[i].pop() );
822 pnkfelix 1.1.2.5 }
823 pnkfelix 1.1.2.5 }
824 pnkfelix 1.1.2.5
825 pnkfelix 1.1.2.5 final class MoveSet {
826 pnkfelix 1.1.2.5 private int size;
827 pnkfelix 1.1.2.5 private Move head; // dummy element
828 pnkfelix 1.1.2.5 final String name;
829 pnkfelix 1.1.2.5 MoveSet(String name) {
830 pnkfelix 1.1.2.5 this.name = name;
831 pnkfelix 1.1.2.5 head = new Move();
832 pnkfelix 1.1.2.5 add_no_check_rep(head);
833 pnkfelix 1.1.2.5 size = 0;
834 pnkfelix 1.1.2.5 checkRep();
835 pnkfelix 1.1.2.5 }
836 pnkfelix 1.1.2.5
837 pnkfelix 1.1.2.5 void checkRep() {
838 pnkfelix 1.1.2.5 if( ! CHECK_INV )
839 pnkfelix 1.1.2.5 return;
840 pnkfelix 1.1.2.5
841 pnkfelix 1.1.2.5 Move curr = head;
842 pnkfelix 1.1.2.5 int checkSize = -1;
843 pnkfelix 1.1.2.5 do {
844 pnkfelix 1.1.2.5 checkSize++;
845 cananian 1.3.2.1 assert curr.s_next.s_prev == curr;
846 cananian 1.3.2.1 assert curr.s_next.s_prev == curr;
847 cananian 1.3.2.1 assert curr.s_rep == this;
848 pnkfelix 1.1.2.5 curr = curr.s_next;
849 pnkfelix 1.1.2.5 } while(curr != head);
850 pnkfelix 1.1.2.5 if (CHECK_INV)
851 cananian 1.3.2.1 assert size == checkSize : "size should be "+checkSize+" not "+size;
852 pnkfelix 1.1.2.5 }
853 pnkfelix 1.1.2.5 Iterator iter() {
854 cananian 1.6 return new UnmodifiableIterator() {
855 pnkfelix 1.1.2.5 Move curr = head;
856 pnkfelix 1.1.2.5 public boolean hasNext() { return curr.s_next != head; }
857 pnkfelix 1.1.2.5 public Object next() {
858 pnkfelix 1.1.2.5 Move n = curr.s_next;
859 pnkfelix 1.1.2.5 curr = curr.s_next;
860 pnkfelix 1.1.2.5 return n;
861 pnkfelix 1.1.2.5 }
862 pnkfelix 1.1.2.5 };
863 pnkfelix 1.1.2.5 }
864 pnkfelix 1.1.2.5 boolean isEmpty() { return size == 0; }
865 pnkfelix 1.1.2.5 Move pop() {
866 cananian 1.3.2.1 assert !isEmpty() : "should not be empty";
867 pnkfelix 1.1.2.5 Move n = head.s_next;
868 pnkfelix 1.1.2.5 if (CHECK_INV)
869 cananian 1.3.2.1 assert n!=head : "should not return head, "+
870 cananian 1.3.2.1 "size:"+size+" set:"+asSet();
871 pnkfelix 1.1.2.5 remove(n);
872 pnkfelix 1.1.2.5 return n;
873 pnkfelix 1.1.2.5 }
874 pnkfelix 1.1.2.5
875 pnkfelix 1.1.2.5 void remove(Move n) {
876 pnkfelix 1.1.2.5 checkRep();
877 pnkfelix 1.1.2.5 if (CHECK_INV)
878 cananian 1.3.2.1 assert n.s_rep == this : ("called "+this+".remove(..) "+
879 cananian 1.3.2.1 "on move:"+n+" in "+n.s_rep);
880 cananian 1.3.2.1 assert size != 0;
881 pnkfelix 1.1.2.5 n.s_prev.s_next = n.s_next;
882 pnkfelix 1.1.2.5 n.s_next.s_prev = n.s_prev;
883 pnkfelix 1.1.2.5 n.s_rep = null; n.s_prev = null; n.s_next = null;
884 pnkfelix 1.1.2.5 size--;
885 pnkfelix 1.1.2.5 checkRep();
886 pnkfelix 1.1.2.5 }
887 pnkfelix 1.1.2.5 void add(Move n) {
888 pnkfelix 1.1.2.5 checkRep();
889 pnkfelix 1.1.2.5 add_no_check_rep(n);
890 pnkfelix 1.1.2.5 checkRep();
891 pnkfelix 1.1.2.5 }
892 pnkfelix 1.1.2.5 private void add_no_check_rep(Move n){
893 pnkfelix 1.1.2.5 Move prev = head.s_prev;
894 pnkfelix 1.1.2.5 prev.s_next = n;
895 pnkfelix 1.1.2.5 n.s_prev = prev; n.s_next = head;
896 pnkfelix 1.1.2.5 n.s_rep = this;
897 pnkfelix 1.1.2.5 head.s_prev = n;
898 pnkfelix 1.1.2.5 size++;
899 pnkfelix 1.1.2.5 }
900 pnkfelix 1.1.2.5 Set asSet() {
901 pnkfelix 1.1.2.5 HashSet rtn = new HashSet();
902 pnkfelix 1.1.2.5 for(Iterator iter=iter(); iter.hasNext();)
903 pnkfelix 1.1.2.5 rtn.add(iter.next());
904 pnkfelix 1.1.2.5 return rtn;
905 pnkfelix 1.1.2.5 }
906 pnkfelix 1.1.2.9 Set asSortedSet() {
907 pnkfelix 1.1.2.9 java.util.TreeSet rtn = new java.util.TreeSet(new java.util.Comparator(){
908 pnkfelix 1.1.2.9 public int compare(Object o1, Object o2) {
909 pnkfelix 1.1.2.9 Move m1 = (Move) o1;
910 pnkfelix 1.1.2.9 Move m2 = (Move) o2;
911 pnkfelix 1.1.2.9 return m1.instr.getID() - m2.instr.getID();
912 pnkfelix 1.1.2.9 }});
913 pnkfelix 1.1.2.9 rtn.addAll( asSet() );
914 pnkfelix 1.1.2.9 return rtn;
915 pnkfelix 1.1.2.9 }
916 pnkfelix 1.1.2.9 public String toString() { return "MoveSet< "+name+", "+asSortedSet()+" >"; }
917 pnkfelix 1.1.2.5 }
918 cananian 1.9 static final class MoveList implements Iterable<Move> {
919 pnkfelix 1.1.2.5 final static class Cons { Move elem; Cons next; }
920 pnkfelix 1.1.2.5 Cons first;
921 pnkfelix 1.1.2.5 int size = 0;
922 pnkfelix 1.1.2.5 boolean isEmpty() {
923 pnkfelix 1.1.2.5 return size == 0;
924 pnkfelix 1.1.2.5 }
925 pnkfelix 1.1.2.7 MoveList() {}
926 pnkfelix 1.1.2.7 MoveList(List/*Move*/ ms) {
927 pnkfelix 1.1.2.7 for(Iterator i=ms.iterator(); i.hasNext();)
928 pnkfelix 1.1.2.7 add( (Move) i.next() );
929 pnkfelix 1.1.2.7 }
930 pnkfelix 1.1.2.5 void add(Move m) {
931 pnkfelix 1.1.2.5 Cons c = new Cons();
932 pnkfelix 1.1.2.5 c.elem = m;
933 pnkfelix 1.1.2.5 if (first == null) {
934 pnkfelix 1.1.2.5 first = c;
935 pnkfelix 1.1.2.5 } else {
936 pnkfelix 1.1.2.5 c.next = first;
937 pnkfelix 1.1.2.5 first = c;
938 pnkfelix 1.1.2.5 }
939 pnkfelix 1.1.2.5 size++;
940 pnkfelix 1.1.2.5 }
941 pnkfelix 1.1.2.5 /** INVALIDATES 'l' */
942 pnkfelix 1.1.2.5 void append(MoveList l) {
943 pnkfelix 1.1.2.5 Cons last = first;
944 pnkfelix 1.1.2.5 while(last.next != null)
945 pnkfelix 1.1.2.5 last = last.next;
946 pnkfelix 1.1.2.5
947 pnkfelix 1.1.2.5 last.next = l.first;
948 pnkfelix 1.1.2.5 size += l.size;
949 pnkfelix 1.1.2.5
950 pnkfelix 1.1.2.5 l.first = null;
951 pnkfelix 1.1.2.5 l.size = -1;
952 pnkfelix 1.1.2.5 }
953 cananian 1.9 public Iterator<Move> iterator() {
954 cananian 1.9 return new UnmodifiableIterator<Move>() {
955 pnkfelix 1.1.2.5 Cons c = first;
956 pnkfelix 1.1.2.5 public boolean hasNext() { return c != null; }
957 cananian 1.9 public Move next() { Move m=c.elem; c=c.next; return m;}
958 pnkfelix 1.1.2.5 };
959 pnkfelix 1.1.2.5 }
960 cananian 1.9 public List<Move> toList() {
961 cananian 1.9 java.util.ArrayList<Move> l = new java.util.ArrayList<Move>();
962 cananian 1.9 for(Iterator<Move> m=iterator(); m.hasNext(); ){
963 pnkfelix 1.1.2.5 l.add(m.next());
964 pnkfelix 1.1.2.5 }
965 cananian 1.9 l.trimToSize();
966 pnkfelix 1.1.2.7 return l;
967 pnkfelix 1.1.2.5 }
968 pnkfelix 1.1.2.7 public String toString() { return "MoveList< "+toList()+" >"; }
969 pnkfelix 1.1.2.5 }
970 pnkfelix 1.1.2.1
971 pnkfelix 1.1.2.1
972 cananian 1.2 }