001: /*
002: * Copyright 2007 Google Inc.
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License"); you may not
005: * use this file except in compliance with the License. You may obtain a copy of
006: * the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
012: * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
013: * License for the specific language governing permissions and limitations under
014: * the License.
015: */
016: package com.google.gwt.dev.jjs.impl;
017:
018: import com.google.gwt.dev.jjs.InternalCompilerException;
019: import com.google.gwt.dev.jjs.ast.Context;
020: import com.google.gwt.dev.jjs.ast.JExpression;
021: import com.google.gwt.dev.jjs.ast.JExpressionStatement;
022: import com.google.gwt.dev.jjs.ast.JLocalRef;
023: import com.google.gwt.dev.jjs.ast.JMethod;
024: import com.google.gwt.dev.jjs.ast.JMethodBody;
025: import com.google.gwt.dev.jjs.ast.JMethodCall;
026: import com.google.gwt.dev.jjs.ast.JModVisitor;
027: import com.google.gwt.dev.jjs.ast.JParameter;
028: import com.google.gwt.dev.jjs.ast.JParameterRef;
029: import com.google.gwt.dev.jjs.ast.JProgram;
030: import com.google.gwt.dev.jjs.ast.JReferenceType;
031: import com.google.gwt.dev.jjs.ast.JReturnStatement;
032: import com.google.gwt.dev.jjs.ast.JStatement;
033: import com.google.gwt.dev.jjs.ast.JThisRef;
034: import com.google.gwt.dev.jjs.ast.JVisitor;
035: import com.google.gwt.dev.jjs.ast.js.JMultiExpression;
036:
037: import java.util.ArrayList;
038: import java.util.HashSet;
039: import java.util.List;
040: import java.util.Set;
041:
042: /**
043: * Inline methods that can be inlined. The current implementation limits the
044: * methods that can be inlined to those that are composed of at most two
045: * top-level expressions.
046: *
047: * Future improvements will allow more complex methods to be inlined based on
048: * the number of call sites, as well as adding support for more complex target
049: * method expressions.
050: */
051: public class MethodInliner {
052:
053: /**
054: * Clones an expression, ensuring no local or this refs.
055: */
056: private class CloneCalleeExpressionVisitor extends
057: CloneExpressionVisitor {
058:
059: public CloneCalleeExpressionVisitor() {
060: super (program);
061: }
062:
063: @Override
064: public boolean visit(JLocalRef x, Context ctx) {
065: throw new InternalCompilerException(
066: "Unable to clone a local reference in a function being inlined");
067: }
068:
069: @Override
070: public boolean visit(JThisRef x, Context ctx) {
071: throw new InternalCompilerException(
072: "Should not encounter a JThisRef "
073: + "within a static method");
074: }
075: }
076:
077: /**
078: * Method inlining visitor.
079: */
080: private class InliningVisitor extends JModVisitor {
081:
082: protected final Set<JMethod> modifiedMethods = new HashSet<JMethod>();
083:
084: /**
085: * Resets with each new visitor, which is good since things that couldn't be
086: * inlined before might become inlinable.
087: */
088: private final Set<JMethod> cannotInline = new HashSet<JMethod>();
089: private JExpression ignoringReturnValueFor;
090:
091: @Override
092: public void endVisit(JMethod x, Context ctx) {
093: currentMethod = null;
094: }
095:
096: @Override
097: public void endVisit(JMethodCall x, Context ctx) {
098: JMethod method = x.getTarget();
099:
100: if (currentMethod == method) {
101: // Never try to inline a recursive call!
102: return;
103: }
104:
105: if (cannotInline.contains(method)) {
106: return;
107: }
108:
109: boolean possibleToInline = false;
110:
111: if (method.isStatic() && !method.isNative()) {
112: JMethodBody body = (JMethodBody) method.getBody();
113: List<JStatement> stmts = body.getStatements();
114:
115: if (method.getEnclosingType() != null
116: && method.getEnclosingType().methods.get(0) == method
117: && !stmts.isEmpty()) {
118: // clinit() calls cannot be inlined unless they are empty
119: possibleToInline = false;
120: } else {
121: JMultiExpression multi = createMultiExpressionFromBody(
122: body, ignoringReturnValueFor == x);
123: if (multi != null) {
124: possibleToInline = tryInlineExpression(x, ctx,
125: multi);
126: }
127: }
128: }
129:
130: // If it will never be possible to inline the method, add it to a
131: // blacklist
132: if (!possibleToInline) {
133: cannotInline.add(method);
134: }
135: }
136:
137: @Override
138: public boolean visit(JExpressionStatement x, Context ctx) {
139: ignoringReturnValueFor = x.getExpr();
140: return true;
141: }
142:
143: @Override
144: public boolean visit(JMethod x, Context ctx) {
145: currentMethod = x;
146: return true;
147: }
148:
149: private JMethodCall createClinitCall(JMethodCall x) {
150: JReferenceType targetEnclosingType = x.getTarget()
151: .getEnclosingType();
152: if (!program.typeOracle.checkClinit(currentMethod
153: .getEnclosingType(), targetEnclosingType)) {
154: // Access from this class to the target class won't trigger a clinit
155: return null;
156: }
157: if (program.isStaticImpl(x.getTarget())) {
158: // No clinit needed; target is really an instance method.
159: return null;
160: }
161: if (x.getTarget() == x.getTarget().getEnclosingType().methods
162: .get(0)) {
163: // This is a clinit call, doesn't need another clinit
164: return null;
165: }
166:
167: JMethod clinit = targetEnclosingType.methods.get(0);
168:
169: // If the clinit is a non-native, empty body we can optimize it out here
170: if (!clinit.isNative()
171: && (((JMethodBody) clinit.getBody()))
172: .getStatements().size() == 0) {
173: return null;
174: }
175:
176: return new JMethodCall(program, x.getSourceInfo(), null,
177: clinit);
178: }
179:
180: /**
181: * Creates a multi expression for evaluating a method call instance and
182: * possible clinit. This is a precursor for inlining the remainder of a
183: * method.
184: */
185: private JMultiExpression createMultiExpressionForInstanceAndClinit(
186: JMethodCall x) {
187: JMultiExpression multi = new JMultiExpression(program, x
188: .getSourceInfo());
189:
190: // Any instance expression goes first (this can happen even with statics).
191: if (x.getInstance() != null) {
192: multi.exprs.add(x.getInstance());
193: }
194:
195: // If we need a clinit call, add it first
196: JMethodCall clinit = createClinitCall(x);
197: if (clinit != null) {
198: multi.exprs.add(clinit);
199: }
200: return multi;
201: }
202:
203: /**
204: * Creates a JMultiExpression from a set of JExpressionStatements,
205: * optionally terminated by a JReturnStatement. If the method doesn't match
206: * this pattern, it returns <code>null</code>.
207: *
208: * If a method has a non-void return statement and can be represented as a
209: * multi-expression, the output of the multi-expression will be the return
210: * expression of the method. If the method is void, the output of the
211: * multi-expression should be considered undefined.
212: */
213: private JMultiExpression createMultiExpressionFromBody(
214: JMethodBody body, boolean ignoringReturnValue) {
215: JMultiExpression multi = new JMultiExpression(program, body
216: .getSourceInfo());
217: CloneCalleeExpressionVisitor cloner = new CloneCalleeExpressionVisitor();
218:
219: for (JStatement stmt : body.getStatements()) {
220: if (stmt instanceof JExpressionStatement) {
221: JExpressionStatement exprStmt = (JExpressionStatement) stmt;
222: JExpression expr = exprStmt.getExpr();
223: JExpression clone = cloner.cloneExpression(expr);
224: multi.exprs.add(clone);
225: } else if (stmt instanceof JReturnStatement) {
226: JReturnStatement returnStatement = (JReturnStatement) stmt;
227: JExpression expr = returnStatement.getExpr();
228: if (expr != null) {
229: if (!ignoringReturnValue
230: || expr.hasSideEffects()) {
231: JExpression clone = cloner
232: .cloneExpression(expr);
233: multi.exprs.add(clone);
234: }
235: }
236: // We hit an unconditional return; no need to evaluate anything else.
237: break;
238: } else {
239: // Any other kind of statement won't be inlinable.
240: return null;
241: }
242: }
243:
244: return multi;
245: }
246:
247: /**
248: * Creates a multi expression for evaluating a method call instance,
249: * possible clinit, and all arguments. This is a precursor for inlining the
250: * remainder of a method that does not reference any parameters.
251: */
252: private JMultiExpression createMultiExpressionIncludingArgs(
253: JMethodCall x) {
254: JMultiExpression multi = createMultiExpressionForInstanceAndClinit(x);
255:
256: for (int i = 0, c = x.getArgs().size(); i < c; ++i) {
257: JExpression arg = x.getArgs().get(i);
258: ExpressionAnalyzer analyzer = new ExpressionAnalyzer();
259: analyzer.accept(arg);
260:
261: if (analyzer.hasAssignment()
262: || analyzer.canThrowException()) {
263: multi.exprs.add(arg);
264: }
265: }
266: return multi;
267: }
268:
269: /**
270: * Replace the current expression with a given multi-expression and mark the
271: * method as modified. The dead-code elimination pass will optimize this if
272: * necessary.
273: */
274: private void replaceWithMulti(Context ctx,
275: JMultiExpression multi) {
276: ctx.replaceMe(multi);
277: modifiedMethods.add(currentMethod);
278: }
279:
280: /**
281: * Inline a call to an expression.
282: */
283: private boolean tryInlineExpression(JMethodCall x, Context ctx,
284: JMultiExpression targetExpr) {
285: List<JParameter> params = x.getTarget().params;
286: ArrayList<JExpression> args = x.getArgs();
287:
288: /*
289: * Limit inlined methods to multiexpressions of length 2 for now. This
290: * handles the simple { return JVariableRef; } or { expression; return
291: * something; } cases.
292: *
293: * TODO: add an expression complexity analyzer.
294: */
295: if (targetExpr.exprs.size() > 2) {
296: return false;
297: }
298:
299: // Do not inline anything that modifies one of its params.
300: ExpressionAnalyzer targetAnalyzer = new ExpressionAnalyzer();
301: targetAnalyzer.accept(targetExpr);
302: if (targetAnalyzer.hasAssignmentToParameter()) {
303: return false;
304: }
305:
306: // Make sure the expression we're about to inline doesn't include a call
307: // to the target method!
308: RecursionCheckVisitor recursionCheckVisitor = new RecursionCheckVisitor(
309: x.getTarget());
310: recursionCheckVisitor.accept(targetExpr);
311: if (recursionCheckVisitor.isRecursive()) {
312: return false;
313: }
314:
315: /*
316: * After this point, it's possible that the method might be inlinable at
317: * some call sites, depending on its arguments. From here on return 'true'
318: * as the method might be inlinable elsewhere.
319: */
320:
321: /*
322: * There are a different number of parameters than args - this is likely a
323: * result of parameter pruning. Don't consider this call site a candidate.
324: *
325: * TODO: would this be possible in the trivial delegation case?
326: */
327: if (params.size() != args.size()) {
328: return true;
329: }
330:
331: // Run the order check. This verifies that all the parameters are
332: // referenced once and only once, not within a conditionally-executing
333: // expression and before any tricky target expressions, such as:
334: // - assignments to any variable
335: // - expressions that throw exceptions
336: // - field references
337:
338: /*
339: * Ensure correct evaluation order or params relative to each other and to
340: * other expressions.
341: */
342: OrderVisitor orderVisitor = new OrderVisitor(
343: x.getTarget().params);
344: orderVisitor.accept(targetExpr);
345:
346: /*
347: * A method that doesn't touch any parameters is trivially inlinable (this
348: * covers the empty method case)
349: */
350: if (orderVisitor.checkResults() == SideEffectCheck.NO_REFERENCES) {
351: JMultiExpression multi = createMultiExpressionIncludingArgs(x);
352: multi.exprs.add(targetExpr);
353: replaceWithMulti(ctx, multi);
354: return true;
355: }
356:
357: /*
358: * We can still inline in the case where all of the actual arguments are
359: * "safe". They must have no side effects, and also have values which
360: * could not be affected by the execution of any code within the callee.
361: */
362: if (orderVisitor.checkResults() == SideEffectCheck.FAILS) {
363: for (JExpression arg : x.getArgs()) {
364: ExpressionAnalyzer argAnalyzer = new ExpressionAnalyzer();
365: argAnalyzer.accept(arg);
366:
367: if (argAnalyzer.hasAssignment()
368: || argAnalyzer.accessesField()
369: || argAnalyzer.createsObject()
370: || argAnalyzer.canThrowException()) {
371:
372: /*
373: * This argument evaluation could affect or be affected by the
374: * callee so we cannot inline here.
375: */
376: return true;
377: }
378: }
379: }
380:
381: // We're safe to inline.
382: JMultiExpression multi = createMultiExpressionForInstanceAndClinit(x);
383:
384: // Replace all params in the target expression with the actual arguments.
385: new ParameterReplacer(x).accept(targetExpr);
386:
387: multi.exprs.add(targetExpr);
388: replaceWithMulti(ctx, multi);
389: return true;
390: }
391: }
392:
393: /**
394: * Verifies that all the parameters are referenced once and only once, not
395: * within a conditionally-executing expression, and any before trouble some
396: * expressions evaluate. Examples of troublesome expressions include:
397: *
398: * <ul>
399: * <li>assignments to any variable</li>
400: * <li>expressions that throw exceptions</li>
401: * <li>field references</li>
402: * </ul>
403: */
404: private class OrderVisitor extends ExpressionAnalyzer {
405: private int currentIndex = 0;
406: private final List<JParameter> parameters;
407: private boolean succeeded = true;
408:
409: public OrderVisitor(List<JParameter> parameters) {
410: this .parameters = parameters;
411: }
412:
413: public SideEffectCheck checkResults() {
414: if (succeeded && currentIndex == parameters.size()) {
415: return SideEffectCheck.CORRECT_ORDER;
416: }
417:
418: if (succeeded && currentIndex == 0) {
419: return SideEffectCheck.NO_REFERENCES;
420: }
421:
422: return SideEffectCheck.FAILS;
423: }
424:
425: @Override
426: public void endVisit(JParameterRef x, Context ctx) {
427: JParameter param = x.getParameter();
428:
429: // If the expression has side-effects before a parameter reference, fail
430: if (hasAssignment() || accessesField()
431: || canThrowException()) {
432: succeeded = false;
433: }
434:
435: // If this parameter reference won't always execute, fail
436: if (isInConditional()) {
437: succeeded = false;
438: }
439:
440: // Ensure this parameter is evaluated in the correct order relative to
441: // other parameters.
442: if (parameters.indexOf(param) == currentIndex) {
443: currentIndex++;
444: } else {
445: succeeded = false;
446: }
447:
448: super .endVisit(x, ctx);
449: }
450: }
451:
452: /**
453: * Replace parameters inside an inlined expression with arguments to the
454: * inlined method.
455: */
456: private class ParameterReplacer extends JModVisitor {
457: private final JMethodCall methodCall;
458:
459: public ParameterReplacer(JMethodCall methodCall) {
460: this .methodCall = methodCall;
461: }
462:
463: @Override
464: public void endVisit(JParameterRef x, Context ctx) {
465: int paramIndex = methodCall.getTarget().params.indexOf(x
466: .getParameter());
467: assert paramIndex != -1;
468:
469: // Replace with a cloned call argument.
470: CloneExpressionVisitor cloner = new CloneExpressionVisitor(
471: program);
472: JExpression arg = methodCall.getArgs().get(paramIndex);
473: JExpression clone = cloner.cloneExpression(arg);
474: ctx.replaceMe(clone);
475: }
476: }
477:
478: private static class RecursionCheckVisitor extends JVisitor {
479: private boolean isRecursive = false;
480: private JMethod method;
481:
482: public RecursionCheckVisitor(JMethod method) {
483: this .method = method;
484: }
485:
486: public void endVisit(JMethodCall x, Context ctx) {
487: if (x.getTarget() == method) {
488: isRecursive = true;
489: }
490: }
491:
492: public boolean isRecursive() {
493: return isRecursive;
494: }
495: }
496:
497: /**
498: * Results of a side-effect and order check.
499: */
500: private enum SideEffectCheck {
501: CORRECT_ORDER, FAILS, NO_REFERENCES
502: }
503:
504: public static boolean exec(JProgram program) {
505: return new MethodInliner(program).execImpl();
506: }
507:
508: private JMethod currentMethod;
509: private final JProgram program;
510:
511: private MethodInliner(JProgram program) {
512: this .program = program;
513: }
514:
515: private boolean execImpl() {
516: boolean madeChanges = false;
517: while (true) {
518: InliningVisitor inliner = new InliningVisitor();
519: inliner.accept(program);
520: if (!inliner.didChange()) {
521: break;
522: }
523: madeChanges = true;
524:
525: // Run a cleanup on the methods we just modified
526: for (JMethod method : inliner.modifiedMethods) {
527: DeadCodeElimination.exec(program, method);
528: }
529: }
530: return madeChanges;
531: }
532: }
|