1 pnkfelix 1.1.2.1 // RegAlloc.java, created Mon Mar 29 16:47:25 1999 by pnkfelix
2 cananian 1.1.2.126 // Copyright (C) 1999 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.7 import harpoon.Temp.Label;
7 pnkfelix 1.1.2.1 import harpoon.Temp.Temp;
8 pnkfelix 1.1.2.101 import harpoon.Temp.TempMap;
9 pnkfelix 1.1.2.1 import harpoon.IR.Assem.Instr;
10 pnkfelix 1.1.2.31 import harpoon.IR.Assem.InstrEdge;
11 pnkfelix 1.1.2.14 import harpoon.IR.Assem.InstrFactory;
12 pnkfelix 1.1.2.125 import harpoon.IR.Assem.InstrGroup;
13 pnkfelix 1.1.2.6 import harpoon.IR.Assem.InstrMEM;
14 pnkfelix 1.1.2.6 import harpoon.IR.Assem.InstrVisitor;
15 pnkfelix 1.1.2.125 import harpoon.IR.Properties.UseDefer;
16 cananian 1.1.2.124 import harpoon.IR.Properties.UseDefable;
17 pnkfelix 1.1.2.60 import harpoon.IR.Properties.CFGrapher;
18 pnkfelix 1.1.2.1 import harpoon.Backend.Generic.Frame;
19 pnkfelix 1.1.2.1 import harpoon.Backend.Generic.Code;
20 pnkfelix 1.1.2.36 import harpoon.Backend.Generic.RegFileInfo;
21 pnkfelix 1.1.2.36 import harpoon.Backend.Generic.RegFileInfo.SpillException;
22 pnkfelix 1.1.2.83 import harpoon.Backend.Generic.RegFileInfo.TempLocator;
23 pnkfelix 1.1.2.83 import harpoon.Backend.Generic.RegFileInfo.MachineRegLoc;
24 pnkfelix 1.1.2.83 import harpoon.Backend.Generic.RegFileInfo.StackOffsetLoc;
25 pnkfelix 1.1.2.36 import harpoon.Backend.Generic.InstrBuilder;
26 pnkfelix 1.1.2.39 import harpoon.Analysis.BasicBlock;
27 salcianu 1.4 import harpoon.Analysis.BasicBlockInterf;
28 cananian 1.1.2.73 import harpoon.Analysis.Maps.Derivation;
29 pnkfelix 1.1.2.99 import harpoon.Backend.Maps.BackendDerivation;
30 pnkfelix 1.1.2.3 import harpoon.ClassFile.HCodeFactory;
31 pnkfelix 1.1.2.3 import harpoon.ClassFile.HCode;
32 pnkfelix 1.1.2.99 import harpoon.ClassFile.HClass;
33 pnkfelix 1.1.2.3 import harpoon.ClassFile.HCodeElement;
34 pnkfelix 1.1.2.3 import harpoon.ClassFile.HMethod;
35 pnkfelix 1.1.2.7 import harpoon.Util.Util;
36 cananian 1.8 import net.cscott.jutil.Default;
37 cananian 1.8 import net.cscott.jutil.MultiMap;
38 cananian 1.8 import net.cscott.jutil.MultiMapFactory;
39 cananian 1.8 import net.cscott.jutil.GenericMultiMap;
40 cananian 1.8 import net.cscott.jutil.UnmodifiableIterator;
41 cananian 1.8 import net.cscott.jutil.CombineIterator;
42 pnkfelix 1.1.2.44
43 pnkfelix 1.1.2.42 import harpoon.Analysis.DataFlow.ReachingDefs;
44 pnkfelix 1.1.2.42 import harpoon.Analysis.DataFlow.ForwardDataFlowBasicBlockVisitor;
45 pnkfelix 1.1.2.42 import harpoon.Analysis.DataFlow.InstrSolver;
46 pnkfelix 1.1.2.19
47 pnkfelix 1.1.2.1 import java.util.Hashtable;
48 pnkfelix 1.1.2.19 import java.util.Arrays;
49 pnkfelix 1.1.2.49 import java.util.Collection;
50 pnkfelix 1.1.2.56 import java.util.Collections;
51 pnkfelix 1.1.2.1 import java.util.Set;
52 pnkfelix 1.1.2.1 import java.util.Vector;
53 pnkfelix 1.1.2.7 import java.util.List;
54 pnkfelix 1.1.2.90 import java.util.ArrayList;
55 pnkfelix 1.1.2.1 import java.util.ListIterator;
56 pnkfelix 1.1.2.6 import java.util.Iterator;
57 pnkfelix 1.1.2.1 import java.util.HashSet;
58 pnkfelix 1.1.2.1 import java.util.Map;
59 pnkfelix 1.1.2.1 import java.util.HashMap;
60 pnkfelix 1.1.2.1
61 pnkfelix 1.1.2.3
62 pnkfelix 1.1.2.1 /**
63 pnkfelix 1.1.2.3 * <code>RegAlloc</code> performs Register Allocation for a set of
64 pnkfelix 1.1.2.12 * <code>Instr</code>s in a <code>Backend.Generic.Code</code>. After
65 pnkfelix 1.1.2.12 * register allocation is completed for a set of <code>Instr</code>s,
66 pnkfelix 1.1.2.65 * references to non-register <code>Temp</code>s in the
67 pnkfelix 1.1.2.65 * <code>Instr</code>s will have been replaced by references to
68 pnkfelix 1.1.2.65 * machine registers. Since the number of simultaneously live
69 pnkfelix 1.1.2.65 * temporaries will exceed the space in the register file, spill code
70 pnkfelix 1.1.2.65 * will also be inserted to maintain the state of the register file at
71 pnkfelix 1.1.2.65 * each instruction, storing values to the stack and reloading them as
72 pnkfelix 1.1.2.65 * needed.
73 pnkfelix 1.1.2.1 *
74 pnkfelix 1.1.2.94 * <BR> <B>DESIGN NOTE:</B> The <code>abstractSpillFactory</code>
75 pnkfelix 1.1.2.68 * method relies on the subclasses of <code>RegAlloc</code> to perform
76 pnkfelix 1.1.2.68 * actual allocation. This causes a cycle in our module dependency
77 pnkfelix 1.1.2.68 * graph, which, while not strictly illegal, tends to be a sign of a
78 pnkfelix 1.1.2.68 * design flaw. Consider moving the code factory generator out of the
79 pnkfelix 1.1.2.68 * <code>RegAlloc</code> class into a seperate class to get rid of the
80 pnkfelix 1.1.2.68 * cycle. In the meantime, any new <code>RegAlloc</code> subclasses
81 pnkfelix 1.1.2.68 * can be incorporated into this method to be used in the compiler.
82 pnkfelix 1.1.2.68 * Perhaps should also design a way to parameterize which
83 pnkfelix 1.1.2.68 * <code>RegAlloc</code> subclasses will be used.
84 pnkfelix 1.1.2.64 *
85 cananian 1.1.2.126 * @author Felix S. Klock II <pnkfelix@mit.edu>
86 cananian 1.9 * @version $Id: RegAlloc.java,v 1.9 2004/02/08 03:19:37 cananian Exp $
87 pnkfelix 1.1.2.65 */
88 pnkfelix 1.1.2.3 public abstract class RegAlloc {
89 pnkfelix 1.1.2.109
90 pnkfelix 1.1.2.109 public static abstract class Factory {
91 pnkfelix 1.1.2.109 public abstract RegAlloc makeRegAlloc(Code c);
92 pnkfelix 1.1.2.109 }
93 pnkfelix 1.1.2.1
94 pnkfelix 1.1.2.106 /** Flags whether debugging information should be printed to
95 pnkfelix 1.1.2.106 System.out. */
96 pnkfelix 1.1.2.66 public static final boolean DEBUG = false;
97 pnkfelix 1.1.2.68
98 pnkfelix 1.1.2.106 /** Flags whether timing information should be printed to
99 pnkfelix 1.1.2.106 System.out. */
100 pnkfelix 1.1.2.107 public static final boolean TIME = false;
101 pnkfelix 1.1.2.106
102 pnkfelix 1.1.2.106 /** <code>Generic.Frame</code> for <code>this</code>. */
103 pnkfelix 1.1.2.3 protected Frame frame;
104 pnkfelix 1.1.2.106
105 pnkfelix 1.1.2.106 /** <code>Generic.Code</code> for <code>this</code>. */
106 pnkfelix 1.1.2.3 protected Code code;
107 pnkfelix 1.1.2.106
108 pnkfelix 1.1.2.106 /** <code>BasicBlock.Factory</code> for BasicBlocks of
109 pnkfelix 1.1.2.106 <code>this.code</code>. */
110 pnkfelix 1.1.2.75 protected BasicBlock.Factory bbFact;
111 pnkfelix 1.1.2.1
112 pnkfelix 1.1.2.106 /** Tracks <code>Instr</code>s that have been verified for
113 pnkfelix 1.1.2.106 debugging purposes. */
114 pnkfelix 1.1.2.90 protected HashSet checked = new HashSet();
115 pnkfelix 1.1.2.82
116 pnkfelix 1.1.2.125 /** (Helper method) Returns a <code>CFGrapher</code> that treats
117 pnkfelix 1.1.2.125 <code>InstrGroup</code>s of <code>Type</code> <code>t</code>
118 pnkfelix 1.1.2.125 as single atomic elements. */
119 pnkfelix 1.1.2.125 protected CFGrapher getGrapherFor(InstrGroup.Type t) {
120 pnkfelix 1.1.2.125 return code.getInstrFactory().getGrapherFor(t);
121 pnkfelix 1.1.2.125 }
122 pnkfelix 1.1.2.125
123 pnkfelix 1.1.2.125 /** (Helper method) Returns a <code>UseDefer</code> that treats
124 pnkfelix 1.1.2.125 <code>InstrGroup</code>s of <code>Type</code> <code>t</code>
125 pnkfelix 1.1.2.125 as single atomic elements. */
126 pnkfelix 1.1.2.125 protected UseDefer getUseDeferFor(InstrGroup.Type t) {
127 pnkfelix 1.1.2.125 return code.getInstrFactory().getUseDeferFor(t);
128 pnkfelix 1.1.2.125 }
129 pnkfelix 1.1.2.125
130 pnkfelix 1.1.2.125 /** (Helper method) Returns the RegFileInfo for the frame of the code being analyzed.
131 pnkfelix 1.1.2.125 */
132 pnkfelix 1.1.2.125 protected final RegFileInfo rfi() {
133 pnkfelix 1.1.2.125 return frame.getRegFileInfo();
134 pnkfelix 1.1.2.125 }
135 pnkfelix 1.1.2.114
136 pnkfelix 1.1.2.102 /** Map[ Instr:i -> Instr:b ], where `i' was added to `code'
137 pnkfelix 1.1.2.102 because of `b'. The `b' is used when queries are performed on
138 pnkfelix 1.1.2.102 `i', so it is important that all of the <code>Temp</code>s
139 pnkfelix 1.1.2.102 referenced by `i' are also referenced by `b' (so that
140 pnkfelix 1.1.2.102 Derivation lookups will succeed).
141 pnkfelix 1.1.2.99 */
142 pnkfelix 1.1.2.114 private Map backedInstrs = new HashMap();
143 pnkfelix 1.1.2.114
144 pnkfelix 1.1.2.114 /** adds a mapping <code>instr</code> to <code>back</code> in
145 pnkfelix 1.1.2.114 to the BackedInstrs.
146 pnkfelix 1.1.2.114 */
147 pnkfelix 1.1.2.114 protected void back(Instr instr, Instr back) {
148 pnkfelix 1.1.2.114 if (backedInstrs.keySet().contains(back)) {
149 pnkfelix 1.1.2.114 backedInstrs.put(instr, backedInstrs.get(back));
150 pnkfelix 1.1.2.114 } else {
151 pnkfelix 1.1.2.114 backedInstrs.put(instr, back);
152 pnkfelix 1.1.2.114 }
153 pnkfelix 1.1.2.114 }
154 pnkfelix 1.1.2.114
155 pnkfelix 1.1.2.125 /** replaces 'orig' with 'repl', and modifies internal data
156 pnkfelix 1.1.2.125 structures to reflect that replacement as necessary.
157 pnkfelix 1.1.2.125 */
158 pnkfelix 1.1.2.125 protected void replace(Instr orig, Instr repl) {
159 pnkfelix 1.1.2.125 Instr.replace(orig, repl);
160 pnkfelix 1.1.2.125 back(repl, orig);
161 pnkfelix 1.1.2.125 }
162 pnkfelix 1.1.2.125
163 pnkfelix 1.1.2.114 /** returns the root backing <code>i</code>. Instrs not
164 pnkfelix 1.1.2.114 present in BackedInstrs are their own root.
165 pnkfelix 1.1.2.114 */
166 pnkfelix 1.1.2.114 protected Instr getBack(Instr i) {
167 pnkfelix 1.1.2.114 if (!backedInstrs.keySet().contains(i))
168 pnkfelix 1.1.2.114 return i;
169 pnkfelix 1.1.2.114
170 pnkfelix 1.1.2.114 Instr b = (Instr) backedInstrs.get(i);
171 pnkfelix 1.1.2.114 while(backedInstrs.keySet().contains(b)) {
172 pnkfelix 1.1.2.114 b = (Instr) backedInstrs.get(b);
173 pnkfelix 1.1.2.114 }
174 pnkfelix 1.1.2.114 return b;
175 pnkfelix 1.1.2.114 }
176 pnkfelix 1.1.2.99
177 pnkfelix 1.1.2.23 /** Class for <code>RegAlloc</code> usage in loading registers.
178 pnkfelix 1.1.2.23
179 pnkfelix 1.1.2.23 Note that the constructors automagically put in the
180 pnkfelix 1.1.2.23 "appropriate" `d# and `s# operands.
181 pnkfelix 1.1.2.62
182 pnkfelix 1.1.2.23
183 pnkfelix 1.1.2.64 REP INVARIANT: SpillLoads have only one src Temp.
184 pnkfelix 1.1.2.66 */
185 pnkfelix 1.1.2.87 public static class SpillLoad extends InstrMEM {
186 pnkfelix 1.1.2.87 static SpillLoad makeLD(Instr i, String prefix,
187 pnkfelix 1.1.2.87 Temp dst, Temp src) {
188 pnkfelix 1.1.2.91 return new SpillLoad(i,prefix+" "+dst+" "+src,dst,src);
189 pnkfelix 1.1.2.87 }
190 pnkfelix 1.1.2.87
191 pnkfelix 1.1.2.87 static SpillLoad makeLD(Instr i, String prefix,
192 pnkfelix 1.1.2.87 Collection dsts, Temp src) {
193 pnkfelix 1.1.2.91 return new SpillLoad(i,prefix+" "+dsts+" "+src, dsts, src);
194 pnkfelix 1.1.2.87 }
195 pnkfelix 1.1.2.87
196 pnkfelix 1.1.2.94 private StackOffsetTemp stackOffset;
197 pnkfelix 1.1.2.94
198 pnkfelix 1.1.2.87 SpillLoad(InstrFactory inf, Instr i, String assem,
199 pnkfelix 1.1.2.87 Temp dst, Temp src) {
200 pnkfelix 1.1.2.87 super(inf, i, assem,
201 pnkfelix 1.1.2.16 new Temp[]{dst}, new Temp[]{src});
202 pnkfelix 1.1.2.16 }
203 pnkfelix 1.1.2.64 SpillLoad(Instr i, String assem, Temp dst, Temp src) {
204 pnkfelix 1.1.2.49 this(i.getFactory(), i, assem, dst, src);
205 pnkfelix 1.1.2.23 }
206 pnkfelix 1.1.2.40
207 pnkfelix 1.1.2.49 // Note that the order that 'dsts' will appear in is the order
208 pnkfelix 1.1.2.49 // that its iterator returns the Temps in.
209 pnkfelix 1.1.2.64 SpillLoad(InstrFactory inf, Instr i, String assem, Collection dsts, Temp src) {
210 pnkfelix 1.1.2.87 super(inf, i, assem,
211 pnkfelix 1.1.2.87 (Temp[])dsts.toArray(new Temp[dsts.size()]),
212 pnkfelix 1.1.2.23 new Temp[]{src});
213 pnkfelix 1.1.2.14 }
214 pnkfelix 1.1.2.64 SpillLoad(Instr i, String assem, Collection dsts, Temp src) {
215 pnkfelix 1.1.2.49 this(i.getFactory(), i, assem, dsts, src);
216 pnkfelix 1.1.2.49 }
217 pnkfelix 1.1.2.23
218 pnkfelix 1.1.2.14 }
219 pnkfelix 1.1.2.14
220 pnkfelix 1.1.2.23 /** Class for <code>RegAlloc</code> usage in spilling registers.
221 pnkfelix 1.1.2.23
222 pnkfelix 1.1.2.23 Note that the constructors automagically put in the
223 pnkfelix 1.1.2.23 "appropriate" `d# and `s# operands.
224 pnkfelix 1.1.2.23
225 pnkfelix 1.1.2.64 REP INVARIANT: SpillStores have only one dst Temp.
226 pnkfelix 1.1.2.62
227 pnkfelix 1.1.2.23 */
228 pnkfelix 1.1.2.87 public static class SpillStore extends InstrMEM {
229 pnkfelix 1.1.2.87 static SpillStore makeST(Instr i, String prefix,
230 pnkfelix 1.1.2.87 Temp dst, Temp src) {
231 pnkfelix 1.1.2.94 SpillStore ss = new SpillStore(i,prefix+" "+dst+" "+src,dst,src);
232 pnkfelix 1.1.2.94 return ss;
233 pnkfelix 1.1.2.87 }
234 pnkfelix 1.1.2.87
235 pnkfelix 1.1.2.87 static SpillStore makeST(Instr i, String prefix,
236 pnkfelix 1.1.2.87 Temp dst, Collection srcs) {
237 pnkfelix 1.1.2.94 SpillStore ss = new SpillStore(i,prefix+" "+dst+" "+srcs,dst,srcs);
238 pnkfelix 1.1.2.94 return ss;
239 pnkfelix 1.1.2.87 }
240 pnkfelix 1.1.2.87
241 pnkfelix 1.1.2.94 private StackOffsetTemp stackOffset;
242 pnkfelix 1.1.2.94
243 pnkfelix 1.1.2.94 private SpillStore(Instr i, String assem, Temp dst, Temp src) {
244 pnkfelix 1.1.2.49 this(i.getFactory(), i, assem, dst, src);
245 pnkfelix 1.1.2.49 }
246 pnkfelix 1.1.2.49
247 pnkfelix 1.1.2.94 private SpillStore(InstrFactory inf, HCodeElement hce,
248 pnkfelix 1.1.2.14 String assem, Temp dst, Temp src) {
249 pnkfelix 1.1.2.94 this(inf, hce, assem, dst, Collections.singleton(src));
250 pnkfelix 1.1.2.16 }
251 pnkfelix 1.1.2.40
252 pnkfelix 1.1.2.49 // Note that the order that 'dsts' will appear in is the order
253 pnkfelix 1.1.2.49 // that its iterator returns the Temps in.
254 pnkfelix 1.1.2.94 private SpillStore(InstrFactory inf, HCodeElement hce,
255 pnkfelix 1.1.2.49 String assem, Temp dst, Collection srcs) {
256 pnkfelix 1.1.2.87 super(inf, hce, assem,new Temp[]{dst},
257 pnkfelix 1.1.2.23 (Temp[])srcs.toArray(new Temp[srcs.size()]));
258 pnkfelix 1.1.2.14 }
259 pnkfelix 1.1.2.49
260 pnkfelix 1.1.2.94 private SpillStore(Instr i, String assem, Temp dst, Collection srcs) {
261 pnkfelix 1.1.2.49 this(i.getFactory(), i, assem, dst, srcs);
262 pnkfelix 1.1.2.49 }
263 pnkfelix 1.1.2.92
264 pnkfelix 1.1.2.94
265 cananian 1.3.2.3 public Collection<Temp> defC() {
266 cananian 1.3.2.3 Collection<Temp> defs = super.defC();
267 pnkfelix 1.1.2.94 return defs;
268 pnkfelix 1.1.2.94 }
269 pnkfelix 1.1.2.94
270 pnkfelix 1.1.2.14 }
271 pnkfelix 1.1.2.125
272 pnkfelix 1.1.2.125 protected class SpillProxy extends Instr {
273 pnkfelix 1.1.2.125 Instr instr;
274 pnkfelix 1.1.2.125 Temp tmp;
275 pnkfelix 1.1.2.125 SpillProxy(Instr def, Temp t) {
276 pnkfelix 1.1.2.125 super(def.getFactory(), def, "SPILL "+t,
277 pnkfelix 1.1.2.125 new Temp[]{ }, new Temp[]{ t },
278 cananian 1.7 true, (List<Label>) Collections.EMPTY_LIST);
279 pnkfelix 1.1.2.125 instr = def;
280 pnkfelix 1.1.2.125 tmp = t;
281 pnkfelix 1.1.2.125 }
282 pnkfelix 1.1.2.125 public Instr rename(InstrFactory inf,
283 pnkfelix 1.1.2.125 TempMap defMap, TempMap useMap) {
284 pnkfelix 1.1.2.125 Instr i = new SpillProxy(instr,
285 pnkfelix 1.1.2.125 // instr.rename(inf, defMap, useMap),
286 pnkfelix 1.1.2.125 useMap.tempMap(tmp));
287 pnkfelix 1.1.2.125 return i;
288 pnkfelix 1.1.2.125 }
289 pnkfelix 1.1.2.125
290 pnkfelix 1.1.2.125 }
291 pnkfelix 1.1.2.125
292 pnkfelix 1.1.2.125 protected class RestoreProxy extends Instr {
293 pnkfelix 1.1.2.125 Instr instr;
294 pnkfelix 1.1.2.125 Temp tmp;
295 pnkfelix 1.1.2.125 RestoreProxy(Instr use, Temp t) {
296 pnkfelix 1.1.2.125 super(use.getFactory(), use, "RESTORE "+t,
297 pnkfelix 1.1.2.125 new Temp[]{ t }, new Temp[]{},
298 cananian 1.7 true, (List<Label>) Collections.EMPTY_LIST);
299 pnkfelix 1.1.2.125 instr = use;
300 pnkfelix 1.1.2.125 tmp = t;
301 pnkfelix 1.1.2.125 }
302 pnkfelix 1.1.2.125 public Instr rename(InstrFactory inf,
303 pnkfelix 1.1.2.125 TempMap defMap, TempMap useMap){
304 pnkfelix 1.1.2.125 Instr i = new RestoreProxy(instr,
305 pnkfelix 1.1.2.125 //instr.rename(inf,defMap,useMap),
306 pnkfelix 1.1.2.125 defMap.tempMap(tmp));
307 pnkfelix 1.1.2.125 return i;
308 pnkfelix 1.1.2.125 }
309 pnkfelix 1.1.2.125 }
310 pnkfelix 1.1.2.125
311 pnkfelix 1.1.2.125
312 pnkfelix 1.1.2.125 /** Replaces the proxy instructions with symbolic loads and
313 pnkfelix 1.1.2.125 stores. (The proxys don't have register assignment info
314 pnkfelix 1.1.2.125 internally, the new instructions do.)
315 pnkfelix 1.1.2.125 */
316 pnkfelix 1.1.2.125 protected void fixupSpillCode() {
317 pnkfelix 1.1.2.125 for(Iterator is=code.getElementsI(); is.hasNext(); ) {
318 pnkfelix 1.1.2.125 Instr i = (Instr) is.next();
319 pnkfelix 1.1.2.125 if (i instanceof SpillProxy) {
320 pnkfelix 1.1.2.125 SpillProxy sp = (SpillProxy) i;
321 pnkfelix 1.1.2.125 Instr spillInstr =
322 pnkfelix 1.1.2.125 SpillStore.makeST(sp.instr, "FSK-ST", sp.tmp,
323 pnkfelix 1.1.2.125 code.getRegisters(sp,sp.tmp));
324 pnkfelix 1.1.2.125 replace(sp, spillInstr);
325 pnkfelix 1.1.2.125 back(spillInstr, sp.instr);
326 pnkfelix 1.1.2.125 } else if (i instanceof RestoreProxy) {
327 pnkfelix 1.1.2.125 RestoreProxy rp = (RestoreProxy) i;
328 pnkfelix 1.1.2.125 Instr loadInstr =
329 pnkfelix 1.1.2.125 SpillLoad.makeLD(rp.instr, "FSK-LD",
330 pnkfelix 1.1.2.125 code.getRegisters(rp,rp.tmp),
331 pnkfelix 1.1.2.125 rp.tmp);
332 pnkfelix 1.1.2.125 replace(rp, loadInstr);
333 pnkfelix 1.1.2.125 }
334 pnkfelix 1.1.2.125 }
335 pnkfelix 1.1.2.125 }
336 pnkfelix 1.1.2.125
337 pnkfelix 1.1.2.125
338 pnkfelix 1.1.2.125
339 pnkfelix 1.1.2.14
340 pnkfelix 1.1.2.75 /** Creates a <code>RegAlloc</code>. <code>RegAlloc</code>s are
341 pnkfelix 1.1.2.75 each associated with a unique <code>Code</code> which they are
342 pnkfelix 1.1.2.75 responsible for performing register allocation and assignment
343 pnkfelix 1.1.2.75 for.
344 pnkfelix 1.1.2.125 <BR> <B>modifies:</B> `this.{frame, code, bbFact}'
345 pnkfelix 1.1.2.125 <BR> <B>effects:</B>
346 pnkfelix 1.1.2.125 sets the frame, code in accordance with the code argument,
347 pnkfelix 1.1.2.125 and computesBasicBlocks.
348 pnkfelix 1.1.2.1 */
349 pnkfelix 1.1.2.12 protected RegAlloc(Code code) {
350 pnkfelix 1.1.2.12 this.frame = code.getFrame();
351 pnkfelix 1.1.2.1 this.code = code;
352 pnkfelix 1.1.2.125 this.bbFact = computeBasicBlocks();
353 pnkfelix 1.1.2.1 }
354 pnkfelix 1.1.2.49
355 pnkfelix 1.1.2.102 /** returns a <code>Derivation</code> for analyses to use on the
356 pnkfelix 1.1.2.102 register-allocated code. This allows for register allocation
357 pnkfelix 1.1.2.102 routines to make transformations on the code and still allow
358 pnkfelix 1.1.2.102 Derivation information to propagate to later analyses.
359 pnkfelix 1.1.2.101 <BR> <B>requires:</B>
360 pnkfelix 1.1.2.101 <code>this.generateRegAssignment()</code> has been
361 pnkfelix 1.1.2.101 called.
362 pnkfelix 1.1.2.101 */
363 pnkfelix 1.1.2.102 protected abstract Derivation getDerivation();
364 pnkfelix 1.1.2.101
365 pnkfelix 1.1.2.106 /** Computes <code>BasicBlock</code>s for the <code>Code</code>
366 pnkfelix 1.1.2.106 associated with <code>this</code>.
367 pnkfelix 1.1.2.125 <BR> <B>requires:</B> `this.code' has been set
368 pnkfelix 1.1.2.125 @return a basic-block factory for `this.code',
369 pnkfelix 1.1.2.125 using the default control-flow view of the code.
370 pnkfelix 1.1.2.106 */
371 pnkfelix 1.1.2.125 protected BasicBlock.Factory computeBasicBlocks() {
372 pnkfelix 1.1.2.125 return new BasicBlock.Factory
373 pnkfelix 1.1.2.125 (code, code.getInstrFactory().getGrapherFor(InstrGroup.AGGREGATE));
374 pnkfelix 1.1.2.85 }
375 pnkfelix 1.1.2.127
376 pnkfelix 1.1.2.127 /** Iterates over a view of the code which skips over instrs that
377 pnkfelix 1.1.2.127 are not in our basic block set. This is a useful notion
378 pnkfelix 1.1.2.127 because many of the datastructures used for register
379 pnkfelix 1.1.2.127 allocation barf if given an instruction that wasn't in a basic
380 pnkfelix 1.1.2.127 block (such as a element in a data-table). Note that this
381 pnkfelix 1.1.2.127 method uses the basic-block structure as the basis for its
382 pnkfelix 1.1.2.127 data, so if computeBasicBlocks() is overriden, the behavior of
383 pnkfelix 1.1.2.127 the iteration may change.
384 pnkfelix 1.1.2.127
385 pnkfelix 1.1.2.127 <p> Note also that if the compiler emits dead code, the instrs
386 pnkfelix 1.1.2.127 in such code will not ever be yielded from this, but MAY
387 pnkfelix 1.1.2.127 indeed be yielded from code.getElementsI(). Since FLEX seems
388 pnkfelix 1.1.2.127 to be emitting unreachable code in certain cases, an allocator
389 pnkfelix 1.1.2.127 may want still provide some bogus assignment so that we don't
390 pnkfelix 1.1.2.127 die in an assertion failure in this module. Or perhaps one
391 pnkfelix 1.1.2.127 would prefer to fix the earlier part that is generating
392 pnkfelix 1.1.2.127 unreachable code. C:P
393 pnkfelix 1.1.2.127
394 pnkfelix 1.1.2.127 */
395 pnkfelix 1.1.2.127 protected Iterator reachableInstrs() {
396 pnkfelix 1.1.2.127 final Iterator blocks = bbFact.blockSet().iterator();
397 pnkfelix 1.1.2.127 return new CombineIterator(new UnmodifiableIterator() {
398 pnkfelix 1.1.2.127 public Object next() {
399 pnkfelix 1.1.2.127 return ((BasicBlock)blocks.next()).statements().iterator();}
400 pnkfelix 1.1.2.127 public boolean hasNext() {
401 pnkfelix 1.1.2.127 return blocks.hasNext();}
402 pnkfelix 1.1.2.127 });
403 pnkfelix 1.1.2.127 }
404 pnkfelix 1.1.2.127
405 pnkfelix 1.1.2.1
406 pnkfelix 1.1.2.3 /** Assigns registers in the code for <code>this</code>.
407 pnkfelix 1.1.2.1
408 pnkfelix 1.1.2.3 <BR> <B>effects:</B> Partially or completely allocates
409 pnkfelix 1.1.2.3 registers for the values defined and used in the code for
410 pnkfelix 1.1.2.3 <code>this</code>. Values will be preserved in the code;
411 pnkfelix 1.1.2.3 any live value will be stored before its assigned
412 pnkfelix 1.1.2.18 register is overwritten.
413 pnkfelix 1.1.2.18 <BR> Loads and Stores in general
414 pnkfelix 1.1.2.64 are added in the form of <code>SpillLoad</code>s and
415 pnkfelix 1.1.2.64 <code>SpillStore</code>s; the main <code>RegAlloc</code>
416 pnkfelix 1.1.2.85 class will use <code>resolveOutstandingTemps()</code>
417 pnkfelix 1.1.2.17 to replace these "fake" loads and stores with frame
418 pnkfelix 1.1.2.17 specified Memory instructions.
419 pnkfelix 1.1.2.17
420 pnkfelix 1.1.2.85 @see RegAlloc#resolveOutstandingTemps()
421 pnkfelix 1.1.2.3 */
422 pnkfelix 1.1.2.65 protected abstract void generateRegAssignment();
423 pnkfelix 1.1.2.1
424 pnkfelix 1.1.2.109 public static HCodeFactory codeFactory(final HCodeFactory pFact,
425 pnkfelix 1.1.2.109 final Frame frame,
426 pnkfelix 1.1.2.109 final RegAlloc.Factory raFact) {
427 pnkfelix 1.1.2.109 return (frame.getGCInfo() == null) ?
428 pnkfelix 1.1.2.109 concreteSpillFactory
429 pnkfelix 1.1.2.109 (abstractSpillFactory(pFact, frame, raFact), frame) :
430 pnkfelix 1.1.2.109 concreteSpillFactory
431 pnkfelix 1.1.2.109 (frame.getGCInfo().codeFactory
432 pnkfelix 1.1.2.109 (abstractSpillFactory(pFact, frame, raFact), frame), frame);
433 pnkfelix 1.1.2.109 }
434 pnkfelix 1.1.2.109
435 pnkfelix 1.1.2.3 /** Creates a register-allocating <code>HCodeFactory</code> for
436 pnkfelix 1.1.2.3 "instr" form.
437 pnkfelix 1.1.2.3 <BR> <B>requires:</B> <code>parentFactory</code> produces code
438 pnkfelix 1.1.2.3 in a derivative of "instr" form.
439 pnkfelix 1.1.2.3 <BR> <B>effects:</B> Produces an <code>HCodeFactory</code>
440 pnkfelix 1.1.2.3 which allocates registers in the code produced by
441 pnkfelix 1.1.2.3 <code>parentFactory</code> using the machine properties
442 pnkfelix 1.1.2.3 specified in <code>frame</code>.
443 pnkfelix 1.1.2.3 */
444 pnkfelix 1.1.2.3 public static HCodeFactory codeFactory(final HCodeFactory parentFactory,
445 pnkfelix 1.1.2.3 final Frame frame) {
446 kkz 1.1.2.89 return (frame.getGCInfo() == null) ?
447 kkz 1.1.2.89 concreteSpillFactory
448 kkz 1.1.2.89 (abstractSpillFactory(parentFactory, frame), frame) :
449 kkz 1.1.2.89 concreteSpillFactory
450 kkz 1.1.2.89 (frame.getGCInfo().codeFactory
451 kkz 1.1.2.89 (abstractSpillFactory(parentFactory, frame), frame), frame);
452 pnkfelix 1.1.2.1 }
453 pnkfelix 1.1.2.62
454 pnkfelix 1.1.2.96 /** <code>IntermediateCode</code> is a code which has been
455 pnkfelix 1.1.2.66 register allocated but the architecture-specific spill
456 pnkfelix 1.1.2.96 instructions and method prologue/epilogue have not been
457 pnkfelix 1.1.2.96 inserted yet. Stack Offsets have been determined and are
458 pnkfelix 1.1.2.96 stored in the spill code instructions, but the output needs to
459 pnkfelix 1.1.2.96 be passed through <code>RegAlloc.concreteSpillFactory()</code>
460 pnkfelix 1.1.2.96 before it will be executable.
461 pnkfelix 1.1.2.66 @see RegAlloc#abstractSpillFactory
462 pnkfelix 1.1.2.66 @see RegAlloc#concreteSpillFactory
463 pnkfelix 1.1.2.66 */
464 pnkfelix 1.1.2.96 public static interface IntermediateCode {
465 pnkfelix 1.1.2.96 Set usedRegisterTemps();
466 pnkfelix 1.1.2.96 int numberOfLocals();
467 pnkfelix 1.1.2.96 TempLocator getTempLocator();
468 pnkfelix 1.1.2.96 }
469 pnkfelix 1.1.2.96
470 pnkfelix 1.1.2.96 /** IntermediateCodeFactory is an HCodeFactory that is guaranteed
471 pnkfelix 1.1.2.96 to produce <code>IntermediateCode</code>s. If the Java
472 pnkfelix 1.1.2.96 langaguage supported covariant return types, we would be able
473 pnkfelix 1.1.2.96 to enforce this constraint in the lanuage, but for now we are
474 pnkfelix 1.1.2.96 forced to rely on enforcing the constraint through
475 pnkfelix 1.1.2.96 specification alone. FSK is just keeping the interface around
476 pnkfelix 1.1.2.96 because its make things confusing to go and remove all of the
477 pnkfelix 1.1.2.96 references to IntermediateCodeFactory from Karen's code.
478 pnkfelix 1.1.2.96 */
479 pnkfelix 1.1.2.96 public static interface IntermediateCodeFactory
480 pnkfelix 1.1.2.96 extends HCodeFactory {
481 pnkfelix 1.1.2.96 /** The <code>HCode</code>s returned by this method are
482 pnkfelix 1.1.2.96 guaranteed to implement the <code>IntermediateCode</code>
483 pnkfelix 1.1.2.96 interface.
484 pnkfelix 1.1.2.96 */
485 pnkfelix 1.1.2.96 HCode convert(HMethod m);
486 pnkfelix 1.1.2.62 }
487 pnkfelix 1.1.2.62
488 pnkfelix 1.1.2.98 /** Produces an <code>IntermediateCodeFactory</code> which can be
489 pnkfelix 1.1.2.97 used to extract Derivation information about code it
490 pnkfelix 1.1.2.97 generates.
491 pnkfelix 1.1.2.64 <BR> <B>requires:</B> <code>parentFactory</code> produces code
492 pnkfelix 1.1.2.64 in a derivative of "instr" form.
493 pnkfelix 1.1.2.64 <BR> <B>effects:</B> Produces an
494 pnkfelix 1.1.2.97 <code>IntermediateCodeFactory</code> which allocates
495 pnkfelix 1.1.2.64 registers in the code produced by
496 pnkfelix 1.1.2.96 <code>parentFactory</code> using the machine properties
497 pnkfelix 1.1.2.97 specified in <code>frame</code>.
498 pnkfelix 1.1.2.96 Spilled temporarys are assigned a stack offset but the
499 pnkfelix 1.1.2.96 actual code does not have the concrete load and store
500 pnkfelix 1.1.2.96 instructions necessary for the spilling. In addition,
501 pnkfelix 1.1.2.96 the architecture specific method prologue and epilogue
502 pnkfelix 1.1.2.96 instructions have not been inserted either. The
503 pnkfelix 1.1.2.97 <code>IntermediateCodeFactory</code> returned can be
504 pnkfelix 1.1.2.97 passed to <code>concreteSpillFactory()</code> to produce
505 pnkfelix 1.1.2.97 a code factory suitable for generating runnable assembly
506 pnkfelix 1.1.2.97 code.
507 pnkfelix 1.1.2.64 */
508 pnkfelix 1.1.2.96 public static IntermediateCodeFactory
509 pnkfelix 1.1.2.88 abstractSpillFactory(final HCodeFactory parent,
510 pnkfelix 1.1.2.88 final Frame frame) {
511 pnkfelix 1.1.2.111 return abstractSpillFactory(parent, frame,
512 pnkfelix 1.1.2.120 false?LOCAL:GLOBAL);
513 pnkfelix 1.1.2.109 }
514 pnkfelix 1.1.2.115 public static final Factory GLOBAL = GraphColoringRegAlloc.FACTORY;
515 pnkfelix 1.1.2.129 // public static final Factory GLOBAL = AppelRegAlloc.FACTORY;
516 pnkfelix 1.1.2.115 public static final Factory LOCAL = LocalCffRegAlloc.FACTORY;
517 pnkfelix 1.1.2.115
518 pnkfelix 1.1.2.119 static class MyCode extends Code
519 pnkfelix 1.1.2.119 implements IntermediateCode {
520 pnkfelix 1.1.2.119 Code mycode;
521 pnkfelix 1.1.2.119 int numLocals; TempLocator tl; Set usedRegs;
522 pnkfelix 1.1.2.119 MyCode(Code code, Instr i,
523 pnkfelix 1.1.2.119 Derivation d, String codeName,
524 pnkfelix 1.1.2.119 int numLocals, TempLocator tl, Set usedRegs) {
525 pnkfelix 1.1.2.119 super(code, i, d, codeName);
526 pnkfelix 1.1.2.119 mycode = code;
527 pnkfelix 1.1.2.119 this.numLocals = numLocals;
528 pnkfelix 1.1.2.119 this.tl = tl;
529 pnkfelix 1.1.2.119 this.usedRegs = usedRegs;
530 pnkfelix 1.1.2.119 }
531 pnkfelix 1.1.2.119 public String getName() { return mycode.getName(); }
532 pnkfelix 1.1.2.119 public List getRegisters(Instr i, Temp t) {
533 pnkfelix 1.1.2.119 return mycode.getRegisters(i,t);
534 pnkfelix 1.1.2.119 }
535 pnkfelix 1.1.2.119 public String getRegisterName(Instr i, Temp t, String s) {
536 pnkfelix 1.1.2.119 return mycode.getRegisterName(i,t,s);
537 pnkfelix 1.1.2.119 }
538 pnkfelix 1.1.2.119 public void assignRegister(Instr i, Temp pReg, List regs) {
539 pnkfelix 1.1.2.119 mycode.assignRegister(i, pReg, regs);
540 pnkfelix 1.1.2.119 }
541 pnkfelix 1.1.2.119 public boolean registerAssigned(Instr i, Temp t) {
542 pnkfelix 1.1.2.119 return mycode.registerAssigned(i, t);
543 pnkfelix 1.1.2.119 }
544 pnkfelix 1.1.2.119 public void removeAssignment(Instr i, Temp t) {
545 pnkfelix 1.1.2.119 mycode.removeAssignment(i, t);
546 pnkfelix 1.1.2.119 }
547 pnkfelix 1.1.2.119 public int numberOfLocals() { return numLocals; }
548 pnkfelix 1.1.2.119 public TempLocator getTempLocator() { return tl; }
549 pnkfelix 1.1.2.119 public Set usedRegisterTemps() { return usedRegs; }
550 pnkfelix 1.1.2.119 }
551 pnkfelix 1.1.2.119
552 pnkfelix 1.1.2.109 public static IntermediateCodeFactory
553 pnkfelix 1.1.2.109 abstractSpillFactory(final HCodeFactory parent,
554 pnkfelix 1.1.2.109 final Frame frame,
555 pnkfelix 1.1.2.109 final RegAlloc.Factory raFact) {
556 pnkfelix 1.1.2.64 return new IntermediateCodeFactory() {
557 pnkfelix 1.1.2.96 HCodeFactory p = parent;
558 pnkfelix 1.1.2.96
559 pnkfelix 1.1.2.96 public HCode convert(HMethod m) {
560 pnkfelix 1.1.2.96 Code preAllocCode = (Code) p.convert(m);
561 pnkfelix 1.1.2.96 if (preAllocCode == null) {
562 pnkfelix 1.1.2.96 return null;
563 pnkfelix 1.1.2.65 }
564 pnkfelix 1.1.2.65
565 pnkfelix 1.1.2.109 RegAlloc globalCode;
566 pnkfelix 1.1.2.65
567 pnkfelix 1.1.2.104 if (TIME) System.out.print("C");
568 pnkfelix 1.1.2.109 globalCode = raFact.makeRegAlloc(preAllocCode);
569 pnkfelix 1.1.2.104 if (TIME) System.out.print("G");
570 pnkfelix 1.1.2.65 globalCode.generateRegAssignment();
571 pnkfelix 1.1.2.104 if (TIME) System.out.print("R");
572 pnkfelix 1.1.2.96 List triple = globalCode.resolveOutstandingTemps();
573 pnkfelix 1.1.2.104 if (TIME) System.out.print("#");
574 pnkfelix 1.1.2.104
575 pnkfelix 1.1.2.96 final Instr instr = (Instr) triple.get(0);
576 pnkfelix 1.1.2.88 final RegFileInfo.TempLocator tl =
577 pnkfelix 1.1.2.96 (RegFileInfo.TempLocator) triple.get(1);
578 pnkfelix 1.1.2.68 final Code mycode = globalCode.code;
579 pnkfelix 1.1.2.96 final int numLocals = ((Integer)triple.get(2)).intValue();
580 pnkfelix 1.1.2.96 final Set usedRegs = globalCode.computeUsedRegs(instr);
581 cananian 1.3.2.1 assert mycode != null;
582 pnkfelix 1.1.2.96
583 pnkfelix 1.1.2.68
584 pnkfelix 1.1.2.96 return new MyCode(mycode, instr,
585 pnkfelix 1.1.2.119 globalCode.getDerivation(),
586 pnkfelix 1.1.2.119 mycode.getName(), numLocals, tl, usedRegs);
587 pnkfelix 1.1.2.65 }
588 pnkfelix 1.1.2.65
589 pnkfelix 1.1.2.64 public String getCodeName() { return p.getCodeName(); }
590 pnkfelix 1.1.2.64 public void clear(HMethod m) { p.clear(m); }
591 pnkfelix 1.1.2.64 };
592 pnkfelix 1.1.2.62 }
593 pnkfelix 1.1.2.93
594 pnkfelix 1.1.2.93 protected boolean allRegs(Collection c) {
595 cananian 1.9 for (Object tO : c) {
596 cananian 1.9 Temp t = (Temp) tO;
597 pnkfelix 1.1.2.93 if (!isRegister(t)) {
598 pnkfelix 1.1.2.93 return false;
599 pnkfelix 1.1.2.93 }
600 pnkfelix 1.1.2.93 }
601 pnkfelix 1.1.2.93 return true;
602 pnkfelix 1.1.2.93 }
603 pnkfelix 1.1.2.93
604 pnkfelix 1.1.2.62
605 pnkfelix 1.1.2.64 /** Produces an <code>HCodeFactory</code> which will transform the
606 pnkfelix 1.1.2.64 abstract spills into concrete spills.
607 pnkfelix 1.1.2.64 <BR> <B>effects:</B> Produces an <code>HCodeFactory</code>
608 pnkfelix 1.1.2.64 which takes the codes produced by <code>parent</code>,
609 pnkfelix 1.1.2.66 finds the code spilling abstract stack-offset Temps
610 pnkfelix 1.1.2.66 (generated by <code>parent</code>) and replaces it with
611 pnkfelix 1.1.2.66 concrete, architecture-dependant spill code.
612 pnkfelix 1.1.2.64 */
613 pnkfelix 1.1.2.66 public static HCodeFactory concreteSpillFactory(final IntermediateCodeFactory parent,
614 pnkfelix 1.1.2.66 final Frame frame) {
615 pnkfelix 1.1.2.66 // Not sure how to handle multiple Temp references in one
616 pnkfelix 1.1.2.66 // InstrMEM...for now will assume that there is only one
617 pnkfelix 1.1.2.66 // memory references per InstrMEM...
618 pnkfelix 1.1.2.66 class InstrReplacer extends InstrVisitor {
619 pnkfelix 1.1.2.93 private boolean allRegs(Collection c) {
620 cananian 1.9 for (Object tO : c) {
621 cananian 1.9 Temp t = (Temp) tO;
622 pnkfelix 1.1.2.93 if (!frame.getRegFileInfo().isRegister(t)) {
623 pnkfelix 1.1.2.93 return false;
624 pnkfelix 1.1.2.93 }
625 pnkfelix 1.1.2.93 }
626 pnkfelix 1.1.2.93 return true;
627 pnkfelix 1.1.2.93 }
628 pnkfelix 1.1.2.93
629 pnkfelix 1.1.2.66 // Make these SMARTER: get rid of requirement that Loads
630 pnkfelix 1.1.2.66 // and Stores have only one references to memory (to
631 pnkfelix 1.1.2.66 // allow for StrongARMs ldm* instructions : starting doing
632 pnkfelix 1.1.2.66 // this, but I think TempFinder above relies on some parts
633 pnkfelix 1.1.2.66 // of it, at least when assigning offsets. Check over
634 pnkfelix 1.1.2.66 // this.
635 pnkfelix 1.1.2.66 private void visitStore(SpillStore m) {
636 pnkfelix 1.1.2.95 StackOffsetTemp def = m.stackOffset;
637 pnkfelix 1.1.2.94 List regs = Arrays.asList(m.use());
638 cananian 1.3.2.1 assert allRegs(regs);
639 pnkfelix 1.1.2.66 List instrs = frame.getInstrBuilder().
640 pnkfelix 1.1.2.93 makeStore(regs, def.offset, m);
641 pnkfelix 1.1.2.66 Instr.replaceInstrList(m, instrs);
642 pnkfelix 1.1.2.66 }
643 pnkfelix 1.1.2.66
644 pnkfelix 1.1.2.66 private void visitLoad(SpillLoad m) {
645 pnkfelix 1.1.2.95 StackOffsetTemp use = m.stackOffset;
646 pnkfelix 1.1.2.94 List regs = Arrays.asList(m.def());
647 cananian 1.3.2.1 assert allRegs(regs);
648 pnkfelix 1.1.2.66 List instrs = frame.getInstrBuilder().
649 pnkfelix 1.1.2.93 makeLoad(regs, use.offset, m);
650 pnkfelix 1.1.2.66 Instr.replaceInstrList(m, instrs);
651 pnkfelix 1.1.2.66 }
652 pnkfelix 1.1.2.66
653 pnkfelix 1.1.2.66 public void visit(Instr i) {
654 pnkfelix 1.1.2.66 // do nothing
655 pnkfelix 1.1.2.66 }
656 pnkfelix 1.1.2.66
657 pnkfelix 1.1.2.66 public void visit(InstrMEM i) {
658 pnkfelix 1.1.2.66 if (i instanceof SpillStore) {
659 pnkfelix 1.1.2.66 visitStore((SpillStore) i);
660 pnkfelix 1.1.2.66 } else if (i instanceof SpillLoad) {
661 pnkfelix 1.1.2.66 visitLoad((SpillLoad) i);
662 pnkfelix 1.1.2.66 }
663 pnkfelix 1.1.2.66 }
664 pnkfelix 1.1.2.66 }
665 pnkfelix 1.1.2.66
666 pnkfelix 1.1.2.66 return new HCodeFactory() {
667 pnkfelix 1.1.2.66 HCodeFactory p = parent;
668 pnkfelix 1.1.2.66 public HCode convert(HMethod m) {
669 pnkfelix 1.1.2.66 Code absCode = (Code) p.convert(m);
670 pnkfelix 1.1.2.66 if (absCode == null) {
671 pnkfelix 1.1.2.66 return null;
672 pnkfelix 1.1.2.66 }
673 pnkfelix 1.1.2.96
674 pnkfelix 1.1.2.96 int locals = ((IntermediateCode)absCode).numberOfLocals();
675 pnkfelix 1.1.2.96 Set usedRegs = ((IntermediateCode)absCode).usedRegisterTemps();
676 pnkfelix 1.1.2.96 Instr root = (Instr) absCode.getRootElement();
677 pnkfelix 1.1.2.96
678 pnkfelix 1.1.2.96 root = frame.getCodeGen().
679 pnkfelix 1.1.2.96 procFixup(absCode.getMethod(),root,locals,usedRegs);
680 pnkfelix 1.1.2.66
681 pnkfelix 1.1.2.66 InstrReplacer replace = new InstrReplacer();
682 pnkfelix 1.1.2.66
683 pnkfelix 1.1.2.66 Iterator instrs = absCode.getElementsI();
684 pnkfelix 1.1.2.66 while(instrs.hasNext()) {
685 pnkfelix 1.1.2.66 Instr i = (Instr) instrs.next();
686 pnkfelix 1.1.2.66 i.accept(replace);
687 pnkfelix 1.1.2.66 }
688 pnkfelix 1.1.2.66
689 pnkfelix 1.1.2.82 if (DEBUG) {
690 pnkfelix 1.1.2.82 instrs = absCode.getElementsI(); // debug check
691 pnkfelix 1.1.2.82 while(instrs.hasNext()) {
692 pnkfelix 1.1.2.82 Instr i = (Instr) instrs.next();
693 cananian 1.3.2.1 assert !(i instanceof SpillLoad) : "SpillLoad in i-list!";
694 cananian 1.3.2.1 assert !(i instanceof SpillStore) : "SpillStore in i-list! "
695 pnkfelix 1.1.2.107 /* + i.getPrev() + " " +
696 cananian 1.3.2.1 i + " " + i.getNext() */;
697 pnkfelix 1.1.2.82 }
698 pnkfelix 1.1.2.105 }
699 pnkfelix 1.1.2.82
700 pnkfelix 1.1.2.82
701 pnkfelix 1.1.2.66 return absCode;
702 pnkfelix 1.1.2.66 }
703 pnkfelix 1.1.2.66
704 pnkfelix 1.1.2.66 public String getCodeName() { return p.getCodeName(); }
705 pnkfelix 1.1.2.66 public void clear(HMethod m) { p.clear(m); }
706 pnkfelix 1.1.2.66 };
707 pnkfelix 1.1.2.62 }
708 pnkfelix 1.1.2.62
709 pnkfelix 1.1.2.6
710 pnkfelix 1.1.2.66 /** Temp Wrapper that incorporates a stack offset. */
711 pnkfelix 1.1.2.66 private static class StackOffsetTemp extends Temp
712 pnkfelix 1.1.2.66 implements RegFileInfo.StackOffsetLoc {
713 pnkfelix 1.1.2.66
714 pnkfelix 1.1.2.66 Temp wrappedTemp; // FSK: is this field needed?
715 pnkfelix 1.1.2.66 int offset;
716 pnkfelix 1.1.2.66 StackOffsetTemp(Temp t, int stackOffset) {
717 pnkfelix 1.1.2.66 super(t);
718 pnkfelix 1.1.2.66 wrappedTemp = t;
719 pnkfelix 1.1.2.66 offset = stackOffset;
720 pnkfelix 1.1.2.66 }
721 pnkfelix 1.1.2.66
722 pnkfelix 1.1.2.77 public int kind() {
723 pnkfelix 1.1.2.77 return RegFileInfo.StackOffsetLoc.KIND;
724 pnkfelix 1.1.2.76 }
725 pnkfelix 1.1.2.66 public int stackOffset() { return offset; }
726 pnkfelix 1.1.2.87
727 pnkfelix 1.1.2.87 public String name() {
728 pnkfelix 1.1.2.87 return "StkTmp"+offset+
729 pnkfelix 1.1.2.87 "("+wrappedTemp.toString()+")";
730 pnkfelix 1.1.2.87 }
731 pnkfelix 1.1.2.66 }
732 pnkfelix 1.1.2.66
733 pnkfelix 1.1.2.65 /** Transforms Temp references for <code>this</code> into appropriate offsets
734 pnkfelix 1.1.2.13 from the Stack Pointer in the Memory.
735 pnkfelix 1.1.2.65 <BR> <B>modifies:</B> this
736 pnkfelix 1.1.2.64 <BR> <B>effects:</B> Replaces the <code>SpillLoad</code> and
737 pnkfelix 1.1.2.64 <code>SpillStore</code>s with memory instructions for the
738 pnkfelix 1.1.2.96 appropriate <code>Frame</code>. Returns a three-elem list
739 pnkfelix 1.1.2.96 (instr, tempLocator, numLocals) :: Instr x TempLocator x Integer
740 pnkfelix 1.1.2.52 */
741 pnkfelix 1.1.2.82 protected final List resolveOutstandingTemps() {
742 pnkfelix 1.1.2.7 // This implementation is REALLY braindead. Fix to do a
743 pnkfelix 1.1.2.7 // smarter Graph-Coloring stack offset allocator
744 pnkfelix 1.1.2.65 Code in = code;
745 pnkfelix 1.1.2.83 final MultiMap tempXinstrToCommonLoc = new GenericMultiMap();
746 cananian 1.3.2.1 assert in != null : "Don't try to resolve Temps for null HCodes";
747 pnkfelix 1.1.2.7
748 pnkfelix 1.1.2.19 class TempFinder extends InstrVisitor {
749 pnkfelix 1.1.2.6 HashMap tempsToOffsets = new HashMap();
750 pnkfelix 1.1.2.87 int nextOffset = 0;
751 pnkfelix 1.1.2.6
752 pnkfelix 1.1.2.66 private void visitLoad(SpillLoad m) {
753 pnkfelix 1.1.2.14 // look for non-Register Temps in use, adding
754 pnkfelix 1.1.2.6 // them to internal map
755 pnkfelix 1.1.2.85 Temp use = m.use()[0];
756 pnkfelix 1.1.2.88 if(!isRegister(use)) {
757 pnkfelix 1.1.2.85 if (tempsToOffsets.get(use)==null){
758 pnkfelix 1.1.2.85 tempsToOffsets.put(use, new Integer(nextOffset));
759 pnkfelix 1.1.2.85 nextOffset += frame.getInstrBuilder().getSize(use);
760 pnkfelix 1.1.2.85 }
761 pnkfelix 1.1.2.85
762 pnkfelix 1.1.2.85 int off = ((Integer)tempsToOffsets.get(use)).intValue();
763 pnkfelix 1.1.2.85 // replace 'use' with StackOffsetTemp
764 pnkfelix 1.1.2.94 StackOffsetTemp stkOff =
765 pnkfelix 1.1.2.94 new StackOffsetTemp(use, off);
766 pnkfelix 1.1.2.85
767 pnkfelix 1.1.2.94 m.stackOffset = stkOff;
768 pnkfelix 1.1.2.94
769 pnkfelix 1.1.2.94 List dxi = Default.pair(use, m);
770 pnkfelix 1.1.2.85 tempXinstrToCommonLoc.add(dxi, stkOff);
771 pnkfelix 1.1.2.85
772 pnkfelix 1.1.2.6 }
773 pnkfelix 1.1.2.85 }
774 pnkfelix 1.1.2.85
775 pnkfelix 1.1.2.66 private void visitStore(SpillStore m) {
776 pnkfelix 1.1.2.14 // look for non-Register Temps in def, adding
777 pnkfelix 1.1.2.14 // them to internal map
778 pnkfelix 1.1.2.85 Temp def = m.def()[0];
779 pnkfelix 1.1.2.88 if(!isRegister(def)) {
780 pnkfelix 1.1.2.85 if (tempsToOffsets.get(def)==null){
781 pnkfelix 1.1.2.85 tempsToOffsets.put(def, new Integer(nextOffset));
782 pnkfelix 1.1.2.85 nextOffset += frame.getInstrBuilder().getSize(def);
783 pnkfelix 1.1.2.85 }
784 pnkfelix 1.1.2.85
785 pnkfelix 1.1.2.85 int off =
786 pnkfelix 1.1.2.85 ((Integer)tempsToOffsets.get(def)).intValue();
787 pnkfelix 1.1.2.85
788 pnkfelix 1.1.2.85 // replace 'def' with StackOffsetTemp
789 pnkfelix 1.1.2.85 StackOffsetTemp stkOff =
790 pnkfelix 1.1.2.85 new StackOffsetTemp(def, off);
791 pnkfelix 1.1.2.94
792 pnkfelix 1.1.2.94 m.stackOffset = stkOff;
793 pnkfelix 1.1.2.85
794 pnkfelix 1.1.2.94 List dxi = Default.pair(def, m);
795 pnkfelix 1.1.2.85 tempXinstrToCommonLoc.add(dxi, stkOff);
796 pnkfelix 1.1.2.85 } else {
797 pnkfelix 1.1.2.85 System.out.println("what kind of spill is this??? : "+m);
798 pnkfelix 1.1.2.14 }
799 pnkfelix 1.1.2.14 }
800 pnkfelix 1.1.2.9
801 pnkfelix 1.1.2.66 public void visit(Instr i) {
802 pnkfelix 1.1.2.83 // lookup CommonLocs for defs in 'i'
803 cananian 1.9 for (Object defO : i.defC()) {
804 cananian 1.9 Temp def = (Temp) defO;
805 pnkfelix 1.1.2.83 List dxi = Default.pair(def, i);
806 pnkfelix 1.1.2.88 if (isRegister(def)) {
807 pnkfelix 1.1.2.84 tempXinstrToCommonLoc.add(dxi, def);
808 pnkfelix 1.1.2.84 } else {
809 cananian 1.3.2.1 // assert checked.contains(i) : i+" not checked";
810 cananian 1.3.2.1 assert code.registerAssigned(i,def) : ("def:"+def+" not assigned in "+
811 pnkfelix 1.1.2.112 i.getID()+" : "+i);
812 pnkfelix 1.1.2.84 Collection regs = code.getRegisters(i, def);
813 pnkfelix 1.1.2.84 tempXinstrToCommonLoc.addAll(dxi, regs);
814 pnkfelix 1.1.2.84 }
815 pnkfelix 1.1.2.83 }
816 pnkfelix 1.1.2.66 }
817 pnkfelix 1.1.2.19
818 pnkfelix 1.1.2.66 public void visit(InstrMEM m) {
819 pnkfelix 1.1.2.64 if (m instanceof SpillStore)
820 pnkfelix 1.1.2.64 visitStore((SpillStore) m);
821 pnkfelix 1.1.2.64 else if (m instanceof SpillLoad) {
822 pnkfelix 1.1.2.64 visitLoad((SpillLoad) m);
823 pnkfelix 1.1.2.63 }
824 pnkfelix 1.1.2.6 }
825 pnkfelix 1.1.2.6 }
826 pnkfelix 1.1.2.6
827 pnkfelix 1.1.2.6 TempFinder tf = new TempFinder();
828 pnkfelix 1.1.2.6 Iterator instrs = in.getElementsI();
829 pnkfelix 1.1.2.6 while(instrs.hasNext()) {
830 pnkfelix 1.1.2.6 Instr i = (Instr) instrs.next();
831 pnkfelix 1.1.2.35 i.accept(tf);
832 pnkfelix 1.1.2.6 }
833 pnkfelix 1.1.2.96
834 pnkfelix 1.1.2.66 // now 'instrs' has spill instructions which reference Temps
835 pnkfelix 1.1.2.66 // that are associated with stack offsets
836 pnkfelix 1.1.2.58
837 pnkfelix 1.1.2.56 Instr instr = (Instr) in.getRootElement();
838 pnkfelix 1.1.2.56
839 pnkfelix 1.1.2.83 TempLocator tl = new TempLocator() {
840 pnkfelix 1.1.2.83 public Set locate(Temp t, Instr i) {
841 pnkfelix 1.1.2.83 return (Set)
842 pnkfelix 1.1.2.83 tempXinstrToCommonLoc.getValues(Default.pair(t,i));
843 pnkfelix 1.1.2.83 }
844 pnkfelix 1.1.2.83 };
845 pnkfelix 1.1.2.83
846 pnkfelix 1.1.2.96 return Arrays.asList
847 pnkfelix 1.1.2.96 (new Object[] { instr, tl, new Integer(tf.nextOffset) });
848 pnkfelix 1.1.2.6 }
849 pnkfelix 1.1.2.52
850 pnkfelix 1.1.2.56 private Set computeUsedRegs(Instr instrs) {
851 pnkfelix 1.1.2.56 Set s = new HashSet();
852 pnkfelix 1.1.2.56 for (Instr il = instrs; il!=null; il=il.getNext()) {
853 pnkfelix 1.1.2.64 if (il instanceof SpillStore) continue;
854 pnkfelix 1.1.2.56 Temp[] d = il.def();
855 pnkfelix 1.1.2.56 for (int i=0; i<d.length; i++) {
856 pnkfelix 1.1.2.88 if (isRegister(d[i])) {
857 pnkfelix 1.1.2.56 s.add(d[i]);
858 pnkfelix 1.1.2.56 } else {
859 pnkfelix 1.1.2.56 Collection c = code.getRegisters(il, d[i]);
860 pnkfelix 1.1.2.56 s.addAll(c);
861 pnkfelix 1.1.2.56 }
862 pnkfelix 1.1.2.56 }
863 pnkfelix 1.1.2.56 }
864 pnkfelix 1.1.2.56 return Collections.unmodifiableSet(s);
865 pnkfelix 1.1.2.56 }
866 pnkfelix 1.1.2.56
867 pnkfelix 1.1.2.90 /** Returns a List of the Component Temps that compose
868 pnkfelix 1.1.2.90 <code>t</code (Helper method).
869 pnkfelix 1.1.2.90 */
870 pnkfelix 1.1.2.90 public List expand(Temp t) {
871 pnkfelix 1.1.2.90 return frame.getRegFileInfo().expand(t);
872 pnkfelix 1.1.2.90 }
873 pnkfelix 1.1.2.90
874 pnkfelix 1.1.2.90 /** Checks if any element of <code>c</code> is a register (Helper
875 pnkfelix 1.1.2.90 method).
876 pnkfelix 1.1.2.90 <BR> <B>requires:</B> <code>c</code> is a
877 pnkfelix 1.1.2.90 <code>Collection</code> of <code>Temp</code>s.
878 pnkfelix 1.1.2.90 <BR> <B>effects:</B> If <code>c</code> contains any Register
879 pnkfelix 1.1.2.90 <code>Temp</code>s, returns true. Else returns false.
880 pnkfelix 1.1.2.90 */
881 pnkfelix 1.1.2.90 protected boolean hasRegister(Collection c) {
882 cananian 1.9 for (Object tO : c) {
883 cananian 1.9 Temp t = (Temp) tO;
884 pnkfelix 1.1.2.90 if (isRegister(t)) {
885 pnkfelix 1.1.2.90 return true;
886 pnkfelix 1.1.2.90 }
887 pnkfelix 1.1.2.90 }
888 pnkfelix 1.1.2.90 return false;
889 pnkfelix 1.1.2.90 }
890 pnkfelix 1.1.2.1
891 pnkfelix 1.1.2.3 /** Checks if <code>t</code> is a register (Helper method).
892 pnkfelix 1.1.2.3 <BR> <B>effects:</B> If <code>t</code> is a register for the
893 pnkfelix 1.1.2.3 <code>frame</code> associated with <code>this</code>,
894 pnkfelix 1.1.2.3 then returns true. Else returns false.
895 pnkfelix 1.1.2.3 */
896 pnkfelix 1.1.2.88 protected boolean isRegister(Temp t) {
897 cananian 1.1.2.37 return frame.getRegFileInfo().isRegister(t);
898 pnkfelix 1.1.2.1 }
899 pnkfelix 1.1.2.1
900 pnkfelix 1.1.2.1 /** Checks if <code>i</code> is last use of <code>reg</code> in
901 pnkfelix 1.1.2.48 the block of instructions listed in <code>iter</code>.
902 pnkfelix 1.1.2.1
903 pnkfelix 1.1.2.1 <BR> <B>requires:</B>
904 pnkfelix 1.1.2.9 <BR> 1. <code>i</code> is an element in <code>iter</code>
905 pnkfelix 1.1.2.9 <BR> 2. <code>iter</code> is an <code>Iterator</code> of
906 pnkfelix 1.1.2.9 a linear series of <code>Instr</code>s in the
907 pnkfelix 1.1.2.9 order that they will be executed.
908 pnkfelix 1.1.2.9 <BR> 3. <code>iter</code> is currently indexed at
909 pnkfelix 1.1.2.9 <code>i</code>
910 pnkfelix 1.1.2.9 <BR> <B>modifies:</B> <code>iter</code>
911 pnkfelix 1.1.2.9 <BR> <B>effects:</B>
912 pnkfelix 1.1.2.9 <BR> 1. Returns true if no instruction after
913 pnkfelix 1.1.2.9 <code>i</code> in <code>iter</code> uses
914 pnkfelix 1.1.2.9 <code>reg</code> before <code>reg</code> is
915 pnkfelix 1.1.2.9 redefined (<code>i</code> redefining
916 pnkfelix 1.1.2.9 <code>reg</code> is sufficient). Else returns
917 pnkfelix 1.1.2.9 false.
918 pnkfelix 1.1.2.9 <BR> 2. <code>iter</code> is left at an undetermined
919 pnkfelix 1.1.2.9 index.
920 pnkfelix 1.1.2.1 */
921 cananian 1.1.2.124 protected static boolean lastUse(Temp reg, UseDefable i, Iterator iter) {
922 cananian 1.1.2.124 UseDefable curr = i;
923 pnkfelix 1.1.2.1 boolean r = true;
924 pnkfelix 1.1.2.102 while (iter.hasNext() && ! curr.defC().contains(reg ) ) {
925 cananian 1.1.2.124 curr = (UseDefable) iter.next();
926 pnkfelix 1.1.2.102
927 pnkfelix 1.1.2.102 if (curr.useC().contains(reg)) {
928 pnkfelix 1.1.2.1 r = false;
929 pnkfelix 1.1.2.1 break;
930 pnkfelix 1.1.2.1 }
931 pnkfelix 1.1.2.1 }
932 pnkfelix 1.1.2.1 return r;
933 pnkfelix 1.1.2.3 }
934 pnkfelix 1.1.2.43
935 pnkfelix 1.1.2.43 }
936 pnkfelix 1.1.2.42
937 pnkfelix 1.1.2.43 /** Visits <code>BasicBlock</code>s of <code>Instr</code>s and
938 pnkfelix 1.1.2.64 uses the <code>SpillLoad</code> and <code>SpillStore</code>
939 pnkfelix 1.1.2.43 instructions to construct <code>Web</code>s for this method,
940 pnkfelix 1.1.2.43 These webs will need to be run through a merging dataflow
941 pnkfelix 1.1.2.43 analysis pass. This is effectively ReachingDefs, but I
942 pnkfelix 1.1.2.43 couldn't figure out how to easily adapt Whaley's version of
943 pnkfelix 1.1.2.43 ReachingDefs to my needs (note to FSK, either figure out
944 pnkfelix 1.1.2.43 Whaley's version or rewrite it in a form thats at least as
945 pnkfelix 1.1.2.43 useful as the LiveVars class) (also note to FSK: the current
946 pnkfelix 1.1.2.43 implementation is soft and flabby (space and time
947 pnkfelix 1.1.2.43 inefficient); look into really fixing up ReachingDefs and
948 pnkfelix 1.1.2.43 LiveVars to be fast AND easy-to-use)
949 pnkfelix 1.1.2.43 */
950 pnkfelix 1.1.2.43 class MakeWebsDumb extends ForwardDataFlowBasicBlockVisitor {
951 pnkfelix 1.1.2.43 /** struct class:
952 pnkfelix 1.1.2.43 'in' maps a Temp to a Web that is defined somewhere above
953 pnkfelix 1.1.2.43 this block.
954 pnkfelix 1.1.2.43 'out' maps a Temp to a Web that is defined somewhere above
955 pnkfelix 1.1.2.43 or within this block (note that the Web defined IN
956 pnkfelix 1.1.2.43 this block is a distinct object from the one defined
957 pnkfelix 1.1.2.43 ABOVE this block)
958 pnkfelix 1.1.2.43 'use' maps a Temp to the Set of Instrs that refer to it up
959 pnkfelix 1.1.2.43 until (and not including) that Temp's LAST definition
960 pnkfelix 1.1.2.43 in the block
961 pnkfelix 1.1.2.43 'def' maps a Temp to the Set of Instrs from that Temp's
962 pnkfelix 1.1.2.43 LAST definition in the basic block through all of its
963 pnkfelix 1.1.2.43 subsequent uses in the block
964 pnkfelix 1.1.2.42 */
965 pnkfelix 1.1.2.43 class WebInfo {
966 cananian 1.3.2.2 MultiMapFactory mmf = new MultiMapFactory();
967 pnkfelix 1.1.2.48
968 cananian 1.1.2.72 MultiMap in = new GenericMultiMap(); // Map[Temp, [Web] ]
969 cananian 1.1.2.72 MultiMap out = new GenericMultiMap(); // Map[Temp, [Web] ]
970 cananian 1.1.2.122 MultiMap use = new GenericMultiMap(new MySetFactory()); // Map[Temp, [Instr] ]
971 cananian 1.1.2.122 MultiMap def = new GenericMultiMap(new MySetFactory()); // Map[Temp, [Instr] ]
972 pnkfelix 1.1.2.48
973 cananian 1.8 class MySetFactory extends net.cscott.jutil.SetFactory {
974 pnkfelix 1.1.2.44 public Set makeSet(java.util.Collection c) {
975 pnkfelix 1.1.2.44 return new java.util.HashSet(c) {
976 pnkfelix 1.1.2.44 /** temporarily overriding this.toString() to
977 pnkfelix 1.1.2.44 give dense description of Set's contents. */
978 pnkfelix 1.1.2.44 public String toString() {
979 pnkfelix 1.1.2.44 StringBuffer str = new StringBuffer("{ ");
980 pnkfelix 1.1.2.44 Iterator iter = iterator();
981 pnkfelix 1.1.2.44 while(iter.hasNext()) {
982 pnkfelix 1.1.2.44 Instr i = (Instr) iter.next();
983 pnkfelix 1.1.2.44 str.append( i.getID() );
984 pnkfelix 1.1.2.44 if (iter.hasNext()) str.append(", ");
985 pnkfelix 1.1.2.44 }
986 pnkfelix 1.1.2.44 str.append(" }");
987 pnkfelix 1.1.2.44 return str.toString();
988 pnkfelix 1.1.2.44 }
989 pnkfelix 1.1.2.44 };
990 pnkfelix 1.1.2.44 }
991 pnkfelix 1.1.2.44 }
992 pnkfelix 1.1.2.44
993 pnkfelix 1.1.2.43
994 pnkfelix 1.1.2.64 void foundLoad(RegAlloc.SpillLoad instr) {
995 cananian 1.9 for (Object tO : instr.useC()) {
996 cananian 1.9 Temp t = (Temp) tO;
997 pnkfelix 1.1.2.49
998 cananian 1.3.2.1 assert t != null : "No nulls for Temps";
999 pnkfelix 1.1.2.43
1000 pnkfelix 1.1.2.45 if ((def.getValues(t)).isEmpty()) {
1001 pnkfelix 1.1.2.43 // if it uses a variable defined in
1002 pnkfelix 1.1.2.43 // another block, then add to USE
1003 pnkfelix 1.1.2.45 use.add(t, instr);
1004 pnkfelix 1.1.2.43 } else {
1005 pnkfelix 1.1.2.43 // put it in the DEF set; we'll move the DEF
1006 pnkfelix 1.1.2.43 // set into the USE set later if we have to.
1007 pnkfelix 1.1.2.45 def.add(t, instr);
1008 pnkfelix 1.1.2.42 }
1009 pnkfelix 1.1.2.42 }
1010 pnkfelix 1.1.2.43 }
1011 pnkfelix 1.1.2.42
1012 pnkfelix 1.1.2.64 void foundStore(RegAlloc.SpillStore instr) {
1013 cananian 1.9 for (Object tO : instr.defC()) {
1014 cananian 1.9 Temp t = (Temp) tO;
1015 pnkfelix 1.1.2.49
1016 cananian 1.3.2.1 assert t != null : "No nulls for Temps";
1017 pnkfelix 1.1.2.43
1018 pnkfelix 1.1.2.45 if (!(def.getValues(t)).isEmpty()) {
1019 pnkfelix 1.1.2.43 // We have seen a DEF for t in this block
1020 pnkfelix 1.1.2.43 // before; need to move all those instrs over
1021 pnkfelix 1.1.2.43 // before putting this in the DEF set
1022 pnkfelix 1.1.2.43 Iterator instrs =
1023 pnkfelix 1.1.2.45 (def.getValues(t)).iterator();
1024 pnkfelix 1.1.2.43 while(instrs.hasNext()) {
1025 pnkfelix 1.1.2.45 use.add(t, instrs.next());
1026 pnkfelix 1.1.2.42 }
1027 pnkfelix 1.1.2.42 }
1028 pnkfelix 1.1.2.45 def.add(t, instr);
1029 pnkfelix 1.1.2.42 }
1030 pnkfelix 1.1.2.42 }
1031 pnkfelix 1.1.2.43 }
1032 pnkfelix 1.1.2.43
1033 pnkfelix 1.1.2.43 HashMap bbInfoMap;
1034 pnkfelix 1.1.2.43
1035 pnkfelix 1.1.2.43 MakeWebsDumb(Iterator basicBlocks) {
1036 pnkfelix 1.1.2.43 bbInfoMap = new HashMap();
1037 pnkfelix 1.1.2.43
1038 pnkfelix 1.1.2.43 // initialize USE/DEF info
1039 pnkfelix 1.1.2.43 while(basicBlocks.hasNext()) {
1040 pnkfelix 1.1.2.43 BasicBlock bb = (BasicBlock) basicBlocks.next();
1041 pnkfelix 1.1.2.43 WebInfo info = new WebInfo();
1042 pnkfelix 1.1.2.43 bbInfoMap.put(bb, info);
1043 pnkfelix 1.1.2.42
1044 pnkfelix 1.1.2.71 ListIterator instrs = bb.statements().listIterator();
1045 pnkfelix 1.1.2.43 while(instrs.hasNext()) {
1046 pnkfelix 1.1.2.43 Instr instr = (Instr) instrs.next();
1047 pnkfelix 1.1.2.64 if (instr instanceof RegAlloc.SpillLoad) {
1048 pnkfelix 1.1.2.43 // LOAD FROM MEM
1049 pnkfelix 1.1.2.64 info.foundLoad((RegAlloc.SpillLoad) instr);
1050 pnkfelix 1.1.2.64 } else if (instr instanceof RegAlloc.SpillStore) {
1051 pnkfelix 1.1.2.43 // STORE TO MEM
1052 pnkfelix 1.1.2.64 info.foundStore((RegAlloc.SpillStore) instr);
1053 pnkfelix 1.1.2.43 }
1054 pnkfelix 1.1.2.43 }
1055 pnkfelix 1.1.2.43 }
1056 pnkfelix 1.1.2.43 }
1057 pnkfelix 1.1.2.43
1058 salcianu 1.4 public boolean merge(BasicBlockInterf from, BasicBlockInterf to) {
1059 pnkfelix 1.1.2.46
1060 pnkfelix 1.1.2.43 WebInfo fromInfo = (WebInfo) bbInfoMap.get(from);
1061 pnkfelix 1.1.2.43 WebInfo toInfo = (WebInfo) bbInfoMap.get(to);
1062 pnkfelix 1.1.2.43
1063 pnkfelix 1.1.2.43 // FSK: can't just use putAll(); need to track if a change
1064 pnkfelix 1.1.2.43 // FSK: occurred.
1065 pnkfelix 1.1.2.43 // toInfo.in.putAll(fromInfo.out);
1066 pnkfelix 1.1.2.43 boolean changed = false;
1067 pnkfelix 1.1.2.43 Iterator keys = fromInfo.out.keySet().iterator();
1068 pnkfelix 1.1.2.43 while(keys.hasNext()) {
1069 pnkfelix 1.1.2.43 Object key = keys.next();
1070 pnkfelix 1.1.2.46 java.util.Collection newVals = fromInfo.out.getValues(key);
1071 pnkfelix 1.1.2.46 changed = changed || toInfo.in.addAll(key, newVals);
1072 pnkfelix 1.1.2.42 }
1073 pnkfelix 1.1.2.46
1074 pnkfelix 1.1.2.49 // System.out.println("\t\t\tMerging from " + from +
1075 pnkfelix 1.1.2.49 // " to " + to + ":" +
1076 pnkfelix 1.1.2.49 // (changed?"changed":"nochange"));
1077 pnkfelix 1.1.2.43
1078 pnkfelix 1.1.2.43 return changed;
1079 pnkfelix 1.1.2.43 }
1080 pnkfelix 1.1.2.43
1081 pnkfelix 1.1.2.43 public void visit(BasicBlock b) {
1082 pnkfelix 1.1.2.49 // System.out.println("\t\t\tVisiting " + b);
1083 pnkfelix 1.1.2.42
1084 pnkfelix 1.1.2.43 WebInfo webInfo = (WebInfo) bbInfoMap.get(b);
1085 pnkfelix 1.1.2.43
1086 cananian 1.9 for (Object entryO : webInfo.in.entrySet()) {
1087 cananian 1.9 Map.Entry entry = (Map.Entry) entryO;
1088 pnkfelix 1.1.2.43 Temp t = (Temp) entry.getKey();
1089 pnkfelix 1.1.2.43 Web web = (Web) entry.getValue();
1090 pnkfelix 1.1.2.45 Iterator instrs = webInfo.use.getValues(t).iterator();
1091 pnkfelix 1.1.2.46
1092 pnkfelix 1.1.2.49 // System.out.println("\t\t\t\t IN -> OUT : [" +
1093 pnkfelix 1.1.2.49 // web + ", "+b+"]" );
1094 pnkfelix 1.1.2.46
1095 pnkfelix 1.1.2.43 while(instrs.hasNext()) {
1096 pnkfelix 1.1.2.47 web.refs.add(instrs.next());
1097 pnkfelix 1.1.2.43 }
1098 pnkfelix 1.1.2.42
1099 pnkfelix 1.1.2.43 webInfo.out.put(t, web);
1100 pnkfelix 1.1.2.42 }
1101 pnkfelix 1.1.2.43
1102 cananian 1.9 for (Object tO : webInfo.def.keySet()) {
1103 cananian 1.9 Temp t = (Temp) tO;
1104 pnkfelix 1.1.2.45 Set instrs = (Set) webInfo.def.getValues(t);
1105 pnkfelix 1.1.2.42
1106 pnkfelix 1.1.2.43 Web web = new Web(t, instrs);
1107 pnkfelix 1.1.2.42
1108 pnkfelix 1.1.2.43 // Note that this will replace any web in OUT that was
1109 pnkfelix 1.1.2.43 // in IN with the last defined web (with the same temp) in
1110 pnkfelix 1.1.2.43 // this Basic Block (if one exists). This is the correct
1111 pnkfelix 1.1.2.43 // behavior.
1112 pnkfelix 1.1.2.43 webInfo.out.put(t, web);
1113 pnkfelix 1.1.2.43
1114 pnkfelix 1.1.2.42 }
1115 pnkfelix 1.1.2.3 }
1116 pnkfelix 1.1.2.1 }
1117 cananian 1.2