Fixed looping data flow analyzer (due to asymme...

Fixed looping data flow analyzer (due to asymmetric equals method in
lattices) (ticket #30).

6 files changed, 63 insertions, 47 deletions

diff --git a/src/compiler/scala/tools/nsc/backend/icode/analysis/CompleteLattice.scala b/src/compiler/scala/tools/nsc/backend/icode/analysis/CompleteLattice.scala
index f124ea777f..16c53c4668 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/analysis/CompleteLattice.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/CompleteLattice.scala
@@ -10,7 +10,21 @@ package scala.tools.nsc.backend.icode.analysis
 /** A complete lattice.
  */
 trait CompleteLattice {
-  type Elem
+  type Elem <: AnyRef
+
+  /** Hold together local variable and stack state. The
+   *  equals method uses reference equality for top and bottom,
+   *  and structural equality for other values.
+   */
+  case class IState[V, S](val vars: V, val stack: S) {
+    override def equals(other: Any): Boolean = other match {
+      case that: IState[_, _] =>
+        if ((this eq bottom) || (that eq bottom)) this eq that
+        else if ((this eq top) || (that eq top)) this eq that
+        else (stack == that.stack && vars == that.vars)
+      case _ => false
+    }
+  }
 
   /** Return the least upper bound of <code>a</code> and <code>b</code> */
   def lub2(a: Elem, b: Elem): Elem
diff --git a/src/compiler/scala/tools/nsc/backend/icode/analysis/CopyPropagation.scala b/src/compiler/scala/tools/nsc/backend/icode/analysis/CopyPropagation.scala
index aca103aecf..ec2e8e1c93 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/analysis/CopyPropagation.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/CopyPropagation.scala
@@ -481,6 +481,7 @@ abstract class CopyPropagation {
       var values = in.stack.take(1 + ctor.info.paramTypes.length).reverse.drop(1);
       val bindings = new HashMap[Symbol, Value];
 
+      if (settings.debug.value) log("getBindings for: " + ctor)
       // this relies on having the same order in paramAccessors and
       // the arguments on the stack. It should be the same!
       for ((p, i) <- paramAccessors.zipWithIndex) {
@@ -490,6 +491,7 @@ abstract class CopyPropagation {
         values = values.tail;
       }
 
+      if (settings.debug.value) log("\t" + bindings)
       bindings
     }
 
diff --git a/src/compiler/scala/tools/nsc/backend/icode/analysis/ReachingDefinitions.scala b/src/compiler/scala/tools/nsc/backend/icode/analysis/ReachingDefinitions.scala
index 3b610e11bc..27342deb85 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/analysis/ReachingDefinitions.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/ReachingDefinitions.scala
@@ -8,7 +8,7 @@
 package scala.tools.nsc.backend.icode.analysis
 
 import compat.StringBuilder
-import scala.collection.mutable.{HashMap, Map}
+import scala.collection.jcl.{HashMap, Map}
 import scala.collection.immutable.{Set, ListSet, HashSet}
 
 /** Compute reaching definitions. We are only interested in reaching
@@ -26,15 +26,13 @@ abstract class ReachingDefinitions {
    */
   object rdefLattice extends CompleteLattice {
     type Definition = (Local, BasicBlock, Int)
-    type Elem = (Set[Definition], Stack)
+    type Elem = IState[Set[Definition], Stack]
     type StackPos = Set[(BasicBlock, Int)]
     type Stack = List[StackPos]
 
-    val top: Elem = (new ListSet[Definition]() {
-      override def equals(that: Any): Boolean = this eq that.asInstanceOf[AnyRef]
-    }, Nil)
+    val top: Elem = IState(new ListSet[Definition](), Nil)
 
-    val bottom: Elem = (new ListSet[Definition]() {
+    val bottom: Elem = IState(new ListSet[Definition]() {
       override def equals(that: Any): Boolean = this eq that.asInstanceOf[AnyRef]
       override def toString = "<bottom>"
     }, Nil)
@@ -44,13 +42,13 @@ abstract class ReachingDefinitions {
       if (bottom == a) b
       else if (bottom == b) a
       else {
-        val locals = a._1 incl b._1
-        val stack = if (a._2 == Nil)
-          b._2
-        else if (b._2 == Nil) a._2
-        else List.map2(a._2, b._2) (_ incl _)
+        val locals = a.vars incl b.vars
+        val stack = if (a.stack == Nil)
+          b.stack
+        else if (b.stack == Nil) a.stack
+        else List.map2(a.stack, b.stack) (_ incl _)
 
-        val res = (locals, stack)
+        val res = IState(locals, stack)
 
 //        Console.println("\tlub2: " + a + ", " + b)
 //        Console.println("\tis: " + res)
@@ -96,7 +94,7 @@ abstract class ReachingDefinitions {
           out(b) = lattice.bottom
         }
         m.exh foreach { e =>
-          in(e.startBlock) = (new ListSet[Definition], List(new ListSet[(BasicBlock, Int)]))
+          in(e.startBlock) = lattice.IState(new ListSet[Definition], List(new ListSet[(BasicBlock, Int)]))
         }
 
       }
@@ -149,11 +147,15 @@ abstract class ReachingDefinitions {
       if (settings.debug.value) {
         linearizer.linearize(method).foreach(b => if (b != method.code.startBlock)
           assert(lattice.bottom != in(b),
-            "Block " + b + " in " + this.method + " has input equal to bottom -- not visited?"));
+            "Block " + b + " in " + this.method + " has input equal to bottom -- not visited? " + in(b)
+                 + ": bot: " + lattice.bottom
+                 + "\nin(b) == bottom: " + (in(b) == lattice.bottom)
+                 + "\nbottom == in(b): " + (lattice.bottom == in(b))));
       }
     }
 
     import opcodes._
+    import lattice.IState
     def updateReachingDefinition(b: BasicBlock, idx: Int, rd: Set[Definition]): Set[Definition] = {
       val STORE_LOCAL(local) = b(idx)
       var tmp = local
@@ -161,15 +163,15 @@ abstract class ReachingDefinitions {
     }
 
     private def blockTransfer(b: BasicBlock, in: lattice.Elem): lattice.Elem = {
-      var locals: Set[Definition] = (in._1 filter { case (l, _, _) => !kill(b)(l) }) incl gen(b)
-      if (locals eq lattice.bottom._1) locals = new ListSet[Definition]
-      (locals, outStack(b) ::: in._2.drop(drops(b)))
+      var locals: Set[Definition] = (in.vars filter { case (l, _, _) => !kill(b)(l) }) incl gen(b)
+      if (locals eq lattice.bottom.vars) locals = new ListSet[Definition]
+      IState(locals, outStack(b) ::: in.stack.drop(drops(b)))
     }
 
     /** Return the reaching definitions corresponding to the point after idx. */
     def interpret(b: BasicBlock, idx: Int, in: lattice.Elem): Elem = {
-      var locals = in._1
-      var stack  = in._2
+      var locals = in.vars
+      var stack  = in.stack
       val instr = b(idx)
       instr match {
         case STORE_LOCAL(l1) =>
@@ -187,7 +189,7 @@ abstract class ReachingDefinitions {
         prod = prod - 1
       }
 
-      (locals, stack)
+      IState(locals, stack)
     }
 
     override def toString: String = {
diff --git a/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala b/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala
index eacd40d42a..79c3bf341b 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala
@@ -76,18 +76,14 @@ abstract class TypeFlowAnalysis {
    */
   object typeFlowLattice extends CompleteLattice {
     import icodes._
-    type Elem = (VarBinding, icodes.TypeStack)
+    type Elem = IState[VarBinding, icodes.TypeStack]
 
-    override val top    = new Pair(new VarBinding, typeStackLattice.top) {
-      override def equals(that: Any) = (this eq that.asInstanceOf[AnyRef])
-    }
-    override val bottom = new Pair(new VarBinding, typeStackLattice.bottom) {
-      override def equals(that: Any) = (this eq that.asInstanceOf[AnyRef])
-    }
+    override val top    = new Elem(new VarBinding, typeStackLattice.top)
+    override val bottom = new Elem(new VarBinding, typeStackLattice.bottom)
 
     def lub2(a: Elem, b: Elem) = {
-      val (env1, s1) = a
-      val (env2, s2) = b
+      val IState(env1, s1) = a
+      val IState(env2, s2) = b
 
       val resultingLocals = new VarBinding
 
@@ -101,7 +97,7 @@ abstract class TypeFlowAnalysis {
         resultingLocals += binding2._1 -> typeLattice.lub2(binding2._2, tp1)
       }
 
-      (resultingLocals, typeStackLattice.lub2(a._2, b._2))
+      IState(resultingLocals, typeStackLattice.lub2(a.stack, b.stack))
     }
   }
 
@@ -127,7 +123,7 @@ abstract class TypeFlowAnalysis {
           out(b) = typeFlowLattice.bottom
         }
         m.exh foreach { e =>
-          in(e.startBlock) = Pair(in(e.startBlock)._1, typeStackLattice.exceptionHandlerStack)
+          in(e.startBlock) = lattice.IState(in(e.startBlock).vars, typeStackLattice.exceptionHandlerStack)
         }
       }
     }
@@ -152,9 +148,9 @@ abstract class TypeFlowAnalysis {
 
     /** Abstract interpretation for one instruction. */
     def interpret(in: typeFlowLattice.Elem, i: Instruction): typeFlowLattice.Elem = {
-      val out = Pair(new VarBinding(in._1), new TypeStack(in._2))
-      val bindings = out._1
-      val stack = out._2
+      val out = lattice.IState(new VarBinding(in.vars), new TypeStack(in.stack))
+      val bindings = out.vars
+      val stack = out.stack
 
 //      if (settings.debug.value) {
 //        Console.println("Stack: " + stack);
diff --git a/src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala b/src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala
index 496051ea99..d8a25f2bbb 100644
--- a/src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala
+++ b/src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala
@@ -96,7 +96,7 @@ abstract class DeadCodeElimination extends SubComponent {
         for (Pair(i, idx) <- bb.toList.zipWithIndex) {
           i match {
             case LOAD_LOCAL(l) =>
-              defs = defs + ((bb, idx)) -> rd._1
+              defs = defs + ((bb, idx)) -> rd.vars
 //              Console.println(i + ": " + (bb, idx) + " rd: " + rd + " and having: " + defs)
             case RETURN(_) | JUMP(_) | CJUMP(_, _, _, _) | CZJUMP(_, _, _, _) | STORE_FIELD(_, _) |
                  DROP(_) | THROW()   | STORE_ARRAY_ITEM(_) | SCOPE_ENTER(_) | SCOPE_EXIT(_) |
@@ -253,7 +253,7 @@ abstract class DeadCodeElimination extends SubComponent {
       }
 
       if (n > 0) {
-        val stack = rdef.in(bb)._2
+        val stack = rdef.in(bb).stack
         assert(stack.length >= n, "entry stack is too small, expected: " + n + " found: " + stack)
         stack.drop(d).take(n) foreach { defs =>
           res = defs.toList ::: res
@@ -261,7 +261,7 @@ abstract class DeadCodeElimination extends SubComponent {
       }
       res
     } else {
-      val stack = rdef.in(bb)._2
+      val stack = rdef.in(bb).stack
       assert(stack.length >= m, "entry stack is too small, expected: " + m + " found: " + stack)
       stack.take(m) flatMap (_.toList)
     }
diff --git a/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala b/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala
index 3f48f8b576..177b7301f5 100644
--- a/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala
+++ b/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala
@@ -236,13 +236,13 @@ abstract class Inliners extends SubComponent {
            i match {
              case RETURN(kind) => kind match {
                  case UNIT =>
-                   if (!info._2.types.isEmpty) {
-                     info._2.types foreach { t => inlinedBlock(bb).emit(DROP(t), targetPos); }
+                   if (!info.stack.types.isEmpty) {
+                     info.stack.types foreach { t => inlinedBlock(bb).emit(DROP(t), targetPos); }
                    }
                  case _ =>
-                   if (info._2.length > 1) {
+                   if (info.stack.length > 1) {
                      inlinedBlock(bb).emit(STORE_LOCAL(retVal), targetPos);
-                     info._2.types.drop(1) foreach { t => inlinedBlock(bb).emit(DROP(t), targetPos); }
+                     info.stack.types.drop(1) foreach { t => inlinedBlock(bb).emit(DROP(t), targetPos); }
                      inlinedBlock(bb).emit(LOAD_LOCAL(retVal), targetPos);
                    }
                }
@@ -294,7 +294,7 @@ abstract class Inliners extends SubComponent {
               if (!retry) {
                 i match {
                   case CALL_METHOD(msym, Dynamic) =>
-                    val receiver = info._2.types.drop(msym.info.paramTypes.length).head match {
+                    val receiver = info.stack.types.drop(msym.info.paramTypes.length).head match {
                       case REFERENCE(s) => s;
                       case _ => NoSymbol;
                     }
@@ -323,7 +323,7 @@ abstract class Inliners extends SubComponent {
                               && (inlinedMethods(inc.symbol) < 2)
                               && (inc.code ne null)
                               && shouldInline(m, inc)
-                              && isSafeToInline(m, inc, info._2)) {
+                              && isSafeToInline(m, inc, info.stack)) {
                             retry = true;
                             if (!isClosureClass(receiver)) // only count non-closures
                                 count = count + 1;
@@ -339,7 +339,7 @@ abstract class Inliners extends SubComponent {
                                   + "\n\t(inlinedMethods(inc.symbol) < 2): " + (inlinedMethods(inc.symbol) < 2)
                                   + "\n\tinc.code ne null: " + (inc.code ne null)
                                   + "\n\tinc.code.blocks.length < MAX_INLINE_SIZE: " + (inc.code.blocks.length < MAX_INLINE_SIZE) + "(" + inc.code.blocks.length + ")"
-                                  + "\n\tisSafeToInline(m, inc, info._2): " + isSafeToInline(m, inc, info._2)
+                                  + "\n\tisSafeToInline(m, inc, info.stack): " + isSafeToInline(m, inc, info.stack)
                                   + "\n\tshouldInline heuristics: " + shouldInline(m, inc));
                           }
                         case None =>
@@ -428,8 +428,10 @@ abstract class Inliners extends SubComponent {
     }
 
     private def lookupImpl(meth: Symbol, clazz: Symbol): Symbol = {
-//      println("\t\tlooking up " + meth + " in " + clazz.fullNameString + " meth.owner = " + meth.owner)
-      if (meth.owner == clazz) meth
+      //println("\t\tlooking up " + meth + " in " + clazz.fullNameString + " meth.owner = " + meth.owner)
+      if (meth.owner == clazz
+          || clazz == definitions.AllRefClass
+          || clazz == definitions.AllClass) meth
       else {
         val implementingMethod = meth.overridingSymbol(clazz)
         if (implementingMethod != NoSymbol)