1 kkz 1.1.2.1 // GCInfo.java, created Wed Jan 26 09:40:41 2000 by kkz
2 cananian 1.1.2.12 // 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.Generic;
5 kkz 1.1.2.1
6 kkz 1.1.2.1 import harpoon.Analysis.Instr.RegAlloc.IntermediateCodeFactory;
7 kkz 1.1.2.1 import harpoon.Backend.Generic.Frame;
8 kkz 1.1.2.1 import harpoon.Backend.Generic.RegFileInfo.CommonLoc;
9 kkz 1.1.2.1 import harpoon.Backend.Generic.RegFileInfo.MachineRegLoc;
10 kkz 1.1.2.1 import harpoon.Backend.Generic.RegFileInfo.StackOffsetLoc;
11 kkz 1.1.2.5 import harpoon.ClassFile.HClass;
12 kkz 1.1.2.1 import harpoon.ClassFile.HCodeFactory;
13 kkz 1.1.2.1 import harpoon.ClassFile.HMethod;
14 kkz 1.1.2.1 import harpoon.IR.Assem.Instr;
15 kkz 1.1.2.1 import harpoon.Temp.Label;
16 kkz 1.1.2.1 import harpoon.Util.Util;
17 kkz 1.1.2.1
18 kkz 1.1.2.1 import java.util.ArrayList;
19 kkz 1.1.2.9 import java.util.Collections;
20 kkz 1.1.2.1 import java.util.Iterator;
21 kkz 1.1.2.1 import java.util.List;
22 kkz 1.1.2.1 import java.util.HashMap;
23 kkz 1.1.2.10 import java.util.HashSet;
24 kkz 1.1.2.1 import java.util.Map;
25 kkz 1.1.2.1 import java.util.Set;
26 kkz 1.1.2.1
27 kkz 1.1.2.1 /**
28 kkz 1.1.2.1 * A <code>GCInfo</code> object collects data needed for
29 kkz 1.1.2.1 * garbage collection and makes necessary annotations to
30 kkz 1.1.2.1 * the instruction stream.
31 kkz 1.1.2.1 *
32 cananian 1.1.2.12 * @author Karen K. Zee <kkz@alum.mit.edu>
33 cananian 1.5 * @version $Id: GCInfo.java,v 1.5 2004/02/08 03:20:50 cananian Exp $
34 kkz 1.1.2.1 */
35 kkz 1.1.2.1 public abstract class GCInfo {
36 kkz 1.1.2.1 /** Creates an <code>IntermediateCodeFactory</code> that
37 kkz 1.1.2.1 prepares the code for garbage collection.
38 kkz 1.1.2.1 <BR> <B>requires:</B> The <code>parentFactory</code>
39 kkz 1.1.2.5 must produce code in <code>Instr</code> form.
40 kkz 1.1.2.1 <BR> <B>effects:</B> Returns an
41 kkz 1.1.2.1 <code>IntermediateCodeFactory</code> that modifies
42 kkz 1.1.2.1 the code as needed for a particular garbage
43 kkz 1.1.2.1 collection scheme and stores the necessary
44 kkz 1.1.2.1 garbage collection data in the <code>GCInfo</code>
45 kkz 1.1.2.1 object.
46 kkz 1.1.2.1 */
47 kkz 1.1.2.1 public abstract IntermediateCodeFactory
48 kkz 1.1.2.1 codeFactory(IntermediateCodeFactory parentFactory, Frame frame);
49 kkz 1.1.2.1 /** Returns an ordered <code>List</code> of the
50 kkz 1.1.2.2 <code>GCPoint</code>s in a given <code>HMethod</code>.
51 kkz 1.1.2.2 Returns <code>null</code> if the <code>HMethod</code>
52 kkz 1.1.2.2 has not been evaluated for garbage collection purposes.
53 kkz 1.1.2.2 Returns an empty <code>List</code> if the
54 kkz 1.1.2.2 <code>HMethod</code> has been evaluated and has been
55 kkz 1.1.2.2 found to not contain any GC points.
56 kkz 1.1.2.2 */
57 kkz 1.1.2.5 public abstract List gcPoints(HMethod hm);
58 kkz 1.1.2.5 /** Returns a <code>List</code> of <code>HMethod</code>s
59 kkz 1.1.2.5 with the following properties:
60 kkz 1.1.2.5 - The declaring class of the <code>HMethod</code> is
61 kkz 1.1.2.5 <code>HClass</code>.
62 kkz 1.1.2.5 - The <code>convert</code> method of the
63 kkz 1.1.2.5 <code>IntermediateCodeFactory</code> has been invoked
64 kkz 1.1.2.5 on all the <code>HMethod</code>s in the <code>List</code>.
65 kkz 1.1.2.5 The <code>IntermediateCodeFactory</code> referred
66 kkz 1.1.2.5 to here is the one returned by the <code>codeFactory</code>
67 kkz 1.1.2.5 method of <code>this</code>. Returns null if the given
68 kkz 1.1.2.5 <code>HClass</code> does not declare any methods on which
69 kkz 1.1.2.5 <code>convert</code> has been invoked.
70 kkz 1.1.2.5 - The <code>HMethod</code>s are ordered according to the
71 kkz 1.1.2.5 order in which the <code>convert</code> method was invoked.
72 kkz 1.1.2.5 */
73 kkz 1.1.2.5 public abstract List getOrderedMethods(HClass hc);
74 kkz 1.1.2.1 /** A <code>GCPoint</code> contains information about all
75 kkz 1.1.2.1 * the live objects that the garbage collector needs to
76 kkz 1.1.2.1 * add to the root set at a particular GC point.
77 kkz 1.1.2.1 */
78 kkz 1.1.2.1 public static class GCPoint {
79 kkz 1.1.2.1 protected Instr gcPoint;
80 kkz 1.1.2.1 protected Label label;
81 kkz 1.1.2.6 protected Map regDerivations;
82 kkz 1.1.2.6 protected Map stackDerivations;
83 kkz 1.1.2.1 protected Set liveStackOffsetLocs;
84 kkz 1.1.2.1 protected Set liveMachineRegLocs;
85 kkz 1.1.2.9 protected Map calleeSaved;
86 kkz 1.1.2.1 /** Creates a <code>GCPoint</code> object
87 kkz 1.1.2.1 @param label
88 kkz 1.1.2.1 the <code>Label</code> identifying
89 kkz 1.1.2.1 the <code>gcPoint</code>
90 kkz 1.1.2.1 @param liveDerivations
91 kkz 1.1.2.6 a <code>Map</code> of pointer locations as
92 kkz 1.1.2.5 <code>Set</code>s of <code>CommonLoc</code>s to
93 kkz 1.1.2.5 the corresponding derivation information as
94 kkz 1.1.2.5 <code>DLoc</code>s
95 kkz 1.1.2.1 @param locations
96 kkz 1.1.2.5 a <code>Set</code> of <code>CommonLoc</code>s that
97 kkz 1.1.2.7 represent live pointers at the given GC point
98 kkz 1.1.2.7 @param calleeSaved
99 kkz 1.1.2.9 a <code>Map</code> of the callee-saved
100 kkz 1.1.2.9 <code>BackendDerivation.Register</code>s to
101 kkz 1.1.2.10 the <code>WrappedStackOffsetLoc</code>s
102 kkz 1.1.2.9 where its contents has been stored
103 kkz 1.1.2.5 */
104 kkz 1.1.2.1 public GCPoint(Instr gcPoint, Label label, Map liveDerivations,
105 kkz 1.1.2.9 Set locations, Map calleeSaved) {
106 kkz 1.1.2.1 this.gcPoint = gcPoint;
107 kkz 1.1.2.1 this.label = label;
108 kkz 1.1.2.7 this.calleeSaved = calleeSaved;
109 kkz 1.1.2.10 this.liveStackOffsetLocs = new HashSet();
110 kkz 1.1.2.10 this.liveMachineRegLocs = new HashSet();
111 kkz 1.1.2.6 filter(liveDerivations);
112 kkz 1.1.2.1 filter(locations);
113 kkz 1.1.2.1 }
114 kkz 1.1.2.6 // Sorts derivations by location type of derived pointer
115 kkz 1.1.2.6 private void filter(Map derivations) {
116 kkz 1.1.2.6 regDerivations = new HashMap();
117 kkz 1.1.2.6 stackDerivations = new HashMap();
118 cananian 1.5 for(Object keyO : derivations.keySet()) {
119 cananian 1.5 Set key = (Set) keyO;
120 kkz 1.1.2.6 DLoc derivation = (DLoc)derivations.get(key);
121 cananian 1.5 for(Object locO : key) {
122 cananian 1.5 CommonLoc loc = (CommonLoc) locO;
123 kkz 1.1.2.6 switch(loc.kind()) {
124 kkz 1.1.2.6 case StackOffsetLoc.KIND:
125 kkz 1.1.2.10 WrappedStackOffsetLoc wsol =
126 kkz 1.1.2.10 new WrappedStackOffsetLoc((StackOffsetLoc)loc);
127 kkz 1.1.2.10 stackDerivations.put(wsol, derivation);
128 kkz 1.1.2.10 break;
129 kkz 1.1.2.6 case MachineRegLoc.KIND:
130 kkz 1.1.2.10 WrappedMachineRegLoc wmrl =
131 kkz 1.1.2.10 new WrappedMachineRegLoc((MachineRegLoc)loc);
132 kkz 1.1.2.10 regDerivations.put(wmrl, derivation);
133 kkz 1.1.2.10 break;
134 kkz 1.1.2.6 default:
135 cananian 1.3.2.1 assert false;
136 kkz 1.1.2.6 }
137 kkz 1.1.2.6 }
138 kkz 1.1.2.6 }
139 kkz 1.1.2.6 }
140 kkz 1.1.2.1 // Sorts the various locations by type
141 kkz 1.1.2.1 private void filter(Set locations) {
142 cananian 1.5 for(Object locO : locations) {
143 cananian 1.5 CommonLoc loc = (CommonLoc) locO;
144 kkz 1.1.2.5 switch(loc.kind()) {
145 kkz 1.1.2.5 case StackOffsetLoc.KIND:
146 kkz 1.1.2.10 WrappedStackOffsetLoc wsol =
147 kkz 1.1.2.10 new WrappedStackOffsetLoc((StackOffsetLoc)loc);
148 kkz 1.1.2.10 liveStackOffsetLocs.add(wsol);
149 kkz 1.1.2.10 break;
150 kkz 1.1.2.5 case MachineRegLoc.KIND:
151 kkz 1.1.2.10 WrappedMachineRegLoc wmrl =
152 kkz 1.1.2.10 new WrappedMachineRegLoc((MachineRegLoc)loc);
153 kkz 1.1.2.10 liveMachineRegLocs.add(wmrl);
154 kkz 1.1.2.10 break;
155 kkz 1.1.2.5 default:
156 cananian 1.3.2.1 assert false;
157 kkz 1.1.2.1 }
158 kkz 1.1.2.1 }
159 kkz 1.1.2.1 }
160 kkz 1.1.2.6 /** Returns the <code>Label</code> identifying the GC point */
161 kkz 1.1.2.1 public Label label() { return label; }
162 kkz 1.1.2.9 /** Returns an unmodifiable <code>Map</code> of live derived
163 kkz 1.1.2.10 pointers in <code>WrappedMachineRegLoc</code>s to the
164 kkz 1.1.2.10 derivation information in the form of <code>DLoc</code>s
165 kkz 1.1.2.10 for that GC point */
166 kkz 1.1.2.9 public Map regDerivations() {
167 kkz 1.1.2.9 return Collections.unmodifiableMap(regDerivations);
168 kkz 1.1.2.9 }
169 kkz 1.1.2.9 /** Returns an unmodifiable <code>Map</code> of live derived
170 kkz 1.1.2.9 pointers in <code>StackOffsetLoc</code>s to the
171 kkz 1.1.2.9 derivation information in the form of <code>DLoc</code>s
172 kkz 1.1.2.9 for that GC point */
173 kkz 1.1.2.9 public Map stackDerivations() {
174 kkz 1.1.2.9 return Collections.unmodifiableMap(stackDerivations);
175 kkz 1.1.2.9 }
176 kkz 1.1.2.9 /** Returns an unmodifiable <code>Set</code> of live,
177 kkz 1.1.2.10 non-derived pointers at this GC point as
178 kkz 1.1.2.10 <code>WrappedStackOffsetLoc</code>s */
179 kkz 1.1.2.9 public Set liveStackOffsetLocs() {
180 kkz 1.1.2.9 return Collections.unmodifiableSet(liveStackOffsetLocs);
181 kkz 1.1.2.9 }
182 kkz 1.1.2.9 /** Returns an unmodifiable <code>Set</code> of live,
183 kkz 1.1.2.10 non-derived pointers at this GC point as
184 kkz 1.1.2.10 <code>WrappedMachineRegLoc</code>s */
185 kkz 1.1.2.9 public Set liveMachineRegLocs() {
186 kkz 1.1.2.9 return Collections.unmodifiableSet(liveMachineRegLocs);
187 kkz 1.1.2.9 }
188 kkz 1.1.2.9 /** Returns an unmodifiable <code>Map</code> of callee-saved
189 kkz 1.1.2.9 <code>BackendDerivation.Register</code>s to the
190 kkz 1.1.2.9 <code>CommonLoc</code>s where its contents has been stored */
191 kkz 1.1.2.9 public Map calleeSaved() {
192 kkz 1.1.2.9 return Collections.unmodifiableMap(calleeSaved);
193 kkz 1.1.2.9 }
194 kkz 1.1.2.9 }
195 kkz 1.1.2.9 /** <code>WrappedMachineRegLoc</code> is a wrapper object for
196 kkz 1.1.2.9 <code>MachineRegLoc</code>s that implement special
197 kkz 1.1.2.9 <code>equals</code> and <code>hashCode</code> methods.
198 kkz 1.1.2.9 Two <code>WrappedMachineRegLoc</code> objects are equal
199 kkz 1.1.2.9 if the underlying <code>MachineRegLoc</code>s represent
200 kkz 1.1.2.9 the same register.
201 kkz 1.1.2.9 */
202 kkz 1.1.2.9 public static class WrappedMachineRegLoc {
203 kkz 1.1.2.9 protected MachineRegLoc mrl;
204 kkz 1.1.2.9 /** Creates a <code>WrappedMachineRegLoc</code> object */
205 kkz 1.1.2.9 public WrappedMachineRegLoc(MachineRegLoc mrl) {
206 kkz 1.1.2.9 this.mrl = mrl;
207 kkz 1.1.2.9 }
208 kkz 1.1.2.9 /** Returns the abstract index of underlying
209 kkz 1.1.2.9 <code>MachineRegLoc</code> in the register file.
210 kkz 1.1.2.9 The index returned is identical to what is
211 kkz 1.1.2.9 returned by the <code>regIndex</code> method of
212 kkz 1.1.2.9 the underlying <code>MachineRegLoc</code> object.
213 kkz 1.1.2.9 */
214 kkz 1.1.2.9 public int regIndex() {
215 kkz 1.1.2.9 return mrl.regIndex();
216 kkz 1.1.2.9 }
217 kkz 1.1.2.9 /** Compares two <code>WrappedMachineRegLoc</code> objects
218 kkz 1.1.2.9 for equality. Two <code>WrappedMachineRegLoc</code>
219 kkz 1.1.2.9 objects are equal if they represent the same register.
220 kkz 1.1.2.9 */
221 kkz 1.1.2.9 public boolean equals(Object obj) {
222 kkz 1.1.2.9 try {
223 kkz 1.1.2.9 return (regIndex() == ((WrappedMachineRegLoc)obj).regIndex());
224 kkz 1.1.2.9 } catch (ClassCastException cce) {
225 kkz 1.1.2.9 return false;
226 kkz 1.1.2.9 }
227 kkz 1.1.2.9 }
228 kkz 1.1.2.9 /** Returns the hash code value for the object. Two
229 kkz 1.1.2.9 <code>WrappedMachineRegLoc</code> return the same hash
230 kkz 1.1.2.9 code if the underlying <code>MachineRegLoc</code>
231 kkz 1.1.2.9 objects represent the same register.
232 kkz 1.1.2.9 */
233 kkz 1.1.2.9 public int hashCode() {
234 kkz 1.1.2.9 // okay, i'm cheating quite a bit in this implementation
235 kkz 1.1.2.9 // but this s the simplest way I can think of to ensure
236 kkz 1.1.2.9 // that two WrappedMachineRegLoc objects referring to the
237 kkz 1.1.2.9 // same abstract register are equal
238 kkz 1.1.2.9 return ((new Integer(regIndex())).hashCode());
239 kkz 1.1.2.9 }
240 kkz 1.1.2.9 }
241 kkz 1.1.2.9 /** <code>WrappedStackOffsetLoc</code> is a wrapper object for
242 kkz 1.1.2.9 <code>StackOffsetLoc</code>s that implement special
243 kkz 1.1.2.9 <code>equals</code> and <code>hashCode</code> methods.
244 kkz 1.1.2.9 Two <code>StackOffsetLoc</code> objects are equal
245 kkz 1.1.2.9 if the underlying <code>StackOffsetLoc</code>s represent
246 kkz 1.1.2.9 the same stack offset.
247 kkz 1.1.2.9 */
248 kkz 1.1.2.9 public static class WrappedStackOffsetLoc {
249 kkz 1.1.2.9 protected StackOffsetLoc sol;
250 kkz 1.1.2.9 /** Creates a <code>WrappedStackOffsetLoc</code> object */
251 kkz 1.1.2.9 public WrappedStackOffsetLoc(StackOffsetLoc sol) {
252 kkz 1.1.2.9 this.sol = sol;
253 kkz 1.1.2.9 }
254 kkz 1.1.2.9 /** Returns the abstract stack offset of underlying
255 kkz 1.1.2.9 <code>StackOffsetLoc</code>. The absolute location
256 kkz 1.1.2.9 in memory to which a stack offset refers is
257 kkz 1.1.2.9 context-dependent. For example, the stack offset of
258 kkz 1.1.2.9 an object in one method may have the same abstract
259 kkz 1.1.2.9 value as the stack offset of another object in a
260 kkz 1.1.2.9 different method, but they do not necessarily refer
261 kkz 1.1.2.9 to the same absolute location in the stack.
262 kkz 1.1.2.9 The stack offset returned is identical to what is
263 kkz 1.1.2.9 returned by the <code>stackOffset</code> method of
264 kkz 1.1.2.9 the underlying <code>StackOffsetLoc</code> object.
265 kkz 1.1.2.9 */
266 kkz 1.1.2.9 public int stackOffset() {
267 kkz 1.1.2.9 return sol.stackOffset();
268 kkz 1.1.2.9 }
269 kkz 1.1.2.9 /** Compares two <code>WrappedStackOffsetLoc</code> objects
270 kkz 1.1.2.9 for equality. Two <code>WrappedStackOffsetLoc</code>
271 kkz 1.1.2.9 objects are equal if they refer to the same abstract
272 kkz 1.1.2.9 stack offset.
273 kkz 1.1.2.9 */
274 kkz 1.1.2.9 public boolean equals(Object obj) {
275 kkz 1.1.2.9 try {
276 kkz 1.1.2.9 return (stackOffset() ==
277 kkz 1.1.2.9 ((WrappedStackOffsetLoc)obj).stackOffset());
278 kkz 1.1.2.9 } catch (ClassCastException cce) {
279 kkz 1.1.2.9 return false;
280 kkz 1.1.2.9 }
281 kkz 1.1.2.9 }
282 kkz 1.1.2.9 /** Returns the hash code value for the object. Two
283 kkz 1.1.2.9 <code>WrappedStackOffsetLoc</code> return the same hash
284 kkz 1.1.2.9 code if the underlying <code>StackOffsetLoc</code> refer
285 kkz 1.1.2.9 to the same abstract stack offset.
286 kkz 1.1.2.9 */
287 kkz 1.1.2.9 public int hashCode() {
288 kkz 1.1.2.9 // okay, i'm cheating quite a bit in this implementation
289 kkz 1.1.2.9 // but this s the simplest way I can think of to ensure
290 kkz 1.1.2.9 // that two WrappedStackOffsetLoc objects referring to the
291 kkz 1.1.2.9 // same abstract stack offset are equal
292 kkz 1.1.2.9 return ((new Integer(stackOffset())).hashCode());
293 kkz 1.1.2.9 }
294 kkz 1.1.2.1 }
295 kkz 1.1.2.5 /**
296 kkz 1.1.2.5 Derivation information stored as <code>CommonLoc</code>s.
297 kkz 1.1.2.5 */
298 kkz 1.1.2.5 public static class DLoc {
299 kkz 1.1.2.5 /** Arrays of base pointer locations */
300 kkz 1.1.2.10 public final WrappedMachineRegLoc[] regLocs;
301 kkz 1.1.2.10 public final WrappedStackOffsetLoc[] stackLocs;
302 kkz 1.1.2.5 /** Arrays of booleans */
303 kkz 1.1.2.5 public final boolean[] regSigns;
304 kkz 1.1.2.5 public final boolean[] stackSigns;
305 kkz 1.1.2.5 /** Constructor. */
306 kkz 1.1.2.10 public DLoc(WrappedMachineRegLoc[] regLocs,
307 kkz 1.1.2.10 WrappedStackOffsetLoc[] stackLocs,
308 kkz 1.1.2.5 boolean[] regSigns, boolean[] stackSigns) {
309 kkz 1.1.2.5 this.regLocs = regLocs;
310 kkz 1.1.2.5 this.stackLocs = stackLocs;
311 kkz 1.1.2.5 this.regSigns = regSigns;
312 kkz 1.1.2.5 this.stackSigns = stackSigns;
313 kkz 1.1.2.5 }
314 kkz 1.1.2.5 }
315 kkz 1.1.2.1 }
316 cananian 1.2