1
2
3
4 package joeq.Compiler.Analysis.IPA;
5
6 import java.util.Iterator;
7 import java.io.PrintStream;
8 import joeq.Class.jq_Method;
9 import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary;
10 import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary.ParamNode;
11 import joeq.Compiler.Analysis.IPSSA.IPSSABuilder;
12 import joeq.Compiler.Quad.CodeCache;
13 import joeq.Compiler.Quad.Quad;
14 import joeq.Compiler.Quad.QuadIterator;
15 import jwutil.util.Assert;
16 import net.sf.javabdd.BDD;
17 import net.sf.javabdd.TypedBDDFactory.TypedBDD;
18
19 /***
20 * A query on top of PAResults. Will probably need to move nested classes
21 * to other places later.
22 * @see PAQuery.ParamAliasFinder
23 * @see PAQuery.ConstParameterFinder
24 *
25 * @author Vladimir Livshits
26 * @version $Id: PAQuery.java 2470 2006-07-17 05:20:48Z joewhaley $
27 * */
28 public class PAQuery {
29 /***
30 * Finds parameter aliases under different constexts.
31 * */
32 public static class ParamAliasFinder extends IPSSABuilder.Application {
33 PAResults _paResults = null;
34 PA _r = null;
35
36 public ParamAliasFinder() {
37 super(null, null, null);
38 }
39 public ParamAliasFinder(IPSSABuilder builder, String name, String[] args) {
40 super(builder, name, args);
41 }
42
43 protected void parseParams(String[] args) {}
44
45 class ModifiableBoolean {
46 boolean _value;
47
48 ModifiableBoolean(boolean value){
49 this._value = value;
50 }
51 boolean getValue() {return _value;}
52 void setValue(boolean value) {this._value = value;}
53 }
54
55 void visitMethod(jq_Method m){
56
57
58 MethodSummary ms = MethodSummary.getSummary(m);
59 if(ms == null) return;
60 if(ms.getNumOfParams() < 2) return;
61
62 _paResults = getBuilder().getPAResults();
63 _r = _paResults.getPAResults();
64
65
66 BDD methodBDD = _r.M.ithVar(_paResults.getMethodIndex(m));
67 BDD params = _r.formal.relprod(methodBDD, _r.Mset);
68
69 TypedBDD contexts = (TypedBDD)params.relprod(_r.vP,
70 _r.V1.set().unionWith(_r.H1cset).unionWith(_r.H1.set()).unionWith(_r.Z.set()) );
71
72
73
74 int i = 0;
75 ModifiableBoolean printedInfo = new ModifiableBoolean(false);
76 long contextSize = (long)contexts.satCount(_r.V1cset);
77 for(Iterator contextIter = contexts.iterator(); contextIter.hasNext(); i++) {
78 TypedBDD context = (TypedBDD)contextIter.next();
79
80 processContext(m, ms, params, context, contextSize, printedInfo, i);
81 }
82 }
83
84 void processContext(jq_Method m, MethodSummary ms, BDD params, TypedBDD context, long contextSize, ModifiableBoolean printedInfo, int i){
85
86
87 Assert._assert(_r.vPfilter != null);
88 TypedBDD t = (TypedBDD)_r.vP.and(_r.vPfilter.id());
89 TypedBDD t2 = (TypedBDD)params.relprod(t, _r.V1.set());
90 t.free();
91 t = t2;
92
93
94 TypedBDD pointsTo = (TypedBDD)context.relprod(t, _r.V1cset.union(_r.H1cset));
95 t.free();
96
97 t = (TypedBDD)pointsTo.exist(_r.Z.set());
98
99 int pointsToSize = (int)pointsTo.satCount(_r.H1.set().union(_r.Zset));
100 int projSize = (int)t.satCount( _r.H1.set() );
101 if(projSize < pointsToSize) {
102 if(!printedInfo.getValue()) {
103 printMethodInfo(m, ms);
104 printedInfo.setValue(true);
105 }
106 ProgramLocation loc = new ProgramLocation.BCProgramLocation(m, 0);
107 System.out.println("\tPotential aliasing in context #" + i + " calling " + m.toString() + " at " +
108 loc.getSourceFile() + ":" + loc.getLineNumber());
109 if(contextSize > 5) {
110 System.out.println("\t\t(A total of " + contextSize + " contexts) \n");
111 return;
112 }
113 }
114 t.free();
115 }
116
117 void printMethodInfo(jq_Method m, MethodSummary ms) {
118 System.out.println("Processing method " + m + ":\t[" + ms.getNumOfParams() + "]");
119 for(int i = 0; i < ms.getNumOfParams(); i++) {
120 ParamNode paramNode = ms.getParamNode(i);
121 System.out.print("\t\t");
122 System.out.println(paramNode == null ? "<null>" : paramNode.toString_long());
123 }
124 System.out.print("\n");
125 }
126 public void run() {
127 for(Iterator iter = getBuilder().getCallGraph().getAllMethods().iterator(); iter.hasNext();) {
128 jq_Method m = (jq_Method)iter.next();
129
130 visitMethod(m);
131 }
132 }
133 }
134
135 /***
136 * Application for finding and printing const-parameters.
137 * */
138 public static class ConstParameterFinder extends IPSSABuilder.Application {
139 static final String NON_CONST_QUALIFIER = "non_const ";
140 static final String CONST_QUALIFIER = "const ";
141 PAResults _paResults;
142 PA _r;
143
144 public ConstParameterFinder() {
145 this(null, "ConstParameterFinder", null);
146 }
147 public ConstParameterFinder(IPSSABuilder builder, String name, String[] args) {
148 super(builder, name, args);
149 }
150
151 void visitMethod(jq_Method m){
152 if(getBuilder().skipMethod(m)) return;
153
154 MethodSummary ms = MethodSummary.getSummary(m);
155 if(ms == null) return;
156
157 _paResults = getBuilder().getPAResults();
158 _r = _paResults.getPAResults();
159
160 TypedBDD params = (TypedBDD)_r.formal.relprod(_r.M.ithVar(_paResults.getMethodIndex(m)), _r.Mset);
161
162 System.out.print(m.toString() + "( ");
163 for(Iterator paramIter = params.iterator(); paramIter.hasNext();) {
164 TypedBDD param = (TypedBDD)((TypedBDD)paramIter.next()).exist(_r.Zset);
165
166 boolean isConst = isConst(param, m, true);
167
168 System.out.print(isConst ? CONST_QUALIFIER : NON_CONST_QUALIFIER);
169 System.out.print(param.toStringWithDomains()
170 }
171 System.out.print(") \n");
172 }
173
174 /***
175 * Check whether parameter param : V1 can of method m can be declared a const parameter.
176 * recursive determines whether we consider callees to look for modifications.
177 * */
178 public boolean isConst(TypedBDD param, jq_Method m, boolean recursive) {
179
180 BDD pointsTo = _r.vP.restrict(param);
181 BDD methodBDD = _r.M.ithVar(_paResults.getMethodIndex(m));
182
183 BDD mods = null;
184 if (!recursive) {
185
186 mods = _r.S.relprod(param, _r.V1set);
187 } else {
188 BDD method_plus_context0 = methodBDD.andWith(_r.V1c[0].ithVar(0));
189 BDD reachableVars = _paResults.getReachableVars(method_plus_context0);
190 reachableVars = reachableVars.exist(_r.V1cset);
191 reachableVars.or(param);
192 System.err.println("reachableVars: " + _paResults.toString((TypedBDD)reachableVars, -1));
193
194 BDD stores = _r.S.relprod(reachableVars, _r.V2set);
195 mods = stores.relprod(_r.vP, _r.V1set);
196 }
197
198 boolean result = mods.isZero();
199 mods.free();
200
201 return result;
202 }
203
204 protected void parseParams(String[] args) {}
205
206 public void run() {
207 for(Iterator iter = getBuilder().getCallGraph().getAllMethods().iterator(); iter.hasNext();) {
208 jq_Method m = (jq_Method)iter.next();
209
210 visitMethod(m);
211 }
212 }
213 }
214
215 /***
216 * Produces statistics on how many locations are references by a given load
217 * or store within a given context.
218 * */
219 public static class HeapReferenceStat extends IPSSABuilder.Application {
220 private int _stores = 0;
221 private int _loads = 0;
222 private int _mods = 0;
223 private int _refs = 0;
224
225 public HeapReferenceStat() {
226 super(null, null, null);
227 }
228
229 protected void parseParams(String[] args) {}
230
231 public void run() {
232 for(Iterator iter = getBuilder().getCallGraph().getAllMethods().iterator(); iter.hasNext();) {
233 jq_Method m = (jq_Method)iter.next();
234
235 visitMethod(m);
236 }
237
238 printStat(System.out);
239 }
240
241 void printStat(PrintStream out) {
242 out.println("Statistics:");
243 out.println("\tLoads:\t" + _loads);
244 out.println("\tStores:\t" + _stores);
245
246 out.println("\tAvg mod:\t" + _mods/_stores);
247 out.println("\tAvg ref:\t" + _refs/_loads);
248 }
249
250 private void visitMethod(jq_Method m) {
251 if(getBuilder().skipMethod(m)) return;
252
253 MethodSummary ms = MethodSummary.getSummary(m);
254 if(ms == null) return;
255
256 for(QuadIterator iter = new QuadIterator(CodeCache.getCode(m)); iter.hasNext(); ) {
257 Quad quad = iter.nextQuad();
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273 }
274 }
275 }
276 }