1 cananian 1.1.2.1 // TypeSwitchRemover.java, created Tue Oct 10 13:32:03 2000 by cananian
2 cananian 1.1.2.1 // Copyright (C) 2000 C. Scott Ananian <cananian@alumni.princeton.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.1 import harpoon.Analysis.Maps.Derivation;
7 cananian 1.1.2.1 import harpoon.ClassFile.HClass;
8 cananian 1.1.2.1 import harpoon.ClassFile.HCode;
9 cananian 1.1.2.1 import harpoon.ClassFile.HCodeAndMaps;
10 cananian 1.1.2.1 import harpoon.ClassFile.HCodeElement;
11 cananian 1.1.2.1 import harpoon.ClassFile.HCodeFactory;
12 cananian 1.1.2.2 import harpoon.IR.Quads.CJMP;
13 cananian 1.1.2.2 import harpoon.IR.Quads.Code;
14 cananian 1.1.2.2 import harpoon.IR.Quads.Edge;
15 cananian 1.1.2.2 import harpoon.IR.Quads.INSTANCEOF;
16 cananian 1.1.2.2 import harpoon.IR.Quads.Quad;
17 cananian 1.1.2.2 import harpoon.IR.Quads.QuadFactory;
18 cananian 1.1.2.2 import harpoon.IR.Quads.SIGMA;
19 cananian 1.1.2.2 import harpoon.IR.Quads.TYPESWITCH;
20 cananian 1.1.2.1 import harpoon.IR.LowQuad.DerivationMap;
21 cananian 1.1.2.1 import harpoon.Temp.Temp;
22 cananian 1.1.2.1 import harpoon.Temp.TempFactory;
23 cananian 1.6 import net.cscott.jutil.CombineIterator;
24 cananian 1.1.2.1 import harpoon.Util.HClassUtil;
25 cananian 1.1.2.1 import harpoon.Util.Util;
26 cananian 1.1.2.1
27 cananian 1.1.2.1 import java.util.Iterator;
28 cananian 1.1.2.1 import java.util.LinkedList;
29 cananian 1.1.2.1 import java.util.List;
30 cananian 1.1.2.1 /**
31 cananian 1.1.2.1 * <code>TypeSwitchRemover</code> converts <code>TYPESWITCH</code> quads
32 cananian 1.1.2.1 * into chains of <code>INSTANCEOF</code> and <code>CJMP</code> quads.
33 cananian 1.1.2.1 *
34 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
35 cananian 1.6 * @version $Id: TypeSwitchRemover.java,v 1.6 2004/02/08 01:53:14 cananian Exp $
36 cananian 1.1.2.1 */
37 cananian 1.1.2.1 public final class TypeSwitchRemover
38 cananian 1.5 extends harpoon.Analysis.Transformation.MethodMutator<Quad> {
39 cananian 1.1.2.1
40 cananian 1.1.2.1 /** Creates a <code>TypeSwitchRemover</code>. */
41 cananian 1.1.2.1 public TypeSwitchRemover(HCodeFactory parent) { super(parent); }
42 cananian 1.1.2.1
43 cananian 1.5 protected HCode<Quad> mutateHCode(HCodeAndMaps<Quad> input) {
44 cananian 1.1.2.1 Code hc = (Code) input.hcode();
45 cananian 1.1.2.1 // get mutable derivation map.
46 cananian 1.1.2.1 // (no changes necessary to allocation information map)
47 cananian 1.5 DerivationMap<Quad> dm = (DerivationMap<Quad>) hc.getDerivation();
48 cananian 1.1.2.1 // dm (if non-null) will be updated as TYPESWITCHes are replaced.
49 cananian 1.1.2.1
50 cananian 1.1.2.1 // we put all elements in array to avoid screwing up the
51 cananian 1.1.2.1 // iterator as we mutate the quad graph in-place.
52 cananian 1.5 Quad[] allquads = hc.getElements();
53 cananian 1.1.2.1 for (int i=0; i<allquads.length; i++)
54 cananian 1.1.2.1 if (allquads[i] instanceof TYPESWITCH)
55 cananian 1.1.2.1 replace((TYPESWITCH) allquads[i], dm);
56 cananian 1.1.2.1 // now we have to prune off any newly-unreachable TYPESWITCH cases.
57 cananian 1.1.2.1 Unreachable.prune(hc);
58 cananian 1.1.2.1 // yay, done!
59 cananian 1.1.2.1 return hc;
60 cananian 1.1.2.1 }
61 cananian 1.1.2.1
62 cananian 1.5 private static void replace(TYPESWITCH ts, DerivationMap<Quad> dm) {
63 cananian 1.1.2.1 /* construct instanceof chain */
64 cananian 1.1.2.1 Edge e = ts.prevEdge(0);
65 cananian 1.1.2.1 TypeTree tt =
66 cananian 1.5 makeTest(constructCT(ts), ts, e.from(), e.which_succ(),
67 cananian 1.1.2.1 ts.src(), dm);
68 cananian 1.1.2.1 // fixup derivations if present.
69 cananian 1.1.2.1 if (dm!=null) tt.fixupSigmaDerivations(ts, dm);
70 cananian 1.1.2.1 }
71 cananian 1.1.2.1 /** Construct INSTANCEOF chain from a proper & pruned ClassTree */
72 cananian 1.1.2.1 private static TypeTree makeTest(ClassTree ct, TYPESWITCH ts,
73 cananian 1.1.2.1 Quad head, int which_succ, Temp[] src,
74 cananian 1.5 DerivationMap<Quad> dm) {
75 cananian 1.1.2.1 QuadFactory qf = ts.getFactory();
76 cananian 1.1.2.1 TempFactory tf = qf.tempFactory();
77 cananian 1.1.2.1 TypeNode ftn = new TypeNode(null), ptn = ftn; // keep track of TypeTree
78 cananian 1.5 for (Iterator<ClassTree> it=ct.children(); it.hasNext(); ) {
79 cananian 1.1.2.1 // for each child c of ct...
80 cananian 1.5 ClassTree c = it.next();
81 cananian 1.1.2.1 // tweak sigma functions.
82 cananian 1.1.2.1 Temp[][] dst = mkdst(src);
83 cananian 1.1.2.1 if (!c.children().hasNext())
84 cananian 1.1.2.1 tweak(dst, 1, ts, c.edgenum);// copy into slice 1
85 cananian 1.1.2.1 if (!it.hasNext())
86 cananian 1.1.2.1 tweak(dst, 0, ts, ct.edgenum);// copy into slice 0
87 cananian 1.1.2.1 // make INSTANCEOF(c.key) then makeTest(c) else...
88 cananian 1.1.2.1 Temp Textra = new Temp(tf);
89 cananian 1.1.2.1 Quad q0 = new INSTANCEOF(qf, ts, Textra, ts.index(), c.key);
90 cananian 1.1.2.1 CJMP q1 = new CJMP(qf, ts, Textra, dst, src);
91 cananian 1.1.2.1 Quad.addEdge(head, which_succ, q0, 0);
92 cananian 1.1.2.1 Quad.addEdge(q0, 0, q1, 0);
93 cananian 1.1.2.1 if (dm!=null) // update derivation w/ info about Textra
94 cananian 1.1.2.1 dm.putType(q0, Textra, HClass.Int/*internal form of boolean*/);
95 cananian 1.1.2.1 ptn = (TypeNode) (ptn.child[0] = new TypeNode(q1));
96 cananian 1.1.2.1 // then...
97 cananian 1.1.2.1 ptn.child[1] = makeTest(c, ts, q1, 1, slice(q1, 1), dm);
98 cananian 1.1.2.1 // else...
99 cananian 1.1.2.1 head=q1; which_succ=0; src=slice(q1, 0);
100 cananian 1.1.2.1 }
101 cananian 1.1.2.1 // link remaining else... to TYPESWITCH edge ct.edgenum
102 cananian 1.1.2.1 Edge e = ts.nextEdge(ct.edgenum);
103 cananian 1.5 Quad.addEdge(head, which_succ, e.to(), e.which_pred());
104 cananian 1.1.2.1 ptn.child[0] = new TypeLeaf(ct.edgenum);
105 cananian 1.1.2.1 // check that all sigma functions have been handled
106 cananian 1.1.2.1 if (ct.key==null && !ct.children().hasNext())
107 cananian 1.3.2.1 assert ts.numSigmas()==0;// um, 1-arity TS should not have
108 cananian 1.1.2.1 // sigma functions
109 cananian 1.1.2.1 // done.
110 cananian 1.1.2.1 return ftn.child[0]; // return root of TypeTree.
111 cananian 1.1.2.1 }
112 cananian 1.1.2.1 /** Copy a slice of the TYPESWITCH's sigma function to the specified
113 cananian 1.1.2.1 * slice of the dst array. */
114 cananian 1.1.2.1 private static void tweak(Temp[][] dst, int dslice,
115 cananian 1.1.2.1 TYPESWITCH ts, int edgenum) {
116 cananian 1.1.2.1 for (int i=0; i<dst.length; i++)
117 cananian 1.1.2.1 dst[i][dslice] = ts.dst(i, edgenum);
118 cananian 1.1.2.1 }
119 cananian 1.1.2.1 /** make a slice of the given sigma function dsts */
120 cananian 1.1.2.1 private static Temp[] slice(SIGMA s, int nTuple) {
121 cananian 1.1.2.1 Temp[] r = new Temp[s.numSigmas()];
122 cananian 1.1.2.1 for (int i=0; i<s.numSigmas(); i++)
123 cananian 1.1.2.1 r[i] = s.dst(i, nTuple);
124 cananian 1.1.2.1 return r;
125 cananian 1.1.2.1 }
126 cananian 1.1.2.1 /** clone the src array temps twice to make an appropriate dst array */
127 cananian 1.1.2.1 private static Temp[][] mkdst(Temp[] src) {
128 cananian 1.1.2.1 Temp[][] r = new Temp[src.length][2];
129 cananian 1.1.2.1 for (int i=0; i<src.length; i++)
130 cananian 1.1.2.1 for (int j=0; j<2; j++)
131 cananian 1.1.2.1 r[i][j] = new Temp(src[i]);
132 cananian 1.1.2.1 return r;
133 cananian 1.1.2.1 }
134 cananian 1.1.2.1
135 cananian 1.1.2.1 /** Make pruned ClassTree from cases of the TYPESWITCH */
136 cananian 1.1.2.1 private static ClassTree constructCT(TYPESWITCH ts) {
137 cananian 1.1.2.1 ClassTree root = new ClassTree(null, ts.keysLength());
138 cananian 1.1.2.1 for (int i=0; i<ts.keysLength(); i++)
139 cananian 1.1.2.1 addNode(root, new ClassTree(ts.keys(i), i));
140 cananian 1.1.2.3 // if the TYPESWITCH has no default case, fixup the ClassTree.
141 cananian 1.1.2.3 if (!ts.hasDefault()) {
142 cananian 1.5 Iterator<ClassTree> it = root.children();
143 cananian 1.1.2.3 // must have at least one key if it has no default.
144 cananian 1.1.2.3 // make key with highest edgenum the new default.
145 cananian 1.5 ClassTree newdefault = it.next();
146 cananian 1.1.2.3 while (it.hasNext()) {
147 cananian 1.5 ClassTree ct = it.next();
148 cananian 1.1.2.3 if (ct.edgenum > newdefault.edgenum)
149 cananian 1.1.2.3 newdefault = ct;
150 cananian 1.1.2.3 }
151 cananian 1.1.2.3 // now make new root node and reparent children of newdefault
152 cananian 1.1.2.3 // and other children of root.
153 cananian 1.1.2.3 ClassTree newroot = new ClassTree(null, newdefault.edgenum);
154 cananian 1.5 it = new CombineIterator<ClassTree>
155 cananian 1.5 (root.children(), newdefault.children());
156 cananian 1.1.2.3 while (it.hasNext()) {
157 cananian 1.5 ClassTree ct = it.next();
158 cananian 1.1.2.3 it.remove();
159 cananian 1.1.2.3 if (ct!=newdefault) newroot.addChild(ct);
160 cananian 1.1.2.3 }
161 cananian 1.1.2.3 root = newroot;
162 cananian 1.1.2.3 }
163 cananian 1.1.2.3 // okay, done.
164 cananian 1.1.2.1 return root;
165 cananian 1.1.2.1 }
166 cananian 1.1.2.1 /** Recursively descend ClassTree to find where to place this node */
167 cananian 1.1.2.1 private static void addNode(ClassTree root, ClassTree node) {
168 cananian 1.3.2.1 assert root.key==null || node.key.isInstanceOf(root.key);
169 cananian 1.3.2.1 assert !node.children().hasNext();
170 cananian 1.1.2.1 if (node.edgenum > root.edgenum) return;
171 cananian 1.1.2.1 // traverse child list. either node is a subclass of a child,
172 cananian 1.1.2.1 // or one-or-more children are subclasses of node, or neither.
173 cananian 1.1.2.1 boolean linkme=true;
174 cananian 1.5 for (Iterator<ClassTree> it=root.children(); it.hasNext(); ) {
175 cananian 1.5 ClassTree ctp = it.next();
176 cananian 1.1.2.1 if (node.key.isInstanceOf(ctp.key)) {
177 cananian 1.1.2.1 addNode(ctp, node);
178 cananian 1.1.2.1 linkme=false;
179 cananian 1.1.2.1 } else if (ctp.key.isInstanceOf(node.key)) {
180 cananian 1.1.2.1 /* unlink this node from parent */
181 cananian 1.1.2.1 it.remove();
182 cananian 1.1.2.1 /* now, if propitious, link to this. */
183 cananian 1.1.2.1 if (ctp.edgenum < node.edgenum)
184 cananian 1.1.2.1 node.addChild(ctp);
185 cananian 1.1.2.1 continue;
186 cananian 1.1.2.1 }
187 cananian 1.1.2.1 }
188 cananian 1.1.2.1 if (linkme)
189 cananian 1.1.2.1 root.addChild(node);
190 cananian 1.1.2.1 }
191 cananian 1.1.2.1
192 cananian 1.1.2.3 /** The class tree structure represents the class hierarchy relation
193 cananian 1.1.2.3 * over the subset of the classes mentioned in the TYPESWITCH.
194 cananian 1.1.2.3 * Each node also contains an edgenum which corresponds to the
195 cananian 1.1.2.3 * key number in the TYPESWITCH which mentions this class; nodes
196 cananian 1.1.2.3 * are pruned on insertion such that parent.edgenum > child.edgenum,
197 cananian 1.1.2.3 * which ensures that all nodes correspond to reachable cases of
198 cananian 1.1.2.3 * the TYPESWITCH. The root corresponds to the default case. */
199 cananian 1.1.2.1 private static class ClassTree {
200 cananian 1.1.2.1 final HClass key;
201 cananian 1.1.2.1 final int edgenum;
202 cananian 1.5 private List<ClassTree> children;
203 cananian 1.1.2.1 ClassTree(HClass key, int edgenum) {
204 cananian 1.1.2.1 this.key = key; this.edgenum = edgenum;
205 cananian 1.1.2.1 this.children = new LinkedList();
206 cananian 1.1.2.1 }
207 cananian 1.5 Iterator<ClassTree> children() { return children.iterator(); }
208 cananian 1.1.2.1 void addChild(ClassTree nchild) {
209 cananian 1.3.2.1 assert this.edgenum > nchild.edgenum;
210 cananian 1.1.2.1 children.add(nchild);
211 cananian 1.1.2.1 }
212 cananian 1.1.2.1 // pretty-printing.
213 cananian 1.1.2.1 public String toString() { return "CT<"+key+","+edgenum+">"; }
214 cananian 1.1.2.1 public void dump(java.io.PrintWriter pw) { dump(pw, 0); pw.flush(); }
215 cananian 1.1.2.1 private void dump(java.io.PrintWriter pw, int indent) {
216 cananian 1.1.2.1 for (int i=0; i<indent; i++) pw.print(" ");
217 cananian 1.1.2.1 pw.println(toString());
218 cananian 1.5 for (Iterator<ClassTree> it=children(); it.hasNext(); )
219 cananian 1.5 it.next().dump(pw, indent+1);
220 cananian 1.1.2.1 }
221 cananian 1.1.2.1 public void dump(java.io.Writer w) {
222 cananian 1.1.2.1 dump(new java.io.PrintWriter(w));
223 cananian 1.1.2.1 }
224 cananian 1.1.2.1 public void dump(java.io.OutputStream os) {
225 cananian 1.1.2.1 dump(new java.io.PrintWriter(os));
226 cananian 1.1.2.1 }
227 cananian 1.1.2.1 }
228 cananian 1.1.2.1
229 cananian 1.1.2.1 // UGH. Lots of cruft for proper derivations. ------------
230 cananian 1.1.2.1
231 cananian 1.1.2.1 /** The typetree keeps a record of the created CJMP structure
232 cananian 1.1.2.1 * so that we can go back (and with fixupSigmaDerivations()) add
233 cananian 1.1.2.1 * the proper derivation information in a post-pass. */
234 cananian 1.1.2.1 private static abstract class TypeTree {
235 cananian 1.1.2.1 /** add proper derivation information to the CJMPs described by this.*/
236 cananian 1.1.2.1 abstract TypeAndDerivation[] fixupSigmaDerivations(TYPESWITCH ts,
237 cananian 1.5 DerivationMap<Quad> dm);
238 cananian 1.1.2.1 }
239 cananian 1.1.2.1 /** A TypeNode represents a CJMP, with sigmas that need derivations. */
240 cananian 1.1.2.1 private static class TypeNode extends TypeTree {
241 cananian 1.1.2.1 final CJMP cjmp;
242 cananian 1.1.2.1 final TypeTree[] child = new TypeTree[2];
243 cananian 1.1.2.1 TypeNode(CJMP cjmp) { this.cjmp = cjmp; }
244 cananian 1.1.2.1 TypeAndDerivation[] fixupSigmaDerivations(TYPESWITCH ts,
245 cananian 1.5 DerivationMap<Quad> dm) {
246 cananian 1.1.2.1 TypeAndDerivation[] result=new TypeAndDerivation[ts.numSigmas()];
247 cananian 1.1.2.1 for (int i=0; i<2; i++) {
248 cananian 1.1.2.1 TypeAndDerivation[] tad=child[i].fixupSigmaDerivations(ts,dm);
249 cananian 1.1.2.1 for (int j=0; j<tad.length; j++) {
250 cananian 1.1.2.1 tad[j].apply(dm, cjmp, cjmp.dst(j, i));
251 cananian 1.1.2.1 result[j] = (result[j]==null) ? tad[j] :
252 cananian 1.1.2.1 TypeAndDerivation.merge(result[j], tad[j]);
253 cananian 1.1.2.1 }
254 cananian 1.1.2.1 }
255 cananian 1.1.2.1 return result;
256 cananian 1.1.2.1 }
257 cananian 1.1.2.1 }
258 cananian 1.1.2.1 /** A TypeLeaf represents an edge which corresponds to an edge of
259 cananian 1.1.2.1 * the original TYPESWITCH -- i.e. the sigma derivations for this
260 cananian 1.1.2.1 * edge should be identical to those on the original TYPESWITCH edge. */
261 cananian 1.1.2.1 private static class TypeLeaf extends TypeTree {
262 cananian 1.1.2.1 final int edgenum;
263 cananian 1.1.2.1 TypeLeaf(int edgenum) { this.edgenum = edgenum; }
264 cananian 1.1.2.1 TypeAndDerivation[] fixupSigmaDerivations(TYPESWITCH ts,
265 cananian 1.5 DerivationMap<Quad> dm) {
266 cananian 1.1.2.1 // fetch types from appropriate slice of TYPESWITCH
267 cananian 1.1.2.1 TypeAndDerivation[] r = new TypeAndDerivation[ts.numSigmas()];
268 cananian 1.1.2.1 for (int i=0; i<r.length; i++) {
269 cananian 1.1.2.1 r[i]=new TypeAndDerivation(dm, ts, ts.dst(i, edgenum));
270 cananian 1.1.2.1 dm.remove(ts, ts.dst(i, edgenum)); // clean up.
271 cananian 1.1.2.1 }
272 cananian 1.1.2.1 return r;
273 cananian 1.1.2.1 }
274 cananian 1.1.2.1 }
275 cananian 1.1.2.1 /** unified type/derivation information. */
276 cananian 1.1.2.1 private static class TypeAndDerivation {
277 cananian 1.1.2.1 /** non-null for base pointers */
278 cananian 1.1.2.1 public final HClass type;
279 cananian 1.1.2.1 /** non-null for derived pointers */
280 cananian 1.1.2.1 public final Derivation.DList derivation;
281 cananian 1.1.2.1 // public constructors
282 cananian 1.1.2.1 TypeAndDerivation(HClass type) { this(type, null); }
283 cananian 1.1.2.1 TypeAndDerivation(Derivation.DList deriv) { this(null, deriv); }
284 cananian 1.1.2.1 // helpful.
285 cananian 1.5 <HCE extends HCodeElement> TypeAndDerivation(Derivation<HCE> d,
286 cananian 1.5 HCE hce, Temp t) {
287 cananian 1.1.2.1 this(d.typeMap(hce, t), d.derivation(hce, t));
288 cananian 1.1.2.1 }
289 cananian 1.1.2.1 /** private constructor */
290 cananian 1.1.2.1 private TypeAndDerivation(HClass type, Derivation.DList derivation) {
291 cananian 1.3.2.1 assert type!=null ^ derivation!=null;
292 cananian 1.1.2.1 this.type = type;
293 cananian 1.1.2.1 this.derivation = derivation;
294 cananian 1.1.2.1 }
295 cananian 1.1.2.1 /** store this TypeAndDerivation information in the given
296 cananian 1.1.2.1 * DerivationMap for the given HCodeElement/Temp pair. */
297 cananian 1.5 <HCE extends HCodeElement> void apply(DerivationMap<HCE> dm,
298 cananian 1.5 HCE hce, Temp t) {
299 cananian 1.1.2.1 if (type!=null) dm.putType(hce, t, type);
300 cananian 1.1.2.1 else dm.putDerivation(hce, t, derivation);
301 cananian 1.1.2.1 }
302 cananian 1.1.2.1 /** Merge the given TypeAndDerivations. */
303 cananian 1.1.2.1 static TypeAndDerivation merge(TypeAndDerivation a,
304 cananian 1.1.2.1 TypeAndDerivation b) {
305 cananian 1.1.2.1 if (a.type!=null && b.type!=null)
306 cananian 1.1.2.1 return new TypeAndDerivation
307 cananian 1.1.2.1 (HClassUtil.commonParent(a.type, b.type));
308 cananian 1.1.2.1 // both ought to be derivations.
309 cananian 1.3.2.1 assert a.derivation!=null && b.derivation!=null : "can't merge type with derivation";
310 cananian 1.3.2.1 assert a.derivation.equals(b.derivation) : "can't merge derivations";
311 cananian 1.1.2.1 return a;
312 cananian 1.1.2.1 }
313 cananian 1.1.2.1 }
314 cananian 1.2 }