View Javadoc

1   package joeq.Compiler.Analysis.IPSSA.Apps;
2   
3   import java.util.Arrays;
4   import java.util.Collection;
5   import java.util.Collections;
6   import java.util.HashMap;
7   import java.util.Iterator;
8   import java.util.LinkedList;
9   import java.util.Map;
10  import java.io.BufferedReader;
11  import java.io.FileReader;
12  import java.io.IOException;
13  import joeq.Class.PrimordialClassLoader;
14  import joeq.Class.jq_Class;
15  import joeq.Class.jq_InstanceMethod;
16  import joeq.Class.jq_Method;
17  import joeq.Class.jq_Type;
18  import joeq.Compiler.Quad.BasicBlock;
19  import joeq.Compiler.Quad.CodeCache;
20  import joeq.Compiler.Quad.ControlFlowGraph;
21  import joeq.Compiler.Quad.Operand;
22  import joeq.Compiler.Quad.Operator;
23  import joeq.Compiler.Quad.Quad;
24  import joeq.Compiler.Quad.RegisterFactory;
25  import joeq.Main.HostedVM;
26  import joeq.Util.Templates.List;
27  import joeq.Util.Templates.ListIterator;
28  import jwutil.collections.AppendIterator;
29  import jwutil.collections.HashWorklist;
30  import jwutil.collections.Worklist;
31  import jwutil.util.Assert;
32  
33  public class FindOwnership {
34      static class SimpleOwnershipFinder implements Runnable {
35          private Collection _classes;
36          //private CallGraph _cg;        
37          private Map procValue = new HashMap();
38          
39          private boolean _verbose = false;
40          
41          public SimpleOwnershipFinder(Iterator classIter){
42              _classes = new LinkedList();
43              Collection roots = new LinkedList();
44              
45              while(classIter.hasNext()) {
46                  jq_Class c = (jq_Class) jq_Type.parseType((String)classIter.next());
47                  c.load();
48                  _classes.add(c);
49                  roots.addAll(Arrays.asList(c.getDeclaredStaticMethods()));
50              }
51              
52              /* 
53               _cg = new RootedCHACallGraph();
54              _cg.setRoots(roots);
55              */
56          }
57          
58          public static void main(String[] args) {
59              HostedVM.initialize();
60              CodeCache.AlwaysMap = true;
61              ///initPredefinedClasses();
62              //ClassAndMethod.initializeClasses();
63              
64              Iterator i = null;
65              for (int x=0; x<args.length; ++x) {
66                  if (args[x].equals("-file")) {
67                      try {
68                          BufferedReader br = new BufferedReader(new FileReader(args[++x]));
69                          LinkedList list = new LinkedList();
70                          for (;;) {
71                              String s = br.readLine();
72                              if (s == null) break;
73                              if (s.length() == 0) continue;
74                              if (s.startsWith("%")) continue;
75                              if (s.startsWith("#")) continue;
76                              list.add(s);
77                          }
78                          i = new AppendIterator(list.iterator(), i);
79                      }catch(IOException e) {
80                          e.printStackTrace();
81                          System.exit(2);
82                      }
83                      
84                  } else
85                      if (args[x].endsWith("*")) {
86                          i = new AppendIterator(PrimordialClassLoader.loader.listPackage(args[x].substring(0, args[x].length()-1)), i);
87                      } else 
88                          if(args[x].charAt(0) == '-'){
89                              System.exit(2);                    
90                          }else {
91                              String classname = args[x];
92                              i = new AppendIterator(Collections.singleton(classname).iterator(), i);
93                          }
94              }
95  
96              SimpleOwnershipFinder finder = new SimpleOwnershipFinder(i);
97              finder.run();
98          }
99          
100         public void run() {
101             for(Iterator iter = _classes.iterator(); iter.hasNext();) {
102                 jq_Class c = (jq_Class)iter.next();
103                                 
104                 processClass(c);
105             }
106         }
107 
108         private void processClass(jq_Class c) {
109             System.out.println("Processing class " + c);
110             jq_InstanceMethod[] methods = c.getDeclaredInstanceMethods();
111             for(int i = 0; i < methods.length; i++) {
112                 jq_InstanceMethod m = methods[i];
113                 
114                 if(m.isInitializer()) {
115                     computeInitializations(m);                    
116                 }
117             }
118         }
119         
120         void computeInitializations(jq_Method m){
121             if(_verbose) System.out.println("Processing constructor " + m);
122             
123             ControlFlowGraph cfg = CodeCache.getCode(m);
124             // Collection/*jq_Method*/ targets = _cg.getCallees(m);
125             Worklist/*BasicBlock*/ worklist = new HashWorklist();
126             worklist.push(cfg.entry());
127             Map valueAtEnd = new HashMap();
128             // initialize the parameters as unowned
129             OwnershipValue initValue = getInitValue(m);
130 
131             worklist.push(cfg.entry());
132             while(!worklist.isEmpty()) {
133                 BasicBlock b = (BasicBlock)worklist.pull();
134                 OwnershipValue predValue = null;
135                 if(b.getNumberOfPredecessors() > 0) {
136                     // merge node -- merge the values at predecessors
137                     List.BasicBlock l = b.getPredecessors();
138                     for(joeq.Util.Templates.ListIterator.BasicBlock i = l.basicBlockIterator(); i.hasNext();) {
139                         BasicBlock pred = i.nextBasicBlock();
140                         OwnershipValue v_pred = (OwnershipValue)valueAtEnd.get(pred);
141                         if(v_pred != null) {
142                             if(predValue == null) {
143                                 predValue = new OwnershipValue(v_pred);
144                                 //changed = true;
145                             }else {
146                                 OwnershipValue.meet(predValue, v_pred); 
147                             }
148                         }
149                     }
150                     //System.err.println("predValue for " + b + " is " + predValue);
151                 }else
152                 if(b.getNumberOfPredecessors() == 0) {
153                     // first Basic Block
154                     predValue = initValue;
155                 }
156                 
157                 OwnershipValue v_b = processBlock(m, b, predValue);
158                 OwnershipValue v_b_old = (OwnershipValue)valueAtEnd.get(b);
159                 boolean changed = false;
160                 if(v_b_old != null) {
161                     changed |= OwnershipValue.meet(v_b, v_b_old);
162                 }else{
163                     changed = true;
164                     valueAtEnd.put(b, v_b);                    
165                 }
166                 
167                 if(changed) {
168                     // enlist the successors
169                     List.BasicBlock l = b.getSuccessors();
170                     for(joeq.Util.Templates.ListIterator.BasicBlock i = l.basicBlockIterator(); i.hasNext();) {
171                         BasicBlock succ = i.nextBasicBlock();
172                         if(!worklist.contains(succ)) {
173                             worklist.push(succ);
174                         }
175                     }
176                 }
177             }
178             
179             procValue.put(m, valueAtEnd.get(cfg.exit()));
180             System.out.println(cutto("\tValue for " + m + ": ", 50) + getExitValue(m));
181         }
182         
183         private OwnershipValue getExitValue(jq_Method m) {
184             return (OwnershipValue)procValue.get(m);
185         }
186 
187         private OwnershipValue getInitValue(jq_Method m) {
188             OwnershipValue result = new OwnershipValue();
189             //RegisterFactory rf = CodeCache.getRegisterFactory(m);
190             //System.out.println("Method: " + m + "; " + rf);
191             
192             /*for(Iterator iter = rf.iterator(); iter.hasNext();) {
193                 RegisterFactory.Register reg = (Register)iter.next();
194                 if(!reg.isTemp()) {
195                     System.out.println("\t" + reg);
196                 }
197             }
198             */            
199             return null;
200         }
201 
202         OwnershipValue processBlock(jq_Method m, BasicBlock block, OwnershipValue predValue) {
203             // start with the input value
204             OwnershipValue result = (predValue != null) ? new OwnershipValue(predValue) : new OwnershipValue();
205             for(ListIterator.Quad qiter = block.iterator(); qiter.hasNext();) {
206                 Quad q = qiter.nextQuad();
207                 //System.out.println("\tProcessing " + q);
208                                 
209                 if(q.getOperator() instanceof Operator.New){
210                     if(_verbose) System.out.println("Processing initialization " + q);
211                     Operand.RegisterOperand o = Operator.New.getDest(q);
212                     jq_Type type = Operator.New.getType(q).getType();
213                     
214                     result.addValue(o.getRegister(), new OwnershipLattice(OwnershipLattice.OWNED, type));
215                 }else
216                 if(q.getOperator() instanceof Operator.Move){
217                     joeq.Util.Templates.ListIterator.RegisterOperand uiter = q.getUsedRegisters().registerOperandIterator();
218                     joeq.Util.Templates.ListIterator.RegisterOperand diter = q.getDefinedRegisters().registerOperandIterator();
219                     
220                     if(!uiter.hasNext() || !diter.hasNext()) continue;
221                     Operand.RegisterOperand use = (Operand.RegisterOperand)uiter.nextOperand();
222                     Operand.RegisterOperand def = (Operand.RegisterOperand)diter.nextOperand();
223                     if(_verbose) System.err.println("Processing move from " + use + " to " + def);
224                     
225                     if(result.hasValue(use.getRegister())) {
226                         // copy the type of the use to the type of the definition 
227                         result.putValue(def.getRegister(), result.getValue(use.getRegister()));                        
228                     } else {
229                         result.putValue(def.getRegister(), new OwnershipLattice(OwnershipLattice.UNOWNED));
230                     }
231                     if(_verbose) System.err.println("Saved data for " + def);
232                 }else
233                 if(q.getOperator() instanceof Operator.Putfield) {
234                     if(_verbose) System.out.println("Processing store: " + q);
235                     
236                     joeq.Util.Templates.ListIterator.RegisterOperand uiter = q.getUsedRegisters().registerOperandIterator();
237                     uiter.nextOperand();
238                     Operand.RegisterOperand use = (Operand.RegisterOperand)uiter.nextOperand();
239                     
240                     if(result.hasValue(use.getRegister())) {
241                         result.putValue(Operator.Putfield.getField(q).getField(), result.getValue(use.getRegister()));    
242                     }else {
243                         if(_verbose) System.err.println("No data for RHS of a store: " + q + "( " + use + " ), result: " + result);
244                         result.putValue(Operator.Putfield.getField(q).getField(), new OwnershipLattice(OwnershipLattice.UNOWNED));
245                     }                    
246                 }else
247                 if(q.getOperator() instanceof Operator.Invoke) {
248                     if(_verbose) System.out.println("Processing call: " + q);
249                     
250                     jq_Method callee = Operator.Invoke.getMethod(q).getMethod();
251                     OwnershipValue value = (OwnershipValue)procValue.get(callee);
252                     if(value != null) {
253                         OwnershipValue.meet(result, value);
254                     }                    
255                 }
256             }
257             
258             result = result.removeRegisters();
259             
260             if(_verbose) System.err.println("result for " + block + result);
261             
262             return result;
263         }
264         
265         /***
266          * Lattice of values -- types go to values.
267          * */
268         static class OwnershipValue {
269             HashMap/*<Object, LatticeValue>*/ _values = new HashMap();
270             
271             OwnershipValue(){}
272             
273             public OwnershipValue removeRegisters() {
274                 OwnershipValue result = new OwnershipValue();
275                 for(Iterator iter = _values.keySet().iterator(); iter.hasNext();) {
276                     Object key = iter.next();
277                     
278                     if(!(key instanceof RegisterFactory.Register)) {
279                         result.addValue(key, getValue(key));
280                     }
281                 }
282                 return result;
283             }
284             public void putValue(Object o, OwnershipLattice value) {
285                 _values.put(o, value);
286             }
287             public OwnershipLattice getValue(Object o) {
288                 return (OwnershipLattice)_values.get(o);
289             }
290             public boolean hasValue(Object o) {
291                 return _values.containsKey(o);
292             }
293 
294             OwnershipValue(OwnershipValue that){
295                 for(Iterator iter = that._values.keySet().iterator(); iter.hasNext();) {
296                     Object o  = iter.next();
297                     OwnershipLattice value = (OwnershipLattice)that._values.get(o);
298                     Assert._assert(value != null);
299                     
300                     addValue(o, value);
301                 }
302             }
303             
304             static boolean meet(OwnershipValue This, OwnershipValue That) {
305                 boolean changed = false;
306                 OwnershipValue result = new OwnershipValue(This);
307                 for(Iterator iter = That._values.keySet().iterator(); iter.hasNext(); ) {
308                     Object o = iter.next();
309                     
310                     if(!This._values.containsKey(o)) {
311                         changed = true;
312                         OwnershipLattice t = (OwnershipLattice)That._values.get(o);
313                         Assert._assert(t != null);
314                         This._values.put(o, t);
315                     }
316                 }
317                 
318                 return changed;
319             }
320             
321             void addValue(Object o, OwnershipLattice value) {                
322                 _values.put(o, value);
323             }
324             
325             public String toString() {
326                 return _values.toString();
327             }
328         }
329         
330         static class OwnershipLattice {
331             static final String OWNED   = "OWNED";
332             static final String UNOWNED = "UNOWNED";
333             
334             private String  _value;
335             private jq_Type _type;
336             
337             OwnershipLattice(String value, jq_Type type){
338                 _value = value;
339                 _type = type;
340             }            
341             OwnershipLattice(String value){
342                 this(value, null);
343             }
344             
345             public String toString() {return _value;}
346         }
347     }
348     private static String cutto(String string, int to) {
349         return string.length() < to ? 
350                                      string + repeat(" ", to - string.length()) : 
351                                          string.substring(0, to - 3) + "..."; 
352     }
353     private static String repeat(String string, int to) {
354         StringBuffer result = new StringBuffer();
355         for(int i = 0; i < to; i++) {
356             result.append(string);  
357         }
358         
359         return result.toString();
360     }
361 }