KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > soot > dava > toolkits > base > AST > traversals > CopyPropagation


1 /* Soot - a J*va Optimization Framework
2  * Copyright (C) 2005 Nomair A. Naeem
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  * Maintained by Nomair A. Naeem
22  */
23
24 /*
25  * Change log: * November 22nd 2005: Moved this class from structuredAnalysis
26  * package to traversals package. Since this is a traversal not an analysis
27  *
28  * * November 23rd 2005. MASSIVE CHANGES
29  * Created a Class LocalVariableCleaner which should
30  * be run after running copy prop and moved some of the
31  * functionality from this class to localVariableCleaner
32  */
33
34 /*
35  * TODO: November 23rd, 2005. What if removeStmt removes a copyStmt and that was the only
36  * stmt in the stmtSequenceBlock. Shouldnt that block be removed??
37  */
38
39 package soot.dava.toolkits.base.AST.traversals;
40
41 import soot.*;
42 import java.util.*;
43 import soot.jimple.*;
44 import soot.dava.internal.javaRep.*;
45 import soot.dava.internal.AST.*;
46 import soot.dava.internal.asg.*;
47 import soot.dava.toolkits.base.AST.analysis.*;
48 import soot.dava.toolkits.base.AST.structuredAnalysis.*;
49
50 /*
51   This analysis uses the results from
52       1 ReachingCopies
53       2 uD and dU chains
54   to eliminate extra copies
55
56
57   ALGORITHM:
58   When you encounter a copy stmt (a=b) find all uses of local a (using dU chain)
59
60   if For ALL uses the ReachingCopies set contains copy stmt (a=b)
61     Remove Copy Stmt
62     Replace use of a with use of b
63
64     Note:
65       copy stmts can be encountered in:
66         a, ASTStatementSequenceNode
67     b, for loop init -------> dont want to remove this
68     c, for loop update ---------> dont want to remove this
69
70 */
71
72 public class CopyPropagation extends DepthFirstAdapter{
73     ASTNode AST;
74     ASTUsesAndDefs useDefs;
75     ReachingCopies reachingCopies;
76     ASTParentNodeFinder parentOf;
77     
78     boolean someCopyStmtModified;
79
80     //need to keep track of whenever we modify the AST
81 //this flag is set to true whenever a stmt is removed or a local substituted for another
82 boolean ASTMODIFIED;
83
84     public CopyPropagation(ASTNode AST){
85     super();
86     someCopyStmtModified=false;
87     this.AST=AST;
88     ASTMODIFIED=false;
89     setup();
90     }
91
92     public CopyPropagation(boolean verbose,ASTNode AST){
93     super(verbose);
94     someCopyStmtModified=false;
95     this.AST=AST;
96     ASTMODIFIED=false;
97     setup();
98     }
99
100
101
102     private void setup(){
103     //create the uD and dU chains
104 useDefs = new ASTUsesAndDefs(AST);
105     AST.apply(useDefs);
106     
107     //apply the reaching copies Structural flow Analysis
108 reachingCopies = new ReachingCopies(AST);
109
110     parentOf = new ASTParentNodeFinder();
111     AST.apply(parentOf);
112     }
113
114
115     /*
116      * If any copy stmt was removed or any substitution made
117      * we might be able to get better results by redoing the analysis
118      */
119     public void outASTMethodNode(ASTMethodNode node){
120     if(ASTMODIFIED){
121         //need to rerun copy prop
122
123         //before running a structured flow analysis have to do this one
124 AST.apply(ClosestAbruptTargetFinder.v());
125
126         //System.out.println("\n\n\nCOPY PROP\n\n\n\n");
127
128         CopyPropagation prop1 = new CopyPropagation(AST);
129         AST.apply(prop1);
130     }
131     }
132
133
134
135
136     public void inASTStatementSequenceNode(ASTStatementSequenceNode node){
137     List statements = node.getStatements();
138     Iterator it = statements.iterator();
139     
140     while(it.hasNext()){
141         AugmentedStmt as = (AugmentedStmt)it.next();
142         Stmt s = as.get_Stmt();
143         if(isCopyStmt(s)){
144         handleCopyStmt((DefinitionStmt)s);
145         }
146     }
147     }
148     
149
150
151
152     public boolean isCopyStmt(Stmt s){
153     if(!(s instanceof DefinitionStmt)){
154         //only definition stmts can be copy stmts
155 return false;
156     }
157
158     // x = expr;
159 //check if expr is a local in which case this is a copy
160 Value leftOp = ((DefinitionStmt)s).getLeftOp();
161     Value rightOp = ((DefinitionStmt)s).getRightOp();
162
163     if(leftOp instanceof Local && rightOp instanceof Local){
164         //this is a copy statement
165 return true;
166     }
167     return false;
168     }
169
170
171
172     /*
173      * Given a copy stmt (a=b) find all uses of local a (using dU chain)
174
175      * if For ALL uses the ReachingCopies set contains copy stmt (a=b)
176      * Remove Copy Stmt
177      * Replace use of a with use of b
178     */
179     public void handleCopyStmt(DefinitionStmt copyStmt){
180     //System.out.println("COPY STMT FOUND-----------------------------------"+copyStmt);
181
182     //get defined local...safe to cast since this is copyStmt
183 Local definedLocal = (Local)copyStmt.getLeftOp();
184
185     //get all uses of this local from the dU chain
186 Object JavaDoc temp = useDefs.getDUChain(copyStmt);
187
188     ArrayList uses= new ArrayList();
189     if(temp != null){
190         uses = (ArrayList)temp;
191     }
192
193     //the uses list contains all stmts / nodes which use the definedLocal
194
195     //check if uses is non-empty
196 if(uses.size()!=0){
197         
198         //System.out.println(">>>>The defined local:"+definedLocal+" is used in the following");
199 //System.out.println("\n numof uses:"+uses.size()+uses+">>>>>>>>>>>>>>>\n\n");
200
201
202         //continuing with copy propagation algorithm
203
204         //create localPair for copy stmt in question...same to cast as its a copyStmt
205 Local leftLocal = (Local)copyStmt.getLeftOp();
206         Local rightLocal = (Local)copyStmt.getRightOp();
207
208         ReachingCopies.LocalPair localPair = reachingCopies.new LocalPair(leftLocal,rightLocal);
209         
210         //check for all the non zero uses
211 Iterator useIt = uses.iterator();
212         while(useIt.hasNext()){
213         //check that the reaching copies of each use has the copy stmt
214 //a use is either a statement or a node(condition, synch, switch , for etc)
215 Object JavaDoc tempUse = useIt.next();
216         
217         DavaFlowSet reaching = reachingCopies.getReachingCopies(tempUse);
218         
219         if(!reaching.contains(localPair)){
220             //this copy stmt does not reach this use
221 //no copy elimination can be done
222 return;
223         }
224         }
225
226         //if we get here that means that the copy stmt reached each use
227
228         //replace each use of a with b
229 useIt = uses.iterator();
230         while(useIt.hasNext()){
231         Object JavaDoc tempUse = useIt.next();
232         replace(leftLocal,rightLocal,tempUse);
233         }
234
235         //remove copy stmt a=b
236 removeStmt(copyStmt);
237        
238
239         if(someCopyStmtModified){
240         //get all the analyses re-set
241 setup();
242         someCopyStmtModified=false;
243         }
244     }
245     else{
246         //the copy stmt is usesless since the definedLocal is not being used anywhere after definition
247 //System.out.println("The defined local:"+definedLocal+" is not used anywhere");
248 removeStmt(copyStmt);
249     }
250     }
251
252
253
254     public void removeStmt(Stmt stmt){
255     Object JavaDoc tempParent = parentOf.getParentOf(stmt);
256     if(tempParent == null){
257         //System.out.println("NO PARENT FOUND CANT DO ANYTHING");
258 return;
259     }
260
261     //parents are always ASTNodes, hence safe to cast
262 ASTNode parent = (ASTNode)tempParent;
263
264     //REMOVING STMT
265 if(!(parent instanceof ASTStatementSequenceNode)){
266         //parent of a statement should always be a ASTStatementSequenceNode
267 throw new RuntimeException JavaDoc("Found a stmt whose parent is not an ASTStatementSequenceNode");
268     }
269     ASTStatementSequenceNode parentNode = (ASTStatementSequenceNode)parent;
270
271     ArrayList newSequence = new ArrayList();
272     
273     Iterator it = parentNode.getStatements().iterator();
274     while (it.hasNext()){
275         AugmentedStmt as = (AugmentedStmt)it.next();
276         Stmt s = as.get_Stmt();
277         if(s.toString().compareTo(stmt.toString())!=0){
278         //this is not the stmt to be removed
279 newSequence.add(as);
280         }
281     }
282     //System.out.println("STMT REMOVED---------------->"+stmt);
283 parentNode.setStatements(newSequence);
284
285     ASTMODIFIED=true;
286     return;
287     }
288
289
290
291
292
293
294     /*
295      * If the value inside a useBox is a local with toString giving <from>
296      * this is replaced by the local <to>
297      */
298     public void replaceBoxes(Local from, Local to, List useBoxes){
299     Iterator it = useBoxes.iterator();
300     while(it.hasNext()){
301         ValueBox valBox =(ValueBox)it.next();
302         Value val = valBox.getValue();
303         if(val instanceof Local){
304         Local local = (Local)val;
305         if(local.getName().compareTo(from.getName())==0){
306             //replace the name with the one in "to"
307 valBox.setValue(to);
308             ASTMODIFIED=true;
309         }
310         }
311     }
312     }
313
314
315
316
317
318     /*
319      * Method goes depth first into the condition tree and returns a list of use boxes
320      */
321     public List getUseList(ASTCondition cond){
322     if(cond instanceof ASTAggregatedCondition){
323         ArrayList useList = new ArrayList();
324         useList.addAll(getUseList(((ASTAggregatedCondition)cond).getLeftOp()));
325         useList.addAll(getUseList(((ASTAggregatedCondition)cond).getRightOp()));
326         return useList;
327     }
328     else if(cond instanceof ASTUnaryCondition){
329         //get uses from unary condition
330 Value val = ((ASTUnaryCondition)cond).getValue();
331         return val.getUseBoxes();
332     }
333     else if(cond instanceof ASTBinaryCondition){
334         //get uses from binaryCondition
335 Value val = ((ASTBinaryCondition)cond).getConditionExpr();
336         return val.getUseBoxes();
337     }
338     else{
339         throw new RuntimeException JavaDoc("Method getUseList in CopyPropagation encountered unknown condition type");
340     }
341     }
342
343
344
345
346
347
348
349
350     /*
351      * Invoked by handleCopyStmt to replace the use of local <from>
352      * to the use of local <to> in <use>
353      *
354      * Notice <use> can be a stmt or an ASTNode
355      */
356
357     public void replace(Local from, Local to, Object JavaDoc use){
358     if(use instanceof Stmt){
359         Stmt s = (Stmt)use;
360         if(isCopyStmt(s)){
361         someCopyStmtModified=true;
362         }
363         List useBoxes = s.getUseBoxes();
364         replaceBoxes(from,to,useBoxes);
365     }
366     else if (use instanceof ASTNode){
367         if (use instanceof ASTSwitchNode){
368         ASTSwitchNode temp = (ASTSwitchNode)use;
369         Value val = (Value)temp.get_Key();
370         if(val instanceof Local){
371             if(((Local)val).getName().compareTo(from.getName())==0){
372             //replace the name with the one in "to"
373 ASTMODIFIED=true;
374             temp.set_Key(to);
375             }
376         }
377         else{
378             List useBoxes = val.getUseBoxes();
379             replaceBoxes(from,to,useBoxes);
380         }
381         }
382         else if (use instanceof ASTSynchronizedBlockNode){
383         ASTSynchronizedBlockNode temp = (ASTSynchronizedBlockNode)use;
384         Local local = temp.getLocal();
385         if(local.getName().compareTo(from.getName())==0){
386             //replace the name with the one in "to"
387 temp.setLocal(to);
388             ASTMODIFIED=true;
389         }
390         }
391         else if(use instanceof ASTIfNode){
392         ASTIfNode temp = (ASTIfNode)use;
393         ASTCondition cond = temp.get_Condition();
394         List useBoxes = getUseList(cond);
395         replaceBoxes(from,to,useBoxes);
396         }
397         else if (use instanceof ASTIfElseNode){
398         ASTIfElseNode temp = (ASTIfElseNode)use;
399         ASTCondition cond = temp.get_Condition();
400         List useBoxes = getUseList(cond);
401         replaceBoxes(from,to,useBoxes);
402         }
403         else if (use instanceof ASTWhileNode){
404         ASTWhileNode temp = (ASTWhileNode)use;
405         ASTCondition cond = temp.get_Condition();
406         List useBoxes = getUseList(cond);
407         replaceBoxes(from,to,useBoxes);
408         }
409         else if (use instanceof ASTDoWhileNode){
410         ASTDoWhileNode temp = (ASTDoWhileNode)use;
411         ASTCondition cond = temp.get_Condition();
412         List useBoxes = getUseList(cond);
413         replaceBoxes(from,to,useBoxes);
414         }
415         else if (use instanceof ASTForLoopNode){
416         ASTForLoopNode temp = (ASTForLoopNode)use;
417
418         //init
419 List init = temp.getInit();
420         Iterator it = init.iterator();
421         while(it.hasNext()){
422             AugmentedStmt as = (AugmentedStmt)it.next();
423             Stmt s = as.get_Stmt();
424             replace(from,to,s);
425         }
426
427
428         //update
429 List update = temp.getUpdate();
430         it = update.iterator();
431         while(it.hasNext()){
432             AugmentedStmt as = (AugmentedStmt)it.next();
433             Stmt s = as.get_Stmt();
434             replace(from,to,s);
435         }
436
437
438         //condition
439 ASTCondition cond = temp.get_Condition();
440         List useBoxes = getUseList(cond);
441         replaceBoxes(from,to,useBoxes);
442         }
443         else{
444         throw new RuntimeException JavaDoc("Encountered an unknown ASTNode in copyPropagation method replace");
445         }
446     }
447     else{
448         throw new RuntimeException JavaDoc("Encountered an unknown use in copyPropagation method replace");
449     }
450
451     }
452
453
454 }
Popular Tags