1 pnkfelix 1.1.2.1 // GraphColoringRegAlloc.java, created Mon Jul 17 16:39:13 2000 by pnkfelix
2 cananian 1.1.2.44 // Copyright (C) 2000 Felix S. Klock II <pnkfelix@mit.edu>
3 pnkfelix 1.1.2.1 // 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.Analysis.Maps.Derivation;
7 pnkfelix 1.1.2.20 import harpoon.Backend.Maps.BackendDerivation;
8 pnkfelix 1.1.2.10 import harpoon.Analysis.DataFlow.LiveTemps;
9 pnkfelix 1.1.2.29 import harpoon.Analysis.DataFlow.SpaceHeavyLiveTemps;
10 pnkfelix 1.1.2.3 import harpoon.Analysis.ReachingDefs;
11 pnkfelix 1.1.2.4 import harpoon.Analysis.ReachingDefsAltImpl;
12 pnkfelix 1.1.2.5 import harpoon.Analysis.GraphColoring.AbstractGraph;
13 pnkfelix 1.1.2.5 import harpoon.Analysis.GraphColoring.ColorableGraph;
14 pnkfelix 1.1.2.5 import harpoon.Analysis.GraphColoring.Color;
15 pnkfelix 1.1.2.5 import harpoon.Analysis.GraphColoring.GraphColorer;
16 pnkfelix 1.1.2.11 import harpoon.Analysis.GraphColoring.OptimisticGraphColorer;
17 pnkfelix 1.1.2.5 import harpoon.Analysis.GraphColoring.SimpleGraphColorer;
18 pnkfelix 1.1.2.5 import harpoon.Analysis.GraphColoring.UnableToColorGraph;
19 pnkfelix 1.1.2.1 import harpoon.Backend.Generic.Code;
20 pnkfelix 1.1.2.5 import harpoon.Backend.Generic.RegFileInfo;
21 pnkfelix 1.1.2.20 import harpoon.ClassFile.HClass;
22 pnkfelix 1.1.2.20 import harpoon.ClassFile.HCodeElement;
23 pnkfelix 1.1.2.2 import harpoon.IR.Assem.Instr;
24 pnkfelix 1.1.2.31 import harpoon.IR.Assem.InstrFactory;
25 pnkfelix 1.1.2.2 import harpoon.Temp.Temp;
26 pnkfelix 1.1.2.31 import harpoon.Temp.TempMap;
27 pnkfelix 1.1.2.4 import harpoon.Util.Util;
28 cananian 1.5 import net.cscott.jutil.CombineIterator;
29 cananian 1.5 import net.cscott.jutil.FilterIterator;
30 cananian 1.5 import net.cscott.jutil.Default;
31 pnkfelix 1.1.2.5 import harpoon.Util.ArraySet;
32 cananian 1.5 import net.cscott.jutil.ListFactory;
33 cananian 1.5 import net.cscott.jutil.Factories;
34 cananian 1.5 import net.cscott.jutil.LinearSet;
35 cananian 1.5 import net.cscott.jutil.MultiMap;
36 cananian 1.5 import net.cscott.jutil.GenericMultiMap;
37 cananian 1.5 import net.cscott.jutil.InvertibleMap;
38 cananian 1.5 import net.cscott.jutil.GenericInvertibleMap;
39 pnkfelix 1.1.2.1
40 pnkfelix 1.1.2.5 import java.util.Arrays;
41 pnkfelix 1.1.2.2 import java.util.Map;
42 pnkfelix 1.1.2.2 import java.util.HashMap;
43 pnkfelix 1.1.2.2 import java.util.Set;
44 pnkfelix 1.1.2.5 import java.util.AbstractSet;
45 pnkfelix 1.1.2.2 import java.util.HashSet;
46 pnkfelix 1.1.2.2 import java.util.List;
47 pnkfelix 1.1.2.6 import java.util.AbstractList;
48 pnkfelix 1.1.2.4 import java.util.ArrayList;
49 pnkfelix 1.1.2.2 import java.util.LinkedList;
50 pnkfelix 1.1.2.2 import java.util.Iterator;
51 pnkfelix 1.1.2.2 import java.util.Collection;
52 pnkfelix 1.1.2.8 import java.util.AbstractCollection;
53 pnkfelix 1.1.2.2 import java.util.Collections;
54 pnkfelix 1.1.2.33 import java.util.Date;
55 pnkfelix 1.1.2.6
56 pnkfelix 1.1.2.1 /**
57 pnkfelix 1.1.2.6 * <code>GraphColoringRegAlloc</code> uses graph coloring heuristics
58 pnkfelix 1.1.2.6 * to find a register assignment for a Code.
59 pnkfelix 1.1.2.1 *
60 cananian 1.1.2.44 * @author Felix S. Klock II <pnkfelix@mit.edu>
61 cananian 1.6 * @version $Id: GraphColoringRegAlloc.java,v 1.6 2004/02/08 03:19:37 cananian Exp $
62 pnkfelix 1.1.2.1 */
63 pnkfelix 1.1.2.1 public class GraphColoringRegAlloc extends RegAlloc {
64 pnkfelix 1.1.2.24
65 pnkfelix 1.1.2.36 // Information output control flags
66 pnkfelix 1.1.2.36 private static final boolean TIME = false;
67 pnkfelix 1.1.2.19 private static final boolean RESULTS = false;
68 pnkfelix 1.1.2.28 private static final boolean SPILL_INFO = false;
69 pnkfelix 1.1.2.23 private static final boolean STATS = false;
70 pnkfelix 1.1.2.32 private static final boolean COALESCE_STATS = false;
71 pnkfelix 1.1.2.34 private static final boolean SCARY_OUTPUT = false;
72 pnkfelix 1.1.2.38 private static final boolean UNIFY_INFO = false;
73 pnkfelix 1.1.2.34
74 pnkfelix 1.1.2.36 // Code output control flags
75 pnkfelix 1.1.2.39 private static final boolean DEF_COALESCE_MOVES = true;
76 pnkfelix 1.1.2.41 private static final boolean COALESCE_MACH_REGS = false;
77 pnkfelix 1.1.2.39
78 pnkfelix 1.1.2.39 private boolean COALESCE_MOVES = DEF_COALESCE_MOVES;
79 pnkfelix 1.1.2.39
80 pnkfelix 1.1.2.39 static RegAlloc.Factory BRAINDEAD_FACTORY =
81 pnkfelix 1.1.2.39 new RegAlloc.Factory() {
82 pnkfelix 1.1.2.39 public RegAlloc makeRegAlloc(Code c) {
83 pnkfelix 1.1.2.39 GraphColorer gc;
84 pnkfelix 1.1.2.39
85 pnkfelix 1.1.2.39 // gc = new SimpleGraphColorer();
86 pnkfelix 1.1.2.39
87 pnkfelix 1.1.2.39 // TODO: Implement a Node Selector that will not
88 pnkfelix 1.1.2.39 // select nodes that have already been spilled in the
89 pnkfelix 1.1.2.39 // code, and pass it in here...
90 pnkfelix 1.1.2.39 NodeSelector ns = new NodeSelector();
91 pnkfelix 1.1.2.39 gc = new OptimisticGraphColorer(ns);
92 pnkfelix 1.1.2.39 ns.gcra = new GraphColoringRegAlloc(c, gc, true);
93 pnkfelix 1.1.2.39 ns.gcra.COALESCE_MOVES = false;
94 pnkfelix 1.1.2.39 return ns.gcra;
95 pnkfelix 1.1.2.39 }
96 pnkfelix 1.1.2.39 };
97 pnkfelix 1.1.2.36
98 pnkfelix 1.1.2.34 static RegAlloc.Factory AGGRESSIVE_FACTORY =
99 pnkfelix 1.1.2.34 new RegAlloc.Factory() {
100 pnkfelix 1.1.2.34 public RegAlloc makeRegAlloc(Code c) {
101 pnkfelix 1.1.2.34 GraphColorer gc;
102 pnkfelix 1.1.2.34
103 pnkfelix 1.1.2.34 // gc = new SimpleGraphColorer();
104 pnkfelix 1.1.2.34
105 pnkfelix 1.1.2.34 // TODO: Implement a Node Selector that will not
106 pnkfelix 1.1.2.34 // select nodes that have already been spilled in the
107 pnkfelix 1.1.2.34 // code, and pass it in here...
108 pnkfelix 1.1.2.34 NodeSelector ns = new NodeSelector();
109 pnkfelix 1.1.2.34 gc = new OptimisticGraphColorer(ns);
110 pnkfelix 1.1.2.34 ns.gcra = new GraphColoringRegAlloc(c, gc, true);
111 pnkfelix 1.1.2.34
112 pnkfelix 1.1.2.34 return ns.gcra;
113 pnkfelix 1.1.2.34 }
114 pnkfelix 1.1.2.34 };
115 pnkfelix 1.1.2.34
116 pnkfelix 1.1.2.5 public static RegAlloc.Factory FACTORY =
117 pnkfelix 1.1.2.5 new RegAlloc.Factory() {
118 pnkfelix 1.1.2.5 public RegAlloc makeRegAlloc(Code c) {
119 pnkfelix 1.1.2.11 GraphColorer gc;
120 pnkfelix 1.1.2.11
121 pnkfelix 1.1.2.11 // gc = new SimpleGraphColorer();
122 pnkfelix 1.1.2.11
123 pnkfelix 1.1.2.28 // TODO: Implement a Node Selector that will not
124 pnkfelix 1.1.2.28 // select nodes that have already been spilled in the
125 pnkfelix 1.1.2.28 // code, and pass it in here...
126 pnkfelix 1.1.2.28 NodeSelector ns = new NodeSelector();
127 pnkfelix 1.1.2.28 gc = new OptimisticGraphColorer(ns);
128 pnkfelix 1.1.2.28 ns.gcra = new GraphColoringRegAlloc(c, gc);
129 pnkfelix 1.1.2.28
130 pnkfelix 1.1.2.28 return ns.gcra;
131 pnkfelix 1.1.2.4 }
132 pnkfelix 1.1.2.5 };
133 pnkfelix 1.1.2.5
134 pnkfelix 1.1.2.28 static class NodeSelector extends OptimisticGraphColorer.SimpleSelector {
135 pnkfelix 1.1.2.28 GraphColoringRegAlloc gcra;
136 pnkfelix 1.1.2.30 public boolean allowedToRemove(Object n, ColorableGraph g) {
137 pnkfelix 1.1.2.31 return gcra.isAvailableToSpill( n );
138 pnkfelix 1.1.2.30 }
139 pnkfelix 1.1.2.29 public Object chooseNodeForHiding(ColorableGraph g) {
140 pnkfelix 1.1.2.29 HashSet l = new HashSet();
141 pnkfelix 1.1.2.29 Object n = super.chooseNodeForHiding(g);
142 pnkfelix 1.1.2.31 while (!gcra.isAvailableToSpill(n)) {
143 pnkfelix 1.1.2.29 // delay hiding spilled nodes as long as possible
144 pnkfelix 1.1.2.33 // System.out.println("DELAY "+n);
145 pnkfelix 1.1.2.29 g.hide(n);
146 pnkfelix 1.1.2.29 l.add(n);
147 pnkfelix 1.1.2.29 Object _n = super.chooseNodeForHiding(g);
148 pnkfelix 1.1.2.29 if (_n == null)
149 pnkfelix 1.1.2.29 break;
150 pnkfelix 1.1.2.29 else
151 pnkfelix 1.1.2.29 n = _n;
152 pnkfelix 1.1.2.29 }
153 pnkfelix 1.1.2.29 Object _n; if (!l.isEmpty()) do {
154 pnkfelix 1.1.2.29 _n = g.replace();
155 pnkfelix 1.1.2.29 } while(l.contains(_n));
156 pnkfelix 1.1.2.31 //System.out.println("HIDE:"+n);
157 pnkfelix 1.1.2.29 return n;
158 pnkfelix 1.1.2.29 }
159 pnkfelix 1.1.2.29
160 pnkfelix 1.1.2.28 public Object chooseNodeForRemoval(ColorableGraph g) {
161 pnkfelix 1.1.2.28 Object spillChoice = null;
162 pnkfelix 1.1.2.28 Set nset = g.nodeSet();
163 pnkfelix 1.1.2.28 int maxDegree = -1;
164 pnkfelix 1.1.2.28 for(Iterator ns=nset.iterator(); ns.hasNext(); ) {
165 pnkfelix 1.1.2.28 Object n = ns.next();
166 pnkfelix 1.1.2.28 if (g.getColor(n) == null &&
167 pnkfelix 1.1.2.28 g.getDegree(n) > maxDegree) {
168 pnkfelix 1.1.2.31 if (gcra.isAvailableToSpill(n)) { // <= THIS IS KEY
169 pnkfelix 1.1.2.28 spillChoice = n;
170 pnkfelix 1.1.2.28 maxDegree = g.getDegree(n);
171 pnkfelix 1.1.2.29 }
172 pnkfelix 1.1.2.29 }
173 pnkfelix 1.1.2.29 }
174 pnkfelix 1.1.2.29 if(spillChoice == null) {
175 pnkfelix 1.1.2.29 // backup strategy : spill COLORED nodes
176 pnkfelix 1.1.2.29 for(Iterator ns=nset.iterator(); ns.hasNext(); ) {
177 pnkfelix 1.1.2.29 Object n = ns.next();
178 pnkfelix 1.1.2.29 if (g.getDegree(n) > maxDegree) {
179 pnkfelix 1.1.2.31 if (gcra.isAvailableToSpill(n)) { // <= THIS IS KEY
180 pnkfelix 1.1.2.29 spillChoice = n;
181 pnkfelix 1.1.2.29 maxDegree = g.getDegree(n);
182 pnkfelix 1.1.2.29 } else {
183 pnkfelix 1.1.2.34 if (SCARY_OUTPUT) System.out.println
184 pnkfelix 1.1.2.29 ("SKIP (2) "+n+" (already spilled)");
185 pnkfelix 1.1.2.29 }
186 pnkfelix 1.1.2.29 }
187 pnkfelix 1.1.2.29 }
188 pnkfelix 1.1.2.29 }
189 pnkfelix 1.1.2.29 if(spillChoice == null) {
190 pnkfelix 1.1.2.29 // backup strategy : spill HIDDEN node
191 pnkfelix 1.1.2.29 LinkedList rehide = new LinkedList();
192 pnkfelix 1.1.2.29 for(Object n=g.replace(); n!=null; n=g.replace()) {
193 pnkfelix 1.1.2.29 rehide.addLast(n);
194 pnkfelix 1.1.2.29 if (g.getDegree(n) > maxDegree) {
195 pnkfelix 1.1.2.31 if (gcra.isAvailableToSpill(n)) {
196 pnkfelix 1.1.2.29 spillChoice = n;
197 pnkfelix 1.1.2.29 maxDegree = g.getDegree(n);
198 pnkfelix 1.1.2.29 } else {
199 pnkfelix 1.1.2.34 if (SCARY_OUTPUT) System.out.println
200 pnkfelix 1.1.2.29 ("SKIP (3) "+n+" (already spilled)");
201 pnkfelix 1.1.2.29 }
202 pnkfelix 1.1.2.28 }
203 pnkfelix 1.1.2.28 }
204 pnkfelix 1.1.2.29 while(!rehide.isEmpty()) {
205 pnkfelix 1.1.2.29 g.hide(rehide.removeLast());
206 pnkfelix 1.1.2.29 }
207 pnkfelix 1.1.2.28 }
208 pnkfelix 1.1.2.28 if(spillChoice == null) {
209 pnkfelix 1.1.2.29 // wtf? Are ALL the nodes spilled?
210 pnkfelix 1.1.2.29 for(Iterator ns=g.nodeSet().iterator();ns.hasNext();){
211 pnkfelix 1.1.2.29 Object n = ns.next();
212 cananian 1.3.2.1 assert !gcra.isAvailableToSpill(n);
213 pnkfelix 1.1.2.29 }
214 pnkfelix 1.1.2.29 LinkedList rehide = new LinkedList();
215 pnkfelix 1.1.2.29 for(Object n=g.replace(); n!=null; n=g.replace()) {
216 pnkfelix 1.1.2.29 rehide.addLast(n);
217 cananian 1.3.2.1 assert !gcra.isAvailableToSpill(n);
218 pnkfelix 1.1.2.29 }
219 pnkfelix 1.1.2.29 while(!rehide.isEmpty()) {
220 pnkfelix 1.1.2.29 g.hide(rehide.removeLast());
221 pnkfelix 1.1.2.29 }
222 pnkfelix 1.1.2.28 }
223 pnkfelix 1.1.2.31 //System.out.println("SPILL:"+spillChoice);
224 pnkfelix 1.1.2.28 return spillChoice;
225 pnkfelix 1.1.2.28 }
226 pnkfelix 1.1.2.28 }
227 pnkfelix 1.1.2.28
228 pnkfelix 1.1.2.5 private static final int INITIAL_DISPLACEMENT = 0;
229 pnkfelix 1.1.2.4
230 pnkfelix 1.1.2.2 double defWt, useWt, copyWt;
231 pnkfelix 1.1.2.5 int baseReg;
232 pnkfelix 1.1.2.2 int disp = INITIAL_DISPLACEMENT, argReg;
233 pnkfelix 1.1.2.2 List stack; // List<Integer>
234 pnkfelix 1.1.2.6 Map realReg; // Integer -> Integer
235 pnkfelix 1.1.2.1
236 pnkfelix 1.1.2.5 final RegFileInfo rfi;
237 pnkfelix 1.1.2.9 ReachingDefs rdefs;
238 pnkfelix 1.1.2.10 LiveTemps liveTemps;
239 pnkfelix 1.1.2.5
240 pnkfelix 1.1.2.13 // TYPES IN COMMENTS
241 pnkfelix 1.1.2.13 // Reg : All r in Temp such that isRegister(r)
242 pnkfelix 1.1.2.13 // VReg : Temp - Reg
243 pnkfelix 1.1.2.13 // AReg : All r such that Exists some t in Temp such that
244 pnkfelix 1.1.2.13 // rfi.getRegAssignments(t) contains some
245 pnkfelix 1.1.2.13 // List<Reg>, l, such that r is in l.
246 pnkfelix 1.1.2.13 // Assign : List<AReg>
247 pnkfelix 1.1.2.13 // SysReg : Reg - AReg
248 pnkfelix 1.1.2.5
249 pnkfelix 1.1.2.13 MultiMap regToDefs; // Reg -> Instr
250 pnkfelix 1.1.2.13 MultiMap regToUses; // Reg -> Instr
251 pnkfelix 1.1.2.15
252 pnkfelix 1.1.2.29 // used to associate a VReg with the available register
253 pnkfelix 1.1.2.29 // assignments for its components.
254 pnkfelix 1.1.2.29 // VReg maps to an array of Maps, where the array-indices
255 pnkfelix 1.1.2.29 // correspond to component indices in the assignment.
256 pnkfelix 1.1.2.29 Map implicitAssigns; // VReg -> (AReg -> Assign)[]
257 pnkfelix 1.1.2.15
258 pnkfelix 1.1.2.15
259 pnkfelix 1.1.2.27 InvertibleMap webPrecolor; // WebRecord -> AReg
260 pnkfelix 1.1.2.13 Map regToColor; // AReg -> RegColor
261 pnkfelix 1.1.2.27 Map regToWeb; // AReg -> RegWebRecord
262 pnkfelix 1.1.2.5
263 pnkfelix 1.1.2.18 Map ixtToWebPreCombine; // Instr x VReg -> WebRecord
264 pnkfelix 1.1.2.18 Map ixtToWeb; // Instr x VReg -> WebRecord
265 pnkfelix 1.1.2.6 List webRecords; // List<WebRecord>
266 pnkfelix 1.1.2.6
267 pnkfelix 1.1.2.6 List tempWebRecords; // List<TempWebRecord>
268 pnkfelix 1.1.2.13 List regWebRecords; // List<RegWebRecord>
269 pnkfelix 1.1.2.5
270 pnkfelix 1.1.2.11 GraphColorer colorer;
271 pnkfelix 1.1.2.11
272 pnkfelix 1.1.2.34 private boolean aggressivelyCoalesce;
273 pnkfelix 1.1.2.34
274 pnkfelix 1.1.2.26 private WebRecord getWR(Instr i, Temp t) {
275 pnkfelix 1.1.2.26 if (isRegister(t)) {
276 cananian 1.6 for(Object rO : regWebRecords){
277 cananian 1.6 WebRecord r = (WebRecord) rO;
278 pnkfelix 1.1.2.26 if (r.temp().equals(t))
279 pnkfelix 1.1.2.26 return r;
280 pnkfelix 1.1.2.26 }
281 pnkfelix 1.1.2.26 return null;
282 pnkfelix 1.1.2.26 } else {
283 pnkfelix 1.1.2.26 return (WebRecord) ixtToWeb.get(Default.pair(i,t));
284 pnkfelix 1.1.2.26 }
285 pnkfelix 1.1.2.26 }
286 pnkfelix 1.1.2.26
287 pnkfelix 1.1.2.11 /** Creates a <code>GraphColoringRegAlloc</code>, assigning `gc'
288 pnkfelix 1.1.2.34 as its graph coloring strategy and using a overly conservative
289 pnkfelix 1.1.2.34 move coalescing strategy.
290 pnkfelix 1.1.2.11 */
291 pnkfelix 1.1.2.11 public GraphColoringRegAlloc(Code code, GraphColorer gc) {
292 pnkfelix 1.1.2.34 this(code, gc, false);
293 pnkfelix 1.1.2.34 }
294 pnkfelix 1.1.2.34
295 pnkfelix 1.1.2.34 /** Creates a <code>GraphColoringRegAlloc</code>, assigning `gc'
296 pnkfelix 1.1.2.34 as its graph coloring strategy. If
297 pnkfelix 1.1.2.34 <code>aggressiveCoalesce</code> is true, will choose to
298 pnkfelix 1.1.2.34 coalesce moves in the face of increased memory traffic.
299 pnkfelix 1.1.2.34 */
300 pnkfelix 1.1.2.34 public GraphColoringRegAlloc(Code code, GraphColorer gc,
301 pnkfelix 1.1.2.34 boolean aggressiveCoalesce) {
302 pnkfelix 1.1.2.1 super(code);
303 pnkfelix 1.1.2.5 rfi = frame.getRegFileInfo();
304 pnkfelix 1.1.2.11 colorer = gc;
305 pnkfelix 1.1.2.34 aggressivelyCoalesce = aggressiveCoalesce;
306 pnkfelix 1.1.2.1 }
307 pnkfelix 1.1.2.34
308 pnkfelix 1.1.2.37 private LinkedList replOrigPairs = new LinkedList();
309 pnkfelix 1.1.2.43 protected void replace(Instr orig, Instr repl) {
310 pnkfelix 1.1.2.43 super.replace(orig, repl);
311 pnkfelix 1.1.2.37 replOrigPairs.addFirst(Default.pair(repl, orig));
312 pnkfelix 1.1.2.31 }
313 pnkfelix 1.1.2.31 private void undoCoalescing() {
314 pnkfelix 1.1.2.34 if (SCARY_OUTPUT) System.out.print(" UNDO");
315 cananian 1.6 for(Object prO : replOrigPairs){
316 cananian 1.6 List pr = (List) prO;
317 pnkfelix 1.1.2.37 Instr repl = (Instr) pr.get(0);
318 pnkfelix 1.1.2.37 Instr orig = (Instr) pr.get(1);
319 pnkfelix 1.1.2.36 // System.out.println("UNDO: replacing "+repl+" w/ "+orig);
320 pnkfelix 1.1.2.36 // System.out.println("==:"+(repl==orig)+" equls:"+repl.equals(orig));
321 pnkfelix 1.1.2.31 Instr.replace(repl, orig);
322 pnkfelix 1.1.2.31 }
323 pnkfelix 1.1.2.37 replOrigPairs.clear();
324 pnkfelix 1.1.2.31 willRemoveLater.clear();
325 pnkfelix 1.1.2.32 webPrecolor.clear();
326 pnkfelix 1.1.2.32 // remap = EqTempSets.make(this, false);
327 pnkfelix 1.1.2.32 remap = new EqWebRecords();
328 pnkfelix 1.1.2.28 }
329 pnkfelix 1.1.2.28
330 pnkfelix 1.1.2.5 protected Derivation getDerivation() {
331 pnkfelix 1.1.2.20 final Derivation oldD = code.getDerivation();
332 pnkfelix 1.1.2.20 return new BackendDerivation() {
333 pnkfelix 1.1.2.20 private HCodeElement orig(HCodeElement h){
334 pnkfelix 1.1.2.20 return getBack((Instr)h);
335 pnkfelix 1.1.2.20 }
336 pnkfelix 1.1.2.28 private Temp orig(HCodeElement h, Temp t) {
337 cananian 1.3.2.1 assert false;
338 pnkfelix 1.1.2.28 Temp t2 = null;
339 pnkfelix 1.1.2.28 Instr inst = (Instr) orig(h);
340 pnkfelix 1.1.2.28 Iterator rs = new
341 pnkfelix 1.1.2.28 CombineIterator(inst.defC().iterator(),
342 pnkfelix 1.1.2.28 inst.useC().iterator());
343 pnkfelix 1.1.2.28 while(rs.hasNext()) {
344 pnkfelix 1.1.2.28 t2 = (Temp) rs.next();
345 pnkfelix 1.1.2.32 // if (remap.tempMap(t2).equals(t))
346 pnkfelix 1.1.2.28 break;
347 pnkfelix 1.1.2.28 }
348 cananian 1.3.2.1 assert t2 != null;
349 pnkfelix 1.1.2.28 return t2;
350 pnkfelix 1.1.2.28 }
351 pnkfelix 1.1.2.20 public HClass typeMap(HCodeElement hce, Temp t) {
352 pnkfelix 1.1.2.20 HCodeElement hce2 = orig(hce);
353 pnkfelix 1.1.2.28 Temp t2 = orig(hce, t);
354 pnkfelix 1.1.2.28 return oldD.typeMap(hce2, t2);
355 pnkfelix 1.1.2.20 }
356 pnkfelix 1.1.2.20 public Derivation.DList derivation(HCodeElement hce, Temp t) {
357 pnkfelix 1.1.2.20 HCodeElement hce2 = orig(hce);
358 pnkfelix 1.1.2.28 Temp t2 = orig(hce, t);
359 pnkfelix 1.1.2.28 try {
360 pnkfelix 1.1.2.28 return Derivation.DList.rename
361 pnkfelix 1.1.2.32 (oldD.derivation(hce2, t2), null); // remap);
362 pnkfelix 1.1.2.28 } catch (TypeNotKnownException e) {
363 pnkfelix 1.1.2.28 System.out.println("called derivation("+hce+","+t+")");
364 pnkfelix 1.1.2.28 System.out.println("die on derivation("+hce2+","+t2+")");
365 pnkfelix 1.1.2.28 throw e;
366 pnkfelix 1.1.2.28 }
367 pnkfelix 1.1.2.20 }
368 pnkfelix 1.1.2.20 public BackendDerivation.Register
369 pnkfelix 1.1.2.20 calleeSaveRegister(HCodeElement hce, Temp t) {
370 pnkfelix 1.1.2.20 hce = orig(hce);
371 pnkfelix 1.1.2.20 return ((BackendDerivation)oldD).calleeSaveRegister(hce, t);
372 pnkfelix 1.1.2.20 }
373 pnkfelix 1.1.2.20 };
374 pnkfelix 1.1.2.5 }
375 pnkfelix 1.1.2.5
376 pnkfelix 1.1.2.10 /** Returns a new Collection cr, where
377 pnkfelix 1.1.2.10 for all e element of edges
378 pnkfelix 1.1.2.10 there exists a unique c element of cr such that
379 pnkfelix 1.1.2.10 c = [nodeToNum(e.get(0)), nodeToNum(e.get(1))]
380 pnkfelix 1.1.2.10 */
381 pnkfelix 1.1.2.28 private static Collection readableEdges(final Collection edges,
382 pnkfelix 1.1.2.28 final Map nodeToNum) {
383 pnkfelix 1.1.2.10 return new AbstractCollection() {
384 pnkfelix 1.1.2.10 public int size() { return edges.size(); }
385 pnkfelix 1.1.2.10 public Iterator iterator() {
386 pnkfelix 1.1.2.29 final int sz = size();
387 pnkfelix 1.1.2.10 return new FilterIterator
388 pnkfelix 1.1.2.10 (edges.iterator(),
389 pnkfelix 1.1.2.10 new FilterIterator.Filter() {
390 pnkfelix 1.1.2.10 public Object map(Object o) {
391 pnkfelix 1.1.2.10 List l=(List)o;
392 pnkfelix 1.1.2.10 return Default.pair(nodeToNum.get(l.get(0)),
393 pnkfelix 1.1.2.10 nodeToNum.get(l.get(1)));
394 pnkfelix 1.1.2.10 }});
395 pnkfelix 1.1.2.10 }
396 pnkfelix 1.1.2.10 };
397 pnkfelix 1.1.2.10 }
398 pnkfelix 1.1.2.28 private static Collection readableNodes(final Collection nodes,
399 pnkfelix 1.1.2.28 final Map nodeToNum) {
400 pnkfelix 1.1.2.11 return new AbstractCollection() {
401 pnkfelix 1.1.2.11 public int size() { return nodes.size(); }
402 pnkfelix 1.1.2.11 public Iterator iterator() {
403 pnkfelix 1.1.2.11 return new FilterIterator
404 pnkfelix 1.1.2.11 (nodes.iterator(),
405 pnkfelix 1.1.2.11 new FilterIterator.Filter() {
406 pnkfelix 1.1.2.11 public Object map(Object o) {
407 pnkfelix 1.1.2.11 return nodeToNum.get(o);
408 pnkfelix 1.1.2.11 }
409 pnkfelix 1.1.2.11 });
410 pnkfelix 1.1.2.11 }
411 pnkfelix 1.1.2.11 };
412 pnkfelix 1.1.2.11 }
413 pnkfelix 1.1.2.11
414 pnkfelix 1.1.2.10
415 pnkfelix 1.1.2.1 protected void generateRegAssignment() {
416 pnkfelix 1.1.2.1 boolean success, coalesced;
417 pnkfelix 1.1.2.28 AdjMtx adjMtx = null;
418 pnkfelix 1.1.2.28
419 pnkfelix 1.1.2.36 boolean doCoalescing = COALESCE_MOVES; // HACK
420 pnkfelix 1.1.2.28
421 pnkfelix 1.1.2.24 if (TIME) System.out.println();
422 pnkfelix 1.1.2.22
423 pnkfelix 1.1.2.27
424 pnkfelix 1.1.2.1 do {
425 pnkfelix 1.1.2.1 do {
426 pnkfelix 1.1.2.26 buildRegAssigns();
427 pnkfelix 1.1.2.41 if (TIME) System.out.println("ReachingDefs \t\t"+new Date());
428 pnkfelix 1.1.2.26 rdefs = new ReachingDefsAltImpl(code);
429 pnkfelix 1.1.2.41 if (TIME) System.out.println("LiveTemps \t\t"+new Date());
430 pnkfelix 1.1.2.29 liveTemps = SpaceHeavyLiveTemps.make(code, rfi.liveOnExit());
431 pnkfelix 1.1.2.26 ixtToWeb = new HashMap();
432 pnkfelix 1.1.2.26 ixtToWebPreCombine = new HashMap();
433 pnkfelix 1.1.2.27 webPrecolor = new GenericInvertibleMap();
434 pnkfelix 1.1.2.18
435 pnkfelix 1.1.2.33 if (TIME) System.out.println("Making Webs \t\t"+new Date());
436 pnkfelix 1.1.2.11
437 pnkfelix 1.1.2.5 makeWebs(rdefs);
438 pnkfelix 1.1.2.21
439 pnkfelix 1.1.2.21 // ASSERTION CHECKING LOOPS
440 pnkfelix 1.1.2.21 for(int k=0; k<webRecords.size(); k++) {
441 cananian 1.3.2.1 assert ((WebRecord)webRecords.get(k)).sreg() == k;
442 pnkfelix 1.1.2.21 }
443 pnkfelix 1.1.2.12 for(Iterator is=code.getElementsI(); is.hasNext();){
444 pnkfelix 1.1.2.12 Instr i = (Instr) is.next();
445 pnkfelix 1.1.2.26
446 cananian 1.6 for(Object tO : i.defC()) {
447 cananian 1.6 Temp t = (Temp) tO;
448 pnkfelix 1.1.2.12 if (! isRegister(t) ) {
449 pnkfelix 1.1.2.12 List ixt = Default.pair(i,t);
450 pnkfelix 1.1.2.12 WebRecord web = (WebRecord)ixtToWeb.get(ixt);
451 pnkfelix 1.1.2.12 if (web == null) {
452 cananian 1.3.2.1 assert ixtToWebPreCombine.get(ixt)==null : "There was a web for "+ixt+
453 pnkfelix 1.1.2.12 " pre-combination! "+
454 cananian 1.3.2.1 ixtToWebPreCombine.get(ixt);
455 cananian 1.3.2.1 assert false : ("no web for i:"+i+", t:"+t);
456 pnkfelix 1.1.2.12 }
457 pnkfelix 1.1.2.12 }
458 pnkfelix 1.1.2.12 }
459 cananian 1.6 for(Object tO : i.useC()) {
460 cananian 1.6 Temp t = (Temp) tO;
461 pnkfelix 1.1.2.12 if (! isRegister(t) ) {
462 pnkfelix 1.1.2.12 WebRecord web = (WebRecord)
463 pnkfelix 1.1.2.12 ixtToWeb.get(Default.pair(i,t));
464 cananian 1.3.2.1 assert web != null : ("no web for i:"+i+", t:"+t);
465 pnkfelix 1.1.2.12 }
466 pnkfelix 1.1.2.12 }
467 pnkfelix 1.1.2.21 }
468 pnkfelix 1.1.2.21 // END ASSERTION CHECKING LOOPS
469 pnkfelix 1.1.2.21
470 pnkfelix 1.1.2.7 // System.out.println("webs: "+webRecords);
471 pnkfelix 1.1.2.5
472 pnkfelix 1.1.2.33 if(TIME)System.out.println("Building Matrix \t"+new Date());
473 pnkfelix 1.1.2.11
474 pnkfelix 1.1.2.28
475 pnkfelix 1.1.2.41 adjMtx = buildAdjMatrix();
476 pnkfelix 1.1.2.33
477 pnkfelix 1.1.2.41 if(TIME)printConflictTime();
478 pnkfelix 1.1.2.41
479 pnkfelix 1.1.2.33 if(TIME)System.out.println("Adjacency Matrix Built \t"+new Date());
480 pnkfelix 1.1.2.7 // System.out.println(adjMtx);
481 pnkfelix 1.1.2.28 if (doCoalescing) {
482 pnkfelix 1.1.2.33 if(TIME)System.out.println("Coalescing Registers \t"+new Date());
483 pnkfelix 1.1.2.28 Set coal = coalesceRegs(adjMtx);
484 pnkfelix 1.1.2.31 coalesced = !coal.isEmpty();
485 pnkfelix 1.1.2.28 } else {
486 pnkfelix 1.1.2.28 coalesced = false;
487 pnkfelix 1.1.2.28 }
488 pnkfelix 1.1.2.41 if(TIME)printConflictTime();
489 pnkfelix 1.1.2.1 } while (coalesced);
490 pnkfelix 1.1.2.5
491 pnkfelix 1.1.2.33 if(TIME)System.out.println("Building Lists \t\t"+new Date());
492 pnkfelix 1.1.2.11
493 pnkfelix 1.1.2.6 WebRecord[] adjLsts = buildAdjLists(adjMtx);
494 pnkfelix 1.1.2.18
495 pnkfelix 1.1.2.5 adjMtx = null;
496 pnkfelix 1.1.2.5
497 pnkfelix 1.1.2.21 // STAT GATHERING LOOPS
498 pnkfelix 1.1.2.21 Iterator wri;
499 pnkfelix 1.1.2.21 StatGather regStat = new StatGather();
500 pnkfelix 1.1.2.21 for(wri=regWebRecords.iterator(); wri.hasNext();) {
501 pnkfelix 1.1.2.21 RegWebRecord rwr = (RegWebRecord) wri.next();
502 pnkfelix 1.1.2.21 int deg = rwr.adjnds.size();
503 pnkfelix 1.1.2.21 regStat.add(deg);
504 pnkfelix 1.1.2.21 }
505 pnkfelix 1.1.2.21 StatGather tmpStat = new StatGather();
506 pnkfelix 1.1.2.21 for(wri=tempWebRecords.iterator(); wri.hasNext();) {
507 pnkfelix 1.1.2.21 TempWebRecord twr = (TempWebRecord) wri.next();
508 pnkfelix 1.1.2.21 int deg = twr.adjnds.size();
509 pnkfelix 1.1.2.21 tmpStat.add(deg);
510 pnkfelix 1.1.2.21 }
511 pnkfelix 1.1.2.24 if(STATS)System.out.println("\nRegDeg"+regStat + " TmpDeg"+tmpStat );
512 pnkfelix 1.1.2.21 // END STAT GATHERING LOOPS
513 pnkfelix 1.1.2.18
514 pnkfelix 1.1.2.7 // System.out.println(Arrays.asList(adjLsts));
515 pnkfelix 1.1.2.5
516 pnkfelix 1.1.2.1 computeSpillCosts();
517 pnkfelix 1.1.2.5
518 pnkfelix 1.1.2.33 if(TIME)System.out.println("Building Graph \t\t"+new Date());
519 pnkfelix 1.1.2.11
520 pnkfelix 1.1.2.15 final Graph graph = buildGraph(adjLsts);
521 pnkfelix 1.1.2.28
522 pnkfelix 1.1.2.28 Map nodeToNum = printGraph(graph, RESULTS);
523 pnkfelix 1.1.2.5
524 pnkfelix 1.1.2.24 if(STATS)System.out.println(" |g.V|:"+graph.nodeSet().size() +
525 pnkfelix 1.1.2.24 " |g.E|:"+graph.edges().size());
526 pnkfelix 1.1.2.19
527 pnkfelix 1.1.2.5 try {
528 pnkfelix 1.1.2.6 List colors = new ArrayList(regToColor.values());
529 pnkfelix 1.1.2.10 // System.out.println("colors:"+colors);
530 pnkfelix 1.1.2.6 colorer.color(graph, colors);
531 pnkfelix 1.1.2.18
532 pnkfelix 1.1.2.17 for(int j=0; j<adjLsts.length; j++) {
533 pnkfelix 1.1.2.17 WebRecord wr = adjLsts[j];
534 pnkfelix 1.1.2.22
535 pnkfelix 1.1.2.22 if (isRegister(wr.temp())) continue;
536 pnkfelix 1.1.2.22
537 pnkfelix 1.1.2.17 Iterator wrs;
538 pnkfelix 1.1.2.17 for(wrs=wr.adjnds.iterator(); wrs.hasNext();){
539 pnkfelix 1.1.2.17 WebRecord nb = (WebRecord) wrs.next();
540 pnkfelix 1.1.2.18 HashSet nbl = new HashSet(graph.regs(nb));
541 pnkfelix 1.1.2.17
542 cananian 1.3.2.1 assert !nbl.isEmpty() : "no regs for "+nb;
543 cananian 1.3.2.1 assert !graph.regs(wr).isEmpty() : "no regs for "+wr;
544 pnkfelix 1.1.2.17
545 pnkfelix 1.1.2.17 nbl.retainAll(graph.regs(wr));
546 pnkfelix 1.1.2.28
547 pnkfelix 1.1.2.28
548 cananian 1.3.2.1 assert nbl.isEmpty() : "conflict detected: "+
549 pnkfelix 1.1.2.28 wr+"("+graph.regs(wr)+
550 pnkfelix 1.1.2.28 ",precol:"+webPrecolor.containsKey(wr)+
551 pnkfelix 1.1.2.28 ")"+
552 pnkfelix 1.1.2.28
553 pnkfelix 1.1.2.17 " and "+
554 pnkfelix 1.1.2.28 nb+"("+graph.regs(nb)+
555 pnkfelix 1.1.2.28 ",precol:"+webPrecolor.containsKey(wr)+
556 pnkfelix 1.1.2.28 ")"+
557 cananian 1.3.2.1 "";
558 pnkfelix 1.1.2.17
559 cananian 1.3.2.1 assert rfi.getRegAssignments(wr.temp()).
560 cananian 1.3.2.1 contains(graph.regs(wr)) : rfi.getRegAssignments(wr.temp())+
561 cananian 1.3.2.1 " does not contain "+graph.regs(wr);
562 pnkfelix 1.1.2.17
563 pnkfelix 1.1.2.17 }
564 pnkfelix 1.1.2.17 }
565 pnkfelix 1.1.2.17
566 pnkfelix 1.1.2.10 MultiMap c2n = new GenericMultiMap();
567 pnkfelix 1.1.2.9 for(Iterator nds=graph.nodeSet().iterator();nds.hasNext();){
568 pnkfelix 1.1.2.9 Object nd = nds.next();
569 pnkfelix 1.1.2.10 c2n.add(graph.getColor(nd), nd);
570 pnkfelix 1.1.2.10 }
571 pnkfelix 1.1.2.22
572 pnkfelix 1.1.2.22 if (RESULTS)
573 pnkfelix 1.1.2.22 for(Iterator cs=c2n.keySet().iterator();cs.hasNext();){
574 pnkfelix 1.1.2.10 Object col=cs.next();
575 pnkfelix 1.1.2.24 System.out.println(col + " nodes: "+
576 pnkfelix 1.1.2.24 readableNodes(c2n.getValues(col),nodeToNum));
577 pnkfelix 1.1.2.9 }
578 pnkfelix 1.1.2.22
579 pnkfelix 1.1.2.15 modifyCode(graph);
580 pnkfelix 1.1.2.28
581 pnkfelix 1.1.2.33 // OptimisticGraphColorer.MONITOR = false;
582 pnkfelix 1.1.2.5 success = true;
583 pnkfelix 1.1.2.11 } catch (UnableToColorGraph u) {
584 pnkfelix 1.1.2.33 // OptimisticGraphColorer.MONITOR = true;
585 pnkfelix 1.1.2.5 success = false;
586 pnkfelix 1.1.2.34 if (!aggressivelyCoalesce && doCoalescing) {
587 pnkfelix 1.1.2.28 doCoalescing = false;
588 pnkfelix 1.1.2.31 undoCoalescing();
589 pnkfelix 1.1.2.28 } else {
590 pnkfelix 1.1.2.32 // doCoalescing = true;
591 pnkfelix 1.1.2.28 genSpillCode(u, graph);
592 pnkfelix 1.1.2.28 }
593 pnkfelix 1.1.2.1 }
594 pnkfelix 1.1.2.1 } while (!success);
595 pnkfelix 1.1.2.18
596 pnkfelix 1.1.2.18 fixupSpillCode();
597 cananian 1.6 for(Object iO : willRemoveLater){
598 cananian 1.6 Instr i = (Instr) iO;
599 pnkfelix 1.1.2.28 Temp sym;
600 pnkfelix 1.1.2.28 if (isRegister(i.def()[0])) {
601 pnkfelix 1.1.2.28 sym = i.use()[0];
602 pnkfelix 1.1.2.28 } else {
603 pnkfelix 1.1.2.28 sym = i.def()[0];
604 pnkfelix 1.1.2.28 }
605 pnkfelix 1.1.2.28 InstrMOVEproxy proxy = new InstrMOVEproxy(i);
606 pnkfelix 1.1.2.28 replace(i, proxy);
607 pnkfelix 1.1.2.28 code.assignRegister(proxy, sym, code.getRegisters(i, sym));
608 pnkfelix 1.1.2.28 }
609 pnkfelix 1.1.2.1 }
610 pnkfelix 1.1.2.2
611 pnkfelix 1.1.2.13 // sets regToColor, regToDefs, regToUses, implicitAssigns
612 pnkfelix 1.1.2.5 private void buildRegAssigns() {
613 pnkfelix 1.1.2.13 HashSet assigns; // Set<Assign>
614 pnkfelix 1.1.2.13 HashMap asnSetToImplc; // Set<Assign> -> Reg -> Assign
615 pnkfelix 1.1.2.13
616 pnkfelix 1.1.2.13 // local vars
617 pnkfelix 1.1.2.13 assigns = new HashSet();
618 pnkfelix 1.1.2.13 asnSetToImplc = new HashMap();
619 pnkfelix 1.1.2.5
620 pnkfelix 1.1.2.13 // global vars
621 pnkfelix 1.1.2.13 implicitAssigns = new HashMap();
622 pnkfelix 1.1.2.13 regToColor = new HashMap();
623 pnkfelix 1.1.2.5 regToDefs = new GenericMultiMap();
624 pnkfelix 1.1.2.9 regToUses = new GenericMultiMap();
625 pnkfelix 1.1.2.13
626 pnkfelix 1.1.2.5 for(Iterator instrs=code.getElementsI(); instrs.hasNext();){
627 pnkfelix 1.1.2.29 Instr inst = (Instr) instrs.next();
628 pnkfelix 1.1.2.29 Iterator tmps = new CombineIterator(inst.defC().iterator(),
629 pnkfelix 1.1.2.29 inst.useC().iterator());
630 pnkfelix 1.1.2.5 while(tmps.hasNext()) {
631 pnkfelix 1.1.2.5 Temp t = (Temp) tmps.next();
632 pnkfelix 1.1.2.5 if (rfi.isRegister(t)) {
633 pnkfelix 1.1.2.29 if (inst.defC().contains(t)) regToDefs.add(t, inst);
634 pnkfelix 1.1.2.29 if (inst.useC().contains(t)) regToUses.add(t, inst);
635 pnkfelix 1.1.2.13
636 pnkfelix 1.1.2.13 // do not make a color for `t' here; otherwise
637 pnkfelix 1.1.2.13 // system registers (PC, SP, etc) get colors
638 pnkfelix 1.1.2.13 continue;
639 pnkfelix 1.1.2.13 }
640 pnkfelix 1.1.2.13
641 pnkfelix 1.1.2.13 Set suggRegs = rfi.getRegAssignments(t);
642 pnkfelix 1.1.2.13 assigns.addAll(suggRegs);
643 pnkfelix 1.1.2.13
644 pnkfelix 1.1.2.13 // incorporate into regToColor
645 cananian 1.6 for(Object rLO : suggRegs){
646 cananian 1.6 List rL = (List) rLO;
647 cananian 1.6 for(Object regO : rL){
648 cananian 1.6 Temp reg = (Temp) regO;
649 pnkfelix 1.1.2.13 regToColor(reg);
650 pnkfelix 1.1.2.13 }
651 pnkfelix 1.1.2.13 }
652 pnkfelix 1.1.2.13
653 pnkfelix 1.1.2.13 if (!implicitAssigns.keySet().contains(t)) {
654 pnkfelix 1.1.2.13 if (!asnSetToImplc.keySet().contains(suggRegs)) {
655 pnkfelix 1.1.2.29 // build (Reg -> Assign)[] for suggRegs
656 pnkfelix 1.1.2.29 Map[] i2r2a = null;
657 cananian 1.6 for(Object asnO : suggRegs){
658 cananian 1.6 List asn = (List) asnO;
659 pnkfelix 1.1.2.29 if (i2r2a == null) {
660 pnkfelix 1.1.2.29 i2r2a = new Map[asn.size()];
661 pnkfelix 1.1.2.29 for(int j=0; j<i2r2a.length; j++) {
662 pnkfelix 1.1.2.29 i2r2a[j] = new HashMap(10);
663 pnkfelix 1.1.2.29 }
664 pnkfelix 1.1.2.29 }
665 pnkfelix 1.1.2.29 for(int i=0; i<asn.size(); i++) {
666 pnkfelix 1.1.2.29 Temp reg = (Temp) asn.get(i);
667 pnkfelix 1.1.2.29 i2r2a[i].put(reg, asn);
668 pnkfelix 1.1.2.13 }
669 pnkfelix 1.1.2.5 }
670 pnkfelix 1.1.2.29 asnSetToImplc.put(suggRegs, i2r2a);
671 pnkfelix 1.1.2.5 }
672 pnkfelix 1.1.2.13
673 pnkfelix 1.1.2.13 // add to implicitAssigns
674 pnkfelix 1.1.2.29 Object i2r2a = asnSetToImplc.get(suggRegs);
675 pnkfelix 1.1.2.29 implicitAssigns.put(t, i2r2a);
676 pnkfelix 1.1.2.5 }
677 pnkfelix 1.1.2.5 }
678 pnkfelix 1.1.2.5 }
679 pnkfelix 1.1.2.5 }
680 pnkfelix 1.1.2.5
681 pnkfelix 1.1.2.16 private RegColor regToColor(Temp reg) {
682 pnkfelix 1.1.2.16 RegColor c = (RegColor) regToColor.get(reg);
683 pnkfelix 1.1.2.5 if (c == null) {
684 pnkfelix 1.1.2.5 c = new RegColor(reg);
685 pnkfelix 1.1.2.5 regToColor.put(reg, c);
686 pnkfelix 1.1.2.5 }
687 pnkfelix 1.1.2.5 return c;
688 pnkfelix 1.1.2.5 }
689 pnkfelix 1.1.2.2
690 pnkfelix 1.1.2.5 class RegColor extends Color {
691 pnkfelix 1.1.2.5 final Temp reg;
692 pnkfelix 1.1.2.5 RegColor(Temp r) {
693 pnkfelix 1.1.2.5 this.reg = r;
694 pnkfelix 1.1.2.5 }
695 pnkfelix 1.1.2.6 public String toString() {
696 pnkfelix 1.1.2.6 return "c:"+reg;
697 pnkfelix 1.1.2.6 }
698 pnkfelix 1.1.2.17 public boolean equals(Object o) {
699 pnkfelix 1.1.2.17 return ((RegColor)o).reg.equals(this.reg);
700 pnkfelix 1.1.2.17 }
701 pnkfelix 1.1.2.5 }
702 pnkfelix 1.1.2.5
703 pnkfelix 1.1.2.4 /**
704 pnkfelix 1.1.2.5 nwebs is set after this method returns.
705 pnkfelix 1.1.2.21 regWebRecords, tempWebRecords, and webRecords are set
706 pnkfelix 1.1.2.5 after this method returns.
707 pnkfelix 1.1.2.4 */
708 pnkfelix 1.1.2.3 private void makeWebs(ReachingDefs rdefs) {
709 pnkfelix 1.1.2.12 Set webSet = new HashSet(), tmp1; // Set<TempWebRecord>
710 pnkfelix 1.1.2.5 TempWebRecord web1, web2;
711 pnkfelix 1.1.2.4 List sd; // [Temp, Def]
712 pnkfelix 1.1.2.2 int i, oldnwebs;
713 pnkfelix 1.1.2.2
714 pnkfelix 1.1.2.3 for(Iterator instrs = code.getElementsI();instrs.hasNext();){
715 pnkfelix 1.1.2.3 Instr inst = (Instr) instrs.next();
716 cananian 1.6 for(Object tO : inst.useC()){
717 cananian 1.6 Temp t = (Temp) tO;
718 pnkfelix 1.1.2.22
719 pnkfelix 1.1.2.24 if (isRegister(t)) continue;
720 pnkfelix 1.1.2.8
721 pnkfelix 1.1.2.5 TempWebRecord web =
722 pnkfelix 1.1.2.5 new TempWebRecord
723 pnkfelix 1.1.2.5 (t, new LinearSet(rdefs.reachingDefs(inst,t)),
724 pnkfelix 1.1.2.5 new LinearSet(Collections.singleton(inst)));
725 pnkfelix 1.1.2.3 webSet.add(web);
726 pnkfelix 1.1.2.12
727 pnkfelix 1.1.2.12 List ixt = Default.pair(inst, t);
728 pnkfelix 1.1.2.12 if (!ixtToWebPreCombine.keySet().contains(ixt)) {
729 pnkfelix 1.1.2.12 ixtToWebPreCombine.put(ixt, web);
730 pnkfelix 1.1.2.12 }
731 pnkfelix 1.1.2.3 }
732 pnkfelix 1.1.2.7
733 pnkfelix 1.1.2.7 // in practice, the remainder of the web building should
734 pnkfelix 1.1.2.12 // work w/o the following loop. but if there is a def w/o
735 pnkfelix 1.1.2.7 // a corresponding use, the system breaks.
736 pnkfelix 1.1.2.12
737 cananian 1.6 for(Object tO : inst.defC()){
738 cananian 1.6 Temp t = (Temp) tO;
739 pnkfelix 1.1.2.22
740 pnkfelix 1.1.2.24 if (isRegister(t)) continue;
741 pnkfelix 1.1.2.40
742 pnkfelix 1.1.2.40 // FSK: shouldn't this be kept in the else-block
743 pnkfelix 1.1.2.40 // alone? Leaving alone for now... (XP style)
744 pnkfelix 1.1.2.7 TempWebRecord web =
745 pnkfelix 1.1.2.7 new TempWebRecord
746 pnkfelix 1.1.2.7 (t, new LinearSet(Collections.singleton(inst)),
747 pnkfelix 1.1.2.7 new LinearSet(Collections.EMPTY_SET));
748 pnkfelix 1.1.2.7 webSet.add(web);
749 pnkfelix 1.1.2.12
750 pnkfelix 1.1.2.12 List ixt = Default.pair(inst, t);
751 pnkfelix 1.1.2.12 if (ixtToWebPreCombine.keySet().contains(ixt)) {
752 pnkfelix 1.1.2.12 TempWebRecord wr = (TempWebRecord)
753 pnkfelix 1.1.2.12 ixtToWebPreCombine.get(ixt);
754 pnkfelix 1.1.2.12 wr.defs.add(inst);
755 pnkfelix 1.1.2.12 } else {
756 pnkfelix 1.1.2.40
757 pnkfelix 1.1.2.12 ixtToWebPreCombine.put(ixt, web);
758 pnkfelix 1.1.2.12 }
759 pnkfelix 1.1.2.7 }
760 pnkfelix 1.1.2.2 }
761 pnkfelix 1.1.2.5
762 pnkfelix 1.1.2.7 // System.out.println("pre-duchain-combination");
763 pnkfelix 1.1.2.7 // System.out.println("webSet: "+webSet);
764 pnkfelix 1.1.2.5
765 pnkfelix 1.1.2.40 boolean changed;
766 pnkfelix 1.1.2.2 do {
767 pnkfelix 1.1.2.2 // combine du-chains for the same symbol and that have a
768 pnkfelix 1.1.2.7 // def in common to make webs
769 pnkfelix 1.1.2.5 changed = false;
770 pnkfelix 1.1.2.3 tmp1 = new HashSet(webSet);
771 pnkfelix 1.1.2.40
772 pnkfelix 1.1.2.2 while(!tmp1.isEmpty()) {
773 pnkfelix 1.1.2.5 web1 = (TempWebRecord) tmp1.iterator().next();
774 pnkfelix 1.1.2.2 tmp1.remove(web1);
775 pnkfelix 1.1.2.12
776 pnkfelix 1.1.2.40 // put webs to be removed post-iteration here
777 pnkfelix 1.1.2.40 HashSet removeFromTmp1 = new HashSet();
778 pnkfelix 1.1.2.40
779 pnkfelix 1.1.2.12 for(Iterator t2s=tmp1.iterator(); t2s.hasNext(); ){
780 pnkfelix 1.1.2.12 web2 = (TempWebRecord) t2s.next();
781 pnkfelix 1.1.2.40
782 pnkfelix 1.1.2.2 if (web1.sym.equals(web2.sym)) {
783 pnkfelix 1.1.2.9 boolean combineWebs;
784 pnkfelix 1.1.2.3 Set ns = new HashSet(web1.defs);
785 pnkfelix 1.1.2.3 ns.retainAll(web2.defs);
786 pnkfelix 1.1.2.9 combineWebs = !ns.isEmpty();
787 pnkfelix 1.1.2.9
788 pnkfelix 1.1.2.9 if (!combineWebs) {
789 pnkfelix 1.1.2.9 // IMPORTANT: current temp->reg assignment
790 pnkfelix 1.1.2.9 // design breaks if an instr needs two
791 pnkfelix 1.1.2.9 // different regs for the same temp in the
792 pnkfelix 1.1.2.22 // uses and defines. Take this clause out
793 pnkfelix 1.1.2.22 // after that is fixed.
794 pnkfelix 1.1.2.9 Set s1 = new HashSet(web1.defs);
795 pnkfelix 1.1.2.9 s1.retainAll(web2.uses);
796 pnkfelix 1.1.2.9
797 pnkfelix 1.1.2.9 Set s2 = new HashSet(web2.defs);
798 pnkfelix 1.1.2.9 s2.retainAll(web1.uses);
799 pnkfelix 1.1.2.9 combineWebs = (!s1.isEmpty() || !s2.isEmpty());
800 pnkfelix 1.1.2.9 }
801 pnkfelix 1.1.2.9
802 pnkfelix 1.1.2.22 if (false) System.out.println
803 pnkfelix 1.1.2.22 (combineWebs?
804 pnkfelix 1.1.2.22 "combining "+web1+" & "+web2:
805 pnkfelix 1.1.2.22 "NOT combining "+web1+" & "+web2);
806 pnkfelix 1.1.2.9
807 pnkfelix 1.1.2.9 if (combineWebs) {
808 pnkfelix 1.1.2.2 web1.defs.addAll(web2.defs);
809 pnkfelix 1.1.2.2 web1.uses.addAll(web2.uses);
810 pnkfelix 1.1.2.2 webSet.remove(web2);
811 pnkfelix 1.1.2.40 removeFromTmp1.add(web2);
812 pnkfelix 1.1.2.5 changed = true;
813 pnkfelix 1.1.2.2 }
814 pnkfelix 1.1.2.2 }
815 pnkfelix 1.1.2.2 }
816 pnkfelix 1.1.2.40
817 pnkfelix 1.1.2.40 tmp1.removeAll(removeFromTmp1);
818 pnkfelix 1.1.2.40
819 pnkfelix 1.1.2.2 }
820 pnkfelix 1.1.2.5 } while ( changed );
821 pnkfelix 1.1.2.5
822 pnkfelix 1.1.2.7 // System.out.println("post-duchain-combination");
823 pnkfelix 1.1.2.7 // System.out.println("webSet: "+webSet);
824 pnkfelix 1.1.2.2
825 pnkfelix 1.1.2.13
826 pnkfelix 1.1.2.13 regWebRecords = new ArrayList(regToColor.keySet().size());
827 pnkfelix 1.1.2.13
828 pnkfelix 1.1.2.27 regToWeb = new HashMap();
829 pnkfelix 1.1.2.13 Iterator rs = regToColor.keySet().iterator();
830 pnkfelix 1.1.2.13 for(i=0; rs.hasNext(); i++) {
831 pnkfelix 1.1.2.13 Temp reg = (Temp) rs.next();
832 pnkfelix 1.1.2.13 WebRecord w = new RegWebRecord(reg);
833 pnkfelix 1.1.2.5 w.sreg(i);
834 pnkfelix 1.1.2.13 regWebRecords.add(w);
835 pnkfelix 1.1.2.27 regToWeb.put(reg, w);
836 pnkfelix 1.1.2.5 }
837 pnkfelix 1.1.2.5 tempWebRecords = new ArrayList(webSet.size());
838 pnkfelix 1.1.2.5 for(Iterator webs = webSet.iterator(); webs.hasNext(); i++) {
839 pnkfelix 1.1.2.5 WebRecord w = (TempWebRecord) webs.next();
840 pnkfelix 1.1.2.5 w.sreg(i);
841 pnkfelix 1.1.2.5 tempWebRecords.add(w);
842 pnkfelix 1.1.2.5 }
843 pnkfelix 1.1.2.5 webRecords = ListFactory.concatenate
844 pnkfelix 1.1.2.13 (Default.pair(regWebRecords, tempWebRecords));
845 pnkfelix 1.1.2.12
846 cananian 1.6 for(Object wrO : tempWebRecords){
847 cananian 1.6 WebRecord wr = (WebRecord) wrO;
848 pnkfelix 1.1.2.13 Temp t = wr.temp();
849 pnkfelix 1.1.2.35
850 pnkfelix 1.1.2.13 Iterator is = new
851 pnkfelix 1.1.2.13 CombineIterator(wr.defs().iterator(),
852 pnkfelix 1.1.2.13 wr.uses().iterator());
853 pnkfelix 1.1.2.13 while( is.hasNext() ) {
854 pnkfelix 1.1.2.13 Instr inst = (Instr) is.next();
855 pnkfelix 1.1.2.13 List ixt = Default.pair(inst,t);
856 pnkfelix 1.1.2.13 WebRecord prior = (WebRecord) ixtToWeb.get(ixt);
857 cananian 1.3.2.1 assert prior == null || prior == wr;
858 pnkfelix 1.1.2.13 ixtToWeb.put(ixt, wr);
859 pnkfelix 1.1.2.12 }
860 pnkfelix 1.1.2.12 }
861 pnkfelix 1.1.2.21
862 pnkfelix 1.1.2.21 // ASSERTION EQUALITY CHECK (with feedback info)
863 pnkfelix 1.1.2.12 if(!ixtToWeb.keySet().equals(ixtToWebPreCombine.keySet())) {
864 pnkfelix 1.1.2.12 HashSet postMinusPre = new HashSet(ixtToWeb.keySet());
865 pnkfelix 1.1.2.12 HashSet preMinusPost = new HashSet(ixtToWebPreCombine.keySet());
866 pnkfelix 1.1.2.12 postMinusPre.removeAll(ixtToWebPreCombine.keySet());
867 pnkfelix 1.1.2.12 preMinusPost.removeAll(ixtToWeb.keySet());
868 pnkfelix 1.1.2.12
869 pnkfelix 1.1.2.12 System.out.println("PRE - POST: " + preMinusPost);
870 pnkfelix 1.1.2.12 System.out.println();
871 pnkfelix 1.1.2.12 System.out.println("POST - PRE: " + postMinusPre);
872 pnkfelix 1.1.2.12 System.out.println();
873 cananian 1.3.2.1 assert false;
874 pnkfelix 1.1.2.12 }
875 pnkfelix 1.1.2.5 }
876 pnkfelix 1.1.2.33
877 pnkfelix 1.1.2.5 private AdjMtx buildAdjMatrix() {
878 pnkfelix 1.1.2.18 HashSet visited = new HashSet();
879 pnkfelix 1.1.2.18
880 pnkfelix 1.1.2.5 AdjMtx adjMtx = new AdjMtx(webRecords);
881 pnkfelix 1.1.2.2 int i, j;
882 pnkfelix 1.1.2.18 int sz = webRecords.size();
883 pnkfelix 1.1.2.25
884 pnkfelix 1.1.2.18 for(i=0; i<sz; i++) {
885 pnkfelix 1.1.2.11 WebRecord wr1 = (WebRecord) webRecords.get(i);
886 pnkfelix 1.1.2.18 visited.add(wr1);
887 pnkfelix 1.1.2.33
888 pnkfelix 1.1.2.18 for(j=i+1; j<sz; j++) {
889 pnkfelix 1.1.2.5 WebRecord wr2 = (WebRecord) webRecords.get(j);
890 pnkfelix 1.1.2.33
891 pnkfelix 1.1.2.33 adjMtx.set(wr1.sreg(),wr2.sreg(),wr1.conflictsWith(wr2));
892 pnkfelix 1.1.2.2 }
893 pnkfelix 1.1.2.2 }
894 pnkfelix 1.1.2.25
895 pnkfelix 1.1.2.5 return adjMtx;
896 pnkfelix 1.1.2.2 }
897 pnkfelix 1.1.2.28
898 pnkfelix 1.1.2.32 Set willRemoveLater = new HashSet(); // Set<Instr>
899 pnkfelix 1.1.2.32 // EqTempSets remap = EqTempSets.make(this, false);
900 pnkfelix 1.1.2.32 EqWebRecords remap = new EqWebRecords();
901 pnkfelix 1.1.2.32
902 pnkfelix 1.1.2.28 /** returns the set of removed Instrs. */
903 pnkfelix 1.1.2.28 private Set coalesceRegs(AdjMtx adjMtx) {
904 pnkfelix 1.1.2.32 // RESET DATA STRUCTURES
905 pnkfelix 1.1.2.28 HashSet willRemoveNow = new HashSet(); // Set<Instr>
906 pnkfelix 1.1.2.32 willRemoveLater.clear();
907 pnkfelix 1.1.2.32 webPrecolor.clear();
908 pnkfelix 1.1.2.32 // remap = EqTempSets.make(this, false);
909 pnkfelix 1.1.2.32 remap = new EqWebRecords();
910 pnkfelix 1.1.2.28
911 pnkfelix 1.1.2.26 // ANALYZE
912 pnkfelix 1.1.2.26 for(Iterator is=code.getElementsI(); is.hasNext();) {
913 pnkfelix 1.1.2.26 Instr i = (Instr) is.next();
914 pnkfelix 1.1.2.41
915 pnkfelix 1.1.2.41 // System.out.println("Instr: "+i);
916 pnkfelix 1.1.2.41
917 pnkfelix 1.1.2.26 if (i instanceof harpoon.IR.Assem.InstrMOVE) {
918 pnkfelix 1.1.2.27 Temp use = i.use()[0];
919 pnkfelix 1.1.2.27 Temp def = i.def()[0];
920 pnkfelix 1.1.2.27 WebRecord wUse = getWR(i, use);
921 pnkfelix 1.1.2.27 WebRecord wDef = getWR(i, def);
922 pnkfelix 1.1.2.31
923 pnkfelix 1.1.2.31 // this assertion seems like it should hold, but
924 pnkfelix 1.1.2.31 // doesn't. Need to review conflictsWith code and
925 pnkfelix 1.1.2.31 // change to update adjMtx accordingly
926 pnkfelix 1.1.2.31 if (false)
927 cananian 1.3.2.1 assert wUse.conflictsWith(wDef) ==
928 cananian 1.3.2.1 adjMtx.get(wUse.sreg(), wDef.sreg()) : " conflictsWith:"+wUse.conflictsWith(wDef)+
929 pnkfelix 1.1.2.31 " adjMtx.get:"+adjMtx.get(wUse.sreg(),
930 cananian 1.3.2.1 wDef.sreg());
931 pnkfelix 1.1.2.31
932 pnkfelix 1.1.2.35 // if (adjMtx.get(wUse.sreg(), wDef.sreg())) {
933 pnkfelix 1.1.2.35 // if (wUse.conflictsWith(wDef)) {
934 pnkfelix 1.1.2.41
935 pnkfelix 1.1.2.41 long start_time = System.currentTimeMillis();
936 pnkfelix 1.1.2.41
937 pnkfelix 1.1.2.41 boolean remapConflicting = remap.conflicting(wDef, wUse);
938 pnkfelix 1.1.2.41
939 pnkfelix 1.1.2.41 if (false)System.out.println("remapConflict compute time:"+
940 pnkfelix 1.1.2.41 (System.currentTimeMillis() - start_time));
941 pnkfelix 1.1.2.41
942 pnkfelix 1.1.2.41 if (remapConflicting) {
943 pnkfelix 1.1.2.35
944 pnkfelix 1.1.2.35 } else {
945 pnkfelix 1.1.2.27 if (def.equals(use)) {
946 pnkfelix 1.1.2.27 // (nothing special to update)
947 pnkfelix 1.1.2.28 willRemoveNow.add(i);
948 pnkfelix 1.1.2.27 } else if (isRegister(def)) {
949 pnkfelix 1.1.2.41 if (!COALESCE_MACH_REGS) continue; // FSK investigated scalability problems
950 pnkfelix 1.1.2.41
951 pnkfelix 1.1.2.35 //if (webPrecolor.containsKey(wUse)) continue;
952 pnkfelix 1.1.2.35 if (remap.anyConflicting
953 pnkfelix 1.1.2.35 (wUse,webPrecolor.invert().getValues(def))){
954 pnkfelix 1.1.2.27 continue;
955 pnkfelix 1.1.2.35 }
956 pnkfelix 1.1.2.27 webPrecolor.put(wUse, def);
957 pnkfelix 1.1.2.28 willRemoveLater.add(i);
958 pnkfelix 1.1.2.27 } else if (isRegister(use)) {
959 pnkfelix 1.1.2.41 if (!COALESCE_MACH_REGS) continue; // FSK investigated scalability problems
960 pnkfelix 1.1.2.41
961 pnkfelix 1.1.2.35 // if (webPrecolor.containsKey(wUse)) continue;
962 pnkfelix 1.1.2.35 if (remap.anyConflicting
963 pnkfelix 1.1.2.35 (wDef,webPrecolor.invert().getValues(use))){
964 pnkfelix 1.1.2.27 continue;
965 pnkfelix 1.1.2.35 }
966 pnkfelix 1.1.2.27 webPrecolor.put(wDef, use);
967 pnkfelix 1.1.2.28 willRemoveLater.add(i);
968 pnkfelix 1.1.2.26 } else {
969 cananian 1.3.2.1 assert !wDef.equals(wUse);
970 pnkfelix 1.1.2.32 remap.union(wDef, wUse);
971 pnkfelix 1.1.2.28 willRemoveNow.add(i);
972 pnkfelix 1.1.2.26 }
973 pnkfelix 1.1.2.26 }
974 pnkfelix 1.1.2.26 }
975 pnkfelix 1.1.2.26 }
976 pnkfelix 1.1.2.26
977 pnkfelix 1.1.2.26 // TRANSFORM
978 pnkfelix 1.1.2.28 if (!willRemoveNow.isEmpty()) {
979 pnkfelix 1.1.2.27 for(Iterator is=code.getElementsI(); is.hasNext();) {
980 pnkfelix 1.1.2.27 Instr i= (Instr) is.next();
981 pnkfelix 1.1.2.28 if (willRemoveNow.contains(i)) {
982 pnkfelix 1.1.2.32 replace(i, new InstrMOVEproxy(remap.rename(i)));
983 pnkfelix 1.1.2.27 } else {
984 pnkfelix 1.1.2.27 Iterator itr = new
985 pnkfelix 1.1.2.27 CombineIterator(i.useC().iterator(),
986 pnkfelix 1.1.2.27 i.defC().iterator());
987 pnkfelix 1.1.2.27 while(itr.hasNext()) {
988 pnkfelix 1.1.2.27 Temp t = (Temp) itr.next();
989 pnkfelix 1.1.2.32
990 pnkfelix 1.1.2.32 //if (!remap.tempMap(t).equals(t)) {
991 pnkfelix 1.1.2.32 if (remap.containsTemp(t)) {
992 pnkfelix 1.1.2.32 Instr repl = remap.rename(i);
993 pnkfelix 1.1.2.31 replace(i, repl);
994 pnkfelix 1.1.2.32 if (willRemoveLater.contains(i)) {
995 pnkfelix 1.1.2.32 willRemoveLater.remove(i);
996 pnkfelix 1.1.2.31 willRemoveLater.add(repl);
997 pnkfelix 1.1.2.32 }
998 pnkfelix 1.1.2.27 break;
999 pnkfelix 1.1.2.2 }
1000 pnkfelix 1.1.2.2 }
1001 pnkfelix 1.1.2.2 }
1002 pnkfelix 1.1.2.2 }
1003 pnkfelix 1.1.2.28 if (COALESCE_STATS)
1004 pnkfelix 1.1.2.28 System.out.print("R:"+ willRemoveNow.size() );
1005 pnkfelix 1.1.2.28 } else if (!willRemoveLater.isEmpty()) {
1006 pnkfelix 1.1.2.28 if (COALESCE_STATS)
1007 pnkfelix 1.1.2.28 System.out.print("R:"+ willRemoveLater.size() );
1008 pnkfelix 1.1.2.2 }
1009 pnkfelix 1.1.2.28 return willRemoveNow;
1010 pnkfelix 1.1.2.2 }
1011 pnkfelix 1.1.2.35
1012 pnkfelix 1.1.2.6 private WebRecord[] buildAdjLists(AdjMtx adjMtx) {
1013 pnkfelix 1.1.2.2 int i, j;
1014 pnkfelix 1.1.2.5 final int nwebs = webRecords.size();
1015 pnkfelix 1.1.2.6 final WebRecord[] adjLsts = new WebRecord[nwebs];
1016 pnkfelix 1.1.2.13 for(i=0; i<regWebRecords.size(); i++) {
1017 pnkfelix 1.1.2.13 adjLsts[i] = (WebRecord) regWebRecords.get(i);
1018 pnkfelix 1.1.2.2 adjLsts[i].spcost = Double.POSITIVE_INFINITY;
1019 pnkfelix 1.1.2.2 }
1020 pnkfelix 1.1.2.13 int offset = regWebRecords.size();
1021 pnkfelix 1.1.2.6 for(i=0; i<tempWebRecords.size(); i++) {
1022 pnkfelix 1.1.2.6 adjLsts[offset+i]= (WebRecord) tempWebRecords.get(i);
1023 pnkfelix 1.1.2.2 }
1024 pnkfelix 1.1.2.5 for(i=1; i < nwebs; i++) {
1025 pnkfelix 1.1.2.5 for(j=0; j < i; j++) {
1026 pnkfelix 1.1.2.18 WebRecord wr1, wr2;
1027 pnkfelix 1.1.2.18 wr1 = adjLsts[i];
1028 pnkfelix 1.1.2.18 wr2 = adjLsts[j];
1029 pnkfelix 1.1.2.31
1030 pnkfelix 1.1.2.31 //FSK: using this test breaks (i suspect due to
1031 pnkfelix 1.1.2.31 //FSK: modifying instr-sequence concurrently with
1032 pnkfelix 1.1.2.31 //FSK: analysis)
1033 pnkfelix 1.1.2.28 // if (wr1.conflictsWith(wr2)) {
1034 pnkfelix 1.1.2.18 if (adjMtx.get(wr1.sreg(),wr2.sreg())) {
1035 pnkfelix 1.1.2.28
1036 pnkfelix 1.1.2.18 wr1.adjnds.add(wr2);
1037 pnkfelix 1.1.2.18 wr2.adjnds.add(wr1);
1038 pnkfelix 1.1.2.18 wr1.nints++;
1039 pnkfelix 1.1.2.18 wr2.nints++;
1040 pnkfelix 1.1.2.2 }
1041 pnkfelix 1.1.2.2 }
1042 pnkfelix 1.1.2.2 }
1043 pnkfelix 1.1.2.5 return adjLsts;
1044 pnkfelix 1.1.2.2 }
1045 pnkfelix 1.1.2.2
1046 pnkfelix 1.1.2.2 private void computeSpillCosts() {
1047 pnkfelix 1.1.2.2
1048 pnkfelix 1.1.2.2 }
1049 pnkfelix 1.1.2.2
1050 pnkfelix 1.1.2.13 private Graph buildGraph(WebRecord[] adjLsts) {
1051 pnkfelix 1.1.2.14 Graph g = new Graph();
1052 pnkfelix 1.1.2.14 for(int i=0; i<adjLsts.length; i++) {
1053 pnkfelix 1.1.2.14 g.add(adjLsts[i]);
1054 pnkfelix 1.1.2.14 }
1055 pnkfelix 1.1.2.14 return g;
1056 pnkfelix 1.1.2.2 }
1057 pnkfelix 1.1.2.2
1058 pnkfelix 1.1.2.42 private Set defRegSet( Instr i ){
1059 pnkfelix 1.1.2.42 LinearSet regs = new LinearSet();
1060 cananian 1.6 for(Object dO : i.defC()){
1061 cananian 1.6 Temp d = (Temp) dO;
1062 pnkfelix 1.1.2.42 if (code.registerAssigned(i,d))
1063 pnkfelix 1.1.2.42 regs.addAll( code.getRegisters(i,d) );
1064 pnkfelix 1.1.2.42 }
1065 pnkfelix 1.1.2.42 return regs;
1066 pnkfelix 1.1.2.42 }
1067 pnkfelix 1.1.2.42
1068 pnkfelix 1.1.2.15 private void modifyCode(Graph g) {
1069 cananian 1.6 for(Object wrO : tempWebRecords){
1070 cananian 1.6 TempWebRecord wr = (TempWebRecord) wrO;
1071 pnkfelix 1.1.2.6 Iterator instrs;
1072 pnkfelix 1.1.2.6 for(instrs = wr.defs.iterator(); instrs.hasNext();) {
1073 pnkfelix 1.1.2.6 Instr i = (Instr) instrs.next();
1074 pnkfelix 1.1.2.42
1075 pnkfelix 1.1.2.42 // assert def-sets are disjoint for a given instruction
1076 pnkfelix 1.1.2.42 Set regs = defRegSet(i);
1077 pnkfelix 1.1.2.42 regs.retainAll( g.regs(wr) );
1078 cananian 1.3.2.1 assert regs.isEmpty() : "def-sets should be disjoint!";
1079 pnkfelix 1.1.2.42
1080 pnkfelix 1.1.2.15 code.assignRegister(i, wr.sym, g.regs(wr));
1081 pnkfelix 1.1.2.6 }
1082 pnkfelix 1.1.2.6 for(instrs = wr.uses.iterator(); instrs.hasNext();) {
1083 pnkfelix 1.1.2.6 Instr i = (Instr) instrs.next();
1084 pnkfelix 1.1.2.15 code.assignRegister(i, wr.sym, g.regs(wr));
1085 pnkfelix 1.1.2.6 }
1086 pnkfelix 1.1.2.6 }
1087 pnkfelix 1.1.2.2 }
1088 pnkfelix 1.1.2.2
1089 pnkfelix 1.1.2.18
1090 pnkfelix 1.1.2.18 HashSet spilled = new HashSet();
1091 pnkfelix 1.1.2.28
1092 pnkfelix 1.1.2.28 private boolean isPrecolored(Object n) {
1093 pnkfelix 1.1.2.28 Graph.Node node = (Graph.Node) n;
1094 pnkfelix 1.1.2.28 if (node.wr instanceof RegWebRecord)
1095 pnkfelix 1.1.2.28 return true;
1096 pnkfelix 1.1.2.28 if (webPrecolor.containsKey(node.wr))
1097 pnkfelix 1.1.2.28 return true;
1098 pnkfelix 1.1.2.28 return false;
1099 pnkfelix 1.1.2.28 }
1100 pnkfelix 1.1.2.28
1101 pnkfelix 1.1.2.31 private boolean isAvailableToSpill(Object n) {
1102 pnkfelix 1.1.2.28 Graph.Node node = (Graph.Node) n;
1103 pnkfelix 1.1.2.29 if (isRegister(node.wr.temp()))
1104 pnkfelix 1.1.2.31 return false;
1105 cananian 1.6 for(Object splO : spilled){
1106 cananian 1.6 WebRecord spl = (WebRecord) splO;
1107 pnkfelix 1.1.2.29 if (spl.temp().equals(node.wr.temp()) &&
1108 pnkfelix 1.1.2.29 spl.overlaps(node.wr))
1109 pnkfelix 1.1.2.31 return false;
1110 pnkfelix 1.1.2.28 }
1111 pnkfelix 1.1.2.31 return true;
1112 pnkfelix 1.1.2.28 }
1113 pnkfelix 1.1.2.28
1114 pnkfelix 1.1.2.28
1115 pnkfelix 1.1.2.28 private void genSpillCode(UnableToColorGraph u, Graph g) {
1116 pnkfelix 1.1.2.28 Collection remove = u.getRemovalSuggestions();
1117 pnkfelix 1.1.2.22 HashSet spillThese = new HashSet(remove.size());
1118 pnkfelix 1.1.2.28
1119 cananian 1.6 for(Object nodeO : remove) {
1120 cananian 1.6 Graph.Node node = (Graph.Node) nodeO;
1121 pnkfelix 1.1.2.28
1122 pnkfelix 1.1.2.31 if (!isAvailableToSpill(node)) {
1123 pnkfelix 1.1.2.34 if (SCARY_OUTPUT) System.out.println("SKIP ONE (1)");
1124 pnkfelix 1.1.2.28 }
1125 pnkfelix 1.1.2.28
1126 pnkfelix 1.1.2.22 spillThese.add(node);
1127 pnkfelix 1.1.2.22 }
1128 pnkfelix 1.1.2.34 if (SCARY_OUTPUT) System.out.println("HIT1:"+spillThese.size());
1129 pnkfelix 1.1.2.28
1130 pnkfelix 1.1.2.28 if (spillThese.isEmpty()) {
1131 pnkfelix 1.1.2.28 System.out.println(" remove:" +remove+ " contains nothing new");
1132 pnkfelix 1.1.2.28 Collection removeLrg = u.getRemovalSuggestionsBackup();
1133 pnkfelix 1.1.2.28 removeLrg = new HashSet(removeLrg);
1134 pnkfelix 1.1.2.28 removeLrg.removeAll(remove);
1135 pnkfelix 1.1.2.28 nextNode:
1136 cananian 1.6 for(Object nodeO : removeLrg) {
1137 cananian 1.6 Graph.Node node = (Graph.Node) nodeO;
1138 pnkfelix 1.1.2.28
1139 pnkfelix 1.1.2.31 if (!isAvailableToSpill(node)) {
1140 pnkfelix 1.1.2.34 if (SCARY_OUTPUT) System.out.println("SKIP ONE (2)");
1141 pnkfelix 1.1.2.28 continue nextNode;
1142 pnkfelix 1.1.2.28 }
1143 pnkfelix 1.1.2.28
1144 pnkfelix 1.1.2.28 spillThese.add(node);
1145 pnkfelix 1.1.2.28 }
1146 pnkfelix 1.1.2.28
1147 pnkfelix 1.1.2.34 if (SCARY_OUTPUT) System.out.println("HIT2:"+spillThese.size());
1148 pnkfelix 1.1.2.29
1149 pnkfelix 1.1.2.28 if (spillThese.isEmpty())
1150 pnkfelix 1.1.2.34 if (SCARY_OUTPUT) System.out.println
1151 pnkfelix 1.1.2.28 (" remove:" +removeLrg+ " contains nothing new");
1152 pnkfelix 1.1.2.28 }
1153 pnkfelix 1.1.2.28
1154 pnkfelix 1.1.2.28
1155 pnkfelix 1.1.2.22 if (spillThese.isEmpty()) {
1156 pnkfelix 1.1.2.22 // choose a node independently of the suggested ones, since
1157 pnkfelix 1.1.2.22 // those are all already spilled...
1158 pnkfelix 1.1.2.22 HashSet nset = new HashSet(g.nodeSet());
1159 pnkfelix 1.1.2.22 nset.removeAll(spilled);
1160 pnkfelix 1.1.2.22 int md = -1; Object mn=null;
1161 cananian 1.6 for(Object nO : nset) {
1162 cananian 1.6 Graph.Node n = (Graph.Node) nO;
1163 pnkfelix 1.1.2.22 if (g.getDegree(n) > md &&
1164 pnkfelix 1.1.2.22 !isRegister(n.wr.temp()) &&
1165 pnkfelix 1.1.2.31 isAvailableToSpill(n)) {
1166 pnkfelix 1.1.2.22 mn = n;
1167 pnkfelix 1.1.2.22 md = g.getDegree(n);
1168 pnkfelix 1.1.2.22 }
1169 pnkfelix 1.1.2.22 }
1170 pnkfelix 1.1.2.29 if (mn != null)
1171 pnkfelix 1.1.2.29 spillThese.add(mn);
1172 pnkfelix 1.1.2.22 }
1173 pnkfelix 1.1.2.22
1174 cananian 1.3.2.1 assert !spillThese.isEmpty();
1175 cananian 1.3.2.1 assert !spillThese.contains(null);
1176 pnkfelix 1.1.2.29
1177 cananian 1.6 for(Object nodeO : spillThese) {
1178 cananian 1.6 Graph.Node node = (Graph.Node) nodeO;
1179 pnkfelix 1.1.2.18 spilled.add(node.wr);
1180 pnkfelix 1.1.2.18
1181 pnkfelix 1.1.2.18 TempWebRecord wr = (TempWebRecord) node.wr;
1182 cananian 1.3.2.1 assert !isRegister(wr.temp());
1183 pnkfelix 1.1.2.22
1184 pnkfelix 1.1.2.28 if (SPILL_INFO)
1185 pnkfelix 1.1.2.28 System.out.print("\nSpilling "+wr);
1186 pnkfelix 1.1.2.22
1187 pnkfelix 1.1.2.18 Temp t = wr.temp();
1188 cananian 1.6 for(Object iO : wr.defs) {
1189 cananian 1.6 Instr i = (Instr) iO;
1190 pnkfelix 1.1.2.36
1191 pnkfelix 1.1.2.36 if (i.isDummy())
1192 pnkfelix 1.1.2.36 continue;
1193 pnkfelix 1.1.2.36
1194 pnkfelix 1.1.2.18 Instr n = i.getNext();
1195 pnkfelix 1.1.2.42
1196 pnkfelix 1.1.2.42 // FSK: checking if <n> is a dummy and
1197 pnkfelix 1.1.2.42 // shifting the spill down if so...
1198 pnkfelix 1.1.2.42 while( n.isDummy()) {
1199 pnkfelix 1.1.2.42 i = n;
1200 pnkfelix 1.1.2.42 n = i.getNext();
1201 pnkfelix 1.1.2.42 }
1202 pnkfelix 1.1.2.42
1203 cananian 1.3.2.1 assert i.canFallThrough &&
1204 cananian 1.3.2.1 i.getTargets().isEmpty() : "can't insert spill at <"+i+" , "+n+">";
1205 pnkfelix 1.1.2.18 SpillProxy sp = new SpillProxy(i, t);
1206 pnkfelix 1.1.2.18 sp.layout(i, n);
1207 pnkfelix 1.1.2.18 }
1208 cananian 1.6 for(Object iO : wr.uses) {
1209 cananian 1.6 Instr i = (Instr) iO;
1210 pnkfelix 1.1.2.36
1211 pnkfelix 1.1.2.36 if (i.isDummy())
1212 pnkfelix 1.1.2.36 continue;
1213 pnkfelix 1.1.2.36
1214 pnkfelix 1.1.2.18 Instr p = i.getPrev();
1215 cananian 1.3.2.1 assert p.canFallThrough &&
1216 pnkfelix 1.1.2.18 p.getTargets().isEmpty() &&
1217 cananian 1.3.2.1 i.predC().size() == 1 : "can't insert restore at<"+p+" , "+i+">";
1218 pnkfelix 1.1.2.18 RestoreProxy rp = new RestoreProxy(i, t);
1219 pnkfelix 1.1.2.18 rp.layout(p, i);
1220 pnkfelix 1.1.2.18 }
1221 pnkfelix 1.1.2.18 }
1222 pnkfelix 1.1.2.18
1223 pnkfelix 1.1.2.34 if (SCARY_OUTPUT) System.out.print("*** SPILLED ("+spilled.size()+")"+
1224 pnkfelix 1.1.2.34 (true?"":(": " + spilled)));
1225 pnkfelix 1.1.2.5 }
1226 pnkfelix 1.1.2.5
1227 pnkfelix 1.1.2.28 /** returns nodeToNum. */
1228 pnkfelix 1.1.2.28 public static Map printGraph(ColorableGraph graph, boolean PRINT) {
1229 pnkfelix 1.1.2.28 final Map nodeToNum = new HashMap();
1230 pnkfelix 1.1.2.28 if(PRINT)System.out.println("nodes of graph");
1231 pnkfelix 1.1.2.28 int i=0;
1232 pnkfelix 1.1.2.28 for(Iterator nodes=graph.nodeSet().iterator();nodes.hasNext();){
1233 pnkfelix 1.1.2.28 i++;
1234 pnkfelix 1.1.2.28 Object n=nodes.next();
1235 pnkfelix 1.1.2.28 nodeToNum.put(n, new Integer(i));
1236 pnkfelix 1.1.2.28 if(PRINT)System.out.println(i+"\t"+n);
1237 pnkfelix 1.1.2.28 }
1238 pnkfelix 1.1.2.28 if (PRINT){
1239 pnkfelix 1.1.2.29 String s = ""+graph.edges();
1240 pnkfelix 1.1.2.28 Collection readEdges = readableEdges(graph.edges(),nodeToNum);
1241 pnkfelix 1.1.2.28 System.out.println("edges of graph "+readEdges);
1242 pnkfelix 1.1.2.28 }
1243 pnkfelix 1.1.2.28 return nodeToNum;
1244 pnkfelix 1.1.2.28 }
1245 pnkfelix 1.1.2.14
1246 pnkfelix 1.1.2.5 /** Graph is a graph view of the adjacency lists in this.
1247 pnkfelix 1.1.2.13 There is a many-to-one mapping from Nodes to WebRecords.
1248 pnkfelix 1.1.2.15 Note that when a Node is hidden or colored, its association
1249 pnkfelix 1.1.2.15 with the WebRecord it maps to may cause other nodes to be
1250 pnkfelix 1.1.2.15 hidden or colored (nb: need to think this through more
1251 pnkfelix 1.1.2.15 carefully; algorithms depend on a particular semantics for
1252 pnkfelix 1.1.2.15 replace()'s behavior...)
1253 pnkfelix 1.1.2.13 */
1254 pnkfelix 1.1.2.5 class Graph extends AbstractGraph implements ColorableGraph {
1255 pnkfelix 1.1.2.29 private LinkedList nodes; // LinkedList<Node>
1256 pnkfelix 1.1.2.15 private LinkedList hidden; // List<WebRecord>
1257 pnkfelix 1.1.2.15 private MultiMap wr2node; // WebRecord -> Node
1258 pnkfelix 1.1.2.15
1259 pnkfelix 1.1.2.15 /** Node is a record class representing the
1260 pnkfelix 1.1.2.15 Node -> WebRecord mapping.
1261 pnkfelix 1.1.2.15 It also holds the color for the node.
1262 pnkfelix 1.1.2.14 */
1263 pnkfelix 1.1.2.14 class Node {
1264 pnkfelix 1.1.2.14 final WebRecord wr;
1265 pnkfelix 1.1.2.14 final int index;
1266 pnkfelix 1.1.2.14 RegColor color;
1267 pnkfelix 1.1.2.29
1268 pnkfelix 1.1.2.29 LinearSet adjR;
1269 pnkfelix 1.1.2.29 LinkedList adjT;
1270 pnkfelix 1.1.2.29
1271 pnkfelix 1.1.2.29 Node(WebRecord w, int i) {
1272 pnkfelix 1.1.2.29 wr = w;
1273 pnkfelix 1.1.2.29 index = i;
1274 pnkfelix 1.1.2.29 adjT = new LinkedList();
1275 pnkfelix 1.1.2.29 adjR = new LinearSet();
1276 pnkfelix 1.1.2.29
1277 pnkfelix 1.1.2.29 nodes.add(this);
1278 pnkfelix 1.1.2.29 wr2node.add(w, this);
1279 pnkfelix 1.1.2.29
1280 pnkfelix 1.1.2.29 if (w instanceof TempWebRecord) {
1281 pnkfelix 1.1.2.29 Map[] i2r2a = (Map[]) implicitAssigns.get(w.temp());
1282 pnkfelix 1.1.2.29 Set conflictRegs = new LinearSet(regToWeb.keySet());
1283 pnkfelix 1.1.2.29 Set possibleRegs = i2r2a[index].keySet();
1284 pnkfelix 1.1.2.29 conflictRegs.removeAll(possibleRegs);
1285 pnkfelix 1.1.2.29 for(Iterator cnf=conflictRegs.iterator();cnf.hasNext();){
1286 pnkfelix 1.1.2.29 adjR.add(wr2node.get(regToWeb.get(cnf.next())));
1287 pnkfelix 1.1.2.29 }
1288 pnkfelix 1.1.2.29 }
1289 cananian 1.6 for(Object _wrO : wr.adjnds){
1290 cananian 1.6 WebRecord _wr = (WebRecord) _wrO;
1291 pnkfelix 1.1.2.29 if (!wr2node.containsKey(_wr))
1292 pnkfelix 1.1.2.29 continue;
1293 pnkfelix 1.1.2.29
1294 cananian 1.6 for (Object _nO : wr2node.getValues(_wr)) {
1295 cananian 1.6 Node _n = (Node) _nO;
1296 pnkfelix 1.1.2.29 if (_n.wr instanceof TempWebRecord) {
1297 pnkfelix 1.1.2.29 adjT.add(_n);
1298 pnkfelix 1.1.2.29 } else if (_n.wr instanceof RegWebRecord) {
1299 pnkfelix 1.1.2.29 adjR.add(_n);
1300 pnkfelix 1.1.2.29 } else {
1301 cananian 1.3.2.1 assert false;
1302 pnkfelix 1.1.2.29 }
1303 pnkfelix 1.1.2.29
1304 pnkfelix 1.1.2.29 if (w instanceof RegWebRecord) {
1305 pnkfelix 1.1.2.29 _n.adjR.add(this);
1306 pnkfelix 1.1.2.29 } else {
1307 pnkfelix 1.1.2.29 _n.adjT.add(this);
1308 pnkfelix 1.1.2.29 }
1309 pnkfelix 1.1.2.29 }
1310 pnkfelix 1.1.2.29 }
1311 pnkfelix 1.1.2.29
1312 pnkfelix 1.1.2.29 }
1313 pnkfelix 1.1.2.16 public String toString() {
1314 pnkfelix 1.1.2.16 return "n:<"+wr+","+index+","+color+">";
1315 pnkfelix 1.1.2.16 }
1316 pnkfelix 1.1.2.14 }
1317 pnkfelix 1.1.2.14
1318 pnkfelix 1.1.2.15 /** Helper function for resolving the WebRecord -> Node
1319 pnkfelix 1.1.2.15 relation.
1320 pnkfelix 1.1.2.15 */
1321 pnkfelix 1.1.2.15 private Collection nodes(Object wr) {
1322 pnkfelix 1.1.2.14 return wr2node.getValues(wr);
1323 pnkfelix 1.1.2.14 }
1324 pnkfelix 1.1.2.14
1325 pnkfelix 1.1.2.14 Graph() {
1326 pnkfelix 1.1.2.14 this.nodes = new LinkedList();
1327 pnkfelix 1.1.2.6 hidden = new LinkedList();
1328 pnkfelix 1.1.2.14 wr2node = new GenericMultiMap();
1329 pnkfelix 1.1.2.14 }
1330 pnkfelix 1.1.2.15
1331 pnkfelix 1.1.2.15 /** Adds nodes and edges representing `wr' and its conflicts
1332 pnkfelix 1.1.2.15 to this graph.
1333 pnkfelix 1.1.2.15 */
1334 pnkfelix 1.1.2.14 void add(WebRecord wr) {
1335 pnkfelix 1.1.2.22 if (isRegister(wr.temp())) {
1336 pnkfelix 1.1.2.15 Node n = new Node(wr, 0);
1337 pnkfelix 1.1.2.16 n.color = regToColor(wr.temp());
1338 pnkfelix 1.1.2.27 } else if (webPrecolor.keySet().contains(wr)) {
1339 pnkfelix 1.1.2.29 // FSK: wrong for Precolored Doubles (fix later)
1340 pnkfelix 1.1.2.27 Node n = new Node(wr, 0);
1341 pnkfelix 1.1.2.27 n.color = regToColor((Temp)webPrecolor.get(wr));
1342 pnkfelix 1.1.2.15 } else {
1343 pnkfelix 1.1.2.29 Map[] i2r2a = (Map[]) implicitAssigns.get(wr.temp());
1344 pnkfelix 1.1.2.29 Map r2a = i2r2a[0];
1345 cananian 1.3.2.1 assert r2a != null : "no implicit assigns for "+wr.temp();
1346 pnkfelix 1.1.2.15 List rl = (List) r2a.values().iterator().next();
1347 pnkfelix 1.1.2.15 for(int j=0; j<rl.size(); j++) {
1348 pnkfelix 1.1.2.15 Node n = new Node(wr, j);
1349 pnkfelix 1.1.2.15 }
1350 pnkfelix 1.1.2.15 }
1351 pnkfelix 1.1.2.15 }
1352 pnkfelix 1.1.2.15
1353 pnkfelix 1.1.2.15 /** Returns the Assignment that has been given to `wr'.
1354 pnkfelix 1.1.2.15 requires: this has been colored.
1355 pnkfelix 1.1.2.15 */
1356 pnkfelix 1.1.2.15 List regs(WebRecord wr) {
1357 pnkfelix 1.1.2.17 if (wr instanceof RegWebRecord) {
1358 pnkfelix 1.1.2.17 return Collections.nCopies(1, wr.temp());
1359 pnkfelix 1.1.2.17 }
1360 pnkfelix 1.1.2.17
1361 pnkfelix 1.1.2.15 Collection c = wr2node.getValues(wr);
1362 pnkfelix 1.1.2.15 List a = new ArrayList(c);
1363 cananian 1.6 for(Object nO : c) {
1364 cananian 1.6 Node n = (Node) nO;
1365 pnkfelix 1.1.2.15 a.set(n.index, n.color.reg);
1366 pnkfelix 1.1.2.14 }
1367 pnkfelix 1.1.2.15 return a;
1368 pnkfelix 1.1.2.5 }
1369 pnkfelix 1.1.2.15
1370 pnkfelix 1.1.2.5 public Set nodeSet() {
1371 pnkfelix 1.1.2.5 return new AbstractSet() {
1372 pnkfelix 1.1.2.14 public int size() { return nodes.size(); }
1373 pnkfelix 1.1.2.5 public Iterator iterator() {
1374 pnkfelix 1.1.2.14 return nodes.iterator();
1375 pnkfelix 1.1.2.5 }
1376 pnkfelix 1.1.2.5 };
1377 pnkfelix 1.1.2.5 }
1378 pnkfelix 1.1.2.15
1379 pnkfelix 1.1.2.29 public Collection neighborsOf(final Object n) {
1380 pnkfelix 1.1.2.29 if (true) {
1381 pnkfelix 1.1.2.29 // System.out.println("neighborsOf("+n+") : "+((Node)n).adjs);
1382 pnkfelix 1.1.2.29 return new AbstractCollection() {
1383 pnkfelix 1.1.2.29 Node nd = (Node) n;
1384 pnkfelix 1.1.2.29 public int size() {
1385 pnkfelix 1.1.2.29 return nd.adjT.size() + nd.adjR.size();
1386 pnkfelix 1.1.2.29 }
1387 pnkfelix 1.1.2.29 public Iterator iterator() {
1388 pnkfelix 1.1.2.29 return new CombineIterator
1389 pnkfelix 1.1.2.29 (nd.adjT.iterator(), nd.adjR.iterator());
1390 pnkfelix 1.1.2.29 }
1391 pnkfelix 1.1.2.29 };
1392 pnkfelix 1.1.2.29
1393 pnkfelix 1.1.2.29 }
1394 pnkfelix 1.1.2.29
1395 pnkfelix 1.1.2.29
1396 pnkfelix 1.1.2.14 if (!(n instanceof Node))
1397 pnkfelix 1.1.2.5 throw new IllegalArgumentException();
1398 pnkfelix 1.1.2.28 final Node node = (Node) n;
1399 pnkfelix 1.1.2.14 return new AbstractCollection() {
1400 pnkfelix 1.1.2.28 private Iterator wrs() {
1401 pnkfelix 1.1.2.28 Iterator prependIter;
1402 pnkfelix 1.1.2.28 if (!(node.wr instanceof RegWebRecord)) {
1403 pnkfelix 1.1.2.28 Iterator regWebIter = regToWeb.values().iterator();
1404 pnkfelix 1.1.2.29 final Map[] i2r2a =
1405 pnkfelix 1.1.2.29 (Map[])implicitAssigns.get(node.wr.temp());
1406 pnkfelix 1.1.2.29 final Map r2a = i2r2a[node.index];
1407 pnkfelix 1.1.2.29
1408 pnkfelix 1.1.2.29 FilterIterator.Filter RWFltr =
1409 pnkfelix 1.1.2.28 new FilterIterator.Filter() {
1410 pnkfelix 1.1.2.28 public boolean isElement(Object o) {
1411 pnkfelix 1.1.2.28 RegWebRecord rwr = (RegWebRecord) o;
1412 pnkfelix 1.1.2.28 return
1413 pnkfelix 1.1.2.28 !r2a.containsKey(rwr.temp()) &&
1414 pnkfelix 1.1.2.28 !node.wr.adjnds.contains(rwr);
1415 pnkfelix 1.1.2.28 }
1416 pnkfelix 1.1.2.28 };
1417 pnkfelix 1.1.2.29 prependIter =
1418 pnkfelix 1.1.2.29 new FilterIterator(regWebIter,RWFltr);
1419 pnkfelix 1.1.2.28 } else {
1420 pnkfelix 1.1.2.28 prependIter = Default.nullIterator;
1421 pnkfelix 1.1.2.28 }
1422 pnkfelix 1.1.2.28 return new CombineIterator
1423 pnkfelix 1.1.2.28 (prependIter, node.wr.adjnds.iterator());
1424 pnkfelix 1.1.2.28 }
1425 pnkfelix 1.1.2.14 public int size() {
1426 pnkfelix 1.1.2.14 int s=0;
1427 pnkfelix 1.1.2.29 for(Iterator wrs = wrs(); wrs.hasNext(); ) {
1428 pnkfelix 1.1.2.29 Object wr = wrs.next();
1429 pnkfelix 1.1.2.29 s += nodes(wr).size();
1430 pnkfelix 1.1.2.29 }
1431 pnkfelix 1.1.2.14 return s;
1432 pnkfelix 1.1.2.14 }
1433 pnkfelix 1.1.2.14
1434 pnkfelix 1.1.2.14 FilterIterator.Filter TO_NODE_ITER =
1435 pnkfelix 1.1.2.14 new FilterIterator.Filter() {
1436 pnkfelix 1.1.2.14 public Object map(Object o) {
1437 pnkfelix 1.1.2.14 return nodes(o).iterator();
1438 pnkfelix 1.1.2.14 }
1439 pnkfelix 1.1.2.14 };
1440 pnkfelix 1.1.2.14 public Iterator iterator() {
1441 pnkfelix 1.1.2.14 Iterator iters =
1442 pnkfelix 1.1.2.14 new FilterIterator(wrs(), TO_NODE_ITER);
1443 pnkfelix 1.1.2.29 return new CombineIterator(iters) {
1444 pnkfelix 1.1.2.29 public boolean hasNext() {
1445 pnkfelix 1.1.2.29 return super.hasNext();
1446 pnkfelix 1.1.2.29 }
1447 pnkfelix 1.1.2.29 public Object next() {
1448 pnkfelix 1.1.2.29 return super.next();
1449 pnkfelix 1.1.2.29 }
1450 pnkfelix 1.1.2.29 };
1451 pnkfelix 1.1.2.14 }
1452 pnkfelix 1.1.2.14 };
1453 pnkfelix 1.1.2.5 }
1454 pnkfelix 1.1.2.14
1455 pnkfelix 1.1.2.16 public void hide(Object o) {
1456 pnkfelix 1.1.2.16 if (! (o instanceof Node))
1457 pnkfelix 1.1.2.16 throw new IllegalArgumentException(o+" not in node-set");
1458 pnkfelix 1.1.2.16 Node n = (Node) o;
1459 pnkfelix 1.1.2.29
1460 pnkfelix 1.1.2.29 doHide(n.wr);
1461 pnkfelix 1.1.2.29 }
1462 pnkfelix 1.1.2.29
1463 pnkfelix 1.1.2.29 private void doHide(WebRecord wr) {
1464 pnkfelix 1.1.2.29 if (hidden.contains(wr)) {
1465 pnkfelix 1.1.2.16 return;
1466 pnkfelix 1.1.2.16 }
1467 pnkfelix 1.1.2.29 nodes.removeAll( nodes(wr) );
1468 pnkfelix 1.1.2.16 Iterator nbors;
1469 pnkfelix 1.1.2.29 for(nbors=wr.adjnds.iterator(); nbors.hasNext();){
1470 pnkfelix 1.1.2.16 WebRecord nbor = (WebRecord) nbors.next();
1471 pnkfelix 1.1.2.29 nbor.adjnds.remove(wr);
1472 pnkfelix 1.1.2.29 }
1473 pnkfelix 1.1.2.29 hidden.addLast(wr);
1474 pnkfelix 1.1.2.29
1475 cananian 1.6 for(Object nO : nodes(wr)) {
1476 cananian 1.6 Node n = (Node) nO;
1477 cananian 1.6 for(Object _nO : n.adjT) {
1478 cananian 1.6 Node _n = (Node) _nO;
1479 cananian 1.3.2.1 assert _n.wr instanceof TempWebRecord : _n.wr;
1480 pnkfelix 1.1.2.29 _n.adjT.remove(n);
1481 pnkfelix 1.1.2.29 }
1482 pnkfelix 1.1.2.6 }
1483 pnkfelix 1.1.2.6 }
1484 pnkfelix 1.1.2.15
1485 pnkfelix 1.1.2.6 public Object replace() {
1486 pnkfelix 1.1.2.14 WebRecord wr;
1487 pnkfelix 1.1.2.6 try {
1488 pnkfelix 1.1.2.14 wr = (WebRecord) hidden.removeLast();
1489 pnkfelix 1.1.2.6 } catch (java.util.NoSuchElementException e) {
1490 pnkfelix 1.1.2.16 return null;
1491 pnkfelix 1.1.2.6 }
1492 pnkfelix 1.1.2.29 nodes.addAll( nodes(wr) );
1493 cananian 1.6 for(Object nborO : wr.adjnds){
1494 cananian 1.6 WebRecord nbor = (WebRecord) nborO;
1495 pnkfelix 1.1.2.29 if (!nbor.adjnds.contains(wr)) {
1496 pnkfelix 1.1.2.29 nbor.adjnds.add(wr);
1497 pnkfelix 1.1.2.29 }
1498 pnkfelix 1.1.2.29 }
1499 pnkfelix 1.1.2.16
1500 cananian 1.6 for(Object nO : nodes(wr)){
1501 cananian 1.6 Node n = (Node) nO;
1502 cananian 1.6 for(Object _nO : n.adjT) {
1503 cananian 1.6 Node _n = (Node) _nO;
1504 cananian 1.3.2.1 assert _n.wr instanceof TempWebRecord;
1505 pnkfelix 1.1.2.29 _n.adjT.add(n);
1506 pnkfelix 1.1.2.29 }
1507 pnkfelix 1.1.2.29 }
1508 pnkfelix 1.1.2.29
1509 cananian 1.6 for(Object nO : nodes(wr)){
1510 cananian 1.6 Node n = (Node) nO;
1511 pnkfelix 1.1.2.16 if (n.index == 0) return n;
1512 pnkfelix 1.1.2.16 }
1513 pnkfelix 1.1.2.16
1514 pnkfelix 1.1.2.16 throw new RuntimeException();
1515 pnkfelix 1.1.2.6 }
1516 pnkfelix 1.1.2.6 public void replaceAll() {
1517 pnkfelix 1.1.2.6 while(!hidden.isEmpty()) {
1518 pnkfelix 1.1.2.6 replace();
1519 pnkfelix 1.1.2.6 }
1520 pnkfelix 1.1.2.6 }
1521 pnkfelix 1.1.2.6 public Color getColor(Object n) {
1522 pnkfelix 1.1.2.29 Node nd;
1523 pnkfelix 1.1.2.29 try { nd = (Node) n; return nd.color;
1524 pnkfelix 1.1.2.17 } catch (ClassCastException e) {
1525 pnkfelix 1.1.2.17 throw new IllegalArgumentException();
1526 pnkfelix 1.1.2.6 }
1527 pnkfelix 1.1.2.6 }
1528 pnkfelix 1.1.2.6
1529 pnkfelix 1.1.2.6 public void resetColors() {
1530 pnkfelix 1.1.2.6 Iterator ns;
1531 pnkfelix 1.1.2.14 for(ns = nodes.iterator(); ns.hasNext();) {
1532 pnkfelix 1.1.2.15 ((Node) ns.next()).color = null;
1533 pnkfelix 1.1.2.6 }
1534 pnkfelix 1.1.2.16 for(Iterator wrs = hidden.iterator(); wrs.hasNext();) {
1535 pnkfelix 1.1.2.16 for(ns=nodes((WebRecord)wrs.next()).iterator();ns.hasNext();){
1536 pnkfelix 1.1.2.16 ((Node) ns.next()).color = null;
1537 pnkfelix 1.1.2.16 }
1538 pnkfelix 1.1.2.6 }
1539 pnkfelix 1.1.2.6 }
1540 pnkfelix 1.1.2.6
1541 pnkfelix 1.1.2.30 public void unsetColor(Object o) {
1542 pnkfelix 1.1.2.30 try {
1543 pnkfelix 1.1.2.30 Node nd = (Node) o;
1544 cananian 1.6 for(Object nO : nodes(nd.wr)){
1545 cananian 1.6 Node n = (Node) nO;
1546 pnkfelix 1.1.2.30 n.color = null;
1547 pnkfelix 1.1.2.30 }
1548 pnkfelix 1.1.2.30 } catch (ClassCastException e) {
1549 pnkfelix 1.1.2.30 throw new IllegalArgumentException();
1550 pnkfelix 1.1.2.30 }
1551 pnkfelix 1.1.2.30 }
1552 pnkfelix 1.1.2.30
1553 pnkfelix 1.1.2.16 public void setColor(Object o, Color col)
1554 pnkfelix 1.1.2.16 throws ColorableGraph.IllegalColor {
1555 cananian 1.3.2.1 assert col != null;
1556 pnkfelix 1.1.2.6 try {
1557 pnkfelix 1.1.2.16 Node node = (Node) o;
1558 cananian 1.3.2.1 assert node.index == 0 : "setColor on bad node "+node;
1559 pnkfelix 1.1.2.16 RegColor rc = (RegColor) col;
1560 pnkfelix 1.1.2.16 Collection nds = nodes(node.wr);
1561 pnkfelix 1.1.2.29 Map[] i2r2a = (Map[]) implicitAssigns.get(node.wr.temp());
1562 pnkfelix 1.1.2.29 Map r2a = i2r2a[node.index];
1563 pnkfelix 1.1.2.16 if (!r2a.keySet().contains(rc.reg))
1564 pnkfelix 1.1.2.16 throw new ColorableGraph.IllegalColor(o, col);
1565 pnkfelix 1.1.2.16 List assign = (List) r2a.get(rc.reg);
1566 pnkfelix 1.1.2.17
1567 pnkfelix 1.1.2.17 // verify all color choices
1568 cananian 1.6 for(Object nO : nds) {
1569 cananian 1.6 Node n = (Node) nO;
1570 pnkfelix 1.1.2.17 Temp t = (Temp) assign.get(n.index);
1571 pnkfelix 1.1.2.17 rc = regToColor(t);
1572 pnkfelix 1.1.2.17 Iterator nbs;
1573 pnkfelix 1.1.2.17 for(nbs=neighborsOf(n).iterator();nbs.hasNext();){
1574 pnkfelix 1.1.2.17 Node nb = (Node) nbs.next();
1575 pnkfelix 1.1.2.22 if (nb.color != null &&
1576 pnkfelix 1.1.2.22 nb.color.equals(rc)) {
1577 pnkfelix 1.1.2.17 throw new ColorableGraph.IllegalColor(n,rc);
1578 pnkfelix 1.1.2.17 }
1579 pnkfelix 1.1.2.17 }
1580 pnkfelix 1.1.2.17 if (false) System.out.println
1581 pnkfelix 1.1.2.17 (n+" passed verify for "+rc+
1582 pnkfelix 1.1.2.17 ", neighbors:"+neighborsOf(n));
1583 pnkfelix 1.1.2.17 }
1584 pnkfelix 1.1.2.17
1585 pnkfelix 1.1.2.17 // got here, colors passed verification
1586 cananian 1.6 for(Object nO : nds){
1587 cananian 1.6 Node n = (Node) nO;
1588 pnkfelix 1.1.2.16 Temp t = (Temp) assign.get(n.index);
1589 pnkfelix 1.1.2.16 rc = regToColor(t);
1590 pnkfelix 1.1.2.16 n.color = rc;
1591 pnkfelix 1.1.2.16 if (false) System.out.println("set color of "+n);
1592 pnkfelix 1.1.2.16 }
1593 pnkfelix 1.1.2.6 } catch (ClassCastException e) {
1594 pnkfelix 1.1.2.6 throw new IllegalArgumentException();
1595 pnkfelix 1.1.2.6 }
1596 pnkfelix 1.1.2.6 }
1597 pnkfelix 1.1.2.5 }
1598 pnkfelix 1.1.2.5
1599 pnkfelix 1.1.2.21 class StatGather {
1600 pnkfelix 1.1.2.21 int sum=0; int sumSq=0; int cnt=0;
1601 pnkfelix 1.1.2.21 void add(int elem) { cnt++; sum+=elem; sumSq+=elem*elem; }
1602 pnkfelix 1.1.2.21 int size() { return cnt; }
1603 pnkfelix 1.1.2.21 int mean() { return sum / cnt; }
1604 pnkfelix 1.1.2.21 int variance() { int m=mean(); return sumSq/cnt - m*m; }
1605 pnkfelix 1.1.2.21 public String toString() {
1606 pnkfelix 1.1.2.21 return "Stat<size:"+size()+" mean:"+mean()+" var:"+variance()+">";
1607 pnkfelix 1.1.2.21 }
1608 pnkfelix 1.1.2.21 }
1609 pnkfelix 1.1.2.21
1610 pnkfelix 1.1.2.41 static void printConflictTime() {
1611 pnkfelix 1.1.2.41 System.out.println("conflict time -"+
1612 pnkfelix 1.1.2.41 " tnr: "+rntwrNumChecks+
1613 pnkfelix 1.1.2.41 " (num:"+rnrwrNumChecks+
1614 pnkfelix 1.1.2.41 " ave:"+(rntwrNumChecks/rnrwrNumChecks)+")"+
1615 pnkfelix 1.1.2.41 " twr: "+twrConflictTime+
1616 pnkfelix 1.1.2.41 " (num:"+twrNumConflicts+
1617 pnkfelix 1.1.2.41 " ave:"+(twrConflictTime/twrNumConflicts)+")"+
1618 pnkfelix 1.1.2.41 " rwr: "+rwrConflictTime+
1619 pnkfelix 1.1.2.41 " (num:"+rwrNumConflicts+
1620 pnkfelix 1.1.2.41 " ave:"+(rwrConflictTime/rwrNumConflicts)+")");
1621 pnkfelix 1.1.2.41 rwrConflictTime = twrConflictTime = 1;
1622 pnkfelix 1.1.2.41 rwrNumConflicts = twrNumConflicts = 1;
1623 pnkfelix 1.1.2.41 rnrwrNumChecks = rntwrNumChecks = 1;
1624 pnkfelix 1.1.2.41 }
1625 pnkfelix 1.1.2.41 static long rwrConflictTime = 0; static int rwrNumConflicts = 0;
1626 pnkfelix 1.1.2.41 static long twrConflictTime = 0; static int twrNumConflicts = 0;
1627 pnkfelix 1.1.2.41 static int rntwrNumChecks = 1, rnrwrNumChecks = 1;
1628 pnkfelix 1.1.2.5 abstract class WebRecord {
1629 pnkfelix 1.1.2.6 int nints, disp;
1630 pnkfelix 1.1.2.6 double spcost;
1631 pnkfelix 1.1.2.6 List adjnds; // List<WebRecord>
1632 pnkfelix 1.1.2.6
1633 pnkfelix 1.1.2.9 private int sreg;
1634 pnkfelix 1.1.2.9 private boolean sregYet = false;
1635 pnkfelix 1.1.2.6
1636 pnkfelix 1.1.2.15 WebRecord() {
1637 pnkfelix 1.1.2.6 nints = 0;
1638 pnkfelix 1.1.2.6 disp = Integer.MIN_VALUE;
1639 pnkfelix 1.1.2.6 spcost = 0.0;
1640 pnkfelix 1.1.2.6 adjnds = new LinkedList();
1641 pnkfelix 1.1.2.6 }
1642 pnkfelix 1.1.2.9
1643 cananian 1.3.2.1 int sreg() { assert sregYet; return sreg; }
1644 pnkfelix 1.1.2.5 void sreg(int val) {
1645 cananian 1.3.2.1 assert !sregYet;
1646 pnkfelix 1.1.2.5 sreg = val;
1647 pnkfelix 1.1.2.9 sregYet = true;
1648 pnkfelix 1.1.2.28 }
1649 pnkfelix 1.1.2.28
1650 pnkfelix 1.1.2.28 /** Returns true if this shares a use/def with wr. */
1651 pnkfelix 1.1.2.28 boolean overlaps(WebRecord wr) {
1652 pnkfelix 1.1.2.28 HashSet refs =
1653 pnkfelix 1.1.2.28 new HashSet( defs().size() + uses().size() );
1654 pnkfelix 1.1.2.28 refs.addAll(defs());
1655 pnkfelix 1.1.2.28 refs.addAll(uses());
1656 pnkfelix 1.1.2.28 HashSet rfs2 = new HashSet(refs);
1657 pnkfelix 1.1.2.28 if (refs.retainAll(wr.defs()) ||
1658 pnkfelix 1.1.2.28 rfs2.retainAll(wr.uses())) {
1659 pnkfelix 1.1.2.34 if (SCARY_OUTPUT) System.out.println(this + " overlaps " + wr);
1660 pnkfelix 1.1.2.28 return true;
1661 pnkfelix 1.1.2.28 }
1662 pnkfelix 1.1.2.34 if (SCARY_OUTPUT) System.out.println(this + " does NOT overlap " + wr);
1663 pnkfelix 1.1.2.28 return false;
1664 pnkfelix 1.1.2.9 }
1665 pnkfelix 1.1.2.9
1666 pnkfelix 1.1.2.8 // ( interference based on Muchnick, page 494.)
1667 pnkfelix 1.1.2.5 boolean conflictsWith(WebRecord wr) {
1668 pnkfelix 1.1.2.41 long immed_conflict_time, reg_conflict_time=0, start_time;
1669 pnkfelix 1.1.2.41
1670 pnkfelix 1.1.2.41 start_time = System.currentTimeMillis();
1671 pnkfelix 1.1.2.27 boolean r =
1672 pnkfelix 1.1.2.27 this.conflictsWith1D(wr) ||
1673 pnkfelix 1.1.2.9 wr.conflictsWith1D(this);
1674 pnkfelix 1.1.2.41 immed_conflict_time = System.currentTimeMillis() - start_time;
1675 pnkfelix 1.1.2.27 if (!r &&
1676 pnkfelix 1.1.2.27 webPrecolor.containsKey(this)) {
1677 pnkfelix 1.1.2.27 WebRecord rwr = (WebRecord)
1678 pnkfelix 1.1.2.27 regToWeb.get(webPrecolor.get(this));
1679 pnkfelix 1.1.2.41
1680 pnkfelix 1.1.2.41 start_time = System.currentTimeMillis();
1681 pnkfelix 1.1.2.27 r = rwr.conflictsWith(wr);
1682 pnkfelix 1.1.2.41 reg_conflict_time = System.currentTimeMillis() - start_time;
1683 pnkfelix 1.1.2.27 }
1684 pnkfelix 1.1.2.41 if (false && reg_conflict_time > 10)
1685 pnkfelix 1.1.2.41 System.out.println("conflict compute time, imm: "+
1686 pnkfelix 1.1.2.41 immed_conflict_time+" reg: "+
1687 pnkfelix 1.1.2.41 reg_conflict_time);
1688 pnkfelix 1.1.2.27 return r;
1689 pnkfelix 1.1.2.9 }
1690 pnkfelix 1.1.2.9
1691 pnkfelix 1.1.2.9 // one directional conflict check (helper function)
1692 pnkfelix 1.1.2.9 // if this is live at a def in wr, returns true.
1693 pnkfelix 1.1.2.12 boolean conflictsWith1D(WebRecord wr) {
1694 pnkfelix 1.1.2.41 long start_time = System.currentTimeMillis();
1695 pnkfelix 1.1.2.41 boolean r = false;
1696 cananian 1.6 for(Object dO : this.defs()){
1697 cananian 1.6 Instr d = (Instr) dO;
1698 pnkfelix 1.1.2.42
1699 pnkfelix 1.1.2.42 // "a,b := f()" ==> a and b interfere, even though
1700 pnkfelix 1.1.2.42 // there may not be any defs of either that "reach"
1701 pnkfelix 1.1.2.42 // this statement (a statement need not reach itself)
1702 pnkfelix 1.1.2.42 if (wr.defs().contains( d ))
1703 pnkfelix 1.1.2.42 return true;
1704 pnkfelix 1.1.2.42
1705 pnkfelix 1.1.2.11 Set l= liveTemps.getLiveAfter(d);
1706 pnkfelix 1.1.2.33 if(l.contains(wr.temp())) {
1707 pnkfelix 1.1.2.25 if (wr instanceof RegWebRecord) {
1708 pnkfelix 1.1.2.41 r = true;
1709 pnkfelix 1.1.2.41 break;
1710 pnkfelix 1.1.2.25 }
1711 pnkfelix 1.1.2.33
1712 pnkfelix 1.1.2.19 HashSet wDefs = new HashSet
1713 pnkfelix 1.1.2.19 (rdefs.reachingDefs(d, wr.temp()));
1714 pnkfelix 1.1.2.19 wDefs.retainAll(wr.defs());
1715 pnkfelix 1.1.2.25 if (!wDefs.isEmpty()) {
1716 pnkfelix 1.1.2.41 r = true;
1717 pnkfelix 1.1.2.41 break;
1718 pnkfelix 1.1.2.25 }
1719 pnkfelix 1.1.2.19 }
1720 pnkfelix 1.1.2.41
1721 pnkfelix 1.1.2.5 }
1722 pnkfelix 1.1.2.41 twrConflictTime += System.currentTimeMillis() - start_time;
1723 pnkfelix 1.1.2.41 twrNumConflicts++;
1724 pnkfelix 1.1.2.41 return r;
1725 pnkfelix 1.1.2.5 }
1726 pnkfelix 1.1.2.9
1727 pnkfelix 1.1.2.5 // returns the set of instrs that this web holds definitions
1728 pnkfelix 1.1.2.5 // for. These instrs are used to detect conflicts between
1729 pnkfelix 1.1.2.5 // webs.
1730 pnkfelix 1.1.2.5 abstract Set defs();
1731 pnkfelix 1.1.2.9
1732 pnkfelix 1.1.2.9 // returns the set of instrs that this web holds uses
1733 pnkfelix 1.1.2.9 // for. These instrs are used to detect conflicts between
1734 pnkfelix 1.1.2.9 // webs.
1735 pnkfelix 1.1.2.9 abstract Set uses();
1736 pnkfelix 1.1.2.9
1737 pnkfelix 1.1.2.13 // returns the Temp that this WebRecord represents.
1738 pnkfelix 1.1.2.13 abstract Temp temp();
1739 pnkfelix 1.1.2.5
1740 pnkfelix 1.1.2.13 public String toString() { return "w:"+temp(); }
1741 pnkfelix 1.1.2.13 }
1742 pnkfelix 1.1.2.9
1743 pnkfelix 1.1.2.13 class RegWebRecord extends WebRecord {
1744 pnkfelix 1.1.2.13 final Temp reg;
1745 pnkfelix 1.1.2.13 RegWebRecord(Temp reg) {
1746 pnkfelix 1.1.2.15 super();
1747 pnkfelix 1.1.2.13 this.reg = reg;
1748 pnkfelix 1.1.2.13 }
1749 pnkfelix 1.1.2.33 public int hashCode() { return reg.hashCode(); }
1750 pnkfelix 1.1.2.33 public boolean equals(Object o) {
1751 pnkfelix 1.1.2.33 if (o == this)
1752 pnkfelix 1.1.2.33 return true;
1753 pnkfelix 1.1.2.33 if (o != null && o instanceof RegWebRecord) {
1754 pnkfelix 1.1.2.33 return reg.equals(((RegWebRecord)o).reg);
1755 pnkfelix 1.1.2.33 } else {
1756 pnkfelix 1.1.2.33 return false;
1757 pnkfelix 1.1.2.33 }
1758 pnkfelix 1.1.2.33 }
1759 pnkfelix 1.1.2.13 public Set defs() { return (Set) regToDefs.getValues(reg); }
1760 pnkfelix 1.1.2.13 public Set uses() { return (Set) regToUses.getValues(reg); }
1761 pnkfelix 1.1.2.13 public Temp temp() { return reg; }
1762 pnkfelix 1.1.2.9
1763 pnkfelix 1.1.2.23 boolean conflictsWith1D(WebRecord wr) {
1764 pnkfelix 1.1.2.41 long start_time = System.currentTimeMillis();
1765 pnkfelix 1.1.2.41 boolean r;
1766 pnkfelix 1.1.2.13 if (wr instanceof RegWebRecord) {
1767 pnkfelix 1.1.2.41 r = true;
1768 pnkfelix 1.1.2.5 } else {
1769 pnkfelix 1.1.2.41 r = super.conflictsWith1D(wr);
1770 pnkfelix 1.1.2.27 if (!r &&
1771 pnkfelix 1.1.2.27 webPrecolor.invert().containsKey(reg)) {
1772 pnkfelix 1.1.2.41 Collection preWebsForReg = webPrecolor.invert().getValues(reg);
1773 pnkfelix 1.1.2.41 int nms=0;
1774 pnkfelix 1.1.2.41 Iterator wbs = preWebsForReg.iterator();
1775 pnkfelix 1.1.2.41 while(wbs.hasNext()) { nms++;
1776 pnkfelix 1.1.2.27 WebRecord _wr = (WebRecord) wbs.next();
1777 pnkfelix 1.1.2.27 if (_wr.conflictsWith1D(wr) ||
1778 pnkfelix 1.1.2.27 wr.conflictsWith1D(_wr)) {
1779 pnkfelix 1.1.2.41 r = true;
1780 pnkfelix 1.1.2.41 break;
1781 pnkfelix 1.1.2.27 }
1782 pnkfelix 1.1.2.27 }
1783 pnkfelix 1.1.2.41 rntwrNumChecks+=nms; rnrwrNumChecks++;
1784 pnkfelix 1.1.2.27 }
1785 pnkfelix 1.1.2.5 }
1786 pnkfelix 1.1.2.41 rwrConflictTime += System.currentTimeMillis() - start_time;
1787 pnkfelix 1.1.2.41 rwrNumConflicts++;
1788 pnkfelix 1.1.2.41 return r;
1789 pnkfelix 1.1.2.5 }
1790 pnkfelix 1.1.2.5 }
1791 pnkfelix 1.1.2.5
1792 pnkfelix 1.1.2.9 // converts a Set<Instr>:s1 into a Set<Integer>:s2 where the
1793 pnkfelix 1.1.2.9 // elements in s2 correspond to the IDs of the instructions in s1
1794 pnkfelix 1.1.2.9 private static Integer i2int(Instr i) { return new Integer(i.getID()); }
1795 pnkfelix 1.1.2.9 private static Set readable(final Set instrs) {
1796 pnkfelix 1.1.2.9 final FilterIterator.Filter fltr = new FilterIterator.Filter() {
1797 pnkfelix 1.1.2.9 public Object map(Object o) { return i2int((Instr)o); }
1798 pnkfelix 1.1.2.9 };
1799 pnkfelix 1.1.2.9 return new AbstractSet() {
1800 pnkfelix 1.1.2.9 public int size() { return instrs.size(); }
1801 pnkfelix 1.1.2.9 public Iterator iterator() {
1802 pnkfelix 1.1.2.9 return new FilterIterator(instrs.iterator(), fltr);
1803 pnkfelix 1.1.2.9 }
1804 pnkfelix 1.1.2.9 };
1805 pnkfelix 1.1.2.9 }
1806 pnkfelix 1.1.2.9
1807 pnkfelix 1.1.2.5 class TempWebRecord extends WebRecord {
1808 pnkfelix 1.1.2.5 Temp sym;
1809 pnkfelix 1.1.2.5 Set defs, uses; // Set<Instr>
1810 pnkfelix 1.1.2.5 boolean spill;
1811 pnkfelix 1.1.2.5 int disp;
1812 pnkfelix 1.1.2.33
1813 pnkfelix 1.1.2.33 public int hashCode() { return sym.hashCode(); }
1814 pnkfelix 1.1.2.33 public boolean equals(Object o) {
1815 pnkfelix 1.1.2.33 if (o == this)
1816 pnkfelix 1.1.2.33 return true;
1817 pnkfelix 1.1.2.33 if (o != null && o instanceof TempWebRecord) {
1818 pnkfelix 1.1.2.33 TempWebRecord t = (TempWebRecord) o;
1819 pnkfelix 1.1.2.33 return sym.equals(t.sym) &&
1820 pnkfelix 1.1.2.33 defs.equals(t.defs) &&
1821 pnkfelix 1.1.2.33 uses.equals(t.uses);
1822 pnkfelix 1.1.2.33 } else {
1823 pnkfelix 1.1.2.33 return false;
1824 pnkfelix 1.1.2.33 }
1825 pnkfelix 1.1.2.33 }
1826 pnkfelix 1.1.2.5 TempWebRecord(Temp symbol, Set defSet, Set useSet) {
1827 pnkfelix 1.1.2.15 super();
1828 pnkfelix 1.1.2.5 sym = symbol; defs = defSet; uses = useSet;
1829 pnkfelix 1.1.2.9 spill = false; disp = -1;
1830 cananian 1.3.2.1 assert !isRegister(sym);
1831 pnkfelix 1.1.2.5 }
1832 pnkfelix 1.1.2.5
1833 pnkfelix 1.1.2.13 public Temp temp() { return sym; }
1834 pnkfelix 1.1.2.12 public Set defs() { return Collections.unmodifiableSet(defs);}
1835 pnkfelix 1.1.2.12 public Set uses() { return Collections.unmodifiableSet(uses);}
1836 pnkfelix 1.1.2.7
1837 pnkfelix 1.1.2.5 public String toString() {
1838 pnkfelix 1.1.2.12 List a = (List) rfi.getRegAssignments(sym).iterator().next();
1839 pnkfelix 1.1.2.22 if (true)
1840 pnkfelix 1.1.2.21 return "<web sym:"+sym+
1841 pnkfelix 1.1.2.7 ", defs:"+readable(defs)+
1842 pnkfelix 1.1.2.7 ", uses:"+readable(uses)+
1843 pnkfelix 1.1.2.12 ((a.size()==1)?", single-word":", multi-word")+
1844 pnkfelix 1.1.2.7 " >";
1845 pnkfelix 1.1.2.7 else
1846 pnkfelix 1.1.2.21 return "w:"+sym+" degree:"+adjnds.size();
1847 pnkfelix 1.1.2.5 }
1848 pnkfelix 1.1.2.5 }
1849 pnkfelix 1.1.2.5
1850 pnkfelix 1.1.2.5 class AdjMtx {
1851 pnkfelix 1.1.2.21 // a Lower Triangular Matrix backed by a HashSet of IntPairs
1852 pnkfelix 1.1.2.21 HashSet pairSet;
1853 pnkfelix 1.1.2.21 AdjMtx(List symReg) {
1854 pnkfelix 1.1.2.21 pairSet = new HashSet(symReg.size());
1855 pnkfelix 1.1.2.21 }
1856 pnkfelix 1.1.2.21 public boolean get(int x, int y) {
1857 pnkfelix 1.1.2.21 return pairSet.contains(new IntPair(x, y));
1858 pnkfelix 1.1.2.21 }
1859 pnkfelix 1.1.2.21 public void set(int x, int y, boolean b) {
1860 pnkfelix 1.1.2.21 IntPair p = new IntPair(x, y);
1861 pnkfelix 1.1.2.21 if (b) {
1862 pnkfelix 1.1.2.21 pairSet.add(p);
1863 pnkfelix 1.1.2.21 } else {
1864 pnkfelix 1.1.2.21 pairSet.remove(p);
1865 pnkfelix 1.1.2.21 }
1866 pnkfelix 1.1.2.21 }
1867 pnkfelix 1.1.2.21 class IntPair {
1868 pnkfelix 1.1.2.21 final int m,n;
1869 pnkfelix 1.1.2.21 IntPair(int x, int y) {
1870 pnkfelix 1.1.2.21 if (x > y) {
1871 pnkfelix 1.1.2.21 m=x; n=y;
1872 pnkfelix 1.1.2.21 } else {
1873 pnkfelix 1.1.2.21 m=y; n=x;
1874 pnkfelix 1.1.2.21 }
1875 pnkfelix 1.1.2.21 }
1876 pnkfelix 1.1.2.33 public int hashCode() { return ((m<<16)|(m>>16)) ^ n; }
1877 pnkfelix 1.1.2.21 public boolean equals(Object o) {
1878 pnkfelix 1.1.2.21 IntPair p = (IntPair) o;
1879 pnkfelix 1.1.2.21 return m == p.m && n == p.n;
1880 pnkfelix 1.1.2.21 }
1881 pnkfelix 1.1.2.21 }
1882 pnkfelix 1.1.2.21
1883 pnkfelix 1.1.2.21 }
1884 pnkfelix 1.1.2.21
1885 pnkfelix 1.1.2.21 class AdjMtxOld {
1886 pnkfelix 1.1.2.13 // a Lower Triangular Matrix backed by a BitString. Note that
1887 pnkfelix 1.1.2.13 // for Lower Triangular Matrix, order of coordinate args is
1888 pnkfelix 1.1.2.13 // insignificant (from p.o.v. of user).
1889 pnkfelix 1.1.2.13
1890 cananian 1.5 final net.cscott.jutil.BitString bits;
1891 pnkfelix 1.1.2.11 final int side;
1892 pnkfelix 1.1.2.21 AdjMtxOld(List symReg) {
1893 pnkfelix 1.1.2.11 side = symReg.size();
1894 cananian 1.5 bits = new net.cscott.jutil.BitString(side * side / 2);
1895 pnkfelix 1.1.2.11 }
1896 pnkfelix 1.1.2.11 boolean get(int x, int y) {
1897 cananian 1.3.2.1 assert x != y;
1898 cananian 1.3.2.1 assert x < side;
1899 cananian 1.3.2.1 assert y < side;
1900 pnkfelix 1.1.2.11 return bits.get(convert(x,y));
1901 pnkfelix 1.1.2.11 }
1902 pnkfelix 1.1.2.11 void set(int x, int y, boolean b) {
1903 cananian 1.3.2.1 assert x != y;
1904 cananian 1.3.2.1 assert x < side;
1905 cananian 1.3.2.1 assert y < side;
1906 pnkfelix 1.1.2.11 if (b) bits.set(convert(x,y));
1907 pnkfelix 1.1.2.11 else bits.clear(convert(x,y));
1908 cananian 1.3.2.1 assert get(x,y) == b;
1909 pnkfelix 1.1.2.11 }
1910 pnkfelix 1.1.2.11 private int convert(int x, int y) {
1911 pnkfelix 1.1.2.18 if (x > y) return offset(x) + y;
1912 pnkfelix 1.1.2.11 else return offset(y) + x;
1913 pnkfelix 1.1.2.11 }
1914 pnkfelix 1.1.2.18 private int offset(int x) { return (x * (x - 1)) / 2; }
1915 pnkfelix 1.1.2.32 }
1916 pnkfelix 1.1.2.32
1917 pnkfelix 1.1.2.32 // only defined for unions of WebRecords
1918 cananian 1.5 class EqWebRecords extends net.cscott.jutil.DisjointSet {
1919 pnkfelix 1.1.2.32 private HashSet temps = new HashSet();
1920 pnkfelix 1.1.2.35 MultiMap wrToEqwrs = new GenericMultiMap();
1921 pnkfelix 1.1.2.35
1922 pnkfelix 1.1.2.32 public boolean containsTemp(Temp t) {
1923 pnkfelix 1.1.2.32 return temps.contains(t);
1924 pnkfelix 1.1.2.32 }
1925 pnkfelix 1.1.2.32 public Instr rename(final Instr i) {
1926 pnkfelix 1.1.2.32 TempMap tmap = new TempMap() {
1927 pnkfelix 1.1.2.32 public Temp tempMap(Temp tmp) {
1928 pnkfelix 1.1.2.32 WebRecord wr = getWR(i,tmp);
1929 pnkfelix 1.1.2.32 if (wr == null) return tmp;
1930 pnkfelix 1.1.2.32 wr = (WebRecord) find(wr);
1931 pnkfelix 1.1.2.32 return wr.temp();
1932 pnkfelix 1.1.2.32 }
1933 pnkfelix 1.1.2.32 };
1934 pnkfelix 1.1.2.32 return i.rename(tmap);
1935 pnkfelix 1.1.2.32 }
1936 pnkfelix 1.1.2.32 public void union(Object a, Object b) {
1937 pnkfelix 1.1.2.38 if ( super.find(a).equals(super.find(b)))
1938 pnkfelix 1.1.2.38 return;
1939 pnkfelix 1.1.2.35
1940 pnkfelix 1.1.2.38 WebRecord wrA = (WebRecord) a;
1941 pnkfelix 1.1.2.38 WebRecord wrB = (WebRecord) b;
1942 pnkfelix 1.1.2.41 if (UNIFY_INFO)
1943 pnkfelix 1.1.2.41 System.out.println("unioning0 "
1944 pnkfelix 1.1.2.41 +" ("+System.identityHashCode(super.find(wrA))+")"
1945 pnkfelix 1.1.2.41 +" ("+System.identityHashCode(super.find(wrB))+")"
1946 pnkfelix 1.1.2.41 );
1947 pnkfelix 1.1.2.38 if (UNIFY_INFO)
1948 pnkfelix 1.1.2.41 System.out.println(" unioning1 " + asTemps(unified(wrA))
1949 pnkfelix 1.1.2.41 + " and " + asTemps(unified(wrB))
1950 pnkfelix 1.1.2.41 );
1951 pnkfelix 1.1.2.35
1952 pnkfelix 1.1.2.38 Collection as = unified(wrA);
1953 pnkfelix 1.1.2.38 Collection bs = unified(wrB);
1954 pnkfelix 1.1.2.38
1955 pnkfelix 1.1.2.38 temps.add( wrA.temp() );
1956 pnkfelix 1.1.2.38 temps.add( wrB.temp() );
1957 pnkfelix 1.1.2.38 super.union(super.find(wrA), super.find(wrB));
1958 pnkfelix 1.1.2.35
1959 pnkfelix 1.1.2.38 // clear old mappings
1960 pnkfelix 1.1.2.38 wrToEqwrs.remove(wrA);
1961 pnkfelix 1.1.2.38 wrToEqwrs.remove(wrB);
1962 pnkfelix 1.1.2.35
1963 pnkfelix 1.1.2.38 if (UNIFY_INFO)
1964 pnkfelix 1.1.2.38 System.out.println(" unioning2 " + asTemps(unified(wrA))
1965 pnkfelix 1.1.2.38 + " and " + asTemps(unified(wrB)));
1966 pnkfelix 1.1.2.38
1967 pnkfelix 1.1.2.38 wrToEqwrs.addAll(super.find(wrA), as);
1968 pnkfelix 1.1.2.38 wrToEqwrs.addAll(super.find(wrB), bs);
1969 pnkfelix 1.1.2.38
1970 pnkfelix 1.1.2.38 if (UNIFY_INFO)
1971 pnkfelix 1.1.2.38 System.out.println(" unioning3 " + asTemps(unified(wrA))
1972 pnkfelix 1.1.2.38 + " and " + asTemps(unified(wrB)));
1973 pnkfelix 1.1.2.35 }
1974 pnkfelix 1.1.2.35
1975 pnkfelix 1.1.2.35 boolean anyConflicting(WebRecord wr1, Collection wrs) {
1976 cananian 1.6 for(Object wr2O : wrs) {
1977 cananian 1.6 WebRecord wr2 = (WebRecord) wr2O;
1978 pnkfelix 1.1.2.38 if (real_conflicting(wr1, wr2))
1979 pnkfelix 1.1.2.35 return true;
1980 pnkfelix 1.1.2.35 }
1981 pnkfelix 1.1.2.35 return false;
1982 pnkfelix 1.1.2.35 }
1983 pnkfelix 1.1.2.35
1984 pnkfelix 1.1.2.35 boolean conflicting(WebRecord wr1, WebRecord wr2) {
1985 pnkfelix 1.1.2.38 boolean rtn = real_conflicting(wr1, wr2);
1986 pnkfelix 1.1.2.38 return rtn;
1987 pnkfelix 1.1.2.38 }
1988 pnkfelix 1.1.2.38
1989 pnkfelix 1.1.2.38 private Collection unified(WebRecord wr) {
1990 pnkfelix 1.1.2.38 Collection wrs = new ArrayList(wrToEqwrs.getValues(super.find(wr)));
1991 pnkfelix 1.1.2.38 wrs.add(wr);
1992 pnkfelix 1.1.2.38 return wrs;
1993 pnkfelix 1.1.2.38 }
1994 pnkfelix 1.1.2.38
1995 pnkfelix 1.1.2.38 private Collection asTemps(final Collection wrs) {
1996 pnkfelix 1.1.2.38 return new java.util.AbstractCollection() {
1997 pnkfelix 1.1.2.38 public int size() { return wrs.size(); }
1998 pnkfelix 1.1.2.38 public Iterator iterator() {
1999 pnkfelix 1.1.2.38 return new FilterIterator
2000 pnkfelix 1.1.2.38 (wrs.iterator(),
2001 pnkfelix 1.1.2.38 new FilterIterator.Filter() {
2002 pnkfelix 1.1.2.38 public Object map(Object o) {
2003 pnkfelix 1.1.2.38 return ((WebRecord)o).temp();
2004 pnkfelix 1.1.2.38 }
2005 pnkfelix 1.1.2.38 });
2006 pnkfelix 1.1.2.38 }
2007 pnkfelix 1.1.2.38 };
2008 pnkfelix 1.1.2.38 }
2009 pnkfelix 1.1.2.38 private boolean real_conflicting(WebRecord wr1, WebRecord wr2) {
2010 pnkfelix 1.1.2.38 Collection wrs1 = unified(wr1);
2011 pnkfelix 1.1.2.38 Collection wrs2 = unified(wr2);
2012 cananian 1.6 for(Object wrAO : wrs1) {
2013 cananian 1.6 WebRecord wrA = (WebRecord) wrAO;
2014 cananian 1.6 for(Object wrBO : wrs2) {
2015 cananian 1.6 WebRecord wrB = (WebRecord) wrBO;
2016 pnkfelix 1.1.2.35 if (wrA.conflictsWith(wrB))
2017 pnkfelix 1.1.2.35 return true;
2018 pnkfelix 1.1.2.35 }
2019 pnkfelix 1.1.2.35 }
2020 pnkfelix 1.1.2.35 return false;
2021 pnkfelix 1.1.2.32 }
2022 pnkfelix 1.1.2.11 }
2023 pnkfelix 1.1.2.11
2024 cananian 1.2 }