1 cananian 1.1.2.1 // Canonicalize.java, created Mon Feb 14 20:16:11 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.Tree;
5 cananian 1.1.2.1
6 cananian 1.1.2.3 import harpoon.Analysis.Maps.Derivation.DList;
7 cananian 1.1.2.3 import harpoon.ClassFile.HClass;
8 cananian 1.1.2.1 import harpoon.ClassFile.HCodeFactory;
9 cananian 1.1.2.3 import harpoon.IR.Tree.DerivationGenerator;
10 cananian 1.1.2.1 import harpoon.IR.Tree.ESEQ;
11 jwhaley 1.1.2.5 import harpoon.IR.Tree.EXPR;
12 cananian 1.1.2.1 import harpoon.IR.Tree.Exp;
13 cananian 1.1.2.1 import harpoon.IR.Tree.ExpList;
14 cananian 1.1.2.1 import harpoon.IR.Tree.MOVE;
15 cananian 1.1.2.1 import harpoon.IR.Tree.SEQ;
16 cananian 1.1.2.1 import harpoon.IR.Tree.Stm;
17 cananian 1.1.2.1 import harpoon.IR.Tree.TEMP;
18 cananian 1.1.2.1 import harpoon.IR.Tree.Tree;
19 cananian 1.1.2.1 import harpoon.IR.Tree.TreeFactory;
20 cananian 1.1.2.1 import harpoon.IR.Tree.TreeKind;
21 cananian 1.1.2.1 import harpoon.Temp.Temp;
22 cananian 1.1.2.1
23 cananian 1.1.2.1 import java.util.ArrayList;
24 cananian 1.1.2.1 import java.util.Collections;
25 cananian 1.1.2.1 import java.util.List;
26 cananian 1.1.2.1 /**
27 cananian 1.1.2.3 * <code>Canonicalize</code> is an application of <code>Simplification</code>
28 cananian 1.1.2.3 * to do pattern-driven tree canonicalization.
29 cananian 1.1.2.1 *
30 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
31 cananian 1.2 * @version $Id: Canonicalize.java,v 1.2 2002/02/25 21:00:32 cananian Exp $
32 cananian 1.1.2.1 */
33 cananian 1.1.2.1 public abstract class Canonicalize extends Simplification {
34 cananian 1.1.2.1 // hide constructor
35 cananian 1.1.2.1 private Canonicalize() { }
36 cananian 1.1.2.1
37 cananian 1.1.2.1 private final static List _RULES = new ArrayList();
38 cananian 1.1.2.3 /** Default canonicalization rules. */
39 cananian 1.1.2.1 public final static List RULES = // protect the rules list.
40 cananian 1.1.2.1 Collections.unmodifiableList(_RULES);
41 cananian 1.1.2.1
42 cananian 1.1.2.1 /** Code factory for applying the default set of simplifications to
43 cananian 1.1.2.1 * the given tree form. Clones the tree before simplifying it
44 cananian 1.1.2.1 * in-place. */
45 cananian 1.1.2.1 public static HCodeFactory codeFactory(final HCodeFactory parent) {
46 cananian 1.1.2.1 return codeFactory(parent, RULES);
47 cananian 1.1.2.1 }
48 cananian 1.1.2.1
49 cananian 1.1.2.1 // static initialization: add all rules to the rule set
50 cananian 1.1.2.1 static {
51 cananian 1.1.2.1
52 cananian 1.1.2.2 // ...REDUCE TOP-LEVEL ESEQs...
53 cananian 1.1.2.1 // ESEQ(s1, ESEQ(s2, e)) --> ESEQ(SEQ(s1, s2), e)
54 cananian 1.1.2.1 Rule doubleEseq = new Rule("doubleEseq") {
55 cananian 1.1.2.1 public boolean match(Exp e) {
56 cananian 1.1.2.1 if (!contains(_KIND(e), _ESEQ)) return false;
57 cananian 1.1.2.1 ESEQ eseq = (ESEQ) e;
58 cananian 1.1.2.1 return contains(_KIND(eseq.getExp()), _ESEQ);
59 cananian 1.1.2.1 }
60 cananian 1.1.2.3 public Exp apply(TreeFactory tf, Exp e, DerivationGenerator dg) {
61 cananian 1.1.2.1 ESEQ e1 = (ESEQ) e;
62 cananian 1.1.2.1 ESEQ e2 = (ESEQ) e1.getExp();
63 cananian 1.1.2.3 if (dg!=null) { dg.remove(e1); dg.remove(e2); }
64 cananian 1.1.2.1 return new ESEQ(tf, e,
65 cananian 1.1.2.1 new SEQ(tf, e, e1.getStm(), e2.getStm()),
66 cananian 1.1.2.1 e2.getExp());
67 cananian 1.1.2.1 }
68 cananian 1.1.2.1 };
69 cananian 1.1.2.2 // ...REDUCE LEFT-MOST ESEQs.....
70 cananian 1.1.2.1 // BINOP(op, ESEQ(s, e1), e2) --> ESEQ(s, BINOP(op, e1, e2))
71 cananian 1.1.2.1 // MEM(ESEQ(s, e1)) --> ESEQ(s, MEM(e1))
72 cananian 1.1.2.1 // ...and other Exps with ESEQs as left-most child...
73 cananian 1.1.2.1 // JUMP(ESEQ(s, e1)) --> SEQ(s, JUMP(e1))
74 cananian 1.1.2.1 // CJUMP(ESEQ(s, e1), l1, l2) --> SEQ(s, CJUMP(e1, l1, l2))
75 cananian 1.1.2.1 // ...and other Stms with ESEQs as left-most child.
76 cananian 1.1.2.1 Rule leftEseq = new Rule("leftEseq") {
77 cananian 1.1.2.1 public boolean match(Exp e) {
78 cananian 1.1.2.1 if (contains(_KIND(e), _ESEQ)) return false;
79 cananian 1.1.2.1 if (e.getParent()!=null && // avoid MOVE(ESEQ(MEM(..)), ..)
80 cananian 1.1.2.4 contains(_KIND(e.getParent()), _MOVE) &&
81 cananian 1.1.2.4 ((MOVE)e.getParent()).getDst() == e) return false;
82 cananian 1.1.2.1 ExpList el = e.kids();
83 cananian 1.1.2.1 if (el==null) return false;
84 cananian 1.1.2.1 return contains(_KIND(el.head), _ESEQ);
85 cananian 1.1.2.1 }
86 cananian 1.1.2.3 public Exp apply(TreeFactory tf, Exp e, DerivationGenerator dg) {
87 cananian 1.1.2.1 ExpList el = e.kids();
88 cananian 1.1.2.1 ESEQ eseq = (ESEQ) el.head;
89 cananian 1.1.2.1 el = new ExpList(eseq.getExp(), el.tail);
90 cananian 1.1.2.3 Exp newE = e.build(el);
91 cananian 1.1.2.3 if (dg != null) dg.update(e, newE);
92 cananian 1.1.2.3 return new ESEQ(tf, e, eseq.getStm(), newE);
93 cananian 1.1.2.1 }
94 cananian 1.1.2.1 public boolean match(Stm s) {
95 cananian 1.1.2.1 if (contains(_KIND(s), _SEQ)) return false;
96 cananian 1.1.2.1 ExpList el = s.kids();
97 cananian 1.1.2.1 if (el==null) return false;
98 cananian 1.1.2.1 return contains(_KIND(el.head), _ESEQ);
99 cananian 1.1.2.1 }
100 cananian 1.1.2.3 public Stm apply(TreeFactory tf, Stm s, DerivationGenerator dg) {
101 cananian 1.1.2.1 ExpList el = s.kids();
102 cananian 1.1.2.1 ESEQ eseq = (ESEQ) el.head;
103 cananian 1.1.2.1 el = new ExpList(eseq.getExp(), el.tail);
104 cananian 1.1.2.6 return new SEQ(tf, s, eseq.getStm(), sbuild(s,dg, el));
105 cananian 1.1.2.1 }
106 cananian 1.1.2.1 };
107 cananian 1.1.2.1
108 cananian 1.1.2.2 // ...MOVE RIGHT-HAND ESEQs LEFTWARD...
109 cananian 1.1.2.1 // BINOP(op, e1, ESEQ(s, e2)) --> ESEQ(s, BINOP(op, e1, e2))
110 cananian 1.1.2.2 // if (s, e1) commute...
111 cananian 1.1.2.2 // --> BINOP(op, ESEQ(SEQ(MOVE(t, e1), s), t), e2)
112 cananian 1.1.2.2 // ...otherwise.
113 cananian 1.1.2.1 // CALL(..[e1, ESEQ(s, e2), e3]..)-->SEQ(s, CALL(..[e1, e2, e3]..))
114 cananian 1.1.2.2 // if (s, e1) commute...
115 cananian 1.1.2.2 // --> CALL(..[ESEQ(SEQ(MOVE(t, e1), s), t), e2, e3]..)
116 cananian 1.1.2.2 // ...otherwise.
117 cananian 1.1.2.2 Rule rightEseq = new Rule("rightEseq") {
118 cananian 1.1.2.1 public boolean match(Exp e) {
119 cananian 1.1.2.1 if (contains(_KIND(e), _ESEQ)) return false;
120 cananian 1.1.2.1 ExpList el = e.kids();
121 cananian 1.1.2.1 if (el==null || el.tail==null) return false;
122 cananian 1.1.2.1 for (ExpList elp = el; elp.tail!=null; elp=elp.tail) {
123 cananian 1.1.2.1 if (contains(_KIND(elp.tail.head), _ESEQ))
124 cananian 1.1.2.2 return true;
125 cananian 1.1.2.1 }
126 cananian 1.1.2.1 return false;
127 cananian 1.1.2.1 }
128 cananian 1.1.2.1 public boolean match(Stm s) {
129 cananian 1.1.2.1 if (contains(_KIND(s), _SEQ)) return false;
130 cananian 1.1.2.1 ExpList el = s.kids();
131 cananian 1.1.2.1 if (el==null || el.tail==null) return false;
132 cananian 1.1.2.1 for (ExpList elp = el; elp.tail!=null; elp=elp.tail) {
133 cananian 1.1.2.1 if (contains(_KIND(elp.tail.head), _ESEQ))
134 cananian 1.1.2.2 return true;
135 cananian 1.1.2.1 }
136 cananian 1.1.2.1 return false;
137 cananian 1.1.2.1 }
138 cananian 1.1.2.3 public Exp apply(TreeFactory tf, Exp e, DerivationGenerator dg) {
139 cananian 1.1.2.3 Exp newE = e.build(shiftOne(tf, dg, e.kids()));
140 cananian 1.1.2.3 if (dg != null) dg.update(e, newE);
141 cananian 1.1.2.3 return newE;
142 cananian 1.1.2.1 }
143 cananian 1.1.2.3 public Stm apply(TreeFactory tf, Stm s, DerivationGenerator dg) {
144 cananian 1.1.2.6 return sbuild(s,dg, shiftOne(tf, dg, s.kids()));
145 cananian 1.1.2.3 }
146 cananian 1.1.2.3 ExpList shiftOne(TreeFactory tf, DerivationGenerator dg,
147 cananian 1.1.2.3 ExpList el) {
148 cananian 1.1.2.1 if (!contains(_KIND(el.tail.head), _ESEQ))
149 cananian 1.1.2.3 return new ExpList(el.head, shiftOne(tf, dg, el.tail));
150 cananian 1.1.2.1 Exp e1 = el.head;
151 cananian 1.1.2.1 ESEQ e2 = (ESEQ) el.tail.head;
152 cananian 1.1.2.3 if (dg != null) dg.remove(e2); // ain't gonna live no mo'
153 cananian 1.1.2.3 if (commute(e2.getStm(), e1)) { // simple case.
154 cananian 1.1.2.3 // [..e1, ESEQ(s, e2), ..] --> [..ESEQ(s, e1), e2,..]
155 cananian 1.1.2.2 return new ExpList(new ESEQ(tf, e1, e2.getStm(), e1),
156 cananian 1.1.2.2 new ExpList(e2.getExp(), el.tail.tail));
157 cananian 1.1.2.3 }
158 cananian 1.1.2.2 // otherwise, we have to make a new temp...
159 cananian 1.1.2.3 // [..e1, ESEQ(s, e2),..] -->
160 cananian 1.1.2.3 // [..ESEQ(SEQ(MOVE(t, e1), s), t), e2..]
161 cananian 1.1.2.2 Temp t = new Temp(tf.tempFactory(), "canon");
162 cananian 1.1.2.3 TEMP T1 = new TEMP(tf, e1, e1.type(), t);
163 cananian 1.1.2.3 TEMP T2 = new TEMP(tf, e1, e1.type(), t);
164 cananian 1.1.2.3 if (dg!=null) { // make types for the new TEMPs/Temp
165 cananian 1.1.2.3 HClass hc = dg.typeMap(e1);
166 cananian 1.1.2.3 if (hc!=null) {
167 cananian 1.1.2.3 dg.putTypeAndTemp(T1, hc, t);
168 cananian 1.1.2.3 dg.putTypeAndTemp(T2, hc, t);
169 cananian 1.1.2.3 } else {
170 cananian 1.1.2.3 dg.putDerivation(T1, dg.derivation(e1));
171 cananian 1.1.2.3 dg.putDerivation(T2, dg.derivation(e1));
172 cananian 1.1.2.3 }
173 cananian 1.1.2.3 }
174 cananian 1.1.2.1 return new ExpList
175 cananian 1.1.2.1 (new ESEQ
176 cananian 1.1.2.1 (tf, e1,
177 cananian 1.1.2.1 new SEQ
178 cananian 1.1.2.1 (tf, e1,
179 cananian 1.1.2.3 new MOVE(tf, e1, T1, e1),
180 cananian 1.1.2.1 e2.getStm() ),
181 cananian 1.1.2.3 T2 ),
182 cananian 1.1.2.1 new ExpList(e2.getExp(), el.tail.tail));
183 cananian 1.1.2.1 }
184 cananian 1.1.2.1 };
185 cananian 1.1.2.1
186 cananian 1.1.2.1 // add rules to the rule set.
187 cananian 1.1.2.1 _RULES.add(doubleEseq);
188 cananian 1.1.2.1 _RULES.add(leftEseq);
189 cananian 1.1.2.2 _RULES.add(rightEseq);
190 cananian 1.1.2.1 }
191 cananian 1.1.2.1
192 cananian 1.1.2.1 private static boolean commute(Stm a, Exp b) {
193 cananian 1.1.2.1 return isNop(a) || contains(_KIND(b), _NAME|_CONST);
194 cananian 1.1.2.1 }
195 cananian 1.1.2.1 private static boolean isNop(Stm a) {
196 jwhaley 1.1.2.5 return contains(_KIND(a), _EXPR) &&
197 jwhaley 1.1.2.5 contains(_KIND(((EXPR)a).getExp()), _CONST|_TEMP);
198 cananian 1.1.2.6 }
199 cananian 1.1.2.6 /* MOVE.build() doesn't correctly propagate derivation information to
200 cananian 1.1.2.6 * MOVE(MEM(...), ...); this utility function fixes this case up. */
201 cananian 1.1.2.6 private static Stm sbuild(Stm s, DerivationGenerator dg, ExpList kids) {
202 cananian 1.1.2.6 Stm ns = s.build(kids);
203 cananian 1.1.2.6 if (dg!=null &&
204 cananian 1.1.2.6 contains(_KIND(s), _MOVE) &&
205 cananian 1.1.2.6 contains(_KIND(s.getFirstChild()), _MEM))
206 cananian 1.1.2.6 dg.update((Exp)s.getFirstChild(), (Exp)ns.getFirstChild());
207 cananian 1.1.2.6 return ns;
208 cananian 1.1.2.1 }
209 cananian 1.1.2.2 /** Testing function, for use in assertions that a given tree is
210 cananian 1.1.2.2 * canonical. */
211 cananian 1.1.2.1 public static boolean containsEseq(Tree t) {
212 cananian 1.1.2.1 if (t.kind() == TreeKind.ESEQ) return true;
213 cananian 1.1.2.1 // else, recurse
214 cananian 1.1.2.1 for (Tree tp=t.getFirstChild(); tp!=null; tp=tp.getSibling())
215 cananian 1.1.2.1 if (containsEseq(tp)) return true;
216 cananian 1.1.2.1 // i guess it doesn't, then.
217 cananian 1.1.2.1 return false;
218 cananian 1.1.2.1 }
219 cananian 1.2 }