Pruner


1   /*
2    * Copyright 2007 Google Inc.
3    * 
4    * Licensed under the Apache License, Version 2.0 (the "License"); you may not
5    * use this file except in compliance with the License. You may obtain a copy of
6    * the License at
7    * 
8    * http://www.apache.org/licenses/LICENSE-2.0
9    * 
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
12   * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
13   * License for the specific language governing permissions and limitations under
14   * the License.
15   */
16  package com.google.gwt.dev.jjs.impl;
17  
18  import com.google.gwt.dev.jjs.ast.Context;
19  import com.google.gwt.dev.jjs.ast.JAbsentArrayDimension;
20  import com.google.gwt.dev.jjs.ast.JArrayType;
21  import com.google.gwt.dev.jjs.ast.JBinaryOperation;
22  import com.google.gwt.dev.jjs.ast.JBinaryOperator;
23  import com.google.gwt.dev.jjs.ast.JClassLiteral;
24  import com.google.gwt.dev.jjs.ast.JClassType;
25  import com.google.gwt.dev.jjs.ast.JExpression;
26  import com.google.gwt.dev.jjs.ast.JField;
27  import com.google.gwt.dev.jjs.ast.JFieldRef;
28  import com.google.gwt.dev.jjs.ast.JInterfaceType;
29  import com.google.gwt.dev.jjs.ast.JLocal;
30  import com.google.gwt.dev.jjs.ast.JLocalRef;
31  import com.google.gwt.dev.jjs.ast.JMethod;
32  import com.google.gwt.dev.jjs.ast.JMethodCall;
33  import com.google.gwt.dev.jjs.ast.JModVisitor;
34  import com.google.gwt.dev.jjs.ast.JNewArray;
35  import com.google.gwt.dev.jjs.ast.JNewInstance;
36  import com.google.gwt.dev.jjs.ast.JParameter;
37  import com.google.gwt.dev.jjs.ast.JParameterRef;
38  import com.google.gwt.dev.jjs.ast.JPrimitiveType;
39  import com.google.gwt.dev.jjs.ast.JProgram;
40  import com.google.gwt.dev.jjs.ast.JReferenceType;
41  import com.google.gwt.dev.jjs.ast.JStringLiteral;
42  import com.google.gwt.dev.jjs.ast.JThisRef;
43  import com.google.gwt.dev.jjs.ast.JType;
44  import com.google.gwt.dev.jjs.ast.JVariable;
45  import com.google.gwt.dev.jjs.ast.JVariableRef;
46  import com.google.gwt.dev.jjs.ast.JVisitor;
47  import com.google.gwt.dev.jjs.ast.js.JsniFieldRef;
48  import com.google.gwt.dev.jjs.ast.js.JsniMethod;
49  import com.google.gwt.dev.jjs.ast.js.JsniMethodRef;
50  
51  import java.util.ArrayList  ;
52  import java.util.HashSet  ;
53  import java.util.Iterator  ;
54  import java.util.List  ;
55  import java.util.Set  ;
56  
57  /**
58   * Remove globally unreferenced classes, interfaces, methods, and fields from
59   * the AST. This algorithm is based on having known "entry points" into the
60   * application which serve as the root(s) from which reachability is determined
61   * and everything else is rescued. Pruner determines reachability at a global
62   * level based on method calls and new operations; it does not perform any local
63   * code flow analysis. But, a local code flow optimization pass that can
64   * eliminate method calls would allow Pruner to prune additional nodes.
65   * 
66   * Note: references to pruned types may still exist in the tree after this pass
67   * runs, however, it should only be in contexts that do not rely on any code
68   * generation for the pruned type. For example, it's legal to have a variable of
69   * a pruned type, or to try to cast to a pruned type. These will cause natural
70   * failures at run time; or later optimizations might be able to hard-code
71   * failures at compile time.
72   */
73  public class Pruner {
74  
75    /**
76     * Remove assignments to pruned fields and locals.
77     * 
78     * TODO(later): prune params too
79     */
80    private class CleanupRefsVisitor extends JModVisitor {
81  
82      public void endVisit(JBinaryOperation x, Context ctx) {
83        // The LHS of assignments may have been pruned.
84        if (x.getOp() == JBinaryOperator.ASG) {
85          JExpression lhs = x.getLhs();
86          if (lhs.hasSideEffects()) {
87            return;
88          }
89          if (lhs instanceof JFieldRef || lhs instanceof JLocalRef) {
90            JVariable var = ((JVariableRef) lhs).getTarget();
91            if (!referencedNonTypes.contains(var)) {
92              // Just replace with my RHS
93              ctx.replaceMe(x.getRhs());
94            }
95          }
96        }
97      }
98    }
99  
100   /**
101    * Remove any unreferenced classes and interfaces from JProgram. Remove any
102    * unreferenced methods and fields from their containing classes.
103    */
104   private class PruneVisitor extends JVisitor {
105 
106     private boolean didChange = false;
107 
108     public boolean didChange() {
109       return didChange;
110     }
111 
112     // @Override
113     public boolean visit(JClassType type, Context ctx) {
114 
115       assert (referencedTypes.contains(type));
116       boolean isInstantiated = program.typeOracle.isInstantiatedType(type);
117 
118       for (Iterator   it = type.fields.iterator(); it.hasNext();) {
119         JField field = (JField) it.next();
120         if (!referencedNonTypes.contains(field)
121             || pruneViaNoninstantiability(isInstantiated, field)) {
122           it.remove();
123           didChange = true;
124         }
125       }
126 
127       for (Iterator   it = type.methods.iterator(); it.hasNext();) {
128         JMethod method = (JMethod) it.next();
129         if (!methodIsReferenced(method)
130             || pruneViaNoninstantiability(isInstantiated, method)) {
131           it.remove();
132           didChange = true;
133         } else {
134           accept(method);
135         }
136       }
137 
138       return false;
139     }
140 
141     // @Override
142     public boolean visit(JInterfaceType type, Context ctx) {
143       boolean isReferenced = referencedTypes.contains(type);
144       boolean isInstantiated = program.typeOracle.isInstantiatedType(type);
145 
146       for (Iterator   it = type.fields.iterator(); it.hasNext();) {
147         JField field = (JField) it.next();
148         // all interface fields are static and final
149         if (!isReferenced || !referencedNonTypes.contains(field)) {
150           it.remove();
151           didChange = true;
152         }
153       }
154 
155       Iterator   it = type.methods.iterator();
156       if (it.hasNext()) {
157         // start at index 1; never prune clinit directly out of the interface
158         it.next();
159       }
160       while (it.hasNext()) {
161         JMethod method = (JMethod) it.next();
162         // all other interface methods are instance and abstract
163         if (!isInstantiated || !methodIsReferenced(method)) {
164           it.remove();
165           didChange = true;
166         }
167       }
168 
169       return false;
170     }
171 
172     public boolean visit(JMethod method, Context ctx) {
173       for (Iterator   it = method.locals.iterator(); it.hasNext();) {
174         JLocal local = (JLocal) it.next();
175         if (!referencedNonTypes.contains(local)) {
176           it.remove();
177           didChange = true;
178         }
179       }
180       return false;
181     }
182 
183     // @Override
184     public boolean visit(JProgram program, Context ctx) {
185       for (Iterator   it = program.getDeclaredTypes().iterator(); it.hasNext(); ) {
186         JReferenceType type = (JReferenceType) it.next();
187         if (referencedTypes.contains(type)
188             || program.typeOracle.isInstantiatedType(type)) {
189           accept(type);
190         } else {
191           it.remove();
192           didChange = true;
193         }
194       }
195       return false;
196     }
197 
198     /**
199      * Returns <code>true</code> if a method is referenced.
200      */
201     private boolean methodIsReferenced(JMethod method) {
202       // Is the method directly referenced?
203       if (referencedNonTypes.contains(method)) {
204         return true;
205       }
206 
207       /*
208        * Special case: if method is the static impl for a live instance method,
209        * don't prune it unless this is the final prune.
210        * 
211        * In some cases, the staticImpl can be inlined into the instance method
212        * but still be needed at other call sites.
213        */
214       JMethod staticImplFor = program.staticImplFor(method);
215       if (staticImplFor != null && referencedNonTypes.contains(staticImplFor)) {
216         if (noSpecialTypes) {
217           return true;
218         }
219       }
220       return false;
221     }
222 
223     private boolean pruneViaNoninstantiability(boolean isInstantiated, JField it) {
224       return (!isInstantiated && !it.isStatic());
225     }
226 
227     private boolean pruneViaNoninstantiability(boolean isInstantiated,
228         JMethod it) {
229       return (!isInstantiated && (!it.isStatic() || program.isStaticImpl(it)));
230     }
231   }
232 
233   /**
234    * Marks as "referenced" any types, methods, and fields that are reachable.
235    * Also marks as "instantiable" any the classes and interfaces that can
236    * possibly be instantiated.
237    * 
238    * TODO(later): make RescueVisitor use less stack?
239    */
240   private class RescueVisitor extends JVisitor {
241 
242     private final Set  /* <JReferenceType> */instantiatedTypes = new HashSet  /* <JReferenceType> */();
243 
244     public void commitInstantiatedTypes() {
245       program.typeOracle.setInstantiatedTypes(instantiatedTypes);
246     }
247 
248     // @Override
249     public boolean visit(JArrayType type, Context ctx) {
250       assert (referencedTypes.contains(type));
251       boolean isInstantiated = instantiatedTypes.contains(type);
252 
253       JType leafType = type.getLeafType();
254       int dims = type.getDims();
255 
256       // Rescue my super array type
257       if (leafType instanceof JReferenceType) {
258         JReferenceType rLeafType = (JReferenceType) leafType;
259         if (rLeafType.extnds != null) {
260           JArrayType superArray = program.getTypeArray(rLeafType.extnds, dims);
261           rescue(superArray, true, isInstantiated);
262         }
263 
264         for (int i = 0; i < rLeafType.implments.size(); ++i) {
265           JInterfaceType intfType = (JInterfaceType) rLeafType.implments.get(i);
266           JArrayType intfArray = program.getTypeArray(intfType, dims);
267           rescue(intfArray, true, isInstantiated);
268         }
269       }
270 
271       return false;
272     }
273 
274     public boolean visit(JBinaryOperation x, Context ctx) {
275       // special string concat handling
276       if (x.getOp() == JBinaryOperator.ADD
277           && x.getType() == program.getTypeJavaLangString()) {
278         rescueByConcat(x.getLhs().getType());
279         rescueByConcat(x.getRhs().getType());
280       } else if (x.getOp() == JBinaryOperator.ASG) {
281         // Don't rescue variables that are merely assigned to and never read
282         boolean doSkip = false;
283         JExpression lhs = x.getLhs();
284         if (lhs.hasSideEffects()) {
285           // cannot skip
286         } else if (lhs instanceof JLocalRef) {
287           // locals are ok to skip
288           doSkip = true;
289         } else if (lhs instanceof JFieldRef) {
290           JFieldRef fieldRef = (JFieldRef) lhs;
291           /*
292            * Whether we can skip depends on what the qualifier is; we have to be
293            * certain the qualifier cannot be a null pointer (in which case we'd
294            * fail to throw the appropriate exception.
295            * 
296            * TODO: better non-null tracking!
297            */
298           JExpression instance = fieldRef.getInstance();
299           if (fieldRef.getField().isStatic()) {
300             // statics are always okay
301             doSkip = true;
302           } else if (instance instanceof JThisRef) {
303             // a this ref cannot be null
304             doSkip = true;
305           } else if (instance instanceof JParameterRef) {
306             JParameter param = ((JParameterRef) instance).getParameter();
307             JMethod enclosingMethod = param.getEnclosingMethod();
308             if (program.isStaticImpl(enclosingMethod)
309                 && enclosingMethod.params.get(0) == param) {
310               doSkip = true;
311             }
312           }
313         }
314 
315         if (doSkip) {
316           accept(x.getRhs());
317           return false;
318         }
319       }
320       return true;
321     }
322 
323     // @Override
324     public boolean visit(JClassLiteral literal, Context ctx) {
325       // rescue and instantiate java.lang.Class
326       // JLS 12.4.1: do not rescue the target type
327       rescue(program.getTypeJavaLangClass(), true, true);
328       return true;
329     }
330 
331     // @Override
332     public boolean visit(JClassType type, Context ctx) {
333       assert (referencedTypes.contains(type));
334       boolean isInstantiated = instantiatedTypes.contains(type);
335 
336       /*
337        * SPECIAL: Some classes contain methods used by code generation later.
338        * Unless those transforms have already been performed, we must rescue all
339        * contained methods for later user.
340        */
341       if (noSpecialTypes && program.specialTypes.contains(type)) {
342         for (int i = 0; i < type.methods.size(); ++i) {
343           JMethod it = (JMethod) type.methods.get(i);
344           rescue(it);
345         }
346       }
347 
348       // Rescue my super type
349       rescue(type.extnds, true, isInstantiated);
350 
351       // Rescue my clinit (it won't ever be explicitly referenced
352       rescue((JMethod) type.methods.get(0));
353 
354       // JLS 12.4.1: don't rescue my super interfaces just because I'm rescued.
355       // However, if I'm instantiated, let's mark them as instantiated.
356       for (int i = 0; i < type.implments.size(); ++i) {
357         JInterfaceType intfType = (JInterfaceType) type.implments.get(i);
358         rescue(intfType, false, isInstantiated);
359       }
360 
361       return false;
362     }
363 
364     // @Override
365     public boolean visit(JFieldRef ref, Context ctx) {
366       JField target = ref.getField();
367 
368       // JLS 12.4.1: references to static, non-final, or
369       // non-compile-time-constant fields rescue the enclosing class.
370       // JDT already folds in compile-time constants as literals, so we must
371       // rescue the enclosing types for any static fields that make it here.
372       if (target.isStatic()) {
373         rescue(target.getEnclosingType(), true, false);
374       }
375       rescue(target);
376       return true;
377     }
378 
379     // @Override
380     public boolean visit(JInterfaceType type, Context ctx) {
381       boolean isReferenced = referencedTypes.contains(type);
382       boolean isInstantiated = instantiatedTypes.contains(type);
383       assert (isReferenced || isInstantiated);
384 
385       // Rescue my clinit (it won't ever be explicitly referenced
386       rescue((JMethod) type.methods.get(0));
387 
388       // JLS 12.4.1: don't rescue my super interfaces just because I'm rescued.
389       // However, if I'm instantiated, let's mark them as instantiated.
390       if (isInstantiated) {
391         for (int i = 0; i < type.implments.size(); ++i) {
392           JInterfaceType intfType = (JInterfaceType) type.implments.get(i);
393           rescue(intfType, false, true);
394         }
395       }
396 
397       // visit any field initializers
398       for (int i = 0; i < type.fields.size(); ++i) {
399         JField it = (JField) type.fields.get(i);
400         accept(it);
401       }
402 
403       return false;
404     }
405 
406     // @Override
407     public boolean visit(JLocalRef ref, Context ctx) {
408       JLocal target = ref.getLocal();
409       rescue(target);
410       return true;
411     }
412 
413     // @Override
414     public boolean visit(JMethodCall call, Context ctx) {
415       JMethod target = call.getTarget();
416       // JLS 12.4.1: references to static methods rescue the enclosing class
417       if (target.isStatic()) {
418         rescue(target.getEnclosingType(), true, false);
419       }
420       rescue(target);
421       return true;
422     }
423 
424     // @Override
425     public boolean visit(JNewArray newArray, Context ctx) {
426       // rescue and instantiate the array type
427       JArrayType arrayType = newArray.getArrayType();
428       if (newArray.dims != null) {
429         // rescue my type and all the implicitly nested types (with fewer dims)
430         int nDims = arrayType.getDims();
431         JType leafType = arrayType.getLeafType();
432         assert (newArray.dims.size() == nDims);
433         for (int i = 0; i < nDims; ++i) {
434           if (newArray.dims.get(i) instanceof JAbsentArrayDimension) {
435             break;
436           }
437           rescue(program.getTypeArray(leafType, nDims - i), true, true);
438         }
439       } else {
440         // just rescue my own specific type
441         rescue(arrayType, true, true);
442       }
443 
444       // also rescue and instantiate the "base" array type
445       rescue(program.getSpecialArray(), true, true);
446       return true;
447     }
448 
449     // @Override
450     public boolean visit(JNewInstance newInstance, Context ctx) {
451       // rescue and instantiate the target class!
452       rescue(newInstance.getClassType(), true, true);
453       return true;
454     }
455 
456     // @Override
457     public boolean visit(JsniFieldRef x, Context ctx) {
458       /*
459        * SPECIAL: this could be an assignment that passes a value from
460        * JavaScript into Java.
461        * 
462        * TODO(later): technically we only need to do this if the field is being
463        * assigned to.
464        */
465       maybeRescueJavaScriptObjectPassingIntoJava(x.getField().getType());
466       // JsniFieldRef rescues as JFieldRef
467       return visit((JFieldRef) x, ctx);
468     }
469 
470     // @Override
471     public boolean visit(JsniMethodRef x, Context ctx) {
472       /*
473        * SPECIAL: each argument of the call passes a value from JavaScript into
474        * Java.
475        */
476       ArrayList   params = x.getTarget().params;
477       for (int i = 0, c = params.size(); i < c; ++i) {
478         JParameter param = (JParameter) params.get(i);
479         maybeRescueJavaScriptObjectPassingIntoJava(param.getType());
480       }
481       // JsniMethodRef rescues as JMethodCall
482       return visit((JMethodCall) x, ctx);
483     }
484 
485     // @Override
486     public boolean visit(JStringLiteral literal, Context ctx) {
487       // rescue and instantiate java.lang.String
488       rescue(program.getTypeJavaLangString(), true, true);
489       return true;
490     }
491 
492     /**
493      * Subclasses of JavaScriptObject are never instantiated directly. They are
494      * created "magically" when a JSNI method passes a reference to an existing
495      * JS object into Java code. The point at which a subclass of JSO is passed
496      * into Java code constitutes "instantiation". We must identify these points
497      * and trigger a rescue and instantiation of that particular JSO subclass.
498      * 
499      * @param type The type of the value passing from Java to JavaScript.
500      * @see com.google.gwt.core.client.JavaScriptObject
501      */
502     private void maybeRescueJavaScriptObjectPassingIntoJava(JType type) {
503       if (type instanceof JReferenceType) {
504         JReferenceType refType = (JReferenceType) type;
505         if (program.typeOracle.canTriviallyCast(refType,
506             program.getSpecialJavaScriptObject())) {
507           rescue(refType, true, true);
508         }
509       }
510     }
511 
512     private boolean rescue(JMethod method) {
513       if (method != null) {
514         if (!referencedNonTypes.contains(method)) {
515           referencedNonTypes.add(method);
516           accept(method);
517           if (method instanceof JsniMethod) {
518             /*
519              * SPECIAL: returning from this method passes a value from
520              * JavaScript into Java.
521              */
522             maybeRescueJavaScriptObjectPassingIntoJava(method.getType());
523           }
524           return true;
525         }
526       }
527       return false;
528     }
529 
530     private void rescue(JReferenceType type, boolean isReferenced,
531         boolean isInstantiated) {
532       if (type != null) {
533 
534         boolean doVisit = false;
535         if (isInstantiated && !instantiatedTypes.contains(type)) {
536           instantiatedTypes.add(type);
537           doVisit = true;
538         }
539 
540         if (isReferenced && !referencedTypes.contains(type)) {
541           referencedTypes.add(type);
542           doVisit = true;
543         }
544 
545         if (doVisit) {
546           accept(type);
547         }
548       }
549     }
550 
551     private void rescue(JVariable var) {
552       if (var != null) {
553         if (!referencedNonTypes.contains(var)) {
554           referencedNonTypes.add(var);
555         }
556       }
557     }
558 
559     /**
560      * Handle special rescues needed implicitly to support concat.
561      */
562     private void rescueByConcat(JType type) {
563       JClassType stringType = program.getTypeJavaLangString();
564       JPrimitiveType charType = program.getTypePrimitiveChar();
565       if (type instanceof JReferenceType && type != stringType) {
566         /*
567          * Any reference types (except String, which works by default) that take
568          * part in a concat must rescue java.lang.Object.toString().
569          */
570         JMethod toStringMethod = program.getSpecialMethod("Object.toString");
571         rescue(toStringMethod);
572       } else if (type == charType) {
573         /*
574          * Characters must rescue String.valueOf(char)
575          */
576         if (stringValueOfChar == null) {
577           for (int i = 0; i < stringType.methods.size(); ++i) {
578             JMethod meth = (JMethod) stringType.methods.get(i);
579             if (meth.getName().equals("valueOf")) {
580               List   params = meth.getOriginalParamTypes();
581               if (params.size() == 1) {
582                 if (params.get(0) == charType) {
583                   stringValueOfChar = meth;
584                   break;
585                 }
586               }
587             }
588           }
589           assert (stringValueOfChar != null);
590         }
591         rescue(stringValueOfChar);
592       }
593     }
594   }
595 
596   /**
597    * A method that isn't called directly can still be needed, if it overrides or
598    * implements any methods that are called.
599    */
600   private class UpRefVisitor extends JVisitor {
601 
602     private boolean didRescue = false;
603     private final RescueVisitor rescuer;
604 
605     public UpRefVisitor(RescueVisitor rescuer) {
606       this.rescuer = rescuer;
607     }
608 
609     public boolean didRescue() {
610       return didRescue;
611     }
612 
613     // @Override
614     public boolean visit(JMethod x, Context ctx) {
615       if (referencedNonTypes.contains(x)) {
616         return false;
617       }
618 
619       for (int i = 0; i < x.overrides.size(); ++i) {
620         JMethod ref = (JMethod) x.overrides.get(i);
621         if (referencedNonTypes.contains(ref)) {
622           rescuer.rescue(x);
623           didRescue = true;
624           return false;
625         }
626       }
627       JMethod[] virtualOverrides = program.typeOracle.getAllVirtualOverrides(x);
628       for (int i = 0; i < virtualOverrides.length; ++i) {
629         JMethod ref = virtualOverrides[i];
630         if (referencedNonTypes.contains(ref)) {
631           rescuer.rescue(x);
632           didRescue = true;
633           return false;
634         }
635       }
636       return false;
637     }
638 
639     // @Override
640     public boolean visit(JProgram x, Context ctx) {
641       didRescue = false;
642       return true;
643     }
644 
645     // @Override
646     public boolean visit(JsniMethod x, Context ctx) {
647       return visit((JMethod) x, ctx);
648     }
649   }
650 
651   public static boolean exec(JProgram program, boolean noSpecialTypes) {
652     return new Pruner(program, noSpecialTypes).execImpl();
653   }
654 
655   private final boolean noSpecialTypes;
656   private final JProgram program;
657   private final Set  /* <JNode> */referencedNonTypes = new HashSet  /* <JNode> */();
658   private final Set  /* <JReferenceType> */referencedTypes = new HashSet  /* <JReferenceType> */();
659   private JMethod stringValueOfChar = null;
660 
661   private Pruner(JProgram program, boolean noSpecialTypes) {
662     this.program = program;
663     this.noSpecialTypes = noSpecialTypes;
664   }
665 
666   private boolean execImpl() {
667     boolean madeChanges = false;
668     while (true) {
669       RescueVisitor rescuer = new RescueVisitor();
670       for (int i = 0; i < program.specialTypes.size(); ++i) {
671         JReferenceType type = (JReferenceType) program.specialTypes.get(i);
672         rescuer.rescue(type, true, noSpecialTypes);
673       }
674       for (int i = 0; i < program.entryMethods.size(); ++i) {
675         JMethod method = (JMethod) program.entryMethods.get(i);
676         rescuer.rescue(method);
677       }
678 
679       UpRefVisitor upRefer = new UpRefVisitor(rescuer);
680       do {
681         rescuer.commitInstantiatedTypes();
682         upRefer.accept(program);
683       } while (upRefer.didRescue());
684 
685       PruneVisitor pruner = new PruneVisitor();
686       pruner.accept(program);
687       if (!pruner.didChange()) {
688         break;
689       }
690 
691       CleanupRefsVisitor cleaner = new CleanupRefsVisitor();
692       cleaner.accept(program);
693 
694       referencedTypes.clear();
695       referencedNonTypes.clear();
696       madeChanges = true;
697     }
698     return madeChanges;
699   }
700 
701 }
702
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags