1 kkz 1.1 // DynamicWBInserter.java, created Tue Jul 16 19:13:41 2002 by kkz
2 kkz 1.1 // Copyright (C) 2000 Karen Zee <kkz@tmi.lcs.mit.edu>
3 kkz 1.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 kkz 1.1 package harpoon.Analysis.PreciseGC;
5 kkz 1.1
6 kkz 1.1 import harpoon.Analysis.AllocationInformationMap;
7 kkz 1.1 import harpoon.Analysis.AllocationInformationMap.AllocationPropertiesImpl;
8 kkz 1.1 import harpoon.Analysis.ClassHierarchy;
9 kkz 1.1 import harpoon.Analysis.DefaultAllocationInformation;
10 kkz 1.1 import harpoon.Analysis.Maps.AllocationInformation.AllocationProperties;
11 kkz 1.1 import harpoon.ClassFile.HClass;
12 kkz 1.1 import harpoon.ClassFile.HCode;
13 kkz 1.1 import harpoon.ClassFile.HCodeAndMaps;
14 kkz 1.1 import harpoon.ClassFile.HCodeFactory;
15 kkz 1.1 import harpoon.ClassFile.HConstructor;
16 kkz 1.1 import harpoon.ClassFile.HMethod;
17 kkz 1.1 import harpoon.ClassFile.Linker;
18 kkz 1.1 import harpoon.IR.Quads.ANEW;
19 kkz 1.1 import harpoon.IR.Quads.CALL;
20 kkz 1.1 import harpoon.IR.Quads.Code;
21 kkz 1.1 import harpoon.IR.Quads.Edge;
22 kkz 1.1 import harpoon.IR.Quads.FOOTER;
23 kkz 1.1 import harpoon.IR.Quads.HEADER;
24 kkz 1.1 import harpoon.IR.Quads.METHOD;
25 kkz 1.1 import harpoon.IR.Quads.NEW;
26 kkz 1.1 import harpoon.IR.Quads.PHI;
27 kkz 1.1 import harpoon.IR.Quads.Quad;
28 kkz 1.1 import harpoon.IR.Quads.QuadKind;
29 kkz 1.1 import harpoon.IR.Quads.QuadFactory;
30 kkz 1.1 import harpoon.IR.Quads.THROW;
31 kkz 1.1 import harpoon.Temp.Temp;
32 kkz 1.1 import harpoon.Temp.TempFactory;
33 kkz 1.1
34 kkz 1.1 import java.util.Collections;
35 kkz 1.1 import java.util.HashMap;
36 kkz 1.1 import java.util.HashSet;
37 kkz 1.1 import java.util.Iterator;
38 kkz 1.1 import java.util.Map;
39 kkz 1.1 import java.util.Set;
40 kkz 1.1
41 kkz 1.1 /**
42 kkz 1.1 * <code>DynamicWBInserter</code> inserts instructions where needed to
43 kkz 1.1 * set and clear the per-object bit for dynamic write barriers.
44 kkz 1.1 *
45 kkz 1.1 * @author Karen Zee <kkz@tmi.lcs.mit.edu>
46 cananian 1.2 * @version $Id: DynamicWBInserter.java,v 1.2 2004/02/08 03:20:07 cananian Exp $ */
47 kkz 1.1 public class DynamicWBInserter extends
48 kkz 1.1 harpoon.Analysis.Transformation.MethodMutator {
49 kkz 1.1
50 kkz 1.1 final static boolean DEBUG1 = false;
51 kkz 1.1 final static boolean DEBUG2 = false;
52 kkz 1.1
53 kkz 1.1 private final HMethod clearBitHM;
54 kkz 1.1 private final Map ignoreMap = new HashMap(); /* maps Codes to Sets */
55 kkz 1.1 private final DynamicWBAnalysis dwba;
56 kkz 1.1
57 kkz 1.1 /** Creates a <code>DynamicWBInserter</code>. */
58 kkz 1.1 public DynamicWBInserter(HCodeFactory parent, Linker linker,
59 kkz 1.1 ClassHierarchy ch, DynamicWBAnalysis dwba) {
60 kkz 1.1 super(parent);
61 kkz 1.1 clearBitHM = linker.forName
62 kkz 1.1 ("harpoon.Runtime.PreciseGC.WriteBarrier").getMethod
63 kkz 1.1 ("clearBit", new HClass[] {linker.forName("java.lang.Object")});
64 kkz 1.1 this.dwba = dwba;
65 kkz 1.1 // force passes to run; or else the dwba information will be wrong
66 kkz 1.1 for(Iterator it=ch.callableMethods().iterator(); it.hasNext(); )
67 kkz 1.1 parent.convert((HMethod)it.next());
68 kkz 1.1 }
69 kkz 1.1
70 kkz 1.1 protected HCode mutateHCode(HCodeAndMaps input) {
71 kkz 1.1 Code hc = (Code) input.hcode();
72 kkz 1.1 Map aem = input.ancestorElementMap();
73 kkz 1.1 // fetch allocation information
74 kkz 1.1 AllocationInformationMap aim =
75 kkz 1.1 (AllocationInformationMap) hc.getAllocationInformation();
76 kkz 1.1 // code may not have any associated allocation information
77 kkz 1.1 if (aim == null) {
78 kkz 1.1 aim = new AllocationInformationMap();
79 kkz 1.1 hc.setAllocationInformation(aim);
80 kkz 1.1 }
81 kkz 1.1 // we put all elements in array to avoid screwing up the
82 kkz 1.1 // iterator as we mutate the quad graph in-place.
83 kkz 1.1 Quad[] allquads = (Quad[]) hc.getElements();
84 kkz 1.1 FOOTER footer = ((HEADER) hc.getRootElement()).footer();
85 kkz 1.1 for (int i=0; i<allquads.length; i++) {
86 kkz 1.1 Quad q = allquads[i];
87 kkz 1.1 int kind = q.kind();
88 kkz 1.1 if (kind == QuadKind.NEW || kind == QuadKind.ANEW) {
89 kkz 1.1 Quad ancestor = (Quad) aem.get(q);
90 kkz 1.1 assert ancestor != null : "cannot find ancestor for "+q;
91 kkz 1.1 if (dwba.areWBsRemoved(ancestor)) {
92 kkz 1.1 if (DEBUG1) System.out.println(q);
93 kkz 1.1 // insert set instructions
94 kkz 1.1 associateAllocationProperties(q, aim, true);
95 kkz 1.1 // insert clear instructions
96 kkz 1.1 BitClearAnalysis bca = new BitClearAnalysis(hc, q, true);
97 kkz 1.1 Map call2exception = new HashMap();
98 kkz 1.1 Map edge2temp = bca.needClear;
99 cananian 1.2 for(Object edgeO : edge2temp.keySet()) {
100 cananian 1.2 Edge edge = (Edge) edgeO;
101 kkz 1.1 Temp dst = (Temp) edge2temp.get(edge);
102 kkz 1.1 //footer=insertClear((Quad)edge.to(), edge, dst, footer);
103 kkz 1.1 insertClear((Quad)edge.to(), edge, dst, call2exception);
104 kkz 1.1 }
105 kkz 1.1 footer = insertTHROW(footer, call2exception);
106 kkz 1.1 } else {
107 kkz 1.1 associateAllocationProperties(q, aim, false);
108 kkz 1.1 }
109 kkz 1.1 }
110 kkz 1.1 }
111 kkz 1.1 return hc;
112 kkz 1.1 }
113 kkz 1.1
114 kkz 1.1 // modify the given AllocationInformationMap so that the
115 kkz 1.1 // AllocationProperties associated with Quad q has its
116 kkz 1.1 // setDynamicWBFlag property set accordingly
117 kkz 1.1 private void associateAllocationProperties(Quad q,
118 kkz 1.1 AllocationInformationMap aim,
119 kkz 1.1 boolean setDynamicWBFlag) {
120 kkz 1.1 AllocationProperties ap = aim.query(q);
121 kkz 1.1 if (ap == null)
122 kkz 1.1 ap = DefaultAllocationInformation.SINGLETON.query(q);
123 kkz 1.1 aim.associate(q, new AllocationPropertiesImpl
124 kkz 1.1 (ap.hasInteriorPointers(),
125 kkz 1.1 ap.canBeStackAllocated(),
126 kkz 1.1 ap.canBeThreadAllocated(),
127 kkz 1.1 ap.makeHeap(),
128 kkz 1.1 ap.noSync(),
129 kkz 1.1 ap.allocationHeap(),
130 kkz 1.1 ap.actualClass(),
131 kkz 1.1 setDynamicWBFlag));
132 kkz 1.1 }
133 kkz 1.1
134 kkz 1.1 // helper function to insert placeholder CALL on given Edge
135 kkz 1.1 private FOOTER insertClear(Quad q, Edge e, Temp t, FOOTER f) {
136 kkz 1.1 if (DEBUG1) System.out.println("\tclear before "+q);
137 kkz 1.1 QuadFactory qf = q.getFactory();
138 kkz 1.1 Temp clearexT = new Temp(qf.tempFactory(), "clearex");
139 kkz 1.1 Quad q1 = new CALL(qf, q, clearBitHM,
140 kkz 1.1 new Temp[] { t }, null, clearexT,
141 kkz 1.1 false, false, new Temp[0]);
142 kkz 1.1 Quad q2 = new THROW(qf, q, clearexT);
143 kkz 1.1 Quad.addEdge((Quad) e.from(), e.which_succ(), q1, 0);
144 kkz 1.1 Quad.addEdge(q1, 0, (Quad) e.to(), e.which_pred());
145 kkz 1.1 Quad.addEdge(q1, 1, q2, 0);
146 kkz 1.1 return f.attach(q2, 0);
147 kkz 1.1 }
148 kkz 1.1
149 kkz 1.1 // helper function to insert placeholder CALL on given Edge
150 kkz 1.1 private void insertClear(Quad q, Edge e, Temp t, Map call2exception) {
151 kkz 1.1 if (DEBUG1) System.out.println("\tclear before "+q);
152 kkz 1.1 QuadFactory qf = q.getFactory();
153 kkz 1.1 Temp clearexT = new Temp(qf.tempFactory(), "clearex");
154 kkz 1.1 Quad q1 = new CALL(qf, q, clearBitHM,
155 kkz 1.1 new Temp[] { t }, null, clearexT,
156 kkz 1.1 false, false, new Temp[0]);
157 kkz 1.1 Quad.addEdge((Quad) e.from(), e.which_succ(), q1, 0);
158 kkz 1.1 Quad.addEdge(q1, 0, (Quad) e.to(), e.which_pred());
159 kkz 1.1 call2exception.put(q1, clearexT);
160 kkz 1.1 }
161 kkz 1.1
162 kkz 1.1 // helper function to insert combined THROW for all CALLs
163 kkz 1.1 private FOOTER insertTHROW(FOOTER footer, Map call2exception) {
164 kkz 1.1 Iterator it=call2exception.keySet().iterator();
165 kkz 1.1 if (it.hasNext()) {
166 kkz 1.1 // at least one CALL inserted
167 kkz 1.1 CALL call = (CALL) it.next();
168 kkz 1.1 QuadFactory qf = call.getFactory();
169 kkz 1.1 if (it.hasNext()) {
170 kkz 1.1 // more than one CALL inserted, need PHI
171 kkz 1.1 Temp clearexT = new Temp(qf.tempFactory(), "clearex");
172 kkz 1.1 PHI phi = new PHI(qf, call, new Temp[]
173 kkz 1.1 { clearexT }, new Temp[][]
174 kkz 1.1 {new Temp[] {(Temp) call2exception.get(call)}},
175 kkz 1.1 1);
176 kkz 1.1 Quad.addEdge(call, 1, phi, 0);
177 kkz 1.1 // process rest of CALLs
178 kkz 1.1 for(int i = 1; it.hasNext(); i++) {
179 kkz 1.1 call = (CALL) it.next();
180 kkz 1.1 phi = phi.grow(new Temp[]
181 kkz 1.1 { (Temp) call2exception.get(call) }, i);
182 kkz 1.1 Quad.addEdge(call, 1, phi, i);
183 kkz 1.1 }
184 kkz 1.1 // THROW comes after PHI
185 kkz 1.1 THROW thr = new THROW(qf, call, clearexT);
186 kkz 1.1 Quad.addEdge(phi, 0, thr, 0);
187 kkz 1.1 return footer.attach(thr, 0);
188 kkz 1.1 } else {
189 kkz 1.1 // THROW comes after CALL to write barrier
190 kkz 1.1 THROW thr = new THROW(qf, call, (Temp) call2exception.get(call));
191 kkz 1.1 Quad.addEdge(call, 1, thr, 0);
192 kkz 1.1 return footer.attach(thr, 0);
193 kkz 1.1 }
194 kkz 1.1 }
195 kkz 1.1 return footer;
196 kkz 1.1 }
197 kkz 1.1
198 kkz 1.1 private static class BitClearAnalysis extends PointsToQuadVisitor {
199 kkz 1.1
200 kkz 1.1 private final boolean mobject;
201 kkz 1.1 private final Quad alloc;
202 kkz 1.1 final Map needClear = new HashMap();
203 kkz 1.1
204 kkz 1.1 BitClearAnalysis(Code code, Quad alloc, boolean mobject) {
205 kkz 1.1 super(code);
206 kkz 1.1 this.alloc = alloc; // target allocation
207 kkz 1.1 this.mobject = mobject; // ignore once definitely not mobject?
208 kkz 1.1 // run alias analysis
209 kkz 1.1 analyze(Collections.EMPTY_SET);
210 kkz 1.1 // locate edges on which clear instructions need to be added
211 kkz 1.1 markQuads(alloc, null, get(alloc.prevEdge(0)), new HashSet());
212 kkz 1.1 }
213 kkz 1.1
214 kkz 1.1 // depth-first search algorithm for marking edges that require
215 kkz 1.1 // a clear.
216 kkz 1.1 // requires: q is the current <code>Quad</code>.
217 kkz 1.1 // prevE is the most recently traversed
218 kkz 1.1 // <code>Edge</code>.
219 kkz 1.1 // aliases contains the <code>Temp</code>s that must
220 kkz 1.1 // point to the allocated object on the incoming
221 kkz 1.1 // <code>Edge</code> of q.
222 kkz 1.1 // visited contains <code>Quad</code>s that do not
223 kkz 1.1 // need to be examined further.
224 kkz 1.1 private void markQuads(Quad q, Edge prevE, Set aliases, Set visited) {
225 kkz 1.1 if (DEBUG2) System.out.println(q);
226 kkz 1.1 // already working on this Quad
227 kkz 1.1 if (visited.contains(q)) return;
228 kkz 1.1 int kind = q.kind();
229 kkz 1.1 if (kind != QuadKind.PHI) visited.add(q);
230 kkz 1.1 // find Quads where a clear is needed
231 kkz 1.1 if (kind == QuadKind.RETURN ||
232 kkz 1.1 (kind == QuadKind.THROW &&
233 kkz 1.1 !((THROW)q).throwable().name().startsWith("wbex"))) {
234 kkz 1.1 needClear.put(prevE, aliases.iterator().next());
235 kkz 1.1 } else {
236 kkz 1.1 for (int i = 0; i < q.nextLength(); i++) {
237 kkz 1.1 Edge nextE = q.nextEdge(i);
238 kkz 1.1 Set next = get(nextE);
239 kkz 1.1 if (next.isEmpty()) {
240 kkz 1.1 if (kind != QuadKind.PHI ||
241 kkz 1.1 (((PHI)q).numPhis() == 1 &&
242 kkz 1.1 !((PHI)q).dst(0).name().startsWith("wbex")))
243 kkz 1.1 needClear.put(prevE, aliases.iterator().next());
244 kkz 1.1 } else {
245 kkz 1.1 markQuads(q.next(i), nextE, next, visited);
246 kkz 1.1 }
247 kkz 1.1 }
248 kkz 1.1 }
249 kkz 1.1 }
250 kkz 1.1
251 kkz 1.1 public void visit(ANEW q) {
252 kkz 1.1 if (q == alloc) {
253 kkz 1.1 Set aliases = new HashSet(get(q.prevEdge(0)));
254 kkz 1.1 aliases.add(q.dst());
255 kkz 1.1 raiseValue(q.nextEdge(0), aliases);
256 kkz 1.1 } else if (mobject) {
257 kkz 1.1 raiseValue(q.nextEdge(0), Collections.EMPTY_SET);
258 kkz 1.1 } else {
259 kkz 1.1 visit((Quad)q);
260 kkz 1.1 }
261 kkz 1.1 }
262 kkz 1.1
263 kkz 1.1 public void visit(NEW q) {
264 kkz 1.1 if (q == alloc) {
265 kkz 1.1 Set aliases = new HashSet(get(q.prevEdge(0)));
266 kkz 1.1 aliases.add(q.dst());
267 kkz 1.1 raiseValue(q.nextEdge(0), aliases);
268 kkz 1.1 } else if (mobject) {
269 kkz 1.1 raiseValue(q.nextEdge(0), Collections.EMPTY_SET);
270 kkz 1.1 } else {
271 kkz 1.1 visit((Quad)q);
272 kkz 1.1 }
273 kkz 1.1 }
274 kkz 1.1 }
275 kkz 1.1
276 kkz 1.1 /** A <code>DynamicWBAnalysis</code> identifies <code>NEW</code>
277 kkz 1.1 * and <code>ANEW</code> <code>Quad</code>s for which
278 kkz 1.1 * corresponding write barriers are removed. */
279 kkz 1.1 public interface DynamicWBAnalysis {
280 kkz 1.1
281 kkz 1.1 /** Returns true if this <code>Quad</code> is a
282 kkz 1.1 * <code>NEW</code> or <code>ANEW</code> for which write *
283 kkz 1.1 * barriers have been removed. */
284 kkz 1.1 public boolean areWBsRemoved(Quad q);
285 kkz 1.1
286 kkz 1.1 }
287 kkz 1.1 }