1 bdemsky 1.1.2.1 // LoopAnalysis.java, created Thu Jun 24 11:45:07 1998 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 bdemsky 1.1.2.1 import harpoon.Analysis.UseDef;
7 bdemsky 1.1.2.1 import harpoon.Analysis.Loops.LoopFinder;
8 cananian 1.5 import net.cscott.jutil.WorkSet;
9 bdemsky 1.1.2.16 import harpoon.ClassFile.HCodeElement;
10 bdemsky 1.1.2.16 import harpoon.ClassFile.HCode;
11 bdemsky 1.1.2.16 import harpoon.IR.Quads.AGET;
12 bdemsky 1.1.2.16 import harpoon.IR.Quads.ALENGTH;
13 bdemsky 1.1.2.16 import harpoon.IR.Quads.ANEW;
14 bdemsky 1.1.2.16 import harpoon.IR.Quads.ARRAYINIT;
15 bdemsky 1.1.2.16 import harpoon.IR.Quads.ASET;
16 bdemsky 1.1.2.16 import harpoon.IR.Quads.CALL;
17 bdemsky 1.1.2.16 import harpoon.IR.Quads.CJMP;
18 bdemsky 1.1.2.16 import harpoon.IR.Quads.COMPONENTOF;
19 bdemsky 1.1.2.16 import harpoon.IR.Quads.CONST;
20 bdemsky 1.1.2.16 import harpoon.IR.Quads.GET;
21 bdemsky 1.1.2.16 import harpoon.IR.Quads.INSTANCEOF;
22 bdemsky 1.1.2.16 import harpoon.IR.Quads.MONITORENTER;
23 bdemsky 1.1.2.16 import harpoon.IR.Quads.MONITOREXIT;
24 bdemsky 1.1.2.16 import harpoon.IR.Quads.MOVE;
25 bdemsky 1.1.2.16 import harpoon.IR.Quads.NEW;
26 bdemsky 1.1.2.16 import harpoon.IR.Quads.Quad;
27 bdemsky 1.1.2.16 import harpoon.IR.Quads.Qop;
28 bdemsky 1.1.2.16 import harpoon.IR.Quads.RETURN;
29 bdemsky 1.1.2.16 import harpoon.IR.Quads.SET;
30 bdemsky 1.1.2.18 import harpoon.IR.Quads.SIGMA;
31 bdemsky 1.1.2.16 import harpoon.IR.Quads.THROW;
32 bdemsky 1.1.2.16 import harpoon.IR.Quads.TYPECAST;
33 bdemsky 1.1.2.16 import harpoon.IR.Quads.OPER;
34 bdemsky 1.1.2.16 import harpoon.IR.Quads.PHI;
35 bdemsky 1.1.2.18 import harpoon.IR.Quads.QuadKind;
36 bdemsky 1.1.2.16 import harpoon.IR.LowQuad.LowQuadVisitor;
37 bdemsky 1.1.2.16 import harpoon.IR.LowQuad.POPER;
38 bdemsky 1.1.2.16 import harpoon.IR.LowQuad.PCALL;
39 bdemsky 1.1.2.16 import harpoon.IR.LowQuad.PGET;
40 bdemsky 1.1.2.16 import harpoon.IR.LowQuad.PSET;
41 bdemsky 1.1.2.16 import harpoon.IR.LowQuad.PARRAY;
42 bdemsky 1.1.2.16 import harpoon.IR.LowQuad.PFIELD;
43 bdemsky 1.1.2.16 import harpoon.IR.LowQuad.PMETHOD;
44 bdemsky 1.1.2.16 import harpoon.IR.LowQuad.PCONST;
45 bdemsky 1.1.2.16 import harpoon.IR.LowQuad.PAOFFSET;
46 bdemsky 1.1.2.16 import harpoon.IR.LowQuad.PFOFFSET;
47 bdemsky 1.1.2.16 import harpoon.IR.LowQuad.PMOFFSET;
48 bdemsky 1.1.2.16 import harpoon.IR.LowQuad.PFCONST;
49 bdemsky 1.1.2.16 import harpoon.IR.LowQuad.PMCONST;
50 bdemsky 1.1.2.18 import harpoon.IR.LowQuad.LowQuadKind;
51 bdemsky 1.1.2.16 import harpoon.Analysis.Loops.LoopFinder;
52 bdemsky 1.1.2.16 import harpoon.Analysis.Loops.Loops;
53 bdemsky 1.1.2.1 import harpoon.Temp.Temp;
54 bdemsky 1.1.2.1 import harpoon.Temp.TempMap;
55 cananian 1.1.2.20 import harpoon.IR.Properties.CFGraphable;
56 bdemsky 1.1.2.2 import harpoon.Analysis.LowQuad.Loop.AllInductions;
57 bdemsky 1.1.2.4 import harpoon.Analysis.LowQuad.Loop.BasicInductions;
58 bdemsky 1.1.2.2 import harpoon.Analysis.LowQuad.Loop.LoopInvariance;
59 bdemsky 1.1.2.5 import harpoon.Analysis.Maps.AllInductionsMap;
60 bdemsky 1.1.2.5 import harpoon.Analysis.Maps.BasicInductionsMap;
61 bdemsky 1.1.2.5 import harpoon.Analysis.Maps.InvariantsMap;
62 bdemsky 1.1.2.12 import harpoon.Util.Util;
63 bdemsky 1.1.2.2
64 bdemsky 1.1.2.2 import java.util.HashMap;
65 bdemsky 1.1.2.9 import java.util.Map;
66 bdemsky 1.1.2.2 import java.util.ArrayList;
67 bdemsky 1.1.2.1 import java.util.Set;
68 bdemsky 1.1.2.1 import java.util.Iterator;
69 bdemsky 1.1.2.5
70 bdemsky 1.1.2.1 /**
71 bdemsky 1.1.2.5 * <code>LoopAnalysis</code> implements <code>AllInductionsMap</code>,
72 bdemsky 1.1.2.5 * <code>BasicInductionsMap</code>, and <code>InvariantsMap</code>.
73 bdemsky 1.1.2.1 *
74 cananian 1.1.2.23 * @author Brian Demsky <bdemsky@mit.edu>
75 cananian 1.5 * @version $Id: LoopAnalysis.java,v 1.5 2004/02/08 01:52:54 cananian Exp $
76 bdemsky 1.1.2.1 */
77 bdemsky 1.1.2.1
78 bdemsky 1.1.2.5 public class LoopAnalysis implements AllInductionsMap, BasicInductionsMap, InvariantsMap {
79 bdemsky 1.1.2.1
80 bdemsky 1.1.2.5 HCode lasthc;
81 bdemsky 1.1.2.1 TempMap tm;
82 bdemsky 1.1.2.5 HashMap aimap, bimap, invmap;
83 bdemsky 1.1.2.5 LoopFinder rtloop;
84 bdemsky 1.1.2.12 UseDef ud;
85 bdemsky 1.1.2.1
86 bdemsky 1.1.2.11 /** Creates a <code>LoopAnalysis</code>. Takes in a TempMap
87 bdemsky 1.1.2.11 that for SSI forms needs to map SSI->SSA.*/
88 bdemsky 1.1.2.1 public LoopAnalysis(TempMap tm) {
89 bdemsky 1.1.2.1 this.tm=tm;
90 bdemsky 1.1.2.12 this.ud=new UseDef();
91 bdemsky 1.1.2.1 }
92 bdemsky 1.1.2.1
93 bdemsky 1.1.2.1 /*-----------------------------*/
94 bdemsky 1.1.2.1 // Class state.
95 bdemsky 1.1.2.1
96 bdemsky 1.1.2.1 /*---------------------------*/
97 bdemsky 1.1.2.1 // public information accessor methods.
98 bdemsky 1.1.2.1
99 bdemsky 1.1.2.5 public Loops rootloop(HCode hc) {
100 bdemsky 1.1.2.5 analyze(hc);
101 bdemsky 1.1.2.5 return rtloop;
102 bdemsky 1.1.2.5 }
103 bdemsky 1.1.2.5
104 bdemsky 1.1.2.9 public Map allInductionsMap(HCode hc, Loops lp) {
105 bdemsky 1.1.2.5 analyze(hc);
106 bdemsky 1.1.2.8 return (HashMap) aimap.get(lp.loopEntrances().toArray()[0]);
107 bdemsky 1.1.2.5 }
108 bdemsky 1.1.2.5
109 bdemsky 1.1.2.9 public Map basicInductionsMap(HCode hc, Loops lp) {
110 bdemsky 1.1.2.5 analyze(hc);
111 bdemsky 1.1.2.8 return (HashMap) bimap.get(lp.loopEntrances().toArray()[0]);
112 bdemsky 1.1.2.5 }
113 bdemsky 1.1.2.5
114 bdemsky 1.1.2.5 public Set invariantsMap(HCode hc, Loops lp) {
115 bdemsky 1.1.2.1 analyze(hc);
116 bdemsky 1.1.2.7 return (Set) invmap.get(lp.loopEntrances().toArray()[0]);
117 bdemsky 1.1.2.1 }
118 bdemsky 1.1.2.1
119 bdemsky 1.1.2.12
120 bdemsky 1.1.2.12 /** <code>initialTemp</code> takes in a <code>Temp</code> t that needs to be a basic
121 bdemsky 1.1.2.12 * induction variable, a <code>Loops</code> that is the loop that t is an
122 bdemsky 1.1.2.12 * induction variable in and returns a <code>Temp</code> with its initial value. */
123 bdemsky 1.1.2.12
124 bdemsky 1.1.2.12 Temp initialTemp(HCode hc, Temp t, Loops lp) {
125 cananian 1.1.2.22 Set loopelements=lp.loopIncElements();
126 cananian 1.3.2.1 assert lp.loopEntrances().size()==1 : "Loop must have one entrance";
127 bdemsky 1.1.2.12 PHI q=(PHI)(lp.loopEntrances()).toArray()[0];
128 bdemsky 1.1.2.12
129 bdemsky 1.1.2.12 int j=0;
130 bdemsky 1.1.2.12 for (;j<q.numPhis();j++) {
131 bdemsky 1.1.2.12 if (q.dst(j)==t) break;
132 bdemsky 1.1.2.12 }
133 bdemsky 1.1.2.12 Temp[] uses=q.src(j);
134 cananian 1.3.2.1 assert uses.length==2;
135 bdemsky 1.1.2.12 Temp initial=null;
136 bdemsky 1.1.2.12 for(int i=0;i<uses.length;i++) {
137 bdemsky 1.1.2.12 HCodeElement[] sources=ud.defMap(hc,tm.tempMap(uses[i]));
138 cananian 1.3.2.1 assert sources.length==1;
139 bdemsky 1.1.2.12 if (!loopelements.contains(sources[0])) {
140 bdemsky 1.1.2.12 initial=uses[i];
141 bdemsky 1.1.2.12 break;
142 bdemsky 1.1.2.12 }
143 bdemsky 1.1.2.12 }
144 bdemsky 1.1.2.12 return initial;
145 bdemsky 1.1.2.12 }
146 bdemsky 1.1.2.12
147 bdemsky 1.1.2.12 /** <code>findIncrement</code> finds out how much the basic induction variable is
148 bdemsky 1.1.2.12 * incremented by.*/
149 bdemsky 1.1.2.12
150 bdemsky 1.1.2.12 Temp findIncrement(HCode hc, Temp t, Loops lp) {
151 cananian 1.1.2.22 Set loopelements=lp.loopIncElements();
152 cananian 1.3.2.1 assert lp.loopEntrances().size()==1 : "Loop must have one entrance";
153 bdemsky 1.1.2.12 PHI oheader=(PHI)(lp.loopEntrances()).toArray()[0];
154 bdemsky 1.1.2.12 Quad q=addQuad(hc, oheader, t,loopelements);
155 bdemsky 1.1.2.12 HCodeElement []source=ud.defMap(hc,tm.tempMap(t));
156 cananian 1.3.2.1 assert source.length==1;
157 bdemsky 1.1.2.12 PHI qq=(PHI)source[0];
158 bdemsky 1.1.2.12 Temp[] uses=q.use();
159 bdemsky 1.1.2.12 Temp result=null;
160 bdemsky 1.1.2.12
161 bdemsky 1.1.2.12 for (int i=0;i<uses.length;i++) {
162 bdemsky 1.1.2.12 HCodeElement []sources=ud.defMap(hc,tm.tempMap(uses[i]));
163 cananian 1.3.2.1 assert sources.length==1;
164 bdemsky 1.1.2.12 if (sources[0]!=qq) {
165 bdemsky 1.1.2.12 result=uses[i];
166 bdemsky 1.1.2.12 break;
167 bdemsky 1.1.2.12 }
168 bdemsky 1.1.2.12 }
169 bdemsky 1.1.2.12 return result;
170 bdemsky 1.1.2.12 }
171 bdemsky 1.1.2.12
172 bdemsky 1.1.2.12 /** <code>addQuad</code> takes in a <code>Temp</code> t that needs to be a basic
173 bdemsky 1.1.2.12 * induction variable, and returns the <code>Quad</code> that does the adding. */
174 bdemsky 1.1.2.12
175 bdemsky 1.1.2.12 Quad addQuad(HCode hc, PHI q,Temp t, Set loopelements) {
176 bdemsky 1.1.2.12 int j=0;
177 bdemsky 1.1.2.12 for (;j<q.numPhis();j++) {
178 bdemsky 1.1.2.12 if (q.dst(j)==t) break;
179 bdemsky 1.1.2.12 }
180 bdemsky 1.1.2.12 Temp[] uses=q.src(j);
181 cananian 1.3.2.1 assert uses.length==2;
182 bdemsky 1.1.2.12 Temp initial=null;
183 bdemsky 1.1.2.12 for(int i=0;i<uses.length;i++) {
184 bdemsky 1.1.2.12 HCodeElement[] sources=ud.defMap(hc,tm.tempMap(uses[i]));
185 cananian 1.3.2.1 assert sources.length==1;
186 bdemsky 1.1.2.12 if (loopelements.contains(sources[0])) {
187 bdemsky 1.1.2.12 initial=uses[i];
188 bdemsky 1.1.2.12 break;
189 bdemsky 1.1.2.12 }
190 bdemsky 1.1.2.12 }
191 bdemsky 1.1.2.12 HCodeElement[] sources=ud.defMap(hc,tm.tempMap(initial));
192 cananian 1.3.2.1 assert sources.length==1;
193 bdemsky 1.1.2.12 return (Quad)sources[0];
194 bdemsky 1.1.2.12 }
195 bdemsky 1.1.2.5
196 bdemsky 1.1.2.1 /*---------------------------*/
197 bdemsky 1.1.2.1 // Analysis code.
198 bdemsky 1.1.2.1
199 bdemsky 1.1.2.1 /** Set of analyzed methods. */
200 bdemsky 1.1.2.1
201 bdemsky 1.1.2.1 /** Main analysis method. */
202 bdemsky 1.1.2.1 void analyze(HCode hc) {
203 bdemsky 1.1.2.5 if (lasthc!=hc) {
204 bdemsky 1.1.2.5 invmap=new HashMap();
205 bdemsky 1.1.2.5 aimap=new HashMap();
206 bdemsky 1.1.2.5 bimap=new HashMap();
207 bdemsky 1.1.2.5 lasthc=hc;
208 bdemsky 1.1.2.5 rtloop=new LoopFinder(hc);
209 bdemsky 1.1.2.5 analyzetree(hc,rtloop,"");
210 bdemsky 1.1.2.5 }
211 bdemsky 1.1.2.1 } // end analysis.
212 bdemsky 1.1.2.1
213 bdemsky 1.1.2.5 void analyzetree(HCode hc, Loops lp, String st) {
214 bdemsky 1.1.2.1 WorkSet kids=(WorkSet)lp.nestedLoops();
215 bdemsky 1.1.2.1 Iterator iterate=kids.iterator();
216 bdemsky 1.1.2.5
217 bdemsky 1.1.2.1 while (iterate.hasNext()) {
218 bdemsky 1.1.2.5 analyzetree(hc, (Loops)iterate.next(),st+" ");
219 bdemsky 1.1.2.1 }
220 bdemsky 1.1.2.5
221 bdemsky 1.1.2.27 /* throw assertion if loop has no entrance (root loop) */
222 cananian 1.3.2.1 assert !lp.loopEntrances().isEmpty();
223 bdemsky 1.1.2.27
224 ovy 1.1.2.26
225 bdemsky 1.1.2.1 //Find loop invariants
226 cananian 1.1.2.22 WorkSet elements=(WorkSet)lp.loopIncElements();
227 bdemsky 1.1.2.2 LoopInvariance invar=new LoopInvariance(tm,hc);
228 bdemsky 1.1.2.2 WorkSet invariants=invar.invariants(elements);
229 bdemsky 1.1.2.1
230 bdemsky 1.1.2.1 //Find basic induction variables
231 bdemsky 1.1.2.5
232 bdemsky 1.1.2.4 BasicInductions binductor=new BasicInductions(tm,hc);
233 bdemsky 1.1.2.6 HashMap basicinductions=binductor.doInduction(lp,invariants);
234 bdemsky 1.1.2.1
235 bdemsky 1.1.2.5
236 bdemsky 1.1.2.5 //Find all induction variables
237 bdemsky 1.1.2.2 AllInductions ainductor=new AllInductions(tm,hc);
238 bdemsky 1.1.2.5 HashMap allInductions=ainductor.doAllInductions(lp, invariants, basicinductions);
239 bdemsky 1.1.2.1
240 bdemsky 1.1.2.5 //Add to our maps
241 bdemsky 1.1.2.7 aimap.put(lp.loopEntrances().toArray()[0], allInductions);
242 bdemsky 1.1.2.7 bimap.put(lp.loopEntrances().toArray()[0], basicinductions);
243 bdemsky 1.1.2.7 invmap.put(lp.loopEntrances().toArray()[0], invariants);
244 bdemsky 1.1.2.1
245 bdemsky 1.1.2.1
246 bdemsky 1.1.2.5 //Show the user everything
247 bdemsky 1.1.2.10 //iterate=invariants.iterator();
248 bdemsky 1.1.2.10 //System.out.println(st+"Invariants:");
249 bdemsky 1.1.2.10 //while (iterate.hasNext()) {
250 bdemsky 1.1.2.10 // System.out.println(st+((Quad)iterate.next()).toString());
251 bdemsky 1.1.2.10 //}
252 bdemsky 1.1.2.10 //iterate=elements.iterator();
253 bdemsky 1.1.2.10 //System.out.println(st+"Noninvariants:");
254 bdemsky 1.1.2.10 //while (iterate.hasNext()) {
255 bdemsky 1.1.2.10 // System.out.println(st+((Quad)iterate.next()).toString());
256 bdemsky 1.1.2.10 //}
257 bdemsky 1.1.2.10 //iterate=(basicinductions.keySet()).iterator();
258 bdemsky 1.1.2.10
259 bdemsky 1.1.2.10 //System.out.println(st+"Basic induction variables:");
260 bdemsky 1.1.2.10 //while (iterate.hasNext()) {
261 bdemsky 1.1.2.10 // Temp tmp=(Temp) iterate.next();
262 bdemsky 1.1.2.10 // System.out.println(st+tmp.toString());
263 bdemsky 1.1.2.10 // System.out.println(st+((Induction)basicinductions.get(tmp)).toString());
264 bdemsky 1.1.2.10 //}
265 bdemsky 1.1.2.10 //iterate=(allInductions.keySet()).iterator();
266 bdemsky 1.1.2.10
267 bdemsky 1.1.2.10 //System.out.println(st+"All induction variables:");
268 bdemsky 1.1.2.10 //while (iterate.hasNext()) {
269 bdemsky 1.1.2.10 // Temp tmp=(Temp) iterate.next();
270 bdemsky 1.1.2.10 // System.out.println(st+tmp.toString());
271 bdemsky 1.1.2.10 // System.out.println(st+((Induction)allInductions.get(tmp)).toString());
272 bdemsky 1.1.2.10 //}
273 bdemsky 1.1.2.13 }
274 bdemsky 1.1.2.13
275 bdemsky 1.1.2.13 /** <code>doLooptest</code> moves test conditions from original induction variables
276 bdemsky 1.1.2.13 * to new ones whenever possible.*/
277 bdemsky 1.1.2.13
278 bdemsky 1.1.2.13 Set doLooptest(HCode hc, Loops lp) {
279 bdemsky 1.1.2.13 //Make sure we have done analysis
280 bdemsky 1.1.2.13 analyze(hc);
281 bdemsky 1.1.2.13 //Create the set of loop elements
282 cananian 1.1.2.22 Set elements=lp.loopIncElements();
283 bdemsky 1.1.2.13 WorkSet tests=new WorkSet();
284 bdemsky 1.1.2.13 //Iterate through this set
285 bdemsky 1.1.2.13 Iterator iterate=elements.iterator();
286 bdemsky 1.1.2.13
287 bdemsky 1.1.2.13 //create sets of loop invariants and map of induction variables
288 bdemsky 1.1.2.13 //to pass to the visitor
289 bdemsky 1.1.2.13 Set loopinvars=(Set)invmap.get(lp.loopEntrances().toArray()[0]);
290 bdemsky 1.1.2.13 Map allinductions=(Map)aimap.get(lp.loopEntrances().toArray()[0]);
291 bdemsky 1.1.2.13
292 bdemsky 1.1.2.13 TestVisitor visitor=new TestVisitor(loopinvars, allinductions, tm,hc, lp, tests);
293 bdemsky 1.1.2.13 //visit the nodes
294 bdemsky 1.1.2.13 while (iterate.hasNext()) {
295 bdemsky 1.1.2.13 Quad q=(Quad) iterate.next();
296 bdemsky 1.1.2.13 q.accept(visitor);
297 bdemsky 1.1.2.13 }
298 bdemsky 1.1.2.13 return tests;
299 bdemsky 1.1.2.13 }
300 bdemsky 1.1.2.13
301 bdemsky 1.1.2.13
302 bdemsky 1.1.2.13 /**<code>TestVisitor</code> does all the magic for changing test conditions.*/
303 bdemsky 1.1.2.13
304 bdemsky 1.1.2.13 class TestVisitor extends LowQuadVisitor {
305 bdemsky 1.1.2.13 Set inductvars;
306 bdemsky 1.1.2.13 Set loopinvars;
307 bdemsky 1.1.2.13 Map allinductions;
308 bdemsky 1.1.2.13 TempMap ssitossamap;
309 bdemsky 1.1.2.13 Loops lp;
310 bdemsky 1.1.2.13 HCode hc;
311 bdemsky 1.1.2.13 Set tests;
312 bdemsky 1.1.2.13
313 bdemsky 1.1.2.13 //Create TestVisitor, and inform it of everything.
314 bdemsky 1.1.2.13 TestVisitor(Set loopinvars, Map allinductions, TempMap ssitossamap, HCode hc, Loops lp, Set tests) {
315 bdemsky 1.1.2.13 this.loopinvars=loopinvars;
316 bdemsky 1.1.2.13 this.allinductions=allinductions;
317 bdemsky 1.1.2.13 this.inductvars=allinductions.keySet();
318 bdemsky 1.1.2.13 this.ssitossamap=ssitossamap;
319 bdemsky 1.1.2.13 this.hc=hc;
320 bdemsky 1.1.2.13 this.lp=lp;
321 bdemsky 1.1.2.13 this.tests=tests;
322 bdemsky 1.1.2.13 }
323 bdemsky 1.1.2.13
324 bdemsky 1.1.2.13 //Default method...do nothing
325 bdemsky 1.1.2.13 public void visit(Quad q) {/* Do nothing*/}
326 bdemsky 1.1.2.13
327 bdemsky 1.1.2.13 //POPER visitor
328 bdemsky 1.1.2.13 //Only look at ICMPEQ, and ICMPGT
329 bdemsky 1.1.2.13 public void visit(harpoon.IR.Quads.AGET q) {}
330 bdemsky 1.1.2.13
331 bdemsky 1.1.2.13 public void visit(harpoon.IR.Quads.ASET q) {}
332 bdemsky 1.1.2.13
333 bdemsky 1.1.2.13 public void visit(harpoon.IR.Quads.CALL q) {}
334 bdemsky 1.1.2.13
335 bdemsky 1.1.2.13 public void visit(harpoon.IR.Quads.GET q) {}
336 bdemsky 1.1.2.13
337 bdemsky 1.1.2.13 // Lets let this error go through...shouldn't see any HANDLERS
338 bdemsky 1.1.2.13 // in a loop.
339 bdemsky 1.1.2.13 // public void visit(harpoon.IR.Quads.HANDLER q) {}
340 bdemsky 1.1.2.13
341 bdemsky 1.1.2.13 public void visit(harpoon.IR.Quads.SET q) {}
342 bdemsky 1.1.2.13
343 bdemsky 1.1.2.13 public void visit(POPER q) {
344 bdemsky 1.1.2.13 switch (q.opcode()) {
345 bdemsky 1.1.2.13 case Qop.ICMPEQ:
346 bdemsky 1.1.2.13 case Qop.ICMPGT:
347 bdemsky 1.1.2.17 case Qop.LCMPEQ:
348 bdemsky 1.1.2.17 case Qop.LCMPGT:
349 bdemsky 1.1.2.13 //look at the POPER
350 bdemsky 1.1.2.13 //return new POPER if we can do stuff
351 bdemsky 1.1.2.13 if (lookat(q)) tests.add(q);
352 bdemsky 1.1.2.13 break;
353 bdemsky 1.1.2.13 default:
354 bdemsky 1.1.2.13 }
355 bdemsky 1.1.2.13 }
356 bdemsky 1.1.2.13
357 bdemsky 1.1.2.13 public void visit(OPER q) {
358 bdemsky 1.1.2.13 switch (q.opcode()) {
359 bdemsky 1.1.2.13 case Qop.ICMPEQ:
360 bdemsky 1.1.2.13 case Qop.ICMPGT:
361 bdemsky 1.1.2.17 case Qop.LCMPEQ:
362 bdemsky 1.1.2.17 case Qop.LCMPGT:
363 bdemsky 1.1.2.13 //look at the OPER
364 bdemsky 1.1.2.13 //return new OPER if we can do stuff
365 bdemsky 1.1.2.13 if (lookat(q)) tests.add(q);
366 bdemsky 1.1.2.13 break;
367 bdemsky 1.1.2.13 default:
368 bdemsky 1.1.2.13 }
369 bdemsky 1.1.2.13 }
370 bdemsky 1.1.2.13
371 bdemsky 1.1.2.13 /**<code>lookat</code> examines a test condition.*/
372 bdemsky 1.1.2.13 boolean lookat(OPER q) {
373 bdemsky 1.1.2.13 Temp[] operands=q.operands();
374 cananian 1.3.2.1 assert operands.length==2;
375 bdemsky 1.1.2.13 boolean good=true;
376 bdemsky 1.1.2.13 int flag=-1;
377 bdemsky 1.1.2.13 POPER newpoper=null;
378 ovy 1.1.2.26 Set loopIncElements = lp.loopIncElements();
379 bdemsky 1.1.2.13
380 bdemsky 1.1.2.13 //Loop through the operands
381 bdemsky 1.1.2.13 //we need one induction variable
382 bdemsky 1.1.2.13 //and one loop invariant
383 bdemsky 1.1.2.13
384 bdemsky 1.1.2.13 for (int i=0;i<operands.length;i++) {
385 bdemsky 1.1.2.13 if (inductvars.contains(ssitossamap.tempMap(operands[i]))) {
386 bdemsky 1.1.2.13 if (flag==-1)
387 bdemsky 1.1.2.13 flag=i;
388 bdemsky 1.1.2.13 else
389 bdemsky 1.1.2.13 good=false;
390 bdemsky 1.1.2.13 }
391 bdemsky 1.1.2.13 else {
392 bdemsky 1.1.2.13 HCodeElement[] sources=ud.defMap(hc,ssitossamap.tempMap(operands[i]));
393 cananian 1.3.2.1 assert sources.length==1;
394 ovy 1.1.2.26 /* good only if defined in invariant or outside the loop */
395 ovy 1.1.2.26 if (!loopinvars.contains(sources[0]) &&
396 ovy 1.1.2.26 loopIncElements.contains(sources[0]))
397 bdemsky 1.1.2.13 good=false;
398 bdemsky 1.1.2.13 }
399 bdemsky 1.1.2.13 }
400 bdemsky 1.1.2.13 return (good&&(flag!=-1));
401 bdemsky 1.1.2.13 }
402 bdemsky 1.1.2.1 }
403 bdemsky 1.1.2.19 /**<code>forloop</code> takes in an <code>HCode</code> and
404 bdemsky 1.1.2.19 * <code>Loops</code> to analyze. It returns a null if there is
405 bdemsky 1.1.2.19 * no for loop, or a <code>ForLoopInfo</code> if it finds a for loop.
406 bdemsky 1.1.2.19 * It works on Quads and LowQuads on both SSI and SSA forms.*/
407 bdemsky 1.1.2.14
408 bdemsky 1.1.2.17 public ForLoopInfo forloop(HCode hc, Loops lp) {
409 bdemsky 1.1.2.14 analyze(hc);
410 cananian 1.3.2.1 assert lp.loopEntrances().size()==1 : "Loop must have one entrance";
411 bdemsky 1.1.2.14 Quad header=(Quad)(lp.loopEntrances()).toArray()[0];;
412 bdemsky 1.1.2.14 Set testsopers=doLooptest(hc,lp);
413 bdemsky 1.1.2.15 ForLoopVisitor flv=new ForLoopVisitor(testsopers, hc, ud, lp, tm);
414 bdemsky 1.1.2.15 for (Quad ptr=header.next(0);!(flv.sideEffects()||flv.done());ptr=ptr.next(0)) {
415 bdemsky 1.1.2.15 ptr.accept(flv);
416 bdemsky 1.1.2.15 }
417 bdemsky 1.1.2.15 if (flv.forLoop()) {
418 bdemsky 1.1.2.17 ForLoopInfo retval=null;
419 bdemsky 1.1.2.17 OPER test=flv.testCondition();
420 bdemsky 1.1.2.17 CJMP cjmp=flv.cjmpExit();
421 bdemsky 1.1.2.17 Temp ivar=flv.inductionVar();
422 bdemsky 1.1.2.17 Temp increment=findIncrement(hc, ivar, lp);
423 bdemsky 1.1.2.17 int bindex=flv.bindex();
424 bdemsky 1.1.2.17 int cjmpedge=flv.cjmpedge();
425 bdemsky 1.1.2.17 switch (test.opcode()) {
426 bdemsky 1.1.2.17 case Qop.LCMPEQ:
427 bdemsky 1.1.2.17 case Qop.ICMPEQ:
428 bdemsky 1.1.2.17 if (cjmpedge==1)
429 bdemsky 1.1.2.17 retval=new ForLoopInfo(ForLoopInfo.NEQ,ivar,increment,
430 bdemsky 1.1.2.17 initialTemp(hc, ivar, lp),
431 bdemsky 1.1.2.17 test.operands(1-bindex),test,cjmp);
432 bdemsky 1.1.2.17 break;
433 bdemsky 1.1.2.17 case Qop.LCMPGT:
434 bdemsky 1.1.2.17 case Qop.ICMPGT:
435 bdemsky 1.1.2.17 int cond=0;
436 bdemsky 1.1.2.17 if ((bindex==0)&&(cjmpedge==1))
437 bdemsky 1.1.2.18 cond=ForLoopInfo.LTE;
438 bdemsky 1.1.2.17 if ((bindex==1)&&(cjmpedge==1))
439 bdemsky 1.1.2.18 cond=ForLoopInfo.GTE;
440 bdemsky 1.1.2.17 if ((bindex==0)&&(cjmpedge==0))
441 bdemsky 1.1.2.18 cond=ForLoopInfo.GT;
442 bdemsky 1.1.2.17 if ((bindex==1)&&(cjmpedge==0))
443 bdemsky 1.1.2.18 cond=ForLoopInfo.LT;
444 bdemsky 1.1.2.17 retval=new ForLoopInfo(cond,ivar,increment,
445 bdemsky 1.1.2.17 initialTemp(hc, ivar, lp),
446 bdemsky 1.1.2.17 test.operands(1-bindex),test,cjmp);
447 bdemsky 1.1.2.17 break;
448 bdemsky 1.1.2.17 default:
449 bdemsky 1.1.2.17 }
450 bdemsky 1.1.2.17 return retval;
451 bdemsky 1.1.2.15 }
452 bdemsky 1.1.2.15 else
453 bdemsky 1.1.2.15 return null;
454 bdemsky 1.1.2.14 }
455 bdemsky 1.1.2.14
456 bdemsky 1.1.2.19 /**<code>ForLoopInfo</code> encapsulated information on a for loop.*/
457 bdemsky 1.1.2.18 public class ForLoopInfo {
458 bdemsky 1.1.2.17 private int testtype;
459 bdemsky 1.1.2.17 private Temp induction;
460 bdemsky 1.1.2.17 private Temp increment;
461 bdemsky 1.1.2.17 private Temp indinitial;
462 bdemsky 1.1.2.17 private Temp indfinal;
463 bdemsky 1.1.2.17 private OPER testquad;
464 bdemsky 1.1.2.17 private CJMP loopexit;
465 bdemsky 1.1.2.17 ForLoopInfo(int testtype,Temp induction, Temp increment,Temp indinitial, Temp indfinal, OPER testoper, CJMP loopexit) {
466 bdemsky 1.1.2.17 this.testtype=testtype;
467 bdemsky 1.1.2.17 this.induction=induction;
468 bdemsky 1.1.2.17 this.indinitial=indinitial;
469 bdemsky 1.1.2.17 this.indfinal=indfinal;
470 bdemsky 1.1.2.17 this.testquad=testquad;
471 bdemsky 1.1.2.17 this.loopexit=loopexit;
472 bdemsky 1.1.2.17 this.increment=increment;
473 bdemsky 1.1.2.17 }
474 bdemsky 1.1.2.19 /**<code>testtype</code> tells the type of test used. This is the
475 bdemsky 1.1.2.19 * condition to continue in the loop.*/
476 bdemsky 1.1.2.17 public int testtype() {
477 bdemsky 1.1.2.17 return testtype;
478 bdemsky 1.1.2.17 }
479 bdemsky 1.1.2.19 /**<code>increment</code> gives the temp with the loop invariant
480 bdemsky 1.1.2.19 * value to increment the induction variable by.*/
481 bdemsky 1.1.2.17 public Temp increment() {
482 bdemsky 1.1.2.17 return increment;
483 bdemsky 1.1.2.17 }
484 bdemsky 1.1.2.19 /**<code>induction</code> gives the temp with the induction variable
485 bdemsky 1.1.2.19 * of the for loop.*/
486 bdemsky 1.1.2.17 public Temp induction() {
487 bdemsky 1.1.2.17 return induction;
488 bdemsky 1.1.2.17 }
489 bdemsky 1.1.2.19 /**<code>indInitial</code> gives the initial value of the induction
490 bdemsky 1.1.2.19 * variable.*/
491 bdemsky 1.1.2.17 public Temp indInitial() {
492 bdemsky 1.1.2.17 return indinitial;
493 bdemsky 1.1.2.17 }
494 bdemsky 1.1.2.19 /**<code>indFinal</code> gives the final value of the induction
495 bdemsky 1.1.2.19 * variable.*/
496 bdemsky 1.1.2.17 public Temp indFinal() {
497 bdemsky 1.1.2.17 return indfinal;
498 bdemsky 1.1.2.17 }
499 bdemsky 1.1.2.19 /**<code>testOPER</code> gives the <code>OPER</code> containing the
500 bdemsky 1.1.2.19 * for loop test condition.*/
501 bdemsky 1.1.2.17 public OPER testOPER() {
502 bdemsky 1.1.2.17 return testquad;
503 bdemsky 1.1.2.17 }
504 bdemsky 1.1.2.19 /**<code>loopExit</code> gives the <code>CJMP</code> that is the
505 bdemsky 1.1.2.19 * first exit of the loop.*/
506 bdemsky 1.1.2.17 public CJMP loopExit() {
507 bdemsky 1.1.2.17 return loopexit;
508 bdemsky 1.1.2.17 }
509 bdemsky 1.1.2.19 /** != case */
510 bdemsky 1.1.2.17 public final static int NEQ = 0;
511 bdemsky 1.1.2.19 /** < case */
512 bdemsky 1.1.2.17 public final static int LT = 1;
513 bdemsky 1.1.2.19 /** <= case */
514 bdemsky 1.1.2.17 public final static int LTE = 2;
515 bdemsky 1.1.2.19 /** > case */
516 bdemsky 1.1.2.17 public final static int GT = 3;
517 bdemsky 1.1.2.19 /** >= case */
518 bdemsky 1.1.2.17 public final static int GTE = 4;
519 bdemsky 1.1.2.19 /** <code>toString</code> returns a string representation of the
520 bdemsky 1.1.2.19 * for loop.*/
521 bdemsky 1.1.2.17 public String toString() {
522 bdemsky 1.1.2.17 String ttype=null;
523 bdemsky 1.1.2.17 switch(testtype) {
524 bdemsky 1.1.2.17 case NEQ:
525 bdemsky 1.1.2.17 ttype="!=";
526 bdemsky 1.1.2.17 break;
527 bdemsky 1.1.2.17 case LT:
528 bdemsky 1.1.2.17 ttype="<";
529 bdemsky 1.1.2.17 break;
530 bdemsky 1.1.2.17 case LTE:
531 bdemsky 1.1.2.17 ttype="<=";
532 bdemsky 1.1.2.17 break;
533 bdemsky 1.1.2.17 case GT:
534 bdemsky 1.1.2.17 ttype=">";
535 bdemsky 1.1.2.17 break;
536 bdemsky 1.1.2.17 case GTE:
537 bdemsky 1.1.2.17 ttype=">=";
538 bdemsky 1.1.2.17 break;
539 bdemsky 1.1.2.17 default:
540 bdemsky 1.1.2.17 }
541 bdemsky 1.1.2.17 return new String(induction+"="+indinitial+
542 bdemsky 1.1.2.17 ";"+induction+ttype+indfinal+";"
543 bdemsky 1.1.2.17 +induction+"+="+increment);
544 bdemsky 1.1.2.17 }
545 bdemsky 1.1.2.17 }
546 bdemsky 1.1.2.17
547 bdemsky 1.1.2.17
548 bdemsky 1.1.2.14 /* NOTE: Assumption is made that no quad can go wrong, otherwise
549 bdemsky 1.1.2.14 there would have been an explicity test before it...*/
550 bdemsky 1.1.2.14 class ForLoopVisitor extends LowQuadVisitor {
551 bdemsky 1.1.2.14 private WorkSet track;
552 bdemsky 1.1.2.14 private boolean sideeffects;
553 bdemsky 1.1.2.14 private Set testsopers;
554 bdemsky 1.1.2.14 private UseDef ud;
555 bdemsky 1.1.2.14 private HCode hc;
556 bdemsky 1.1.2.14 private Loops lp;
557 bdemsky 1.1.2.14 private TempMap ssitossamap;
558 bdemsky 1.1.2.15 private boolean analysisdone;
559 bdemsky 1.1.2.15 private Temp inductionvar;
560 bdemsky 1.1.2.15 private OPER testcondition;
561 bdemsky 1.1.2.17 private int bindex;
562 bdemsky 1.1.2.17 private int cjmpedge;
563 bdemsky 1.1.2.17 private CJMP cjmp;
564 bdemsky 1.1.2.14
565 bdemsky 1.1.2.14 ForLoopVisitor(Set testsopers, HCode hc, UseDef ud, Loops lp, TempMap ssitossamap) {
566 bdemsky 1.1.2.14 this.track=new WorkSet();
567 bdemsky 1.1.2.14 this.sideeffects=false;
568 bdemsky 1.1.2.14 this.testsopers=testsopers;
569 bdemsky 1.1.2.14 this.ud=ud;
570 bdemsky 1.1.2.14 this.hc=hc;
571 bdemsky 1.1.2.14 this.lp=lp;
572 bdemsky 1.1.2.14 this.ssitossamap=ssitossamap;
573 bdemsky 1.1.2.15 this.analysisdone=false;
574 bdemsky 1.1.2.15 this.inductionvar=null;
575 bdemsky 1.1.2.15 this.testcondition=null;
576 bdemsky 1.1.2.17 this.cjmpedge=-1;
577 bdemsky 1.1.2.17 }
578 bdemsky 1.1.2.17
579 bdemsky 1.1.2.17 int cjmpedge() {
580 bdemsky 1.1.2.17 return cjmpedge;
581 bdemsky 1.1.2.15 }
582 bdemsky 1.1.2.15
583 bdemsky 1.1.2.15 boolean done() {
584 bdemsky 1.1.2.15 return analysisdone;
585 bdemsky 1.1.2.14 }
586 bdemsky 1.1.2.14
587 bdemsky 1.1.2.14 boolean sideEffects() {
588 bdemsky 1.1.2.14 return sideeffects;
589 bdemsky 1.1.2.14 }
590 bdemsky 1.1.2.14
591 bdemsky 1.1.2.15 boolean forLoop() {
592 bdemsky 1.1.2.15 return (analysisdone&&(inductionvar!=null));
593 bdemsky 1.1.2.15 }
594 bdemsky 1.1.2.15
595 bdemsky 1.1.2.17 CJMP cjmpExit() {
596 bdemsky 1.1.2.17 return cjmp;
597 bdemsky 1.1.2.17 }
598 bdemsky 1.1.2.17
599 bdemsky 1.1.2.15 OPER testCondition() {
600 bdemsky 1.1.2.15 return testcondition;
601 bdemsky 1.1.2.15 }
602 bdemsky 1.1.2.15
603 bdemsky 1.1.2.15 Temp inductionVar() {
604 bdemsky 1.1.2.15 return inductionvar;
605 bdemsky 1.1.2.15 }
606 bdemsky 1.1.2.15
607 bdemsky 1.1.2.17 int bindex() {
608 bdemsky 1.1.2.17 return bindex;
609 bdemsky 1.1.2.17 }
610 bdemsky 1.1.2.17
611 bdemsky 1.1.2.14 public void visit(Quad q) {
612 bdemsky 1.1.2.14 System.out.println("Error in ForLoopVisitor");
613 bdemsky 1.1.2.14 System.out.println(q.toString()+" unhandled");
614 bdemsky 1.1.2.14 }
615 bdemsky 1.1.2.14
616 bdemsky 1.1.2.14 public void visit(AGET q) { trackuses(q); }
617 bdemsky 1.1.2.14 public void visit(ALENGTH q) { trackuses(q); }
618 bdemsky 1.1.2.14 public void visit(ANEW q) { trackuses(q); }
619 bdemsky 1.1.2.14 //These two may have side effects....
620 bdemsky 1.1.2.14 //Need to complete more complicated analysis on them...
621 bdemsky 1.1.2.14 public void visit(ARRAYINIT q) { sideeffects(q); }
622 bdemsky 1.1.2.14 public void visit(ASET q) { sideeffects(q); }
623 bdemsky 1.1.2.14
624 bdemsky 1.1.2.14 //Calls have side efects
625 bdemsky 1.1.2.14 public void visit(CALL q) { sideeffects(q); }
626 bdemsky 1.1.2.14
627 bdemsky 1.1.2.14 //CJMP stops search
628 bdemsky 1.1.2.14 public void visit(CJMP q) {
629 bdemsky 1.1.2.14 //is this a test condition?
630 bdemsky 1.1.2.14 Temp test=q.test();
631 bdemsky 1.1.2.14 Quad[] defs=(Quad[])ud.defMap(hc, test);
632 cananian 1.3.2.1 assert defs.length==1 : "We work only with SSA/SSI";
633 bdemsky 1.1.2.15 Temp binvar=null;
634 bdemsky 1.1.2.14 if (testsopers.contains(defs[0])) {
635 bdemsky 1.1.2.14 //Need to see if it:
636 bdemsky 1.1.2.14 //1) Is on a basic induction variable!
637 bdemsky 1.1.2.14 //2) That the jump leaves the loop
638 bdemsky 1.1.2.14 //3) None of the trackuses set gets used outside of the loop
639 bdemsky 1.1.2.14 //4) None of the sigma defines gets used outside of the loop
640 bdemsky 1.1.2.14 //5) That the increment of the basic induction variable doesn't
641 bdemsky 1.1.2.14 //get used at any point other than the phi function...
642 bdemsky 1.1.2.17 int exit=analyzecjmp(q);
643 bdemsky 1.1.2.17 if (exit!=-1) {
644 bdemsky 1.1.2.14 //finished #2, setup track for #3, 4...
645 bdemsky 1.1.2.14 //See if we have a basic induction varible...
646 bdemsky 1.1.2.14 OPER testoper=(OPER)defs[0];
647 bdemsky 1.1.2.14 Map bamap=(Map)bimap.get(lp.loopEntrances().toArray()[0]);
648 bdemsky 1.1.2.14 for (int i=0;i<testoper.operandsLength();i++) {
649 bdemsky 1.1.2.17 if (bamap.containsKey(ssitossamap.tempMap(testoper.operands(i)))) {
650 bdemsky 1.1.2.15 binvar=ssitossamap.tempMap(testoper.operands(i));
651 bdemsky 1.1.2.17 bindex=i;
652 bdemsky 1.1.2.17 }
653 bdemsky 1.1.2.14 //have a basic induction variable [#1 finished]
654 bdemsky 1.1.2.14 }
655 bdemsky 1.1.2.15 if (binvar!=null) {
656 bdemsky 1.1.2.14 //Still need to verify track set [#3, #4]
657 bdemsky 1.1.2.14 //Still need to check uses of increment [#5]
658 bdemsky 1.1.2.15 PHI header=(PHI)(lp.loopEntrances()).toArray()[0];
659 cananian 1.1.2.22 OPER addquad=(OPER)addQuad(hc, header,binvar, lp.loopIncElements());
660 bdemsky 1.1.2.15 Temp nextinc=addquad.dst();
661 bdemsky 1.1.2.18 boolean otheruse=false;
662 bdemsky 1.1.2.18 WorkSet tocheck=new WorkSet();
663 bdemsky 1.1.2.18 WorkSet done=new WorkSet();
664 bdemsky 1.1.2.18 tocheck.add(nextinc);
665 bdemsky 1.1.2.18 boolean good=true;
666 bdemsky 1.1.2.18 while(good&&(!tocheck.isEmpty())) {
667 bdemsky 1.1.2.18 Temp tuse=(Temp)tocheck.pop();
668 bdemsky 1.1.2.18 done.add(tuse);
669 bdemsky 1.1.2.18 HCodeElement[] niuses=ud.useMap(hc, tuse);
670 bdemsky 1.1.2.18 for (int i=0;i<niuses.length;i++)
671 bdemsky 1.1.2.18 if (niuses[i]!=header) {
672 bdemsky 1.1.2.18 int kind=((Quad)niuses[i]).kind();
673 bdemsky 1.1.2.18 if ((kind==QuadKind.CJMP)||
674 cananian 1.1.2.21 (kind==QuadKind.SWITCH)||
675 cananian 1.1.2.21 (kind==QuadKind.TYPESWITCH)) {
676 bdemsky 1.1.2.18 SIGMA sigma=(SIGMA)niuses[i];
677 bdemsky 1.1.2.18 for(int j=0;j<sigma.numSigmas();j++)
678 bdemsky 1.1.2.18 if(sigma.src(j)==tuse) {
679 bdemsky 1.1.2.18 for(int k=0;k<sigma.arity();k++)
680 bdemsky 1.1.2.18 if (!done.contains(sigma.dst(j,k)))
681 bdemsky 1.1.2.18 tocheck.add(sigma.dst(j,k));
682 bdemsky 1.1.2.18 }
683 bdemsky 1.1.2.18 } else if(kind==QuadKind.CALL) {
684 bdemsky 1.1.2.18 CALL csigma=(CALL)niuses[i];
685 bdemsky 1.1.2.18 for(int l=0;l<csigma.paramsLength();l++)
686 bdemsky 1.1.2.18 if (csigma.params(i)==tuse) {
687 bdemsky 1.1.2.18 good=false;
688 bdemsky 1.1.2.18 break;
689 bdemsky 1.1.2.18 }
690 bdemsky 1.1.2.18 if (good)
691 bdemsky 1.1.2.18 for(int j=0;j<csigma.numSigmas();j++)
692 bdemsky 1.1.2.18 if(csigma.src(j)==tuse) {
693 bdemsky 1.1.2.18 for(int k=0;k<csigma.arity();k++)
694 bdemsky 1.1.2.18 if (!done.contains(csigma.dst(j,k)))
695 bdemsky 1.1.2.18 tocheck.add(csigma.dst(j,k));
696 bdemsky 1.1.2.18 }
697 bdemsky 1.1.2.18 } else if(kind==LowQuadKind.PCALL) {
698 bdemsky 1.1.2.18 PCALL psigma=(PCALL)niuses[i];
699 bdemsky 1.1.2.18 for(int l=0;l<psigma.paramsLength();l++)
700 bdemsky 1.1.2.18 if (psigma.params(i)==tuse) {
701 bdemsky 1.1.2.18 good=false;
702 bdemsky 1.1.2.18 break;
703 bdemsky 1.1.2.18 }
704 bdemsky 1.1.2.18 if (good)
705 bdemsky 1.1.2.18 for(int j=0;j<psigma.numSigmas();j++)
706 bdemsky 1.1.2.18 if(psigma.src(j)==tuse) {
707 bdemsky 1.1.2.18 for(int k=0;k<psigma.arity();k++)
708 bdemsky 1.1.2.18 if (!done.contains(psigma.dst(j,k)))
709 bdemsky 1.1.2.18 tocheck.add(psigma.dst(j,k));
710 bdemsky 1.1.2.18 }
711 bdemsky 1.1.2.18 } else if(kind==QuadKind.PHI) {
712 bdemsky 1.1.2.18 PHI phi=(PHI)niuses[i];
713 bdemsky 1.1.2.18 for (int j=0;j<phi.numPhis();j++)
714 bdemsky 1.1.2.18 for (int k=0;k<phi.numPhis();k++) {
715 bdemsky 1.1.2.18 if (tuse==phi.src(j,k)) {
716 bdemsky 1.1.2.18 if (!done.contains(phi.dst(j)))
717 bdemsky 1.1.2.18 tocheck.add(phi.dst(j));
718 bdemsky 1.1.2.18 }
719 bdemsky 1.1.2.18 }
720 bdemsky 1.1.2.18 } else
721 bdemsky 1.1.2.18 good=false;
722 bdemsky 1.1.2.18
723 bdemsky 1.1.2.18 }
724 bdemsky 1.1.2.18 }
725 bdemsky 1.1.2.18 if (good)
726 bdemsky 1.1.2.15 //condition #5 satisfied
727 bdemsky 1.1.2.15 if (checktracks()) {
728 bdemsky 1.1.2.15 inductionvar=binvar;
729 bdemsky 1.1.2.17 cjmpedge=exit;
730 bdemsky 1.1.2.15 testcondition=testoper;
731 bdemsky 1.1.2.17 cjmp=q;
732 bdemsky 1.1.2.15 }
733 bdemsky 1.1.2.15 //conditions 3&4 satisfied
734 bdemsky 1.1.2.15 }
735 bdemsky 1.1.2.15 }
736 bdemsky 1.1.2.15 }
737 bdemsky 1.1.2.15 analysisdone=true;
738 bdemsky 1.1.2.15 }
739 bdemsky 1.1.2.14
740 bdemsky 1.1.2.15 boolean checktracks() {
741 bdemsky 1.1.2.15 Iterator trackiterate=track.iterator();
742 bdemsky 1.1.2.15 boolean go=true;
743 cananian 1.1.2.22 Set loopset=lp.loopIncElements();
744 bdemsky 1.1.2.15 while (trackiterate.hasNext()&&go) {
745 bdemsky 1.1.2.15 Temp temptocheck=(Temp)trackiterate.next();
746 bdemsky 1.1.2.15 HCodeElement[] uses=ud.useMap(hc, temptocheck);
747 bdemsky 1.1.2.15 for (int i=0;i<uses.length;i++) {
748 bdemsky 1.1.2.15 if (!loopset.contains(uses[i])) {
749 bdemsky 1.1.2.15 go=false;
750 bdemsky 1.1.2.15 break;
751 bdemsky 1.1.2.14 }
752 bdemsky 1.1.2.14 }
753 bdemsky 1.1.2.14 }
754 bdemsky 1.1.2.15 return go;
755 bdemsky 1.1.2.14 }
756 bdemsky 1.1.2.15
757 bdemsky 1.1.2.17 int analyzecjmp(CJMP q) {
758 bdemsky 1.1.2.17 int exit=-1;
759 bdemsky 1.1.2.14 for (int i=0;i<q.nextLength();i++)
760 cananian 1.1.2.22 if (!lp.loopIncElements().contains(q.next(i))) {
761 bdemsky 1.1.2.14 //we've found the way out...
762 bdemsky 1.1.2.14 //we only add things in if
763 bdemsky 1.1.2.14 //they were not generated in front of us...
764 bdemsky 1.1.2.15 //might create confusing semantics,
765 bdemsky 1.1.2.14 //but gotta do it to find any for loops at all that
766 bdemsky 1.1.2.14 //allow lv to escape
767 bdemsky 1.1.2.14 for(int j=0;j<q.numSigmas();j++)
768 bdemsky 1.1.2.14 if (track.contains(q.src(j)))
769 bdemsky 1.1.2.14 track.add(q.dst(j,i));
770 bdemsky 1.1.2.17 exit=i;
771 bdemsky 1.1.2.14 }
772 bdemsky 1.1.2.14 return exit;
773 bdemsky 1.1.2.14 }
774 bdemsky 1.1.2.14
775 bdemsky 1.1.2.14 public void visit(COMPONENTOF q) { trackuses(q); }
776 bdemsky 1.1.2.14 public void visit(CONST q) { trackuses(q); }
777 bdemsky 1.1.2.14
778 bdemsky 1.1.2.14 public void visit(GET q) { trackuses(q); }
779 bdemsky 1.1.2.14
780 bdemsky 1.1.2.14 //Our friend...
781 bdemsky 1.1.2.14 public void visit(INSTANCEOF q) { trackuses(q); }
782 bdemsky 1.1.2.14
783 bdemsky 1.1.2.14 public void visit(MONITORENTER q) { sideeffects(q); }
784 bdemsky 1.1.2.14 public void visit(MONITOREXIT q) { sideeffects(q); }
785 bdemsky 1.1.2.14 public void visit(MOVE q) { trackuses(q); }
786 bdemsky 1.1.2.14 public void visit(NEW q) { trackuses(q); }
787 bdemsky 1.1.2.14
788 bdemsky 1.1.2.14 public void visit(POPER q) { checkopers(q); }
789 bdemsky 1.1.2.14 public void visit(OPER q) { checkopers(q); }
790 bdemsky 1.1.2.14
791 bdemsky 1.1.2.19 //See if we have division by 0
792 bdemsky 1.1.2.14 private void checkopers(OPER q) {
793 bdemsky 1.1.2.14 switch (q.opcode()) {
794 bdemsky 1.1.2.14 case Qop.IDIV:
795 bdemsky 1.1.2.14 case Qop.IREM:
796 bdemsky 1.1.2.14 case Qop.LDIV:
797 bdemsky 1.1.2.14 case Qop.LREM:
798 bdemsky 1.1.2.14 sideeffects(q);
799 bdemsky 1.1.2.14 break;
800 bdemsky 1.1.2.14 default:
801 bdemsky 1.1.2.14 trackuses(q);
802 bdemsky 1.1.2.14 break;
803 bdemsky 1.1.2.14 }
804 bdemsky 1.1.2.14 }
805 bdemsky 1.1.2.14
806 bdemsky 1.1.2.14 //Might want to do something different here....
807 bdemsky 1.1.2.14 //IE..Only add if track.cotnains(src of the phi function)...
808 bdemsky 1.1.2.14 //Not done yet, would complicate things...
809 bdemsky 1.1.2.14 public void visit(PHI q) { trackuses(q); }
810 bdemsky 1.1.2.14 public void visit(RETURN q) { sideeffects(q); }
811 bdemsky 1.1.2.14 //Have to do more complicated analysis...
812 bdemsky 1.1.2.14 public void visit(SET q) { sideeffects(q); }
813 bdemsky 1.1.2.14
814 bdemsky 1.1.2.14 public void visit(THROW q) { sideeffects(q); }
815 bdemsky 1.1.2.14 public void visit(TYPECAST q) { trackuses(q); }
816 bdemsky 1.1.2.14
817 bdemsky 1.1.2.14 public void visit(PCALL q) { sideeffects(q); }
818 bdemsky 1.1.2.14 public void visit(PGET q) { trackuses(q); }
819 bdemsky 1.1.2.14 //Need more complicated analysis...
820 bdemsky 1.1.2.14 public void visit(PSET q) { sideeffects(q); }
821 bdemsky 1.1.2.14
822 bdemsky 1.1.2.14 // PPTR:
823 bdemsky 1.1.2.14 public void visit(PARRAY q) { trackuses(q); }
824 bdemsky 1.1.2.14 public void visit(PFIELD q) { trackuses(q); }
825 bdemsky 1.1.2.14 public void visit(PMETHOD q) { trackuses(q); }
826 bdemsky 1.1.2.14 // PCONST:
827 bdemsky 1.1.2.14 public void visit(PCONST q) { trackuses(q); }
828 bdemsky 1.1.2.14 public void visit(PAOFFSET q) { trackuses(q); }
829 bdemsky 1.1.2.14 public void visit(PFOFFSET q) { trackuses(q); }
830 bdemsky 1.1.2.14 public void visit(PMOFFSET q) { trackuses(q); }
831 bdemsky 1.1.2.14 public void visit(PFCONST q) { trackuses(q); }
832 bdemsky 1.1.2.14 public void visit(PMCONST q) { trackuses(q); }
833 bdemsky 1.1.2.14 void trackuses(Quad q) {
834 bdemsky 1.1.2.14 Temp[] defs=q.def();
835 bdemsky 1.1.2.14 for (int i=0;i<defs.length;i++) {
836 bdemsky 1.1.2.14 track.add(defs[i]);
837 bdemsky 1.1.2.14 }
838 bdemsky 1.1.2.14 }
839 bdemsky 1.1.2.14 void sideeffects(Quad q) {
840 bdemsky 1.1.2.14 sideeffects=true;
841 bdemsky 1.1.2.14 }
842 bdemsky 1.1.2.14 }
843 bdemsky 1.1.2.1 }
844 bdemsky 1.1.2.14
845 bdemsky 1.1.2.3
846 cananian 1.2