Add initial Skylark byte code generation code.

Does not yet contain any implementation for expressions and statements
but sets up various needed mechanisms and helper classes.

--
MOS_MIGRATED_REVID=107222845

18 files changed, 1282 insertions, 10 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/BUILD b/src/main/java/com/google/devtools/build/lib/BUILD
index f3e1fe6d2c..ccbbeb1f7f 100644
--- a/src/main/java/com/google/devtools/build/lib/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/BUILD
@@ -78,7 +78,7 @@ java_library(
 
 java_library(
     name = "syntax",
-    srcs = glob(["syntax/*.java"]),
+    srcs = glob(["syntax/**/*.java"]),
     deps = [
         ":base-util",
         ":collect",
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Expression.java b/src/main/java/com/google/devtools/build/lib/syntax/Expression.java
index b78f2b2c8f..76c2d66894 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Expression.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Expression.java
@@ -13,6 +13,11 @@
 // limitations under the License.
 package com.google.devtools.build.lib.syntax;
 
+import com.google.devtools.build.lib.syntax.compiler.DebugInfo;
+import com.google.devtools.build.lib.syntax.compiler.VariableScope;
+
+import net.bytebuddy.implementation.bytecode.ByteCodeAppender;
+
 /**
  * Base class for all expression nodes in the AST.
  */
@@ -66,4 +71,12 @@ public abstract class Expression extends ASTNode {
    * @see Statement
    */
   abstract void validate(ValidationEnvironment env) throws EvalException;
+
+  /**
+   * Builds a {@link ByteCodeAppender} that implements this expression by consuming its operands
+   * from the byte code stack and pushing its result.
+   */
+  ByteCodeAppender compile(VariableScope scope, DebugInfo debugInfo) {
+    throw new UnsupportedOperationException(this.getClass().getSimpleName() + " unsupported.");
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/FunctionDefStatement.java b/src/main/java/com/google/devtools/build/lib/syntax/FunctionDefStatement.java
index 8d1ed36f5d..9c11547a15 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/FunctionDefStatement.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/FunctionDefStatement.java
@@ -13,7 +13,13 @@
 // limitations under the License.
 package com.google.devtools.build.lib.syntax;
 
+import com.google.common.base.Optional;
 import com.google.common.collect.ImmutableList;
+import com.google.devtools.build.lib.syntax.compiler.DebugInfo;
+import com.google.devtools.build.lib.syntax.compiler.LoopLabels;
+import com.google.devtools.build.lib.syntax.compiler.VariableScope;
+
+import net.bytebuddy.implementation.bytecode.ByteCodeAppender;
 
 import java.util.ArrayList;
 import java.util.List;
@@ -117,4 +123,12 @@ public class FunctionDefStatement extends Statement {
       stmts.validate(localEnv);
     }
   }
+
+  @Override
+  ByteCodeAppender compile(
+      VariableScope scope, Optional<LoopLabels> loopLabels, DebugInfo debugInfo) {
+    throw new UnsupportedOperationException(
+        "Skylark does not support nested function definitions"
+            + " and the current entry point for the compiler is UserDefinedFunction.");
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/FunctionSignature.java b/src/main/java/com/google/devtools/build/lib/syntax/FunctionSignature.java
index 45b190aa98..7ad3d2bd39 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/FunctionSignature.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/FunctionSignature.java
@@ -19,6 +19,7 @@ import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Interner;
 import com.google.common.collect.Interners;
 import com.google.common.collect.Lists;
+import com.google.devtools.build.lib.syntax.SkylarkList.Tuple;
 import com.google.devtools.build.lib.util.StringCanonicalizer;
 
 import java.io.Serializable;
@@ -26,6 +27,7 @@ import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.HashSet;
 import java.util.List;
+import java.util.Map;
 import java.util.Set;
 
 import javax.annotation.Nullable;
@@ -49,7 +51,7 @@ import javax.annotation.Nullable;
  *   to an argument list, and we optimize for the common case of no key-only mandatory parameters.
  *   key-only parameters are thus grouped together.
  *   positional mandatory and key-only mandatory parameters are separate,
- *   but there no loop over a contiguous chunk of them, anyway.
+ *   but there is no loop over a contiguous chunk of them, anyway.
  * <li>The named are all grouped together, with star and star_star rest arguments coming last.
  * <li>Mandatory arguments in each category (positional and named-only) come before the optional
  *   arguments, for the sake of slightly better clarity to human implementers. This eschews an
@@ -58,7 +60,7 @@ import javax.annotation.Nullable;
  *   passed, at which point it is dwarfed by the slowness of keyword processing.
  * </ol>
  *
- * <p>Parameters are thus sorted in the following obvious order:
+ * <p>Parameters are thus sorted in the following order:
  * positional mandatory arguments (if any), positional optional arguments (if any),
  * key-only mandatory arguments (if any), key-only optional arguments (if any),
  * then star argument (if any), then star_star argument (if any).
@@ -109,13 +111,13 @@ public abstract class FunctionSignature implements Serializable {
     public abstract boolean hasKwArg();
 
 
-    // The are computed argument counts
-    /** number of optional positional arguments. */
+    // These are computed argument counts
+    /** number of optional and mandatory positional arguments. */
     public int getPositionals() {
       return getMandatoryPositionals() + getOptionalPositionals();
     }
 
-    /** number of optional named-only arguments. */
+    /** number of optional and mandatory named-only arguments. */
     public int getNamedOnly() {
       return getMandatoryNamedOnly() + getOptionalNamedOnly();
     }
@@ -125,9 +127,33 @@ public abstract class FunctionSignature implements Serializable {
       return getOptionalPositionals() + getOptionalNamedOnly();
     }
 
+    /** number of all named parameters: mandatory and optional of positionals and named-only */
+    public int getAllNamed() {
+      return getPositionals() + getNamedOnly();
+    }
+
     /** total number of arguments */
     public int getArguments() {
-      return getPositionals() + getNamedOnly() + (hasStarArg() ? 1 : 0) + (hasKwArg() ? 1 : 0);
+      return getAllNamed() + (hasStarArg() ? 1 : 0) + (hasKwArg() ? 1 : 0);
+    }
+
+    /**
+     * @return this signature shape converted to a list of classes
+     */
+    public List<Class<?>> toClasses() {
+      List<Class<?>> parameters = new ArrayList<>();
+
+      for (int i = 0; i < getAllNamed(); i++) {
+        parameters.add(Object.class);
+      }
+      if (hasStarArg()) {
+        parameters.add(Tuple.class);
+      }
+      if (hasKwArg()) {
+        parameters.add(Map.class);
+      }
+
+      return parameters;
     }
   }
 
@@ -182,7 +208,6 @@ public abstract class FunctionSignature implements Serializable {
     return sb.toString();
   }
 
-
   /**
    * FunctionSignature.WithValues: also specifies a List of default values and types.
    *
@@ -427,7 +452,8 @@ public abstract class FunctionSignature implements Serializable {
             }
           }
         }
-      };
+      }
+
       Show show = new Show();
 
       int i = skipFirstMandatory ? 1 : 0;
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/LoadStatement.java b/src/main/java/com/google/devtools/build/lib/syntax/LoadStatement.java
index d85907ef53..33c98d3081 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/LoadStatement.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/LoadStatement.java
@@ -14,10 +14,16 @@
 package com.google.devtools.build.lib.syntax;
 
 import com.google.common.base.Joiner;
+import com.google.common.base.Optional;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
+import com.google.devtools.build.lib.syntax.compiler.DebugInfo;
+import com.google.devtools.build.lib.syntax.compiler.LoopLabels;
+import com.google.devtools.build.lib.syntax.compiler.VariableScope;
 import com.google.devtools.build.lib.vfs.PathFragment;
 
+import net.bytebuddy.implementation.bytecode.ByteCodeAppender;
+
 import java.util.Map;
 
 /**
@@ -119,4 +125,12 @@ public final class LoadStatement extends Statement {
       throw new EvalException(getLocation(), error);
     }
   }
+
+  @Override
+  ByteCodeAppender compile(
+      VariableScope scope, Optional<LoopLabels> loopLabels, DebugInfo debugInfo) {
+    throw new UnsupportedOperationException(
+        "load statements should never appear in method bodies and"
+            + " should never be compiled in general");
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Runtime.java b/src/main/java/com/google/devtools/build/lib/syntax/Runtime.java
index 754d9049e5..e35a6a29d1 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Runtime.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Runtime.java
@@ -17,6 +17,9 @@ package com.google.devtools.build.lib.syntax;
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
+import com.google.devtools.build.lib.syntax.compiler.ByteCodeUtils;
+
+import net.bytebuddy.implementation.bytecode.StackManipulation;
 
 import java.lang.reflect.Field;
 import java.util.HashMap;
@@ -64,11 +67,16 @@ public final class Runtime {
     }
   }
 
+  /**
+   * Load {@link #NONE} on the stack.
+   * <p>Kept close to the definition to avoid reflection errors when changing it.
+   */
+  public static final StackManipulation GET_NONE = ByteCodeUtils.getField(Runtime.class, "NONE");
+
   @SkylarkSignature(name = "None", returnType = NoneType.class,
       doc = "Literal for the None value.")
   public static final NoneType NONE = new NoneType();
 
-
   @SkylarkSignature(name = "PACKAGE_NAME", returnType = String.class,
       doc = "The name of the package the rule or build extension is called from. "
           + "For example, in the BUILD file <code>some/package/BUILD</code>, its value "
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Statement.java b/src/main/java/com/google/devtools/build/lib/syntax/Statement.java
index 829c4a29ab..3db9b1cdd5 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Statement.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Statement.java
@@ -13,6 +13,13 @@
 // limitations under the License.
 package com.google.devtools.build.lib.syntax;
 
+import com.google.common.base.Optional;
+import com.google.devtools.build.lib.syntax.compiler.DebugInfo;
+import com.google.devtools.build.lib.syntax.compiler.LoopLabels;
+import com.google.devtools.build.lib.syntax.compiler.VariableScope;
+
+import net.bytebuddy.implementation.bytecode.ByteCodeAppender;
+
 /**
  * Base class for all statements nodes in the AST.
  */
@@ -59,4 +66,15 @@ public abstract class Statement extends ASTNode {
    * @throws EvalException if the Statement has a semantical error.
    */
   abstract void validate(ValidationEnvironment env) throws EvalException;
+
+  /**
+   * Builds a {@link ByteCodeAppender} that implements this statement.
+   *
+   * <p>A statement implementation should never require any particular state of the byte code
+   * stack and should leave it in the state it was before.
+   */
+  ByteCodeAppender compile(
+      VariableScope scope, Optional<LoopLabels> loopLabels, DebugInfo debugInfo) {
+    throw new UnsupportedOperationException(this.getClass().getSimpleName() + " unsupported.");
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/UserDefinedFunction.java b/src/main/java/com/google/devtools/build/lib/syntax/UserDefinedFunction.java
index df0c1977ab..cf68aeb6f4 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/UserDefinedFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/UserDefinedFunction.java
@@ -13,13 +13,54 @@
 // limitations under the License.
 package com.google.devtools.build.lib.syntax;
 
+import com.google.common.base.Optional;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Iterables;
+import com.google.devtools.build.lib.events.Location;
 import com.google.devtools.build.lib.events.Location.LineAndColumn;
 import com.google.devtools.build.lib.profiler.Profiler;
 import com.google.devtools.build.lib.profiler.ProfilerTask;
+import com.google.devtools.build.lib.syntax.compiler.ByteCodeUtils;
+import com.google.devtools.build.lib.syntax.compiler.DebugInfo;
+import com.google.devtools.build.lib.syntax.compiler.LoopLabels;
+import com.google.devtools.build.lib.syntax.compiler.ReflectionUtils;
+import com.google.devtools.build.lib.syntax.compiler.VariableScope;
 import com.google.devtools.build.lib.vfs.PathFragment;
 
+import net.bytebuddy.ByteBuddy;
+import net.bytebuddy.asm.ClassVisitorWrapper;
+import net.bytebuddy.description.method.MethodDescription;
+import net.bytebuddy.description.modifier.MethodManifestation;
+import net.bytebuddy.description.modifier.Ownership;
+import net.bytebuddy.description.modifier.TypeManifestation;
+import net.bytebuddy.description.modifier.Visibility;
+import net.bytebuddy.description.type.TypeDescription;
+import net.bytebuddy.dynamic.DynamicType.Unloaded;
+import net.bytebuddy.dynamic.loading.ClassLoadingStrategy;
+import net.bytebuddy.implementation.Implementation;
+import net.bytebuddy.implementation.MethodDelegation;
+import net.bytebuddy.implementation.bytecode.ByteCodeAppender;
+import net.bytebuddy.implementation.bytecode.member.MethodReturn;
+import net.bytebuddy.matcher.ElementMatchers;
+
+import org.objectweb.asm.ClassVisitor;
+import org.objectweb.asm.ClassWriter;
+import org.objectweb.asm.Label;
+import org.objectweb.asm.Opcodes;
+import org.objectweb.asm.util.Textifier;
+import org.objectweb.asm.util.TraceClassVisitor;
+
+import java.io.File;
+import java.io.IOException;
+import java.io.PrintWriter;
+import java.lang.reflect.InvocationTargetException;
+import java.lang.reflect.Method;
+import java.nio.file.Files;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.List;
+
 /**
  * The actual function registered in the environment. This function is defined in the
  * parsed code using {@link FunctionDefStatement}.
@@ -31,12 +72,20 @@ public class UserDefinedFunction extends BaseFunction {
   // we close over the globals at the time of definition
   private final Environment.Frame definitionGlobals;
 
+  private Optional<Method> method;
+  // TODO(bazel-team) make this configurable once the compiler is stable
+  public static boolean debugCompiler = false;
+  public static boolean debugCompilerPrintByteCode = false;
+  private static File debugFolder;
+  public static boolean enableCompiler = false;
+
   protected UserDefinedFunction(Identifier function,
       FunctionSignature.WithValues<Object, SkylarkType> signature,
       ImmutableList<Statement> statements, Environment.Frame definitionGlobals) {
     super(function.getName(), signature, function.getLocation());
     this.statements = statements;
     this.definitionGlobals = definitionGlobals;
+    method = enableCompiler ? buildCompiledFunction() : Optional.<Method>absent();
   }
 
   public FunctionSignature.WithValues<Object, SkylarkType> getFunctionSignature() {
@@ -59,6 +108,13 @@ public class UserDefinedFunction extends BaseFunction {
               getName(), Iterables.getLast(env.getStackTrace()).getName()));
     }
 
+    if (enableCompiler && method.isPresent()) {
+      Object returnValue = callCompiledFunction(arguments, ast, env);
+      if (returnValue != null) {
+        return returnValue;
+      }
+    }
+
     Profiler.instance().startTask(ProfilerTask.SKYLARK_USER_FN,
         getLocationPathAndLine() + "#" + getName());
     try {
@@ -91,6 +147,161 @@ public class UserDefinedFunction extends BaseFunction {
     }
   }
 
+  private Object callCompiledFunction(Object[] arguments, FuncallExpression ast, Environment env) {
+    compilerDebug("Calling compiled function " + getLocationPathAndLine() + " " + getName());
+    try {
+      env.enterScope(this, ast, definitionGlobals);
+
+      return method
+          .get()
+          .invoke(null, ImmutableList.builder().add(arguments).add(env).build().toArray());
+
+    } catch (IllegalAccessException e) {
+      // this should never happen
+      throw new RuntimeException(
+          "Compiler created code that could not be accessed reflectively.", e);
+    } catch (InvocationTargetException e) {
+      compilerDebug("Error running compiled version", e.getCause());
+      return null;
+    } finally {
+      env.exitScope();
+    }
+  }
+
+  /**
+   * Generates a subclass of {@link CompiledFunction} with a static method "call" and static
+   * methods for getting information from a {@link DebugInfo} instance.
+   *
+   * <p>The "call" method contains the compiled version of this function's AST.
+   */
+  private Optional<Method> buildCompiledFunction() {
+    // replace the / character in the path so we have file system compatible class names
+    // the java specification mentions that $ should be used in generated code
+    // see http://docs.oracle.com/javase/specs/jls/se7/html/jls-3.html#jls-3.8
+    String path =
+        location.getPath() != null ? location.getPath().getPathString().replace('/', '$') : "";
+    String compiledFunctionClassName =
+        CompiledFunction.class.getCanonicalName() + path + "$" + getName();
+    compilerDebug("Compiling " + getLocationPathAndLine() + " " + getName());
+    try {
+      int publicStatic = Visibility.PUBLIC.getMask() | Ownership.STATIC.getMask();
+      TypeDescription.Latent latentCompiledFunctionClass =
+          new TypeDescription.Latent(
+              compiledFunctionClassName,
+              publicStatic | TypeManifestation.FINAL.getMask(),
+              new TypeDescription.ForLoadedType(CompiledFunction.class),
+              Collections.<TypeDescription>emptyList());
+      MethodDescription getAstNode =
+          new MethodDescription.Latent(
+              latentCompiledFunctionClass,
+              new MethodDescription.Token(
+                  "getAstNode",
+                  publicStatic | MethodManifestation.FINAL.getMask(),
+                  new TypeDescription.ForLoadedType(ASTNode.class),
+                  Arrays.asList(new TypeDescription.ForLoadedType(int.class))));
+      MethodDescription getLocation =
+          new MethodDescription.Latent(
+              latentCompiledFunctionClass,
+              new MethodDescription.Token(
+                  "getLocation",
+                  publicStatic | MethodManifestation.FINAL.getMask(),
+                  new TypeDescription.ForLoadedType(Location.class),
+                  Arrays.asList(new TypeDescription.ForLoadedType(int.class))));
+
+      DebugInfo debugInfo = new DebugInfo(getAstNode, getLocation);
+      FunctionSignature sig = signature.getSignature();
+      VariableScope scope = VariableScope.function(sig.getNames());
+      Implementation compiledImplementation = compileBody(scope, debugInfo);
+
+      List<Class<?>> parameterTypes = sig.getShape().toClasses();
+      parameterTypes.add(Environment.class);
+      Unloaded<CompiledFunction> unloadedImplementation =
+          new ByteBuddy()
+              .withClassVisitor(new StackMapFrameClassVisitor(debugCompilerPrintByteCode))
+              .subclass(CompiledFunction.class)
+              .name(compiledFunctionClassName)
+              .defineMethod(
+                  "call",
+                  Object.class,
+                  parameterTypes,
+                  Visibility.PUBLIC,
+                  Ownership.STATIC,
+                  MethodManifestation.FINAL)
+              .intercept(compiledImplementation)
+              .defineMethod(getAstNode)
+              // TODO(bazel-team) unify the two delegate fields into one, probably needs a custom
+              // ImplementationDelegate that adds it only once? or just create the static field
+              // itself with the correct value and create getAstNode & getLocation with a custom
+              // implementation using it
+              .intercept(
+                  MethodDelegation.to(debugInfo, DebugInfo.class, "getAstNodeDelegate")
+                      .filter(ElementMatchers.named("getAstNode")))
+              .defineMethod(getLocation)
+              .intercept(
+                  MethodDelegation.to(debugInfo, DebugInfo.class, "getLocationDelegate")
+                      .filter(ElementMatchers.named("getLocation")))
+              .make();
+      saveByteCode(unloadedImplementation);
+      Class<? extends CompiledFunction> functionClass =
+          unloadedImplementation
+              .load(getClass().getClassLoader(), ClassLoadingStrategy.Default.WRAPPER)
+              .getLoaded();
+
+      return Optional.of(
+          ReflectionUtils.getMethod(
+                  functionClass,
+                  "call",
+                  parameterTypes.toArray(new Class<?>[parameterTypes.size()]))
+              .getLoadedMethod());
+    } catch (Throwable e) {
+      compilerDebug("Error while compiling", e);
+      // TODO(bazel-team) don't capture all throwables? couldn't compile this, log somewhere?
+      return Optional.absent();
+    }
+  }
+
+  /**
+   * Saves byte code to a temporary directory prefixed with "skylarkbytecode" in the system
+   * default temporary directory.
+   */
+  private void saveByteCode(Unloaded<CompiledFunction> unloadedImplementation) {
+    if (debugCompiler) {
+      try {
+        if (debugFolder == null) {
+          debugFolder = Files.createTempDirectory("skylarkbytecode").toFile();
+        }
+        unloadedImplementation.saveIn(debugFolder);
+      } catch (IOException e) {
+        throw new RuntimeException(e);
+      }
+    }
+  }
+
+  /**
+   * Builds a byte code implementation of the AST.
+   */
+  private Implementation compileBody(VariableScope scope, DebugInfo debugInfo) {
+    List<ByteCodeAppender> code = new ArrayList<>(statements.size());
+    code.add(null); // reserve space for later addition of the local variable initializer
+
+    for (Statement statement : statements) {
+      code.add(statement.compile(scope, LoopLabels.ABSENT, debugInfo));
+    }
+    // add a return None if there are no statements or the last one to ensure the method always
+    // returns something. This implements the interpreters behavior.
+    if (statements.isEmpty()
+        || !(statements.get(statements.size() - 1) instanceof ReturnStatement)) {
+      code.add(new ByteCodeAppender.Simple(Runtime.GET_NONE, MethodReturn.REFERENCE));
+    }
+    // we now know which variables we used in the method, so assign them "undefined" (i.e. null)
+    // at the beginning of the method
+    code.set(0, scope.createLocalVariablesUndefined());
+    // TODO(bazel-team) wrap ByteCodeAppender in our own type including a reference to the ASTNode
+    // it came from and verify the stack and local variables ourselves, because ASM does not help
+    // with debugging much when its stack map frame calculation fails because of invalid byte code
+    return new Implementation.Simple(ByteCodeUtils.compoundAppender(code));
+  }
+
   /**
    * Returns the location (filename:line) of the BaseFunction's definition.
    *
@@ -113,4 +324,71 @@ public class UserDefinedFunction extends BaseFunction {
     }
     return builder.toString();
   }
+
+  private void compilerDebug(String message) {
+    System.err.println(message);
+  }
+
+  private void compilerDebug(String message, Throwable e) {
+    compilerDebug(message);
+    e.printStackTrace();
+  }
+
+  /**
+   * A simple super class for all compiled function's classes.
+   */
+  protected abstract static class CompiledFunction {}
+
+  /**
+   * A {@link Textifier} for printing the generated byte code that keeps the ASM-internal label
+   * names in place for easier debugging with IDE debuggers.
+   */
+  private static class DebugTextifier extends Textifier {
+    DebugTextifier() {
+      super(Opcodes.ASM5);
+    }
+
+    @Override
+    protected void appendLabel(Label l) {
+      buf.append(l.toString());
+    }
+
+    @Override
+    protected Textifier createTextifier() {
+      return new DebugTextifier();
+    }
+  }
+
+  /**
+   * Passes the {@link ClassWriter#COMPUTE_FRAMES} hint to ASM and optionally prints generated
+   * byte code to System.err.
+   */
+  private static class StackMapFrameClassVisitor implements ClassVisitorWrapper {
+
+    private final boolean debug;
+
+    private StackMapFrameClassVisitor(boolean debug) {
+      this.debug = debug;
+    }
+
+    @Override
+    public int mergeWriter(int hint) {
+      return hint | ClassWriter.COMPUTE_FRAMES;
+    }
+
+    @Override
+    public int mergeReader(int hint) {
+      return hint;
+    }
+
+    @Override
+    public ClassVisitor wrap(ClassVisitor classVisitor) {
+      if (debug) {
+        return new TraceClassVisitor(
+            classVisitor, new DebugTextifier(), new PrintWriter(System.err, true));
+      } else {
+        return classVisitor;
+      }
+    }
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/compiler/ByteCodeUtils.java b/src/main/java/com/google/devtools/build/lib/syntax/compiler/ByteCodeUtils.java
new file mode 100644
index 0000000000..4eb5433529
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/syntax/compiler/ByteCodeUtils.java
@@ -0,0 +1,53 @@
+// Copyright 2015 The Bazel Authors. All rights reserved.
+//
+// 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.devtools.build.lib.syntax.compiler;
+
+import net.bytebuddy.implementation.bytecode.ByteCodeAppender;
+import net.bytebuddy.implementation.bytecode.ByteCodeAppender.Compound;
+import net.bytebuddy.implementation.bytecode.StackManipulation;
+import net.bytebuddy.implementation.bytecode.member.FieldAccess;
+import net.bytebuddy.implementation.bytecode.member.MethodInvocation;
+
+import java.util.List;
+
+/**
+ * Various utility methods for byte code generation.
+ */
+public class ByteCodeUtils {
+
+  /**
+   * Create a {@link ByteCodeAppender} applying a list of them.
+   *
+   * <p>Exists just because {@link Compound} does not have a constructor taking a list.
+   */
+  public static ByteCodeAppender compoundAppender(List<ByteCodeAppender> code) {
+    return new Compound(code.toArray(new ByteCodeAppender[code.size()]));
+  }
+
+  /**
+   * Builds a {@link StackManipulation} that loads the field.
+   */
+  public static StackManipulation getField(Class<?> clazz, String field) {
+    return FieldAccess.forField(ReflectionUtils.getField(clazz, field)).getter();
+  }
+
+  /**
+   * Builds a {@link StackManipulation} that invokes the method identified via reflection on the
+   * given class, method and parameter types.
+   */
+  public static StackManipulation invoke(
+      Class<?> clazz, String methodName, Class<?>... parameterTypes) {
+    return MethodInvocation.invoke(ReflectionUtils.getMethod(clazz, methodName, parameterTypes));
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/compiler/DebugInfo.java b/src/main/java/com/google/devtools/build/lib/syntax/compiler/DebugInfo.java
new file mode 100644
index 0000000000..458c0cdbe9
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/syntax/compiler/DebugInfo.java
@@ -0,0 +1,90 @@
+// Copyright 2015 The Bazel Authors. All rights reserved.
+//
+// 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.devtools.build.lib.syntax.compiler;
+
+import com.google.devtools.build.lib.events.Location;
+import com.google.devtools.build.lib.syntax.ASTNode;
+
+import net.bytebuddy.description.method.MethodDescription;
+import net.bytebuddy.implementation.bytecode.StackManipulation;
+import net.bytebuddy.implementation.bytecode.constant.IntegerConstant;
+import net.bytebuddy.implementation.bytecode.member.MethodInvocation;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * A single point of access for references to the AST for debug location purposes.
+ */
+public final class DebugInfo {
+
+  /**
+   * Contains byte code instructions for calls to a DebugInfo instances methods.
+   */
+  public static final class AstAccessors {
+    public final StackManipulation loadAstNode;
+    public final StackManipulation loadLocation;
+
+    private AstAccessors(int index, StackManipulation getAstNode, StackManipulation getLocation) {
+      StackManipulation indexValue = IntegerConstant.forValue(index);
+      this.loadAstNode = new StackManipulation.Compound(indexValue, getAstNode);
+      this.loadLocation = new StackManipulation.Compound(indexValue, getLocation);
+    }
+  }
+
+  private final List<ASTNode> astNodes;
+  private final StackManipulation getAstNode;
+  private final StackManipulation getLocation;
+
+  /**
+   * @param getAstNode A {@link MethodDescription} which can be used to access this instance's
+   *     {@link #getAstNode(int)} in a static way.
+   * @param getLocation A {@link MethodDescription} which can be used to access this instance's
+   *     {@link #getLocation(int)} in a static way.
+   */
+  public DebugInfo(MethodDescription getAstNode, MethodDescription getLocation) {
+    astNodes = new ArrayList<>();
+    this.getAstNode = MethodInvocation.invoke(getAstNode);
+    this.getLocation = MethodInvocation.invoke(getLocation);
+  }
+
+  /**
+   * Get an {@link ASTNode} for reference at runtime.
+   *
+   * <p>Needed for rule construction which refers back to the function call node to get argument
+   * locations.
+   */
+  public ASTNode getAstNode(int index) {
+    return astNodes.get(index);
+  }
+
+  /**
+   * Get a {@link Location} for reference at runtime.
+   *
+   * <p>Needed to provide source code error locations at runtime.
+   */
+  public Location getLocation(int index) {
+    return getAstNode(index).getLocation();
+  }
+
+  /**
+   * Use this during compilation to add AST nodes needed at runtime.
+   * @return an {@link AstAccessors} instance which can be used to get the info at runtime in the
+   * static context of the byte code
+   */
+  public AstAccessors add(ASTNode node) {
+    astNodes.add(node);
+    return new AstAccessors(astNodes.size() - 1, getAstNode, getLocation);
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/compiler/Jump.java b/src/main/java/com/google/devtools/build/lib/syntax/compiler/Jump.java
new file mode 100644
index 0000000000..e13b1e6fa8
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/syntax/compiler/Jump.java
@@ -0,0 +1,138 @@
+// Copyright 2015 The Bazel Authors. All rights reserved.
+//
+// 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.devtools.build.lib.syntax.compiler;
+
+import net.bytebuddy.implementation.Implementation.Context;
+import net.bytebuddy.implementation.bytecode.StackManipulation;
+
+import org.objectweb.asm.Label;
+import org.objectweb.asm.MethodVisitor;
+import org.objectweb.asm.Opcodes;
+
+/**
+ * Implements byte code for gotos and conditional jumps.
+ */
+public class Jump implements StackManipulation {
+
+  protected final int opCode;
+  protected final Label target;
+  protected final Size stackSizeChange;
+
+  private Jump(int opCode, Label target, Size stackSizeChange) {
+    this.opCode = opCode;
+    this.target = target;
+    this.stackSizeChange = stackSizeChange;
+  }
+
+  @Override
+  public boolean isValid() {
+    return true;
+  }
+
+  @Override
+  public Size apply(MethodVisitor methodVisitor, Context implementationContext) {
+    methodVisitor.visitJumpInsn(opCode, target);
+    return stackSizeChange;
+  }
+
+  @Override
+  public String toString() {
+    return "Jump(" + opCode + ", " + target + ")";
+  }
+
+  /**
+   * Builds a conditional jump for two int operands on the stack.
+   */
+  public static JumpWithoutTarget ifIntOperands(PrimitiveComparison comparison) {
+    return new JumpWithoutTarget(Opcodes.IF_ICMPEQ + comparison.ordinal(), new Size(-2, 0));
+  }
+
+  /**
+   * Builds a conditional jump for one int operand from the stack compared to zero.
+   */
+  public static JumpWithoutTarget ifIntOperandToZero(PrimitiveComparison comparison) {
+    return new JumpWithoutTarget(Opcodes.IFEQ + comparison.ordinal(), new Size(-1, 0));
+  }
+
+  /**
+   * Builds a conditional jump for two reference type operands from the stack.
+   */
+  public static JumpWithoutTarget ifReferenceOperands(ReferenceComparison comparison) {
+    return new JumpWithoutTarget(Opcodes.IF_ACMPEQ + comparison.ordinal(), new Size(-2, 0));
+  }
+
+  /**
+   * Builds a conditional jump for one reference type operand from the stack compared to null.
+   */
+  public static JumpWithoutTarget ifReferenceOperandToNull(ReferenceComparison comparison) {
+    return new JumpWithoutTarget(Opcodes.IFNULL + comparison.ordinal(), new Size(-1, 0));
+  }
+
+  /**
+   * Builds an unconditional jump to the target label.
+   */
+  public static Jump to(Label target) {
+    return new Jump(Opcodes.GOTO, target, new Size(0, 0));
+  }
+
+  /**
+   * Builds an unconditional jump to the label added by the given {@link LabelAdder}.
+   */
+  public static Jump to(LabelAdder target) {
+    return to(target.getLabel());
+  }
+
+  /**
+   * Builder helper class for partially built jumps from conditionals.
+   *
+   * <p>Allows adding a jump target label.
+   */
+  public static final class JumpWithoutTarget {
+
+    protected final int opCode;
+    protected final Size stackSizeChange;
+
+    private JumpWithoutTarget(int opCode, Size stackSizeChange) {
+      this.opCode = opCode;
+      this.stackSizeChange = stackSizeChange;
+    }
+
+    /**
+     * Builds a jump to the given target and the previously initialized conditional.
+     */
+    public Jump to(LabelAdder target) {
+      return new Jump(opCode, target.getLabel(), stackSizeChange);
+    }
+  }
+
+  /**
+   * All primitive comparisons for which there are byte code equivalents.
+   */
+  public enum PrimitiveComparison {
+    EQUAL,
+    NOT_EQUAL,
+    LESS,
+    GREATER_EQUAL,
+    GREATER,
+    LESS_EQUAL;
+  }
+
+  /**
+   * All reference comparisons for which there are byte code equivalents.
+   */
+  public enum ReferenceComparison {
+    EQUAL,
+    NOT_EQUAL;
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/compiler/LabelAdder.java b/src/main/java/com/google/devtools/build/lib/syntax/compiler/LabelAdder.java
new file mode 100644
index 0000000000..348c40d4d3
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/syntax/compiler/LabelAdder.java
@@ -0,0 +1,52 @@
+// Copyright 2015 The Bazel Authors. All rights reserved.
+//
+// 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.devtools.build.lib.syntax.compiler;
+
+import net.bytebuddy.implementation.Implementation.Context;
+import net.bytebuddy.implementation.bytecode.StackManipulation;
+
+import org.objectweb.asm.Label;
+import org.objectweb.asm.MethodVisitor;
+
+/**
+ * Adds a fresh label to the byte code.
+ */
+public class LabelAdder implements StackManipulation {
+
+  private final Label label;
+
+  public LabelAdder() {
+    this.label = new Label();
+  }
+
+  public Label getLabel() {
+    return label;
+  }
+
+  @Override
+  public boolean isValid() {
+    return true;
+  }
+
+  @Override
+  public Size apply(MethodVisitor methodVisitor, Context implementationContext) {
+    methodVisitor.visitLabel(label);
+    return new Size(0, 0);
+  }
+
+  @Override
+  public String toString() {
+    return "Label(" + label + ")";
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/compiler/LoopLabels.java b/src/main/java/com/google/devtools/build/lib/syntax/compiler/LoopLabels.java
new file mode 100644
index 0000000000..e1bb9d36b1
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/syntax/compiler/LoopLabels.java
@@ -0,0 +1,55 @@
+// Copyright 2015 The Bazel Authors. All rights reserved.
+//
+// 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.devtools.build.lib.syntax.compiler;
+
+import com.google.common.base.Optional;
+import com.google.devtools.build.lib.syntax.FlowStatement.Kind;
+
+import org.objectweb.asm.Label;
+
+/**
+ * Container for passing around current loop labels during compilation.
+ */
+public class LoopLabels {
+  public final Label continueLabel;
+  public final Label breakLabel;
+
+  private LoopLabels(Label continueLabel, Label breakLabel) {
+    this.continueLabel = continueLabel;
+    this.breakLabel = breakLabel;
+  }
+
+  /**
+   * Only use Optional-wrapped instances of this class.
+   */
+  public static Optional<LoopLabels> of(Label continueLabel, Label breakLabel) {
+    return Optional.of(new LoopLabels(continueLabel, breakLabel));
+  }
+
+  public static final Optional<LoopLabels> ABSENT = Optional.absent();
+
+  /**
+   * Get the label for a certain kind of flow statement.
+   */
+  public Label labelFor(Kind kind) {
+    switch (kind) {
+      case BREAK:
+        return breakLabel;
+      case CONTINUE:
+        return continueLabel;
+      default:
+        throw new Error("missing flow kind: " + kind);
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/compiler/ReflectionUtils.java b/src/main/java/com/google/devtools/build/lib/syntax/compiler/ReflectionUtils.java
new file mode 100644
index 0000000000..5dff149ee0
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/syntax/compiler/ReflectionUtils.java
@@ -0,0 +1,59 @@
+// Copyright 2015 The Bazel Authors. All rights reserved.
+//
+// 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.devtools.build.lib.syntax.compiler;
+
+import net.bytebuddy.description.field.FieldDescription;
+import net.bytebuddy.description.method.MethodDescription;
+
+import java.util.Arrays;
+
+/**
+ * Utilities for reflective access of declared methods.
+ */
+public class ReflectionUtils {
+
+  /**
+   * Get a Byte Buddy {@link MethodDescription} for a method from a class.
+   *
+   * @throws Error when the method cannot be found via reflection
+   */
+  public static MethodDescription.ForLoadedMethod getMethod(
+      Class<?> clazz, String name, Class<?>... parameterTypes) {
+    try {
+      return new MethodDescription.ForLoadedMethod(clazz.getMethod(name, parameterTypes));
+    } catch (NoSuchMethodException e) {
+      throw new Error(
+          String.format(
+              "Error when reflectively getting method %s with parameter types %s from class %s",
+              name,
+              Arrays.toString(parameterTypes),
+              clazz),
+          e);
+    }
+  }
+
+  /**
+   * Get a Byte Buddy {@link FieldDescription} for a field of a class.
+   *
+   * @throws Error when the field cannot be found via reflection
+   */
+  public static FieldDescription getField(Class<?> clazz, String name) {
+    try {
+      return new FieldDescription.ForLoadedField(clazz.getField(name));
+    } catch (NoSuchFieldException e) {
+      throw new RuntimeException(
+          String.format("Error when reflectively getting field %s from class %s", name, clazz), e);
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/compiler/Variable.java b/src/main/java/com/google/devtools/build/lib/syntax/compiler/Variable.java
new file mode 100644
index 0000000000..41e2e5d32d
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/syntax/compiler/Variable.java
@@ -0,0 +1,168 @@
+// Copyright 2015 The Bazel Authors. All rights reserved.
+//
+// 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.devtools.build.lib.syntax.compiler;
+
+import com.google.devtools.build.lib.syntax.ASTNode;
+import com.google.devtools.build.lib.syntax.Environment;
+import com.google.devtools.build.lib.syntax.Environment.NoSuchVariableException;
+import com.google.devtools.build.lib.syntax.EvalException;
+import com.google.devtools.build.lib.syntax.EvalExceptionWithStackTrace;
+import com.google.devtools.build.lib.syntax.compiler.DebugInfo.AstAccessors;
+import com.google.devtools.build.lib.syntax.compiler.Jump.ReferenceComparison;
+
+import net.bytebuddy.description.type.TypeDescription;
+import net.bytebuddy.implementation.bytecode.ByteCodeAppender;
+import net.bytebuddy.implementation.bytecode.Duplication;
+import net.bytebuddy.implementation.bytecode.Removal;
+import net.bytebuddy.implementation.bytecode.StackManipulation;
+import net.bytebuddy.implementation.bytecode.constant.TextConstant;
+import net.bytebuddy.implementation.bytecode.member.MethodVariableAccess;
+
+/**
+ * Superclass for various variable representations during compile time.
+ */
+public abstract class Variable {
+
+  /**
+   * The index in the byte code local variable array of the method.
+   *
+   * <p>package-protected for access by VariableScope and variable-modifying byte code generators
+   */
+  final int index;
+
+  private Variable(int index) {
+    this.index = index;
+  }
+
+  /**
+   * Store operands on the stack to this variables array slot in byte code.
+   */
+  public abstract ByteCodeAppender store();
+
+  /**
+   * A variable generated for a named local variable in Skylark.
+   *
+   * <p>To get correct Python-style semantics in byte code, we need to allow control-flow paths
+   * along which variables may be "undefined". This must result in a runtime error.
+   */
+  public static class SkylarkVariable extends Variable {
+
+    public final String name;
+    private final ByteCodeAppender store;
+
+    SkylarkVariable(String name, int index) {
+      super(index);
+      this.name = name;
+      this.store = VariableStore.into(this);
+    }
+
+    /**
+     * Builds a ByteCodeAppender for loading this variable which makes sure it was defined before
+     * this use.
+     */
+    public ByteCodeAppender load(VariableScope scope, AstAccessors debugAccessors) {
+      // the variable may not be defined
+      // along the control-flow path taken at runtime, so we need to check for that then
+      LabelAdder end = new LabelAdder();
+      return new ByteCodeAppender.Simple(
+          // we don't generate primitive local variables from Skylark variables currently
+          // we'd also need a more elaborate way to check whether they were undefined
+          MethodVariableAccess.REFERENCE.loadOffset(index),
+          Duplication.SINGLE,
+          Jump.ifReferenceOperandToNull(ReferenceComparison.NOT_EQUAL).to(end),
+          Removal.SINGLE,
+          // not a method parameter or variable defined previously in the method body, must look it
+          // up in the environment passed to the call
+          scope.loadEnvironment(),
+          new TextConstant(name),
+          debugAccessors.loadAstNode,
+          ByteCodeUtils.invoke(
+              SkylarkVariable.class,
+              "lookupUnboundVariable",
+              Environment.class,
+              String.class,
+              ASTNode.class),
+          end);
+    }
+
+    @Override
+    public ByteCodeAppender store() {
+      return store;
+    }
+
+    /**
+     * Looks for the variable in the method calls outside environment and fail with debug info
+     * if not found.
+     */
+    public static Object lookupUnboundVariable(Environment global, String variable, ASTNode node)
+        throws EvalExceptionWithStackTrace {
+      try {
+        return global.lookup(variable);
+      } catch (NoSuchVariableException e) {
+        throw new EvalExceptionWithStackTrace(
+            new EvalException(
+                node.getLocation(),
+                "local variable '" + variable + "' referenced before assignment"),
+            node);
+      }
+    }
+  }
+
+  /**
+   * Parameter of a Skylark function.
+   *
+   * <p>These will always have a value along each intra-procedural control-flow path and thus we
+   * can generate simpler code.
+   */
+  public static final class SkylarkParameter extends SkylarkVariable {
+
+    SkylarkParameter(String name, int index) {
+      super(name, index);
+    }
+
+    @Override
+    public ByteCodeAppender load(VariableScope scope, AstAccessors debugAccessors) {
+      return new ByteCodeAppender.Simple(MethodVariableAccess.REFERENCE.loadOffset(index));
+    }
+  }
+
+  /**
+   * A variable generated for internal use and thus the property holds that all uses are dominated
+   * by their definition and we can actually type it.
+   */
+  public static final class InternalVariable extends Variable {
+
+    public final TypeDescription type;
+    private final ByteCodeAppender store;
+
+    InternalVariable(TypeDescription type, int index) {
+      super(index);
+      this.type = type;
+      this.store = VariableStore.into(this);
+    }
+
+    /**
+     * Builds a simple StackManipulation which loads the variable from its index while taking into
+     * account the correct type.
+     */
+    public StackManipulation load() {
+      return MethodVariableAccess.forType(type).loadOffset(index);
+    }
+
+    @Override
+    public ByteCodeAppender store() {
+      return store;
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/compiler/VariableScope.java b/src/main/java/com/google/devtools/build/lib/syntax/compiler/VariableScope.java
new file mode 100644
index 0000000000..b077cb879f
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/syntax/compiler/VariableScope.java
@@ -0,0 +1,175 @@
+// Copyright 2015 The Bazel Authors. All rights reserved.
+//
+// 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.devtools.build.lib.syntax.compiler;
+
+import com.google.devtools.build.lib.syntax.Environment;
+import com.google.devtools.build.lib.syntax.Identifier;
+import com.google.devtools.build.lib.syntax.compiler.Variable.InternalVariable;
+import com.google.devtools.build.lib.syntax.compiler.Variable.SkylarkParameter;
+import com.google.devtools.build.lib.syntax.compiler.Variable.SkylarkVariable;
+
+import net.bytebuddy.description.type.TypeDescription;
+import net.bytebuddy.implementation.bytecode.ByteCodeAppender;
+import net.bytebuddy.implementation.bytecode.ByteCodeAppender.Simple;
+import net.bytebuddy.implementation.bytecode.StackManipulation;
+import net.bytebuddy.implementation.bytecode.constant.NullConstant;
+import net.bytebuddy.implementation.bytecode.member.MethodVariableAccess;
+
+import java.util.ArrayList;
+import java.util.LinkedHashMap;
+import java.util.List;
+import java.util.Map;
+
+import javax.annotation.Nullable;
+
+/**
+ * Tracks variable scopes and and their assignment to indices of the methods local variable array.
+ */
+public class VariableScope {
+
+  /**
+   * The scope of a whole function.
+   *
+   * <p>This manages the variable index allocation for the whole function.
+   * We do not try to re-use variable slots in sub-scopes and once variables are not live anymore.
+   * Instead we rely on the register allocation of the JVM JIT compiler to remove any unnecessary
+   * ones we add.
+   */
+  private static final class FunctionVariableScope extends VariableScope {
+    private final StackManipulation loadEnvironment;
+    private final int parameterCount;
+    private int next;
+
+    private FunctionVariableScope(List<String> parameterNames) {
+      super(null, parameterNames);
+      this.parameterCount = parameterNames.size();
+      InternalVariable environment =
+          freshVariable(new TypeDescription.ForLoadedType(Environment.class));
+      loadEnvironment = MethodVariableAccess.REFERENCE.loadOffset(environment.index);
+    }
+
+    @Override
+    int next() {
+      return next++;
+    }
+
+    @Override
+    public StackManipulation loadEnvironment() {
+      return loadEnvironment;
+    }
+
+    @Override
+    public ByteCodeAppender createLocalVariablesUndefined() {
+      List<ByteCodeAppender> code = new ArrayList<>();
+      int skipped = 0;
+      Simple nullConstant = new ByteCodeAppender.Simple(NullConstant.INSTANCE);
+      for (Variable variable : variables.values()) {
+        if (skipped >= parameterCount) {
+          code.add(nullConstant);
+          code.add(variable.store());
+        } else {
+          skipped++;
+        }
+      }
+      return ByteCodeUtils.compoundAppender(code);
+    }
+  }
+
+  /**
+   * Initialize a new VariableScope for a function.
+   *
+   * <p>Will associate the names in order with the local variable indices beginning at 0.
+   *  Additionally adds an unnamed local variable parameter at the end for the
+   *  {@link com.google.devtools.build.lib.syntax.Environment}. This is needed for
+   *  compiling {@link com.google.devtools.build.lib.syntax.UserDefinedFunction}s.
+   */
+  public static VariableScope function(List<String> parameterNames) {
+    return new FunctionVariableScope(parameterNames);
+  }
+
+  /** only null for the topmost FunctionVariableScope */
+  @Nullable private final VariableScope parent;
+
+  /** default for access by subclass */
+  final Map<String, SkylarkVariable> variables;
+
+  private VariableScope(VariableScope parent) {
+    this.parent = parent;
+    variables = new LinkedHashMap<>();
+  }
+
+  private VariableScope(VariableScope parent, List<String> parameterNames) {
+    this(parent);
+    for (String variable : parameterNames) {
+      variables.put(variable, new SkylarkParameter(variable, next()));
+    }
+  }
+
+  /** delegate next variable index allocation to topmost scope */
+  int next() {
+    return parent.next();
+  }
+
+  // TODO(klaasb) javadoc
+  public SkylarkVariable getVariable(Identifier identifier) {
+    String name = identifier.getName();
+    SkylarkVariable variable = variables.get(name);
+    if (variable == null) {
+      variable = new SkylarkVariable(name, next());
+      variables.put(name, variable);
+    }
+    return variable;
+  }
+
+  /**
+   * @return a {@link StackManipulation} that loads the {@link Environment} parameter of the
+   * function.
+   */
+  public StackManipulation loadEnvironment() {
+    return parent.loadEnvironment();
+  }
+
+  /**
+   * @return a fresh anonymous variable which will never collide with user-defined ones
+   */
+  public InternalVariable freshVariable(TypeDescription type) {
+    return new InternalVariable(type, next());
+  }
+
+  /**
+   * @return a fresh anonymous variable which will never collide with user-defined ones
+   */
+  public InternalVariable freshVariable(Class<?> type) {
+    return freshVariable(new TypeDescription.ForLoadedType(type));
+  }
+
+  /**
+   * Create a sub scope in which variables can shadow variables from super scopes like this one.
+   *
+   * <p>Sub scopes don't ensure that variables are initialized with null for "undefined".
+   */
+  public VariableScope createSubScope() {
+    return new VariableScope(this);
+  }
+
+  /**
+   * Create code that initializes all variables corresponding to Skylark variables to null.
+   *
+   * <p>This is needed to make sure a byte code variable exists along all code paths and that we
+   * can check at runtime whether it wasn't defined along the path actually taken.
+   */
+  public ByteCodeAppender createLocalVariablesUndefined() {
+    return parent.createLocalVariablesUndefined();
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/compiler/VariableStore.java b/src/main/java/com/google/devtools/build/lib/syntax/compiler/VariableStore.java
new file mode 100644
index 0000000000..cd5af7e903
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/syntax/compiler/VariableStore.java
@@ -0,0 +1,106 @@
+// Copyright 2015 The Bazel Authors. All rights reserved.
+//
+// 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.devtools.build.lib.syntax.compiler;
+
+import com.google.common.base.Preconditions;
+import com.google.devtools.build.lib.syntax.compiler.Variable.InternalVariable;
+import com.google.devtools.build.lib.syntax.compiler.Variable.SkylarkVariable;
+
+import net.bytebuddy.description.method.MethodDescription;
+import net.bytebuddy.description.type.TypeDescription;
+import net.bytebuddy.implementation.Implementation.Context;
+import net.bytebuddy.implementation.bytecode.ByteCodeAppender;
+import net.bytebuddy.implementation.bytecode.StackManipulation.Size;
+import net.bytebuddy.implementation.bytecode.StackSize;
+
+import org.objectweb.asm.MethodVisitor;
+import org.objectweb.asm.Opcodes;
+
+// TODO(klaasb) javadoc
+enum VariableStore {
+  INTEGER(Opcodes.ISTORE, StackSize.SINGLE),
+  LONG(Opcodes.LSTORE, StackSize.DOUBLE),
+  FLOAT(Opcodes.FSTORE, StackSize.SINGLE),
+  DOUBLE(Opcodes.DSTORE, StackSize.DOUBLE),
+  REFERENCE(Opcodes.ASTORE, StackSize.SINGLE);
+
+  private final int opCode;
+  private final Size size;
+
+  private VariableStore(int opCode, StackSize size) {
+    this.opCode = opCode;
+    this.size = size.toIncreasingSize();
+  }
+
+  // TODO(klaasb) javadoc
+  private VariableIndexStore into(int index) {
+    return new VariableIndexStore(index);
+  }
+
+  // TODO(klaasb) javadoc
+  public static VariableIndexStore into(SkylarkVariable variable) {
+    return REFERENCE.into(variable.index);
+  }
+
+  // TODO(klaasb) javadoc
+  public static VariableIndexStore into(InternalVariable variable) {
+    return forType(variable.type).into(variable.index);
+  }
+
+  // TODO(klaasb) javadoc
+  class VariableIndexStore implements ByteCodeAppender {
+
+    private int operandIndex;
+
+    private VariableIndexStore(int operandIndex) {
+      this.operandIndex = operandIndex;
+    }
+
+    @Override
+    public ByteCodeAppender.Size apply(
+        MethodVisitor methodVisitor,
+        Context implementationContext,
+        MethodDescription instrumentedMethod) {
+      methodVisitor.visitVarInsn(opCode, operandIndex);
+      return new ByteCodeAppender.Size(
+          size.getMaximalSize(), Math.max(instrumentedMethod.getStackSize(), operandIndex + 1));
+    }
+
+    @Override
+    public String toString() {
+      return "VariableStore(" + opCode + ", " + operandIndex + ")";
+    }
+  }
+
+  /**
+   * Selects the correct VariableStore value for the given type
+   */
+  public static VariableStore forType(TypeDescription type) {
+    if (type.isPrimitive()) {
+      if (type.represents(long.class)) {
+        return LONG;
+      } else if (type.represents(double.class)) {
+        return DOUBLE;
+      } else if (type.represents(float.class)) {
+        return FLOAT;
+      } else {
+        Preconditions.checkArgument(
+            !type.represents(void.class), "Variables can't be of void type");
+        return INTEGER;
+      }
+    } else {
+      return REFERENCE;
+    }
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/SkylarkShell.java b/src/test/java/com/google/devtools/build/lib/syntax/SkylarkShell.java
index 72635cb86b..364db10fa1 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/SkylarkShell.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/SkylarkShell.java
@@ -81,6 +81,11 @@ class SkylarkShell {
   }
 
   public static void main(String[] args) {
+    if (args.length > 0 && args[0].equals("--compiler-debug")) {
+      UserDefinedFunction.enableCompiler = true;
+      UserDefinedFunction.debugCompiler = true;
+      UserDefinedFunction.debugCompilerPrintByteCode = true;
+    }
     new SkylarkShell().readEvalPrintLoop();
   }
 }