Speedy ANF (#6440)

* ANF transformation in Speedy. The idea behind this PR is to transform speedy expressions into a simpler form where all non-atomic sub-expressions are made explicit by the introduction of let-forms. In particular, for the function-application form. These simpler forms allow the execution engine to take advantage of the atomic assumption, and often removes many additional execution steps. In particular the pushing of continuations to allow execution to continue after a compound expression has been reduced to a value. changelog_begin changelog_end * improve comment * inline functions relocateA/L * remove comment about scalafmt * remove commented out alterative def for transformLet1 * improve code by adding incr methods to DepthA/E * remove (n == 0) special case in trackBindings * clarify comment further * improve validate/go to not consume stack for deeply right-nested let-expressions * address comments from Remy: be private; use final case case; etc * rename to unsafeCompilationPipeline * add back some trailing commas * remove commented-out debug line * improve comment * remove dev/debug code in compilationPipeline * remove commented out code in SEAppGeneral.execute * undo unrelated code improvement in SValue.scala * fix compile. object Anf cannot be private
digital-asset · Jun 30, 2020 · 353d0da · 353d0da
1 parent 2cd2a8f
commit 353d0da
Show file tree

Hide file tree

Showing 24 changed files with 973 additions and 453 deletions.
diff --git a/compatibility/bazel_tools/testing.bzl b/compatibility/bazel_tools/testing.bzl
@@ -72,6 +72,17 @@ excluded_test_tool_tests = [
             },
         ],
     },
+    {
+        "end": "1.3.0-snapshot.20200617.4484.0.7e0a6848",
+        "platform_ranges": [
+            {
+                "start": "0.0.0",  # fixme on next release
+                "exclusions": [
+                    "CommandServiceIT",
+                ],
+            },
+        ],
+    },
 ]
 
 def in_range(version, range):

diff --git a/compiler/repl-service/server/src/main/scala/com/digitalasset/daml/lf/ReplServiceMain.scala b/compiler/repl-service/server/src/main/scala/com/digitalasset/daml/lf/ReplServiceMain.scala
@@ -12,6 +12,7 @@ import com.daml.lf.data.Ref._
 import com.daml.lf.engine.script._
 import com.daml.lf.language.Ast._
 import com.daml.lf.language.{Ast, LanguageVersion}
+import com.daml.lf.speedy.AExpr
 import com.daml.lf.speedy.SExpr._
 import com.daml.lf.speedy.{Compiler, SValue, SExpr, SError}
 import com.daml.grpc.adapter.{AkkaExecutionSequencerPool, ExecutionSequencerFactory}
@@ -190,7 +191,7 @@ class ReplService(
     mat: Materializer)
     extends ReplServiceGrpc.ReplServiceImplBase {
   var packages: Map[PackageId, Package] = Map.empty
-  var compiledDefinitions: Map[SDefinitionRef, SExpr] = Map.empty
+  var compiledDefinitions: Map[SDefinitionRef, AExpr] = Map.empty
   var results: Seq[SValue] = Seq()
   implicit val ec_ = ec
   implicit val esf_ = esf

diff --git a/...er/scenario-service/server/src/main/scala/com/digitalasset/daml/lf/scenario/Context.scala b/...er/scenario-service/server/src/main/scala/com/digitalasset/daml/lf/scenario/Context.scala
@@ -15,7 +15,7 @@ import com.daml.lf.speedy.Compiler
 import com.daml.lf.speedy.ScenarioRunner
 import com.daml.lf.speedy.SError._
 import com.daml.lf.speedy.Speedy
-import com.daml.lf.speedy.SExpr
+import com.daml.lf.speedy.AExpr
 import com.daml.lf.speedy.SValue
 import com.daml.lf.speedy.SExpr.{LfDefRef, SDefinitionRef}
 import com.daml.lf.transaction.TransactionVersions
@@ -54,10 +54,10 @@ class Context(val contextId: Context.ContextId) {
   val homePackageId: PackageId = PackageId.assertFromString("-homePackageId-")
 
   private var extPackages: Map[PackageId, Ast.Package] = HashMap.empty
-  private var extDefns: Map[SDefinitionRef, SExpr] = HashMap.empty
+  private var extDefns: Map[SDefinitionRef, AExpr] = HashMap.empty
   private var modules: Map[ModuleName, Ast.Module] = HashMap.empty
-  private var modDefns: Map[ModuleName, Map[SDefinitionRef, SExpr]] = HashMap.empty
-  private var defns: Map[SDefinitionRef, SExpr] = HashMap.empty
+  private var modDefns: Map[ModuleName, Map[SDefinitionRef, AExpr]] = HashMap.empty
+  private var defns: Map[SDefinitionRef, AExpr] = HashMap.empty
 
   def loadedModules(): Iterable[ModuleName] = modules.keys
   def loadedPackages(): Iterable[PackageId] = extPackages.keys
@@ -150,7 +150,7 @@ class Context(val contextId: Context.ContextId) {
     for {
       defn <- defns.get(LfDefRef(identifier))
     } yield
-      Speedy.Machine.fromScenarioSExpr(
+      Speedy.Machine.fromScenarioAExpr(
         compiledPackages,
         txSeeding,
         defn,

diff --git a/...lf/engine/src/main/scala/com/digitalasset/daml/lf/engine/ConcurrentCompiledPackages.scala b/...lf/engine/src/main/scala/com/digitalasset/daml/lf/engine/ConcurrentCompiledPackages.scala
@@ -18,15 +18,15 @@ import scala.collection.concurrent.{Map => ConcurrentMap}
 final class ConcurrentCompiledPackages extends MutableCompiledPackages {
   private[this] val _packages: ConcurrentMap[PackageId, Package] =
     new ConcurrentHashMap().asScala
-  private[this] val _defns: ConcurrentHashMap[speedy.SExpr.SDefinitionRef, speedy.SExpr] =
+  private[this] val _defns: ConcurrentHashMap[speedy.SExpr.SDefinitionRef, speedy.AExpr] =
     new ConcurrentHashMap()
   private[this] val _packageDeps: ConcurrentHashMap[PackageId, Set[PackageId]] =
     new ConcurrentHashMap()
   private[this] var _profilingMode: speedy.Compiler.ProfilingMode = speedy.Compiler.NoProfile
   private[this] var _stackTraceMode: speedy.Compiler.StackTraceMode = speedy.Compiler.FullStackTrace
 
   def getPackage(pId: PackageId): Option[Package] = _packages.get(pId)
-  def getDefinition(dref: speedy.SExpr.SDefinitionRef): Option[speedy.SExpr] =
+  def getDefinition(dref: speedy.SExpr.SDefinitionRef): Option[speedy.AExpr] =
     Option(_defns.get(dref))
 
   override def profilingMode = _profilingMode

diff --git a/daml-lf/engine/src/main/scala/com/digitalasset/daml/lf/engine/Engine.scala b/daml-lf/engine/src/main/scala/com/digitalasset/daml/lf/engine/Engine.scala
@@ -8,7 +8,7 @@ import com.daml.lf.command._
 import com.daml.lf.data._
 import com.daml.lf.data.Ref.{PackageId, ParticipantId, Party}
 import com.daml.lf.language.Ast._
-import com.daml.lf.speedy.{InitialSeeding, Pretty, SExpr}
+import com.daml.lf.speedy.{InitialSeeding, Pretty}
 import com.daml.lf.speedy.Speedy.Machine
 import com.daml.lf.speedy.SResult._
 import com.daml.lf.transaction.{TransactionVersions, Transaction => Tx}
@@ -275,8 +275,7 @@ class Engine(config: Engine.Config) {
         compiledPackages = compiledPackages,
         submissionTime = submissionTime,
         initialSeeding = seeding,
-        expr = SExpr
-          .SEApp(compiledPackages.compiler.unsafeCompile(commands), Array(SExpr.SEValue.Token)),
+        anf = Machine.makeApplyToToken(compiledPackages.compiler.unsafeCompile(commands)),
         globalCids = globalCids,
         committers = submitters,
         supportedValueVersions = config.allowedOutputValueVersions,

diff --git a/daml-lf/interpreter/perf/BUILD.bazel b/daml-lf/interpreter/perf/BUILD.bazel
@@ -32,6 +32,8 @@ da_scala_binary(
     data = [
         ":Examples.dar",
         ":Examples.dar.pp",
+        ":JsonParser.dar",
+        ":JsonParser.dar.pp",
     ],
     main_class = "com.daml.lf.speedy.explore.ExploreDar",
     runtime_deps = [

diff --git a/daml-lf/interpreter/perf/src/main/scala/com/daml/lf/explore/Explore.scala b/daml-lf/interpreter/perf/src/main/scala/com/daml/lf/explore/Explore.scala
@@ -30,8 +30,8 @@ object PlaySpeedy {
 
     names.foreach { name =>
       val (expected, expr) = examples(name)
-      val converted = compiler.unsafeClosureConvert(expr)
-      val machine = Speedy.Machine.fromPureSExpr(noPackages, converted)
+      val anf = compiler.unsafeCompilationPipeline(expr)
+      val machine = Speedy.Machine.fromPureAExpr(noPackages, anf)
       runMachine(name, machine, expected)
     }
   }
@@ -84,7 +84,7 @@ object PlaySpeedy {
     }
   }
 
-  final case class MachineProblem(s: String) extends RuntimeException(s, null, false, false)
+  final case class MachineProblem(s: String) extends RuntimeException(s)
 
   def examples: Map[String, (Int, SExpr)] = {
 
@@ -98,6 +98,8 @@ object PlaySpeedy {
     def subtract2(x: SExpr, y: SExpr): SExpr = SEApp(SEBuiltin(SBSubInt64), Array(x, y))
     val subtract = SEAbs(2, subtract2(SEVar(2), SEVar(1)))
 
+    val identity = SEAbs(1, SEVar(1))
+
     def twice2(f: SExpr, x: SExpr): SExpr = SEApp(f, Array(SEApp(f, Array(x))))
     val twice = SEAbs(2, twice2(SEVar(2), SEVar(1)))
 
@@ -117,6 +119,10 @@ object PlaySpeedy {
         "subF", //88-55
         33,
         SEApp(subtract, Array(num(88), num(55)))),
+      (
+        "id-id", // id id 77
+        77,
+        SEApp(identity, Array(identity, num(77)))),
       (
         "thrice", // thrice (\x -> x - 1) 0
         -3,

diff --git a/daml-lf/interpreter/perf/src/main/scala/com/daml/lf/explore/ExploreDar.scala b/daml-lf/interpreter/perf/src/main/scala/com/daml/lf/explore/ExploreDar.scala
@@ -30,6 +30,7 @@ object PlaySpeedy {
   }
 
   def parseArgs(args0: List[String]): Config = {
+    var moduleName: String = "Examples"
     var funcName: String = "triangle"
     var argValue: Long = 10
     var stacktracing: Compiler.StackTraceMode = Compiler.NoStackTrace
@@ -43,15 +44,19 @@ object PlaySpeedy {
       case "--stacktracing" :: args =>
         stacktracing = Compiler.FullStackTrace
         loop(args)
+      case "--base" :: x :: args =>
+        moduleName = x
+        loop(args)
       case x :: args =>
         funcName = x
         loop(args)
     }
     loop(args0)
-    Config(funcName, argValue, stacktracing)
+    Config(moduleName, funcName, argValue, stacktracing)
   }
 
   final case class Config(
+      moduleName: String,
       funcName: String,
       argValue: Long,
       stacktracing: Compiler.StackTraceMode,
@@ -60,8 +65,8 @@ object PlaySpeedy {
   def main(args0: List[String]) = {
 
     println("Start...")
-    val base = "Examples"
     val config = parseArgs(args0)
+    val base = config.moduleName
     val dar = s"daml-lf/interpreter/perf/${base}.dar"
     val darFile = new File(rlocation(dar))
 

diff --git a/daml-lf/interpreter/src/main/scala/com/digitalasset/daml/lf/CompiledPackages.scala b/daml-lf/interpreter/src/main/scala/com/digitalasset/daml/lf/CompiledPackages.scala
@@ -6,18 +6,18 @@ package com.daml.lf
 import com.daml.lf.data.Ref.PackageId
 import com.daml.lf.language.Ast.Package
 import com.daml.lf.speedy.SExpr.SDefinitionRef
-import com.daml.lf.speedy.{Compiler, SExpr}
+import com.daml.lf.speedy.{Compiler, AExpr}
 
 /** Trait to abstract over a collection holding onto DAML-LF package definitions + the
   * compiled speedy expressions.
   */
 trait CompiledPackages {
   def getPackage(pkgId: PackageId): Option[Package]
-  def getDefinition(dref: SDefinitionRef): Option[SExpr]
+  def getDefinition(dref: SDefinitionRef): Option[AExpr]
 
   def packages: PartialFunction[PackageId, Package] = Function.unlift(this.getPackage)
   def packageIds: Set[PackageId]
-  def definitions: PartialFunction[SDefinitionRef, SExpr] =
+  def definitions: PartialFunction[SDefinitionRef, AExpr] =
     Function.unlift(this.getDefinition)
 
   def stackTraceMode: Compiler.StackTraceMode
@@ -28,13 +28,13 @@ trait CompiledPackages {
 
 final class PureCompiledPackages private (
     packages: Map[PackageId, Package],
-    defns: Map[SDefinitionRef, SExpr],
+    defns: Map[SDefinitionRef, AExpr],
     stacktracing: Compiler.StackTraceMode,
     profiling: Compiler.ProfilingMode,
 ) extends CompiledPackages {
   override def packageIds: Set[PackageId] = packages.keySet
   override def getPackage(pkgId: PackageId): Option[Package] = packages.get(pkgId)
-  override def getDefinition(dref: SDefinitionRef): Option[SExpr] = defns.get(dref)
+  override def getDefinition(dref: SDefinitionRef): Option[AExpr] = defns.get(dref)
   override def stackTraceMode = stacktracing
   override def profilingMode = profiling
 }
@@ -46,7 +46,7 @@ object PureCompiledPackages {
     */
   private[lf] def apply(
       packages: Map[PackageId, Package],
-      defns: Map[SDefinitionRef, SExpr],
+      defns: Map[SDefinitionRef, AExpr],
       stacktracing: Compiler.StackTraceMode,
       profiling: Compiler.ProfilingMode
   ): PureCompiledPackages =

diff --git a/daml-lf/interpreter/src/main/scala/com/digitalasset/daml/lf/speedy/AExpr.scala b/daml-lf/interpreter/src/main/scala/com/digitalasset/daml/lf/speedy/AExpr.scala
@@ -0,0 +1,9 @@
+// Copyright (c) 2020 Digital Asset (Switzerland) GmbH and/or its affiliates. All rights reserved.
+// SPDX-License-Identifier: Apache-2.0
+
+package com.daml.lf.speedy
+
+/**
+  * The even more simplified AST for the speedy interpreter, following ANF transformation.
+  */
+final case class AExpr(wrapped: SExpr) extends Serializable