KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > soot > shimple > internal > SPhiExpr


1 /* Soot - a J*va Optimization Framework
2  * Copyright (C) 2003 Navindra Umanee <navindra@cs.mcgill.ca>
3  *
4  * This library is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU Lesser General Public
6  * License as published by the Free Software Foundation; either
7  * version 2.1 of the License, or (at your option) any later version.
8  *
9  * This library is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12  * Lesser General Public License for more details.
13  *
14  * You should have received a copy of the GNU Lesser General Public
15  * License along with this library; if not, write to the
16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17  * Boston, MA 02111-1307, USA.
18  */

19
20 package soot.shimple.internal;
21
22 import soot.*;
23 import soot.shimple.*;
24 import soot.jimple.*;
25 import soot.jimple.internal.*;
26 import soot.util.*;
27 import java.util.*;
28 import soot.toolkits.scalar.*;
29 import soot.toolkits.graph.*;
30
31 /**
32  * Internal implementation of Phi nodes.
33  *
34  * @author Navindra Umanee
35  * @see soot.shimple.PhiExpr
36  **/

37 public class SPhiExpr implements PhiExpr
38 {
39     protected List argPairs = new ArrayList();
40     protected Map predToPair = new HashMap(); // cache
41
protected Type type;
42     
43     /**
44      * Create a trivial Phi expression for leftLocal. preds is an ordered
45      * list of the control flow predecessor Blocks of the PhiExpr.
46      **/

47     public SPhiExpr(Local leftLocal, List preds)
48     {
49         type = leftLocal.getType();
50
51         Iterator predsIt = preds.iterator();
52         while(predsIt.hasNext())
53         {
54             Object JavaDoc pred = predsIt.next();
55
56             if(pred instanceof Block)
57                 addArg(leftLocal, (Block)pred);
58             else if(pred instanceof Unit)
59                 addArg(leftLocal, (Unit)pred);
60             else
61                 throw new RuntimeException JavaDoc("Must be a CFG block or tail unit.");
62         }
63     }
64
65     /**
66      * Create a Phi expression from the given list of Values and Blocks.
67      **/

68     public SPhiExpr(List args, List preds)
69     {
70         if(args.size() == 0)
71             throw new RuntimeException JavaDoc("Arg list may not be empty");
72         
73         if(args.size() != preds.size())
74             throw new RuntimeException JavaDoc("Arg list does not match Pred list");
75
76         type = ((Value) args.get(0)).getType();
77         Iterator argsIt = args.iterator();
78         Iterator predsIt = preds.iterator();
79
80         while(argsIt.hasNext()){
81             Value arg = (Value) argsIt.next();
82             Object JavaDoc pred = predsIt.next();
83
84             if(pred instanceof Block)
85                 addArg(arg, (Block)pred);
86             else if(pred instanceof Unit)
87                 addArg(arg, (Unit)pred);
88             else
89                 throw new RuntimeException JavaDoc("Must be a CFG block or tail unit.");
90         }
91     }
92
93     /* get-accessor implementations */
94     
95     public List getArgs()
96     {
97         return Collections.unmodifiableList(argPairs);
98     }
99
100     public List getValues()
101     {
102         List args = new ArrayList();
103         Iterator argPairsIt = argPairs.iterator();
104
105         while(argPairsIt.hasNext()){
106             Value arg = ((ValueUnitPair)argPairsIt.next()).getValue();
107             args.add(arg);
108         }
109         
110         return args;
111     }
112
113     public List getPreds()
114     {
115         List preds = new ArrayList();
116         Iterator argPairsIt = argPairs.iterator();
117
118         while(argPairsIt.hasNext()){
119             Unit arg = ((ValueUnitPair)argPairsIt.next()).getUnit();
120             preds.add(arg);
121         }
122         
123         return preds;
124     }
125
126     public int getArgCount()
127     {
128         return argPairs.size();
129     }
130
131     public ValueUnitPair getArgBox(int index)
132     {
133         if(index < 0 || index >= argPairs.size())
134             return null;
135         return (ValueUnitPair) argPairs.get(index);
136     }
137     
138     public Value getValue(int index)
139     {
140         ValueUnitPair arg = getArgBox(index);
141         if(arg == null)
142             return null;
143         return arg.getValue();
144     }
145
146     public Unit getPred(int index)
147     {
148         ValueUnitPair arg = getArgBox(index);
149         if(arg == null)
150             return null;
151         return arg.getUnit();
152     }
153
154     public int getArgIndex(Unit predTailUnit)
155     {
156         ValueUnitPair pair = getArgBox(predTailUnit);
157         return argPairs.indexOf(pair); // (-1 on null)
158
}
159
160     public ValueUnitPair getArgBox(Unit predTailUnit)
161     {
162         ValueUnitPair vup = (ValueUnitPair) predToPair.get(predTailUnit);
163
164         // we pay a penalty for misses but hopefully the common case
165
// is faster than an iteration over argPairs every time
166
if(vup == null || vup.getUnit() != predTailUnit){
167             updateCache();
168             vup = (ValueUnitPair) predToPair.get(predTailUnit);
169             if((vup != null) && (vup.getUnit() != predTailUnit))
170                 throw new RuntimeException JavaDoc("Assertion failed.");
171         }
172
173         // (null if not found)
174
return vup;
175     }
176     
177     public Value getValue(Unit predTailUnit)
178     {
179         ValueBox vb = getArgBox(predTailUnit);
180         if(vb == null)
181             return null;
182         return vb.getValue();
183     }
184
185     public int getArgIndex(Block pred)
186     {
187         ValueUnitPair box = getArgBox(pred);
188         return argPairs.indexOf(box); // (-1 on null)
189
}
190
191     public ValueUnitPair getArgBox(Block pred)
192     {
193         Unit predTailUnit = pred.getTail();
194         ValueUnitPair box = getArgBox(predTailUnit);
195
196         // workaround added for internal cases where the predTailUnit
197
// may not be at the end of the predecessor block
198
// (eg, fall-through pointer not moved)
199
while(box == null){
200             predTailUnit = pred.getPredOf(predTailUnit);
201             if(predTailUnit == null)
202                 break;
203             box = getArgBox(predTailUnit);
204         }
205
206         return box;
207     }
208
209     public Value getValue(Block pred)
210     {
211         ValueBox vb = getArgBox(pred);
212         if(vb == null)
213             return null;
214         return vb.getValue();
215     }
216
217     /* set-accessor implementations */
218     
219     public boolean setArg(int index, Value arg, Unit predTailUnit)
220     {
221         boolean ret1 = setValue(index, arg);
222         boolean ret2 = setPred(index, predTailUnit);
223         if(ret1 != ret2)
224             throw new RuntimeException JavaDoc("Assertion failed.");
225         return ret1;
226     }
227     
228     public boolean setArg(int index, Value arg, Block pred)
229     {
230         return setArg(index, arg, pred.getTail());
231     }
232     
233     public boolean setValue(int index, Value arg)
234     {
235         ValueUnitPair argPair = getArgBox(index);
236         if(argPair == null)
237             return false;
238         argPair.setValue(arg);
239         return true;
240     }
241
242     public boolean setValue(Unit predTailUnit, Value arg)
243     {
244         int index = getArgIndex(predTailUnit);
245         return setValue(index, arg);
246     }
247
248     public boolean setValue(Block pred, Value arg)
249     {
250         int index = getArgIndex(pred);
251         return setValue(index, arg);
252     }
253
254     public boolean setPred(int index, Unit predTailUnit)
255     {
256         ValueUnitPair argPair = getArgBox(index);
257         if(argPair == null)
258             return false;
259
260         int other = getArgIndex(predTailUnit);
261         if(other != -1){
262             G.v().out.println("WARNING: An argument with control flow predecessor " + predTailUnit + " already exists in " + this + "!");
263             G.v().out.println("WARNING: setPred resulted in deletion of " + argPair + " from " + this + ".");
264             removeArg(argPair);
265             return false;
266         }
267
268         argPair.setUnit(predTailUnit);
269         return true;
270     }
271
272     public boolean setPred(int index, Block pred)
273     {
274         return setPred(index, pred.getTail());
275     }
276     
277     /* add/remove implementations */
278     
279     public boolean removeArg(int index)
280     {
281         ValueUnitPair arg = getArgBox(index);
282         return removeArg(arg);
283     }
284
285     public boolean removeArg(Unit predTailUnit)
286     {
287         ValueUnitPair arg = getArgBox(predTailUnit);
288         return removeArg(arg);
289     }
290
291     public boolean removeArg(Block pred)
292     {
293         ValueUnitPair arg = getArgBox(pred);
294         return removeArg(arg);
295     }
296     
297     public boolean removeArg(ValueUnitPair arg)
298     {
299         if(argPairs.remove(arg)){
300             // update cache
301
predToPair.remove(arg.getUnit());
302             // remove back-pointer
303
arg.getUnit().removeBoxPointingToThis(arg);
304             return true;
305         }
306         
307         return false;
308     }
309
310     public boolean addArg(Value arg, Block pred)
311     {
312         return addArg(arg, pred.getTail());
313     }
314     
315     public boolean addArg(Value arg, Unit predTailUnit)
316     {
317         // we have no choice but to flush the cache
318
updateCache();
319
320         // we disallow duplicate arguments
321
if(predToPair.keySet().contains(predTailUnit))
322             return false;
323
324         ValueUnitPair vup = new SValueUnitPair(arg, predTailUnit);
325
326         // add and update cache
327
argPairs.add(vup);
328         predToPair.put(predTailUnit, vup);
329         return true;
330     }
331
332     int blockId = -1;
333
334     public void setBlockId(int blockId)
335     {
336         this.blockId = blockId;
337     }
338
339     public int getBlockId()
340     {
341         if(blockId == -1)
342             throw new RuntimeException JavaDoc("Assertion failed: Block Id unknown.");
343         return blockId;
344     }
345     
346     /* misc */
347
348     /**
349      * Update predToPair cache map which could be out-of-sync due to
350      * external setUnit or clone operations on the UnitBoxes.
351      **/

352     protected void updateCache()
353     {
354         predToPair = new HashMap();
355         Iterator pairsIt = argPairs.iterator();
356         while(pairsIt.hasNext()){
357             ValueUnitPair vup = (ValueUnitPair) pairsIt.next();
358             predToPair.put(vup.getUnit(), vup);
359         }
360     }
361
362     public boolean equivTo(Object JavaDoc o)
363     {
364         if(o instanceof SPhiExpr){
365             SPhiExpr pe = (SPhiExpr) o;
366
367             if(getArgCount() != pe.getArgCount())
368                 return false;
369
370             for(int i = 0; i < getArgCount(); i++){
371                 if(!getArgBox(i).equivTo(pe.getArgBox(i)))
372                     return false;
373             }
374
375             return true;
376         }
377
378         return false;
379     }
380
381     public int equivHashCode()
382     {
383         int hashcode = 1;
384         
385         for(int i = 0; i < getArgCount(); i++){
386             hashcode = hashcode * 17 + getArgBox(i).equivHashCode();
387         }
388
389         return hashcode;
390     }
391
392     public List getUnitBoxes()
393     {
394         return argPairs;
395     }
396
397     public void clearUnitBoxes()
398     {
399         Iterator boxesIt = getUnitBoxes().iterator();
400         while(boxesIt.hasNext()){
401             UnitBox box = (UnitBox) boxesIt.next();
402             box.setUnit(null);
403         }
404     }
405     
406     public List getUseBoxes()
407     {
408         Set set = new HashSet();
409
410         Iterator argPairsIt = argPairs.iterator();
411
412         while(argPairsIt.hasNext()){
413             ValueUnitPair argPair = (ValueUnitPair) argPairsIt.next();
414             set.addAll(argPair.getValue().getUseBoxes());
415             set.add(argPair);
416         }
417
418         return new ArrayList(set);
419     }
420
421     public Type getType()
422     {
423         return type;
424     }
425
426     public String JavaDoc toString()
427     {
428         StringBuffer JavaDoc expr = new StringBuffer JavaDoc(Shimple.PHI + "(");
429         Iterator argPairsIt = argPairs.iterator();
430
431         while(argPairsIt.hasNext()){
432             ValueUnitPair vuPair = (ValueUnitPair)argPairsIt.next();
433             Value arg = vuPair.getValue();
434             expr.append(arg.toString());
435
436             if(argPairsIt.hasNext())
437                 expr.append(", ");
438         }
439
440         expr.append(")");
441
442         return expr.toString();
443     }
444     
445     public void toString(UnitPrinter up)
446     {
447         up.literal(Shimple.PHI);
448         up.literal("(");
449
450         Iterator argPairsIt = argPairs.iterator();
451         while(argPairsIt.hasNext()){
452             ValueUnitPair vuPair = (ValueUnitPair)argPairsIt.next();
453             vuPair.toString(up);
454
455             if(argPairsIt.hasNext())
456                 up.literal(", ");
457         }
458
459         up.literal(")");
460     }
461         
462     public void apply(Switch sw)
463     {
464         ((ShimpleExprSwitch) sw).casePhiExpr(this);
465     }
466
467     public Object JavaDoc clone()
468     {
469         // Note to self: Do not try to "fix" this *again*. Yes, it
470
// should be a shallow copy in order to conform with the rest
471
// of Soot. When a body is cloned, the Values are cloned
472
// explicitly and replaced, and UnitBoxes are explicitly
473
// patched. See Body.importBodyContentsFrom for details.
474
return new SPhiExpr(getValues(), getPreds());
475     }
476 }
477
Popular Tags