Fixed some problems with the closure eliminatio...

Fixed some problems with the closure elimination phase.

6 files changed, 168 insertions, 92 deletions

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 4de2e24014..242c9e96fe 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/analysis/CopyPropagation.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/CopyPropagation.scala
@@ -15,14 +15,15 @@ abstract class CopyPropagation {
   /** Locations can be local variables. */
   abstract sealed class Location;
   case class LocalVar(l: Local) extends Location;
+  case class Field(r: Record, sym: Symbol) extends Location;
 
   /** Values that can be on the stack. */
   abstract class Value;
   case class This extends Value;
   case class Record(cls: Symbol, bindings: Map[Symbol, Value]) extends Value;
   case class Deref(l: Location) extends Value;
-  case class Field(r: Record, sym: Symbol)   extends Value;
   case object Unknown extends Value;
+  object AllRecords extends Record(NoSymbol, new HashMap[Symbol, Value]);
 
   /** The lattice for this analysis.   */
   object copyLattice extends CompleteLattice {
@@ -51,7 +52,6 @@ abstract class CopyPropagation {
         var stop = false;
 
         while (bindings.isDefinedAt(LocalVar(target)) && !stop) {
-          Console.println("finding alias for " + target);
           bindings(LocalVar(target)) match {
             case Deref(LocalVar(t)) => target = t;
             case _ => stop = true;
@@ -112,8 +112,8 @@ abstract class CopyPropagation {
       else if (b eq bottom) a
       else if (a == b) a
       else {
-        assert(a.stack.length == b.stack.length,
-               "Invalid stacks in states: " + a + b);
+        if (a.stack.length != b.stack.length)
+          throw new LubError(a, b, "Invalid stacks in states: ");
         val resStack = List.map2(a.stack, b.stack) { (v1, v2) =>
           if (v1 == v2) v1 else Unknown
         }
@@ -145,6 +145,9 @@ abstract class CopyPropagation {
         m.exh foreach { e =>
           in(e.startBlock) = new copyLattice.State(copyLattice.emptyBinding, Unknown :: Nil);
         }
+
+        // first block is special: it's not bottom, but a precisely defined state with no bindings
+        in(m.code.startBlock) = new lattice.State(lattice.emptyBinding, Nil);
       }
     }
 
@@ -168,17 +171,18 @@ abstract class CopyPropagation {
       var out = in.dup;
 
       if (settings.debug.value) {
-        Console.println("- " + i);
-        Console.println("in: " + in);
-        Console.println("\n");
+        log("- " + i);
+        log("in: " + in);
+        log("\n");
       }
 
       i match {
         case THIS(_) =>
           out.stack = This :: out.stack;
 
-        case CONSTANT(_) =>
-          out.stack = Unknown :: out.stack;
+        case CONSTANT(k) =>
+        	if (k.tag != UnitTag)
+        	  out.stack = Unknown :: out.stack;
 
         case LOAD_ARRAY_ITEM(_) =>
           out.stack = (Unknown :: out.stack.drop(2));
@@ -192,7 +196,7 @@ abstract class CopyPropagation {
           else {
             val v1 = in.stack match {
               case (r @ Record(cls, bindings)) :: xs =>
-                Field(r, field)
+                Deref(Field(r, field))
 
               case _ => Unknown
             }
@@ -206,7 +210,7 @@ abstract class CopyPropagation {
           out.stack = out.stack.drop(3);
 
         case STORE_LOCAL(local) =>
-          cleanReferencesTo(out, local.sym);
+          cleanReferencesTo(out, LocalVar(local));
           in.stack match {
             case Unknown :: xs => ();
             case v :: vs =>
@@ -225,7 +229,7 @@ abstract class CopyPropagation {
             out.stack = out.stack.drop(1);
           else {
             out.stack = out.stack.drop(2);
-            cleanReferencesTo(out, field);
+            cleanReferencesTo(out, Field(AllRecords, field));
             in.stack match {
               case v :: Record(_, bindings) :: vs =>
                 bindings += field -> v;
@@ -327,12 +331,11 @@ abstract class CopyPropagation {
      *  and bindings. It is called when a new assignment destroys
      *  previous copy-relations.
      */
-    final def cleanReferencesTo(s: copyLattice.State, sym: Symbol): Unit = {
+    final def cleanReferencesTo(s: copyLattice.State, target: Location): Unit = {
       def cleanRecord(r: Record): Record = {
         r.bindings filter { (loc, value) =>
           value match {
-            case Deref(LocalVar(sym1)) if (sym1 == sym) => false
-            case Field(_, sym1) if (sym1 == sym) => false
+            case Deref(loc1) if (loc1 == target) => false
             case _ => true
           }
         }
@@ -346,14 +349,17 @@ abstract class CopyPropagation {
       }}
 
       s.bindings filter { (loc, value) =>
-        value match {
-          case Deref(LocalVar(sym1)) if (sym1 == sym) => false
-          case Field(_, sym1) if (sym1 == sym) => false
+        (value match {
+          case Deref(loc1) if (loc1 == target) => false
           case Record(_, _) =>
             cleanRecord(value.asInstanceOf[Record]);
             true
           case _ => true
-        }
+        }) &&
+        (loc match {
+          case l: Location if (l == target) => false
+          case _ => true
+        })
       }
     }
 
@@ -361,17 +367,10 @@ abstract class CopyPropagation {
      * by the result of the call. If the method is impure, all bindings to record fields are cleared.
      */
     final def simulateCall(s: copyLattice.State, method: Symbol, static: Boolean): copyLattice.State = {
-//       if (static)
-//         Console.println("Method type is: " + method.info);
-
       val out = new copyLattice.State(s.bindings, s.stack);
       out.stack = out.stack.drop(method.info.paramTypes.length + (if (static) 0 else 1));
-//       if (static)
-//         Console.println("Stack after drops: " + out.stack);
       if (method.info.resultType != definitions.UnitClass.tpe)
         out.stack = Unknown :: out.stack;
-//       if (static)
-//         Console.println("Stack after return type: " + out.stack);
       if (!isPureMethod(method))
         invalidateRecords(out);
       out
@@ -387,7 +386,7 @@ abstract class CopyPropagation {
 
       s.bindings filter { (loc, value) =>
         value match {
-          case Field(_, _) => false
+          case Deref(Field(_, _)) => false
           case _ => true
         }
       }
diff --git a/src/compiler/scala/tools/nsc/backend/icode/analysis/DataFlowAnalysis.scala b/src/compiler/scala/tools/nsc/backend/icode/analysis/DataFlowAnalysis.scala
index 93d265caac..4c18086d13 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/analysis/DataFlowAnalysis.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/DataFlowAnalysis.scala
@@ -37,7 +37,7 @@ trait DataFlowAnalysis[L <: CompleteLattice] {
         succs foreach { p =>
           if (!worklist.contains(p))
             worklist += p;
-          in(p) = lattice.lub(p.predecessors map out.apply)
+          in(p) = lattice.lub(in(p) :: (p.predecessors map out.apply))
         }
       }
     }
diff --git a/src/compiler/scala/tools/nsc/backend/icode/analysis/LubError.scala b/src/compiler/scala/tools/nsc/backend/icode/analysis/LubError.scala
new file mode 100644
index 0000000000..0271f8ebea
--- /dev/null
+++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/LubError.scala
@@ -0,0 +1,5 @@
+package scala.tools.nsc.backend.icode.analysis;
+
+class LubError(a: Any, b: Any, msg: String) extends Exception {
+  override def toString() = "Lub error: " + msg + a + b;
+}
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala b/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala
index 03c45cef94..4a6d1b2c4e 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala
@@ -541,6 +541,18 @@ abstract class GenJVM extends SubComponent {
       var crtPC = 0;
 
       b traverse ( instr => {
+        class CompilationError(msg: String) extends Error {
+          override def toString(): String = {
+            msg +
+            "\nCurrent method: " + method +
+            "\nCurrent block: " + b +
+            "\nCurrent instruction: " + instr +
+            "\n---------------------" +
+            dump(method)
+          }
+        }
+        def assert(cond: Boolean, msg: String) = if (!cond) throw new CompilationError(msg);
+
         if (b.lastInstruction == instr)
           endPC(b) = jcode.getPC();
 
@@ -816,7 +828,9 @@ abstract class GenJVM extends SubComponent {
 
         crtPC = jcode.getPC();
         val crtLine = try { clasz.cunit.position(instr.pos).line; } catch {
-            case _: Error => lastLineNr;
+            case _: Error =>
+              log("Warning: wrong position in: " + method);
+              lastLineNr;
         }
 	//System.err.println("CRTLINE: " + instr.pos + " " +
 	//	   /* (if (instr.pos < clasz.cunit.source.content.length) clasz.cunit.source.content(instr.pos) else '*') + */ " " + crtLine);
@@ -1044,13 +1058,13 @@ abstract class GenJVM extends SubComponent {
     def indexOf(m: IMethod, sym: Symbol): Int = {
       val Some(local) = m.lookupLocal(sym);
       assert (local.index >= 0,
-              "Invalid index for: " + local);
+              "Invalid index for: " + local + "{" + local.hashCode + "}");
       local.index
     }
 
     def indexOf(local: Local): Int = {
       assert (local.index >= 0,
-              "Invalid index for: " + local);
+              "Invalid index for: " + local + "{" + local.hashCode + "}");
       local.index
     }
 
@@ -1065,7 +1079,7 @@ abstract class GenJVM extends SubComponent {
 
       for (val l <- m.locals) {
         if (settings.debug.value)
-          log("Index value for " + l + ": " + idx);
+          log("Index value for " + l + "{" + l.hashCode + "}: " + idx);
         l.index = idx;
         idx = idx + sizeOf(l.kind);
       }
@@ -1204,5 +1218,12 @@ abstract class GenJVM extends SubComponent {
                                         lvTab.array());
         jcode.addAttribute(attr);
     }
+
+    def assert(cond: Boolean, msg: String) = if (!cond) {
+        dump(method);
+        throw new Error(msg + "\nMethod: " + method)
+      }
+
+    def assert(cond: Boolean): Unit = assert(cond, "Assertion failed.");
   }
 }
diff --git a/src/compiler/scala/tools/nsc/backend/opt/ClosureElimination.scala b/src/compiler/scala/tools/nsc/backend/opt/ClosureElimination.scala
index 414f51365f..f13eb65832 100644
--- a/src/compiler/scala/tools/nsc/backend/opt/ClosureElimination.scala
+++ b/src/compiler/scala/tools/nsc/backend/opt/ClosureElimination.scala
@@ -1,4 +1,4 @@
-/* NSC -- new scala compiler
+ /* NSC -- new scala compiler
  * Copyright 2005 LAMP/EPFL
  * @author  Iulian Dragos
  */
@@ -8,6 +8,7 @@
 package scala.tools.nsc.backend.opt;
 
 import scala.collection.mutable.{Map, HashMap};
+import scala.tools.nsc.backend.icode.analysis.LubError;
 import scala.tools.nsc.symtab._;
 
 /**
@@ -56,10 +57,34 @@ abstract class ClosureElimination extends SubComponent {
       ret
     }
 
+    /** A simple peephole optimizer. */
+    val peephole = new PeepholeOpt( (i1, i2) =>
+    	Pair(i1, i2) match {
+        case Pair(CONSTANT(c), DROP(_)) =>
+          if (c.tag == UnitTag)
+            Some(List(i2))
+          else
+            Some(Nil);
+
+        case Pair(LOAD_LOCAL(x), STORE_LOCAL(y)) =>
+        	if (x eq y) Some(Nil) else None
+
+        case Pair(LOAD_LOCAL(_), DROP(_)) =>
+          Some(Nil)
+
+        case Pair(LOAD_FIELD(sym, isStatic), DROP(_)) =>
+        	if (isStatic)
+            Some(Nil)
+          else
+            Some(DROP(REFERENCE(definitions.ObjectClass)) :: Nil);
+
+        case _ => None;
+      });
+
     def analyzeClass(cls: IClass): Unit = if (settings.Xcloselim.value) {
-      if (settings.debug.value)
-      	log("Analyzing " + cls);
-      cls.methods.foreach { m => analyzeMethod(m)
+      cls.methods.foreach { m =>
+        analyzeMethod(m);
+        peephole.transformMethod(m);
      }}
 
 
@@ -69,8 +94,8 @@ abstract class ClosureElimination extends SubComponent {
     import copyPropagation._;
 
     /* Some embryonic copy propagation. */
-    def analyzeMethod(m: IMethod): Unit = if (m.code ne null) {
-      Console.println("Analyzing " + m);
+    def analyzeMethod(m: IMethod): Unit = try {if (m.code ne null) {
+      log("Analyzing " + m);
       cpp.init(m);
       cpp.run;
 
@@ -84,27 +109,25 @@ abstract class ClosureElimination extends SubComponent {
               t match {
                 case Deref(LocalVar(v)) =>
                   bb.replaceInstruction(i, valueToInstruction(t));
-                  Console.println("replaced " + i + " with " + t);
+                  log("replaced " + i + " with " + t);
 
                 case This() =>
                   bb.replaceInstruction(i, valueToInstruction(t));
-                  Console.println("replaced " + i + " with " + t);
+                  log("replaced " + i + " with " + t);
 
                 case _ =>
                   bb.replaceInstruction(i, LOAD_LOCAL(info.getAlias(l)));
-                  Console.println("replaced " + i + " with " + info.getAlias(l));
+                  log("replaced " + i + " with " + info.getAlias(l));
 
               }
 
             case LOAD_FIELD(f, false) =>
-              Console.println(" * * * \n" + i + "\n" + info);
-
               info.stack(0) match {
                 case r @ Record(cls, bindings) if bindings.isDefinedAt(f) =>
                   bb.replaceInstruction(i,
                                         DROP(REFERENCE(cls)) ::
                                         valueToInstruction(info.getBinding(r, f)) :: Nil);
-                  Console.println("Replaced " + i + " with " + info.getBinding(r, f));
+                  log("Replaced " + i + " with " + info.getBinding(r, f));
 
                 case Deref(LocalVar(l)) =>
                   info.getBinding(l) match {
@@ -112,10 +135,9 @@ abstract class ClosureElimination extends SubComponent {
                       bb.replaceInstruction(i,
                                             DROP(REFERENCE(cls)) ::
                                             valueToInstruction(info.getBinding(r, f)) :: Nil);
-                      Console.println("Replaced " + i + " with " + info.getBinding(r, f));
+                      log("Replaced " + i + " with " + info.getBinding(r, f));
                     case _ => ();
                   }
-                  Console.println(info.getBinding(l));
 
                 case _ => ();
               }
@@ -125,6 +147,10 @@ abstract class ClosureElimination extends SubComponent {
           info = cpp.interpret(info, i);
         }
       }
+    }} catch {
+      case e: LubError =>
+        Console.println("In method: " + m);
+        Console.println(e);
     }
 
     /* Partial mapping from values to instructions that load them. */
@@ -140,7 +166,7 @@ abstract class ClosureElimination extends SubComponent {
 
 
   /** Peephole optimization. */
-/*  class PeepholeOpt(f: (Instruction, Instruction) => List[Instruction]) {
+  class PeepholeOpt(peep: (Instruction, Instruction) => Option[List[Instruction]]) {
 
     private var method: IMethod = null;
 
@@ -150,30 +176,34 @@ abstract class ClosureElimination extends SubComponent {
         transformBlock(b);
     }
 
-    def transformBlock(b: BasicBlock): Unit = {
+    def transformBlock(b: BasicBlock): Unit = if (b.size >= 2) {
       var newInstructions: List[Instruction] = Nil;
-      var first: Instruction = null;
-      var second: Instruction = null;
-
-      def emit(i: Instruction) = {
-        if (first == null)
-          first = i;
-        else if (second == null)
-          second = i
-        else {
-          newInstructions = second :: newInstructions;
-          first = second;
-          second = i;
-        }
-      }
 
-      for (val i <- b.toList) {
-        if (first && second) {
-          first = null; second = null;
-          f(first, second) foreach emit;
+      newInstructions = b.toList;
+
+      var redo = false;
+      do {
+        var h = newInstructions.head;
+        var t = newInstructions.tail;
+        var seen: List[Instruction] = Nil;
+        redo = false;
+
+        while (t != Nil) {
+          peep(h, t.head) match {
+            case Some(newInstrs) =>
+            	Console.println("Replacing " + h + " : " + t.head + " by " + newInstrs);
+              newInstructions = seen.reverse ::: newInstrs ::: t.tail;
+              redo = true;
+            case None =>
+            	()
+          }
+          seen = h :: seen;
+          h = t.head;
+          t = t.tail;
         }
-      }
+      } while (redo);
+      b.fromList(newInstructions);
     }
   }
-*/
+
 } /* class ClosureElimination */
diff --git a/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala b/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala
index ef17fc478a..004969c3c5 100644
--- a/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala
+++ b/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala
@@ -61,9 +61,10 @@ abstract class Inliners extends SubComponent {
                block:  BasicBlock,
                instr:  Instruction,
                callee: IMethod): Unit = {
-       log("Inlining " + callee + " in " + caller + " at pos: " +
-           classes(caller.symbol.owner).cunit.position(instr.pos));
+//       log("Inlining " + callee + " in " + caller + " at pos: " +
+//           classes(caller.symbol.owner).cunit.position(instr.pos));
 
+       val targetPos = instr.pos;
        val a = new analysis.MethodTFA(callee);
 
        /* The exception handlers that are active at the current block. */
@@ -72,6 +73,9 @@ abstract class Inliners extends SubComponent {
        /* Map 'original' blocks to the ones inlined in the caller. */
        val inlinedBlock: Map[BasicBlock, BasicBlock] = new HashMap;
 
+       /* Map callee's parameters to inlined local variables. */
+       val argsToLocal: Map[Local, Local] = new HashMap;
+
        val instrBefore = block.toList.takeWhile( i => i ne instr);
        val instrAfter  = block.toList.drop(instrBefore.length + 1);
 
@@ -101,6 +105,23 @@ abstract class Inliners extends SubComponent {
          handler
        }
 
+       /** Adds parameters from another method as locals */
+       def addParamsAsLocals(m: IMethod, ls: List[Local]): Unit = {
+         m.locals = m.locals ::: (ls map { a =>
+           if (a.arg) {
+             val l = new Local(a.sym, a.kind, false);
+             argsToLocal += a -> l;
+             l
+           } else
+             a
+        });
+       }
+
+       def addLocals(m: IMethod, ls: List[Local]) =
+         m.locals = m.locals ::: ls;
+       def addLocal(m: IMethod, l: Local): Unit =
+         addLocals(m, List(l));
+
        val afterBlock = newBlock;
 
        /** Map an instruction from the callee to one suitable for the caller. */
@@ -123,6 +144,14 @@ abstract class Inliners extends SubComponent {
            case RETURN(kind) =>
              JUMP(afterBlock);
 
+           case LOAD_LOCAL(l) if (argsToLocal.isDefinedAt(l)) =>
+             Console.println("Replacing load_local");
+             LOAD_LOCAL(argsToLocal(l))
+
+           case STORE_LOCAL(l) if (argsToLocal.isDefinedAt(l)) =>
+             Console.println("Replacing store_local");
+             STORE_LOCAL(argsToLocal(l))
+
            case _ => i
          }
 
@@ -140,16 +169,16 @@ abstract class Inliners extends SubComponent {
        // re-emit the instructions before the call
        block.open;
        block.clear;
-       instrBefore.foreach(block.emit);
+       instrBefore.foreach(i => block.emit(i, i.pos));
 
        // store the arguments into special locals
        callee.params.reverse.foreach { param =>
-         block.emit(STORE_LOCAL(param));
+         block.emit(STORE_LOCAL(param), targetPos);
        }
-       block.emit(STORE_LOCAL(inlinedThis));
+       block.emit(STORE_LOCAL(inlinedThis), targetPos);
 
        // jump to the start block of the callee
-       block.emit(JUMP(inlinedBlock(callee.code.startBlock)));
+       block.emit(JUMP(inlinedBlock(callee.code.startBlock)), targetPos);
        block.close;
 
        // duplicate the other blocks in the callee
@@ -160,24 +189,24 @@ abstract class Inliners extends SubComponent {
              case RETURN(kind) => kind match {
                  case UNIT =>
                    if (!info._2.types.isEmpty) {
-                     info._2.types foreach { t => inlinedBlock(bb).emit(DROP(t)); }
+                     info._2.types foreach { t => inlinedBlock(bb).emit(DROP(t), targetPos); }
                    }
                  case _ =>
                    if (info._2.length > 1) {
-                     inlinedBlock(bb).emit(STORE_LOCAL(retVal));
-                     info._2.types.drop(1) foreach { t => inlinedBlock(bb).emit(DROP(t)); }
-                     inlinedBlock(bb).emit(LOAD_LOCAL(retVal));
+                     inlinedBlock(bb).emit(STORE_LOCAL(retVal), targetPos);
+                     info._2.types.drop(1) foreach { t => inlinedBlock(bb).emit(DROP(t), targetPos); }
+                     inlinedBlock(bb).emit(LOAD_LOCAL(retVal), targetPos);
                    }
                }
              case _ => ();
            }
-           inlinedBlock(bb).emit(map(i), 0);
+           inlinedBlock(bb).emit(map(i), targetPos);
            info = a.interpret(info, i);
          }
          inlinedBlock(bb).close;
        }
 
-       instrAfter.foreach(afterBlock.emit);
+       instrAfter.foreach(i => afterBlock.emit(i, i.pos));
        afterBlock.close;
        count = count + 1;
 
@@ -185,17 +214,6 @@ abstract class Inliners extends SubComponent {
        caller.exh = (callee.exh map translateExh) ::: caller.exh;
      }
 
-
-    /** Add a local to this method, alfa-renaming is not
-     *  necessary because we use symbols to refer to locals.
-     */
-    def addLocals(m: IMethod, ls: List[Local]): Unit = {
-      m.locals = m.locals ::: ls map { l => new Local(l.sym, l.kind, false) };
-    }
-
-    def addLocal(m: IMethod, l: Local): Unit =
-      addLocals(m, List(l));
-
     val InlineAttr = if (settings.inline.value) global.definitions.getClass("scala.inline").tpe else null;
 
     def analyzeClass(cls: IClass): Unit = if (settings.inline.value) {
@@ -214,7 +232,7 @@ abstract class Inliners extends SubComponent {
       do {
         retry = false;
         if (m.code ne null) {
-          this.count = 0;
+//          this.count = 0;
           if (settings.debug.value)
             log("Analyzing " + m + " count " + count);
           tfa.init(m);
@@ -262,9 +280,12 @@ abstract class Inliners extends SubComponent {
                 info = tfa.interpret(info, i);
               }}}}
       } while (retry && count < 5);
+      normalize(m);
     } catch {
       case e =>
         Console.println("############# Cought exception: " + e + " #################");
+        Console.println("\nMethod: " + m +
+                        "\nMethod owner: " + m.symbol.owner);
         e.printStackTrace();
         dump(m);
         throw e;