diff options
author | Iulian Dragos <jaguarul@gmail.com> | 2006-05-31 10:43:12 +0000 |
---|---|---|
committer | Iulian Dragos <jaguarul@gmail.com> | 2006-05-31 10:43:12 +0000 |
commit | 213addb673ea0003ea13cb5ec7c402254b29dfc7 (patch) | |
tree | 10cf95921ba6b8bc21e7b8f02d42f0d70367eba7 | |
parent | 23904f63552d7cb98865d5a07101e2e9795d2ad1 (diff) | |
download | scala-213addb673ea0003ea13cb5ec7c402254b29dfc7.tar.gz scala-213addb673ea0003ea13cb5ec7c402254b29dfc7.tar.bz2 scala-213addb673ea0003ea13cb5ec7c402254b29dfc7.zip |
10 files changed, 360 insertions, 17 deletions
diff --git a/src/compiler/scala/tools/nsc/Global.scala b/src/compiler/scala/tools/nsc/Global.scala index 7ab7d5872a..12c1a80f02 100644 --- a/src/compiler/scala/tools/nsc/Global.scala +++ b/src/compiler/scala/tools/nsc/Global.scala @@ -26,7 +26,7 @@ import transform._ import backend.icode.{ICodes, GenICode, Checkers} import backend.ScalaPrimitives import backend.jvm.GenJVM -import backend.opt.{Inliners, ClosureElimination} +import backend.opt.{Inliners, ClosureElimination, DeadCodeElimination} import backend.icode.analysis._ class Global(val settings: Settings, val reporter: Reporter) extends SymbolTable @@ -99,7 +99,7 @@ class Global(val settings: Settings, val reporter: Reporter) extends SymbolTable def inform(msg: String) = System.err.println(msg) def inform[T](msg: String, value: T): T = { inform(msg+value); value } - //reporter.info(null, msg, true); + //reporter.info(null, msg, true); def informProgress(msg: String) = if (settings.verbose.value) inform("[" + msg + "]") @@ -311,7 +311,11 @@ class Global(val settings: Settings, val reporter: Reporter) extends SymbolTable val global: Global.this.type = Global.this } - object closser extends ClosureElimination { + object closureElimination extends ClosureElimination { + val global: Global.this.type = Global.this + } + + object deadCode extends DeadCodeElimination { val global: Global.this.type = Global.this } @@ -344,7 +348,8 @@ class Global(val settings: Settings, val reporter: Reporter) extends SymbolTable cleanup, genicode, inliner, - closser, + closureElimination, + deadCode, genJVM, sampleTransform); @@ -416,10 +421,10 @@ class Global(val settings: Settings, val reporter: Reporter) extends SymbolTable override val terminalPhase : Phase = if (onlyPresentation) typerPhase.next.next - else new GlobalPhase(p) { + else /* new GlobalPhase(p) { def name = "terminal" def apply(unit: CompilationUnit): unit = {} - } + }*/ p; private def addUnit(unit: CompilationUnit): unit = { unitbuf += unit diff --git a/src/compiler/scala/tools/nsc/Settings.scala b/src/compiler/scala/tools/nsc/Settings.scala index e54c051d11..8721d377e0 100644 --- a/src/compiler/scala/tools/nsc/Settings.scala +++ b/src/compiler/scala/tools/nsc/Settings.scala @@ -112,6 +112,7 @@ class Settings(error: String => unit) { val inline = BooleanSetting("-Xinline", "Perform inlining when possible") val Xcloselim = BooleanSetting("-Xcloselim", "Perform closure elimination") + val Xdce = BooleanSetting("-Xdce", "Perform dead code elimination") val Xshowcls = StringSetting ("-Xshowcls", "class", "Show class info", "") val Xshowobj = StringSetting ("-Xshowobj", "object", "Show object info", "") val Xshowicode = BooleanSetting("-Xshowicode", "Print the generated ICode") diff --git a/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala b/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala index 5209fde3cb..df0a85a0bb 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala @@ -87,6 +87,29 @@ trait BasicBlocks requires ICodes { else instructionList.length; + /** Return the index of the instruction which produced the value + * consumed by the given instruction. */ + def findDef(pos: Int): Option[Int] = { + assert(closed); + var i = pos; + var d = 0; + while (i > 0 && d >= 0) { + i = i - 1; + d = d + (instrs(i).consumed - instrs(i).produced); + } + if (i >= 0) + Some(i) + else + None + } + + /** Return the n-th instruction. */ + def apply(n: Int): Instruction = { + if (closed) + instrs(n) + else + instructionList.reverse(n) + } ///////////////////// Substitutions /////////////////////// @@ -146,6 +169,23 @@ trait BasicBlocks requires ICodes { changed } + /** Remove instructions found at the given positions. */ + def removeInstructionsAt(positions: Int*): Unit = { + assert(closed); + val removed = positions.toList; + val newInstrs = new Array[Instruction](instrs.length - positions.length); + var i = 0; + var j = 0; + while (i < instrs.length) { + if (!removed.contains(i)) { + newInstrs(j) = instrs(i); + j = j + 1; + } + i = i + 1; + } + instrs = newInstrs; + } + /** Replace all instructions found in the map. */ def subst(map: Map[Instruction, Instruction]) = if (!closed) substOnList(map) else { diff --git a/src/compiler/scala/tools/nsc/backend/icode/ICodes.scala b/src/compiler/scala/tools/nsc/backend/icode/ICodes.scala index 9863b54417..b16e9a9893 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/ICodes.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/ICodes.scala @@ -11,6 +11,7 @@ import java.io.PrintWriter; import scala.tools.nsc.symtab._; import scala.collection.mutable.HashMap; +import analysis.Liveness; /** Glue together ICode parts. */ @@ -68,16 +69,16 @@ abstract class ICodes extends AnyRef b.successors.length == 1; val succ = b.successors.head; succ.predecessors.length == 1; - succ.predecessors.head == b -/* !(m.exh.contains { (e: ExceptionHandler) => e.covers(b) && !e.covers(succ) }) */) { - Console.println("Block " + b + ".lastInstruction" + b.lastInstruction); - Console.println(" has successors: " + b.successors + " and succ has pred: " + succ.predecessors); - //yield Pair(b, succ) - } -// Console.println("Mergeable: " + mergeablePairs.mkString("", "\n", "")); + succ.predecessors.head == b; + !(m.exh.contains { (e: ExceptionHandler) => e.covers(b) && !e.covers(succ) })) + yield Pair(b, succ) () } + object liveness extends Liveness { + val global: ICodes.this.global.type = ICodes.this.global; + } + def init = { } } diff --git a/src/compiler/scala/tools/nsc/backend/icode/Opcodes.scala b/src/compiler/scala/tools/nsc/backend/icode/Opcodes.scala index ea280b6fd2..856e91283b 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/Opcodes.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/Opcodes.scala @@ -62,6 +62,12 @@ trait Opcodes requires ICodes { /** This abstract method returns the number of produced elements on the stack */ def produced : Int = 0; + /** This instruction consumes these types from the top of the stack. */ + def consumedTypes: List[TypeKind] = Nil; + + /** This instruction produces these types on top of the stack. */ + def producedTypes: List[TypeKind] = Nil; + /** This method returns the difference of size of the stack when the instruction is used */ def difference = produced-consumed; @@ -71,7 +77,7 @@ trait Opcodes requires ICodes { object opcodes { - /** Loads the "this" references on top of the stack. + /** Loads "this" on top of the stack. * Stack: ... * ->: ...:ref */ @@ -81,6 +87,8 @@ trait Opcodes requires ICodes { override def consumed = 0; override def produced = 1; + + override def producedTypes = List(REFERENCE(clasz)); } /** Loads a constant on the stack. @@ -93,6 +101,8 @@ trait Opcodes requires ICodes { override def consumed = 0; override def produced = 1; + + override def producedTypes = List(toTypeKind(constant.tpe)); } /** Loads an element of an array. The array and the index should @@ -106,6 +116,9 @@ trait Opcodes requires ICodes { override def consumed = 2; override def produced = 1; + + override def consumedTypes = List(ARRAY(kind), INT); + override def producedTypes = List(kind); } /** Load a local variable on the stack. It can be a method argument. @@ -118,6 +131,8 @@ trait Opcodes requires ICodes { override def consumed = 0; override def produced = 1; + + override def producedTypes = List(local.kind); } /** Load a field on the stack. The object to which it refers should be @@ -132,6 +147,9 @@ trait Opcodes requires ICodes { override def consumed = if(isStatic) 0 else 1; override def produced = 1; + + override def consumedTypes = if (isStatic) Nil else List(REFERENCE(field.owner)); + override def producedTypes = List(toTypeKind(field.tpe)); } case class LOAD_MODULE(module: Symbol) extends Instruction { @@ -143,6 +161,8 @@ trait Opcodes requires ICodes { override def consumed = 0; override def produced = 1; + + override def producedTypes = List(REFERENCE(module)); } /** Store a value into an array at a specified index. @@ -155,6 +175,8 @@ trait Opcodes requires ICodes { override def consumed = 3; override def produced = 0; + + override def consumedTypes = List(ARRAY(kind), INT, kind); } /** Store a value into a local variable. It can be an argument. @@ -167,6 +189,8 @@ trait Opcodes requires ICodes { override def consumed = 1; override def produced = 0; + + override def consumedTypes = List(local.kind); } /** Store a value into a field. @@ -180,6 +204,12 @@ trait Opcodes requires ICodes { override def consumed = if(isStatic) 1 else 2; override def produced = 0; + + override def consumedTypes = + if (isStatic) + List(toTypeKind(field.tpe)) + else + List(REFERENCE(field.owner), toTypeKind(field.tpe)); } /** Call a primitive function. @@ -206,7 +236,38 @@ trait Opcodes requires ICodes { case EndConcat => 1; } override def produced = 1; - } + + override def consumedTypes = primitive match { + case Negation(kind) => List(kind); + case Test(_, kind, true) => List(kind); + case Test(_, kind, false) => List(kind, kind); + case Comparison(_, kind) => List(kind, kind); + case Arithmetic(NOT, kind) => List(kind); + case Arithmetic(_, kind) => List(kind, kind); + case Logical(_, kind) => List(kind, kind); + case Shift(_, kind) => List(kind, INT); + case Conversion(from, _) => List(from); + case ArrayLength(kind) => List(ARRAY(kind)); + case StringConcat(kind) => List(ConcatClass, kind); + case StartConcat => Nil; + case EndConcat => List(ConcatClass); + } + + override def producedTypes = primitive match { + case Negation(kind) => List(kind); + case Test(_, _, true) => List(BOOL); + case Test(_, _, false) => List(BOOL); + case Comparison(_, _) => List(INT); + case Arithmetic(_, kind) => List(kind); + case Logical(_, kind) => List(kind); + case Shift(_, kind) => List(kind); + case Conversion(_, to) => List(to); + case ArrayLength(_) => List(INT); + case StringConcat(_) => List(ConcatClass); + case StartConcat => List(ConcatClass); + case EndConcat => List(REFERENCE(global.definitions.StringClass)); + } + } /** This class represents a CALL_METHOD instruction * STYLE: dynamic / static(StaticInstance) 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 9585c929dc..36e10d6366 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/analysis/CompleteLattice.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/CompleteLattice.scala @@ -15,5 +15,5 @@ trait CompleteLattice { def bottom: Elem; /** Compute the least upper bound of a list of elements. */ - def lub(xs: List[Elem]): Elem = xs reduceLeft lub2; + def lub(xs: List[Elem]): Elem = if (xs == Nil) bottom else xs reduceLeft lub2; } 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 4c18086d13..1dfe643afd 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/analysis/DataFlowAnalysis.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/DataFlowAnalysis.scala @@ -42,4 +42,21 @@ trait DataFlowAnalysis[L <: CompleteLattice] { } } } + + def backwardAnalysis(f: (P, lattice.Elem) => lattice.Elem): Unit = { + while (!worklist.isEmpty) { + val point = worklist.elements.next; worklist -= point; + + out(point) = lattice.lub(point.successors map in.apply); + val input = f(point, out(point)); + + if (in(point) == (lattice.bottom) || input != in(point)) { + in(point) = input; + point.predecessors foreach { p => + if (!worklist.contains(p)) + worklist += p; + } + } + } + } } diff --git a/src/compiler/scala/tools/nsc/backend/icode/analysis/Liveness.scala b/src/compiler/scala/tools/nsc/backend/icode/analysis/Liveness.scala new file mode 100644 index 0000000000..dfaf52a24c --- /dev/null +++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/Liveness.scala @@ -0,0 +1,109 @@ +package scala.tools.nsc.backend.icode.analysis; + +import scala.collection.mutable.{HashMap, Map} +import scala.collection.immutable.{Set, ListSet} + +/** + * Compute liveness information for local variables. + */ +abstract class Liveness { + val global: Global; + import global._; + import icodes._; + + /** The lattice for this analysis. */ + object livenessLattice extends CompleteLattice { + type Elem = Set[Local]; + + val top: Elem = new ListSet[Local]() { + override def equals(that: Any): Boolean = this eq that.asInstanceOf[AnyRef]; + } + + val bottom: Elem = new ListSet[Local]() { + override def equals(that: Any): Boolean = this eq that.asInstanceOf[AnyRef]; + } + + def lub2(a: Elem, b: Elem): Elem = a incl b; + } + + final class LivenessAnalysis extends DataFlowAnalysis[livenessLattice.type] { + type P = BasicBlock; + val lattice = livenessLattice; + + var method: IMethod = _; + + val gen: Map[BasicBlock, Set[Local]] = new HashMap(); + val kill:Map[BasicBlock, Set[Local]] = new HashMap(); + + def init(m: IMethod): Unit = { + this.method = m; + + for (val b <- m.code.blocks.toList; + val Pair(g, k) = genAndKill(b)) { + gen += b -> g; + kill += b -> k; + } + + init { + worklist ++= m.code.blocks.toList; + m.code.blocks.foreach { b => + in(b) = lattice.bottom; + out(b) = lattice.bottom; + } + } + } + + import opcodes._; + + /** Return the gen and kill sets for this block. */ + def genAndKill(b: BasicBlock): Pair[Set[Local], Set[Local]] = { + var genSet = new ListSet[Local]; + var killSet = new ListSet[Local]; + for (val i <- b.toList) i match { + case LOAD_LOCAL(local) if (!killSet(local)) => genSet = genSet + local; + case STORE_LOCAL(local) => killSet = killSet + local; + case _ => (); + } + Pair(genSet, killSet) + } + + override def run: Unit = { + backwardAnalysis(blockTransfer); + if (settings.debug.value) { + linearizer.linearize(method).foreach(b => if (b != method.code.startBlock) + assert(in(b) != lattice.bottom, + "Block " + b + " in " + this.method + " has input equal to bottom -- not visited?")); + } + } + + def blockTransfer(b: BasicBlock, out: lattice.Elem): lattice.Elem = + gen(b) incl (out excl kill(b)) + + /** Abstract interpretation for one instruction. */ + def interpret(out: lattice.Elem, i: Instruction): lattice.Elem = { + var in = out; + + if (settings.debug.value) { + log("- " + i); + log("out: " + out); + log("\n"); + } + + i match { + case LOAD_LOCAL(l) => in = in + l; + case STORE_LOCAL(l) => in = in - l; + case _ => + () + } + in + } /* def interpret */ + + override def toString(): String = { + val buf = new StringBuffer(); + for (val b <- method.code.blocks.toList) { + buf.append("\nlive-in(" + b + ")=" + in(b) + "\nlive-out(" + b + ")=" + out(b)); + } + buf.toString() + } + } /* Liveness analysis */ +} diff --git a/src/compiler/scala/tools/nsc/backend/opt/ClosureElimination.scala b/src/compiler/scala/tools/nsc/backend/opt/ClosureElimination.scala index f13eb65832..27bb116a3f 100644 --- a/src/compiler/scala/tools/nsc/backend/opt/ClosureElimination.scala +++ b/src/compiler/scala/tools/nsc/backend/opt/ClosureElimination.scala @@ -18,7 +18,7 @@ abstract class ClosureElimination extends SubComponent { import icodes._; import icodes.opcodes._; - val phaseName = "closurelim"; + val phaseName = "closurelimination"; /** Create a new phase */ override def newPhase(p: Phase) = new ClosureEliminationPhase(p); diff --git a/src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala b/src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala new file mode 100644 index 0000000000..791dcd50c2 --- /dev/null +++ b/src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala @@ -0,0 +1,109 @@ +/* NSC -- new scala compiler + * Copyright 2005 LAMP/EPFL + * @author Iulian Dragos + */ + +// $Id: $ + +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._; + +/** + */ +abstract class DeadCodeElimination extends SubComponent { + import global._; + import icodes._; + import icodes.opcodes._; + + val phaseName = "deadcode"; + + /** Create a new phase */ + override def newPhase(p: Phase) = new DeadCodeEliminationPhase(p); + + /** Dead code elimination phase. + */ + class DeadCodeEliminationPhase(prev: Phase) extends GlobalPhase(prev) { + def name = phaseName; + override def newFlags = phaseNewFlags; + + override def erasedTypes = true; + val dce = new DeadCode(); + + override def run: Unit = { + if (settings.debug.value) inform("[running phase " + name + " on icode]"); + if (settings.Xdce.value) + classes.values foreach dce.analyzeClass; + } + override def apply(unit: CompilationUnit): Unit = + abort("Dead code elimination works on icode classes, not on compilation units!"); + } + + /** Remove dead code. + */ + class DeadCode { + def analyzeClass(cls: IClass): Unit = + cls.methods.foreach { m => + analyzeMethod(m); + } + + val a = new liveness.LivenessAnalysis(); + + def analyzeMethod(m: IMethod): Unit = if (m.code ne null) { + log("DCE on " + m); + a.init(m); + a.run; + + for (val bb <- m.code.blocks.toList; + val Pair(i, pos) <- bb.toList.zipWithIndex.reverse) { + var live = a.out(bb); + + i match { + case STORE_LOCAL(l) if (!live(l)) => + removeDefUse(bb, pos); + case _ => () + } + live = a.interpret(live, i); + } + } + + /** Remove a pair def-use, if safe to do so. The `use' is given by index + * in the basic block. The `def' is the closest previous instruction which + * produced the top value on the stack. + */ + def removeDefUse(bb: BasicBlock, use: Int): Unit = { + bb.findDef(use) match { + case Some(defPos) => + val definition = bb(defPos); + if (isSafeToRemove(definition)) { + log("Removing instructions at BB " + bb + " def: " + definition + ", use: " + bb(use)); + + if (definition.consumed == 0) { + bb.removeInstructionsAt(defPos, use) + } else { + bb.replaceInstruction(definition, definition.consumedTypes map DROP); + bb.removeInstructionsAt(use); + } + } + case None => + val i = bb(use); + bb.replaceInstruction(i, i.consumedTypes map DROP); + log("Replaced dead " + i + " by DROP in bb " + bb); + } + } + + def isSafeToRemove(i: Instruction): Boolean = i match { +/* case LOAD_LOCAL(l) => true + case LOAD_FIELD(_, _) => true + case THIS(_) => true +*/ + case CALL_METHOD(m, style) => + (m.isClassConstructor && + definitions.refClass.values.contains(m.owner)); + case _ => true; + } + + } /* DeadCode */ +}
\ No newline at end of file |