1 cananian 1.1.2.1 // SSIToSSAMap.java, created Thu Jun 17 16:11:41 1999 by root
2 cananian 1.1.2.1 // Copyright (C) 1999 Brian Demsky <bdemsky@mit.edu>
3 cananian 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 cananian 1.1.2.1 package harpoon.Analysis.Quads;
5 cananian 1.1.2.1 import harpoon.Temp.TempMap;
6 cananian 1.1.2.1 import harpoon.Temp.Temp;
7 cananian 1.3 import net.cscott.jutil.WorkSet;
8 cananian 1.1.2.1 import harpoon.IR.LowQuad.LowQuadVisitor;
9 cananian 1.1.2.1 import harpoon.IR.Quads.AGET;
10 cananian 1.1.2.1 import harpoon.IR.Quads.ASET;
11 cananian 1.1.2.1 import harpoon.IR.Quads.GET;
12 cananian 1.1.2.1 import harpoon.IR.Quads.HANDLER;
13 cananian 1.1.2.1 import harpoon.IR.Quads.OPER;
14 cananian 1.1.2.1 import harpoon.IR.Quads.PHI;
15 cananian 1.1.2.1 import harpoon.IR.Quads.Quad;
16 cananian 1.1.2.1 import harpoon.IR.Quads.SET;
17 cananian 1.1.2.1 import harpoon.IR.Quads.SIGMA;
18 cananian 1.1.2.1 import harpoon.ClassFile.HCode;
19 cananian 1.1.2.1
20 cananian 1.1.2.1 import java.util.HashMap;
21 cananian 1.1.2.1 import java.util.Iterator;
22 cananian 1.1.2.1 import java.util.Set;
23 cananian 1.1.2.1 /**
24 cananian 1.1.2.1 * An <code>SSIToSSAMap</code> allows you to look at an SSI
25 cananian 1.1.2.1 * representation "with glasses on" so that it appears as SSA. This
26 cananian 1.1.2.1 * is often useful when the additional value-information
27 cananian 1.1.2.1 * discrimination of SSI form is unnecessary, but converting the input
28 cananian 1.1.2.1 * to SSA is undesirable.
29 cananian 1.1.2.1 *
30 cananian 1.1.2.1 * @author Brian Demsky <bdemsky@mit.edu>
31 cananian 1.4 * @version $Id: SSIToSSAMap.java,v 1.4 2004/02/08 03:20:10 cananian Exp $
32 cananian 1.1.2.1 */
33 cananian 1.1.2.1 public class SSIToSSAMap implements TempMap {
34 cananian 1.1.2.1
35 cananian 1.1.2.1 /** Creates a <code>SSIToSSAMap</code> for the <code>HCode</code>
36 cananian 1.1.2.1 * <code>hc</code>. */
37 cananian 1.1.2.1 public SSIToSSAMap(HCode hc) {
38 cananian 1.1.2.1 //We need to build to map in the constructor
39 cananian 1.1.2.1 //Set HCode pointer
40 cananian 1.1.2.1 this.hc=hc;
41 cananian 1.1.2.1
42 cananian 1.1.2.1 //Set forward SSI->SSA Map
43 cananian 1.1.2.1 this.forward=new HashMap();
44 cananian 1.1.2.1
45 cananian 1.1.2.1 //Set backward SSA->set of SSI Temps Map
46 cananian 1.1.2.1 this.backward=new HashMap();
47 cananian 1.1.2.1
48 cananian 1.1.2.1 //List of sigmas
49 cananian 1.1.2.1 this.sigmas=new WorkSet();
50 cananian 1.1.2.1
51 cananian 1.1.2.1 //List of phis
52 cananian 1.1.2.1 this.phis=new WorkSet();
53 cananian 1.1.2.1
54 cananian 1.1.2.1 //List of phi destinations
55 cananian 1.1.2.1 this.phiresults=new WorkSet();
56 cananian 1.1.2.1
57 cananian 1.1.2.1 //Build the map
58 cananian 1.1.2.1 buildmap();
59 cananian 1.1.2.1 //debug();
60 cananian 1.1.2.1 }
61 cananian 1.1.2.1
62 cananian 1.1.2.1 void debug() {
63 cananian 1.1.2.1 //Print out the map
64 cananian 1.1.2.1 Set W=forward.keySet();
65 cananian 1.4 for (Object tO : W) {
66 cananian 1.4 Temp t = (Temp) tO;
67 cananian 1.1.2.1 Temp tt=(Temp)forward.get(t);
68 cananian 1.1.2.1 System.out.println(t.toString()+"--->"+tt.toString());
69 cananian 1.1.2.1 }
70 cananian 1.1.2.1 }
71 cananian 1.1.2.1
72 cananian 1.1.2.1 void buildmap() {
73 cananian 1.1.2.1 //Find all of the Sigmas and Phis
74 cananian 1.1.2.1 findSigmaPhis();
75 cananian 1.1.2.1
76 cananian 1.1.2.1 //Add the Sigmas into the map
77 cananian 1.1.2.1 addSigmas();
78 cananian 1.1.2.1
79 cananian 1.1.2.1 //Add the Phis into the map
80 cananian 1.1.2.1 addPhis();
81 cananian 1.1.2.1 }
82 cananian 1.1.2.1
83 cananian 1.1.2.1 void addSigmas() {
84 cananian 1.1.2.1 //Iterate over the set of sigmas
85 cananian 1.1.2.1
86 cananian 1.1.2.1 Iterator iterate=sigmas.iterator();
87 cananian 1.1.2.1 while (iterate.hasNext()) {
88 cananian 1.1.2.1
89 cananian 1.1.2.1 //Put the current SIGMA object in sigma
90 cananian 1.1.2.1 SIGMA sigma=(SIGMA) iterate.next();
91 cananian 1.1.2.1 int numbersigmas=sigma.numSigmas();
92 cananian 1.1.2.1 int splitting=sigma.arity();
93 cananian 1.1.2.1
94 cananian 1.1.2.1 //Loop over each individual sigma in it
95 cananian 1.1.2.1 for (int i=0;i<numbersigmas;i++) {
96 cananian 1.1.2.1
97 cananian 1.1.2.1
98 cananian 1.1.2.1 Temp tmpsrc;
99 cananian 1.1.2.1 WorkSet backset;
100 cananian 1.1.2.1
101 cananian 1.1.2.1 //Need to see if the source of the sigma is already in our map
102 cananian 1.1.2.1 if (forward.get(sigma.src(i))!=null) {
103 cananian 1.1.2.1
104 cananian 1.1.2.1 //If so, we need to look at its source to get
105 cananian 1.1.2.1 //the original SSA assignment
106 cananian 1.1.2.1 tmpsrc=(Temp)forward.get(sigma.src(i));
107 cananian 1.1.2.1
108 cananian 1.1.2.1 //We also need to get its backset to add the
109 cananian 1.1.2.1 //destinations of our sigmas to
110 cananian 1.1.2.1 backset=(WorkSet)backward.get(tmpsrc);
111 cananian 1.1.2.1 }
112 cananian 1.1.2.1 else {
113 cananian 1.1.2.1 //The source isn't in the map
114 cananian 1.1.2.1 //Create a new backwards entry for it
115 cananian 1.1.2.1 if (backward.containsKey(sigma.src(i))) {
116 cananian 1.1.2.1 backset=(WorkSet)backward.get(sigma.src(i));
117 cananian 1.1.2.1 }
118 cananian 1.1.2.1 else {
119 cananian 1.1.2.1 backset=new WorkSet();
120 cananian 1.1.2.1
121 cananian 1.1.2.1 //Push this entry in the backwards map
122 cananian 1.1.2.1 backward.put(sigma.src(i), backset);
123 cananian 1.1.2.1 }
124 cananian 1.1.2.1
125 cananian 1.1.2.1 //Set the source up for the destinations of the sigmas
126 cananian 1.1.2.1 tmpsrc=sigma.src(i);
127 cananian 1.1.2.1 }
128 cananian 1.1.2.1 for (int j=0;j<splitting;j++) {
129 cananian 1.1.2.1 //src(i)--><dst(i,0),dst(i,1)...dst(i,splitting)>
130 cananian 1.1.2.1
131 cananian 1.1.2.1 //Put us in the forward map
132 cananian 1.1.2.1 forward.put((Temp)sigma.dst(i,j),tmpsrc);
133 cananian 1.1.2.1
134 cananian 1.1.2.1 //Add us to the set of things referencing tmpsrc
135 cananian 1.1.2.1 backset.push((Temp)sigma.dst(i,j));
136 cananian 1.1.2.1
137 cananian 1.1.2.1 //look for nodes referencing us
138 cananian 1.1.2.1 WorkSet back=(WorkSet)backward.get(sigma.dst(i,j));
139 cananian 1.1.2.1
140 cananian 1.1.2.1 if (back!=null) {
141 cananian 1.1.2.1 //get rid of our backward reference set
142 cananian 1.1.2.1 backward.remove(sigma.dst(i,j));
143 cananian 1.1.2.1
144 cananian 1.1.2.1 //Iterate through temps referencing us
145 cananian 1.4 for (Object tO : back) {
146 cananian 1.4 Temp t = (Temp) tO;
147 cananian 1.1.2.1
148 cananian 1.1.2.1 //Fix their forward map
149 cananian 1.1.2.1 forward.put(t,tmpsrc);
150 cananian 1.1.2.1 //Add them to the set referencing tmpsrc
151 cananian 1.1.2.1 backset.push(t);
152 cananian 1.1.2.1 }
153 cananian 1.1.2.1 }
154 cananian 1.1.2.1 }
155 cananian 1.1.2.1 }
156 cananian 1.1.2.1 }
157 cananian 1.1.2.1 }
158 cananian 1.1.2.1
159 cananian 1.1.2.1 void addPhis() {
160 cananian 1.1.2.1 boolean dirty=true;
161 cananian 1.1.2.1 //Iterate through the phi's until we stop
162 cananian 1.1.2.1 //adding phi's into our maps
163 cananian 1.1.2.1 while (dirty) {
164 cananian 1.1.2.1 dirty=false;
165 cananian 1.1.2.1
166 cananian 1.1.2.1
167 cananian 1.1.2.1 Iterator iterate = phis.iterator();
168 cananian 1.1.2.1 while (iterate.hasNext()) {
169 cananian 1.1.2.1 //Put the next phi in a variable
170 cananian 1.1.2.1 InternalPhi nxtPhi=(InternalPhi)iterate.next();
171 cananian 1.1.2.1
172 cananian 1.1.2.1 //Phi's with only one unique definition
173 cananian 1.1.2.1 //Can be eliminated
174 cananian 1.1.2.1 Temp uniquedef=null;
175 cananian 1.1.2.1
176 cananian 1.1.2.1 //Set flag that keeps track of whether we can
177 cananian 1.1.2.1 //put this phi in our mapping
178 cananian 1.1.2.1 boolean good=true;
179 cananian 1.1.2.1
180 cananian 1.1.2.1 //Set this boolean to flag if
181 cananian 1.1.2.1 //we have a definition from outside
182 cananian 1.1.2.1 //the set {phi destinations, sigma destinations}
183 cananian 1.1.2.1
184 cananian 1.1.2.1 boolean outsidedef=false;
185 cananian 1.1.2.1
186 cananian 1.1.2.1 //Loop through each phi src arguement
187 cananian 1.1.2.1
188 cananian 1.1.2.1 for (int i=0;i<nxtPhi.src.length;i++) {
189 cananian 1.1.2.1
190 cananian 1.1.2.1 //Possible Conditions:
191 cananian 1.1.2.1 //1) All sources are either the destination of the Phi
192 cananian 1.1.2.1 //or one unique Temp
193 cananian 1.1.2.1 //Then add this phi to our mapping
194 cananian 1.1.2.1 //
195 cananian 1.1.2.1 //2) One source is not in the set {phi destinations,
196 cananian 1.1.2.1 //sigma sources, sigma destinations}
197 cananian 1.1.2.1 //
198 cananian 1.1.2.1 //
199 cananian 1.1.2.1 //3) Two sources are not in the set
200 cananian 1.1.2.1 //{phi destination, sigma destinations}
201 cananian 1.1.2.1 //Useless phi, toss it!
202 cananian 1.1.2.1
203 cananian 1.1.2.1 if (forward.containsKey(nxtPhi.src[i])) {
204 cananian 1.1.2.1 //This phi is in our forward mapping already
205 cananian 1.1.2.1 Temp tmp=(Temp)forward.get(nxtPhi.src[i]);
206 cananian 1.1.2.1
207 cananian 1.1.2.1 //Check to see if this references our destination
208 cananian 1.1.2.1 //if so just ignore it
209 cananian 1.1.2.1 if (tmp!=nxtPhi.dst) {
210 cananian 1.1.2.1 //If not, we need to see if we already have found an unique reference
211 cananian 1.1.2.1 if (uniquedef==null)
212 cananian 1.1.2.1 //if not, set Temp to this reference
213 cananian 1.1.2.1 uniquedef=tmp;
214 cananian 1.1.2.1 else {
215 cananian 1.1.2.1 //If we have found one already, see if they are the same one
216 cananian 1.1.2.1 if (uniquedef!=tmp) {
217 cananian 1.1.2.1 //Nope... Set flag, and break out of here
218 cananian 1.1.2.1 good=false;
219 cananian 1.1.2.1 break;
220 cananian 1.1.2.1 }
221 cananian 1.1.2.1 }
222 cananian 1.1.2.1 }
223 cananian 1.1.2.1 } else {
224 cananian 1.1.2.1 if (!phiresults.contains(nxtPhi.src[i])) {
225 cananian 1.1.2.1 //Approach here is to get useless nodes out of our list to speed up iterations
226 cananian 1.1.2.1
227 cananian 1.1.2.1 if (outsidedef) {
228 cananian 1.1.2.1 //If we already have a unique outside definition, trash this one
229 cananian 1.1.2.1 if(uniquedef!=nxtPhi.src[i]) {
230 cananian 1.1.2.1 phiresults.remove(nxtPhi.dst);
231 cananian 1.1.2.1 good=false;
232 cananian 1.1.2.1 iterate.remove();
233 cananian 1.1.2.1 break;
234 cananian 1.1.2.1 }
235 cananian 1.1.2.1 } else {
236 cananian 1.1.2.1 //Make this out unique definition
237 cananian 1.1.2.1 outsidedef=true;
238 cananian 1.1.2.1
239 cananian 1.1.2.1 if (uniquedef==null)
240 cananian 1.1.2.1 //Good we don't have a def yet
241 cananian 1.1.2.1 uniquedef=nxtPhi.src[i];
242 cananian 1.1.2.1 else {
243 cananian 1.1.2.1 //we already have one, is it the same?
244 cananian 1.1.2.1 if (uniquedef!=nxtPhi.src[i]) {
245 cananian 1.1.2.1 //nope...toss it back to the pool
246 cananian 1.1.2.1 good=false;
247 cananian 1.1.2.1 break;
248 cananian 1.1.2.1 }
249 cananian 1.1.2.1 }
250 cananian 1.1.2.1 }
251 cananian 1.1.2.1 } else {
252 cananian 1.1.2.1 //This one has a src that is in the Phi pool
253 cananian 1.1.2.1 if (nxtPhi.src[i]!=nxtPhi.dst) {
254 cananian 1.1.2.1 //Make sure it isn't ourself
255 cananian 1.1.2.1 if (uniquedef==null)
256 cananian 1.1.2.1 //Store a uniquedef
257 cananian 1.1.2.1 uniquedef=nxtPhi.src[i];
258 cananian 1.1.2.1 else {
259 cananian 1.1.2.1 //We have a uniquedef, see if they are the same
260 cananian 1.1.2.1 if (uniquedef!=nxtPhi.src[i]) {
261 cananian 1.1.2.1 //Toss it back into the pool for the next iteration
262 cananian 1.1.2.1 good=false;
263 cananian 1.1.2.1 break;
264 cananian 1.1.2.1 }
265 cananian 1.1.2.1 }
266 cananian 1.1.2.1 }
267 cananian 1.1.2.1 }
268 cananian 1.1.2.1 }
269 cananian 1.1.2.1 }
270 cananian 1.1.2.1 if (good) {
271 cananian 1.1.2.1 //Set the dirty flag to true for another pass
272 cananian 1.1.2.1 dirty=true;
273 cananian 1.1.2.1
274 cananian 1.1.2.1 phiresults.remove(nxtPhi.dst);
275 cananian 1.1.2.1
276 cananian 1.1.2.1 //Get rid of this phi in the phi WorkSet
277 cananian 1.1.2.1 iterate.remove();
278 cananian 1.1.2.1
279 cananian 1.1.2.1 //Need to look for references looking at our destination
280 cananian 1.1.2.1 if (backward.containsKey(nxtPhi.dst)) {
281 cananian 1.1.2.1 //Fix each of them
282 cananian 1.1.2.1 WorkSet tmp=(WorkSet)backward.get(nxtPhi.dst);
283 cananian 1.1.2.1 Iterator iterat=tmp.iterator();
284 cananian 1.1.2.1 Temp dest;
285 cananian 1.1.2.1 //Correct the forward references
286 cananian 1.1.2.1 while(iterat.hasNext()) {
287 cananian 1.1.2.1 forward.put(iterat.next(),uniquedef);
288 cananian 1.1.2.1 }
289 cananian 1.1.2.1
290 cananian 1.1.2.1 //Make a new super set of people looking at uniquedef
291 cananian 1.1.2.1 WorkSet tmp2;
292 cananian 1.1.2.1 if (backward.containsKey(uniquedef))
293 cananian 1.1.2.1 tmp2=(WorkSet)backward.get(uniquedef);
294 cananian 1.1.2.1 else
295 cananian 1.1.2.1 tmp2=new WorkSet();
296 cananian 1.1.2.1
297 cananian 1.1.2.1 //Add the set of people looking at us to this new set
298 cananian 1.1.2.1 iterat=tmp.iterator();
299 cananian 1.1.2.1 while(iterat.hasNext()) {
300 cananian 1.1.2.1 tmp2.push((Temp)iterat.next());
301 cananian 1.1.2.1 }
302 cananian 1.1.2.1
303 cananian 1.1.2.1 //Add us into the set
304 cananian 1.1.2.1 tmp2.push(nxtPhi.dst);
305 cananian 1.1.2.1 //Hand off the new set
306 cananian 1.1.2.1 backward.put(uniquedef,tmp2);
307 cananian 1.1.2.1 //No one is referencing us anymore....tell the backward list
308 cananian 1.1.2.1 backward.remove(nxtPhi.dst);
309 cananian 1.1.2.1 //Add out forward link
310 cananian 1.1.2.1 forward.put(nxtPhi.dst, uniquedef);
311 cananian 1.1.2.1 } else {
312 cananian 1.1.2.1 //Just add us...
313 cananian 1.1.2.1 forward.put(nxtPhi.dst,uniquedef);
314 cananian 1.1.2.1 if (backward.containsKey(uniquedef)) {
315 cananian 1.1.2.1 //Set of references to uniquedef exist, add us
316 cananian 1.1.2.1 ((WorkSet)backward.get(uniquedef)).push(nxtPhi.dst);
317 cananian 1.1.2.1 } else {
318 cananian 1.1.2.1 //No set exist, create on with us in it...
319 cananian 1.1.2.1 WorkSet us=new WorkSet();
320 cananian 1.1.2.1 us.push(nxtPhi.dst);
321 cananian 1.1.2.1 backward.put(uniquedef,us);
322 cananian 1.1.2.1 }
323 cananian 1.1.2.1 }
324 cananian 1.1.2.1 }
325 cananian 1.1.2.1 }
326 cananian 1.1.2.1 }
327 cananian 1.1.2.1 }
328 cananian 1.1.2.1
329 cananian 1.1.2.1 void findSigmaPhis() {
330 cananian 1.1.2.1 LowQuadVisitor visitor = new LowQuadVisitor(false/*non-strict*/) {
331 cananian 1.1.2.1 public void visit(Quad q) {
332 cananian 1.1.2.1 }
333 cananian 1.1.2.1
334 cananian 1.1.2.1 public void visit(SIGMA q) {
335 cananian 1.1.2.1 sigmas.push(q);
336 cananian 1.1.2.1 }
337 cananian 1.1.2.1
338 cananian 1.1.2.1 public void visit(PHI q) {
339 cananian 1.1.2.1 //create list of phi temps
340 cananian 1.1.2.1 int numberofphis=q.numPhis();
341 cananian 1.1.2.1 for (int i=0;i<numberofphis;i++) {
342 cananian 1.1.2.1 phiresults.push(q.dst(i));
343 cananian 1.1.2.1 phis.push(new InternalPhi(q.src(i),q.dst(i)));
344 cananian 1.1.2.1 }
345 cananian 1.1.2.1 }
346 cananian 1.1.2.1 };
347 cananian 1.1.2.1
348 cananian 1.1.2.1 Iterator iterate=hc.getElementsI();
349 cananian 1.1.2.1 while (iterate.hasNext()) {
350 cananian 1.1.2.1 Quad thisone=(Quad) iterate.next();
351 cananian 1.1.2.1 thisone.accept(visitor);
352 cananian 1.1.2.1 }
353 cananian 1.1.2.1 }
354 cananian 1.1.2.1
355 cananian 1.1.2.1 public Temp tempMap(Temp t) {
356 cananian 1.1.2.1 if (forward.containsKey(t))
357 cananian 1.1.2.1 return ((Temp)forward.get(t));
358 cananian 1.1.2.1 else
359 cananian 1.1.2.1 return t;
360 cananian 1.1.2.1 }
361 cananian 1.1.2.1
362 cananian 1.1.2.1 private class InternalPhi {
363 cananian 1.1.2.1 public Temp [] src;
364 cananian 1.1.2.1 public Temp dst;
365 cananian 1.1.2.1 InternalPhi (Temp [] src, Temp dst) {
366 cananian 1.1.2.1 this.src=src;
367 cananian 1.1.2.1 this.dst=dst;
368 cananian 1.1.2.1 }
369 cananian 1.1.2.1 }
370 cananian 1.1.2.1
371 cananian 1.1.2.1 HCode hc;
372 cananian 1.1.2.1 HashMap forward;
373 cananian 1.1.2.1 HashMap backward;
374 cananian 1.1.2.1 WorkSet sigmas;
375 cananian 1.1.2.1 WorkSet phis;
376 cananian 1.1.2.1 WorkSet phiresults;
377 cananian 1.1.2.1 }
378 cananian 1.1.2.1
379 cananian 1.1.2.1
380 cananian 1.2