KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > soot > jimple > toolkits > scalar > DeadAssignmentEliminator


1 /* Soot - a J*va Optimization Framework
2  * Copyright (C) 1997-1999 Raja Vallee-Rai
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 /*
21  * Modified by the Sable Research Group and others 1997-1999.
22  * See the 'credits' file distributed with Soot for the complete list of
23  * contributors. (Soot is distributed at http://www.sable.mcgill.ca/soot)
24  */
25
26
27
28
29
30
31 package soot.jimple.toolkits.scalar;
32 import soot.options.*;
33
34 import soot.*;
35 import soot.jimple.*;
36 import soot.toolkits.scalar.*;
37 import soot.util.*;
38 import soot.toolkits.graph.*;
39 import java.util.*;
40
41 public class DeadAssignmentEliminator extends BodyTransformer
42 {
43     public DeadAssignmentEliminator( Singletons.Global g ) {}
44     public static DeadAssignmentEliminator v() { return G.v().soot_jimple_toolkits_scalar_DeadAssignmentEliminator(); }
45
46     /** Eliminates dead code in a linear fashion. Complexity is linear
47         with respect to the statements.
48         
49         Does not work on grimp code because of the check on the right hand
50         side for side effects.
51     */
52     
53     protected void internalTransform(Body b, String JavaDoc phaseName, Map options)
54     {
55         boolean eliminateOnlyStackLocals = PhaseOptions.getBoolean(options, "only-stack-locals");
56
57         if(Options.v().verbose())
58             G.v().out.println("[" + b.getMethod().getName() +
59                 "] Eliminating dead code...");
60         
61         if(Options.v().time())
62             Timers.v().deadCodeTimer.start();
63
64         Set essentialStmts = new HashSet();
65         LinkedList toVisit = new LinkedList();
66         Chain units = b.getUnits();
67         
68         // Make a first pass through the statements, noting
69 // the statements we must absolutely keep.
70 {
71             Iterator stmtIt = units.iterator();
72             
73             while(stmtIt.hasNext())
74             {
75                 Stmt s = (Stmt) stmtIt.next();
76                 boolean isEssential = true;
77                  
78                 if(s instanceof NopStmt)
79                     isEssential = false;
80                  
81                 if(s instanceof AssignStmt)
82                 {
83                     AssignStmt as = (AssignStmt) s;
84                     
85                     if(as.getLeftOp() instanceof Local &&
86                         (!eliminateOnlyStackLocals ||
87                             ((Local) as.getLeftOp()).getName().startsWith("$")))
88                     {
89                         Value rhs = as.getRightOp();
90                     
91                         isEssential = false;
92
93                         if(rhs instanceof InvokeExpr ||
94                            rhs instanceof ArrayRef)
95                         {
96                            // Note that ArrayRef and InvokeExpr all can
97 // have side effects (like throwing a null pointer exception)
98
99                             isEssential = true;
100                         }
101
102                         if(rhs instanceof InstanceFieldRef &&
103                            !(!b.getMethod().isStatic() &&
104                              ((InstanceFieldRef)rhs).getBase() ==
105                                     b.getThisLocal()))
106                         {
107                             // Any InstanceFieldRef may have side effects,
108 // unless the base is reading from 'this'
109 // in a non-static method
110 isEssential = true;
111                         }
112
113
114                         else if(rhs instanceof DivExpr ||
115                             rhs instanceof RemExpr)
116                         {
117                             BinopExpr expr = (BinopExpr) rhs;
118                             
119                             if(expr.getOp1().getType().equals(IntType.v()) ||
120                                 expr.getOp2().getType().equals(IntType.v()) ||
121                                expr.getOp1().getType().equals(LongType.v()) ||
122                                 expr.getOp2().getType().equals(LongType.v()))
123                             {
124                                 // Can trigger a division by zero
125 isEssential = true;
126                             }
127                         }
128
129                         else if(rhs instanceof CastExpr)
130                         {
131                             // Can trigger ClassCastException
132 isEssential = true;
133                         }
134                     }
135                 }
136                 
137                 if(isEssential)
138                 {
139                     essentialStmts.add(s);
140                     toVisit.addLast(s);
141                 }
142             }
143         }
144
145         ExceptionalUnitGraph graph = new ExceptionalUnitGraph(b);
146         LocalDefs defs = new SmartLocalDefs(graph, new SimpleLiveLocals(graph));
147         LocalUses uses = new SimpleLocalUses(graph, defs);
148         
149         // Add all the statements which are used to compute values
150 // for the essential statements, recursively
151 {
152             
153             while(!toVisit.isEmpty())
154             {
155                 Stmt s = (Stmt) toVisit.removeFirst();
156                 Iterator boxIt = s.getUseBoxes().iterator();
157                                 
158                 while(boxIt.hasNext())
159                 {
160                     ValueBox box = (ValueBox) boxIt.next();
161                     
162                     if(box.getValue() instanceof Local)
163                     {
164                         Iterator defIt = defs.getDefsOfAt(
165                             (Local) box.getValue(), s).iterator();
166                         
167                         while(defIt.hasNext())
168                         {
169                             // Add all the definitions as essential stmts
170
171                             Stmt def = (Stmt) defIt.next();
172                             
173                             if(!essentialStmts.contains(def))
174                             {
175                                 essentialStmts.add(def);
176                                 toVisit.addLast(def);
177                             }
178                         }
179                     }
180                 }
181             }
182         }
183         
184         // Remove the dead statements
185 {
186             Iterator stmtIt = units.iterator();
187             
188             while(stmtIt.hasNext())
189             {
190                 Stmt s = (Stmt) stmtIt.next();
191                 
192                 if(!essentialStmts.contains(s)){
193                     stmtIt.remove();
194                     s.clearUnitBoxes();
195                 }
196                 else if(s instanceof AssignStmt &&
197                     ((AssignStmt) s).getLeftOp() == ((AssignStmt) s).getRightOp() &&
198                     ((AssignStmt) s).getLeftOp() instanceof Local)
199                 {
200                     // Stmt is of the form a = a which is useless
201
202                     stmtIt.remove();
203                     s.clearUnitBoxes();
204                 }
205             }
206         }
207         
208         // Eliminate dead assignments from invokes such as x = f(), where
209 // x is no longer used
210 {
211             Iterator stmtIt = units.snapshotIterator();
212             
213             while(stmtIt.hasNext())
214             {
215                 Stmt s = (Stmt) stmtIt.next();
216                 
217                 if(s instanceof AssignStmt &&
218                     s.containsInvokeExpr())
219                 {
220                     Local l = (Local) ((AssignStmt) s).getLeftOp();
221                     InvokeExpr e = (InvokeExpr) s.getInvokeExpr();
222                     
223                     // Just find one use of l which is essential
224 {
225                         Iterator useIt = uses.getUsesOf(s).iterator();
226                         boolean isEssential = false;
227                         
228                         while(useIt.hasNext())
229                         {
230                             UnitValueBoxPair pair = (UnitValueBoxPair)
231                                 useIt.next();
232                                 
233                             if(essentialStmts.contains(pair.unit))
234                             {
235                                 isEssential = true;
236                                 break;
237                             }
238                         }
239                         
240                         if(!isEssential)
241                         {
242                             // Transform it into a simple invoke.
243
244                             Stmt newInvoke = Jimple.v().newInvokeStmt(e);
245                             newInvoke.addAllTagsOf(s);
246                             
247                             units.swapWith(s, newInvoke);
248                         }
249                     }
250                 }
251             }
252         }
253         
254         if(Options.v().time())
255             Timers.v().deadCodeTimer.end();
256
257     }
258 }
259
260
261
262
263
264
265
266
Popular Tags