KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > soot > toolkits > scalar > CombinedDUAnalysis


1 /* Soot - a J*va Optimization Framework
2  * Copyright (C) 2004 Ondrej 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.toolkits.scalar;
21 import soot.options.*;
22
23 import soot.jimple.*;
24 import soot.toolkits.graph.*;
25 import soot.*;
26 import soot.util.*;
27 import java.util.*;
28
29
30 /**
31  * Analysis that computes live locals, local defs, and local uses all at once.
32  */

33 public class CombinedDUAnalysis extends BackwardFlowAnalysis implements CombinedAnalysis, LocalDefs, LocalUses, LiveLocals
34 {
35     // Implementations of our interfaces...
36
private Map defsOfAt = new HashMap();
37     public List getDefsOfAt(Local l, Unit s) {
38         Cons cons = new Cons(l, s);
39         List ret = (List) defsOfAt.get(cons);
40         if(ret == null) {
41             defsOfAt.put(cons, ret = new ArrayList());
42         }
43         return ret;
44     }
45     private Map usesOf = new HashMap();
46     public List getUsesOf(Unit u) {
47         List ret = (List) usesOf.get(u);
48         if( ret == null ) {
49             Local def = localDefed(u);
50             if( def == null ) {
51                 usesOf.put(u, ret = Collections.EMPTY_LIST);
52             } else {
53                 usesOf.put(u, ret = new ArrayList());
54                 for( Iterator vbIt = ((FlowSet)getFlowAfter(u)).iterator(); vbIt.hasNext(); ) {
55                     final ValueBox vb = (ValueBox) vbIt.next();
56                     if( vb.getValue() != def ) continue;
57                     ret.add(new UnitValueBoxPair((Unit)useBoxToUnit.get(vb), vb));
58                 }
59             }
60         }
61         return ret;
62     }
63     private Map liveLocalsBefore = new HashMap();
64     public List getLiveLocalsBefore(Unit u) {
65         List ret = (List) liveLocalsBefore.get(u);
66         if( ret == null ) {
67             HashSet hs = new HashSet();
68             for( Iterator vbIt = ((FlowSet)getFlowBefore(u)).iterator(); vbIt.hasNext(); ) {
69                 final ValueBox vb = (ValueBox) vbIt.next();
70                 hs.add(vb.getValue());
71             }
72             liveLocalsBefore.put(u, ret = new ArrayList(hs));
73         }
74         return ret;
75     }
76     private Map liveLocalsAfter = new HashMap();
77     public List getLiveLocalsAfter(Unit u) {
78         List ret = (List) liveLocalsAfter.get(u);
79         if( ret == null ) {
80             HashSet hs = new HashSet();
81             for( Iterator vbIt = ((FlowSet)getFlowAfter(u)).iterator(); vbIt.hasNext(); ) {
82                 final ValueBox vb = (ValueBox) vbIt.next();
83                 hs.add(vb.getValue());
84             }
85             liveLocalsAfter.put(u, ret = new ArrayList(hs));
86         }
87         return ret;
88     }
89
90     // The actual analysis is below.
91

92     private final Map useBoxToUnit = new HashMap();
93     private final Map unitToLocalDefed = new HashMap();
94     private Local localDefed(Unit u) { return (Local) unitToLocalDefed.get(u); }
95     private final Map unitToLocalUseBoxes = new HashMap();
96     private final MultiMap localToUseBoxes = new HashMultiMap();
97     private final UnitGraph graph;
98
99     public static CombinedAnalysis v(final UnitGraph graph) {
100         if(true) {
101             return new CombinedDUAnalysis(graph);
102         }
103
104         return new CombinedAnalysis() {
105             CombinedDUAnalysis combined = new CombinedDUAnalysis(graph);
106             SimpleLocalDefs defs = new SimpleLocalDefs(graph);
107             SimpleLocalUses uses = new SimpleLocalUses(graph, defs);
108             SimpleLiveLocals live = new SimpleLiveLocals(graph);
109             public List getDefsOfAt(Local l, Unit s) {
110                 HashSet hs1 = new HashSet(combined.getDefsOfAt(l, s));
111                 HashSet hs2 = new HashSet(defs.getDefsOfAt(l, s));
112                 if( !hs1.equals(hs2) ) throw new RuntimeException JavaDoc(
113                         "Defs of "+l+" in "+s+"\ncombined: "+hs1+"\nsimple: "+hs2);
114                 return combined.getDefsOfAt(l, s);
115             }
116             public List getUsesOf(Unit u) {
117                 HashSet hs1 = new HashSet(combined.getUsesOf(u));
118                 HashSet hs2 = new HashSet(uses.getUsesOf(u));
119                 if( !hs1.equals(hs2) ) throw new RuntimeException JavaDoc(
120                         "Uses of "+u+"\ncombined: "+hs1+"\nsimple: "+hs2);
121                 return combined.getUsesOf(u);
122             }
123             public List getLiveLocalsBefore(Unit u) {
124                 HashSet hs1 = new HashSet(combined.getLiveLocalsBefore(u));
125                 HashSet hs2 = new HashSet(live.getLiveLocalsBefore(u));
126                 if( !hs1.equals(hs2) ) throw new RuntimeException JavaDoc(
127                         "llb of "+u+"\ncombined: "+hs1+"\nsimple: "+hs2);
128                 return combined.getLiveLocalsBefore(u);
129             }
130             public List getLiveLocalsAfter(Unit u) {
131                 HashSet hs1 = new HashSet(combined.getLiveLocalsAfter(u));
132                 HashSet hs2 = new HashSet(live.getLiveLocalsAfter(u));
133                 if( !hs1.equals(hs2) ) throw new RuntimeException JavaDoc(
134                         "lla of "+u+"\ncombined: "+hs1+"\nsimple: "+hs2);
135                 return combined.getLiveLocalsAfter(u);
136             }
137         }
138         ;
139     }
140     private CombinedDUAnalysis(UnitGraph graph) {
141         super(graph);
142         this.graph = graph;
143
144         if(Options.v().verbose())
145             G.v().out.println("[" + graph.getBody().getMethod().getName() +
146                                "] Constructing CombinedDUAnalysis...");
147  
148         for( Iterator uIt = graph.iterator(); uIt.hasNext(); ) {
149  
150             final Unit u = (Unit) uIt.next();
151             List defs = localsInBoxes(u.getDefBoxes());
152             if( defs.size() == 1 ) unitToLocalDefed.put(u, defs.get(0));
153             else if(defs.size() != 0) throw new RuntimeException JavaDoc("Locals defed in "+u+": "+defs.size());
154             ArraySparseSet localUseBoxes = new ArraySparseSet();
155             for( Iterator vbIt = u.getUseBoxes().iterator(); vbIt.hasNext(); ) {
156                 final ValueBox vb = (ValueBox) vbIt.next();
157                 Value v = vb.getValue();
158                 if(!(v instanceof Local)) continue;
159                 localUseBoxes.add(vb);
160                 if( useBoxToUnit.containsKey(vb) ) throw new RuntimeException JavaDoc("Aliased ValueBox "+vb+" in Unit "+u);
161                 useBoxToUnit.put(vb, u);
162                 localToUseBoxes.put(v, vb);
163             }
164             unitToLocalUseBoxes.put(u, localUseBoxes);
165         }
166
167         doAnalysis();
168
169         for( Iterator defUnitIt = graph.iterator(); defUnitIt.hasNext(); ) {
170
171             final Unit defUnit = (Unit) defUnitIt.next();
172             /*
173             getLiveLocalsAfter(defUnit);
174             getLiveLocalsBefore(defUnit);
175             getUsesOf(defUnit);
176             */

177             Local localDefed = localDefed(defUnit);
178             if( localDefed == null ) continue;
179             for( Iterator vbIt = ((FlowSet)getFlowAfter(defUnit)).iterator(); vbIt.hasNext(); ) {
180                 final ValueBox vb = (ValueBox) vbIt.next();
181                 if( vb.getValue() != localDefed ) continue;
182                 Unit useUnit = (Unit) useBoxToUnit.get(vb);
183                 getDefsOfAt(localDefed, useUnit).add(defUnit);
184             }
185         }
186         if(Options.v().verbose())
187             G.v().out.println("[" + graph.getBody().getMethod().getName() +
188                                "] Finished CombinedDUAnalysis...");
189  
190     }
191     private List localsInBoxes(List/*ValueBox*/ boxes) {
192         List ret = new ArrayList();
193         for( Iterator vbIt = boxes.iterator(); vbIt.hasNext(); ) {
194             final ValueBox vb = (ValueBox) vbIt.next();
195             Value v = vb.getValue();
196             if( !(v instanceof Local) ) continue;
197             ret.add(v);
198         }
199         return ret;
200     }
201
202
203 // STEP 1: What are we computing?
204
// SETS OF USE BOXES CONTAINING LOCALS => Use HashSet.
205
//
206
// STEP 2: Precisely define what we are computing.
207
// A use box B is live at program point P if there exists a path from P to the
208
// unit using B on which the local in B is not defined.
209
//
210
// STEP 3: Decide whether it is a backwards or forwards analysis.
211
// BACKWARDS
212
//
213
// STEP 4: Is the merge operator union or intersection?
214
// UNION
215
protected void merge(Object JavaDoc inoutO, Object JavaDoc inO) {
216         FlowSet inout = (FlowSet) inoutO;
217         FlowSet in = (FlowSet) inO;
218
219         inout.union(in);
220     }
221     protected void merge(Object JavaDoc in1O, Object JavaDoc in2O, Object JavaDoc outO) {
222         FlowSet in1 = (FlowSet) in1O;
223         FlowSet in2 = (FlowSet) in2O;
224         FlowSet out = (FlowSet) outO;
225
226         in1.union(in2, out);
227     }
228 // STEP 5: Define flow equations.
229
// in(s) = ( out(s) minus boxes(def(s)) ) union useboxes(s)
230
protected void flowThrough(Object JavaDoc outValue, Object JavaDoc unit, Object JavaDoc inValue) {
231         Unit u = (Unit) unit;
232         FlowSet in = (FlowSet) inValue;
233         FlowSet out = (FlowSet) outValue;
234         Local def = localDefed(u);
235         out.copy(in);
236         if(def != null) {
237             Collection boxesDefed = localToUseBoxes.get(def);
238             for( Iterator vbIt = in.toList().iterator(); vbIt.hasNext(); ) {
239                 final ValueBox vb = (ValueBox) vbIt.next();
240                 if(boxesDefed.contains(vb)) in.remove(vb);
241             }
242         }
243         in.union((FlowSet) unitToLocalUseBoxes.get(u));
244     }
245
246 // STEP 6: Determine value for start/end node, and
247
// initial approximation.
248
//
249
// end node: empty set
250
// initial approximation: empty set
251
protected Object JavaDoc entryInitialFlow()
252     {
253         return new ArraySparseSet();
254     }
255         
256     protected Object JavaDoc newInitialFlow()
257     {
258         return new ArraySparseSet();
259     }
260
261     protected void copy(Object JavaDoc source, Object JavaDoc dest) {
262         FlowSet sourceSet = (FlowSet) source;
263         FlowSet destSet = (FlowSet) dest;
264             
265         sourceSet.copy(destSet);
266     }
267
268 }
269
270
Popular Tags