SConstantPropagatorAndFolder


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.toolkits.scalar;
21  
22  import soot.*;
23  import soot.util.*;
24  import soot.options.*;
25  import soot.jimple.*;
26  import soot.shimple.*;
27  import soot.toolkits.scalar.*;
28  import soot.toolkits.graph.*;
29  import java.util.*;
30  import soot.shimple.toolkits.scalar.SEvaluator.MetaConstant;
31  import soot.shimple.toolkits.scalar.SEvaluator.TopConstant;
32  import soot.shimple.toolkits.scalar.SEvaluator.BottomConstant;
33  
34  /**
35   * A powerful constant propagator and folder based on an algorithm
36   * sketched by Cytron et al that takes conditional control flow into
37   * account.  This optimization demonstrates some of the benefits of
38   * SSA -- particularly the fact that Phi nodes represent natural merge
39   * points in the control flow.
40   *
41   * @author Navindra Umanee
42   * @see <a
43   * HREF="http://citeseer.nj.nec.com/cytron91efficiently.html">Efficiently
44   * Computing Static Single Assignment Form and the Control Dependence
45   * Graph</a>
46   **/
47  public class SConstantPropagatorAndFolder extends BodyTransformer
48  {
49      public SConstantPropagatorAndFolder(Singletons.Global g) {}
50  
51      public static SConstantPropagatorAndFolder v()
52      { return G.v().soot_shimple_toolkits_scalar_SConstantPropagatorAndFolder(); }
53  
54      protected ShimpleBody sb;
55      protected boolean debug;
56      
57      protected void internalTransform(Body b, String   phaseName, Map options)
58      {
59          if(!(b instanceof ShimpleBody))
60              throw new RuntimeException  ("SConstantPropagatorAndFolder requires a ShimpleBody.");
61          
62          this.sb = (ShimpleBody) b;
63  
64          if(!sb.isSSA())
65              throw new RuntimeException  ("ShimpleBody is not in proper SSA form as required by SConstantPropagatorAndFolder.  You may need to rebuild it or use ConstantPropagatorAndFolder instead.");
66  
67          boolean pruneCFG = PhaseOptions.getBoolean(options, "prune-cfg");
68          debug = Options.v().debug();
69          debug |= sb.getOptions().debug();
70          
71          if (Options.v().verbose())
72              G.v().out.println("[" + sb.getMethod().getName() +
73                                "] Propagating and folding constants (SSA)...");
74  
75          // *** FIXME: What happens when Shimple is built with another UnitGraph?
76          SCPFAnalysis scpf = new SCPFAnalysis(new ExceptionalUnitGraph(sb));
77  
78          propagateResults(scpf.getResults());
79          if(pruneCFG){
80              removeStmts(scpf.getDeadStmts());
81              replaceStmts(scpf.getStmtsToReplace());
82          }
83      }
84  
85      /**
86       * Propagates constants to the definition and uses of the relevant
87       * locals given a mapping.  Notice that we use the Shimple
88       * implementation of LocalDefs and LocalUses.
89       **/
90      protected void propagateResults(Map localToConstant)
91      {
92          Chain units = sb.getUnits();
93          Chain locals = sb.getLocals();
94          ShimpleLocalDefs localDefs = new ShimpleLocalDefs(sb);
95          ShimpleLocalUses localUses = new ShimpleLocalUses(sb);
96          
97          Iterator localsIt = locals.iterator();
98          while(localsIt.hasNext()){
99              Local local = (Local) localsIt.next();
100             Constant constant = (Constant) localToConstant.get(local);
101             
102             if(constant instanceof MetaConstant)
103                 continue;
104 
105             // update definition
106             {
107                 DefinitionStmt stmt =
108                     (DefinitionStmt) localDefs.getDefsOf(local).get(0);
109 
110                 ValueBox defSrcBox = stmt.getRightOpBox();
111                 Value defSrc = defSrcBox.getValue();
112                 
113                 if(defSrcBox.canContainValue(constant)){
114                     defSrcBox.setValue(constant);
115 
116                     // remove dangling pointers
117                     if(defSrc instanceof UnitBoxOwner)
118                         ((UnitBoxOwner)defSrc).clearUnitBoxes();
119                 }
120                 else if(debug)
121                     G.v().out.println("Warning: Couldn't propagate constant " + constant + " to box " + defSrcBox.getValue() + " in unit " + stmt);
122             }
123             
124             // update uses
125             {
126                 Iterator usesIt = localUses.getUsesOf(local).iterator();
127                 
128                 while(usesIt.hasNext()){
129                     UnitValueBoxPair pair = (UnitValueBoxPair) usesIt.next();
130                     ValueBox useBox = pair.getValueBox();
131 
132                     if(useBox.canContainValue(constant))
133                        useBox.setValue(constant);
134                     else if(debug)
135                         G.v().out.println("Warning: Couldn't propagate constant " + constant + " to box " + useBox.getValue() + " in unit " + pair.getUnit());
136                 }
137             }
138         }
139     }
140 
141     /**
142      * Removes the given list of fall through IfStmts from the body.
143      **/
144     protected void removeStmts(List deadStmts)
145     {
146         Chain units = sb.getUnits();
147         Iterator deadIt = deadStmts.iterator();
148         while(deadIt.hasNext()){
149             Unit dead = (Unit) deadIt.next();
150             units.remove(dead);
151             dead.clearUnitBoxes();
152         }
153     }
154 
155     /**
156      * Replaces conditional branches by unconditional branches as
157      * given by the mapping.
158      **/
159     protected void replaceStmts(Map stmtsToReplace)
160     {
161         Chain units = sb.getUnits();
162         Iterator stmtsIt = stmtsToReplace.keySet().iterator();
163         while(stmtsIt.hasNext()){
164             // important not to call clearUnitBoxes() on booted since
165             // replacement uses the same UnitBox
166             Unit booted = (Unit) stmtsIt.next();
167             Unit replacement = (Unit) stmtsToReplace.get(booted);
168             units.swapWith(booted, replacement);
169         }
170     }
171 }
172 
173 /**
174  * The actual branching flow analysis implementation.  Briefly, a
175  * sketch of the sketch from the Cytron et al paper:
176  *
177  * <p> Initially the algorithm assumes that each edge is unexecutable
178  * (the entry nodes are reachable) and that each variable is constant
179  * with an unknown value, Top.  Assumptions are corrected until they
180  * stabilise.
181  *
182  * <p> For example, if <tt>q</tt> is found to be not a constant (Bottom)
183  * in <tt>if(q == 0) goto label1</tt> then both edges leaving the the
184  * statement are considered executable, if <tt>q</tt> is found to be a
185  * constant then only one of the edges are executable.
186  *
187  * <p> Whenever a reachable definition statement such as "x = 3" is
188  * found, the information is propagated to all uses of x (this works
189  * due to the SSA property).
190  *
191  * <p> Perhaps the crucial point is that if a node such as <tt>x =
192  * Phi(x_1, x_2)</tt> is ever found, information on <tt>x</tt> is
193  * assumed as follows:
194  *
195  * <ul>
196  *  <li>If <tt>x_1</tt> and <tt>x_2</tt> are the same assumed
197  *  constant, <tt>x</tt> is assumed to be that constant.  If they are
198  *  not the same constant, <tt>x</tt> is Bottom.</li>
199  *
200  *  <li>If either one is Top and the other is a constant, <tt>x</tt>
201  *  is assumed to be the same as the known constant.</li>
202  *
203  *  <li>If either is Bottom, <tt>x</tt> is assumed to be Bottom.</li>
204  * </ul>
205  *
206  * <p> The crucial point about the crucial point is that if
207  * definitions of <tt>x_1</tt> or <tt>x_2</tt> are never reached, the
208  * Phi node will still assume them to be Top and hence they will not
209  * influence the decision as to whether <tt>x</tt> is a constant or not.
210  **/
211 class SCPFAnalysis extends ForwardBranchedFlowAnalysis
212 {
213     protected FlowSet emptySet;
214 
215     /**
216      * A mapping of the locals to their current assumed constant value
217      * (which may be Top or Bottom).
218      **/
219     protected Map localToConstant;
220 
221     /**
222      * A map from conditional branches to their possible replacement 
223      * unit, an unconditional branch.
224      **/
225     protected Map stmtToReplacement;
226 
227     /**
228      * A list of IfStmts that always fall through.
229      **/
230     protected List deadStmts;
231 
232 
233     /**
234      * Returns the localToConstant map.
235      **/
236     public Map getResults()
237     {
238         return localToConstant;
239     }
240 
241     /**
242      * Returns the list of fall through IfStmts.
243      **/
244     public List getDeadStmts()
245     {
246         return deadStmts;
247     }
248 
249     /**
250      * Returns a Map from conditional branches to the unconditional branches
251      * that can replace them.
252      **/
253     public Map getStmtsToReplace()
254     {
255         return stmtToReplacement;
256     }
257     
258     public SCPFAnalysis(UnitGraph graph)
259     {
260         super(graph);
261         emptySet = new ArraySparseSet();
262         stmtToReplacement = new HashMap();
263         deadStmts = new ArrayList();
264         
265         // initialise localToConstant map -- assume all scalars are
266         // constant (Top)
267         {
268             Chain locals = graph.getBody().getLocals();
269             Iterator localsIt = locals.iterator();
270             localToConstant = new HashMap(graph.size() * 2 + 1, 0.7f);
271 
272             while(localsIt.hasNext()){
273                 Local local = (Local) localsIt.next();
274                 localToConstant.put(local, TopConstant.v());
275             }
276         }
277 
278         doAnalysis();
279     }
280 
281     // *** NOTE: this is here because ForwardBranchedFlowAnalysis does
282     // *** not handle exceptional control flow properly in the
283     // *** dataflow analysis.  this should be removed when
284     // *** ForwardBranchedFlowAnalysis is fixed.
285     protected boolean treatTrapHandlersAsEntries()
286     {
287         return true;
288     }
289 
290     /**
291      * If a node has empty IN sets we assume that it is not reachable.
292      * Hence, we initialise the entry sets to be non-empty to indicate
293      * that they are reachable.
294      **/
295     protected Object   entryInitialFlow()
296     {
297         FlowSet entrySet = (FlowSet) emptySet.emptySet();
298         entrySet.add(TopConstant.v());
299         return entrySet;
300     }
301 
302     /**
303      * All other nodes are assumed to be unreachable by default.
304      **/
305     protected Object   newInitialFlow()
306     {
307         return emptySet.emptySet();
308     }
309 
310     /**
311      * Since we are interested in control flow from all branches,
312      * take the union.
313      **/
314     protected void merge(Object   in1, Object   in2, Object   out)
315     {
316         FlowSet fin1 = (FlowSet) in1;
317         FlowSet fin2 = (FlowSet) in2;
318         FlowSet fout = (FlowSet) out;
319 
320         fin1.union(fin2, fout);
321     }
322 
323     /**
324      * Defer copy to FlowSet.
325      **/
326     protected void copy(Object   source, Object   dest)
327     {
328         FlowSet fource = (FlowSet) source;
329         FlowSet fest = (FlowSet) dest;
330 
331         fource.copy(fest);
332     }
333 
334     /**
335      * If a node has an empty in set, it is considered unreachable.
336      * Otherwise the node is examined and if any assumptions have to
337      * be corrected, a Pair containing the corrected assumptions is
338      * flowed to the reachable nodes.  If no assumptions have to be
339      * corrected then no information other than the in set is
340      * propagated to the reachable nodes.
341      *
342      * <p> Pair serves no other purpose than to keep the analysis
343      * flowing for as long as needed.  The final results are
344      * accumulated in the localToConstant map.
345      **/
346     protected void flowThrough(Object   in, Unit s, List fallOut, List branchOuts)
347     {
348         FlowSet fin = (FlowSet) ((FlowSet)in).clone();
349 
350         // not reachable
351         if(fin.isEmpty())
352             return;
353         
354         // If s is a definition, check if any assumptions have to be
355         // corrected.
356         Pair pair = processDefinitionStmt(s);
357 
358         if(pair != null)
359             fin.add(pair);
360         
361         // normal, non-branching statement
362         if(!s.branches() && s.fallsThrough()){
363             Iterator fallOutIt = fallOut.iterator();
364             while(fallOutIt.hasNext()){
365                 FlowSet fallSet = (FlowSet) fallOutIt.next();
366                 fallSet.union(fin);
367             }
368 
369             return;
370         }
371 
372         /* determine which nodes are reachable. */
373         
374         boolean conservative = true;
375         boolean fall = false;
376         boolean branch = false;
377         FlowSet oneBranch = null;
378         
379         IFSTMT:
380         {
381         if(s instanceof IfStmt){
382             IfStmt ifStmt = (IfStmt) s;
383             Value cond = ifStmt.getCondition();
384             Constant constant =
385                 SEvaluator.getFuzzyConstantValueOf(cond, localToConstant);
386             
387             // flow both ways
388             if(constant instanceof BottomConstant){
389                 deadStmts.remove(ifStmt);
390                 stmtToReplacement.remove(ifStmt);
391                 break IFSTMT;
392             }
393 
394             // no flow
395             if(constant instanceof TopConstant)
396                 return;
397 
398             /* determine whether to flow through or branch */
399             
400             conservative = false;
401 
402             Constant trueC = IntConstant.v(1);
403             Constant falseC = IntConstant.v(0);
404 
405             if(constant.equals(trueC)){
406                 branch = true;
407                 GotoStmt gotoStmt =
408                     Jimple.v().newGotoStmt(ifStmt.getTargetBox());
409                 stmtToReplacement.put(ifStmt, gotoStmt);
410             }
411 
412             if(constant.equals(falseC)){
413                 fall = true;
414                 deadStmts.add(ifStmt);
415             }
416         }
417         } // end IFSTMT
418 
419         TABLESWITCHSTMT:
420         {
421         if(s instanceof TableSwitchStmt){
422             TableSwitchStmt table = (TableSwitchStmt) s;
423             Value keyV = table.getKey();
424             Constant keyC =
425                 SEvaluator.getFuzzyConstantValueOf(keyV, localToConstant);
426 
427             // flow all branches
428             if(keyC instanceof BottomConstant){
429                 stmtToReplacement.remove(table);
430                 break TABLESWITCHSTMT;
431             }
432 
433             // no flow
434             if(keyC instanceof TopConstant)
435                 return;
436 
437             // flow all branches
438             if(!(keyC instanceof IntConstant))
439                 break TABLESWITCHSTMT;
440 
441             /* find the one branch we need to flow to */
442 
443             conservative = false;
444             
445             int key = ((IntConstant)keyC).value;
446             int low = table.getLowIndex();
447             int high = table.getHighIndex();
448             int index = key - low;
449 
450             UnitBox branchBox = null;
451             if(index < 0 || index > high)
452                 branchBox = table.getDefaultTargetBox();
453             else
454                 branchBox = table.getTargetBox(index);
455 
456             GotoStmt gotoStmt = Jimple.v().newGotoStmt(branchBox);
457             stmtToReplacement.put(table, gotoStmt);
458             
459             List unitBoxes = table.getUnitBoxes();
460             int setIndex = unitBoxes.indexOf(branchBox);
461             oneBranch = (FlowSet) branchOuts.get(setIndex);
462         }
463         } // end TABLESWITCHSTMT
464 
465         LOOKUPSWITCHSTMT:
466         {
467         if(s instanceof LookupSwitchStmt){
468             LookupSwitchStmt lookup = (LookupSwitchStmt) s;
469             Value keyV = lookup.getKey();
470             Constant keyC =
471                 SEvaluator.getFuzzyConstantValueOf(keyV, localToConstant);
472 
473             // flow all branches
474             if(keyC instanceof BottomConstant){
475                 stmtToReplacement.remove(lookup);
476                 break LOOKUPSWITCHSTMT;
477             }
478 
479             // no flow
480             if(keyC instanceof TopConstant)
481                 return;
482 
483             // flow all branches
484             if(!(keyC instanceof IntConstant))
485                 break LOOKUPSWITCHSTMT;
486 
487             /* find the one branch we need to flow to */
488 
489             conservative = false;
490             
491             int index = lookup.getLookupValues().indexOf(keyC);
492 
493             UnitBox branchBox = null;
494             if(index == -1)
495                 branchBox = lookup.getDefaultTargetBox();
496             else
497                 branchBox = lookup.getTargetBox(index);
498 
499             GotoStmt gotoStmt = Jimple.v().newGotoStmt(branchBox);
500             stmtToReplacement.put(lookup, gotoStmt);
501             
502             List unitBoxes = lookup.getUnitBoxes();
503             int setIndex = unitBoxes.indexOf(branchBox);
504             oneBranch = (FlowSet) branchOuts.get(setIndex);
505         }
506         } // end LOOKUPSWITCHSTMT
507         
508         // conservative control flow estimates
509         if(conservative){
510             fall = s.fallsThrough();
511             branch = s.branches();
512         }
513 
514         if(fall){
515             Iterator fallOutIt = fallOut.iterator();
516             while(fallOutIt.hasNext()){
517                 FlowSet fallSet = (FlowSet) fallOutIt.next();
518                 fallSet.union(fin);
519             }
520         }
521         
522         if(branch){
523             Iterator branchOutsIt = branchOuts.iterator();
524             while(branchOutsIt.hasNext()){
525                 FlowSet branchSet = (FlowSet) branchOutsIt.next();
526                 branchSet.union(fin);
527             }
528         }
529 
530         if(oneBranch != null){
531             oneBranch.union(fin);
532         }
533     }
534 
535     /**
536      * Returns (Unit, Constant) pair if an assumption has  changed 
537      * due to the fact that u is reachable.  Else returns null.
538      **/
539     protected Pair processDefinitionStmt(Unit u)
540     {
541         if(!(u instanceof DefinitionStmt))
542             return null;
543 
544         DefinitionStmt dStmt = (DefinitionStmt) u;
545         
546         Local local;
547 
548         {
549             Value value = dStmt.getLeftOp();
550             if(!(value instanceof Local))
551                 return null;
552             local = (Local) value;
553         }
554 
555         /* update assumptions */
556 
557         Value rightOp = dStmt.getRightOp();
558         Constant constant =
559             SEvaluator.getFuzzyConstantValueOf(rightOp, localToConstant);
560         
561         if(!merge(local, constant))
562             return null;
563 
564         return new Pair(u, localToConstant.get(local));
565     }
566     
567     /**
568      * Verifies if the given assumption "constant" changes the
569      * previous assumption about "local" and merges the information
570      * into the localToConstant map.  Returns true if something
571      * changed.
572      **/
573     protected boolean merge(Local local, Constant constant)
574     {
575         Constant current = (Constant) localToConstant.get(local);
576 
577         if(current instanceof BottomConstant) 
578             return false;
579 
580         if(current instanceof TopConstant){
581             localToConstant.put(local, constant);
582             return true;
583         }
584 
585         if(current.equals(constant))
586             return false;
587 
588         // not equal
589         localToConstant.put(local, BottomConstant.v());
590         return true;
591     }
592 }
593
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags