001: /* Soot - a J*va Optimization Framework
002: * Copyright (C) 2005 Antoine Mine
003: *
004: * This library is free software; you can redistribute it and/or
005: * modify it under the terms of the GNU Lesser General Public
006: * License as published by the Free Software Foundation; either
007: * version 2.1 of the License, or (at your option) any later version.
008: *
009: * This library is distributed in the hope that it will be useful,
010: * but WITHOUT ANY WARRANTY; without even the implied warranty of
011: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
012: * Lesser General Public License for more details.
013: *
014: * You should have received a copy of the GNU Lesser General Public
015: * License along with this library; if not, write to the
016: * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
017: * Boston, MA 02111-1307, USA.
018: */
019:
020: /**
021: * Implementation of the paper "A Combined Pointer and Purity Analysis for
022: * Java Programs" by Alexandru Salcianu and Martin Rinard, within the
023: * Soot Optimization Framework.
024: *
025: * by Antoine Mine, 2005/01/24
026: */package soot.jimple.toolkits.annotation.purity;
027:
028: import java.util.*;
029: import soot.*;
030: import soot.util.dot.*;
031: import soot.jimple.*;
032: import soot.jimple.toolkits.callgraph.*;
033: import soot.toolkits.graph.*;
034: import soot.options.PurityOptions;
035: import soot.tagkit.*;
036:
037: public class PurityInterproceduralAnalysis extends
038: AbstractInterproceduralAnalysis {
039:
040: // Note: these method lists are adapted to JDK-1.4.2.06 and may
041: // not work for other versions
042:
043: // unanalysed methods assumed pure (& return a new obj)
044: // class name prefix / method name
045: static private final String[][] pureMethods = {
046: { "java.lang.", "valueOf" },
047: { "java.", "equals" },
048: { "javax.", "equals" },
049: { "sun.", "equals" },
050: { "java.", "compare" },
051: { "javax.", "compare" },
052: { "sun.", "compare" },
053: { "java.", "getClass" },
054: { "javax.", "getClass" },
055: { "sun.", "getClass" },
056: { "java.", "hashCode" },
057: { "javax.", "hashCode" },
058: { "sun.", "hashCode" },
059: { "java.", "toString" },
060: { "javax.", "toString" },
061: { "sun.", "toString" },
062: { "java.", "valueOf" },
063: { "javax.", "valueOf" },
064: { "sun.", "valueOf" },
065: { "java.", "compareTo" },
066: { "javax.", "compareTo" },
067: { "sun.", "compareTo" },
068:
069: { "java.lang.System", "identityHashCode" },
070:
071: // we assume that all standard class initialisers are pure!!!
072: { "java.", "<clinit>" },
073: { "javax.", "<clinit>" },
074: { "sun.", "<clinit>" },
075:
076: // if we define these as pure, the analysis will find them impure as
077: // they call static native functions that could, in theory,
078: // change the whole program state under our feets
079: { "java.lang.Math", "abs" }, { "java.lang.Math", "acos" },
080: { "java.lang.Math", "asin" }, { "java.lang.Math", "atan" },
081: { "java.lang.Math", "atan2" },
082: { "java.lang.Math", "ceil" }, { "java.lang.Math", "cos" },
083: { "java.lang.Math", "exp" }, { "java.lang.Math", "floor" },
084: { "java.lang.Math", "IEEEremainder" },
085: { "java.lang.Math", "log" }, { "java.lang.Math", "max" },
086: { "java.lang.Math", "min" }, { "java.lang.Math", "pow" },
087: { "java.lang.Math", "rint" },
088: { "java.lang.Math", "round" }, { "java.lang.Math", "sin" },
089: { "java.lang.Math", "sqrt" }, { "java.lang.Math", "tan" },
090: // TODO: put StrictMath as well ?
091:
092: { "java.lang.Throwable", "<init>" },
093:
094: // to break the cycle exception -> getCharsAt -> exception
095: { "java.lang.StringIndexOutOfBoundsException", "<init>" } };
096:
097: // unanalysed methods that modify the whole environment
098: static private final String[][] impureMethods = {
099: { "java.io.", "<init>" }, { "java.io.", "close" },
100: { "java.io.", "read" }, { "java.io.", "write" },
101: { "java.io.", "flush" }, { "java.io.", "flushBuffer" },
102: { "java.io.", "print" }, { "java.io.", "println" },
103:
104: { "java.lang.Runtime", "exit" },
105:
106: /*
107: // for soot...
108: {"java.io.","skip"},
109: {"java.io.","ensureOpen"},
110: {"java.io.","fill"},
111: {"java.io.","readLine"},
112: {"java.io.","available"},
113: {"java.io.","mark"},
114: {"java.io.","reset"},
115: {"java.io.","toByteArray"},
116: {"java.io.","size"},
117: {"java.io.","writeTo"},
118: {"java.io.","readBoolean"},
119: {"java.io.","readChar"},
120: {"java.io.","readDouble"},
121: {"java.io.","readFloat"},
122: {"java.io.","readByte"},
123: {"java.io.","readShort"},
124: {"java.io.","readInt"},
125: {"java.io.","readLong"},
126: {"java.io.","readUnsignedByte"},
127: {"java.io.","readUnsignedShort"},
128: {"java.io.","readUTF"},
129: {"java.io.","readFully"},
130: {"java.io.","writeBoolean"},
131: {"java.io.","writeChar"},
132: {"java.io.","writeChars"},
133: {"java.io.","writeDouble"},
134: {"java.io.","writeFloat"},
135: {"java.io.","writeByte"},
136: {"java.io.","writeBytes"},
137: {"java.io.","writeShort"},
138: {"java.io.","writeInt"},
139: {"java.io.","writeLong"},
140: {"java.io.","writeUTF"},
141: {"java.io.","canRead"},
142: {"java.io.","delete"},
143: {"java.io.","exists"},
144: {"java.io.","isDirectory"},
145: {"java.io.","isFile"},
146: {"java.io.","mkdir"},
147: {"java.io.","mkdirs"},
148: {"java.io.","getAbsoluteFile"},
149: {"java.io.","getCanonicalFile"},
150: {"java.io.","getParentFile"},
151: {"java.io.","listFiles"},
152: {"java.io.","getAbsolutePath"},
153: {"java.io.","getCanonicalPath"},
154: {"java.io.","getName"},
155: {"java.io.","getParent"},
156: {"java.io.","getPath"},
157: {"java.io.","list"},
158: {"java.io.","toURI"},
159: {"java.io.","lastModified"},
160: {"java.io.","length"},
161: {"java.io.","implies"},
162: {"java.io.","newPermissionCollection"},
163: {"java.io.","getLineNumber"},
164: {"java.io.","enableResolveObject"},
165: {"java.io.","readClassDescriptor"},
166: {"java.io.","readFields"},
167: {"java.io.","readObject"},
168: {"java.io.","readUnshared"},
169: {"java.io.","defaultReadObject"},
170: {"java.io.","defaultWriteObject"},
171: {"java.io.","putFields"},
172: {"java.io.","writeFields"},
173: {"java.io.","writeObject"},
174: {"java.io.","writeUnshared"},
175: {"java.io.","unread"},
176: {"java.io.","lineno"},
177: {"java.io.","nextToken"},
178: {"java.io.","commentChar"},
179: {"java.io.","lowerCaseMode"},
180: {"java.io.","ordinaryChar"},
181: {"java.io.","quoteChar"},
182: {"java.io.","resetSyntax"},
183: {"java.io.","slashSlashComments"},
184: {"java.io.","slashSltarComments"},
185: {"java.io.","whitespaceChars"},
186: {"java.io.","wordChars"},
187: {"java.io.","markSupported"},
188: {"java.","getCause"},
189: {"java.","getMessage"},
190: {"java.","getReason"},
191: */
192:
193: };
194:
195: // unanalysed methods that alter its arguments, but have no side effect
196: static private final String[][] alterMethods = {
197: { "java.lang.System", "arraycopy" },
198:
199: // these are really huge methods used internally by StringBuffer
200: // printing => put here to speed-up the analysis
201: { "java.lang.FloatingDecimal", "dtoa" },
202: { "java.lang.FloatingDecimal", "developLongDigits" },
203: { "java.lang.FloatingDecimal", "big5pow" },
204: { "java.lang.FloatingDecimal", "getChars" },
205: { "java.lang.FloatingDecimal", "roundup" }, };
206:
207: /** Filter out some method. */
208: static private class Filter implements SootMethodFilter {
209: public boolean want(SootMethod method) {
210: // could be optimized with HashSet....
211: String c = method.getDeclaringClass().toString();
212: String m = method.getName();
213: String[][] o = PurityInterproceduralAnalysis.pureMethods;
214: for (String[] element : o)
215: if (m.equals(element[1]) && c.startsWith(element[0]))
216: return false;
217: o = PurityInterproceduralAnalysis.impureMethods;
218: for (String[] element : o)
219: if (m.equals(element[1]) && c.startsWith(element[0]))
220: return false;
221: o = PurityInterproceduralAnalysis.alterMethods;
222: for (String[] element : o)
223: if (m.equals(element[1]) && c.startsWith(element[0]))
224: return false;
225: return true;
226: }
227: }
228:
229: /** The constructor does it all! */
230: PurityInterproceduralAnalysis(CallGraph cg,
231: Iterator<SootMethod> heads, PurityOptions opts) {
232: super (cg, new Filter(), heads, opts.dump_cg());
233:
234: if (opts.dump_cg()) {
235: G.v().out.println("[AM] Dumping empty .dot call-graph");
236: drawAsOneDot("EmptyCallGraph");
237: }
238:
239: Date start = new Date();
240: G.v().out.println("[AM] Analysis began");
241: doAnalysis(opts.verbose());
242: G.v().out.println("[AM] Analysis finished");
243: Date finish = new Date();
244: long runtime = finish.getTime() - start.getTime();
245: G.v().out.println("[AM] run time: " + runtime / 1000. + " s");
246:
247: if (opts.dump_cg()) {
248: G.v().out.println("[AM] Dumping annotated .dot call-graph");
249: drawAsOneDot("CallGraph");
250: }
251:
252: if (opts.dump_summaries()) {
253: G.v().out
254: .println("[AM] Dumping .dot summaries of analysed methods");
255: drawAsManyDot("Summary_", false);
256: }
257:
258: if (opts.dump_intra()) {
259: G.v().out
260: .println("[AM] Dumping .dot full intra-procedural method analyses");
261: // relaunch the interprocedural analysis once on each method
262: // to get a purity graph at each statement, not only summaries
263: Iterator it = getAnalysedMethods();
264: while (it.hasNext()) {
265: SootMethod method = (SootMethod) it.next();
266: Body body = method.retrieveActiveBody();
267: ExceptionalUnitGraph graph = new ExceptionalUnitGraph(
268: body);
269: if (opts.verbose())
270: G.v().out.println(" |- " + method);
271: PurityIntraproceduralAnalysis r = new PurityIntraproceduralAnalysis(
272: graph, this );
273: r.drawAsOneDot("Intra_", method.toString());
274: PurityGraphBox b = new PurityGraphBox();
275: r.copyResult(b);
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: "
296: + (isPure ? "pure" : "impure")));
297: if (opts.print())
298: G.v().out.println(" |- method " + m.toString()
299: + " is " + (isPure ? "pure" : "impure"));
300:
301: // param & this ro / safety
302: if (!m.isStatic()) {
303: int status = b.g.this Status();
304: String s;
305: switch (status) {
306: case PurityGraph.PARAM_RW:
307: s = "read/write";
308: break;
309: case PurityGraph.PARAM_RO:
310: s = "read-only";
311: break;
312: case PurityGraph.PARAM_SAFE:
313: s = "Safe";
314: break;
315: default:
316: s = "unknown";
317: }
318: /* m.addTag(new GenericAttribute("thisStatus",s.getBytes()));
319: */
320: m.addTag(new StringTag("this: " + s));
321: if (opts.print())
322: G.v().out.println(" | |- this is " + s);
323: }
324:
325: Iterator itt = m.getParameterTypes().iterator();
326: int i = 0;
327: while (itt.hasNext()) {
328: if (itt.next() instanceof RefLikeType) {
329: int status = b.g.paramStatus(i);
330: String s;
331: switch (status) {
332: case PurityGraph.PARAM_RW:
333: s = "read/write";
334: break;
335: case PurityGraph.PARAM_RO:
336: s = "read-only";
337: break;
338: case PurityGraph.PARAM_SAFE:
339: s = "safe";
340: break;
341: default:
342: s = "unknown";
343: }
344: /*
345: m.addTag(new GenericAttribute("param"+i+"Status",
346: s.getBytes()));
347: */
348: m.addTag(new StringTag("param" + i + ": " + s));
349: if (opts.print())
350: G.v().out.println(" | |- param " + i
351: + " is " + s);
352: }
353: i++;
354: }
355: }
356: }
357:
358: }
359:
360: protected Object newInitialSummary() {
361: return new PurityGraphBox();
362: }
363:
364: protected void merge(Object in1, Object in2, Object out) {
365: PurityGraphBox i1 = (PurityGraphBox) in1;
366: PurityGraphBox i2 = (PurityGraphBox) in2;
367: PurityGraphBox o = (PurityGraphBox) out;
368: if (out != i1)
369: o.g = new PurityGraph(i1.g);
370: o.g.union(i2.g);
371: }
372:
373: protected void copy(Object source, Object dest) {
374: PurityGraphBox src = (PurityGraphBox) source;
375: PurityGraphBox dst = (PurityGraphBox) dest;
376: dst.g = new PurityGraph(src.g);
377: }
378:
379: protected void analyseMethod(SootMethod method, Object dst) {
380: Body body = method.retrieveActiveBody();
381: ExceptionalUnitGraph graph = new ExceptionalUnitGraph(body);
382: PurityIntraproceduralAnalysis r = new PurityIntraproceduralAnalysis(
383: graph, this );
384: r.copyResult(dst);
385: }
386:
387: /**
388: * @see PurityGraph.conservativeGraph
389: * @see PurityGraph.freshGraph
390: */
391: protected Object summaryOfUnanalysedMethod(SootMethod method) {
392: PurityGraphBox b = new PurityGraphBox();
393: String c = method.getDeclaringClass().toString();
394: String m = method.getName();
395:
396: // impure with side-effect, unless otherwise specified
397: b.g = PurityGraph.conservativeGraph(method, true);
398:
399: String[][] o = PurityInterproceduralAnalysis.pureMethods;
400: for (String[] element : o)
401: if (m.equals(element[1]) && c.startsWith(element[0]))
402: b.g = PurityGraph.freshGraph(method);
403:
404: o = PurityInterproceduralAnalysis.alterMethods;
405: for (String[] element : o)
406: if (m.equals(element[1]) && c.startsWith(element[0]))
407: b.g = PurityGraph.conservativeGraph(method, false);
408:
409: return b;
410: }
411:
412: /**
413: * @param stmt any statement containing an InvokeExpr
414: * @see PurityGraph.methodCall
415: */
416: protected void applySummary(Object src, Stmt stmt, Object summary,
417: Object dst) {
418: // extract call info
419: InvokeExpr e = stmt.getInvokeExpr();
420: Local ret = null;
421: if (stmt instanceof AssignStmt) {
422: Local v = (Local) ((AssignStmt) stmt).getLeftOp();
423: if (v.getType() instanceof RefLikeType)
424: ret = v;
425: }
426: Local obj = null;
427: if (!(e instanceof StaticInvokeExpr))
428: obj = (Local) ((InstanceInvokeExpr) e).getBase();
429: List args = e.getArgs();
430:
431: // call methoCall on the PurityGraph
432: PurityGraphBox s = (PurityGraphBox) src;
433: PurityGraphBox d = (PurityGraphBox) dst;
434: PurityGraph g = new PurityGraph(s.g);
435: g.methodCall(((PurityGraphBox) summary).g, obj, args, ret);
436: d.g = g;
437: }
438:
439: protected void fillDotGraph(String prefix, Object o, DotGraph out) {
440: PurityGraphBox b = (PurityGraphBox) o;
441: b.g.fillDotGraph(prefix, out);
442: }
443:
444: }
|