KickJava   Java API By Example, From Geeks To Geeks.

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


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.File JavaDoc;
31 import soot.*;
32 import soot.util.*;
33 import soot.util.dot.*;
34 import soot.jimple.*;
35 import soot.toolkits.scalar.*;
36 import soot.toolkits.graph.*;
37
38 /**
39  * Intra-procedural purity-graph analysis.
40  *
41  * You must pass an AbstractInterproceduralAnalysis object so that the
42  * intraprocedural part can resolve the effect of method calls.
43  * This manipulates PurityGraphBox.
44  */

45 public class PurityIntraproceduralAnalysis extends ForwardFlowAnalysis
46 {
47
48     AbstractInterproceduralAnalysis inter;
49
50     protected Object JavaDoc newInitialFlow()
51     { return new PurityGraphBox(); }
52
53     protected Object JavaDoc entryInitialFlow()
54     { return new PurityGraphBox(); }
55
56     protected void merge(Object JavaDoc in1, Object JavaDoc in2, Object JavaDoc out)
57     {
58     PurityGraphBox i1 = (PurityGraphBox)in1;
59     PurityGraphBox i2 = (PurityGraphBox)in2;
60     PurityGraphBox o = (PurityGraphBox)out;
61     if (out!=i1) o.g = new PurityGraph(i1.g);
62     o.g.union(i2.g);
63     }
64
65     protected void copy(Object JavaDoc source, Object JavaDoc dest)
66     {
67     PurityGraphBox src = (PurityGraphBox)source;
68     PurityGraphBox dst = (PurityGraphBox)dest;
69     dst.g = new PurityGraph(src.g);
70     }
71
72
73     /**
74      * Returns the local variable that get the result of the method call,
75      * or null if there is no return value or it is a primitive type.
76      */

77     private Local callExtractReturn(Stmt stmt)
78     {
79     if (!(stmt instanceof AssignStmt)) return null;
80     Local v = (Local)((AssignStmt)stmt).getLeftOp();
81     if (v.getType() instanceof RefLikeType) return v;
82     return null;
83     }
84
85     /**
86      * Returns the local variable containing the object on which the
87      * method is called, or null for a static method call.
88      */

89     private Local callExtractObj(Stmt stmt)
90     {
91     InvokeExpr e;
92     if (stmt instanceof InvokeStmt) e = ((InvokeStmt)stmt).getInvokeExpr();
93     else e = (InvokeExpr)((AssignStmt)stmt).getRightOp();
94     if (e instanceof StaticInvokeExpr) return null;
95     return (Local)((InstanceInvokeExpr)e).getBase();
96     }
97
98     /**
99      * Returns the List of Value corresponding the the arguments of
100      * the method call.
101      */

102     private List callExtractArgs(Stmt stmt)
103     {
104     InvokeExpr e;
105     if (stmt instanceof InvokeStmt) e = ((InvokeStmt)stmt).getInvokeExpr();
106     else e = (InvokeExpr)((AssignStmt)stmt).getRightOp();
107     return e.getArgs();
108     }
109
110
111     protected void flowThrough(Object JavaDoc inValue, Object JavaDoc unit, Object JavaDoc outValue)
112     {
113     PurityGraphBox i = (PurityGraphBox)inValue;
114     PurityGraphBox o = (PurityGraphBox)outValue;
115     Stmt stmt = (Stmt)unit;
116
117     o.g = new PurityGraph(i.g);
118     
119     // ********************
120
// BIG PATTERN MATCHING
121
// ********************
122

123     // I throw much "match failure" Errors to ease debugging...
124
// => we could optimize the pattern matching a little bit
125

126     //G.v().out.println(" | |- exec "+stmt);
127

128
129     ///////////
130
// Calls //
131
///////////
132
if (stmt.containsInvokeExpr()) {
133         inter.analyseCall(inValue, stmt, outValue);
134     }
135
136     /////////////
137
// AssignStmt
138
/////////////
139

140     else if (stmt instanceof AssignStmt) {
141         Value leftOp = ((AssignStmt)stmt).getLeftOp();
142         Value rightOp = ((AssignStmt)stmt).getRightOp();
143
144         // v = ...
145
if (leftOp instanceof Local) {
146         Local left = (Local)leftOp;
147
148         // remove optional cast
149
if (rightOp instanceof CastExpr)
150             rightOp = ((CastExpr)rightOp).getOp();
151
152         // ignore primitive types
153
if (!(left.getType() instanceof RefLikeType)) {
154         }
155
156         // v = v
157
else if (rightOp instanceof Local) {
158             Local right = (Local) rightOp;
159             o.g.assignLocalToLocal(right, left);
160         }
161
162         // v = v[i]
163
else if (rightOp instanceof ArrayRef) {
164             Local right = (Local) ((ArrayRef)rightOp).getBase();
165             o.g.assignFieldToLocal(stmt, right, "[]", left);
166         }
167
168         // v = v.f
169
else if (rightOp instanceof InstanceFieldRef) {
170             Local right =
171             (Local) ((InstanceFieldRef)rightOp).getBase();
172             String JavaDoc field =
173             ((InstanceFieldRef)rightOp).getField().getName();
174             o.g.assignFieldToLocal(stmt, right, field, left);
175         }
176
177         // v = C.f
178
else if (rightOp instanceof StaticFieldRef) {
179             o.g.localIsUnknown(left);
180         }
181
182         // v = cst
183
else if (rightOp instanceof Constant) {
184             // do nothing...
185
}
186
187
188         // v = new / newarray / newmultiarray
189
else if (rightOp instanceof AnyNewExpr) {
190             o.g.assignNewToLocal(stmt, left);
191         }
192
193         // v = binary or unary operator
194
else if (rightOp instanceof BinopExpr ||
195              rightOp instanceof UnopExpr ||
196              rightOp instanceof InstanceOfExpr) {
197             // do nothing...
198
}
199
200         else throw new Error JavaDoc("AssignStmt match failure (rightOp)"+stmt);
201         }
202
203         // v[i] = ...
204
else if (leftOp instanceof ArrayRef) {
205         Local left = (Local) ((ArrayRef)leftOp).getBase();
206
207         // v[i] = v
208
if (rightOp instanceof Local) {
209             Local right = (Local)rightOp;
210             if (right.getType() instanceof RefLikeType)
211             o.g.assignLocalToField(right, left, "[]");
212             else
213             o.g.mutateField(left, "[]");
214         }
215
216         // v[i] = cst
217
else if (rightOp instanceof Constant)
218             o.g.mutateField(left, "[]");
219         
220         else throw new Error JavaDoc("AssignStmt match failure (rightOp)"+stmt);
221         }
222
223         // v.f = ...
224
else if (leftOp instanceof InstanceFieldRef) {
225         Local left = (Local) ((InstanceFieldRef)leftOp).getBase();
226         String JavaDoc field = ((InstanceFieldRef)leftOp).getField().getName();
227
228         // v.f = v
229
if (rightOp instanceof Local) {
230             Local right = (Local)rightOp;
231             // ignore primitive types
232
if (right.getType() instanceof RefLikeType)
233             o.g.assignLocalToField(right, left, field);
234             else
235             o.g.mutateField(left, field);
236         }
237
238         // v.f = cst
239
else if (rightOp instanceof Constant)
240             o.g.mutateField(left, field);
241         
242         else throw new Error JavaDoc("AssignStmt match failure (rightOp) "+stmt);
243         }
244
245         // C.f = ...
246
else if (leftOp instanceof StaticFieldRef) {
247         String JavaDoc field = ((StaticFieldRef)leftOp).getField().getName();
248         
249         // C.f = v
250
if (rightOp instanceof Local) {
251             Local right = (Local)rightOp;
252             if (right.getType() instanceof RefLikeType)
253             o.g.assignLocalToStaticField(right, field);
254             else
255             o.g.mutateStaticField(field);
256         }
257
258         // C.f = cst
259
else if (rightOp instanceof Constant)
260             o.g.mutateStaticField(field);
261
262         else throw new Error JavaDoc("AssignStmt match failure (rightOp) "+stmt);
263         }
264
265         else throw new Error JavaDoc("AssignStmt match failure (leftOp) "+stmt);
266
267     }
268
269
270     ///////////////
271
// IdentityStmt
272
///////////////
273

274     else if (stmt instanceof IdentityStmt) {
275         Local left = (Local)((IdentityStmt)stmt).getLeftOp();
276         Value rightOp = ((IdentityStmt)stmt).getRightOp();
277         
278         if (rightOp instanceof ThisRef) {
279         o.g.assignThisToLocal(left);
280         }
281
282         else if (rightOp instanceof ParameterRef) {
283         ParameterRef p = (ParameterRef)rightOp;
284         // ignore primitive types
285
if (p.getType() instanceof RefLikeType)
286             o.g.assignParamToLocal(p.getIndex(),left);
287         }
288
289         else if (rightOp instanceof CaughtExceptionRef) {
290         // local = exception
291
o.g.localIsUnknown(left);
292         }
293
294         else throw new Error JavaDoc("IdentityStmt match failure (rightOp) "+stmt);
295
296     }
297
298
299     ////////////
300
// ThrowStmt
301
////////////
302

303     else if (stmt instanceof ThrowStmt) {
304         Value op = ((ThrowStmt)stmt).getOp();
305
306         if (op instanceof Local) {
307         Local v = (Local)op;
308         o.g.localEscapes(v);
309         }
310
311         else if (op instanceof Constant) {
312         // do nothing...
313
}
314
315         else throw new Error JavaDoc("ThrowStmt match failure "+stmt);
316     }
317
318
319     /////////////
320
// ReturnStmt
321
/////////////
322

323     else if (stmt instanceof ReturnVoidStmt) {
324         // do nothing...
325
}
326
327     else if (stmt instanceof ReturnStmt) {
328         Value v = ((ReturnStmt)stmt).getOp();
329
330         if (v instanceof Local) {
331         // ignore primitive types
332
if (v.getType() instanceof RefLikeType)
333             o.g.returnLocal((Local)v);
334         }
335
336         else if (v instanceof Constant) {
337         // do nothing...
338
}
339
340         else throw new Error JavaDoc("ReturnStmt match failure "+stmt);
341
342     }
343
344
345     //////////
346
// ignored
347
//////////
348

349     else if (stmt instanceof IfStmt ||
350          stmt instanceof GotoStmt ||
351          stmt instanceof LookupSwitchStmt ||
352          stmt instanceof TableSwitchStmt ||
353          stmt instanceof MonitorStmt ||
354          stmt instanceof BreakpointStmt ||
355          stmt instanceof NopStmt) {
356         // do nothing...
357
}
358          
359
360     else throw new Error JavaDoc("Stmt match faliure "+stmt);
361
362     //o.g.updateStat();
363
}
364
365
366     /**
367      * Draw the result of the intra-procedural analysis as one big dot file,
368      * named className.methodName.dot, containing one purity graph for each
369      * statment in the method.
370      */

371     public void drawAsOneDot(String JavaDoc prefix, String JavaDoc name)
372     {
373     DotGraph dot = new DotGraph(name);
374     dot.setGraphLabel(name);
375     dot.setGraphAttribute("compound","true");
376     dot.setGraphAttribute("rankdir","LR");
377     Map node = new HashMap();
378     int id = 0;
379     Iterator it = graph.iterator();
380     while (it.hasNext()) {
381         Unit stmt = (Unit)it.next();
382         PurityGraphBox ref = (PurityGraphBox) getFlowAfter(stmt);
383         DotGraph sub = dot.createSubGraph("cluster"+id);
384         DotGraphNode label = sub.drawNode("head"+id);
385         String JavaDoc lbl = stmt.toString();
386         if (lbl.startsWith("lookupswitch")) lbl = "lookupswitch...";
387         if (lbl.startsWith("tableswitch")) lbl = "tableswitch...";
388         sub.setGraphLabel(" ");
389         label.setLabel(lbl);
390         label.setAttribute("fontsize","18");
391         label.setShape("box");
392         ref.g.fillDotGraph("X"+id,sub);
393         node.put(stmt,new Integer JavaDoc(id));
394         id++;
395     }
396     it = graph.iterator();
397     while (it.hasNext()) {
398         Object JavaDoc src = it.next();
399         Iterator itt = graph.getSuccsOf(src).iterator();
400         while (itt.hasNext()) {
401         Object JavaDoc dst = itt.next();
402         DotGraphEdge edge =
403             dot.drawEdge("head"+node.get(src),"head"+node.get(dst));
404         edge.setAttribute("ltail", "cluster"+node.get(src));
405         edge.setAttribute("lhead", "cluster"+node.get(dst));
406         }
407     }
408
409     File JavaDoc f = new File JavaDoc (SourceLocator.v().getOutputDir(),
410                prefix+name+DotGraph.DOT_EXTENSION);
411     dot.plot(f.getPath());
412     }
413
414
415     /**
416      * Put into dst the purity graph obtained by merging all purity graphs at
417      * the method return.
418      * It is a valid summary that can be used in methodCall if you do
419      * interprocedural analysis.
420      *
421      */

422     public void copyResult(Object JavaDoc dst)
423     {
424     PurityGraph r = new PurityGraph();
425     Iterator it = graph.getTails().iterator();
426     while (it.hasNext()) {
427         Stmt stmt = (Stmt)it.next();
428         PurityGraphBox ref = (PurityGraphBox) getFlowAfter(stmt);
429         r.union(ref.g);
430     }
431     r.removeLocals();
432     //r.simplifyLoad();
433
//r.simplifyInside();
434
//r.updateStat();
435
((PurityGraphBox)dst).g = r;
436     }
437
438     /**
439      * Perform purity analysis on the Jimple unit graph g, as part of
440      * a larger interprocedural analysis.
441      * Once constructed, you may call copyResult and drawAsOneDot to query
442      * the analysis result.
443      */

444     PurityIntraproceduralAnalysis(UnitGraph g,
445                   AbstractInterproceduralAnalysis inter)
446     {
447     super(g);
448     this.inter = inter;
449     doAnalysis();
450     }
451 }
452
453
454
Popular Tags