Use absolute stack locations in SExpr1 (#11877)

* SExpr1.SELocS - carry relBad/absGood - abs unused so far * compute/pass SELocS.abs in ClosureConversion, and check in Anf that it matches the reconstructed value CHANGELOG_BEGIN CHANGELOG_END * Remove relative stack locations. Rename as SELocAbsoluteS. Simplify Anf. Remove shiftLoc in ClosureConversion.
digital-asset · Nov 26, 2021 · 8ef348d · 8ef348d
1 parent 071bcf7
commit 8ef348d
Show file tree

Hide file tree

Showing 3 changed files with 20 additions and 24 deletions.
diff --git a/daml-lf/interpreter/src/main/scala/com/digitalasset/daml/lf/speedy/Anf.scala b/daml-lf/interpreter/src/main/scala/com/digitalasset/daml/lf/speedy/Anf.scala
@@ -155,17 +155,15 @@ private[lf] object Anf {
     *    it absolute because an offset doesn't change as new bindings are pushed onto the
     *    stack.
     *
-    *    Note the contrast with the expression form `ELocS` which contains a relative offset
-    *    from the end of the stack. This relative-position is used in both the original
-    *    expression which we traverse AND the new ANF expression we are constructing. The
+    *    Happily, the source expressions use absolute stack offsets in `SELocAbsoluteS`.
+    *    In contrast to the target expressions which use relative offsets in `SELocS`. The
     *    relative-offset to a binding varies as new bindings are pushed on the stack.
     */
   private[this] case class AbsBinding(abs: DepthA)
 
-  private[this] def makeAbsoluteB(env: Env, rel: Int): AbsBinding = {
-    val oldAbs = env.oldDepth.incr(-rel)
-    env.absMap.get(oldAbs) match {
-      case None => throw CompilationError(s"makeAbsoluteB(env=$env,rel=$rel)")
+  private[this] def makeAbsoluteB(env: Env, abs: Int): AbsBinding = {
+    env.absMap.get(DepthE(abs)) match {
+      case None => throw CompilationError(s"makeAbsoluteB(env=$env,abs=$abs)")
       case Some(abs) => AbsBinding(abs)
     }
   }
@@ -178,7 +176,7 @@ private[lf] object Anf {
 
   private def convertLoc(x: source.SELoc): target.SELoc = {
     x match {
-      case source.SELocS(x) => target.SELocS(x)
+      case source.SELocAbsoluteS(_) => sys.error("Anf.convertLoc/SELocAbsoluteS, unreachable code")
       case source.SELocA(x) => target.SELocA(x)
       case source.SELocF(x) => target.SELocF(x)
     }
@@ -193,7 +191,7 @@ private[lf] object Anf {
   }
 
   private[this] def makeAbsoluteA(env: Env, atom: source.SExprAtomic): AbsAtom = atom match {
-    case source.SELocS(rel) => Right(makeAbsoluteB(env, rel))
+    case source.SELocAbsoluteS(abs) => Right(makeAbsoluteB(env, abs))
     case x => Left(convertAtom(x))
   }
 
@@ -206,13 +204,13 @@ private[lf] object Anf {
   private[this] type AbsLoc = Either[source.SELoc, AbsBinding]
 
   private[this] def makeAbsoluteL(env: Env, loc: source.SELoc): AbsLoc = loc match {
-    case source.SELocS(rel) => Right(makeAbsoluteB(env, rel))
+    case source.SELocAbsoluteS(abs) => Right(makeAbsoluteB(env, abs))
     case x: source.SELocA => Left(x)
     case x: source.SELocF => Left(x)
   }
 
   private[this] def makeRelativeL(depth: DepthA)(loc: AbsLoc): target.SELoc = loc match {
-    case Left(x: source.SELocS) => throw CompilationError(s"makeRelativeL: unexpected: $x")
+    case Left(x: source.SELocAbsoluteS) => throw CompilationError(s"makeRelativeL: unexpected: $x")
     case Left(loc) => convertLoc(loc)
     case Right(binding) => target.SELocS(makeRelativeB(depth, binding))
   }

diff --git a/daml-lf/interpreter/src/main/scala/com/digitalasset/daml/lf/speedy/ClosureConversion.scala b/daml-lf/interpreter/src/main/scala/com/digitalasset/daml/lf/speedy/ClosureConversion.scala
@@ -21,7 +21,7 @@ private[speedy] object ClosureConversion {
   private[speedy] def closureConvert(source0: source.SExpr): target.SExpr = {
 
     // TODO: Recode the 'Env' management to avoid the polynomial-complexity of 'shift'. Issue #11830
-    case class Env(mapping: Map[Int, target.SELoc]) {
+    case class Env(depth: Int, mapping: Map[Int, target.SELoc]) {
 
       def lookup(i: Int): target.SELoc =
         mapping.get(i) match {
@@ -31,22 +31,20 @@ private[speedy] object ClosureConversion {
         }
 
       def shift(n: Int): Env = {
-        def shiftLoc(loc: target.SELoc, n: Int): target.SELoc = loc match {
-          case target.SELocS(i) => target.SELocS(i + n)
-          case target.SELocA(_) | target.SELocF(_) => loc
-        }
-        // We must update both the keys of the map (the relative-indexes from the original SEVar)
-        // And also any values in the map which are stack located (SELocS), which are also indexed relatively
-        val m1 = mapping.map { case (k, loc) => (n + k, shiftLoc(loc, n)) }
+        // We just update the keys of the map (the relative-indexes from the original SEVar)
+        val m1 = mapping.map { case (k, loc) => (n + k, loc) }
         // And create mappings for the `n` new stack items
-        val m2 = (1 to n).view.map(i => (i, target.SELocS(i)))
-        Env(m1 ++ m2)
+        val m2 = (1 to n).view.map { rel =>
+          val abs = this.depth + n - rel
+          (rel, target.SELocAbsoluteS(abs))
+        }
+        Env(this.depth + n, m1 ++ m2)
       }
     }
 
     object Env {
       def apply(): Env = {
-        Env(Map.empty)
+        Env(0, Map.empty)
       }
       def absBody(arity: Int, fvs: List[Int]): Env = {
         val newRemapsF: Map[Int, target.SELoc] = fvs.view.zipWithIndex.map { case (orig, i) =>
@@ -57,7 +55,7 @@ private[speedy] object ClosureConversion {
         }
         // The keys in newRemapsF and newRemapsA are disjoint
         val m1 = newRemapsF ++ newRemapsA
-        Env(m1)
+        Env(0, m1)
       }
     }
 

diff --git a/daml-lf/interpreter/src/main/scala/com/digitalasset/daml/lf/speedy/SExpr1.scala b/daml-lf/interpreter/src/main/scala/com/digitalasset/daml/lf/speedy/SExpr1.scala
@@ -51,7 +51,7 @@ private[speedy] object SExpr1 {
   sealed abstract class SELoc extends SExprAtomic
 
   // SELocS -- variable is located on the stack (SELet & binding forms of SECasePat)
-  final case class SELocS(n: Int) extends SELoc
+  final case class SELocAbsoluteS(n: Int) extends SELoc
 
   // SELocS -- variable is located in the args array of the application
   final case class SELocA(n: Int) extends SELoc