1 pnkfelix 1.1.2.1 // AppelRegAlloc.java, created Mon Feb 5 13:44:00 2001 by pnkfelix
2 cananian 1.1.2.4 // 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 cananian 1.1.2.2 import harpoon.Analysis.Instr.AppelRegAllocClasses.Web;
7 pnkfelix 1.1.2.13 import harpoon.Analysis.Instr.SpillHeuristics.SpillHeuristic;
8 pnkfelix 1.1.2.1
9 pnkfelix 1.1.2.1 import harpoon.IR.Assem.Instr;
10 pnkfelix 1.1.2.1 import harpoon.IR.Assem.InstrEdge;
11 pnkfelix 1.1.2.1 import harpoon.IR.Assem.InstrGroup;
12 pnkfelix 1.1.2.1 import harpoon.Backend.Generic.Code;
13 pnkfelix 1.1.2.1 import harpoon.IR.Properties.CFGrapher;
14 pnkfelix 1.1.2.1 import harpoon.IR.Properties.UseDefer;
15 pnkfelix 1.1.2.1 import harpoon.Temp.Temp;
16 pnkfelix 1.1.2.1
17 pnkfelix 1.1.2.1 import harpoon.Analysis.BasicBlock;
18 pnkfelix 1.1.2.1 import harpoon.Analysis.Maps.Derivation;
19 pnkfelix 1.1.2.1
20 pnkfelix 1.1.2.1 import harpoon.Analysis.ReachingDefs;
21 pnkfelix 1.1.2.1 import harpoon.Analysis.ReachingDefsAltImpl;
22 pnkfelix 1.1.2.1 import harpoon.Analysis.DataFlow.LiveTemps;
23 pnkfelix 1.1.2.1 import harpoon.Analysis.DataFlow.SpaceHeavyLiveTemps;
24 pnkfelix 1.1.2.1 import harpoon.Analysis.DataFlow.Solver;
25 pnkfelix 1.1.2.1
26 pnkfelix 1.1.2.1 import harpoon.Util.Util;
27 cananian 1.6 import net.cscott.jutil.Default;
28 cananian 1.6 import net.cscott.jutil.CombineIterator;
29 cananian 1.6 import net.cscott.jutil.FilterIterator;
30 cananian 1.6 import net.cscott.jutil.Factories;
31 cananian 1.6 import net.cscott.jutil.GenericMultiMap;
32 cananian 1.6 import net.cscott.jutil.LinearSet;
33 cananian 1.6 import net.cscott.jutil.MultiMap;
34 cananian 1.6 import net.cscott.jutil.ReverseIterator;
35 cananian 1.6 import net.cscott.jutil.UnmodifiableIterator;
36 pnkfelix 1.1.2.1
37 pnkfelix 1.1.2.1 import java.util.Map;
38 pnkfelix 1.1.2.1 import java.util.Collection;
39 pnkfelix 1.1.2.1 import java.util.AbstractCollection;
40 pnkfelix 1.1.2.1 import java.util.Collections;
41 pnkfelix 1.1.2.1 import java.util.Arrays;
42 pnkfelix 1.1.2.1 import java.util.Set;
43 pnkfelix 1.1.2.1 import java.util.AbstractSet;
44 pnkfelix 1.1.2.1 import java.util.HashSet;
45 pnkfelix 1.1.2.1 import java.util.HashMap;
46 pnkfelix 1.1.2.1 import java.util.List;
47 pnkfelix 1.1.2.1 import java.util.LinkedList;
48 cananian 1.7 import java.util.LinkedHashSet;
49 pnkfelix 1.1.2.1 import java.util.ArrayList;
50 pnkfelix 1.1.2.1 import java.util.Iterator;
51 pnkfelix 1.1.2.1
52 pnkfelix 1.1.2.1 /**
53 pnkfelix 1.1.2.1 * <code>AppelRegAlloc</code>
54 pnkfelix 1.1.2.1 *
55 cananian 1.1.2.4 * @author Felix S. Klock II <pnkfelix@mit.edu>
56 cananian 1.7 * @version $Id: AppelRegAlloc.java,v 1.7 2004/02/08 04:55:22 cananian Exp $
57 pnkfelix 1.1.2.1 */
58 pnkfelix 1.1.2.13 public abstract class AppelRegAlloc extends AppelRegAllocClasses {
59 pnkfelix 1.1.2.11 public static final boolean PRINT_DEPTH_TO_SPILL_INFO = true;
60 pnkfelix 1.1.2.13 public static final boolean PRINT_HEURISTIC_INFO = true;
61 pnkfelix 1.1.2.13 public static final boolean PRINT_CLEANING_INFO = true;
62 pnkfelix 1.1.2.10
63 pnkfelix 1.1.2.1
64 pnkfelix 1.1.2.12 private static final int NUM_CLEANINGS_TO_TRY = 2;
65 pnkfelix 1.1.2.13 private boolean try_to_clean = false; // FSK: turning off cleaning during FORCE_FELIX Experimentation
66 pnkfelix 1.1.2.11 // activates an extension to cleaning that doesn't spill defs that
67 pnkfelix 1.1.2.11 // are dead at the BasicBlock's end.
68 pnkfelix 1.1.2.12 private static final boolean CLEAN_BB_LOCAL_DEFS = false; // trackdown _213_javac
69 pnkfelix 1.1.2.6
70 pnkfelix 1.1.2.11 // activates a prepass removing "mov t0, t0" InstrMOVEs.
71 pnkfelix 1.1.2.11 private static final boolean TRIVIAL_MOVE_COALESCE = true;
72 pnkfelix 1.1.2.1 static RegAlloc.Factory FACTORY = new RegAlloc.Factory() {
73 pnkfelix 1.1.2.1 public RegAlloc makeRegAlloc(Code c) {
74 pnkfelix 1.1.2.13 return new AppelRegAllocStd(c);
75 pnkfelix 1.1.2.1 }
76 pnkfelix 1.1.2.1 };
77 pnkfelix 1.1.2.12
78 pnkfelix 1.1.2.7 /** Removes all spill code, resets statistical info, and turns off cleaning.
79 pnkfelix 1.1.2.7 */
80 pnkfelix 1.1.2.7 private void stopTryingToClean() {
81 pnkfelix 1.1.2.7 // Once rewrite crosses threshold, need to remove old spill
82 pnkfelix 1.1.2.7 // code so that the worst nodes will be respilled with
83 pnkfelix 1.1.2.7 // non-cleaned code. This is a bit of a hack to get around
84 pnkfelix 1.1.2.7 // problems with keeping information alive across the
85 pnkfelix 1.1.2.7 // recreation of the interference graph with new nodes and
86 pnkfelix 1.1.2.7 // such.
87 pnkfelix 1.1.2.7 for(Iterator instrs=code.getElementsI(); instrs.hasNext();){
88 pnkfelix 1.1.2.7 Instr i = (Instr) instrs.next();
89 pnkfelix 1.1.2.13 if (insertedSpillCode.contains(i)) {
90 pnkfelix 1.1.2.7 i.remove();
91 pnkfelix 1.1.2.7 }
92 pnkfelix 1.1.2.7 }
93 pnkfelix 1.1.2.13 insertedSpillCode.clear();
94 pnkfelix 1.1.2.11 dontSpillTheseDefs.clear();
95 pnkfelix 1.1.2.7 depthToNumSpills = new int[SPILL_STAT_DEPTH];
96 pnkfelix 1.1.2.7 try_to_clean = false;
97 pnkfelix 1.1.2.7 }
98 pnkfelix 1.1.2.13 HashSet insertedSpillCode = new HashSet();
99 pnkfelix 1.1.2.7
100 pnkfelix 1.1.2.1 int K; // size of register set
101 pnkfelix 1.1.2.1
102 pnkfelix 1.1.2.1 ReachingDefs rdefs;
103 pnkfelix 1.1.2.1 LiveTemps liveTemps;
104 pnkfelix 1.1.2.1
105 pnkfelix 1.1.2.1 CFGrapher grapher;
106 pnkfelix 1.1.2.1 UseDefer usedefer;
107 pnkfelix 1.1.2.1
108 pnkfelix 1.1.2.13 SpillHeuristics sh = new SpillHeuristics(this);
109 pnkfelix 1.1.2.13
110 pnkfelix 1.1.2.13 // Temp t -> Webs for t (rather than going through a Temp renaming
111 pnkfelix 1.1.2.13 // process on the whole method)
112 cananian 1.7 GenericMultiMap<Temp,Web> tempToWebs;
113 pnkfelix 1.1.2.13
114 pnkfelix 1.1.2.13
115 pnkfelix 1.1.2.7 static final int SPILL_STAT_DEPTH = 20;
116 pnkfelix 1.1.2.7 int[] depthToNumSpills;
117 pnkfelix 1.1.2.7 static int[] globalDepthToNumSpills = new int[SPILL_STAT_DEPTH];
118 pnkfelix 1.1.2.13 protected String spillStats(int[] stats){
119 pnkfelix 1.1.2.7 StringBuffer sb = new StringBuffer();
120 pnkfelix 1.1.2.7 for(int i=0; i<stats.length; i++) {
121 pnkfelix 1.1.2.7 if (stats[i] != 0)
122 pnkfelix 1.1.2.7 sb.append
123 pnkfelix 1.1.2.7 (",\tdepth:"+ i +
124 pnkfelix 1.1.2.7 " => spills:"+ stats[i] );
125 pnkfelix 1.1.2.7 }
126 pnkfelix 1.1.2.7 return sb.toString();
127 pnkfelix 1.1.2.7 }
128 pnkfelix 1.1.2.7
129 pnkfelix 1.1.2.7
130 pnkfelix 1.1.2.13 protected AppelRegAlloc(Code code) {
131 pnkfelix 1.1.2.1 super(code);
132 pnkfelix 1.1.2.1 K = rfi().getGeneralRegistersC().size();
133 pnkfelix 1.1.2.1 grapher= code.getInstrFactory().getGrapherFor ( InstrGroup.AGGREGATE );
134 pnkfelix 1.1.2.1 usedefer=code.getInstrFactory().getUseDeferFor( InstrGroup.AGGREGATE );
135 pnkfelix 1.1.2.1 // System.out.println("done constructing AppelRegAlloc");
136 pnkfelix 1.1.2.7 depthToNumSpills = new int[SPILL_STAT_DEPTH];
137 pnkfelix 1.1.2.1 }
138 pnkfelix 1.1.2.1
139 pnkfelix 1.1.2.5 boolean intersects(Collection a, Collection b) {
140 pnkfelix 1.1.2.5 HashSet ns = new HashSet(a);
141 pnkfelix 1.1.2.5 ns.retainAll(b);
142 pnkfelix 1.1.2.5 return ! ns.isEmpty();
143 pnkfelix 1.1.2.5 }
144 pnkfelix 1.1.2.5
145 pnkfelix 1.1.2.1 void buildTempToWebs() {
146 pnkfelix 1.1.2.1 // translated from code in GraphColoringRegAlloc
147 cananian 1.7 tempToWebs = new GenericMultiMap<Temp,Web>(Factories.<Web>arrayListFactory());
148 pnkfelix 1.1.2.1
149 pnkfelix 1.1.2.7 //for(Iterator instrs=code.getElementsI(); instrs.hasNext();){
150 pnkfelix 1.1.2.7 for(Iterator instrs=reachableInstrs(); instrs.hasNext();){
151 pnkfelix 1.1.2.1 Instr inst = (Instr) instrs.next();
152 cananian 1.7 for(Temp t : useCT(inst)){
153 pnkfelix 1.1.2.1 if (isRegister(t)) continue;
154 pnkfelix 1.1.2.1 Set defC = rdefs.reachingDefs(inst, t);
155 pnkfelix 1.1.2.1 Set useC = Collections.singleton(inst);
156 pnkfelix 1.1.2.1 addWeb( t, defC, useC );
157 pnkfelix 1.1.2.1 }
158 pnkfelix 1.1.2.1
159 pnkfelix 1.1.2.1 // in practice, the remainder of the web building
160 pnkfelix 1.1.2.1 // should work w/o the following loop. But if there
161 pnkfelix 1.1.2.1 // is a def w/o a corresponding use, the system breaks.
162 pnkfelix 1.1.2.1
163 cananian 1.7 for(Temp t : defCT(inst)){
164 pnkfelix 1.1.2.1 if( isRegister(t) ) continue;
165 pnkfelix 1.1.2.1
166 pnkfelix 1.1.2.1 if( haveWebFor(t, inst) ) {
167 pnkfelix 1.1.2.1 Web w = webFor(t, inst);
168 pnkfelix 1.1.2.1 w.defs.add(inst);
169 pnkfelix 1.1.2.1 } else {
170 pnkfelix 1.1.2.1 Set defC = Collections.singleton(inst);
171 pnkfelix 1.1.2.1 Set useC = Collections.EMPTY_SET;
172 pnkfelix 1.1.2.1 addWeb( t, defC, useC );
173 pnkfelix 1.1.2.1 }
174 pnkfelix 1.1.2.1 }
175 pnkfelix 1.1.2.1 }
176 pnkfelix 1.1.2.1
177 pnkfelix 1.1.2.1 boolean changed;
178 pnkfelix 1.1.2.1 do {
179 pnkfelix 1.1.2.1 // combine du-chains for the same symbol and that have a
180 pnkfelix 1.1.2.1 // def in common to make webs
181 pnkfelix 1.1.2.1 changed = false;
182 pnkfelix 1.1.2.1
183 pnkfelix 1.1.2.1 // look into using a faster structure than a hashset here?
184 cananian 1.7 Set<Web> tmp1 = new LinkedHashSet<Web>( tempToWebs.values() );
185 pnkfelix 1.1.2.1
186 pnkfelix 1.1.2.1 while( ! tmp1.isEmpty() ){
187 cananian 1.7 Web web1 = tmp1.iterator().next();
188 pnkfelix 1.1.2.1 tmp1.remove( web1 );
189 pnkfelix 1.1.2.1
190 pnkfelix 1.1.2.1 // put webs to be removed post-iteration here
191 cananian 1.7 Set<Web> removeFromTmp1 = new LinkedHashSet<Web>();
192 pnkfelix 1.1.2.1
193 cananian 1.7 for(Web web2 : tmp1){
194 pnkfelix 1.1.2.1
195 pnkfelix 1.1.2.1 if( web1.temp.equals( web2.temp )){
196 pnkfelix 1.1.2.1 boolean combineWebs;
197 pnkfelix 1.1.2.5 combineWebs = intersects( web1.defs, web2.defs );
198 pnkfelix 1.1.2.1
199 pnkfelix 1.1.2.1 if( ! combineWebs ){
200 pnkfelix 1.1.2.11 // FSK IMPORTANT: current temp->reg assignment
201 pnkfelix 1.1.2.1 // design breaks if an instr needs two
202 pnkfelix 1.1.2.1 // different regs for the same temp in the
203 pnkfelix 1.1.2.1 // uses and defines. Take this clause out
204 pnkfelix 1.1.2.1 // after that is fixed.
205 pnkfelix 1.1.2.1
206 pnkfelix 1.1.2.5 combineWebs = ( intersects( web1.defs, web2.uses ) ||
207 pnkfelix 1.1.2.5 intersects( web2.defs, web1.uses ) );
208 pnkfelix 1.1.2.1 }
209 pnkfelix 1.1.2.1
210 pnkfelix 1.1.2.1 if( combineWebs ){
211 pnkfelix 1.1.2.1 web1.defs.addAll( web2.defs );
212 pnkfelix 1.1.2.1 web1.uses.addAll( web2.uses );
213 pnkfelix 1.1.2.1 tempToWebs.remove( web2.temp, web2 );
214 pnkfelix 1.1.2.1 removeFromTmp1.add( web2 );
215 pnkfelix 1.1.2.1 changed = true;
216 pnkfelix 1.1.2.1 }
217 pnkfelix 1.1.2.1 }
218 pnkfelix 1.1.2.1 }
219 pnkfelix 1.1.2.1
220 pnkfelix 1.1.2.1 tmp1.removeAll( removeFromTmp1 );
221 pnkfelix 1.1.2.1
222 pnkfelix 1.1.2.1 }
223 pnkfelix 1.1.2.1 } while( changed );
224 pnkfelix 1.1.2.1 }
225 pnkfelix 1.1.2.1
226 pnkfelix 1.1.2.1 void buildWebToNodes() {
227 pnkfelix 1.1.2.16 checkPrecolored();
228 cananian 1.7 for(Object regO : rfi().getAllRegistersC()){
229 cananian 1.7 Temp reg = (Temp) regO;
230 pnkfelix 1.1.2.1 makePrecolored(reg);
231 pnkfelix 1.1.2.1 }
232 pnkfelix 1.1.2.16 checkPrecolored();
233 cananian 1.7 for(Object tempO : tempToWebs.keySet()){
234 cananian 1.7 Temp temp = (Temp) tempO;
235 pnkfelix 1.1.2.1 if( ! isRegister(temp) ) {
236 pnkfelix 1.1.2.1 makeInitial( temp );
237 pnkfelix 1.1.2.16 } else {
238 cananian 1.3.2.1 assert nodesFor( (Web) tempToWebs.get( temp ) ).size() == 1;
239 cananian 1.3.2.1 assert ((Node)nodesFor
240 cananian 1.3.2.1 ( (Web) tempToWebs.get( temp ) ).get(0)).isPrecolored();
241 pnkfelix 1.1.2.1 }
242 pnkfelix 1.1.2.16 checkPrecolored();
243 pnkfelix 1.1.2.1 }
244 pnkfelix 1.1.2.16 checkPrecolored();
245 pnkfelix 1.1.2.1 }
246 pnkfelix 1.1.2.1
247 pnkfelix 1.1.2.1
248 pnkfelix 1.1.2.1
249 pnkfelix 1.1.2.1
250 pnkfelix 1.1.2.1 public Derivation getDerivation() { return null; }
251 pnkfelix 1.1.2.1
252 pnkfelix 1.1.2.1 // Invariants that hold post Build, see Appel pg 254
253 pnkfelix 1.1.2.1 public void checkInv() {
254 pnkfelix 1.1.2.16 if( ! CHECK_INV ) return;
255 pnkfelix 1.1.2.16
256 pnkfelix 1.1.2.16 checkPrecolored();
257 pnkfelix 1.1.2.1 checkMoveSets();
258 pnkfelix 1.1.2.1 checkDisjointInv();
259 pnkfelix 1.1.2.1 checkDegreeInv();
260 pnkfelix 1.1.2.1 checkSimplifyWorklistInv();
261 pnkfelix 1.1.2.1 checkFreezeWorklistInv();
262 pnkfelix 1.1.2.1 checkSpillWorklistInv();
263 pnkfelix 1.1.2.1
264 pnkfelix 1.1.2.16 }
265 pnkfelix 1.1.2.16
266 pnkfelix 1.1.2.16 public void checkPrecolored() {
267 pnkfelix 1.1.2.16 if (!CHECK_INV) return;
268 pnkfelix 1.1.2.16
269 pnkfelix 1.1.2.1 for(NodeIter ni=precolored.iter(); ni.hasNext();){
270 cananian 1.3.2.2 Node n = ni.next();
271 cananian 1.3.2.2 assert n.isPrecolored();
272 pnkfelix 1.1.2.1 }
273 pnkfelix 1.1.2.16 for(Iterator nodes=allNodes(); nodes.hasNext(); ){
274 pnkfelix 1.1.2.16 Node n = (Node) nodes.next();
275 pnkfelix 1.1.2.16 if (n.web == null) continue;
276 cananian 1.3.2.1 assert n.isPrecolored() || !rfi().isRegister( n.web.temp ) : n;
277 cananian 1.3.2.1 assert !n.isPrecolored() || rfi().isRegister( n.web.temp ) : n;
278 pnkfelix 1.1.2.16 }
279 pnkfelix 1.1.2.1 }
280 pnkfelix 1.1.2.1
281 pnkfelix 1.1.2.1 public void checkDisjointInv() {
282 pnkfelix 1.1.2.1 HashSet pset = new HashSet();
283 pnkfelix 1.1.2.1 HashSet iset = new HashSet();
284 pnkfelix 1.1.2.1 HashSet simplset = new HashSet();
285 pnkfelix 1.1.2.1 HashSet fset = new HashSet();
286 pnkfelix 1.1.2.1 HashSet spillset = new HashSet();
287 pnkfelix 1.1.2.1 HashSet spilledset = new HashSet();
288 pnkfelix 1.1.2.1 HashSet coalset = new HashSet();
289 pnkfelix 1.1.2.1 HashSet coloredset = new HashSet();
290 pnkfelix 1.1.2.1 HashSet selectset = new HashSet();
291 pnkfelix 1.1.2.1
292 pnkfelix 1.1.2.1 HashSet[] sets = new HashSet[] {
293 pnkfelix 1.1.2.1 pset, iset, simplset, fset, spillset,
294 pnkfelix 1.1.2.1 spilledset, coalset, coloredset, selectset
295 pnkfelix 1.1.2.1 };
296 pnkfelix 1.1.2.1
297 pnkfelix 1.1.2.1 NodeIter ni;
298 pnkfelix 1.1.2.1 for(ni=precolored.iter(); ni.hasNext();) pset.add(ni.next());
299 pnkfelix 1.1.2.1 for(ni=initial.iter(); ni.hasNext();) iset.add(ni.next());
300 pnkfelix 1.1.2.1 for(ni=simplify_worklist.iter();ni.hasNext();) simplset.add(ni.next());
301 pnkfelix 1.1.2.1 for(ni=freeze_worklist.iter();ni.hasNext();) fset.add(ni.next());
302 pnkfelix 1.1.2.1 for(ni=spill_worklist.iter();ni.hasNext();) spillset.add(ni.next());
303 pnkfelix 1.1.2.1 for(ni=spilled_nodes.iter();ni.hasNext();) spilledset.add(ni.next());
304 pnkfelix 1.1.2.1 for(ni=coalesced_nodes.iter();ni.hasNext();) coalset.add(ni.next());
305 pnkfelix 1.1.2.1 for(ni=colored_nodes.iter();ni.hasNext();) coloredset.add(ni.next());
306 pnkfelix 1.1.2.1 for(ni=select_stack.iter(); ni.hasNext();) selectset.add(ni.next());
307 pnkfelix 1.1.2.1
308 pnkfelix 1.1.2.1 for(int i=0; i<sets.length; i++) {
309 pnkfelix 1.1.2.1 HashSet s = sets[i];
310 pnkfelix 1.1.2.1 for(int j=i+1; j<sets.length; j++) {
311 cananian 1.3.2.1 assert ! intersects( sets[j], s );
312 pnkfelix 1.1.2.1 }
313 pnkfelix 1.1.2.1 }
314 pnkfelix 1.1.2.1 }
315 pnkfelix 1.1.2.13
316 pnkfelix 1.1.2.13 /** Checks degree invariant documented in Tiger book;
317 pnkfelix 1.1.2.13 abstract because a variant of the algorithm breaks
318 pnkfelix 1.1.2.13 it on purpose.
319 pnkfelix 1.1.2.13 The invariant, as given in the Tiger book, is:
320 pnkfelix 1.1.2.13 <pre>
321 pnkfelix 1.1.2.13 u isIn (simplifyWorklist \/ freezeWorklist \/ spillWorklist ) ==>
322 pnkfelix 1.1.2.13 degree(u) = | adjList(u) /\ ( precolored \/ simplifyWorklist \/
323 pnkfelix 1.1.2.13 freezeWorklist \/ spillWorklist ) |
324 pnkfelix 1.1.2.13 </pre>
325 pnkfelix 1.1.2.13 */
326 pnkfelix 1.1.2.13 protected abstract void checkDegreeInv();
327 pnkfelix 1.1.2.1
328 pnkfelix 1.1.2.1 public void checkSimplifyWorklistInv() {
329 pnkfelix 1.1.2.1 // u isIn simplifyWorklist ==>
330 pnkfelix 1.1.2.1 // degree(u) < K &&
331 pnkfelix 1.1.2.1 // moveList[u] /\ ( activeMoves \/ worklistMoves ) = {}
332 pnkfelix 1.1.2.1
333 pnkfelix 1.1.2.1 for( NodeIter ni=simplify_worklist.iter(); ni.hasNext(); ) {
334 pnkfelix 1.1.2.1 Node u = ni.next();
335 cananian 1.3.2.1 assert u.degree < K : "simplify worklist inv. violated "+
336 cananian 1.3.2.1 "( should be u.degree < K )";
337 cananian 1.7 for(Move m : u.moves) {
338 cananian 1.3.2.1 assert !m.isActive() : "simplify worklist inv. violated"+
339 cananian 1.3.2.1 "( should be !m.isActive() )";
340 cananian 1.3.2.1 assert !m.isWorklist() : "simplify worklist inv. violated"+
341 cananian 1.3.2.1 "( should be !m.isWorklist() )";
342 pnkfelix 1.1.2.1 }
343 pnkfelix 1.1.2.1 }
344 pnkfelix 1.1.2.1 }
345 pnkfelix 1.1.2.1
346 pnkfelix 1.1.2.1 public void checkFreezeWorklistInv() {
347 pnkfelix 1.1.2.1 // u isIn freezeWorklist ==>
348 pnkfelix 1.1.2.1 // degree(u) < K &&
349 pnkfelix 1.1.2.1 // moveList[u] /\ ( activeMoves \/ worklistMoves ) != {}
350 pnkfelix 1.1.2.1
351 pnkfelix 1.1.2.1 for( NodeIter ni=freeze_worklist.iter(); ni.hasNext(); ) {
352 pnkfelix 1.1.2.1 Node u = ni.next();
353 cananian 1.3.2.1 assert u.degree < K : "freeze worklist inv. violated";
354 pnkfelix 1.1.2.1
355 cananian 1.7 for(Move m : u.moves) {
356 pnkfelix 1.1.2.1
357 pnkfelix 1.1.2.1 if( m.isActive() || m.isWorklist() )
358 pnkfelix 1.1.2.1 return;
359 pnkfelix 1.1.2.1 }
360 pnkfelix 1.1.2.1
361 cananian 1.3.2.1 assert false : ("freeze worklist inv. violated, "+
362 pnkfelix 1.1.2.1 " node:"+u+
363 pnkfelix 1.1.2.1 " moves:"+u.moves);
364 pnkfelix 1.1.2.1 }
365 pnkfelix 1.1.2.1 }
366 pnkfelix 1.1.2.1
367 pnkfelix 1.1.2.1 public void checkSpillWorklistInv() {
368 pnkfelix 1.1.2.1 // u isIn spillWorklist ==> degree(u) >= K
369 pnkfelix 1.1.2.1 for( NodeIter ni=spill_worklist.iter(); ni.hasNext(); ) {
370 pnkfelix 1.1.2.1 Node u = ni.next();
371 cananian 1.3.2.1 assert u . degree >= K : "spill worklist inv. violated";
372 pnkfelix 1.1.2.1 }
373 pnkfelix 1.1.2.1 }
374 pnkfelix 1.1.2.1
375 pnkfelix 1.1.2.7 public void appelLoopBody( SpillHeuristic sh ) throws CouldntFindSpillExn {
376 pnkfelix 1.1.2.1
377 pnkfelix 1.1.2.1 // System.out.println("making worklist");
378 pnkfelix 1.1.2.1 makeWorklist();
379 pnkfelix 1.1.2.1 // System.out.println("done making worklist");
380 pnkfelix 1.1.2.1
381 pnkfelix 1.1.2.1 checkInv();
382 pnkfelix 1.1.2.1 do {
383 pnkfelix 1.1.2.1 if( ! simplify_worklist.isEmpty()) {
384 pnkfelix 1.1.2.1 simplify(); checkInv();
385 pnkfelix 1.1.2.1 } else if( ! worklist_moves.isEmpty()) {
386 pnkfelix 1.1.2.1 coalesce(); checkInv();
387 pnkfelix 1.1.2.1 } else if( ! freeze_worklist.isEmpty()) {
388 pnkfelix 1.1.2.1 freeze(); checkInv();
389 pnkfelix 1.1.2.1 } else if( ! spill_worklist.isEmpty()) {
390 pnkfelix 1.1.2.1 selectSpill( sh );
391 pnkfelix 1.1.2.1
392 pnkfelix 1.1.2.1 // FSK: (3/26/01) invariant DOESN'T HOLD here (this
393 pnkfelix 1.1.2.1 // FSK: agrees with assertion commented out from
394 pnkfelix 1.1.2.1 // FSK: CSAHack.RegAlloc.Color
395 pnkfelix 1.1.2.1 // checkInv();
396 pnkfelix 1.1.2.1 }
397 pnkfelix 1.1.2.1
398 pnkfelix 1.1.2.1 } while ( ! simplify_worklist.isEmpty() ||
399 pnkfelix 1.1.2.1 ! worklist_moves.isEmpty() ||
400 pnkfelix 1.1.2.1 ! freeze_worklist.isEmpty() ||
401 pnkfelix 1.1.2.1 ! spill_worklist.isEmpty() );
402 pnkfelix 1.1.2.1
403 pnkfelix 1.1.2.1 }
404 pnkfelix 1.1.2.1
405 pnkfelix 1.1.2.11 private void trivialMoveCoalesce() {
406 pnkfelix 1.1.2.11 // FSK: TODO: insert code here to do a prepass eliminating
407 pnkfelix 1.1.2.11 // moves of the form "mov t0, t0;" because they are truly
408 pnkfelix 1.1.2.11 // useless (unless we add support for assigning different regs
409 pnkfelix 1.1.2.11 // to the same temp based on its status in its instr as a use
410 pnkfelix 1.1.2.11 // or a def)
411 pnkfelix 1.1.2.11 if (!TRIVIAL_MOVE_COALESCE)
412 pnkfelix 1.1.2.11 return;
413 pnkfelix 1.1.2.11
414 pnkfelix 1.1.2.11 int numRemoved = 0;
415 pnkfelix 1.1.2.11 for(Iterator instrs=code.getElementsI(); instrs.hasNext(); ){
416 pnkfelix 1.1.2.11 Instr i = (Instr) instrs.next();
417 pnkfelix 1.1.2.11 if (i.isMove()) {
418 cananian 1.3.2.1 assert i.defC().size() == 1;
419 cananian 1.3.2.1 assert i.useC().size() == 1;
420 pnkfelix 1.1.2.11 Temp dst = (Temp) i.defC().iterator().next();
421 pnkfelix 1.1.2.11 Temp src = (Temp) i.useC().iterator().next();
422 pnkfelix 1.1.2.11 if (dst == src) {
423 pnkfelix 1.1.2.11 i.remove();
424 pnkfelix 1.1.2.11 numRemoved++;
425 pnkfelix 1.1.2.11 }
426 pnkfelix 1.1.2.11 }
427 pnkfelix 1.1.2.11 }
428 pnkfelix 1.1.2.11
429 pnkfelix 1.1.2.11 if (numRemoved > 0) {
430 pnkfelix 1.1.2.11 bbFact = computeBasicBlocks();
431 pnkfelix 1.1.2.11 }
432 pnkfelix 1.1.2.11 }
433 pnkfelix 1.1.2.11
434 pnkfelix 1.1.2.11 void time(String note) { //System.out.println("TIME "+note+" "+new java.util.Date());
435 pnkfelix 1.1.2.11 }
436 pnkfelix 1.1.2.13
437 pnkfelix 1.1.2.13 /** Finds the minimum cost heuristic in <code>h</code>.
438 pnkfelix 1.1.2.13 <BR> <B>requires:</B> all h' in h have been run.
439 pnkfelix 1.1.2.13 @return the h' in h with minimum actualCost.
440 pnkfelix 1.1.2.13 */
441 pnkfelix 1.1.2.13 protected SpillHeuristic minimum(SpillHeuristic[] h) {
442 pnkfelix 1.1.2.13 SpillHeuristic h_min = h[0];
443 pnkfelix 1.1.2.13 int minIndex = -1; // negative represents "any will do"
444 pnkfelix 1.1.2.13
445 pnkfelix 1.1.2.13 for(int i=1; i < h.length; i++) {
446 pnkfelix 1.1.2.13 // if (h[i].accumExpCost < h_min.accumExpCost) {
447 pnkfelix 1.1.2.13 if (h[i].actualCost < h_min.actualCost) {
448 pnkfelix 1.1.2.13 h_min = h[i];
449 pnkfelix 1.1.2.13 minIndex = i;
450 pnkfelix 1.1.2.13 } else if (minIndex == -1 &&
451 pnkfelix 1.1.2.13 h_min.actualCost < h[i].actualCost) {
452 pnkfelix 1.1.2.13 // need this special case so that our data
453 pnkfelix 1.1.2.13 // properly states when using h[0] *is*
454 pnkfelix 1.1.2.13 // significant.
455 pnkfelix 1.1.2.13 minIndex = 0;
456 pnkfelix 1.1.2.13 }
457 pnkfelix 1.1.2.13 }
458 pnkfelix 1.1.2.13 if (minIndex == -1 && (h_min.actualCost < 0.001)) {
459 pnkfelix 1.1.2.13 minIndex = -2; // -2 means "any will do && no spilling"
460 pnkfelix 1.1.2.13 }
461 pnkfelix 1.1.2.13
462 pnkfelix 1.1.2.13 if( PRINT_HEURISTIC_INFO
463 pnkfelix 1.1.2.13 // (leave -2 results out of output when not incremental)
464 pnkfelix 1.1.2.13 && (minIndex != -2) ) {
465 pnkfelix 1.1.2.13
466 pnkfelix 1.1.2.13 for(int i=0;i<h.length;i++)
467 pnkfelix 1.1.2.13 System.out.print("\nAPPLY SPILL HEURISTIC "+i+" \t=> "+h[i]);
468 pnkfelix 1.1.2.13 System.out.println
469 pnkfelix 1.1.2.13 ("\nCHOOSING SPILL HEURISTIC "+minIndex+" \t=> "+h_min);
470 pnkfelix 1.1.2.13 }
471 pnkfelix 1.1.2.13 return h_min;
472 pnkfelix 1.1.2.13 }
473 pnkfelix 1.1.2.11
474 pnkfelix 1.1.2.1 public void generateRegAssignment() {
475 pnkfelix 1.1.2.11 trivialMoveCoalesce();
476 pnkfelix 1.1.2.11
477 pnkfelix 1.1.2.1 while (true) {
478 pnkfelix 1.1.2.1 // System.out.println("post spill coloring");
479 pnkfelix 1.1.2.13 initializeSets();
480 pnkfelix 1.1.2.13 preAnalysis();
481 pnkfelix 1.1.2.13 buildTempToWebs();
482 pnkfelix 1.1.2.13 buildWebToNodes();
483 pnkfelix 1.1.2.16
484 pnkfelix 1.1.2.16 // Tracking down MIPS failure
485 cananian 1.7 for(Object regO : rfi().getAllRegistersC()){
486 cananian 1.7 Temp reg = (Temp) regO;
487 cananian 1.7 assert nodesFor( tempToWebs.get( reg ) ).size() == 1;
488 cananian 1.3.2.1 assert ((Node)nodesFor
489 cananian 1.7 ( tempToWebs.get( reg ) ).get(0)).isPrecolored();
490 pnkfelix 1.1.2.16 }
491 pnkfelix 1.1.2.16 checkPrecolored();
492 pnkfelix 1.1.2.16
493 pnkfelix 1.1.2.15 adjSet = makeNodePairSet();
494 pnkfelix 1.1.2.11
495 pnkfelix 1.1.2.1 // Appel's real code begins here
496 pnkfelix 1.1.2.13 buildInterferenceGraph();
497 pnkfelix 1.1.2.1
498 pnkfelix 1.1.2.13 checkInv();
499 pnkfelix 1.1.2.7 try {
500 pnkfelix 1.1.2.10 SpillHeuristic h_min = null;
501 pnkfelix 1.1.2.13 SpillHeuristic[] h = sh.spillHeuristics();
502 pnkfelix 1.1.2.15 if ( h.length == 1 ) {
503 pnkfelix 1.1.2.15 appelLoopBody( h[0] );
504 pnkfelix 1.1.2.15 } else {
505 pnkfelix 1.1.2.15 checkpointState();
506 pnkfelix 1.1.2.7 for(int i = 0; i < h.length; i++) {
507 pnkfelix 1.1.2.10 // FSK: look into breaking out of this loop if
508 pnkfelix 1.1.2.10 // we color without any spilling at all.
509 pnkfelix 1.1.2.13 appelLoopBody( h[i] );
510 pnkfelix 1.1.2.10
511 pnkfelix 1.1.2.13 checkMoveSets();
512 pnkfelix 1.1.2.10
513 pnkfelix 1.1.2.13 assignColors();
514 pnkfelix 1.1.2.10
515 pnkfelix 1.1.2.13 checkInv();
516 pnkfelix 1.1.2.10
517 pnkfelix 1.1.2.10 if (h[i].maxExpSpills == 0)
518 cananian 1.3.2.1 assert spilled_nodes.isEmpty();
519 pnkfelix 1.1.2.10
520 pnkfelix 1.1.2.10 if ( spilled_nodes.isEmpty() ) {
521 pnkfelix 1.1.2.10 h_min = h[i];
522 pnkfelix 1.1.2.10
523 pnkfelix 1.1.2.13 // FSK: break here for better speed
524 pnkfelix 1.1.2.11 // (no spills ==> don't need reiteration of heuristics)
525 pnkfelix 1.1.2.11 // ((may want disable later if i gather
526 pnkfelix 1.1.2.11 // data measuring benefit of alt spill
527 pnkfelix 1.1.2.11 // heuristics))
528 pnkfelix 1.1.2.11 break;
529 pnkfelix 1.1.2.10 } else {
530 pnkfelix 1.1.2.10 h[i].reallySpill(spilled_nodes.iter());
531 pnkfelix 1.1.2.10 }
532 pnkfelix 1.1.2.10
533 pnkfelix 1.1.2.13 resetState();
534 pnkfelix 1.1.2.1 }
535 pnkfelix 1.1.2.10
536 pnkfelix 1.1.2.13 if (h_min == null)
537 pnkfelix 1.1.2.13 h_min = minimum(h);
538 pnkfelix 1.1.2.10
539 pnkfelix 1.1.2.10 h_min.reset();
540 pnkfelix 1.1.2.13 appelLoopBody( h_min );
541 pnkfelix 1.1.2.10
542 pnkfelix 1.1.2.1 }
543 pnkfelix 1.1.2.13
544 pnkfelix 1.1.2.13 assignColors();
545 pnkfelix 1.1.2.10 // h_min.reallySpill(spilled_nodes.iter());
546 pnkfelix 1.1.2.10 // System.out.println("\nFINAL SPILL HEURISTIC \t=> "+h_min);
547 pnkfelix 1.1.2.10
548 pnkfelix 1.1.2.13 checkInv();
549 pnkfelix 1.1.2.10
550 pnkfelix 1.1.2.7 if( ! spilled_nodes.isEmpty()) {
551 pnkfelix 1.1.2.7 System.out.print(" R"+rewriteCalledNumTimes+", S!"+spilled_nodes.asSet().size());
552 pnkfelix 1.1.2.7 rewriteProgram(); checkInv();
553 pnkfelix 1.1.2.7 continue;
554 pnkfelix 1.1.2.7 } else {
555 pnkfelix 1.1.2.7 break;
556 pnkfelix 1.1.2.7 }
557 pnkfelix 1.1.2.7 } catch (CouldntFindSpillExn e) {
558 pnkfelix 1.1.2.13 if (try_to_clean) {
559 pnkfelix 1.1.2.13 if (PRINT_CLEANING_INFO)
560 pnkfelix 1.1.2.13 System.out.println
561 pnkfelix 1.1.2.13 ("COULDN'T FIND A SPILL! TURNING OFF CLEANING!");
562 pnkfelix 1.1.2.13 stopTryingToClean();
563 pnkfelix 1.1.2.7 } else {
564 pnkfelix 1.1.2.13 String s = "[ ";
565 pnkfelix 1.1.2.13 for(NodeIter ni = spill_worklist.iter(); ni.hasNext();){
566 pnkfelix 1.1.2.13 s += ni.next().web+ (ni.hasNext() ? ", " : " ]");
567 pnkfelix 1.1.2.13 }
568 cananian 1.3.2.1 assert false : s;
569 pnkfelix 1.1.2.7 }
570 pnkfelix 1.1.2.13 bbFact = computeBasicBlocks();
571 pnkfelix 1.1.2.1 }
572 pnkfelix 1.1.2.1 }
573 pnkfelix 1.1.2.1
574 pnkfelix 1.1.2.7 // copy spill stats
575 pnkfelix 1.1.2.7 String local_stats = spillStats( depthToNumSpills );
576 pnkfelix 1.1.2.7 if (local_stats.length() > 0) {
577 pnkfelix 1.1.2.7 for(int i=0; i < depthToNumSpills.length; i++) {
578 pnkfelix 1.1.2.7 globalDepthToNumSpills[i] += depthToNumSpills[i];
579 pnkfelix 1.1.2.7 }
580 pnkfelix 1.1.2.11 if (PRINT_DEPTH_TO_SPILL_INFO) {
581 pnkfelix 1.1.2.11 String global_stats = spillStats(globalDepthToNumSpills);
582 pnkfelix 1.1.2.11 System.out.println();
583 pnkfelix 1.1.2.11 System.out.print("globally "+global_stats);
584 pnkfelix 1.1.2.11 System.out.println();
585 pnkfelix 1.1.2.11 }
586 pnkfelix 1.1.2.7 }
587 pnkfelix 1.1.2.13
588 pnkfelix 1.1.2.13 // introduce Flex-style assignments here
589 pnkfelix 1.1.2.13 performFinalAssignment(colorToReg());
590 pnkfelix 1.1.2.13
591 pnkfelix 1.1.2.1 }
592 pnkfelix 1.1.2.7
593 pnkfelix 1.1.2.13 protected Temp[] colorToReg() {
594 pnkfelix 1.1.2.13 // set up color (int) -> register mapping
595 pnkfelix 1.1.2.13 Temp[] regs = new Temp[ precolored.size ];
596 pnkfelix 1.1.2.13 for(NodeIter ri=precolored.iter(); ri.hasNext();) {
597 pnkfelix 1.1.2.13 Node r = ri.next();
598 pnkfelix 1.1.2.13 // this is legal; node in precolored has exactly one color.
599 pnkfelix 1.1.2.13 regs[r.color[0]] = r.web.temp;
600 pnkfelix 1.1.2.1 }
601 pnkfelix 1.1.2.13 return regs;
602 pnkfelix 1.1.2.1 }
603 pnkfelix 1.1.2.13
604 pnkfelix 1.1.2.13 // FSK: placeholder for future method that should allow me to
605 pnkfelix 1.1.2.13 // push more code from subclasses up into here.
606 pnkfelix 1.1.2.13 protected List/*Reg*/ webToRegAssignment( Web w ){
607 pnkfelix 1.1.2.13 return null;
608 pnkfelix 1.1.2.1 }
609 pnkfelix 1.1.2.1
610 pnkfelix 1.1.2.13 /** Gives each Instr in the code a register assignment.
611 pnkfelix 1.1.2.13 This is the last step in generateRegAssignment; it
612 pnkfelix 1.1.2.13 is abstract because different variants have different
613 pnkfelix 1.1.2.13 node to color mappings and so they extract the
614 pnkfelix 1.1.2.13 assignments in different ways.
615 pnkfelix 1.1.2.13 @param regs (regs[i] == n.web.temp) ==> (n in precolored && n.color = i).
616 pnkfelix 1.1.2.13 */
617 pnkfelix 1.1.2.13 protected abstract void performFinalAssignment(Temp[] regs);
618 pnkfelix 1.1.2.13
619 pnkfelix 1.1.2.13
620 pnkfelix 1.1.2.1 private void preAnalysis() {
621 pnkfelix 1.1.2.1 rdefs = new ReachingDefsAltImpl(code,grapher,usedefer);
622 pnkfelix 1.1.2.1
623 pnkfelix 1.1.2.1 // TODO: update to use grapher/usedefer
624 pnkfelix 1.1.2.1 // (requires revision of LiveTemps code)
625 pnkfelix 1.1.2.1 // liveTemps = new SpaceHeavyLiveTemps(bbFact, rfi().liveOnExit(), usedefer, grapher);
626 pnkfelix 1.1.2.1 liveTemps = new LiveTemps(bbFact, rfi().liveOnExit(), usedefer);
627 pnkfelix 1.1.2.1 liveTemps.solve();
628 pnkfelix 1.1.2.1
629 pnkfelix 1.1.2.1 if (CHECK_INV)
630 pnkfelix 1.1.2.1 Check.liveSetsAreConsistent
631 pnkfelix 1.1.2.1 ( code, bbFact, grapher, usedefer, liveTemps, rfi().liveOnExit() );
632 pnkfelix 1.1.2.16 if (false && CHECK_INV) // TODO need to fix that r0 def at outset thing
633 pnkfelix 1.1.2.1 Check.allLiveVarsHaveDefs
634 pnkfelix 1.1.2.1 ( code, bbFact, grapher, usedefer, rdefs, liveTemps );
635 pnkfelix 1.1.2.1
636 pnkfelix 1.1.2.1 if (false) System.out.println("RegAlloc Analysis for "+
637 pnkfelix 1.1.2.1 code.getMethod().getName()+
638 pnkfelix 1.1.2.1 " completed successfully ");
639 pnkfelix 1.1.2.1
640 pnkfelix 1.1.2.1
641 pnkfelix 1.1.2.1 }
642 pnkfelix 1.1.2.1
643 pnkfelix 1.1.2.11
644 pnkfelix 1.1.2.1
645 pnkfelix 1.1.2.1
646 pnkfelix 1.1.2.13 /** Builds the interference graph for the code.
647 pnkfelix 1.1.2.13 Abstract because Moves need to be treated specially
648 pnkfelix 1.1.2.13 by this routine, and variants of the algorithm
649 pnkfelix 1.1.2.13 have different ways of dealing with Moves.
650 pnkfelix 1.1.2.13 The algorithm as given in the Tiger book is:
651 pnkfelix 1.1.2.13 <pre>
652 pnkfelix 1.1.2.13 forall b : blocks in program
653 pnkfelix 1.1.2.13 let live = liveOut(b)
654 pnkfelix 1.1.2.13 forall I : instructions(b) in reverse order
655 pnkfelix 1.1.2.13 if isMoveInstruction(I) then
656 pnkfelix 1.1.2.13 live <- live \ use(I)
657 pnkfelix 1.1.2.13 forall n : def(I) \/ use(I)
658 pnkfelix 1.1.2.13 moveList[n] <- moveList[n] \/ I
659 pnkfelix 1.1.2.13 worklistMoves <- worklistMoves \/ { I }
660 pnkfelix 1.1.2.13 live <- live \/ def(I)
661 pnkfelix 1.1.2.13 forall d : def(I)
662 pnkfelix 1.1.2.13 forall l : live
663 pnkfelix 1.1.2.13 AddEdge(l, d)
664 pnkfelix 1.1.2.13 live <- use(I) \/ ( live \ def(I) )
665 pnkfelix 1.1.2.13 </pre>
666 pnkfelix 1.1.2.13 */
667 pnkfelix 1.1.2.13 protected abstract void buildInterferenceGraph();
668 pnkfelix 1.1.2.1
669 pnkfelix 1.1.2.13 protected Instr lastStm(BasicBlock b) {
670 pnkfelix 1.1.2.1 List stms = b.statements();
671 pnkfelix 1.1.2.1 return (Instr) stms.get( stms.size() - 1 );
672 pnkfelix 1.1.2.1 }
673 pnkfelix 1.1.2.13 protected Instr firstStm(BasicBlock b) {
674 pnkfelix 1.1.2.1 return (Instr) b.statements().get(0);
675 pnkfelix 1.1.2.1 }
676 pnkfelix 1.1.2.13 protected Instr pred(Instr i) {
677 pnkfelix 1.1.2.1 Instr i_r = (Instr) grapher.predElemC(i).iterator().next();
678 cananian 1.3.2.1 assert i != i_r;
679 pnkfelix 1.1.2.1 return i_r;
680 pnkfelix 1.1.2.1 }
681 pnkfelix 1.1.2.1
682 cananian 1.7 protected Collection<Temp> useCT( Instr i ) { return usedefer.useC( i ); }
683 cananian 1.7 protected Collection<Temp> defCT( Instr i ) { return usedefer.defC( i ); }
684 pnkfelix 1.1.2.1
685 pnkfelix 1.1.2.13 protected NodeIter nodesIter(final Iterator i) {
686 pnkfelix 1.1.2.1 return new NodeIter() {
687 pnkfelix 1.1.2.1 public boolean hasNext() { return i.hasNext(); }
688 pnkfelix 1.1.2.1 public Node next() { return (Node) i.next(); }
689 pnkfelix 1.1.2.1 };
690 pnkfelix 1.1.2.1 }
691 pnkfelix 1.1.2.1
692 pnkfelix 1.1.2.13 Iterator instrs() {
693 pnkfelix 1.1.2.1 final Iterator bbs = bbFact.blocksIterator();
694 pnkfelix 1.1.2.1 return new UnmodifiableIterator() {
695 pnkfelix 1.1.2.1 Iterator currStms;
696 pnkfelix 1.1.2.1 public boolean hasNext() {
697 pnkfelix 1.1.2.1 return bbs.hasNext() || currStms.hasNext();
698 pnkfelix 1.1.2.1 }
699 pnkfelix 1.1.2.1 public Object next() {
700 pnkfelix 1.1.2.1 if (currStms != null && currStms.hasNext()) {
701 pnkfelix 1.1.2.1 return currStms.next();
702 pnkfelix 1.1.2.1 } else if (bbs.hasNext()) {
703 pnkfelix 1.1.2.1 currStms = ((BasicBlock)bbs.next()).statements().iterator();
704 pnkfelix 1.1.2.1 return currStms.next();
705 pnkfelix 1.1.2.1 } else {
706 pnkfelix 1.1.2.1 throw new java.util.NoSuchElementException();
707 pnkfelix 1.1.2.1 }
708 pnkfelix 1.1.2.1 }
709 pnkfelix 1.1.2.1 };
710 pnkfelix 1.1.2.1 }
711 pnkfelix 1.1.2.13
712 pnkfelix 1.1.2.13 /** Introduces an edge between u and v in both the
713 pnkfelix 1.1.2.13 interference graph and in the neighbor lists for
714 pnkfelix 1.1.2.13 u and v.
715 pnkfelix 1.1.2.13 Abstract because variants of the algorithm have
716 pnkfelix 1.1.2.13 different ways of handling the incrementing of
717 pnkfelix 1.1.2.13 the degrees and of mutating the neighbor lists.
718 pnkfelix 1.1.2.13 */
719 pnkfelix 1.1.2.13 protected abstract void addEdge( Node u, Node v );
720 pnkfelix 1.1.2.1
721 pnkfelix 1.1.2.10 /** Moves Nodes from initial to appropriate set in
722 pnkfelix 1.1.2.10 { spill, freeze, simplify }_worklist.
723 pnkfelix 1.1.2.10 MODIFIES: initial, { spill, freeze, simplify }_worklist
724 pnkfelix 1.1.2.10 */
725 pnkfelix 1.1.2.1 public void makeWorklist() {
726 pnkfelix 1.1.2.1 while( ! initial.isEmpty()) {
727 pnkfelix 1.1.2.1 Node n = initial.pop();
728 pnkfelix 1.1.2.1 if( n.degree >= K) {
729 pnkfelix 1.1.2.1 spill_worklist.add(n);
730 pnkfelix 1.1.2.1 } else if( moveRelated(n)) {
731 pnkfelix 1.1.2.1 freeze_worklist.add(n);
732 pnkfelix 1.1.2.1 } else {
733 pnkfelix 1.1.2.1 simplify_worklist.add(n);
734 pnkfelix 1.1.2.1 }
735 pnkfelix 1.1.2.1 }
736 pnkfelix 1.1.2.1
737 pnkfelix 1.1.2.1 // at this point, all Nodes should be in appropriate starting
738 pnkfelix 1.1.2.1 // sets. Do a consistency check...
739 pnkfelix 1.1.2.1 if (CHECK_INV)
740 pnkfelix 1.1.2.1 for( Iterator moves = worklist_moves.iter(); moves.hasNext(); ){
741 pnkfelix 1.1.2.1 Move m = (Move) moves.next();
742 cananian 1.3.2.1 assert m.isWorklist() : "m should be in worklist_moves";
743 cananian 1.7 for(Object nO : m.dsts()) {
744 cananian 1.7 Node n = (Node) nO;
745 pnkfelix 1.1.2.1 if (CHECK_INV)
746 cananian 1.3.2.1 assert moveRelated( n ) : "m.dst should be moveRelated, not "+n.s_rep.name;
747 pnkfelix 1.1.2.1 }
748 cananian 1.7 for(Object nO : m.srcs()) {
749 cananian 1.7 Node n = (Node) nO;
750 pnkfelix 1.1.2.1 if (CHECK_INV)
751 cananian 1.3.2.1 assert moveRelated( n ) : "m.src should be moveRelated, not "+n.s_rep.name;
752 pnkfelix 1.1.2.1 }
753 pnkfelix 1.1.2.1 }
754 pnkfelix 1.1.2.1 }
755 pnkfelix 1.1.2.1 Iterator nodeMoves( Node u ){
756 pnkfelix 1.1.2.1 return activeOrWorklistMoves( u );
757 pnkfelix 1.1.2.1 }
758 pnkfelix 1.1.2.1 Iterator activeOrWorklistMoves( Node u ) {
759 pnkfelix 1.1.2.1 return new FilterIterator
760 pnkfelix 1.1.2.1 (u.moves.iterator(),
761 pnkfelix 1.1.2.1 new FilterIterator.Filter() {
762 pnkfelix 1.1.2.1 public boolean isElement(Object o) {
763 pnkfelix 1.1.2.1 Move m = (Move) o;
764 pnkfelix 1.1.2.1 return (m.isActive() || m.isWorklist());
765 pnkfelix 1.1.2.1 }
766 pnkfelix 1.1.2.1 }
767 pnkfelix 1.1.2.1 );
768 pnkfelix 1.1.2.1 }
769 pnkfelix 1.1.2.1 public boolean moveRelated( Node n ) {
770 pnkfelix 1.1.2.1 Iterator nms = nodeMoves( n );
771 pnkfelix 1.1.2.1 return nms.hasNext();
772 pnkfelix 1.1.2.1 }
773 pnkfelix 1.1.2.1 public void simplify() {
774 pnkfelix 1.1.2.1 Node n = simplify_worklist.pop();
775 pnkfelix 1.1.2.1 select_stack.add(n);
776 pnkfelix 1.1.2.1
777 pnkfelix 1.1.2.1 for( NodeIter adj=adjacent(n); adj.hasNext(); ){
778 pnkfelix 1.1.2.1 Node m = adj.next();
779 pnkfelix 1.1.2.1
780 pnkfelix 1.1.2.1 if (m.isPrecolored()) {
781 pnkfelix 1.1.2.1 // FSK: added 3/26/01 based on CSA's code in
782 pnkfelix 1.1.2.1 // FSK: CSAHack.RegAlloc.Color (though algorithm given
783 pnkfelix 1.1.2.1 // FSK: in Appel does not have this check!)
784 pnkfelix 1.1.2.1 continue;
785 pnkfelix 1.1.2.1 }
786 pnkfelix 1.1.2.1
787 pnkfelix 1.1.2.13 decrementDegree(m,n);
788 pnkfelix 1.1.2.1 }
789 pnkfelix 1.1.2.1 }
790 pnkfelix 1.1.2.1
791 pnkfelix 1.1.2.13 /** Updates m to account for n being removed from the interference
792 pnkfelix 1.1.2.13 graph.
793 pnkfelix 1.1.2.13 Abstract because variants of the algorithm have different
794 pnkfelix 1.1.2.13 ways to represent the interferences between the nodes.
795 pnkfelix 1.1.2.13 modifies: m, active_moves, worklist_moves, spill_worklist,
796 pnkfelix 1.1.2.1 freeze_worklist, simplify_worklist
797 pnkfelix 1.1.2.11 effects: m in Precolored ==> no changes
798 pnkfelix 1.1.2.11 else decrements degree of m, moving it (and associated moves)
799 pnkfelix 1.1.2.1 into the appropriate lists if it has crossed the threshold
800 pnkfelix 1.1.2.1 from K to K-1.
801 pnkfelix 1.1.2.1 */
802 pnkfelix 1.1.2.13 protected abstract void decrementDegree( Node m, Node n );
803 pnkfelix 1.1.2.1
804 pnkfelix 1.1.2.13 protected void enableMoves( NodeIter nodes ) {
805 pnkfelix 1.1.2.1 while( nodes.hasNext() )
806 pnkfelix 1.1.2.1 enableMoves( nodes.next() );
807 pnkfelix 1.1.2.1 }
808 pnkfelix 1.1.2.13 protected void enableMoves( Node node) {
809 cananian 1.7 for(Move m : node.moves) {
810 pnkfelix 1.1.2.1 if( m.isActive() ) {
811 pnkfelix 1.1.2.1 active_moves.remove(m);
812 pnkfelix 1.1.2.1 worklist_moves.add(m);
813 pnkfelix 1.1.2.1 }
814 pnkfelix 1.1.2.1 }
815 pnkfelix 1.1.2.1 }
816 pnkfelix 1.1.2.1
817 pnkfelix 1.1.2.1 public void coalesce() {
818 pnkfelix 1.1.2.1 Move m = worklist_moves.pop();
819 pnkfelix 1.1.2.1
820 pnkfelix 1.1.2.1 Iterator xs = m.dsts().iterator();
821 pnkfelix 1.1.2.1 Iterator ys = m.srcs().iterator();
822 pnkfelix 1.1.2.1 while(xs.hasNext()) {
823 pnkfelix 1.1.2.1 Node x = (Node) xs.next();
824 pnkfelix 1.1.2.1 Node y = (Node) ys.next();
825 pnkfelix 1.1.2.1 coalesce(m, x, y);
826 pnkfelix 1.1.2.1 }
827 pnkfelix 1.1.2.1 }
828 pnkfelix 1.1.2.1 // helper function, adapted from Appel's original Coalesce code
829 pnkfelix 1.1.2.1 // (am just applying it to all nodes on each side of the move)
830 pnkfelix 1.1.2.1
831 pnkfelix 1.1.2.1 public void coalesce(Move m, Node x, Node y) {
832 pnkfelix 1.1.2.1 // System.out.println("called coalesce("+m+","+x+","+y+")");
833 pnkfelix 1.1.2.1
834 pnkfelix 1.1.2.1 x = getAlias(x);
835 pnkfelix 1.1.2.1 y = getAlias(y);
836 pnkfelix 1.1.2.1
837 pnkfelix 1.1.2.1 Node u, v;
838 pnkfelix 1.1.2.1 if( y.isPrecolored() ){
839 pnkfelix 1.1.2.1 u = y; v = x;
840 pnkfelix 1.1.2.1 } else {
841 pnkfelix 1.1.2.1 u = x; v = y;
842 pnkfelix 1.1.2.1 }
843 pnkfelix 1.1.2.1
844 pnkfelix 1.1.2.1 // FSK: see coalesce() above [ pop() implicitly removes m ]
845 pnkfelix 1.1.2.1 // worklist_moves.remove(m);
846 pnkfelix 1.1.2.1
847 pnkfelix 1.1.2.1 // TODO: NEED TO THINK ABOUT WHICH SET THE MOVE WILL GO INTO!!!
848 pnkfelix 1.1.2.1 // ( possibly adding new cases here?!!? )
849 pnkfelix 1.1.2.1
850 pnkfelix 1.1.2.1 if (u.equals(v)) {
851 pnkfelix 1.1.2.13 // seems silly until you notice the getAlias(..)'s above
852 pnkfelix 1.1.2.1
853 pnkfelix 1.1.2.1 coalesced_moves.add(m);
854 pnkfelix 1.1.2.1 addWorkList(u);
855 pnkfelix 1.1.2.11
856 pnkfelix 1.1.2.11 } else if (v.isPrecolored() || adjSet.contains(u,v) ) {
857 pnkfelix 1.1.2.11 // slightly obfuscated way of asking "do u and v conflict?"
858 pnkfelix 1.1.2.1
859 pnkfelix 1.1.2.1 constrained_moves.add(m);
860 pnkfelix 1.1.2.1 addWorkList(u);
861 pnkfelix 1.1.2.1 addWorkList(v);
862 pnkfelix 1.1.2.1
863 pnkfelix 1.1.2.1 } else if(( u.isPrecolored() &&
864 pnkfelix 1.1.2.1 forall_t_in_adj_of_v__OK_t_u(v, u))
865 pnkfelix 1.1.2.1 ||
866 pnkfelix 1.1.2.13 ( ! u.isPrecolored() && conservative(u, v)) ) {
867 pnkfelix 1.1.2.1 // System.out.println( "ugly case, u:"+u+" v:"+v );
868 pnkfelix 1.1.2.1
869 pnkfelix 1.1.2.1 coalesced_moves.add(m);
870 pnkfelix 1.1.2.1
871 pnkfelix 1.1.2.1 combine(u, v);
872 pnkfelix 1.1.2.1
873 pnkfelix 1.1.2.1 addWorkList(u);
874 pnkfelix 1.1.2.1
875 pnkfelix 1.1.2.1 } else {
876 pnkfelix 1.1.2.1 // System.out.println( "'else' case "+m );
877 pnkfelix 1.1.2.1
878 pnkfelix 1.1.2.1 active_moves.add(m);
879 pnkfelix 1.1.2.1 }
880 pnkfelix 1.1.2.1 }
881 pnkfelix 1.1.2.1 private boolean forall_t_in_adj_of_v__OK_t_u(Node v, Node u) {
882 pnkfelix 1.1.2.1 for( NodeIter ni=adjacent(v); ni.hasNext(); ){
883 pnkfelix 1.1.2.1 Node t = ni.next();
884 pnkfelix 1.1.2.1 if( ! OK(t, u) ) {
885 pnkfelix 1.1.2.1 return false;
886 pnkfelix 1.1.2.1 }
887 pnkfelix 1.1.2.1 }
888 pnkfelix 1.1.2.1 return true;
889 pnkfelix 1.1.2.1 }
890 pnkfelix 1.1.2.1
891 pnkfelix 1.1.2.1 private void addWorkList(Node u) {
892 pnkfelix 1.1.2.1 if( ! u.isPrecolored() &&
893 pnkfelix 1.1.2.1 ! moveRelated( u ) &&
894 pnkfelix 1.1.2.1 u.degree < K ) {
895 pnkfelix 1.1.2.1
896 pnkfelix 1.1.2.1 freeze_worklist.remove( u );
897 pnkfelix 1.1.2.1
898 pnkfelix 1.1.2.1 simplify_worklist.add( u );
899 pnkfelix 1.1.2.1 }
900 pnkfelix 1.1.2.1 }
901 pnkfelix 1.1.2.1
902 pnkfelix 1.1.2.1
903 pnkfelix 1.1.2.1 private boolean OK(Node t, Node r) {
904 pnkfelix 1.1.2.1 return t.degree < K
905 pnkfelix 1.1.2.1 || t.isPrecolored()
906 pnkfelix 1.1.2.1 || adjSet.contains(t, r);
907 pnkfelix 1.1.2.1 }
908 pnkfelix 1.1.2.13 /** conservative coalescing heuristic due to Preston Briggs.
909 pnkfelix 1.1.2.13 Abstracting out because in the prescence of multi-slotted
910 pnkfelix 1.1.2.13 nodes, this changes.
911 pnkfelix 1.1.2.13 */
912 pnkfelix 1.1.2.13 protected abstract boolean conservative(Node u, Node v);
913 pnkfelix 1.1.2.1
914 pnkfelix 1.1.2.1
915 pnkfelix 1.1.2.13 protected Node getAlias(Node n) { // FSK: umm... bound on this runtime?
916 pnkfelix 1.1.2.1 while( n.isCoalesced() ) {
917 pnkfelix 1.1.2.1 n = n.alias;
918 pnkfelix 1.1.2.1 }
919 pnkfelix 1.1.2.1 return n;
920 pnkfelix 1.1.2.1 }
921 pnkfelix 1.1.2.1
922 pnkfelix 1.1.2.1 /**
923 pnkfelix 1.1.2.1 modifies; freeze_worklist, spill_worklist,
924 pnkfelix 1.1.2.1 */
925 pnkfelix 1.1.2.1 private void combine(Node u, Node v) {
926 pnkfelix 1.1.2.1 if (v.isFreezeWorkL()) {
927 pnkfelix 1.1.2.1 freeze_worklist.remove(v);
928 pnkfelix 1.1.2.1 } else {
929 pnkfelix 1.1.2.1 spill_worklist.remove(v);
930 pnkfelix 1.1.2.1 }
931 pnkfelix 1.1.2.1 coalesced_nodes.add(v);
932 pnkfelix 1.1.2.1 v.alias = u;
933 pnkfelix 1.1.2.1
934 pnkfelix 1.1.2.13 enableMoves(v);
935 pnkfelix 1.1.2.1 u.moves.append(v.moves);
936 pnkfelix 1.1.2.1
937 pnkfelix 1.1.2.1 for( NodeIter adj=adjacent(v); adj.hasNext(); ) {
938 pnkfelix 1.1.2.1 Node t = adj.next();
939 pnkfelix 1.1.2.1 addEdge(t,u);
940 pnkfelix 1.1.2.13 decrementDegree(t,v);
941 pnkfelix 1.1.2.1 }
942 pnkfelix 1.1.2.1
943 pnkfelix 1.1.2.1 if( u.degree >= K && u.isFreezeWorkL() ) {
944 pnkfelix 1.1.2.1 freeze_worklist.remove(u);
945 pnkfelix 1.1.2.1 spill_worklist.add(u);
946 pnkfelix 1.1.2.1 }
947 pnkfelix 1.1.2.1 }
948 pnkfelix 1.1.2.1
949 pnkfelix 1.1.2.1 public void freeze() {
950 pnkfelix 1.1.2.1 Node u = freeze_worklist.pop();
951 pnkfelix 1.1.2.1 // System.out.println("FREEZING :"+u);
952 pnkfelix 1.1.2.1
953 pnkfelix 1.1.2.1 simplify_worklist.add(u);
954 pnkfelix 1.1.2.1 checkMoveSets();
955 pnkfelix 1.1.2.1 freezeMoves(u);
956 pnkfelix 1.1.2.1 checkMoveSets();
957 pnkfelix 1.1.2.1 }
958 pnkfelix 1.1.2.1
959 pnkfelix 1.1.2.1
960 pnkfelix 1.1.2.1 private void freezeMoves(Node u) {
961 pnkfelix 1.1.2.1 for( Iterator moves= nodeMoves(u); moves.hasNext(); ) {
962 pnkfelix 1.1.2.1 Move m = (Move) moves.next();
963 pnkfelix 1.1.2.1 Node x = m.dst, y = m.src;
964 pnkfelix 1.1.2.1
965 pnkfelix 1.1.2.1 Node v;
966 pnkfelix 1.1.2.1 if( getAlias(y).equals(getAlias(u)) ) {
967 pnkfelix 1.1.2.1 v = getAlias(x);
968 pnkfelix 1.1.2.1 } else {
969 pnkfelix 1.1.2.1 v = getAlias(y);
970 pnkfelix 1.1.2.1 }
971 pnkfelix 1.1.2.1
972 pnkfelix 1.1.2.1 checkMoveSets();
973 pnkfelix 1.1.2.1 active_moves.remove(m);
974 pnkfelix 1.1.2.1 frozen_moves.add(m);
975 pnkfelix 1.1.2.1 checkMoveSets();
976 pnkfelix 1.1.2.1
977 pnkfelix 1.1.2.1 if ( ( ! nodeMoves(v).hasNext()) && v.degree < K ) {
978 pnkfelix 1.1.2.1 freeze_worklist.remove(v);
979 pnkfelix 1.1.2.1 simplify_worklist.add(v);
980 pnkfelix 1.1.2.1 }
981 pnkfelix 1.1.2.1 }
982 pnkfelix 1.1.2.1 }
983 pnkfelix 1.1.2.1
984 pnkfelix 1.1.2.13 private boolean spillable( Web w ) {
985 cananian 1.7 for(Object dO : w.defs) {
986 cananian 1.7 Instr d = (Instr) dO;
987 pnkfelix 1.1.2.13 if (d instanceof RestoreProxy ||
988 pnkfelix 1.1.2.13 dontSpillTheseDefs.contains(d)) {
989 pnkfelix 1.1.2.13 return false;
990 pnkfelix 1.1.2.1 }
991 pnkfelix 1.1.2.13 }
992 pnkfelix 1.1.2.13 for(Iterator ui = w.uses.iterator(); ui.hasNext(); ){
993 pnkfelix 1.1.2.13 if (ui.next() instanceof SpillProxy) {
994 pnkfelix 1.1.2.13 return false;
995 pnkfelix 1.1.2.1 }
996 pnkfelix 1.1.2.1 }
997 pnkfelix 1.1.2.13 return true;
998 pnkfelix 1.1.2.1 }
999 pnkfelix 1.1.2.1
1000 pnkfelix 1.1.2.7 static class CouldntFindSpillExn extends Exception {}
1001 pnkfelix 1.1.2.7 private void selectSpill(SpillHeuristic sh) throws CouldntFindSpillExn {
1002 pnkfelix 1.1.2.1 // Note: avoid choosing nodes that are tiny live ranges
1003 pnkfelix 1.1.2.1 // from fetching spilled registers
1004 pnkfelix 1.1.2.1 Node minNode = null;
1005 pnkfelix 1.1.2.1 double minCost = Double.MAX_VALUE;
1006 pnkfelix 1.1.2.1
1007 pnkfelix 1.1.2.1 nextNode:
1008 pnkfelix 1.1.2.1 for(NodeIter nI = spill_worklist.iter(); nI.hasNext(); ) {
1009 pnkfelix 1.1.2.1 Node n = nI.next();
1010 pnkfelix 1.1.2.1
1011 cananian 1.3.2.1 assert ! isRegister(n.web.temp);
1012 pnkfelix 1.1.2.12
1013 pnkfelix 1.1.2.13 // if (!n.web.isSpillable())
1014 pnkfelix 1.1.2.13 if ( ! spillable(n.web) )
1015 pnkfelix 1.1.2.12 continue nextNode;
1016 pnkfelix 1.1.2.1
1017 pnkfelix 1.1.2.1 double cost = sh.cost( n );
1018 pnkfelix 1.1.2.1 if (cost > minCost)
1019 pnkfelix 1.1.2.1 continue;
1020 pnkfelix 1.1.2.1 else {
1021 pnkfelix 1.1.2.1 minNode = n;
1022 pnkfelix 1.1.2.1 minCost = cost;
1023 pnkfelix 1.1.2.1 }
1024 pnkfelix 1.1.2.1 }
1025 pnkfelix 1.1.2.7 if (minNode == null) throw new CouldntFindSpillExn();
1026 pnkfelix 1.1.2.1
1027 pnkfelix 1.1.2.1 // System.out.println("spilling node with cost : "+minCost);
1028 pnkfelix 1.1.2.1
1029 pnkfelix 1.1.2.10 sh.expectSpill( minNode );
1030 pnkfelix 1.1.2.1 spill_worklist.remove( minNode );
1031 pnkfelix 1.1.2.1 simplify_worklist.add( minNode );
1032 pnkfelix 1.1.2.1 freezeMoves( minNode );
1033 pnkfelix 1.1.2.1 }
1034 pnkfelix 1.1.2.1
1035 pnkfelix 1.1.2.13 /** Gives the nodes a legal color assignment.
1036 pnkfelix 1.1.2.13 Abstract because different variants have different
1037 pnkfelix 1.1.2.13 ways of mapping nodes to colors.
1038 pnkfelix 1.1.2.13 */
1039 pnkfelix 1.1.2.13 protected abstract void assignColors();
1040 pnkfelix 1.1.2.1
1041 pnkfelix 1.1.2.1 int rewriteCalledNumTimes = 0;
1042 pnkfelix 1.1.2.1 public void rewriteProgram() {
1043 pnkfelix 1.1.2.1 rewriteCalledNumTimes++;
1044 pnkfelix 1.1.2.7
1045 pnkfelix 1.1.2.12 if (try_to_clean &&
1046 pnkfelix 1.1.2.12 rewriteCalledNumTimes == NUM_CLEANINGS_TO_TRY) {
1047 pnkfelix 1.1.2.12 stopTryingToClean();
1048 pnkfelix 1.1.2.16 // initializeSets();
1049 pnkfelix 1.1.2.12 bbFact = computeBasicBlocks();
1050 pnkfelix 1.1.2.12 return;
1051 pnkfelix 1.1.2.12 }
1052 pnkfelix 1.1.2.7
1053 pnkfelix 1.1.2.1 // Allocate memory locations for each v : spilledNodes
1054 pnkfelix 1.1.2.1 // Create a new temporary v_i for each definition and each use
1055 pnkfelix 1.1.2.1 // In the program (instructions), insert a store after each
1056 pnkfelix 1.1.2.1 // definition of a v_i, a fetch before each use of a v_i.
1057 pnkfelix 1.1.2.1 // Put all the v_i into a set newTemps
1058 pnkfelix 1.1.2.1 // spilledNodes <- {}
1059 pnkfelix 1.1.2.1 // initial <- coloredNodes \/ coalescedNodes \/ newTemps
1060 pnkfelix 1.1.2.1 // coloredNodes <- {}
1061 pnkfelix 1.1.2.1 // coalescedNodes <- {}
1062 pnkfelix 1.1.2.1
1063 pnkfelix 1.1.2.1 // simplifies to
1064 pnkfelix 1.1.2.1 // foreach w : spilledNodes.web
1065 pnkfelix 1.1.2.1 // foreach d : w.defs
1066 pnkfelix 1.1.2.1 // insert SpillProxy
1067 pnkfelix 1.1.2.1 // foreach u : w.uses
1068 pnkfelix 1.1.2.1 // insert RestoreProxy
1069 pnkfelix 1.1.2.1 // (possibly excepting instrs that both define and use w.temp)
1070 pnkfelix 1.1.2.1 // initializeSets
1071 pnkfelix 1.1.2.1 HashSet seenWebs = new HashSet();
1072 pnkfelix 1.1.2.1 for(NodeIter ni=spilled_nodes.iter(); ni.hasNext(); ){
1073 pnkfelix 1.1.2.1 Node n = ni.next();
1074 pnkfelix 1.1.2.1 // System.out.println("spilling node with cost : "+costOf(n));
1075 pnkfelix 1.1.2.1 Web w = n.web;
1076 pnkfelix 1.1.2.1 if( seenWebs.add(w) ){
1077 pnkfelix 1.1.2.1 Collection spillCode = addDefs(w);
1078 pnkfelix 1.1.2.1 Collection restoreCode = addUses(w);
1079 pnkfelix 1.1.2.13 insertedSpillCode.addAll(spillCode);
1080 pnkfelix 1.1.2.13 insertedSpillCode.addAll(restoreCode);
1081 pnkfelix 1.1.2.1 }
1082 pnkfelix 1.1.2.1 }
1083 pnkfelix 1.1.2.1
1084 pnkfelix 1.1.2.11 if (PRINT_DEPTH_TO_SPILL_INFO) {
1085 pnkfelix 1.1.2.11 System.out.println();
1086 pnkfelix 1.1.2.11 System.out.print("locally "+spillStats(depthToNumSpills));
1087 pnkfelix 1.1.2.11 System.out.println();
1088 pnkfelix 1.1.2.11 }
1089 pnkfelix 1.1.2.7
1090 pnkfelix 1.1.2.16 // initializeSets();
1091 pnkfelix 1.1.2.1 bbFact = computeBasicBlocks();
1092 pnkfelix 1.1.2.1 }
1093 pnkfelix 1.1.2.7
1094 pnkfelix 1.1.2.1 private Collection addDefs(Web w) {
1095 pnkfelix 1.1.2.1 HashSet groupDefs = new HashSet(w.defs.size());
1096 pnkfelix 1.1.2.11 int cleanedNum = 0;
1097 cananian 1.7 for(Object dO : w.defs) {
1098 cananian 1.7 Instr d = (Instr) dO;
1099 pnkfelix 1.1.2.7 Instr exit = d.getExit(InstrGroup.NO_SPILL);
1100 pnkfelix 1.1.2.11
1101 pnkfelix 1.1.2.11 BasicBlock bb = bbFact.getBlock(exit);
1102 cananian 1.3.2.1 assert bbFact.getBlock(exit) != null : "no BB found for exit";
1103 pnkfelix 1.1.2.11
1104 pnkfelix 1.1.2.11 if (CLEAN_BB_LOCAL_DEFS && try_to_clean) {
1105 pnkfelix 1.1.2.11 Set liveOut = liveTemps.getLiveAfter(bb.getLast());
1106 pnkfelix 1.1.2.11 if ( ! liveOut.contains( w.temp )) {
1107 pnkfelix 1.1.2.11 System.out.println
1108 pnkfelix 1.1.2.11 ("refusing to spill bb-local! "+w.temp);
1109 pnkfelix 1.1.2.11 dontSpillTheseDefs.add(d);
1110 pnkfelix 1.1.2.11 cleanedNum++;
1111 pnkfelix 1.1.2.11 continue;
1112 pnkfelix 1.1.2.11 }
1113 pnkfelix 1.1.2.11 }
1114 pnkfelix 1.1.2.11 groupDefs.add(exit);
1115 pnkfelix 1.1.2.1 }
1116 pnkfelix 1.1.2.1
1117 pnkfelix 1.1.2.7 if ( try_to_clean ){
1118 pnkfelix 1.1.2.1 // clean out redundant targets
1119 pnkfelix 1.1.2.1 LinearSet blocks = new LinearSet();
1120 cananian 1.7 for(Object instrO : groupDefs){
1121 cananian 1.7 Instr instr = (Instr) instrO;
1122 pnkfelix 1.1.2.7 BasicBlock bb = bbFact.getBlock( instr );
1123 pnkfelix 1.1.2.7 blocks.add( bb );
1124 pnkfelix 1.1.2.1 }
1125 cananian 1.7 for(Object bbO : blocks){
1126 cananian 1.7 BasicBlock bb = (BasicBlock) bbO;
1127 pnkfelix 1.1.2.1 boolean seenOne = false;
1128 pnkfelix 1.1.2.1 Iterator stms =bb.statements().iterator();
1129 pnkfelix 1.1.2.1 stms = new ReverseIterator( stms );
1130 pnkfelix 1.1.2.1 while( stms.hasNext() ){
1131 pnkfelix 1.1.2.1 Instr i = (Instr) stms.next();
1132 pnkfelix 1.1.2.1 if (groupDefs.contains(i)){
1133 pnkfelix 1.1.2.1 if (!seenOne) {
1134 pnkfelix 1.1.2.11 seenOne = true;
1135 pnkfelix 1.1.2.11 continue;
1136 pnkfelix 1.1.2.1 } else {
1137 pnkfelix 1.1.2.1 groupDefs.remove(i);
1138 pnkfelix 1.1.2.1 cleanedNum++;
1139 pnkfelix 1.1.2.1 }
1140 pnkfelix 1.1.2.1 }
1141 pnkfelix 1.1.2.1 }
1142 pnkfelix 1.1.2.1 }
1143 pnkfelix 1.1.2.10 if (PRINT_CLEANING_INFO && cleanedNum != 0)
1144 pnkfelix 1.1.2.1 System.out.println("Def cleaning removed "+cleanedNum);
1145 pnkfelix 1.1.2.1 }
1146 pnkfelix 1.1.2.1
1147 pnkfelix 1.1.2.1 return addDefs( w, groupDefs );
1148 pnkfelix 1.1.2.1 }
1149 pnkfelix 1.1.2.1 private Collection addDefs( Web w, Collection groupDefs) {
1150 pnkfelix 1.1.2.1 ArrayList spills = new ArrayList();
1151 cananian 1.7 for(Object dO : groupDefs) {
1152 cananian 1.7 Instr d = (Instr) dO;
1153 pnkfelix 1.1.2.1 Instr n = d.getNext();
1154 cananian 1.3.2.1 assert d.canFallThrough &&
1155 cananian 1.3.2.1 d.getTargets().isEmpty();
1156 pnkfelix 1.1.2.1
1157 pnkfelix 1.1.2.13 depthToNumSpills[sh.depth(d)]++;
1158 pnkfelix 1.1.2.1
1159 pnkfelix 1.1.2.1 SpillProxy sp = new SpillProxy(d, w.temp);
1160 pnkfelix 1.1.2.1 spills.add(sp);
1161 pnkfelix 1.1.2.1 sp.layout(d, d.getNext());
1162 pnkfelix 1.1.2.1 }
1163 pnkfelix 1.1.2.1 return spills;
1164 pnkfelix 1.1.2.1 }
1165 pnkfelix 1.1.2.1 private Collection addUses(Web w) {
1166 pnkfelix 1.1.2.1 HashSet groupUses = new HashSet(w.uses.size());
1167 cananian 1.7 for(Object uO : w.uses) {
1168 cananian 1.7 Instr u = (Instr) uO;
1169 pnkfelix 1.1.2.1 Instr instrToAdd = u.getEntry(InstrGroup.NO_SPILL);
1170 cananian 1.3.2.1 assert ! instrToAdd.isDummy();
1171 pnkfelix 1.1.2.1 groupUses.add( instrToAdd );
1172 pnkfelix 1.1.2.1 }
1173 pnkfelix 1.1.2.1
1174 pnkfelix 1.1.2.7 if ( try_to_clean ){
1175 pnkfelix 1.1.2.1 // clean out redundant targets
1176 pnkfelix 1.1.2.1 int cleanedNum = 0;
1177 pnkfelix 1.1.2.1 LinearSet blocks = new LinearSet();
1178 pnkfelix 1.1.2.1 for(Iterator ds = groupUses.iterator(); ds.hasNext(); ){
1179 pnkfelix 1.1.2.1 blocks.add( bbFact.getBlock( (Instr)ds.next() ));
1180 pnkfelix 1.1.2.1 }
1181 cananian 1.7 for(Object bbO : blocks){
1182 cananian 1.7 BasicBlock bb = (BasicBlock) bbO;
1183 pnkfelix 1.1.2.1 boolean seenOne = false;
1184 cananian 1.7 for (Object iO : bb.statements()){
1185 cananian 1.7 Instr i = (Instr) iO;
1186 pnkfelix 1.1.2.1 if (groupUses.contains(i)){
1187 pnkfelix 1.1.2.1 if (!seenOne) {
1188 pnkfelix 1.1.2.1 seenOne = true; continue;
1189 pnkfelix 1.1.2.1 } else {
1190 pnkfelix 1.1.2.1 groupUses.remove(i);
1191 pnkfelix 1.1.2.1 cleanedNum++;
1192 pnkfelix 1.1.2.1 }
1193 pnkfelix 1.1.2.7 }
1194 pnkfelix 1.1.2.11 if ( !seenOne && w.defs.contains(i) ){
1195 pnkfelix 1.1.2.11 if ( PRINT_CLEANING_INFO )
1196 pnkfelix 1.1.2.11 System.out.print("\nFSK saw a def before a use: "+i);
1197 pnkfelix 1.1.2.7 seenOne = true;
1198 pnkfelix 1.1.2.1 }
1199 pnkfelix 1.1.2.1 }
1200 pnkfelix 1.1.2.1 }
1201 pnkfelix 1.1.2.10 if (PRINT_CLEANING_INFO && cleanedNum != 0)
1202 pnkfelix 1.1.2.10 System.out.println("\nUse cleaning removed "+cleanedNum);
1203 pnkfelix 1.1.2.1 }
1204 pnkfelix 1.1.2.1
1205 pnkfelix 1.1.2.1 return addUses( w, groupUses );
1206 pnkfelix 1.1.2.1 }
1207 pnkfelix 1.1.2.1 private Collection addUses( Web w, Collection groupUses ){
1208 pnkfelix 1.1.2.1 ArrayList spills = new ArrayList();
1209 cananian 1.7 for(Object uO : groupUses) {
1210 cananian 1.7 Instr u = (Instr) uO;
1211 pnkfelix 1.1.2.1 Instr p = u.getPrev();
1212 cananian 1.3.2.1 assert p.canFallThrough &&
1213 pnkfelix 1.1.2.1 p.getTargets().isEmpty() &&
1214 cananian 1.3.2.1 u.predC().size() == 1;
1215 pnkfelix 1.1.2.1
1216 pnkfelix 1.1.2.13 depthToNumSpills[sh.depth(u)]++;
1217 pnkfelix 1.1.2.1
1218 pnkfelix 1.1.2.1 RestoreProxy rp = new RestoreProxy(u, w.temp);
1219 pnkfelix 1.1.2.1 spills.add(rp);
1220 pnkfelix 1.1.2.1 rp.layout(p, u);
1221 pnkfelix 1.1.2.1 }
1222 pnkfelix 1.1.2.1 return spills;
1223 pnkfelix 1.1.2.1 }
1224 pnkfelix 1.1.2.1
1225 pnkfelix 1.1.2.1 int precolor;
1226 pnkfelix 1.1.2.13 protected Node makePrecolored(Temp reg) {
1227 cananian 1.3.2.1 assert rfi().isRegister(reg);
1228 pnkfelix 1.1.2.16 Web w = new Web(reg, Collections.EMPTY_SET, Collections.EMPTY_SET);
1229 pnkfelix 1.1.2.16 tempToWebs.put(reg,w);
1230 pnkfelix 1.1.2.1 Node n = new Node(precolored, w);
1231 pnkfelix 1.1.2.13 n.color[0] = precolor;
1232 pnkfelix 1.1.2.1 n.degree = Integer.MAX_VALUE;
1233 pnkfelix 1.1.2.1 precolor++;
1234 pnkfelix 1.1.2.13 return n;
1235 pnkfelix 1.1.2.1 }
1236 pnkfelix 1.1.2.1
1237 pnkfelix 1.1.2.13 /** Creates node(s) for <code>t</code> in the interference graph.
1238 pnkfelix 1.1.2.13 Abstract because variants of the algorithm map <code>Temps</code>
1239 pnkfelix 1.1.2.13 to nodes differently.
1240 pnkfelix 1.1.2.13 */
1241 pnkfelix 1.1.2.13 protected abstract void makeInitial(Temp t);
1242 pnkfelix 1.1.2.13
1243 pnkfelix 1.1.2.1 // resets the state in preparation for a coloring attempt
1244 pnkfelix 1.1.2.13 protected void initializeSets() {
1245 pnkfelix 1.1.2.1 precolor = 0;
1246 pnkfelix 1.1.2.1 initializeNodeSets();
1247 pnkfelix 1.1.2.1 initializeMoveSets();
1248 pnkfelix 1.1.2.13 sh.reset();
1249 pnkfelix 1.1.2.13 }
1250 pnkfelix 1.1.2.11
1251 pnkfelix 1.1.2.13 protected NodeIter def(Instr i) {
1252 pnkfelix 1.1.2.13 return nodesIter( defCN( i ).iterator() );
1253 pnkfelix 1.1.2.13 }
1254 pnkfelix 1.1.2.13 protected NodeIter usedef(Instr i) {
1255 pnkfelix 1.1.2.13 HashSet s = new HashSet();
1256 pnkfelix 1.1.2.13 s.addAll( useCN( i ));
1257 pnkfelix 1.1.2.13 s.addAll( defCN( i ));
1258 pnkfelix 1.1.2.13 return nodesIter( s.iterator() );
1259 pnkfelix 1.1.2.1 }
1260 pnkfelix 1.1.2.1
1261 pnkfelix 1.1.2.13 protected Collection/*Node*/ useCN(Instr i) {
1262 pnkfelix 1.1.2.13 Collection nodeC = tempCtoNodes( useCT( i ), i );
1263 pnkfelix 1.1.2.13 return nodeC;
1264 pnkfelix 1.1.2.13 }
1265 pnkfelix 1.1.2.1
1266 pnkfelix 1.1.2.13 protected Collection/*Node*/ defCN(Instr i) {
1267 pnkfelix 1.1.2.13 Collection nodeC = tempCtoNodes( defCT( i ), i);
1268 pnkfelix 1.1.2.13 return nodeC;
1269 pnkfelix 1.1.2.13 }
1270 pnkfelix 1.1.2.13
1271 pnkfelix 1.1.2.13 protected Set/*Node*/ tempCtoNodes( Collection temps, Instr i ) {
1272 pnkfelix 1.1.2.13 HashSet set = new HashSet();
1273 cananian 1.7 for(Object tO : temps) {
1274 cananian 1.7 Temp t = (Temp) tO;
1275 pnkfelix 1.1.2.13 Web web = webFor( t, i );
1276 pnkfelix 1.1.2.13 set.addAll( nodesFor( web ));
1277 pnkfelix 1.1.2.13 }
1278 pnkfelix 1.1.2.13 return set;
1279 pnkfelix 1.1.2.13 }
1280 pnkfelix 1.1.2.13 // RETURN a Set of Node or a NodeSet ???
1281 pnkfelix 1.1.2.13 protected Set liveOut(BasicBlock b) {
1282 pnkfelix 1.1.2.13 Instr last = lastStm( b );
1283 pnkfelix 1.1.2.13 Set s = liveTemps.getLiveAfter( last );
1284 pnkfelix 1.1.2.13
1285 pnkfelix 1.1.2.13 // TODO: check that 'last' is the right thing to pass in here...
1286 pnkfelix 1.1.2.13 return tempCtoNodes( s, last );
1287 pnkfelix 1.1.2.13 }
1288 pnkfelix 1.1.2.13
1289 pnkfelix 1.1.2.13
1290 pnkfelix 1.1.2.13 /** Returns a List of Node mapped to by <code>w</code>.
1291 pnkfelix 1.1.2.13 Abstract because variants of the algorithm map Webs to Nodes
1292 pnkfelix 1.1.2.13 in different ways.
1293 pnkfelix 1.1.2.13 */
1294 pnkfelix 1.1.2.13 protected abstract List nodesFor( Web w );
1295 pnkfelix 1.1.2.13
1296 pnkfelix 1.1.2.1
1297 pnkfelix 1.1.2.1 private boolean haveWebFor(Temp t, Instr i) {
1298 pnkfelix 1.1.2.1 // TODO: implement method or eliminate calls to it
1299 pnkfelix 1.1.2.1 return false;
1300 pnkfelix 1.1.2.1 }
1301 pnkfelix 1.1.2.13 protected Web webFor(Temp t, Instr i) {
1302 cananian 1.7 if ( isRegister(t) ) { return tempToWebs.get(t); }
1303 pnkfelix 1.1.2.1
1304 pnkfelix 1.1.2.1 // TODO: Find reasoning justifying this line! (webFor works on
1305 pnkfelix 1.1.2.1 // concrete view of code? Need to revise specs of many many
1306 pnkfelix 1.1.2.1 // methods...)
1307 pnkfelix 1.1.2.1 i = i.getEntry( InstrGroup.AGGREGATE );
1308 pnkfelix 1.1.2.1
1309 pnkfelix 1.1.2.1 if ( !defCT(i).contains(t) && !useCT(i).contains(t) ){
1310 pnkfelix 1.1.2.1 // slight hack; look up a def associated with 't' for 'i'
1311 pnkfelix 1.1.2.1 // on demand. Saves us trouble of storing total live
1312 pnkfelix 1.1.2.1 // range inside of web. (New thought; can actually get
1313 pnkfelix 1.1.2.1 // away with only storing uses in Webs if necessary)
1314 pnkfelix 1.1.2.1
1315 pnkfelix 1.1.2.1 Set defs = rdefs.reachingDefs(i,t);
1316 pnkfelix 1.1.2.1
1317 pnkfelix 1.1.2.1 if (defs.isEmpty()) {
1318 pnkfelix 1.1.2.1 code.printPreallocatedCode();
1319 cananian 1.3.2.1 assert false : "should exist defs of "+t+" that reach "+i;
1320 pnkfelix 1.1.2.1 }
1321 pnkfelix 1.1.2.1
1322 pnkfelix 1.1.2.1 i = (Instr) defs.iterator().next();
1323 pnkfelix 1.1.2.1 }
1324 pnkfelix 1.1.2.1
1325 pnkfelix 1.1.2.1 // should never be asserted now...
1326 cananian 1.3.2.1 assert defCT(i).contains(t) || useCT(i).contains(t) : "Method not guaranteed behave properly "+
1327 cananian 1.3.2.1 "on Instrs that don't refer to 't'";
1328 pnkfelix 1.1.2.1
1329 cananian 1.7 Collection<Web> webs = tempToWebs.getValues(t);
1330 cananian 1.7 for(Object wO : webs) {
1331 cananian 1.7 Web w = (Web) wO;
1332 pnkfelix 1.1.2.1 if (w.defs.contains(i) ||
1333 pnkfelix 1.1.2.1 w.uses.contains(i) ) {
1334 pnkfelix 1.1.2.1 return w;
1335 pnkfelix 1.1.2.1 }
1336 pnkfelix 1.1.2.1 }
1337 cananian 1.3.2.1 assert false : "Couldn't find the web for "+t+" , "+i;
1338 pnkfelix 1.1.2.1 return null;
1339 pnkfelix 1.1.2.1 }
1340 pnkfelix 1.1.2.1 private Web addWeb( Temp t, Set defs, Set uses ) {
1341 pnkfelix 1.1.2.1 Web web = new Web( t, defs, uses );
1342 pnkfelix 1.1.2.1 tempToWebs.add( t, web );
1343 pnkfelix 1.1.2.1 return web;
1344 pnkfelix 1.1.2.1 }
1345 pnkfelix 1.1.2.1
1346 cananian 1.2 }