1 kkz 1.1.2.1 // MakeGCThreadSafe.java, created Tue Jan 23 14:24:35 2001 by kkz
2 cananian 1.1.2.4 // 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.Backend.Generic.Frame;
7 kkz 1.1.2.1 import harpoon.ClassFile.HClass;
8 kkz 1.1.2.1 import harpoon.ClassFile.HCode;
9 kkz 1.1.2.2 import harpoon.ClassFile.HCodeEdge;
10 kkz 1.1.2.2 import harpoon.ClassFile.HCodeElement;
11 kkz 1.1.2.1 import harpoon.ClassFile.HCodeFactory;
12 kkz 1.1.2.1 import harpoon.ClassFile.HMethod;
13 kkz 1.1.2.2 import harpoon.IR.Properties.CFGrapher;
14 kkz 1.1.2.1 import harpoon.IR.Tree.CanonicalTreeCode;
15 kkz 1.1.2.1 import harpoon.IR.Tree.CJUMP;
16 kkz 1.1.2.1 import harpoon.IR.Tree.DerivationGenerator;
17 kkz 1.1.2.2 import harpoon.IR.Tree.Exp;
18 kkz 1.1.2.2 import harpoon.IR.Tree.JUMP;
19 kkz 1.1.2.1 import harpoon.IR.Tree.LABEL;
20 kkz 1.1.2.1 import harpoon.IR.Tree.MEM;
21 kkz 1.1.2.1 import harpoon.IR.Tree.METHOD;
22 kkz 1.1.2.1 import harpoon.IR.Tree.NAME;
23 kkz 1.1.2.1 import harpoon.IR.Tree.NATIVECALL;
24 kkz 1.1.2.1 import harpoon.IR.Tree.SEQ;
25 kkz 1.1.2.1 import harpoon.IR.Tree.Stm;
26 kkz 1.1.2.1 import harpoon.IR.Tree.Type;
27 kkz 1.1.2.2 import harpoon.IR.Tree.Tree;
28 kkz 1.1.2.1 import harpoon.IR.Tree.TreeFactory;
29 kkz 1.1.2.2 import harpoon.IR.Tree.TreeKind;
30 kkz 1.1.2.1 import harpoon.Temp.Label;
31 kkz 1.1.2.1 import harpoon.Util.Util;
32 kkz 1.1.2.2 import harpoon.Util.Worklist;
33 cananian 1.1.2.6 import harpoon.Util.Collections.WorkSet;
34 kkz 1.1.2.1
35 kkz 1.1.2.1 import java.util.ArrayList;
36 kkz 1.1.2.1 import java.util.Arrays;
37 kkz 1.1.2.2 import java.util.HashMap;
38 kkz 1.1.2.1 import java.util.HashSet;
39 kkz 1.1.2.2 import java.util.Iterator;
40 kkz 1.1.2.1 import java.util.List;
41 kkz 1.1.2.2 import java.util.Map;
42 kkz 1.1.2.1 import java.util.Set;
43 kkz 1.1.2.1
44 kkz 1.1.2.1 /**
45 kkz 1.1.2.2 * <code>MakeGCThreadSafe</code> adds checks to see whether another thread
46 kkz 1.1.2.2 * has caused a GC, and if so, halts the current thread by calling out to
47 kkz 1.1.2.2 * the runtime. The check is added to the beginning of each method (after
48 kkz 1.1.2.2 * the <code>METHOD</code> node), and to backedges (before
49 kkz 1.1.2.2 * <code>JUMP</code>s and <code>CJUMP</code>s that can branch to an
50 kkz 1.1.2.2 * earlier node). The purpose of the former is to ensure that all threads
51 kkz 1.1.2.2 * halt in a timely manner.
52 kkz 1.1.2.1 * <p>
53 kkz 1.1.2.1 * This pass is invoked in <code>harpoon.Main.SAMain</code>.
54 kkz 1.1.2.1 *
55 cananian 1.1.2.4 * @author Karen K. Zee <kkz@alum.mit.edu>
56 cananian 1.6 * @version $Id: MakeGCThreadSafe.java,v 1.6 2004/02/08 03:20:42 cananian Exp $
57 kkz 1.1.2.1 */
58 kkz 1.1.2.1 public class MakeGCThreadSafe extends harpoon.Analysis.Tree.Simplification {
59 kkz 1.1.2.1 // hide constructor
60 kkz 1.1.2.1 private MakeGCThreadSafe() { }
61 kkz 1.1.2.1 /** Code factory for adding GC polling calls to a
62 kkz 1.1.2.1 * canonical tree. Clones the tree before doing
63 kkz 1.1.2.2 * optimization in-place. (Stolen from
64 kkz 1.1.2.2 * <code>Analysis.Tree.JumpOptimization</code>;
65 kkz 1.1.2.2 * it wouldn't have made any sense to subclass.)
66 kkz 1.1.2.1 */
67 kkz 1.1.2.1 public static HCodeFactory codeFactory(final HCodeFactory parent,
68 kkz 1.1.2.1 final Frame f) {
69 cananian 1.3.2.1 assert parent.getCodeName().equals(CanonicalTreeCode.codename);
70 kkz 1.1.2.1 final Frame frame = f;
71 kkz 1.1.2.1 return new HCodeFactory() {
72 kkz 1.1.2.1 public HCode convert(HMethod m) {
73 kkz 1.1.2.1 HCode hc = parent.convert(m);
74 kkz 1.1.2.1 if (hc!=null) {
75 kkz 1.1.2.1 harpoon.IR.Tree.Code code = (harpoon.IR.Tree.Code) hc;
76 kkz 1.1.2.1 // clone code...
77 kkz 1.1.2.1 code = (harpoon.IR.Tree.Code) code.clone(m).hcode();
78 kkz 1.1.2.1 DerivationGenerator dg = null;
79 kkz 1.1.2.1 try {
80 kkz 1.1.2.1 dg = (DerivationGenerator) code.getTreeDerivation();
81 kkz 1.1.2.1 } catch (ClassCastException ex) { /* i guess not */ }
82 kkz 1.1.2.1 // ...do analysis and modify cloned code in-place.
83 kkz 1.1.2.1 simplify((Stm)code.getRootElement(), dg,
84 kkz 1.1.2.1 HCE_RULES(code, f));
85 kkz 1.1.2.1 hc = code;
86 kkz 1.1.2.1 }
87 kkz 1.1.2.1 return hc;
88 kkz 1.1.2.1 }
89 kkz 1.1.2.1 public String getCodeName() { return parent.getCodeName(); }
90 kkz 1.1.2.1 public void clear(HMethod m) { parent.clear(m); }
91 kkz 1.1.2.1 };
92 kkz 1.1.2.1 }
93 cananian 1.5 public static List<Rule> HCE_RULES(final harpoon.IR.Tree.Code code,
94 kkz 1.1.2.1 final Frame f) {
95 kkz 1.1.2.2 // collect information about reachable JUMPs and CJUMPs
96 cananian 1.5 CFGrapher<Tree> cfgr = code.getGrapher();
97 cananian 1.5 final Tree[] roots = cfgr.getFirstElements(code);
98 cananian 1.5 final Set<Tree> reachable = new HashSet<Tree>();
99 cananian 1.5 Worklist<Tree> worklist = new WorkSet<Tree>();
100 kkz 1.1.2.2 for(int i = 0; i < roots.length; i++)
101 kkz 1.1.2.2 worklist.push(roots[i]);
102 kkz 1.1.2.2 while(!worklist.isEmpty()) {
103 cananian 1.5 Tree curr = worklist.pull();
104 kkz 1.1.2.2 reachable.add(curr);
105 cananian 1.6 for(HCodeEdge<Tree> succ : cfgr.succC(curr)) {
106 kkz 1.1.2.2 if (!reachable.contains(succ.to()))
107 kkz 1.1.2.2 worklist.push(succ.to());
108 kkz 1.1.2.2 }
109 kkz 1.1.2.2 }
110 kkz 1.1.2.2 cfgr = null;
111 kkz 1.1.2.2 worklist = null;
112 kkz 1.1.2.2 // collect information to identify back edges
113 kkz 1.1.2.2 final Map m = new HashMap();
114 kkz 1.1.2.2 int count = 0;
115 cananian 1.5 for (Iterator<Tree> it=code.getElementsI(); it.hasNext(); ) {
116 cananian 1.5 Tree tr = it.next();
117 kkz 1.1.2.2 if (tr.kind() == TreeKind.LABEL)
118 kkz 1.1.2.2 m.put(((LABEL)tr).label, new Integer(count++));
119 kkz 1.1.2.2 else if (tr.kind() == TreeKind.CJUMP ||
120 kkz 1.1.2.2 tr.kind() == TreeKind.JUMP)
121 kkz 1.1.2.2 m.put(tr, new Integer(count++));
122 kkz 1.1.2.2 }
123 kkz 1.1.2.1 final Label LGCflag = new Label("halt_for_GC_flag");
124 cananian 1.1.2.5 final Label LGCfunc = new Label(f.getRuntime().getNameMap().c_function_name
125 kkz 1.1.2.1 ("halt_for_GC"));
126 cananian 1.5 final Set<CJUMP> cjumps = new HashSet<CJUMP>();
127 kkz 1.1.2.1 return Arrays.asList(new Rule[] {
128 kkz 1.1.2.2 new Rule("GCpollatMethod") {
129 cananian 1.5 private final Set<Stm> clones = new HashSet<Stm>();
130 kkz 1.1.2.1 public boolean match(Stm stm) {
131 kkz 1.1.2.2 // poll at the beginning of each method
132 kkz 1.1.2.1 return (contains(_KIND(stm), _METHOD) &&
133 kkz 1.1.2.1 !clones.contains(stm));
134 kkz 1.1.2.1 }
135 kkz 1.1.2.1 public Stm apply(TreeFactory tf, Stm stm,
136 kkz 1.1.2.1 DerivationGenerator dg) {
137 cananian 1.3.2.1 assert reachable.contains(stm);
138 kkz 1.1.2.1 final Label Ltrue = new Label();
139 kkz 1.1.2.1 final Label Lfalse = new Label();
140 kkz 1.1.2.1 final METHOD orig = (METHOD)stm;
141 kkz 1.1.2.1 final Stm clone = new METHOD(tf, stm,
142 kkz 1.1.2.1 orig.getMethod(),
143 kkz 1.1.2.1 orig.getReturnType(),
144 kkz 1.1.2.1 orig.getParams());
145 kkz 1.1.2.1 clones.add(clone);
146 kkz 1.1.2.1 final NAME flag = new NAME(tf, stm, LGCflag);
147 kkz 1.1.2.1 final NAME func = new NAME(tf, stm, LGCfunc);
148 kkz 1.1.2.2 final CJUMP cjump = new CJUMP
149 kkz 1.1.2.2 (tf, stm,
150 kkz 1.1.2.2 new MEM
151 kkz 1.1.2.2 (tf, stm, Type.INT, flag), Ltrue, Lfalse);
152 kkz 1.1.2.2 cjumps.add(cjump);
153 kkz 1.1.2.1 return new SEQ
154 kkz 1.1.2.1 (tf, stm, clone,
155 kkz 1.1.2.1 new SEQ
156 kkz 1.1.2.2 (tf, stm, cjump,
157 kkz 1.1.2.1 new SEQ
158 kkz 1.1.2.1 (tf, stm,
159 kkz 1.1.2.1 new LABEL
160 kkz 1.1.2.1 (tf, stm, Ltrue, false),
161 kkz 1.1.2.1 new SEQ
162 kkz 1.1.2.1 (tf, stm,
163 kkz 1.1.2.1 new NATIVECALL
164 kkz 1.1.2.1 (tf, stm, null, func, null),
165 kkz 1.1.2.1 new LABEL
166 kkz 1.1.2.1 (tf, stm, Lfalse, false)))));
167 kkz 1.1.2.1 }
168 kkz 1.1.2.2 },
169 kkz 1.1.2.2 new Rule("GCpollatCjump") {
170 cananian 1.5 private final Set<Stm> clones = new HashSet<Stm>();
171 kkz 1.1.2.2 public boolean match(Stm stm) {
172 kkz 1.1.2.2 // not a cjump, already processed, or our cjump
173 kkz 1.1.2.2 if (!contains(_KIND(stm), _CJUMP) ||
174 kkz 1.1.2.2 clones.contains(stm) ||
175 kkz 1.1.2.2 cjumps.contains(stm))
176 kkz 1.1.2.2 return false;
177 kkz 1.1.2.2 CJUMP cjump = (CJUMP) stm;
178 kkz 1.1.2.2 int cid = ((Integer)m.get(cjump)).intValue();
179 kkz 1.1.2.2 // either target may be a back branch
180 kkz 1.1.2.2 return (cid > ((Integer)m.get(cjump.iftrue)).intValue() ||
181 kkz 1.1.2.2 cid > ((Integer)m.get(cjump.iffalse)).intValue());
182 kkz 1.1.2.2 }
183 kkz 1.1.2.2 public Stm apply(TreeFactory tf, Stm stm,
184 kkz 1.1.2.2 DerivationGenerator dg) {
185 cananian 1.3.2.1 assert reachable.contains(stm);
186 kkz 1.1.2.2 final Label Ltrue = new Label();
187 kkz 1.1.2.2 final Label Lfalse = new Label();
188 kkz 1.1.2.2 final CJUMP orig = (CJUMP)stm;
189 kkz 1.1.2.2 final Stm clone = new CJUMP(tf, stm,
190 kkz 1.1.2.2 orig.getTest(),
191 kkz 1.1.2.2 orig.iftrue,
192 kkz 1.1.2.2 orig.iffalse);
193 kkz 1.1.2.2 clones.add(clone);
194 kkz 1.1.2.2 final NAME flag = new NAME(tf, stm, LGCflag);
195 kkz 1.1.2.2 final NAME func = new NAME(tf, stm, LGCfunc);
196 kkz 1.1.2.2 final CJUMP cjump = new CJUMP
197 kkz 1.1.2.2 (tf, stm,
198 kkz 1.1.2.2 new MEM
199 kkz 1.1.2.2 (tf, stm, Type.INT, flag), Ltrue, Lfalse);
200 kkz 1.1.2.2 cjumps.add(cjump);
201 kkz 1.1.2.2 return new SEQ
202 kkz 1.1.2.2 (tf, stm,
203 kkz 1.1.2.2 new SEQ
204 kkz 1.1.2.2 (tf, stm, cjump,
205 kkz 1.1.2.2 new SEQ
206 kkz 1.1.2.2 (tf, stm,
207 kkz 1.1.2.2 new LABEL
208 kkz 1.1.2.2 (tf, stm, Ltrue, false),
209 kkz 1.1.2.2 new SEQ
210 kkz 1.1.2.2 (tf, stm,
211 kkz 1.1.2.2 new NATIVECALL
212 kkz 1.1.2.2 (tf, stm, null, func, null),
213 kkz 1.1.2.2 new LABEL
214 kkz 1.1.2.2 (tf, stm, Lfalse, false)))),
215 kkz 1.1.2.2 clone);
216 kkz 1.1.2.2 }
217 kkz 1.1.2.2 },
218 kkz 1.1.2.2 new Rule("GCpollatJump") {
219 cananian 1.5 private final Set<Stm> clones = new HashSet<Stm>();
220 kkz 1.1.2.2 public boolean match(Stm stm) {
221 kkz 1.1.2.2 // not a jump or already processed or not reachable
222 kkz 1.1.2.2 if (!contains(_KIND(stm), _JUMP) ||
223 kkz 1.1.2.2 clones.contains(stm) ||
224 kkz 1.1.2.2 !reachable.contains(stm))
225 kkz 1.1.2.2 return false;
226 kkz 1.1.2.2 Exp target = ((JUMP) stm).getExp();
227 kkz 1.1.2.2 // any calculated branch may be a back edge
228 kkz 1.1.2.2 if (!contains(_KIND(target), _NAME))
229 kkz 1.1.2.2 return true;
230 kkz 1.1.2.2 // a non-computed branch
231 kkz 1.1.2.2 Label Ltarget = ((NAME)target).label;
232 kkz 1.1.2.2 return (((Integer)m.get(stm)).intValue() >
233 kkz 1.1.2.2 ((Integer)m.get(Ltarget)).intValue());
234 kkz 1.1.2.2 }
235 kkz 1.1.2.2 public Stm apply(TreeFactory tf, Stm stm,
236 kkz 1.1.2.2 DerivationGenerator dg) {
237 kkz 1.1.2.2 final Label Ltrue = new Label();
238 kkz 1.1.2.2 final Label Lfalse = new Label();
239 kkz 1.1.2.2 final JUMP orig = (JUMP)stm;
240 kkz 1.1.2.2 final Stm clone = new JUMP(tf, stm,
241 kkz 1.1.2.2 orig.getExp(),
242 kkz 1.1.2.2 orig.targets);
243 kkz 1.1.2.2 clones.add(clone);
244 kkz 1.1.2.2 final NAME flag = new NAME(tf, stm, LGCflag);
245 kkz 1.1.2.2 final NAME func = new NAME(tf, stm, LGCfunc);
246 kkz 1.1.2.2 final CJUMP cjump = new CJUMP
247 kkz 1.1.2.2 (tf, stm,
248 kkz 1.1.2.2 new MEM
249 kkz 1.1.2.2 (tf, stm, Type.INT, flag), Ltrue, Lfalse);
250 kkz 1.1.2.2 cjumps.add(cjump);
251 kkz 1.1.2.2 return new SEQ
252 kkz 1.1.2.1 (tf, stm,
253 kkz 1.1.2.2 new SEQ
254 kkz 1.1.2.2 (tf, stm, cjump,
255 kkz 1.1.2.2 new SEQ
256 kkz 1.1.2.2 (tf, stm,
257 kkz 1.1.2.2 new LABEL
258 kkz 1.1.2.2 (tf, stm, Ltrue, false),
259 kkz 1.1.2.2 new SEQ
260 kkz 1.1.2.2 (tf, stm,
261 kkz 1.1.2.2 new NATIVECALL
262 kkz 1.1.2.2 (tf, stm, null, func, null),
263 kkz 1.1.2.2 new LABEL
264 kkz 1.1.2.2 (tf, stm, Lfalse, false)))),
265 kkz 1.1.2.2 clone);
266 kkz 1.1.2.2 }
267 kkz 1.1.2.1 }
268 kkz 1.1.2.1 });
269 kkz 1.1.2.1 }
270 cananian 1.2 }