1 kkz 1.1.2.1 // BasicGCInfo.java, created Wed Jan 26 11:05:45 2000 by kkz
2 cananian 1.1.2.22 // Copyright (C) 2000 Karen K. Zee <kkz@alum.mit.edu>
3 kkz 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 kkz 1.1.2.1 package harpoon.Backend.Analysis;
5 kkz 1.1.2.1
6 kkz 1.1.2.1 import harpoon.Analysis.BasicBlock;
7 kkz 1.1.2.1 import harpoon.Analysis.DataFlow.LiveTemps;
8 kkz 1.1.2.16 import harpoon.Analysis.Instr.IgnoreSpillUseDefer;
9 pnkfelix 1.1.2.15 import harpoon.Analysis.Instr.RegAlloc.IntermediateCode;
10 kkz 1.1.2.1 import harpoon.Analysis.Instr.RegAlloc.IntermediateCodeFactory;
11 kkz 1.1.2.1 import harpoon.Analysis.Liveness;
12 kkz 1.1.2.6 import harpoon.Analysis.Maps.Derivation;
13 kkz 1.1.2.6 import harpoon.Analysis.Maps.Derivation.DList;
14 kkz 1.1.2.6 import harpoon.Analysis.ReachingDefs;
15 kkz 1.1.2.19 import harpoon.Analysis.ReachingDefsAltImpl;
16 kkz 1.1.2.1 import harpoon.Backend.Generic.Frame;
17 kkz 1.1.2.6 import harpoon.Backend.Generic.GCInfo.DLoc;
18 kkz 1.1.2.1 import harpoon.Backend.Generic.GCInfo.GCPoint;
19 kkz 1.1.2.14 import harpoon.Backend.Generic.GCInfo.WrappedMachineRegLoc;
20 kkz 1.1.2.14 import harpoon.Backend.Generic.GCInfo.WrappedStackOffsetLoc;
21 kkz 1.1.2.6 import harpoon.Backend.Generic.RegFileInfo.CommonLoc;
22 kkz 1.1.2.6 import harpoon.Backend.Generic.RegFileInfo.MachineRegLoc;
23 kkz 1.1.2.6 import harpoon.Backend.Generic.RegFileInfo.StackOffsetLoc;
24 kkz 1.1.2.6 import harpoon.Backend.Generic.RegFileInfo.TempLocator;
25 kkz 1.1.2.11 import harpoon.Backend.Maps.BackendDerivation;
26 kkz 1.1.2.6 import harpoon.ClassFile.HClass;
27 kkz 1.1.2.1 import harpoon.ClassFile.HCode;
28 kkz 1.1.2.1 import harpoon.ClassFile.HCodeEdge;
29 kkz 1.1.2.1 import harpoon.ClassFile.HCodeElement;
30 kkz 1.1.2.1 import harpoon.ClassFile.HCodeFactory;
31 kkz 1.1.2.1 import harpoon.ClassFile.HMethod;
32 kkz 1.1.2.1 import harpoon.IR.Assem.Instr;
33 kkz 1.1.2.1 import harpoon.IR.Assem.InstrCALL;
34 kkz 1.1.2.1 import harpoon.IR.Assem.InstrEdge;
35 kkz 1.1.2.14 import harpoon.IR.Assem.InstrJUMP;
36 kkz 1.1.2.1 import harpoon.IR.Assem.InstrLABEL;
37 kkz 1.1.2.1 import harpoon.IR.Assem.InstrVisitor;
38 kkz 1.1.2.1 import harpoon.IR.Properties.CFGrapher;
39 kkz 1.1.2.16 import harpoon.IR.Properties.UseDefer;
40 kkz 1.1.2.1 import harpoon.Temp.Label;
41 kkz 1.1.2.1 import harpoon.Temp.Temp;
42 kkz 1.1.2.1 import harpoon.Util.Util;
43 kkz 1.1.2.1 import harpoon.Util.Worklist;
44 cananian 1.1.2.24 import harpoon.Util.Collections.WorkSet;
45 kkz 1.1.2.1
46 kkz 1.1.2.1 import java.util.ArrayList;
47 kkz 1.1.2.14 import java.util.Collection;
48 kkz 1.1.2.14 import java.util.Collections;
49 kkz 1.1.2.1 import java.util.HashMap;
50 kkz 1.1.2.1 import java.util.HashSet;
51 kkz 1.1.2.1 import java.util.Iterator;
52 kkz 1.1.2.1 import java.util.List;
53 kkz 1.1.2.1 import java.util.Map;
54 kkz 1.1.2.1 import java.util.Set;
55 kkz 1.1.2.1 /**
56 kkz 1.1.2.1 * <code>BasicGCInfo</code> selects as GC points all
57 kkz 1.1.2.1 * call sites and backward branches.
58 kkz 1.1.2.1 *
59 cananian 1.1.2.22 * @author Karen K. Zee <kkz@alum.mit.edu>
60 cananian 1.6 * @version $Id: BasicGCInfo.java,v 1.6 2004/02/08 03:20:42 cananian Exp $
61 kkz 1.1.2.1 */
62 kkz 1.1.2.1 public class BasicGCInfo extends harpoon.Backend.Generic.GCInfo {
63 kkz 1.1.2.6 // Maps methods to gc points
64 kkz 1.1.2.6 final private Map m = new HashMap();
65 kkz 1.1.2.6 // Maps classes to methods that have been processed
66 kkz 1.1.2.6 final private Map orderedMethods = new HashMap();
67 kkz 1.1.2.14 /** Returns an ordered, unmodifiable <code>List</code> of the
68 kkz 1.1.2.6 <code>GCPoint</code>s in a given <code>HMethod</code>.
69 kkz 1.1.2.6 Returns <code>null</code> if the <code>HMethod</code>
70 kkz 1.1.2.6 has not been evaluated for garbage collection purposes.
71 kkz 1.1.2.6 Returns an empty <code>List</code> if the
72 kkz 1.1.2.6 <code>HMethod</code> has been evaluated and has been
73 kkz 1.1.2.6 found to not contain any GC points.
74 kkz 1.1.2.6 */
75 kkz 1.1.2.6 public List gcPoints(HMethod hm) {
76 kkz 1.1.2.14 return Collections.unmodifiableList((List)m.get(hm));
77 kkz 1.1.2.6 }
78 kkz 1.1.2.14 /** Returns an ordered, unmodifiable <code>List</code> of
79 kkz 1.1.2.14 <code>HMethod</code>s with the following properties:
80 kkz 1.1.2.6 - The declaring class of the <code>HMethod</code> is
81 kkz 1.1.2.6 <code>HClass</code>.
82 kkz 1.1.2.6 - The <code>convert</code> method of the
83 kkz 1.1.2.6 <code>IntermediateCodeFactory</code> has been invoked
84 kkz 1.1.2.6 on all the <code>HMethod</code>s in the <code>List</code>.
85 kkz 1.1.2.6 The <code>IntermediateCodeFactory</code> referred
86 kkz 1.1.2.6 to here is the one returned by the <code>codeFactory</code>
87 kkz 1.1.2.6 method of <code>this</code>. Returns null if the given
88 kkz 1.1.2.6 <code>HClass</code> does not declare any methods on which
89 kkz 1.1.2.6 <code>convert</code> has been invoked.
90 kkz 1.1.2.6 - The <code>HMethod</code>s are ordered according to the
91 kkz 1.1.2.6 order in which the <code>convert</code> method was invoked.
92 kkz 1.1.2.6 */
93 kkz 1.1.2.6 public List getOrderedMethods(HClass hc) {
94 kkz 1.1.2.14 final List result = (List)orderedMethods.get(hc);
95 kkz 1.1.2.14 if (result == null) return null;
96 kkz 1.1.2.14 return Collections.unmodifiableList(result);
97 kkz 1.1.2.6 }
98 kkz 1.1.2.6 // adds a given method to the orderedMethod map
99 kkz 1.1.2.6 // used to maintain the orderedMethod map
100 kkz 1.1.2.6 private void addToOrderedMethods(HMethod hm) {
101 kkz 1.1.2.6 List l = (List)orderedMethods.get(hm.getDeclaringClass());
102 kkz 1.1.2.6 if (l != null) {
103 kkz 1.1.2.6 // hm should not yet be in the List
104 cananian 1.3.2.1 assert !l.contains(hm);
105 kkz 1.1.2.6 } else {
106 kkz 1.1.2.14 // the HClass is not yet in the map; make a new List
107 kkz 1.1.2.6 l = new ArrayList();
108 kkz 1.1.2.6 // add new entry to map
109 kkz 1.1.2.6 orderedMethods.put(hm.getDeclaringClass(), l);
110 kkz 1.1.2.6 }
111 kkz 1.1.2.14 l.add(hm);
112 kkz 1.1.2.6 }
113 kkz 1.1.2.1 /** Returns an IntermediateCodeFactory that inserts
114 kkz 1.1.2.1 <code>InstrLABEL</code>s at garbage collection points
115 kkz 1.1.2.1 and stores the information needed by the garbage
116 kkz 1.1.2.6 collector in <code>this</code>.
117 kkz 1.1.2.1 <BR> <B>requires:</B> The <code>parentFactory</code>
118 kkz 1.1.2.6 in <code>Instr</code> form.
119 kkz 1.1.2.1 */
120 kkz 1.1.2.1 public IntermediateCodeFactory
121 kkz 1.1.2.1 codeFactory(final IntermediateCodeFactory parentFactory,
122 kkz 1.1.2.1 final Frame frame)
123 kkz 1.1.2.1 {
124 kkz 1.1.2.1 return new IntermediateCodeFactory() {
125 kkz 1.1.2.1 protected final HCodeFactory parent = parentFactory;
126 kkz 1.1.2.1 protected final Frame f = frame;
127 kkz 1.1.2.1 protected final CFGrapher cfger = CFGrapher.DEFAULT;
128 kkz 1.1.2.14 protected final Map hce2label = new HashMap();
129 kkz 1.1.2.1 public HCode convert(HMethod hm) {
130 kkz 1.1.2.6 // preserve ordering information
131 kkz 1.1.2.6 addToOrderedMethods(hm);
132 kkz 1.1.2.6 harpoon.IR.Assem.Code hc =
133 kkz 1.1.2.6 (harpoon.IR.Assem.Code)parent.convert(hm);
134 kkz 1.1.2.6 if (hc == null) {
135 kkz 1.1.2.6 // need to map method to empty List
136 kkz 1.1.2.6 // of GC points to indicate that the
137 kkz 1.1.2.6 // method has been processed, but no
138 kkz 1.1.2.6 // GC points were found
139 kkz 1.1.2.6 m.put(hm, new ArrayList());
140 kkz 1.1.2.6 return null;
141 kkz 1.1.2.6 }
142 kkz 1.1.2.14 List hceList = hc.getElementsL();
143 kkz 1.1.2.16 UseDefer ud = new IgnoreSpillUseDefer();
144 kkz 1.1.2.6 // pass 1: liveness and reaching definitions analyses
145 kkz 1.1.2.16 LiveTemps ltAnalysis = analyzeLiveness(hc, ud);
146 kkz 1.1.2.19 ReachingDefs rdAnalysis =
147 kkz 1.1.2.19 new ReachingDefsAltImpl(hc, cfger, ud);
148 kkz 1.1.2.1 // pass 2: identify backward branches
149 kkz 1.1.2.6 Set backEdgeGCPts = identifyBackwardBranches(hc);
150 kkz 1.1.2.1 // pass 3: identify GC points
151 kkz 1.1.2.1 List gcps = new ArrayList();
152 kkz 1.1.2.14 // clear map before going into GCPointFinder
153 kkz 1.1.2.14 hce2label.clear();
154 kkz 1.1.2.16 // GCPointFinder gcpf = new GCPointFinder
155 kkz 1.1.2.16 // (hm, hc, gcps, ltAnalysis, rdAnalysis, backEdgeGCPts,
156 kkz 1.1.2.16 // hc.getDerivation());
157 kkz 1.1.2.16 // For now, ignoring back edges.
158 kkz 1.1.2.6 GCPointFinder gcpf =
159 kkz 1.1.2.14 new GCPointFinder(hm, hc, gcps, ltAnalysis, rdAnalysis,
160 kkz 1.1.2.17 new HashSet(), hc.getDerivation(), ud);
161 kkz 1.1.2.1 for(Iterator instrs = hc.getElementsL().iterator();
162 kkz 1.1.2.1 instrs.hasNext(); )
163 kkz 1.1.2.1 ((Instr)instrs.next()).accept(gcpf);
164 kkz 1.1.2.14 // put labels in
165 cananian 1.6 for(Object iO : hce2label.keySet()) {
166 cananian 1.6 Instr i = (Instr) iO;
167 kkz 1.1.2.14 InstrLABEL label = (InstrLABEL)hce2label.get(i);
168 kkz 1.1.2.14 // instr should only have one successor
169 cananian 1.5 assert cfger.succC(i).size() == 1;
170 kkz 1.1.2.16 // insert label
171 kkz 1.1.2.14 label.layout(i, i.getNext());
172 kkz 1.1.2.14 }
173 kkz 1.1.2.1 m.put(hm, gcps); // add to map
174 kkz 1.1.2.14 return hc;
175 kkz 1.1.2.1 }
176 kkz 1.1.2.1 // do liveness analysis and return analysis
177 kkz 1.1.2.16 private LiveTemps analyzeLiveness(HCode intermediateCode,
178 kkz 1.1.2.16 UseDefer ud) {
179 kkz 1.1.2.1 // use CFGrapher.DEFAULT for now at Felix's bequest
180 kkz 1.1.2.1 // Instrs should graduate to having their own CFGrapher
181 pnkfelix 1.1.2.5 BasicBlock.Factory bbFact =
182 cananian 1.1.2.8 new BasicBlock.Factory(intermediateCode, cfger);
183 kkz 1.1.2.1 Set liveOnExit = f.getRegFileInfo().liveOnExit();
184 kkz 1.1.2.16 LiveTemps ltAnalysis = new LiveTemps(bbFact, liveOnExit, ud);
185 pnkfelix 1.1.2.5 // get an iterator for the solver
186 pnkfelix 1.1.2.5 Iterator it = bbFact.blockSet().iterator();
187 kkz 1.1.2.1 harpoon.Analysis.DataFlow.Solver.worklistSolve(it, ltAnalysis);
188 kkz 1.1.2.16 // ltAnalysis should now contain the liveness
189 kkz 1.1.2.16 // results we want
190 kkz 1.1.2.1 return ltAnalysis;
191 kkz 1.1.2.1 }
192 kkz 1.1.2.16 // identify and return Instrs that come before
193 kkz 1.1.2.16 // backward branches
194 kkz 1.1.2.1 private Set identifyBackwardBranches(HCode intermediateCode) {
195 kkz 1.1.2.1 // pass 1: number Instrs
196 kkz 1.1.2.1 Map ordering = new HashMap();
197 kkz 1.1.2.1 int index = 0;
198 kkz 1.1.2.16 for(Iterator instrs = intermediateCode.getElementsL().
199 kkz 1.1.2.16 iterator(); instrs.hasNext(); )
200 kkz 1.1.2.1 ordering.put(instrs.next(), new Integer(index++));
201 kkz 1.1.2.1 // pass 2: identify backward branches
202 kkz 1.1.2.1 Set results = new HashSet();
203 kkz 1.1.2.1 // work list of edges that need to be examined
204 kkz 1.1.2.1 // start with the successors of the root Instr
205 kkz 1.1.2.1 HCodeElement root = intermediateCode.getRootElement();
206 kkz 1.1.2.1 Worklist toProcess = new WorkSet(cfger.succC(root));
207 kkz 1.1.2.1 while(!toProcess.isEmpty()) {
208 kkz 1.1.2.1 HCodeEdge edge = (HCodeEdge)toProcess.pull();
209 kkz 1.1.2.1 Integer from = (Integer)ordering.get(edge.from());
210 kkz 1.1.2.1 Integer to = (Integer)ordering.get(edge.to());
211 cananian 1.3.2.1 assert from != null && to != null;
212 kkz 1.1.2.1 if (from.intValue() > to.intValue())
213 kkz 1.1.2.1 results.add(edge.from());
214 kkz 1.1.2.1 else {
215 cananian 1.3.2.1 assert from.intValue() != to.intValue();
216 kkz 1.1.2.1 // add to work list the successor edges
217 kkz 1.1.2.16 for (Iterator edges = cfger.succC(edge.to()).
218 kkz 1.1.2.16 iterator(); edges.hasNext(); )
219 kkz 1.1.2.1 toProcess.push(edges.next());
220 kkz 1.1.2.1 }
221 kkz 1.1.2.1 }
222 kkz 1.1.2.1 return results;
223 kkz 1.1.2.1 }
224 kkz 1.1.2.1 public String getCodeName() {
225 kkz 1.1.2.1 return parent.getCodeName(); // should i have my own name?
226 kkz 1.1.2.1 }
227 kkz 1.1.2.1 public void clear(HMethod hm) {
228 kkz 1.1.2.1 parent.clear(hm);
229 kkz 1.1.2.1 m.remove(hm); // remove from map
230 kkz 1.1.2.1 }
231 kkz 1.1.2.1 class GCPointFinder extends InstrVisitor {
232 kkz 1.1.2.1 protected final List results;
233 kkz 1.1.2.1 protected final LiveTemps lt;
234 kkz 1.1.2.6 protected final ReachingDefs rd;
235 kkz 1.1.2.1 protected final Set s;
236 kkz 1.1.2.11 protected final TempLocator tl;
237 cananian 1.1.2.2 protected final harpoon.Analysis.Maps.Derivation d;
238 kkz 1.1.2.14 protected final HMethod hm;
239 kkz 1.1.2.14 protected final HCode hc;
240 kkz 1.1.2.17 protected final UseDefer ud;
241 kkz 1.1.2.1 protected int index = 0;
242 kkz 1.1.2.1 /** Creates a <code>GCPointFinder</code> object.
243 kkz 1.1.2.1 @param results
244 kkz 1.1.2.16 an empty <code>List</code> for storing
245 kkz 1.1.2.16 the resulting <code>GCPoint</code> objects
246 kkz 1.1.2.1 @param lt
247 kkz 1.1.2.16 the completed <code>LiveTemps</code> analysis
248 kkz 1.1.2.1 @param s
249 kkz 1.1.2.16 the <code>Set</code> of <code>Instr</code>s
250 kkz 1.1.2.16 that occur before a backward branch
251 kkz 1.1.2.1 */
252 kkz 1.1.2.14 public GCPointFinder(HMethod hm, HCode hc, List results,
253 kkz 1.1.2.14 LiveTemps lt,
254 kkz 1.1.2.6 ReachingDefs rd, Set s,
255 kkz 1.1.2.17 harpoon.Analysis.Maps.Derivation d,
256 kkz 1.1.2.17 UseDefer ud) {
257 kkz 1.1.2.1 this.hm = hm;
258 kkz 1.1.2.14 this.hc = hc;
259 cananian 1.3.2.1 assert results != null && results.isEmpty();
260 kkz 1.1.2.1 this.results = results;
261 kkz 1.1.2.1 this.lt = lt;
262 kkz 1.1.2.6 this.rd = rd;
263 kkz 1.1.2.1 this.s = s;
264 kkz 1.1.2.1 this.d = d;
265 pnkfelix 1.1.2.15 this.tl = ((IntermediateCode)hc).getTempLocator();
266 kkz 1.1.2.17 this.ud = ud;
267 kkz 1.1.2.1 }
268 kkz 1.1.2.1 public void visit(InstrCALL c) {
269 kkz 1.1.2.6 // all InstrCALLs are GC points
270 kkz 1.1.2.14 if (c.getTargets().size() == 0) {
271 kkz 1.1.2.14 // native calls fall through
272 cananian 1.3.2.1 assert c.canFallThrough : "InstrCALL with no targets must fall through.";
273 kkz 1.1.2.14 updateGCInfo(c, null);
274 kkz 1.1.2.14 } else {
275 kkz 1.1.2.14 List targets = c.getTargets();
276 kkz 1.1.2.14 // non-native calls have a return
277 kkz 1.1.2.14 // address and an exception address
278 cananian 1.3.2.1 assert targets.size() == 2 : "InstrCALL with targets must have regular"+
279 cananian 1.3.2.1 " and exceptional return addresses.";
280 kkz 1.1.2.14 updateGCInfo(c, (Label)targets.get(0));
281 kkz 1.1.2.14 }
282 kkz 1.1.2.14 }
283 kkz 1.1.2.14 public void visit(InstrJUMP j) {
284 kkz 1.1.2.14 // InstrJUMPs are GC points only if
285 kkz 1.1.2.14 // they come before a backward edge
286 kkz 1.1.2.14 if (!s.contains(j)) return;
287 kkz 1.1.2.14 List targets = j.getTargets();
288 cananian 1.3.2.1 assert targets.size() == 1 : "Multiple targets for InstrJUMP.";
289 kkz 1.1.2.14 updateGCInfo(j, (Label)targets.get(0));
290 kkz 1.1.2.1 }
291 kkz 1.1.2.1 public void visit(Instr i) {
292 kkz 1.1.2.1 if (!s.contains(i)) return;
293 kkz 1.1.2.14 // Instrs are GC points only if
294 kkz 1.1.2.14 // they come before a backward edge,
295 kkz 1.1.2.14 // in which case they must have a
296 kkz 1.1.2.14 // conditional target
297 cananian 1.3.2.1 assert i.canFallThrough : "Cannot fall through non-jump,"+
298 cananian 1.3.2.1 " non-call Instr before a backward edge.";
299 kkz 1.1.2.14 List targets = i.getTargets();
300 cananian 1.3.2.1 assert targets.size() == 1 : "No target for Instr before a backward edge.";
301 kkz 1.1.2.14 updateGCInfo(i, (Label)targets.get(0));
302 kkz 1.1.2.14 // alternatively:
303 kkz 1.1.2.14 // updateGCInfo(i, null);
304 kkz 1.1.2.1 }
305 kkz 1.1.2.14 private void updateGCInfo(Instr i, Label l) {
306 kkz 1.1.2.14 // add label if one is not already provided
307 kkz 1.1.2.14 if (l == null) {
308 kkz 1.1.2.14 String str =
309 cananian 1.1.2.23 f.getRuntime().getNameMap().mangle(hm, "gcp_"+index++);
310 kkz 1.1.2.14 l = new Label(str);
311 kkz 1.1.2.14 InstrLABEL label = f.getInstrBuilder().makeLabel(l, i);
312 kkz 1.1.2.14 hce2label.put(i, label);
313 kkz 1.1.2.14 }
314 kkz 1.1.2.14 // we want the live temps going into the instr
315 kkz 1.1.2.6 WorkSet live = new WorkSet();
316 kkz 1.1.2.1 live.addAll(lt.getLiveBefore(i));
317 kkz 1.1.2.6 // filter out non-pointers and derived pointers
318 kkz 1.1.2.6 Set liveLocs = new HashSet();
319 kkz 1.1.2.10 Map derivedPtrs = new HashMap();
320 kkz 1.1.2.13 Map calleeSaved = new HashMap();
321 kkz 1.1.2.6 while(!live.isEmpty()) {
322 kkz 1.1.2.6 Temp t = (Temp)live.pull();
323 kkz 1.1.2.19 //System.out.println(t.toString()+" is live.");
324 cananian 1.3.2.1 assert i != null : "Cannot pass null instruction"+
325 cananian 1.3.2.1 " to reaching definitions analysis";
326 cananian 1.3.2.1 assert t != null : "Cannot pass null temporary"+
327 cananian 1.3.2.1 " to reaching definitions analysis";
328 kkz 1.1.2.16 Iterator defPtsit =
329 kkz 1.1.2.16 rd.reachingDefs(i, t).iterator();
330 kkz 1.1.2.16 // there must be at least one defintion
331 kkz 1.1.2.16 // that reaches i
332 cananian 1.3.2.1 assert defPtsit.hasNext() : "Cannot find"+
333 kkz 1.1.2.14 " definition of "+t.toString()+" at "+
334 cananian 1.3.2.1 i.toString();
335 kkz 1.1.2.14 Instr defPt = (Instr)defPtsit.next();
336 kkz 1.1.2.6 // all of the above defPts should work
337 kkz 1.1.2.19 DList ddl = d.derivation(defPt, t);
338 kkz 1.1.2.11 if (ddl == null) {
339 kkz 1.1.2.11 // try and find its type
340 kkz 1.1.2.19 HClass hclass = d.typeMap(defPt, t);
341 kkz 1.1.2.11 if (hclass == null) {
342 kkz 1.1.2.11 // no derivation, no type means
343 kkz 1.1.2.11 // this is a callee-saved register
344 kkz 1.1.2.11 BackendDerivation bd = (BackendDerivation)d;
345 kkz 1.1.2.11 // find out which register's contents we have
346 kkz 1.1.2.11 BackendDerivation.Register reg =
347 kkz 1.1.2.14 bd.calleeSaveRegister(defPt, t);
348 kkz 1.1.2.14 Set locationSet = tl.locate(t, defPt);
349 kkz 1.1.2.13 // the following may be a bad assumption
350 cananian 1.3.2.1 assert locationSet.size() == 1;
351 kkz 1.1.2.11 for (Iterator it=locationSet.iterator();
352 kkz 1.1.2.12 it.hasNext(); ) {
353 kkz 1.1.2.13 calleeSaved.put(reg, (CommonLoc)it.next());
354 kkz 1.1.2.12 }
355 kkz 1.1.2.11 } else if (!hclass.isPrimitive())
356 kkz 1.1.2.11 // a non-derived pointer: add all
357 kkz 1.1.2.11 // locations where it can be found
358 kkz 1.1.2.14 liveLocs.addAll(tl.locate(t, defPt));
359 kkz 1.1.2.11 } else
360 kkz 1.1.2.10 // a derived pointer: add to set of derived ptrs
361 kkz 1.1.2.14 derivedPtrs.put(tl.locate(t, defPt),
362 kkz 1.1.2.6 unroll(ddl, i));
363 kkz 1.1.2.1 }
364 kkz 1.1.2.11 GCPoint gcp =
365 kkz 1.1.2.14 new GCPoint(i, l, derivedPtrs, liveLocs, calleeSaved);
366 kkz 1.1.2.1 results.add(gcp);
367 kkz 1.1.2.1 }
368 kkz 1.1.2.6 private DLoc unroll(DList ddl, Instr instr) {
369 kkz 1.1.2.6 List regLocs = new ArrayList();
370 kkz 1.1.2.6 List regSigns = new ArrayList();
371 kkz 1.1.2.6 List stackLocs = new ArrayList();
372 kkz 1.1.2.6 List stackSigns = new ArrayList();
373 kkz 1.1.2.6 while(ddl != null) {
374 kkz 1.1.2.6 Temp base = ddl.base;
375 pnkfelix 1.1.2.20 // System.out.println("doing reachingDefs"+
376 kkz 1.1.2.19 // " instr:"+instr+
377 kkz 1.1.2.19 // " base:"+base);
378 pnkfelix 1.1.2.18 Collection c1 = rd.reachingDefs(instr, base);
379 cananian 1.3.2.1 assert c1 != null;
380 cananian 1.3.2.1 assert c1.size() >0;
381 pnkfelix 1.1.2.18 Instr[] defPts = (Instr[])
382 pnkfelix 1.1.2.18 c1.toArray(new Instr[c1.size()]);
383 kkz 1.1.2.6 // any of the definition points should work
384 pnkfelix 1.1.2.18 Collection c2 = tl.locate(base, defPts[0]);
385 cananian 1.3.2.1 assert c2 != null && c2.size() > 0;
386 pnkfelix 1.1.2.18 CommonLoc[] locs = (CommonLoc[])
387 pnkfelix 1.1.2.18 c2.toArray(new CommonLoc[c2.size()]);
388 kkz 1.1.2.6 // any of the CommonLocs should work
389 kkz 1.1.2.6 switch(locs[0].kind()) {
390 kkz 1.1.2.6 case StackOffsetLoc.KIND:
391 kkz 1.1.2.14 WrappedStackOffsetLoc wsol = new
392 kkz 1.1.2.14 WrappedStackOffsetLoc((StackOffsetLoc)locs[0]);
393 kkz 1.1.2.14 stackLocs.add(wsol);
394 kkz 1.1.2.6 stackSigns.add(new Boolean(ddl.sign));
395 kkz 1.1.2.6 break;
396 kkz 1.1.2.6 case MachineRegLoc.KIND:
397 kkz 1.1.2.14 WrappedMachineRegLoc wmrl = new
398 kkz 1.1.2.14 WrappedMachineRegLoc((MachineRegLoc)locs[0]);
399 kkz 1.1.2.14 regLocs.add(wmrl);
400 kkz 1.1.2.6 regSigns.add(new Boolean(ddl.sign));
401 kkz 1.1.2.6 break;
402 cananian 1.3.2.1 default: assert false;
403 kkz 1.1.2.6 }
404 pnkfelix 1.1.2.18 ddl = ddl.next; // FSK moved this outside switch
405 kkz 1.1.2.6 }
406 cananian 1.3.2.1 assert regLocs.size() == regSigns.size();
407 kkz 1.1.2.14 WrappedMachineRegLoc[] regArray =
408 kkz 1.1.2.14 (WrappedMachineRegLoc[])regLocs.toArray
409 kkz 1.1.2.14 (new WrappedMachineRegLoc[0]);
410 kkz 1.1.2.6 boolean[] regSignArray = new boolean[regSigns.size()];
411 kkz 1.1.2.6 int i=0;
412 kkz 1.1.2.6 for(Iterator it=regSigns.iterator(); it.hasNext(); )
413 kkz 1.1.2.6 regSignArray[i++] =
414 kkz 1.1.2.6 ((Boolean)it.next()).booleanValue();
415 cananian 1.3.2.1 assert stackLocs.size() == stackSigns.size();
416 kkz 1.1.2.14 WrappedStackOffsetLoc[] stackArray =
417 kkz 1.1.2.14 (WrappedStackOffsetLoc[])stackLocs.toArray
418 kkz 1.1.2.14 (new WrappedStackOffsetLoc[0]);
419 kkz 1.1.2.6 boolean[] stackSignArray = new boolean[stackSigns.size()];
420 kkz 1.1.2.6 int j=0;
421 kkz 1.1.2.6 for(Iterator it=stackSigns.iterator(); it.hasNext(); )
422 kkz 1.1.2.6 stackSignArray[j++] =
423 kkz 1.1.2.6 ((Boolean)it.next()).booleanValue();
424 kkz 1.1.2.6
425 kkz 1.1.2.6 return new DLoc(regArray, stackArray,
426 kkz 1.1.2.6 regSignArray, stackSignArray);
427 kkz 1.1.2.6 }
428 kkz 1.1.2.1 }
429 kkz 1.1.2.1 };
430 kkz 1.1.2.1 } // codeFactory
431 kkz 1.1.2.1 } // class
432 kkz 1.1.2.16
433 kkz 1.1.2.16
434 kkz 1.1.2.6
435 kkz 1.1.2.1
436 cananian 1.2