1 kkz 1.1 // WriteBarrierInserter.java, created Wed Jun 19 16:47:07 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.ClassFile.HClass;
7 kkz 1.1 import harpoon.ClassFile.HCode;
8 kkz 1.1 import harpoon.ClassFile.HCodeAndMaps;
9 kkz 1.1 import harpoon.ClassFile.HCodeFactory;
10 kkz 1.1 import harpoon.ClassFile.HMethod;
11 kkz 1.1 import harpoon.ClassFile.Linker;
12 kkz 1.1 import harpoon.IR.Quads.ASET;
13 kkz 1.1 import harpoon.IR.Quads.CALL;
14 kkz 1.1 import harpoon.IR.Quads.Code;
15 kkz 1.1 import harpoon.IR.Quads.CONST;
16 kkz 1.1 import harpoon.IR.Quads.Code;
17 kkz 1.1 import harpoon.IR.Quads.Edge;
18 kkz 1.1 import harpoon.IR.Quads.FOOTER;
19 kkz 1.1 import harpoon.IR.Quads.HEADER;
20 kkz 1.1 import harpoon.IR.Quads.Quad;
21 kkz 1.1 import harpoon.IR.Quads.QuadFactory;
22 kkz 1.1 import harpoon.IR.Quads.QuadVisitor;
23 kkz 1.1 import harpoon.IR.Quads.SET;
24 kkz 1.1 import harpoon.IR.Quads.THROW;
25 kkz 1.1 import harpoon.IR.Quads.Code;
26 kkz 1.1 import harpoon.Temp.Temp;
27 kkz 1.1 import harpoon.Temp.TempFactory;
28 kkz 1.1
29 kkz 1.1 import java.util.Collections;
30 kkz 1.1 import java.util.Map;
31 kkz 1.1 import java.util.Set;
32 kkz 1.1
33 kkz 1.1 /**
34 kkz 1.1 * <code>WriteBarrierInserter</code> takes code in Quad form and inserts
35 kkz 1.1 * write barriers for generational garbage collection. Write barriers are
36 kkz 1.1 * inserted before <code>SET</code>s of non-static <code>Object</code> and
37 kkz 1.1 * <code>ASET<code>s of <code>Object</code> arrays.
38 kkz 1.1 *
39 kkz 1.1 * The write barrier used is a call to a native implementation that may be
40 kkz 1.1 * replaced in later passes with a more efficient implementation.
41 kkz 1.1 *
42 kkz 1.1 * @author Karen Zee <kkz@tmi.lcs.mit.edu>
43 kkz 1.1 * @version $Id: WriteBarrierInserter.java,v 1.1 2002/06/25 18:16:22 kkz Exp $
44 kkz 1.1 */
45 kkz 1.1 public class WriteBarrierInserter extends
46 kkz 1.1 harpoon.Analysis.Transformation.MethodMutator {
47 kkz 1.1 private final HClass JLRF;
48 kkz 1.1 private final HMethod arrayWB;
49 kkz 1.1 private final HMethod fieldWB;
50 kkz 1.1 private final WriteBarrierAnalysis wba;
51 kkz 1.1
52 kkz 1.1 /** Creates a <code>WriteBarrierInserter</code>. */
53 kkz 1.1 public WriteBarrierInserter(HCodeFactory parent, Linker linker,
54 kkz 1.1 WriteBarrierAnalysis wba) {
55 kkz 1.1 super(parent);
56 kkz 1.1 this.wba = wba;
57 kkz 1.1 HClass WBC = linker.forName("harpoon.Runtime.PreciseGC.WriteBarrier");
58 kkz 1.1 HClass JLO = linker.forName("java.lang.Object");
59 kkz 1.1 this.JLRF = linker.forName("java.lang.reflect.Field");
60 kkz 1.1 this.arrayWB = WBC.getMethod("asc", new HClass[]
61 kkz 1.1 { JLO, HClass.Int, JLO, HClass.Int });
62 kkz 1.1 this.fieldWB = WBC.getMethod("fsc", new HClass[]
63 kkz 1.1 { JLO, JLRF, JLO, HClass.Int });
64 kkz 1.1 }
65 kkz 1.1
66 kkz 1.1 /** Creates a <code>WriteBarrierInserter</code> using a default
67 kkz 1.1 * no-analysis <code>WriteBarrierAnalysis</code>.
68 kkz 1.1 */
69 kkz 1.1 public WriteBarrierInserter(HCodeFactory parent, Linker linker) {
70 kkz 1.1 this(parent, linker, DefaultWriteBarrierAnalysis.SINGLETON);
71 kkz 1.1 }
72 kkz 1.1
73 kkz 1.1 protected HCode mutateHCode(HCodeAndMaps input) {
74 kkz 1.1 Code hc = (Code) input.hcode();
75 kkz 1.1 // we should not have to update derivation information
76 kkz 1.1 assert hc.getDerivation() == null:
77 kkz 1.1 "WriteBarrierInserter does not handle derivation information";
78 kkz 1.1 HEADER header = (HEADER) hc.getRootElement();
79 kkz 1.1 FOOTER footer = (FOOTER) header.footer();
80 kkz 1.1 Set ignore = wba.getIgnoreSet(hc);
81 kkz 1.1 QuadVisitor qv = new WriteBarrierInserterVisitor
82 kkz 1.1 (footer, ignore, input.ancestorElementMap());
83 kkz 1.1 // we put all elements in array to avoid screwing up
84 kkz 1.1 // the iterator as we mutate the quad graph in-place.
85 kkz 1.1 Quad[] allquads = (Quad[]) hc.getElements();
86 kkz 1.1 for(int i = 0; i < allquads.length; i++)
87 kkz 1.1 allquads[i].accept(qv);
88 kkz 1.1 return hc;
89 kkz 1.1 }
90 kkz 1.1
91 kkz 1.1 private class WriteBarrierInserterVisitor extends QuadVisitor {
92 kkz 1.1 private FOOTER footer;
93 kkz 1.1 private final Set ignore;
94 kkz 1.1 private final Map quadM;
95 kkz 1.1
96 kkz 1.1 /** Creates a <code>WriteBarrierInserterVisitor</code>. */
97 kkz 1.1 WriteBarrierInserterVisitor(FOOTER footer, Set ignore, Map quadM) {
98 kkz 1.1 this.footer = footer;
99 kkz 1.1 this.ignore = ignore;
100 kkz 1.1 this.quadM = quadM;
101 kkz 1.1 }
102 kkz 1.1
103 kkz 1.1 public void visit(Quad q) { /* do nothing */ }
104 kkz 1.1
105 kkz 1.1 /* insert write barrier before ASET, if needed. */
106 kkz 1.1 public void visit(ASET q) {
107 kkz 1.1 // we are interested only in ASETs of arrays
108 kkz 1.1 // containing pointers not found in ignore
109 kkz 1.1 if (q.type().isPrimitive()) return;
110 kkz 1.1 if (ignore.contains(quadM.get(q))) return;
111 kkz 1.1 QuadFactory qf = (QuadFactory) q.getFactory();
112 kkz 1.1 TempFactory tf = qf.tempFactory();
113 kkz 1.1 // create needed Temps
114 kkz 1.1 Temp retex = new Temp(tf, "wbex");
115 kkz 1.1 Temp id = new Temp(tf, "wbid");
116 kkz 1.1 // create needed Quads
117 kkz 1.1 CONST idC = new CONST(qf, q, id, new Integer(0), HClass.Int);
118 kkz 1.1 CALL call = new CALL(qf, q, arrayWB, new Temp[]
119 kkz 1.1 { q.objectref(), q.index(), q.src(), id },
120 kkz 1.1 null, retex, false, false, new Temp[0]);
121 kkz 1.1 THROW thr = new THROW(qf, q, retex);
122 kkz 1.1 // add CONST and CALL before ASET
123 kkz 1.1 splice(idC, q.prevEdge(0));
124 kkz 1.1 splice(call, q.prevEdge(0));
125 kkz 1.1 // add THROW after CALL
126 kkz 1.1 Quad.addEdge(call, 1, thr, 0);
127 kkz 1.1 footer = footer.attach(thr, 0);
128 kkz 1.1 }
129 kkz 1.1
130 kkz 1.1 /* inserts write barrier before SET, if needed. */
131 kkz 1.1 public void visit(SET q) {
132 kkz 1.1 // we are interested only in SETs of non-static
133 kkz 1.1 // Object fields not found in ignore
134 kkz 1.1 if (q.isStatic()) return;
135 kkz 1.1 if (q.field().getType().isPrimitive()) return;
136 kkz 1.1 if (ignore.contains(quadM.get(q))) return;
137 kkz 1.1 QuadFactory qf = (QuadFactory)q.getFactory();
138 kkz 1.1 TempFactory tf = qf.tempFactory();
139 kkz 1.1 // create needed Temps
140 kkz 1.1 Temp field = new Temp(tf, "wbfield");
141 kkz 1.1 Temp retex = new Temp(tf, "wbex");
142 kkz 1.1 Temp id = new Temp(tf, "wbid");
143 kkz 1.1 // create needed Quads
144 kkz 1.1 CONST idC = new CONST(qf, q, id, new Integer(0), HClass.Int);
145 kkz 1.1 CONST fieldC = new CONST(qf, q, field, q.field(), JLRF);
146 kkz 1.1 CALL call = new CALL(qf, q, fieldWB, new Temp[]
147 kkz 1.1 { q.objectref(), field, q.src(), id },
148 kkz 1.1 null, retex, false, false, new Temp[0]);
149 kkz 1.1 THROW thr = new THROW(qf, q, retex);
150 kkz 1.1 // add CONSTs and CALL before SET
151 kkz 1.1 splice(idC, q.prevEdge(0));
152 kkz 1.1 splice(fieldC, q.prevEdge(0));
153 kkz 1.1 splice(call, q.prevEdge(0));
154 kkz 1.1 // add THROW after CALL
155 kkz 1.1 Quad.addEdge(call, 1, thr, 0);
156 kkz 1.1 footer = footer.attach(thr, 0);
157 kkz 1.1 }
158 kkz 1.1
159 kkz 1.1 /* helper method inserts the given Quad on the given Edge. */
160 kkz 1.1 private void splice(Quad q, Edge e) {
161 kkz 1.1 Quad.addEdge((Quad) e.from(), e.which_succ(), q, 0);
162 kkz 1.1 Quad.addEdge(q, 0, (Quad) e.to(), e.which_pred());
163 kkz 1.1 }
164 kkz 1.1 }
165 kkz 1.1
166 kkz 1.1 /** A <code>WriteBarrierAnalysis</code> maps <code>Code</code>s
167 kkz 1.1 * to <code>Set</code>s of Quads for which write barriers have
168 kkz 1.1 * been deemed unnecessary.
169 kkz 1.1 */
170 kkz 1.1 public interface WriteBarrierAnalysis {
171 kkz 1.1
172 kkz 1.1 /** returns a <code>Set</code> of <code>Quad</code>s for
173 kkz 1.1 * the given <code>Code</code> for which write barriers
174 kkz 1.1 * are not required.
175 kkz 1.1 */
176 kkz 1.1 public Set getIgnoreSet(Code hc);
177 kkz 1.1 }
178 kkz 1.1
179 kkz 1.1 /** <code>DefaultWriteBarrierAnalysis</code> returns a no-
180 kkz 1.1 * analysis <code>WriteBarrierAnalysis</code> Object that
181 kkz 1.1 * assumes write barriers are needed for all SET and ASETs
182 kkz 1.1 * of object fields.
183 kkz 1.1 */
184 kkz 1.1 public static class DefaultWriteBarrierAnalysis implements
185 kkz 1.1 WriteBarrierAnalysis {
186 kkz 1.1
187 kkz 1.1 /** A static instance of the singleton
188 kkz 1.1 * <code>DefaultWriteBarrierAnalysis</code>.
189 kkz 1.1 */
190 kkz 1.1 public static final WriteBarrierAnalysis SINGLETON =
191 kkz 1.1 new DefaultWriteBarrierAnalysis();
192 kkz 1.1
193 kkz 1.1 private DefaultWriteBarrierAnalysis() { }
194 kkz 1.1
195 kkz 1.1 /** returns the empty <code>Set</code> for all <code>Code<code>s.
196 kkz 1.1 */
197 kkz 1.1 public Set getIgnoreSet(Code hc) {
198 kkz 1.1 return Collections.EMPTY_SET;
199 kkz 1.1 }
200 kkz 1.1 }
201 kkz 1.1 }
202 kkz 1.1