1 cananian 1.1.2.14 // DominatingMemoryAccess.java, created Fri Oct 27 16:33:24 2000 by witchel
2 cananian 1.1.2.14 // Copyright (C) 2001 Emmett Witchel <witchel@mit.edu>
3 cananian 1.1.2.14 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 witchel 1.1.2.1 package harpoon.Analysis.Tree;
5 witchel 1.1.2.1
6 cananian 1.1.2.13 import harpoon.Analysis.ClassHierarchy;
7 cananian 1.1.2.13 import harpoon.Backend.Generic.Frame;
8 witchel 1.1.2.1 import harpoon.ClassFile.HCode;
9 witchel 1.1.2.1 import harpoon.ClassFile.HCodeEdge;
10 witchel 1.1.2.1 import harpoon.ClassFile.HCodeElement;
11 witchel 1.1.2.1 import harpoon.ClassFile.HCodeFactory;
12 witchel 1.1.2.1 import harpoon.ClassFile.HMethod;
13 witchel 1.1.2.1 import harpoon.ClassFile.HClass;
14 witchel 1.1.2.1 import harpoon.IR.Properties.CFGrapher;
15 witchel 1.1.2.1
16 witchel 1.1.2.1 import harpoon.IR.Tree.Typed;
17 witchel 1.1.2.1 import harpoon.IR.Tree.CanonicalTreeCode;
18 witchel 1.1.2.1 import harpoon.IR.Tree.TreeKind;
19 witchel 1.1.2.1 import harpoon.IR.Tree.Tree;
20 witchel 1.1.2.1 import harpoon.IR.Tree.BINOP;
21 witchel 1.1.2.1 import harpoon.IR.Tree.CONST;
22 witchel 1.1.2.1 // harpoon.IR.Tree.TEMP are tree temps, basically all unique
23 witchel 1.1.2.1 // Closer to a virtual register
24 cananian 1.1.2.13 // CSA Note: actually, harpoon.Temp.Temp's are exactly virtual registers,
25 cananian 1.1.2.13 // Tree.TEMP is just a wrapper object to make an lvalue/rvalue
26 cananian 1.1.2.13 // out of the Temp.
27 witchel 1.1.2.1 import harpoon.IR.Tree.TEMP;
28 witchel 1.1.2.1 import harpoon.Temp.Temp;
29 witchel 1.1.2.1 import harpoon.IR.Tree.Bop;
30 witchel 1.1.2.1 import harpoon.IR.Tree.CALL;
31 witchel 1.1.2.1 import harpoon.IR.Tree.MOVE;
32 witchel 1.1.2.1 import harpoon.IR.Tree.MEM;
33 witchel 1.1.2.11 import harpoon.IR.Tree.Stm;
34 witchel 1.1.2.1 import harpoon.IR.Tree.Exp;
35 witchel 1.1.2.1 import harpoon.Util.Util;
36 cananian 1.5 import net.cscott.jutil.BitSetFactory;
37 witchel 1.1.2.1
38 witchel 1.1.2.1 import java.util.Iterator;
39 witchel 1.1.2.1 import java.util.HashMap;
40 witchel 1.1.2.6 import java.util.Map;
41 witchel 1.1.2.2 import java.util.HashSet;
42 witchel 1.1.2.6 import java.util.Set;
43 witchel 1.1.2.2 import java.util.Stack;
44 witchel 1.1.2.2 import java.util.BitSet;
45 witchel 1.1.2.1 import java.util.List;
46 witchel 1.1.2.2 import java.util.Comparator;
47 witchel 1.1.2.2 import java.util.Collection;
48 witchel 1.1.2.16 import java.util.ArrayList;
49 witchel 1.1.2.1
50 witchel 1.1.2.2 /**
51 witchel 1.1.2.5 * <code>DominatingMemoryAccess</code> is an analysis that uses
52 witchel 1.1.2.5 information about memory operations to determine which of them need
53 witchel 1.1.2.5 to do cache tag checks, and which don't. If one access dominates
54 witchel 1.1.2.5 another, and they are provably on the same cache line, we do not need
55 witchel 1.1.2.5 to check the later's tag.
56 witchel 1.1.2.5
57 witchel 1.1.2.5 We assume that the system allocator does not break objects over cache
58 witchel 1.1.2.5 lines.
59 witchel 1.1.2.5
60 witchel 1.1.2.5 We assign direct address register numbers to the most important
61 witchel 1.1.2.5 references. The defining access set the register to point to the
62 witchel 1.1.2.5 cache location of the data, and the using accesses, um, use the data
63 witchel 1.1.2.5 at that cache location. This is a standard register allocation
64 witchel 1.1.2.5 problem, but we
65 witchel 1.1.2.5 don't spill, since the contents of a direct address register is a
66 witchel 1.1.2.5 hardware decoded cache location which is kept consistent in the face
67 witchel 1.1.2.5 of replacements by the hardware. To restore an old value of the
68 witchel 1.1.2.5 register would potentially allow a process access into protected
69 witchel 1.1.2.5 data. Anyway, there is no CPU interface to get at the contents of
70 witchel 1.1.2.5 direct address registers for precisely the reason that it shouldn't
71 witchel 1.1.2.5 use them.
72 witchel 1.1.2.5
73 witchel 1.1.2.5 The backend needs to know which direct address register numbers we
74 witchel 1.1.2.5 used since it needs to invalidate them on a function return.
75 witchel 1.1.2.2 *
76 cananian 1.1.2.14 * @author Emmett Witchel <witchel@mit.edu>
77 cananian 1.6 * @version $Id: DominatingMemoryAccess.java,v 1.6 2004/02/08 03:20:34 cananian Exp $
78 witchel 1.1.2.2 */
79 witchel 1.1.2.1 public class DominatingMemoryAccess {
80 witchel 1.1.2.1
81 witchel 1.1.2.11 /** Solves data flow equations for live variables.
82 witchel 1.1.2.11 This version relies on the fact that there is at most one MEM per
83 witchel 1.1.2.11 Stm, which is guaranteed by the MemHoisting pass.
84 witchel 1.1.2.11 The in/out sets hold MEMs, but we traverse Stms.
85 witchel 1.1.2.11 */
86 witchel 1.1.2.15 class Live {
87 witchel 1.1.2.11
88 witchel 1.1.2.11 private void doOne(Stm root, Tree m) {
89 witchel 1.1.2.11 for(Tree t = m.getFirstChild(); t != null; t = t.getSibling()) {
90 witchel 1.1.2.11 doOne(root, t);
91 witchel 1.1.2.11 }
92 witchel 1.1.2.11 if(m.kind() == TreeKind.MEM) {
93 cananian 1.3.2.1 assert stmToMem.containsKey(root) == false : "******* Stm*"
94 witchel 1.1.2.11 + harpoon.IR.Tree.Print.print(root)
95 witchel 1.1.2.11 + "\n******* tree* "
96 cananian 1.3.2.1 + harpoon.IR.Tree.Print.print(m);
97 cananian 1.3.2.1 assert memToStm.containsKey(m) == false;
98 witchel 1.1.2.11 stmToMem.put(root, m);
99 witchel 1.1.2.11 memToStm.put(m, root);
100 witchel 1.1.2.11 }
101 witchel 1.1.2.11 }
102 witchel 1.1.2.11 // Not strictly necessary, but then in/out is never null
103 witchel 1.1.2.11 private void init_inout(Set nodes) {
104 witchel 1.1.2.11 this.in = new HashMap(nodes.size());
105 witchel 1.1.2.11 this.out = new HashMap(nodes.size());
106 cananian 1.6 for(Object hceO : nodes) {
107 cananian 1.6 HCodeElement hce = (HCodeElement) hceO;
108 witchel 1.1.2.11 in.put(hce, bsf.makeSet());
109 witchel 1.1.2.11 out.put(hce, bsf.makeSet());
110 witchel 1.1.2.11 }
111 witchel 1.1.2.11 }
112 witchel 1.1.2.11 private void initStmMemMaps(final CFGrapher cfgr, final HCode code) {
113 witchel 1.1.2.11 // Build the stm <-> MEM maps
114 cananian 1.6 for(Object stmO : cfgr.getElements(code)) {
115 cananian 1.6 Stm stm = (Stm) stmO;
116 cananian 1.3.2.1 assert stm != null;
117 witchel 1.1.2.11 doOne(stm, (Tree)stm);
118 witchel 1.1.2.11 }
119 witchel 1.1.2.11 }
120 witchel 1.1.2.11 private void init(final CFGrapher cfgr, final HCode code) {
121 witchel 1.1.2.11 stmToMem = new HashMap();
122 witchel 1.1.2.11 memToStm = new HashMap();
123 witchel 1.1.2.11 initStmMemMaps(cfgr, code);
124 witchel 1.1.2.11 HashSet universe = new HashSet(defUseMap.keySet());
125 witchel 1.1.2.11 universe.addAll(useDefMap.keySet());
126 witchel 1.1.2.11 this.bsf = new BitSetFactory (universe);
127 witchel 1.1.2.11 init_inout(cfgr.getElements(code));
128 witchel 1.1.2.11 }
129 witchel 1.1.2.15 public Live(CFGrapher cfgr, HCode code,
130 witchel 1.1.2.15 Map _defUseMap, Map _useDefMap) {
131 witchel 1.1.2.11 this.defUseMap = _defUseMap;
132 witchel 1.1.2.11 this.useDefMap = _useDefMap;
133 witchel 1.1.2.11 init(cfgr, code);
134 witchel 1.1.2.11 boolean change;
135 witchel 1.1.2.11 Set inbs;
136 witchel 1.1.2.11 Set outbs;
137 witchel 1.1.2.11 int pass = 0;
138 witchel 1.1.2.11 do {
139 witchel 1.1.2.11 change = false;
140 witchel 1.1.2.11 if(trace) {
141 witchel 1.1.2.11 System.err.println("pass " + pass);
142 witchel 1.1.2.11 }
143 cananian 1.6 for(Object hceO : cfgr.getElements(code)) {
144 cananian 1.6 HCodeElement hce = (HCodeElement) hceO;
145 witchel 1.1.2.11 inbs = bsf.makeSet(out(hce));
146 witchel 1.1.2.11 outbs = union_out(cfgr, hce);
147 witchel 1.1.2.11 if(def(hce) != null)
148 witchel 1.1.2.11 inbs.remove(def(hce));
149 witchel 1.1.2.11 if(use(hce) != null) {
150 witchel 1.1.2.11 if(trace)
151 witchel 1.1.2.11 System.err.println("USE " + use(hce));
152 witchel 1.1.2.11 inbs.add(use(hce));
153 witchel 1.1.2.11 }
154 witchel 1.1.2.11 if(trace) {
155 witchel 1.1.2.11 if(!inbs.equals(in(hce))) {
156 witchel 1.1.2.11 System.err.println(hce.hashCode()
157 witchel 1.1.2.11 + " inbs "
158 witchel 1.1.2.11 + in(hce).toString()
159 witchel 1.1.2.11 + " -> "
160 witchel 1.1.2.11 + inbs.toString());
161 witchel 1.1.2.11 }
162 witchel 1.1.2.11 System.err.println(hce.hashCode()
163 witchel 1.1.2.11 + " outbs "
164 witchel 1.1.2.11 + out(hce).toString()
165 witchel 1.1.2.11 + " -> "
166 witchel 1.1.2.11 + outbs.toString());
167 witchel 1.1.2.11 }
168 witchel 1.1.2.11 change = change
169 witchel 1.1.2.11 || !inbs.equals(in(hce))
170 witchel 1.1.2.11 || !outbs.equals(out(hce));
171 witchel 1.1.2.11 out.put(hce, outbs);
172 witchel 1.1.2.11 in.put(hce, inbs);
173 witchel 1.1.2.11 }
174 witchel 1.1.2.11 pass++;
175 witchel 1.1.2.11 } while(change);
176 witchel 1.1.2.11 }
177 witchel 1.1.2.11
178 witchel 1.1.2.11 ////////////////////////////////////////////////////////////
179 witchel 1.1.2.11 // Query functions
180 witchel 1.1.2.11 public HCodeElement use(HCodeElement hce) {
181 witchel 1.1.2.11 if(stmToMem.containsKey(hce)) {
182 witchel 1.1.2.11 MEM m = (MEM)stmToMem.get(hce);
183 witchel 1.1.2.11 if(useDefMap.containsKey(m)) {
184 witchel 1.1.2.11 HCodeElement dom = (HCodeElement)useDefMap.get(m);
185 cananian 1.3.2.1 assert defUseMap.containsKey(dom);
186 cananian 1.3.2.1 assert memToStm.containsKey(dom);
187 witchel 1.1.2.11 return dom;
188 witchel 1.1.2.11 }
189 witchel 1.1.2.11 }
190 witchel 1.1.2.11 return null;
191 witchel 1.1.2.11 }
192 witchel 1.1.2.11 public HCodeElement def(HCodeElement hce) {
193 witchel 1.1.2.11 if(stmToMem.containsKey(hce)) {
194 witchel 1.1.2.11 MEM m = (MEM)stmToMem.get(hce);
195 witchel 1.1.2.11 if(defUseMap.containsKey(m)) {
196 witchel 1.1.2.11 return m;
197 witchel 1.1.2.11 }
198 witchel 1.1.2.11 }
199 witchel 1.1.2.11 return null;
200 witchel 1.1.2.11 }
201 witchel 1.1.2.11 public Set in(HCodeElement hce) {
202 witchel 1.1.2.11 if(in.containsKey(hce) == true) {
203 witchel 1.1.2.11 return ((Set)in.get(hce));
204 witchel 1.1.2.11 }
205 cananian 1.3.2.1 //assert false;
206 witchel 1.1.2.11 return null;
207 witchel 1.1.2.11 }
208 witchel 1.1.2.11 public Set out(HCodeElement hce) {
209 witchel 1.1.2.11 if(out.containsKey(hce) == true) {
210 witchel 1.1.2.11 return ((Set)out.get(hce));
211 witchel 1.1.2.11 }
212 cananian 1.3.2.1 //assert false;
213 witchel 1.1.2.11 return null;
214 witchel 1.1.2.11 }
215 witchel 1.1.2.11
216 witchel 1.1.2.11 private Set union_out(final CFGrapher cfgr, HCodeElement hce) {
217 witchel 1.1.2.11 Collection succ = cfgr.succElemC(hce);
218 witchel 1.1.2.11 Set bs = bsf.makeSet();
219 witchel 1.1.2.11 if(trace) {
220 witchel 1.1.2.11 System.err.print(" union out "
221 witchel 1.1.2.11 + hce.hashCode()
222 witchel 1.1.2.11 + " -> ");
223 witchel 1.1.2.11 if(succ.isEmpty()) {
224 witchel 1.1.2.11 System.err.print("\n");
225 witchel 1.1.2.11 }
226 witchel 1.1.2.11 }
227 cananian 1.6 for(Object suckO : succ) {
228 cananian 1.6 HCodeElement suck = (HCodeElement) suckO;
229 witchel 1.1.2.11 if(trace)
230 witchel 1.1.2.11 System.err.println( suck.hashCode()
231 witchel 1.1.2.11 + " " + in(suck));
232 witchel 1.1.2.11 bs.addAll(in(suck));
233 witchel 1.1.2.11 }
234 witchel 1.1.2.11 return bs;
235 witchel 1.1.2.11 }
236 witchel 1.1.2.11
237 witchel 1.1.2.11 private Map in;
238 witchel 1.1.2.11 private Map out;
239 witchel 1.1.2.11 private Map useDefMap;
240 witchel 1.1.2.11 private Map defUseMap;
241 witchel 1.1.2.11 // Map from Stm to enclosing MEM and back
242 witchel 1.1.2.11 private Map stmToMem;
243 witchel 1.1.2.11 private Map memToStm;
244 cananian 1.5 private net.cscott.jutil.BitSetFactory bsf;
245 witchel 1.1.2.11 private static final boolean trace = false;
246 witchel 1.1.2.11 }
247 witchel 1.1.2.11
248 witchel 1.1.2.2 public class daNum {
249 witchel 1.1.2.2 public daNum(int val, boolean def) {
250 witchel 1.1.2.2 this.val = val;
251 witchel 1.1.2.2 this.def = def;
252 witchel 1.1.2.2 }
253 witchel 1.1.2.2 public boolean isDef() {
254 witchel 1.1.2.2 return def;
255 witchel 1.1.2.2 }
256 witchel 1.1.2.2 public boolean isUse() {
257 witchel 1.1.2.2 return !def;
258 witchel 1.1.2.2 }
259 witchel 1.1.2.2 public int num() {
260 witchel 1.1.2.2 return val;
261 witchel 1.1.2.2 }
262 witchel 1.1.2.3 public int val() {
263 witchel 1.1.2.3 return val;
264 witchel 1.1.2.3 }
265 witchel 1.1.2.2 private int val;
266 witchel 1.1.2.2 private boolean def;
267 witchel 1.1.2.2 }
268 witchel 1.1.2.2
269 witchel 1.1.2.2 /** Use live range information to compute interference graph and
270 witchel 1.1.2.2 allocate DA registers.
271 witchel 1.1.2.2 */
272 witchel 1.1.2.2 class DARegAlloc {
273 witchel 1.1.2.2
274 witchel 1.1.2.2 // All DA variables that are simultaneously live interfere with
275 witchel 1.1.2.2 // each other
276 witchel 1.1.2.6 private void addInter(Map inter, Set in) {
277 cananian 1.6 for(Object meO : in) {
278 cananian 1.6 HCodeElement me = (HCodeElement) meO;
279 cananian 1.3.2.1 assert defUseMap.containsKey(me);
280 witchel 1.1.2.6 Set interset = (Set)inter.get(me);
281 witchel 1.1.2.2 if(interset == null) {
282 witchel 1.1.2.6 interset = new HashSet();
283 witchel 1.1.2.2 inter.put(me, interset);
284 witchel 1.1.2.2 }
285 cananian 1.6 for(Object himO : in) {
286 cananian 1.6 HCodeElement him = (HCodeElement) himO;
287 witchel 1.1.2.3 if(!me.equals(him)) {
288 witchel 1.1.2.2 interset.add(him);
289 witchel 1.1.2.3 }
290 witchel 1.1.2.2 }
291 witchel 1.1.2.2 }
292 witchel 1.1.2.2 }
293 witchel 1.1.2.2
294 witchel 1.1.2.2 // At each program point, find the set of live DA
295 witchel 1.1.2.2 // variables--that is the interference set for this program
296 witchel 1.1.2.2 // point. Each of these
297 witchel 1.1.2.2 // point in the interference set.
298 witchel 1.1.2.2 // This is an interference graph
299 witchel 1.1.2.6 private Map interfereClasses() {
300 witchel 1.1.2.6 Map inter = new HashMap(nodes.size()/4);
301 cananian 1.6 for(Object nodeO : nodes) {
302 cananian 1.6 HCodeElement node = (HCodeElement) nodeO;
303 witchel 1.1.2.2 addInter(inter, live.in(node));
304 witchel 1.1.2.2 addInter(inter, live.out(node));
305 witchel 1.1.2.2 }
306 witchel 1.1.2.2 return inter;
307 witchel 1.1.2.2 }
308 witchel 1.1.2.6 private void removeEdgesTo(HCodeElement hce, Map interGrph) {
309 cananian 1.6 for(Object intersetO : interGrph.values()) {
310 cananian 1.6 Set interset = (Set) intersetO;
311 witchel 1.1.2.2 interset.remove(hce);
312 witchel 1.1.2.2 }
313 witchel 1.1.2.2 }
314 witchel 1.1.2.2 /**
315 witchel 1.1.2.2 The score is the number of tag checks this reference
316 witchel 1.1.2.2 provides, minus the numer of tag checks it prevents by
317 witchel 1.1.2.2 disallowing the references from all of the members of its
318 witchel 1.1.2.2 interference set. This is not accurate, since it doesn't
319 witchel 1.1.2.2 necessarily prevent all of the member of the interference
320 witchel 1.1.2.2 set from being colored, but it seems like a good heuristic.
321 witchel 1.1.2.2 */
322 witchel 1.1.2.6 private int score(HCodeElement hce, Set interset) {
323 cananian 1.3.2.1 assert defUseMap.containsKey(hce);
324 witchel 1.1.2.9 int provides = ((Set)defUseMap.get(hce)).size();
325 witchel 1.1.2.2 int prevents = 0;
326 cananian 1.6 for(Object interO : interset) {
327 cananian 1.6 HCodeElement inter = (HCodeElement) interO;
328 witchel 1.1.2.9 prevents += ((Set)defUseMap.get(inter)).size();
329 witchel 1.1.2.2 }
330 witchel 1.1.2.2 return provides - prevents;
331 witchel 1.1.2.2 }
332 witchel 1.1.2.2 /** Do traditional simplification
333 witchel 1.1.2.2 */
334 witchel 1.1.2.2 // This dismantles the interGrph data structure
335 witchel 1.1.2.6 private void simplify(Map interGrph, Stack colorable) {
336 witchel 1.1.2.2 // For each iteration, find the
337 witchel 1.1.2.2 boolean done = true;
338 witchel 1.1.2.2 Set nodes = interGrph.keySet();
339 witchel 1.1.2.2 do {
340 witchel 1.1.2.2 done = true;
341 witchel 1.1.2.2 boolean simpWorked;
342 witchel 1.1.2.2 do {
343 witchel 1.1.2.2 simpWorked = false;
344 witchel 1.1.2.2 // Read-only copy for iteration
345 witchel 1.1.2.6 Set nodesRO = new HashSet(nodes);
346 cananian 1.6 for(Object hceO : nodesRO) {
347 cananian 1.6 HCodeElement hce = (HCodeElement) hceO;
348 witchel 1.1.2.6 Set interset = (Set)interGrph.get(hce);
349 witchel 1.1.2.2 if(interset.size() < maxRegs) {
350 witchel 1.1.2.2 simpWorked = true;
351 witchel 1.1.2.2 colorable.push(hce);
352 witchel 1.1.2.2 nodes.remove(hce);
353 witchel 1.1.2.2 removeEdgesTo(hce, interGrph);
354 witchel 1.1.2.2 }
355 witchel 1.1.2.2 }
356 witchel 1.1.2.2 } while (simpWorked);
357 witchel 1.1.2.2 // When we get stuck, find the "spill" that is least
358 witchel 1.1.2.2 // attractive, then restart the simplification process
359 witchel 1.1.2.2 int lowest_score = 10000;
360 witchel 1.1.2.2 HCodeElement spillme = null;
361 cananian 1.6 for(Object hceO : nodes) {
362 cananian 1.6 HCodeElement hce = (HCodeElement) hceO;
363 witchel 1.1.2.6 Set interset = (Set)interGrph.get(hce);
364 witchel 1.1.2.2 if(interset.size() > maxRegs) {
365 witchel 1.1.2.2 done = false;
366 witchel 1.1.2.2 int score = score(hce, interset);
367 witchel 1.1.2.2 if(lowest_score > score) {
368 witchel 1.1.2.2 lowest_score = score;
369 witchel 1.1.2.2 spillme = hce;
370 witchel 1.1.2.2 }
371 witchel 1.1.2.2 }
372 witchel 1.1.2.2 }
373 witchel 1.1.2.2 if(spillme != null) {
374 witchel 1.1.2.2 colorable.push(spillme);
375 witchel 1.1.2.2 nodes.remove(spillme);
376 witchel 1.1.2.2 removeEdgesTo(spillme, interGrph);
377 witchel 1.1.2.2 }
378 witchel 1.1.2.2 } while( !done );
379 witchel 1.1.2.2 }
380 witchel 1.1.2.6 private void select(Map interGrph, Stack interNodes) {
381 witchel 1.1.2.16 ArrayList regs = new ArrayList(maxRegs);
382 witchel 1.1.2.16 // Don't shuffle in register 0, stick it on the end
383 witchel 1.1.2.16 for(int i = 1; i < maxRegs; ++i) {
384 witchel 1.1.2.16 regs.add(new Integer(i));
385 witchel 1.1.2.16 }
386 witchel 1.1.2.16 java.util.Random rand = new java.util.Random(seed++);
387 witchel 1.1.2.16 // Shuffle the register numbers
388 witchel 1.1.2.16 for(int i = 0; i < 70; ++i) {
389 witchel 1.1.2.16 int idx = rand.nextInt()% (maxRegs - 1);
390 witchel 1.1.2.16 // signed only in java
391 witchel 1.1.2.16 idx = idx < 0 ? -idx : idx;
392 witchel 1.1.2.16 regs.add(regs.remove(idx));
393 witchel 1.1.2.16 }
394 witchel 1.1.2.16 // Allocate reg 0 last since it is used in function entry/exit
395 witchel 1.1.2.16 regs.add(new Integer(0));
396 witchel 1.1.2.16
397 witchel 1.1.2.2 while(!interNodes.empty()) {
398 witchel 1.1.2.2 HCodeElement hce = (HCodeElement)interNodes.pop();
399 witchel 1.1.2.6 Set interset = (Set)interGrph.get(hce);
400 witchel 1.1.2.6 Set takenDA = new HashSet();
401 cananian 1.6 for(Object interO : interset) {
402 cananian 1.6 HCodeElement inter = (HCodeElement) interO;
403 witchel 1.1.2.2 if(ref2dareg.containsKey(inter)) {
404 witchel 1.1.2.3 takenDA.add(new Integer(((daNum)ref2dareg.get(inter)).num()));
405 witchel 1.1.2.2 }
406 witchel 1.1.2.2 }
407 cananian 1.6 for(Object danumO : regs) {
408 cananian 1.6 Integer danum = (Integer) danumO;
409 witchel 1.1.2.2 // If all the danums are taken, just don't assign this
410 witchel 1.1.2.2 // one a da reg. No spilling.
411 witchel 1.1.2.3 if(takenDA.contains(danum) == false) {
412 cananian 1.3.2.1 assert ref2dareg.containsKey(hce) == false;
413 witchel 1.1.2.16 int i = danum.intValue();
414 witchel 1.1.2.16 // There can't be a single use and def of a DA regstier
415 witchel 1.1.2.16 daNum defda = new daNum(i, true);
416 witchel 1.1.2.16 daNum useda = new daNum(i, false);
417 witchel 1.1.2.16 usedDANum.add(danum);
418 witchel 1.1.2.2 ref2dareg.put(hce, defda);
419 cananian 1.6 for(Object useO : ((Set)defUseMap.get(hce))) {
420 cananian 1.6 HCodeElement use = (HCodeElement) useO;
421 cananian 1.3.2.1 assert ref2dareg.containsKey(use) == false;
422 witchel 1.1.2.2 ref2dareg.put(use, useda);
423 witchel 1.1.2.2 }
424 witchel 1.1.2.2 break;
425 witchel 1.1.2.2 }
426 witchel 1.1.2.2 }
427 witchel 1.1.2.2 }
428 witchel 1.1.2.2 }
429 witchel 1.1.2.6 public Set usedDANum() {
430 witchel 1.1.2.4 return usedDANum;
431 witchel 1.1.2.4 }
432 witchel 1.1.2.11 DARegAlloc(CFGrapher cfgr, HCode code, Live _live,
433 witchel 1.1.2.6 Map _defUseMap, Map _useDefMap) {
434 witchel 1.1.2.11 nodes = cfgr.getElements(code);
435 witchel 1.1.2.2 live = _live;
436 witchel 1.1.2.2 defUseMap = _defUseMap;
437 witchel 1.1.2.2 useDefMap = _useDefMap;
438 witchel 1.1.2.2 ref2dareg = new HashMap(nodes.size()/4);
439 witchel 1.1.2.4 usedDANum = new HashSet();
440 witchel 1.1.2.2 // Register allocation algorithm is inspired by Appel "Modern
441 witchel 1.1.2.2 // compiler implementation in Java" Chapter 11 -- Register
442 witchel 1.1.2.2 // Allocation. We modify it because we have a clear metric
443 witchel 1.1.2.2 // of usefulness--number of tag checks eliminated, and we
444 witchel 1.1.2.2 // have no notion of spilling.
445 witchel 1.1.2.6 Map interGrph = interfereClasses();
446 witchel 1.1.2.2 Stack interNodes = new Stack();
447 witchel 1.1.2.2 simplify(new HashMap(interGrph), interNodes);
448 witchel 1.1.2.2 select(interGrph, interNodes);
449 witchel 1.1.2.2 }
450 witchel 1.1.2.2 public boolean isDef(HCodeElement hce) {
451 witchel 1.1.2.2 return defUseMap.containsKey(hce);
452 witchel 1.1.2.2 }
453 witchel 1.1.2.6 public Map getRef2Dareg() {
454 witchel 1.1.2.2 return ref2dareg;
455 witchel 1.1.2.2 }
456 witchel 1.1.2.2
457 witchel 1.1.2.2 private final int maxRegs = 8;
458 witchel 1.1.2.2 private Live live;
459 witchel 1.1.2.2 private Set nodes;
460 witchel 1.1.2.6 private Map defUseMap;
461 witchel 1.1.2.6 private Map useDefMap;
462 witchel 1.1.2.6 private Map ref2dareg;
463 witchel 1.1.2.6 private Set usedDANum;
464 witchel 1.1.2.3 private static final boolean trace = false;
465 witchel 1.1.2.2 }
466 witchel 1.1.2.2
467 witchel 1.1.2.6 // For every access that dominates another access to the same base
468 witchel 1.1.2.6 // pointer (memory equiv class), make the dominating access the Def
469 witchel 1.1.2.6 // and the subordinate accesses uses
470 witchel 1.1.2.9 private void findDADefUse(HCodeElement[] elts,
471 witchel 1.1.2.6 final CacheEquivalence eqClasses,
472 witchel 1.1.2.6 Map defUseMap, Map useDefMap) {
473 witchel 1.1.2.9 for(int i = 0; i < elts.length; ++i) {
474 witchel 1.1.2.9 HCodeElement hce = elts[i];
475 witchel 1.1.2.9 if(((Tree)hce).kind() == TreeKind.MEM) {
476 witchel 1.1.2.9 MEM mem = (MEM)hce;
477 witchel 1.1.2.11 if(eqClasses.needs_tag_check(mem)) {
478 witchel 1.1.2.11 if(eqClasses.num_using_this_tag(mem) > 1) {
479 witchel 1.1.2.11 // Then this is a def that is used
480 witchel 1.1.2.11 defUseMap.put(mem, eqClasses.ops_using_this_tag(mem));
481 witchel 1.1.2.11 }
482 witchel 1.1.2.11 } else {
483 witchel 1.1.2.11 useDefMap.put(mem, eqClasses.whose_tag_check(mem));
484 witchel 1.1.2.11 }
485 witchel 1.1.2.6 }
486 witchel 1.1.2.6 }
487 witchel 1.1.2.6 }
488 witchel 1.1.2.6
489 witchel 1.1.2.15
490 witchel 1.1.2.2 private void printDA (harpoon.IR.Tree.Code code,
491 witchel 1.1.2.2 final Live live,
492 witchel 1.1.2.6 final Map defUseMap,
493 witchel 1.1.2.6 final Map useDefMap,
494 witchel 1.1.2.6 final Map ref2dareg) {
495 witchel 1.1.2.2 HCodeElement[] nodes = code.getElements();
496 witchel 1.1.2.6 Map _h2n = new HashMap(nodes.length);
497 witchel 1.1.2.2 for(int i = 0; i < nodes.length; ++i) {
498 witchel 1.1.2.2 _h2n.put(nodes[i], new Integer(i));
499 witchel 1.1.2.2 }
500 witchel 1.1.2.6 final Map h2n = _h2n;
501 witchel 1.1.2.2 harpoon.IR.Tree.Print.print(
502 witchel 1.1.2.2 new java.io.PrintWriter(System.out), code,
503 witchel 1.1.2.2 new HCode.PrintCallback(){
504 witchel 1.1.2.2 public void printAfter(java.io.PrintWriter pw,
505 witchel 1.1.2.2 HCodeElement hce) {
506 witchel 1.1.2.2 if(defUseMap.containsKey(hce)) {
507 witchel 1.1.2.2 pw.print(" NODE " + (Integer)h2n.get(hce));
508 witchel 1.1.2.2 }
509 witchel 1.1.2.2 if(useDefMap.containsKey(hce)) {
510 witchel 1.1.2.2 pw.print(" DOM BY "
511 witchel 1.1.2.2 + (Integer)h2n.get(useDefMap.get(hce)));
512 witchel 1.1.2.2 }
513 witchel 1.1.2.2 if(ref2dareg.containsKey(hce)) {
514 witchel 1.1.2.3 daNum danum = (daNum)ref2dareg.get(hce);
515 witchel 1.1.2.3 pw.print(" DA ");
516 witchel 1.1.2.3 if(danum.isUse()) {
517 witchel 1.1.2.3 pw.print(" USE ");
518 witchel 1.1.2.3 } else {
519 witchel 1.1.2.3 pw.print(" DEF ");
520 witchel 1.1.2.3 }
521 witchel 1.1.2.3 pw.print(danum.num());
522 witchel 1.1.2.2 }
523 witchel 1.1.2.2 if(live.in(hce) != null) {
524 witchel 1.1.2.2 boolean notlive = true;
525 witchel 1.1.2.2 if(live.in(hce).size() > 0) {
526 witchel 1.1.2.2 notlive = false;
527 witchel 1.1.2.2 pw.print(" LIVE IN { ");
528 cananian 1.6 for(Object inO : live.in(hce)) {
529 cananian 1.6 HCodeElement in = (HCodeElement) inO;
530 witchel 1.1.2.2 pw.print(in.hashCode() + " ");
531 witchel 1.1.2.2 }
532 witchel 1.1.2.2 pw.print("}");
533 witchel 1.1.2.2 }
534 witchel 1.1.2.2 if(live.out(hce).size() > 0) {
535 witchel 1.1.2.2 notlive = false;
536 witchel 1.1.2.2 pw.print(" LIVE OUT { ");
537 cananian 1.6 for(Object outO : live.out(hce)) {
538 cananian 1.6 HCodeElement out = (HCodeElement) outO;
539 witchel 1.1.2.2 pw.print(out.hashCode() + " ");
540 witchel 1.1.2.2 }
541 witchel 1.1.2.2 pw.print("}");
542 witchel 1.1.2.2 }
543 witchel 1.1.2.2 if(notlive) {
544 witchel 1.1.2.2 pw.print(" NO LIVE ");
545 witchel 1.1.2.2 }
546 witchel 1.1.2.2 }
547 witchel 1.1.2.2 }
548 witchel 1.1.2.2 }
549 witchel 1.1.2.2 );
550 witchel 1.1.2.2 }
551 witchel 1.1.2.2
552 witchel 1.1.2.4 private void report_stats (harpoon.IR.Tree.Code code,
553 witchel 1.1.2.4 final Live live,
554 witchel 1.1.2.6 final Map defUseMap,
555 witchel 1.1.2.6 final Map useDefMap,
556 witchel 1.1.2.4 final DARegAlloc alloc) {
557 witchel 1.1.2.6 Map ref2dareg = alloc.getRef2Dareg();
558 witchel 1.1.2.6 Set useda = alloc.usedDANum();
559 witchel 1.1.2.4 int tot_defs = defUseMap.keySet().size();
560 witchel 1.1.2.4 int tot_uses = 0;
561 cananian 1.6 for(Object usesO : defUseMap.values()) {
562 cananian 1.6 Set uses = (Set) usesO;
563 witchel 1.1.2.4 tot_uses += uses.size();
564 witchel 1.1.2.4 }
565 witchel 1.1.2.4 float avg = tot_defs != 0 ? (float)tot_uses/tot_defs : 0;
566 witchel 1.1.2.4 System.err.print(" DEF-USE " + tot_defs + "-" + tot_uses);
567 witchel 1.1.2.4 if(avg != 0.0 && avg != 1.0) {
568 witchel 1.1.2.4 System.err.print(" (" + avg + ")");
569 witchel 1.1.2.4 }
570 witchel 1.1.2.4 int alloc_def = 0;
571 witchel 1.1.2.4 int alloc_use = 0;
572 cananian 1.6 for(Object danumO : ref2dareg.values()) {
573 cananian 1.6 daNum danum = (daNum) danumO;
574 witchel 1.1.2.4 if(danum.isDef()) alloc_def++; else alloc_use++;
575 witchel 1.1.2.4 }
576 witchel 1.1.2.4 avg = alloc_def != 0 ? (float)alloc_use/alloc_def : 0;
577 witchel 1.1.2.4 System.err.print(" REGDEF-USE " + alloc_def + "-" + alloc_use);
578 witchel 1.1.2.4 if(avg != 0.0 && avg != 1.0) {
579 witchel 1.1.2.4 System.err.print(" (" + avg + ")");
580 witchel 1.1.2.4 }
581 witchel 1.1.2.4 if(useda.size() > 1) {
582 witchel 1.1.2.4 System.err.print(" ALLOC:");
583 cananian 1.6 for(Object danumO : useda) {
584 cananian 1.6 Integer danum = (Integer) danumO;
585 witchel 1.1.2.4 System.err.print(" " + danum);
586 witchel 1.1.2.4 }
587 witchel 1.1.2.4 }
588 witchel 1.1.2.4 System.err.println("");
589 witchel 1.1.2.4
590 witchel 1.1.2.4 }
591 witchel 1.1.2.4
592 witchel 1.1.2.5 /**
593 witchel 1.1.2.5 Returns true if the MEM operation that returned this specifier
594 witchel 1.1.2.5 (from <code>harpoon.Backend.MIPS.Frame.daNum</code>) is the
595 witchel 1.1.2.5 defining access.
596 witchel 1.1.2.5 A defining access does a tag check for the cache line it is on.
597 witchel 1.1.2.5 */
598 witchel 1.1.2.2 static public boolean isDef(Object _danum) {
599 witchel 1.1.2.2 daNum danum = (daNum) _danum;
600 witchel 1.1.2.2 return danum.isDef();
601 witchel 1.1.2.2 }
602 witchel 1.1.2.5 /**
603 witchel 1.1.2.5 Returns true if the MEM operation that returned this specifier
604 witchel 1.1.2.5 (from <code>harpoon.Backend.MIPS.Frame.daNum</code>) is a use.
605 witchel 1.1.2.5 A use memory access can skip the tag check, since it has been
606 witchel 1.1.2.5 done for this line.
607 witchel 1.1.2.5 */
608 witchel 1.1.2.2 static public boolean isUse(Object _danum) {
609 witchel 1.1.2.2 daNum danum = (daNum) _danum;
610 witchel 1.1.2.2 return danum.isUse();
611 witchel 1.1.2.2 }
612 witchel 1.1.2.5 /**
613 witchel 1.1.2.5 Returns the direct address register used by the MEM operation
614 witchel 1.1.2.5 that returned this specifier (from
615 witchel 1.1.2.5 <code>harpoon.Backend.MIPS.Frame.daNum</code>). A direct
616 witchel 1.1.2.5 address register is
617 witchel 1.1.2.5 an on-cache register that points to a specific cache location.
618 witchel 1.1.2.5 You can think of it as a cache line identifier. A dominant
619 witchel 1.1.2.5 accesses might do the tag check and set direct address register
620 witchel 1.1.2.5 3. A subordinate access can skip the tag check, and use direct
621 witchel 1.1.2.5 address register 3 instead. The direct address register number
622 witchel 1.1.2.5 substitutes for the virtual address to identify the cache line.
623 witchel 1.1.2.5 */
624 witchel 1.1.2.2 static public int num(Object _danum) {
625 witchel 1.1.2.2 daNum danum = (daNum) _danum;
626 witchel 1.1.2.2 return danum.num();
627 witchel 1.1.2.2 }
628 witchel 1.1.2.2
629 witchel 1.1.2.5 /** Standard interface to run this analysis */
630 witchel 1.1.2.1 public HCodeFactory codeFactory() {
631 cananian 1.3.2.1 assert parent.getCodeName().equals(CanonicalTreeCode.codename);
632 witchel 1.1.2.1 return new HCodeFactory() {
633 witchel 1.1.2.1 public HCode convert(HMethod m) {
634 witchel 1.1.2.6 hc = parent.convert(m);
635 witchel 1.1.2.1 harpoon.IR.Tree.Code code = (harpoon.IR.Tree.Code) hc;
636 witchel 1.1.2.11 CFGrapher cfgr = code.getGrapher();
637 witchel 1.1.2.6 // Scott's neato analysis
638 cananian 1.1.2.13 CacheEquivalence cacheEq = new CacheEquivalence(code, ch);
639 witchel 1.1.2.6 Map defUseMap = new HashMap();
640 witchel 1.1.2.6 Map useDefMap = new HashMap();
641 witchel 1.1.2.16 findDADefUse(code.getElements(), cacheEq,defUseMap, useDefMap);
642 witchel 1.1.2.15 Live live = new Live(cfgr, code, defUseMap, useDefMap);
643 witchel 1.1.2.11 alloc = new DARegAlloc(cfgr, code, live, defUseMap, useDefMap);
644 witchel 1.1.2.6 Map ref2dareg = alloc.getRef2Dareg();
645 witchel 1.1.2.12 ((harpoon.Backend.MIPS.Frame)frame).setNoTagCheckMap(new HashMap(ref2dareg));
646 witchel 1.1.2.12 ((harpoon.Backend.MIPS.Frame)frame).setUsedDANum(new HashSet(alloc.usedDANum()));
647 witchel 1.1.2.12 if(print_decorated_graph)
648 witchel 1.1.2.2 printDA(code, live, defUseMap, useDefMap, ref2dareg);
649 witchel 1.1.2.4 if(static_stats)
650 witchel 1.1.2.4 report_stats(code, live, defUseMap, useDefMap, alloc);
651 witchel 1.1.2.4
652 witchel 1.1.2.12 live = null;
653 witchel 1.1.2.12 cacheEq = null;
654 witchel 1.1.2.12 cfgr = null;
655 witchel 1.1.2.12 alloc = null;
656 witchel 1.1.2.12 defUseMap = useDefMap = null;
657 witchel 1.1.2.1 return hc;
658 witchel 1.1.2.1 }
659 witchel 1.1.2.1 public String getCodeName() { return parent.getCodeName(); }
660 witchel 1.1.2.1 public void clear(HMethod m) { parent.clear(m); }
661 witchel 1.1.2.1 };
662 witchel 1.1.2.1 }
663 witchel 1.1.2.1
664 witchel 1.1.2.1 public DominatingMemoryAccess(final HCodeFactory parent,
665 cananian 1.1.2.13 final Frame frame, final ClassHierarchy ch) {
666 witchel 1.1.2.1 this.parent = parent;
667 witchel 1.1.2.1 this.frame = frame;
668 cananian 1.1.2.13 this.ch = ch;
669 witchel 1.1.2.1 }
670 witchel 1.1.2.6
671 witchel 1.1.2.16 private static int seed = 8675309;
672 witchel 1.1.2.6 private HCode hc;
673 witchel 1.1.2.1 private HCodeFactory parent;
674 witchel 1.1.2.1 private Frame frame;
675 cananian 1.1.2.13 private ClassHierarchy ch;
676 witchel 1.1.2.4 private DARegAlloc alloc;
677 witchel 1.1.2.1 private boolean trace = false;
678 witchel 1.1.2.12 // This is more useful than trace.
679 witchel 1.1.2.12 private boolean print_decorated_graph = false;
680 witchel 1.1.2.12 // If true print some stats about how many uses per def
681 witchel 1.1.2.4 private boolean static_stats = false;
682 witchel 1.1.2.1 }
683 cananian 1.2