Shimple


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;
21  
22  import soot.*;
23  import soot.options.Options;
24  import soot.jimple.*;
25  import soot.shimple.internal.*;
26  import soot.util.*;
27  import soot.toolkits.scalar.ValueUnitPair;
28  import java.util.*;
29  import java.io.*;
30  
31  /**
32   * Contains the constructors for the components of the SSA Shimple
33   * grammar.  Methods are available to construct Shimple from
34   * Jimple/Shimple, create Phi nodes, and converting back from
35   * Shimple to Jimple.
36   *
37   * <p> This should normally be used in conjunction with the
38   * constructor methods from soot.jimple.Jimple.
39   *
40   * <p> Miscellaneous utility functions are also available in this
41   * class.
42   *
43   * @author Navindra Umanee
44   * @see soot.jimple.Jimple
45   * @see <a
46   * HREF="http://citeseer.nj.nec.com/cytron91efficiently.html">Efficiently
47   * Computing Static Single Assignment Form and the Control Dependence
48   * Graph</a>
49  **/
50  public class Shimple
51  {
52      public static final String   IFALIAS = "IfAlias";
53      public static final String   MAYMODIFY = "MayModify";
54      public static final String   PHI = "Phi";
55      public static final String   PI = "Pi";
56      public static final String   PHASE = "shimple";
57      
58      public Shimple(Singletons.Global g) {}
59  
60      public static Shimple v()
61      { return G.v().soot_shimple_Shimple(); }
62  
63      /**
64       * Returns an empty ShimpleBody associated with method m, using
65       * default phase options.
66       **/
67      public ShimpleBody newBody(SootMethod m)
68      {
69          Map options = PhaseOptions.v().getPhaseOptions(PHASE);
70          return new ShimpleBody(m, options);
71      }
72  
73      /**
74       * Returns an empty ShimpleBody associated with method m, using
75       * provided option map.
76       **/
77      public ShimpleBody newBody(SootMethod m, Map options)
78      {
79          return new ShimpleBody(m, options);
80      }
81  
82      /**
83       * Returns a ShimpleBody constructed from b, using default phase
84       * options.
85       **/
86      public ShimpleBody newBody(Body b)
87      {
88          Map options = PhaseOptions.v().getPhaseOptions(PHASE);
89          return new ShimpleBody(b, options);
90      }
91  
92      /**
93       * Returns a ShimpleBody constructed from b, using provided option
94       * Map.
95       **/
96      public ShimpleBody newBody(Body b, Map options)
97      {
98          return new ShimpleBody(b, options);
99      }
100 
101     /**
102      * Create a trivial PhiExpr, where preds are an ordered list of
103      * the control predecessor Blocks of the Phi expression.  Instead
104      * of a list of blocks, you may provide a list of the tail Units
105      * from the corresponding blocks.
106      **/
107     public PhiExpr newPhiExpr(Local leftLocal, List preds)
108     {
109         return new SPhiExpr(leftLocal, preds);
110     }
111 
112     public PiExpr newPiExpr(Local local, Unit predicate, Object   targetKey)
113     {
114         return new SPiExpr(local, predicate, targetKey);
115     }
116     
117     /**
118      * Create a PhiExpr with the provided list of Values (Locals or
119      * Constants) and the corresponding control flow predecessor
120      * Blocks.  Instead of a list of predecessor blocks, you may
121      * provide a list of the tail Units from the corresponding blocks.
122      **/
123     public PhiExpr newPhiExpr(List args, List preds)
124     {
125         return new SPhiExpr(args, preds);
126     }
127 
128     /**
129      * Constructs a JimpleBody from a ShimpleBody.
130      *
131      * @see soot.options.ShimpleOptions
132      **/
133     public JimpleBody newJimpleBody(ShimpleBody body)
134     {
135         return body.toJimpleBody();
136     }
137 
138     /**
139      * Returns true if the value is a Phi expression, false otherwise.
140      **/
141     public static boolean isPhiExpr(Value value)
142     {
143         return (value instanceof PhiExpr);
144     }
145     
146     /**
147      * Returns true if the unit is a Phi node, false otherwise.
148      **/
149     public static boolean isPhiNode(Unit unit)
150     {
151         return
152             getPhiExpr(unit) == null ? false : true;
153     }
154 
155     /**
156      * Returns the corresponding PhiExpr if the unit is a Phi node,
157      * null otherwise.
158      **/
159     public static PhiExpr getPhiExpr(Unit unit)
160     {
161         if(!(unit instanceof AssignStmt))
162             return null;
163 
164         Value right = ((AssignStmt)unit).getRightOp();
165         
166         if(isPhiExpr(right))
167             return (PhiExpr) right;
168 
169         return null;
170     }
171 
172     public static boolean isPiExpr(Value value)
173     {
174         return (value instanceof PiExpr);
175     }
176 
177     public static boolean isPiNode(Unit unit)
178     {
179         return getPiExpr(unit) == null ? false : true;
180     }
181 
182     public static PiExpr getPiExpr(Unit unit)
183     {
184         if(!(unit instanceof AssignStmt))
185             return null;
186 
187         Value right = ((AssignStmt)unit).getRightOp();
188 
189         if(isPiExpr(right))
190             return (PiExpr) right;
191 
192         return null;
193     }
194 
195     /**
196      * Returns the corresponding left Local if the unit is a Shimple node,
197      * null otherwise.
198      **/
199     public static Local getLhsLocal(Unit unit)
200     {
201         if(!(unit instanceof AssignStmt))
202             return null;
203 
204         Value right = ((AssignStmt)unit).getRightOp();
205         
206         if(right instanceof ShimpleExpr){
207             Value left = ((AssignStmt)unit).getLeftOp();
208             return (Local) left;
209         }
210 
211         return null;
212     }
213 
214     /**
215      * If you are removing a Unit from a Unit chain which contains
216      * PhiExpr's, you might want to call this utility function in
217      * order to update any PhiExpr pointers to the Unit to point to
218      * the Unit's predecessor(s). This function will not modify
219      * "branch target" UnitBoxes.
220      *
221      * <p> Normally you should not have to call this function
222      * directly, since patching is taken care of Shimple's internal
223      * implementation of PatchingChain.
224      **/
225     public static void redirectToPreds(Body body, Unit remove)
226     {
227         boolean debug = Options.v().debug();
228         if(body instanceof ShimpleBody)
229             debug |= ((ShimpleBody)body).getOptions().debug();
230             
231         Chain units = body.getUnits();
232 
233         /* Determine whether we should continue processing or not. */
234 
235         Iterator pointersIt = remove.getBoxesPointingToThis().iterator();
236 
237         if(!pointersIt.hasNext())
238             return;
239 
240         while(pointersIt.hasNext()){
241             UnitBox pointer = (UnitBox) pointersIt.next();
242 
243             // a PhiExpr may be involved, hence continue processing.
244             // note that we will use the value of "pointer" and
245             // continue iteration from where we left off.
246             if(!pointer.isBranchTarget())
247                 break;
248 
249             // no PhiExpr's are involved, abort
250             if(!pointersIt.hasNext())
251                 return;
252         }
253 
254         /* Ok, continuing... */
255             
256         Set preds = new HashSet();
257         Set phis  = new HashSet();
258         
259         // find fall-through pred
260         if(!remove.equals(units.getFirst())){
261             Unit possiblePred = (Unit) units.getPredOf(remove);
262             if(possiblePred.fallsThrough())
263                 preds.add(possiblePred);
264         }
265 
266         // find the rest of the preds and all Phi's that point to remove
267         Iterator unitsIt = units.iterator();
268         while(unitsIt.hasNext()){
269             Unit unit = (Unit) unitsIt.next();
270             Iterator targetsIt = unit.getUnitBoxes().iterator();
271             while(targetsIt.hasNext()){
272                 UnitBox targetBox = (UnitBox) targetsIt.next();
273                 
274                 if(remove.equals(targetBox.getUnit())){
275                     if(targetBox.isBranchTarget())
276                         preds.add(unit);
277                     else{
278                         PhiExpr phiExpr = Shimple.getPhiExpr(unit);
279                         if(phiExpr != null)
280                             phis.add(phiExpr);
281                     }
282                 }
283             }
284         }
285 
286         /* sanity check */
287         
288         if(phis.size() == 0){
289             if(debug)
290                 G.v().out.println("Warning: Orphaned UnitBoxes to " + remove + "? Shimple.redirectToPreds is giving up.");
291             return;
292         }
293 
294         if(preds.size() == 0){
295             if(debug)
296                 G.v().out.println("Warning: Shimple.redirectToPreds couldn't find any predecessors for " + remove + " in " + body.getMethod() + ".");
297 
298             if(!remove.equals(units.getFirst())){
299                 Unit pred = (Unit) units.getPredOf(remove);
300                 if(debug)
301                     G.v().out.println("Warning: Falling back to immediate chain predecessor: " + pred + ".");
302                 preds.add(pred);
303             }
304             else if(!remove.equals(units.getLast())){
305                 Unit succ = (Unit) units.getSuccOf(remove);
306                 if(debug)
307                     G.v().out.println("Warning: Falling back to immediate chain successor: " + succ + ".");
308                 preds.add(succ);
309             }
310             else
311                 throw new RuntimeException  ("Assertion failed.");
312         }
313 
314         /* At this point we have found all the preds and relevant Phi's */
315 
316         /* Each Phi needs an argument for each pred. */
317         Iterator phiIt = phis.iterator();
318         while(phiIt.hasNext()){
319             PhiExpr phiExpr = (PhiExpr) phiIt.next();
320             ValueUnitPair argBox = phiExpr.getArgBox(remove);
321 
322             if(argBox == null)
323                 throw new RuntimeException  ("Assertion failed.");
324             
325             // now we've got the value!
326             Value arg = argBox.getValue();
327             phiExpr.removeArg(argBox);
328 
329             // add new arguments to Phi
330             Iterator predsIt = preds.iterator();
331             while(predsIt.hasNext()){
332                 Unit pred = (Unit) predsIt.next();
333                 phiExpr.addArg(arg, pred);
334             }
335         }
336     }
337 
338     /**
339      * Redirects PhiExpr pointers to the given Unit to the new Unit.
340      *
341      * <p> Normally you should not have to call this function
342      * directly, since patching is taken care of Shimple's internal
343      * implementation of PatchingChain.
344      **/
345     public static void redirectPointers(Unit oldLocation, Unit newLocation)
346     {
347         List boxesPointing = oldLocation.getBoxesPointingToThis();
348 
349         // important to change this to an array to have a static copy
350         Object  [] boxes = boxesPointing.toArray();
351 
352         for(int i = 0; i < boxes.length; i++){
353             UnitBox box = (UnitBox) boxes[i];
354 
355             if(box.getUnit() != oldLocation)
356                 throw new RuntimeException  ("Something weird's happening");
357             
358             if(!box.isBranchTarget())
359                 box.setUnit(newLocation);
360         }
361     }
362 }
363
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags