KickJava   Java API By Example, From Geeks To Geeks.

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


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 to traversals
26  * as this is a traversal
27  * * November 22nd 2005 Reasoned about correctness of code
28  * * Extensively tested this
29  */
30
31
32 package soot.dava.toolkits.base.AST.traversals;
33
34 import soot.*;
35 import java.util.*;
36 import soot.jimple.*;
37 import soot.dava.internal.asg.*;
38 import soot.dava.internal.AST.*;
39 import soot.dava.internal.javaRep.*;
40 import soot.dava.toolkits.base.AST.analysis.*;
41 import soot.dava.toolkits.base.AST.structuredAnalysis.*;
42
43 /*
44   THE ALGORITHM USES THE RESULTS OF REACHINGDEFS STRUCTURAL FLOW ANALYSIS
45
46   DEFINITION uD Chain:
47      For a use of variable x, the uD Chain gives ALL POSSIBLE definitions of x that can reach the use x
48
49   DEFINITION dU Chain:
50      For a definition d, the dU Chain gives all places where this definition is used
51
52
53   Need to be very clear when a local can be used
54   It can be used in the following places:
55   a, a conditional in if, ifelse, while , do while, for condition
56   b, in the for init or update
57   c, in a switch choice
58   d, in a syncrhnoized block
59   d, in a statement
60
61 */
62 public class ASTUsesAndDefs extends DepthFirstAdapter{
63     HashMap uD; //mapping a use to all possible definitions
64 HashMap dU; //mapping a def to all possible uses
65 ReachingDefs reaching; //using structural analysis information
66
67     public ASTUsesAndDefs(ASTNode AST){
68     uD = new HashMap();
69     dU = new HashMap();
70     reaching = new ReachingDefs(AST);
71     }
72
73     public ASTUsesAndDefs(boolean verbose,ASTNode AST){
74     super(verbose);
75     uD = new HashMap();
76     dU = new HashMap();
77     reaching = new ReachingDefs(AST);
78     }
79
80
81
82
83
84     /*
85      * Method is used to strip away boxes from the actual values
86      * only those are returned which are locals
87      */
88     private List getUsesFromBoxes(List useBoxes){
89     ArrayList toReturn = new ArrayList();
90     Iterator it = useBoxes.iterator();
91     while(it.hasNext()){
92         Value val =((ValueBox)it.next()).getValue();
93         if(val instanceof Local)
94         toReturn.add(val);
95     }
96     //System.out.println("VALUES:"+toReturn);
97 return toReturn;
98     }
99
100
101
102
103
104     public void checkStatementUses(Stmt s,Object JavaDoc useNodeOrStatement){
105     List useBoxes = s.getUseBoxes();
106     //System.out.println("Uses in this statement:"+useBoxes);
107 List uses= getUsesFromBoxes(useBoxes);
108     //System.out.println("Local Uses in this statement:"+uses);
109
110     Iterator it = uses.iterator();
111     while(it.hasNext()){
112         Local local = (Local)it.next();
113         createUDDUChain(local,useNodeOrStatement);
114     }//end of going through all locals uses in statement
115
116
117     /*
118       see if this is a def stmt in which case add an empty entry into the dU chain
119
120       The wisdowm behind this is that later on when this definition is used we will
121       use this arraylist to store the uses of this definition
122     */
123     if(s instanceof DefinitionStmt){
124         //check if dU doesnt already have something for this
125 if(dU.get(s)==null){
126         dU.put(s,new ArrayList());
127         }
128     }
129     }
130
131     
132
133
134
135
136
137
138     /*
139      * The method gets the reaching defs of local used
140      * Then all the possible defs are added into the uD chain of the node
141      * The use is added to all the defs reaching this node
142      */
143     public void createUDDUChain(Local local, Object JavaDoc useNodeOrStatement){
144     //System.out.println("Local is:"+local);
145 //System.out.println("useNodeOrStatement is"+useNodeOrStatement);
146
147     List reachingDefs = reaching.getReachingDefs(local,useNodeOrStatement);
148     //System.out.println("Reaching def for:"+local+" are:"+reachingDefs);
149
150     //add the reaching defs into the use def chain
151 Object JavaDoc tempObj = uD.get(useNodeOrStatement);
152     if(tempObj != null){
153         List tempList = (List)tempObj;
154         tempList.addAll(reachingDefs);
155         uD.put(useNodeOrStatement,tempList);
156     }
157     else
158         uD.put(useNodeOrStatement,reachingDefs);
159     
160     //add the use into the def use chain
161 Iterator defIt = reachingDefs.iterator();
162     while(defIt.hasNext()){
163         //for each reaching def
164 Object JavaDoc defStmt = defIt.next();
165         
166         //get the dU Chain
167 Object JavaDoc useObj = dU.get(defStmt);
168         List uses=null;
169         if(useObj==null)
170         uses = new ArrayList();
171         else
172         uses = (List)useObj;
173         
174         //add the new local use to this list (we add the node since thats where the local is used
175 uses.add(useNodeOrStatement);
176         //System.out.println("Adding definition:"+defStmt+"with uses:"+uses);
177 dU.put(defStmt,uses);
178     }
179     }
180
181
182
183
184
185
186
187
188
189
190
191
192     /*
193      * Given a unary/binary or aggregated condition this method is used
194      * to find the locals used in the condition
195      */
196     public List getUseList(ASTCondition cond){
197     ArrayList useList = new ArrayList();
198     if(cond instanceof ASTAggregatedCondition){
199         useList.addAll(getUseList(((ASTAggregatedCondition)cond).getLeftOp()));
200         useList.addAll(getUseList(((ASTAggregatedCondition)cond).getRightOp()));
201         return useList;
202     }
203     else if(cond instanceof ASTUnaryCondition){
204         //get uses from unary condition
205 List uses = new ArrayList();
206
207         Value val = ((ASTUnaryCondition)cond).getValue();
208         if(val instanceof Local){
209         uses.add(val);
210         }
211         else{
212         List useBoxes = val.getUseBoxes();
213         uses= getUsesFromBoxes(useBoxes);
214         }
215         return uses;
216     }
217     else if(cond instanceof ASTBinaryCondition){
218         //get uses from binaryCondition
219 Value val = ((ASTBinaryCondition)cond).getConditionExpr();
220         List useBoxes = val.getUseBoxes();
221         return getUsesFromBoxes(useBoxes);
222     }
223     else{
224         throw new RuntimeException JavaDoc("Method getUseList in ASTUsesAndDefs encountered unknown condition type");
225     }
226     }
227
228
229
230
231
232
233
234
235
236
237
238
239     /*
240      * This method gets a list of all uses of locals in the condition
241      * Then it invokes the createUDDUChain for each local
242      */
243     public void checkConditionalUses(ASTCondition cond,ASTNode node){
244     List useList = getUseList(cond);
245
246     //System.out.println("FOR NODE with condition:"+cond+"USE list is:"+useList);
247
248     //FOR EACH USE
249 Iterator it = useList.iterator();
250     while(it.hasNext()){
251         Local local = (Local)it.next();
252         //System.out.println("creating uddu for "+local);
253 createUDDUChain(local,node);
254     }//end of going through all locals uses in condition
255 }
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281     /*
282       The key in a switch stmt can be a local or a value
283       which can contain Locals
284
285       Hence the some what indirect approach
286     */
287     public void inASTSwitchNode(ASTSwitchNode node){
288     Value val = (Value)node.get_Key();
289     List uses = new ArrayList();
290     if(val instanceof Local){
291         uses.add(val);
292     }
293     else{
294         List useBoxes = val.getUseBoxes();
295         uses= getUsesFromBoxes(useBoxes);
296     }
297
298     Iterator it = uses.iterator();
299     //System.out.println("SWITCH uses start:");
300 while(it.hasNext()){
301         Local local = (Local)it.next();
302         //System.out.println(local);
303 createUDDUChain(local,node);
304     }//end of going through all locals uses in switch key
305 //System.out.println("SWITCH uses end:");
306 }
307
308
309
310
311
312
313     public void inASTSynchronizedBlockNode(ASTSynchronizedBlockNode node){
314     Local local = node.getLocal();
315     createUDDUChain(local,node);
316     }
317
318
319
320
321
322
323
324     /*
325      * The condition of an if node can use a local
326      *
327      */
328     public void inASTIfNode(ASTIfNode node){
329     ASTCondition cond = node.get_Condition();
330     checkConditionalUses(cond,node);
331     }
332
333
334     /*
335      * The condition of an ifElse node can use a local
336      *
337      */
338     public void inASTIfElseNode(ASTIfElseNode node){
339     ASTCondition cond = node.get_Condition();
340     checkConditionalUses(cond,node);
341     }
342
343
344
345
346     /*
347      * The condition of a while node can use a local
348      *
349      */
350     public void inASTWhileNode(ASTWhileNode node){
351     ASTCondition cond = node.get_Condition();
352     checkConditionalUses(cond,node);
353     }
354
355
356
357     /*
358      * The condition of a doWhile node can use a local
359      *
360      */
361     public void inASTDoWhileNode(ASTDoWhileNode node){
362     ASTCondition cond = node.get_Condition();
363     checkConditionalUses(cond,node);
364     }
365
366
367
368
369     /*
370      * The init of a for loop can use a local
371      * The condition of a for node can use a local
372      * The update in a for loop can use a local
373      *
374      */
375     public void inASTForLoopNode(ASTForLoopNode node){
376
377     //checking uses in init
378 List init = node.getInit();
379     Iterator it = init.iterator();
380     while(it.hasNext()){
381         AugmentedStmt as = (AugmentedStmt)it.next();
382         Stmt s = as.get_Stmt();
383         checkStatementUses(s,node);
384     }
385
386     //checking uses in condition
387 ASTCondition cond = node.get_Condition();
388     checkConditionalUses(cond,node);
389
390     
391     //checking uses in update
392 List update = node.getUpdate();
393     it = update.iterator();
394     while(it.hasNext()){
395         AugmentedStmt as = (AugmentedStmt)it.next();
396         Stmt s = as.get_Stmt();
397         checkStatementUses(s,node);
398     }
399     }
400
401
402
403     public void inASTStatementSequenceNode(ASTStatementSequenceNode node){
404     List statements = node.getStatements();
405     Iterator it = statements.iterator();
406     
407     while(it.hasNext()){
408         AugmentedStmt as = (AugmentedStmt)it.next();
409         Stmt s = as.get_Stmt();
410         //in the case of stmtts in a stmtt sequence each stmt is considered an entity
411 //compared to the case where these stmts occur within other constructs
412 //where the node is the entity
413 checkStatementUses(s,s);
414     }
415     }
416
417
418     /*
419      * Input is a construct (ASTNode or statement) that has some locals used and output are all defs reached
420      * for all the uses in that construct...
421      *
422      * dont know whether it actually makes sense for the nodes but it definetly makes sense for the statements
423      */
424     public List getUDChain(Object JavaDoc node){
425     return (List)uD.get(node);
426     }
427
428
429     /*
430      * Give it a def stmt and it will return all places where it is used
431      */
432     public List getDUChain(Object JavaDoc node){
433     return (List)dU.get(node);
434     }
435
436     public HashMap getDUHashMap(){
437     return dU;
438     }
439
440
441     public void outASTMethodNode(ASTMethodNode node){
442     //print();
443 }
444
445     public void print(){
446     System.out.println("\n\n\nPRINTING uD dU CHAINS ______________________________");
447     Iterator it = dU.keySet().iterator();
448     while(it.hasNext()){
449         DefinitionStmt s = (DefinitionStmt)it.next();
450         System.out.println("*****The def "+s+" has following uses:");
451         Object JavaDoc obj = dU.get(s);
452         if(obj !=null){
453         ArrayList list = (ArrayList)obj;
454         Iterator tempIt = list.iterator();
455         while(tempIt.hasNext()){
456             Object JavaDoc tempUse = tempIt.next();
457             System.out.println("-----------Use "+tempUse);
458             System.out.println("----------------Defs of this use: "+uD.get(tempUse));
459         }
460         }
461     }
462     System.out.println("END --------PRINTING uD dU CHAINS ______________________________");
463     }
464
465 }
Popular Tags