PiNodeManager


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 PiNodeManager
64  {
65      protected ShimpleBody body;
66      protected ShimpleFactory sf;
67      protected DominatorTree dt;
68      protected DominanceFrontier df;
69      protected ReversibleGraph cfg;
70      protected boolean trimmed;
71      
72      /**
73       * Transforms the provided body to pure SSA form.
74       **/
75      public PiNodeManager(ShimpleBody body, boolean trimmed)
76      {
77          this.body = body;
78          this.trimmed = trimmed;
79          sf = G.v().shimpleFactory;
80      }
81  
82      public void update()
83      {
84          cfg = sf.getReverseBlockGraph();
85          dt = sf.getReverseDominatorTree();
86          df = sf.getReverseDominanceFrontier();
87      }
88      protected MultiMap varToBlocks;
89      
90      public boolean insertTrivialPiNodes()
91      {
92          update();
93          boolean change = false;
94          MultiMap localsToUsePoints = new SHashMultiMap();
95          varToBlocks = new HashMultiMap();    
96          
97          // compute localsToUsePoints and varToBlocks
98          for(Iterator blocksIt = cfg.iterator(); blocksIt.hasNext();){
99              Block block = (Block)blocksIt.next();
100 
101             for(Iterator unitsIt = block.iterator(); unitsIt.hasNext();){
102                 Unit unit = (Unit) unitsIt.next();
103 
104                 List useBoxes = unit.getUseBoxes();
105                 for(Iterator useBoxesIt = useBoxes.iterator(); useBoxesIt.hasNext();){
106                     Value use = ((ValueBox)useBoxesIt.next()).getValue();
107                     if(use instanceof Local)
108                         localsToUsePoints.put(use, block);
109                 }
110 
111                 if(Shimple.isPiNode(unit))
112                     varToBlocks.put(Shimple.getLhsLocal(unit), block);
113             }
114         }
115 
116         /* Routine initialisations. */
117         
118         int[] workFlags = new int[cfg.size()];
119         int[] hasAlreadyFlags = new int[cfg.size()];
120         
121         int iterCount = 0;
122         Stack workList = new Stack();
123 
124         /* Main Cytron algorithm. */
125         
126         {
127             Iterator localsIt = localsToUsePoints.keySet().iterator();
128 
129             while(localsIt.hasNext()){
130                 Local local = (Local) localsIt.next();
131 
132                 iterCount++;
133 
134                 // initialise worklist
135                 {
136                     Iterator useNodesIt = localsToUsePoints.get(local).iterator();
137                     while(useNodesIt.hasNext()){
138                         Block block = (Block) useNodesIt.next();
139                         workFlags[block.getIndexInMethod()] = iterCount;
140                         workList.push(block);
141                     }
142                 }
143 
144                 while(!workList.empty()){
145                     Block block = (Block) workList.pop();
146                     DominatorNode node = dt.getDode(block);
147                     Iterator frontierNodes = df.getDominanceFrontierOf(node).iterator();
148 
149                     while(frontierNodes.hasNext()){
150                         Block frontierBlock = (Block) ((DominatorNode) frontierNodes.next()).getGode();
151                         int fBIndex = frontierBlock.getIndexInMethod();
152                         
153                         if(hasAlreadyFlags[fBIndex] < iterCount){
154                             insertPiNodes(local, frontierBlock);
155                             change = true;
156                             
157                             hasAlreadyFlags[fBIndex] = iterCount;
158 
159                             if(workFlags[fBIndex] < iterCount){
160                                 workFlags[fBIndex] = iterCount;
161                                 workList.push(frontierBlock);
162                             }
163                         }
164                     }
165                 }
166             }
167         }
168 
169         if(change)
170             sf.clearCache();
171         return change;
172     }
173 
174     public void insertPiNodes(Local local, Block frontierBlock)
175     {
176         if(varToBlocks.get(local).contains(frontierBlock.getSuccs().get(0)))
177             return;
178 
179         Unit u = frontierBlock.getTail();
180 
181         TRIMMED:
182         {
183             if(trimmed){
184                 for(Iterator i = u.getUseBoxes().iterator(); i.hasNext();){
185                     Value use = ((ValueBox)i.next()).getValue();
186                     if(use.equals(local))
187                         break TRIMMED;
188                 }
189                 return;
190             }
191         }
192             
193         if(u instanceof IfStmt)
194             piHandleIfStmt(local, (IfStmt) u);
195         else if((u instanceof LookupSwitchStmt) || (u instanceof TableSwitchStmt))
196             piHandleSwitchStmt(local, u);
197         else
198             throw new RuntimeException  ("Assertion failed: Unhandled stmt: " + u);
199     }
200 
201     public void piHandleIfStmt(Local local, IfStmt u)
202     {
203         Unit target = u.getTarget();
204         
205         PiExpr pit = Shimple.v().newPiExpr(local, u, Boolean.TRUE);
206         PiExpr pif = Shimple.v().newPiExpr(local, u, Boolean.FALSE);
207         Unit addt = Jimple.v().newAssignStmt(local, pit);
208         Unit addf = Jimple.v().newAssignStmt(local, pif);
209             
210         PatchingChain units = body.getUnits();
211             
212         // insert after should be safe; a new block should result if
213         // the Unit originally after the IfStmt had another predecessor.
214         // what about SPatchingChain?  seems sane.
215         units.insertAfter(addf, u);
216 
217         /* we need to be careful with insertBefore, if target
218            already had some other predecessors. */
219 
220         // handle immediate predecessor if it falls through
221         // *** FIXME: Does SPatchingChain do the right thing?
222         PREDFALLSTHROUGH:
223         {
224             Unit predOfTarget = null;
225             try{
226                 predOfTarget = (Unit) units.getPredOf(target);
227             }
228             catch(NoSuchElementException e){
229                 predOfTarget = null;
230             }
231             
232             if(predOfTarget == null)
233                 break PREDFALLSTHROUGH;
234             
235             if(predOfTarget.fallsThrough()){
236                 GotoStmt gotoStmt = Jimple.v().newGotoStmt(target);
237                 units.insertAfter(gotoStmt, predOfTarget);
238             }
239         }
240 
241         // we do not want to move the pointers for other branching statements
242         units.getNonPatchingChain().insertBefore(addt, target);
243         u.setTarget(addt);
244     }
245 
246     public void piHandleSwitchStmt(Local local, Unit u)
247     {
248         List targetBoxes = new ArrayList();
249         List targetKeys = new ArrayList();
250 
251         if(u instanceof LookupSwitchStmt){
252             LookupSwitchStmt lss = (LookupSwitchStmt) u;
253             targetBoxes.add(lss.getDefaultTargetBox());
254             targetKeys.add("default");
255             for(int i = 0; i < lss.getTargetCount(); i++)
256                 targetBoxes.add(lss.getTargetBox(i));
257             targetKeys.addAll(lss.getLookupValues());
258         }
259         else if(u instanceof TableSwitchStmt){
260             TableSwitchStmt tss = (TableSwitchStmt) u;
261             int low = tss.getLowIndex();
262             int hi = tss.getHighIndex();
263 
264             targetBoxes.add(tss.getDefaultTargetBox());
265             targetKeys.add("default");
266             for(int i = 0; i <= (hi - low); i++)
267                 targetBoxes.add(tss.getTargetBox(i));
268             for(int i = low; i <= hi; i++)
269                 targetKeys.add(new Integer  (i));
270         }
271         else{
272             throw new RuntimeException  ("Assertion failed.");
273         }
274             
275         for(int count = 0; count < targetBoxes.size(); count++){
276             UnitBox targetBox = (UnitBox) targetBoxes.get(count);
277             Unit target = targetBox.getUnit();
278             Object   targetKey = targetKeys.get(count);
279             
280             PiExpr pi1 = Shimple.v().newPiExpr(local, u, targetKey);
281             Unit add1 = Jimple.v().newAssignStmt(local, pi1);
282             
283             PatchingChain units = body.getUnits();
284 
285             /* we need to be careful with insertBefore, if target
286                already had some other predecessors. */
287 
288             // handle immediate predecessor if it falls through
289             // *** FIXME: Does SPatchingChain do the right thing?
290             PREDFALLSTHROUGH:
291             {
292                 Unit predOfTarget = null;
293                 try{
294                     predOfTarget = (Unit) units.getPredOf(target);
295                 }
296                 catch(NoSuchElementException e){
297                     predOfTarget = null;
298                 }
299                 
300                 if(predOfTarget == null)
301                     break PREDFALLSTHROUGH;
302 
303                 if(predOfTarget.fallsThrough()){
304                     GotoStmt gotoStmt = Jimple.v().newGotoStmt(target);
305                     units.insertAfter(gotoStmt, predOfTarget);
306                 }
307             }
308 
309             // we do not want to move the pointers for other branching statements
310             units.getNonPatchingChain().insertBefore(add1, target);
311             targetBox.setUnit(add1);
312         }
313     }
314 
315     public void eliminatePiNodes(boolean smart)
316     {
317         if(smart){
318             Map newToOld = new HashMap();
319             List boxes = new ArrayList();
320             
321             for(Iterator unitsIt = body.getUnits().iterator(); unitsIt.hasNext();){
322                 Unit u = (Unit) unitsIt.next();
323                 PiExpr pe = Shimple.getPiExpr(u);
324                 if(pe != null){
325                     newToOld.put(Shimple.getLhsLocal(u), pe.getValue());
326                     unitsIt.remove();
327                 }
328                 else{
329                     boxes.addAll(u.getUseBoxes());
330                 }
331             }
332 
333             for(Iterator boxesIt = boxes.iterator(); boxesIt.hasNext();){
334                 ValueBox box = (ValueBox) boxesIt.next();
335                 Value value = box.getValue();
336                 Value old = (Value) newToOld.get(value);
337                 if(old != null)
338                     box.setValue(old);
339             }
340 
341             DeadAssignmentEliminator.v().transform(body);
342             CopyPropagator.v().transform(body);
343             DeadAssignmentEliminator.v().transform(body);            
344         }
345         else{
346             for(Iterator unitsIt = body.getUnits().iterator(); unitsIt.hasNext();){
347                 Unit u = (Unit) unitsIt.next();
348                 PiExpr pe = Shimple.getPiExpr(u);
349                 if(pe != null)
350                     ((AssignStmt)u).setRightOp(pe.getValue());
351             }
352         }
353     }
354     
355     public static List getUseBoxesFromBlock(Block block)
356     {
357         Iterator unitsIt = block.iterator();
358         
359         List useBoxesList = new ArrayList();
360     
361         while(unitsIt.hasNext())
362             useBoxesList.addAll(((Unit)unitsIt.next()).getUseBoxes());
363         
364         return useBoxesList;
365     }
366 }
367
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags