1 bdemsky 1.1.2.1 // Loopinvariance.java, created Mon Jun 28 13:33:40 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 bdemsky 1.1.2.1 import harpoon.Analysis.UseDef;
7 cananian 1.1.2.10 import harpoon.ClassFile.HCode;
8 cananian 1.1.2.10 import harpoon.ClassFile.HCodeElement;
9 cananian 1.1.2.10 import harpoon.IR.LowQuad.LowQuadVisitor;
10 cananian 1.1.2.10 import harpoon.IR.LowQuad.PAOFFSET;
11 cananian 1.1.2.10 import harpoon.IR.LowQuad.PARRAY;
12 cananian 1.1.2.10 import harpoon.IR.LowQuad.PCALL;
13 cananian 1.1.2.10 import harpoon.IR.LowQuad.PFCONST;
14 cananian 1.1.2.10 import harpoon.IR.LowQuad.PFIELD;
15 cananian 1.1.2.10 import harpoon.IR.LowQuad.PFOFFSET;
16 cananian 1.1.2.10 import harpoon.IR.LowQuad.PGET;
17 cananian 1.1.2.10 import harpoon.IR.LowQuad.PMCONST;
18 cananian 1.1.2.10 import harpoon.IR.LowQuad.PMETHOD;
19 cananian 1.1.2.10 import harpoon.IR.LowQuad.PMOFFSET;
20 cananian 1.1.2.10 import harpoon.IR.LowQuad.POPER;
21 cananian 1.1.2.10 import harpoon.IR.LowQuad.PSET;
22 cananian 1.1.2.10 import harpoon.IR.Quads.AGET;
23 cananian 1.1.2.10 import harpoon.IR.Quads.ALENGTH;
24 cananian 1.1.2.10 import harpoon.IR.Quads.ANEW;
25 cananian 1.1.2.10 import harpoon.IR.Quads.ARRAYINIT;
26 cananian 1.1.2.10 import harpoon.IR.Quads.ASET;
27 cananian 1.1.2.10 import harpoon.IR.Quads.CALL;
28 cananian 1.1.2.10 import harpoon.IR.Quads.COMPONENTOF;
29 cananian 1.1.2.10 import harpoon.IR.Quads.CONST;
30 cananian 1.1.2.10 import harpoon.IR.Quads.FOOTER;
31 cananian 1.1.2.10 import harpoon.IR.Quads.GET;
32 cananian 1.1.2.10 import harpoon.IR.Quads.HANDLER;
33 cananian 1.1.2.10 import harpoon.IR.Quads.HEADER;
34 cananian 1.1.2.10 import harpoon.IR.Quads.INSTANCEOF;
35 cananian 1.1.2.10 import harpoon.IR.Quads.METHOD;
36 cananian 1.1.2.10 import harpoon.IR.Quads.MONITORENTER;
37 cananian 1.1.2.10 import harpoon.IR.Quads.MONITOREXIT;
38 cananian 1.1.2.10 import harpoon.IR.Quads.MOVE;
39 cananian 1.1.2.10 import harpoon.IR.Quads.NEW;
40 cananian 1.1.2.10 import harpoon.IR.Quads.NOP;
41 cananian 1.1.2.10 import harpoon.IR.Quads.OPER;
42 cananian 1.1.2.10 import harpoon.IR.Quads.PHI;
43 cananian 1.1.2.10 import harpoon.IR.Quads.Qop;
44 cananian 1.1.2.10 import harpoon.IR.Quads.Quad;
45 cananian 1.1.2.10 import harpoon.IR.Quads.RETURN;
46 cananian 1.1.2.10 import harpoon.IR.Quads.SET;
47 cananian 1.1.2.10 import harpoon.IR.Quads.SIGMA;
48 cananian 1.1.2.10 import harpoon.IR.Quads.THROW;
49 bdemsky 1.1.2.1 import harpoon.Temp.TempMap;
50 bdemsky 1.1.2.1 import harpoon.Temp.Temp;
51 cananian 1.3 import net.cscott.jutil.WorkSet;
52 bdemsky 1.1.2.1
53 bdemsky 1.1.2.1 import java.util.Iterator;
54 bdemsky 1.1.2.1 /**
55 bdemsky 1.1.2.1 * <code>LoopInvariance</code>
56 bdemsky 1.1.2.1 *
57 bdemsky 1.1.2.1 * @author Brian Demsky <bdemsky@mit.edu>
58 cananian 1.3 * @version $Id: LoopInvariance.java,v 1.3 2004/02/08 01:52:54 cananian Exp $
59 bdemsky 1.1.2.1 */
60 bdemsky 1.1.2.1 public class LoopInvariance {
61 bdemsky 1.1.2.1
62 bdemsky 1.1.2.1
63 bdemsky 1.1.2.1 TempMap tm;
64 bdemsky 1.1.2.1 HCode hc;
65 bdemsky 1.1.2.1
66 bdemsky 1.1.2.2 /** Creates a <code>LoopInvariance</code>. */
67 bdemsky 1.1.2.1 public LoopInvariance(TempMap tm,HCode hc) {
68 bdemsky 1.1.2.1 this.tm=tm;
69 bdemsky 1.1.2.1 this.hc=hc;
70 bdemsky 1.1.2.1 }
71 bdemsky 1.1.2.1
72 bdemsky 1.1.2.2 /** Creates a <code>WorkSet</code> containing <code>Quad</code>s that
73 bdemsky 1.1.2.2 * are loop invariant. Takes in a <code>WorkSet</code> of
74 bdemsky 1.1.2.2 * <code>Quad</code>s that are in the loop. */
75 bdemsky 1.1.2.2
76 bdemsky 1.1.2.1 public WorkSet invariants(WorkSet elements) {
77 bdemsky 1.1.2.1 WorkSet invariants=new WorkSet();
78 bdemsky 1.1.2.1 harpoon.Analysis.UseDef ud = new harpoon.Analysis.UseDef();
79 bdemsky 1.1.2.1 boolean change=true;
80 bdemsky 1.1.2.1 InvariantVisitor visitor=new InvariantVisitor(ud, elements, invariants);
81 bdemsky 1.1.2.1 while (visitor.change()) {
82 bdemsky 1.1.2.1 visitor.reset();
83 bdemsky 1.1.2.1 Iterator ourself=elements.iterator();
84 bdemsky 1.1.2.1 while (ourself.hasNext()) {
85 bdemsky 1.1.2.1 Quad nxt=(Quad)ourself.next();
86 bdemsky 1.1.2.1 //is this node invariant?
87 cananian 1.1.2.8 nxt.accept(visitor);
88 bdemsky 1.1.2.1 if (visitor.remove())
89 bdemsky 1.1.2.1 ourself.remove();
90 bdemsky 1.1.2.1 //doesn't depend on this loop...so add it to invariants
91 bdemsky 1.1.2.1 }
92 bdemsky 1.1.2.1 }
93 bdemsky 1.1.2.1 return invariants;
94 bdemsky 1.1.2.1 }
95 bdemsky 1.1.2.2
96 bdemsky 1.1.2.2 /** <code>InvariantVisitor</code> visits Quads and determines if they are
97 bdemsky 1.1.2.2 * loop invariant.*/
98 bdemsky 1.1.2.1
99 bdemsky 1.1.2.1 class InvariantVisitor extends LowQuadVisitor {
100 bdemsky 1.1.2.1 UseDef ud;
101 bdemsky 1.1.2.1 WorkSet invariants;
102 bdemsky 1.1.2.1 boolean change;
103 bdemsky 1.1.2.1 WorkSet elements;
104 bdemsky 1.1.2.1 boolean removeflag;
105 bdemsky 1.1.2.1
106 bdemsky 1.1.2.1 InvariantVisitor(UseDef ud, WorkSet elements, WorkSet invariants) {
107 bdemsky 1.1.2.1 this.ud=ud;
108 bdemsky 1.1.2.1 this.invariants=invariants;
109 bdemsky 1.1.2.1 this.elements=elements;
110 bdemsky 1.1.2.1 change=true;
111 bdemsky 1.1.2.1 }
112 bdemsky 1.1.2.1
113 bdemsky 1.1.2.1 public boolean remove() {
114 bdemsky 1.1.2.1 return removeflag;
115 bdemsky 1.1.2.1 }
116 bdemsky 1.1.2.1
117 bdemsky 1.1.2.1 public boolean change() {
118 bdemsky 1.1.2.1 return change;
119 bdemsky 1.1.2.1 }
120 bdemsky 1.1.2.1
121 bdemsky 1.1.2.1 public void reset() {
122 bdemsky 1.1.2.1 change=false;
123 bdemsky 1.1.2.4 }
124 bdemsky 1.1.2.4
125 bdemsky 1.1.2.3 void visitdefault(Quad q) {
126 bdemsky 1.1.2.1 Temp [] uses=q.use();
127 bdemsky 1.1.2.1 boolean ours=false;
128 bdemsky 1.1.2.1 for (int i=0;i<uses.length;i++) {
129 bdemsky 1.1.2.1 HCodeElement []sources=ud.defMap(hc,tm.tempMap(uses[i]));
130 bdemsky 1.1.2.1 for (int j=0;j<sources.length;j++) {
131 bdemsky 1.1.2.1 if (elements.contains(sources[j])) {
132 bdemsky 1.1.2.1 ours=true; break;
133 bdemsky 1.1.2.1 }
134 bdemsky 1.1.2.1 }
135 bdemsky 1.1.2.6 }
136 bdemsky 1.1.2.1 if (ours==false) {
137 bdemsky 1.1.2.1 change=true;
138 bdemsky 1.1.2.1 removeflag=true;
139 bdemsky 1.1.2.1 invariants.push(q);
140 bdemsky 1.1.2.1 } else
141 bdemsky 1.1.2.1 removeflag=false;
142 bdemsky 1.1.2.1 }
143 bdemsky 1.1.2.1
144 bdemsky 1.1.2.1
145 bdemsky 1.1.2.7 public void visit(Quad q) {
146 bdemsky 1.1.2.7 System.out.println("Not expected in LoopInvariance:" + q.toString());
147 bdemsky 1.1.2.1 removeflag=false;
148 bdemsky 1.1.2.3 }
149 bdemsky 1.1.2.9
150 bdemsky 1.1.2.9 /* All of these redefined to avoid error messages!*/
151 bdemsky 1.1.2.9 public void visit(harpoon.IR.Quads.AGET q) {
152 bdemsky 1.1.2.9 removeflag=false;
153 bdemsky 1.1.2.9 }
154 bdemsky 1.1.2.9
155 bdemsky 1.1.2.9 public void visit(harpoon.IR.Quads.ASET q) {
156 bdemsky 1.1.2.9 removeflag=false;
157 bdemsky 1.1.2.9 }
158 bdemsky 1.1.2.9
159 bdemsky 1.1.2.9 public void visit(harpoon.IR.Quads.CALL q) {
160 bdemsky 1.1.2.9 removeflag=false;
161 bdemsky 1.1.2.9 }
162 bdemsky 1.1.2.9
163 bdemsky 1.1.2.9 public void visit(harpoon.IR.Quads.GET q) {
164 bdemsky 1.1.2.9 removeflag=false;
165 bdemsky 1.1.2.9 }
166 bdemsky 1.1.2.9
167 bdemsky 1.1.2.9 public void visit(harpoon.IR.Quads.HANDLER q) {
168 bdemsky 1.1.2.9 //better not be in a loop!!!!!!!
169 bdemsky 1.1.2.9 removeflag=false;
170 bdemsky 1.1.2.9 }
171 bdemsky 1.1.2.9
172 bdemsky 1.1.2.9 public void visit(harpoon.IR.Quads.OPER q) {
173 bdemsky 1.1.2.9 switch (q.opcode()) {
174 bdemsky 1.1.2.9 case Qop.DDIV:
175 bdemsky 1.1.2.9 case Qop.FDIV:
176 bdemsky 1.1.2.9 case Qop.IDIV:
177 bdemsky 1.1.2.9 case Qop.LDIV:
178 bdemsky 1.1.2.9 removeflag=false;
179 bdemsky 1.1.2.9 break;
180 bdemsky 1.1.2.9 default:
181 bdemsky 1.1.2.9 visitdefault(q);
182 bdemsky 1.1.2.9 }
183 bdemsky 1.1.2.9 }
184 bdemsky 1.1.2.9
185 bdemsky 1.1.2.9 public void visit(harpoon.IR.Quads.SET q) {
186 bdemsky 1.1.2.9 removeflag=false;
187 bdemsky 1.1.2.9 }
188 bdemsky 1.1.2.9
189 bdemsky 1.1.2.3
190 bdemsky 1.1.2.7 public void visit(ALENGTH q) {
191 bdemsky 1.1.2.7 visitdefault(q);
192 bdemsky 1.1.2.6 }
193 bdemsky 1.1.2.6
194 bdemsky 1.1.2.7 public void visit(ANEW q) {
195 bdemsky 1.1.2.7 //Not loop invariant
196 bdemsky 1.1.2.5 removeflag=false;
197 bdemsky 1.1.2.5 }
198 bdemsky 1.1.2.5
199 bdemsky 1.1.2.7 public void visit(ARRAYINIT q) {
200 bdemsky 1.1.2.5 removeflag=false;
201 bdemsky 1.1.2.5 }
202 bdemsky 1.1.2.5
203 bdemsky 1.1.2.7 public void visit(COMPONENTOF q) {
204 bdemsky 1.1.2.7 visitdefault(q);
205 bdemsky 1.1.2.5 }
206 bdemsky 1.1.2.5
207 bdemsky 1.1.2.7 public void visit(CONST q) {
208 bdemsky 1.1.2.7 visitdefault(q);
209 bdemsky 1.1.2.1 }
210 bdemsky 1.1.2.1
211 bdemsky 1.1.2.5 public void visit(FOOTER q) {
212 bdemsky 1.1.2.6 removeflag=false;
213 bdemsky 1.1.2.6 }
214 bdemsky 1.1.2.6
215 bdemsky 1.1.2.6 public void visit(HEADER q) {
216 bdemsky 1.1.2.5 removeflag=false;
217 bdemsky 1.1.2.5 }
218 bdemsky 1.1.2.5
219 bdemsky 1.1.2.7 public void visit(INSTANCEOF q) {
220 bdemsky 1.1.2.7 visitdefault(q);
221 bdemsky 1.1.2.7 }
222 bdemsky 1.1.2.7
223 bdemsky 1.1.2.5 public void visit(METHOD q) {
224 bdemsky 1.1.2.5 removeflag=false;
225 bdemsky 1.1.2.5 }
226 bdemsky 1.1.2.5
227 bdemsky 1.1.2.5 public void visit(MONITORENTER q) {
228 bdemsky 1.1.2.5 removeflag=false;
229 bdemsky 1.1.2.5 }
230 bdemsky 1.1.2.5
231 bdemsky 1.1.2.5 public void visit(MONITOREXIT q) {
232 bdemsky 1.1.2.5 removeflag=false;
233 bdemsky 1.1.2.5 }
234 bdemsky 1.1.2.5
235 bdemsky 1.1.2.7 public void visit(MOVE q) {
236 bdemsky 1.1.2.7 visitdefault(q);
237 bdemsky 1.1.2.7 }
238 bdemsky 1.1.2.7
239 bdemsky 1.1.2.7 public void visit(NEW q) {
240 bdemsky 1.1.2.7 removeflag=false;
241 bdemsky 1.1.2.7 }
242 bdemsky 1.1.2.7
243 bdemsky 1.1.2.7 public void visit(NOP q) {
244 bdemsky 1.1.2.7 visitdefault(q);
245 bdemsky 1.1.2.7 }
246 bdemsky 1.1.2.7
247 bdemsky 1.1.2.1 public void visit(PCALL q) {
248 bdemsky 1.1.2.1 //Calls aren't loop invariant...
249 bdemsky 1.1.2.1 //they might have side effects
250 bdemsky 1.1.2.7 removeflag=false;
251 bdemsky 1.1.2.7 }
252 bdemsky 1.1.2.7
253 bdemsky 1.1.2.7 public void visit(PARRAY q) { visitdefault(q); }
254 bdemsky 1.1.2.7 public void visit(PFIELD q) { visitdefault(q); }
255 bdemsky 1.1.2.7 public void visit(PMETHOD q) { visitdefault(q); }
256 bdemsky 1.1.2.7 public void visit(PAOFFSET q) { visitdefault(q); }
257 bdemsky 1.1.2.7 public void visit(PFOFFSET q) { visitdefault(q); }
258 bdemsky 1.1.2.7 public void visit(PMOFFSET q) { visitdefault(q); }
259 bdemsky 1.1.2.7 public void visit(PFCONST q) { visitdefault(q); }
260 bdemsky 1.1.2.7 public void visit(PMCONST q) { visitdefault(q); }
261 bdemsky 1.1.2.7
262 bdemsky 1.1.2.7 public void visit(PGET q) {
263 bdemsky 1.1.2.7 removeflag=false;
264 bdemsky 1.1.2.7 }
265 bdemsky 1.1.2.7
266 bdemsky 1.1.2.7 public void visit(POPER q) {
267 bdemsky 1.1.2.7 switch (q.opcode()) {
268 bdemsky 1.1.2.7 case Qop.DDIV:
269 bdemsky 1.1.2.7 case Qop.FDIV:
270 bdemsky 1.1.2.7 case Qop.IDIV:
271 bdemsky 1.1.2.7 case Qop.LDIV:
272 bdemsky 1.1.2.7 removeflag=false;
273 bdemsky 1.1.2.7 break;
274 bdemsky 1.1.2.7 default:
275 bdemsky 1.1.2.7 visitdefault(q);
276 bdemsky 1.1.2.7 }
277 bdemsky 1.1.2.7 }
278 bdemsky 1.1.2.7
279 bdemsky 1.1.2.7 public void visit(PSET q) {
280 bdemsky 1.1.2.7 removeflag=false;
281 bdemsky 1.1.2.7 }
282 bdemsky 1.1.2.7
283 bdemsky 1.1.2.7 public void visit(RETURN q) {
284 bdemsky 1.1.2.1 removeflag=false;
285 bdemsky 1.1.2.1 }
286 bdemsky 1.1.2.5
287 bdemsky 1.1.2.1 public void visit(SIGMA q) {
288 bdemsky 1.1.2.1 removeflag=false;
289 bdemsky 1.1.2.1 }
290 bdemsky 1.1.2.1
291 bdemsky 1.1.2.5 public void visit(THROW q) {
292 bdemsky 1.1.2.5 removeflag=false;
293 bdemsky 1.1.2.5 }
294 bdemsky 1.1.2.5
295 bdemsky 1.1.2.1 public void visit(PHI q) {
296 bdemsky 1.1.2.1 removeflag=false;
297 bdemsky 1.1.2.1 }
298 bdemsky 1.1.2.1 }
299 bdemsky 1.1.2.1 }
300 cananian 1.2