View Javadoc

1   // PAQuery.java, created Oct 21, 2003 12:56:45 AM by livshits
2   // Copyright (C) 2003 Vladimir Livshits
3   // Licensed under the terms of the GNU LGPL; see COPYING for details.
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              //if(getBuilder().skipMethod(m)) return;
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              // get formal arguments for the method
66              BDD methodBDD = _r.M.ithVar(_paResults.getMethodIndex(m));
67              BDD params = _r.formal.relprod(methodBDD, _r.Mset);
68              //System.out.println("params: " + params.toStringWithDomains());
69              TypedBDD contexts = (TypedBDD)params.relprod(_r.vP, 
70                  _r.V1.set().unionWith(_r.H1cset).unionWith(_r.H1.set()).unionWith(_r.Z.set()) );
71              //System.out.println("contexts: \n" + paResults.toString(contexts, -1));
72              //TypedBDD pointsTo = (TypedBDD)params.relprod(r.vP, r.V1cH1cset);
73              //System.out.println("pointsTo: \n" + paResults.toString(pointsTo, -1));
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              //System.out.println("context #" + i + ": " + context.toStringWithDomains());
86                  
87              Assert._assert(_r.vPfilter != null);
88              TypedBDD t = (TypedBDD)_r.vP.and(_r.vPfilter.id());   // restrict by the type filter
89              TypedBDD t2 = (TypedBDD)params.relprod(t, _r.V1.set());
90              t.free();
91              t = t2;
92                  
93              //TypedBDD t = (TypedBDD)params.relprod(r.vP, r.V1.set());
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              //System.out.println(t.satCount() + ", " + pointsTo.satCount());
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() /*_paResults.toString(param, -1) */ + " ");
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             // pointsTo is what this particular parameter may point to
180             BDD pointsTo = _r.vP.restrict(param);                               // H1xH1cxF
181             BDD methodBDD = _r.M.ithVar(_paResults.getMethodIndex(m));          // M
182             
183             BDD mods = null;
184             if (!recursive) {               
185                 // these are the modified heap locations
186                 mods = _r.S.relprod(param, _r.V1set);                           // H1xH1cxFxV2xV1cxV2c
187             } else {
188                 BDD method_plus_context0 = methodBDD.andWith(_r.V1c[0].ithVar(0));
189                 BDD reachableVars = _paResults.getReachableVars(method_plus_context0); // V1xV1c
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);             // V1xV1c x V1xV1cxFxV2xV2c = V1xV1cxF
195                 mods = stores.relprod(_r.vP, _r.V1set);                         // V1xV1cxF x V1xV1cxH1xH1c = H1xH1cxF
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                 /*  // doesn't compile.
260                 if(IPSSABuilder.isLoad(quad)) {
261                     Set refs = this.getBuilder().getPAResults().ref(m, iter.getCurrentBasicBlock(), quad);
262                     System.out.println("Quad: " + quad + refs);
263                     _loads++;
264                     _refs += refs.size();
265                 }else
266                 if(IPSSABuilder.isStore(quad)) {
267                     Set mods = this.getBuilder().getPAResults().mod(m, iter.getCurrentBasicBlock(), quad);
268                     System.out.println("Quad: " + quad + mods);
269                     _stores++;
270                     _mods += mods.size();
271                 }
272                 */
273             }                                               
274         }    
275     }
276 }