1 bdemsky 1.1.2.1 // Induction.java, created Mon Jun 28 13:36:40 1999 by root
2 cananian 1.1.2.7 // 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.Temp.Temp;
7 bdemsky 1.1.2.1 import harpoon.ClassFile.HClass;
8 bdemsky 1.1.2.5 import harpoon.Util.Util;
9 bdemsky 1.1.2.1
10 bdemsky 1.1.2.1 import java.util.ArrayList;
11 bdemsky 1.1.2.5 import java.util.Iterator;
12 bdemsky 1.1.2.1
13 bdemsky 1.1.2.1 /**
14 bdemsky 1.1.2.1 * <code>Induction</code>
15 bdemsky 1.1.2.1 *
16 cananian 1.1.2.7 * @author Brian Demsky <bdemsky@mit.edu>
17 cananian 1.4 * @version $Id: Induction.java,v 1.4 2002/04/10 02:59:57 cananian Exp $
18 bdemsky 1.1.2.3 * This class allows us to store information on Basic/Derived Induction variables.
19 bdemsky 1.1.2.1 */
20 bdemsky 1.1.2.3
21 bdemsky 1.1.2.1 public class Induction {
22 bdemsky 1.1.2.1
23 bdemsky 1.1.2.1 /* Want to be able to store structures of the form:
24 bdemsky 1.1.2.1 pi+pb
25 bdemsky 1.1.2.1 or
26 bdemsky 1.1.2.1 (i*a+b)
27 bdemsky 1.1.2.1 or
28 bdemsky 1.1.2.1 (i*a+b)*pa+pb
29 bdemsky 1.1.2.1 */
30 bdemsky 1.1.2.1
31 bdemsky 1.1.2.1 /* pi+pb */
32 bdemsky 1.1.2.1
33 bdemsky 1.1.2.3 /** Creates basic pointer induction variable.*/
34 bdemsky 1.1.2.5 Induction(Temp ptrvariable, ArrayList pointeroffset, boolean ptrsign) {
35 bdemsky 1.1.2.5 this.ptrvariable=ptrvariable;
36 bdemsky 1.1.2.1 this.pointeroffset=new ArrayList(pointeroffset);
37 bdemsky 1.1.2.5 this.integers=null;
38 bdemsky 1.1.2.1 this.objectsize=null;
39 bdemsky 1.1.2.5 this.ptrsign=ptrsign;
40 bdemsky 1.1.2.4 this.copied=false;
41 bdemsky 1.1.2.1 }
42 bdemsky 1.1.2.1
43 bdemsky 1.1.2.3 /* Creates basic integer induction variable.*/
44 bdemsky 1.1.2.1 Induction(Temp variable, int offset, int intmultiplier) {
45 bdemsky 1.1.2.5 this.ptrvariable=null;
46 bdemsky 1.1.2.5 this.integers=new IntMultAdd(variable,intmultiplier,offset);
47 bdemsky 1.1.2.5 this.ptrsign=true;
48 bdemsky 1.1.2.1 this.objectsize=null;
49 bdemsky 1.1.2.1 this.pointeroffset=new ArrayList();
50 bdemsky 1.1.2.4 this.copied=false;
51 bdemsky 1.1.2.1 }
52 bdemsky 1.1.2.1
53 bdemsky 1.1.2.5
54 bdemsky 1.1.2.5 /** Copy Constructor*/
55 bdemsky 1.1.2.5 Induction(Induction x) {
56 bdemsky 1.1.2.5 this.ptrvariable=x.ptrvariable;
57 bdemsky 1.1.2.5 this.integers=new IntMultAdd(x.integers);
58 bdemsky 1.1.2.5 this.ptrsign=x.ptrsign;
59 bdemsky 1.1.2.5 this.objectsize=x.objectsize;
60 bdemsky 1.1.2.5 this.pointeroffset=new ArrayList(x.pointeroffset);
61 bdemsky 1.1.2.5 this.copied=false;
62 bdemsky 1.1.2.5 x.copied=true;
63 bdemsky 1.1.2.5 }
64 bdemsky 1.1.2.5
65 bdemsky 1.1.2.5 /** Copy Constructor*/
66 bdemsky 1.1.2.5 Induction(Induction x, HClass objectsize) {
67 bdemsky 1.1.2.5 this.ptrvariable=x.ptrvariable;
68 bdemsky 1.1.2.5 this.integers=new IntMultAdd(x.integers);
69 bdemsky 1.1.2.5 this.ptrsign=x.ptrsign;
70 bdemsky 1.1.2.1 this.objectsize=objectsize;
71 bdemsky 1.1.2.5 this.pointeroffset=new ArrayList(x.pointeroffset);
72 bdemsky 1.1.2.5 this.copied=false;
73 bdemsky 1.1.2.5 x.copied=true;
74 bdemsky 1.1.2.5 }
75 bdemsky 1.1.2.5
76 bdemsky 1.1.2.5 /** Constant operator*/
77 bdemsky 1.1.2.5 private Induction(Induction x, boolean operation, int operand) {
78 bdemsky 1.1.2.5 //bool
79 bdemsky 1.1.2.5 this.ptrvariable=x.ptrvariable;
80 bdemsky 1.1.2.5 this.integers=new IntMultAdd(x.integers);
81 bdemsky 1.1.2.5 this.ptrsign=x.ptrsign;
82 bdemsky 1.1.2.5 this.objectsize=x.objectsize;
83 bdemsky 1.1.2.5 this.pointeroffset=new ArrayList(x.pointeroffset);
84 bdemsky 1.1.2.4 this.copied=false;
85 bdemsky 1.1.2.5 x.copied=true;
86 bdemsky 1.1.2.5 if (operation) {
87 bdemsky 1.1.2.5 //Multiply
88 bdemsky 1.1.2.5 if (this.integers.loopinvariant()!=null) {
89 bdemsky 1.1.2.5 this.integers=new IntMultAdd(x.integers, operand,0);
90 bdemsky 1.1.2.5 } else
91 bdemsky 1.1.2.5 this.integers.multiply(operand);
92 bdemsky 1.1.2.5 } else {
93 bdemsky 1.1.2.5 //add
94 bdemsky 1.1.2.5 if (this.integers.loopinvariant()!=null) {
95 bdemsky 1.1.2.5 this.integers=new IntMultAdd(x.integers, 1, operand);
96 bdemsky 1.1.2.5 } else
97 bdemsky 1.1.2.5 this.integers.add(operand);
98 bdemsky 1.1.2.5 }
99 bdemsky 1.1.2.1 }
100 bdemsky 1.1.2.1
101 bdemsky 1.1.2.5 /** Loop invariant operator*/
102 bdemsky 1.1.2.5 private Induction(Induction x, boolean operation, Temp operand) {
103 bdemsky 1.1.2.5 this.ptrvariable=x.ptrvariable;
104 bdemsky 1.1.2.5 this.integers=new IntMultAdd(x.integers);
105 bdemsky 1.1.2.5 this.ptrsign=x.ptrsign;
106 bdemsky 1.1.2.1 this.objectsize=x.objectsize;
107 bdemsky 1.1.2.1 this.pointeroffset=new ArrayList(x.pointeroffset);
108 bdemsky 1.1.2.4 this.copied=false;
109 bdemsky 1.1.2.4 x.copied=true;
110 bdemsky 1.1.2.5 if (this.integers.loopinvariant()!=null) {
111 bdemsky 1.1.2.5 this.integers=new IntMultAdd(x.integers, operand, operation);
112 bdemsky 1.1.2.5 } else {
113 bdemsky 1.1.2.5 this.integers.loopinvariant(operand);
114 bdemsky 1.1.2.5 this.integers.multiply(operation);
115 bdemsky 1.1.2.5 }
116 bdemsky 1.1.2.5 }
117 bdemsky 1.1.2.5
118 bdemsky 1.1.2.5
119 bdemsky 1.1.2.5 public Induction add(int operand) {
120 bdemsky 1.1.2.5 return new Induction(this, false, operand );
121 bdemsky 1.1.2.5 }
122 bdemsky 1.1.2.5
123 bdemsky 1.1.2.5 public Induction multiply(int operand) {
124 bdemsky 1.1.2.5 return new Induction(this, true, operand);
125 bdemsky 1.1.2.5 }
126 bdemsky 1.1.2.5
127 bdemsky 1.1.2.5 public Induction add(Temp operand) {
128 bdemsky 1.1.2.5 return new Induction(this, false, operand);
129 bdemsky 1.1.2.5 }
130 bdemsky 1.1.2.5
131 bdemsky 1.1.2.5 public Induction multiply(Temp operand) {
132 bdemsky 1.1.2.5 return new Induction(this, true, operand);
133 bdemsky 1.1.2.5 }
134 bdemsky 1.1.2.5
135 bdemsky 1.1.2.5 public void padd(Temp operand) {
136 bdemsky 1.1.2.5 pointeroffset.add(new Object[] {operand, new Boolean(true)});
137 bdemsky 1.1.2.5 }
138 bdemsky 1.1.2.5
139 bdemsky 1.1.2.5 public IntMultAdd bottom() {
140 bdemsky 1.1.2.5 return integers.bottom();
141 bdemsky 1.1.2.5 }
142 bdemsky 1.1.2.5
143 bdemsky 1.1.2.5 public Induction negate() {
144 bdemsky 1.1.2.5 Induction temp=new Induction(this);
145 bdemsky 1.1.2.5 if (temp.ptrvariable!=null)
146 bdemsky 1.1.2.5 temp.ptrsign=(!temp.ptrsign);
147 bdemsky 1.1.2.5 else
148 bdemsky 1.1.2.5 temp.integers.negate();
149 bdemsky 1.1.2.5 Iterator iterate=temp.pointeroffset.iterator();
150 bdemsky 1.1.2.5 temp.pointeroffset=new ArrayList();
151 bdemsky 1.1.2.5 while (iterate.hasNext()) {
152 bdemsky 1.1.2.5 Object[] ptr=(Object[])iterate.next();
153 bdemsky 1.1.2.5 temp.pointeroffset.add(new Object[] {ptr[0], new Boolean(!((Boolean)ptr[1]).booleanValue())});
154 bdemsky 1.1.2.5 }
155 bdemsky 1.1.2.5 return temp;
156 bdemsky 1.1.2.2 }
157 bdemsky 1.1.2.2
158 bdemsky 1.1.2.3 /** toString method returns string describing contents of the class.*/
159 bdemsky 1.1.2.2 public String toString() {
160 bdemsky 1.1.2.2 String temp;
161 bdemsky 1.1.2.5 temp=" iv: "+variable().toString()+" offset: ";
162 bdemsky 1.1.2.6 if (constant())
163 bdemsky 1.1.2.6 temp+=(new Integer(offset())).toString() +" intmultiplier: "+
164 bdemsky 1.1.2.6 (new Integer(intmultiplier())).toString();
165 bdemsky 1.1.2.2 if (objectsize!=null)
166 bdemsky 1.1.2.2 temp+=" os: "+objectsize.toString();
167 bdemsky 1.1.2.2 if (pointeroffset!=null)
168 bdemsky 1.1.2.2 temp+=" poff: "+pointeroffset.toString();
169 bdemsky 1.1.2.2 return temp;
170 bdemsky 1.1.2.1 }
171 bdemsky 1.1.2.1
172 bdemsky 1.1.2.5
173 bdemsky 1.1.2.3 /** The <code>pointerindex</code> <code>boolean</code> describes whether
174 bdemsky 1.1.2.5 * the Temp induction variable is a pointer [true] or an
175 bdemsky 1.1.2.5 * integer [false].*/
176 bdemsky 1.1.2.1 public boolean pointerindex;
177 bdemsky 1.1.2.3
178 bdemsky 1.1.2.5 /** The <code>variable</code> <code>Temp</code> stores the basic
179 bdemsky 1.1.2.5 * induction variable.*/
180 bdemsky 1.1.2.5 public Temp variable() {
181 bdemsky 1.1.2.5 IntMultAdd ptr=integers;
182 bdemsky 1.1.2.5 while (ptr.child()!=null)
183 bdemsky 1.1.2.5 ptr=ptr.child();
184 bdemsky 1.1.2.5 return ptr.inductionvar();
185 bdemsky 1.1.2.5 }
186 bdemsky 1.1.2.3
187 bdemsky 1.1.2.5 public boolean constant() {
188 bdemsky 1.1.2.5 return integers.constant();
189 bdemsky 1.1.2.5 }
190 bdemsky 1.1.2.4
191 bdemsky 1.1.2.5 public int intmultiplier() {
192 cananian 1.3.2.1 assert this.constant();
193 bdemsky 1.1.2.5 return integers.intmultiplier();
194 bdemsky 1.1.2.5 }
195 bdemsky 1.1.2.4
196 bdemsky 1.1.2.5 public int offset() {
197 cananian 1.3.2.1 assert this.constant();
198 bdemsky 1.1.2.5 return integers.offset();
199 bdemsky 1.1.2.5 }
200 bdemsky 1.1.2.4
201 bdemsky 1.1.2.5 public int depth() {
202 bdemsky 1.1.2.5 if (integers!=null)
203 bdemsky 1.1.2.5 return integers.depth();
204 bdemsky 1.1.2.5 else return 0;
205 bdemsky 1.1.2.5 }
206 bdemsky 1.1.2.4
207 bdemsky 1.1.2.5 /** The <code>intmultadd</code> int saves integer arithmetic.*/
208 bdemsky 1.1.2.5 private IntMultAdd integers;
209 bdemsky 1.1.2.4
210 bdemsky 1.1.2.5 public Temp ptrvariable;
211 bdemsky 1.1.2.4
212 bdemsky 1.1.2.5 /** The <code>ptrsign</code> saves the relative sign.
213 bdemsky 1.1.2.5 * True being the same sign*/
214 bdemsky 1.1.2.5 public boolean ptrsign;
215 bdemsky 1.1.2.4
216 bdemsky 1.1.2.4
217 bdemsky 1.1.2.5 /** The <code>objectsize</code> <code>HClass</code>
218 bdemsky 1.1.2.5 * saves the array type.*/
219 bdemsky 1.1.2.5 public HClass objectsize;
220 bdemsky 1.1.2.4
221 bdemsky 1.1.2.4
222 bdemsky 1.1.2.5 /** The <code>ArrayList</code> saves pointer <code>Temp</code>s
223 bdemsky 1.1.2.5 * that are added in.*/
224 bdemsky 1.1.2.5 public ArrayList pointeroffset;
225 bdemsky 1.1.2.5 public boolean copied;
226 bdemsky 1.1.2.4
227 bdemsky 1.1.2.4
228 bdemsky 1.1.2.5 public class IntMultAdd {
229 bdemsky 1.1.2.5 //Form:
230 bdemsky 1.1.2.5 //(ax+b)?loopinvariant
231 bdemsky 1.1.2.5 IntMultAdd(Temp inductionvar, int intmultiplier, int offset) {
232 bdemsky 1.1.2.5 this.intmultiplier=intmultiplier;
233 bdemsky 1.1.2.5 this.offset=offset;
234 bdemsky 1.1.2.5 this.inductionvar=inductionvar;
235 bdemsky 1.1.2.5 }
236 bdemsky 1.1.2.5
237 bdemsky 1.1.2.5 IntMultAdd(IntMultAdd x, int intmultiplier, int offset) {
238 bdemsky 1.1.2.5 this.intmultiplier=intmultiplier;
239 bdemsky 1.1.2.5 this.offset=offset;
240 bdemsky 1.1.2.5 this.inductionvar=null;
241 bdemsky 1.1.2.5 this.child=new IntMultAdd(x);
242 bdemsky 1.1.2.5 this.child.parent=this;
243 bdemsky 1.1.2.5 }
244 bdemsky 1.1.2.5
245 bdemsky 1.1.2.5 IntMultAdd(IntMultAdd x) {
246 bdemsky 1.1.2.5 this.intmultiplier=x.intmultiplier;
247 bdemsky 1.1.2.5 this.offset=x.offset;
248 bdemsky 1.1.2.5 this.inductionvar=x.inductionvar;
249 bdemsky 1.1.2.5 this.multiply=x.multiply;
250 bdemsky 1.1.2.5 this.loopinvariant=x.loopinvariant;
251 bdemsky 1.1.2.5 this.invariantsign=x.invariantsign;
252 bdemsky 1.1.2.5 if (x.child!=null) {
253 bdemsky 1.1.2.5 this.child=new IntMultAdd(x.child);
254 bdemsky 1.1.2.5 this.child.parent=this;
255 bdemsky 1.1.2.5 }
256 bdemsky 1.1.2.5 else
257 bdemsky 1.1.2.5 this.child=null;
258 bdemsky 1.1.2.5 }
259 bdemsky 1.1.2.5
260 bdemsky 1.1.2.5 IntMultAdd(IntMultAdd x, Temp operand, boolean multiply) {
261 bdemsky 1.1.2.5 this.intmultiplier=1;
262 bdemsky 1.1.2.5 this.offset=0;
263 bdemsky 1.1.2.5 this.inductionvar=null;
264 bdemsky 1.1.2.5 this.loopinvariant=operand;
265 bdemsky 1.1.2.5 this.invariantsign=true;
266 bdemsky 1.1.2.5 this.multiply=multiply;
267 bdemsky 1.1.2.5 this.child=new IntMultAdd(x);
268 bdemsky 1.1.2.5 this.child.parent=this;
269 bdemsky 1.1.2.5 }
270 bdemsky 1.1.2.5
271 bdemsky 1.1.2.5
272 bdemsky 1.1.2.5 public IntMultAdd bottom() {
273 bdemsky 1.1.2.5 IntMultAdd ptr=this;
274 bdemsky 1.1.2.5 while (ptr.child()!=null)
275 bdemsky 1.1.2.5 ptr=ptr.child();
276 bdemsky 1.1.2.5 return ptr;
277 bdemsky 1.1.2.5 }
278 bdemsky 1.1.2.5
279 bdemsky 1.1.2.5 public int depth() {
280 bdemsky 1.1.2.5 IntMultAdd ptr=this;
281 bdemsky 1.1.2.5 int count=1;
282 bdemsky 1.1.2.5 while (ptr.child()!=null) {
283 bdemsky 1.1.2.5 ptr=ptr.child;
284 bdemsky 1.1.2.5 count++;
285 bdemsky 1.1.2.5 }
286 bdemsky 1.1.2.5 return count;
287 bdemsky 1.1.2.5 }
288 bdemsky 1.1.2.5
289 bdemsky 1.1.2.5 public void multiply(int x) {
290 bdemsky 1.1.2.5 intmultiplier*=x;
291 bdemsky 1.1.2.5 offset*=x;
292 bdemsky 1.1.2.5 }
293 bdemsky 1.1.2.5
294 bdemsky 1.1.2.5 public void add(int x) {
295 bdemsky 1.1.2.5 offset+=x;
296 bdemsky 1.1.2.5 }
297 bdemsky 1.1.2.5
298 bdemsky 1.1.2.5 public void negate() {
299 bdemsky 1.1.2.5 intmultiplier=-intmultiplier;
300 bdemsky 1.1.2.5 offset=-offset;
301 bdemsky 1.1.2.5 invariantsign=!invariantsign;
302 bdemsky 1.1.2.5 }
303 bdemsky 1.1.2.5
304 bdemsky 1.1.2.5 public boolean constant() {
305 bdemsky 1.1.2.5 if ((child==null)&&(loopinvariant==null))
306 bdemsky 1.1.2.5 return true;
307 bdemsky 1.1.2.5 else
308 bdemsky 1.1.2.5 return false;
309 bdemsky 1.1.2.5 }
310 bdemsky 1.1.2.5
311 bdemsky 1.1.2.5 public IntMultAdd parent() {
312 bdemsky 1.1.2.5 return parent;
313 bdemsky 1.1.2.5 }
314 bdemsky 1.1.2.5
315 bdemsky 1.1.2.5 public int intmultiplier() {
316 bdemsky 1.1.2.5 return intmultiplier;
317 bdemsky 1.1.2.5 }
318 bdemsky 1.1.2.5
319 bdemsky 1.1.2.5 public int offset() {
320 bdemsky 1.1.2.5 return offset;
321 bdemsky 1.1.2.5 }
322 bdemsky 1.1.2.5
323 bdemsky 1.1.2.5 public Temp inductionvar() {
324 bdemsky 1.1.2.5 return inductionvar;
325 bdemsky 1.1.2.5 }
326 bdemsky 1.1.2.5
327 bdemsky 1.1.2.5 public IntMultAdd child() {
328 bdemsky 1.1.2.5 return child;
329 bdemsky 1.1.2.5 }
330 bdemsky 1.1.2.5
331 bdemsky 1.1.2.5 public void multiply(boolean operation) {
332 bdemsky 1.1.2.5 this.multiply=operation;
333 bdemsky 1.1.2.5 }
334 bdemsky 1.1.2.5
335 bdemsky 1.1.2.5 public boolean multiply() {
336 bdemsky 1.1.2.5 return multiply;
337 bdemsky 1.1.2.5 }
338 bdemsky 1.1.2.5
339 bdemsky 1.1.2.5 public Temp loopinvariant() {
340 bdemsky 1.1.2.5 return loopinvariant;
341 bdemsky 1.1.2.5 }
342 bdemsky 1.1.2.5
343 bdemsky 1.1.2.5 public void loopinvariant(Temp loopinvariant) {
344 bdemsky 1.1.2.5 this.loopinvariant=loopinvariant;
345 bdemsky 1.1.2.5 }
346 bdemsky 1.1.2.5
347 bdemsky 1.1.2.5 public boolean invariantsign() {
348 bdemsky 1.1.2.5 return invariantsign;
349 bdemsky 1.1.2.5 }
350 bdemsky 1.1.2.5
351 bdemsky 1.1.2.5 private boolean multiply; //operation true: ?=*/ false: ?=+
352 bdemsky 1.1.2.5 private Temp loopinvariant; //loop invariant
353 bdemsky 1.1.2.5 private boolean invariantsign;
354 bdemsky 1.1.2.5
355 bdemsky 1.1.2.5 private int intmultiplier;//a
356 bdemsky 1.1.2.5 private int offset;//b
357 bdemsky 1.1.2.5 private IntMultAdd parent;
358 bdemsky 1.1.2.5 private IntMultAdd child;//x
359 bdemsky 1.1.2.5 private Temp inductionvar;//x
360 bdemsky 1.1.2.5 }
361 cananian 1.2 }