1 cananian 1.1.2.1 // MethodInliningCodeFactory.java, created Mon Feb 1 09:22:29 1999 by pnkfelix
2 cananian 1.1.2.6 // Copyright (C) 1999 Felix S. Klock II <pnkfelix@mit.edu>
3 cananian 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 cananian 1.1.2.1 package harpoon.Analysis.Quads;
5 cananian 1.1.2.1
6 cananian 1.1.2.5 import harpoon.Analysis.Maps.UseDefMap;
7 cananian 1.1.2.5 import harpoon.Analysis.UseDef;
8 cananian 1.1.2.7 import harpoon.ClassFile.HCode;
9 cananian 1.1.2.7 import harpoon.ClassFile.HCodeAndMaps;
10 cananian 1.1.2.1 import harpoon.ClassFile.HCodeFactory;
11 cananian 1.1.2.1 import harpoon.ClassFile.HMethod;
12 cananian 1.1.2.1 import harpoon.IR.Quads.CALL;
13 cananian 1.1.2.7 import harpoon.IR.Quads.Edge;
14 cananian 1.1.2.1 import harpoon.IR.Quads.HEADER;
15 cananian 1.1.2.1 import harpoon.IR.Quads.METHOD;
16 cananian 1.1.2.1 import harpoon.IR.Quads.MOVE;
17 cananian 1.1.2.7 import harpoon.IR.Quads.NOP;
18 cananian 1.1.2.7 import harpoon.IR.Quads.PHI;
19 cananian 1.1.2.7 import harpoon.IR.Quads.Quad;
20 cananian 1.1.2.8 import harpoon.IR.Quads.QuadRSSx;
21 cananian 1.1.2.8 import harpoon.IR.Quads.QuadSSA;
22 cananian 1.1.2.1 import harpoon.IR.Quads.QuadVisitor;
23 cananian 1.1.2.7 import harpoon.IR.Quads.RETURN;
24 cananian 1.1.2.7 import harpoon.IR.Quads.THROW;
25 cananian 1.1.2.1 import harpoon.Util.Util;
26 cananian 1.1.2.1 import harpoon.Temp.TempMap;
27 cananian 1.1.2.1 import harpoon.Temp.Temp;
28 cananian 1.1.2.1 import harpoon.Temp.CloningTempMap;
29 cananian 1.1.2.1
30 cananian 1.1.2.1
31 cananian 1.1.2.7 import java.util.ArrayList;
32 cananian 1.1.2.7 import java.util.HashMap;
33 cananian 1.1.2.1 import java.util.HashSet;
34 cananian 1.1.2.1 import java.util.Iterator;
35 cananian 1.1.2.7 import java.util.List;
36 cananian 1.1.2.7 import java.util.Map;
37 cananian 1.1.2.7 import java.util.Set;
38 cananian 1.1.2.1
39 cananian 1.1.2.1 import java.io.PrintWriter;
40 cananian 1.1.2.1 import harpoon.ClassFile.HClass;
41 cananian 1.1.2.1 import harpoon.ClassFile.HCodeElement;
42 cananian 1.1.2.1 /**
43 cananian 1.1.2.1 * <code>MethodInliningCodeFactory</code> makes an <code>HCode</code>
44 cananian 1.1.2.1 * from an <code>HMethod</code>, and inlines methods at call sites
45 cananian 1.1.2.1 * registered with the <code>inline(CALL)</code> function.
46 cananian 1.1.2.1 * <P>
47 cananian 1.1.2.1 * Recursive functions are legal, but this factory does not provide
48 cananian 1.1.2.1 * facilities for specifying number of recursive inlinings.
49 cananian 1.1.2.1 *
50 cananian 1.1.2.6 * @author Felix S. Klock II <pnkfelix@mit.edu>
51 cananian 1.4 * @version $Id: MethodInliningCodeFactory.java,v 1.4 2002/04/10 03:00:59 cananian Exp $ */
52 cananian 1.1.2.1 public class MethodInliningCodeFactory implements HCodeFactory {
53 cananian 1.1.2.1
54 cananian 1.1.2.1 HCodeFactory parent;
55 cananian 1.1.2.7 private final Map h = new HashMap(); // code cache.
56 cananian 1.1.2.1
57 cananian 1.1.2.1 // sites to be inlined
58 cananian 1.1.2.1 HashSet inlinedSites;
59 cananian 1.1.2.1
60 cananian 1.1.2.1 // sites that have already been inlined (used to detect recursive
61 cananian 1.1.2.1 // inlining)
62 cananian 1.1.2.7 private HashSet currentlyInlining = new HashSet();
63 cananian 1.1.2.1
64 cananian 1.1.2.1 /** Creates a <code>MethodInliningCodeFactory</code>, using
65 cananian 1.1.2.1 <code>parentFactory</code>.
66 cananian 1.1.2.1 <BR> <B>requires:</B> <code>parentFactory</code> produces
67 cananian 1.1.2.1 "quad-ssi" code.
68 cananian 1.1.2.1 */
69 cananian 1.1.2.1 public MethodInliningCodeFactory(HCodeFactory parentFactory) {
70 cananian 1.3.2.1 assert parentFactory.getCodeName().equals(QuadSSA.codename);
71 cananian 1.1.2.1 parent = parentFactory;
72 cananian 1.1.2.1 inlinedSites = new HashSet();
73 cananian 1.1.2.1 }
74 cananian 1.1.2.1
75 cananian 1.1.2.1 /** Returns a string naming the type of the <code>HCode</code>
76 cananian 1.1.2.1 that this factory produces. <p>
77 cananian 1.1.2.1 <code>this.getCodeName()</code> should equal
78 cananian 1.1.2.1 <code>this.convert(m).getName()</code> for every
79 cananian 1.1.2.1 <code>HMethod m</code>.
80 cananian 1.1.2.1 */
81 cananian 1.1.2.8 public String getCodeName() { return MyRSSx.codename; }
82 cananian 1.1.2.1
83 cananian 1.1.2.1 /** Removes representation of method <code>m</code> from all caches
84 cananian 1.1.2.1 in this factory and its parents.
85 cananian 1.1.2.1 */
86 cananian 1.1.2.1 public void clear(HMethod m) { parent.clear(m); }
87 cananian 1.1.2.1
88 cananian 1.1.2.1 /** Make an <code>HCode</code> from an <code>HMethod</code>.
89 cananian 1.1.2.1 <p>
90 cananian 1.1.2.1 <code>convert</code> is allowed to return null if the requested
91 cananian 1.1.2.1 conversion is impossible; typically this is because it's attempt
92 cananian 1.1.2.1 to convert a source representation failed -- for
93 cananian 1.1.2.1 example, because <code>m</code> is a native method.
94 cananian 1.1.2.1 <p>
95 cananian 1.1.2.1 MethodInliningCodeFactory also inlines any call sites within
96 cananian 1.1.2.1 <code>m</code> marked by the <code>this.inline(CALL)</code>
97 cananian 1.1.2.1 method.
98 cananian 1.1.2.1 */
99 cananian 1.1.2.1 public HCode convert(HMethod m) {
100 cananian 1.1.2.7 if (h.containsKey(m)) return (HCode) h.get(m); // even if get()==null.
101 cananian 1.1.2.8 harpoon.IR.Quads.Code newCode = (QuadSSA) parent.convert(m);
102 cananian 1.1.2.7 if (newCode == null) { h.put(m, null); return null; }
103 cananian 1.1.2.1
104 cananian 1.1.2.1 // The below was added in response to Scott's request that the
105 cananian 1.1.2.1 // HCode be cloned prior to being fuddled with by the Inliner
106 cananian 1.1.2.8 HCodeAndMaps hcam = MyRSSx.cloneToRSSx(newCode, m);
107 cananian 1.1.2.8 newCode = (MyRSSx) hcam.hcode();
108 cananian 1.1.2.7 Map aem = hcam.ancestorElementMap();
109 cananian 1.1.2.1
110 cananian 1.1.2.1 Quad[] ql = (Quad[]) newCode.getElements();
111 cananian 1.1.2.1
112 cananian 1.1.2.1 // pw.println( "Sites to inline are " + inlinedSites );
113 cananian 1.1.2.1
114 cananian 1.1.2.1 for (int i=0; i<ql.length; i++) {
115 cananian 1.1.2.1
116 cananian 1.1.2.7 boolean inline = inlinedSites.contains( aem.get(ql[i]) ) &&
117 cananian 1.1.2.7 ! currentlyInlining.contains( ((CALL)ql[i]).method() );
118 cananian 1.1.2.1 if (inline) {
119 cananian 1.1.2.1
120 cananian 1.1.2.7 // pw.out.println("Hey, I'm supposed to inline " + ql[i]);
121 cananian 1.1.2.1
122 cananian 1.1.2.1 // ql[i] is a CALL site that has been marked to be
123 cananian 1.1.2.1 // inlined and isn't being inlined currently. Inline it.
124 cananian 1.1.2.1 CALL call = (CALL) ql[i];
125 cananian 1.1.2.7 currentlyInlining.add( call.method() );// no recursive inlining
126 cananian 1.1.2.1 HCode calledCode = this.convert( call.method() );
127 cananian 1.1.2.7 currentlyInlining.remove( call.method() );
128 cananian 1.1.2.1
129 cananian 1.1.2.1
130 cananian 1.1.2.7 Quad header = (HEADER) calledCode.getRootElement();
131 cananian 1.1.2.1 Quad newQ = Quad.clone(call.getFactory(), header);
132 cananian 1.1.2.1
133 cananian 1.1.2.1 class QuadArrayBuilder {
134 cananian 1.1.2.1 Set s;
135 cananian 1.1.2.1 QuadArrayBuilder(HEADER q) {
136 cananian 1.1.2.1 s = new HashSet();
137 cananian 1.1.2.1 recurse(q);
138 cananian 1.1.2.1 }
139 cananian 1.1.2.1
140 cananian 1.1.2.1 private void recurse(Quad q) {
141 cananian 1.1.2.7 if (s.contains(q)) return;
142 cananian 1.1.2.1 s.add(q);
143 cananian 1.1.2.1 Quad[] next = q.next();
144 cananian 1.1.2.1 for (int j=0; j<next.length; j++) {
145 cananian 1.1.2.1 recurse(next[j]);
146 cananian 1.1.2.1 }
147 cananian 1.1.2.1 }
148 cananian 1.1.2.1
149 cananian 1.1.2.1 Quad[] getElements() {
150 cananian 1.1.2.7 return (Quad[]) s.toArray( new Quad[s.size()] );
151 cananian 1.1.2.1 }
152 cananian 1.1.2.1 }
153 cananian 1.1.2.1
154 cananian 1.1.2.1
155 cananian 1.1.2.1 QuadArrayBuilder build = new QuadArrayBuilder((HEADER) newQ);
156 cananian 1.1.2.7 Quad[] newElems = build.getElements();
157 cananian 1.1.2.7 // make method-renaming map.
158 cananian 1.1.2.7 TempMap renameMap = makeMap((METHOD)newQ.next(1), call);
159 cananian 1.1.2.1
160 cananian 1.1.2.7 InliningVisitor qv = new InliningVisitor( call );
161 cananian 1.1.2.1 for(int j=0; j<newElems.length; j++) {
162 cananian 1.1.2.7 if (newElems[j] instanceof HEADER) continue;
163 cananian 1.1.2.7 Quad nq = newElems[j].rename(renameMap, renameMap);
164 cananian 1.1.2.7 Quad.replace(newElems[j], nq);
165 cananian 1.1.2.7 nq.accept(qv);
166 cananian 1.1.2.1 }
167 cananian 1.1.2.7 // now make phis for throw/return merge.
168 cananian 1.1.2.7 PHI retphi = new PHI(newQ.getFactory(), call,
169 cananian 1.1.2.7 new Temp[0], qv.return_sites.size());
170 cananian 1.1.2.7 PHI thrphi = new PHI(newQ.getFactory(), call,
171 cananian 1.1.2.7 new Temp[0], qv.throw_sites.size());
172 cananian 1.1.2.7 Edge ret = call.nextEdge(0), thr = call.nextEdge(1);
173 cananian 1.1.2.7 Quad.addEdge(retphi, 0, (Quad)ret.to(), ret.which_pred());
174 cananian 1.1.2.7 Quad.addEdge(thrphi, 0, (Quad)thr.to(), thr.which_pred());
175 cananian 1.1.2.7 int j=0;
176 cananian 1.1.2.7 for (Iterator it=qv.return_sites.iterator(); it.hasNext(); )
177 cananian 1.1.2.7 Quad.addEdge((Quad)it.next(), 0, retphi, j++);
178 cananian 1.1.2.7 j=0;
179 cananian 1.1.2.7 for (Iterator it=qv.throw_sites.iterator(); it.hasNext(); )
180 cananian 1.1.2.7 Quad.addEdge((Quad)it.next(), 0, thrphi, j++);
181 cananian 1.1.2.1 }
182 cananian 1.1.2.1 }
183 cananian 1.1.2.7 // remove useless/unreachable phis
184 cananian 1.1.2.7 // (methods which don't return/don't throw exceptions, etc)
185 cananian 1.1.2.7 Unreachable.prune(newCode);
186 cananian 1.1.2.7 // done!
187 cananian 1.1.2.7 h.put(m, newCode); // cache this puppy.
188 cananian 1.1.2.1 return newCode;
189 cananian 1.1.2.8 }
190 cananian 1.1.2.8 private static class MyRSSx extends QuadRSSx {
191 cananian 1.1.2.8 private MyRSSx(HMethod m) { super(m, null); }
192 cananian 1.1.2.8 public static HCodeAndMaps cloneToRSSx(harpoon.IR.Quads.Code c,
193 cananian 1.1.2.8 HMethod m) {
194 cananian 1.1.2.8 MyRSSx r = new MyRSSx(m);
195 cananian 1.1.2.8 return r.cloneHelper(c, r);
196 cananian 1.1.2.8 }
197 cananian 1.1.2.1 }
198 cananian 1.1.2.1
199 cananian 1.1.2.1 /** Marks a call site to be inlined when code is generated.
200 cananian 1.1.2.1 <BR> <B>modifies:</B> <code>this</code>
201 cananian 1.1.2.1 <BR> <B>effects:</B> Marks <code>site</code> as a location to
202 cananian 1.1.2.1 inline if <code>this</code> is ever asked
203 cananian 1.1.2.1 to generate code for the
204 cananian 1.1.2.1 <code>HMethod</code> containing
205 cananian 1.1.2.1 <code>site</code>.
206 cananian 1.1.2.1 */
207 cananian 1.1.2.1 public void inline(CALL site) {
208 cananian 1.1.2.1 inlinedSites.add(site);
209 cananian 1.1.2.1 }
210 cananian 1.1.2.1
211 cananian 1.1.2.1 /** Marks a call site to not be inlined when code is generated.
212 cananian 1.1.2.1 <BR> <B>modifies:</B> <code>this</code>
213 cananian 1.1.2.1 <BR> <B>effects:</B> If <code>site</code> is in the set of
214 cananian 1.1.2.1 call sites to be inlined, takes
215 cananian 1.1.2.1 <code>site</code> out of the set. Else
216 cananian 1.1.2.1 does nothing.
217 cananian 1.1.2.1 */
218 cananian 1.1.2.1 public void uninline(CALL site) {
219 cananian 1.1.2.1 inlinedSites.remove(site);
220 cananian 1.1.2.1 }
221 cananian 1.1.2.1
222 cananian 1.1.2.7 private static class MapTempMap extends HashMap implements TempMap {
223 cananian 1.1.2.7 public Temp tempMap(Temp t) {
224 cananian 1.1.2.7 return containsKey(t)?(Temp)get(t):t;
225 cananian 1.1.2.7 }
226 cananian 1.1.2.7 }
227 cananian 1.1.2.7 private TempMap makeMap(METHOD q, CALL site) {
228 cananian 1.1.2.7 Temp[] passedParams = site.params();
229 cananian 1.1.2.7 MapTempMap mtm = new MapTempMap();
230 cananian 1.1.2.7 // METHOD has temp var parameters for this sequence of
231 cananian 1.1.2.7 // quads...make a temp map to substitute in the passed
232 cananian 1.1.2.7 // arguments.
233 cananian 1.1.2.7 Temp[] params = q.params();
234 cananian 1.1.2.7 for (int i=0; i<params.length; i++)
235 cananian 1.1.2.7 mtm.put(params[i], passedParams[i]);
236 cananian 1.1.2.7 return mtm;
237 cananian 1.1.2.7 }
238 cananian 1.1.2.7
239 cananian 1.1.2.1 static class InliningVisitor extends QuadVisitor {
240 cananian 1.1.2.1
241 cananian 1.1.2.1 CALL site;
242 cananian 1.1.2.7 MapTempMap renameMap = new MapTempMap();
243 cananian 1.1.2.7 List return_sites = new ArrayList();
244 cananian 1.1.2.7 List throw_sites = new ArrayList();
245 cananian 1.1.2.1
246 cananian 1.1.2.1
247 cananian 1.1.2.7 InliningVisitor( CALL site ) {
248 cananian 1.1.2.1 this.site = site;
249 cananian 1.1.2.1 }
250 cananian 1.1.2.1
251 cananian 1.1.2.1 public void visit(Quad q) {
252 cananian 1.1.2.1 // not sure what to do in the general case...
253 cananian 1.1.2.1
254 cananian 1.1.2.1 }
255 cananian 1.1.2.1
256 cananian 1.1.2.1 public void visit(METHOD q) {
257 cananian 1.1.2.1 // METHOD succ[0] is the first bit of executable bytecode;
258 cananian 1.1.2.1 // make the code prior to the CALL point to it.
259 cananian 1.1.2.7 Edge frm = site.prevEdge(0), to = q.nextEdge(0);
260 cananian 1.1.2.7 Quad.addEdge((Quad) frm.from(), frm.which_succ(),
261 cananian 1.1.2.7 (Quad) to.to(), to.which_pred());
262 cananian 1.1.2.1 }
263 cananian 1.1.2.1
264 cananian 1.1.2.1 public void visit(THROW q) {
265 cananian 1.1.2.1 // do something similar to RETURN here
266 cananian 1.1.2.1 Temp retEx = site.retex();
267 cananian 1.1.2.1 Quad replace;
268 cananian 1.1.2.1 if (retEx != null) {
269 cananian 1.1.2.1 replace = new MOVE(site.getFactory(), null,
270 cananian 1.1.2.1 retEx, q.throwable());
271 cananian 1.1.2.1 } else {
272 cananian 1.1.2.1 // no place to put the exception...don't know under what
273 cananian 1.1.2.1 // situation this would occur...perhaps put in an
274 cananian 1.1.2.1 // assertion to ensure that it doesn't?
275 cananian 1.1.2.1 replace = new NOP(site.getFactory(), null);
276 cananian 1.3.2.1 assert false;
277 cananian 1.1.2.1 }
278 salcianu 1.1.2.3 // make the successor(replace) be the 1-successor of the
279 salcianu 1.1.2.3 // calling site (the succesor for the "exception thrown" case).
280 cananian 1.1.2.7 Edge frm = q.prevEdge(0);
281 cananian 1.1.2.7 Quad.addEdge((Quad)frm.from(), frm.which_succ(), replace, 0);
282 cananian 1.1.2.7 throw_sites.add(replace);
283 cananian 1.1.2.1 }
284 cananian 1.1.2.1
285 cananian 1.1.2.1 public void visit(RETURN q) {
286 cananian 1.1.2.1 // replace with a MOVE to the target value, and a branch to
287 cananian 1.1.2.1 // the footer.
288 cananian 1.1.2.1 Temp retVal = site.retval();
289 cananian 1.1.2.1 Quad replace;
290 cananian 1.1.2.1 if (retVal != null) {
291 cananian 1.1.2.1 // put in the MOVE to target val and replace := MOVE
292 cananian 1.1.2.1 replace = new MOVE(site.getFactory(), null,
293 cananian 1.1.2.1 retVal, q.retval());
294 cananian 1.1.2.1 } else {
295 cananian 1.1.2.1 // there is no value to return...ummm...for now put in
296 cananian 1.1.2.1 // a NOP and replace := NOP
297 cananian 1.1.2.1 replace = new NOP(site.getFactory(), null);
298 cananian 1.1.2.1 }
299 salcianu 1.1.2.3 // make the successor(replace) be the 0-successor of the
300 salcianu 1.1.2.3 // calling site (the succesor for the normal case).
301 cananian 1.1.2.7 Edge frm = q.prevEdge(0);
302 cananian 1.1.2.7 Quad.addEdge((Quad)frm.from(), frm.which_succ(), replace, 0);
303 cananian 1.1.2.7 return_sites.add(replace);
304 cananian 1.1.2.1 }
305 cananian 1.1.2.1 }
306 cananian 1.1.2.1
307 cananian 1.2 }