[vpm] label-based translation of matches

1 files changed, 173 insertions, 185 deletions

diff --git a/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala b/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala
index b060fd7121..552c236bde 100644
--- a/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala
@@ -43,7 +43,7 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
     val outer     = newTermName("<outer>")
     val runOrElse = newTermName("runOrElse")
     val zero      = newTermName("zero")
-    val _match  = newTermName("__match") // don't call it __match, since that will trigger virtual pattern matching...
+    val _match    = newTermName("__match") // don't call it __match, since that will trigger virtual pattern matching...
 
     def counted(str: String, i: Int) = newTermName(str+i)
   }
@@ -177,7 +177,7 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
                 CaseDef(
                   Bind(exSym, Ident(nme.WILDCARD)), // TODO: does this need fixing upping?
                   EmptyTree,
-                  combineCasesNoSubstOnly(CODE.REF(exSym), scrutSym, casesNoSubstOnly, pt, matchOwner, scrut => Throw(CODE.REF(exSym)))
+                  combineCasesNoSubstOnly(CODE.REF(exSym), scrutSym, casesNoSubstOnly, pt, matchOwner, casegen => scrut => Throw(CODE.REF(exSym)))
                 )
               })
         }
@@ -733,23 +733,25 @@ class Foo(x: Other) { x._1 } // no error in this order
       private[this] var currSub: Substitution = null
 
       // build Tree that chains `next` after the current extractor
-      def chainBefore(next: Tree, pt: Type): Tree
+      def chainBefore(next: Tree)(casegen: Casegen): Tree
     }
 
-    case class TrivialTreeMaker(tree: Tree) extends TreeMaker {
-      val localSubstitution: Substitution = EmptySubstitution
-      def chainBefore(next: Tree, pt: Type): Tree = tree
+    trait NoNewBinders extends TreeMaker {
+      protected val localSubstitution: Substitution = EmptySubstitution
     }
 
-    case class BodyTreeMaker(body: Tree, matchPt: Type) extends TreeMaker {
-      val localSubstitution: Substitution = EmptySubstitution
-      def chainBefore(next: Tree, pt: Type): Tree = // assert(next eq EmptyTree)
-        atPos(body.pos)(substitution(codegen.one(body, body.tpe, matchPt))) // since SubstOnly treemakers are dropped, need to do it here
+    case class TrivialTreeMaker(tree: Tree) extends TreeMaker with NoNewBinders {
+      def chainBefore(next: Tree)(casegen: Casegen): Tree = tree
+    }
+
+    case class BodyTreeMaker(body: Tree, matchPt: Type) extends TreeMaker with NoNewBinders {
+      def chainBefore(next: Tree)(casegen: Casegen): Tree = // assert(next eq EmptyTree)
+        atPos(body.pos)(casegen.one(substitution(body))) // since SubstOnly treemakers are dropped, need to do it here
     }
 
     case class SubstOnlyTreeMaker(prevBinder: Symbol, nextBinder: Symbol) extends TreeMaker {
       val localSubstitution = Substitution(prevBinder, CODE.REF(nextBinder))
-      def chainBefore(next: Tree, pt: Type): Tree = substitution(next)
+      def chainBefore(next: Tree)(casegen: Casegen): Tree = substitution(next)
     }
 
     abstract class FunTreeMaker extends TreeMaker {
@@ -766,8 +768,8 @@ class Foo(x: Other) { x._1 } // no error in this order
       lazy val nextBinder = freshSym(pos, nextBinderTp)
       lazy val localSubstitution = Substitution(List(prevBinder), List(CODE.REF(nextBinder)))
 
-      def chainBefore(next: Tree, pt: Type): Tree =
-        atPos(pos)(codegen.flatMapCond(cond, res, nextBinder, nextBinderTp, substitution(next)))
+      def chainBefore(next: Tree)(casegen: Casegen): Tree =
+        atPos(pos)(casegen.flatMapCond(cond, res, nextBinder, substitution(next)))
     }
 
     /**
@@ -778,11 +780,11 @@ class Foo(x: Other) { x._1 } // no error in this order
      * in this function's body, and all the subsequent ones, references to the symbols in `from` will be replaced by the corresponding tree in `to`
      */
     case class ExtractorTreeMaker(extractor: Tree, extraCond: Option[Tree], nextBinder: Symbol, localSubstitution: Substitution)(extractorReturnsBoolean: Boolean) extends FunTreeMaker {
-      def chainBefore(next: Tree, pt: Type): Tree = {
-        val condAndNext = extraCond map (codegen.ifThenElseZero(_, next)) getOrElse next
+      def chainBefore(next: Tree)(casegen: Casegen): Tree = {
+        val condAndNext = extraCond map (casegen.ifThenElseZero(_, next)) getOrElse next
         atPos(extractor.pos)(
-          if (extractorReturnsBoolean) codegen.flatMapCond(extractor, CODE.UNIT, nextBinder, nextBinder.info.widen, substitution(condAndNext))
-          else codegen.flatMap(extractor, nextBinder, substitution(condAndNext))
+          if (extractorReturnsBoolean) casegen.flatMapCond(extractor, CODE.UNIT, nextBinder, substitution(condAndNext))
+          else casegen.flatMap(extractor, nextBinder, substitution(condAndNext))
         )
       }
 
@@ -791,10 +793,10 @@ class Foo(x: Other) { x._1 } // no error in this order
 
     // TODO: allow user-defined unapplyProduct
     case class ProductExtractorTreeMaker(prevBinder: Symbol, extraCond: Option[Tree], localSubstitution: Substitution) extends TreeMaker { import CODE._
-      def chainBefore(next: Tree, pt: Type): Tree = {
+      def chainBefore(next: Tree)(casegen: Casegen): Tree = {
         val nullCheck = REF(prevBinder) OBJ_NE NULL
         val cond = extraCond map (nullCheck AND _) getOrElse nullCheck
-        codegen.ifThenElseZero(cond, substitution(next))
+        casegen.ifThenElseZero(cond, substitution(next))
       }
 
       override def toString = "P"+(prevBinder,  extraCond getOrElse "", localSubstitution)
@@ -907,58 +909,30 @@ class Foo(x: Other) { x._1 } // no error in this order
       override def toString = "ET"+(prevBinder, patTree)
     }
 
-    case class AlternativesTreeMaker(prevBinder: Symbol, var altss: List[List[TreeMaker]], pos: Position) extends TreeMaker {
+    case class AlternativesTreeMaker(prevBinder: Symbol, var altss: List[List[TreeMaker]], pos: Position) extends TreeMaker with NoNewBinders {
       // don't substitute prevBinder to nextBinder, a set of alternatives does not need to introduce a new binder, simply reuse the previous one
-      val localSubstitution: Substitution = EmptySubstitution
 
       override private[TreeMakers] def incorporateOuterSubstitution(outerSubst: Substitution): Unit = {
         super.incorporateOuterSubstitution(outerSubst)
         altss = altss map (alts => propagateSubstitution(alts, substitution))
       }
 
-      def chainBefore(next: Tree, pt: Type): Tree = { import CODE._
-        // next does not contain deftrees, is pretty short
-        val canDuplicate = {
-          var okToInline = true
-          var sizeBudget = 100 / (altss.length max 1)  // yep, totally arbitrary!
-          object travOkToInline extends Traverser { override def traverse(tree: Tree): Unit = if (sizeBudget >= 0) { sizeBudget -= 1; tree match {
-            case TypeApply(_, _) | Apply(_, _) | Select(_, _)
-               | Block(_, _) | Assign(_, _) | If(_, _, _) | Typed(_, _) => super.traverse(tree) // these are allowed if their subtrees are
-            case EmptyTree | This(_) | New(_) | Literal(_) | Ident(_)   => // these are always ok
-            case _ if tree.isType                                       => // these are always ok
-            case _                                                      => okToInline = false //; println("not inlining: "+ (tree, tree.getClass))
-          }}}
-          travOkToInline.traverse(next)
-          // println("(okToInline, sizeBudget): "+ (okToInline, sizeBudget))
-          okToInline && sizeBudget > 0 // must be strict comparison
-        }
+      def chainBefore(next: Tree)(codegenAlt: Casegen): Tree = { import CODE._
+        atPos(pos){
+          // one alternative may still generate multiple trees (e.g., an extractor call + equality test)
+          // (for now,) alternatives may not bind variables (except wildcards), so we don't care about the final substitution built internally by makeTreeMakers
+          val combinedAlts = altss map (altTreeMakers =>
+            ((casegen: Casegen) => combineExtractors(altTreeMakers :+ TrivialTreeMaker(casegen.one(TRUE)))(casegen))
+          )
 
-        atPos(pos)(
-          if (canDuplicate) {
-            altss map {altTreeMakers =>
-              combineExtractors(altTreeMakers :+ TrivialTreeMaker(substitution(next).duplicate), pt)
-            } reduceLeft codegen.typedOrElse(pt)
-          } else {
-            val rest = freshSym(pos, functionType(List(), inMatchMonad(pt)), "rest")
-            // rest.info.member(nme.apply).withAnnotation(AnnotationInfo(ScalaInlineClass.tpe, Nil, Nil))
-
-            // one alternative may still generate multiple trees (e.g., an extractor call + equality test)
-            // (for now,) alternatives may not bind variables (except wildcards), so we don't care about the final substitution built internally by makeTreeMakers
-            val combinedAlts = altss map (altTreeMakers =>
-              combineExtractors(altTreeMakers :+ TrivialTreeMaker(REF(rest) APPLY ()), pt)
-            )
-            BLOCK(
-              VAL(rest) === Function(Nil, substitution(next)),
-              combinedAlts reduceLeft codegen.typedOrElse(pt)
-            )
-          }
-        )
+          val findAltMatcher = codegenAlt.matcher(EmptyTree, NoSymbol, BooleanClass.tpe)(combinedAlts, Some((casegen: Casegen) => x => casegen.one(FALSE)))
+          codegenAlt.ifThenElseZero(findAltMatcher, substitution(next))
+        }
       }
     }
 
-    case class GuardTreeMaker(guardTree: Tree) extends TreeMaker {
-      val localSubstitution: Substitution = EmptySubstitution
-      def chainBefore(next: Tree, pt: Type): Tree = codegen.flatMapGuard(substitution(guardTree), next)
+    case class GuardTreeMaker(guardTree: Tree) extends TreeMaker with NoNewBinders {
+      def chainBefore(next: Tree)(casegen: Casegen): Tree = casegen.flatMapGuard(substitution(guardTree), next)
       override def toString = "G("+ guardTree +")"
     }
 
@@ -978,49 +952,40 @@ class Foo(x: Other) { x._1 } // no error in this order
     // calls propagateSubstitution on the treemakers
     def combineCases(scrut: Tree, scrutSym: Symbol, casesRaw: List[List[TreeMaker]], pt: Type, owner: Symbol): Tree = {
       val casesNoSubstOnly = casesRaw map (propagateSubstitution(_, EmptySubstitution)) // drops SubstOnlyTreeMakers, since their effect is now contained in the TreeMakers that follow them
-      combineCasesNoSubstOnly(scrut, scrutSym, casesNoSubstOnly, pt, owner, CODE.MATCHERROR(_))
+      combineCasesNoSubstOnly(scrut, scrutSym, casesNoSubstOnly, pt, owner, casegen => CODE.MATCHERROR(_))
     }
 
-    def combineCasesNoSubstOnly(scrut: Tree, scrutSym: Symbol, casesNoSubstOnly: List[List[TreeMaker]], pt: Type, owner: Symbol, matchFail: Tree => Tree): Tree = fixerUpper(owner, scrut.pos){
-      emitSwitch(scrut, scrutSym, casesNoSubstOnly, pt).getOrElse{
-        val (matcher, hasDefault, toHoist) =
-          if (casesNoSubstOnly nonEmpty) {
-            // when specified, need to propagate pt explicitly (type inferencer can't handle it)
-            val optPt =
-              if (isFullyDefined(pt)) inMatchMonad(pt)
-              else NoType
-
-            // do this check on casesNoSubstOnly, since DCE will eliminate trivial cases like `case _ =>`, even if they're the last one
-            // exhaustivity and reachability must be checked before optimization as well
-            // TODO: improve, a trivial type test before the body still makes for a default case
-            // ("trivial" depends on whether we're emitting a straight match or an exception, or more generally, any supertype of scrutSym.tpe is a no-op)
-            val hasDefault = casesNoSubstOnly.nonEmpty && {
-              val nonTrivLast = casesNoSubstOnly.last
-              nonTrivLast.nonEmpty && nonTrivLast.head.isInstanceOf[BodyTreeMaker]
-            }
-
-            val (cases, toHoist) = optimizeCases(scrutSym, casesNoSubstOnly, pt)
-
-            val combinedCases =
-              cases.map(combineExtractors(_, pt)).reduceLeft(codegen.typedOrElse(optPt))
+    def combineCasesNoSubstOnly(scrut: Tree, scrutSym: Symbol, casesNoSubstOnly: List[List[TreeMaker]], pt: Type, owner: Symbol, matchFail: Casegen => Tree => Tree): Tree = fixerUpper(owner, scrut.pos){
+      val ptDefined = if (isFullyDefined(pt)) pt else NoType
 
-            (combinedCases, hasDefault, toHoist)
-          } else (codegen.zero, false, Nil)
-
-        // catch-all
-        val catchAll =
-          if (hasDefault) None // no need for a catch-all when there's already a default
-          else Some(matchFail)
-        val expr = codegen.runOrElse(scrut, scrutSym, matcher, if (isFullyDefined(pt)) pt else NoType, catchAll)
-        if (toHoist isEmpty) expr
-        else Block(toHoist, expr)
+      emitSwitch(scrut, scrutSym, casesNoSubstOnly, pt).getOrElse{
+        if (casesNoSubstOnly nonEmpty) {
+          // check casesNoSubstOnly for presence of a default case, since DCE will eliminate trivial cases like `case _ =>`, even if they're the last one
+          // exhaustivity and reachability must be checked before optimization as well
+          // TODO: improve, a trivial type test before the body still makes for a default case
+          // ("trivial" depends on whether we're emitting a straight match or an exception, or more generally, any supertype of scrutSym.tpe is a no-op)
+          val catchAll =
+            if (casesNoSubstOnly.nonEmpty && {
+                  val nonTrivLast = casesNoSubstOnly.last
+                  nonTrivLast.nonEmpty && nonTrivLast.head.isInstanceOf[BodyTreeMaker]
+                }) None
+            else Some(matchFail)
+
+          val (cases, toHoist) = optimizeCases(scrutSym, casesNoSubstOnly, pt)
+
+          val matchRes = codegen.matcher(scrut, scrutSym, pt)(cases map combineExtractors, catchAll)
+
+          if (toHoist isEmpty) matchRes else Block(toHoist, matchRes)
+        } else {
+          codegen.matcher(scrut, scrutSym, pt)(Nil, Some(matchFail))
+        }
       }
     }
 
     // combineExtractors changes the current substitution's of the tree makers in `treeMakers`
     // requires propagateSubstitution(treeMakers) has been called
-    def combineExtractors(treeMakers: List[TreeMaker], pt: Type): Tree =
-      treeMakers.foldRight (EmptyTree: Tree) (_.chainBefore(_, pt))
+    def combineExtractors(treeMakers: List[TreeMaker])(casegen: Casegen): Tree =
+      treeMakers.foldRight(EmptyTree: Tree)((a, b) => a.chainBefore(b)(casegen))
 
     // TODO: do this during tree construction, but that will require tracking the current owner in treemakers
     // TODO: assign more fine-grained positions
@@ -1070,34 +1035,36 @@ class Foo(x: Other) { x._1 } // no error in this order
 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
   trait CodegenCore extends MatchMonadInterface {
     private var ctr = 0
-    def freshSym(pos: Position, tp: Type = NoType, prefix: String = "x") = {ctr += 1;
-      // assert(owner ne null)
-      // assert(owner ne NoSymbol)
-      NoSymbol.newTermSymbol(vpmName.counted(prefix, ctr), pos) setInfo repackExistential(tp)
-    }
+    def freshName(prefix: String) = {ctr += 1; vpmName.counted(prefix, ctr)}
+
+    // assert(owner ne null); assert(owner ne NoSymbol)
+    def freshSym(pos: Position, tp: Type = NoType, prefix: String = "x") =
+      NoSymbol.newTermSymbol(freshName(prefix), pos) setInfo repackExistential(tp)
 
     // codegen relevant to the structure of the translation (how extractors are combined)
     trait AbsCodegen {
-      def runOrElse(scrut: Tree, scrutSym: Symbol, matcher: Tree, resTp: Type, catchAll: Option[Tree => Tree]): Tree
-      def one(res: Tree, bodyPt: Type, matchPt: Type): Tree
-      def zero: Tree
-      def flatMap(prev: Tree, b: Symbol, next: Tree): Tree
-      def typedOrElse(pt: Type)(thisCase: Tree, elseCase: Tree): Tree
+      def matcher(scrut: Tree, scrutSym: Symbol, restpe: Type)(cases: List[Casegen => Tree], catchAllGen: Option[Casegen => Tree => Tree]): Tree
 
-      def flatMapCond(cond: Tree, res: Tree, nextBinder: Symbol, nextBinderTp: Type, next: Tree): Tree
-      def flatMapGuard(cond: Tree, next: Tree): Tree
-
-      def fun(arg: Symbol, body: Tree): Tree
-      def ifThenElseZero(c: Tree, then: Tree): Tree
-      def _equals(checker: Tree, binder: Symbol): Tree
+      // local / context-free
       def _asInstanceOf(b: Symbol, tp: Type): Tree
+      def _equals(checker: Tree, binder: Symbol): Tree
+      def _isInstanceOf(b: Symbol, tp: Type): Tree
+      def and(a: Tree, b: Tree): Tree
+      def drop(tgt: Tree)(n: Int): Tree
+      def index(tgt: Tree)(i: Int): Tree
       def mkZero(tp: Type): Tree
-
       def tupleSel(binder: Symbol)(i: Int): Tree
-      def index(tgt: Tree)(i: Int): Tree
-      def drop(tgt: Tree)(n: Int): Tree
-      def and(a: Tree, b: Tree): Tree
-      def _isInstanceOf(b: Symbol, tp: Type): Tree
+    }
+
+    // structure
+    trait Casegen extends AbsCodegen { import CODE._
+      def one(res: Tree): Tree
+
+      def flatMap(prev: Tree, b: Symbol, next: Tree): Tree
+      def flatMapCond(cond: Tree, res: Tree, nextBinder: Symbol, next: Tree): Tree
+      def flatMapGuard(cond: Tree, next: Tree): Tree
+      def ifThenElseZero(c: Tree, then: Tree): Tree = IF (c) THEN then ELSE zero
+      protected def zero: Tree
     }
 
     def codegen: AbsCodegen
@@ -1112,7 +1079,6 @@ class Foo(x: Other) { x._1 } // no error in this order
       def drop(tgt: Tree)(n: Int): Tree                = (tgt DOT vpmName.drop) (LIT(n))
       def _equals(checker: Tree, binder: Symbol): Tree = checker MEMBER_== REF(binder)          // NOTE: checker must be the target of the ==, that's the patmat semantics for ya
       def and(a: Tree, b: Tree): Tree                  = a AND b
-      def ifThenElseZero(c: Tree, then: Tree): Tree     = IF (c) THEN then ELSE zero
 
       // the force is needed mainly to deal with the GADT typing hack (we can't detect it otherwise as tp nor pt need contain an abstract type, we're just casting wildly)
       def _asInstanceOf(t: Tree, tp: Type, force: Boolean = false): Tree      = { val tpX = repackExistential(tp)
@@ -1166,28 +1132,29 @@ class Foo(x: Other) { x._1 } // no error in this order
   trait PureCodegen extends CodegenCore with PureMatchMonadInterface {
     def codegen: AbsCodegen = pureCodegen
 
-    object pureCodegen extends CommonCodegen { import CODE._
+    object pureCodegen extends CommonCodegen with Casegen { import CODE._
       //// methods in MatchingStrategy (the monad companion) -- used directly in translation
       // __match.runOrElse(`scrut`)(`scrutSym` => `matcher`)
       // TODO: consider catchAll, or virtualized matching will break in exception handlers
-      def runOrElse(scrut: Tree, scrutSym: Symbol, matcher: Tree, resTp: Type, catchAll: Option[Tree => Tree]): Tree
-        = _match(vpmName.runOrElse) APPLY (scrut) APPLY (fun(scrutSym, matcher))
+      def matcher(scrut: Tree, scrutSym: Symbol, restpe: Type)(cases: List[Casegen => Tree], catchAllGen: Option[Casegen => Tree => Tree]): Tree =
+        _match(vpmName.runOrElse) APPLY (scrut) APPLY (fun(scrutSym, cases map (f => f(this)) reduceLeft typedOrElse))
+
       // __match.one(`res`)
-      def one(res: Tree, bodyPt: Type, matchPt: Type): Tree = (_match(vpmName.one)) (res)
+      def one(res: Tree): Tree = (_match(vpmName.one)) (res)
       // __match.zero
       def zero: Tree = _match(vpmName.zero)
       // __match.guard(`c`, `then`)
-      def guard(c: Tree, then: Tree, tp: Type): Tree = _match(vpmName.guard) APPLY (c, then)
+      def guard(c: Tree, then: Tree): Tree = _match(vpmName.guard) APPLY (c, then)
 
       //// methods in the monad instance -- used directly in translation
       // `prev`.flatMap(`b` => `next`)
       def flatMap(prev: Tree, b: Symbol, next: Tree): Tree = (prev DOT vpmName.flatMap)(fun(b, next))
       // `thisCase`.orElse(`elseCase`)
-      def typedOrElse(pt: Type)(thisCase: Tree, elseCase: Tree): Tree = (thisCase DOT vpmName.orElse) APPLY (elseCase)
+      def typedOrElse(thisCase: Tree, elseCase: Tree): Tree = (thisCase DOT vpmName.orElse) APPLY (elseCase)
       //  __match.guard(`cond`, `res`).flatMap(`nextBinder` => `next`)
-      def flatMapCond(cond: Tree, res: Tree, nextBinder: Symbol, nextBinderTp: Type, next: Tree): Tree = flatMap(guard(cond, res, nextBinderTp), nextBinder, next)
+      def flatMapCond(cond: Tree, res: Tree, nextBinder: Symbol, next: Tree): Tree = flatMap(guard(cond, res), nextBinder, next)
       //  __match.guard(`guardTree`, ()).flatMap((_: P[Unit]) => `next`)
-      def flatMapGuard(guardTree: Tree, next: Tree): Tree = flatMapCond(guardTree, CODE.UNIT, freshSym(guardTree.pos, pureType(UnitClass.tpe)), pureType(UnitClass.tpe), next)
+      def flatMapGuard(guardTree: Tree, next: Tree): Tree = flatMapCond(guardTree, CODE.UNIT, freshSym(guardTree.pos, pureType(UnitClass.tpe)), next)
     }
   }
 
@@ -1456,8 +1423,8 @@ class Foo(x: Other) { x._1 } // no error in this order
       }
 
       // TODO: finer-grained duplication
-      def chainBefore(next: Tree, pt: Type): Tree = // assert(codegen eq optimizedCodegen)
-        atPos(pos)(optimizedCodegen.flatMapCondStored(cond, storedCond, res, nextBinder, substitution(next).duplicate))
+      def chainBefore(next: Tree)(casegen: Casegen): Tree = // assert(codegen eq optimizedCodegen)
+        atPos(pos)(casegen.asInstanceOf[optimizedCodegen.OptimizedCasegen].flatMapCondStored(cond, storedCond, res, nextBinder, substitution(next).duplicate))
     }
 
     case class ReusingCondTreeMaker(sharedPrefix: List[Test], toReused: TreeMaker => TreeMaker) extends TreeMaker { import CODE._
@@ -1474,12 +1441,11 @@ class Foo(x: Other) { x._1 } // no error in this order
         oldSubs.foldLeft(Substitution(from, to))(_ >> _)
       }
 
-      def chainBefore(next: Tree, pt: Type): Tree = {
+      def chainBefore(next: Tree)(casegen: Casegen): Tree = {
         val cond = REF(dropped_priors.reverse.collectFirst{case (_, Some(ctm: ReusedCondTreeMaker)) => ctm}.get.storedCond)
 
-        IF (cond) THEN BLOCK(
-          substitution(next).duplicate // TODO: finer-grained duplication -- MUST duplicate though, or we'll get VerifyErrors since sharing trees confuses lambdalift, and its confusion it emits illegal casts (diagnosed by Grzegorz: checkcast T ; invokevirtual S.m, where T not a subtype of S)
-        ) ELSE codegen.zero
+        // TODO: finer-grained duplication -- MUST duplicate though, or we'll get VerifyErrors since sharing trees confuses lambdalift, and its confusion it emits illegal casts (diagnosed by Grzegorz: checkcast T ; invokevirtual S.m, where T not a subtype of S)
+        casegen.ifThenElseZero(cond, substitution(next).duplicate)
       }
     }
   }
@@ -1657,8 +1623,7 @@ class Foo(x: Other) { x._1 } // no error in this order
     // for example, `o.flatMap(f)` becomes `if(o == None) None else f(o.get)`, similarly for orElse and guard
     //   this is a special instance of the advanced inlining optimization that takes a method call on
     //   an object of a type that only has two concrete subclasses, and inlines both bodies, guarded by an if to distinguish the two cases
-    object optimizedCodegen extends CommonCodegen /*with AbsOptimizedCodegen*/ { import CODE._
-      lazy val zeroSym        = freshSym(NoPosition, optionType(NothingClass.tpe), "zero")
+    object optimizedCodegen extends CommonCodegen { import CODE._
 
       /** Inline runOrElse and get rid of Option allocations
        *
@@ -1666,67 +1631,90 @@ class Foo(x: Other) { x._1 } // no error in this order
        * the matcher's optional result is encoded as a flag, keepGoing, where keepGoing == true encodes result.isEmpty,
        * if keepGoing is false, the result Some(x) of the naive translation is encoded as matchRes == x
        */
-      @inline private def dontStore(tp: Type) = (tp.typeSymbol eq UnitClass) || (tp.typeSymbol eq NothingClass)
-      lazy val keepGoing = freshSym(NoPosition, BooleanClass.tpe, "keepGoing") setFlag MUTABLE
-      lazy val matchRes  = freshSym(NoPosition, AnyClass.tpe, "matchRes") setFlag MUTABLE
-      def runOrElse(scrut: Tree, scrutSym: Symbol, matcher: Tree, resTp: Type, catchAll: Option[Tree => Tree]) = {
-        matchRes.info = if (resTp ne NoType) resTp.widen else AnyClass.tpe // we don't always know resTp, and it might be AnyVal, in which case we can't assign NULL
-        if (dontStore(resTp)) matchRes resetFlag MUTABLE  // don't assign to Unit-typed var's, in fact, make it a val -- conveniently also works around SI-5245
-        BLOCK(
-          VAL(zeroSym)   === REF(NoneModule),       // TODO: can we just get rid of explicitly emitted zero? don't know how to do that as a local rewrite...
-          VAL(scrutSym)  === scrut,
-          VAL(matchRes)  === mkZero(matchRes.info), // must cast to deal with GADT typing, hence the private mkZero above
-          VAL(keepGoing) === TRUE,
-          matcher,
-          catchAll map { catchAllGen => (IF (REF(keepGoing)) THEN catchAllGen(REF(scrutSym)) ELSE REF(matchRes)) } getOrElse REF(matchRes)
-        )
-      }
+      def matcher(scrut: Tree, scrutSym: Symbol, restpe: Type)(cases: List[Casegen => Tree], catchAllGen: Option[Casegen => Tree => Tree]): Tree = {
+        val matchEnd = NoSymbol.newLabel(freshName("matchEnd"), NoPosition) setFlag (SYNTHETIC | Flags.CASE)
+        val matchRes = NoSymbol.newValueParameter(newTermName("x"), NoPosition, SYNTHETIC) setInfo restpe
+        matchEnd setInfo MethodType(List(matchRes), restpe)
+
+        def newCaseSym = NoSymbol.newLabel(freshName("case"), NoPosition) setInfo MethodType(Nil, restpe) setFlag (SYNTHETIC | Flags.CASE)
+        var nextCase = newCaseSym
+        def caseDef(mkCase: Casegen => Tree): Tree = {
+          val currCase = nextCase
+          nextCase = newCaseSym
+          val casegen = new OptimizedCasegen(matchEnd, nextCase)
+          LabelDef(currCase, Nil, mkCase(casegen))
+        }
 
-      // only used to wrap the RHS of a body
-      def one(res: Tree, bodyPt: Type, matchPt: Type): Tree = {
-        BLOCK(
-          REF(keepGoing) === FALSE, // comes before assignment to matchRes, so the latter is in tail positions (can ignore the trailing zero -- will disappear when we flatten blocks, which is TODO)
-          if (dontStore(matchPt)) res else (REF(matchRes) === res), // runOrElse hasn't been called yet, so matchRes.isMutable is irrelevant, also, tp may be a subtype of resTp used in runOrElse...
-          zero // to have a nice lub for lubs -- otherwise we'll get a boxed unit here -- TODO: get rid of all those dangling else zero's
+        def catchAll = catchAllGen map { catchAllGen =>
+          val casegen = new OptimizedCasegen(matchEnd, NoSymbol)
+          val scrutRef = if(scrutSym eq NoSymbol) EmptyTree else REF(scrutSym)
+          LabelDef(nextCase, Nil, catchAllGen(casegen)(scrutRef))
+        } toList
+
+        val prologue = if(scrutSym ne NoSymbol) List(VAL(scrutSym)  === scrut) else Nil
+        Block(
+          prologue ++ (cases map caseDef) ++ catchAll,
+          LabelDef(matchEnd, List(matchRes), REF(matchRes))
         )
       }
 
-      def zero: Tree = REF(zeroSym)
+      class OptimizedCasegen(matchEnd: Symbol, nextCase: Symbol) extends CommonCodegen with Casegen {
+        def matcher(scrut: Tree, scrutSym: Symbol, restpe: Type)(cases: List[Casegen => Tree], catchAllGen: Option[Casegen => Tree => Tree]): Tree =
+          optimizedCodegen.matcher(scrut, scrutSym, restpe)(cases, catchAllGen)
 
-      def flatMap(prev: Tree, b: Symbol, next: Tree): Tree = {
-        val tp      = inMatchMonad(b.tpe)
-        val prevSym = freshSym(prev.pos, tp, "o")
-        val isEmpty = tp member vpmName.isEmpty
-        val get     = tp member vpmName.get
+        def zero: Tree   = nextCase APPLY ()
 
-        BLOCK(
-          VAL(prevSym) === prev,
-          IF (prevSym DOT isEmpty) THEN zero ELSE Substitution(b, prevSym DOT get)(next) // must be isEmpty and get as we don't control the target of the call (could be the result of a user-defined extractor)
-        )
-      }
+        // only used to wrap the RHS of a body
+        // res: T
+        // returns MatchMonad[T]
+        def one(res: Tree): Tree = matchEnd APPLY (res)
 
-      def typedOrElse(pt: Type)(thisCase: Tree, elseCase: Tree): Tree = {
-        BLOCK(
-          thisCase,
-          IF (REF(keepGoing)) THEN elseCase ELSE zero // leave trailing zero for now, otherwise typer adds () anyway
-        )
+
+        override def ifThenElseZero(c: Tree, then: Tree): Tree =
+          IF (c) THEN then ELSE zero
+
+        // prev: MatchMonad[T]
+        // b: T
+        // next: MatchMonad[U]
+        // returns MatchMonad[U]
+        def flatMap(prev: Tree, b: Symbol, next: Tree): Tree = {
+          val tp      = inMatchMonad(b.tpe)
+          val prevSym = freshSym(prev.pos, tp, "o")
+          val isEmpty = tp member vpmName.isEmpty
+          val get     = tp member vpmName.get
+
+          BLOCK(
+            VAL(prevSym) === prev,
+            // must be isEmpty and get as we don't control the target of the call (prev is an extractor call)
+            ifThenElseZero(NOT(prevSym DOT isEmpty), Substitution(b, prevSym DOT get)(next))
+          )
+        }
+
+        // cond: Boolean
+        // res: T
+        // nextBinder: T
+        // next == MatchMonad[U]
+        // returns MatchMonad[U]
+        def flatMapCond(cond: Tree, res: Tree, nextBinder: Symbol, next: Tree): Tree =
+          ifThenElseZero(cond, BLOCK(
+            VAL(nextBinder) === res,
+            next
+          ))
+
+        // guardTree: Boolean
+        // next: MatchMonad[T]
+        // returns MatchMonad[T]
+        def flatMapGuard(guardTree: Tree, next: Tree): Tree =
+          ifThenElseZero(guardTree, next)
+
+        def flatMapCondStored(cond: Tree, condSym: Symbol, res: Tree, nextBinder: Symbol, next: Tree): Tree =
+          ifThenElseZero(cond, BLOCK(
+            condSym    === TRUE,
+            nextBinder === res,
+            next
+          ))
       }
 
-      def flatMapCond(cond: Tree, res: Tree, nextBinder: Symbol, nextBinderTp: Type, next: Tree): Tree =
-        IF (cond) THEN BLOCK(
-          VAL(nextBinder) === res,
-          next
-        ) ELSE zero
-
-      def flatMapCondStored(cond: Tree, condSym: Symbol, res: Tree, nextBinder: Symbol, next: Tree): Tree =
-        IF (cond) THEN BLOCK(
-          condSym    === TRUE,
-          nextBinder === res,
-          next
-        ) ELSE zero
-
-      def flatMapGuard(guardTree: Tree, next: Tree): Tree =
-        IF (guardTree) THEN next ELSE zero
     }
   }