KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > soot > dava > toolkits > base > AST > structuredAnalysis > ReachingDefs


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 /**
22  * Maintained by: Nomair A. Naeem
23  */
24
25
26 package soot.dava.toolkits.base.AST.structuredAnalysis;
27
28 import soot.*;
29 import java.util.*;
30 import soot.jimple.*;
31 //import soot.dava.internal.javaRep.*;
32 import soot.dava.internal.AST.*;
33 //import soot.dava.internal.SET.*;
34 import soot.dava.toolkits.base.AST.traversals.*;
35
36 /**
37  * CHANGE LOG: * November 21st Added support for implicit breaks and continues
38  * Tested code for reaching defs within switch/try/if/while/for
39  *
40  * * November 22nd Refactored code to make structure flow analysis framework
41  * handle breaks and returns.
42  *
43  * * November 24th newInitialFlow ERROR............initialFlow should be the set of
44  * all defs........since there needs to exist SOME path
45  */
46
47 /*
48   Reaching Defs
49   Step 1:
50           Set of definitions (a definition is a Stmt within a StatementSequenceNode)
51   Step 2:
52           A definition d: x = ... reaches a point p in the program if there exists a path from
53       p such that there is no other definition of x between d and p.
54   Step 3:
55           Forward Analysis
56   Step 4:
57          Union
58   Step 5:
59          d: x = expr
60      kill = { all existing defs of x}
61      
62      gen = (d)
63
64   Step 6:
65          newInitialFlow: No definitions reach (safe) (Catch bodies)
66      //November 24th.........changing above to be the universal set of all definitions
67
68
69      out(start) = {} since there has been no definition so far
70
71      out(Si) not needed for structured flow analysis
72 */
73
74 public class ReachingDefs extends StructuredAnalysis{
75     Object JavaDoc toAnalyze;
76
77     public ReachingDefs(Object JavaDoc analyze){
78     super();
79     toAnalyze = analyze;
80     DavaFlowSet temp = (DavaFlowSet)process(analyze,new DavaFlowSet());
81     }
82
83
84     /*
85      * Initial flow into catch statements is empty meaning no definition reaches
86      *
87      */
88     public Object JavaDoc newInitialFlow(){
89     DavaFlowSet initial = new DavaFlowSet();
90     //find all definitions in the program
91 AllDefinitionsFinder defFinder = new AllDefinitionsFinder();
92     ((ASTNode)toAnalyze).apply(defFinder);
93     List allDefs = defFinder.getAllDefs();
94     //all defs is the list of all augmented stmts which contains DefinitionStmts
95 Iterator defIt = allDefs.iterator();
96     while(defIt.hasNext())
97         initial.add(defIt.next());
98
99     //initial is not the universal set of all definitions
100 return initial;
101     }
102     
103
104
105     /*
106      * Using union
107      *
108      */
109     public void setMergeType(){
110     MERGETYPE=UNION;
111     }
112     
113
114
115     public Object JavaDoc cloneFlowSet(Object JavaDoc flowSet){
116     if(flowSet instanceof DavaFlowSet){
117         return ((DavaFlowSet)flowSet).clone();
118     }
119     else
120         throw new RuntimeException JavaDoc("cloneFlowSet not implemented for other flowSet types");
121     }
122
123
124
125
126
127
128
129     /*
130      *In the case of reachingDefs the evaluation of a condition has no effect on the reachingDefs
131      *
132      */
133     public Object JavaDoc processUnaryBinaryCondition(ASTUnaryBinaryCondition cond, Object JavaDoc input){
134     if(!(input instanceof DavaFlowSet)){
135         throw new RuntimeException JavaDoc("processCondition is not implemented for other flowSet types");
136     }
137     DavaFlowSet inSet = (DavaFlowSet)input;
138     return inSet;
139     }
140
141
142     /*
143      *In the case of reachingDefs the use of a local has no effect on reachingDefs
144      *
145      */
146     public Object JavaDoc processSynchronizedLocal(Local local,Object JavaDoc input){
147     if(!(input instanceof DavaFlowSet)){
148         throw new RuntimeException JavaDoc("processCondition is not implemented for other flowSet types");
149     }
150     DavaFlowSet inSet = (DavaFlowSet)input;
151     return inSet;
152     }
153
154
155     /*
156      *In the case of reachingDefs a value has no effect on reachingDefs
157      *
158      */
159     public Object JavaDoc processSwitchKey(Value key,Object JavaDoc input){
160     if(!(input instanceof DavaFlowSet)){
161         throw new RuntimeException JavaDoc("processCondition is not implemented for other flowSet types");
162     }
163     DavaFlowSet inSet = (DavaFlowSet)input;
164     return inSet;
165     }
166
167
168
169
170     /*
171      * This method internally invoked by the process method decides which Statement
172      * specialized method to call
173      */
174     public Object JavaDoc processStatement(Stmt s, Object JavaDoc input){
175     if(!(input instanceof DavaFlowSet)){
176         throw new RuntimeException JavaDoc("processStatement is not implemented for other flowSet types");
177     }
178     DavaFlowSet inSet = (DavaFlowSet)input;
179
180     /*
181       If this path will not be taken return no path straightaway
182     */
183     if(inSet == NOPATH){
184         return inSet;
185     }
186
187     if(s instanceof DefinitionStmt){
188         DavaFlowSet toReturn = (DavaFlowSet)cloneFlowSet(inSet);
189         //d:x = expr
190 //gen is x
191 //kill is all previous defs of x
192
193         Value leftOp = ((DefinitionStmt)s).getLeftOp();
194
195         if(leftOp instanceof Local){
196         // KILL any reaching defs of leftOp
197 kill(toReturn,(Local)leftOp);
198         // GEN
199 gen(toReturn,(DefinitionStmt)s);
200         return toReturn;
201         }//leftop is a local
202 }
203     return input;
204     }
205
206
207
208     public void gen(DavaFlowSet in, DefinitionStmt s){
209     //System.out.println("Adding Definition Stmt: "+s);
210 in.add(s);
211     }
212     
213     public void kill(DavaFlowSet in, Local redefined){
214     String JavaDoc redefinedLocalName = redefined.getName();
215
216     // kill any previous localpairs which have the redefined Local in the left i.e. previous definitions
217 List list = in.toList();
218     Iterator listIt = list.iterator();
219     while(listIt.hasNext()){
220         DefinitionStmt tempStmt = (DefinitionStmt)listIt.next();
221         Value leftOp = tempStmt.getLeftOp();
222         if(leftOp instanceof Local){
223         String JavaDoc storedLocalName = ((Local)leftOp).getName();
224         if(redefinedLocalName.compareTo(storedLocalName)==0){
225             //need to kill this from the list
226 //System.out.println("Killing "+tempStmt);
227 in.remove(tempStmt);
228         }
229         }
230     }
231     }
232
233
234     public List getReachingDefs(Local local,Object JavaDoc node){
235     ArrayList toReturn = new ArrayList();
236
237     //get the reaching defs of this node
238 Object JavaDoc beforeSet=null;
239     /*
240       If this object is some sort of loop while, for dowhile, unconditional then return after set
241     */
242     if(node instanceof ASTWhileNode || node instanceof ASTDoWhileNode || node instanceof ASTUnconditionalLoopNode
243        || node instanceof ASTForLoopNode)
244         beforeSet = getAfterSet(node);
245     else
246         beforeSet=getBeforeSet(node);
247
248
249     if(beforeSet == null){
250         throw new RuntimeException JavaDoc("Could not get reaching defs of node");
251     }
252     if(!(beforeSet instanceof DavaFlowSet)){
253         throw new RuntimeException JavaDoc("Reaching def set is not a Dava FlowSet");
254     }
255     DavaFlowSet beforeSetReaching = (DavaFlowSet)beforeSet;
256
257
258     //find all reachingdefs matching this local
259 List allReachingDefs = beforeSetReaching.toList();
260
261
262     Iterator it = allReachingDefs.iterator();
263     while(it.hasNext()){
264         //checking each def to see if it is a def of local
265 Object JavaDoc temp = it.next();
266         if(!(temp instanceof DefinitionStmt))
267         throw new RuntimeException JavaDoc("Not an instanceof DefinitionStmt"+temp);
268         DefinitionStmt stmt = (DefinitionStmt)temp;
269         Value leftOp = stmt.getLeftOp();
270         if(leftOp.toString().compareTo(local.toString())==0){
271         toReturn.add(stmt);
272         }
273     }
274     return toReturn;
275     }
276
277
278
279
280
281
282
283
284
285
286
287     public void reachingDefsToString(Object JavaDoc node){
288     ArrayList toReturn = new ArrayList();
289
290     //get the reaching defs of this node
291 Object JavaDoc beforeSet=null;
292     /*
293       If this object is some sort of loop while, for dowhile, unconditional then return after set
294     */
295     if(node instanceof ASTWhileNode || node instanceof ASTDoWhileNode || node instanceof ASTUnconditionalLoopNode
296        || node instanceof ASTForLoopNode)
297         beforeSet = getAfterSet(node);
298     else
299         beforeSet=getBeforeSet(node);
300
301
302
303     if(beforeSet == null){
304         throw new RuntimeException JavaDoc("Could not get reaching defs of node");
305     }
306     if(!(beforeSet instanceof DavaFlowSet)){
307         throw new RuntimeException JavaDoc("Reaching def set is not a Dava FlowSet");
308     }
309     DavaFlowSet beforeSetReaching = (DavaFlowSet)beforeSet;
310     
311     //find all reachingdefs matching this local
312 List allReachingDefs = beforeSetReaching.toList();
313     Iterator it = allReachingDefs.iterator();
314     while(it.hasNext()){
315         System.out.println("Reaching def:"+it.next());
316     }
317     }
318 }
Popular Tags