1 cananian 1.1.2.10 // ToCanonicalTree.java, created Mon Mar 29 0:08:40 1999 by duncan
2 cananian 1.1.2.9 // Copyright (C) 1998 Duncan Bryce <duncan@lcs.mit.edu>
3 cananian 1.1.2.9 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 duncan 1.1.2.1 package harpoon.IR.Tree;
5 duncan 1.1.2.1
6 cananian 1.1.2.25 import harpoon.Analysis.Maps.Derivation.DList;
7 duncan 1.1.2.4 import harpoon.Backend.Generic.Frame;
8 duncan 1.1.2.1 import harpoon.ClassFile.HClass;
9 duncan 1.1.2.1 import harpoon.ClassFile.HCode;
10 duncan 1.1.2.1 import harpoon.ClassFile.HCodeElement;
11 duncan 1.1.2.4 import harpoon.Temp.CloningTempMap;
12 duncan 1.1.2.1 import harpoon.Temp.Temp;
13 cananian 1.1.2.28 import harpoon.Temp.TempMap;
14 duncan 1.1.2.1 import harpoon.Util.Tuple;
15 duncan 1.1.2.1 import harpoon.Util.Util;
16 duncan 1.1.2.1
17 duncan 1.1.2.8 import java.util.HashMap;
18 duncan 1.1.2.21 import java.util.Iterator;
19 duncan 1.1.2.8 import java.util.Map;
20 duncan 1.1.2.21 import java.util.HashSet;
21 duncan 1.1.2.1
22 duncan 1.1.2.1 /**
23 duncan 1.1.2.1 * The <code>ToCanonicalTree</code> class translates tree code to
24 duncan 1.1.2.2 * canonical tree code (no ESEQ). Based on the translator to canonical
25 duncan 1.1.2.2 * form by Andrew Appel.
26 duncan 1.1.2.1 *
27 duncan 1.1.2.1 * @author Duncan Bryce <duncan@lcs.mit.edu>
28 cananian 1.4 * @version $Id: ToCanonicalTree.java,v 1.4 2002/04/10 03:05:45 cananian Exp $
29 duncan 1.1.2.1 */
30 cananian 1.1.2.24 public class ToCanonicalTree {
31 duncan 1.1.2.1 private Tree m_tree;
32 cananian 1.1.2.24 private DerivationGenerator m_dg = new DerivationGenerator();
33 duncan 1.1.2.1
34 duncan 1.1.2.4 /** Class constructor.
35 duncan 1.1.2.4 *
36 duncan 1.1.2.4 * @param tf The <code>TreeFactory</code> which will be used for all
37 duncan 1.1.2.4 * elements of the new <code>CanonicalTreeCode</code>.
38 duncan 1.1.2.4 * @param code The <code>TreeCode</code> which we wish to translate
39 duncan 1.1.2.4 */
40 cananian 1.3.2.2 public ToCanonicalTree(final TreeFactory tf, Code code) {
41 cananian 1.3.2.1 assert tf instanceof Code.TreeFactory;
42 cananian 1.3.2.1 assert ((Code.TreeFactory)tf).getParent().getName().equals("canonical-tree");
43 duncan 1.1.2.19
44 cananian 1.1.2.24 m_tree = translate(tf, code);
45 duncan 1.1.2.1 }
46 duncan 1.1.2.1
47 cananian 1.1.2.24 /** Returns a <code>TreeDerivation</code> object for the
48 cananian 1.1.2.24 * generated <code>Tree</code> form. */
49 cananian 1.1.2.25 public TreeDerivation getTreeDerivation() { return new TreeDerivation() {
50 cananian 1.1.2.25 public HClass typeMap(Exp exp) { return HClass.Void; }
51 cananian 1.1.2.25 public DList derivation(Exp exp) { return null; }
52 cananian 1.1.2.25 };
53 cananian 1.1.2.25 }
54 duncan 1.1.2.1
55 duncan 1.1.2.1 /** Returns the root of the generated tree code */
56 duncan 1.1.2.1 public Tree getTree() {
57 duncan 1.1.2.1 return m_tree;
58 duncan 1.1.2.1 }
59 duncan 1.1.2.1
60 duncan 1.1.2.1 // translate to canonical form
61 cananian 1.3.2.2 private Tree translate(TreeFactory tf, Code code) {
62 duncan 1.1.2.8 CanonicalizingVisitor cv; // Translates the TreeCode
63 duncan 1.1.2.8 Stm root; // The root of "code"
64 duncan 1.1.2.8 TreeMap tm; // maps old trees to translated trees
65 duncan 1.1.2.8
66 duncan 1.1.2.8 tm = new TreeMap();
67 cananian 1.1.2.24 cv = new CanonicalizingVisitor(tf, tm, code);
68 duncan 1.1.2.8 root = (Stm)code.getRootElement();
69 duncan 1.1.2.4
70 duncan 1.1.2.4 // This visitor recursively visits all relevant nodes on its own
71 cananian 1.1.2.16 root.accept(cv);
72 duncan 1.1.2.4
73 duncan 1.1.2.4 // Return the node which rootClone has been mapped to
74 duncan 1.1.2.8 return tm.get(root);
75 duncan 1.1.2.1 }
76 duncan 1.1.2.1
77 duncan 1.1.2.1 // Visitor class to translate to canonical form
78 duncan 1.1.2.1 class CanonicalizingVisitor extends TreeVisitor {
79 duncan 1.1.2.8 private CloningTempMap ctm;
80 cananian 1.3.2.2 private Code code;
81 duncan 1.1.2.1 private TreeFactory tf;
82 duncan 1.1.2.1 private TreeMap treeMap;
83 cananian 1.1.2.24 private TreeDerivation oldDeriv;
84 duncan 1.1.2.12 private java.util.Set visited = new java.util.HashSet();
85 duncan 1.1.2.1
86 duncan 1.1.2.1 public CanonicalizingVisitor(TreeFactory tf, TreeMap tm,
87 cananian 1.3.2.2 Code code) {
88 duncan 1.1.2.1 this.code = code;
89 duncan 1.1.2.1 this.treeMap = tm;
90 duncan 1.1.2.1 this.tf = tf;
91 cananian 1.1.2.24 this.oldDeriv = code.getTreeDerivation();
92 duncan 1.1.2.8 this.ctm = new CloningTempMap
93 duncan 1.1.2.8 (((Stm)code.getRootElement()).getFactory().tempFactory(),
94 duncan 1.1.2.8 tf.tempFactory());
95 duncan 1.1.2.1 }
96 duncan 1.1.2.1
97 duncan 1.1.2.21
98 duncan 1.1.2.1 public void visit(Tree t) {
99 duncan 1.1.2.1 throw new Error("No defaults here");
100 duncan 1.1.2.1 }
101 duncan 1.1.2.1
102 duncan 1.1.2.1 public void visit(MOVE s) {
103 duncan 1.1.2.12 if (!visited.add(s)) return;
104 duncan 1.1.2.1
105 duncan 1.1.2.19 //s.getSrc().accept(this);
106 duncan 1.1.2.19 if (s.getDst().kind()==TreeKind.ESEQ) {
107 cananian 1.3.2.1 assert false : "Dangerous use of ESEQ";
108 duncan 1.1.2.19 ESEQ eseq = (ESEQ)s.getDst();
109 duncan 1.1.2.19 eseq.getExp().accept(this);
110 duncan 1.1.2.19 eseq.getStm().accept(this);
111 duncan 1.1.2.1 SEQ tmp = new SEQ
112 duncan 1.1.2.19 (tf, treeMap.get(eseq.getStm()),
113 duncan 1.1.2.3 s,
114 duncan 1.1.2.3 new MOVE
115 duncan 1.1.2.3 (tf, s,
116 duncan 1.1.2.19 treeMap.get(eseq.getExp()),
117 duncan 1.1.2.19 treeMap.get(s.getSrc())));
118 cananian 1.1.2.16 tmp.accept(this);
119 duncan 1.1.2.8 treeMap.map(s, treeMap.get(tmp));
120 duncan 1.1.2.1 }
121 duncan 1.1.2.1 else {
122 duncan 1.1.2.8 treeMap.map(s, reorderMove(s));
123 duncan 1.1.2.1 }
124 duncan 1.1.2.19
125 duncan 1.1.2.1 }
126 duncan 1.1.2.1
127 duncan 1.1.2.1 public void visit(SEQ s) {
128 duncan 1.1.2.12 if (!visited.add(s)) return;
129 duncan 1.1.2.19 s.getLeft().accept(this);
130 duncan 1.1.2.19 s.getRight().accept(this);
131 duncan 1.1.2.19 treeMap.map(s, seq(treeMap.get(s.getLeft()), treeMap.get(s.getRight())));
132 duncan 1.1.2.1 }
133 duncan 1.1.2.1
134 cananian 1.1.2.20 public void visit(DATUM s) {
135 duncan 1.1.2.13 if (!visited.add(s)) return;
136 duncan 1.1.2.13 treeMap.map(s, reorderData(s));
137 duncan 1.1.2.13 }
138 duncan 1.1.2.13
139 duncan 1.1.2.12 public void visit(Stm s) {
140 duncan 1.1.2.12 if (!visited.add(s)) return;
141 duncan 1.1.2.1 treeMap.map(s, reorderStm(s));
142 duncan 1.1.2.1 }
143 duncan 1.1.2.1
144 duncan 1.1.2.21 public void visit(Exp e) {
145 duncan 1.1.2.12 if (!visited.add(e)) {
146 duncan 1.1.2.12 return;
147 duncan 1.1.2.12 }
148 duncan 1.1.2.1 treeMap.map(e, reorderExp(e));
149 duncan 1.1.2.1 }
150 duncan 1.1.2.1
151 cananian 1.1.2.26 public void visit(METHOD e) {
152 cananian 1.1.2.26 if (!visited.add(e)) return;
153 cananian 1.1.2.26 TEMP[] pOld = e.getParams();
154 cananian 1.1.2.26 TEMP[] pNew = new TEMP[pOld.length];
155 cananian 1.1.2.26 for(int i=0; i<pNew.length; i++) {
156 cananian 1.1.2.26 pNew[i] = _MAP(pOld[i]);
157 cananian 1.1.2.26 }
158 cananian 1.1.2.30 treeMap.map(e, new METHOD(tf, e, e.getMethod(), e.getReturnType(),
159 cananian 1.1.2.30 pNew));
160 cananian 1.1.2.26 }
161 cananian 1.1.2.26 public void visit(CALL s) {
162 cananian 1.1.2.26 if (!visited.add(s)) return;
163 cananian 1.1.2.26 TEMP tNewV = (s.getRetval()==null)?null:_MAP(s.getRetval());
164 cananian 1.1.2.26 TEMP tNewX = _MAP(s.getRetex());
165 cananian 1.1.2.26 NAME handler = new NAME(tf, s.getHandler(), s.getHandler().label);
166 cananian 1.1.2.26 StmExpList x = reorder(s.kids());
167 cananian 1.1.2.26 CALL c = new CALL(tf, s, tNewV, tNewX,
168 cananian 1.1.2.26 x.exps.head, x.exps.tail, handler,
169 cananian 1.1.2.26 s.isTailCall);
170 cananian 1.1.2.26 treeMap.map(s, c);
171 cananian 1.1.2.26 }
172 cananian 1.1.2.26 public void visit(NATIVECALL s) {
173 cananian 1.1.2.26 if (!visited.add(s)) return;
174 cananian 1.1.2.26 TEMP tNew = (s.getRetval()==null)?null:_MAP(s.getRetval());
175 cananian 1.1.2.26 StmExpList x = reorder(s.kids());
176 cananian 1.1.2.26 NATIVECALL nc = new NATIVECALL(tf, s, tNew,
177 cananian 1.1.2.26 x.exps.head, x.exps.tail);
178 cananian 1.1.2.26 treeMap.map(s, nc);
179 cananian 1.1.2.26 }
180 cananian 1.1.2.26
181 duncan 1.1.2.8 public void visit(TEMP e) {
182 duncan 1.1.2.12 if (!visited.add(e)) return;
183 duncan 1.1.2.8 TEMP tNew = _MAP(e);
184 duncan 1.1.2.8 treeMap.map(e, reorderExp(tNew));
185 duncan 1.1.2.8 }
186 duncan 1.1.2.8
187 duncan 1.1.2.1 public void visit(ESEQ e) {
188 duncan 1.1.2.12 if (!visited.add(e)) return;
189 duncan 1.1.2.19 e.getStm().accept(this);
190 duncan 1.1.2.19 e.getExp().accept(this);
191 duncan 1.1.2.3 treeMap.map(e, new ESEQ(tf, e,
192 duncan 1.1.2.19 seq(treeMap.get(e.getStm()),
193 duncan 1.1.2.19 ((ESEQ)treeMap.get(e.getExp())).getStm()),
194 duncan 1.1.2.19 ((ESEQ)treeMap.get(e.getExp())).getExp()));
195 duncan 1.1.2.13 }
196 duncan 1.1.2.13
197 cananian 1.1.2.20 private Stm reorderData(DATUM s) {
198 duncan 1.1.2.13 ExpList kids = s.kids();
199 duncan 1.1.2.13 if (kids.head==null) return s.build(tf, kids);
200 duncan 1.1.2.13 else {
201 duncan 1.1.2.19 StmExpList x = reorder(kids);
202 duncan 1.1.2.19 return seq((x.stm), s.build(tf, x.exps));
203 duncan 1.1.2.13 }
204 duncan 1.1.2.1 }
205 duncan 1.1.2.19
206 duncan 1.1.2.8 private Stm reorderMove(MOVE m) {
207 duncan 1.1.2.19 if (m.getDst().kind() == TreeKind.TEMP) {
208 duncan 1.1.2.19 TEMP tNew = _MAP((TEMP)m.getDst());
209 cananian 1.1.2.26 StmExpList x = reorder(m.kids());
210 cananian 1.3.2.1 assert x.exps.tail==null;
211 cananian 1.1.2.26 return seq(x.stm, new MOVE(tf, m, tNew, x.exps.head));
212 duncan 1.1.2.8 }
213 duncan 1.1.2.8 else {
214 cananian 1.3.2.1 assert m.getDst().kind() == TreeKind.MEM;
215 cananian 1.1.2.18 StmExpList d = reorder(new ExpList(m.kids().head, null));
216 cananian 1.1.2.18 StmExpList s = reorder(m.kids().tail);
217 cananian 1.3.2.1 assert d.exps.tail==null && s.exps.tail==null;
218 cananian 1.1.2.26 MOVE nm = new MOVE(tf, m,
219 cananian 1.1.2.26 m.getDst().build(tf, d.exps),
220 cananian 1.1.2.26 s.exps.head);
221 cananian 1.1.2.26 return seq(s.stm, seq(d.stm, nm));
222 duncan 1.1.2.8 }
223 duncan 1.1.2.8 }
224 duncan 1.1.2.1
225 duncan 1.1.2.1 private Stm reorderStm(Stm s) {
226 duncan 1.1.2.1 StmExpList x = reorder(s.kids());
227 duncan 1.1.2.8 return seq(x.stm, s.build(tf, x.exps));
228 duncan 1.1.2.1 }
229 duncan 1.1.2.1
230 duncan 1.1.2.1 private ESEQ reorderExp (Exp e) {
231 duncan 1.1.2.1 StmExpList x = reorder(e.kids());
232 duncan 1.1.2.8 return new ESEQ(tf, e, x.stm, e.build(tf, x.exps));
233 duncan 1.1.2.1 }
234 duncan 1.1.2.1
235 duncan 1.1.2.1 private StmExpList reorder(ExpList exps) {
236 duncan 1.1.2.8 if (exps==null)
237 duncan 1.1.2.8 return new StmExpList
238 jwhaley 1.1.2.29 (new EXPR
239 duncan 1.1.2.8 (this.tf, code.getRootElement(),
240 duncan 1.1.2.8 new CONST(this.tf, code.getRootElement(), 0)),
241 duncan 1.1.2.8 null);
242 duncan 1.1.2.1 else {
243 cananian 1.1.2.16 Exp a = exps.head; a.accept(this);
244 duncan 1.1.2.1 ESEQ aa = (ESEQ)treeMap.get(a);
245 duncan 1.1.2.21
246 duncan 1.1.2.1 StmExpList bb = reorder(exps.tail);
247 duncan 1.1.2.21
248 duncan 1.1.2.19 if (commute(bb.stm, aa.getExp()))
249 duncan 1.1.2.19 return new StmExpList(seq(aa.getStm(),bb.stm),
250 duncan 1.1.2.19 new ExpList(aa.getExp(),bb.exps));
251 duncan 1.1.2.8 else { // FIXME: must update DT for new Temp
252 duncan 1.1.2.1 Temp t = new Temp(tf.tempFactory());
253 duncan 1.1.2.1 return new StmExpList
254 duncan 1.1.2.1 (seq
255 duncan 1.1.2.19 (aa.getStm(),
256 duncan 1.1.2.1 seq
257 duncan 1.1.2.1 (new MOVE
258 duncan 1.1.2.1 (tf, aa,
259 duncan 1.1.2.19 new TEMP(tf, aa, aa.getExp().type(), t),
260 duncan 1.1.2.19 aa.getExp()),
261 duncan 1.1.2.1 bb.stm)),
262 duncan 1.1.2.19 new ExpList(new TEMP(tf, aa, aa.getExp().type(), t),
263 duncan 1.1.2.1 bb.exps));
264 duncan 1.1.2.1 }
265 duncan 1.1.2.1 }
266 duncan 1.1.2.1 }
267 duncan 1.1.2.1
268 cananian 1.1.2.24 protected void updateDT(Exp eOld, Exp eNew) {
269 cananian 1.1.2.24 HClass hc = oldDeriv.typeMap(eOld);
270 cananian 1.1.2.24 if (hc!=null) {
271 cananian 1.1.2.24 if (eNew instanceof TEMP)
272 cananian 1.1.2.24 m_dg.putTypeAndTemp(eNew, hc, ((TEMP)eNew).temp);
273 cananian 1.1.2.24 else
274 cananian 1.1.2.24 m_dg.putType(eNew, hc);
275 cananian 1.1.2.24 } else {
276 cananian 1.1.2.24 m_dg.putDerivation(eNew, oldDeriv.derivation(eOld));
277 duncan 1.1.2.1 }
278 duncan 1.1.2.1 }
279 duncan 1.1.2.1
280 duncan 1.1.2.3 Stm seq(Stm a, Stm b) {
281 duncan 1.1.2.8 if (isNop(a)) return b;
282 duncan 1.1.2.3 else if (isNop(b)) return a;
283 duncan 1.1.2.3 else return new SEQ(tf, a, a, b);
284 duncan 1.1.2.3 }
285 duncan 1.1.2.8
286 duncan 1.1.2.8 private TEMP _MAP(TEMP t) {
287 cananian 1.1.2.27 return (TEMP)t.rename(tf, ctm, new Tree.CloneCallback() {
288 cananian 1.1.2.28 public Tree callback(Tree o, Tree n, TempMap tm) { return n; }
289 cananian 1.1.2.27 });
290 duncan 1.1.2.8 }
291 duncan 1.1.2.3 }
292 duncan 1.1.2.8
293 duncan 1.1.2.1 static boolean commute(Stm a, Exp b) {
294 duncan 1.1.2.5 return isNop(a) ||
295 duncan 1.1.2.5 (b.kind()==TreeKind.NAME) ||
296 duncan 1.1.2.5 (b.kind()==TreeKind.CONST);
297 duncan 1.1.2.1 }
298 duncan 1.1.2.1
299 duncan 1.1.2.1 static boolean isNop(Stm s) {
300 jwhaley 1.1.2.29 return (s.kind()==TreeKind.EXPR) &&
301 jwhaley 1.1.2.29 ((((EXPR)s).getExp()).kind()==TreeKind.CONST);
302 duncan 1.1.2.1 }
303 duncan 1.1.2.1 }
304 duncan 1.1.2.1
305 duncan 1.1.2.1 class StmExpList {
306 duncan 1.1.2.1 Stm stm;
307 duncan 1.1.2.1 ExpList exps;
308 duncan 1.1.2.1 StmExpList(Stm s, ExpList e) {stm=s; exps=e;}
309 duncan 1.1.2.1 }
310 duncan 1.1.2.1
311 duncan 1.1.2.1 class TreeMap {
312 duncan 1.1.2.8 private Map h = new HashMap();
313 duncan 1.1.2.1 void map(Tree t1, Tree t2) { h.put(t1, t2); }
314 duncan 1.1.2.1 Exp get(Exp e) { return (Exp)h.get(e); }
315 duncan 1.1.2.1 Stm get(Stm s) { return (Stm)h.get(s); }
316 duncan 1.1.2.1 }
317 duncan 1.1.2.1
318 duncan 1.1.2.1
319 duncan 1.1.2.1
320 duncan 1.1.2.1
321 duncan 1.1.2.1
322 duncan 1.1.2.1
323 cananian 1.2