1 kkz 1.1.2.1 // InsertWriteBarrier.java, created Fri Aug 3 10:52:53 2001 by kkz
2 kkz 1.1.2.1 // Copyright (C) 2000 Karen Zee <kkz@tmi.lcs.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.ClassFile.HClass;
7 kkz 1.1.2.1 import harpoon.ClassFile.HCode;
8 kkz 1.1.2.1 import harpoon.ClassFile.HCodeFactory;
9 kkz 1.1.2.1 import harpoon.ClassFile.HMethod;
10 kkz 1.1.2.1 import harpoon.IR.Tree.DerivationGenerator;
11 kkz 1.1.2.1 import harpoon.IR.Tree.Exp;
12 kkz 1.1.2.1 import harpoon.IR.Tree.ExpList;
13 kkz 1.1.2.1 import harpoon.IR.Tree.MEM;
14 kkz 1.1.2.1 import harpoon.IR.Tree.MOVE;
15 kkz 1.1.2.1 import harpoon.IR.Tree.NAME;
16 kkz 1.1.2.1 import harpoon.IR.Tree.NATIVECALL;
17 kkz 1.1.2.1 import harpoon.IR.Tree.SEQ;
18 kkz 1.1.2.1 import harpoon.IR.Tree.Stm;
19 kkz 1.1.2.1 import harpoon.IR.Tree.Print;
20 kkz 1.1.2.1 import harpoon.IR.Tree.TEMP;
21 kkz 1.1.2.1 import harpoon.IR.Tree.TreeFactory;
22 kkz 1.1.2.1 import harpoon.IR.Tree.Typed;
23 kkz 1.1.2.1 import harpoon.Temp.Label;
24 kkz 1.1.2.1 import harpoon.Temp.Temp;
25 kkz 1.1.2.1 import harpoon.Util.Util;
26 kkz 1.1.2.1
27 kkz 1.1.2.1 import java.util.Arrays;
28 kkz 1.1.2.1 import java.util.Collections;
29 kkz 1.1.2.1 import java.util.HashSet;
30 kkz 1.1.2.1 import java.util.List;
31 kkz 1.1.2.1 import java.util.Set;
32 kkz 1.1.2.1
33 kkz 1.1.2.1 /**
34 kkz 1.1.2.1 * <code>InsertWriteBarrier</code> instruments any writes to pointer
35 kkz 1.1.2.1 * locations with a store check. This pass is used for generational
36 kkz 1.1.2.1 * garbage collection, to keep track of pointers from older to
37 kkz 1.1.2.1 * younger generations.
38 kkz 1.1.2.1 *
39 kkz 1.1.2.1 * @author Karen Zee <kkz@tmi.lcs.mit.edu>
40 cananian 1.5 * @version $Id: InsertWriteBarrier.java,v 1.5 2003/03/11 18:46:55 cananian Exp $
41 kkz 1.1.2.1 */
42 kkz 1.1.2.1 public abstract class InsertWriteBarrier extends
43 kkz 1.1.2.1 harpoon.Analysis.Tree.Simplification {
44 kkz 1.1.2.1
45 kkz 1.1.2.1 // hide constructor
46 kkz 1.1.2.1 private InsertWriteBarrier() { }
47 kkz 1.1.2.1
48 kkz 1.1.2.1 /** Code factory for inserting write barriers to a tree.
49 kkz 1.1.2.1 * Clones the tree before doing transformation in-place.
50 kkz 1.1.2.1 */
51 kkz 1.1.2.1 public static HCodeFactory codeFactory(final HCodeFactory parent) {
52 kkz 1.1.2.1 return new HCodeFactory() {
53 kkz 1.1.2.1 public HCode convert(HMethod m) {
54 kkz 1.1.2.1 HCode hc = parent.convert(m);
55 kkz 1.1.2.1 if (hc!=null) {
56 kkz 1.1.2.1 harpoon.IR.Tree.Code code = (harpoon.IR.Tree.Code) hc;
57 kkz 1.1.2.1 // clone code...
58 kkz 1.1.2.1 code = (harpoon.IR.Tree.Code) code.clone(m).hcode();
59 kkz 1.1.2.1 DerivationGenerator dg = null;
60 kkz 1.1.2.1 try {
61 kkz 1.1.2.1 dg = (DerivationGenerator) code.getTreeDerivation();
62 kkz 1.1.2.1 } catch (ClassCastException ex) { /* i guess not */ }
63 kkz 1.1.2.1 // ...do analysis and modify cloned code in-place.
64 kkz 1.1.2.1 simplify((Stm)code.getRootElement(), dg, HCE_RULES(dg));
65 kkz 1.1.2.1 hc = code;
66 kkz 1.1.2.1 }
67 kkz 1.1.2.1 return hc;
68 kkz 1.1.2.1 }
69 kkz 1.1.2.1 public String getCodeName() { return parent.getCodeName(); }
70 kkz 1.1.2.1 public void clear(HMethod m) { parent.clear(m); }
71 kkz 1.1.2.1 };
72 kkz 1.1.2.1 }
73 kkz 1.1.2.1
74 cananian 1.5 public static List<Rule> HCE_RULES(final DerivationGenerator _dg) {
75 kkz 1.1.2.1 // we keep track of MEMs we have created
76 kkz 1.1.2.1 // since they don't need to be visited
77 cananian 1.5 final Set<MOVE> created = new HashSet<MOVE>();
78 kkz 1.1.2.1 // now make rules.
79 kkz 1.1.2.1 return Arrays.asList(new Rule[] {
80 kkz 1.1.2.1 // this rule matches moves into memory
81 kkz 1.1.2.1 // when the subexpression of the MEM is
82 kkz 1.1.2.1 // already in a TEMP
83 kkz 1.1.2.1 new Rule("movesWithTemps") {
84 kkz 1.1.2.1 public boolean match(Stm stm) {
85 kkz 1.1.2.1 if (!contains(_KIND(stm), _MOVE)) return false;
86 kkz 1.1.2.1 MOVE move = (MOVE) stm;
87 kkz 1.1.2.1 if (!contains(_KIND(move.getDst()), _MEM)) return false;
88 kkz 1.1.2.1 MEM mem = (MEM) move.getDst();
89 kkz 1.1.2.1 if (_dg != null) {
90 kkz 1.1.2.1 HClass hc = _dg.typeMap(mem);
91 kkz 1.1.2.1 if (hc != null && hc.isPrimitive()) return false;
92 kkz 1.1.2.1 hc = _dg.typeMap(move.getSrc());
93 kkz 1.1.2.1 if (hc != null && hc.isPrimitive()) return false;
94 kkz 1.1.2.1 }
95 cananian 1.3.2.1 assert move.type() == Typed.POINTER;
96 kkz 1.1.2.1 return (contains(_KIND(mem.getExp()), _TEMP) &&
97 kkz 1.1.2.1 !created.contains(move));
98 kkz 1.1.2.1 }
99 kkz 1.1.2.1 public Stm apply(TreeFactory tf,
100 kkz 1.1.2.1 Stm stm,
101 kkz 1.1.2.1 DerivationGenerator dg) {
102 kkz 1.1.2.1 // create reference to write-barrier
103 kkz 1.1.2.1 final NAME func =
104 kkz 1.1.2.1 new NAME(tf, stm,
105 kkz 1.1.2.1 new Label(tf.getFrame().getRuntime().
106 kkz 1.1.2.1 getNameMap().c_function_name
107 kkz 1.1.2.1 ("generational_write_barrier")));
108 kkz 1.1.2.1 if (dg != null) dg.putType(func, HClass.Void);
109 kkz 1.1.2.1 // first, we need to clone the MOVE
110 kkz 1.1.2.1 // since it will be removed from the Tree
111 kkz 1.1.2.1 // we know from the match that the target
112 kkz 1.1.2.1 // is a MEM evaluated from a TEMP
113 kkz 1.1.2.1 final MOVE omove = (MOVE) stm;
114 kkz 1.1.2.1 final MEM mem = (MEM)omove.getDst();
115 kkz 1.1.2.1 final MOVE nmove = new MOVE(tf, stm, mem, omove.getSrc());
116 kkz 1.1.2.1 created.add(nmove);
117 kkz 1.1.2.1 // create a new TEMP and update the derivation information
118 kkz 1.1.2.1 final TEMP T1 = (TEMP)mem.getExp();
119 kkz 1.1.2.1 final Temp t = T1.temp;
120 kkz 1.1.2.1 final TEMP T2 = new TEMP(tf, stm, T1.type(), t);
121 kkz 1.1.2.1 if (dg != null) {
122 kkz 1.1.2.1 HClass hc = dg.typeMap(T1);
123 kkz 1.1.2.1 if (hc != null)
124 kkz 1.1.2.1 dg.putTypeAndTemp(T2, hc, t);
125 kkz 1.1.2.1 else
126 kkz 1.1.2.1 dg.putDerivation(T2, dg.derivation(T1));
127 kkz 1.1.2.1 }
128 kkz 1.1.2.1 return new SEQ(tf, stm,
129 kkz 1.1.2.1 new NATIVECALL(tf, stm, null, func,
130 kkz 1.1.2.1 new ExpList(T2, null)),
131 kkz 1.1.2.1 nmove);
132 kkz 1.1.2.1 }
133 kkz 1.1.2.1 },
134 kkz 1.1.2.1 // this rule matches moves into memory
135 kkz 1.1.2.1 // when the subexpression of the MEM is
136 kkz 1.1.2.1 // not in a TEMP
137 kkz 1.1.2.1 new Rule("movesWithoutTemps") {
138 kkz 1.1.2.1 public boolean match(Stm stm) {
139 kkz 1.1.2.1 if (!contains(_KIND(stm), _MOVE)) return false;
140 kkz 1.1.2.1 MOVE move = (MOVE) stm;
141 kkz 1.1.2.1 if (!contains(_KIND(move.getDst()), _MEM)) return false;
142 kkz 1.1.2.1 MEM mem = (MEM) move.getDst();
143 kkz 1.1.2.1 if (_dg != null) {
144 kkz 1.1.2.1 HClass hc = _dg.typeMap(mem);
145 kkz 1.1.2.1 if (hc != null && hc.isPrimitive()) return false;
146 kkz 1.1.2.1 hc = _dg.typeMap(move.getSrc());
147 kkz 1.1.2.1 if (hc != null && hc.isPrimitive()) return false;
148 kkz 1.1.2.1 }
149 cananian 1.3.2.1 assert move.type() == Typed.POINTER;
150 kkz 1.1.2.1 return (!contains(_KIND(mem.getExp()), _TEMP) &&
151 kkz 1.1.2.1 !created.contains(move));
152 kkz 1.1.2.1 }
153 kkz 1.1.2.1 public Stm apply(TreeFactory tf,
154 kkz 1.1.2.1 Stm stm,
155 kkz 1.1.2.1 DerivationGenerator dg) {
156 kkz 1.1.2.1 // create reference to write-barrier
157 kkz 1.1.2.1 final NAME func =
158 kkz 1.1.2.1 new NAME(tf, stm,
159 kkz 1.1.2.1 new Label(tf.getFrame().getRuntime().
160 kkz 1.1.2.1 getNameMap().c_function_name
161 kkz 1.1.2.1 ("generational_write_barrier")));
162 kkz 1.1.2.1 if (dg != null) dg.putType(func, HClass.Void);
163 kkz 1.1.2.1 // we know from the match that we
164 kkz 1.1.2.1 // have a MOVE whose target is a MEM
165 kkz 1.1.2.1 final MOVE omove = (MOVE) stm;
166 kkz 1.1.2.1 final MEM omem = (MEM)omove.getDst();
167 kkz 1.1.2.1 // create a Temp to store the result of
168 kkz 1.1.2.1 // evaluating the subexpression for the MEM
169 kkz 1.1.2.1 final Exp exp = omem.getExp();
170 kkz 1.1.2.1 Temp t = new Temp(tf.tempFactory());
171 kkz 1.1.2.1 TEMP T1 = new TEMP(tf, stm, exp.type(), t);
172 kkz 1.1.2.1 TEMP T2 = new TEMP(tf, stm, exp.type(), t);
173 kkz 1.1.2.1 TEMP T3 = new TEMP(tf, stm, exp.type(), t);
174 kkz 1.1.2.1 // update the derivation information
175 kkz 1.1.2.1 if (dg != null) {
176 kkz 1.1.2.1 HClass hc = dg.typeMap(exp);
177 kkz 1.1.2.1 if (hc != null) {
178 kkz 1.1.2.1 dg.putTypeAndTemp(T1, hc, t);
179 kkz 1.1.2.1 dg.putTypeAndTemp(T2, hc, t);
180 kkz 1.1.2.1 dg.putTypeAndTemp(T3, hc, t);
181 kkz 1.1.2.1 } else {
182 kkz 1.1.2.1 dg.putDerivation(T1, dg.derivation(exp));
183 kkz 1.1.2.1 dg.putDerivation(T2, dg.derivation(exp));
184 kkz 1.1.2.1 dg.putDerivation(T3, dg.derivation(exp));
185 kkz 1.1.2.1 }
186 kkz 1.1.2.1 }
187 kkz 1.1.2.1 // create a new MOVE that assigns the Temp
188 kkz 1.1.2.1 MOVE move1 = new MOVE(tf, stm, T1, exp);
189 kkz 1.1.2.1 // create a new MEM that uses the Temp
190 kkz 1.1.2.1 MEM nmem = new MEM(tf, stm, omem.type(), T2);
191 kkz 1.1.2.1 // update the derivation information
192 kkz 1.1.2.1 dg.update(omem, nmem);
193 kkz 1.1.2.1 // do the original move using the new MEM
194 kkz 1.1.2.1 MOVE move2 = new MOVE(tf, stm, nmem, omove.getSrc());
195 kkz 1.1.2.1 created.add(move2);
196 kkz 1.1.2.1 return new SEQ(tf, stm,
197 kkz 1.1.2.1 new SEQ(tf, stm, move1,
198 kkz 1.1.2.1 new NATIVECALL(tf, stm, null, func,
199 kkz 1.1.2.1 new ExpList(T3,
200 kkz 1.1.2.1 null))),
201 kkz 1.1.2.1 move2);
202 kkz 1.1.2.1 }
203 kkz 1.1.2.1 }
204 kkz 1.1.2.1 });
205 kkz 1.1.2.1 }
206 cananian 1.2 }