[vpm] common sub-expression elimination for conditions

TreeMakers (esp. CondTreeMakers) are approximated by hash-cons'ed Conds
sharing is detected for prefixes of Conds, and shared conditions are only tested once
their results are stored, and repeated tests branch on the last shared condition,
reusing the results from the first time they were checked

a Test is 1-to-1 with a TreeMaker, but may share its Cond

TODO: clean separation of the two translation strategies:
	- naive flatMap/orElse (for virtualization)
	- less-naive if-then-else (with CSE etc coming)

sharing trees caused wrong bytecode to be emitted (verifyerror)
tentative explanation:
"because lambdalift uses mutable state to track which variables have been captured
if you refer to the same variable with the same tree twice
it'll get confused"

 Sent at 8:27 PM on Thursday
>> grzegorz.kossakowski:  so we found a bug in jvm
according to http://java.sun.com/docs/books/jvms/second_edition/html/Instructions2.doc2.html
checkcast should throw a classcastexception
becuase it's a shorthand for if !(x instanceof T) throw ClassCastExcpt
but jvm decided to throw verifyerror
and yeah, the check is wrong
if jvm was not throwing verifyerror it would throw classcast exception
saying that ObjectRef cannot be casted to $colon$colon
...
>> me:
so now where does it come from?
since a ref is involved, i thought LambdaLift
>> grzegorz.kossakowski:  yup
or now
I don't think lambalift introduces that kind of low-level casts
but I might be wrong
btw. it's interesting that it unpacks stuff from objectref twice
in your code
and in one place checkcast is correct
and in another is wrong
 Sent at 9:33 PM on Thursday
>> grzegorz.kossakowski:  also, since it's a verifyerror
I think genjvm should have an assertion

>> grzegorz.kossakowski:
  193:        getfield        #54; //Field scala/runtime/ObjectRef.elem:Ljava/lang/Object;
  196:        checkcast        #8; //class scala/runtime/ObjectRef
  199:        invokevirtual        #95; //Method scala/collection/immutable/$colon$colon.tl$1:()Lscala/collection/immutable/List;
it's this
see
you have checkcast for ObjectRef
and then on that value, you try to call tl() method from List

 Sent at 9:56 PM on Thursday
>> me:  fixed
sharing trees is bad
very bad
because lambdalift uses mutable state to track which variables have been captured
if you refer to the same variable with the same tree twice
it'll get confused

5 files changed, 456 insertions, 81 deletions

diff --git a/src/compiler/scala/tools/nsc/transform/UnCurry.scala b/src/compiler/scala/tools/nsc/transform/UnCurry.scala
index 769ef79546..2921607c24 100644
--- a/src/compiler/scala/tools/nsc/transform/UnCurry.scala
+++ b/src/compiler/scala/tools/nsc/transform/UnCurry.scala
@@ -290,7 +290,26 @@ abstract class UnCurry extends InfoTransform
           val idparam = m.paramss.head.head
           val substParam = new TreeSymSubstituter(List(vparam), List(idparam))
           def substTree[T <: Tree](t: T): T = substParam(resetLocalAttrs(t))
-
+          object VirtPatmatOpt {
+            object Last {
+              def unapply[T](xs: List[T]) = xs.lastOption
+            }
+            // keep this in synch by what's generated by combineCases/runOrElse
+            object MatcherBlock {
+              def unapply(matcher: Tree): Option[(ValDef, ValDef, ValDef, ValDef, List[Tree])] = matcher match { // TODO: BUG the unapplySeq version of the case below does not seem to work in virtpatmat??
+                case Block((zero: ValDef) :: (x: ValDef) :: (matchRes: ValDef) :: (keepGoing: ValDef) :: stats, _) => Some(zero, x, matchRes, keepGoing, stats)
+                case _ => None
+              }
+            }
+            // TODO: virtpatmat use case: would be nice if could abstract over the repeated pattern more easily
+            // case Block(Last(P)) =>
+            // case P =>
+            def unapply(matcher: Tree): Option[(ValDef, ValDef, ValDef, ValDef, List[Tree], Tree => Tree)] = matcher match {
+              case MatcherBlock(zero, x, matchRes, keepGoing, stats) => Some(zero, x, matchRes, keepGoing, stats, identity[Tree])
+              case Block(outerStats, MatcherBlock(zero, x, matchRes, keepGoing, stats)) => Some(zero, x, matchRes, keepGoing, stats, inner => Block(outerStats, inner))
+              case b => treeBrowser browse b; None
+            }
+          }
           DefDef(m, (fun.body: @unchecked) match {
             case Match(selector, cases) =>
               def transformCase(cdef: CaseDef): CaseDef =
@@ -301,6 +320,7 @@ abstract class UnCurry extends InfoTransform
                 if (cases exists treeInfo.isDefaultCase) Literal(Constant(true))
                 else Match(substTree(selector.duplicate), (cases map transformCase) :+ defaultCase)
               )
+            // TODO: find a better way to keep this in synch with the code generard by patmatvirtualizer
             // TODO: check tgt.tpe.typeSymbol isNonBottomSubclass MatchingStrategyClass
             case Apply(Apply(TypeApply(Select(tgt, nme.runOrElse), targs), args_scrut), args_pm) if opt.virtPatmat =>
               object noOne extends Transformer {
@@ -317,7 +337,7 @@ abstract class UnCurry extends InfoTransform
               }
               substTree(Apply(Apply(TypeApply(Select(tgt.duplicate, tgt.tpe.member("isSuccess".toTermName)), targs map (_.duplicate)), args_scrut map (_.duplicate)), args_pm map (noOne.transform)))
             // for no-option version of virtpatmat
-            case Block(List(zero: ValDef, x: ValDef, matchRes: ValDef, keepGoing: ValDef, stats@_*), _) if opt.virtPatmat => import CODE._
+            case VirtPatmatOpt(zero, x, matchRes, keepGoing, stats, addOuter) if opt.virtPatmat => import CODE._
               object dropMatchResAssign extends Transformer {
                 // override val treeCopy = newStrictTreeCopier // will duplicate below
                 override def transform(tree: Tree): Tree = tree match {
@@ -329,14 +349,14 @@ abstract class UnCurry extends InfoTransform
                 }
               }
               val statsNoMatchRes: List[Tree] = stats map (dropMatchResAssign.transform) toList
-              val idaBlock = Block(
+              val idaBlock = addOuter(Block(
                 zero ::
                 x ::
                 /* drop matchRes def */
                 keepGoing ::
                 statsNoMatchRes,
                 NOT(REF(keepGoing.symbol)) // replace `if (keepGoing) throw new MatchError(...) else matchRes` by `!keepGoing`
-              )
+              ))
               substTree(idaBlock.duplicate) // duplicate on block as a whole to ensure valdefs are properly cloned and substed
           })
         }
diff --git a/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala b/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala
index 05a85e97fe..f563f8bca2 100644
--- a/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala
@@ -245,7 +245,7 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer =>
             // `one(x) : T` where x is the binder before this pattern, which will be replaced by the binder for the alternative by TreeMaker.singleBinder below
             // T is the widened type of the previous binder -- this ascription is necessary to infer a clean type for `or` -- the alternative combinator -- in the presence of existential types
             // see pos/virtpatmat_exist1.scala
-            combineExtractors(translatePattern(patBinder, alt), pmgen.one(CODE.REF(patBinder), patBinder.info.widen)) // only RHS of actual case should use caseResult, else the optimized codegen breaks
+            combineExtractors(propagateSubstitution(translatePattern(patBinder, alt)), pmgen.one(CODE.REF(patBinder), patBinder.info.widen)) // only RHS of actual case should use caseResult, else the optimized codegen breaks
           }
 
           noFurtherSubPats(AlternativesTreeMaker(patBinder, altTrees : _*))
@@ -664,51 +664,97 @@ defined class Foo */
 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 
   trait TreeMakers {
-    trait TreeMaker {
-      def substitution: Substitution ={
-        if (currSub eq null) currSub = initialSubstitution
-        currSub
-      }
+    abstract class TreeMaker {
+      def substitution: Substitution =
+        if (currSub eq null) localSubstitution
+        else currSub
 
-      protected def initialSubstitution: Substitution
+      protected def localSubstitution: Substitution
 
-      private[TreeMakers] def addOuterSubstitution(outerSubst: Substitution): TreeMaker = {
-        currSub = outerSubst >> substitution
+      private[TreeMakers] def incorporateOuterSubstitution(outerSubst: Substitution): TreeMaker = {
+        if (currSub ne null) {
+          println("BUG: incorporateOuterSubstitution called more than once for "+ (this, currSub, outerSubst))
+          Thread.dumpStack()
+        }
+        else currSub = outerSubst >> substitution
         this
       }
       private[this] var currSub: Substitution = null
 
       def chainBefore(next: Tree): Tree
+      def treesToHoist: List[Tree] = Nil
     }
 
-    case class SubstOnlyTreeMaker(initialSubstitution: Substitution) extends TreeMaker {
+    case class SubstOnlyTreeMaker(localSubstitution: Substitution) extends TreeMaker {
       def chainBefore(next: Tree): Tree = substitution(next)
     }
 
-    trait FunTreeMaker extends TreeMaker {
+    abstract class FunTreeMaker extends TreeMaker {
       val nextBinder: Symbol
       // wrap a Fun (with binder nextBinder) around the next tree (unless nextBinder == NoSymbol) and perform our substitution
-      protected def wrapFunSubst(next: Tree): Tree = pmgen.fun(nextBinder, substitution(next))
+      protected def wrapFunSubst(next: Tree): Tree
+        = pmgen.fun(nextBinder, substitution(next))
+
+      var reused: Boolean = false
+      def reusedBinders: List[Symbol] = Nil
+      override def treesToHoist: List[Tree] = { import CODE._
+        reusedBinders map { b => VAL(b) === pmgen.mkZero(b.info) }
+      }
     }
 
-    trait FreshFunTreeMaker extends FunTreeMaker {
+    abstract class FreshFunTreeMaker extends FunTreeMaker {
       val pos: Position
+      val prevBinder: Symbol
       val nextBinderTp: Type
       lazy val nextBinder = freshSym(pos, nextBinderTp)
+      lazy val localSubstitution = Substitution(List(prevBinder), List(CODE.REF(nextBinder)))
     }
 
-    trait SingleExtractorTreeMaker extends FunTreeMaker {
+    abstract class SingleExtractorTreeMaker extends FunTreeMaker {
       val extractor: Tree
       // build Tree that chains `next` after the current extractor
-      def chainBefore(next: Tree): Tree = pmgen.flatMap(extractor, wrapFunSubst(next)) setPos extractor.pos
+      def chainBefore(next: Tree): Tree =
+        pmgen.flatMap(extractor, wrapFunSubst(next)) setPos extractor.pos
+
     }
 
-    trait SingleBinderTreeMaker extends FunTreeMaker {
-      val prevBinder: Symbol
-      lazy val initialSubstitution = Substitution(List(prevBinder), List(CODE.REF(nextBinder)))
+    // TODO: in the process of shifting optimized code gen into the treemakers: complete and make it conditional in the same way as is happening in pmgen
+    abstract class CondTreeMaker extends FreshFunTreeMaker { import CODE._
+      val cond: Tree
+      val res: Tree
+
+      // must set reused before!
+      override lazy val reusedBinders = if(reused) List(freshSym(pos, BooleanClass.tpe, "rc") setFlag MUTABLE, nextBinder setFlag MUTABLE) else Nil
+      def storedCond         = reusedBinders(0)
+      def storedRes          = reusedBinders(1)
+
+      def chainBefore(next: Tree): Tree =
+        if (!reused)
+          atPos(pos)(pmgen.flatMapCond(cond, res, nextBinder, nextBinderTp, substitution(next)))
+        else {
+          IF (cond) THEN BLOCK(
+            storedCond === TRUE,
+            storedRes  === res,
+            substitution(next).duplicate // TODO: finer-grained dup'ing
+          ) ELSE pmgen.zero
+        }
     }
 
-    abstract class SimpleTreeMaker extends SingleExtractorTreeMaker with SingleBinderTreeMaker with FreshFunTreeMaker
+    case class ReusingCondTreeMaker(dropped_priors: List[(TreeMaker, Option[TreeMaker])]) extends TreeMaker { import CODE._
+      lazy val localSubstitution = {
+        val (from, to) = dropped_priors.collect {case (dropped: CondTreeMaker, Some(prior: CondTreeMaker)) => (dropped.nextBinder, REF(prior.storedRes))}.unzip
+        val oldSubs = dropped_priors.collect {case (dropped: TreeMaker, _) => dropped.substitution}
+        oldSubs.foldLeft(Substitution(from, to))(_ >> _)
+      }
+
+      def chainBefore(next: Tree): Tree = {
+        val cond = REF(dropped_priors.reverse.collectFirst{case (_, Some(ctm: CondTreeMaker)) => 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 pmgen.zero
+      }
+    }
 
     /**
      * Make a TreeMaker that will result in an extractor call specified by `extractor`
@@ -717,9 +763,12 @@ defined class Foo */
      * the function's body is determined by the next TreeMaker
      * 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, nextBinder: Symbol, initialSubstitution: Substitution) extends SingleExtractorTreeMaker
+    case class ExtractorTreeMaker(extractor: Tree, nextBinder: Symbol, localSubstitution: Substitution) extends SingleExtractorTreeMaker {
+      override def toString = "X"+(extractor, nextBinder)
+    }
 
-    case class ProductExtractorTreeMaker(prevBinder: Symbol, extraCond: Option[Tree], initialSubstitution: Substitution) extends TreeMaker { import CODE._
+    // TODO: allow user-defined unapplyProduct
+    case class ProductExtractorTreeMaker(prevBinder: Symbol, extraCond: Option[Tree], localSubstitution: Substitution) extends TreeMaker { import CODE._
       def chainBefore(next: Tree): Tree = {
         val nullCheck = REF(prevBinder) OBJ_NE NULL
         val cond = extraCond match {
@@ -728,34 +777,44 @@ defined class Foo */
         }
         pmgen.condOptimized(cond, substitution(next))
       }
+
+      override def toString = "P"+(prevBinder,  extraCond getOrElse "", localSubstitution)
     }
 
-    case class FilteredExtractorTreeMaker(extractor: Tree, guard: Tree, nextBinder: Symbol, initialSubstitution: Substitution) extends FunTreeMaker {
+    case class FilteredExtractorTreeMaker(extractor: Tree, guard: Tree, nextBinder: Symbol, localSubstitution: Substitution) extends FunTreeMaker {
       def chainBefore(next: Tree): Tree =
         pmgen.flatMap(extractor, wrapFunSubst(pmgen.condOptimized(guard, next))) setPos extractor.pos
+      override def toString = "FX"+(extractor, guard, nextBinder)
     }
 
     // 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 SimpleTreeMaker {
-      val extractor = pmgen.condCast(typeTest(prevBinder, nextBinderTp), prevBinder, nextBinderTp)
+    case class TypeTestTreeMaker(prevBinder: Symbol, nextBinderTp: Type, pos: Position) extends CondTreeMaker {
+      val cond = typeTest(prevBinder, nextBinderTp)
+      val res  = pmgen._asInstanceOf(prevBinder, nextBinderTp)
+      override def toString = "TT"+(prevBinder, nextBinderTp)
     }
 
     // implements the run-time aspects of (§8.2) (typedPattern has already done the necessary type transformations)
-    case class TypeAndEqualityTestTreeMaker(prevBinder: Symbol, patBinder: Symbol, pt: Type, pos: Position) extends SimpleTreeMaker {
+    case class TypeAndEqualityTestTreeMaker(prevBinder: Symbol, patBinder: Symbol, pt: Type, pos: Position) extends CondTreeMaker {
       val nextBinderTp = glb(List(patBinder.info.widen, pt))
-      val extractor = pmgen.condCast(typeAndEqualityTest(patBinder, pt), patBinder, nextBinderTp)
+
+      val cond = typeAndEqualityTest(patBinder, pt)
+      val res  = pmgen._asInstanceOf(patBinder, nextBinderTp)
+      override def toString = "TET"+(patBinder, pt)
     }
 
     // need to substitute to deal with existential types -- TODO: deal with existentials better, don't substitute (see RichClass during quick.comp)
-    case class EqualityTestTreeMaker(prevBinder: Symbol, patTree: Tree, pos: Position) extends SimpleTreeMaker {
-      val nextBinderTp: Type = prevBinder.info.widen
+    case class EqualityTestTreeMaker(prevBinder: Symbol, patTree: Tree, pos: Position) extends CondTreeMaker {
+      val nextBinderTp = prevBinder.info.widen
 
       // NOTE: generate `patTree == patBinder`, since the extractor must be in control of the equals method (also, patBinder may be null)
       // equals need not be well-behaved, so don't intersect with pattern's (stabilized) type (unlike MaybeBoundTyped's accumType, where it's required)
-      val extractor = atPos(pos)(pmgen.cond(pmgen._equals(patTree, prevBinder), CODE.REF(prevBinder), nextBinderTp))
+      val cond = pmgen._equals(patTree, prevBinder)
+      val res  = CODE.REF(prevBinder)
+      override def toString = "ET"+(prevBinder, patTree)
     }
 
-    case class AlternativesTreeMaker(prevBinder: Symbol, alts: Tree*) extends SingleBinderTreeMaker with FreshFunTreeMaker {
+    case class AlternativesTreeMaker(prevBinder: Symbol, alts: Tree*) extends FreshFunTreeMaker {
       val nextBinderTp: Type = prevBinder.info.widen
       val pos = alts.head.pos
       def chainBefore(next: Tree): Tree =
@@ -763,67 +822,296 @@ defined class Foo */
     }
 
     case class GuardTreeMaker(guardTree: Tree) extends /*SingleExtractor*/TreeMaker {
-      val initialSubstitution: Substitution = EmptySubstitution
+      val localSubstitution: Substitution = EmptySubstitution
       // val nextBinder = freshSym(guardTree.pos, UnitClass.tpe)
       // val extractor = pmgen.guard(guardTree)
       def chainBefore(next: Tree): Tree = { import CODE._
         IF (guardTree) THEN next ELSE pmgen.zero
       }
-
       override def toString = "G("+ guardTree +")"
     }
 
-    // combineExtractors changes the current substitution's of the tree makers in `treeMakers`
-    def combineExtractors(treeMakers: List[TreeMaker], body: Tree): Tree = {
-      // a foldLeft to accumulate the initialSubstitution left-to-right, but written using a map and a var for clarity
-      def propagateSubstitution(treeMakers: List[TreeMaker]): List[TreeMaker] = {
-        var accumSubst: Substitution = EmptySubstitution
-        treeMakers foreach { maker =>
-          // could mutate maker instead, but it doesn't seem to shave much time off of quick.comp
-          maker addOuterSubstitution accumSubst
-          accumSubst = maker.substitution
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+// decisions, decisions
+///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+    object Test {
+      var currId = 0
+    }
+    case class Test(cond: Cond, treeMaker: TreeMaker) {
+      // def <:<(other: Test) = cond <:< other.cond
+      // def andThen_: (prev: List[Test]): List[Test] =
+      //   prev.filterNot(this <:< _) :+ this
+
+      private val reusedBy = new collection.mutable.HashSet[Test]
+      var reuses: Option[Test] = None
+      def registerReuseBy(later: Test): Unit = {
+        assert(later.reuses.isEmpty)
+        reusedBy += later
+        later.reuses = Some(this)
+      }
+
+      val id = { Test.currId += 1; Test.currId}
+      override def toString =
+        if (cond eq Top) "T"
+        else if(cond eq Havoc) "!?"
+        else "T"+ id + (if(reusedBy nonEmpty) "!["+ treeMaker +"]" else (if(reuses.isEmpty) "["+ treeMaker +"]" else  " cf. T"+reuses.get.id))
+    }
+
+    object Cond {
+      // def refines(self: Cond, other: Cond): Boolean = (self, other) match {
+      //   case (Bottom, _)       => true
+      //   case (Havoc , _)       => true
+      //   case (_         , Top) => true
+      //   case (_         , _)   => false
+      // }
+      var currId = 0
+    }
+
+    abstract class Cond {
+      // def testedPath: Tree
+      // def <:<(other: Cond) = Cond.refines(this, other)
+
+      val id = { Cond.currId += 1; Cond.currId}
+    }
+
+    // does not contribute any knowledge
+    case object Top extends Cond
+
+    // takes away knowledge. e.g., a user-defined guard
+    case object Havoc extends Cond
+
+    // we know everything! everything!
+    // this either means the case is unreachable,
+    // or that it is statically known to be picked -- at this point in the decision tree --> no point in emitting further alternatives
+    // case object Bottom extends Cond
+
+
+    object EqualityCond {
+      private val uniques = new collection.mutable.HashMap[(Tree, Tree), EqualityCond]
+      def apply(testedPath: Tree, rhs: Tree): EqualityCond = uniques getOrElseUpdate((testedPath, rhs), new EqualityCond(testedPath, rhs))
+    }
+    class EqualityCond(testedPath: Tree, rhs: Tree) extends Cond {
+      // def negation         = TopCond // inequality doesn't teach us anything
+      // do simplification when we know enough about the tree statically:
+      //  - collapse equal trees
+      //  - accumulate tests when (in)equality not known statically
+      //  - become bottom when we statically know this can never match
+
+      override def toString = testedPath +" == "+ rhs +"#"+ id
+    }
+
+    object TypeCond {
+      private val uniques = new collection.mutable.HashMap[(Tree, Type), TypeCond]
+      def apply(testedPath: Tree, pt: Type): TypeCond = uniques getOrElseUpdate((testedPath, pt), new TypeCond(testedPath, pt))
+    }
+    class TypeCond(testedPath: Tree, pt: Type) extends Cond {
+      // def negation         = TopCond // inequality doesn't teach us anything
+      // do simplification when we know enough about the tree statically:
+      //  - collapse equal trees
+      //  - accumulate tests when (in)equality not known statically
+      //  - become bottom when we statically know this can never match
+      override def toString = testedPath +" <: "+ pt +"#"+ id
+    }
+
+    object TypeAndEqualityCond {
+      private val uniques = new collection.mutable.HashMap[(Tree, Type), TypeAndEqualityCond]
+      def apply(testedPath: Tree, pt: Type): TypeAndEqualityCond = uniques getOrElseUpdate((testedPath, pt), new TypeAndEqualityCond(testedPath, pt))
+    }
+    class TypeAndEqualityCond(testedPath: Tree, pt: Type) extends Cond {
+      // def negation         = TopCond // inequality doesn't teach us anything
+      // do simplification when we know enough about the tree statically:
+      //  - collapse equal trees
+      //  - accumulate tests when (in)equality not known statically
+      //  - become bottom when we statically know this can never match
+      override def toString = testedPath +" (<: && ==) "+ pt +"#"+ id
+    }
+
+    /** 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], Tree)], pt: Type): List[(List[TreeMaker], Tree)] = {
+      // 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)
+
+      // 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
+      var accumSubst: Substitution = EmptySubstitution
+
+      val trees = new collection.mutable.HashSet[Tree]
+
+      def approximateTreeMaker(tm: TreeMaker): Test = {
+        val subst = tm.substitution
+
+        // find part of substitution that replaces bound symbols by new symbols, and reverse that part
+        // so that we don't introduce new aliases for existing symbols, thus keeping the set of bound symbols minimal
+        val (boundSubst, unboundSubst) = (subst.from zip subst.to) partition {case (f, t) =>
+            t.isInstanceOf[Ident] && (t.symbol ne NoSymbol) && pointsToBound(f)
+          }
+        val (boundFrom, boundTo) = boundSubst.unzip
+        normalize >>= Substitution(boundTo map (_.symbol), boundFrom map (CODE.REF(_)))
+        // println("normalize: "+ normalize)
+
+        val (unboundFrom, unboundTo) = unboundSubst unzip
+        val okSubst = Substitution(unboundFrom, unboundTo map (normalize(_))) // it's important substitution does not duplicate trees here -- it helps to keep hash consing simple, anyway
+        pointsToBound ++= ((okSubst.from, okSubst.to).zipped filter { (f, t) => pointsToBound exists (sym => t.exists(_.symbol == sym)) })._1
+        // println("pointsToBound: "+ pointsToBound)
+
+        accumSubst >>= okSubst
+        // println("accumSubst: "+ accumSubst)
+
+        // TODO: improve, e.g., for constants
+        def sameValue(a: Tree, b: Tree): Boolean = (a eq b) || ((a, b) match {
+          case (_ : Ident, _ : Ident) => a.symbol eq b.symbol
+          case _                      => false
+        })
+
+        // hashconsing trees (modulo value-equality)
+        def unique(t: Tree): Tree =
+          trees find (a => a.equalsStructure0(t)(sameValue)) match {
+            case Some(orig) => orig // println("unique: "+ (t eq orig, orig));
+            case _ => trees += t; t
+          }
+
+        def uniqueTp(tp: Type): Type = tp match {
+          // typerefs etc are already hashconsed
+          case _ : UniqueType                      => tp
+          case tp@RefinedType(parents, EmptyScope) => tp.memo(tp: Type)(identity) // TODO: does this help?
+          case _                                   => tp
         }
-        treeMakers
+
+        def binderToUniqueTree(b: Symbol) = unique(accumSubst(normalize(CODE.REF(b))))
+
+        Test(tm match {
+          case ProductExtractorTreeMaker(pb, None, subst)           => Top // TODO: NotNullTest(prevBinder)
+          case tm@TypeTestTreeMaker(prevBinder, nextBinderTp, _)    => TypeCond(binderToUniqueTree(prevBinder), uniqueTp(nextBinderTp))
+          case tm@TypeAndEqualityTestTreeMaker(_, patBinder, pt, _) => TypeAndEqualityCond(binderToUniqueTree(patBinder), uniqueTp(pt))
+          case tm@EqualityTestTreeMaker(prevBinder, patTree, _)     => EqualityCond(binderToUniqueTree(prevBinder), unique(patTree))
+          case ExtractorTreeMaker(_, _, _)
+             | GuardTreeMaker(_)
+             | ProductExtractorTreeMaker(_, Some(_), _)             => Havoc
+          case FilteredExtractorTreeMaker(x, g, nb, subst)          => Havoc
+          case AlternativesTreeMaker(_, _*)                         => Havoc // TODO: can do better here
+          case SubstOnlyTreeMaker(_)                                => Top
+        }, tm)
       }
 
-      propagateSubstitution(treeMakers).foldRight (body) (_ chainBefore _)
-    //   this optimization doesn't give us much
-    //   var accumSubst: Substitution = EmptySubstitution
-    //   var revMakers: List[TreeMaker] = Nil
-    //   treeMakers foreach { maker =>
-    //     accumSubst = accumSubst >> maker.substitution
-    //     maker.substitution = accumSubst
-    //     revMakers ::= maker
-    //   }
-    //
-    //   var accumTree = body
-    //   revMakers foreach { maker =>
-    //     accumTree = maker chainBefore accumTree
-    //   }
-    //
-    //   atPos(pos)(accumTree)
+      val testss = cases.map {case (treeMakers, _) => treeMakers map approximateTreeMaker }
+
+      // interpret:
+      val dependencies = new collection.mutable.LinkedHashMap[Test, Set[Cond]]
+      val tested = new collection.mutable.HashSet[Cond]
+      testss foreach { tests =>
+        tested.clear()
+        tests dropWhile { test =>
+          val cond = test.cond
+          if ((cond eq Havoc) || (cond eq Top)) (cond eq Top) // stop when we encounter a havoc, skip top
+          else {
+            tested += cond
+
+            // is there an earlier test that checks our condition and whose dependencies are implied by ours?
+            dependencies find { case (priorTest, deps) =>
+              ((priorTest.cond eq cond) || (deps contains cond)) && (deps subsetOf tested)
+            } foreach { case (priorTest, deps) =>
+              // if so, note the dependency in both tests
+              priorTest registerReuseBy test
+            }
+
+            dependencies(test) = tested.toSet // copies
+            true
+          }
+        }
+      }
+
+      // find longest prefix of tests that reuse a prior test, and whose dependent conditions monotonically increase
+      // then, collapse these contiguous sequences of reusing tests
+      // store the result of the final test and the intermediate results in hoisted mutable variables (TODO: optimize: don't store intermediate results that aren't used)
+      // replace each reference to a variable originally bound by a collapsed test by a reference to the hoisted variable
+      (testss, cases).zipped map { case (tests, (_, caseBody)) =>
+        var currDeps = Set[Cond]()
+        val (sharedPrefix, suffix) = tests span { test =>
+          (test.cond eq Top) || (for(
+              reusedTest <- test.reuses;
+              nextDeps <- dependencies.get(reusedTest);
+              diff <- (nextDeps -- currDeps).headOption;
+              _ <- Some(currDeps = nextDeps))
+                yield diff).nonEmpty
+        }
+
+        val collapsedTreeMakers = if (sharedPrefix.lengthCompare(1) > 0) { // prefix must be longer than one for the optimization to pay off
+          for (test <- sharedPrefix; reusedTest <- test.reuses; if reusedTest.treeMaker.isInstanceOf[FunTreeMaker])
+            reusedTest.treeMaker.asInstanceOf[FunTreeMaker].reused = true
+          // println("sharedPrefix: "+ sharedPrefix)
+          for (lastShared <- sharedPrefix.reverse.dropWhile(_.cond eq Top).headOption;
+               lastReused <- lastShared.reuses)
+            yield ReusingCondTreeMaker(sharedPrefix map (t => (t.treeMaker, t.reuses map (_.treeMaker)))) :: suffix.map(_.treeMaker)
+        } else None
+
+        (collapsedTreeMakers getOrElse tests.map(_.treeMaker), // sharedPrefix need not be empty (but it only contains Top-tests, which are dropped above)
+         caseBody)
+      }
     }
 
-    def combineCases(scrut: Tree, scrutSym: Symbol, cases: List[(List[TreeMaker], Tree)], pt: Type): Tree = {
+
+    // a foldLeft to accumulate the localSubstitution left-to-right, mutating the treemakers in-place for performance
+    def propagateSubstitution(treeMakers: List[TreeMaker]): List[TreeMaker] = {
+      var accumSubst: Substitution = EmptySubstitution
+      treeMakers foreach { maker =>
+        maker incorporateOuterSubstitution accumSubst
+        accumSubst = maker.substitution
+      }
+      treeMakers
+    }
+
+    // calls propagateSubstitution on the treemakers
+    def analyzeCases(prevBinder: Symbol, cases: List[(List[TreeMaker], Tree)], pt: Type): List[(List[TreeMaker], Tree)] = {
+      cases foreach { case (pats, _) => propagateSubstitution(pats) }
+      doCSE(prevBinder, cases, pt)
+    }
+
+    def combineCases(scrut: Tree, scrutSym: Symbol, cases0: List[(List[TreeMaker], Tree)], pt: Type): Tree = {
+      var toHoist = List[Tree]()
       val matcher =
-        if (cases nonEmpty) {
+        if (cases0 nonEmpty) {
           // when specified, need to propagate pt explicitly (type inferencer can't handle it)
           val optPt =
             if (isFullyDefined(pt)) appliedType(matchingMonadType, List(pt))
             else NoType
 
+          val cases = analyzeCases(scrutSym, cases0, pt)
+
           // map + foldLeft
           var combinedCases = combineExtractors(cases.head._1, cases.head._2)
           cases.tail foreach { case (pats, body) =>
             combinedCases = pmgen.typedOrElse(optPt)(combinedCases, combineExtractors(pats, body))
           }
 
+          toHoist   = (for ((treeMakers, _) <- cases; tm <- treeMakers; hoisted <- tm.treesToHoist) yield hoisted).toList
+
           pmgen.fun(scrutSym, combinedCases)
         } else pmgen.zero
 
-      pmgen.runOrElse(scrut, matcher, scrutSym.info, if (isFullyDefined(pt)) pt else NoType)
+
+      val expr = pmgen.runOrElse(scrut, matcher, scrutSym.info, if (isFullyDefined(pt)) pt else NoType)
+      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], body: Tree): Tree =
+      treeMakers.foldRight (body) (_ chainBefore _)
+
+
     object Substitution {
       def apply(from: Symbol, to: Tree) = new Substitution(List(from), List(to))
       // requires sameLength(from, to)
@@ -833,11 +1121,14 @@ defined class Foo */
 
     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) {
@@ -845,6 +1136,8 @@ defined class Foo */
       override def >>(other: Substitution): Substitution = other
     }
 
+
+
     def matchingMonadType: Type
     def typedSubst(tree: Tree, from: List[Symbol], to: List[Tree]): Tree
     def freshSym(pos: Position, tp: Type = NoType, prefix: String = "x"): Symbol
@@ -855,6 +1148,7 @@ defined class Foo */
     trait AbsCodeGen { import CODE.UNIT
       def runOrElse(scrut: Tree, matcher: Tree, scrutTp: Type, resTp: Type): Tree
       def flatMap(a: Tree, b: Tree): Tree
+      def flatMapCond(cond: Tree, res: Tree, nextBinder: Symbol, nextBinderTp: Type, next: Tree): Tree
       def fun(arg: Symbol, body: Tree): Tree
       def or(f: Tree, as: List[Tree]): Tree
       def typedOrElse(pt: Type)(thisCase: Tree, elseCase: Tree): Tree
@@ -868,6 +1162,8 @@ defined class Foo */
       def condOptimized(c: Tree, then: Tree): Tree
       def condCast(c: Tree, binder: Symbol, expectedTp: Type): Tree
       def _equals(checker: Tree, binder: Symbol): Tree
+      def _asInstanceOf(b: Symbol, tp: Type): Tree
+      def mkZero(tp: Type): Tree
     }
 
     def pmgen: AbsCodeGen
@@ -967,6 +1263,22 @@ defined class Foo */
         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 MatchingStrategyGen { self: CommonCodeGen with MatchingStrategyGen with MonadInstGen =>
@@ -989,6 +1301,8 @@ defined class Foo */
     trait MonadInstGen { self: CommonCodeGen with MatchingStrategyGen with MonadInstGen =>
       // methods in the monad instance -- used directly in translation
       def flatMap(a: Tree, b: Tree): Tree                                = (a DOT vpmName.flatMap)(b)
+      def flatMapCond(condi: Tree, res: Tree, nextBinder: Symbol, nextBinderTp: Type, next: Tree): Tree =
+        flatMap(cond(condi, res, nextBinderTp), fun(nextBinder, next))
       def typedOrElse(pt: Type)(thisCase: Tree, elseCase: Tree): Tree    = (genTypeApply(thisCase DOT vpmName.orElse, pt)) APPLY (elseCase)
     }
 
@@ -1004,22 +1318,6 @@ defined class Foo */
       override def zero: Tree = REF(zeroSym)
       override def one(res: Tree, tp: Type = NoType, oneName: Name = vpmName.one): Tree = Apply(genTypeApply(REF(SomeModule), tp), List(res))
 
-      // duplicated out of frustration with cast generation
-      private 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
-        }
-      }
-
 
       /** Inline runOrElse and get rid of Option allocations
        *
@@ -1103,6 +1401,12 @@ defined class Foo */
         case _ => println("huh?")
           (opt DOT vpmName.flatMap)(fun)
       }
+
+      override def flatMapCond(cond: Tree, res: Tree, nextBinder: Symbol, nextBinderTp: Type, next: Tree): Tree =
+        IF (cond) THEN BLOCK(
+          VAL(nextBinder) === res,
+          next
+        ) ELSE zero
     }
 
     def genTypeApply(tfun: Tree, args: Type*): Tree                       = if(args contains NoType) tfun else TypeApply(tfun, args.toList map TypeTree)
@@ -1161,3 +1465,42 @@ defined class Foo */
 //   var okTree: Tree = null
 // }
 // private def c(t: Tree): Tree = noShadowedUntyped(t)
+
+    //   def approximateTreeMaker(tm: TreeMaker): List[Test] = tm match {
+    //     case ExtractorTreeMaker(extractor, _, _) => HavocTest
+    //     case FilteredExtractorTreeMaker(extractor, lenGuard, _, _) => HavocTest
+    //     case ProductExtractorTreeMaker(testedBinder, lenGuard, _) => TopTest // TODO: (testedBinder ne null) and lenGuard
+    //
+    //     // cond = typeTest(prevBinder, nextBinderTp)
+    //     // res  = pmgen._asInstanceOf(prevBinder, nextBinderTp)
+    //     case TypeTestTreeMaker(testedBinder, pt, _) =>
+    //
+    //     // cond = typeAndEqualityTest(patBinder, pt)
+    //     // res  = pmgen._asInstanceOf(patBinder, nextBinderTp)
+    //     case TypeAndEqualityTestTreeMaker(_, testedBinder, pt, _) =>
+    //
+    //     // cond = pmgen._equals(patTree, prevBinder)
+    //     // res  = CODE.REF(prevBinder)
+    //     case EqualityTestTreeMaker(testedBinder, rhs, _) =>
+    //
+    //     case AlternativesTreeMaker(_, alts: *) =>
+    //
+    //     case GuardTreeMaker(guardTree) =>
+    //   }
+
+    // // TODO: it's not exactly sound to represent an unapply-call by its symbol... also need to consider the prefix, like the outer-test (can this be captured as the path to this test?)
+    // type ExtractorRepr = Symbol
+    //
+    // // TODO: we're undoing tree-construction that we ourselves performed earlier -- how about not-doing so we don't have to undo?
+    // private def findBinderArgOfApply(extractor: Tree, unappSym: Symbol): Symbol = {
+    //   class CollectTreeTraverser[T](pf: PartialFunction[Tree => T]) extends Traverser {
+    //     val hits = new ListBuffer[T]
+    //     override def traverse(t: Tree) {
+    //       if (pf.isDefinedAt(t)) hits += pf(t)
+    //       super.traverse(t)
+    //     }
+    //   }
+    //   val trav = new CollectTreeTraverser{ case Apply(unapp, List(arg)) if unapp.symbol eq unappSym => arg.symbol}
+    //   trav.traverse(extractor)
+    //   trav.hits.headOption getOrElse NoSymbol
+    // }
diff --git a/test/files/run/virtpatmat_opt_sharing.check b/test/files/run/virtpatmat_opt_sharing.check
new file mode 100644
index 0000000000..d00491fd7e
--- /dev/null
+++ b/test/files/run/virtpatmat_opt_sharing.check
@@ -0,0 +1 @@
+1
diff --git a/test/files/run/virtpatmat_opt_sharing.flags b/test/files/run/virtpatmat_opt_sharing.flags
new file mode 100644
index 0000000000..9769db9257
--- /dev/null
+++ b/test/files/run/virtpatmat_opt_sharing.flags
@@ -0,0 +1 @@
+ -Yvirtpatmat -Xexperimental
diff --git a/test/files/run/virtpatmat_opt_sharing.scala b/test/files/run/virtpatmat_opt_sharing.scala
new file mode 100644
index 0000000000..119e3050ea
--- /dev/null
+++ b/test/files/run/virtpatmat_opt_sharing.scala
@@ -0,0 +1,10 @@
+object Test extends App {
+  virtMatch()
+  def virtMatch() = {
+    List(1, 3, 4, 7) match {
+      case 1 :: 3 :: 4 :: 5 :: x => println("nope")
+      case 1 :: 3 :: 4 :: 6 :: x => println("nope")
+      case 1 :: 3 :: 4 :: 7 :: x => println(1)
+    }
+  }
+}
\ No newline at end of file