From a61449bc644c7880639847abfe23012a031e257b Mon Sep 17 00:00:00 2001 From: Iulian Dragos Date: Fri, 20 Jan 2006 16:33:06 +0000 Subject: Added option '-Xlinearizer:' and made 'rev... Added option '-Xlinearizer:' and made 'reverse post order' the default linearization strategy, to greatly improve performance on java 1.4 --- src/compiler/scala/tools/nsc/Settings.scala | 1 + .../tools/nsc/backend/icode/BasicBlocks.scala | 4 +- .../scala/tools/nsc/backend/icode/ICodes.scala | 11 ++++ .../tools/nsc/backend/icode/Linearizers.scala | 71 +++++++++++++++++++++- .../scala/tools/nsc/backend/icode/Printers.scala | 1 - .../scala/tools/nsc/backend/jvm/GenJVM.scala | 2 - 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; -- cgit v1.2.3