[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

1 files changed, 10 insertions, 0 deletions

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