KickJava   Java API By Example, From Geeks To Geeks.

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


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: Removed check of DAbruptStmt from analysis since
26  * this is now handled by the structredAnalysis framework
27  *
28  * * November 22nd: Inlined the LocalPair class
29  * Tested Extensively: found bug in implementation of process_doWhile in structuredAnalysis :)
30  */
31
32 package soot.dava.toolkits.base.AST.structuredAnalysis;
33
34 import soot.*;
35 import java.util.*;
36 import soot.jimple.*;
37 import soot.dava.internal.javaRep.*;
38 import soot.dava.internal.AST.*;
39
40 /*
41   ReachingCopies
42   Step 1:
43           Set of pairs where each pair has the form (a,b) indicating a statement a=b
44   Step 2:
45           A copy statement (a=b) reaches a statement s if all paths leading to s have a copy
46       statemet a=b and the values of a and b are not changed between the copy statement and the statement s.
47   Step 3:
48           Forward Analysis
49   Step 4:
50          Intersection
51   Step 5:
52          x = expr
53      kill = { all pairs containing x in left or right position}
54      
55      if expr is a local , y
56      gen = (x,y)
57   Step 6:
58          out(start) = {}
59          newInitialFlow: No copies are available. an empty flow set
60      remember new InitialFlow is ONLY used for input to catchBodies
61
62      In ordinary flow analyses one has to assume that out(Si) is the universal set
63      for reaching copies. However the way structured flow analysis works
64      there is no need for such an assumption since it is never used in the structured flow analysis code
65 */
66
67 public class ReachingCopies extends StructuredAnalysis{
68
69
70     /***************** DEFINIING LOCAL PAIR CLASS ************************/
71     public class LocalPair{
72     private Local leftLocal;
73     private Local rightLocal;
74     
75     public LocalPair(Local left, Local right){
76         leftLocal=left;
77         rightLocal=right;
78     }
79     
80     
81     public Local getLeftLocal(){
82         return leftLocal;
83     }
84     
85     public Local getRightLocal(){
86         return rightLocal;
87     }
88     
89     public boolean equals(Object JavaDoc other){
90         if(other instanceof LocalPair){
91         if(this.leftLocal.toString().equals(((LocalPair)other).getLeftLocal().toString())){
92             if(this.rightLocal.toString().equals(((LocalPair)other).getRightLocal().toString())){
93             return true;
94             }
95         }
96         }
97         return false;
98     }
99     
100     /**
101      * Method checks whether local occurs in the left or right side of the localpair
102      * different semantics than the usual contains method which checks something in a list
103      */
104     public boolean contains(Local local){
105         if(leftLocal.toString().equals(local.toString()) || rightLocal.toString().equals(local.toString())){
106         return true;
107         }
108         return false;
109     }
110     
111     public String JavaDoc toString(){
112         StringBuffer JavaDoc b = new StringBuffer JavaDoc();
113         b.append("<"+leftLocal.toString()+","+rightLocal.toString()+">");
114         return b.toString();
115     }
116     
117     }
118
119     /******************************END OF LOCAL PAIR CLASS ***********************/
120
121
122
123
124
125
126     public ReachingCopies(Object JavaDoc analyze){
127     super();
128     //the input to the process method is an empty DavaFlow Set meaning out(start) ={}
129 DavaFlowSet temp = (DavaFlowSet)process(analyze,new DavaFlowSet());
130     }
131
132
133     public void setMergeType(){
134     MERGETYPE=INTERSECTION;
135     }
136
137     public Object JavaDoc newInitialFlow(){
138     return new DavaFlowSet();
139     }
140     
141     public Object JavaDoc cloneFlowSet(Object JavaDoc flowSet){
142     if(flowSet instanceof DavaFlowSet){
143         return ((DavaFlowSet)flowSet).clone();
144     }
145     else
146         throw new RuntimeException JavaDoc("cloneFlowSet not implemented for other flowSet types");
147     }
148
149
150
151
152     /*
153      * By construction conditions never have assignment statements.
154      * Hence processing a condition has no effect on this analysis
155      */
156     public Object JavaDoc processUnaryBinaryCondition(ASTUnaryBinaryCondition cond, Object JavaDoc input){
157     if(!(input instanceof DavaFlowSet)){
158         throw new RuntimeException JavaDoc("processCondition is not implemented for other flowSet types");
159     }
160     return input;
161     }
162
163
164     /*
165      * By construction the synchronized Local is a Value and can definetly not have an assignment stmt
166      * Processing a synch local has no effect on this analysis
167      */
168     public Object JavaDoc processSynchronizedLocal(Local local,Object JavaDoc input){
169     if(!(input instanceof DavaFlowSet)){
170         throw new RuntimeException JavaDoc("processCondition is not implemented for other flowSet types");
171     }
172     return input;
173     }
174
175
176
177     /*
178      * The switch key is stored as a value and hence can never have an assignment stmt
179      * Processing the switch key has no effect on the analysis
180      */
181     public Object JavaDoc processSwitchKey(Value key,Object JavaDoc input){
182     if(!(input instanceof DavaFlowSet)){
183         throw new RuntimeException JavaDoc("processCondition is not implemented for other flowSet types");
184     }
185     return input;
186     }
187
188
189
190
191
192
193
194
195
196
197     /*
198      * This method internally invoked by the process method decides which Statement
199      * specialized method to call
200      */
201     public Object JavaDoc processStatement(Stmt s, Object JavaDoc input){
202     if(!(input instanceof DavaFlowSet)){
203         throw new RuntimeException JavaDoc("processStatement is not implemented for other flowSet types");
204     }
205     DavaFlowSet inSet = (DavaFlowSet)input;
206
207     /*
208       If this path will not be taken return no path straightaway
209     */
210     if(inSet == NOPATH){
211         return inSet;
212     }
213
214     if(s instanceof DefinitionStmt){
215         DavaFlowSet toReturn = (DavaFlowSet)cloneFlowSet(inSet);
216         // x = expr;
217 //check if expr is a local in which case this is a copy
218 Value leftOp = ((DefinitionStmt)s).getLeftOp();
219         Value rightOp = ((DefinitionStmt)s).getRightOp();
220
221
222         if(leftOp instanceof Local){
223         // KILL any available copy with local since it has been redefined
224 kill(toReturn,(Local)leftOp);
225         }//leftop is a local
226
227
228         if(leftOp instanceof Local && rightOp instanceof Local){
229         //this is a copy statement
230 // GEN
231 gen(toReturn,(Local)leftOp,(Local)rightOp);
232         }
233         return toReturn;
234     }
235     else{
236         /*
237           Analysis cares only about break and continue stmts along with DEFINTION STMT
238         */
239         return input;
240     }
241     }
242
243
244     public void gen(DavaFlowSet in, Local left, Local right){
245     //adding localpair
246 //no need to check for duplicates as the DavaFlowSet checks that
247 LocalPair localp = new LocalPair(left,right);
248     in.add(localp);
249     }
250     
251     public void kill(DavaFlowSet in, Local redefined){
252     // kill any previous localpairs which have the redefined Local in the left OR right position
253 List list = in.toList();
254     Iterator listIt = list.iterator();
255     while(listIt.hasNext()){
256         LocalPair tempPair = (LocalPair)listIt.next();
257         if(tempPair.contains(redefined)){
258         //need to kill this from the list
259 in.remove(tempPair);
260         }
261     }
262     }
263
264
265
266     /*
267      * Wrapper method to get before set of an ASTNode or Statement
268      * which gives us the reaching copies at this point
269      */
270     public DavaFlowSet getReachingCopies(Object JavaDoc node){
271     //get the before set for this node
272 Object JavaDoc beforeSet=getBeforeSet(node);
273
274     if(beforeSet == null){
275         throw new RuntimeException JavaDoc("Could not get reaching copies of node/stmt");
276     }
277     if(!(beforeSet instanceof DavaFlowSet)){
278         throw new RuntimeException JavaDoc("Reaching def set is not a Dava FlowSet");
279     }
280
281     DavaFlowSet beforeSetReaching = (DavaFlowSet)beforeSet;
282     //Get all reachingCopies
283
284     /* the list that toList of this object contains elements of
285      * type LocalPair (a,b) which means this is a copy
286      * stmt of the form a=b
287      */
288
289     return beforeSetReaching;
290     }
291
292 }
Popular Tags