Added option '-Xlinearizer:<lin>' and made 'rev...

Added option '-Xlinearizer:<lin>' and made 'reverse post order' the
default linearization strategy, to greatly improve performance on java
1.4

6 files changed, 84 insertions, 6 deletions

diff --git a/src/compiler/scala/tools/nsc/Settings.scala b/src/compiler/scala/tools/nsc/Settings.scala
index 7aae61a5e1..0ce0b34a07 100644
--- a/src/compiler/scala/tools/nsc/Settings.scala
+++ b/src/compiler/scala/tools/nsc/Settings.scala
@@ -89,6 +89,7 @@ class Settings(error: String => unit) {
   val Xshowobj      = StringSetting ("-Xshowobj", "object", "Show object info", "")
   val Xshowicode    = BooleanSetting("-Xshowicode", "Print the generated ICode")
   val Xgadt         = BooleanSetting("-Xgadt", "enable gadt for classes")
+  val Xlinearizer   = ChoiceSetting ("-Xlinearizer", "Linearizer to use", List("normal", "dfs", "rpo"), "rpo")
 
   /** A list of all settings */
   def allSettings: List[Setting] = allsettings.reverse
diff --git a/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala b/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala
index 4fc5891be8..83128a8274 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala
@@ -216,8 +216,8 @@ mixin class BasicBlocks requires ICodes {
     def successors : List[BasicBlock] = if (isEmpty) Nil else
       lastInstruction match {
         case JUMP (where) => List(where);
-        case CJUMP(success, failure, _, _) => failure::success::Nil;
-        case CZJUMP(success, failure, _, _) => failure::success::Nil;
+        case CJUMP(success, failure, _, _) => success :: failure :: Nil;
+        case CZJUMP(success, failure, _, _) => success :: failure :: Nil;
         case SWITCH(_,labels) => labels;
         case RETURN(_) => Nil;
         case THROW() => Nil;
diff --git a/src/compiler/scala/tools/nsc/backend/icode/ICodes.scala b/src/compiler/scala/tools/nsc/backend/icode/ICodes.scala
index d29a8b5433..99ecc1b1c2 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/ICodes.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/ICodes.scala
@@ -26,6 +26,17 @@ abstract class ICodes extends AnyRef
   /** The ICode representation of classes */
   var classes: List[IClass] = _;
 
+  /** The ICode linearizer. */
+  val linearizer: Linearizer =
+    if (global.settings.Xlinearizer.value == "rpo")
+      new ReversePostOrderLinearizer();
+    else if (global.settings.Xlinearizer.value == "dfs")
+      new DepthFirstLinerizer();
+    else if (global.settings.Xlinearizer.value == "normal")
+      new NormalLinearizer();
+    else
+      global.abort("Unknown linearizer: " + global.settings.Xlinearizer.value);
+
   def init = { classes = Nil }
 }
 
diff --git a/src/compiler/scala/tools/nsc/backend/icode/Linearizers.scala b/src/compiler/scala/tools/nsc/backend/icode/Linearizers.scala
index 8a3ad0fe23..52611fd4d5 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/Linearizers.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/Linearizers.scala
@@ -8,7 +8,7 @@
 package scala.tools.nsc.backend.icode;
 
 import scala.tools.nsc.ast._;
-import scala.collection.mutable.Stack;
+import scala.collection.mutable.{Stack, HashSet};
 
 mixin class Linearizers requires ICodes {
   import opcodes._;
@@ -86,4 +86,73 @@ mixin class Linearizers requires ICodes {
 
     def add(bs: List[BasicBlock]): Unit = bs foreach add;
   }
+
+  /**
+   * Linearize code using a depth first traversal.
+   */
+  class DepthFirstLinerizer extends Linearizer {
+    var blocks: List[BasicBlock] = Nil;
+
+    def linearize(m: IMethod): List[BasicBlock] = {
+      blocks = Nil;
+
+      dfs(m.code.startBlock);
+      m.exh foreach (b => dfs(b.startBlock));
+
+      blocks.reverse
+    }
+
+    def dfs(b: BasicBlock): Unit =
+      if (b.size > 0 && add(b))
+        b.successors foreach dfs;
+
+    /**
+     * Prepend b to the list, if not already scheduled.
+     * TODO: use better test than linear search
+     * @return Returns true if the block was added.
+     */
+    def add(b: BasicBlock): Boolean =
+      if (blocks.contains(b))
+        false
+      else {
+        blocks = b :: blocks;
+        true
+      }
+  }
+
+  /**
+   * Linearize code in reverse post order. In fact, it does
+   * a post order traversal, prepending visited nodes to the list.
+   * This way, it is constructed already in reverse post order.
+   */
+  class ReversePostOrderLinearizer extends Linearizer {
+    var blocks: List[BasicBlock] = Nil;
+    var visited: HashSet[BasicBlock] = new HashSet;
+
+    def linearize(m: IMethod): List[BasicBlock] = {
+      blocks = Nil;
+      visited.clear;
+
+      m.exh foreach (b => rpo(b.startBlock));
+      rpo(m.code.startBlock);
+
+      blocks
+    }
+
+    def rpo(b: BasicBlock): Unit =
+      if (b.size > 0 && !(visited contains b)) {
+        visited += b;
+        b.successors foreach rpo;
+        add(b);
+      }
+
+    /**
+     * Prepend b to the list, if not already scheduled.
+     * TODO: use better test than linear search
+     * @return Returns true if the block was added.
+     */
+    def add(b: BasicBlock) =
+      if (!blocks.contains(b))
+        blocks = b :: blocks;
+  }
 }
diff --git a/src/compiler/scala/tools/nsc/backend/icode/Printers.scala b/src/compiler/scala/tools/nsc/backend/icode/Printers.scala
index dbc7badb9a..68ead723d7 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/Printers.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/Printers.scala
@@ -21,7 +21,6 @@ abstract class Printers {
   class TextPrinter(writer: PrintWriter) {
     var margin = 0;
     var out = writer;
-    val linearizer = new NormalLinearizer();
 
     final val TAB = 2;
 
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala b/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala
index b01d39071d..7b9c00016a 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala
@@ -317,8 +317,6 @@ abstract class GenJVM extends SubComponent {
       emitClass(mirrorClass, clasz.symbol);
     }
 
-
-    val linearizer = new NormalLinearizer();
     var linearization: List[BasicBlock] = Nil;
 
     var isModuleInitialized = false;