PhiNodeManager


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   * @author Navindra Umanee
40   * @see soot.shimple.ShimpleBody
41   * @see <a
42   * HREF="http://citeseer.nj.nec.com/cytron91efficiently.html">Efficiently
43   * Computing Static Single Assignment Form and the Control Dependence
44   * Graph</a>
45   **/
46  public class PhiNodeManager
47  {
48      protected ShimpleBody body;
49      protected ShimpleFactory sf;
50      protected DominatorTree dt;
51      protected DominanceFrontier df;
52      protected BlockGraph cfg;
53      protected GuaranteedDefs gd;
54      
55      public PhiNodeManager(ShimpleBody body)
56      {
57          this.body = body;
58          sf = G.v().shimpleFactory;
59      }
60  
61      public void update()
62      {
63          gd = new GuaranteedDefs(sf.getUnitGraph());
64          cfg = sf.getBlockGraph();
65          dt = sf.getDominatorTree();
66          df = sf.getDominanceFrontier();
67      }
68  
69      protected MultiMap varToBlocks;
70      
71      /**
72       * Phi node Insertion Algorithm from Cytron et al 91, P24-5,
73       *
74       * <p>Special Java case: If a variable is not defined along all
75       * paths of entry to a node, a Phi node is not needed.</p>
76       **/
77      public boolean insertTrivialPhiNodes()
78      {
79          update();
80          boolean change = false;
81          MultiMap localsToDefPoints = new SHashMultiMap();
82          varToBlocks = new HashMultiMap();    
83          
84          // compute localsToDefPoints and varToBlocks
85          for(Iterator blocksIt = cfg.iterator(); blocksIt.hasNext();){
86              Block block = (Block)blocksIt.next();
87  
88              for(Iterator unitsIt = block.iterator(); unitsIt.hasNext();){
89                  Unit unit = (Unit) unitsIt.next();
90  
91                  List defBoxes = unit.getDefBoxes();
92                  for(Iterator defBoxesIt = defBoxes.iterator(); defBoxesIt.hasNext();){
93                      Value def = ((ValueBox)defBoxesIt.next()).getValue();
94                      if(def instanceof Local)
95                          localsToDefPoints.put(def, block);
96                  }
97  
98                  if(Shimple.isPhiNode(unit))
99                      varToBlocks.put(Shimple.getLhsLocal(unit), block);
100             }
101         }
102 
103         /* Routine initialisations. */
104         
105         int[] workFlags = new int[cfg.size()];
106         int iterCount = 0;
107         Stack workList = new Stack();
108 
109         /* Main Cytron algorithm. */
110         
111         {
112             Iterator localsIt = localsToDefPoints.keySet().iterator();
113 
114             while(localsIt.hasNext()){
115                 Local local = (Local) localsIt.next();
116 
117                 iterCount++;
118 
119                 // initialise worklist
120                 {
121                     Iterator defNodesIt = localsToDefPoints.get(local).iterator();
122                     while(defNodesIt.hasNext()){
123                         Block block = (Block) defNodesIt.next();
124                         workFlags[block.getIndexInMethod()] = iterCount;
125                         workList.push(block);
126                     }
127                 }
128 
129                 while(!workList.empty()){
130                     Block block = (Block) workList.pop();
131                     DominatorNode node = dt.getDode(block);
132                     Iterator frontierNodes = df.getDominanceFrontierOf(node).iterator();
133 
134                     while(frontierNodes.hasNext()){
135                         Block frontierBlock = (Block) ((DominatorNode) frontierNodes.next()).getGode();
136                         int fBIndex = frontierBlock.getIndexInMethod();
137                         
138                         if(needsPhiNode(local, frontierBlock)){
139                             prependTrivialPhiNode(local, frontierBlock);
140                             change = true;
141 
142                             if(workFlags[fBIndex] < iterCount){
143                                 workFlags[fBIndex] = iterCount;
144                                 workList.push(frontierBlock);
145                             }
146                         }
147                     }
148                 }
149             }
150         }
151 
152         return change;
153     }
154 
155     /**
156      * Inserts a trivial Phi node with the appropriate number of
157      * arguments.
158      **/
159     public void prependTrivialPhiNode(Local local, Block frontierBlock)
160     {
161         List preds = frontierBlock.getPreds();
162         PhiExpr pe = Shimple.v().newPhiExpr(local, preds);
163         pe.setBlockId(frontierBlock.getIndexInMethod());
164         Unit trivialPhi = Jimple.v().newAssignStmt(local, pe);
165         Unit blockHead = frontierBlock.getHead();
166 
167         // is it a catch block?
168         if(blockHead instanceof IdentityUnit)
169             frontierBlock.insertAfter(trivialPhi, frontierBlock.getHead());
170         else
171             frontierBlock.insertBefore(trivialPhi, frontierBlock.getHead());
172 
173         varToBlocks.put(local, frontierBlock);
174     }
175 
176     /**
177      * Function that allows us to weed out special cases where
178      * we do not require Phi nodes.
179      *
180      * <p> Temporary implementation, with much room for improvement.
181      **/
182     protected boolean needsPhiNode(Local local, Block block)
183     {
184         if(varToBlocks.get(local).contains(block))
185             return false;
186 
187         Iterator unitsIt = block.iterator();
188 
189         if(!unitsIt.hasNext()){
190             if(!block.getSuccs().isEmpty())
191                 throw new RuntimeException  ("Empty block in CFG?");
192             
193             // tail block
194             return false;
195         }
196 
197         Unit unit = (Unit) unitsIt.next();
198 
199         // this will return null if the head unit is an inserted Phi statement
200         List definedLocals = gd.getGuaranteedDefs(unit);
201 
202         // this should not fail
203         while(definedLocals == null){
204             if(!unitsIt.hasNext())
205                 throw new RuntimeException  ("Almost empty block in CFG?");
206             unit = (Unit) unitsIt.next();
207             definedLocals = gd.getGuaranteedDefs(unit);
208         }
209         
210         return definedLocals.contains(local);
211     }
212 
213     /**
214      * Exceptional Phi nodes have a huge number of arguments and control
215      * flow predecessors by default.  Since it is useless trying to keep
216      * the number of arguments and control flow predecessors in synch,
217      * we might as well trim out all redundant arguments and eliminate
218      * a huge number of copy statements when we get out of SSA form in
219      * the process.
220      **/
221     public void trimExceptionalPhiNodes()
222     {
223         Set handlerUnits = new HashSet();
224         Iterator trapsIt = body.getTraps().iterator();
225 
226         while(trapsIt.hasNext()) {
227             Trap trap = (Trap) trapsIt.next();
228             handlerUnits.add(trap.getHandlerUnit());
229         }
230 
231         Iterator blocksIt = cfg.iterator();
232         while(blocksIt.hasNext()){
233             Block block = (Block) blocksIt.next();
234 
235             // trim relevant Phi expressions
236             if(handlerUnits.contains(block.getHead())){
237                 Iterator unitsIt = block.iterator();
238                 while(unitsIt.hasNext()){
239                     Unit unit = (Unit) unitsIt.next();
240 
241                     //if(!(newPhiNodes.contains(unit)))
242                     PhiExpr phi = Shimple.getPhiExpr(unit);
243 
244                     if(phi == null)
245                         continue;
246 
247                     trimPhiNode(phi);
248                 }
249             }
250         }
251     }
252 
253     /**
254      * @see #trimExceptionalPhiNodes()
255      **/
256     public void trimPhiNode(PhiExpr phiExpr)
257     {
258         /* A value may appear many times in an exceptional Phi. Hence,
259            the same value may be associated with many UnitBoxes. We
260            build the MultiMap valueToPairs for convenience.  */
261 
262         MultiMap valueToPairs = new HashMultiMap();
263 
264         Iterator argsIt = phiExpr.getArgs().iterator();
265         while(argsIt.hasNext()){
266             ValueUnitPair argPair = (ValueUnitPair) argsIt.next();
267             Value value = argPair.getValue();
268             valueToPairs.put(value, argPair);
269         }
270 
271         /* Consider each value and see if we can find the dominating
272            UnitBoxes.  Once we havpe found all the dominating
273            UnitBoxes, the rest of the redundant arguments can be
274            trimmed.  */
275         
276         Iterator valuesIt = valueToPairs.keySet().iterator();
277         while(valuesIt.hasNext()){
278             Value value = (Value) valuesIt.next();
279 
280             // although the champs list constantly shrinks, guaranteeing
281             // termination, the challengers list never does.  This could
282             // be optimised.
283             Set pairsSet = valueToPairs.get(value);
284             List champs = new ArrayList(pairsSet);
285             List challengers = new ArrayList(pairsSet);
286             
287             // champ is the currently assumed dominator
288             ValueUnitPair champ = (ValueUnitPair) champs.remove(0);
289             Unit champU = champ.getUnit();
290 
291             // hopefully everything will work out the first time, but
292             // if not, we will have to try a new champion just in case
293             // there is more that can be trimmed.
294             boolean retry = true;
295             while(retry){
296                 retry = false;
297 
298                 // go through each challenger and see if we dominate them
299                 // if not, the challenger becomes the new champ
300                 for(int i = 0; i < challengers.size(); i++){
301                     ValueUnitPair challenger = (ValueUnitPair)challengers.get(i);
302 
303                     if(challenger.equals(champ))
304                         continue;
305                     Unit challengerU = challenger.getUnit();
306                 
307                     // kill the challenger
308                     if(dominates(champU, challengerU))
309                         phiExpr.removeArg(challenger);
310 
311                     // we die, find a new champ
312                     else if(dominates(challengerU, champU)){
313                         phiExpr.removeArg(champ);
314                         champ = challenger;
315                         champU = champ.getUnit();
316                         champs.remove(champ);
317                     }
318 
319                     // neither wins, oops!  we'll have to try the next
320                     // available champ at the next pass.  It may very
321                     // well be inevitable that we will have two
322                     // identical value args in an exceptional PhiExpr,
323                     // but the more we can trim the better.
324                     else
325                         retry = true;
326                 }
327 
328                 if(retry) {
329                     if(champs.size() == 0)
330                         break;
331                     champ = (ValueUnitPair)champs.remove(0);
332                     champU = champ.getUnit();
333                 }
334             }
335         }
336 
337         /*
338         {
339             List preds = phiExpr.getPreds();
340 
341             for(int i = 0; i < phiExpr.getArgCount(); i++){
342                 ValueUnitPair vup = phiExpr.getArgBox(i);
343                 Value value = vup.getValue();
344                 Unit unit = vup.getUnit();
345 
346                 PhiExpr innerPhi = Shimple.getPhiExpr(unit);
347                 if(innerPhi == null)
348                     continue;
349                 
350                 Value innerValue = Shimple.getLhsLocal(unit);
351                 if(!innerValue.equals(value))
352                     continue;
353 
354                 boolean canRemove = true;
355                 for(int j = 0; j < innerPhi.getArgCount(); j++){
356                     Unit innerPred = innerPhi.getPred(j);
357                     if(!preds.contains(innerPred)){
358                         canRemove = false;
359                         break;
360                     }
361                 }
362 
363                 if(canRemove)
364                     phiExpr.removeArg(vup);
365             }
366         }
367         */
368     }
369     
370     protected Map unitToBlock;
371 
372     /**
373      * Returns true if champ dominates challenger.  Note that false
374      * doesn't necessarily mean that challenger dominates champ.
375      **/
376     public boolean dominates(Unit champ, Unit challenger)
377     {
378         if(champ == null || challenger == null)
379             throw new RuntimeException  ("Assertion failed.");
380         
381         // self-domination
382         if(champ.equals(challenger))
383             return true;
384         
385         if(unitToBlock == null)
386             unitToBlock = getUnitToBlockMap(cfg);
387 
388         Block champBlock = (Block) unitToBlock.get(champ);
389         Block challengerBlock = (Block) unitToBlock.get(challenger);
390 
391         if(champBlock.equals(challengerBlock)){
392             Iterator unitsIt = champBlock.iterator();
393 
394             while(unitsIt.hasNext()){
395                 Unit unit = (Unit) unitsIt.next();
396                 if(unit.equals(champ))
397                     return true;
398                 if(unit.equals(challenger))
399                     return false;
400             }
401 
402             throw new RuntimeException  ("Assertion failed.");
403         }
404 
405         DominatorNode champNode = dt.getDode(champBlock);
406         DominatorNode challengerNode = dt.getDode(challengerBlock);
407 
408         // *** FIXME: System.out.println("champ: " + champNode);
409         // System.out.println("chall: " + challengerNode);
410         
411         return(dt.isDominatorOf(champNode, challengerNode));
412     }
413     
414     /**
415      * Eliminate Phi nodes in block by naively replacing them with
416      * shimple assignment statements in the control flow predecessors.
417      * Returns true if new locals were added to the body during the
418      * process, false otherwise.
419      **/
420     public boolean doEliminatePhiNodes()
421     {
422         // flag that indicates whether we created new locals during the
423         // elimination process
424         boolean addedNewLocals = false;
425         
426         // List of Phi nodes to be deleted.
427         List phiNodes = new ArrayList();
428 
429         // This stores the assignment statements equivalent to each
430         // (and every) Phi.  We use lists instead of a Map of
431         // non-determinate order since we prefer to preserve the order
432         // of the assignment statements, i.e. if a block has more than
433         // one Phi expression, we prefer that the equivalent
434         // assignments be placed in the same order as the Phi expressions.
435         List equivStmts = new ArrayList();
436 
437         // Similarly, to preserve order, instead of directly storing
438         // the pred, we store the pred box so that we follow the
439         // pointers when SPatchingChain moves them.
440         List predBoxes = new ArrayList();
441         
442         Chain units = body.getUnits();
443         Iterator unitsIt = units.iterator();
444 
445         while(unitsIt.hasNext()){
446             Unit unit = (Unit) unitsIt.next();
447             PhiExpr phi = Shimple.getPhiExpr(unit);
448 
449             if(phi == null)
450                 continue;
451 
452             Local lhsLocal = Shimple.getLhsLocal(unit);
453 
454             for(int i = 0; i < phi.getArgCount(); i++){
455                 Value phiValue = phi.getValue(i);
456                 AssignStmt convertedPhi =
457                     Jimple.v().newAssignStmt(lhsLocal, phiValue);
458 
459                 equivStmts.add(convertedPhi);
460                 predBoxes.add(phi.getArgBox(i));
461             }
462 
463             phiNodes.add(unit);
464         }
465 
466         if(equivStmts.size() != predBoxes.size())
467             throw new RuntimeException  ("Assertion failed.");
468         
469         /* Avoid Concurrent Modification exceptions. */
470 
471         for(int i = 0; i < equivStmts.size(); i++){
472             AssignStmt stmt = (AssignStmt) equivStmts.get(i);
473             Unit pred = ((UnitBox) predBoxes.get(i)).getUnit();
474 
475             if(pred == null)
476                 throw new RuntimeException  ("Assertion failed.");
477 
478             // if we need to insert the copy statement *before* an
479             // instruction that happens to be *using* the Local being
480             // defined, we need to do some extra work to make sure we
481             // don't overwrite the old value of the local
482             if(pred.branches()){
483                 boolean needPriming = false;
484                 Local lhsLocal = (Local) stmt.getLeftOp();
485                 Local savedLocal = Jimple.v().newLocal(lhsLocal.getName()+"_",
486                                                        lhsLocal.getType());
487                 Iterator useBoxesIt = pred.getUseBoxes().iterator();
488 
489                 while(useBoxesIt.hasNext()){
490                     ValueBox useBox = (ValueBox) useBoxesIt.next();
491                     if(lhsLocal.equals(useBox.getValue())){
492                         needPriming = true;
493                         addedNewLocals = true;
494                         useBox.setValue(savedLocal);
495                     }
496                 }
497 
498                 if(needPriming){
499                     body.getLocals().add(savedLocal);
500                     AssignStmt copyStmt = Jimple.v().newAssignStmt(savedLocal, lhsLocal);
501                     units.insertBefore(copyStmt, pred);
502                 }
503 
504                 // this is all we really wanted to do!
505                 units.insertBefore(stmt, pred);
506             }
507             else
508                 units.insertAfter(stmt, pred);
509         }
510         
511         Iterator phiNodesIt = phiNodes.iterator();
512 
513         while(phiNodesIt.hasNext()){
514             Unit removeMe = (Unit) phiNodesIt.next();
515             units.remove(removeMe);
516             removeMe.clearUnitBoxes();
517         }
518 
519         return addedNewLocals;
520     }
521 
522     /**
523      * Convenience function that maps units to blocks.  Should
524      * probably be in BlockGraph.
525      **/
526     public Map getUnitToBlockMap(BlockGraph blocks)
527     {
528         Map unitToBlock = new HashMap();
529 
530         Iterator blocksIt = blocks.iterator();
531         while(blocksIt.hasNext()){
532             Block block = (Block) blocksIt.next();
533             Iterator unitsIt = block.iterator();
534 
535             while(unitsIt.hasNext()){
536                 Unit unit = (Unit) unitsIt.next();
537                 unitToBlock.put(unit, block);
538             }
539         }
540 
541         return unitToBlock;
542     }
543 }
544
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags