1 cananian 1.1.2.1 // CommutativityExpander.java, created Thu Feb 17 15:42:30 2000 by cananian
2 cananian 1.1.2.1 // Copyright (C) 1999 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.Tools.PatMat;
5 cananian 1.1.2.1
6 cananian 1.1.2.1 /**
7 cananian 1.1.2.1 * The <code>CommutativityExpander</code> tool expands a set of
8 cananian 1.1.2.1 * <code>Spec.Rules</code> to include add'l valid patterns
9 cananian 1.1.2.1 * generated from the commutative properties of various
10 cananian 1.1.2.1 * <code>Spec.ExpBinop</code>s.
11 cananian 1.1.2.1 *
12 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
13 cananian 1.2 * @version $Id: CommutativityExpander.java,v 1.2 2002/02/25 21:08:30 cananian Exp $
14 cananian 1.1.2.1 */
15 cananian 1.1.2.1 public abstract class CommutativityExpander {
16 cananian 1.1.2.1 //hide constructor.
17 cananian 1.1.2.1 private CommutativityExpander() { }
18 cananian 1.1.2.5 // prefix for generated private members
19 cananian 1.1.2.5 private final static String prefix="__CommExp__";
20 cananian 1.1.2.5
21 cananian 1.1.2.5 // two functions needed both here and in the generated code.
22 cananian 1.1.2.5 private final static String isCommFunc =
23 cananian 1.1.2.5 "private static boolean "+prefix+"isCommutative(int op) {\n"+
24 cananian 1.1.2.5 "\tswitch(op) {\n"+
25 cananian 1.1.2.5 "\tcase harpoon.IR.Tree.Bop.CMPGT:\n"+
26 cananian 1.1.2.5 "\tcase harpoon.IR.Tree.Bop.CMPGE:\n"+
27 cananian 1.1.2.5 "\tcase harpoon.IR.Tree.Bop.CMPLE:\n"+
28 cananian 1.1.2.5 "\tcase harpoon.IR.Tree.Bop.CMPLT: return true; \n"+
29 cananian 1.1.2.5 "\tdefault: return harpoon.IR.Tree.Bop.isCommutative(op);\n"+
30 cananian 1.1.2.5 "\t}\n"+
31 cananian 1.1.2.5 "}\n";
32 cananian 1.1.2.5 private static boolean isCommutative(int op) {
33 cananian 1.1.2.5 switch(op) {
34 cananian 1.1.2.5 case harpoon.IR.Tree.Bop.CMPGT:
35 cananian 1.1.2.5 case harpoon.IR.Tree.Bop.CMPGE:
36 cananian 1.1.2.5 case harpoon.IR.Tree.Bop.CMPLE:
37 cananian 1.1.2.5 case harpoon.IR.Tree.Bop.CMPLT: return true;
38 cananian 1.1.2.5 default: return harpoon.IR.Tree.Bop.isCommutative(op);
39 cananian 1.1.2.5 }
40 cananian 1.1.2.5 }
41 cananian 1.1.2.5 private final static String swapCmpOpFunc =
42 cananian 1.1.2.5 "private static int "+prefix+"swapCmpOp(int op) {\n"+
43 cananian 1.1.2.5 "\tswitch(op) {\n"+
44 cananian 1.1.2.5 "\tcase harpoon.IR.Tree.Bop.CMPGT:return harpoon.IR.Tree.Bop.CMPLT;\n"+
45 cananian 1.1.2.5 "\tcase harpoon.IR.Tree.Bop.CMPGE:return harpoon.IR.Tree.Bop.CMPLE;\n"+
46 cananian 1.1.2.5 "\tcase harpoon.IR.Tree.Bop.CMPLE:return harpoon.IR.Tree.Bop.CMPGE;\n"+
47 cananian 1.1.2.5 "\tcase harpoon.IR.Tree.Bop.CMPLT:return harpoon.IR.Tree.Bop.CMPGT;\n"+
48 cananian 1.1.2.5 "\tdefault: return op;\n"+
49 cananian 1.1.2.5 "\t}\n"+
50 cananian 1.1.2.5 "}\n";
51 cananian 1.1.2.5 private static int swapCmpOp(int op) {
52 cananian 1.1.2.5 switch(op) {
53 cananian 1.1.2.5 case harpoon.IR.Tree.Bop.CMPGT:return harpoon.IR.Tree.Bop.CMPLT;
54 cananian 1.1.2.5 case harpoon.IR.Tree.Bop.CMPGE:return harpoon.IR.Tree.Bop.CMPLE;
55 cananian 1.1.2.5 case harpoon.IR.Tree.Bop.CMPLE:return harpoon.IR.Tree.Bop.CMPGE;
56 cananian 1.1.2.5 case harpoon.IR.Tree.Bop.CMPLT:return harpoon.IR.Tree.Bop.CMPGT;
57 cananian 1.1.2.5 default: return op;
58 cananian 1.1.2.5 }
59 cananian 1.1.2.5 }
60 cananian 1.1.2.1
61 cananian 1.1.2.5 // this is the actual expansion function.
62 cananian 1.1.2.1 public static Spec expand(Spec s) {
63 cananian 1.1.2.5 return new Spec(s.global_stms,
64 cananian 1.1.2.5 s.class_stms +"\n"+ isCommFunc + swapCmpOpFunc +"\n",
65 cananian 1.1.2.1 s.method_prologue_stms, s.method_epilogue_stms,
66 cananian 1.1.2.1 expand(s.rules));
67 cananian 1.1.2.1 }
68 cananian 1.1.2.1 private static Spec.RuleList expand(Spec.RuleList rl) {
69 cananian 1.1.2.1 if (rl==null) return null;
70 cananian 1.1.2.1 Spec.RuleList result = expand(rl.tail);
71 cananian 1.1.2.1 Spec.Rule[] ra = expand(rl.head);
72 cananian 1.1.2.1 for (int i=0; i<ra.length; i++)
73 cananian 1.1.2.1 result = new Spec.RuleList(ra[i], result);
74 cananian 1.1.2.1 return result;
75 cananian 1.1.2.1 }
76 cananian 1.1.2.1 private static Spec.Rule[] expand(Spec.Rule r) {
77 cananian 1.1.2.1 if (r instanceof Spec.RuleExp)
78 cananian 1.1.2.1 return expand((Spec.RuleExp) r);
79 cananian 1.1.2.1 if (r instanceof Spec.RuleStm)
80 cananian 1.1.2.1 return expand((Spec.RuleStm) r);
81 cananian 1.1.2.1 throw new Error("Unknown Spec.Rule type!");
82 cananian 1.1.2.1 }
83 cananian 1.1.2.1 private static Spec.RuleExp[] expand(Spec.RuleExp r) {
84 cananian 1.1.2.2 ExpAndPred[] choices = expand(r.exp);
85 cananian 1.1.2.1 Spec.RuleExp[] result = new Spec.RuleExp[choices.length];
86 cananian 1.1.2.1 for (int i=0; i<result.length; i++)
87 cananian 1.1.2.2 result[i] = new Spec.RuleExp(choices[i].exp, r.result_id,
88 cananian 1.1.2.2 addPred(r.details, choices[i].pred),
89 cananian 1.1.2.2 r.action_str);
90 cananian 1.1.2.1 return result;
91 cananian 1.1.2.1 }
92 cananian 1.1.2.1 private static Spec.RuleStm[] expand(Spec.RuleStm r) {
93 cananian 1.1.2.2 StmAndPred[] choices = expand(r.stm);
94 cananian 1.1.2.1 Spec.RuleStm[] result = new Spec.RuleStm[choices.length];
95 cananian 1.1.2.1 for (int i=0; i<result.length; i++)
96 cananian 1.1.2.2 result[i] = new Spec.RuleStm(choices[i].stm,
97 cananian 1.1.2.2 addPred(r.details, choices[i].pred),
98 cananian 1.1.2.2 r.action_str);
99 cananian 1.1.2.1 return result;
100 cananian 1.1.2.1 }
101 cananian 1.1.2.2 private static ExpAndPred[] dispatch(Spec.Exp exp) {
102 cananian 1.1.2.1 if (exp instanceof Spec.ExpBinop)
103 cananian 1.1.2.1 return expand((Spec.ExpBinop)exp);
104 cananian 1.1.2.1 else return expand(exp);
105 cananian 1.1.2.1 }
106 cananian 1.1.2.1 // this is the real deal:
107 cananian 1.1.2.2 private static ExpAndPred[] expand(Spec.ExpBinop exp) {
108 cananian 1.1.2.1 // make normal combinations first.
109 cananian 1.1.2.2 ExpListAndPred[] combos = makeAllCombinations(exp.kids());
110 cananian 1.1.2.1 // check whether this exp rules is commutative & worth expanding.
111 cananian 1.1.2.3 if ( // first off, one of left/right has to be non-id
112 cananian 1.1.2.3 !(exp.left instanceof Spec.ExpId&&exp.right instanceof Spec.ExpId)
113 cananian 1.1.2.3 && // also, if op is a leafop, it needs to be a commutative one.
114 cananian 1.1.2.3 (exp.opcode instanceof Spec.LeafId ||
115 cananian 1.1.2.3 (exp.opcode instanceof Spec.LeafOp &&
116 cananian 1.1.2.5 isCommutative(((Spec.LeafOp) exp.opcode).op))
117 cananian 1.1.2.3 )) {
118 cananian 1.1.2.5 // check to see if an extra predicate/new leaf is needed.
119 cananian 1.1.2.5 Spec.Leaf l = exp.opcode; String extrapred=null;
120 cananian 1.1.2.5 if (exp.opcode instanceof Spec.LeafOp) {
121 cananian 1.1.2.5 l = new Spec.LeafOp(swapCmpOp(((Spec.LeafOp)exp.opcode).op));
122 cananian 1.1.2.5 } else {
123 cananian 1.1.2.5 String id = ((Spec.LeafId) exp.opcode).id;
124 cananian 1.1.2.5 extrapred = prefix+"isCommutative("+
125 cananian 1.1.2.5 id+"="+prefix+"swapCmpOp("+id+"))";
126 cananian 1.1.2.5 }
127 cananian 1.1.2.1 // okay, reverse kids and make some more combos.
128 cananian 1.1.2.5 ExpAndPred[] result = new ExpAndPred[combos.length * 2];
129 cananian 1.1.2.1 for (int i=0; i<combos.length; i++) {
130 cananian 1.1.2.5 result[2*i] = new ExpAndPred(exp.build(combos[i].explist),
131 cananian 1.1.2.5 combos[i].pred);
132 cananian 1.1.2.5 // reverse args, swap op, add pred.
133 cananian 1.1.2.5 Spec.ExpBinop binop =
134 cananian 1.1.2.5 new Spec.ExpBinop((Spec.TypeSet)exp.types.clone(), l,
135 cananian 1.1.2.5 combos[i].explist.tail.head,
136 cananian 1.1.2.5 combos[i].explist.head);
137 cananian 1.1.2.5 result[2*i+1] =
138 cananian 1.1.2.5 new ExpAndPred(binop, addPred(extrapred, combos[i].pred));
139 cananian 1.1.2.1 }
140 cananian 1.1.2.5 return result;
141 cananian 1.1.2.1 }
142 cananian 1.1.2.1 // make exps from all the explists.
143 cananian 1.1.2.2 ExpAndPred[] result = new ExpAndPred[combos.length];
144 cananian 1.1.2.1 for (int i=0; i<result.length; i++)
145 cananian 1.1.2.2 result[i] = new ExpAndPred(exp.build(combos[i].explist),
146 cananian 1.1.2.2 combos[i].pred);
147 cananian 1.1.2.1 return result;
148 cananian 1.1.2.1 }
149 cananian 1.1.2.2 private static ExpAndPred[] expand(Spec.Exp exp) {
150 cananian 1.1.2.1 // make explists with all combinations of children.
151 cananian 1.1.2.2 ExpListAndPred[] combos = makeAllCombinations(exp.kids());
152 cananian 1.1.2.1 // make exps from all the explists.
153 cananian 1.1.2.2 ExpAndPred[] result = new ExpAndPred[combos.length];
154 cananian 1.1.2.1 for (int i=0; i<result.length; i++)
155 cananian 1.1.2.2 result[i] = new ExpAndPred(exp.build(combos[i].explist),
156 cananian 1.1.2.2 combos[i].pred);
157 cananian 1.1.2.1 return result;
158 cananian 1.1.2.1 }
159 cananian 1.1.2.2 private static StmAndPred[] expand(Spec.Stm stm) {
160 cananian 1.1.2.1 // make explists with all combinations of children.
161 cananian 1.1.2.2 ExpListAndPred[] combos = makeAllCombinations(stm.kids());
162 cananian 1.1.2.1 // make exps from all the explists.
163 cananian 1.1.2.2 StmAndPred[] result = new StmAndPred[combos.length];
164 cananian 1.1.2.1 for (int i=0; i<result.length; i++)
165 cananian 1.1.2.2 result[i] = new StmAndPred(stm.build(combos[i].explist),
166 cananian 1.1.2.2 combos[i].pred);
167 cananian 1.1.2.1 return result;
168 cananian 1.1.2.1 }
169 cananian 1.1.2.1 private static int size(Spec.ExpList el) {
170 cananian 1.1.2.1 int i;
171 cananian 1.1.2.1 for (i=0; el!=null; el=el.tail)
172 cananian 1.1.2.1 i++;
173 cananian 1.1.2.1 return i;
174 cananian 1.1.2.1 }
175 cananian 1.1.2.2 private static ExpListAndPred[] makeAllCombinations(Spec.ExpList kids) {
176 cananian 1.1.2.1 // construct set of expanded children.
177 cananian 1.1.2.2 ExpAndPred[][] choices = new ExpAndPred[size(kids)][];
178 cananian 1.1.2.1 for (int i=0; kids!=null; kids=kids.tail)
179 cananian 1.1.2.1 choices[i++] = dispatch(kids.head);
180 cananian 1.1.2.1 // make explists with all combinations of children.
181 cananian 1.1.2.1 return makeAllCombinations(choices);
182 cananian 1.1.2.1 }
183 cananian 1.1.2.2 private static ExpListAndPred[] makeAllCombinations(ExpAndPred[][] choices)
184 cananian 1.1.2.2 {
185 cananian 1.1.2.1 int[] state = new int[choices.length]; // all zero initially.
186 cananian 1.1.2.1 // count the # of possibilities
187 cananian 1.1.2.1 int numposs = 1;
188 cananian 1.1.2.1 for (int i=0; i<choices.length; i++)
189 cananian 1.1.2.1 numposs *= choices[i].length;
190 cananian 1.1.2.1 // iterate:
191 cananian 1.1.2.2 ExpListAndPred[] result = new ExpListAndPred[numposs];
192 cananian 1.1.2.1 for (int i=0; i < numposs; i++) {
193 cananian 1.1.2.1 // make a Spec.ExpList
194 cananian 1.1.2.2 Spec.ExpList el=null; String pred=null;
195 cananian 1.1.2.2 for (int j=state.length-1; j>=0; j--) {
196 cananian 1.1.2.2 ExpAndPred eap = choices[j][state[j]];
197 cananian 1.1.2.2 pred = addPred(eap.pred, pred);
198 cananian 1.1.2.2 el = new Spec.ExpList( eap.exp, el );
199 cananian 1.1.2.2 }
200 cananian 1.1.2.1 // add to result.
201 cananian 1.1.2.2 result[i] = new ExpListAndPred(el, pred);
202 cananian 1.1.2.1 // advance state by one
203 cananian 1.1.2.1 for (int j=0; j < state.length; j++) {
204 cananian 1.1.2.1 if (++state[j] < choices[j].length)
205 cananian 1.1.2.1 break;
206 cananian 1.1.2.1 else state[j] = 0;
207 cananian 1.1.2.1 }
208 cananian 1.1.2.1 }
209 cananian 1.1.2.1 return result;
210 cananian 1.1.2.2 }
211 cananian 1.1.2.2 private static class ExpAndPred {
212 cananian 1.1.2.2 final Spec.Exp exp;
213 cananian 1.1.2.2 final String pred;
214 cananian 1.1.2.2 ExpAndPred(Spec.Exp exp, String pred) {
215 cananian 1.1.2.2 this.exp = exp; this.pred = pred;
216 cananian 1.1.2.2 }
217 cananian 1.1.2.2 }
218 cananian 1.1.2.2 private static class ExpListAndPred {
219 cananian 1.1.2.2 final Spec.ExpList explist;
220 cananian 1.1.2.2 final String pred;
221 cananian 1.1.2.2 ExpListAndPred(Spec.ExpList explist, String pred) {
222 cananian 1.1.2.2 this.explist = explist; this.pred = pred;
223 cananian 1.1.2.2 }
224 cananian 1.1.2.2 }
225 cananian 1.1.2.2 private static class StmAndPred {
226 cananian 1.1.2.2 final Spec.Stm stm;
227 cananian 1.1.2.2 final String pred;
228 cananian 1.1.2.2 StmAndPred(Spec.Stm stm, String pred) {
229 cananian 1.1.2.2 this.stm = stm; this.pred = pred;
230 cananian 1.1.2.2 }
231 cananian 1.1.2.2 }
232 cananian 1.1.2.2 private static String addPred(String p1, String p2) {
233 cananian 1.1.2.2 if (p1==null) return p2;
234 cananian 1.1.2.2 if (p2==null) return p1;
235 cananian 1.1.2.2 return "("+p1+") && ("+p2+")";
236 cananian 1.1.2.2 }
237 cananian 1.1.2.2 private static Spec.DetailList addPred(Spec.DetailList dl, String pred) {
238 cananian 1.1.2.3 if (pred==null)
239 cananian 1.1.2.3 return dl;
240 cananian 1.1.2.2 if (dl==null)
241 cananian 1.1.2.2 return new Spec.DetailList(new Spec.DetailPredicate(pred), null);
242 cananian 1.1.2.2 if (dl.head instanceof Spec.DetailPredicate) {
243 cananian 1.1.2.2 Spec.DetailPredicate sdp = (Spec.DetailPredicate) dl.head;
244 cananian 1.1.2.2 return new Spec.DetailList(new Spec.DetailPredicate
245 cananian 1.1.2.5 (addPred(pred, sdp.predicate_string)),
246 cananian 1.1.2.5 dl.tail);
247 cananian 1.1.2.2 }
248 cananian 1.1.2.2 else return new Spec.DetailList(dl.head, addPred(dl.tail, pred));
249 cananian 1.1.2.1 }
250 cananian 1.2 }