KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > soot > jimple > toolkits > annotation > parity > ParityAnalysis


1 /* Soot - a J*va Optimization Framework
2  * Copyright (C) 2003 Jennifer Lhotak
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 package soot.jimple.toolkits.annotation.parity;
21
22 import soot.*;
23 import soot.util.*;
24 import java.util.*;
25 import soot.jimple.*;
26 import soot.toolkits.graph.*;
27 import soot.toolkits.scalar.*;
28 import soot.options.*;
29
30 // STEP 1: What are we computing?
31 // SETS OF PAIRS of form (X, T) => Use ArraySparseSet.
32 //
33 // STEP 2: Precisely define what we are computing.
34 // For each statement compute the parity of all variables
35 // in the program.
36 //
37 // STEP 3: Decide whether it is a backwards or forwards analysis.
38 // FORWARDS
39 //
40 //
41 public class ParityAnalysis extends ForwardFlowAnalysis {
42
43     private UnitGraph g;
44     private final static String JavaDoc TOP = "top";
45     private final static String JavaDoc BOTTOM = "bottom";
46     private final static String JavaDoc EVEN = "even";
47     private final static String JavaDoc ODD = "odd";
48
49     private LiveLocals filter;
50     
51     public ParityAnalysis(UnitGraph g, LiveLocals filter)
52     {
53         super(g);
54         this.g = g;
55
56         this.filter = filter;
57         
58         filterUnitToBeforeFlow = new HashMap();
59         buildBeforeFilterMap();
60         
61         filterUnitToAfterFlow = new HashMap();
62         
63         doAnalysis();
64         
65     }
66
67     public ParityAnalysis(UnitGraph g){
68         super(g);
69         this.g = g;
70
71         doAnalysis();
72     }
73     
74     private void buildBeforeFilterMap(){
75         
76         Iterator it = g.getBody().getUnits().iterator();
77         while (it.hasNext()){
78             Stmt s = (Stmt)it.next();
79             //if (!(s instanceof DefinitionStmt)) continue;
80 //Value left = ((DefinitionStmt)s).getLeftOp();
81 //if (!(left instanceof Local)) continue;
82
83             //if (!((left.getType() instanceof IntegerType) || (left.getType() instanceof LongType))) continue;
84 List list = filter.getLiveLocalsBefore(s);
85             HashMap map = new HashMap();
86             Iterator listIt = list.iterator();
87             while (listIt.hasNext()){
88                 map.put(listIt.next(), BOTTOM);
89             }
90             filterUnitToBeforeFlow.put(s, map);
91         }
92         //System.out.println("init filtBeforeMap: "+filterUnitToBeforeFlow);
93 }
94
95 // STEP 4: Is the merge operator union or intersection?
96 //
97 // merge | bottom | even | odd | top
98 // -------+--------+--------+-------+--------
99 // bottom | bottom | even | odd | top
100 // -------+--------+--------+-------+--------
101 // even | even | even | top | top
102 // -------+--------+--------+-------+--------
103 // odd | odd | top | odd | top
104 // -------+--------+--------+-------+--------
105 // top | top | top | top | top
106 //
107
108     protected void merge(Object JavaDoc in1, Object JavaDoc in2, Object JavaDoc out)
109     {
110     HashMap inMap1 = (HashMap) in1;
111     HashMap inMap2 = (HashMap) in2;
112     HashMap outMap = (HashMap) out;
113
114     Set keys = inMap1.keySet();
115     Iterator it = keys.iterator();
116     while (it.hasNext()) {
117         Object JavaDoc var1 = it.next();
118         //System.out.println(var1);
119 String JavaDoc inVal1 = (String JavaDoc)inMap1.get(var1);
120         //System.out.println(inVal1);
121 String JavaDoc inVal2 = (String JavaDoc)inMap2.get(var1);
122         //System.out.println(inVal2);
123 // System.out.println("before out "+outMap.get(var1));
124
125         if (inVal2 == null){
126             outMap.put(var1, inVal1);
127         }
128         else if (inVal1.equals(BOTTOM)) {
129             outMap.put(var1, inVal2);
130         }
131         else if (inVal2.equals(BOTTOM)) {
132                 outMap.put(var1, inVal1);
133         }
134         else if ((inVal1.equals(EVEN)) &&
135             (inVal2.equals(EVEN))) {
136             outMap.put(var1, EVEN);
137         }
138         else if ((inVal1.equals(ODD)) &&
139             (inVal2.equals(ODD))) {
140             outMap.put(var1, ODD);
141         }
142         else {
143             outMap.put(var1, TOP);
144         }
145     }
146     
147     }
148
149 // STEP 5: Define flow equations.
150 // in(s) = ( out(s) minus defs(s) ) union uses(s)
151 //
152
153     protected void copy(Object JavaDoc source, Object JavaDoc dest) {
154
155         //System.out.println("copy");
156 HashMap sourceIn = (HashMap)source;
157         HashMap destOut = (HashMap)dest;
158         //dest = new HashMap();
159 //HashMap destOut = new HashMap();
160 destOut.putAll(sourceIn);
161         dest = destOut;
162
163     }
164    
165     // Parity Tests: even + even = even
166 // even + odd = odd
167 // odd + odd = even
168 //
169 // even * even = even
170 // even * odd = even
171 // odd * odd = odd
172 //
173 // constants are tested mod 2
174 //
175
176     private String JavaDoc getParity(HashMap in, Value val) {
177         //System.out.println("get Parity in: "+in);
178 if ((val instanceof AddExpr) | (val instanceof SubExpr)) {
179             String JavaDoc resVal1 = getParity(in, ((BinopExpr)val).getOp1());
180             String JavaDoc resVal2 = getParity(in, ((BinopExpr)val).getOp2());
181             if (resVal1.equals(TOP) | resVal2.equals(TOP)) {
182                 return TOP;
183             }
184             else if (resVal1.equals(BOTTOM) | resVal2.equals(BOTTOM)){
185                 return BOTTOM;
186             }
187             else if (resVal1.equals(resVal2)) {
188                 return EVEN;
189             }
190             else {
191                 return ODD;
192             }
193         }
194         else if (val instanceof MulExpr) {
195             String JavaDoc resVal1 = getParity(in, ((BinopExpr)val).getOp1());
196             String JavaDoc resVal2 = getParity(in, ((BinopExpr)val).getOp2());
197             if (resVal1.equals(TOP) | resVal2.equals(TOP)) {
198                 return TOP;
199             }
200             else if (resVal1.equals(BOTTOM) | resVal2.equals(BOTTOM)){
201                 return BOTTOM;
202             }
203             else if (resVal1.equals(ODD) && resVal2.equals(ODD)) {
204                 return ODD;
205             }
206             else {
207                 return EVEN;
208             }
209         }
210         else if (val instanceof IntConstant) {
211             int value = ((IntConstant)val).value;
212             if ((value % 2) == 0) {
213                 return EVEN;
214             }
215             else {
216                 return ODD;
217             }
218         }
219         else if (val instanceof LongConstant) {
220             long value = ((LongConstant)val).value;
221             if ((value % 2) == 0) {
222                 return EVEN;
223             }
224             else {
225                 return ODD;
226             }
227         }
228         else if (in.containsKey(val)) {
229             return (String JavaDoc)in.get(val);
230         }
231         else {
232             return TOP;
233         }
234      
235     }
236     
237     
238     protected void flowThrough(Object JavaDoc inValue, Object JavaDoc unit,
239             Object JavaDoc outValue)
240     {
241         HashMap in = (HashMap) inValue;
242         HashMap out = (HashMap) outValue;
243         Stmt s = (Stmt) unit;
244
245         // copy in to out
246 out.putAll(in);
247     
248         // for each stmt where leftOp is defintionStmt find the parity
249 // of rightOp and update parity to EVEN, ODD or TOP
250
251         //boolean useS = false;
252
253         if (s instanceof DefinitionStmt) {
254             Value left = ((DefinitionStmt)s).getLeftOp();
255             if (left instanceof Local) {
256                 if ((left.getType() instanceof IntegerType) || (left.getType() instanceof LongType)){
257                     //useS = true;
258 Value right = ((DefinitionStmt)s).getRightOp();
259                     out.put(left, getParity(out, right));
260                 }
261             }
262         }
263
264         // get all use and def boxes of s
265 // if use or def is int or long constant add their parity
266 Iterator it = s.getUseAndDefBoxes().iterator();
267         while (it.hasNext()){
268             Object JavaDoc next = it.next();
269             Value val = ((ValueBox)next).getValue();
270             //System.out.println("val: "+val.getClass());
271 if (val instanceof ArithmeticConstant){
272                 out.put(val, getParity(out, (ArithmeticConstant)val));
273                 //System.out.println("out map: "+out);
274 }
275         }
276         
277         //if (useS){
278 if (Options.v().interactive_mode()){
279             buildAfterFilterMap(s);
280             updateAfterFilterMap(s);
281         }
282         //}
283 }
284     
285     private void buildAfterFilterMap(Stmt s){
286         
287         List list = filter.getLiveLocalsAfter(s);
288         HashMap map = new HashMap();
289         Iterator listIt = list.iterator();
290         while (listIt.hasNext()){
291             map.put(listIt.next(), BOTTOM);
292         }
293         filterUnitToAfterFlow.put(s, map);
294         //System.out.println("built afterflow filter map: "+filterUnitToAfterFlow);
295 }
296
297
298 // STEP 6: Determine value for start/end node, and
299 // initial approximation.
300 //
301 // start node: locals with BOTTOM
302 // initial approximation: locals with BOTTOM
303 protected Object JavaDoc entryInitialFlow()
304     {
305     /*HashMap initMap = new HashMap();
306     
307     Chain locals = g.getBody().getLocals();
308     Iterator it = locals.iterator();
309     while (it.hasNext()) {
310       initMap.put(it.next(), BOTTOM);
311     }
312         return initMap;*/
313
314         return newInitialFlow();
315     }
316
317     private void updateBeforeFilterMap(){
318     
319         Iterator filterIt = filterUnitToBeforeFlow.keySet().iterator();
320         while (filterIt.hasNext()){
321             Stmt s = (Stmt)filterIt.next();
322             HashMap allData = (HashMap)unitToBeforeFlow.get(s);
323             
324             HashMap filterData = (HashMap)filterUnitToBeforeFlow.get(s);
325
326             filterUnitToBeforeFlow.put(s, updateFilter(allData, filterData));
327             
328         }
329     }
330         
331     private void updateAfterFilterMap(Stmt s){
332     
333         HashMap allData = (HashMap)unitToAfterFlow.get(s);
334             
335         HashMap filterData = (HashMap)filterUnitToAfterFlow.get(s);
336
337         filterUnitToAfterFlow.put(s, updateFilter(allData, filterData));
338             
339     }
340         
341     private HashMap updateFilter(HashMap allData, HashMap filterData){
342
343         if (allData == null) return filterData;
344         Iterator filterVarsIt = filterData.keySet().iterator();
345         ArrayList toRemove = new ArrayList();
346         while (filterVarsIt.hasNext()){
347             Value v = (Value)filterVarsIt.next();
348             if (allData.get(v) == null){
349                 toRemove.add(v);
350                 //filterData.put(v, new HashMap());
351 }
352             else {
353                 filterData.put(v, allData.get(v));
354             }
355         }
356         Iterator removeIt = toRemove.iterator();
357         while (removeIt.hasNext()){
358             filterData.remove(removeIt.next());
359         }
360
361         return filterData;
362     }
363
364     protected Object JavaDoc newInitialFlow()
365     {
366         HashMap initMap = new HashMap();
367     
368         Chain locals = g.getBody().getLocals();
369         Iterator it = locals.iterator();
370         while (it.hasNext()) {
371             Local next = (Local)it.next();
372             //System.out.println("next local: "+next);
373 if ((next.getType() instanceof IntegerType) || (next.getType() instanceof LongType)){
374                 initMap.put(next, BOTTOM);
375             }
376         }
377     
378         Iterator boxIt = g.getBody().getUseAndDefBoxes().iterator();
379         while (boxIt.hasNext()){
380             Value val = ((ValueBox)boxIt.next()).getValue();
381             if (val instanceof ArithmeticConstant) {
382                 initMap.put(val, getParity(initMap, val));
383             }
384         }
385
386         if (Options.v().interactive_mode()){
387             updateBeforeFilterMap();
388         }
389         
390         return initMap;
391
392     }
393         
394
395 }
396
Popular Tags