1 pnkfelix 1.1.2.60 // LocalCffRegAlloc.java, created Sat Dec 11 15:20:45 1999 by pnkfelix
2 pnkfelix 1.1.2.33 // 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 pnkfelix 1.1.2.33 import harpoon.Backend.Generic.Code;
7 pnkfelix 1.1.2.44 import harpoon.Backend.Generic.RegFileInfo;
8 pnkfelix 1.1.2.41 import harpoon.Backend.Generic.RegFileInfo.SpillException;
9 pnkfelix 1.1.2.95 import harpoon.Analysis.Maps.Derivation;
10 pnkfelix 1.1.2.95 import harpoon.Backend.Maps.BackendDerivation;
11 pnkfelix 1.1.2.43 import harpoon.Analysis.BasicBlock;
12 pnkfelix 1.1.2.44 import harpoon.Analysis.DataFlow.LiveTemps;
13 pnkfelix 1.1.2.96 import harpoon.Analysis.ReachingDefs;
14 pnkfelix 1.1.2.106 import harpoon.Analysis.ReachingDefsImpl;
15 pnkfelix 1.1.2.103 import harpoon.Analysis.ReachingDefsCachingImpl;
16 pnkfelix 1.1.2.105 import harpoon.Analysis.ReachingDefsAltImpl;
17 pnkfelix 1.1.2.33 import harpoon.Analysis.Instr.TempInstrPair;
18 pnkfelix 1.1.2.66 import harpoon.Analysis.Instr.RegAlloc.SpillLoad;
19 pnkfelix 1.1.2.66 import harpoon.Analysis.Instr.RegAlloc.SpillStore;
20 pnkfelix 1.1.2.1 import harpoon.IR.Assem.Instr;
21 pnkfelix 1.1.2.59 import harpoon.IR.Assem.InstrMOVE;
22 pnkfelix 1.1.2.39 import harpoon.IR.Assem.InstrEdge;
23 pnkfelix 1.1.2.4 import harpoon.IR.Assem.InstrMEM;
24 pnkfelix 1.1.2.33 import harpoon.Temp.Temp;
25 pnkfelix 1.1.2.119 import harpoon.Temp.TempFactory;
26 pnkfelix 1.1.2.94 import harpoon.Temp.TempMap;
27 pnkfelix 1.1.2.44 import harpoon.Temp.Label;
28 pnkfelix 1.1.2.59
29 pnkfelix 1.1.2.95 import harpoon.ClassFile.HClass;
30 pnkfelix 1.1.2.95 import harpoon.ClassFile.HCodeElement;
31 pnkfelix 1.1.2.95
32 cananian 1.6 import net.cscott.jutil.CombineIterator;
33 pnkfelix 1.1.2.1 import harpoon.Util.Util;
34 cananian 1.6 import net.cscott.jutil.FilterIterator;
35 pnkfelix 1.1.2.1
36 cananian 1.6 import net.cscott.jutil.LinearSet;
37 cananian 1.6 import net.cscott.jutil.Factories;
38 pnkfelix 1.1.2.82
39 cananian 1.6 import net.cscott.jutil.GenericMultiMap;
40 cananian 1.6 import net.cscott.jutil.MultiMap;
41 cananian 1.6 import net.cscott.jutil.SetFactory;
42 cananian 1.6 import net.cscott.jutil.BitSetFactory;
43 cananian 1.6 import net.cscott.jutil.ReverseIterator;
44 pnkfelix 1.1.2.75
45 pnkfelix 1.1.2.75 import java.util.Arrays;
46 pnkfelix 1.1.2.30 import java.util.List;
47 pnkfelix 1.1.2.106 import java.util.ArrayList;
48 pnkfelix 1.1.2.33 import java.util.Set;
49 pnkfelix 1.1.2.44 import java.util.HashSet;
50 pnkfelix 1.1.2.59 import java.util.Collection;
51 pnkfelix 1.1.2.64 import java.util.Collections;
52 pnkfelix 1.1.2.33 import java.util.SortedSet;
53 pnkfelix 1.1.2.59 import java.util.TreeSet;
54 pnkfelix 1.1.2.59 import java.util.Map;
55 pnkfelix 1.1.2.59 import java.util.HashMap;
56 pnkfelix 1.1.2.59 import java.util.Iterator;
57 pnkfelix 1.1.2.75 import java.util.ListIterator;
58 pnkfelix 1.1.2.59
59 pnkfelix 1.1.2.54
60 pnkfelix 1.1.2.59 /**
61 pnkfelix 1.1.2.60 * <code>LocalCffRegAlloc</code> performs <A
62 pnkfelix 1.1.2.71 * HREF="http://lm.lcs.mit.edu/~pnkfelix/papers/hardnessLRA.ps">
63 pnkfelix 1.1.2.71 * Local Register Allocation</A> for a given set of
64 pnkfelix 1.1.2.71 * <code>Instr</code>s using a conservative-furthest-first algorithm.
65 pnkfelix 1.1.2.71 * The papers <A
66 pnkfelix 1.1.2.71 * HREF="http://ctf.lcs.mit.edu/~pnkfelix/papers/OnLocalRegAlloc.ps.gz">
67 pnkfelix 1.1.2.71 * "On Local Register Allocation"</A> and <A
68 pnkfelix 1.1.2.71 * HREF="http://ctf.lcs.mit.edu/~pnkfelix/papers/hardnessLRA.ps">"Hardness and
69 pnkfelix 1.1.2.71 * Algorithms for Local Register Allocation"</A> lay out the basis
70 pnkfelix 1.1.2.71 * for the algorithm it uses to allocate and assign registers.
71 pnkfelix 1.1.2.71 *
72 pnkfelix 1.1.2.59 *
73 pnkfelix 1.1.2.59 * @author Felix S. Klock II <pnkfelix@mit.edu>
74 cananian 1.7 * @version $Id: LocalCffRegAlloc.java,v 1.7 2004/02/08 04:55:22 cananian Exp $
75 pnkfelix 1.1.2.33 */
76 pnkfelix 1.1.2.60 public class LocalCffRegAlloc extends RegAlloc {
77 pnkfelix 1.1.2.112
78 pnkfelix 1.1.2.112 public static RegAlloc.Factory FACTORY =
79 pnkfelix 1.1.2.112 new RegAlloc.Factory() {
80 pnkfelix 1.1.2.112 public RegAlloc makeRegAlloc(Code c) {
81 pnkfelix 1.1.2.112 return new LocalCffRegAlloc(c);
82 pnkfelix 1.1.2.112 }
83 pnkfelix 1.1.2.112 };
84 pnkfelix 1.1.2.63
85 pnkfelix 1.1.2.118 static RegAlloc.Factory RD_DISABLED_FACTORY =
86 pnkfelix 1.1.2.118 new RegAlloc.Factory() {
87 pnkfelix 1.1.2.118 public RegAlloc makeRegAlloc(Code c) {
88 pnkfelix 1.1.2.118 return new LocalCffRegAlloc(c, false);
89 pnkfelix 1.1.2.118 }
90 pnkfelix 1.1.2.118 };
91 pnkfelix 1.1.2.118
92 pnkfelix 1.1.2.119 private static TempFactory preassignTF = new TempFactory() {
93 pnkfelix 1.1.2.119 public String getScope() {
94 pnkfelix 1.1.2.119 return "private TF for RegFileInfo";
95 pnkfelix 1.1.2.119 }
96 pnkfelix 1.1.2.119 public String getUniqueID(String suggestion) {
97 pnkfelix 1.1.2.119 return "rfi"+suggestion.hashCode();
98 pnkfelix 1.1.2.119 }
99 pnkfelix 1.1.2.119 };
100 pnkfelix 1.1.2.119
101 pnkfelix 1.1.2.119 /** <code>PreassignTemp</code> represents <code>Temp</code>s
102 pnkfelix 1.1.2.119 * which have been pre-assigned to machine registers. */
103 pnkfelix 1.1.2.119 public static class PreassignTemp extends Temp {
104 pnkfelix 1.1.2.119 private Temp reg;
105 pnkfelix 1.1.2.119 public PreassignTemp(Temp reg) {
106 pnkfelix 1.1.2.119 super(preassignTF);
107 pnkfelix 1.1.2.119 this.reg = reg;
108 pnkfelix 1.1.2.119 }
109 pnkfelix 1.1.2.119 public String toString() {
110 pnkfelix 1.1.2.119 return reg+"<preassigned>";
111 pnkfelix 1.1.2.119 }
112 pnkfelix 1.1.2.119 }
113 pnkfelix 1.1.2.119
114 pnkfelix 1.1.2.119
115 pnkfelix 1.1.2.119
116 pnkfelix 1.1.2.107 private static final boolean VERIFY = false;
117 pnkfelix 1.1.2.80
118 pnkfelix 1.1.2.107 private static final boolean PREASSIGN_INFO = false;
119 pnkfelix 1.1.2.107 private static final boolean SPILL_INFO = false;
120 pnkfelix 1.1.2.107 private static final boolean COALESCE_MOVES = true;
121 pnkfelix 1.1.2.107
122 pnkfelix 1.1.2.107 /** ASSERTDB => assertions should emit extra info when available. */
123 pnkfelix 1.1.2.107 private static final boolean ASSERTDB = false;
124 pnkfelix 1.1.2.89
125 pnkfelix 1.1.2.110 Collection genRegC;
126 pnkfelix 1.1.2.110 Collection allRegC;
127 pnkfelix 1.1.2.89 Collection allRegisters;
128 pnkfelix 1.1.2.80
129 pnkfelix 1.1.2.119 Collection preassignedTemps = new HashSet();
130 pnkfelix 1.1.2.119
131 pnkfelix 1.1.2.82 private LiveTemps liveTemps;
132 pnkfelix 1.1.2.80
133 pnkfelix 1.1.2.94 // maps Temp:c -> Temp:o where `c' was coalesced and references to
134 pnkfelix 1.1.2.94 // `c' have been replaced with references to `o'
135 pnkfelix 1.1.2.97 // maps Instr:i -> (Temp:c -> Temp:o) where `c' was coalesced in
136 pnkfelix 1.1.2.97 // the BasicBlock containing `i' and references to `c' in the
137 pnkfelix 1.1.2.97 // instructions of that BasicBlock have been replaced with
138 pnkfelix 1.1.2.97 // references to `o'
139 pnkfelix 1.1.2.97 private Map instrToHTempMap;
140 pnkfelix 1.1.2.94
141 pnkfelix 1.1.2.96 // Used for supporting Derivation information
142 pnkfelix 1.1.2.96 private ReachingDefs reachingDefs;
143 pnkfelix 1.1.2.96
144 pnkfelix 1.1.2.96 // maps Temp:t -> Instr:i where `i' is removed and defined `t'
145 pnkfelix 1.1.2.110 private Map tempToRemovedInstrs;
146 pnkfelix 1.1.2.96
147 pnkfelix 1.1.2.82 /** Creates a <code>LocalCffRegAlloc</code>. */
148 pnkfelix 1.1.2.82 public LocalCffRegAlloc(Code code) {
149 pnkfelix 1.1.2.118 this(code, true);
150 pnkfelix 1.1.2.118 }
151 pnkfelix 1.1.2.118 private LocalCffRegAlloc(Code code, boolean enableRD) {
152 pnkfelix 1.1.2.82 super(code);
153 pnkfelix 1.1.2.110 allRegC = frame.getRegFileInfo().getAllRegistersC();
154 pnkfelix 1.1.2.110 genRegC = frame.getRegFileInfo().getGeneralRegistersC();
155 pnkfelix 1.1.2.110 allRegisters = allRegC;
156 pnkfelix 1.1.2.97 instrToHTempMap = new HashMap();
157 pnkfelix 1.1.2.110 tempToRemovedInstrs = new HashMap();
158 pnkfelix 1.1.2.103 if (TIME) System.out.print("D");
159 pnkfelix 1.1.2.105 // reachingDefs = new ReachingDefsCachingImpl(code);
160 pnkfelix 1.1.2.118 if (enableRD)
161 pnkfelix 1.1.2.118 reachingDefs = new ReachingDefsAltImpl(code);
162 pnkfelix 1.1.2.96 }
163 pnkfelix 1.1.2.96
164 pnkfelix 1.1.2.96 private Instr definition(Instr i, Temp t) {
165 pnkfelix 1.1.2.118 if (i.defC().contains(t)
166 pnkfelix 1.1.2.118 || reachingDefs == null // FSK: yuck yuck yuck
167 pnkfelix 1.1.2.118 ) {
168 pnkfelix 1.1.2.110 // System.out.print(" d");
169 pnkfelix 1.1.2.96 return i;
170 pnkfelix 1.1.2.110 } else {
171 pnkfelix 1.1.2.96 Set defset = reachingDefs.reachingDefs(i, t);
172 pnkfelix 1.1.2.96 Iterator defs = defset.iterator();
173 pnkfelix 1.1.2.96 return (Instr) defs.next();
174 pnkfelix 1.1.2.96 }
175 pnkfelix 1.1.2.1 }
176 pnkfelix 1.1.2.33
177 pnkfelix 1.1.2.95 protected Derivation getDerivation() {
178 pnkfelix 1.1.2.95 final Derivation oldD = code.getDerivation();
179 pnkfelix 1.1.2.95 return new BackendDerivation() {
180 pnkfelix 1.1.2.95 private HCodeElement orig(HCodeElement h){
181 pnkfelix 1.1.2.101 return getBack((Instr)h);
182 pnkfelix 1.1.2.95 }
183 pnkfelix 1.1.2.97 private Temp orig(HCodeElement h, Temp t) {
184 pnkfelix 1.1.2.97 HTempMap coalescedTemps = (HTempMap) instrToHTempMap.get(h);
185 cananian 1.3.2.1 assert coalescedTemps != null : (ASSERTDB ? "no mapping for "+h : "no mapping");
186 pnkfelix 1.1.2.96 return coalescedTemps.tempMap(t);
187 pnkfelix 1.1.2.96 }
188 pnkfelix 1.1.2.95 public HClass typeMap(HCodeElement hce, Temp t) {
189 pnkfelix 1.1.2.97 HCodeElement hce2 = orig(hce);
190 pnkfelix 1.1.2.97 Temp t2 = orig(hce, t);
191 pnkfelix 1.1.2.97 return oldD.typeMap(hce2, t2);
192 pnkfelix 1.1.2.95 }
193 pnkfelix 1.1.2.95 public Derivation.DList derivation(HCodeElement hce, Temp t) {
194 pnkfelix 1.1.2.97 HTempMap coalescedTemps = (HTempMap)instrToHTempMap.get(hce);
195 cananian 1.3.2.1 assert coalescedTemps != null : (ASSERTDB ? "no mapping for "+hce : "no mapping");
196 pnkfelix 1.1.2.97 HCodeElement hce2 = orig(hce);
197 pnkfelix 1.1.2.97 Temp t2 = orig(hce, t);
198 pnkfelix 1.1.2.95 return Derivation.DList.rename
199 pnkfelix 1.1.2.97 (oldD.derivation(hce2, t2), coalescedTemps);
200 pnkfelix 1.1.2.95 }
201 pnkfelix 1.1.2.95 public BackendDerivation.Register
202 pnkfelix 1.1.2.95 calleeSaveRegister(HCodeElement hce, Temp t) {
203 pnkfelix 1.1.2.97 hce = orig(hce); t = orig(hce, t);
204 pnkfelix 1.1.2.95 return ((BackendDerivation)oldD).calleeSaveRegister(hce, t);
205 pnkfelix 1.1.2.95 }
206 pnkfelix 1.1.2.95 };
207 pnkfelix 1.1.2.94 }
208 pnkfelix 1.1.2.94
209 pnkfelix 1.1.2.86 final Collection instrsToRemove = new java.util.LinkedList();
210 pnkfelix 1.1.2.86 // final Collection instrsToRemove = new java.util.HashSet();
211 pnkfelix 1.1.2.82
212 pnkfelix 1.1.2.82 // alternating sequence of an Instr followed by its replacement
213 pnkfelix 1.1.2.82 // (due to temp remapping...) eg [ i0 r0 i1 r1 ... iN rN ]
214 pnkfelix 1.1.2.82 final List instrsToReplace = new java.util.LinkedList();
215 pnkfelix 1.1.2.75
216 pnkfelix 1.1.2.75 // When writing spillCode insertion routines, be sure to check
217 pnkfelix 1.1.2.75 // that the method of insertion is correct given the control flow
218 pnkfelix 1.1.2.75 // for that Instr...
219 pnkfelix 1.1.2.75
220 pnkfelix 1.1.2.75 // this List is an alternating sequence of a Load and the Instr
221 pnkfelix 1.1.2.80 // that the Load is to occur BEFORE; eg. [ l0 i0 l1 i1 .. lN iN ]
222 pnkfelix 1.1.2.75 final List spillLoads = new java.util.LinkedList();
223 pnkfelix 1.1.2.75
224 pnkfelix 1.1.2.75 // this List is an alternating sequence of a Store and the Instr
225 pnkfelix 1.1.2.80 // that the Store is to occur AFTER; eg. [ s0 i0 s1 i1 .. sN iN ]
226 pnkfelix 1.1.2.75 final List spillStores = new java.util.LinkedList();
227 pnkfelix 1.1.2.75
228 pnkfelix 1.1.2.82
229 pnkfelix 1.1.2.82 protected void generateRegAssignment() {
230 pnkfelix 1.1.2.116 // this needs to be first, before we insert new Instrs that
231 pnkfelix 1.1.2.116 // won't be in the block-set proper.
232 pnkfelix 1.1.2.116 fixupUnreachableCode();
233 pnkfelix 1.1.2.116
234 pnkfelix 1.1.2.103 if (TIME) System.out.print("L");
235 pnkfelix 1.1.2.82 liveVariableAnalysis();
236 pnkfelix 1.1.2.106 // if (TIME) System.out.print("A");
237 pnkfelix 1.1.2.82 allocationAnalysis();
238 pnkfelix 1.1.2.82 // analysis complete; now update Instrs (which will break
239 pnkfelix 1.1.2.82 // current BasicBlock analysis results...
240 pnkfelix 1.1.2.82
241 pnkfelix 1.1.2.103 if (TIME) System.out.print("S");
242 pnkfelix 1.1.2.82 insertSpillCode();
243 pnkfelix 1.1.2.103
244 pnkfelix 1.1.2.103 if (TIME) System.out.print("M");
245 pnkfelix 1.1.2.82 replaceInstrs();
246 pnkfelix 1.1.2.82 if (COALESCE_MOVES) coalesceMoves();
247 pnkfelix 1.1.2.103
248 pnkfelix 1.1.2.82 if (VERIFY) verifyLRA();
249 pnkfelix 1.1.2.82
250 pnkfelix 1.1.2.94 // code.printNoAssem(new java.io.PrintWriter(System.out));
251 pnkfelix 1.1.2.79 }
252 pnkfelix 1.1.2.82
253 pnkfelix 1.1.2.116 private void fixupUnreachableCode() {
254 pnkfelix 1.1.2.116 for(Iterator is=code.getElementsI(); is.hasNext();){
255 pnkfelix 1.1.2.116 Instr i = (Instr) is.next();
256 pnkfelix 1.1.2.116 if (bbFact.getBlock(i) == null) {
257 pnkfelix 1.1.2.116 for(Iterator refs=getRefs(i); refs.hasNext();){
258 pnkfelix 1.1.2.116 Temp r = (Temp) refs.next();
259 pnkfelix 1.1.2.116 // use any old assignment, since this code MUST
260 pnkfelix 1.1.2.116 // be unreachable anyway.
261 cananian 1.3.2.1 assert !code.registerAssigned(i, r);
262 pnkfelix 1.1.2.116 code.assignRegister
263 pnkfelix 1.1.2.116 (i, r, (List)
264 pnkfelix 1.1.2.116 frame.getRegFileInfo().
265 pnkfelix 1.1.2.116 getRegAssignments(r).iterator().next());
266 pnkfelix 1.1.2.116 }
267 pnkfelix 1.1.2.116 checked.add(i);
268 pnkfelix 1.1.2.116 }
269 pnkfelix 1.1.2.116 }
270 pnkfelix 1.1.2.116 }
271 pnkfelix 1.1.2.116
272 pnkfelix 1.1.2.116 /** includes both pseudo-regs and machine-regs for now. */
273 pnkfelix 1.1.2.116 private static Iterator getRefs(final Instr i) {
274 pnkfelix 1.1.2.116 return new CombineIterator(i.useC().iterator(),
275 pnkfelix 1.1.2.116 i.defC().iterator());
276 pnkfelix 1.1.2.116 }
277 pnkfelix 1.1.2.116
278 pnkfelix 1.1.2.82 private void liveVariableAnalysis() {
279 pnkfelix 1.1.2.82 liveTemps =
280 pnkfelix 1.1.2.82 new LiveTemps(bbFact, frame.getRegFileInfo().liveOnExit());
281 pnkfelix 1.1.2.82 harpoon.Analysis.DataFlow.Solver.worklistSolve
282 pnkfelix 1.1.2.104
283 pnkfelix 1.1.2.104 // (bbFact.preorderBlocksIter(),
284 cananian 1.5 (new ReverseIterator(bbFact.postorderBlocksIter()),
285 pnkfelix 1.1.2.104
286 pnkfelix 1.1.2.104 liveTemps);
287 pnkfelix 1.1.2.79 }
288 pnkfelix 1.1.2.82
289 pnkfelix 1.1.2.108 // runs once / code
290 pnkfelix 1.1.2.108 private void allocationAnalysis() {
291 pnkfelix 1.1.2.106 if (!TIME) {
292 pnkfelix 1.1.2.106 // old way (more space efficient, but harder to profile)
293 cananian 1.7 for (Object blockO : bbFact.blockSet()) {
294 cananian 1.7 BasicBlock block = (BasicBlock) blockO;
295 pnkfelix 1.1.2.106 Set liveOnExit = liveTemps.getLiveOnExit(block);
296 pnkfelix 1.1.2.106 BlockAlloc la = new BlockAlloc(block, liveOnExit);
297 pnkfelix 1.1.2.110 la.emptyRegFile(la.alloc());
298 pnkfelix 1.1.2.106 }
299 pnkfelix 1.1.2.110 } else { // For all below, TIME == true
300 pnkfelix 1.1.2.106 // temporary method for profiling purposes
301 pnkfelix 1.1.2.110 System.out.print("B");
302 pnkfelix 1.1.2.106 Set blockSet = bbFact.blockSet();
303 pnkfelix 1.1.2.106 Iterator blocks = blockSet.iterator();
304 pnkfelix 1.1.2.106 List blockAllocList = new ArrayList(blockSet.size());
305 pnkfelix 1.1.2.110 Instr[] lastInstrs = new Instr[blockSet.size()];
306 pnkfelix 1.1.2.106 while(blocks.hasNext()) {
307 pnkfelix 1.1.2.106 BasicBlock block = (BasicBlock) blocks.next();
308 pnkfelix 1.1.2.106 Set liveOnExit = liveTemps.getLiveOnExit(block);
309 pnkfelix 1.1.2.106 BlockAlloc la = new BlockAlloc(block, liveOnExit);
310 pnkfelix 1.1.2.106 blockAllocList.add(la);
311 pnkfelix 1.1.2.106 }
312 pnkfelix 1.1.2.106
313 pnkfelix 1.1.2.110 Iterator blockAllocs;
314 pnkfelix 1.1.2.110
315 pnkfelix 1.1.2.110 System.out.print("N");
316 pnkfelix 1.1.2.110 blockAllocs = blockAllocList.iterator();
317 pnkfelix 1.1.2.110 while(blockAllocs.hasNext()) {
318 pnkfelix 1.1.2.110 BlockAlloc la = (BlockAlloc) blockAllocs.next();
319 pnkfelix 1.1.2.110 la.buildNextRef();
320 pnkfelix 1.1.2.110 }
321 pnkfelix 1.1.2.110
322 pnkfelix 1.1.2.110 System.out.print("P");
323 pnkfelix 1.1.2.110 blockAllocs = blockAllocList.iterator();
324 pnkfelix 1.1.2.106 while(blockAllocs.hasNext()) {
325 pnkfelix 1.1.2.106 BlockAlloc la = (BlockAlloc) blockAllocs.next();
326 pnkfelix 1.1.2.110 la.buildPreassignMap();
327 pnkfelix 1.1.2.110 }
328 pnkfelix 1.1.2.110
329 pnkfelix 1.1.2.110 System.out.print("T");
330 pnkfelix 1.1.2.110 blockAllocs = blockAllocList.iterator();
331 pnkfelix 1.1.2.110 while(blockAllocs.hasNext()) {
332 pnkfelix 1.1.2.110 BlockAlloc la = (BlockAlloc) blockAllocs.next();
333 pnkfelix 1.1.2.110 la.makeTempSets();
334 pnkfelix 1.1.2.110 la.buildTempSets();
335 pnkfelix 1.1.2.110 }
336 pnkfelix 1.1.2.110
337 pnkfelix 1.1.2.110 System.out.print("A");
338 pnkfelix 1.1.2.110 blockAllocs = blockAllocList.iterator();
339 pnkfelix 1.1.2.110 for(int i=0; blockAllocs.hasNext(); i++) {
340 pnkfelix 1.1.2.110 BlockAlloc la = (BlockAlloc) blockAllocs.next();
341 pnkfelix 1.1.2.110 lastInstrs[i] = la.alloc();
342 pnkfelix 1.1.2.110 }
343 pnkfelix 1.1.2.110
344 pnkfelix 1.1.2.110 System.out.print("E");
345 pnkfelix 1.1.2.110 blockAllocs = blockAllocList.iterator();
346 pnkfelix 1.1.2.110 for(int i=0; blockAllocs.hasNext(); i++) {
347 pnkfelix 1.1.2.110 BlockAlloc la = (BlockAlloc) blockAllocs.next();
348 pnkfelix 1.1.2.110 la.emptyRegFile(lastInstrs[i]);
349 pnkfelix 1.1.2.106 }
350 pnkfelix 1.1.2.1 }
351 pnkfelix 1.1.2.82 }
352 pnkfelix 1.1.2.75
353 pnkfelix 1.1.2.82 private void insertSpillCode() {
354 pnkfelix 1.1.2.75 // done doing analysis on blocks, now update with spill code.
355 pnkfelix 1.1.2.75 // (Remember to verify control flow properties)
356 pnkfelix 1.1.2.75 Iterator loads = spillLoads.iterator();
357 pnkfelix 1.1.2.75 while(loads.hasNext()) {
358 pnkfelix 1.1.2.75 Instr load = (Instr) loads.next();
359 pnkfelix 1.1.2.75 Instr loc = (Instr) loads.next();
360 cananian 1.3.2.1 assert loc.getPrev() != null : (ASSERTDB ? "verify control flow prop 1. "+loc:"cfp1");
361 cananian 1.3.2.1 assert loc.getPrev().getTargets().isEmpty() : (ASSERTDB ? "verify control flow prop 2. "+loc:"cfp2");
362 cananian 1.3.2.1 assert loc.getPrev().canFallThrough : (ASSERTDB ? "verify control flow prop 3. "+loc:"cfp3");
363 pnkfelix 1.1.2.75 load.insertAt(new InstrEdge(loc.getPrev(), loc));
364 pnkfelix 1.1.2.75 }
365 pnkfelix 1.1.2.75
366 pnkfelix 1.1.2.75 Iterator stores = spillStores.iterator();
367 pnkfelix 1.1.2.75 while(stores.hasNext()) {
368 pnkfelix 1.1.2.75 Instr store = (Instr) stores.next();
369 pnkfelix 1.1.2.75 Instr loc = (Instr) stores.next();
370 cananian 1.3.2.1 assert loc.getTargets().isEmpty() : "overconservative assertion (targets may not be empty)";
371 cananian 1.3.2.1 assert loc.canFallThrough : "overconservative assertion (loc need not fall through)";
372 pnkfelix 1.1.2.107
373 cananian 1.3.2.1 assert loc.getNext() != null : (ASSERTDB ? "verify control flow prop 4. "+loc:"cfp4");
374 pnkfelix 1.1.2.75 InstrEdge e = new InstrEdge(loc, loc.getNext());
375 pnkfelix 1.1.2.75 store.insertAt(e);
376 pnkfelix 1.1.2.75 }
377 pnkfelix 1.1.2.80
378 pnkfelix 1.1.2.82 }
379 pnkfelix 1.1.2.80
380 pnkfelix 1.1.2.82 private void coalesceMoves() {
381 cananian 1.7 for (Object irO : instrsToRemove) {
382 cananian 1.7 Instr ir = (Instr) irO;
383 pnkfelix 1.1.2.80
384 pnkfelix 1.1.2.86 // FSK: can't handle directly remove this case: "t4 <- r0"
385 pnkfelix 1.1.2.86 // followed by a use of t4, because the system thinks that
386 pnkfelix 1.1.2.86 // t4 is undefined. (This is instead handled by a
387 pnkfelix 1.1.2.86 // replacement of the Instr with an InstrMOVEproxy)
388 pnkfelix 1.1.2.80
389 cananian 1.3.2.1 assert !hasRegister(expand(ir.use()[0]));
390 cananian 1.3.2.1 assert !hasRegister(expand(ir.def()[0]));
391 pnkfelix 1.1.2.80
392 pnkfelix 1.1.2.82 ir.remove();
393 pnkfelix 1.1.2.80
394 pnkfelix 1.1.2.75 }
395 pnkfelix 1.1.2.82 }
396 pnkfelix 1.1.2.75
397 pnkfelix 1.1.2.82 private void replaceInstrs() {
398 pnkfelix 1.1.2.82 Iterator replace = instrsToReplace.iterator();
399 pnkfelix 1.1.2.82 while(replace.hasNext()) {
400 pnkfelix 1.1.2.82 Instr pre = (Instr) replace.next();
401 pnkfelix 1.1.2.82 Instr post = (Instr) replace.next();
402 pnkfelix 1.1.2.82 Instr.replace(pre, post);
403 pnkfelix 1.1.2.75 }
404 pnkfelix 1.1.2.82 }
405 pnkfelix 1.1.2.80
406 pnkfelix 1.1.2.82 private void verifyLRA() {
407 pnkfelix 1.1.2.104 if (TIME) System.out.print("V");
408 pnkfelix 1.1.2.82
409 pnkfelix 1.1.2.82 // after LRA is completed, load and store instructions may
410 pnkfelix 1.1.2.82 // have been inserted at block beginings/endings.
411 pnkfelix 1.1.2.82 // Therefore we need to redo BB computation.
412 pnkfelix 1.1.2.82 computeBasicBlocks();
413 pnkfelix 1.1.2.82 liveVariableAnalysis();
414 pnkfelix 1.1.2.82
415 pnkfelix 1.1.2.82 Iterator blocks = bbFact.blockSet().iterator();
416 pnkfelix 1.1.2.61
417 pnkfelix 1.1.2.82 Set spillUses = new HashSet();
418 pnkfelix 1.1.2.82 Set spillDefs = new HashSet();
419 pnkfelix 1.1.2.82 while(blocks.hasNext()) {
420 pnkfelix 1.1.2.82 BasicBlock b = (BasicBlock) blocks.next();
421 pnkfelix 1.1.2.82 Set liveOnExit = liveTemps.getLiveOnExit(b);
422 pnkfelix 1.1.2.82 // System.out.println();
423 pnkfelix 1.1.2.82 verify(b, liveOnExit, spillUses, spillDefs);
424 pnkfelix 1.1.2.82 }
425 pnkfelix 1.1.2.82
426 pnkfelix 1.1.2.82 // code.print(new java.io.PrintWriter(System.out));
427 pnkfelix 1.1.2.82
428 pnkfelix 1.1.2.89 final Set vUses = new HashSet(spillUses);
429 pnkfelix 1.1.2.82 Set vDefs = new HashSet(spillDefs);
430 pnkfelix 1.1.2.82 vUses.removeAll(spillDefs);
431 pnkfelix 1.1.2.82 vDefs.removeAll(spillUses);
432 pnkfelix 1.1.2.82
433 cananian 1.3.2.1 assert vUses.isEmpty() : "SpillLoad of undefined Temps";
434 pnkfelix 1.1.2.89
435 pnkfelix 1.1.2.82
436 cananian 1.3.2.1 assert vDefs.isEmpty() : "(overconservative) SpillStore of unused Temp";
437 pnkfelix 1.1.2.82 }
438 pnkfelix 1.1.2.82
439 pnkfelix 1.1.2.75 boolean hasRegs(Instr i, Temp t) {
440 pnkfelix 1.1.2.82 return (isRegister(t) || code.registerAssigned(i, t));
441 pnkfelix 1.1.2.78 }
442 pnkfelix 1.1.2.78
443 pnkfelix 1.1.2.78 boolean hasRegs(Instr i, Collection c) {
444 pnkfelix 1.1.2.78 Iterator iter = c.iterator();
445 pnkfelix 1.1.2.78 boolean b = true;
446 pnkfelix 1.1.2.78 while(iter.hasNext()) {
447 pnkfelix 1.1.2.78 Temp t = (Temp) iter.next();
448 pnkfelix 1.1.2.78 b = b && hasRegs(i, t);
449 pnkfelix 1.1.2.78 }
450 pnkfelix 1.1.2.78 return b;
451 pnkfelix 1.1.2.75 }
452 pnkfelix 1.1.2.75
453 pnkfelix 1.1.2.75 Collection getRegs(Instr i, Temp t) {
454 pnkfelix 1.1.2.82 if (isRegister(t)) {
455 pnkfelix 1.1.2.75 return Collections.singleton(t);
456 pnkfelix 1.1.2.75 } else if (code.registerAssigned(i,t)) {
457 pnkfelix 1.1.2.75 return code.getRegisters(i, t);
458 pnkfelix 1.1.2.75 } else {
459 pnkfelix 1.1.2.75 return null;
460 pnkfelix 1.1.2.75 }
461 pnkfelix 1.1.2.75 }
462 pnkfelix 1.1.2.59
463 pnkfelix 1.1.2.80 private void verify(final BasicBlock block,
464 pnkfelix 1.1.2.80 final Set liveOnExit,
465 pnkfelix 1.1.2.80 final Set spillUses,
466 pnkfelix 1.1.2.80 final Set spillDefs) {
467 pnkfelix 1.1.2.75 // includes SpillLoads and SpillStores...
468 pnkfelix 1.1.2.75 Iterator instrs = block.statements().iterator();
469 pnkfelix 1.1.2.82 Verify verify = new Verify(this, block, spillUses, spillDefs);
470 pnkfelix 1.1.2.75 while(instrs.hasNext()) {
471 pnkfelix 1.1.2.75 Instr i = (Instr) instrs.next();
472 pnkfelix 1.1.2.75 i.accept(verify);
473 cananian 1.3.2.1 assert instrToHTempMap.keySet().contains(i) : (ASSERTDB ? "missing instr:"+i:"missing instr");
474 pnkfelix 1.1.2.75 }
475 pnkfelix 1.1.2.75 }
476 pnkfelix 1.1.2.75
477 pnkfelix 1.1.2.80 /** Updates `tempSets' with instructions from `b'.
478 pnkfelix 1.1.2.80 modifies: `tempSets'
479 pnkfelix 1.1.2.80 effects: incorporates move instructions in `b' into the
480 pnkfelix 1.1.2.80 equivalency classes maintained in `tempSets'
481 pnkfelix 1.1.2.80 The equality operation used for the construction is
482 pnkfelix 1.1.2.80 eq(t1, t2) =
483 pnkfelix 1.1.2.80 exists InstrMOVE: "t1 <- t2" in `b'
484 pnkfelix 1.1.2.80 && NOT (t1 is register && t2 is register)
485 pnkfelix 1.1.2.80 */
486 pnkfelix 1.1.2.82 void buildTempSets(final EqTempSets tempSets, BasicBlock b) {
487 pnkfelix 1.1.2.75 class ScanForMove extends harpoon.IR.Assem.InstrVisitor {
488 pnkfelix 1.1.2.82 public void visit(Instr i) { /* do nothing */ }
489 pnkfelix 1.1.2.82
490 pnkfelix 1.1.2.75 public void visit(InstrMOVE i) {
491 pnkfelix 1.1.2.89 List dl = expand(i.def()[0]);
492 pnkfelix 1.1.2.89 List ul = expand(i.use()[0]);
493 pnkfelix 1.1.2.89
494 cananian 1.3.2.1 assert dl.size() == ul.size();
495 pnkfelix 1.1.2.89 Iterator ds = dl.iterator();
496 pnkfelix 1.1.2.89 Iterator us = ul.iterator();
497 pnkfelix 1.1.2.89
498 pnkfelix 1.1.2.89 while(ds.hasNext()) {
499 pnkfelix 1.1.2.89 Temp d = (Temp) ds.next();
500 pnkfelix 1.1.2.89 Temp u = (Temp) us.next();
501 pnkfelix 1.1.2.78
502 pnkfelix 1.1.2.89 if ((! (isRegister(d) && isRegister(u))) &&
503 pnkfelix 1.1.2.89 ! d.equals(u)) {
504 pnkfelix 1.1.2.89 tempSets.add(d, u);
505 pnkfelix 1.1.2.89 }
506 pnkfelix 1.1.2.75 }
507 pnkfelix 1.1.2.75 }
508 pnkfelix 1.1.2.75 }
509 pnkfelix 1.1.2.75
510 pnkfelix 1.1.2.75 ScanForMove visit = new ScanForMove();
511 pnkfelix 1.1.2.75
512 pnkfelix 1.1.2.75 List instrL = b.statements();
513 cananian 1.7 for (Object iO : instrL) {
514 cananian 1.7 Instr i = (Instr) iO;
515 pnkfelix 1.1.2.75 i.accept(visit);
516 pnkfelix 1.1.2.63 }
517 pnkfelix 1.1.2.63 }
518 pnkfelix 1.1.2.63
519 pnkfelix 1.1.2.75
520 pnkfelix 1.1.2.59 // can add 1 to weight later, so store MAX_VALUE - 1 at most.
521 pnkfelix 1.1.2.59 static Integer INFINITY = new Integer( Integer.MAX_VALUE - 1 );
522 pnkfelix 1.1.2.1
523 pnkfelix 1.1.2.82 class BlockAlloc {
524 pnkfelix 1.1.2.97
525 pnkfelix 1.1.2.97 final HTempMap coalescedTemps = new HTempMap();
526 pnkfelix 1.1.2.59 final BasicBlock block;
527 pnkfelix 1.1.2.59 final Set liveOnExit;
528 pnkfelix 1.1.2.110 final RegFile regfile = new RegFile(allRegC);
529 pnkfelix 1.1.2.82
530 pnkfelix 1.1.2.82 // EqTempSets for this.block
531 pnkfelix 1.1.2.110 EqTempSets tempSets;
532 pnkfelix 1.1.2.63
533 pnkfelix 1.1.2.77 // Temp:t currently in regfile -> Index of next ref to t
534 pnkfelix 1.1.2.110 final Map evictables;
535 pnkfelix 1.1.2.63
536 pnkfelix 1.1.2.82 // (Instr:i x Temp:t) -> Int:2 * index of next Instr w/ ref(t)
537 pnkfelix 1.1.2.82 // [only defined for t's that have a future reference; else null]
538 pnkfelix 1.1.2.110 Map nextRef;
539 pnkfelix 1.1.2.75
540 pnkfelix 1.1.2.82 // Instr currently being alloc'd
541 pnkfelix 1.1.2.79 Instr curr;
542 pnkfelix 1.1.2.79
543 pnkfelix 1.1.2.82 // maps Temp:t -> Set of Regs whose live regions interfere
544 pnkfelix 1.1.2.82 // with t's live region
545 pnkfelix 1.1.2.110 MultiMap preassignMap;
546 pnkfelix 1.1.2.75
547 pnkfelix 1.1.2.82 // maps Temp:s -> Temp:t where s := u) has been selected for
548 pnkfelix 1.1.2.82 // removal and `u' == `t' or remappedTemps.get(`u') == `t' and
549 pnkfelix 1.1.2.82 // thus all uses of `s' must be replaced by uses of `t'
550 pnkfelix 1.1.2.82 final HTempMap remappedTemps = new HTempMap();
551 pnkfelix 1.1.2.78
552 pnkfelix 1.1.2.82 BlockAlloc(BasicBlock b, Set lvOnExit) {
553 pnkfelix 1.1.2.59 block = b;
554 pnkfelix 1.1.2.59 liveOnExit = lvOnExit;
555 pnkfelix 1.1.2.110 evictables = new HashMap(b.statements().size());
556 pnkfelix 1.1.2.110 if (!TIME) {
557 pnkfelix 1.1.2.110 buildNextRef();
558 pnkfelix 1.1.2.110 buildPreassignMap();
559 pnkfelix 1.1.2.110 makeTempSets();
560 pnkfelix 1.1.2.110 buildTempSets();
561 pnkfelix 1.1.2.110 }
562 pnkfelix 1.1.2.110 }
563 pnkfelix 1.1.2.110
564 pnkfelix 1.1.2.110 void buildNextRef() {
565 pnkfelix 1.1.2.110 nextRef = buildNextRef(block);
566 pnkfelix 1.1.2.110 }
567 pnkfelix 1.1.2.110
568 pnkfelix 1.1.2.110 void buildPreassignMap() {
569 pnkfelix 1.1.2.110 preassignMap = buildPreassignMap(block, allRegC, liveOnExit);
570 pnkfelix 1.1.2.110 }
571 pnkfelix 1.1.2.110
572 pnkfelix 1.1.2.110 void makeTempSets() {
573 pnkfelix 1.1.2.104 tempSets = EqTempSets.make(LocalCffRegAlloc.this, false);
574 pnkfelix 1.1.2.110 }
575 pnkfelix 1.1.2.110
576 pnkfelix 1.1.2.110 void buildTempSets() {
577 pnkfelix 1.1.2.110 LocalCffRegAlloc.this.buildTempSets(tempSets, block);
578 pnkfelix 1.1.2.79 }
579 pnkfelix 1.1.2.79
580 pnkfelix 1.1.2.79 private Map buildNextRef(BasicBlock b) {
581 pnkfelix 1.1.2.79 // Temp:t -> the last Instr referencing t
582 pnkfelix 1.1.2.110 Map tempToLastRef = new HashMap(b.statements().size());
583 pnkfelix 1.1.2.79
584 pnkfelix 1.1.2.97 // (Temp:t, Instr:j) -> Int:index of Instr following j w/ ref(t)
585 pnkfelix 1.1.2.110 Map nextRef = new HashMap(b.statements().size());
586 pnkfelix 1.1.2.79
587 pnkfelix 1.1.2.79 Iterator instrs = b.statements().iterator();
588 pnkfelix 1.1.2.82 for(int c=0; instrs.hasNext(); c++) {
589 pnkfelix 1.1.2.79 Instr instr = (Instr) instrs.next();
590 pnkfelix 1.1.2.79 Iterator refs = getRefs(instr);
591 pnkfelix 1.1.2.79 while(refs.hasNext()) {
592 pnkfelix 1.1.2.79 Temp ref = (Temp) refs.next();
593 pnkfelix 1.1.2.79 Instr last = (Instr) tempToLastRef.get(ref);
594 pnkfelix 1.1.2.79 if (last != null) {
595 cananian 1.3.2.1 assert (2*c) <= (Integer.MAX_VALUE - 1) : "IntOverflow;change numeric rep in LRA";
596 pnkfelix 1.1.2.79 nextRef.put(new TempInstrPair(last, ref),
597 pnkfelix 1.1.2.79 new Integer(2*c));
598 pnkfelix 1.1.2.79 }
599 pnkfelix 1.1.2.79 tempToLastRef.put(ref, instr);
600 pnkfelix 1.1.2.79 }
601 pnkfelix 1.1.2.79 }
602 pnkfelix 1.1.2.82
603 cananian 1.7 for (Object entryO : tempToLastRef.entrySet()) {
604 cananian 1.7 Map.Entry entry = (Map.Entry) entryO;
605 pnkfelix 1.1.2.79
606 pnkfelix 1.1.2.82 // enforcing the storage of NULL in nextRef only
607 pnkfelix 1.1.2.82 // for dead Temps, so that they can be distinquished.
608 pnkfelix 1.1.2.82 if (liveOnExit.contains(entry.getKey()))
609 pnkfelix 1.1.2.79 nextRef.put(new TempInstrPair((Temp)entry.getKey(),
610 pnkfelix 1.1.2.79 (Instr)entry.getValue()),
611 pnkfelix 1.1.2.79 INFINITY);
612 pnkfelix 1.1.2.79 }
613 pnkfelix 1.1.2.79 return nextRef;
614 pnkfelix 1.1.2.54 }
615 pnkfelix 1.1.2.75
616 pnkfelix 1.1.2.75 /** Generates a mapping from each temp in <code>block</code>
617 pnkfelix 1.1.2.75 to the set of preassigned registers conflicting with that
618 pnkfelix 1.1.2.75 temp.
619 pnkfelix 1.1.2.75
620 pnkfelix 1.1.2.75 @param block basic block to build the map from
621 pnkfelix 1.1.2.82 @param regs universe of register Temps that may be
622 pnkfelix 1.1.2.82 preassigned
623 pnkfelix 1.1.2.82 @param liveOnExit set of Temps (including register Temps)
624 pnkfelix 1.1.2.82 that are live on exit from <code>block</code>
625 pnkfelix 1.1.2.75 */
626 pnkfelix 1.1.2.82 MultiMap buildPreassignMap(BasicBlock block,
627 pnkfelix 1.1.2.82 Collection regs, Set liveOnExit) {
628 pnkfelix 1.1.2.110 // FSK: there are a lot of hacks strewn throughout this
629 pnkfelix 1.1.2.110 // method, but in the end we're probably STILL doing too
630 pnkfelix 1.1.2.110 // much redundant computation. look into fixing either
631 pnkfelix 1.1.2.110 // preassignMap's construction (here) or changing the code
632 pnkfelix 1.1.2.110 // that uses it...
633 pnkfelix 1.1.2.110
634 pnkfelix 1.1.2.75 List bl = block.statements();
635 pnkfelix 1.1.2.110 // SetFactory regSetFact =
636 pnkfelix 1.1.2.110 // new BitSetFactory(new LinearSet(new HashSet(regs)));
637 pnkfelix 1.1.2.110 BitSetFactory regSetFact =
638 pnkfelix 1.1.2.110 new BitSetFactory((new HashSet(regs)));
639 pnkfelix 1.1.2.75
640 cananian 1.1.2.117 MultiMap tempToRegs = new GenericMultiMap(regSetFact);
641 pnkfelix 1.1.2.59
642 pnkfelix 1.1.2.89 HashSet liveTempSet = new HashSet(liveOnExit);
643 pnkfelix 1.1.2.110 liveTempSet.removeAll(allRegC);
644 pnkfelix 1.1.2.110
645 pnkfelix 1.1.2.75 Set liveRegsOnExit = new HashSet(liveOnExit);
646 pnkfelix 1.1.2.75 liveRegsOnExit.retainAll(regs);
647 pnkfelix 1.1.2.75
648 pnkfelix 1.1.2.75 Set liveRegs = regSetFact.makeSet(liveRegsOnExit);
649 pnkfelix 1.1.2.75
650 pnkfelix 1.1.2.89 updateMapping(tempToRegs, liveTempSet, liveRegs,
651 cananian 1.6 net.cscott.jutil.Default.EMPTY_MAP);
652 pnkfelix 1.1.2.75
653 pnkfelix 1.1.2.75 // doing a reverse iteration
654 pnkfelix 1.1.2.75 ListIterator liter = bl.listIterator(bl.size());
655 pnkfelix 1.1.2.75 while(liter.hasPrevious()) {
656 pnkfelix 1.1.2.75 Instr i = (Instr) liter.previous();
657 pnkfelix 1.1.2.75
658 pnkfelix 1.1.2.89 if (PREASSIGN_INFO)
659 pnkfelix 1.1.2.89 System.out.println("Instr:"+i+" ");
660 pnkfelix 1.1.2.89
661 pnkfelix 1.1.2.89 boolean regchanged = false;
662 pnkfelix 1.1.2.89 boolean tmpchanged = false;
663 pnkfelix 1.1.2.89
664 pnkfelix 1.1.2.89 // consider making `exceptions' a MultiMap...
665 pnkfelix 1.1.2.110 HashMap exceptions = new HashMap(4);
666 pnkfelix 1.1.2.80 if (i instanceof InstrMOVE) {
667 pnkfelix 1.1.2.89 List dl = expand(i.def()[0]);
668 pnkfelix 1.1.2.89 List ul = expand(i.use()[0]);
669 pnkfelix 1.1.2.89
670 cananian 1.3.2.1 assert dl.size() == ul.size();
671 pnkfelix 1.1.2.89 Iterator ds = dl.iterator();
672 pnkfelix 1.1.2.89 Iterator us = ul.iterator();
673 pnkfelix 1.1.2.89
674 pnkfelix 1.1.2.89 while (ds.hasNext()) {
675 pnkfelix 1.1.2.89 Temp d = (Temp) ds.next();
676 pnkfelix 1.1.2.89 Temp u = (Temp) us.next();
677 pnkfelix 1.1.2.89 if (isRegister(d)) {
678 pnkfelix 1.1.2.89 exceptions.put(u, d);
679 pnkfelix 1.1.2.89 } else if (isRegister(u)) {
680 pnkfelix 1.1.2.89 exceptions.put(d, u);
681 pnkfelix 1.1.2.89 }
682 pnkfelix 1.1.2.80 }
683 pnkfelix 1.1.2.89 }
684 pnkfelix 1.1.2.75
685 pnkfelix 1.1.2.75 // make new copy of live
686 pnkfelix 1.1.2.75 liveRegs = regSetFact.makeSet(liveRegs);
687 pnkfelix 1.1.2.75
688 pnkfelix 1.1.2.75 { // liveRegs: kill (regs /\ defs)
689 pnkfelix 1.1.2.110 Set defRegs = regSetFact.makeFullSet();
690 pnkfelix 1.1.2.75 defRegs.retainAll(i.defC());
691 pnkfelix 1.1.2.110 liveRegs.removeAll(defRegs);
692 pnkfelix 1.1.2.75
693 pnkfelix 1.1.2.75 // some regs are clobbered by routines, and thus
694 pnkfelix 1.1.2.89 // appear in a defset but are never used. We
695 pnkfelix 1.1.2.75 // consider these to be impulse signals, and must
696 pnkfelix 1.1.2.75 // be added to the set of conflicts accordingly
697 pnkfelix 1.1.2.75 if (!defRegs.isEmpty()) {
698 pnkfelix 1.1.2.89 updateMapping(tempToRegs,liveTempSet,
699 pnkfelix 1.1.2.89 defRegs,exceptions);
700 pnkfelix 1.1.2.75 }
701 pnkfelix 1.1.2.75 }
702 pnkfelix 1.1.2.75
703 pnkfelix 1.1.2.89 liveTempSet.removeAll(i.defC()); // kill defs
704 pnkfelix 1.1.2.110
705 pnkfelix 1.1.2.110 Set usesNoRegs = new HashSet(i.useC());
706 pnkfelix 1.1.2.110 usesNoRegs.removeAll(allRegC);
707 pnkfelix 1.1.2.110 tmpchanged |= liveTempSet.addAll(usesNoRegs); // add uses
708 pnkfelix 1.1.2.75
709 pnkfelix 1.1.2.75 { // liveRegs: add (regs /\ uses)
710 pnkfelix 1.1.2.110 Set useRegs = regSetFact.makeFullSet();
711 pnkfelix 1.1.2.75 useRegs.retainAll(i.useC());
712 pnkfelix 1.1.2.89 regchanged |= liveRegs.addAll(useRegs);
713 pnkfelix 1.1.2.89 }
714 pnkfelix 1.1.2.89
715 pnkfelix 1.1.2.89 // FSK: optimization to filter debug output (but
716 pnkfelix 1.1.2.89 // should result in faster execution times...). Need
717 pnkfelix 1.1.2.89 // to VERIFY CORRECTNESS though
718 pnkfelix 1.1.2.89 if ( regchanged ) {
719 pnkfelix 1.1.2.89 updateMapping(tempToRegs,liveTempSet,
720 pnkfelix 1.1.2.89 liveRegs,exceptions);
721 pnkfelix 1.1.2.89 } else if ( tmpchanged ) {
722 pnkfelix 1.1.2.89 // hack: if only temps changed, can make iteration
723 pnkfelix 1.1.2.89 // loop significantly smaller by only traversing
724 pnkfelix 1.1.2.89 // differential
725 pnkfelix 1.1.2.89 updateMapping(tempToRegs,i.useC(),
726 pnkfelix 1.1.2.89 liveRegs,exceptions);
727 pnkfelix 1.1.2.75 }
728 pnkfelix 1.1.2.75 }
729 pnkfelix 1.1.2.75
730 pnkfelix 1.1.2.75 return tempToRegs;
731 pnkfelix 1.1.2.75 }
732 pnkfelix 1.1.2.75
733 pnkfelix 1.1.2.89 /** adds `liveRegs' to all the conflicting regs
734 pnkfelix 1.1.2.89 for `liveTempC', excluding the mappings in `excepts'.
735 pnkfelix 1.1.2.89 requires: excepts is a Temp -> Temp map
736 pnkfelix 1.1.2.80 effects:
737 pnkfelix 1.1.2.89 for each t in `liveTempC'
738 pnkfelix 1.1.2.89 let regs = if (t in `excepts.keySet')
739 pnkfelix 1.1.2.89 then `liveRegs' - `excepts.get(t)'
740 pnkfelix 1.1.2.80 else `liveRegs'
741 pnkfelix 1.1.2.80 in adds regs to `tempToRegs'.get(t)
742 pnkfelix 1.1.2.75 */
743 pnkfelix 1.1.2.89 private void updateMapping(MultiMap tempToRegs,
744 pnkfelix 1.1.2.89 Collection liveTempC,
745 pnkfelix 1.1.2.89 Set liveRegs, Map excepts) {
746 pnkfelix 1.1.2.80 if (liveRegs.isEmpty()) return;
747 pnkfelix 1.1.2.110 if (liveTempC.isEmpty()) return;
748 pnkfelix 1.1.2.110
749 pnkfelix 1.1.2.110 if(false)System.out.println("\nadding "+liveRegs+" to conflicts for "+
750 pnkfelix 1.1.2.110 liveTempC+" excluding "+excepts);
751 pnkfelix 1.1.2.110
752 cananian 1.7 for (Object tO : liveTempC) {
753 cananian 1.7 Temp t = (Temp) tO;
754 pnkfelix 1.1.2.89 if (isRegister(t)) continue;
755 pnkfelix 1.1.2.89
756 pnkfelix 1.1.2.89 if (excepts.containsKey(t)) {
757 pnkfelix 1.1.2.89 Temp r = (Temp) excepts.get(t);
758 pnkfelix 1.1.2.89 liveRegs.remove(r);
759 pnkfelix 1.1.2.80 tempToRegs.addAll(t, liveRegs);
760 pnkfelix 1.1.2.89 liveRegs.add(r);
761 pnkfelix 1.1.2.80 } else {
762 pnkfelix 1.1.2.80 tempToRegs.addAll(t, liveRegs);
763 pnkfelix 1.1.2.80 }
764 pnkfelix 1.1.2.75 }
765 pnkfelix 1.1.2.75 }
766 pnkfelix 1.1.2.75
767 pnkfelix 1.1.2.108 // runs once / block
768 pnkfelix 1.1.2.110 Instr alloc() {
769 pnkfelix 1.1.2.82 Iterator instrs = block.statements().iterator();
770 pnkfelix 1.1.2.82 InstrAlloc allocV = new InstrAlloc();
771 pnkfelix 1.1.2.54 while(instrs.hasNext()) {
772 pnkfelix 1.1.2.82 allocV.iloc = curr = (Instr) instrs.next();
773 pnkfelix 1.1.2.75
774 pnkfelix 1.1.2.82 // Temp remapping code for `curr'
775 pnkfelix 1.1.2.82 if (instrHasRemappedTemps(curr)) {
776 pnkfelix 1.1.2.82 Instr oldi = curr;
777 pnkfelix 1.1.2.82 Instr newi = curr.rename(remappedTemps);
778 pnkfelix 1.1.2.82 instrsToReplace.add(oldi);
779 pnkfelix 1.1.2.82 instrsToReplace.add(newi);
780 pnkfelix 1.1.2.101 back(newi, oldi);
781 pnkfelix 1.1.2.75
782 pnkfelix 1.1.2.82 curr = newi;
783 pnkfelix 1.1.2.82 allocV.iloc = oldi;
784 pnkfelix 1.1.2.82 }
785 pnkfelix 1.1.2.82
786 pnkfelix 1.1.2.97 instrToHTempMap.put(curr, coalescedTemps);
787 pnkfelix 1.1.2.82 curr.accept(allocV);
788 pnkfelix 1.1.2.88 // System.out.println(curr + " ("+allocV.iloc+")");
789 pnkfelix 1.1.2.103 if (false && TIME) System.out.print(".");
790 pnkfelix 1.1.2.82 }
791 pnkfelix 1.1.2.110
792 pnkfelix 1.1.2.110 return allocV.iloc;
793 pnkfelix 1.1.2.59 }
794 pnkfelix 1.1.2.82
795 pnkfelix 1.1.2.82 private boolean instrHasRemappedTemps(Instr i) {
796 pnkfelix 1.1.2.82 Collection uses = new HashSet(i.useC());
797 pnkfelix 1.1.2.82 Collection defs = new HashSet(i.defC());
798 pnkfelix 1.1.2.82 uses.retainAll(remappedTemps.keySet());
799 pnkfelix 1.1.2.82 defs.retainAll(remappedTemps.keySet());
800 pnkfelix 1.1.2.82 return (!uses.isEmpty() || !defs.isEmpty());
801 pnkfelix 1.1.2.82 }
802 pnkfelix 1.1.2.82
803 pnkfelix 1.1.2.82 class InstrAlloc extends harpoon.IR.Assem.InstrVisitor {
804 pnkfelix 1.1.2.82
805 pnkfelix 1.1.2.82 // planned target location for visited Instr.
806 pnkfelix 1.1.2.82 Instr iloc;
807 pnkfelix 1.1.2.82 // FSK: Totally ruins the cleanness of the visitor
808 pnkfelix 1.1.2.82 // abstraction; this code should be rewritten using a
809 pnkfelix 1.1.2.82 // different framework since there doesn't seem to be a
810 pnkfelix 1.1.2.82 // clean way to incorporate these two (potentially)
811 pnkfelix 1.1.2.82 // independent pieces of the state.
812 pnkfelix 1.1.2.74
813 pnkfelix 1.1.2.75
814 pnkfelix 1.1.2.77 // filters out hardcoded refs to machine registers
815 pnkfelix 1.1.2.77 class MRegFilter extends FilterIterator.Filter {
816 pnkfelix 1.1.2.77 public boolean isElement(Object o) {
817 pnkfelix 1.1.2.82 return !isRegister((Temp) o);
818 pnkfelix 1.1.2.77 }
819 pnkfelix 1.1.2.77 }
820 pnkfelix 1.1.2.77
821 pnkfelix 1.1.2.108 // runs once / instr
822 pnkfelix 1.1.2.80 /** modifies: `regfile', `evictables'
823 pnkfelix 1.1.2.80 */
824 pnkfelix 1.1.2.78 public void visit(final Instr i) {
825 pnkfelix 1.1.2.78 Map putBackLater = takeUsesOutOfEvictables(i);
826 pnkfelix 1.1.2.77
827 pnkfelix 1.1.2.77 Iterator refs =
828 pnkfelix 1.1.2.77 new FilterIterator(getRefs(i), new MRegFilter());
829 pnkfelix 1.1.2.77
830 pnkfelix 1.1.2.77 while(refs.hasNext()) {
831 pnkfelix 1.1.2.77 Temp t = (Temp) refs.next();
832 pnkfelix 1.1.2.77 assign(t, i, putBackLater);
833 pnkfelix 1.1.2.63 }
834 pnkfelix 1.1.2.63
835 cananian 1.7 for (Object defO : i.defC()) {
836 cananian 1.7 Temp def = (Temp) defO;
837 pnkfelix 1.1.2.82 if (!isRegister(def)) {
838 pnkfelix 1.1.2.82 regfile.writeTo(def);
839 pnkfelix 1.1.2.83 // System.out.println("Dirtifying "+def+" by "+i);
840 pnkfelix 1.1.2.82 } else /* def is a register */ {
841 pnkfelix 1.1.2.79 Temp t = regfile.getTemp(def);
842 pnkfelix 1.1.2.80 if (t != null) {
843 pnkfelix 1.1.2.82 if (liveOnExit.contains(t)) {
844 pnkfelix 1.1.2.80 System.out.println("\tWTF?!? removing " +
845 pnkfelix 1.1.2.80 t + " from " + regfile
846 pnkfelix 1.1.2.89 + " for " + i + ", "+
847 pnkfelix 1.1.2.89 "preassigned to "+
848 pnkfelix 1.1.2.89 preassignMap.get(t)+
849 pnkfelix 1.1.2.89 " i defs "+new HashSet(i.defC()));
850 pnkfelix 1.1.2.82 Instr prev = iloc.getPrev();
851 pnkfelix 1.1.2.80
852 pnkfelix 1.1.2.80 // FSK: update code to do something
853 pnkfelix 1.1.2.80 // smarter (and more general)
854 cananian 1.3.2.1 assert prev.canFallThrough &&
855 pnkfelix 1.1.2.80 prev.getTargets().isEmpty() &&
856 cananian 1.3.2.1 i.predC().size() == 1 : "i.getPrev is bad choice;";
857 pnkfelix 1.1.2.80
858 pnkfelix 1.1.2.82 spillValue(t, prev, regfile, 5);
859 pnkfelix 1.1.2.89
860 pnkfelix 1.1.2.89 // extract extra information
861 pnkfelix 1.1.2.89 while(!prev.defC().contains(t) &&
862 pnkfelix 1.1.2.89 prev.predC().size() == 1)
863 pnkfelix 1.1.2.89 prev = prev.getPrev();
864 pnkfelix 1.1.2.89 if (prev.defC().contains(t))
865 pnkfelix 1.1.2.89 System.out.println(t+" defined by "+prev);
866 pnkfelix 1.1.2.89 else
867 pnkfelix 1.1.2.89 System.out.println(t+" not def'd in BB");
868 pnkfelix 1.1.2.80 }
869 pnkfelix 1.1.2.80 regfile.remove(t);
870 pnkfelix 1.1.2.80 }
871 pnkfelix 1.1.2.79 }
872 pnkfelix 1.1.2.77 }
873 pnkfelix 1.1.2.77
874 pnkfelix 1.1.2.77 evictables.putAll(putBackLater);
875 pnkfelix 1.1.2.77
876 cananian 1.3.2.1 assert hasRegs(i, i.useC()) : (ASSERTDB ?
877 pnkfelix 1.1.2.107 lazyInfo("uses missing reg assignment",i,null)
878 pnkfelix 1.1.2.107 : "uses missing reg assignment");
879 cananian 1.3.2.1 assert hasRegs(i, i.defC()) : (ASSERTDB ?
880 pnkfelix 1.1.2.107 lazyInfo("defs missing reg assignment",i,null)
881 pnkfelix 1.1.2.107 : "defs missing reg assingment");
882 pnkfelix 1.1.2.78
883 pnkfelix 1.1.2.88 checked.add(i);
884 pnkfelix 1.1.2.77 }
885 pnkfelix 1.1.2.108
886 pnkfelix 1.1.2.108 // runs once / instr
887 pnkfelix 1.1.2.77 /** Removes uses of i from `evictables'.
888 pnkfelix 1.1.2.77 modifies: `evictables'
889 pnkfelix 1.1.2.77 effects: Takes any temp used by `i' out of the keyset
890 pnkfelix 1.1.2.77 for `evictables', returning a map holding the
891 pnkfelix 1.1.2.77 removed mappings (for later reinsertion into
892 pnkfelix 1.1.2.77 `evictables'). This way temps used by `i'
893 pnkfelix 1.1.2.77 will not be considered candidates for
894 pnkfelix 1.1.2.77 eviction from the register file.
895 pnkfelix 1.1.2.77 */
896 pnkfelix 1.1.2.78 private Map takeUsesOutOfEvictables(Instr i) {
897 pnkfelix 1.1.2.110 Map putBackLater = new HashMap(i.useC().size());
898 pnkfelix 1.1.2.63 Iterator uses = new FilterIterator(i.useC().iterator(),
899 pnkfelix 1.1.2.63 new MRegFilter());
900 pnkfelix 1.1.2.63 while(uses.hasNext()) {
901 pnkfelix 1.1.2.82 Temp use = (Temp) uses.next();
902 pnkfelix 1.1.2.63 if (evictables.containsKey(use)) {
903 pnkfelix 1.1.2.63 putBackLater.put(use, evictables.get(use));
904 pnkfelix 1.1.2.63 evictables.remove(use);
905 pnkfelix 1.1.2.63 }
906 pnkfelix 1.1.2.63 }
907 pnkfelix 1.1.2.77 return putBackLater;
908 pnkfelix 1.1.2.77 }
909 pnkfelix 1.1.2.82
910 pnkfelix 1.1.2.108 // runs once / ref / instr
911 pnkfelix 1.1.2.77 /** Assigns `t' in `i'.
912 pnkfelix 1.1.2.77 modifies: `code', `evictables', `regfile', `putBackLater'
913 pnkfelix 1.1.2.77 effects:
914 pnkfelix 1.1.2.78 1. if (`t' unassigned) then finds reg assignment
915 pnkfelix 1.1.2.78 for `t' (potentially spilling values in
916 pnkfelix 1.1.2.78 `evictables' to make room for `t')
917 pnkfelix 1.1.2.77 2. Updates structures to reflect assignment for `t'
918 pnkfelix 1.1.2.79 3. if (`t' used by `i' but not in regfile) then adds LOAD `t'
919 pnkfelix 1.1.2.79 4. if (`t' used by `i') then puts `t' into
920 pnkfelix 1.1.2.78 `putBackLater' else puts `t' into `evictables'
921 pnkfelix 1.1.2.77 */
922 pnkfelix 1.1.2.77 private void assign(Temp t, Instr i, Map putBackLater) {
923 pnkfelix 1.1.2.82 if (remappedTemps.keySet().contains(t)) {
924 pnkfelix 1.1.2.82 t = (Temp) remappedTemps.get(t);
925 pnkfelix 1.1.2.82 }
926 pnkfelix 1.1.2.75
927 pnkfelix 1.1.2.82 if (regfile.hasAssignment(t)) {
928 pnkfelix 1.1.2.82
929 pnkfelix 1.1.2.110 // System.out.print(" P");
930 pnkfelix 1.1.2.82 code.assignRegister(i, t, regfile.getAssignment(t));
931 pnkfelix 1.1.2.82 evictables.remove(t); // (`t' reinserted later)
932 pnkfelix 1.1.2.82
933 pnkfelix 1.1.2.77 } else { /* not already assigned */
934 pnkfelix 1.1.2.77
935 pnkfelix 1.1.2.77 Set preassigns = addPreassignments(t);
936 pnkfelix 1.1.2.111 Iterator suggs =
937 pnkfelix 1.1.2.111 getSuggestions(t, regfile, i, evictables, iloc);
938 pnkfelix 1.1.2.111
939 pnkfelix 1.1.2.111
940 pnkfelix 1.1.2.77 List regList = chooseSuggestion(suggs, t);
941 pnkfelix 1.1.2.63
942 pnkfelix 1.1.2.77 if (i.useC().contains(t)) {
943 pnkfelix 1.1.2.82 InstrMEM load =
944 pnkfelix 1.1.2.82 SpillLoad.makeLD(i, "FSK-LD", regList, t);
945 pnkfelix 1.1.2.82 // System.out.println("adding "+load+" to "+regfile);
946 pnkfelix 1.1.2.77 spillLoads.add(load);
947 pnkfelix 1.1.2.82 spillLoads.add(iloc);
948 pnkfelix 1.1.2.100 back(load, i);
949 pnkfelix 1.1.2.97 instrToHTempMap.put(load, coalescedTemps);
950 pnkfelix 1.1.2.77 }
951 pnkfelix 1.1.2.75
952 pnkfelix 1.1.2.82 code.assignRegister(i, t, regList);
953 pnkfelix 1.1.2.91
954 pnkfelix 1.1.2.101 regfile.assign(t, regList, definition(getBack(i),t));
955 pnkfelix 1.1.2.96
956 pnkfelix 1.1.2.82
957 pnkfelix 1.1.2.77 // remove preassignments
958 pnkfelix 1.1.2.77 Iterator preassignIter = preassigns.iterator();
959 pnkfelix 1.1.2.77 while(preassignIter.hasNext()) {
960 pnkfelix 1.1.2.77 regfile.remove((Temp) preassignIter.next());
961 pnkfelix 1.1.2.54 }
962 pnkfelix 1.1.2.77
963 pnkfelix 1.1.2.77 }
964 pnkfelix 1.1.2.82
965 pnkfelix 1.1.2.77 // at this point, 't' has an assignment and needs
966 pnkfelix 1.1.2.77 // to be entered into the 'evictables' pool
967 pnkfelix 1.1.2.77 Integer X = findWeight(t, i);
968 pnkfelix 1.1.2.59
969 pnkfelix 1.1.2.77 // don't accidentally make `t' an eviction candidate
970 pnkfelix 1.1.2.77 if (i.useC().contains(t)) {
971 pnkfelix 1.1.2.82 putBackLater.put(t, X);
972 pnkfelix 1.1.2.77 } else {
973 pnkfelix 1.1.2.82 evictables.put(t, X);
974 pnkfelix 1.1.2.54 }
975 pnkfelix 1.1.2.77 }
976 pnkfelix 1.1.2.82
977 pnkfelix 1.1.2.108 // runs once / ref / instr
978 pnkfelix 1.1.2.77 /** Adds conflicting preassigned registers to `regfile'.
979 pnkfelix 1.1.2.77 modifies: `regfile'
980 pnkfelix 1.1.2.77 effects:
981 pnkfelix 1.1.2.77 let regs = values mapped to by `t' in `preassignMap'
982 pnkfelix 1.1.2.77 tmps = new empty set of Temps
983 pnkfelix 1.1.2.77 in for each r in regs
984 pnkfelix 1.1.2.79 if r is empty in `regfile'
985 pnkfelix 1.1.2.79 then let p = a new PreassignTemp for r
986 pnkfelix 1.1.2.79 in assigns p to r
987 pnkfelix 1.1.2.79 adds p to tmps
988 pnkfelix 1.1.2.77 returns tmps
989 pnkfelix 1.1.2.77 */
990 pnkfelix 1.1.2.78 private Set addPreassignments(final Temp t) {
991 pnkfelix 1.1.2.77 Collection preassigns = preassignMap.getValues(t);
992 pnkfelix 1.1.2.110 Set preassignTempSet = new HashSet(preassigns.size());
993 pnkfelix 1.1.2.77
994 cananian 1.3.2.1 assert preassigns != null : "preassignMap is missing mappings";
995 pnkfelix 1.1.2.77 Iterator preassignIter = preassigns.iterator();
996 pnkfelix 1.1.2.77 while(preassignIter.hasNext()) {
997 pnkfelix 1.1.2.78 final Temp reg = (Temp) preassignIter.next();
998 pnkfelix 1.1.2.78
999 pnkfelix 1.1.2.79 if (regfile.isEmpty(reg)) {
1000 pnkfelix 1.1.2.119 Temp preassign = new PreassignTemp(reg);
1001 pnkfelix 1.1.2.119 preassignedTemps.add(preassign);
1002 pnkfelix 1.1.2.91
1003 pnkfelix 1.1.2.95 // preassigntemps should never be spilled, so
1004 pnkfelix 1.1.2.95 // their sources should never be accessed, so
1005 pnkfelix 1.1.2.95 // 'null' should be safe to add...
1006 pnkfelix 1.1.2.95 regfile.assign( preassign, list(reg) , null);
1007 pnkfelix 1.1.2.78 preassignTempSet.add(preassign);
1008 pnkfelix 1.1.2.78 }
1009 pnkfelix 1.1.2.77 }
1010 pnkfelix 1.1.2.82
1011 pnkfelix 1.1.2.77 return preassignTempSet;
1012 pnkfelix 1.1.2.54 }
1013 pnkfelix 1.1.2.82
1014 pnkfelix 1.1.2.79 /** Finds the weight of `t' when used at `i'.
1015 pnkfelix 1.1.2.79 requires: `t' is used by `i'
1016 pnkfelix 1.1.2.82 `t' has an assignment in `regfile'
1017 pnkfelix 1.1.2.79 effects: let w = 2*(distance until the next use)
1018 pnkfelix 1.1.2.79 in if `t' is dirty
1019 pnkfelix 1.1.2.79 then returns (w+1)
1020 pnkfelix 1.1.2.79 else returns w
1021 pnkfelix 1.1.2.79 */
1022 pnkfelix 1.1.2.79 private Integer findWeight(Temp t, Instr i) {
1023 pnkfelix 1.1.2.79 Integer X = (Integer) nextRef.get(new TempInstrPair(i, t));
1024 pnkfelix 1.1.2.79
1025 pnkfelix 1.1.2.79 // null => never referenced again; effectively infinite
1026 pnkfelix 1.1.2.79 if (X == null) X = INFINITY;
1027 pnkfelix 1.1.2.79
1028 cananian 1.3.2.1 assert X.intValue() <= (Integer.MAX_VALUE - 1) : "Excessive Weight was stored.";
1029 pnkfelix 1.1.2.79
1030 cananian 1.3.2.1 assert regfile.hasAssignment(t) : (ASSERTDB ? lazyInfo("no assignment", i, t)
1031 pnkfelix 1.1.2.107 : "no assignment");
1032 pnkfelix 1.1.2.82
1033 pnkfelix 1.1.2.82 if (regfile.isDirty(t)) {
1034 pnkfelix 1.1.2.79 X = new Integer(X.intValue() + 1);
1035 pnkfelix 1.1.2.79 }
1036 pnkfelix 1.1.2.79
1037 pnkfelix 1.1.2.79 return X;
1038 pnkfelix 1.1.2.79 }
1039 pnkfelix 1.1.2.108
1040 pnkfelix 1.1.2.108 // runs once / instr
1041 pnkfelix 1.1.2.75 public void visit(final InstrMOVE i) {
1042 pnkfelix 1.1.2.96 if (!COALESCE_MOVES) {
1043 pnkfelix 1.1.2.96 super.visit(i);
1044 pnkfelix 1.1.2.96 return;
1045 pnkfelix 1.1.2.96 }
1046 pnkfelix 1.1.2.96
1047 pnkfelix 1.1.2.78 final Temp u = i.use()[0];
1048 pnkfelix 1.1.2.78 final Temp d = i.def()[0];
1049 pnkfelix 1.1.2.78 Map putBackLater = takeUsesOutOfEvictables(i);
1050 pnkfelix 1.1.2.78
1051 pnkfelix 1.1.2.82 if (!isRegister(u) &&
1052 pnkfelix 1.1.2.82 !regfile.hasAssignment(u)) {
1053 pnkfelix 1.1.2.78 // load that value into a register...
1054 pnkfelix 1.1.2.78 assign(u, i, putBackLater);
1055 pnkfelix 1.1.2.82 }
1056 pnkfelix 1.1.2.82
1057 cananian 1.3.2.1 assert isRegister(u) || regfile.hasAssignment(u);
1058 pnkfelix 1.1.2.61
1059 pnkfelix 1.1.2.78 int choice = 0;
1060 pnkfelix 1.1.2.78
1061 pnkfelix 1.1.2.82 coalesceChoice: {
1062 pnkfelix 1.1.2.82 // FSK: overconservative
1063 cananian 1.3.2.1 // assert u == d || !regfile.hasAssignment(d);
1064 pnkfelix 1.1.2.83 if (regfile.hasAssignment(d) && u != d) {
1065 pnkfelix 1.1.2.82 // rare (due to SSI-form) but it happens.
1066 pnkfelix 1.1.2.83 // System.out.println("not coalescing "+i+" (redefinition pt)");
1067 pnkfelix 1.1.2.82 break coalesceChoice;
1068 pnkfelix 1.1.2.82 }
1069 pnkfelix 1.1.2.82
1070 pnkfelix 1.1.2.82 if (isRegister(d) &&
1071 pnkfelix 1.1.2.82 regfile.getAssignment(u).get(0) == d) {
1072 pnkfelix 1.1.2.82 choice = 1;
1073 pnkfelix 1.1.2.82 break coalesceChoice;
1074 pnkfelix 1.1.2.82 }
1075 pnkfelix 1.1.2.78
1076 pnkfelix 1.1.2.82 if (isRegister(u) &&
1077 pnkfelix 1.1.2.82 !preassignMap.getValues(d).contains(u)) {
1078 pnkfelix 1.1.2.82 choice = 2;
1079 pnkfelix 1.1.2.82 break coalesceChoice;
1080 pnkfelix 1.1.2.82 }
1081 pnkfelix 1.1.2.82
1082 pnkfelix 1.1.2.82 if (u == d) {
1083 pnkfelix 1.1.2.82 choice = 3;
1084 pnkfelix 1.1.2.82 break coalesceChoice;
1085 pnkfelix 1.1.2.82 }
1086 pnkfelix 1.1.2.82
1087 pnkfelix 1.1.2.82 if (isRegister(d) || isRegister(u)) {
1088 pnkfelix 1.1.2.82 break coalesceChoice;
1089 pnkfelix 1.1.2.82 }
1090 pnkfelix 1.1.2.82
1091 pnkfelix 1.1.2.82 // u and d are not registers...
1092 pnkfelix 1.1.2.82 Collection uregs = regfile.getAssignment(u);
1093 pnkfelix 1.1.2.82 Collection conflicting = new HashSet(uregs);
1094 pnkfelix 1.1.2.82 conflicting.retainAll(preassignMap.getValues(d));
1095 pnkfelix 1.1.2.82 if (conflicting.isEmpty()) {
1096 pnkfelix 1.1.2.82 choice = 4;
1097 pnkfelix 1.1.2.82 break coalesceChoice;
1098 pnkfelix 1.1.2.82 }
1099 pnkfelix 1.1.2.82 }
1100 pnkfelix 1.1.2.59
1101 pnkfelix 1.1.2.82 if (choice == 0) {
1102 pnkfelix 1.1.2.82 visit((Instr) i);
1103 pnkfelix 1.1.2.82 } else {
1104 cananian 1.3.2.1 assert isRegister(u) ||
1105 pnkfelix 1.1.2.82 isRegister(d) ||
1106 cananian 1.3.2.1 tempSets.getRep(u) == tempSets.getRep(d) : (ASSERTDB ?
1107 pnkfelix 1.1.2.82 "Temps "+u+" & "+d+
1108 pnkfelix 1.1.2.107 " should have same rep to be coalesced"
1109 pnkfelix 1.1.2.107 : "should have same rep to be coalesced");
1110 pnkfelix 1.1.2.82
1111 pnkfelix 1.1.2.82 List regList = isRegister(u)?
1112 pnkfelix 1.1.2.82 list(u):
1113 pnkfelix 1.1.2.82 regfile.getAssignment(u);
1114 pnkfelix 1.1.2.78 code.assignRegister(i, u, regList);
1115 pnkfelix 1.1.2.78 code.assignRegister(i, d, regList);
1116 pnkfelix 1.1.2.82
1117 pnkfelix 1.1.2.82 if (isRegister(u) || isRegister(d)) {
1118 pnkfelix 1.1.2.82 instrsToReplace.add(i);
1119 pnkfelix 1.1.2.115 Instr proxy;
1120 pnkfelix 1.1.2.115 if (isRegister(u)) {
1121 pnkfelix 1.1.2.115 proxy = new InstrMOVEproxy(i);
1122 pnkfelix 1.1.2.115 } else {
1123 pnkfelix 1.1.2.115 proxy = new InstrMOVEproxy(i);
1124 pnkfelix 1.1.2.115 }
1125 pnkfelix 1.1.2.82 instrsToReplace.add(proxy);
1126 pnkfelix 1.1.2.101 back(proxy, i);
1127 pnkfelix 1.1.2.88 checked.add(proxy);
1128 pnkfelix 1.1.2.97 instrToHTempMap.put(proxy, coalescedTemps);
1129 pnkfelix 1.1.2.82 if (isRegister(u)) {
1130 pnkfelix 1.1.2.82 code.assignRegister(proxy, d, list(u));
1131 pnkfelix 1.1.2.82 } else {
1132 cananian 1.3.2.1 assert isRegister(d);
1133 pnkfelix 1.1.2.82 code.assignRegister(proxy, u, list(d));
1134 pnkfelix 1.1.2.82 }
1135 pnkfelix 1.1.2.82 } else {
1136 pnkfelix 1.1.2.82 remove(i, choice);
1137 pnkfelix 1.1.2.94 coalescedTemps.put(d, coalescedTemps.get(u));
1138 pnkfelix 1.1.2.96 tempToRemovedInstrs.put(d, i);
1139 pnkfelix 1.1.2.82 }
1140 pnkfelix 1.1.2.78
1141 cananian 1.3.2.1 assert !(isRegister(u) && isRegister(d));
1142 pnkfelix 1.1.2.82
1143 pnkfelix 1.1.2.82 if (isRegister(u)) {
1144 pnkfelix 1.1.2.101 regfile.assign(d, list(u), definition(getBack(i),d));
1145 pnkfelix 1.1.2.82 regfile.writeTo(d);
1146 pnkfelix 1.1.2.82 } else if (isRegister(d)) {
1147 pnkfelix 1.1.2.82 if (regfile.getTemp(d) == null) {
1148 pnkfelix 1.1.2.82 // FSK: can this actually EVER work???
1149 pnkfelix 1.1.2.96 regfile.assign
1150 pnkfelix 1.1.2.101 (u, list(d), definition(getBack(i),u));
1151 pnkfelix 1.1.2.82 } else {
1152 cananian 1.3.2.1 assert regfile.getTemp(d) == u;
1153 pnkfelix 1.1.2.82 }
1154 pnkfelix 1.1.2.82 } else {
1155 pnkfelix 1.1.2.82 Temp t =
1156 pnkfelix 1.1.2.82 remappedTemps.keySet().contains(u)?
1157 pnkfelix 1.1.2.82 (Temp)remappedTemps.get(u):u;
1158 pnkfelix 1.1.2.82 remappedTemps.put(d, t);
1159 pnkfelix 1.1.2.82 }
1160 pnkfelix 1.1.2.75 // System.out.println("assigning "+i.def()[0] +
1161 pnkfelix 1.1.2.75 // " to "+regList);
1162 pnkfelix 1.1.2.59 }
1163 pnkfelix 1.1.2.78
1164 cananian 1.3.2.1 assert hasRegs(i, u) : (ASSERTDB ? lazyInfo("missing reg assignment",i,u)
1165 pnkfelix 1.1.2.107 : "missing reg assignment");
1166 pnkfelix 1.1.2.82
1167 pnkfelix 1.1.2.78 evictables.putAll(putBackLater);
1168 pnkfelix 1.1.2.54 }
1169 pnkfelix 1.1.2.82
1170 pnkfelix 1.1.2.75 private void remove(Instr i, int n) {
1171 pnkfelix 1.1.2.82 remove(i, n, false);
1172 pnkfelix 1.1.2.75 }
1173 pnkfelix 1.1.2.82
1174 pnkfelix 1.1.2.75 private void remove(Instr i, int n, boolean pr) {
1175 pnkfelix 1.1.2.75 instrsToRemove.add(i);
1176 pnkfelix 1.1.2.75 if (pr) System.out.println("removing"+n+" "+i+" rf: "+regfile);
1177 pnkfelix 1.1.2.75 }
1178 pnkfelix 1.1.2.54 }
1179 pnkfelix 1.1.2.82
1180 pnkfelix 1.1.2.108 // runs once / ref / instr
1181 pnkfelix 1.1.2.59 /** Gets an Iterator of suggested register assignments in
1182 pnkfelix 1.1.2.63 <code>regfile</code> for <code>t</code>. May insert
1183 pnkfelix 1.1.2.63 load/spill code before <code>i</code>. Uses
1184 pnkfelix 1.1.2.63 <code>evictables</code> as a <code>Map</code> from
1185 pnkfelix 1.1.2.63 <code>Temp</code>s to weighted distances to decide which
1186 pnkfelix 1.1.2.82 <code>Temp</code>s to spill, and <code>iloc</code> as the
1187 pnkfelix 1.1.2.82 proxy for the location where <code>i</code> will
1188 pnkfelix 1.1.2.82 eventually be located.
1189 pnkfelix 1.1.2.59 */
1190 pnkfelix 1.1.2.78 private Iterator getSuggestions(final Temp t, final RegFile regfile,
1191 pnkfelix 1.1.2.82 final Instr i, final Map evictables,
1192 pnkfelix 1.1.2.82 final Instr iloc) {
1193 pnkfelix 1.1.2.63 if (false) System.out.println("getting suggestions for "+t+
1194 pnkfelix 1.1.2.63 " in "+i+" with regfile "+regfile+
1195 pnkfelix 1.1.2.63 " and evictables "+evictables);
1196 pnkfelix 1.1.2.63
1197 pnkfelix 1.1.2.59 for(int x=0; true; x++) {
1198 cananian 1.3.2.1 assert x < 10 : "shouldn't have to iterate >10";
1199 pnkfelix 1.1.2.59
1200 pnkfelix 1.1.2.59 try {
1201 pnkfelix 1.1.2.78
1202 pnkfelix 1.1.2.111 Iterator assns =
1203 pnkfelix 1.1.2.59 frame.getRegFileInfo().suggestRegAssignment
1204 pnkfelix 1.1.2.119 (t, regfile.getRegToTemp(), preassignedTemps);
1205 pnkfelix 1.1.2.111
1206 pnkfelix 1.1.2.111 // Assignment Filter: remove *used* regs
1207 pnkfelix 1.1.2.111 assns = new FilterIterator
1208 pnkfelix 1.1.2.111 (assns, new FilterIterator.Filter() {
1209 pnkfelix 1.1.2.111 public boolean isElement(Object o) {
1210 pnkfelix 1.1.2.111 List l = new ArrayList((List) o);
1211 pnkfelix 1.1.2.111 Set conflicts = new LinearSet();
1212 pnkfelix 1.1.2.111 conflicts.addAll(preassignMap.getValues(t));
1213 pnkfelix 1.1.2.111 conflicts.addAll(regfile.getRegToTemp().keySet());
1214 pnkfelix 1.1.2.111 if (false)
1215 pnkfelix 1.1.2.111 System.out.println("assignment filter, "+
1216 pnkfelix 1.1.2.111 "conflicts: "+conflicts+
1217 pnkfelix 1.1.2.111 "suggestion: "+l);
1218 pnkfelix 1.1.2.111
1219 pnkfelix 1.1.2.111 return !l.removeAll(conflicts);
1220 pnkfelix 1.1.2.111 }
1221 pnkfelix 1.1.2.111 });
1222 pnkfelix 1.1.2.111 if (assns.hasNext()) {
1223 pnkfelix 1.1.2.111 return assns;
1224 pnkfelix 1.1.2.111 } else {
1225 pnkfelix 1.1.2.111 throw new SpillException() {
1226 pnkfelix 1.1.2.111 public Iterator getPotentialSpills() {
1227 pnkfelix 1.1.2.111 Iterator sggs;
1228 pnkfelix 1.1.2.111 try {
1229 pnkfelix 1.1.2.111 sggs = frame.getRegFileInfo().
1230 pnkfelix 1.1.2.111 suggestRegAssignment
1231 pnkfelix 1.1.2.119 (t, regfile.getRegToTemp(),
1232 pnkfelix 1.1.2.119 preassignedTemps);
1233 pnkfelix 1.1.2.111 } catch (SpillException e) {
1234 cananian 1.3.2.1 assert false : "cant happen here";
1235 pnkfelix 1.1.2.111 sggs = null;
1236 pnkfelix 1.1.2.111 }
1237 pnkfelix 1.1.2.111
1238 pnkfelix 1.1.2.111 // Spill Filter: remove *hardcoded* regs
1239 pnkfelix 1.1.2.111 sggs = new FilterIterator
1240 pnkfelix 1.1.2.111 (sggs, new FilterIterator.Filter() {
1241 pnkfelix 1.1.2.111 public boolean isElement(Object o) {
1242 pnkfelix 1.1.2.111 List l = new ArrayList((List)o);
1243 pnkfelix 1.1.2.111 Set conflicts=new LinearSet
1244 pnkfelix 1.1.2.111 ((Set)preassignMap.getValues(t));
1245 pnkfelix 1.1.2.111 return !l.removeAll(conflicts);
1246 pnkfelix 1.1.2.111 }
1247 pnkfelix 1.1.2.111 public Object map(Object o) {
1248 pnkfelix 1.1.2.111 List l = (List)o;
1249 pnkfelix 1.1.2.111 Set s = new LinearSet(l.size());
1250 pnkfelix 1.1.2.111 s.addAll(l);
1251 pnkfelix 1.1.2.111 return s;
1252 pnkfelix 1.1.2.111 }
1253 pnkfelix 1.1.2.111 });
1254 pnkfelix 1.1.2.111
1255 pnkfelix 1.1.2.111 return sggs;
1256 pnkfelix 1.1.2.111 }
1257 pnkfelix 1.1.2.111 };
1258 pnkfelix 1.1.2.111 }
1259 pnkfelix 1.1.2.59 } catch (SpillException s) {
1260 pnkfelix 1.1.2.78
1261 pnkfelix 1.1.2.59 Iterator spills = s.getPotentialSpills();
1262 pnkfelix 1.1.2.59 SortedSet weightedSpills = new TreeSet();
1263 pnkfelix 1.1.2.63
1264 pnkfelix 1.1.2.79 Collection preasnRegs = preassignMap.getValues(t);
1265 pnkfelix 1.1.2.79
1266 pnkfelix 1.1.2.59 while(spills.hasNext()) {
1267 pnkfelix 1.1.2.63 boolean valid = true;
1268 pnkfelix 1.1.2.59 Set cand = (Set) spills.next();
1269 pnkfelix 1.1.2.63
1270 pnkfelix 1.1.2.63
1271 pnkfelix 1.1.2.110 HashSet temps = new HashSet(5);
1272 pnkfelix 1.1.2.59 Iterator regs = cand.iterator();
1273 pnkfelix 1.1.2.63
1274 pnkfelix 1.1.2.59 int cost=Integer.MAX_VALUE;
1275 pnkfelix 1.1.2.59 while(regs.hasNext()) {
1276 pnkfelix 1.1.2.59 Temp reg = (Temp) regs.next();
1277 pnkfelix 1.1.2.59 Temp preg = regfile.getTemp(reg);
1278 pnkfelix 1.1.2.63
1279 pnkfelix 1.1.2.63 // did reg previously hold a value?
1280 pnkfelix 1.1.2.63 if (preg != null) {
1281 pnkfelix 1.1.2.63 temps.add(preg);
1282 pnkfelix 1.1.2.63 if (!evictables.containsKey(preg)) {
1283 pnkfelix 1.1.2.63 // --> disallowed evicting preg
1284 pnkfelix 1.1.2.63 valid = false;
1285 pnkfelix 1.1.2.79 break;
1286 pnkfelix 1.1.2.79 } else if (preasnRegs.contains(reg)) {
1287 pnkfelix 1.1.2.79 valid = false;
1288 pnkfelix 1.1.2.63 break;
1289 pnkfelix 1.1.2.79 }
1290 pnkfelix 1.1.2.63 Integer dist = (Integer) evictables.get(preg);
1291 pnkfelix 1.1.2.63 int c = dist.intValue();
1292 pnkfelix 1.1.2.63 if (c < cost) {
1293 pnkfelix 1.1.2.63 cost = c;
1294 pnkfelix 1.1.2.63 }
1295 pnkfelix 1.1.2.36 }
1296 pnkfelix 1.1.2.59 }
1297 pnkfelix 1.1.2.63
1298 pnkfelix 1.1.2.63 if(valid) {
1299 pnkfelix 1.1.2.63 WeightedSet ws = new WeightedSet(cand, cost);
1300 pnkfelix 1.1.2.63 ws.temps = temps;
1301 pnkfelix 1.1.2.63 weightedSpills.add(ws);
1302 pnkfelix 1.1.2.63 }
1303 pnkfelix 1.1.2.63
1304 pnkfelix 1.1.2.63 // System.out.println("Adding "+cand+" at cost "+cost);
1305 pnkfelix 1.1.2.25 }
1306 pnkfelix 1.1.2.63
1307 cananian 1.3.2.1 assert !weightedSpills.isEmpty() : (ASSERTDB ?
1308 pnkfelix 1.1.2.79 lazyInfo("\nneed at least one spill"
1309 pnkfelix 1.1.2.108 +"\nEvictables:"+evictables
1310 pnkfelix 1.1.2.107 ,i,t,regfile)
1311 cananian 1.3.2.1 : "need at least one spill");
1312 pnkfelix 1.1.2.76
1313 pnkfelix 1.1.2.63 WeightedSet spill = (WeightedSet) weightedSpills.first();
1314 pnkfelix 1.1.2.80 if (SPILL_INFO)
1315 pnkfelix 1.1.2.80 System.out.print("for "+t+" in "+i
1316 pnkfelix 1.1.2.80 // + " choosing to spill "+spill
1317 pnkfelix 1.1.2.80 // + " of " + weightedSpills
1318 pnkfelix 1.1.2.80 );
1319 pnkfelix 1.1.2.59
1320 pnkfelix 1.1.2.63 Iterator spRegs = spill.iterator();
1321 pnkfelix 1.1.2.78
1322 pnkfelix 1.1.2.63 while(spRegs.hasNext()) {
1323 pnkfelix 1.1.2.59
1324 pnkfelix 1.1.2.63 // the set we end up spilling may be disjoint from
1325 pnkfelix 1.1.2.63 // the set we were prompted to spill, because the
1326 pnkfelix 1.1.2.63 // SpillException only accounts for making room
1327 pnkfelix 1.1.2.63 // for Load, not in properly maintaining the state
1328 pnkfelix 1.1.2.63 // of the register file
1329 pnkfelix 1.1.2.63
1330 pnkfelix 1.1.2.63 Temp reg = (Temp) spRegs.next();
1331 pnkfelix 1.1.2.63 Temp value = (Temp) regfile.getTemp(reg);
1332 pnkfelix 1.1.2.63
1333 pnkfelix 1.1.2.63 if (value == null) {
1334 pnkfelix 1.1.2.63 // no value associated with 'reg', so we don't
1335 pnkfelix 1.1.2.63 // need to spill it; can go straight to
1336 pnkfelix 1.1.2.63 // storing stuff in it
1337 pnkfelix 1.1.2.80 if (SPILL_INFO) System.out.print(" ; "+reg+" was empty");
1338 pnkfelix 1.1.2.63
1339 pnkfelix 1.1.2.80 } else {
1340 pnkfelix 1.1.2.83
1341 pnkfelix 1.1.2.82 // only bother to store if value is live *and* dirty
1342 pnkfelix 1.1.2.82 if (regfile.isDirty(value)) {
1343 pnkfelix 1.1.2.82 if (liveTemps.getLiveAfter(iloc).contains(value)) {
1344 pnkfelix 1.1.2.83 spillValue(value,iloc.getPrev(),regfile, 3);
1345 pnkfelix 1.1.2.83 if (SPILL_INFO) System.out.print(" ; spilling "+value);
1346 pnkfelix 1.1.2.83 } else {
1347 pnkfelix 1.1.2.83 if (SPILL_INFO) System.out.print(" ; notLive "+value+" (liveAfter:"+liveTemps.getLiveAfter(iloc)+")");
1348 pnkfelix 1.1.2.83 }
1349 pnkfelix 1.1.2.82 } else {
1350 pnkfelix 1.1.2.83 if (SPILL_INFO) System.out.print(" ; notDirty "+value);
1351 pnkfelix 1.1.2.82 }
1352 pnkfelix 1.1.2.82
1353 pnkfelix 1.1.2.82 // FSK: move-coalesced temps need to be
1354 pnkfelix 1.1.2.82 // stored on a spill regardless of
1355 pnkfelix 1.1.2.82 // cleanness of `value'
1356 pnkfelix 1.1.2.83 Collection temps = new java.util.ArrayList(remappedTemps.invert().getValues(value));
1357 cananian 1.7 for (Object ttO : temps) {
1358 cananian 1.7 Temp tt = (Temp) ttO;
1359 pnkfelix 1.1.2.82 if (liveTemps.getLiveAfter(iloc).contains(tt)) {
1360 pnkfelix 1.1.2.83 // System.out.println("spilling "+tt+" before "+iloc+", live after:"+liveTemps.getLiveAfter(iloc));
1361 pnkfelix 1.1.2.96 Instr src;
1362 pnkfelix 1.1.2.96 if(tempToRemovedInstrs.keySet().contains(tt)) {
1363 pnkfelix 1.1.2.96 src=(Instr)tempToRemovedInstrs.get(tt);
1364 pnkfelix 1.1.2.96 } else {
1365 pnkfelix 1.1.2.96 src=regfile.getSource(value);
1366 pnkfelix 1.1.2.96 }
1367 pnkfelix 1.1.2.96
1368 pnkfelix 1.1.2.95 spillValue(tt, iloc.getPrev(),
1369 pnkfelix 1.1.2.96 regfile, src, 2);
1370 pnkfelix 1.1.2.82 }
1371 pnkfelix 1.1.2.83 remappedTemps.remove(tt);
1372 pnkfelix 1.1.2.82 }
1373 pnkfelix 1.1.2.83
1374 pnkfelix 1.1.2.79 regfile.remove(value);
1375 pnkfelix 1.1.2.63 evictables.remove(value);
1376 pnkfelix 1.1.2.63 }
1377 pnkfelix 1.1.2.54 }
1378 pnkfelix 1.1.2.80 if (SPILL_INFO) System.out.println();
1379 pnkfelix 1.1.2.78
1380 pnkfelix 1.1.2.25 }
1381 pnkfelix 1.1.2.25 }
1382 pnkfelix 1.1.2.25 }
1383 pnkfelix 1.1.2.110
1384 pnkfelix 1.1.2.110 private void emptyRegFile(Instr lastInstr) {
1385 pnkfelix 1.1.2.63 // System.out.println("live on exit from " + b + " :\n" + liveOnExit);
1386 pnkfelix 1.1.2.106 Instr instr = curr;
1387 pnkfelix 1.1.2.82
1388 pnkfelix 1.1.2.80 // use a new Set here because we cannot modify regfile
1389 pnkfelix 1.1.2.79 // and traverse its tempSet simultaneously.
1390 pnkfelix 1.1.2.80 Set locvalSet = new LinearSet(regfile.tempSet());
1391 pnkfelix 1.1.2.80 if (SPILL_INFO)
1392 pnkfelix 1.1.2.80 System.out.println("emptying regfile:"+regfile);
1393 pnkfelix 1.1.2.80 final Iterator locvals = locvalSet.iterator();
1394 pnkfelix 1.1.2.79 while(locvals.hasNext()) {
1395 pnkfelix 1.1.2.79 final Temp locval = (Temp) locvals.next();
1396 pnkfelix 1.1.2.79
1397 pnkfelix 1.1.2.82 // FSK: handle spilling move equivalent temps;
1398 pnkfelix 1.1.2.82 // remember that even if the source of the move is
1399 pnkfelix 1.1.2.82 // clean, the "newly defined" temps (the
1400 pnkfelix 1.1.2.82 // move-equivalent virtual ones) are still "dirty" and
1401 pnkfelix 1.1.2.82 // need to be stored to memory.
1402 pnkfelix 1.1.2.82 Iterator vals =
1403 pnkfelix 1.1.2.82 remappedTemps.invert().getValues(locval).iterator();
1404 pnkfelix 1.1.2.79 while(vals.hasNext()) {
1405 pnkfelix 1.1.2.79 final Temp val = (Temp) vals.next();
1406 pnkfelix 1.1.2.63
1407 cananian 1.3.2.1 assert !isRegister(val) : "remapped temp should not be register";
1408 pnkfelix 1.1.2.63
1409 pnkfelix 1.1.2.79 // don't spill dead values.
1410 pnkfelix 1.1.2.80 if (liveOnExit.contains(val)) {
1411 pnkfelix 1.1.2.80 if (SPILL_INFO)
1412 pnkfelix 1.1.2.80 System.out.println("spilling "+val+
1413 pnkfelix 1.1.2.80 " 'cause its live (0)");
1414 pnkfelix 1.1.2.95 chooseSpillSpot(val, instr, regfile,
1415 pnkfelix 1.1.2.110 regfile.getSource(locval), lastInstr);
1416 pnkfelix 1.1.2.63 }
1417 pnkfelix 1.1.2.59 }
1418 pnkfelix 1.1.2.80
1419 pnkfelix 1.1.2.82 if (isRegister(locval)) {
1420 pnkfelix 1.1.2.79 // don't spill register only values
1421 pnkfelix 1.1.2.80
1422 pnkfelix 1.1.2.81 } else if (regfile.isClean(locval)) {
1423 pnkfelix 1.1.2.81 // FSK: weirdness in SpillCodePlacement occurs if
1424 pnkfelix 1.1.2.81 // I (conservatively) leave this case out, which
1425 pnkfelix 1.1.2.82 // is a sign that something's wrong. Experiment
1426 pnkfelix 1.1.2.81 // further...
1427 pnkfelix 1.1.2.81
1428 pnkfelix 1.1.2.79 // don't spill clean values.
1429 pnkfelix 1.1.2.80 if (SPILL_INFO)
1430 pnkfelix 1.1.2.80 System.out.println("not spilling "+locval+
1431 pnkfelix 1.1.2.80 " 'cause its clean");
1432 pnkfelix 1.1.2.80
1433 pnkfelix 1.1.2.79 } else {
1434 pnkfelix 1.1.2.82 // FSK: check and document this
1435 pnkfelix 1.1.2.80 if (liveOnExit.contains(locval)){
1436 pnkfelix 1.1.2.80 // don't spill dead values.
1437 pnkfelix 1.1.2.80 if (SPILL_INFO)
1438 pnkfelix 1.1.2.80 System.out.println("spilling "+locval+
1439 pnkfelix 1.1.2.82 " 'cause its live ");
1440 pnkfelix 1.1.2.110 chooseSpillSpot(locval, instr, regfile, lastInstr);
1441 pnkfelix 1.1.2.80 } else {
1442 pnkfelix 1.1.2.80 if (false && SPILL_INFO)
1443 pnkfelix 1.1.2.80 System.out.println("SKIPPING "+locval+
1444 pnkfelix 1.1.2.80 " 'cause its dead (3)");
1445 pnkfelix 1.1.2.80 }
1446 pnkfelix 1.1.2.63 }
1447 pnkfelix 1.1.2.79
1448 pnkfelix 1.1.2.79 regfile.remove(locval);
1449 pnkfelix 1.1.2.63 }
1450 pnkfelix 1.1.2.79 }
1451 pnkfelix 1.1.2.79
1452 pnkfelix 1.1.2.82 private void chooseSpillSpot(Temp val, Instr instr,
1453 pnkfelix 1.1.2.82 RegFile regfile, Instr iloc) {
1454 pnkfelix 1.1.2.95 chooseSpillSpot(val, instr, regfile,
1455 pnkfelix 1.1.2.95 regfile.getSource(val), iloc);
1456 pnkfelix 1.1.2.95 }
1457 pnkfelix 1.1.2.95
1458 pnkfelix 1.1.2.95 private void chooseSpillSpot(Temp val, Instr instr,
1459 pnkfelix 1.1.2.95 RegFile regfile, Instr src, Instr iloc) {
1460 pnkfelix 1.1.2.79 // need to insert the spill in a place where we can be
1461 pnkfelix 1.1.2.79 // sure it will be executed; the easy case is where
1462 pnkfelix 1.1.2.79 // 'instr' does not redefine the 'val' (so we can just put
1463 pnkfelix 1.1.2.79 // our spills BEFORE 'instr'). If 'instr' does define
1464 pnkfelix 1.1.2.79 // 'val', however, then we MUST wait to spill, and
1465 pnkfelix 1.1.2.79 // then we need to see where control can flow...
1466 pnkfelix 1.1.2.79 // insert a new block solely devoted to spilling
1467 pnkfelix 1.1.2.63
1468 pnkfelix 1.1.2.82 final Instr prev = iloc.getPrev();
1469 pnkfelix 1.1.2.79 if (!instr.defC().contains(val) &&
1470 pnkfelix 1.1.2.79 prev.getTargets().isEmpty() &&
1471 pnkfelix 1.1.2.79 prev.canFallThrough) {
1472 pnkfelix 1.1.2.63
1473 pnkfelix 1.1.2.95 spillValue(val, prev, regfile, src, 1);
1474 pnkfelix 1.1.2.79
1475 pnkfelix 1.1.2.79 } else {
1476 pnkfelix 1.1.2.79
1477 pnkfelix 1.1.2.95 spillValue(val, iloc, regfile, src, 0);
1478 pnkfelix 1.1.2.63
1479 pnkfelix 1.1.2.63 }
1480 pnkfelix 1.1.2.59 }
1481 pnkfelix 1.1.2.79
1482 pnkfelix 1.1.2.79
1483 pnkfelix 1.1.2.63
1484 pnkfelix 1.1.2.108 // runs once / ref / instr
1485 pnkfelix 1.1.2.75 private List chooseSuggestion(Iterator suggs, Temp t) {
1486 pnkfelix 1.1.2.75 return chooseSuggestion(suggs, t, false);
1487 pnkfelix 1.1.2.75 }
1488 pnkfelix 1.1.2.108
1489 pnkfelix 1.1.2.108 // runs once / ref / instr
1490 pnkfelix 1.1.2.75 private List chooseSuggestion(Iterator suggs, Temp t, boolean pr) {
1491 pnkfelix 1.1.2.75 Temp reg = tempSets.getReg(t);
1492 pnkfelix 1.1.2.75 List suggL = null;
1493 pnkfelix 1.1.2.75 if (reg != null) {
1494 pnkfelix 1.1.2.75 // if [ <reg> ] is in <suggs>, ret [ <reg> ]
1495 pnkfelix 1.1.2.75 // else, ret arbitrary elem suggs
1496 pnkfelix 1.1.2.75 do {
1497 pnkfelix 1.1.2.75 suggL = (List) suggs.next();
1498 pnkfelix 1.1.2.91
1499 pnkfelix 1.1.2.111 if (false)
1500 pnkfelix 1.1.2.111 System.out.println("RFI suggests "+suggL+" for "+t);
1501 pnkfelix 1.1.2.111
1502 pnkfelix 1.1.2.75 if (suggL.size() == 1) {
1503 pnkfelix 1.1.2.75 Temp suggReg = (Temp) suggL.get(0);
1504 pnkfelix 1.1.2.75 if (suggReg.equals(reg)) {
1505 pnkfelix 1.1.2.75 if (pr) {
1506 pnkfelix 1.1.2.82 System.out.println
1507 pnkfelix 1.1.2.82 (" ok_Pre " + t +" ("+
1508 pnkfelix 1.1.2.82 tempSets.getRep(t) + ") to " + reg );
1509 pnkfelix 1.1.2.75 }
1510 pnkfelix 1.1.2.75 return suggL;
1511 pnkfelix 1.1.2.75 }
1512 pnkfelix 1.1.2.75 }
1513 pnkfelix 1.1.2.75 } while (suggs.hasNext());
1514 pnkfelix 1.1.2.75
1515 pnkfelix 1.1.2.75 // got to this point => didn't find match for <reg>
1516 pnkfelix 1.1.2.75 if (suggL.size() == 1) {
1517 pnkfelix 1.1.2.82 // insert new association (since we've been forced to
1518 pnkfelix 1.1.2.82 // use a different reg assignment than what we preferred)
1519 pnkfelix 1.1.2.75 reg = (Temp) suggL.get(0);
1520 pnkfelix 1.1.2.75 tempSets.associate(t, reg);
1521 pnkfelix 1.1.2.75 if (pr)
1522 pnkfelix 1.1.2.82 System.out.println
1523 pnkfelix 1.1.2.82 (" badPre " + t +" ("+
1524 pnkfelix 1.1.2.82 tempSets.getRep(t) + ") to " + reg);
1525 pnkfelix 1.1.2.75 }
1526 pnkfelix 1.1.2.75 return suggL;
1527 pnkfelix 1.1.2.75
1528 pnkfelix 1.1.2.75 } else {
1529 pnkfelix 1.1.2.75 suggL = (List) suggs.next();
1530 pnkfelix 1.1.2.111
1531 pnkfelix 1.1.2.111 if (false) System.out.println("RFI suggests "+suggL+" for "+t);
1532 pnkfelix 1.1.2.111
1533 pnkfelix 1.1.2.75 if (suggL.size() == 1) {
1534 pnkfelix 1.1.2.75 reg = (Temp) suggL.get(0);
1535 pnkfelix 1.1.2.75 tempSets.associate(t, reg);
1536 pnkfelix 1.1.2.75 if (pr)
1537 pnkfelix 1.1.2.82 System.out.println
1538 pnkfelix 1.1.2.82 (" no_Pre " + t + " ("+
1539 pnkfelix 1.1.2.82 tempSets.getRep(t) + ") to " + reg );
1540 pnkfelix 1.1.2.75
1541 pnkfelix 1.1.2.75 }
1542 pnkfelix 1.1.2.75 return suggL;
1543 pnkfelix 1.1.2.75 }
1544 pnkfelix 1.1.2.14 }
1545 pnkfelix 1.1.2.82
1546 pnkfelix 1.1.2.79 /** spills `val', adding a store after `loc', but does *NOT*
1547 pnkfelix 1.1.2.79 update the regfile.
1548 pnkfelix 1.1.2.63 */
1549 pnkfelix 1.1.2.95 private void spillValue(Temp val, Instr loc, RegFile regfile,
1550 pnkfelix 1.1.2.95 int thread) {
1551 pnkfelix 1.1.2.95 spillValue(val, loc, regfile, regfile.getSource(val), thread);
1552 pnkfelix 1.1.2.95 }
1553 pnkfelix 1.1.2.95
1554 pnkfelix 1.1.2.95 /** spills `val', adding a store after `loc', but does *NOT*
1555 pnkfelix 1.1.2.95 update the regfile, and using `src' as the source for
1556 pnkfelix 1.1.2.95 `val'.
1557 pnkfelix 1.1.2.95 */
1558 pnkfelix 1.1.2.95 private void spillValue(Temp val, Instr loc, RegFile regfile,
1559 pnkfelix 1.1.2.95 Instr src, int thread) {
1560 cananian 1.3.2.1 assert ! preassignedTemps.contains( val ) : "cannot spill Preassigned Temps";
1561 cananian 1.3.2.1 assert !isRegister(val) : (ASSERTDB ? val+" should not be reg"
1562 pnkfelix 1.1.2.107 : "should not be reg");
1563 pnkfelix 1.1.2.79
1564 pnkfelix 1.1.2.82 Collection regs =
1565 pnkfelix 1.1.2.82 regfile.getAssignment(remappedTemps.tempMap(val));
1566 pnkfelix 1.1.2.92
1567 cananian 1.3.2.1 assert regs != null && !regs.isEmpty() : (ASSERTDB ?
1568 pnkfelix 1.1.2.107 lazyInfo("must map to a nonempty set of registers\n"+
1569 pnkfelix 1.1.2.107 "tempSets:"+tempSets,val,regfile)
1570 pnkfelix 1.1.2.107 : "must map to a nonempty set of registers");
1571 cananian 1.3.2.1 assert allRegs(regs);
1572 pnkfelix 1.1.2.79
1573 pnkfelix 1.1.2.108 InstrMEM spillInstr = SpillStore.makeST(loc, "FSK-ST", val, regs);
1574 pnkfelix 1.1.2.75
1575 pnkfelix 1.1.2.75 spillStores.add(spillInstr);
1576 pnkfelix 1.1.2.75 spillStores.add(loc);
1577 pnkfelix 1.1.2.100 back(spillInstr, src);
1578 pnkfelix 1.1.2.97 instrToHTempMap.put(spillInstr, coalescedTemps);
1579 pnkfelix 1.1.2.14 }
1580 pnkfelix 1.1.2.79
1581 pnkfelix 1.1.2.82 // *** helper methods for debugging within BlockAlloc ***
1582 pnkfelix 1.1.2.82 private Object lazyInfo(String prefix) {
1583 pnkfelix 1.1.2.82 return lazyInfo(prefix, curr, null);
1584 pnkfelix 1.1.2.82 }
1585 pnkfelix 1.1.2.82
1586 pnkfelix 1.1.2.79 private Object lazyInfo(String prefix, Temp t) {
1587 pnkfelix 1.1.2.79 return lazyInfo(prefix, curr, t);
1588 pnkfelix 1.1.2.79 }
1589 pnkfelix 1.1.2.79
1590 pnkfelix 1.1.2.79 private Object lazyInfo(String prefix, Temp t, RegFile regfile) {
1591 pnkfelix 1.1.2.79 return lazyInfo(prefix, curr, t, regfile);
1592 pnkfelix 1.1.2.79 }
1593 pnkfelix 1.1.2.79
1594 pnkfelix 1.1.2.79 private Object lazyInfo(String prefix, Instr i, Temp t) {
1595 pnkfelix 1.1.2.82 return LocalCffRegAlloc.this.lazyInfo(prefix, block, i, t);
1596 pnkfelix 1.1.2.79 }
1597 pnkfelix 1.1.2.79
1598 pnkfelix 1.1.2.79 private Object lazyInfo(String prefix, Instr i, Temp t,
1599 pnkfelix 1.1.2.79 RegFile regfile) {
1600 pnkfelix 1.1.2.82 return LocalCffRegAlloc.this.lazyInfo(prefix, block, i, t, regfile);
1601 pnkfelix 1.1.2.79 }
1602 pnkfelix 1.1.2.59 }
1603 pnkfelix 1.1.2.36
1604 pnkfelix 1.1.2.14
1605 pnkfelix 1.1.2.59
1606 pnkfelix 1.1.2.79
1607 pnkfelix 1.1.2.79
1608 pnkfelix 1.1.2.79 // *** DEBUGGING ROUTINES ***
1609 pnkfelix 1.1.2.79
1610 pnkfelix 1.1.2.79 // lazyInfo(..) family of methods return an object that prints out
1611 pnkfelix 1.1.2.79 // the basic block in a demand driven fashion, so that we do not
1612 pnkfelix 1.1.2.79 // incur the cost of constructing the string representation of the
1613 pnkfelix 1.1.2.79 // basic block until we actually will need it
1614 pnkfelix 1.1.2.79
1615 pnkfelix 1.1.2.82 Object lazyInfo(String prefix, BasicBlock b,
1616 pnkfelix 1.1.2.82 Instr i, Temp t) {
1617 pnkfelix 1.1.2.82 return lazyInfo(prefix, b, i, t, true);
1618 pnkfelix 1.1.2.79 }
1619 pnkfelix 1.1.2.79
1620 pnkfelix 1.1.2.82 Object lazyInfo(String prefix, BasicBlock b,
1621 pnkfelix 1.1.2.82 Instr i, Temp t, RegFile regfile) {
1622 pnkfelix 1.1.2.82 return lazyInfo(prefix, b, i, t, regfile, true);
1623 pnkfelix 1.1.2.79 }
1624 pnkfelix 1.1.2.79
1625 pnkfelix 1.1.2.82 Object lazyInfo(final String prefix, final BasicBlock b,
1626 pnkfelix 1.1.2.82 final Instr i, final Temp t,
1627 pnkfelix 1.1.2.79 final boolean auxSpillCode) {
1628 pnkfelix 1.1.2.79 return new Object() {
1629 pnkfelix 1.1.2.79 public String toString() {
1630 pnkfelix 1.1.2.79 return prefix+"\n"+printInfo(b, i, t, code, auxSpillCode);
1631 pnkfelix 1.1.2.79 }
1632 pnkfelix 1.1.2.79 };
1633 pnkfelix 1.1.2.79 }
1634 pnkfelix 1.1.2.79
1635 pnkfelix 1.1.2.82 Object lazyInfo(final String prefix, final BasicBlock b,
1636 pnkfelix 1.1.2.82 final Instr i, final Temp t,
1637 pnkfelix 1.1.2.79 final RegFile regfile,
1638 pnkfelix 1.1.2.79 final boolean auxSpillCode) {
1639 pnkfelix 1.1.2.79 return new Object() {
1640 pnkfelix 1.1.2.79 public String toString() {
1641 pnkfelix 1.1.2.79 return prefix+"\n"+"RegFile:"+regfile+"\n"+printInfo(b, i, t, code, auxSpillCode);
1642 pnkfelix 1.1.2.79 }
1643 pnkfelix 1.1.2.79 };
1644 pnkfelix 1.1.2.79 }
1645 pnkfelix 1.1.2.79
1646 pnkfelix 1.1.2.79
1647 pnkfelix 1.1.2.79 private String printInfo(BasicBlock block, Instr i,
1648 pnkfelix 1.1.2.79 Temp t, Code code) {
1649 pnkfelix 1.1.2.79 return printInfo(block, i, t, code, true);
1650 pnkfelix 1.1.2.79 }
1651 pnkfelix 1.1.2.79
1652 pnkfelix 1.1.2.79 private String printInfo(BasicBlock block, Instr i,
1653 pnkfelix 1.1.2.79 Temp t, Code code, boolean auxSpillCode) {
1654 pnkfelix 1.1.2.79 java.io.StringWriter swout = new java.io.StringWriter();
1655 pnkfelix 1.1.2.79 java.io.PrintWriter pwout = new java.io.PrintWriter(swout);
1656 pnkfelix 1.1.2.79 // code.print(pwout);
1657 pnkfelix 1.1.2.79
1658 pnkfelix 1.1.2.79 // StringBuffer sb = new StringBuffer(swout.toString());
1659 pnkfelix 1.1.2.79 StringBuffer sb = new StringBuffer();
1660 pnkfelix 1.1.2.79
1661 pnkfelix 1.1.2.79 // inserting the loads and stores may make this routine
1662 pnkfelix 1.1.2.79 // O(n^2), which could be bad...
1663 pnkfelix 1.1.2.79
1664 pnkfelix 1.1.2.79 List blockL = block.statements();
1665 cananian 1.7 for (Object i2O : blockL) {
1666 cananian 1.7 Instr i2 = (Instr) i2O;
1667 pnkfelix 1.1.2.79
1668 pnkfelix 1.1.2.79 if (auxSpillCode) {
1669 pnkfelix 1.1.2.79 // insert loads...
1670 pnkfelix 1.1.2.79 Iterator loads = spillLoads.iterator();
1671 pnkfelix 1.1.2.79 while(loads.hasNext()) {
1672 pnkfelix 1.1.2.79 Instr s = (Instr) loads.next();
1673 pnkfelix 1.1.2.79 Instr loc = (Instr) loads.next();
1674 pnkfelix 1.1.2.79 if (loc == i2) {
1675 pnkfelix 1.1.2.79 sb.append(s+"\n");
1676 pnkfelix 1.1.2.79 }
1677 pnkfelix 1.1.2.79 }
1678 pnkfelix 1.1.2.79 }
1679 pnkfelix 1.1.2.79
1680 pnkfelix 1.1.2.79 // put actual instr in
1681 pnkfelix 1.1.2.91 sb.append(code.toAssem(i2)+
1682 pnkfelix 1.1.2.79 " \t { " + i2 +
1683 pnkfelix 1.1.2.79 " }");
1684 pnkfelix 1.1.2.79
1685 pnkfelix 1.1.2.79 // if instr is scheduled for removal, make a note of that
1686 pnkfelix 1.1.2.79 // as well
1687 pnkfelix 1.1.2.79 if (instrsToRemove.contains(i2)) sb.append("\t* R *");
1688 pnkfelix 1.1.2.79
1689 pnkfelix 1.1.2.79 sb.append("\n");
1690 pnkfelix 1.1.2.79
1691 pnkfelix 1.1.2.79 if (auxSpillCode) {
1692 pnkfelix 1.1.2.79 // insert stores...
1693 pnkfelix 1.1.2.79 Iterator stores = spillStores.iterator();
1694 pnkfelix 1.1.2.79 while(stores.hasNext()) {
1695 pnkfelix 1.1.2.79 Instr s = (Instr) stores.next();
1696 pnkfelix 1.1.2.79 Instr loc = (Instr) stores.next();
1697 pnkfelix 1.1.2.79 if (loc == i2) {
1698 pnkfelix 1.1.2.79 sb.append(s+"\n");
1699 pnkfelix 1.1.2.79 }
1700 pnkfelix 1.1.2.79 }
1701 pnkfelix 1.1.2.79 }
1702 pnkfelix 1.1.2.79 }
1703 pnkfelix 1.1.2.79
1704 pnkfelix 1.1.2.79 return "\n"+
1705 pnkfelix 1.1.2.79 "temp: "+t + "\n"+
1706 pnkfelix 1.1.2.80 "instr: "+ i + "\n\n"+
1707 pnkfelix 1.1.2.80 sb.toString();
1708 pnkfelix 1.1.2.80
1709 pnkfelix 1.1.2.79
1710 pnkfelix 1.1.2.79 }
1711 pnkfelix 1.1.2.79
1712 pnkfelix 1.1.2.82 public List list(Temp t) {
1713 pnkfelix 1.1.2.82 return Arrays.asList( new Temp[]{ t } );
1714 pnkfelix 1.1.2.82 }
1715 pnkfelix 1.1.2.82 public List list(Temp t1, Temp t2) {
1716 pnkfelix 1.1.2.82 return Arrays.asList( new Temp[]{ t1, t2 });
1717 pnkfelix 1.1.2.82 }
1718 pnkfelix 1.1.2.1
1719 pnkfelix 1.1.2.1 }
1720 cananian 1.2