ShimpleBodyBuilder


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.util.*;
24  import java.util.*;
25  import soot.shimple.*;
26  import soot.shimple.toolkits.scalar.*;
27  import soot.shimple.toolkits.graph.*;
28  import soot.options.*;
29  import soot.jimple.*;
30  import soot.jimple.internal.*;
31  import soot.jimple.toolkits.base.*;
32  import soot.jimple.toolkits.callgraph.*;
33  import soot.jimple.toolkits.pointer.*;
34  import soot.jimple.toolkits.scalar.*;
35  import soot.toolkits.graph.*;
36  import soot.toolkits.scalar.*;
37  
38  /**
39   * This class does the real high-level work.  It takes a Jimple body
40   * or Jimple/Shimple hybrid body and produces pure Shimple.
41   *
42   * <p> The work is done in two main steps:
43   *
44   * <ol>
45   * <li> Trivial Phi nodes are added.
46   * <li> A renaming algorithm is executed.
47   * </ol>
48   *
49   * <p> This class can also translate out of Shimple by producing an
50   * equivalent Jimple body with all Phi nodes removed.
51   *
52   * <p> Note that this is an internal class, understanding it should
53   * not be necessary from a user point-of-view and relying on it
54   * directly is not recommended.
55   *
56   * @author Navindra Umanee
57   * @see soot.shimple.ShimpleBody
58   * @see <a
59   * HREF="http://citeseer.nj.nec.com/cytron91efficiently.html">Efficiently
60   * Computing Static Single Assignment Form and the Control Dependence
61   * Graph</a>
62   **/
63  public class ShimpleBodyBuilder
64  {
65      protected ShimpleBody body;
66      protected ShimpleFactory sf;
67      protected DominatorTree dt;
68      protected BlockGraph cfg;
69      
70      /**
71       * A fixed list of all original Locals.
72       **/
73      protected List origLocals;
74  
75      public PhiNodeManager phi;
76      public PiNodeManager pi;
77  
78      ShimpleOptions options;
79      
80      /**
81       * Transforms the provided body to pure SSA form.
82       **/
83      public ShimpleBodyBuilder(ShimpleBody body)
84      {
85          this.body = body;
86          sf = G.v().shimpleFactory;
87          sf.setBody(body);
88          sf.clearCache();
89          phi = new PhiNodeManager(body);
90          pi = new PiNodeManager(body, false);
91          options = body.getOptions();
92          makeUniqueLocalNames();
93      }
94      
95      public void update()
96      {
97          cfg = sf.getBlockGraph();
98          dt = sf.getDominatorTree();
99          origLocals = new ArrayList(body.getLocals());
100     }
101 
102     public void transform()
103     {
104         phi.insertTrivialPhiNodes();
105 
106         boolean change = false;
107         if(options.extended()){
108             change = pi.insertTrivialPiNodes();
109         
110             while(change){
111                 if(phi.insertTrivialPhiNodes()){
112                     change = pi.insertTrivialPiNodes();
113                 }
114                 else{
115                     break;
116                 }
117             }
118         }
119 
120         renameLocals();
121         phi.trimExceptionalPhiNodes();
122         makeUniqueLocalNames();
123     }
124 
125     public void preElimOpt()
126     {
127         boolean optElim = options.node_elim_opt();
128 
129         // *** FIXME: 89e9a0470601091906j26489960j65290849dbe0481f@mail.gmail.com
130         //if(optElim)
131         //DeadAssignmentEliminator.v().transform(body);
132     }
133 
134     public void postElimOpt()
135     {
136         boolean optElim = options.node_elim_opt();
137         
138         if(optElim){
139             DeadAssignmentEliminator.v().transform(body);
140             UnreachableCodeEliminator.v().transform(body);
141             UnconditionalBranchFolder.v().transform(body);
142             Aggregator.v().transform(body);
143             UnusedLocalEliminator.v().transform(body);
144         }
145     }
146     
147     /**
148      * Remove Phi nodes from current body, high probablity this
149      * destroys SSA form.
150      *
151      * <p> Dead code elimination + register aggregation are performed
152      * as recommended by Cytron.  The Aggregator looks like it could
153      * use some improvements.
154      *
155      * @see soot.options.ShimpleOptions
156      **/
157     public void eliminatePhiNodes()
158     {
159         if(phi.doEliminatePhiNodes())
160             makeUniqueLocalNames();
161 
162     }
163 
164     public void eliminatePiNodes()
165     {
166         boolean optElim = options.node_elim_opt();
167         pi.eliminatePiNodes(optElim);
168     }
169     
170     /**
171      * Maps new name Strings to Locals.
172      **/
173     protected Map newLocals;
174 
175     /**
176      * Maps renamed Locals to original Locals.
177      **/
178     protected Map newLocalsToOldLocal;
179 
180     protected int[] assignmentCounters;
181     protected Stack[] namingStacks;
182     
183     /**
184      * Variable Renaming Algorithm from Cytron et al 91, P26-8,
185      * implemented in various bits and pieces by the next functions.
186      * Must be called after trivial nodes have been added.
187      **/
188     public void renameLocals()
189     {
190         update();
191         newLocals = new HashMap();
192         newLocalsToOldLocal = new HashMap();
193 
194         assignmentCounters = new int[origLocals.size()];
195         namingStacks = new Stack[origLocals.size()];
196 
197         for(int i = 0; i < namingStacks.length; i++)
198             namingStacks[i] = new Stack();
199 
200         List heads = cfg.getHeads();
201 
202         if(heads.size() == 0)
203             return;
204 
205         if(heads.size() != 1)
206             throw new RuntimeException  ("Assertion failed:  Only one head expected.");
207         
208         Block entry = (Block) heads.get(0);
209         renameLocalsSearch(entry);
210     }
211 
212     /**
213      * Driven by renameLocals().
214      **/
215     public void renameLocalsSearch(Block block)
216     {
217         // accumulated in Step 1 to be re-processed in Step 4
218         List lhsLocals = new ArrayList();
219         
220         // Step 1 of 4 -- Rename block's uses (ordinary) and defs
221         {
222             // accumulated and re-processed in a later loop
223             Iterator unitsIt = block.iterator();
224 
225             while(unitsIt.hasNext()){
226                 Unit unit = (Unit) unitsIt.next();
227 
228                 // Step 1/2 of 1
229                 {
230                     List useBoxes = new ArrayList();
231 
232                     if(!Shimple.isPhiNode(unit))
233                         useBoxes.addAll(unit.getUseBoxes());
234 
235                     Iterator useBoxesIt = useBoxes.iterator();
236                 
237                     while(useBoxesIt.hasNext()){
238                         ValueBox useBox = (ValueBox) useBoxesIt.next();
239                         Value use = useBox.getValue();
240 
241                         int localIndex = indexOfLocal(use);
242 
243                         // not one of our locals
244                         if(localIndex == -1)
245                             continue;
246 
247                         Local localUse = (Local) use;
248 
249                         if(namingStacks[localIndex].empty())
250                             continue;
251 
252                         Integer   subscript = (Integer  ) namingStacks[localIndex].peek();
253 
254                         Local renamedLocal = fetchNewLocal(localUse, subscript);
255                         useBox.setValue(renamedLocal);
256                     }
257                 }
258 
259                 // Step 1 of 1
260                 {
261                     if(!(unit instanceof DefinitionStmt))
262                         continue;
263                 
264                     DefinitionStmt defStmt = (DefinitionStmt) unit;
265                     
266                     Value lhsValue = defStmt.getLeftOp();
267                     
268                     // not something we're interested in
269                     if(!origLocals.contains(lhsValue))
270                         continue;
271 
272                     ValueBox lhsLocalBox = defStmt.getLeftOpBox();
273                     Local lhsLocal = (Local) lhsValue;
274 
275                     // re-processed in Step 4
276                     lhsLocals.add(lhsLocal);
277 
278                     int localIndex = indexOfLocal(lhsLocal);
279                     if(localIndex == -1)
280                         throw new RuntimeException  ("Assertion failed.");
281                 
282                     Integer   subscript = new Integer  (assignmentCounters[localIndex]);
283 
284                     Local newLhsLocal = fetchNewLocal(lhsLocal, subscript);
285                     lhsLocalBox.setValue(newLhsLocal);
286 
287                     namingStacks[localIndex].push(subscript);
288                     assignmentCounters[localIndex]++;                    
289                     
290                 }
291             }
292         }
293 
294         // Step 2 of 4 -- Rename Phi node uses in Successors
295         {
296             Iterator succsIt = cfg.getSuccsOf(block).iterator();
297 
298             while(succsIt.hasNext()){
299                 Block succ = (Block) succsIt.next();
300 
301                 Iterator unitsIt = succ.iterator();
302 
303                 while(unitsIt.hasNext()){
304                     Unit unit = (Unit) unitsIt.next();
305 
306                     PhiExpr phiExpr = Shimple.getPhiExpr(unit);
307 
308                     if(phiExpr == null)
309                         continue;
310 
311                     // simulate whichPred
312                     int argIndex = phiExpr.getArgIndex(block);
313                     if(argIndex == -1)
314                         throw new RuntimeException  ("Assertion failed.");
315                         
316                     ValueBox phiArgBox = phiExpr.getArgBox(argIndex);
317 
318                     Local phiArg = (Local) phiArgBox.getValue();
319                     
320                     int localIndex = indexOfLocal(phiArg);
321                     if(localIndex == -1)
322                         throw new RuntimeException  ("Assertion failed.");
323                     
324                     if(namingStacks[localIndex].empty())
325                         continue;
326 
327                     Integer   subscript = (Integer  ) namingStacks[localIndex].peek();
328                     
329                     Local newPhiArg = fetchNewLocal(phiArg, subscript);
330                     phiArgBox.setValue(newPhiArg);
331                 }
332             }
333         }
334 
335         // Step 3 of 4 -- Recurse over children.
336         {
337             DominatorNode node = dt.getDode(block);
338 
339             // now we recurse over children
340 
341             Iterator childrenIt = dt.getChildrenOf(node).iterator();
342 
343             while(childrenIt.hasNext()){
344                 DominatorNode childNode = (DominatorNode) childrenIt.next();
345 
346                 renameLocalsSearch((Block) childNode.getGode());
347             }
348         }
349 
350         // Step 4 of 4 -- Tricky name stack updates.
351         {
352             Iterator lhsLocalsIt = lhsLocals.iterator();
353 
354             while(lhsLocalsIt.hasNext()){
355                 Local lhsLocal = (Local) lhsLocalsIt.next();
356 
357                 int lhsLocalIndex = indexOfLocal(lhsLocal);
358                 if(lhsLocalIndex == -1)
359                     throw new RuntimeException  ("Assertion failed.");
360                 
361                 namingStacks[lhsLocalIndex].pop();
362             }
363         }
364 
365         /* And we're done.  The renaming process is complete. */
366     }
367 
368     /**
369      * Clever convenience function to fetch or create new Local's
370      * given a Local and the desired subscript.
371      **/
372     protected Local fetchNewLocal(Local local, Integer   subscript)
373     {
374         Local oldLocal = local;
375         
376         if(!origLocals.contains(local))
377             oldLocal = (Local) newLocalsToOldLocal.get(local);
378         
379         if(subscript.intValue() == 0)
380             return oldLocal;
381 
382         // If the name already exists, makeUniqueLocalNames() will
383         // take care of it.
384         String   name = oldLocal.getName() + "_" + subscript;
385 
386         Local newLocal = (Local) newLocals.get(name);
387 
388         if(newLocal == null){
389             newLocal = new JimpleLocal(name, oldLocal.getType());
390             newLocals.put(name, newLocal);
391             newLocalsToOldLocal.put(newLocal, oldLocal);
392 
393             // add proper Local declation
394             body.getLocals().add(newLocal);
395         }
396 
397         return newLocal;
398     }
399 
400     /**
401      * Convenient function that maps new Locals to the originating
402      * Local, and finds the appropriate array index into the naming
403      * structures.
404      **/
405     protected int indexOfLocal(Value local)
406     {
407         int localIndex = origLocals.indexOf(local);
408 
409         if(localIndex == -1){
410             // might be null
411             Local oldLocal = (Local) newLocalsToOldLocal.get(local);
412 
413             localIndex = origLocals.indexOf(oldLocal);
414         }
415         
416         return localIndex;
417     }
418 
419     /**
420      * Make sure the locals in the given body all have unique String
421      * names.  Renaming is done if necessary.
422      **/
423     public void makeUniqueLocalNames()
424     {
425         if(options.standard_local_names()){
426             LocalNameStandardizer.v().transform(body);
427             return;
428         }
429 
430         Set localNames = new HashSet();
431         Iterator localsIt = body.getLocals().iterator();
432 
433         while(localsIt.hasNext()){
434             Local local = (Local) localsIt.next();
435             String   localName = local.getName();
436             
437             if(localNames.contains(localName)){
438                 String   uniqueName = makeUniqueLocalName(localName, localNames);
439                 local.setName(uniqueName);
440                 localNames.add(uniqueName);
441             }
442             else
443                 localNames.add(localName);
444         }
445     }
446 
447     /**
448      * Given a set of Strings, return a new name for dupName that is
449      * not currently in the set.
450      **/
451     public String   makeUniqueLocalName(String   dupName, Set localNames)
452     {
453         int counter = 1;
454         String   newName = dupName;
455 
456         while(localNames.contains(newName))
457             newName = dupName + "_" + counter++;
458 
459         return newName;
460     }
461 }
462
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags