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 java.io.File;
030: import soot.*;
031: import soot.util.dot.*;
032: import soot.jimple.*;
033: import soot.toolkits.scalar.*;
034: import soot.toolkits.graph.*;
035:
036: /**
037: * Intra-procedural purity-graph analysis.
038: *
039: * You must pass an AbstractInterproceduralAnalysis object so that the
040: * intraprocedural part can resolve the effect of method calls.
041: * This manipulates PurityGraphBox.
042: */
043: public class PurityIntraproceduralAnalysis extends ForwardFlowAnalysis {
044:
045: AbstractInterproceduralAnalysis inter;
046:
047: protected Object newInitialFlow() {
048: return new PurityGraphBox();
049: }
050:
051: protected Object entryInitialFlow() {
052: return new PurityGraphBox();
053: }
054:
055: protected void merge(Object in1, Object in2, Object out) {
056: PurityGraphBox i1 = (PurityGraphBox) in1;
057: PurityGraphBox i2 = (PurityGraphBox) in2;
058: PurityGraphBox o = (PurityGraphBox) out;
059: if (out != i1)
060: o.g = new PurityGraph(i1.g);
061: o.g.union(i2.g);
062: }
063:
064: protected void copy(Object source, Object dest) {
065: PurityGraphBox src = (PurityGraphBox) source;
066: PurityGraphBox dst = (PurityGraphBox) dest;
067: dst.g = new PurityGraph(src.g);
068: }
069:
070: protected void flowThrough(Object inValue, Object unit,
071: Object outValue) {
072: PurityGraphBox i = (PurityGraphBox) inValue;
073: PurityGraphBox o = (PurityGraphBox) outValue;
074: Stmt stmt = (Stmt) unit;
075:
076: o.g = new PurityGraph(i.g);
077:
078: // ********************
079: // BIG PATTERN MATCHING
080: // ********************
081:
082: // I throw much "match failure" Errors to ease debugging...
083: // => we could optimize the pattern matching a little bit
084:
085: //G.v().out.println(" | |- exec "+stmt);
086:
087: ///////////
088: // Calls //
089: ///////////
090: if (stmt.containsInvokeExpr()) {
091: inter.analyseCall(inValue, stmt, outValue);
092: }
093:
094: /////////////
095: // AssignStmt
096: /////////////
097:
098: else if (stmt instanceof AssignStmt) {
099: Value leftOp = ((AssignStmt) stmt).getLeftOp();
100: Value rightOp = ((AssignStmt) stmt).getRightOp();
101:
102: // v = ...
103: if (leftOp instanceof Local) {
104: Local left = (Local) leftOp;
105:
106: // remove optional cast
107: if (rightOp instanceof CastExpr)
108: rightOp = ((CastExpr) rightOp).getOp();
109:
110: // ignore primitive types
111: if (!(left.getType() instanceof RefLikeType)) {
112: }
113:
114: // v = v
115: else if (rightOp instanceof Local) {
116: Local right = (Local) rightOp;
117: o.g.assignLocalToLocal(right, left);
118: }
119:
120: // v = v[i]
121: else if (rightOp instanceof ArrayRef) {
122: Local right = (Local) ((ArrayRef) rightOp)
123: .getBase();
124: o.g.assignFieldToLocal(stmt, right, "[]", left);
125: }
126:
127: // v = v.f
128: else if (rightOp instanceof InstanceFieldRef) {
129: Local right = (Local) ((InstanceFieldRef) rightOp)
130: .getBase();
131: String field = ((InstanceFieldRef) rightOp)
132: .getField().getName();
133: o.g.assignFieldToLocal(stmt, right, field, left);
134: }
135:
136: // v = C.f
137: else if (rightOp instanceof StaticFieldRef) {
138: o.g.localIsUnknown(left);
139: }
140:
141: // v = cst
142: else if (rightOp instanceof Constant) {
143: // do nothing...
144: }
145:
146: // v = new / newarray / newmultiarray
147: else if (rightOp instanceof AnyNewExpr) {
148: o.g.assignNewToLocal(stmt, left);
149: }
150:
151: // v = binary or unary operator
152: else if (rightOp instanceof BinopExpr
153: || rightOp instanceof UnopExpr
154: || rightOp instanceof InstanceOfExpr) {
155: // do nothing...
156: }
157:
158: else
159: throw new Error(
160: "AssignStmt match failure (rightOp)" + stmt);
161: }
162:
163: // v[i] = ...
164: else if (leftOp instanceof ArrayRef) {
165: Local left = (Local) ((ArrayRef) leftOp).getBase();
166:
167: // v[i] = v
168: if (rightOp instanceof Local) {
169: Local right = (Local) rightOp;
170: if (right.getType() instanceof RefLikeType)
171: o.g.assignLocalToField(right, left, "[]");
172: else
173: o.g.mutateField(left, "[]");
174: }
175:
176: // v[i] = cst
177: else if (rightOp instanceof Constant)
178: o.g.mutateField(left, "[]");
179:
180: else
181: throw new Error(
182: "AssignStmt match failure (rightOp)" + stmt);
183: }
184:
185: // v.f = ...
186: else if (leftOp instanceof InstanceFieldRef) {
187: Local left = (Local) ((InstanceFieldRef) leftOp)
188: .getBase();
189: String field = ((InstanceFieldRef) leftOp).getField()
190: .getName();
191:
192: // v.f = v
193: if (rightOp instanceof Local) {
194: Local right = (Local) rightOp;
195: // ignore primitive types
196: if (right.getType() instanceof RefLikeType)
197: o.g.assignLocalToField(right, left, field);
198: else
199: o.g.mutateField(left, field);
200: }
201:
202: // v.f = cst
203: else if (rightOp instanceof Constant)
204: o.g.mutateField(left, field);
205:
206: else
207: throw new Error(
208: "AssignStmt match failure (rightOp) "
209: + stmt);
210: }
211:
212: // C.f = ...
213: else if (leftOp instanceof StaticFieldRef) {
214: String field = ((StaticFieldRef) leftOp).getField()
215: .getName();
216:
217: // C.f = v
218: if (rightOp instanceof Local) {
219: Local right = (Local) rightOp;
220: if (right.getType() instanceof RefLikeType)
221: o.g.assignLocalToStaticField(right, field);
222: else
223: o.g.mutateStaticField(field);
224: }
225:
226: // C.f = cst
227: else if (rightOp instanceof Constant)
228: o.g.mutateStaticField(field);
229:
230: else
231: throw new Error(
232: "AssignStmt match failure (rightOp) "
233: + stmt);
234: }
235:
236: else
237: throw new Error("AssignStmt match failure (leftOp) "
238: + stmt);
239:
240: }
241:
242: ///////////////
243: // IdentityStmt
244: ///////////////
245:
246: else if (stmt instanceof IdentityStmt) {
247: Local left = (Local) ((IdentityStmt) stmt).getLeftOp();
248: Value rightOp = ((IdentityStmt) stmt).getRightOp();
249:
250: if (rightOp instanceof ThisRef) {
251: o.g.assignThisToLocal(left);
252: }
253:
254: else if (rightOp instanceof ParameterRef) {
255: ParameterRef p = (ParameterRef) rightOp;
256: // ignore primitive types
257: if (p.getType() instanceof RefLikeType)
258: o.g.assignParamToLocal(p.getIndex(), left);
259: }
260:
261: else if (rightOp instanceof CaughtExceptionRef) {
262: // local = exception
263: o.g.localIsUnknown(left);
264: }
265:
266: else
267: throw new Error("IdentityStmt match failure (rightOp) "
268: + stmt);
269:
270: }
271:
272: ////////////
273: // ThrowStmt
274: ////////////
275:
276: else if (stmt instanceof ThrowStmt) {
277: Value op = ((ThrowStmt) stmt).getOp();
278:
279: if (op instanceof Local) {
280: Local v = (Local) op;
281: o.g.localEscapes(v);
282: }
283:
284: else if (op instanceof Constant) {
285: // do nothing...
286: }
287:
288: else
289: throw new Error("ThrowStmt match failure " + stmt);
290: }
291:
292: /////////////
293: // ReturnStmt
294: /////////////
295:
296: else if (stmt instanceof ReturnVoidStmt) {
297: // do nothing...
298: }
299:
300: else if (stmt instanceof ReturnStmt) {
301: Value v = ((ReturnStmt) stmt).getOp();
302:
303: if (v instanceof Local) {
304: // ignore primitive types
305: if (v.getType() instanceof RefLikeType)
306: o.g.returnLocal((Local) v);
307: }
308:
309: else if (v instanceof Constant) {
310: // do nothing...
311: }
312:
313: else
314: throw new Error("ReturnStmt match failure " + stmt);
315:
316: }
317:
318: //////////
319: // ignored
320: //////////
321:
322: else if (stmt instanceof IfStmt || stmt instanceof GotoStmt
323: || stmt instanceof LookupSwitchStmt
324: || stmt instanceof TableSwitchStmt
325: || stmt instanceof MonitorStmt
326: || stmt instanceof BreakpointStmt
327: || stmt instanceof NopStmt) {
328: // do nothing...
329: }
330:
331: else
332: throw new Error("Stmt match faliure " + stmt);
333:
334: //o.g.updateStat();
335: }
336:
337: /**
338: * Draw the result of the intra-procedural analysis as one big dot file,
339: * named className.methodName.dot, containing one purity graph for each
340: * statment in the method.
341: */
342: public void drawAsOneDot(String prefix, String name) {
343: DotGraph dot = new DotGraph(name);
344: dot.setGraphLabel(name);
345: dot.setGraphAttribute("compound", "true");
346: dot.setGraphAttribute("rankdir", "LR");
347: Map<Unit, Integer> node = new HashMap<Unit, Integer>();
348: int id = 0;
349: Iterator it = graph.iterator();
350: while (it.hasNext()) {
351: Unit stmt = (Unit) it.next();
352: PurityGraphBox ref = (PurityGraphBox) getFlowAfter(stmt);
353: DotGraph sub = dot.createSubGraph("cluster" + id);
354: DotGraphNode label = sub.drawNode("head" + id);
355: String lbl = stmt.toString();
356: if (lbl.startsWith("lookupswitch"))
357: lbl = "lookupswitch...";
358: if (lbl.startsWith("tableswitch"))
359: lbl = "tableswitch...";
360: sub.setGraphLabel(" ");
361: label.setLabel(lbl);
362: label.setAttribute("fontsize", "18");
363: label.setShape("box");
364: ref.g.fillDotGraph("X" + id, sub);
365: node.put(stmt, new Integer(id));
366: id++;
367: }
368: it = graph.iterator();
369: while (it.hasNext()) {
370: Object src = it.next();
371: Iterator itt = graph.getSuccsOf(src).iterator();
372: while (itt.hasNext()) {
373: Object dst = itt.next();
374: DotGraphEdge edge = dot.drawEdge(
375: "head" + node.get(src), "head" + node.get(dst));
376: edge.setAttribute("ltail", "cluster" + node.get(src));
377: edge.setAttribute("lhead", "cluster" + node.get(dst));
378: }
379: }
380:
381: File f = new File(SourceLocator.v().getOutputDir(), prefix
382: + name + DotGraph.DOT_EXTENSION);
383: dot.plot(f.getPath());
384: }
385:
386: /**
387: * Put into dst the purity graph obtained by merging all purity graphs at
388: * the method return.
389: * It is a valid summary that can be used in methodCall if you do
390: * interprocedural analysis.
391: *
392: */
393: public void copyResult(Object dst) {
394: PurityGraph r = new PurityGraph();
395: Iterator it = graph.getTails().iterator();
396: while (it.hasNext()) {
397: Stmt stmt = (Stmt) it.next();
398: PurityGraphBox ref = (PurityGraphBox) getFlowAfter(stmt);
399: r.union(ref.g);
400: }
401: r.removeLocals();
402: //r.simplifyLoad();
403: //r.simplifyInside();
404: //r.updateStat();
405: ((PurityGraphBox) dst).g = r;
406: }
407:
408: /**
409: * Perform purity analysis on the Jimple unit graph g, as part of
410: * a larger interprocedural analysis.
411: * Once constructed, you may call copyResult and drawAsOneDot to query
412: * the analysis result.
413: */
414: PurityIntraproceduralAnalysis(UnitGraph g,
415: AbstractInterproceduralAnalysis inter) {
416: super(g);
417: this.inter = inter;
418: doAnalysis();
419: }
420: }
|