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   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  ("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  ("Arg list may not be empty");
72          
73          if(args.size() != preds.size())
74              throw new RuntimeException  ("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   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  ("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  ("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  ("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  ("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   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   toString()
427     {
428         StringBuffer   expr = new StringBuffer  (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   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
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags