1 bdemsky 1.1.2.1 // BasicInduction.java, created Mon Jun 28 13:38:30 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.Loops.LoopFinder;
7 bdemsky 1.1.2.1 import harpoon.Analysis.Loops.Loops;
8 bdemsky 1.1.2.1 import harpoon.Analysis.LowQuad.Loop.Induction;
9 bdemsky 1.1.2.1 import harpoon.Analysis.UseDef;
10 cananian 1.1.2.8 import harpoon.ClassFile.HCode;
11 cananian 1.1.2.8 import harpoon.ClassFile.HCodeEdge;
12 cananian 1.1.2.8 import harpoon.ClassFile.HCodeElement;
13 cananian 1.1.2.8 import harpoon.IR.LowQuad.LQop;
14 cananian 1.1.2.8 import harpoon.IR.LowQuad.LowQuadVisitor;
15 cananian 1.1.2.8 import harpoon.IR.LowQuad.POPER;
16 cananian 1.1.2.7 import harpoon.IR.Properties.CFGraphable;
17 cananian 1.1.2.8 import harpoon.IR.Quads.AGET;
18 cananian 1.1.2.8 import harpoon.IR.Quads.ASET;
19 cananian 1.1.2.8 import harpoon.IR.Quads.GET;
20 cananian 1.1.2.8 import harpoon.IR.Quads.HANDLER;
21 cananian 1.1.2.8 import harpoon.IR.Quads.OPER;
22 cananian 1.1.2.8 import harpoon.IR.Quads.PHI;
23 cananian 1.1.2.8 import harpoon.IR.Quads.Qop;
24 cananian 1.1.2.8 import harpoon.IR.Quads.Quad;
25 cananian 1.1.2.8 import harpoon.IR.Quads.SET;
26 cananian 1.5 import net.cscott.jutil.WorkSet;
27 bdemsky 1.1.2.14 import harpoon.Util.Util;
28 bdemsky 1.1.2.1 import harpoon.Temp.Temp;
29 bdemsky 1.1.2.1 import harpoon.Temp.TempMap;
30 bdemsky 1.1.2.1
31 bdemsky 1.1.2.1
32 bdemsky 1.1.2.1 import java.util.HashMap;
33 bdemsky 1.1.2.1 import java.util.Iterator;
34 bdemsky 1.1.2.1
35 bdemsky 1.1.2.1
36 bdemsky 1.1.2.1 /**
37 bdemsky 1.1.2.1 * <code>BasicInductions</code>
38 bdemsky 1.1.2.1 *
39 bdemsky 1.1.2.1 * @author Brian Demsky <bdemsky@mit.edu>
40 cananian 1.5 * @version $Id: BasicInductions.java,v 1.5 2004/02/08 01:52:54 cananian Exp $
41 bdemsky 1.1.2.1 */
42 bdemsky 1.1.2.1 public class BasicInductions {
43 bdemsky 1.1.2.1 HCode hc;
44 bdemsky 1.1.2.1 TempMap tm;
45 bdemsky 1.1.2.1
46 bdemsky 1.1.2.1 /** Creates a <code>BasicInductions</code> object. */
47 bdemsky 1.1.2.1 public BasicInductions(TempMap tm, HCode hc) {
48 bdemsky 1.1.2.1 this.hc=hc;
49 bdemsky 1.1.2.1 this.tm=tm;
50 bdemsky 1.1.2.1 }
51 bdemsky 1.1.2.1
52 bdemsky 1.1.2.1 /** Creates a <code>HashMap</code> mapping <code>Temp</code>s to
53 bdemsky 1.1.2.1 * <code>Induction</code> classes describing the induction variable.
54 bdemsky 1.1.2.1 * This code only finds basic induction variables. */
55 bdemsky 1.1.2.1
56 bdemsky 1.1.2.1 public HashMap doInduction(Loops lp, WorkSet invariants) {
57 bdemsky 1.1.2.1 HashMap basicinductions=new HashMap();
58 bdemsky 1.1.2.1
59 bdemsky 1.1.2.1 /*Get the loop header and
60 bdemsky 1.1.2.1 make sure that this is a single entrance loop.*/
61 bdemsky 1.1.2.1 Iterator iterate=(lp.loopEntrances()).iterator();
62 ovy 1.1.2.13
63 bdemsky 1.1.2.15 /* throw assertion if loop has no entrance (root loop) */
64 cananian 1.3.2.1 assert !lp.loopEntrances().isEmpty();
65 ovy 1.1.2.13
66 bdemsky 1.1.2.1 Quad header=(Quad) iterate.next();
67 bdemsky 1.1.2.1 if (iterate.hasNext())
68 bdemsky 1.1.2.1 System.out.println("This routine doesn't work on multiple entrance loops");
69 bdemsky 1.1.2.1
70 bdemsky 1.1.2.1 /*Set up Sets and the UseDef map*/
71 bdemsky 1.1.2.1
72 cananian 1.1.2.11 WorkSet excelements=(WorkSet) lp.loopExcElements();
73 cananian 1.1.2.11 WorkSet incelements=(WorkSet) lp.loopIncElements();
74 bdemsky 1.1.2.1 UseDef ud= new UseDef();
75 bdemsky 1.1.2.1 WorkSet adds=new WorkSet();
76 bdemsky 1.1.2.1 WorkSet addp=new WorkSet();
77 bdemsky 1.1.2.1 WorkSet phis=new WorkSet();
78 bdemsky 1.1.2.1
79 bdemsky 1.1.2.1 /* Find phi's and adds in this loop's elements.*/
80 bdemsky 1.1.2.1 BasicVisitor visitor=new BasicVisitor(adds, addp, phis);
81 bdemsky 1.1.2.1 iterate=excelements.iterator();
82 bdemsky 1.1.2.1 while (iterate.hasNext()) {
83 bdemsky 1.1.2.1 Quad q=(Quad)iterate.next();
84 cananian 1.1.2.3 q.accept(visitor);
85 bdemsky 1.1.2.1 }
86 bdemsky 1.1.2.1
87 bdemsky 1.1.2.1
88 bdemsky 1.1.2.1 /* Now lets iterate over the add statements.*/
89 bdemsky 1.1.2.1 iterate=adds.iterator();
90 bdemsky 1.1.2.1 while (iterate.hasNext()) {
91 bdemsky 1.1.2.1
92 bdemsky 1.1.2.1 //Get the add statement
93 bdemsky 1.1.2.6 OPER q=(OPER) iterate.next();
94 bdemsky 1.1.2.1 //debug
95 bdemsky 1.1.2.1 //Find the number of operands it has
96 bdemsky 1.1.2.1 int numofoperands=q.operandsLength();
97 bdemsky 1.1.2.1
98 bdemsky 1.1.2.1 //Set the flag that this is a basic induction
99 bdemsky 1.1.2.1 boolean basicinduction=true;
100 bdemsky 1.1.2.1
101 bdemsky 1.1.2.1 //Make sure the phi links back to us
102 bdemsky 1.1.2.1 boolean tous=false;
103 bdemsky 1.1.2.1
104 bdemsky 1.1.2.1 //Set the corresponding phi pointer to null
105 bdemsky 1.1.2.1 PHI phi=null;
106 bdemsky 1.1.2.1 int k=0;
107 bdemsky 1.1.2.1
108 bdemsky 1.1.2.1 //Loop over the operands in the add statement
109 bdemsky 1.1.2.1 for (int i=0;i<numofoperands;i++) {
110 bdemsky 1.1.2.1
111 bdemsky 1.1.2.1 //Find the SSA temp for the operand
112 bdemsky 1.1.2.1 Temp origin=tm.tempMap(q.operands(i));
113 bdemsky 1.1.2.1 HCodeElement []sources=ud.defMap(hc,origin);
114 bdemsky 1.1.2.1
115 bdemsky 1.1.2.1 //See if our list of phis contains sources[0]
116 bdemsky 1.1.2.1 if (phis.contains(sources[0])) {
117 bdemsky 1.1.2.1
118 bdemsky 1.1.2.1 //Have we already seen a different phi?
119 bdemsky 1.1.2.1 if ((phi!=sources[0])&&(phi!=null)) {
120 bdemsky 1.1.2.1
121 bdemsky 1.1.2.1 //Yep...this isn't a basic induction variable
122 bdemsky 1.1.2.1 basicinduction=false;
123 bdemsky 1.1.2.1 break;
124 bdemsky 1.1.2.1 } else if (phi==null) {
125 bdemsky 1.1.2.1
126 bdemsky 1.1.2.1 //Haven't seen a phi yet!
127 bdemsky 1.1.2.1
128 bdemsky 1.1.2.1 //Set the phi pointer here
129 bdemsky 1.1.2.1 phi=(PHI)sources[0];
130 bdemsky 1.1.2.1
131 bdemsky 1.1.2.1 //If the phi isn't the header, it isn't a basic induction variable
132 bdemsky 1.1.2.1
133 bdemsky 1.1.2.1 if (phi!=header) {
134 bdemsky 1.1.2.1 basicinduction=false;
135 bdemsky 1.1.2.1 break;
136 bdemsky 1.1.2.1 }
137 bdemsky 1.1.2.1
138 bdemsky 1.1.2.1 //We need to search for the phi statement...
139 bdemsky 1.1.2.1 k=0; //Get the right phi statement
140 bdemsky 1.1.2.1 while (origin!=phi.dst(k)) k++;
141 bdemsky 1.1.2.1
142 bdemsky 1.1.2.1 //Get an array of the predecessor edges
143 cananian 1.1.2.7 HCodeEdge[] pred=((CFGraphable) phi).pred();
144 bdemsky 1.1.2.1 //Loop through the edges of this phi
145 bdemsky 1.1.2.1 for (int j=0; j<phi.arity();j++) {
146 bdemsky 1.1.2.1
147 bdemsky 1.1.2.1 //If the loop contians the incoming edge,
148 bdemsky 1.1.2.1 //the phi needs to use our
149 bdemsky 1.1.2.1 if(incelements.contains(pred[j].from())) {
150 bdemsky 1.1.2.1
151 bdemsky 1.1.2.1 //Needs to be = to us!
152 bdemsky 1.1.2.1 if(tm.tempMap(phi.src(k,j))!=q.dst()) {
153 bdemsky 1.1.2.1 //Else it isn't a basic induction variable
154 bdemsky 1.1.2.1 basicinduction=false;
155 bdemsky 1.1.2.1 break;
156 bdemsky 1.1.2.1 } else {
157 bdemsky 1.1.2.1 tous=true;
158 bdemsky 1.1.2.1 }
159 bdemsky 1.1.2.1 }
160 bdemsky 1.1.2.1 }
161 bdemsky 1.1.2.1 }
162 bdemsky 1.1.2.1 } else {
163 bdemsky 1.1.2.1 //If it isn't from a phi, it needs to be loop invariant!!!
164 bdemsky 1.1.2.1 //Look to see if this is loop invariant!
165 bdemsky 1.1.2.1 if ((!invariants.contains(sources[0]))&&(incelements.contains(sources[0]))) {
166 bdemsky 1.1.2.1 //Conditions are that it comes from inside the loop and it isn't
167 bdemsky 1.1.2.1 //loop invariant
168 bdemsky 1.1.2.1
169 bdemsky 1.1.2.1 //We don't have an invariant...no go!
170 bdemsky 1.1.2.1 basicinduction=false;
171 bdemsky 1.1.2.1 break;
172 bdemsky 1.1.2.1 }
173 bdemsky 1.1.2.1 }
174 bdemsky 1.1.2.1 }
175 bdemsky 1.1.2.1 //If it made it through the checks, it is a basic induction variable...
176 bdemsky 1.1.2.1 if (basicinduction&&(phi!=null)&&tous) {
177 bdemsky 1.1.2.1 Induction tmp;
178 bdemsky 1.1.2.1 if (addp.contains(q))
179 bdemsky 1.1.2.2 tmp=new Induction(phi.dst(k),null,true);
180 bdemsky 1.1.2.1 else
181 bdemsky 1.1.2.1 tmp=new Induction(phi.dst(k),0,1);
182 bdemsky 1.1.2.1 basicinductions.put(phi.dst(k),tmp);
183 bdemsky 1.1.2.1 }
184 bdemsky 1.1.2.1 }
185 bdemsky 1.1.2.1 return basicinductions;
186 bdemsky 1.1.2.1 }
187 bdemsky 1.1.2.1
188 bdemsky 1.1.2.1 /** BasicVisitor finds ADD and <code>PHI</code> quads. These
189 bdemsky 1.1.2.1 * are used to find basic induction variables.*/
190 bdemsky 1.1.2.1
191 bdemsky 1.1.2.1 class BasicVisitor extends LowQuadVisitor {
192 bdemsky 1.1.2.1 WorkSet adds,addp;
193 bdemsky 1.1.2.1 WorkSet phis;
194 bdemsky 1.1.2.1
195 bdemsky 1.1.2.1 BasicVisitor(WorkSet adds, WorkSet addp, WorkSet phis) {
196 cananian 1.1.2.9 super(false/*non-strict*/);
197 bdemsky 1.1.2.1 this.adds=adds;
198 bdemsky 1.1.2.1 this.addp=addp;
199 bdemsky 1.1.2.1 this.phis=phis;
200 bdemsky 1.1.2.1 }
201 bdemsky 1.1.2.1
202 bdemsky 1.1.2.1 public void visit(Quad q) {
203 bdemsky 1.1.2.1 //Do nothing
204 bdemsky 1.1.2.1 }
205 bdemsky 1.1.2.4
206 bdemsky 1.1.2.1 public void visit(OPER q) {
207 bdemsky 1.1.2.4 switch (q.opcode()) {
208 bdemsky 1.1.2.4 case Qop.IADD:
209 bdemsky 1.1.2.4 // case Qop.LADD:
210 bdemsky 1.1.2.4 adds.push(q);
211 bdemsky 1.1.2.4 break;
212 bdemsky 1.1.2.4 default:
213 bdemsky 1.1.2.4 }
214 bdemsky 1.1.2.1 }
215 bdemsky 1.1.2.1
216 bdemsky 1.1.2.1 public void visit(POPER q) {
217 bdemsky 1.1.2.1 switch (q.opcode()) {
218 bdemsky 1.1.2.1 case LQop.PADD:
219 bdemsky 1.1.2.1 addp.push(q);//put in both list!
220 bdemsky 1.1.2.1 case Qop.IADD:
221 bdemsky 1.1.2.1 // case Qop.LADD:
222 bdemsky 1.1.2.1 adds.push(q);
223 bdemsky 1.1.2.1 break;
224 bdemsky 1.1.2.1 default:
225 bdemsky 1.1.2.1 }
226 bdemsky 1.1.2.1 }
227 bdemsky 1.1.2.1
228 bdemsky 1.1.2.1 public void visit(PHI q) {
229 bdemsky 1.1.2.1 phis.push(q);
230 bdemsky 1.1.2.1 }
231 bdemsky 1.1.2.1 }
232 bdemsky 1.1.2.1 }
233 cananian 1.2