KickJava   Java API By Example, From Geeks To Geeks.

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


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.scalar.*;
37 import soot.toolkits.graph.*;
38 import soot.options.PurityOptions;
39 import soot.tagkit.*;
40
41 public class PurityInterproceduralAnalysis
42     extends AbstractInterproceduralAnalysis {
43
44     // Note: these method lists are adapted to JDK-1.4.2.06 and may
45 // not work for other versions
46
47     // unanalysed methods assumed pure (& return a new obj)
48 // class name prefix / method name
49 static private final String JavaDoc[][] pureMethods =
50     { {"java.lang.","valueOf"},
51     {"java.","equals"},{"javax.","equals"},{"sun.","equals"},
52     {"java.","compare"}, {"javax.","compare"},{"sun.","compare"},
53     {"java.","getClass"},{"javax.","getClass"},{"sun.","getClass"},
54     {"java.","hashCode"},{"javax.","hashCode"},{"sun.","hashCode"},
55     {"java.","toString"},{"javax.","toString"},{"sun.","toString"},
56     {"java.","valueOf"},{"javax.","valueOf"},{"sun.","valueOf"},
57     {"java.","compareTo"},{"javax.","compareTo"},{"sun.","compareTo"},
58
59     {"java.lang.System","identityHashCode"},
60
61     // we assume that all standard class initialisers are pure!!!
62 {"java.","<clinit>"}, {"javax.","<clinit>"}, {"sun.","<clinit>"},
63     
64     // if we define these as pure, the analysis will find them impure as
65 // they call static native functions that could, in theory,
66 // change the whole program state under our feets
67 { "java.lang.Math","abs" },
68     { "java.lang.Math","acos" },
69     { "java.lang.Math","asin" },
70     { "java.lang.Math","atan" },
71     { "java.lang.Math","atan2" },
72     { "java.lang.Math","ceil" },
73     { "java.lang.Math","cos" },
74     { "java.lang.Math","exp" },
75     { "java.lang.Math","floor" },
76     { "java.lang.Math","IEEEremainder" },
77     { "java.lang.Math","log" },
78     { "java.lang.Math","max" },
79     { "java.lang.Math","min" },
80     { "java.lang.Math","pow" },
81     { "java.lang.Math","rint" },
82     { "java.lang.Math","round" },
83     { "java.lang.Math","sin" },
84     { "java.lang.Math","sqrt" },
85     { "java.lang.Math","tan" },
86     // TODO: put StrictMath as well ?
87
88     {"java.lang.Throwable", "<init>"},
89
90     // to break the cycle exception -> getCharsAt -> exception
91 {"java.lang.StringIndexOutOfBoundsException","<init>"}
92     };
93
94     // unanalysed methods that modify the whole environment
95 static private final String JavaDoc[][] impureMethods =
96     {
97     {"java.io.","<init>"},
98     {"java.io.","close"},
99     {"java.io.","read"},
100     {"java.io.","write"},
101     {"java.io.","flush"},
102     {"java.io.","flushBuffer"},
103     {"java.io.","print"},
104     {"java.io.","println"},
105
106     {"java.lang.Runtime","exit"},
107
108     /*
109     // for soot...
110     {"java.io.","skip"},
111     {"java.io.","ensureOpen"},
112     {"java.io.","fill"},
113     {"java.io.","readLine"},
114     {"java.io.","available"},
115     {"java.io.","mark"},
116     {"java.io.","reset"},
117     {"java.io.","toByteArray"},
118     {"java.io.","size"},
119     {"java.io.","writeTo"},
120     {"java.io.","readBoolean"},
121     {"java.io.","readChar"},
122     {"java.io.","readDouble"},
123     {"java.io.","readFloat"},
124     {"java.io.","readByte"},
125     {"java.io.","readShort"},
126     {"java.io.","readInt"},
127     {"java.io.","readLong"},
128     {"java.io.","readUnsignedByte"},
129     {"java.io.","readUnsignedShort"},
130     {"java.io.","readUTF"},
131     {"java.io.","readFully"},
132     {"java.io.","writeBoolean"},
133     {"java.io.","writeChar"},
134     {"java.io.","writeChars"},
135     {"java.io.","writeDouble"},
136     {"java.io.","writeFloat"},
137     {"java.io.","writeByte"},
138     {"java.io.","writeBytes"},
139     {"java.io.","writeShort"},
140     {"java.io.","writeInt"},
141     {"java.io.","writeLong"},
142     {"java.io.","writeUTF"},
143     {"java.io.","canRead"},
144     {"java.io.","delete"},
145     {"java.io.","exists"},
146     {"java.io.","isDirectory"},
147     {"java.io.","isFile"},
148     {"java.io.","mkdir"},
149     {"java.io.","mkdirs"},
150     {"java.io.","getAbsoluteFile"},
151     {"java.io.","getCanonicalFile"},
152     {"java.io.","getParentFile"},
153     {"java.io.","listFiles"},
154     {"java.io.","getAbsolutePath"},
155     {"java.io.","getCanonicalPath"},
156     {"java.io.","getName"},
157     {"java.io.","getParent"},
158     {"java.io.","getPath"},
159     {"java.io.","list"},
160     {"java.io.","toURI"},
161     {"java.io.","lastModified"},
162     {"java.io.","length"},
163     {"java.io.","implies"},
164     {"java.io.","newPermissionCollection"},
165     {"java.io.","getLineNumber"},
166     {"java.io.","enableResolveObject"},
167     {"java.io.","readClassDescriptor"},
168     {"java.io.","readFields"},
169     {"java.io.","readObject"},
170     {"java.io.","readUnshared"},
171     {"java.io.","defaultReadObject"},
172     {"java.io.","defaultWriteObject"},
173     {"java.io.","putFields"},
174     {"java.io.","writeFields"},
175     {"java.io.","writeObject"},
176     {"java.io.","writeUnshared"},
177     {"java.io.","unread"},
178     {"java.io.","lineno"},
179     {"java.io.","nextToken"},
180     {"java.io.","commentChar"},
181     {"java.io.","lowerCaseMode"},
182     {"java.io.","ordinaryChar"},
183     {"java.io.","quoteChar"},
184     {"java.io.","resetSyntax"},
185     {"java.io.","slashSlashComments"},
186     {"java.io.","slashSltarComments"},
187     {"java.io.","whitespaceChars"},
188     {"java.io.","wordChars"},
189     {"java.io.","markSupported"},
190     {"java.","getCause"},
191     {"java.","getMessage"},
192     {"java.","getReason"},
193     */
194
195     };
196     
197     // unanalysed methods that alter its arguments, but have no side effect
198 static private final String JavaDoc[][] alterMethods =
199     {
200     {"java.lang.System","arraycopy"},
201
202     // these are really huge methods used internally by StringBuffer
203 // printing => put here to speed-up the analysis
204 {"java.lang.FloatingDecimal","dtoa"},
205     {"java.lang.FloatingDecimal","developLongDigits"},
206     {"java.lang.FloatingDecimal","big5pow"},
207     {"java.lang.FloatingDecimal","getChars"},
208     {"java.lang.FloatingDecimal","roundup"},
209     };
210
211     /** Filter out some method. */
212     static private class Filter implements SootMethodFilter {
213     public boolean want(SootMethod method) {
214         // could be optimized with HashSet....
215 String JavaDoc c = method.getDeclaringClass().toString();
216         String JavaDoc m = method.getName();
217         String JavaDoc[][] o = PurityInterproceduralAnalysis.pureMethods;
218         for (int i=0;i<o.length;i++)
219         if (m.equals(o[i][1]) && c.startsWith(o[i][0])) return false;
220         o = PurityInterproceduralAnalysis.impureMethods;
221         for (int i=0;i<o.length;i++)
222         if (m.equals(o[i][1]) && c.startsWith(o[i][0])) return false;
223         o = PurityInterproceduralAnalysis.alterMethods;
224         for (int i=0;i<o.length;i++)
225         if (m.equals(o[i][1]) && c.startsWith(o[i][0])) return false;
226         return true;
227     }
228     }
229     
230     /** The constructor does it all! */
231     PurityInterproceduralAnalysis(CallGraph cg,
232                   Iterator heads,
233                   PurityOptions opts)
234     {
235     super(cg,new Filter(),heads, opts.dump_cg());
236     
237     if (opts.dump_cg()) {
238         G.v().out.println("[AM] Dumping empty .dot call-graph");
239         drawAsOneDot("EmptyCallGraph");
240     }
241
242     Date start = new Date();
243     G.v().out.println("[AM] Analysis began");
244     doAnalysis(opts.verbose());
245     G.v().out.println("[AM] Analysis finished");
246     Date finish = new Date();
247     long runtime = finish.getTime() - start.getTime();
248     G.v().out.println("[AM] run time: "+runtime/1000.+" s");
249
250     if (opts.dump_cg()) {
251         G.v().out.println("[AM] Dumping annotated .dot call-graph");
252         drawAsOneDot("CallGraph");
253     }
254
255     if (opts.dump_summaries()) {
256         G.v().out.println("[AM] Dumping .dot summaries of analysed methods");
257         drawAsManyDot("Summary_",false);
258     }
259
260     if (opts.dump_intra()) {
261         G.v().out.println("[AM] Dumping .dot full intra-procedural method analyses");
262         // relaunch the interprocedural analysis once on each method
263 // to get a purity graph at each statement, not only summaries
264 Iterator it = getAnalysedMethods();
265         while (it.hasNext()) {
266         SootMethod method = (SootMethod)it.next();
267         Body body = method.retrieveActiveBody();
268         ExceptionalUnitGraph graph = new ExceptionalUnitGraph(body);
269         if (opts.verbose()) G.v().out.println(" |- "+method);
270         PurityIntraproceduralAnalysis r =
271             new PurityIntraproceduralAnalysis(graph, this);
272         r.drawAsOneDot("Intra_",method.toString());
273         PurityGraphBox b = new PurityGraphBox();
274         r.copyResult(b);
275         }
276     }
277
278
279     {
280         G.v().out.println("[AM] Annotate methods. ");
281         Iterator it = getAnalysedMethods();
282         while (it.hasNext()) {
283         SootMethod m = (SootMethod)it.next();
284         PurityGraphBox b = (PurityGraphBox)getSummaryFor(m);
285
286         // purity
287 boolean isPure;
288         if (m.toString().indexOf("<init>")!=-1)
289             isPure = b.g.isPureConstructor() ;
290         else
291             isPure = b.g.isPure();
292         /* m.addTag(new GenericAttribute("isPure",
293            (new String(isPure?"yes":"no")).getBytes()));
294         */
295         m.addTag(new StringTag("purity: "+(isPure?"pure":"impure")));
296         if (opts.print())
297             G.v().out.println(" |- method "+m.toString()+" is "+(isPure?"pure":"impure"));
298
299         // param & this ro / safety
300 if (!m.isStatic()) {
301             int status = b.g.thisStatus();
302             String JavaDoc s;
303             switch (status) {
304             case PurityGraph.PARAM_RW: s = "read/write";break;
305             case PurityGraph.PARAM_RO: s = "read-only";break;
306             case PurityGraph.PARAM_SAFE: s = "Safe";break;
307             default: s = "unknown";
308             }
309             /* m.addTag(new GenericAttribute("thisStatus",s.getBytes()));
310              */
311             m.addTag(new StringTag("this: "+s));
312             if (opts.print()) G.v().out.println(" | |- this is "+s);
313         }
314         
315         Iterator itt = m.getParameterTypes().iterator();
316         int i = 0;
317         while (itt.hasNext()) {
318             if (itt.next() instanceof RefLikeType) {
319             int status = b.g.paramStatus(i);
320             String JavaDoc s;
321             switch (status) {
322             case PurityGraph.PARAM_RW: s = "read/write";break;
323             case PurityGraph.PARAM_RO: s = "read-only";break;
324             case PurityGraph.PARAM_SAFE: s = "safe";break;
325             default: s = "unknown";
326             }
327             /*
328               m.addTag(new GenericAttribute("param"+i+"Status",
329               s.getBytes()));
330             */
331             m.addTag(new StringTag("param"+i+": "+s));
332             if (opts.print())
333                 G.v().out.println(" | |- param "+i+" is "+s);
334             }
335             i++;
336         }
337         }
338     }
339
340     }
341
342     protected Object JavaDoc newInitialSummary()
343     { return new PurityGraphBox(); }
344
345     protected void merge(Object JavaDoc in1, Object JavaDoc in2, Object JavaDoc out)
346     {
347     PurityGraphBox i1 = (PurityGraphBox)in1;
348     PurityGraphBox i2 = (PurityGraphBox)in2;
349     PurityGraphBox o = (PurityGraphBox)out;
350     if (out!=i1) o.g = new PurityGraph(i1.g);
351     o.g.union(i2.g);
352     }
353
354     protected void copy(Object JavaDoc source, Object JavaDoc dest)
355     {
356     PurityGraphBox src = (PurityGraphBox)source;
357     PurityGraphBox dst = (PurityGraphBox)dest;
358     dst.g = new PurityGraph(src.g);
359     }
360     
361     protected void analyseMethod(SootMethod method,
362                  Object JavaDoc dst)
363     {
364     Body body = method.retrieveActiveBody();
365     ExceptionalUnitGraph graph = new ExceptionalUnitGraph(body);
366     PurityIntraproceduralAnalysis r =
367         new PurityIntraproceduralAnalysis(graph, this);
368     r.copyResult(dst);
369     }
370
371     /**
372      * @see PurityGraph.conservativeGraph
373      * @see PurityGraph.freshGraph
374      */
375     protected Object JavaDoc summaryOfUnanalysedMethod(SootMethod method)
376     {
377     PurityGraphBox b = new PurityGraphBox();
378     String JavaDoc c = method.getDeclaringClass().toString();
379     String JavaDoc m = method.getName();
380
381     // impure with side-effect, unless otherwise specified
382 b.g = PurityGraph.conservativeGraph(method,true);
383
384     String JavaDoc[][] o = PurityInterproceduralAnalysis.pureMethods;
385     for (int i=0;i<o.length;i++)
386         if (m.equals(o[i][1]) && c.startsWith(o[i][0]))
387         b.g = PurityGraph.freshGraph(method);
388
389     o = PurityInterproceduralAnalysis.alterMethods;
390     for (int i=0;i<o.length;i++)
391         if (m.equals(o[i][1]) && c.startsWith(o[i][0]))
392         b.g = PurityGraph.conservativeGraph(method,false);
393
394     return b;
395     }
396
397     /**
398      * @param stmt any statement containing an InvokeExpr
399      * @see PurityGraph.methodCall
400      */
401     protected void applySummary(Object JavaDoc src,
402                 Stmt stmt,
403                 Object JavaDoc summary,
404                 Object JavaDoc dst)
405     {
406     // extract call info
407 InvokeExpr e = stmt.getInvokeExpr();
408     Local ret = null;
409     if (stmt instanceof AssignStmt) {
410         Local v = (Local)((AssignStmt)stmt).getLeftOp();
411         if (v.getType() instanceof RefLikeType) ret = v;
412     }
413     Local obj = null;
414     if (!(e instanceof StaticInvokeExpr))
415         obj = (Local)((InstanceInvokeExpr)e).getBase();
416     List args = e.getArgs();
417     
418     // call methoCall on the PurityGraph
419 PurityGraphBox s = (PurityGraphBox)src;
420     PurityGraphBox d = (PurityGraphBox)dst;
421     PurityGraph g = new PurityGraph(s.g);
422     g.methodCall(((PurityGraphBox)summary).g, obj, args, ret);
423     d.g = g;
424     }
425
426     protected void fillDotGraph(String JavaDoc prefix, Object JavaDoc o, DotGraph out)
427     {
428     PurityGraphBox b = (PurityGraphBox)o;
429     b.g.fillDotGraph(prefix, out);
430     }
431
432 }
433
Popular Tags