View Javadoc

1   // Trimmer.java, created Fri Jan 11 16:49:00 2002 by joewhaley
2   // Copyright (C) 2001-3 John Whaley <jwhaley@alum.mit.edu>
3   // Licensed under the terms of the GNU LGPL; see COPYING for details.
4   package joeq.Compiler.BytecodeAnalysis;
5   
6   import java.util.HashSet;
7   import java.util.Iterator;
8   import java.util.LinkedList;
9   import java.util.List;
10  import java.util.Set;
11  import java.io.PrintStream;
12  import joeq.Allocator.DefaultHeapAllocator;
13  import joeq.Allocator.HeapAllocator;
14  import joeq.Bootstrap.BootstrapRootSet;
15  import joeq.Class.Delegates;
16  import joeq.Class.jq_Array;
17  import joeq.Class.jq_Class;
18  import joeq.Class.jq_FieldVisitor;
19  import joeq.Class.jq_InstanceField;
20  import joeq.Class.jq_InstanceMethod;
21  import joeq.Class.jq_Method;
22  import joeq.Class.jq_MethodVisitor;
23  import joeq.Class.jq_StaticField;
24  import joeq.Class.jq_Type;
25  import joeq.Class.jq_TypeVisitor;
26  import joeq.Runtime.ExceptionDeliverer;
27  import joeq.Runtime.MathSupport;
28  import joeq.Runtime.Monitor;
29  import joeq.Runtime.Reflection;
30  import joeq.Runtime.TypeCheck;
31  import joeq.Runtime.Unsafe;
32  import jwutil.strings.Strings;
33  import jwutil.util.Assert;
34  
35  /***
36   * @author  John Whaley <jwhaley@alum.mit.edu>
37   * @version $Id: Trimmer.java 1941 2004-09-30 03:37:06Z joewhaley $
38   */
39  public class Trimmer {
40  
41      public static /*final*/ boolean TRACE = false;
42      public static final PrintStream out = System.out;
43      
44      private final BootstrapRootSet rs;
45      private final List/*jq_Method*/ methodWorklist;
46      
47      private final Set/*jq_Method*/ invokedVirtualMethods;
48      private final Set/*jq_Method*/ invokedInterfaceMethods;
49      
50      public Trimmer(jq_Method method, Set initialClassSet, boolean addall) {
51          this(initialClassSet, addall);
52          rs.addNecessaryMethod(method);
53      }
54      public Trimmer(Set initialClassSet, boolean addall) {
55          methodWorklist = new LinkedList();
56          invokedVirtualMethods = new HashSet();
57          invokedInterfaceMethods = new HashSet();
58          rs = new BootstrapRootSet(addall);
59          rs.registerNecessaryMethodListener(new AddMethodToWorklist());
60          rs.registerNecessaryFieldListener(new AddStaticFieldContents());
61          rs.registerNecessaryTypeListener(new UpkeepForNewlyDiscoveredClasses());
62          
63          rs.addDefaultRoots();
64          for (Iterator i = initialClassSet.iterator(); i.hasNext(); ) {
65              rs.addNecessaryType((jq_Type)i.next());
66          }
67      }
68  
69      public BootstrapRootSet getRootSet() { return rs; }
70      
71      public void addToWorklist(jq_Method m) {
72          methodWorklist.add(m);
73      }
74      
75      public void addInvokedInterfaceMethod(jq_InstanceMethod m) {
76          invokedInterfaceMethods.add(m);
77      }
78      
79      public void addInvokedVirtualMethod(jq_InstanceMethod m) {
80          invokedVirtualMethods.add(m);
81      }
82      
83      /*
84      public void addToNecessaryTypes(jq_Type t) {
85          if (t.isClassType()) {
86              if (!necessaryTypes.contains(t)) {
87                  necessaryTypes.add(t);
88                  jq_Class c2 = (jq_Class)t;
89                  // add all supertypes as necessary, as well
90                  for (jq_Class c3 = c2.getSuperclass(); c3 != null; c3 = c3.getSuperclass())
91                      addToNecessaryTypes(c3);
92                  if (AddAllClassMethods) {
93                      if (TRACE) out.println("Adding methods of new class "+t);
94                      for(Iterator it = Arrays.asList(c2.getDeclaredStaticMethods()).iterator();
95                          it.hasNext(); ) {
96                          jq_StaticMethod m = (jq_StaticMethod)it.next();
97                          addToWorklist(m);
98                      }
99                      for(Iterator it = Arrays.asList(c2.getDeclaredInstanceMethods()).iterator();
100                         it.hasNext(); ) {
101                         jq_InstanceMethod m = (jq_InstanceMethod)it.next();
102                         addToWorklist(m);
103                     }
104                 }
105                 if (AddAllClassFields) {
106                     if (TRACE) out.println("Adding fields of new class "+t);
107                     for(Iterator it = Arrays.asList(c2.getDeclaredStaticFields()).iterator();
108                         it.hasNext(); ) {
109                         jq_StaticField f = (jq_StaticField)it.next();
110                         addToNecessarySet(f);
111                         if (f.getType().isReferenceType()) addStaticFieldValue(f);
112                     }
113                     for(Iterator it = Arrays.asList(c2.getDeclaredInstanceFields()).iterator();
114                         it.hasNext(); ) {
115                         jq_InstanceField f = (jq_InstanceField)it.next();
116                         addToNecessarySet(f);
117                     }
118                 }
119             }
120             return;
121         }
122         necessaryTypes.add(t);
123     }
124      */
125     
126     public class AddMethodToWorklist extends jq_MethodVisitor.EmptyVisitor {
127         public void visitMethod(jq_Method m) {
128             addToWorklist(m);
129         }
130     }
131     
132     public class AddStaticFieldContents extends jq_FieldVisitor.EmptyVisitor {
133         public void visitStaticField(jq_StaticField f) {
134             if (f.getType().isPrimitiveType()) return;
135             if (f.getType().isAddressType()) return;
136             Object o2 = Reflection.getstatic_A(f);
137             rs.addObjectAndSubfields(o2);
138         }
139     }
140     /*
141     private void addClassInterfaceImplementations(jq_Class k) {
142         jq_Class[] in = k.getInterfaces();
143         for (int i=0; i<in.length; ++i) {
144             jq_Class f = in[i];
145             f.prepare();
146             jq_InstanceMethod[] ims = f.getVirtualMethods();
147             for (int j=0; j<ims.length; ++j) {
148                 jq_InstanceMethod im = ims[j];
149                 if (!necessaryMembers.contains(im)) {
150                     continue;
151                 }
152                 jq_InstanceMethod m2 = k.getVirtualMethod(im.getNameAndDesc());
153                 if (m2 == null) {
154                     // error:
155                     if (TRACE) out.println("Error! Class "+k+" doesn't implement interface method "+im);
156                     continue;
157                 }
158                 if (!necessaryMembers.contains(m2)) {
159                     addToWorklist(m2);
160                 } else {
161                     if (TRACE) out.println(m2+" already added as necessary");
162                 }
163             }
164         }
165     }
166      */
167     
168     /*
169     private void addClassInitializer(jq_Class c) {
170         c.prepare();
171         if (ADD_CLASS_INITIALIZERS) {
172             jq_Method m = c.getClassInitializer();
173             if (m != null) {
174                 if (TRACE) out.println("Adding class initializer "+m);
175                 if (!necessaryMembers.contains(m)) {
176                     addToWorklist(m);
177                     jq_Class superclass = c.getSuperclass();
178                     if (superclass != null) addClassInitializer(superclass);
179                 }
180             }
181         }
182     }
183      */
184     
185     public void go() {
186         while (!methodWorklist.isEmpty()) {
187             while (!methodWorklist.isEmpty()) {
188                 jq_Method m = (jq_Method)methodWorklist.remove(0);
189                 if (TRACE) out.println("Pulling method "+m+" from worklist");
190 
191                 //jq_Class c = m.getDeclaringClass();
192                 //addClassInitializer(c);
193                 //if (!m.isStatic()) {
194                 //    if (c.isInterface()) {
195                 //        jq.Assert(m.isAbstract());
196                 //        addAllInterfaceMethodImplementations((jq_InstanceMethod)m);
197                 //        continue;
198                 //    } else {
199                 //        addSubclassVirtualMethods(c, (jq_InstanceMethod)m);
200                 //    }
201                 //}
202                 if (m.getBytecode() == null) {
203                     // native/abstract method
204                     continue;
205                 }
206                 TrimmerVisitor v = new TrimmerVisitor(m);
207                 v.forwardTraversal();
208             }
209             rs.addNecessarySubfieldsOfVisitedObjects();
210         }
211     }
212     
213     class TrimmerVisitor extends BytecodeVisitor {
214         
215         //jq_Method getstatic_method;
216         
217         TrimmerVisitor(jq_Method method) {
218             super(method);
219             //this.TRACE = true;
220         }
221 
222         public String toString() {
223             return "Trim/"+Strings.left(method.getName().toString(), 10);
224         }
225 
226         public void forwardTraversal() throws VerifyError {
227             if (this.TRACE) this.out.println(this+": Starting traversal.");
228             super.forwardTraversal();
229             if (this.TRACE) this.out.println(this+": Finished traversal.");
230         }
231 
232         public void visitBytecode() throws VerifyError {
233             super.visitBytecode();
234         }
235         
236         public void visitAASTORE() {
237             super.visitAASTORE();
238             INVOKEhelper(INVOKE_STATIC, TypeCheck._arrayStoreCheck);
239         }
240         public void visitLBINOP(byte op) {
241             super.visitLBINOP(op);
242             switch(op) {
243                 case BINOP_DIV:
244                     INVOKEhelper(INVOKE_STATIC, MathSupport._ldiv);
245                     break;
246                 case BINOP_REM:
247                     INVOKEhelper(INVOKE_STATIC, MathSupport._lrem);
248                     break;
249                 default:
250                     break;
251             }
252         }
253         public void visitF2I() {
254             super.visitF2I();
255             rs.addNecessaryField(MathSupport._maxint);
256             rs.addNecessaryField(MathSupport._minint);
257         }
258         public void visitD2I() {
259             super.visitD2I();
260             rs.addNecessaryField(MathSupport._maxint);
261             rs.addNecessaryField(MathSupport._minint);
262         }
263         public void visitF2L() {
264             super.visitF2L();
265             rs.addNecessaryField(MathSupport._maxlong);
266             rs.addNecessaryField(MathSupport._minlong);
267         }
268         public void visitD2L() {
269             super.visitD2L();
270             rs.addNecessaryField(MathSupport._maxlong);
271             rs.addNecessaryField(MathSupport._minlong);
272         }
273         private void GETSTATIChelper(jq_StaticField f) {
274             f = tryResolve(f);
275             //addClassInitializer(f.getDeclaringClass());
276             rs.addNecessaryField(f);
277         }
278         public void visitIGETSTATIC(jq_StaticField f) {
279             super.visitIGETSTATIC(f);
280             GETSTATIChelper(f);
281         }
282         public void visitLGETSTATIC(jq_StaticField f) {
283             super.visitLGETSTATIC(f);
284             GETSTATIChelper(f);
285         }
286         public void visitFGETSTATIC(jq_StaticField f) {
287             super.visitFGETSTATIC(f);
288             GETSTATIChelper(f);
289         }
290         public void visitDGETSTATIC(jq_StaticField f) {
291             super.visitDGETSTATIC(f);
292             GETSTATIChelper(f);
293         }
294         public void visitAGETSTATIC(jq_StaticField f) {
295             super.visitAGETSTATIC(f);
296             GETSTATIChelper(f);
297             /*
298                 if (f.getType() == jq_InstanceMethod._class ||
299                     f.getType() == jq_StaticMethod._class ||
300                     f.getType() == jq_Method._class ||
301                     f.getType() == jq_Initializer._class ||
302                     f.getType() == jq_ClassInitializer._class) {
303                     // reading from a static field of type jq_Method
304                     getstatic_method = (jq_Method)Reflection.getstatic_A(f);
305                     if (this.TRACE) this.out.println("getstatic field "+f+" value: "+getstatic_method);
306                 }
307              */
308         }
309         public void visitZGETSTATIC(jq_StaticField f) {
310             super.visitZGETSTATIC(f);
311             GETSTATIChelper(f);
312         }
313         public void visitBGETSTATIC(jq_StaticField f) {
314             super.visitBGETSTATIC(f);
315             GETSTATIChelper(f);
316         }
317         public void visitCGETSTATIC(jq_StaticField f) {
318             super.visitCGETSTATIC(f);
319             GETSTATIChelper(f);
320         }
321         public void visitSGETSTATIC(jq_StaticField f) {
322             super.visitSGETSTATIC(f);
323             GETSTATIChelper(f);
324         }
325         private void PUTSTATIChelper(jq_StaticField f) {
326             f = tryResolve(f);
327             //addClassInitializer(f.getDeclaringClass());
328             rs.addNecessaryField(f);
329         }
330         public void visitIPUTSTATIC(jq_StaticField f) {
331             super.visitIPUTSTATIC(f);
332             PUTSTATIChelper(f);
333         }
334         public void visitLPUTSTATIC(jq_StaticField f) {
335             super.visitLPUTSTATIC(f);
336             PUTSTATIChelper(f);
337         }
338         public void visitFPUTSTATIC(jq_StaticField f) {
339             super.visitFPUTSTATIC(f);
340             PUTSTATIChelper(f);
341         }
342         public void visitDPUTSTATIC(jq_StaticField f) {
343             super.visitDPUTSTATIC(f);
344             PUTSTATIChelper(f);
345         }
346         public void visitAPUTSTATIC(jq_StaticField f) {
347             super.visitAPUTSTATIC(f);
348             PUTSTATIChelper(f);
349         }
350         public void visitZPUTSTATIC(jq_StaticField f) {
351             super.visitZPUTSTATIC(f);
352             PUTSTATIChelper(f);
353         }
354         public void visitBPUTSTATIC(jq_StaticField f) {
355             super.visitBPUTSTATIC(f);
356             PUTSTATIChelper(f);
357         }
358         public void visitCPUTSTATIC(jq_StaticField f) {
359             super.visitCPUTSTATIC(f);
360             PUTSTATIChelper(f);
361         }
362         public void visitSPUTSTATIC(jq_StaticField f) {
363             super.visitSPUTSTATIC(f);
364             PUTSTATIChelper(f);
365         }
366         private void GETFIELDhelper(jq_InstanceField f) {
367             f = tryResolve(f);
368             rs.addNecessaryField(f);
369         }
370         public void visitIGETFIELD(jq_InstanceField f) {
371             super.visitIGETFIELD(f);
372             GETFIELDhelper(f);
373         }
374         public void visitLGETFIELD(jq_InstanceField f) {
375             super.visitLGETFIELD(f);
376             GETFIELDhelper(f);
377         }
378         public void visitFGETFIELD(jq_InstanceField f) {
379             super.visitFGETFIELD(f);
380             GETFIELDhelper(f);
381         }
382         public void visitDGETFIELD(jq_InstanceField f) {
383             super.visitDGETFIELD(f);
384             GETFIELDhelper(f);
385         }
386         public void visitAGETFIELD(jq_InstanceField f) {
387             super.visitAGETFIELD(f);
388             GETFIELDhelper(f);
389         }
390         public void visitBGETFIELD(jq_InstanceField f) {
391             super.visitBGETFIELD(f);
392             GETFIELDhelper(f);
393         }
394         public void visitCGETFIELD(jq_InstanceField f) {
395             super.visitCGETFIELD(f);
396             GETFIELDhelper(f);
397         }
398         public void visitSGETFIELD(jq_InstanceField f) {
399             super.visitSGETFIELD(f);
400             GETFIELDhelper(f);
401         }
402         public void visitZGETFIELD(jq_InstanceField f) {
403             super.visitZGETFIELD(f);
404             GETFIELDhelper(f);
405         }
406         public void visitIPUTFIELD(jq_InstanceField f) {
407             super.visitIPUTFIELD(f);
408             GETFIELDhelper(f);
409         }
410         public void visitLPUTFIELD(jq_InstanceField f) {
411             super.visitLPUTFIELD(f);
412             GETFIELDhelper(f);
413         }
414         public void visitFPUTFIELD(jq_InstanceField f) {
415             super.visitFPUTFIELD(f);
416             GETFIELDhelper(f);
417         }
418         public void visitDPUTFIELD(jq_InstanceField f) {
419             super.visitDPUTFIELD(f);
420             GETFIELDhelper(f);
421         }
422         public void visitAPUTFIELD(jq_InstanceField f) {
423             super.visitAPUTFIELD(f);
424             GETFIELDhelper(f);
425         }
426         public void visitBPUTFIELD(jq_InstanceField f) {
427             super.visitBPUTFIELD(f);
428             GETFIELDhelper(f);
429         }
430         public void visitCPUTFIELD(jq_InstanceField f) {
431             super.visitCPUTFIELD(f);
432             GETFIELDhelper(f);
433         }
434         public void visitSPUTFIELD(jq_InstanceField f) {
435             super.visitSPUTFIELD(f);
436             GETFIELDhelper(f);
437         }
438         public void visitZPUTFIELD(jq_InstanceField f) {
439             super.visitZPUTFIELD(f);
440             GETFIELDhelper(f);
441         }
442         private void INVOKEhelper(byte op, jq_Method f) {
443             f = (jq_Method) tryResolve(f);
444             switch (op) {
445             case INVOKE_STATIC:
446                 if (f.getDeclaringClass() == Unsafe._class)
447                     return;
448                 rs.addNecessaryMethod(Delegates.default_compiler.getInvokestaticLinkMethod());
449                 rs.addNecessaryMethod(f);
450                 break;
451             case INVOKE_SPECIAL:
452                 rs.addNecessaryMethod(Delegates.default_compiler.getInvokespecialLinkMethod());
453                 f = jq_Class.getInvokespecialTarget(method.getDeclaringClass(), (jq_InstanceMethod)f);
454                 rs.addNecessaryMethod(f);
455                 break;
456             case INVOKE_INTERFACE:
457                 rs.addNecessaryMethod(Delegates.default_compiler.getInvokeinterfaceLinkMethod());
458                 rs.addAllInterfaceMethodImplementations((jq_InstanceMethod)f);
459                 addInvokedInterfaceMethod((jq_InstanceMethod)f);
460                 break;
461             case INVOKE_VIRTUAL:
462                 rs.addAllVirtualMethodImplementations((jq_InstanceMethod)f);
463                 addInvokedVirtualMethod((jq_InstanceMethod)f);
464                 break;
465             }
466             // class initializer added when method is visited.
467             //jq.Assert(f.getDeclaringClass() != Unsafe._class);
468         }
469         /*
470         private void reflective_invoke(byte op, jq_Method f) {
471             if (f.getDeclaringClass() == Reflection._class) {
472                 if (f.getName().toString().startsWith("invokestatic")) {
473                     System.out.println(method+": Reflective static invocation: "+getstatic_method);
474                     // reflective invocation.  where does it go?
475                     if (getstatic_method != null)
476                         INVOKEhelper(INVOKE_STATIC, getstatic_method);
477                 } else if (f.getName().toString().startsWith("invokeinstance")) {
478                     System.out.println(method+": Reflective instance invocation: "+getstatic_method);
479                     // reflective invocation.  where does it go?
480                     if (getstatic_method != null)
481                         INVOKEhelper(INVOKE_SPECIAL, getstatic_method);
482                 }
483             }
484         }
485          */
486         public void visitIINVOKE(byte op, jq_Method f) {
487             super.visitIINVOKE(op, f);
488             //reflective_invoke(op, f);
489             INVOKEhelper(op, f);
490         }
491         public void visitLINVOKE(byte op, jq_Method f) {
492             super.visitLINVOKE(op, f);
493             //reflective_invoke(op, f);
494             INVOKEhelper(op, f);
495         }
496         public void visitFINVOKE(byte op, jq_Method f) {
497             super.visitFINVOKE(op, f);
498             //reflective_invoke(op, f);
499             INVOKEhelper(op, f);
500         }
501         public void visitDINVOKE(byte op, jq_Method f) {
502             super.visitDINVOKE(op, f);
503             //reflective_invoke(op, f);
504             INVOKEhelper(op, f);
505         }
506         public void visitAINVOKE(byte op, jq_Method f) {
507             super.visitAINVOKE(op, f);
508             //reflective_invoke(op, f);
509             INVOKEhelper(op, f);
510         }
511         public void visitVINVOKE(byte op, jq_Method f) {
512             super.visitVINVOKE(op, f);
513             //reflective_invoke(op, f);
514             INVOKEhelper(op, f);
515         }
516         public void visitNEW(jq_Type f) {
517             super.visitNEW(f);
518             //INVOKEhelper(INVOKE_STATIC, DefaultHeapAllocator._allocateObject);
519             INVOKEhelper(INVOKE_STATIC, HeapAllocator._clsinitAndAllocateObject);
520             rs.addNecessaryType(f);
521         }
522         public void visitNEWARRAY(jq_Array f) {
523             super.visitNEWARRAY(f);
524             INVOKEhelper(INVOKE_STATIC, DefaultHeapAllocator._allocateArray);
525             rs.addNecessaryType(f);
526         }
527         public void visitATHROW() {
528             super.visitATHROW();
529             INVOKEhelper(INVOKE_STATIC, ExceptionDeliverer._athrow);
530         }
531         public void visitCHECKCAST(jq_Type f) {
532             super.visitCHECKCAST(f);
533             INVOKEhelper(INVOKE_STATIC, TypeCheck._checkcast);
534         }
535         public void visitINSTANCEOF(jq_Type f) {
536             super.visitINSTANCEOF(f);
537             INVOKEhelper(INVOKE_STATIC, TypeCheck._instance_of);
538         }
539         public void visitMONITOR(byte op) {
540             super.visitMONITOR(op);
541             if (op == MONITOR_ENTER)
542                 INVOKEhelper(INVOKE_STATIC, Monitor._monitorenter);
543             else
544                 INVOKEhelper(INVOKE_STATIC, Monitor._monitorexit);
545         }
546         public void visitMULTINEWARRAY(jq_Type f, char dim) {
547             super.visitMULTINEWARRAY(f, dim);
548             INVOKEhelper(INVOKE_STATIC, joeq.Runtime.Arrays._multinewarray);
549             rs.addNecessaryType(f);
550             for (int i=0; i<dim; ++i) {
551                 if (!f.isArrayType()) {
552                     // TODO: throws VerifyError here!
553                     break;
554                 }
555                 f = ((jq_Array)f).getElementType();
556                 rs.addNecessaryType(f);
557             }
558         }
559     }
560 
561     public void addNecessaryInterfaceMethodImplementations(jq_Class c, jq_Class inter) {
562         inter.prepare();
563         Assert._assert(inter.isInterface());
564         jq_InstanceMethod[] ms = inter.getVirtualMethods();
565         for (int i=0; i<ms.length; ++i) {
566             jq_InstanceMethod m = ms[i];
567             if (!invokedInterfaceMethods.contains(m)) continue;
568             jq_InstanceMethod m2 = c.getVirtualMethod(m.getNameAndDesc());
569             if (m2 == null) continue;
570             rs.addNecessaryMethod(m2);
571         }
572         jq_Class[] interfaces = inter.getInterfaces();
573         for (int i=0; i<interfaces.length; ++i) {
574             jq_Class k2 = interfaces[i];
575             addNecessaryInterfaceMethodImplementations(c, k2);
576         }
577     }
578     
579     public class UpkeepForNewlyDiscoveredClasses extends jq_TypeVisitor.EmptyVisitor {
580         public void visitClass(jq_Class c) {
581             jq_InstanceMethod[] ms = c.getDeclaredInstanceMethods();
582             for (int i=0; i<ms.length; ++i) {
583                 jq_InstanceMethod m = ms[i];
584                 if (m.isOverriding()) {
585                     //if (TRACE) out.println("Checking virtual method "+m);
586                     jq_InstanceMethod m2 = c.getSuperclass().getVirtualMethod(m.getNameAndDesc());
587                     if (m2 != null) {
588                         if (invokedVirtualMethods.contains(m2)) {
589                             if (TRACE) out.println("Method "+m+" is necessary because it overrides "+m2);
590                             rs.addNecessaryMethod(m);
591                             continue;
592                         } else {
593                             //if (TRACE) out.println("Overridden method "+m2+" is not necessary!");
594                         }
595                     }
596                 }
597             }
598             jq_Class[] interfaces = c.getInterfaces();
599             for (int i=0; i<interfaces.length; ++i) {
600                 jq_Class k2 = interfaces[i];
601                 addNecessaryInterfaceMethodImplementations(c, k2);
602             }
603         }
604     }
605 
606 }