MethodInliner


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.SourceInfo;
19  import com.google.gwt.dev.jjs.ast.Context;
20  import com.google.gwt.dev.jjs.ast.JBlock;
21  import com.google.gwt.dev.jjs.ast.JExpression;
22  import com.google.gwt.dev.jjs.ast.JExpressionStatement;
23  import com.google.gwt.dev.jjs.ast.JField;
24  import com.google.gwt.dev.jjs.ast.JFieldRef;
25  import com.google.gwt.dev.jjs.ast.JLiteral;
26  import com.google.gwt.dev.jjs.ast.JMethod;
27  import com.google.gwt.dev.jjs.ast.JMethodCall;
28  import com.google.gwt.dev.jjs.ast.JModVisitor;
29  import com.google.gwt.dev.jjs.ast.JParameterRef;
30  import com.google.gwt.dev.jjs.ast.JProgram;
31  import com.google.gwt.dev.jjs.ast.JReferenceType;
32  import com.google.gwt.dev.jjs.ast.JReturnStatement;
33  import com.google.gwt.dev.jjs.ast.JStatement;
34  import com.google.gwt.dev.jjs.ast.JVisitor;
35  import com.google.gwt.dev.jjs.ast.js.JMultiExpression;
36  
37  import java.util.ArrayList  ;
38  import java.util.HashSet  ;
39  import java.util.Iterator  ;
40  import java.util.List  ;
41  import java.util.Set  ;
42  
43  /**
44   * Inline methods that can be inlined.
45   * 
46   * TODO(later): more aggressive inlining
47   */
48  public class MethodInliner {
49  
50    /**
51     * Flattens <code>JMultiExpressions</code> where possible.
52     * 
53     * TODO: make this a JModVisitor
54     */
55    public class FlattenMultiVisitor extends JVisitor {
56  
57      private boolean didChange = false;
58  
59      public boolean didChange() {
60        return didChange;
61      }
62  
63      // @Override
64      public void endVisit(JMultiExpression x, Context ctx) {
65        ArrayList   exprs = x.exprs;
66  
67        /*
68         * Add the contents of all nested multis into the top multi, in place. We
69         * are in fact iterating over nodes we've just added, but that should be
70         * okay as the children will already be flattened.
71         */
72        for (int i = 0; i < exprs.size(); ++i) {
73          JExpression expr = (JExpression) exprs.get(i);
74          if (expr instanceof JMultiExpression) {
75            JMultiExpression sub = (JMultiExpression) expr;
76            exprs.addAll(i + 1, sub.exprs);
77            didChange = true;
78          }
79        }
80  
81        // now remove the old multis
82        for (Iterator   it = exprs.iterator(); it.hasNext();) {
83          JExpression expr = (JExpression) it.next();
84          if (expr instanceof JMultiExpression) {
85            it.remove();
86            didChange = true;
87          }
88        }
89      }
90    }
91    /**
92     * Method inlining visitor.
93     */
94    public class InliningVisitor extends JModVisitor {
95      /**
96       * Resets with each new visitor, which is good since things that couldn't be
97       * inlined before might become inlineable.
98       */
99      Set  /* <JMethod> */cannotInline = new HashSet  /* <JMethod> */();
100 
101     public void endVisit(JMethod x, Context ctx) {
102       currentMethod = null;
103     }
104 
105     // @Override
106     public void endVisit(JMethodCall x, Context ctx) {
107       JMethod method = x.getTarget();
108 
109       // The method call must be known statically
110       if (!method.isStatic() || method.isNative()) {
111         return;
112       }
113 
114       if (cannotInline.contains(method)) {
115         return;
116       }
117 
118       List  /* <JStatement> */stmts = method.body.statements;
119       boolean possibleToInline = false;
120       if (stmts.isEmpty()) {
121         tryInlineEmptyMethodCall(x, ctx);
122         possibleToInline = true;
123       } else if (stmts.size() == 1) {
124         JStatement stmt = (JStatement) stmts.get(0);
125         if (stmt instanceof JReturnStatement) {
126           possibleToInline = tryInlineExpression(x, ctx,
127               ((JReturnStatement) stmt).getExpr());
128         } else if (stmt instanceof JExpressionStatement) {
129           possibleToInline = tryInlineExpression(x, ctx,
130               ((JExpressionStatement) stmt).getExpr());
131         }
132       }
133 
134       if (!possibleToInline) {
135         cannotInline.add(method);
136       }
137     }
138 
139     public boolean visit(JMethod x, Context ctx) {
140       currentMethod = x;
141       return true;
142     }
143 
144     /**
145      * This complicated method has a simple purpose: see if the expression part
146      * of a return statement is inlinable. The trickiness comes from the fact
147      * that we'd like to be able to do this recursively in certain cases. For
148      * example, the accessor method
149      * 
150      * <pre>
151      * $getFoo(this$static) {
152      *  return this$static.foo
153      * }
154      * </pre>
155      * 
156      * should be inlinable, but we have to first examine the field reference and
157      * then recursively determine that the qualifier is inlinable.
158      */
159     private JExpression canInlineExpression(SourceInfo info,
160         JExpression targetExpr, List  /* <JParameter> */params, ArrayList   args,
161         int[] magicArg) {
162       if (targetExpr instanceof JLiteral) {
163         // just reference the same JLiteral
164         /*
165          * hackish: pretend there is an arg that is returned which comes after
166          * all the real args; this allows the evaluation order check in
167          * tryInlineSimpleMethodCall to succeed
168          */
169         magicArg[0] = args.size();
170         return targetExpr;
171       } else if (targetExpr instanceof JParameterRef) {
172         // translate the param ref into the appropriate arg
173         int i = params.indexOf(((JParameterRef) targetExpr).getTarget());
174         assert (i >= 0);
175         magicArg[0] = i;
176         return (JExpression) args.get(i);
177       } else if (targetExpr instanceof JFieldRef) {
178         JFieldRef oldFieldRef = (JFieldRef) targetExpr;
179         JField field = oldFieldRef.getField();
180         JExpression instance = oldFieldRef.getInstance();
181         if (instance != null) {
182           // If an instance field, we have to be able to inline the qualifier
183           instance = canInlineExpression(info, instance, params, args, magicArg);
184           if (instance == null) {
185             return null;
186           }
187         }
188         JFieldRef newFieldRef = new JFieldRef(program, info, instance, field,
189             currentMethod.getEnclosingType());
190         return newFieldRef;
191       } else {
192         /*
193          * For now, only inline REALLY trivial stuff since we have no way of
194          * cloning arbitrary expressions.
195          */
196         return null;
197       }
198     }
199 
200     /**
201      * Returns <code>true</code> if inlining the target expression would
202      * eliminate a necessary clinit.
203      */
204     private boolean checkClinitViolation(JMethodCall x,
205         JExpression resultExpression) {
206       JReferenceType targetEnclosingType = x.getTarget().getEnclosingType();
207       if (!program.typeOracle.checkClinit(currentMethod.getEnclosingType(), targetEnclosingType)) {
208         // Access from this class to the target class won't trigger a clinit
209         return false;
210       }
211       if (program.isStaticImpl(x.getTarget())) {
212         // No clinit needed; target is really an instance method.
213         return false;
214       }
215 
216       /*
217        * Potential clinit violation! We can only allow this if the result is
218        * itself a static field ref into the target class, which would trigger
219        * the clinit itself.
220        */
221 
222       // resultExpression might be null, which behaves correctly here.
223       if (!(resultExpression instanceof JFieldRef)) {
224         return true;
225       }
226       JFieldRef fieldRefResult = (JFieldRef) resultExpression;
227       JField fieldResult = fieldRefResult.getField();
228       if (!fieldResult.isStatic()) {
229         // A nonstatic field reference won't trigger the clinit we need.
230         return true;
231       }
232       if (fieldResult.getEnclosingType() != targetEnclosingType) {
233         // We have a static field reference, but it's to the wrong class (not
234         // the class whose clinit we must trigger).
235         return true;
236       }
237       // The correct cross-class static field reference will trigger the clinit.
238       return false;
239     }
240 
241     /**
242      * Inlines a call to an empty method.
243      */
244     private void tryInlineEmptyMethodCall(JMethodCall x, Context ctx) {
245       if (checkClinitViolation(x, null)) {
246         return;
247       }
248       JMultiExpression multi = new JMultiExpression(program, x.getSourceInfo());
249       JExpression instance = x.getInstance();
250       if (instance != null && instance.hasSideEffects()) {
251         multi.exprs.add(x.getInstance());
252       }
253       for (int i = 0, c = x.getArgs().size(); i < c; ++i) {
254         if (((JExpression) x.getArgs().get(i)).hasSideEffects()) {
255           multi.exprs.add(x.getArgs().get(i));
256         }
257       }
258       ctx.replaceMe(multi);
259     }
260 
261     /**
262      * Inline a call to a method that contains only a return statement.
263      */
264     private boolean tryInlineExpression(JMethodCall x, Context ctx,
265         JExpression targetExpr) {
266       List  /* <JParameter> */params = x.getTarget().params;
267       ArrayList   args = x.getArgs();
268 
269       // the expression returned by the inlined method, if any
270       JExpression resultExpression;
271       // the argument that is returned by the inlined method, if any
272       int magicArg[] = new int[1];
273 
274       resultExpression = canInlineExpression(x.getSourceInfo(), targetExpr,
275           params, args, magicArg);
276 
277       if (resultExpression == null) {
278         return false; // cannot inline
279       }
280 
281       // The expression is inlinable.
282 
283       if (checkClinitViolation(x, resultExpression)) {
284         /*
285          * Inlining here would cause a clinit to not fire, so we can't. But
286          * return true, because this method could still be inlined from within
287          * the same class.
288          */
289         return true;
290       }
291 
292       // the argument that is returned by the inlined method
293       int iMagicArg = magicArg[0];
294 
295       JMultiExpression multi = new JMultiExpression(program, x.getSourceInfo());
296 
297       // Evaluate the instance argument (we can have one even with static calls)
298       JExpression instance = x.getInstance();
299       if (instance != null && instance.hasSideEffects()) {
300         multi.exprs.add(x.getInstance());
301       }
302 
303       // Now evaluate any side-effect args that aren't the magic arg.
304       for (int i = 0; i < params.size(); ++i) {
305         if (((JExpression) args.get(i)).hasSideEffects()) {
306           if (i < iMagicArg) {
307             // evaluate this arg inside of the multi
308             multi.exprs.add(args.get(i));
309           } else if (i == iMagicArg) {
310             // skip this arg, we'll do it below as the final one
311           } else {
312             assert (i > iMagicArg);
313             /*
314              * ABORT ABORT ABORT! This would cause an out-of-order evalutation.
315              * Due to the way we construct multis, the magic arg must come last.
316              * However, we've encountered a case where an argument coming after
317              * the magic arg must be evaluated. Just bail.
318              * 
319              * However, we return true because this call might be inlinable at
320              * other call sites.
321              */
322             return true;
323           }
324         }
325       }
326 
327       // add in the result expression as the last item in the multi
328       multi.exprs.add(resultExpression);
329       ctx.replaceMe(multi);
330       return true;
331     }
332   }
333 
334   /**
335    * Reduces <code>JMultiExpression</code> where possible.
336    */
337   public class ReduceMultiVisitor extends JModVisitor {
338 
339     // @Override
340     public void endVisit(JBlock x, Context ctx) {
341       for (Iterator   it = x.statements.iterator(); it.hasNext();) {
342         JStatement stmt = (JStatement) it.next();
343         // If we're a JExprStmt with no side effects, just remove me
344         if (stmt instanceof JExpressionStatement) {
345           JExpression expr = ((JExpressionStatement) stmt).getExpr();
346           if (!expr.hasSideEffects()) {
347             it.remove();
348             didChange = true;
349           }
350         }
351       }
352     }
353 
354     // @Override
355     public void endVisit(JMultiExpression x, Context ctx) {
356       ArrayList   exprs = x.exprs;
357 
358       final int c = exprs.size();
359       if (c == 0) {
360         return;
361       }
362 
363       int countSideEffectsBeforeLast = 0;
364       for (int i = 0; i < c - 1; ++i) {
365         JExpression expr = (JExpression) exprs.get(i);
366         if (expr.hasSideEffects()) {
367           ++countSideEffectsBeforeLast;
368         }
369       }
370 
371       if (countSideEffectsBeforeLast == 0) {
372         ctx.replaceMe((JExpression) x.exprs.get(c - 1));
373       } else {
374         JMultiExpression newMulti = new JMultiExpression(program,
375             x.getSourceInfo());
376         for (int i = 0; i < c - 1; ++i) {
377           JExpression expr = (JExpression) exprs.get(i);
378           if (expr.hasSideEffects()) {
379             newMulti.exprs.add(expr);
380           }
381         }
382         newMulti.exprs.add(x.exprs.get(c - 1));
383         if (newMulti.exprs.size() < x.exprs.size()) {
384           ctx.replaceMe(newMulti);
385         }
386       }
387     }
388   }
389 
390   public static boolean exec(JProgram program) {
391     return new MethodInliner(program).execImpl();
392   }
393 
394   private JMethod currentMethod;
395   private final JProgram program;
396 
397   private MethodInliner(JProgram program) {
398     this.program = program;
399   }
400 
401   private boolean execImpl() {
402     boolean madeChanges = false;
403     while (true) {
404       InliningVisitor inliner = new InliningVisitor();
405       inliner.accept(program);
406       if (!inliner.didChange()) {
407         break;
408       }
409       madeChanges = true;
410 
411       FlattenMultiVisitor flattener = new FlattenMultiVisitor();
412       flattener.accept(program);
413 
414       ReduceMultiVisitor reducer = new ReduceMultiVisitor();
415       reducer.accept(program);
416     }
417     return madeChanges;
418   }
419 
420 }
421
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags