KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > soot > jimple > toolkits > annotation > purity > AbstractInterproceduralAnalysis


1 /* Soot - a J*va Optimization Framework
2  * Copyright (C) 2005 Antoine Mine
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  * Implementation of the paper "A Combined Pointer and Purity Analysis for
22  * Java Programs" by Alexandru Salcianu and Martin Rinard, within the
23  * Soot Optimization Framework.
24  *
25  * by Antoine Mine, 2005/01/24
26  */

27
28 package soot.jimple.toolkits.annotation.purity;
29 import java.util.*;
30 import java.io.*;
31 import soot.*;
32 import soot.util.*;
33 import soot.util.dot.*;
34 import soot.jimple.*;
35 import soot.jimple.toolkits.callgraph.*;
36 import soot.toolkits.graph.*;
37
38 /**
39  * Inter-procedural iterator skeleton for summary-based analysis
40  *
41  * A "summary" is an abstract element associated to each method that
42  * fully models the effect of calling the method. In a summary-based
43  * analysis, the summary of a method can be computed using solely
44  * the summary of all methods it calls: the summary does not depend
45  * upon the context in which a method is called.
46  * The inter-procedural analysis interacts with a intra-procedural analysis
47  * that is able to compute the summary of one method, given the summary
48  * of all the method it calls. The inter-procedural analysis calls the
49  * intra-procedural analysis in a reverse topological order of method
50  * dependencies to resolve unknown summaries. It iterates over recursively
51  * dependant methods.
52  *
53  * Generally, the intra-procedural works by maintaining an abstract
54  * value that represent the effect of the method from its entry point
55  * and up to the current point. At the entry point, this value is empty.
56  * The summary of the method is then the merge of the abstract values
57  * at all its return points.
58  *
59  * You can provide off-the-shelf summaries for methods you do not
60  * which to analyse. Any method using these "filtered-out" methods will
61  * use the off-the-shelf summary instead of performing an intra-procedural
62  * analysis. This is useful for native methods, incremental analysis,
63  * or when you hand-made summary. Methods that are called solely by
64  * filtered-out ones will never be analysed, effectively triming the
65  * call-graph dependencies.
66  *
67  * This class tries to use the same abstract methods and data managnment
68  * policy as regular FlowAnalysis classes.
69  */

70 public abstract class AbstractInterproceduralAnalysis {
71
72     public static final boolean doCheck = false;
73
74     protected CallGraph cg; // analysed call-graph
75
protected DirectedGraph dg; // filtered trimed call-graph
76
protected Map data; // SootMethod -> summary
77
protected Map order; // SootMethod -> topo order
78
protected Map unanalysed; // SootMethod -> summary
79

80
81     /** Initial summary value for analysed funtions. */
82     protected abstract Object JavaDoc newInitialSummary();
83     
84     /**
85      * Whenever the analyse requires the summary of a method you filtered-out,
86      * this function is called instead of analyseMethod.
87      *
88      * <p> Note: This function is called at most once per filtered-out
89      * method. It is the equivalent of entryInitialFlow!
90      *
91      */

92     protected abstract Object JavaDoc summaryOfUnanalysedMethod(SootMethod method);
93
94     /**
95      * Compute the summary for a method by analysing its body.
96      *
97      * Will be called only on methods not filtered-out.
98      *
99      * @param method is the method to be analysed
100      * @param dst is where to put the computed method summary
101      */

102     protected abstract void analyseMethod(SootMethod method,
103                       Object JavaDoc dst);
104
105     /**
106      * Interprocedural analysis will call applySummary repeatidly as a
107      * consequence to analyseCall. Once for each possible target method
108      * of the callStmt statement, provided with its summary.
109      *
110      * @param src summary valid before the call statement
111      * @param callStmt a statement containing a InvokeStmt or InvokeExpr
112      * @param summary summary of the possible target of callStmt considered
113      * here
114      * @param dst where to put the result
115      * @see analyseCall
116      */

117     protected abstract void applySummary(Object JavaDoc src,
118                      Stmt callStmt,
119                      Object JavaDoc summary,
120                      Object JavaDoc dst);
121
122     /**
123      * Merge in1 and in2 into out.
124      *
125      * <p> Note: in1 or in2 can be aliased to out (e.g., analyseCall).
126      */

127     protected abstract void merge(Object JavaDoc in1, Object JavaDoc in2, Object JavaDoc out);
128     
129     /** Copy src into dst. */
130     protected abstract void copy(Object JavaDoc sr, Object JavaDoc dst);
131
132     /**
133      * Called by drawAsOneDot to fill dot subgraph out with the contents
134      * of summary o.
135      *
136      * @param prefix gives you a unique string to prefix your node names
137      * and avoid name-clash
138      */

139     protected void fillDotGraph(String JavaDoc prefix, Object JavaDoc o, DotGraph out)
140     { throw new Error JavaDoc("abstract function AbstractInterproceduralAnalysis.fillDotGraph called but not implemented."); }
141  
142
143    /**
144      * Analyse the call callStmt in the context src, and put the resul into
145      * dst.
146      * This will repeatidly calling summaryOfUnanalysedMethod and applySummary,
147      * and then merging the results using merge.
148      *
149      * @see summaryOfUnanalysedMethod
150      * @see applySummary
151      */

152     protected void analyseCall(Object JavaDoc src,
153                    Stmt callStmt,
154                    Object JavaDoc dst)
155     {
156     Object JavaDoc accum = newInitialSummary();
157     Iterator it = cg.edgesOutOf(callStmt);
158     copy(accum, dst);
159     while (it.hasNext()) {
160         Edge edge = (Edge)it.next();
161         SootMethod m = edge.tgt();
162         Object JavaDoc elem;
163         if (data.containsKey(m)) {
164         // analysed method
165
elem = data.get(m);
166         }
167         else {
168         // unanalysed method
169
if (!unanalysed.containsKey(m))
170             unanalysed.put(m, summaryOfUnanalysedMethod(m));
171         elem = unanalysed.get(m);
172         }
173         applySummary(src, callStmt, elem, accum);
174         merge(dst, accum, dst);
175     }
176     }
177
178
179     /**
180      * The constructor performs some preprocessing, but you have to call
181      * doAnalysis to preform the real stuff.
182      */

183     public AbstractInterproceduralAnalysis(CallGraph cg,
184                        SootMethodFilter filter,
185                        Iterator heads,
186                        boolean verbose)
187     {
188     this.cg = cg;
189     this.dg = new DirectedCallGraph(cg, filter, heads, verbose);
190     this.data = new HashMap();
191     this.unanalysed = new HashMap();
192
193     // construct reverse pseudo topological order on filtered methods
194
this.order = new HashMap();
195     PseudoTopologicalOrderer o = new ReversePseudoTopologicalOrderer();
196     Iterator it = (o.newList(dg)).iterator();
197     int i = 0;
198     while (it.hasNext()) {
199         this.order.put(it.next(), new Integer JavaDoc(i));
200         i++;
201     }
202     }
203
204     /**
205      * Dump the interprocedural analysis result as a graph.
206      * One node / subgraph for each analysed method that contains the
207      * method summary, and call-to edges.
208      *
209      * <p> Note: this graph does not show filtered-out methods for which a
210      * conservative summary was asked via summaryOfUnanalysedMethod.
211      *
212      * @param name output filename
213      * @see fillDotGraph
214      */

215     public void drawAsOneDot(String JavaDoc name)
216     {
217     DotGraph dot = new DotGraph(name);
218     dot.setGraphLabel(name);
219     dot.setGraphAttribute("compound","true");
220     //dot.setGraphAttribute("rankdir","LR");
221
int id = 0;
222     Map idmap = new HashMap();
223
224     // draw sub-graph cluster
225
Iterator it = dg.iterator();
226     while (it.hasNext()) {
227         SootMethod m = (SootMethod)it.next();
228         DotGraph sub = dot.createSubGraph("cluster"+id);
229         DotGraphNode label = sub.drawNode("head"+id);
230         idmap.put(m, new Integer JavaDoc(id));
231         sub.setGraphLabel("");
232         label.setLabel("("+order.get(m)+") "+m.toString());
233         label.setAttribute("fontsize","18");
234         label.setShape("box");
235         if (data.containsKey(m))
236         fillDotGraph("X"+id, data.get(m), sub);
237         id++;
238     }
239
240     // connect edges
241
it = dg.iterator();
242     while (it.hasNext()) {
243         SootMethod m = (SootMethod)it.next();
244         Iterator itt = dg.getSuccsOf(m).iterator();
245         while (itt.hasNext()) {
246         SootMethod mm = (SootMethod)itt.next();
247         DotGraphEdge edge = dot.drawEdge("head"+idmap.get(m),
248                          "head"+idmap.get(mm));
249         edge.setAttribute("ltail","cluster"+idmap.get(m));
250         edge.setAttribute("lhead","cluster"+idmap.get(mm));
251         }
252
253     }
254
255
256     File f = new File (SourceLocator.v().getOutputDir(),
257                name+DotGraph.DOT_EXTENSION);
258     dot.plot(f.getPath());
259     }
260
261     /**
262      * Dump the each summary computed by the interprocedural analysis as
263      * a seperate graph.
264      *
265      * @param prefix is prepended before method name in output filename
266      * @param drawUnanalysed do you also want info for the unanalysed methods
267      * required by the analysis via summaryOfUnanalysedMethod ?
268      *
269      * @see fillDotGraph
270      */

271     public void drawAsManyDot(String JavaDoc prefix, boolean drawUnanalysed)
272     {
273     Iterator it = data.keySet().iterator();
274     while (it.hasNext()) {
275         SootMethod m = (SootMethod)it.next();
276         DotGraph dot = new DotGraph(m.toString());
277         dot.setGraphLabel(m.toString());
278         fillDotGraph("X", data.get(m), dot);
279         File f = new File (SourceLocator.v().getOutputDir(),
280                    prefix+m.toString()+DotGraph.DOT_EXTENSION);
281         dot.plot(f.getPath());
282     }
283     
284     if (drawUnanalysed) {
285         it = unanalysed.keySet().iterator();
286         while (it.hasNext()) {
287         SootMethod m = (SootMethod)it.next();
288         DotGraph dot = new DotGraph(m.toString());
289         dot.setGraphLabel(m.toString()+" (unanalysed)");
290         fillDotGraph("X", unanalysed.get(m), dot);
291         File f = new File (SourceLocator.v().getOutputDir(),
292                    prefix+m.toString()+"_u"+
293                    DotGraph.DOT_EXTENSION);
294         dot.plot(f.getPath());
295         }
296     }
297     }
298
299     /**
300      * Query the analysis result.
301      */

302     public Object JavaDoc getSummaryFor(SootMethod m)
303     {
304     if (data.containsKey(m)) return data.get(m);
305     if (unanalysed.containsKey(m)) return unanalysed.get(m);
306     return newInitialSummary();
307     }
308
309     /**
310      * Get an iterator over the list of SootMethod with an associated summary.
311      * (Does not contain filtered-out or native methods.)
312      */

313     public Iterator getAnalysedMethods()
314     { return data.keySet().iterator(); }
315
316     /**
317      * Carry out the analysis.
318      *
319      * Call this from your InterproceduralAnalysis constructor,
320      * just after super(cg).
321      * Then , you will be able to call drawAsDot, for instance.
322      */

323     protected void doAnalysis(boolean verbose)
324     {
325     // queue class
326
class IntComparator implements Comparator {
327         public int compare(Object JavaDoc o1, Object JavaDoc o2)
328         {
329         Integer JavaDoc v1 = (Integer JavaDoc)order.get(o1);
330         Integer JavaDoc v2 = (Integer JavaDoc)order.get(o2);
331         return v1.intValue()-v2.intValue();
332         }
333         public boolean equals(Object JavaDoc o1, Object JavaDoc o2)
334         {
335         Integer JavaDoc v1 = (Integer JavaDoc)order.get(o1);
336         Integer JavaDoc v2 = (Integer JavaDoc)order.get(o2);
337         return v1.intValue()==v2.intValue();
338         }
339     };
340     SortedSet queue = new TreeSet(new IntComparator());
341     
342     // init
343
Iterator it = order.keySet().iterator();
344     while (it.hasNext()) {
345         Object JavaDoc o = it.next();
346         data.put(o, newInitialSummary());
347         queue.add(o);
348     }
349
350     Map nb = new HashMap(); // only for debug pretty-printing
351

352     // fixpoint iterations
353
while (!queue.isEmpty()) {
354         SootMethod m = (SootMethod)queue.first();
355         queue.remove(m);
356         Object JavaDoc newSummary = newInitialSummary();
357         Object JavaDoc oldSummary = data.get(m);
358
359         if (nb.containsKey(m)) nb.put(m,new Integer JavaDoc(((Integer JavaDoc)nb.get(m)).intValue()+1));
360         else nb.put(m,new Integer JavaDoc(1));
361         if (verbose)
362         G.v().out.println(" |- processing "+m.toString()+" ("+nb.get(m)+"-st time)");
363
364         analyseMethod(m,newSummary);
365         if (!oldSummary.equals(newSummary)) {
366         // summary for m changed!
367
data.put(m,newSummary);
368         queue.addAll(dg.getPredsOf(m));
369         }
370     }
371
372     // fixpoint verification
373
if (doCheck) {
374         it = order.keySet().iterator();
375         while (it.hasNext()) {
376         SootMethod m = (SootMethod)it.next();
377         Object JavaDoc newSummary = newInitialSummary();
378         Object JavaDoc oldSummary = data.get(m);
379         analyseMethod(m,newSummary);
380         if (!oldSummary.equals(newSummary)) {
381             G.v().out.println("inter-procedural fixpoint not reached for method "+m.toString());
382             DotGraph gm = new DotGraph("false_fixpoint");
383             DotGraph gmm = new DotGraph("next_iterate");
384             gm.setGraphLabel("false fixpoint: "+m.toString());
385             gmm.setGraphLabel("fixpoint next iterate: "+m.toString());
386             fillDotGraph("", oldSummary, gm);
387             fillDotGraph("", newSummary, gmm);
388             gm.plot(m.toString()+"_false_fixpoint.dot");
389             gmm.plot(m.toString()+"_false_fixpoint_next.dot");
390             throw new Error JavaDoc("AbstractInterproceduralAnalysis sanity check failed!!!");
391         }
392         }
393     }
394
395     }
396 }
397
398
Popular Tags