[vpm] factored out optimizing codegen

2 files changed, 500 insertions, 472 deletions

diff --git a/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala b/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala
index aef85206fa..6d31243fd0 100644
--- a/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala
@@ -7,8 +7,7 @@ package scala.tools.nsc
 package typechecker
 
 import symtab._
-import Flags.{ CASE => _, _ }
-
+import Flags.{MUTABLE, METHOD, LABEL, SYNTHETIC}
 
 /** Translate pattern matching into method calls (these methods form a zero-plus monad), similar in spirit to how for-comprehensions are compiled.
   *
@@ -33,12 +32,90 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
   import global._
   import definitions._
 
-  class MatchTranslator(val typer: Typer) extends MatchCodeGen {
-    def typed(tree: Tree, mode: Int, pt: Type): Tree = typer.typed(tree, mode, pt) // for MatchCodeGen -- imports don't provide implementations for abstract members
+  object vpmName {
+    val one       = newTermName("one")
+    val drop      = newTermName("drop")
+    val flatMap   = newTermName("flatMap")
+    val get       = newTermName("get")
+    val guard     = newTermName("guard")
+    val isEmpty   = newTermName("isEmpty")
+    val orElse    = newTermName("orElse")
+    val outer     = newTermName("<outer>")
+    val runOrElse = newTermName("runOrElse")
+    val zero      = newTermName("zero")
+    val __match   = newTermName("__match")
+
+    def counted(str: String, i: Int) = newTermName(str+i)
+  }
+
+  object MatchTranslator {
+    def apply(typer: Typer): MatchTranslation = {
+      import typer._
+      // typing `__match` to decide which MatchTranslator to create adds 4% to quick.comp.timer
+      newTyper(context.makeImplicit(reportAmbiguousErrors = false)).silent(_.typed(Ident(vpmName.__match), EXPRmode, WildcardType), reportAmbiguousErrors = false) match {
+          case SilentResultValue(ms) => new PureMatchTranslator(typer, ms)
+          case _ => new OptimizingMatchTranslator(typer)
+        }
+    }
+  }
+
+  class PureMatchTranslator(val typer: Typer, val matchStrategy: Tree) extends MatchTranslation with TreeMakers with PureCodegen
+  class OptimizingMatchTranslator(val typer: Typer)                    extends MatchTranslation with TreeMakers with MatchOptimizations
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+// talking to userland
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+
+  /** Interface with user-defined match monad?
+   * if there's a `__match` in scope, we use this as the match strategy, assuming it conforms to MatchStrategy as defined below:
+
+       type Matcher[P[_], M[+_], A] = {
+         def flatMap[B](f: P[A] => M[B]): M[B]
+         def orElse[B >: A](alternative: => M[B]): M[B]
+       }
+
+       abstract class MatchStrategy[P[_], M[+_]] {
+         // runs the matcher on the given input
+         def runOrElse[T, U](in: P[T])(matcher: P[T] => M[U]): P[U]
+
+         def zero: M[Nothing]
+         def one[T](x: P[T]): M[T]
+         def guard[T](cond: P[Boolean], then: => P[T]): M[T]
+         def isSuccess[T, U](x: P[T])(f: P[T] => M[U]): P[Boolean] // used for isDefinedAt
+       }
+
+   * P and M are derived from one's signature (`def one[T](x: P[T]): M[T]`)
+
+
+   * if no `__match` is found, we assume the following implementation (and generate optimized code accordingly)
+
+       object __match extends MatchStrategy[({type Id[x] = x})#Id, Option] {
+         def zero = None
+         def one[T](x: T) = Some(x)
+         // NOTE: guard's return type must be of the shape M[T], where M is the monad in which the pattern match should be interpreted
+         def guard[T](cond: Boolean, then: => T): Option[T] = if(cond) Some(then) else None
+         def runOrElse[T, U](x: T)(f: T => Option[U]): U = f(x) getOrElse (throw new MatchError(x))
+         def isSuccess[T, U](x: T)(f: T => Option[U]): Boolean = !f(x).isEmpty
+       }
+
+   */
+  trait MatchMonadInterface {
+    val typer: Typer
+    val matchOwner = typer.context.owner
+
+    def inMatchMonad(tp: Type): Type
+    def pureType(tp: Type): Type
+    final def matchMonadResult(tp: Type): Type =
+      tp.baseType(matchMonadSym).typeArgs match {
+        case arg :: Nil => arg
+        case _ => ErrorType
+      }
 
-    import typer._
-    import typeDebug.{ ptTree, ptBlock, ptLine }
+    protected def matchMonadSym: Symbol
+  }
 
+  trait MatchTranslation extends MatchMonadInterface { self: TreeMakers with CodegenCore =>
+    import typer.{typed, context, silent, reallyExists}
 
     /** Implement a pattern match by turning its cases (including the implicit failure case)
       * into the corresponding (monadic) extractors, and combining them with the `orElse` combinator.
@@ -56,12 +133,17 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
       //  and the only place that emits Matches after typers is for exception handling anyway)
       assert(phase.id <= currentRun.typerPhase.id, phase)
 
+      def repeatedToSeq(tp: Type): Type = (tp baseType RepeatedParamClass) match {
+        case TypeRef(_, RepeatedParamClass, args) => appliedType(SeqClass.typeConstructor, args)
+        case _ => tp
+      }
+
       val scrutType = repeatedToSeq(elimAnonymousClass(scrut.tpe.widen))
 
       val scrutSym  = freshSym(scrut.pos, pureType(scrutType))
       val okPt = repeatedToSeq(pt)
       // pt = Any* occurs when compiling test/files/pos/annotDepMethType.scala  with -Xexperimental
-      combineCases(scrut, scrutSym, cases map translateCase(scrutSym, okPt), okPt, context.owner)
+      combineCases(scrut, scrutSym, cases map translateCase(scrutSym, okPt), okPt, matchOwner)
     }
 
 
@@ -497,81 +579,6 @@ class Foo(x: Other) { x._1 } // no error in this order
       override def toString() = extractorCall +": "+ extractorCall.tpe +" (symbol= "+ extractorCall.symbol +")."
     }
 
-    // tack an outer test onto `cond` if binder.info and expectedType warrant it
-    def maybeWithOuterCheck(binder: Symbol, expectedTp: Type)(cond: Tree): Tree = { import CODE._
-      if (   !((expectedTp.prefix eq NoPrefix) || expectedTp.prefix.typeSymbol.isPackageClass)
-          && needsOuterTest(expectedTp, binder.info, context.owner)) {
-        val expectedPrefix = expectedTp.prefix match {
-          case ThisType(clazz)  => THIS(clazz)
-          case pre              => REF(pre.prefix, pre.termSymbol)
-        }
-
-        // ExplicitOuter replaces `Select(q, outerSym) OBJ_EQ expectedPrefix` by `Select(q, outerAccessor(outerSym.owner)) OBJ_EQ expectedPrefix`
-        // if there's an outer accessor, otherwise the condition becomes `true` -- TODO: can we improve needsOuterTest so there's always an outerAccessor?
-        val outer = expectedTp.typeSymbol.newMethod(vpmName.outer) setInfo expectedTp.prefix setFlag SYNTHETIC
-        val outerCheck = (Select(codegen._asInstanceOf(binder, expectedTp), outer)) OBJ_EQ expectedPrefix
-
-        // first check cond, since that should ensure we're not selecting outer on null
-        codegen.and(cond, outerCheck)
-      }
-      else
-        cond
-    }
-
-    // TODO: also need to test when erasing pt loses crucial information (and if we can recover it using a manifest)
-    def needsTypeTest(tp: Type, pt: Type) = !(tp <:< pt)
-    def typeTest(binder: Symbol, pt: Type) = maybeWithOuterCheck(binder, pt)(codegen._isInstanceOf(binder, pt))
-
-    /** Type patterns consist of types, type variables, and wildcards. A type pattern T is of one of the following forms:
-        - A reference to a class C, p.C, or T#C.
-          This type pattern matches any non-null instance of the given class.
-          Note that the prefix of the class, if it is given, is relevant for determining class instances.
-          For instance, the pattern p.C matches only instances of classes C which were created with the path p as prefix.
-          The bottom types scala.Nothing and scala.Null cannot be used as type patterns, because they would match nothing in any case.
-
-        - A singleton type p.type.
-          This type pattern matches only the value denoted by the path p
-          (that is, a pattern match involved a comparison of the matched value with p using method eq in class AnyRef). // TODO: the actual pattern matcher uses ==, so that's what I'm using for now
-          // https://issues.scala-lang.org/browse/SI-4577 "pattern matcher, still disappointing us at equality time"
-
-        - A compound type pattern T1 with ... with Tn where each Ti is a type pat- tern.
-          This type pattern matches all values that are matched by each of the type patterns Ti.
-
-        - A parameterized type pattern T[a1,...,an], where the ai are type variable patterns or wildcards _.
-          This type pattern matches all values which match T for some arbitrary instantiation of the type variables and wildcards.
-          The bounds or alias type of these type variable are determined as described in (§8.3).
-
-        - A parameterized type pattern scala.Array[T1], where T1 is a type pattern. // TODO
-          This type pattern matches any non-null instance of type scala.Array[U1], where U1 is a type matched by T1.
-    **/
-
-    // generate the tree for the run-time test that follows from the fact that
-    // a `scrut` of known type `scrutTp` is expected to have type `expectedTp`
-    // uses maybeWithOuterCheck to check the type's prefix
-    def typeAndEqualityTest(patBinder: Symbol, pt: Type): Tree = { import CODE._
-       // TODO: `null match { x : T }` will yield a check that (indirectly) tests whether `null ne null`
-       // don't bother (so that we don't end up with the warning "comparing values of types Null and Null using `ne' will always yield false")
-      def genEqualsAndInstanceOf(sym: Symbol): Tree
-        = codegen._equals(REF(sym), patBinder) AND codegen._isInstanceOf(patBinder, pt.widen)
-
-      def isRefTp(tp: Type) = tp <:< AnyRefClass.tpe
-
-      val patBinderTp = patBinder.info.widen
-      def isMatchUnlessNull = isRefTp(pt) && !needsTypeTest(patBinderTp, pt)
-
-      // TODO: [SPEC] type test for Array
-      // TODO: use manifests to improve tests (for erased types we can do better when we have a manifest)
-      pt match {
-          case SingleType(_, sym) /*this implies sym.isStable*/ => genEqualsAndInstanceOf(sym) // TODO: [SPEC] the spec requires `eq` instead of `==` here
-          case ThisType(sym) if sym.isModule                    => genEqualsAndInstanceOf(sym) // must use == to support e.g. List() == Nil
-          case ThisType(sym)                                    => REF(patBinder) OBJ_EQ This(sym)
-          case ConstantType(Constant(null)) if isRefTp(patBinderTp) => REF(patBinder) OBJ_EQ NULL
-          case ConstantType(const)                              => codegen._equals(Literal(const), patBinder)
-          case _ if isMatchUnlessNull                           => maybeWithOuterCheck(patBinder, pt)(REF(patBinder) OBJ_NE NULL)
-          case _                                                => typeTest(patBinder, pt)
-        }
-    }
-
     /** A conservative approximation of which patterns do not discern anything.
      * They are discarded during the translation.
      */
@@ -597,94 +604,70 @@ class Foo(x: Other) { x._1 } // no error in this order
   }
 
 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
-// the making of the trees
+// substitution
 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
-  /** Interface with user-defined match monad?
-   * if there's a `__match` in scope, we use this as the match strategy, assuming it conforms to MatchStrategy as defined below:
-
-       type Matcher[P[_], M[+_], A] = {
-         def flatMap[B](f: P[A] => M[B]): M[B]
-         def orElse[B >: A](alternative: => M[B]): M[B]
-       }
-
-       abstract class MatchStrategy[P[_], M[+_]] {
-         // runs the matcher on the given input
-         def runOrElse[T, U](in: P[T])(matcher: P[T] => M[U]): P[U]
-
-         def zero: M[Nothing]
-         def one[T](x: P[T]): M[T]
-         def guard[T](cond: P[Boolean], then: => P[T]): M[T]
-         def isSuccess[T, U](x: P[T])(f: P[T] => M[U]): P[Boolean] // used for isDefinedAt
-       }
-
-   * P and M are derived from one's signature (`def one[T](x: P[T]): M[T]`)
-
-
-   * if no `__match` is found, we assume the following implementation (and generate optimized code accordingly)
-
-       object __match extends MatchStrategy[({type Id[x] = x})#Id, Option] {
-         def zero = None
-         def one[T](x: T) = Some(x)
-         // NOTE: guard's return type must be of the shape M[T], where M is the monad in which the pattern match should be interpreted
-         def guard[T](cond: Boolean, then: => T): Option[T] = if(cond) Some(then) else None
-         def runOrElse[T, U](x: T)(f: T => Option[U]): U = f(x) getOrElse (throw new MatchError(x))
-         def isSuccess[T, U](x: T)(f: T => Option[U]): Boolean = !f(x).isEmpty
-       }
-
-   */
-  trait MatchMonadInterface { import CODE._
-    val typer: Typer
-    import typer._
-
-    object vpmName {
-      val one       = newTermName("one")
-      val drop      = newTermName("drop")
-      val flatMap   = newTermName("flatMap")
-      val get       = newTermName("get")
-      val guard     = newTermName("guard")
-      val isEmpty   = newTermName("isEmpty")
-      val orElse    = newTermName("orElse")
-      val outer     = newTermName("<outer>")
-      val runOrElse = newTermName("runOrElse")
-      val zero      = newTermName("zero")
-      val __match   = newTermName("__match")
-
-      def counted(str: String, i: Int) = newTermName(str+i)
+  trait TypedSubstitution extends MatchMonadInterface {
+    object Substitution {
+      def apply(from: Symbol, to: Tree) = new Substitution(List(from), List(to))
+      // requires sameLength(from, to)
+      def apply(from: List[Symbol], to: List[Tree]) =
+        if (from nonEmpty) new Substitution(from, to) else EmptySubstitution
     }
 
-    final lazy val matchStrategy = // typing `__match` instead of just returning EmptyTree adds 4% to quick.comp.timer
-      newTyper(context.makeImplicit(reportAmbiguousErrors = false)).silent(_.typed(Ident(vpmName.__match), EXPRmode, WildcardType), reportAmbiguousErrors = false) match {
-        case SilentResultValue(ms) => ms
-        case _ => EmptyTree
+    class Substitution(val from: List[Symbol], val to: List[Tree]) {
+      // We must explicitly type the trees that we replace inside some other tree, since the latter may already have been typed,
+      // and will thus not be retyped. This means we might end up with untyped subtrees inside bigger, typed trees.
+      def apply(tree: Tree): Tree = {
+        // according to -Ystatistics 10% of translateMatch's time is spent in this method...
+        // since about half of the typedSubst's end up being no-ops, the check below shaves off 5% of the time spent in typedSubst
+        if (!tree.exists { case i@Ident(_) => from contains i.symbol case _ => false}) tree
+        else (new Transformer {
+          @inline private def typedIfOrigTyped(to: Tree, origTp: Type): Tree =
+            if (origTp == null || origTp == NoType) to
+            // important: only type when actually substing and when original tree was typed
+            // (don't need to use origTp as the expected type, though, and can't always do this anyway due to unknown type params stemming from polymorphic extractors)
+            else typer.typed(to, EXPRmode, WildcardType)
+
+          override def transform(tree: Tree): Tree = {
+            def subst(from: List[Symbol], to: List[Tree]): Tree =
+              if (from.isEmpty) tree
+              else if (tree.symbol == from.head) typedIfOrigTyped(to.head.shallowDuplicate, tree.tpe)
+              else subst(from.tail, to.tail)
+
+            tree match {
+              case Ident(_) => subst(from, to)
+              case _        => super.transform(tree)
+            }
+          }
+        }).transform(tree)
       }
 
-    final def optimizingCodeGen: Boolean = matchStrategy eq EmptyTree
-
-    def __match(n: Name): SelectStart = matchStrategy DOT n
-
-    private lazy val oneSig: Type =
-      typed(__match(vpmName.one), EXPRmode | POLYmode | TAPPmode | FUNmode, WildcardType).tpe  // TODO: error message
-
-    final def inMatchMonad(tp: Type): Type =
-      if(optimizingCodeGen) optionType(tp)
-      else appliedType(oneSig, List(tp)).finalResultType
 
-    private lazy val matchMonadSym =
-      if(optimizingCodeGen) OptionClass
-      else oneSig.finalResultType.typeSymbol
-
-    final def matchMonadResult(tp: Type): Type =
-      tp.baseType(matchMonadSym).typeArgs match {
-        case arg :: Nil => arg
-        case _ => ErrorType
+      // the substitution that chains `other` before `this` substitution
+      // forall t: Tree. this(other(t)) == (this >> other)(t)
+      def >>(other: Substitution): Substitution = {
+        val (fromFiltered, toFiltered) = (from, to).zipped filter { (f, t) =>  !other.from.contains(f) }
+        new Substitution(other.from ++ fromFiltered, other.to.map(apply) ++ toFiltered) // a quick benchmarking run indicates the `.map(apply)` is not too costly
       }
+      override def toString = (from zip to) mkString("Substitution(", ", ", ")")
+    }
 
-    final def pureType(tp: Type): Type =
-      if(optimizingCodeGen) tp
-      else appliedType(oneSig, List(tp)).paramTypes.head
+    object EmptySubstitution extends Substitution(Nil, Nil) {
+      override def apply(tree: Tree): Tree = tree
+      override def >>(other: Substitution): Substitution = other
+    }
   }
 
-  trait TreeMakers extends MatchMonadInterface {
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+// the making of the trees
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+  trait TreeMakers extends TypedSubstitution { self: CodegenCore =>
+    def optimizeCases(prevBinder: Symbol, cases: List[List[TreeMaker]], pt: Type): (List[List[TreeMaker]], List[Tree]) =
+      (cases, Nil)
+
+    def emitSwitch(scrut: Tree, scrutSym: Symbol, cases: List[List[TreeMaker]], pt: Type): Option[Tree] =
+      None
+
     abstract class TreeMaker {
       /** captures the scope and the value of the bindings in patterns
        * important *when* the substitution happens (can't accumulate and do at once after the full matcher has been constructed)
@@ -751,7 +734,7 @@ class Foo(x: Other) { x._1 } // no error in this order
      */
     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.condOptimized(_, next)) getOrElse next
+        val condAndNext = extraCond map (codegen.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))
@@ -766,12 +749,36 @@ class Foo(x: Other) { x._1 } // no error in this order
       def chainBefore(next: Tree, pt: Type): Tree = {
         val nullCheck = REF(prevBinder) OBJ_NE NULL
         val cond = extraCond map (nullCheck AND _) getOrElse nullCheck
-        codegen.condOptimized(cond, substitution(next))
+        codegen.ifThenElseZero(cond, substitution(next))
       }
 
       override def toString = "P"+(prevBinder,  extraCond getOrElse "", localSubstitution)
     }
 
+    // tack an outer test onto `cond` if binder.info and expectedType warrant it
+    def maybeWithOuterCheck(binder: Symbol, expectedTp: Type)(cond: Tree): Tree = { import CODE._
+      if (   !((expectedTp.prefix eq NoPrefix) || expectedTp.prefix.typeSymbol.isPackageClass)
+          && needsOuterTest(expectedTp, binder.info, matchOwner)) {
+        val expectedPrefix = expectedTp.prefix match {
+          case ThisType(clazz)  => THIS(clazz)
+          case pre              => REF(pre.prefix, pre.termSymbol)
+        }
+
+        // ExplicitOuter replaces `Select(q, outerSym) OBJ_EQ expectedPrefix` by `Select(q, outerAccessor(outerSym.owner)) OBJ_EQ expectedPrefix`
+        // if there's an outer accessor, otherwise the condition becomes `true` -- TODO: can we improve needsOuterTest so there's always an outerAccessor?
+        val outer = expectedTp.typeSymbol.newMethod(vpmName.outer) setInfo expectedTp.prefix setFlag SYNTHETIC
+        val outerCheck = (Select(codegen._asInstanceOf(binder, expectedTp), outer)) OBJ_EQ expectedPrefix
+
+        // first check cond, since that should ensure we're not selecting outer on null
+        codegen.and(cond, outerCheck)
+      }
+      else
+        cond
+    }
+
+    // TODO: also need to test when erasing pt loses crucial information (and if we can recover it using a manifest)
+    def needsTypeTest(tp: Type, pt: Type) = !(tp <:< pt)
+    private def typeTest(binder: Symbol, pt: Type) = maybeWithOuterCheck(binder, pt)(codegen._isInstanceOf(binder, pt))
 
     // need to substitute since binder may be used outside of the next extractor call (say, in the body of the case)
     case class TypeTestTreeMaker(prevBinder: Symbol, nextBinderTp: Type, pos: Position) extends CondTreeMaker {
@@ -784,6 +791,56 @@ class Foo(x: Other) { x._1 } // no error in this order
     case class TypeAndEqualityTestTreeMaker(prevBinder: Symbol, patBinder: Symbol, pt: Type, pos: Position) extends CondTreeMaker {
       val nextBinderTp = glb(List(patBinder.info.widen, pt))
 
+      /** Type patterns consist of types, type variables, and wildcards. A type pattern T is of one of the following forms:
+          - A reference to a class C, p.C, or T#C.
+            This type pattern matches any non-null instance of the given class.
+            Note that the prefix of the class, if it is given, is relevant for determining class instances.
+            For instance, the pattern p.C matches only instances of classes C which were created with the path p as prefix.
+            The bottom types scala.Nothing and scala.Null cannot be used as type patterns, because they would match nothing in any case.
+
+          - A singleton type p.type.
+            This type pattern matches only the value denoted by the path p
+            (that is, a pattern match involved a comparison of the matched value with p using method eq in class AnyRef). // TODO: the actual pattern matcher uses ==, so that's what I'm using for now
+            // https://issues.scala-lang.org/browse/SI-4577 "pattern matcher, still disappointing us at equality time"
+
+          - A compound type pattern T1 with ... with Tn where each Ti is a type pat- tern.
+            This type pattern matches all values that are matched by each of the type patterns Ti.
+
+          - A parameterized type pattern T[a1,...,an], where the ai are type variable patterns or wildcards _.
+            This type pattern matches all values which match T for some arbitrary instantiation of the type variables and wildcards.
+            The bounds or alias type of these type variable are determined as described in (§8.3).
+
+          - A parameterized type pattern scala.Array[T1], where T1 is a type pattern. // TODO
+            This type pattern matches any non-null instance of type scala.Array[U1], where U1 is a type matched by T1.
+      **/
+
+      // generate the tree for the run-time test that follows from the fact that
+      // a `scrut` of known type `scrutTp` is expected to have type `expectedTp`
+      // uses maybeWithOuterCheck to check the type's prefix
+      private def typeAndEqualityTest(patBinder: Symbol, pt: Type): Tree = { import CODE._
+         // TODO: `null match { x : T }` will yield a check that (indirectly) tests whether `null ne null`
+         // don't bother (so that we don't end up with the warning "comparing values of types Null and Null using `ne' will always yield false")
+        def genEqualsAndInstanceOf(sym: Symbol): Tree
+          = codegen._equals(REF(sym), patBinder) AND codegen._isInstanceOf(patBinder, pt.widen)
+
+        def isRefTp(tp: Type) = tp <:< AnyRefClass.tpe
+
+        val patBinderTp = patBinder.info.widen
+        def isMatchUnlessNull = isRefTp(pt) && !needsTypeTest(patBinderTp, pt)
+
+        // TODO: [SPEC] type test for Array
+        // TODO: use manifests to improve tests (for erased types we can do better when we have a manifest)
+        pt match {
+            case SingleType(_, sym) /*this implies sym.isStable*/ => genEqualsAndInstanceOf(sym) // TODO: [SPEC] the spec requires `eq` instead of `==` here
+            case ThisType(sym) if sym.isModule                    => genEqualsAndInstanceOf(sym) // must use == to support e.g. List() == Nil
+            case ThisType(sym)                                    => REF(patBinder) OBJ_EQ This(sym)
+            case ConstantType(Constant(null)) if isRefTp(patBinderTp) => REF(patBinder) OBJ_EQ NULL
+            case ConstantType(const)                              => codegen._equals(Literal(const), patBinder)
+            case _ if isMatchUnlessNull                           => maybeWithOuterCheck(patBinder, pt)(REF(patBinder) OBJ_NE NULL)
+            case _                                                => typeTest(patBinder, pt)
+          }
+      }
+
       val cond = typeAndEqualityTest(patBinder, pt)
       val res  = codegen._asInstanceOf(patBinder, nextBinderTp)
       override def toString = "TET"+(patBinder, pt)
@@ -855,10 +912,235 @@ class Foo(x: Other) { x._1 } // no error in this order
       override def toString = "G("+ guardTree +")"
     }
 
+    def removeSubstOnly(makers: List[TreeMaker]) = makers filterNot (_.isInstanceOf[SubstOnlyTreeMaker])
+
+    // a foldLeft to accumulate the localSubstitution left-to-right
+    // it drops SubstOnly tree makers, since their only goal in life is to propagate substitutions to the next tree maker, which is fullfilled by propagateSubstitution
+    def propagateSubstitution(treeMakers: List[TreeMaker], initial: Substitution): List[TreeMaker] = {
+      var accumSubst: Substitution = initial
+      treeMakers foreach { maker =>
+        maker incorporateOuterSubstitution accumSubst
+        accumSubst = maker.substitution
+      }
+      removeSubstOnly(treeMakers)
+    }
+
+    // calls propagateSubstitution on the treemakers
+    def combineCases(scrut: Tree, scrutSym: Symbol, casesRaw: List[List[TreeMaker]], pt: Type, owner: Symbol): Tree = fixerUpper(owner, scrut.pos){
+      val casesUnOpt = casesRaw map (propagateSubstitution(_, EmptySubstitution)) // drops SubstOnlyTreeMakers, since their effect is now contained in the TreeMakers that follow them
+
+      emitSwitch(scrut, scrutSym, casesUnOpt, pt).getOrElse{
+        val (matcher, hasDefault, toHoist) =
+          if (casesUnOpt 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 casesUnOpt, 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
+            val hasDefault = casesUnOpt.nonEmpty && {
+              val nonTrivLast = casesUnOpt.last
+              nonTrivLast.nonEmpty && nonTrivLast.head.isInstanceOf[BodyTreeMaker]
+            }
+
+            val (cases, toHoist) = optimizeCases(scrutSym, casesUnOpt, pt)
+
+            val combinedCases =
+              cases.map(combineExtractors(_, pt)).reduceLeft(codegen.typedOrElse(optPt))
+
+            (combinedCases, hasDefault, toHoist)
+          } else (codegen.zero, false, Nil)
+
+        val expr = codegen.runOrElse(scrut, scrutSym, matcher, if (isFullyDefined(pt)) pt else NoType, hasDefault)
+        if (toHoist isEmpty) expr
+        else Block(toHoist, expr)
+      }
+    }
+
+    // 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))
+
+    // TODO: do this during tree construction, but that will require tracking the current owner in treemakers
+    // TODO: assign more fine-grained positions
+    // fixes symbol nesting, assigns positions
+    private def fixerUpper(origOwner: Symbol, pos: Position) = new Traverser {
+      currentOwner = origOwner
+
+      override def traverse(t: Tree) {
+        if (t != EmptyTree && t.pos == NoPosition) {
+          t.setPos(pos)
+        }
+        t match {
+          case Function(_, _) if t.symbol == NoSymbol =>
+            t.symbol = currentOwner.newAnonymousFunctionValue(t.pos)
+            // println("new symbol for "+ (t, t.symbol.ownerChain))
+          case Function(_, _) if (t.symbol.owner == NoSymbol) || (t.symbol.owner == origOwner) =>
+            // println("fundef: "+ (t, t.symbol.ownerChain, currentOwner.ownerChain))
+            t.symbol.owner = currentOwner
+          case d : DefTree if (d.symbol != NoSymbol) && ((d.symbol.owner == NoSymbol) || (d.symbol.owner == origOwner)) => // don't indiscriminately change existing owners! (see e.g., pos/t3440, pos/t3534, pos/unapplyContexts2)
+            // println("def: "+ (d, d.symbol.ownerChain, currentOwner.ownerChain))
+            if(d.symbol.isLazy) { // for lazy val's accessor -- is there no tree??
+              assert(d.symbol.lazyAccessor != NoSymbol && d.symbol.lazyAccessor.owner == d.symbol.owner, d.symbol.lazyAccessor)
+              d.symbol.lazyAccessor.owner = currentOwner
+            }
+            if(d.symbol.moduleClass ne NoSymbol)
+              d.symbol.moduleClass.owner = currentOwner
+
+            d.symbol.owner = currentOwner
+          // case _ if (t.symbol != NoSymbol) && (t.symbol ne null) =>
+          //   println("untouched "+ (t, t.getClass, t.symbol.ownerChain, currentOwner.ownerChain))
+          case _ =>
+        }
+        super.traverse(t)
+      }
+
+      // override def apply
+      // println("before fixerupper: "+ xTree)
+      // currentRun.trackerFactory.snapshot()
+      // println("after fixerupper")
+      // currentRun.trackerFactory.snapshot()
+    }
+  }
+
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+// generate actual trees
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+  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)
+    }
+
+    // codegen relevant to the structure of the translation (how extractors are combined)
+    trait AbsCodegen {
+      def runOrElse(scrut: Tree, scrutSym: Symbol, matcher: Tree, resTp: Type, hasDefault: Boolean): 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 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
+      def _asInstanceOf(b: Symbol, tp: Type): 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
+    }
+
+    def codegen: AbsCodegen
+
+    def typesConform(tp: Type, pt: Type) = ((tp eq pt) || (tp <:< pt))
+
+    abstract class CommonCodegen extends AbsCodegen { import CODE._
+      def fun(arg: Symbol, body: Tree): Tree           = Function(List(ValDef(arg)), body)
+      def genTypeApply(tfun: Tree, args: Type*): Tree  = if(args contains NoType) tfun else TypeApply(tfun, args.toList map TypeTree)
+      def tupleSel(binder: Symbol)(i: Int): Tree       = (REF(binder) DOT nme.productAccessorName(i)) // make tree that accesses the i'th component of the tuple referenced by binder
+      def index(tgt: Tree)(i: Int): Tree               = tgt APPLY (LIT(i))
+      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)
+        if (!force && (t.tpe ne NoType) && t.isTyped && typesConform(t.tpe, tpX))  t //{ println("warning: emitted redundant asInstanceOf: "+(t, t.tpe, tp)); t } //.setType(tpX)
+        else gen.mkAsInstanceOf(t, tpX, true, false)
+      }
+
+      def _isInstanceOf(b: Symbol, tp: Type): Tree    = gen.mkIsInstanceOf(REF(b), repackExistential(tp), true, false)
+      // { val tpX = repackExistential(tp)
+      //   if (typesConform(b.info, tpX)) { println("warning: emitted spurious isInstanceOf: "+(b, tp)); TRUE }
+      //   else gen.mkIsInstanceOf(REF(b), tpX, true, false)
+      // }
+
+      def _asInstanceOf(b: Symbol, tp: Type): Tree    = { val tpX = repackExistential(tp)
+        if (typesConform(b.info, tpX)) REF(b) //{ println("warning: emitted redundant asInstanceOf: "+(b, b.info, tp)); REF(b) } //.setType(tpX)
+        else gen.mkAsInstanceOf(REF(b), tpX, true, false)
+      }
+
+      // duplicated out of frustration with cast generation
+      def mkZero(tp: Type): Tree = {
+        tp.typeSymbol match {
+          case UnitClass    => Literal(Constant())
+          case BooleanClass => Literal(Constant(false))
+          case FloatClass   => Literal(Constant(0.0f))
+          case DoubleClass  => Literal(Constant(0.0d))
+          case ByteClass    => Literal(Constant(0.toByte))
+          case ShortClass   => Literal(Constant(0.toShort))
+          case IntClass     => Literal(Constant(0))
+          case LongClass    => Literal(Constant(0L))
+          case CharClass    => Literal(Constant(0.toChar))
+          case _            => gen.mkAsInstanceOf(Literal(Constant(null)), tp, any = true, wrapInApply = false) // the magic incantation is true/false here
+        }
+      }
+    }
+  }
+
+  trait PureMatchMonadInterface extends MatchMonadInterface {
+    val matchStrategy: Tree
+
+    def inMatchMonad(tp: Type): Type = appliedType(oneSig, List(tp)).finalResultType
+    def pureType(tp: Type): Type     = appliedType(oneSig, List(tp)).paramTypes.head
+    protected def matchMonadSym      = oneSig.finalResultType.typeSymbol
+
+    import CODE._
+    def __match(n: Name): SelectStart = matchStrategy DOT n
+
+    private lazy val oneSig: Type =
+      typer.typed(__match(vpmName.one), EXPRmode | POLYmode | TAPPmode | FUNmode, WildcardType).tpe  // TODO: error message    
+  }
+
+  trait PureCodegen extends CodegenCore with PureMatchMonadInterface {
+    def codegen: AbsCodegen = pureCodegen
+
+    object pureCodegen extends CommonCodegen { import CODE._
+      //// methods in MatchingStrategy (the monad companion) -- used directly in translation
+      // __match.runOrElse(`scrut`)(`scrutSym` => `matcher`)
+      def runOrElse(scrut: Tree, scrutSym: Symbol, matcher: Tree, resTp: Type, hasDefault: Boolean): Tree
+        = __match(vpmName.runOrElse) APPLY (scrut) APPLY (fun(scrutSym, matcher))
+      // __match.one(`res`)
+      def one(res: Tree, bodyPt: Type, matchPt: Type): 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)
+
+      //// 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)
+      //  __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)
+      //  __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)
+    }
+  }
+
+
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+// OPTIMIZATIONS
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+
 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 // decisions, decisions
 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 
+  trait TreeMakerApproximation extends TreeMakers { self: CodegenCore =>
     object Test {
       var currId = 0
     }
@@ -951,27 +1233,16 @@ class Foo(x: Other) { x._1 } // no error in this order
       override def toString = testedPath +" (<: && ==) "+ pt +"#"+ id
     }
 
-//// CSE
-
-    /** a flow-sensitive, generalised, common sub-expression elimination
-     * reuse knowledge from performed tests
-     * the only sub-expressions we consider are the conditions and results of the three tests (type, type&equality, equality)
-     * when a sub-expression is share, it is stored in a mutable variable
-     * the variable is floated up so that its scope includes all of the program that shares it
-     * we generalize sharing to implication, where b reuses a if a => b and priors(a) => priors(b) (the priors of a sub expression form the path through the decision tree)
-     *
-     * intended to be generalised to exhaustivity/reachability checking
-     */
-    def doCSE(prevBinder: Symbol, cases: List[List[TreeMaker]], pt: Type): List[List[TreeMaker]] = {
+    def approximateMatch(root: Symbol, cases: List[List[TreeMaker]]): List[List[Test]] = {
       // a variable in this set should never be replaced by a tree that "does not consist of a selection on a variable in this set" (intuitively)
-      val pointsToBound            = collection.mutable.HashSet(prevBinder)
+      val pointsToBound            = collection.mutable.HashSet(root)
 
       // the substitution that renames variables to variables in pointsToBound
       var normalize: Substitution  = EmptySubstitution
 
       // replaces a variable (in pointsToBound) by a selection on another variable in pointsToBound
       // TODO check:
-      //   pointsToBound -- accumSubst.from == Set(prevBinder) && (accumSubst.from.toSet -- pointsToBound) isEmpty
+      //   pointsToBound -- accumSubst.from == Set(root) && (accumSubst.from.toSet -- pointsToBound) isEmpty
       var accumSubst: Substitution = EmptySubstitution
 
       val trees = new collection.mutable.HashSet[Tree]
@@ -1032,7 +1303,23 @@ class Foo(x: Other) { x._1 } // no error in this order
         }, tm)
       }
 
-      val testss = cases.map { _ map approximateTreeMaker }
+      cases.map { _ map approximateTreeMaker }
+    }
+  }
+
+////
+  trait CommonSubconditionElimination extends TreeMakerApproximation { self: OptimizedCodegen =>
+    /** a flow-sensitive, generalised, common sub-expression elimination
+     * reuse knowledge from performed tests
+     * the only sub-expressions we consider are the conditions and results of the three tests (type, type&equality, equality)
+     * when a sub-expression is share, it is stored in a mutable variable
+     * the variable is floated up so that its scope includes all of the program that shares it
+     * we generalize sharing to implication, where b reuses a if a => b and priors(a) => priors(b) (the priors of a sub expression form the path through the decision tree)
+     *
+     * intended to be generalised to exhaustivity/reachability checking
+     */
+    def doCSE(prevBinder: Symbol, cases: List[List[TreeMaker]], pt: Type): List[List[TreeMaker]] = {
+      val testss = approximateMatch(prevBinder, cases)
 
       // interpret:
       val dependencies = new collection.mutable.LinkedHashMap[Test, Set[Cond]]
@@ -1109,8 +1396,8 @@ class Foo(x: Other) { x._1 } // no error in this order
       }
 
       // TODO: finer-grained duplication
-      def chainBefore(next: Tree, pt: Type): Tree =
-        atPos(pos)(codegenOpt.flatMapCondStored(cond, storedCond, res, nextBinder, substitution(next).duplicate))
+      def chainBefore(next: Tree, pt: Type): Tree = // assert(codegen eq optimizedCodegen)
+        atPos(pos)(optimizedCodegen.flatMapCondStored(cond, storedCond, res, nextBinder, substitution(next).duplicate))
     }
 
     case class ReusingCondTreeMaker(sharedPrefix: List[Test], toReused: TreeMaker => TreeMaker) extends TreeMaker { import CODE._
@@ -1135,10 +1422,11 @@ class Foo(x: Other) { x._1 } // no error in this order
         ) ELSE codegen.zero
       }
     }
+  }
 
 
-//// DCE
-
+  //// DCE
+  trait DeadCodeElimination extends TreeMakers { self: CodegenCore =>
     // TODO: non-trivial dead-code elimination
     // e.g., the following match should compile to a simple instanceof:
     //   case class Ident(name: String)
@@ -1147,10 +1435,10 @@ class Foo(x: Other) { x._1 } // no error in this order
       // do minimal DCE
       cases
     }
+  }
 
-
-//// SWITCHES
-
+  //// SWITCHES
+  trait SwitchEmission extends TreeMakers with OptimizedMatchMonadInterface { self: CodegenCore =>
     object SwitchablePattern { def unapply(pat: Tree) = pat match {
       case Literal(Constant((_: Byte ) | (_: Short) | (_: Int  ) | (_: Char ))) => true // TODO: Java 7 allows strings in switches
       case _                                                                    => false
@@ -1167,7 +1455,7 @@ class Foo(x: Other) { x._1 } // no error in this order
 
     private val switchableTpes = Set(ByteClass.tpe, ShortClass.tpe, IntClass.tpe, CharClass.tpe)
 
-    def emitSwitch(scrut: Tree, scrutSym: Symbol, cases: List[List[TreeMaker]], pt: Type): Option[Tree] = if (!optimizingCodeGen) None else {
+    override def emitSwitch(scrut: Tree, scrutSym: Symbol, cases: List[List[TreeMaker]], pt: Type): Option[Tree] = {
       def sequence[T](xs: List[Option[T]]): Option[List[T]] =
         if (xs exists (_.isEmpty)) None else Some(xs.flatten)
 
@@ -1208,7 +1496,7 @@ class Foo(x: Other) { x._1 } // no error in this order
       }
 
       if (!isSwitchableTpe(scrut.tpe))
-        None
+        None // TODO: emit a cast of the scrutinee and a switch on the cast scrutinee if patterns allow switch but the type of the scrutinee doesn't
       else {
         sequence(caseDefs) map { caseDefs =>
           import CODE._
@@ -1238,216 +1526,27 @@ class Foo(x: Other) { x._1 } // no error in this order
         }
       }
     }
-
-    def optimizeCases(prevBinder: Symbol, cases: List[List[TreeMaker]], pt: Type): List[List[TreeMaker]] =
-      doCSE(prevBinder, doDCE(prevBinder, cases, pt), pt)
-
-
-    def removeSubstOnly(makers: List[TreeMaker]) = makers filterNot (_.isInstanceOf[SubstOnlyTreeMaker])
-
-    // a foldLeft to accumulate the localSubstitution left-to-right
-    // it drops SubstOnly tree makers, since their only goal in life is to propagate substitutions to the next tree maker, which is fullfilled by propagateSubstitution
-    def propagateSubstitution(treeMakers: List[TreeMaker], initial: Substitution): List[TreeMaker] = {
-      var accumSubst: Substitution = initial
-      treeMakers foreach { maker =>
-        maker incorporateOuterSubstitution accumSubst
-        accumSubst = maker.substitution
-      }
-      removeSubstOnly(treeMakers)
-    }
-
-    // calls propagateSubstitution on the treemakers
-    def combineCases(scrut: Tree, scrutSym: Symbol, casesRaw: List[List[TreeMaker]], pt: Type, owner: Symbol): Tree = fixerUpper(owner, scrut.pos){
-      val casesUnOpt = casesRaw map (propagateSubstitution(_, EmptySubstitution)) // drops SubstOnlyTreeMakers, since their effect is now contained in the TreeMakers that follow them
-
-      emitSwitch(scrut, scrutSym, casesUnOpt, pt).getOrElse{
-        var toHoist = List[Tree]()
-        val (matcher, hasDefault) =
-          if (casesUnOpt 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 casesUnOpt, 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
-            val hasDefault = casesUnOpt.nonEmpty && {
-              val nonTrivLast = casesUnOpt.last
-              nonTrivLast.nonEmpty && nonTrivLast.head.isInstanceOf[BodyTreeMaker]
-            }
-
-            val cases =
-              if (optimizingCodeGen) optimizeCases(scrutSym, casesUnOpt, pt)
-              else casesUnOpt
-
-            val combinedCases =
-              cases.map(combineExtractors(_, pt)).reduceLeft(codegen.typedOrElse(optPt))
-
-            toHoist = (
-              for (treeMakers <- cases)
-                yield treeMakers.collect{case tm: ReusedCondTreeMaker => tm.treesToHoist}
-              ).flatten.flatten.toList
-
-            (combinedCases, hasDefault)
-          } else (codegen.zero, false)
-
-        val expr = codegen.runOrElse(scrut, scrutSym, matcher, if (isFullyDefined(pt)) pt else NoType, hasDefault)
-        if (toHoist isEmpty) expr
-        else Block(toHoist, expr)
-      }
-    }
-
-    // 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))
-
-    // TODO: do this during tree construction, but that will require tracking the current owner in treemakers
-    // TODO: assign more fine-grained positions
-    // fixes symbol nesting, assigns positions
-    private def fixerUpper(origOwner: Symbol, pos: Position) = new Traverser {
-      currentOwner = origOwner
-
-      override def traverse(t: Tree) {
-        if (t != EmptyTree && t.pos == NoPosition) {
-          t.setPos(pos)
-        }
-        t match {
-          case Function(_, _) if t.symbol == NoSymbol =>
-            t.symbol = currentOwner.newAnonymousFunctionValue(t.pos)
-            // println("new symbol for "+ (t, t.symbol.ownerChain))
-          case Function(_, _) if (t.symbol.owner == NoSymbol) || (t.symbol.owner == origOwner) =>
-            // println("fundef: "+ (t, t.symbol.ownerChain, currentOwner.ownerChain))
-            t.symbol.owner = currentOwner
-          case d : DefTree if (d.symbol != NoSymbol) && ((d.symbol.owner == NoSymbol) || (d.symbol.owner == origOwner)) => // don't indiscriminately change existing owners! (see e.g., pos/t3440, pos/t3534, pos/unapplyContexts2)
-            // println("def: "+ (d, d.symbol.ownerChain, currentOwner.ownerChain))
-            if(d.symbol.isLazy) { // for lazy val's accessor -- is there no tree??
-              assert(d.symbol.lazyAccessor != NoSymbol && d.symbol.lazyAccessor.owner == d.symbol.owner, d.symbol.lazyAccessor)
-              d.symbol.lazyAccessor.owner = currentOwner
-            }
-            if(d.symbol.moduleClass ne NoSymbol)
-              d.symbol.moduleClass.owner = currentOwner
-
-            d.symbol.owner = currentOwner
-          // case _ if (t.symbol != NoSymbol) && (t.symbol ne null) =>
-          //   println("untouched "+ (t, t.getClass, t.symbol.ownerChain, currentOwner.ownerChain))
-          case _ =>
-        }
-        super.traverse(t)
-      }
-
-      // override def apply
-      // println("before fixerupper: "+ xTree)
-      // currentRun.trackerFactory.snapshot()
-      // println("after fixerupper")
-      // currentRun.trackerFactory.snapshot()
-    }
-
-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
-// substitution
-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
-
-    object Substitution {
-      def apply(from: Symbol, to: Tree) = new Substitution(List(from), List(to))
-      // requires sameLength(from, to)
-      def apply(from: List[Symbol], to: List[Tree]) =
-        if (from nonEmpty) new Substitution(from, to) else EmptySubstitution
-    }
-
-    class Substitution(val from: List[Symbol], val to: List[Tree]) {
-      def apply(tree: Tree): Tree = typedSubst(tree, from, to)
-
-      // the substitution that chains `other` before `this` substitution
-      // forall t: Tree. this(other(t)) == (this >> other)(t)
-      def >>(other: Substitution): Substitution = {
-        val (fromFiltered, toFiltered) = (from, to).zipped filter { (f, t) =>  !other.from.contains(f) }
-        new Substitution(other.from ++ fromFiltered, other.to.map(apply) ++ toFiltered) // a quick benchmarking run indicates the `.map(apply)` is not too costly
-      }
-      override def toString = (from zip to) mkString("Substitution(", ", ", ")")
-    }
-
-    object EmptySubstitution extends Substitution(Nil, Nil) {
-      override def apply(tree: Tree): Tree = tree
-      override def >>(other: Substitution): Substitution = other
-    }
-
-
-    def typedSubst(tree: Tree, from: List[Symbol], to: List[Tree]): Tree
-    def freshSym(pos: Position, tp: Type = NoType, prefix: String = "x"): Symbol
-    def typeAndEqualityTest(patBinder: Symbol, pt: Type): Tree
-    def typeTest(binder: Symbol, pt: Type): Tree
-
-    // codegen relevant to the structure of the translation (how extractors are combined)
-    trait AbsCodeGen {
-      def runOrElse(scrut: Tree, scrutSym: Symbol, matcher: Tree, resTp: Type, hasDefault: Boolean): 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 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 condOptimized(c: Tree, then: Tree): Tree
-      def _equals(checker: Tree, binder: Symbol): Tree
-      def _asInstanceOf(b: Symbol, tp: Type): 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
-    }
-
-    trait AbsOptimizedCodeGen extends AbsCodeGen {
-      def flatMapCondStored(cond: Tree, condSym: Symbol, res: Tree, nextBinder: Symbol, next: Tree): Tree
-    }
-
-    def codegen: AbsCodeGen
-    def codegenOpt: AbsOptimizedCodeGen = codegen.asInstanceOf[AbsOptimizedCodeGen]
-
-    def typed(tree: Tree, mode: Int, pt: Type): Tree // implemented in MatchTranslator
   }
 
-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
-// generate actual trees
-///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
-
-  trait MatchCodeGen extends TreeMakers {
-    lazy val codegen: AbsCodeGen = if (optimizingCodeGen) new OptimizedCodeGen else new NaiveCodeGen
-
-    import CODE._
+  trait OptimizedMatchMonadInterface extends MatchMonadInterface {
+    override def inMatchMonad(tp: Type): Type = optionType(tp)
+    override def pureType(tp: Type): Type     = tp
+    override protected def matchMonadSym      = OptionClass
+  }
 
-    class NaiveCodeGen extends CommonCodeGen {
-      //// methods in MatchingStrategy (the monad companion) -- used directly in translation
-      // __match.runOrElse(`scrut`)(`scrutSym` => `matcher`)
-      def runOrElse(scrut: Tree, scrutSym: Symbol, matcher: Tree, resTp: Type, hasDefault: Boolean): Tree
-        = __match(vpmName.runOrElse) APPLY (scrut) APPLY (fun(scrutSym, matcher))
-      // __match.one(`res`)
-      def one(res: Tree, bodyPt: Type, matchPt: Type): 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)
+  trait OptimizedCodegen extends CodegenCore with TypedSubstitution with OptimizedMatchMonadInterface {
+    override def codegen: AbsCodegen = optimizedCodegen
 
-      //// 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)
-      //  __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)
-      //  __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)
-    }
+    // trait AbsOptimizedCodegen extends AbsCodegen {
+    //   def flatMapCondStored(cond: Tree, condSym: Symbol, res: Tree, nextBinder: Symbol, next: Tree): Tree
+    // }
+    // def optimizedCodegen: AbsOptimizedCodegen
 
     // when we know we're targetting Option, do some inlining the optimizer won't do
     // 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
-    class OptimizedCodeGen extends CommonCodeGen with AbsOptimizedCodeGen {
+    object optimizedCodegen extends CommonCodegen /*with AbsOptimizedCodegen*/ { import CODE._
       lazy val zeroSym        = freshSym(NoPosition, optionType(NothingClass.tpe), "zero")
 
       /** Inline runOrElse and get rid of Option allocations
@@ -1493,7 +1592,7 @@ class Foo(x: Other) { x._1 } // no error in this order
 
         BLOCK(
           VAL(prevSym) === prev,
-          IF (prevSym DOT isEmpty) THEN zero ELSE typedSubst(next, List(b), List(prevSym DOT get)) // must be isEmpty and get as we don't control the target of the call (could be the result of a user-defined extractor)
+          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)
         )
       }
 
@@ -1520,91 +1619,20 @@ class Foo(x: Other) { x._1 } // no error in this order
       def flatMapGuard(guardTree: Tree, next: Tree): Tree =
         IF (guardTree) THEN next ELSE zero
     }
+  }
 
-    @inline private def typedIfOrigTyped(to: Tree, origTp: Type): Tree =
-      if (origTp == null || origTp == NoType) to
-      // important: only type when actually substing and when original tree was typed
-      // (don't need to use origTp as the expected type, though, and can't always do this anyway due to unknown type params stemming from polymorphic extractors)
-      else typed(to, EXPRmode, WildcardType)
-
-    // We must explicitly type the trees that we replace inside some other tree, since the latter may already have been typed,
-    // and will thus not be retyped. This means we might end up with untyped subtrees inside bigger, typed trees.
-    def typedSubst(tree: Tree, from: List[Symbol], to: List[Tree]): Tree = {
-      // according to -Ystatistics 10% of translateMatch's time is spent in this method...
-      // since about half of the typedSubst's end up being no-ops, the check below shaves off 5% of the time spent in typedSubst
-      if (!tree.exists { case i@Ident(_) => from contains i.symbol case _ => false}) tree
-      else (new Transformer {
-        override def transform(tree: Tree): Tree = {
-          def subst(from: List[Symbol], to: List[Tree]): Tree =
-            if (from.isEmpty) tree
-            else if (tree.symbol == from.head) typedIfOrigTyped(to.head.shallowDuplicate, tree.tpe)
-            else subst(from.tail, to.tail)
-
-          tree match {
-            case Ident(_) => subst(from, to)
-            case _        => super.transform(tree)
-          }
-        }
-      }).transform(tree)
-    }
-
-    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 repeatedToSeq(tp: Type): Type = (tp baseType RepeatedParamClass) match {
-      case TypeRef(_, RepeatedParamClass, args) => appliedType(SeqClass.typeConstructor, args)
-      case _ => tp
-    }
-
-
-    def typesConform(tp: Type, pt: Type) = ((tp eq pt) || (tp <:< pt))
-
-    abstract class CommonCodeGen extends AbsCodeGen {
-      def fun(arg: Symbol, body: Tree): Tree           = Function(List(ValDef(arg)), body)
-      def genTypeApply(tfun: Tree, args: Type*): Tree  = if(args contains NoType) tfun else TypeApply(tfun, args.toList map TypeTree)
-      def tupleSel(binder: Symbol)(i: Int): Tree       = (REF(binder) DOT nme.productAccessorName(i)) // make tree that accesses the i'th component of the tuple referenced by binder
-      def index(tgt: Tree)(i: Int): Tree               = tgt APPLY (LIT(i))
-      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 condOptimized(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)
-        if (!force && (t.tpe ne NoType) && t.isTyped && typesConform(t.tpe, tpX))  t //{ println("warning: emitted redundant asInstanceOf: "+(t, t.tpe, tp)); t } //.setType(tpX)
-        else gen.mkAsInstanceOf(t, tpX, true, false)
-      }
-
-      def _isInstanceOf(b: Symbol, tp: Type): Tree    = gen.mkIsInstanceOf(REF(b), repackExistential(tp), true, false)
-      // { val tpX = repackExistential(tp)
-      //   if (typesConform(b.info, tpX)) { println("warning: emitted spurious isInstanceOf: "+(b, tp)); TRUE }
-      //   else gen.mkIsInstanceOf(REF(b), tpX, true, false)
-      // }
 
-      def _asInstanceOf(b: Symbol, tp: Type): Tree    = { val tpX = repackExistential(tp)
-        if (typesConform(b.info, tpX)) REF(b) //{ println("warning: emitted redundant asInstanceOf: "+(b, b.info, tp)); REF(b) } //.setType(tpX)
-        else gen.mkAsInstanceOf(REF(b), tpX, true, false)
-      }
-
-      // duplicated out of frustration with cast generation
-      def mkZero(tp: Type): Tree = {
-        tp.typeSymbol match {
-          case UnitClass    => Literal(Constant())
-          case BooleanClass => Literal(Constant(false))
-          case FloatClass   => Literal(Constant(0.0f))
-          case DoubleClass  => Literal(Constant(0.0d))
-          case ByteClass    => Literal(Constant(0.toByte))
-          case ShortClass   => Literal(Constant(0.toShort))
-          case IntClass     => Literal(Constant(0))
-          case LongClass    => Literal(Constant(0L))
-          case CharClass    => Literal(Constant(0.toChar))
-          case _            => gen.mkAsInstanceOf(Literal(Constant(null)), tp, any = true, wrapInApply = false) // the magic incantation is true/false here
-        }
-      }
+  trait MatchOptimizations extends CommonSubconditionElimination
+                              with DeadCodeElimination
+                              with SwitchEmission
+                              with OptimizedCodegen { self: TreeMakers =>
+    override def optimizeCases(prevBinder: Symbol, cases: List[List[TreeMaker]], pt: Type): (List[List[TreeMaker]], List[Tree]) = {
+      val optCases = doCSE(prevBinder, doDCE(prevBinder, cases, pt), pt)
+      val toHoist = (
+        for (treeMakers <- optCases)
+          yield treeMakers.collect{case tm: ReusedCondTreeMaker => tm.treesToHoist}
+        ).flatten.flatten.toList
+      (optCases, toHoist)
     }
   }
 }
diff --git a/src/compiler/scala/tools/nsc/typechecker/Typers.scala b/src/compiler/scala/tools/nsc/typechecker/Typers.scala
index d3ff331f98..84f1d1ed6f 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Typers.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Typers.scala
@@ -3297,7 +3297,7 @@ trait Typers extends Modes with Adaptations with PatMatVirtualiser {
             val owntype = elimAnonymousClass(owntype0)
             if (needAdapt) cases1 = cases1 map (adaptCase(_, owntype))
 
-            (new MatchTranslator(this)).translateMatch(selector1, cases1, owntype) match {
+            (MatchTranslator(this)).translateMatch(selector1, cases1, owntype) match {
               case Block(vd :: Nil, tree@Match(selector, cases)) =>
                 val selector1 = checkDead(typed(selector, EXPRmode | BYVALmode, WildcardType))
                 var cases1 = typedCases(tree, cases, packCaptured(selector1.tpe.widen), pt)