1 bdemsky 1.1.2.1 // AllInductions.java, created Mon Jun 28 13:40:31 1999 by bdemsky
2 bdemsky 1.1.2.1 // Copyright (C) 1999 Brian Demsky <bdemsky@mit.edu>
3 bdemsky 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 bdemsky 1.1.2.1 package harpoon.Analysis.LowQuad.Loop;
5 bdemsky 1.1.2.1
6 cananian 1.1.2.11 import harpoon.Analysis.Loops.Loops;
7 cananian 1.5 import net.cscott.jutil.WorkSet;
8 bdemsky 1.1.2.1 import harpoon.Analysis.UseDef;
9 cananian 1.1.2.11 import harpoon.ClassFile.HCode;
10 cananian 1.1.2.11 import harpoon.IR.LowQuad.LQop;
11 cananian 1.1.2.11 import harpoon.IR.LowQuad.LowQuadVisitor;
12 cananian 1.1.2.11 import harpoon.IR.LowQuad.PAOFFSET;
13 cananian 1.1.2.11 import harpoon.IR.LowQuad.POPER;
14 cananian 1.1.2.10 import harpoon.IR.Properties.CFGraphable;
15 cananian 1.1.2.11 import harpoon.IR.Quads.AGET;
16 cananian 1.1.2.11 import harpoon.IR.Quads.ASET;
17 cananian 1.1.2.11 import harpoon.IR.Quads.CONST;
18 cananian 1.1.2.11 import harpoon.IR.Quads.GET;
19 cananian 1.1.2.11 import harpoon.IR.Quads.HANDLER;
20 cananian 1.1.2.11 import harpoon.IR.Quads.OPER;
21 cananian 1.1.2.11 import harpoon.IR.Quads.Qop;
22 cananian 1.1.2.11 import harpoon.IR.Quads.Quad;
23 cananian 1.1.2.11 import harpoon.IR.Quads.SET;
24 bdemsky 1.1.2.1 import harpoon.Temp.Temp;
25 bdemsky 1.1.2.1 import harpoon.Temp.TempMap;
26 bdemsky 1.1.2.1 import harpoon.Util.Util;
27 bdemsky 1.1.2.1
28 bdemsky 1.1.2.1 import java.util.HashMap;
29 bdemsky 1.1.2.1 import java.util.Iterator;
30 bdemsky 1.1.2.1
31 bdemsky 1.1.2.1 /**
32 bdemsky 1.1.2.1 * <code>AllInductions</code>
33 bdemsky 1.1.2.1 *
34 bdemsky 1.1.2.1 * @author Brian Demsky <bdemsky@mit.edu>
35 cananian 1.5 * @version $Id: AllInductions.java,v 1.5 2004/02/08 01:52:53 cananian Exp $
36 bdemsky 1.1.2.1 */
37 bdemsky 1.1.2.1 public class AllInductions {
38 bdemsky 1.1.2.1 TempMap tm;
39 bdemsky 1.1.2.1 HCode hc;
40 bdemsky 1.1.2.1
41 bdemsky 1.1.2.3 /** Creates a <code>AllInductions</code> object. */
42 bdemsky 1.1.2.1 public AllInductions(TempMap tm, HCode hc) {
43 bdemsky 1.1.2.1 this.tm=tm;
44 bdemsky 1.1.2.1 this.hc=hc;
45 bdemsky 1.1.2.1 }
46 bdemsky 1.1.2.1
47 bdemsky 1.1.2.2 /** Returns a Hashmap mapping induction <code>Temp</code>s
48 bdemsky 1.1.2.2 * to <code>Induction</code> objects containing information
49 bdemsky 1.1.2.2 * on their derivation.*/
50 bdemsky 1.1.2.2
51 bdemsky 1.1.2.3 public HashMap doAllInductions(Loops lp, WorkSet invariants, HashMap basicinductions) {
52 bdemsky 1.1.2.1 HashMap allInductions=new HashMap(basicinductions);
53 bdemsky 1.1.2.1 CompleteVisitor visitor=new CompleteVisitor(allInductions,invariants);
54 cananian 1.1.2.14 WorkSet elements=new WorkSet(lp.loopIncElements());
55 bdemsky 1.1.2.1 // Want to look for patterns like:
56 bdemsky 1.1.2.1 /* k=j*b, k=j+-b, k=b+-j */
57 bdemsky 1.1.2.1 // Use the representation:
58 bdemsky 1.1.2.1 // (i*a+b)*pa+pb-->i*(a+pa)+(b*pa+pb)
59 bdemsky 1.1.2.1 boolean change=true;
60 bdemsky 1.1.2.1 while (change) {
61 bdemsky 1.1.2.1 change=false;
62 bdemsky 1.1.2.1 Iterator iterate=elements.iterator();
63 bdemsky 1.1.2.1 while (iterate.hasNext()) {
64 bdemsky 1.1.2.1 Quad element=(Quad)iterate.next();
65 cananian 1.1.2.6 element.accept(visitor);
66 bdemsky 1.1.2.1 if (visitor.change()) {
67 bdemsky 1.1.2.1 change=true;
68 bdemsky 1.1.2.1 iterate.remove();
69 bdemsky 1.1.2.1 }
70 bdemsky 1.1.2.1 }
71 bdemsky 1.1.2.1 }
72 bdemsky 1.1.2.1 return allInductions;
73 bdemsky 1.1.2.1 }
74 bdemsky 1.1.2.1
75 bdemsky 1.1.2.1
76 bdemsky 1.1.2.2 /** CompleteVisitor extends <code>LowQuadVisitor</code>
77 bdemsky 1.1.2.2 * and is used to find derived induction variables. */
78 bdemsky 1.1.2.2
79 bdemsky 1.1.2.1 class CompleteVisitor extends LowQuadVisitor {
80 bdemsky 1.1.2.1 HashMap inductions;
81 bdemsky 1.1.2.1 WorkSet invariants;
82 bdemsky 1.1.2.1 boolean changed;
83 bdemsky 1.1.2.1 UseDef ud;
84 bdemsky 1.1.2.1
85 bdemsky 1.1.2.1 CompleteVisitor(HashMap inductions,WorkSet invariants) {
86 cananian 1.1.2.12 super(false/*non-strict*/);
87 bdemsky 1.1.2.1 changed=false;
88 bdemsky 1.1.2.1 this.inductions=inductions;
89 bdemsky 1.1.2.1 this.invariants=invariants;
90 bdemsky 1.1.2.1 ud=new UseDef();
91 bdemsky 1.1.2.1 }
92 bdemsky 1.1.2.1
93 bdemsky 1.1.2.1 public boolean change() {
94 bdemsky 1.1.2.1 return changed;
95 bdemsky 1.1.2.1 }
96 bdemsky 1.1.2.1
97 bdemsky 1.1.2.1 public void visit(Quad q) {
98 bdemsky 1.1.2.1 //Do nothing
99 bdemsky 1.1.2.1 }
100 bdemsky 1.1.2.7
101 bdemsky 1.1.2.1 public void visit(OPER q) {
102 bdemsky 1.1.2.7 switch (q.opcode()) {
103 bdemsky 1.1.2.7 case Qop.IADD:
104 bdemsky 1.1.2.7 //Binary operators
105 bdemsky 1.1.2.7 InstanceofCONSTVisitor visitor=new InstanceofCONSTVisitor();
106 bdemsky 1.1.2.9 boolean good=true;
107 bdemsky 1.1.2.9 int invar=0;
108 bdemsky 1.1.2.9 int index=0;
109 bdemsky 1.1.2.7 for (int i=0;i<q.operandsLength();i++) {
110 bdemsky 1.1.2.7 Temp t=tm.tempMap(q.operands(i));
111 bdemsky 1.1.2.7 if (inductions.containsKey(t)) {
112 bdemsky 1.1.2.7 index=i;
113 bdemsky 1.1.2.7 invar++;
114 bdemsky 1.1.2.7 }
115 bdemsky 1.1.2.7 else
116 bdemsky 1.1.2.7 if (!invariants.contains(ud.defMap(hc,t)[0])) {
117 bdemsky 1.1.2.7 good=false;
118 bdemsky 1.1.2.7 break;
119 bdemsky 1.1.2.7 }
120 bdemsky 1.1.2.7 }
121 bdemsky 1.1.2.7 //Need one induction variable and constants
122 bdemsky 1.1.2.7 if ((invar==1)&&(good)) {
123 bdemsky 1.1.2.7 changed=true;
124 bdemsky 1.1.2.7 //*****************
125 bdemsky 1.1.2.7 Induction tmp=new Induction((Induction)inductions.get(tm.tempMap(q.operands(index))));
126 bdemsky 1.1.2.7 for (int i=0;i<q.operandsLength();i++)
127 bdemsky 1.1.2.7 if (i!=index) {
128 bdemsky 1.1.2.7 Temp t=tm.tempMap(q.operands(i));
129 bdemsky 1.1.2.7 visitor.reset();
130 bdemsky 1.1.2.7 ((Quad)ud.defMap(hc,t)[0]).accept(visitor);
131 bdemsky 1.1.2.7 if (visitor.resetstatus())
132 bdemsky 1.1.2.7 tmp=tmp.add
133 bdemsky 1.1.2.7 (((Integer)(((CONST)ud.defMap(hc,t)[0]).value())).intValue());
134 bdemsky 1.1.2.7 else
135 bdemsky 1.1.2.7 tmp=tmp.add(tm.tempMap(q.operands(i)));
136 bdemsky 1.1.2.7 }
137 bdemsky 1.1.2.7 inductions.put(q.dst(),tmp);
138 bdemsky 1.1.2.7 } else
139 bdemsky 1.1.2.7 changed=false;
140 bdemsky 1.1.2.7 break;
141 bdemsky 1.1.2.7
142 bdemsky 1.1.2.7
143 bdemsky 1.1.2.7
144 bdemsky 1.1.2.7 case Qop.IMUL:
145 bdemsky 1.1.2.7 //Binary operators
146 bdemsky 1.1.2.7 visitor=new InstanceofCONSTVisitor();
147 bdemsky 1.1.2.7 good=true;
148 bdemsky 1.1.2.7 invar=0;
149 bdemsky 1.1.2.7 index=0;
150 bdemsky 1.1.2.7 for (int i=0;i<q.operandsLength();i++) {
151 bdemsky 1.1.2.7 Temp t=tm.tempMap(q.operands(i));
152 bdemsky 1.1.2.7 if (inductions.containsKey(t)) {
153 bdemsky 1.1.2.7 index=i;
154 bdemsky 1.1.2.7 invar++;
155 bdemsky 1.1.2.7 }
156 bdemsky 1.1.2.7 else
157 bdemsky 1.1.2.7 if (!invariants.contains(ud.defMap(hc,t)[0])) {
158 bdemsky 1.1.2.7 good=false;
159 bdemsky 1.1.2.7 break;
160 bdemsky 1.1.2.7 }
161 bdemsky 1.1.2.7 }
162 bdemsky 1.1.2.7 //Need one induction variable and constants
163 bdemsky 1.1.2.7 if ((invar==1)&&(good)) {
164 bdemsky 1.1.2.7 changed=true;
165 bdemsky 1.1.2.7 //*****************
166 bdemsky 1.1.2.7 Induction tmp=new Induction((Induction)inductions.get(tm.tempMap(q.operands(index))));
167 bdemsky 1.1.2.7 for (int i=0;i<q.operandsLength();i++)
168 bdemsky 1.1.2.7 if (i!=index) {
169 bdemsky 1.1.2.7 Temp t=tm.tempMap(q.operands(i));
170 bdemsky 1.1.2.7 visitor.reset();
171 bdemsky 1.1.2.7 ((Quad)ud.defMap(hc,t)[0]).accept(visitor);
172 bdemsky 1.1.2.7 if (visitor.resetstatus())
173 bdemsky 1.1.2.7 tmp=tmp.multiply(
174 bdemsky 1.1.2.7 ((Integer)((CONST)ud.defMap(hc,t)[0]).value()).intValue());
175 bdemsky 1.1.2.7 else
176 bdemsky 1.1.2.7 tmp=tmp.multiply(tm.tempMap(q.operands(i)));
177 bdemsky 1.1.2.7 }
178 bdemsky 1.1.2.7 inductions.put(q.dst(),tmp);
179 bdemsky 1.1.2.7 } else
180 bdemsky 1.1.2.7 changed=false;
181 bdemsky 1.1.2.7 break;
182 bdemsky 1.1.2.7
183 bdemsky 1.1.2.7 case Qop.INEG:
184 bdemsky 1.1.2.7 //Unary operators
185 bdemsky 1.1.2.7
186 bdemsky 1.1.2.7 if (inductions.containsKey(tm.tempMap(q.operands(0)))) {
187 bdemsky 1.1.2.7 changed=true;
188 bdemsky 1.1.2.7 //****************
189 bdemsky 1.1.2.7 Induction tmp=((Induction)inductions.get(tm.tempMap(q.operands(0)))).negate();
190 bdemsky 1.1.2.7 inductions.put(q.dst(),tmp);
191 bdemsky 1.1.2.7 } else
192 bdemsky 1.1.2.7 changed=false;
193 bdemsky 1.1.2.7 break;
194 bdemsky 1.1.2.7 default:
195 bdemsky 1.1.2.7 }
196 bdemsky 1.1.2.1 }
197 bdemsky 1.1.2.7
198 bdemsky 1.1.2.1
199 bdemsky 1.1.2.1 public void visit(PAOFFSET q) {
200 bdemsky 1.1.2.1 //Find if induction variable
201 bdemsky 1.1.2.1 if (inductions.containsKey(tm.tempMap(q.index()))) {
202 bdemsky 1.1.2.1 changed=true;
203 bdemsky 1.1.2.1
204 bdemsky 1.1.2.1 Induction tmp=(Induction)inductions.get(tm.tempMap(q.index()));
205 cananian 1.3.2.1 assert tmp.pointerindex==false;
206 bdemsky 1.1.2.1
207 bdemsky 1.1.2.1 //*********
208 bdemsky 1.1.2.4 inductions.put(q.dst(), new Induction(tmp,q.arrayType()));
209 bdemsky 1.1.2.1
210 bdemsky 1.1.2.1 } else
211 bdemsky 1.1.2.1 changed=false;
212 bdemsky 1.1.2.1 }
213 bdemsky 1.1.2.1
214 bdemsky 1.1.2.1 public void visit(POPER q) {
215 bdemsky 1.1.2.1 switch (q.opcode()) {
216 bdemsky 1.1.2.1 case LQop.PADD:
217 bdemsky 1.1.2.1 //Binary operators
218 bdemsky 1.1.2.1 int invar=0;
219 bdemsky 1.1.2.1 int index=0;
220 bdemsky 1.1.2.1 boolean good=true;
221 bdemsky 1.1.2.1 for (int i=0;i<q.operandsLength();i++) {
222 bdemsky 1.1.2.1 Temp t=tm.tempMap(q.operands(i));
223 bdemsky 1.1.2.1 if (inductions.containsKey(t)) {
224 bdemsky 1.1.2.1 index=i;
225 bdemsky 1.1.2.1 invar++;
226 bdemsky 1.1.2.1 }
227 bdemsky 1.1.2.1 else
228 bdemsky 1.1.2.1 if (!invariants.contains(ud.defMap(hc,t)[0])) {
229 bdemsky 1.1.2.1 good=false;
230 bdemsky 1.1.2.1 break;
231 bdemsky 1.1.2.1 }
232 bdemsky 1.1.2.1 }
233 bdemsky 1.1.2.1 //Need one induction variable and invariants
234 bdemsky 1.1.2.1 if ((invar==1)&&(good)) {
235 bdemsky 1.1.2.1 changed=true;
236 bdemsky 1.1.2.1 //*****************
237 bdemsky 1.1.2.1 Induction tmp=new Induction((Induction)inductions.get(tm.tempMap(q.operands(index))));
238 bdemsky 1.1.2.1 for (int i=0;i<q.operandsLength();i++) {
239 bdemsky 1.1.2.1 if (i!=index)
240 bdemsky 1.1.2.4 tmp.padd(tm.tempMap(q.operands(i)));
241 bdemsky 1.1.2.1 }
242 bdemsky 1.1.2.1 inductions.put(q.dst(),tmp);
243 bdemsky 1.1.2.1 } else
244 bdemsky 1.1.2.1 changed=false;
245 bdemsky 1.1.2.1 break;
246 bdemsky 1.1.2.1
247 bdemsky 1.1.2.1
248 bdemsky 1.1.2.1 case Qop.IADD:
249 bdemsky 1.1.2.1 //Binary operators
250 bdemsky 1.1.2.1 InstanceofCONSTVisitor visitor=new InstanceofCONSTVisitor();
251 bdemsky 1.1.2.5 good=true;
252 bdemsky 1.1.2.1 invar=0;
253 bdemsky 1.1.2.1 index=0;
254 bdemsky 1.1.2.1 for (int i=0;i<q.operandsLength();i++) {
255 bdemsky 1.1.2.1 Temp t=tm.tempMap(q.operands(i));
256 bdemsky 1.1.2.1 if (inductions.containsKey(t)) {
257 bdemsky 1.1.2.1 index=i;
258 bdemsky 1.1.2.1 invar++;
259 bdemsky 1.1.2.1 }
260 bdemsky 1.1.2.5 else
261 bdemsky 1.1.2.5 if (!invariants.contains(ud.defMap(hc,t)[0])) {
262 bdemsky 1.1.2.5 good=false;
263 bdemsky 1.1.2.5 break;
264 bdemsky 1.1.2.5 }
265 bdemsky 1.1.2.1 }
266 bdemsky 1.1.2.1 //Need one induction variable and constants
267 bdemsky 1.1.2.5 if ((invar==1)&&(good)) {
268 bdemsky 1.1.2.1 changed=true;
269 bdemsky 1.1.2.1 //*****************
270 bdemsky 1.1.2.1 Induction tmp=new Induction((Induction)inductions.get(tm.tempMap(q.operands(index))));
271 bdemsky 1.1.2.1 for (int i=0;i<q.operandsLength();i++)
272 bdemsky 1.1.2.4 if (i!=index) {
273 bdemsky 1.1.2.4 Temp t=tm.tempMap(q.operands(i));
274 bdemsky 1.1.2.4 visitor.reset();
275 cananian 1.1.2.6 ((Quad)ud.defMap(hc,t)[0]).accept(visitor);
276 bdemsky 1.1.2.4 if (visitor.resetstatus())
277 bdemsky 1.1.2.4 tmp=tmp.add
278 bdemsky 1.1.2.4 (((Integer)(((CONST)ud.defMap(hc,t)[0]).value())).intValue());
279 bdemsky 1.1.2.4 else
280 bdemsky 1.1.2.4 tmp=tmp.add(tm.tempMap(q.operands(i)));
281 bdemsky 1.1.2.4 }
282 bdemsky 1.1.2.1 inductions.put(q.dst(),tmp);
283 bdemsky 1.1.2.1 } else
284 bdemsky 1.1.2.1 changed=false;
285 bdemsky 1.1.2.1 break;
286 bdemsky 1.1.2.1
287 bdemsky 1.1.2.1
288 bdemsky 1.1.2.1
289 bdemsky 1.1.2.1 case Qop.IMUL:
290 bdemsky 1.1.2.1 //Binary operators
291 bdemsky 1.1.2.1 visitor=new InstanceofCONSTVisitor();
292 bdemsky 1.1.2.5 good=true;
293 bdemsky 1.1.2.1 invar=0;
294 bdemsky 1.1.2.1 index=0;
295 bdemsky 1.1.2.1 for (int i=0;i<q.operandsLength();i++) {
296 bdemsky 1.1.2.1 Temp t=tm.tempMap(q.operands(i));
297 bdemsky 1.1.2.1 if (inductions.containsKey(t)) {
298 bdemsky 1.1.2.1 index=i;
299 bdemsky 1.1.2.1 invar++;
300 bdemsky 1.1.2.1 }
301 bdemsky 1.1.2.5 else
302 bdemsky 1.1.2.5 if (!invariants.contains(ud.defMap(hc,t)[0])) {
303 bdemsky 1.1.2.5 good=false;
304 bdemsky 1.1.2.5 break;
305 bdemsky 1.1.2.5 }
306 bdemsky 1.1.2.1 }
307 bdemsky 1.1.2.1 //Need one induction variable and constants
308 bdemsky 1.1.2.5 if ((invar==1)&&(good)) {
309 bdemsky 1.1.2.1 changed=true;
310 bdemsky 1.1.2.1 //*****************
311 bdemsky 1.1.2.1 Induction tmp=new Induction((Induction)inductions.get(tm.tempMap(q.operands(index))));
312 bdemsky 1.1.2.1 for (int i=0;i<q.operandsLength();i++)
313 bdemsky 1.1.2.1 if (i!=index) {
314 bdemsky 1.1.2.4 Temp t=tm.tempMap(q.operands(i));
315 bdemsky 1.1.2.4 visitor.reset();
316 cananian 1.1.2.6 ((Quad)ud.defMap(hc,t)[0]).accept(visitor);
317 bdemsky 1.1.2.4 if (visitor.resetstatus())
318 bdemsky 1.1.2.4 tmp=tmp.multiply(
319 bdemsky 1.1.2.4 ((Integer)((CONST)ud.defMap(hc,t)[0]).value()).intValue());
320 bdemsky 1.1.2.4 else
321 bdemsky 1.1.2.4 tmp=tmp.multiply(tm.tempMap(q.operands(i)));
322 bdemsky 1.1.2.1 }
323 bdemsky 1.1.2.1 inductions.put(q.dst(),tmp);
324 bdemsky 1.1.2.1 } else
325 bdemsky 1.1.2.1 changed=false;
326 bdemsky 1.1.2.1 break;
327 bdemsky 1.1.2.1
328 bdemsky 1.1.2.1 case Qop.INEG:
329 bdemsky 1.1.2.1 case LQop.PNEG:
330 bdemsky 1.1.2.1 //Unary operators
331 bdemsky 1.1.2.1
332 bdemsky 1.1.2.1 if (inductions.containsKey(tm.tempMap(q.operands(0)))) {
333 bdemsky 1.1.2.1 changed=true;
334 bdemsky 1.1.2.1 //****************
335 bdemsky 1.1.2.4 Induction tmp=((Induction)inductions.get(tm.tempMap(q.operands(0)))).negate();
336 bdemsky 1.1.2.1 inductions.put(q.dst(),tmp);
337 bdemsky 1.1.2.1 } else
338 bdemsky 1.1.2.1 changed=false;
339 bdemsky 1.1.2.1 break;
340 bdemsky 1.1.2.1 default:
341 bdemsky 1.1.2.1 }
342 bdemsky 1.1.2.1 }
343 bdemsky 1.1.2.1 }
344 bdemsky 1.1.2.2
345 bdemsky 1.1.2.2 /** InstanceofCONSTVisitor allows <code>CompleteVisitor</code> to do its
346 bdemsky 1.1.2.2 * work without using an INSTANCEOF. */
347 bdemsky 1.1.2.1
348 bdemsky 1.1.2.1 class InstanceofCONSTVisitor extends LowQuadVisitor {
349 bdemsky 1.1.2.1 boolean reset;
350 bdemsky 1.1.2.1 public InstanceofCONSTVisitor() {
351 bdemsky 1.1.2.1 reset=true;
352 bdemsky 1.1.2.1 }
353 bdemsky 1.1.2.1
354 bdemsky 1.1.2.1 public boolean resetstatus() {
355 bdemsky 1.1.2.1 return reset;
356 bdemsky 1.1.2.1 }
357 bdemsky 1.1.2.1
358 bdemsky 1.1.2.1 public void reset() {
359 bdemsky 1.1.2.1 reset=true;
360 bdemsky 1.1.2.1 }
361 bdemsky 1.1.2.1
362 bdemsky 1.1.2.1 public void visit(Quad q) {
363 bdemsky 1.1.2.1 reset=false;
364 bdemsky 1.1.2.1 }
365 bdemsky 1.1.2.1
366 bdemsky 1.1.2.1 public void visit(CONST q) {
367 bdemsky 1.1.2.1 }
368 bdemsky 1.1.2.1 }
369 cananian 1.2 }