dev/core/src/com/google/gwt/dev/jjs/impl/MakeCallsStatic.java - gwt - Git at Google

 /*
  * Copyright 2008 Google Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License"); you may not
  * use this file except in compliance with the License. You may obtain a copy of
  * the License at
  *
  * http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
  * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
  * License for the specific language governing permissions and limitations under
  * the License.
  */
 package com.google.gwt.dev.jjs.impl;

 import com.google.gwt.dev.jjs.InternalCompilerException;
 import com.google.gwt.dev.jjs.SourceInfo;
 import com.google.gwt.dev.jjs.ast.Context;
 import com.google.gwt.dev.jjs.ast.JAbstractMethodBody;
 import com.google.gwt.dev.jjs.ast.JConstructor;
 import com.google.gwt.dev.jjs.ast.JDeclaredType;
 import com.google.gwt.dev.jjs.ast.JExpression;
 import com.google.gwt.dev.jjs.ast.JMethod;
 import com.google.gwt.dev.jjs.ast.JMethod.Specialization;
 import com.google.gwt.dev.jjs.ast.JMethodBody;
 import com.google.gwt.dev.jjs.ast.JMethodCall;
 import com.google.gwt.dev.jjs.ast.JParameter;
 import com.google.gwt.dev.jjs.ast.JParameterRef;
 import com.google.gwt.dev.jjs.ast.JProgram;
 import com.google.gwt.dev.jjs.ast.JThisRef;
 import com.google.gwt.dev.jjs.ast.JType;
 import com.google.gwt.dev.jjs.ast.JVisitor;
 import com.google.gwt.dev.jjs.ast.RuntimeConstants;
 import com.google.gwt.dev.jjs.ast.js.JMultiExpression;
 import com.google.gwt.dev.jjs.ast.js.JsniMethodBody;
 import com.google.gwt.dev.jjs.impl.codesplitter.CodeSplitter;
 import com.google.gwt.dev.js.ast.JsContext;
 import com.google.gwt.dev.js.ast.JsFunction;
 import com.google.gwt.dev.js.ast.JsModVisitor;
 import com.google.gwt.dev.js.ast.JsName;
 import com.google.gwt.dev.js.ast.JsParameter;
 import com.google.gwt.dev.js.ast.JsThisRef;
 import com.google.gwt.dev.util.log.speedtracer.CompilerEventType;
 import com.google.gwt.dev.util.log.speedtracer.SpeedTracerLogger;
 import com.google.gwt.dev.util.log.speedtracer.SpeedTracerLogger.Event;
 import com.google.gwt.thirdparty.guava.common.annotations.VisibleForTesting;
 import com.google.gwt.thirdparty.guava.common.collect.Lists;
 import com.google.gwt.thirdparty.guava.common.collect.Maps;
 import com.google.gwt.thirdparty.guava.common.collect.Sets;

 import java.util.List;
 import java.util.Map;
 import java.util.Set;

 /**
  * This is an interesting "optimization". It's not really an optimization in and
  * of itself, but it opens the door to other optimizations. The basic idea is
  * that you look for calls to instance methods that are not actually
  * polymorphic. In other words, the target method is (effectively) final, not
  * overridden anywhere in the compilation. We rewrite the single instance method
  * as a static method that contains the implementation plus an instance method
  * that delegates to the static method. Then we update any call sites to call
  * the static method instead. This opens the door to further optimizations,
  * reduces use of the long "this" keyword in the resulting JavaScript, and in
  * most cases the polymorphic version can be pruned later.
  */
 public class MakeCallsStatic {
   /**
    * For all methods that should be made static, move the contents of the method
    * to a new static method, and have the original (instance) method delegate to
    * it. Sometimes the instance method can be pruned later since we update all
    * non-polymorphic call sites.
    */
   static class CreateStaticImplsVisitor extends JVisitor {
     /**
      * When code is moved from an instance method to a static method, all
      * thisRefs must be replaced with paramRefs to the synthetic this param.
      */
     private static class RewriteJsniMethodBody extends JsModVisitor {

       private final JsName thisParam;

       public RewriteJsniMethodBody(JsName thisParam) {
         this.thisParam = thisParam;
       }

       @Override
       public void endVisit(JsThisRef x, JsContext ctx) {
         ctx.replaceMe(thisParam.makeRef(x.getSourceInfo()));
       }

       @Override
       public boolean visit(JsFunction x, JsContext ctx) {
         // Don't recurse into nested functions!
         return false;
       }
     }

     /**
      * When code is moved from an instance method to a static method, all
      * thisRefs must be replaced with paramRefs to the synthetic this param.
      * ParameterRefs also need to be targeted to the params in the new method.
      */
     private class RewriteMethodBody extends JChangeTrackingVisitor {

       private final JParameter thisParam;
       private final Map<JParameter, JParameter> varMap;

       public RewriteMethodBody(JParameter thisParam, Map<JParameter, JParameter> varMap,
           OptimizerContext optimizerCtx) {
         super(optimizerCtx);
         this.thisParam = thisParam;
         this.varMap = varMap;
       }

       @Override
       public void endVisit(JParameterRef x, Context ctx) {
         JParameter param = varMap.get(x.getTarget());
         ctx.replaceMe(param.makeRef(x.getSourceInfo()));
       }

       @Override
       public void endVisit(JThisRef x, Context ctx) {
         ctx.replaceMe(thisParam.makeRef(x.getSourceInfo()));
       }
     }

     private final JProgram program;
     private final OptimizerContext optimizerCtx;

     private CreateStaticImplsVisitor(JProgram program, OptimizerContext optimizerCtx) {
       this.program = program;
       this.optimizerCtx = optimizerCtx;
     }

     CreateStaticImplsVisitor(JProgram program) {
       this.program = program;
       this.optimizerCtx = null;
     }

     @Override
     public boolean visit(JConstructor x, Context ctx) {
       throw new InternalCompilerException("Should not try to staticify constructors");
     }

     @Override
     public boolean visit(JMethod x, Context ctx) {
       assert !x.isJsNative() : "Native methods can not be devirtualized";

       // Let's do it!
       JDeclaredType enclosingType = x.getEnclosingType();
       JType returnType = x.getType();
       SourceInfo sourceInfo = x.getSourceInfo().makeChild();
       int myIndexInClass = enclosingType.getMethods().indexOf(x);
       assert (myIndexInClass > 0);

       // Create the new static method
       String newName = getStaticMethodName(x);

       /*
        * Don't use the JProgram helper because it auto-adds the new method to
        * its enclosing class.
        */
       JMethod newMethod =
           new JMethod(sourceInfo, newName, enclosingType, returnType, false, true, true, x
               .getAccess());
       newMethod.setInliningMode(x.getInliningMode());
       newMethod.setHasSideEffects(x.hasSideEffects());
       newMethod.setSynthetic();
       newMethod.addThrownExceptions(x.getThrownExceptions());
       if (x.isJsOverlay()) {
         newMethod.setJsOverlay();
       }

       // Do not strengthen to non null since the implicit NPE in instance dispatch is gone.
       JType thisParameterType = enclosingType;
       // Setup parameters; map from the old params to the new params
       JParameter thisParam = newMethod.createThisParameter(sourceInfo, thisParameterType);
       Map<JParameter, JParameter> varMap = Maps.newIdentityHashMap();
       for (JParameter oldVar : x.getParams()) {
         JParameter newVar = newMethod.cloneParameter(oldVar);
         varMap.put(oldVar, newVar);
       }

       // Set the new original param types based on the old original param types
       List<JType> originalParamTypes = Lists.newArrayList();
       originalParamTypes.add(thisParameterType);
       originalParamTypes.addAll(x.getOriginalParamTypes());
       newMethod.setOriginalTypes(x.getOriginalReturnType(), originalParamTypes);

       // Move the body of the instance method to the static method
       JAbstractMethodBody movedBody = x.getBody();
       newMethod.setBody(movedBody);

       JMethodBody newBody = new JMethodBody(sourceInfo);
       x.setBody(newBody);
       JMethodCall newCall = new JMethodCall(sourceInfo, null, newMethod);
       newCall.addArg(new JThisRef(sourceInfo, enclosingType));
       for (int i = 0; i < x.getParams().size(); ++i) {
         JParameter param = x.getParams().get(i);
         newCall.addArg(param.makeRef(sourceInfo));
       }
       newBody.getBlock().addStmt(JjsUtils.makeMethodEndStatement(returnType, newCall));

       /*
        * Rewrite the method body. Update all thisRefs to paramRefs. Update
        * paramRefs and localRefs to target the params/locals in the new method.
        */
       if (newMethod.isJsniMethod()) {
         // For natives, we also need to create the JsParameter for this$static,
         // because the jsFunc already has parameters.
         // TODO: Do we really need to do that in BuildTypeMap?
         JsFunction jsFunc = ((JsniMethodBody) movedBody).getFunc();
         JsName paramName = jsFunc.getScope().declareName("this$static");
         jsFunc.getParameters().add(0, new JsParameter(sourceInfo, paramName));
         RewriteJsniMethodBody rewriter = new RewriteJsniMethodBody(paramName);
         // Accept the body to avoid the recursion blocker.
         rewriter.accept(jsFunc.getBody());
       } else {
         RewriteMethodBody rewriter = new RewriteMethodBody(thisParam, varMap, optimizerCtx);
         rewriter.accept(movedBody);
       }

       // Add the new method as a static impl of the old method
       program.putStaticImpl(x, newMethod);
       enclosingType.getMethods().add(myIndexInClass + 1, newMethod);

       if (optimizerCtx != null) {
         optimizerCtx.markModified(x);
         optimizerCtx.markModified(newMethod);
       }
       return false;
     }

     public JMethod getOrCreateStaticImpl(JProgram program, JMethod method) {
       assert !method.isStatic();
       JMethod staticImpl = program.getStaticImpl(method);
       if (staticImpl == null) {
         accept(method);
         staticImpl = program.getStaticImpl(method);
       }
       return staticImpl;
     }
   }

   private static String getStaticMethodName(JMethod x) {
     return "$" + x.getName();
   }

   /**
    * Look for any places where instance methods are called in a static manner.
    * Record this fact so we can create static dispatch implementations.
    */
   private class FindStaticDispatchSitesVisitor extends JVisitor {
     @Override
     public void endVisit(JMethodCall x, Context ctx) {
       JMethod method = x.getTarget();

       if (shouldBeMadeStatic(x, method)) {
         // Let's do it!
         toBeMadeStatic.add(method);
         if (method.getSpecialization() != null &&
             shouldBeMadeStatic(x,
                 method.getSpecialization().getTargetMethod())) {
           toBeMadeStatic.add(method.getSpecialization().getTargetMethod());
         }
       }
     }

     private boolean shouldBeMadeStatic(JMethodCall x, JMethod method) {
       if (method.isExternal()) {
         // Staticifying a method requires modifying the type, which we can't
         // do for external types. Theoretically we could put the static method
         // in some generated code, but what does that really buy us?
         return false;
       }

       if (!method.isDevirtualizationAllowed()) {
         // Method has been specifically excluded from statification.
         return false;
       }

       // Did we already do this one?
       if (program.getStaticImpl(method) != null || toBeMadeStatic.contains(method)) {
         return false;
       }

       // Must be instance and final
       if (x.canBePolymorphic()) {
         return false;
       }
       if (!method.needsDynamicDispatch()) {
         return false;
       }
       if (method.isAbstract()) {
         return false;
       }
       if (method.isJsNative()) {
         return false;
       }
       if (method == program.getNullMethod()) {
         // Special case: we don't make calls to this method static.
         return false;
       }

       if (!method.getEnclosingType().getMethods().contains(method)) {
         // The target method was already pruned (TypeTightener will fix this).
         return false;
       }

       return true;
     }
   }

   /**
    * For any method calls to methods we updated during
    * CreateStaticMethodVisitor, go and rewrite the call sites to call the static
    * method instead.
    */
   private class RewriteCallSites extends JChangeTrackingVisitor {

     private boolean currentMethodIsInitiallyLive;
     private ControlFlowAnalyzer initiallyLive;

     public RewriteCallSites(OptimizerContext optimizerCtx) {
       super(optimizerCtx);
     }

     /**
      * In cases where callers are directly referencing (effectively) final
      * instance methods, rewrite the call site to reference the newly-generated
      * static method instead.
      */
     @Override
     public void endVisit(JMethodCall x, Context ctx) {
       JMethod oldMethod = x.getTarget();
       JMethod newMethod = program.getStaticImpl(oldMethod);

       if (newMethod == null || x.canBePolymorphic()) {
         return;
       }

       if (currentMethodIsInitiallyLive
           && !initiallyLive.getLiveFieldsAndMethods().contains(x.getTarget())) {
         /*
          * Don't devirtualize calls from initial code to non-initial code.
          *
          * TODO(spoon): similar prevention when the callee is exclusive to some
          * split point and the caller is not.
          */
         return;
       }

       ctx.replaceMe(converter.convertCall(x, newMethod));
     }

     @Override
     public boolean enter(JMethod x, Context ctx) {
       currentMethodIsInitiallyLive = initiallyLive.getLiveFieldsAndMethods().contains(x);
       return true;
     }

     @Override
     public boolean visit(JProgram x, Context ctx) {
       // TODO(rluble): This needs to be abstracted out the CodeSplitter.
       initiallyLive = CodeSplitter.computeInitiallyLive(x);
       return true;
     }
   }

   /**
    * Converts instance method calls to equivalent static method calls.
    * Optionally adds a null check on the former "this" parameter.
    */
   static class StaticCallConverter {
     private final JMethod checkNotNull;

     StaticCallConverter(JProgram program, boolean addNullChecksForThis) {
       if (addNullChecksForThis) {
         checkNotNull = program.getIndexedMethod(RuntimeConstants.EXCEPTIONS_CHECK_NOT_NULL);
       } else {
         checkNotNull = null;
       }
     }

     /**
      * Converts an instance method call to the equivalent static method call.
      * @param original the instance method call to convert
      * @param newMethod the static method to call instead
      */
     JExpression convertCall(JMethodCall original, JMethod newMethod) {

       JMethodCall newCall = new JMethodCall(original.getSourceInfo(), null, newMethod);

       /*
        * If the qualifier is a JMultiExpression, invoke on the last value. This
        * ensures that clinits maintain the same execution order relative to
        * parameters in deeply-inlined scenarios.
        */
       //   (a, b).foo() --> (a, foo(b))
       // Or in checked mode:
       //   (a, b).foo() --> (a, foo(checkNotNull(b)))
       if (original.getInstance() instanceof JMultiExpression) {
         JMultiExpression multi = (JMultiExpression) original.getInstance();
         int lastIndex = multi.getNumberOfExpressions() - 1;
         newCall.addArg(makeNullCheck(multi.getExpression(lastIndex), original));
         newCall.addArgs(original.getArgs());
         multi.setExpression(lastIndex, newCall);
         return multi;
       } else {
         // The qualifier becomes the first argument.
         //   a.foo(b) --> foo(a,b)
         // or in checked mode:
         //   a.foo(b) --> foo(checkNotNull(a),b)
         newCall.addArg(makeNullCheck(original.getInstance(), original));
         newCall.addArgs(original.getArgs());
         return newCall;
       }
     }

     private JExpression makeNullCheck(JExpression x, JMethodCall call) {
       if (checkNotNull == null) {
         return x;
       }

       // Existing code plays tricks with JSO's, so don't add the null check.
       if (isJso(call)) {
         return x;
       }

       JMethodCall check = new JMethodCall(x.getSourceInfo(), null, checkNotNull);
       check.addArg(x);
       return check;
     }

     private boolean isJso(JMethodCall call) {
       JDeclaredType type = call.getTarget().getEnclosingType();
       return type != null && type.isJsoType();
     }
   }

   private static final String NAME = MakeCallsStatic.class.getSimpleName();

   public static OptimizerStats exec(JProgram program, boolean addRuntimeChecks,
       OptimizerContext optimizerCtx) {
     Event optimizeEvent = SpeedTracerLogger.start(CompilerEventType.OPTIMIZE, "optimizer", NAME);
     OptimizerStats stats = new MakeCallsStatic(program, addRuntimeChecks).execImpl(optimizerCtx);
     optimizerCtx.setLastStepFor(NAME, optimizerCtx.getOptimizationStep());
     optimizerCtx.incOptimizationStep();
     optimizeEvent.end("didChange", "" + stats.didChange());
     return stats;
   }

   @VisibleForTesting
   static OptimizerStats exec(JProgram program,  boolean addRuntimeChecks) {
     return exec(program, addRuntimeChecks, new FullOptimizerContext(program));
   }

   protected Set<JMethod> toBeMadeStatic = Sets.newLinkedHashSet();

   private final JProgram program;
   private final StaticCallConverter converter;

   private MakeCallsStatic(JProgram program, boolean addRuntimeChecks) {
     this.program = program;
     this.converter = new StaticCallConverter(program, addRuntimeChecks);
   }

   private OptimizerStats execImpl(OptimizerContext optimizerCtx) {
     OptimizerStats stats = new OptimizerStats(NAME);
     FindStaticDispatchSitesVisitor finder = new FindStaticDispatchSitesVisitor();
     Set<JMethod> modifiedMethods =
         optimizerCtx.getModifiedMethodsSince(optimizerCtx.getLastStepFor(NAME));
     Set<JMethod> affectedMethods = affectedMethods(modifiedMethods, optimizerCtx);
     optimizerCtx.traverse(finder, affectedMethods);

     CreateStaticImplsVisitor creator = new CreateStaticImplsVisitor(program, optimizerCtx);
     for (JMethod method : toBeMadeStatic) {
       creator.accept(method);
     }
     for (JMethod method : toBeMadeStatic) {
       // if method has specialization, add it to the static method
       Specialization specialization = method.getSpecialization();
       if (specialization != null) {
         JMethod staticMethod = program.getStaticImpl(method);
         List<JType> params = Lists.newArrayList(specialization.getParams());
         params.add(0, staticMethod.getParams().get(0).getType());
         staticMethod.setSpecialization(params, specialization.getReturns(),
             staticMethod.getName());
         staticMethod.getSpecialization().resolve(params,
             specialization.getReturns(), program.getStaticImpl(specialization
                 .getTargetMethod()));
       }
     }

     /*
      * Run the rewriter even if we didn't make any new static methods; other
      * optimizations can unlock devirtualizations even if no more static impls
      * are created.
      */
     RewriteCallSites rewriter = new RewriteCallSites(optimizerCtx);
     rewriter.accept(program);
     stats.recordModified(rewriter.getNumMods());
     assert (rewriter.didChange() || toBeMadeStatic.isEmpty());
     JavaAstVerifier.assertProgramIsConsistent(program);
     return stats;
   }

   /**
    * Return the set of methods affected (because they are or callers of) by the modifications to the
    * given set functions.
    */
   private Set<JMethod> affectedMethods(Set<JMethod> modifiedMethods,
       OptimizerContext optimizerCtx) {
     assert (modifiedMethods != null);
     Set<JMethod> affectedMethods = Sets.newLinkedHashSet();
     affectedMethods.addAll(modifiedMethods);
     affectedMethods.addAll(optimizerCtx.getCallers(modifiedMethods));
     return affectedMethods;
   }
 }
	/*
	* Copyright 2008 Google Inc.
	*
	* Licensed under the Apache License, Version 2.0 (the "License"); you may not
	* use this file except in compliance with the License. You may obtain a copy of
	* the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
	* WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
	* License for the specific language governing permissions and limitations under
	* the License.
	*/
	package com.google.gwt.dev.jjs.impl;

	import com.google.gwt.dev.jjs.InternalCompilerException;
	import com.google.gwt.dev.jjs.SourceInfo;
	import com.google.gwt.dev.jjs.ast.Context;
	import com.google.gwt.dev.jjs.ast.JAbstractMethodBody;
	import com.google.gwt.dev.jjs.ast.JConstructor;
	import com.google.gwt.dev.jjs.ast.JDeclaredType;
	import com.google.gwt.dev.jjs.ast.JExpression;
	import com.google.gwt.dev.jjs.ast.JMethod;
	import com.google.gwt.dev.jjs.ast.JMethod.Specialization;
	import com.google.gwt.dev.jjs.ast.JMethodBody;
	import com.google.gwt.dev.jjs.ast.JMethodCall;
	import com.google.gwt.dev.jjs.ast.JParameter;
	import com.google.gwt.dev.jjs.ast.JParameterRef;
	import com.google.gwt.dev.jjs.ast.JProgram;
	import com.google.gwt.dev.jjs.ast.JThisRef;
	import com.google.gwt.dev.jjs.ast.JType;
	import com.google.gwt.dev.jjs.ast.JVisitor;
	import com.google.gwt.dev.jjs.ast.RuntimeConstants;
	import com.google.gwt.dev.jjs.ast.js.JMultiExpression;
	import com.google.gwt.dev.jjs.ast.js.JsniMethodBody;
	import com.google.gwt.dev.jjs.impl.codesplitter.CodeSplitter;
	import com.google.gwt.dev.js.ast.JsContext;
	import com.google.gwt.dev.js.ast.JsFunction;
	import com.google.gwt.dev.js.ast.JsModVisitor;
	import com.google.gwt.dev.js.ast.JsName;
	import com.google.gwt.dev.js.ast.JsParameter;
	import com.google.gwt.dev.js.ast.JsThisRef;
	import com.google.gwt.dev.util.log.speedtracer.CompilerEventType;
	import com.google.gwt.dev.util.log.speedtracer.SpeedTracerLogger;
	import com.google.gwt.dev.util.log.speedtracer.SpeedTracerLogger.Event;
	import com.google.gwt.thirdparty.guava.common.annotations.VisibleForTesting;
	import com.google.gwt.thirdparty.guava.common.collect.Lists;
	import com.google.gwt.thirdparty.guava.common.collect.Maps;
	import com.google.gwt.thirdparty.guava.common.collect.Sets;

	import java.util.List;
	import java.util.Map;
	import java.util.Set;

	/**
	* This is an interesting "optimization". It's not really an optimization in and
	* of itself, but it opens the door to other optimizations. The basic idea is
	* that you look for calls to instance methods that are not actually
	* polymorphic. In other words, the target method is (effectively) final, not
	* overridden anywhere in the compilation. We rewrite the single instance method
	* as a static method that contains the implementation plus an instance method
	* that delegates to the static method. Then we update any call sites to call
	* the static method instead. This opens the door to further optimizations,
	* reduces use of the long "this" keyword in the resulting JavaScript, and in
	* most cases the polymorphic version can be pruned later.
	*/
	public class MakeCallsStatic {
	/**
	* For all methods that should be made static, move the contents of the method
	* to a new static method, and have the original (instance) method delegate to
	* it. Sometimes the instance method can be pruned later since we update all
	* non-polymorphic call sites.
	*/
	static class CreateStaticImplsVisitor extends JVisitor {
	/**
	* When code is moved from an instance method to a static method, all
	* thisRefs must be replaced with paramRefs to the synthetic this param.
	*/
	private static class RewriteJsniMethodBody extends JsModVisitor {

	private final JsName thisParam;

	public RewriteJsniMethodBody(JsName thisParam) {
	this.thisParam = thisParam;
	}

	@Override
	public void endVisit(JsThisRef x, JsContext ctx) {
	ctx.replaceMe(thisParam.makeRef(x.getSourceInfo()));
	}

	@Override
	public boolean visit(JsFunction x, JsContext ctx) {
	// Don't recurse into nested functions!
	return false;
	}
	}

	/**
	* When code is moved from an instance method to a static method, all
	* thisRefs must be replaced with paramRefs to the synthetic this param.
	* ParameterRefs also need to be targeted to the params in the new method.
	*/
	private class RewriteMethodBody extends JChangeTrackingVisitor {

	private final JParameter thisParam;
	private final Map<JParameter, JParameter> varMap;

	public RewriteMethodBody(JParameter thisParam, Map<JParameter, JParameter> varMap,
	OptimizerContext optimizerCtx) {
	super(optimizerCtx);
	this.thisParam = thisParam;
	this.varMap = varMap;
	}

	@Override
	public void endVisit(JParameterRef x, Context ctx) {
	JParameter param = varMap.get(x.getTarget());
	ctx.replaceMe(param.makeRef(x.getSourceInfo()));
	}

	@Override
	public void endVisit(JThisRef x, Context ctx) {
	ctx.replaceMe(thisParam.makeRef(x.getSourceInfo()));
	}
	}

	private final JProgram program;
	private final OptimizerContext optimizerCtx;

	private CreateStaticImplsVisitor(JProgram program, OptimizerContext optimizerCtx) {
	this.program = program;
	this.optimizerCtx = optimizerCtx;
	}

	CreateStaticImplsVisitor(JProgram program) {
	this.program = program;
	this.optimizerCtx = null;
	}

	@Override
	public boolean visit(JConstructor x, Context ctx) {
	throw new InternalCompilerException("Should not try to staticify constructors");
	}

	@Override
	public boolean visit(JMethod x, Context ctx) {
	assert !x.isJsNative() : "Native methods can not be devirtualized";

	// Let's do it!
	JDeclaredType enclosingType = x.getEnclosingType();
	JType returnType = x.getType();
	SourceInfo sourceInfo = x.getSourceInfo().makeChild();
	int myIndexInClass = enclosingType.getMethods().indexOf(x);
	assert (myIndexInClass > 0);

	// Create the new static method
	String newName = getStaticMethodName(x);

	/*
	* Don't use the JProgram helper because it auto-adds the new method to
	* its enclosing class.
	*/
	JMethod newMethod =
	new JMethod(sourceInfo, newName, enclosingType, returnType, false, true, true, x
	.getAccess());
	newMethod.setInliningMode(x.getInliningMode());
	newMethod.setHasSideEffects(x.hasSideEffects());
	newMethod.setSynthetic();
	newMethod.addThrownExceptions(x.getThrownExceptions());
	if (x.isJsOverlay()) {
	newMethod.setJsOverlay();
	}

	// Do not strengthen to non null since the implicit NPE in instance dispatch is gone.
	JType thisParameterType = enclosingType;
	// Setup parameters; map from the old params to the new params
	JParameter thisParam = newMethod.createThisParameter(sourceInfo, thisParameterType);
	Map<JParameter, JParameter> varMap = Maps.newIdentityHashMap();
	for (JParameter oldVar : x.getParams()) {
	JParameter newVar = newMethod.cloneParameter(oldVar);
	varMap.put(oldVar, newVar);
	}

	// Set the new original param types based on the old original param types
	List<JType> originalParamTypes = Lists.newArrayList();
	originalParamTypes.add(thisParameterType);
	originalParamTypes.addAll(x.getOriginalParamTypes());
	newMethod.setOriginalTypes(x.getOriginalReturnType(), originalParamTypes);

	// Move the body of the instance method to the static method
	JAbstractMethodBody movedBody = x.getBody();
	newMethod.setBody(movedBody);

	JMethodBody newBody = new JMethodBody(sourceInfo);
	x.setBody(newBody);
	JMethodCall newCall = new JMethodCall(sourceInfo, null, newMethod);
	newCall.addArg(new JThisRef(sourceInfo, enclosingType));
	for (int i = 0; i < x.getParams().size(); ++i) {
	JParameter param = x.getParams().get(i);
	newCall.addArg(param.makeRef(sourceInfo));
	}
	newBody.getBlock().addStmt(JjsUtils.makeMethodEndStatement(returnType, newCall));

	/*
	* Rewrite the method body. Update all thisRefs to paramRefs. Update
	* paramRefs and localRefs to target the params/locals in the new method.
	*/
	if (newMethod.isJsniMethod()) {
	// For natives, we also need to create the JsParameter for this$static,
	// because the jsFunc already has parameters.
	// TODO: Do we really need to do that in BuildTypeMap?
	JsFunction jsFunc = ((JsniMethodBody) movedBody).getFunc();
	JsName paramName = jsFunc.getScope().declareName("this$static");
	jsFunc.getParameters().add(0, new JsParameter(sourceInfo, paramName));
	RewriteJsniMethodBody rewriter = new RewriteJsniMethodBody(paramName);
	// Accept the body to avoid the recursion blocker.
	rewriter.accept(jsFunc.getBody());
	} else {
	RewriteMethodBody rewriter = new RewriteMethodBody(thisParam, varMap, optimizerCtx);
	rewriter.accept(movedBody);
	}

	// Add the new method as a static impl of the old method
	program.putStaticImpl(x, newMethod);
	enclosingType.getMethods().add(myIndexInClass + 1, newMethod);

	if (optimizerCtx != null) {
	optimizerCtx.markModified(x);
	optimizerCtx.markModified(newMethod);
	}
	return false;
	}

	public JMethod getOrCreateStaticImpl(JProgram program, JMethod method) {
	assert !method.isStatic();
	JMethod staticImpl = program.getStaticImpl(method);
	if (staticImpl == null) {
	accept(method);
	staticImpl = program.getStaticImpl(method);
	}
	return staticImpl;
	}
	}

	private static String getStaticMethodName(JMethod x) {
	return "$" + x.getName();
	}

	/**
	* Look for any places where instance methods are called in a static manner.
	* Record this fact so we can create static dispatch implementations.
	*/
	private class FindStaticDispatchSitesVisitor extends JVisitor {
	@Override
	public void endVisit(JMethodCall x, Context ctx) {
	JMethod method = x.getTarget();

	if (shouldBeMadeStatic(x, method)) {
	// Let's do it!
	toBeMadeStatic.add(method);
	if (method.getSpecialization() != null &&
	shouldBeMadeStatic(x,
	method.getSpecialization().getTargetMethod())) {
	toBeMadeStatic.add(method.getSpecialization().getTargetMethod());
	}
	}
	}

	private boolean shouldBeMadeStatic(JMethodCall x, JMethod method) {
	if (method.isExternal()) {
	// Staticifying a method requires modifying the type, which we can't
	// do for external types. Theoretically we could put the static method
	// in some generated code, but what does that really buy us?
	return false;
	}

	if (!method.isDevirtualizationAllowed()) {
	// Method has been specifically excluded from statification.
	return false;
	}

	// Did we already do this one?
	if (program.getStaticImpl(method) != null \|\| toBeMadeStatic.contains(method)) {
	return false;
	}

	// Must be instance and final
	if (x.canBePolymorphic()) {
	return false;
	}
	if (!method.needsDynamicDispatch()) {
	return false;
	}
	if (method.isAbstract()) {
	return false;
	}
	if (method.isJsNative()) {
	return false;
	}
	if (method == program.getNullMethod()) {
	// Special case: we don't make calls to this method static.
	return false;
	}

	if (!method.getEnclosingType().getMethods().contains(method)) {
	// The target method was already pruned (TypeTightener will fix this).
	return false;
	}

	return true;
	}
	}

	/**
	* For any method calls to methods we updated during
	* CreateStaticMethodVisitor, go and rewrite the call sites to call the static
	* method instead.
	*/
	private class RewriteCallSites extends JChangeTrackingVisitor {

	private boolean currentMethodIsInitiallyLive;
	private ControlFlowAnalyzer initiallyLive;

	public RewriteCallSites(OptimizerContext optimizerCtx) {
	super(optimizerCtx);
	}

	/**
	* In cases where callers are directly referencing (effectively) final
	* instance methods, rewrite the call site to reference the newly-generated
	* static method instead.
	*/
	@Override
	public void endVisit(JMethodCall x, Context ctx) {
	JMethod oldMethod = x.getTarget();
	JMethod newMethod = program.getStaticImpl(oldMethod);

	if (newMethod == null \|\| x.canBePolymorphic()) {
	return;
	}

	if (currentMethodIsInitiallyLive
	&& !initiallyLive.getLiveFieldsAndMethods().contains(x.getTarget())) {
	/*
	* Don't devirtualize calls from initial code to non-initial code.
	*
	* TODO(spoon): similar prevention when the callee is exclusive to some
	* split point and the caller is not.
	*/
	return;
	}

	ctx.replaceMe(converter.convertCall(x, newMethod));
	}

	@Override
	public boolean enter(JMethod x, Context ctx) {
	currentMethodIsInitiallyLive = initiallyLive.getLiveFieldsAndMethods().contains(x);
	return true;
	}

	@Override
	public boolean visit(JProgram x, Context ctx) {
	// TODO(rluble): This needs to be abstracted out the CodeSplitter.
	initiallyLive = CodeSplitter.computeInitiallyLive(x);
	return true;
	}
	}

	/**
	* Converts instance method calls to equivalent static method calls.
	* Optionally adds a null check on the former "this" parameter.
	*/
	static class StaticCallConverter {
	private final JMethod checkNotNull;

	StaticCallConverter(JProgram program, boolean addNullChecksForThis) {
	if (addNullChecksForThis) {
	checkNotNull = program.getIndexedMethod(RuntimeConstants.EXCEPTIONS_CHECK_NOT_NULL);
	} else {
	checkNotNull = null;
	}
	}

	/**
	* Converts an instance method call to the equivalent static method call.
	* @param original the instance method call to convert
	* @param newMethod the static method to call instead
	*/
	JExpression convertCall(JMethodCall original, JMethod newMethod) {

	JMethodCall newCall = new JMethodCall(original.getSourceInfo(), null, newMethod);

	/*
	* If the qualifier is a JMultiExpression, invoke on the last value. This
	* ensures that clinits maintain the same execution order relative to
	* parameters in deeply-inlined scenarios.
	*/
	// (a, b).foo() --> (a, foo(b))
	// Or in checked mode:
	// (a, b).foo() --> (a, foo(checkNotNull(b)))
	if (original.getInstance() instanceof JMultiExpression) {
	JMultiExpression multi = (JMultiExpression) original.getInstance();
	int lastIndex = multi.getNumberOfExpressions() - 1;
	newCall.addArg(makeNullCheck(multi.getExpression(lastIndex), original));
	newCall.addArgs(original.getArgs());
	multi.setExpression(lastIndex, newCall);
	return multi;
	} else {
	// The qualifier becomes the first argument.
	// a.foo(b) --> foo(a,b)
	// or in checked mode:
	// a.foo(b) --> foo(checkNotNull(a),b)
	newCall.addArg(makeNullCheck(original.getInstance(), original));
	newCall.addArgs(original.getArgs());
	return newCall;
	}
	}

	private JExpression makeNullCheck(JExpression x, JMethodCall call) {
	if (checkNotNull == null) {
	return x;
	}

	// Existing code plays tricks with JSO's, so don't add the null check.
	if (isJso(call)) {
	return x;
	}

	JMethodCall check = new JMethodCall(x.getSourceInfo(), null, checkNotNull);
	check.addArg(x);
	return check;
	}

	private boolean isJso(JMethodCall call) {
	JDeclaredType type = call.getTarget().getEnclosingType();
	return type != null && type.isJsoType();
	}
	}

	private static final String NAME = MakeCallsStatic.class.getSimpleName();

	public static OptimizerStats exec(JProgram program, boolean addRuntimeChecks,
	OptimizerContext optimizerCtx) {
	Event optimizeEvent = SpeedTracerLogger.start(CompilerEventType.OPTIMIZE, "optimizer", NAME);
	OptimizerStats stats = new MakeCallsStatic(program, addRuntimeChecks).execImpl(optimizerCtx);
	optimizerCtx.setLastStepFor(NAME, optimizerCtx.getOptimizationStep());
	optimizerCtx.incOptimizationStep();
	optimizeEvent.end("didChange", "" + stats.didChange());
	return stats;
	}

	@VisibleForTesting
	static OptimizerStats exec(JProgram program, boolean addRuntimeChecks) {
	return exec(program, addRuntimeChecks, new FullOptimizerContext(program));
	}

	protected Set<JMethod> toBeMadeStatic = Sets.newLinkedHashSet();

	private final JProgram program;
	private final StaticCallConverter converter;

	private MakeCallsStatic(JProgram program, boolean addRuntimeChecks) {
	this.program = program;
	this.converter = new StaticCallConverter(program, addRuntimeChecks);
	}

	private OptimizerStats execImpl(OptimizerContext optimizerCtx) {
	OptimizerStats stats = new OptimizerStats(NAME);
	FindStaticDispatchSitesVisitor finder = new FindStaticDispatchSitesVisitor();
	Set<JMethod> modifiedMethods =
	optimizerCtx.getModifiedMethodsSince(optimizerCtx.getLastStepFor(NAME));
	Set<JMethod> affectedMethods = affectedMethods(modifiedMethods, optimizerCtx);
	optimizerCtx.traverse(finder, affectedMethods);

	CreateStaticImplsVisitor creator = new CreateStaticImplsVisitor(program, optimizerCtx);
	for (JMethod method : toBeMadeStatic) {
	creator.accept(method);
	}
	for (JMethod method : toBeMadeStatic) {
	// if method has specialization, add it to the static method
	Specialization specialization = method.getSpecialization();
	if (specialization != null) {
	JMethod staticMethod = program.getStaticImpl(method);
	List<JType> params = Lists.newArrayList(specialization.getParams());
	params.add(0, staticMethod.getParams().get(0).getType());
	staticMethod.setSpecialization(params, specialization.getReturns(),
	staticMethod.getName());
	staticMethod.getSpecialization().resolve(params,
	specialization.getReturns(), program.getStaticImpl(specialization
	.getTargetMethod()));
	}
	}

	/*
	* Run the rewriter even if we didn't make any new static methods; other
	* optimizations can unlock devirtualizations even if no more static impls
	* are created.
	*/
	RewriteCallSites rewriter = new RewriteCallSites(optimizerCtx);
	rewriter.accept(program);
	stats.recordModified(rewriter.getNumMods());
	assert (rewriter.didChange() \|\| toBeMadeStatic.isEmpty());
	JavaAstVerifier.assertProgramIsConsistent(program);
	return stats;
	}

	/**
	* Return the set of methods affected (because they are or callers of) by the modifications to the
	* given set functions.
	*/
	private Set<JMethod> affectedMethods(Set<JMethod> modifiedMethods,
	OptimizerContext optimizerCtx) {
	assert (modifiedMethods != null);
	Set<JMethod> affectedMethods = Sets.newLinkedHashSet();
	affectedMethods.addAll(modifiedMethods);
	affectedMethods.addAll(optimizerCtx.getCallers(modifiedMethods));
	return affectedMethods;
	}
	}