1 pnkfelix 1.1.2.1 // RegAlloc.java, created Mon Mar 29 16:47:25 1999 by pnkfelix
2 cananian 1.1.2.16 // 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.1 import harpoon.Temp.Temp;
7 pnkfelix 1.1.2.1 import harpoon.IR.Assem.Instr;
8 pnkfelix 1.1.2.11 import harpoon.Backend.Generic.RegFileInfo;
9 pnkfelix 1.1.2.1 import harpoon.Backend.Generic.Frame;
10 pnkfelix 1.1.2.1 import harpoon.Backend.Generic.Code;
11 cananian 1.1.2.14 import harpoon.Analysis.Maps.UseDefMap;
12 pnkfelix 1.1.2.8 import harpoon.Analysis.BasicBlock;
13 pnkfelix 1.1.2.13 import harpoon.Analysis.Maps.Derivation;
14 pnkfelix 1.1.2.1
15 pnkfelix 1.1.2.1 import java.util.Hashtable;
16 pnkfelix 1.1.2.1 import java.util.Set;
17 pnkfelix 1.1.2.1 import java.util.Vector;
18 pnkfelix 1.1.2.1 import java.util.ListIterator;
19 pnkfelix 1.1.2.1 import java.util.HashSet;
20 pnkfelix 1.1.2.1 import java.util.Map;
21 pnkfelix 1.1.2.1 import java.util.HashMap;
22 pnkfelix 1.1.2.1
23 pnkfelix 1.1.2.1 /** <code>DemandDrivenRegAlloc</code> performs
24 pnkfelix 1.1.2.2 <A HREF="http://lm.lcs.mit.edu/~pnkfelix/DemandDrivenRegAlloc.pdf">
25 pnkfelix 1.1.2.1 Demand-Driven Register Allocation</A> for a set of
26 pnkfelix 1.1.2.1 <code>Instr</code>s in a <code>Code</code>.
27 pnkfelix 1.1.2.1
28 cananian 1.1.2.16 @author Felix S. Klock II <pnkfelix@mit.edu>
29 cananian 1.2 @version $Id: DemandDrivenRegAlloc.java,v 1.2 2002/02/25 20:57:30 cananian Exp $
30 pnkfelix 1.1.2.1 */
31 pnkfelix 1.1.2.1 public class DemandDrivenRegAlloc extends RegAlloc {
32 pnkfelix 1.1.2.1
33 cananian 1.1.2.14 UseDefMap uses;
34 pnkfelix 1.1.2.3
35 pnkfelix 1.1.2.3 // maps basicblocks to the variables allocated to registers
36 pnkfelix 1.1.2.3 // entering the block
37 pnkfelix 1.1.2.3 private Map bbToAllocatedMap;
38 pnkfelix 1.1.2.3
39 pnkfelix 1.1.2.3 // maps basicblocks to the live variables entering the block
40 pnkfelix 1.1.2.3 private Map bbToLiveVarMap;
41 pnkfelix 1.1.2.3
42 pnkfelix 1.1.2.3 // TODO: should probably add a local var storing info on
43 pnkfelix 1.1.2.3 // LiveVarAnalysis.
44 pnkfelix 1.1.2.3
45 pnkfelix 1.1.2.1
46 pnkfelix 1.1.2.1 /** Creates a <code>DemandDrivenRegAlloc</code>.
47 pnkfelix 1.1.2.1
48 pnkfelix 1.1.2.1 <BR> <B>Design Issue:</B> should there be a RegAlloc object
49 pnkfelix 1.1.2.1 for every method, or just for every machine target? For
50 pnkfelix 1.1.2.1 now it seems associating a new one with every method will
51 pnkfelix 1.1.2.1 save a lot of headaches.
52 pnkfelix 1.1.2.1
53 pnkfelix 1.1.2.1 <BR> <B>requires:</B>
54 pnkfelix 1.1.2.1 1. Local register allocation has been run on
55 pnkfelix 1.1.2.1 <code>code</code> already.
56 pnkfelix 1.1.2.1 */
57 pnkfelix 1.1.2.6 protected DemandDrivenRegAlloc(Code code) {
58 pnkfelix 1.1.2.6 super(code);
59 cananian 1.1.2.14 uses = new harpoon.Analysis.UseDef( /*code*/ );
60 pnkfelix 1.1.2.3
61 pnkfelix 1.1.2.3 bbToAllocatedMap = new HashMap(); // built during allocation
62 pnkfelix 1.1.2.3
63 pnkfelix 1.1.2.3 bbToLiveVarMap = findLiveVars(code); // invariant during allocation
64 pnkfelix 1.1.2.1 }
65 pnkfelix 1.1.2.13
66 pnkfelix 1.1.2.13 /** stub implementation. */
67 pnkfelix 1.1.2.13 protected Derivation getDerivation() { return null; }
68 pnkfelix 1.1.2.1
69 pnkfelix 1.1.2.9 protected void generateRegAssignment() {
70 pnkfelix 1.1.2.2
71 pnkfelix 1.1.2.2 /* procedure for register allocation for a procedure (taken from
72 pnkfelix 1.1.2.2 Demand-Driven Register Allocation):
73 pnkfelix 1.1.2.2
74 pnkfelix 1.1.2.2 (assumes that Local Allocation has already been performed)
75 pnkfelix 1.1.2.2 */
76 pnkfelix 1.1.2.2
77 pnkfelix 1.1.2.2 /*
78 pnkfelix 1.1.2.2 2. For all loops, l. in the procedure, from innermost to
79 pnkfelix 1.1.2.2 outermost do the following:
80 pnkfelix 1.1.2.2 (a) Attempt to remove loads in l:
81 pnkfelix 1.1.2.1 i. Compute delta-estimates for all instructions in the
82 pnkfelix 1.1.2.1 loop (with ComputeDeltas() ).
83 pnkfelix 1.1.2.1 ii. For each load of a register candidate in the loop,
84 pnkfelix 1.1.2.1 estimate the chance that the value will reach the
85 pnkfelix 1.1.2.1 load in a register. This is the product of all the
86 pnkfelix 1.1.2.1 delta-estimates for that candidate in the load's
87 pnkfelix 1.1.2.1 register-live-range.
88 pnkfelix 1.1.2.1 iii. If no loads have an estimate greater than 0, then
89 pnkfelix 1.1.2.1 quit processing loads.
90 pnkfelix 1.1.2.1 iv. Otherwise, remove the load with the greatest figure
91 pnkfelix 1.1.2.1 of merit, and allocate the candidate a register
92 pnkfelix 1.1.2.1 across its entire register-live-range. (This may
93 pnkfelix 1.1.2.1 require putting a load in the loop's preheader.)
94 pnkfelix 1.1.2.1 (b) Attempt to remove stores in l:
95 pnkfelix 1.1.2.1 i. Compute delta-estimates for all instructions in the
96 pnkfelix 1.1.2.1 loop (with ComputeDeltas() ).
97 pnkfelix 1.1.2.1 ii. For each store of a register candidate in the loop,
98 pnkfelix 1.1.2.1 estimate the chance that the stored value will
99 pnkfelix 1.1.2.1 reach *all* remaining reachable loads in l, and
100 pnkfelix 1.1.2.1 those postexits in which the value is live in a
101 pnkfelix 1.1.2.1 register. This is the product of all the
102 pnkfelix 1.1.2.1 delta-estimates for that candidate along all paths
103 pnkfelix 1.1.2.1 to these loads and postexits.
104 pnkfelix 1.1.2.1 iii. If no stores have an estimate greater than 0, then
105 pnkfelix 1.1.2.1 quit processing stores.
106 pnkfelix 1.1.2.1 iv. Otherwise, remove the store with the greatest
107 pnkfelix 1.1.2.1 figure of merit, and allocate the candidate a
108 pnkfelix 1.1.2.1 register along all paths to the postexits. This
109 pnkfelix 1.1.2.1 requires putting stores in the loop's postexits.
110 pnkfelix 1.1.2.2 */
111 pnkfelix 1.1.2.2
112 pnkfelix 1.1.2.2
113 pnkfelix 1.1.2.2 /*
114 pnkfelix 1.1.2.2
115 pnkfelix 1.1.2.2 3. Remove loads that are not in any loop (Use techniques
116 pnkfelix 1.1.2.2 described in (2a) above.)
117 pnkfelix 1.1.2.2 4. Remove stores that are not in any loop (Use techniques
118 pnkfelix 1.1.2.2 described in (2b) above).
119 pnkfelix 1.1.2.2
120 pnkfelix 1.1.2.2 */
121 pnkfelix 1.1.2.2
122 pnkfelix 1.1.2.2
123 pnkfelix 1.1.2.2 /*
124 pnkfelix 1.1.2.2
125 pnkfelix 1.1.2.2 5. Assign registers to all candidates allocated registers using
126 pnkfelix 1.1.2.1 the Graph Coloring Framework.
127 pnkfelix 1.1.2.2
128 pnkfelix 1.1.2.2 */
129 pnkfelix 1.1.2.2
130 pnkfelix 1.1.2.11 return;
131 pnkfelix 1.1.2.2 }
132 pnkfelix 1.1.2.2
133 pnkfelix 1.1.2.1
134 pnkfelix 1.1.2.1 /** Delta computing function. Taken from the paper "Demand-Driven
135 pnkfelix 1.1.2.1 Register Allocation."
136 pnkfelix 1.1.2.1 <BR> <B>requires:</B> <code>BasicBlock</code> is a set of
137 pnkfelix 1.1.2.1 <code>Instr</code>s.
138 pnkfelix 1.1.2.1 <BR> <B>effects:</B> returns a
139 pnkfelix 1.1.2.1 Map[TempInstrPair, Double] mapping
140 pnkfelix 1.1.2.1 (instr x temp) -> deltaValue
141 pnkfelix 1.1.2.1 */
142 pnkfelix 1.1.2.1 private Map computeDeltas(BasicBlock block) {
143 pnkfelix 1.1.2.1 // initialize configuration
144 pnkfelix 1.1.2.1
145 pnkfelix 1.1.2.3 // { variables allocated registers entering block };
146 pnkfelix 1.1.2.3 Set allocated = (Set) bbToAllocatedMap.get(block);
147 pnkfelix 1.1.2.3
148 pnkfelix 1.1.2.3 // { live variables entering block } - allocated
149 pnkfelix 1.1.2.1 Set candidates = new HashSet();
150 pnkfelix 1.1.2.3 candidates.addAll((Set)bbToLiveVarMap.get(block));
151 pnkfelix 1.1.2.3
152 pnkfelix 1.1.2.3 candidates.removeAll(allocated);
153 pnkfelix 1.1.2.1
154 pnkfelix 1.1.2.3 // min( REGISTERS - |allocated|, |candidates| )
155 pnkfelix 1.1.2.17 int possibly = Math.min(frame.getRegFileInfo().getAllRegisters().length -
156 pnkfelix 1.1.2.3 allocated.size(), candidates.size() );
157 pnkfelix 1.1.2.1
158 pnkfelix 1.1.2.3 // REGISTERS - ( |allocated| + possibly )
159 pnkfelix 1.1.2.17 int unallocated = frame.getRegFileInfo().getAllRegisters().length -
160 pnkfelix 1.1.2.1 (allocated.size() + possibly);
161 pnkfelix 1.1.2.1
162 pnkfelix 1.1.2.1 // *** Implementation Specific local variables ***
163 pnkfelix 1.1.2.3
164 pnkfelix 1.1.2.3 // maps register uses in a particular instruction to the
165 pnkfelix 1.1.2.3 // variable that the register is storing.
166 pnkfelix 1.1.2.3 Map regXinstrToVarMap = new HashMap();
167 pnkfelix 1.1.2.1
168 pnkfelix 1.1.2.1
169 pnkfelix 1.1.2.1 // Iterate over instructions in order
170 pnkfelix 1.1.2.1
171 pnkfelix 1.1.2.10 ListIterator instrs = block.statements().listIterator();
172 pnkfelix 1.1.2.1 while(instrs.hasNext()) {
173 pnkfelix 1.1.2.1 Instr instr = (Instr) instrs.next();
174 pnkfelix 1.1.2.1 double delta;
175 pnkfelix 1.1.2.3
176 pnkfelix 1.1.2.1 { // BELOW: Last use of a register frees it
177 pnkfelix 1.1.2.3 Vector regsFreedByInstr = new Vector();
178 pnkfelix 1.1.2.1 for (int i=0; i<instr.use().length; i++) {
179 pnkfelix 1.1.2.12 if (isRegister(instr.use()[i]) &&
180 pnkfelix 1.1.2.1 lastUse( instr.use()[i], instr, instrs)){
181 pnkfelix 1.1.2.3 regsFreedByInstr.addElement(instr.use()[i]);
182 pnkfelix 1.1.2.1 }
183 pnkfelix 1.1.2.1 }
184 pnkfelix 1.1.2.1 // for all f of { registers freed by instr }
185 pnkfelix 1.1.2.3 for (int i=0;i<regsFreedByInstr.size();i++) {
186 pnkfelix 1.1.2.3 Temp f = (Temp) regsFreedByInstr.get(i);
187 pnkfelix 1.1.2.3
188 pnkfelix 1.1.2.1 // Let t be value held in f
189 pnkfelix 1.1.2.1 Temp t= (Temp)
190 pnkfelix 1.1.2.3 regXinstrToVarMap.get
191 pnkfelix 1.1.2.1 (new TempInstrPair(instr, f)) ;
192 pnkfelix 1.1.2.3
193 pnkfelix 1.1.2.1 if (t != null) {
194 pnkfelix 1.1.2.1 allocated.remove(t);
195 pnkfelix 1.1.2.1 if(true) { // if t is a live variable
196 pnkfelix 1.1.2.1 candidates.add(t);
197 pnkfelix 1.1.2.1 possibly++;
198 pnkfelix 1.1.2.1 } else {
199 pnkfelix 1.1.2.1 unallocated++;
200 pnkfelix 1.1.2.1 }
201 pnkfelix 1.1.2.1 } else {
202 pnkfelix 1.1.2.1 unallocated++;
203 pnkfelix 1.1.2.1 }
204 pnkfelix 1.1.2.1 }
205 pnkfelix 1.1.2.1 }
206 pnkfelix 1.1.2.1
207 pnkfelix 1.1.2.1
208 pnkfelix 1.1.2.1 { // BELOW: First use of a register allocates it
209 pnkfelix 1.1.2.1 if (true) { // if instr allocated r, a register
210 pnkfelix 1.1.2.1 Temp v=null; // Let v be value held in r
211 pnkfelix 1.1.2.1 allocated.add(v);
212 pnkfelix 1.1.2.1 if (true) { // if v holds the value of variable
213 pnkfelix 1.1.2.1 // (ie not a Temporary)
214 pnkfelix 1.1.2.1 candidates.remove(v);
215 pnkfelix 1.1.2.1 }
216 pnkfelix 1.1.2.1 if (possibly > candidates.size() ) {
217 pnkfelix 1.1.2.1 // Only occurs when possibly == |candidates| prior
218 pnkfelix 1.1.2.1 // to satisfying preceding conditional
219 pnkfelix 1.1.2.1 delta = 1.0;
220 pnkfelix 1.1.2.1 possibly--;
221 pnkfelix 1.1.2.1 } else if (unallocated > 0) {
222 pnkfelix 1.1.2.1 // Allocating an empty register cannot kill
223 pnkfelix 1.1.2.1 // anything
224 pnkfelix 1.1.2.1 delta = 1.0;
225 pnkfelix 1.1.2.1 unallocated--;
226 pnkfelix 1.1.2.1 } else {
227 pnkfelix 1.1.2.1 delta = ((double)(possibly-1)) /
228 pnkfelix 1.1.2.1 ((double)possibly);
229 pnkfelix 1.1.2.1 possibly--;
230 pnkfelix 1.1.2.1 }
231 pnkfelix 1.1.2.1 } else {
232 pnkfelix 1.1.2.1 delta = 1.0;
233 pnkfelix 1.1.2.1 }
234 pnkfelix 1.1.2.1 }
235 pnkfelix 1.1.2.1
236 pnkfelix 1.1.2.1 for (;;) { // for all v elem candidates
237 pnkfelix 1.1.2.1 // deltaTable[instr][v] = delta
238 pnkfelix 1.1.2.1 }
239 pnkfelix 1.1.2.1 }
240 pnkfelix 1.1.2.1
241 pnkfelix 1.1.2.1 return null;
242 pnkfelix 1.1.2.1
243 pnkfelix 1.1.2.1 }
244 pnkfelix 1.1.2.3
245 pnkfelix 1.1.2.3 private Map findLiveVars(Code code) {
246 cananian 1.1.2.14 UseDefMap useMap = new harpoon.Analysis.UseDef(/*code*/);
247 pnkfelix 1.1.2.3 return null;
248 pnkfelix 1.1.2.3 }
249 pnkfelix 1.1.2.1
250 pnkfelix 1.1.2.1 }
251 cananian 1.2