From 28f747a2c133e2dea1ab699715517ad250f65fef Mon Sep 17 00:00:00 2001 From: Iulian Dragos Date: Wed, 28 Feb 2007 09:42:57 +0000 Subject: Revamped the icode analyses and removed some ex... Revamped the icode analyses and removed some exhaustivity checks --- src/compiler/scala/tools/nsc/Global.scala | 6 +- .../tools/nsc/backend/icode/BasicBlocks.scala | 46 +++++++- .../scala/tools/nsc/backend/icode/ICodes.scala | 39 ++----- .../scala/tools/nsc/backend/icode/Members.scala | 45 ++++++++ .../scala/tools/nsc/backend/icode/Opcodes.scala | 5 + .../scala/tools/nsc/backend/icode/Printers.scala | 5 +- .../backend/icode/analysis/CopyPropagation.scala | 29 ++--- .../nsc/backend/icode/analysis/Liveness.scala | 11 +- .../icode/analysis/ReachingDefinitions.scala | 128 +++++++++++++++++++++ .../scala/tools/nsc/backend/jvm/GenJVM.scala | 6 +- .../tools/nsc/backend/opt/ClosureElimination.scala | 2 +- .../nsc/backend/opt/DeadCodeElimination.scala | 81 +++++++++++-- .../scala/tools/nsc/backend/opt/Inliners.scala | 30 +++-- .../tools/nsc/symtab/classfile/ICodeReader.scala | 2 +- 14 files changed, 351 insertions(+), 84 deletions(-) create mode 100644 src/compiler/scala/tools/nsc/backend/icode/analysis/ReachingDefinitions.scala diff --git a/src/compiler/scala/tools/nsc/Global.scala b/src/compiler/scala/tools/nsc/Global.scala index 8d8297afd1..b097b865ab 100644 --- a/src/compiler/scala/tools/nsc/Global.scala +++ b/src/compiler/scala/tools/nsc/Global.scala @@ -319,11 +319,11 @@ class Global(var settings: Settings, var reporter: Reporter) extends SymbolTable object genicode extends GenICode { val global: Global.this.type = Global.this } - +/* object icodePrinter extends backend.icode.Printers { val global: Global.this.type = Global.this } - +*/ object scalaPrimitives extends ScalaPrimitives { val global: Global.this.type = Global.this } @@ -617,7 +617,7 @@ class Global(var settings: Settings, var reporter: Reporter) extends SymbolTable } private def writeICode(): Unit = { - val printer = new icodePrinter.TextPrinter(null, icodes.linearizer) + val printer = new icodes.TextPrinter(null, icodes.linearizer) icodes.classes.values.foreach((cls) => { val suffix = if (cls.symbol.hasFlag(Flags.MODULE)) "$.icode" else ".icode" var file = getFile(cls.symbol, suffix) diff --git a/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala b/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala index 8a6d480ca3..f54e102fca 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala @@ -80,7 +80,7 @@ trait BasicBlocks requires ICodes { } /** Compute an hashCode for the block */ - override def hashCode() = label; +// override def hashCode() = label; /** Apply a function to all the instructions of the block. */ def traverse(f: Instruction => unit) = { @@ -123,6 +123,33 @@ trait BasicBlocks requires ICodes { None } + def findDefs(idx: Int, m: Int): List[(BasicBlock, Int)] = { + assert(closed) + var res: List[(BasicBlock, Int)] = Nil + var i = idx + var n = m + // "I look for who produced the 'n' elements below the 'd' topmost slots of the stack" + var d = 0 + while (n > 0) { + i = i - 1 + val prod = instrs(i).produced + if (prod > d) { + res = (this, i) :: res + n = n - (prod - d) + } + d = d + (instrs(i).consumed - instrs(i).produced); + } + res + } + + def findDefs(bb: BasicBlock, d: Int, n: Int): List[(BasicBlock, Int)] = { + var i = bb.size + while (n > 0 && i > 0) { + + } + Nil + } + /** Return the n-th instruction. */ def apply(n: Int): Instruction = if (closed) @@ -219,6 +246,18 @@ trait BasicBlocks requires ICodes { instrs = newInstrs } + /** Remove the last instruction of this basic block. It is + * fast for an open block, but slower when the block is closed. + */ + def removeLastInstruction: Unit = { + if (closed) + removeInstructionsAt(size) + else { + instructionList = instructionList.tail + touched = true + } + } + /** Replaces all instructions found in the map. * * @param map ... @@ -287,6 +326,7 @@ trait BasicBlocks requires ICodes { def open = { closed = false ignore = false + instructionList = instructionList.reverse // prepare for appending to the head } def clear: Unit = { @@ -358,11 +398,11 @@ trait BasicBlocks requires ICodes { preds } - override def equals(other: Any): Boolean = other match { +/* override def equals(other: Any): Boolean = other match { case that: BasicBlock => that.label == label && that.code == code case _ => false } - +*/ // Instead of it, rather use a printer def print() : unit = print(java.lang.System.out) diff --git a/src/compiler/scala/tools/nsc/backend/icode/ICodes.scala b/src/compiler/scala/tools/nsc/backend/icode/ICodes.scala index 9b08ac20e7..404ebd649f 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/ICodes.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/ICodes.scala @@ -7,11 +7,11 @@ package scala.tools.nsc.backend.icode; -import java.io.PrintWriter; +import java.io.PrintWriter import scala.tools.nsc.symtab._; import scala.collection.mutable.HashMap; -import analysis.Liveness; +import analysis.{Liveness, ReachingDefinitions}; /** Glue together ICode parts. */ @@ -24,6 +24,7 @@ abstract class ICodes extends AnyRef with ExceptionHandlers with Primitives with Linearizers + with Printers { val global: Global; @@ -43,41 +44,19 @@ abstract class ICodes extends AnyRef else global.abort("Unknown linearizer: " + global.settings.Xlinearizer.value); - /** Print all classes and basic blocks. Used for debugging. */ def dump: Unit = { - val printer = new global.icodePrinter.TextPrinter(new PrintWriter(Console.out, true), - new global.icodes.DumpLinearizer()); - - global.icodes.classes.values foreach { c => printer.printClass(c); } - } + val printer = new TextPrinter(new PrintWriter(Console.out, true), + new DumpLinearizer); - def dump(m: global.icodes.IMethod) = { - val printer = new global.icodePrinter.TextPrinter(new PrintWriter(Console.out, true), - new global.icodes.DumpLinearizer()); - printer.printMethod(m); + classes.values foreach { c => printer.printClass(c); } } - /** Merge together blocks that have a single successor which has a - * single predecessor. Exception handlers are taken into account (they - * might force to break a block of straight line code like that). - * - * This method should be most effective after heavy inlining. - */ - def normalize(m: IMethod): Unit = if (m.code ne null) { - Console.println("Method " + m); - val mergeablePairs = - for (val b <- m.code.blocks.toList; - 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) })) - yield (b, succ) - () + object liveness extends Liveness { + val global: ICodes.this.global.type = ICodes.this.global; } - object liveness extends Liveness { + object reachingDefinitions extends ReachingDefinitions { val global: ICodes.this.global.type = ICodes.this.global; } diff --git a/src/compiler/scala/tools/nsc/backend/icode/Members.scala b/src/compiler/scala/tools/nsc/backend/icode/Members.scala index f185c4c4b3..6f01d7ce18 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/Members.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/Members.scala @@ -7,6 +7,8 @@ package scala.tools.nsc.backend.icode; +import java.io.PrintWriter; + import scala.collection.mutable.HashMap; import scala.collection.mutable.{Set, HashSet}; import scala.{Symbol => scala_Symbol}; @@ -230,6 +232,49 @@ trait Members requires ICodes { case _ => () } } + + /** Merge together blocks that have a single successor which has a + * single predecessor. Exception handlers are taken into account (they + * might force to break a block of straight line code like that). + * + * This method should be most effective after heavy inlining. + */ + def normalize: Unit = if (this.code ne null) { + import scala.collection.mutable.{Map, HashMap} + val nextBlock: Map[BasicBlock, BasicBlock] = HashMap.empty + for (val b <- code.blocks.toList; + b.successors.length == 1; + val succ = b.successors.head; + succ ne b; + succ.predecessors.length == 1; + succ.predecessors.head eq b; + !(exh.contains { (e: ExceptionHandler) => e.covers(b) && !e.covers(succ) })) { + nextBlock(b) = succ + } + + var bb = code.startBlock + while (!nextBlock.isEmpty) { + if (nextBlock.isDefinedAt(bb)) { + bb.open + var succ = bb + do { + succ = nextBlock(succ); + bb.removeLastInstruction + succ.toList foreach { i => bb.emit(i, i.pos) } + code.blocks -= succ + nextBlock -= bb + } while (nextBlock.isDefinedAt(succ)) + bb.close + } else + bb = nextBlock.keys.next + } + } + + def dump = { + val printer = new TextPrinter(new PrintWriter(Console.out, true), + new DumpLinearizer); + printer.printMethod(this); + } } /** Represent local variables and parameters */ diff --git a/src/compiler/scala/tools/nsc/backend/icode/Opcodes.scala b/src/compiler/scala/tools/nsc/backend/icode/Opcodes.scala index 6002c3ea6d..c02f121ae0 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/Opcodes.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/Opcodes.scala @@ -73,6 +73,9 @@ trait Opcodes requires ICodes { /** The corresponding position in the source file */ var pos: Int = Position.NOPOS; + + /** Used by dead code elimination. */ + var useful: Boolean = true } object opcodes { @@ -365,6 +368,8 @@ trait Opcodes requires ICodes { override def consumed = 1; override def produced = 1; + override val consumedTypes = List(REFERENCE(global.definitions.ObjectClass)) + override def producedTypes = List(typ) } /** This class represents a SWITCH instruction diff --git a/src/compiler/scala/tools/nsc/backend/icode/Printers.scala b/src/compiler/scala/tools/nsc/backend/icode/Printers.scala index 621936693d..06785a45ea 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/Printers.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/Printers.scala @@ -12,8 +12,8 @@ import java.io.PrintWriter; import scala.tools.nsc.util.Position; import scala.tools.nsc.symtab.Flags; -abstract class Printers { - val global: Global; +trait Printers requires ICodes { +// val global: Global; import global._; import global.icodes.opcodes._; import global.icodes._; @@ -88,6 +88,7 @@ abstract class Printers { println(" {"); println("locals: " + m.locals.mkString("", ", ", "")); println("startBlock: " + m.code.startBlock); + println("blocks: " + m.code.blocks.mkString("[", ",", "]")); println; lin.linearize(m) foreach printBlock; println("}"); 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 4da3c1db2b..8084a409fb 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/analysis/CopyPropagation.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/CopyPropagation.scala @@ -271,12 +271,12 @@ abstract class CopyPropagation { case Static(onInstance) => if (onInstance) { val obj = out.stack.drop(method.info.paramTypes.length).head - if (method.isConstructor) { + if (method.isPrimaryConstructor) { obj match { case Record(_, bindings) => for (val v <- out.stack.take(method.info.paramTypes.length + 1); v ne obj) { - bindings ++= getBindingsForClosure(in, method); + bindings ++= getBindingsForPrimaryCtor(in, method); } case _ => () } @@ -301,10 +301,10 @@ abstract class CopyPropagation { val v1 = kind match { case REFERENCE(cls) => - if (isClosureClass(cls)) +/* if (isClosureClass(cls)) Record(cls, new HashMap[Symbol, Value]) - else Unknown - + else Unknown */ + Record(cls, new HashMap[Symbol, Value]) case _ => Unknown } @@ -434,22 +434,19 @@ abstract class CopyPropagation { } } - /** Return bindings from closure's fields to the values on the stack. This + /** Return bindings from an object fields to the values on the stack. This * method has to find the correct mapping from fields to the order in which - * they are passed on the stack. - * - * @param in ... - * @param ctor ... - * @return ... + * they are passed on the stack. It works for primary constructors. */ - private def getBindingsForClosure(in: copyLattice.State, ctor: Symbol): Map[Symbol, Value] = { + private def getBindingsForPrimaryCtor(in: copyLattice.State, ctor: Symbol): Map[Symbol, Value] = { val paramAccessors = ctor.owner.constrParamAccessors; var values = in.stack.take(1 + ctor.info.paramTypes.length).reverse.drop(1); val bindings = new HashMap[Symbol, Value]; // this relies on having the same order in paramAccessors and // the arguments on the stack. It should be the same! - for (val p <- paramAccessors) { + for (val (p, i) <- paramAccessors.zipWithIndex) { + assert(p.tpe == ctor.tpe.paramTypes(i)) bindings += p -> values.head; values = values.tail; } @@ -475,11 +472,7 @@ abstract class CopyPropagation { * @return ... */ final def isPureMethod(m: Symbol): Boolean = - // MO: I added !m.hasFlag(DEFERRED) in a refactoring where - // getters now can be abstract whereas before they could not. - // Adding the condition thus keeps the old behavior. - // todo: review whether this is correct, or whether abstract getters should be included. - m.isGetter && !m.hasFlag(DEFERRED); + m.isGetter // abstract getters are still pure, as we 'know' final override def toString(): String = { var res = "" diff --git a/src/compiler/scala/tools/nsc/backend/icode/analysis/Liveness.scala b/src/compiler/scala/tools/nsc/backend/icode/analysis/Liveness.scala index 4be33c4ef1..72c74804fb 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/analysis/Liveness.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/Liveness.scala @@ -45,6 +45,8 @@ abstract class Liveness { def init(m: IMethod): Unit = { this.method = m + gen.clear + kill.clear for (val b <- m.code.blocks.toList; val Pair(g, k) = genAndKill(b)) { @@ -68,8 +70,8 @@ abstract class Liveness { 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 LOAD_LOCAL(local) if (!killSet(local)) => genSet = genSet + local + case STORE_LOCAL(local) if (!genSet(local)) => killSet = killSet + local case _ => () } Pair(genSet, killSet) @@ -87,7 +89,10 @@ abstract class Liveness { def blockTransfer(b: BasicBlock, out: lattice.Elem): lattice.Elem = gen(b) incl (out excl kill(b)) - /** Abstract interpretation for one instruction. */ + /** Abstract interpretation for one instruction. Very important: + * liveness is a backward DFA, so this method should be used to compute + * liveness *before* the given instruction `i'. + */ def interpret(out: lattice.Elem, i: Instruction): lattice.Elem = { var in = out diff --git a/src/compiler/scala/tools/nsc/backend/icode/analysis/ReachingDefinitions.scala b/src/compiler/scala/tools/nsc/backend/icode/analysis/ReachingDefinitions.scala new file mode 100644 index 0000000000..7c09d9a499 --- /dev/null +++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/ReachingDefinitions.scala @@ -0,0 +1,128 @@ +/* NSC -- new Scala compiler + * Copyright 2005-2007 LAMP/EPFL + * @author Martin Odersky + */ + +// $Id: $ + +package scala.tools.nsc.backend.icode.analysis + +import compat.StringBuilder +import scala.collection.mutable.{HashMap, Map} +import scala.collection.immutable.{Set, ListSet, HashSet} + +/** Compute reaching definitions. We are only interested in reaching + * definitions for local variables, since values on the stack + * behave as-if in SSA form: the closest instruction which produces a value + * on the stack is a reaching definition. + */ +abstract class ReachingDefinitions { + val global: Global + import global._ + import icodes._ + + /** The lattice for reaching definitions. Elements are + * a triple (local variable, basic block, index of instruction of that basic block) + */ + object rdefLattice extends CompleteLattice { + type Definition = (Local, BasicBlock, Int) + type Elem = Set[Definition] + + val top: Elem = new ListSet[Definition]() { + override def equals(that: Any): Boolean = this eq that.asInstanceOf[AnyRef] + } + + val bottom: Elem = new ListSet[Definition]() { + override def equals(that: Any): Boolean = this eq that.asInstanceOf[AnyRef] + } + + def lub2(a: Elem, b: Elem): Elem = a incl b + } + + class ReachingDefinitionsAnalysis extends DataFlowAnalysis[rdefLattice.type] { + type P = BasicBlock + val lattice = rdefLattice + import lattice.Definition + import lattice.Elem + + var method: IMethod = _ + + val gen: Map[BasicBlock, Set[Definition]] = new HashMap() + val kill:Map[BasicBlock, Set[Local]] = new HashMap() + + def init(m: IMethod): Unit = { + this.method = m + gen.clear + kill.clear + + for (val b <- m.code.blocks.toList; + val (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._ + + def genAndKill(b: BasicBlock): (Set[Definition], Set[Local]) = { + var genSet: Set[Definition] = new HashSet + var killSet: Set[Local] = new HashSet + for (val (i, idx) <- b.toList.zipWithIndex) i match { + case STORE_LOCAL(local) => + killSet = killSet + local + genSet = updateReachingDefinition(b, idx, genSet) + case _ => () + } + (genSet, killSet) + } + + override def run: Unit = { + forwardAnalysis(blockTransfer) + 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?")); + } + } + + import opcodes._ + def updateReachingDefinition(b: BasicBlock, idx: Int, rd: Set[Definition]): Set[Definition] = { + val STORE_LOCAL(local) = b(idx) + var tmp = local + (rd filter { case (l, _, _) => l != tmp }) + (tmp, b, idx) + } + + private def blockTransfer(b: BasicBlock, in: Set[Definition]): Set[Definition] = + (in filter { case (l, _, _) => !kill(b)(l) }) incl gen(b) + + /** Return the reaching definitions corresponding to the point after idx. */ + def interpret(b: BasicBlock, idx: Int, in: lattice.Elem): Elem = { + var out = in + b(idx) match { + case STORE_LOCAL(l1) => + out = updateReachingDefinition(b, idx, out) + case _ => + () + } + + out + } + + override def toString: String = { + val sb = new compat.StringBuilder + sb.append("rdef: \n") + for (val b <- method.code.blocks) + sb.append("rdef_entry(" + b + ")= " + in(b)).append("\nrdef_exit(" + b + ")= " + out(b)) + sb.toString() + } + + } +} diff --git a/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala b/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala index 71ca0959bd..a5c78fdf41 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala @@ -658,7 +658,7 @@ abstract class GenJVM extends SubComponent { "\nCurrent block: " + b + "\nCurrent instruction: " + instr + "\n---------------------" + - dump(method) + method.dump } } def assert(cond: Boolean, msg: String) = if (!cond) throw new CompilationError(msg); @@ -1156,7 +1156,7 @@ abstract class GenJVM extends SubComponent { jcode.emitT2T(javaType(INT), javaType(kind)) } - case Comparison(op, kind) => (op, kind) match { + case Comparison(op, kind) => ((op, kind): @unsealed) match { case (CMP, LONG) => jcode.emitLCMP() case (CMPL, FLOAT) => jcode.emitFCMPL() case (CMPG, FLOAT) => jcode.emitFCMPG() @@ -1471,7 +1471,7 @@ abstract class GenJVM extends SubComponent { }}).reverse def assert(cond: Boolean, msg: String) = if (!cond) { - dump(method) + method.dump throw new Error(msg + "\nMethod: " + method) } diff --git a/src/compiler/scala/tools/nsc/backend/opt/ClosureElimination.scala b/src/compiler/scala/tools/nsc/backend/opt/ClosureElimination.scala index 8b7fa9a3f3..cf43b4f611 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 = "closurelimination"; + val phaseName = "closelim"; /** 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 index 152d33354e..329a2fe0bd 100644 --- a/src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala +++ b/src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala @@ -7,7 +7,8 @@ package scala.tools.nsc.backend.opt; -import scala.collection.mutable.{Map, HashMap}; +import scala.collection._ +import scala.collection.immutable.{Map, HashMap, Set, HashSet}; import scala.tools.nsc.backend.icode.analysis.LubError; import scala.tools.nsc.symtab._; @@ -18,7 +19,7 @@ abstract class DeadCodeElimination extends SubComponent { import icodes._; import icodes.opcodes._; - val phaseName = "deadcode"; + val phaseName = "dce"; /** Create a new phase */ override def newPhase(p: Phase) = new DeadCodeEliminationPhase(p); @@ -40,26 +41,77 @@ abstract class DeadCodeElimination extends SubComponent { class DeadCode { def analyzeClass(cls: IClass): Unit = cls.methods.foreach { m => - analyzeMethod(m); +// analyzeMethod(m); + collectRDef(m) } val a = new liveness.LivenessAnalysis(); + val rdef = new reachingDefinitions.ReachingDefinitionsAnalysis; + + /** Use-def chain: give the reaching definitions at the beginning of given instruction. */ + var defs: Map[(BasicBlock, Int), Set[rdef.lattice.Definition]] = HashMap.empty + + /** Useful instructions which have not been scanned yet. */ + val worklist: mutable.Set[(BasicBlock, Int)] = new mutable.HashSet + + /** collect reaching definitions and initial useful instructions for this method. */ + def collectRDef(m: IMethod): Unit = if (m.code ne null) { + log("rdef on " + m); + defs = HashMap.empty; worklist.clear + rdef.init(m); + rdef.run; + + for (val bb <- m.code.blocks.toList) { + var rd = rdef.in(bb); + Console.println("** Block " + bb + " **") + for (val Pair(i, idx) <- bb.toList.zipWithIndex) { + i match { + case LOAD_LOCAL(l) => defs((bb, idx)) = rd + case RETURN(_) => worklist += (bb, idx) + case CALL_METHOD(m, _) if isSideEffecting(m) => worklist += (bb, idx) + case _ => () + } + rd = rdef.interpret(bb, idx, rd); + } + } + } + + /** Mark useful instructions. Instructions in the worklist are each inspected and their + * dependecies are marked useful too, and added to the worklist. + */ + def mark { + while (!worklist.isEmpty) { + val (bb, idx) = worklist.elements.next + worklist -= (bb, idx) + + val instr = bb(idx) + assert(!instr.useful) + instr match { + case LOAD_LOCAL(l1) => + for (val (_, bb1, idx1) <- defs((bb, idx)); !bb1(idx1).useful) + worklist += (bb1, idx1) + case _ => + for (val (bb1, idx1) <- bb.findDefs(idx, 0); !bb1(idx1).useful) + worklist += (bb1, idx1) + } + } + } 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 (i, pos) <- bb.toList.zipWithIndex.reverse) { + for (val bb <- m.code.blocks.toList) { var live = a.out(bb); - - i match { - case STORE_LOCAL(l) if (!live(l)) => - removeDefUse(bb, i); - case _ => () + for (val Pair(i, pos) <- bb.toList.zipWithIndex.reverse) { + i match { + case STORE_LOCAL(l) if (!live(l)) => + removeDefUse(bb, i); + case _ => () + } + live = a.interpret(live, i); } - live = a.interpret(live, i); } } @@ -78,8 +130,8 @@ abstract class DeadCodeElimination extends SubComponent { if (definition.consumed == 0) { bb.removeInstructionsAt(defPos, usePos) } else { - bb.replaceInstruction(definition, definition.consumedTypes map DROP); bb.removeInstructionsAt(usePos); + bb.replaceInstruction(definition, definition.consumedTypes map DROP); } } case None => @@ -88,6 +140,11 @@ abstract class DeadCodeElimination extends SubComponent { } } + /** Is 'sym' a side-effecting method? TODO: proper analysis. */ + private def isSideEffecting(sym: Symbol): Boolean = { + sym.isClassConstructor // for testing only + } + def isSafeToRemove(i: Instruction): Boolean = i match { /* case LOAD_LOCAL(l) => true case LOAD_FIELD(_, _) => true diff --git a/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala b/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala index ea3442222e..31d648e129 100644 --- a/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala +++ b/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala @@ -7,7 +7,7 @@ package scala.tools.nsc.backend.opt; -import scala.collection.mutable.{Map, HashMap}; +import scala.collection.mutable.{Map, HashMap, Set, HashSet}; import scala.tools.nsc.symtab._; /** @@ -41,13 +41,18 @@ abstract class Inliners extends SubComponent { */ class Inliner { + val fresh = new HashMap[String, Int] + /* fresh name counter */ var count = 0; - def freshName(s: String) = { - val ret = s + this.count; - this.count = this.count + 1; - ret + def freshName(s: String) = fresh.get(s) match { + case Some(count) => + fresh(s) = count + 1 + s + count + case None => + fresh(s) = 1 + s + "0" } /** Inline the 'callee' method inside the 'caller' in the given @@ -69,7 +74,14 @@ abstract class Inliners extends SubComponent { /* Map 'original' blocks to the ones inlined in the caller. */ val inlinedBlock: Map[BasicBlock, BasicBlock] = new HashMap; - val instrBefore = block.toList.takeWhile( i => i ne instr); + val varsInScope: Set[Local] = new HashSet[Local] ++ block.varsInScope.elements + + val instrBefore = block.toList.takeWhile { + case i @ SCOPE_ENTER(l) => varsInScope += l + i ne instr + case i => + i ne instr + } val instrAfter = block.toList.drop(instrBefore.length + 1); assert(!instrAfter.isEmpty, "CALL_METHOD cannot be the last instrcution in block!"); @@ -90,6 +102,7 @@ abstract class Inliners extends SubComponent { activeHandlers.foreach (.addBlock(b)); if (retVal ne null) b.varsInScope += retVal b.varsInScope += inlinedThis + b.varsInScope ++= varsInScope b } @@ -240,6 +253,7 @@ abstract class Inliners extends SubComponent { def analyzeMethod(m: IMethod): Unit = try { var retry = false; var count = 0; + fresh.clear do { retry = false; @@ -295,14 +309,14 @@ abstract class Inliners extends SubComponent { info = tfa.interpret(info, i); }}}} } while (retry && count < 15); - normalize(m); + m.normalize } catch { case e => Console.println("############# Cought exception: " + e + " #################"); Console.println("\nMethod: " + m + "\nMethod owner: " + m.symbol.owner); e.printStackTrace(); - dump(m); + m.dump throw e; } diff --git a/src/compiler/scala/tools/nsc/symtab/classfile/ICodeReader.scala b/src/compiler/scala/tools/nsc/symtab/classfile/ICodeReader.scala index 5b521f12c8..c5f1e2115c 100644 --- a/src/compiler/scala/tools/nsc/symtab/classfile/ICodeReader.scala +++ b/src/compiler/scala/tools/nsc/symtab/classfile/ICodeReader.scala @@ -699,7 +699,7 @@ abstract class ICodeReader extends ClassfileParser { } } - icodes.dump(method) + method.dump tfa.init(method) tfa.run for (val bb <- linearizer.linearize(method)) { -- cgit v1.2.3