Scala example source code file (DeadCodeElimination.scala)
The DeadCodeElimination.scala Scala example source code/* NSC -- new scala compiler
* Copyright 2005-2013 LAMP/EPFL
* @author Iulian Dragos
*/
package scala.tools.nsc
package backend.opt
import scala.collection.{ mutable, immutable }
/**
*/
abstract class DeadCodeElimination extends SubComponent {
import global._
import icodes._
import icodes.opcodes._
import definitions.RuntimePackage
/** The block and index where an instruction is located */
type InstrLoc = (BasicBlock, Int)
val phaseName = "dce"
override val enabled: Boolean = settings.Xdce
/** Create a new phase */
override def newPhase(p: Phase) = new DeadCodeEliminationPhase(p)
/** Dead code elimination phase.
*/
class DeadCodeEliminationPhase(prev: Phase) extends ICodePhase(prev) {
def name = phaseName
val dce = new DeadCode()
override def apply(c: IClass) {
if (settings.Xdce && (dce ne null))
dce.analyzeClass(c)
}
}
/** closures that are instantiated at least once, after dead code elimination */
val liveClosures = perRunCaches.newSet[Symbol]()
/** closures that are eliminated, populated by GenASM.AsmPhase.run()
* these class symbols won't have a .class physical file, thus shouldn't be included in InnerClasses JVM attribute,
* otherwise some tools get confused or slow (SI-6546)
* */
val elidedClosures = perRunCaches.newSet[Symbol]()
/** Remove dead code.
*/
class DeadCode {
def analyzeClass(cls: IClass) {
log(s"Analyzing ${cls.methods.size} methods in $cls.")
cls.methods.foreach { m =>
this.method = m
dieCodeDie(m)
global.closureElimination.peephole(m)
}
}
val rdef = new reachingDefinitions.ReachingDefinitionsAnalysis
/** Use-def chain: give the reaching definitions at the beginning of given instruction. */
var defs: immutable.Map[InstrLoc, immutable.Set[rdef.lattice.Definition]] = immutable.HashMap.empty
/** Useful instructions which have not been scanned yet. */
val worklist: mutable.Set[InstrLoc] = new mutable.LinkedHashSet
/** what instructions have been marked as useful? */
val useful: mutable.Map[BasicBlock, mutable.BitSet] = perRunCaches.newMap()
/** what local variables have been accessed at least once? */
var accessedLocals: List[Local] = Nil
/** Map from a local and a basic block to the instructions that store to that local in that basic block */
val localStores = mutable.Map[(Local, BasicBlock), mutable.BitSet]() withDefault {_ => mutable.BitSet()}
/** Stores that clobber previous stores to array or ref locals. See SI-5313 */
val clobbers = mutable.Set[InstrLoc]()
/** the current method. */
var method: IMethod = _
/** Map instructions who have a drop on some control path, to that DROP instruction. */
val dropOf: mutable.Map[InstrLoc, List[InstrLoc]] = perRunCaches.newMap()
def dieCodeDie(m: IMethod) {
if (m.hasCode) {
debuglog("dead code elimination on " + m)
dropOf.clear()
localStores.clear()
clobbers.clear()
m.code.blocks.clear()
m.code.touched = true
accessedLocals = m.params.reverse
m.code.blocks ++= linearizer.linearize(m)
m.code.touched = true
collectRDef(m)
mark()
sweep(m)
accessedLocals = accessedLocals.distinct
val diff = m.locals diff accessedLocals
if (diff.nonEmpty) {
val msg = diff.map(_.sym.name)mkString(", ")
log(s"Removed ${diff.size} dead locals: $msg")
m.locals = accessedLocals.reverse
}
}
}
/** collect reaching definitions and initial useful instructions for this method. */
def collectRDef(m: IMethod): Unit = if (m.hasCode) {
defs = immutable.HashMap.empty; worklist.clear(); useful.clear()
rdef.init(m)
rdef.run()
m foreachBlock { bb =>
useful(bb) = new mutable.BitSet(bb.size)
var rd = rdef.in(bb)
for ((i, idx) <- bb.toList.zipWithIndex) {
// utility for adding to worklist
def moveToWorkList() = moveToWorkListIf(cond = true)
// utility for (conditionally) adding to worklist
def moveToWorkListIf(cond: Boolean) =
if (cond) {
debuglog("in worklist: " + i)
worklist += ((bb, idx))
} else {
debuglog("not in worklist: " + i)
}
// instruction-specific logic
i match {
case LOAD_LOCAL(_) =>
defs = defs + (((bb, idx), rd.vars))
moveToWorkListIf(cond = false)
case STORE_LOCAL(l) =>
/* SI-4935 Check whether a module is stack top, if so mark the instruction that loaded it
* (otherwise any side-effects of the module's constructor go lost).
* (a) The other two cases where a module's value is stored (STORE_FIELD and STORE_ARRAY_ITEM)
* are already marked (case clause below).
* (b) A CALL_METHOD targeting a method `m1` where the receiver is potentially a module (case clause below)
* will have the module's load marked provided `isSideEffecting(m1)`.
* TODO check for purity (the ICode?) of the module's constructor (besides m1's purity).
* See also https://github.com/paulp/scala/blob/topic/purity-analysis/src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala
*/
val necessary = rdef.findDefs(bb, idx, 1) exists { p =>
val (bb1, idx1) = p
bb1(idx1) match {
case LOAD_MODULE(module) => isLoadNeeded(module)
case _ => false
}
}
moveToWorkListIf(necessary)
// add it to the localStores map
val key = (l, bb)
val set = localStores(key)
set += idx
localStores(key) = set
case RETURN(_) | JUMP(_) | CJUMP(_, _, _, _) | CZJUMP(_, _, _, _) | STORE_FIELD(_, _) |
THROW(_) | LOAD_ARRAY_ITEM(_) | STORE_ARRAY_ITEM(_) | SCOPE_ENTER(_) | SCOPE_EXIT(_) | STORE_THIS(_) |
LOAD_EXCEPTION(_) | SWITCH(_, _) | MONITOR_ENTER() | MONITOR_EXIT() | CHECK_CAST(_) =>
moveToWorkList()
case CALL_METHOD(m1, _) if isSideEffecting(m1) =>
moveToWorkList()
case CALL_METHOD(m1, SuperCall(_)) =>
moveToWorkList() // super calls to constructor
case DROP(_) =>
val necessary = rdef.findDefs(bb, idx, 1) exists { p =>
val (bb1, idx1) = p
bb1(idx1) match {
case CALL_METHOD(m1, _) if isSideEffecting(m1) => true
case LOAD_EXCEPTION(_) | DUP(_) | LOAD_MODULE(_) => true
case _ =>
dropOf((bb1, idx1)) = (bb,idx) :: dropOf.getOrElse((bb1, idx1), Nil)
debuglog("DROP is innessential: " + i + " because of: " + bb1(idx1) + " at " + bb1 + ":" + idx1)
false
}
}
moveToWorkListIf(necessary)
case LOAD_MODULE(sym) if isLoadNeeded(sym) =>
moveToWorkList() // SI-4859 Module initialization might side-effect.
case _ => ()
moveToWorkListIf(cond = false)
}
rd = rdef.interpret(bb, idx, rd)
}
}
}
private def isLoadNeeded(module: Symbol): Boolean = {
module.info.member(nme.CONSTRUCTOR).filter(isSideEffecting) != NoSymbol
}
/** Mark useful instructions. Instructions in the worklist are each inspected and their
* dependencies are marked useful too, and added to the worklist.
*/
def mark() {
// log("Starting with worklist: " + worklist)
while (!worklist.isEmpty) {
val (bb, idx) = worklist.head
worklist -= ((bb, idx))
debuglog("Marking instr: \tBB_" + bb + ": " + idx + " " + bb(idx))
val instr = bb(idx)
// adds the instrutions that define the stack values about to be consumed to the work list to
// be marked useful
def addDefs() = for ((bb1, idx1) <- rdef.findDefs(bb, idx, instr.consumed) if !useful(bb1)(idx1)) {
debuglog(s"\t${bb1(idx1)} is consumed by $instr")
worklist += ((bb1, idx1))
}
// DROP logic -- if an instruction is useful, its drops are also useful
// and we don't mark the DROPs as useful directly but add them to the
// worklist so we also mark their reaching defs as useful - see SI-7060
if (!useful(bb)(idx)) {
useful(bb) += idx
dropOf.get((bb, idx)) foreach {
for ((bb1, idx1) <- _) {
/*
* SI-7060: A drop that we now mark as useful can be reached via several paths,
* so we should follow by marking all its reaching definition as useful too:
*/
debuglog("\tAdding: " + bb1(idx1) + " to the worklist, as a useful DROP.")
worklist += ((bb1, idx1))
}
}
// per-instruction logic
instr match {
case LOAD_LOCAL(l1) =>
for ((l2, bb1, idx1) <- defs((bb, idx)) if l1 == l2; if !useful(bb1)(idx1)) {
debuglog("\tAdding " + bb1(idx1))
worklist += ((bb1, idx1))
}
case STORE_LOCAL(l1) if l1.kind.isRefOrArrayType =>
addDefs()
// see SI-5313
// search for clobbers of this store if we aren't doing l1 = null
// this doesn't catch the second store in x=null;l1=x; but in practice this catches
// a lot of null stores very cheaply
if (idx == 0 || bb(idx - 1) != CONSTANT(Constant(null)))
findClobbers(l1, bb, idx + 1)
case nw @ NEW(REFERENCE(sym)) =>
assert(nw.init ne null, "null new.init at: " + bb + ": " + idx + "(" + instr + ")")
worklist += findInstruction(bb, nw.init)
if (inliner.isClosureClass(sym)) {
liveClosures += sym
}
// it may be better to move static initializers from closures to
// the enclosing class, to allow the optimizer to remove more closures.
// right now, the only static fields in closures are created when caching
// 'symbol literals.
case LOAD_FIELD(sym, true) if inliner.isClosureClass(sym.owner) =>
log("added closure class for field " + sym)
liveClosures += sym.owner
case LOAD_EXCEPTION(_) =>
()
case _ =>
addDefs()
}
}
}
}
/**
* Finds and marks all clobbers of the given local starting in the given
* basic block at the given index
*
* Storing to local variables of reference or array type may be indirectly
* observable because it may remove a reference to an object which may allow the object
* to be gc'd. See SI-5313. In this code I call the LOCAL_STORE(s) that immediately follow a
* LOCAL_STORE and that store to the same local "clobbers." If a LOCAL_STORE is marked
* useful then its clobbers must go into the set of clobbers, which will be
* compensated for later
*/
def findClobbers(l: Local, bb: BasicBlock, idx: Int) {
// previously visited blocks tracked to prevent searching forever in a cycle
val inspected = mutable.Set[BasicBlock]()
// our worklist of blocks that still need to be checked
val blocksToBeInspected = mutable.Set[BasicBlock]()
// Tries to find the next clobber of l1 in bb1 starting at idx1.
// if it finds one it adds the clobber to clobbers set for later
// handling. If not it adds the direct successor blocks to
// the uninspectedBlocks to try to find clobbers there. Either way
// it adds the exception successor blocks for further search
def findClobberInBlock(idx1: Int, bb1: BasicBlock) {
val key = ((l, bb1))
val foundClobber = (localStores contains key) && {
def minIdx(s : mutable.BitSet) = if(s.isEmpty) -1 else s.min
// find the smallest index greater than or equal to idx1
val clobberIdx = minIdx(localStores(key) dropWhile (_ < idx1))
if (clobberIdx == -1)
false
else {
debuglog(s"\t${bb1(clobberIdx)} is a clobber of ${bb(idx)}")
clobbers += ((bb1, clobberIdx))
true
}
}
// always need to look into the exception successors for additional clobbers
// because we don't know when flow might enter an exception handler
blocksToBeInspected ++= (bb1.exceptionSuccessors filterNot inspected)
// If we didn't find a clobber here then we need to look at successor blocks.
// if we found a clobber then we don't need to search in the direct successors
if (!foundClobber) {
blocksToBeInspected ++= (bb1.directSuccessors filterNot inspected)
}
}
// first search starting at the current index
// note we don't put bb in the inspected list yet because a loop may later force
// us back around to search from the beginning of bb
findClobberInBlock(idx, bb)
// then loop until we've exhausted the set of uninspected blocks
while(!blocksToBeInspected.isEmpty) {
val bb1 = blocksToBeInspected.head
blocksToBeInspected -= bb1
inspected += bb1
findClobberInBlock(0, bb1)
}
}
def sweep(m: IMethod) {
val compensations = computeCompensations(m)
debuglog("Sweeping: " + m)
m foreachBlock { bb =>
debuglog(bb + ":")
val oldInstr = bb.toList
bb.open()
bb.clear()
for ((i, idx) <- oldInstr.zipWithIndex) {
if (useful(bb)(idx)) {
debuglog(" * " + i + " is useful")
bb.emit(i, i.pos)
compensations.get((bb, idx)) match {
case Some(is) => is foreach bb.emit
case None => ()
}
// check for accessed locals
i match {
case LOAD_LOCAL(l) if !l.arg =>
accessedLocals = l :: accessedLocals
case STORE_LOCAL(l) if !l.arg =>
accessedLocals = l :: accessedLocals
case _ => ()
}
} else {
i match {
case NEW(REFERENCE(sym)) =>
log(s"Eliminated instantation of $sym inside $m")
case STORE_LOCAL(l) if clobbers contains ((bb, idx)) =>
// if an unused instruction was a clobber of a used store to a reference or array type
// then we'll replace it with the store of a null to make sure the reference is
// eliminated. See SI-5313
bb emit CONSTANT(Constant(null))
bb emit STORE_LOCAL(l)
case _ => ()
}
debuglog(" " + i + " [swept]")
}
}
if (bb.nonEmpty) bb.close()
else log(s"empty block encountered in $m")
}
}
private def computeCompensations(m: IMethod): mutable.Map[InstrLoc, List[Instruction]] = {
val compensations: mutable.Map[InstrLoc, List[Instruction]] = new mutable.HashMap
m foreachBlock { bb =>
assert(bb.closed, "Open block in computeCompensations")
foreachWithIndex(bb.toList) { (i, idx) =>
if (!useful(bb)(idx)) {
foreachWithIndex(i.consumedTypes.reverse) { (consumedType, depth) =>
debuglog("Finding definitions of: " + i + "\n\t" + consumedType + " at depth: " + depth)
val defs = rdef.findDefs(bb, idx, 1, depth)
for (d <- defs) {
val (bb, idx) = d
debuglog("rdef: "+ bb(idx))
bb(idx) match {
case DUP(_) if idx > 0 =>
bb(idx - 1) match {
case nw @ NEW(_) =>
val init = findInstruction(bb, nw.init)
log("Moving DROP to after <init> call: " + nw.init)
compensations(init) = List(DROP(consumedType))
case _ =>
compensations(d) = List(DROP(consumedType))
}
case _ =>
compensations(d) = List(DROP(consumedType))
}
}
}
}
}
}
compensations
}
private def findInstruction(bb: BasicBlock, i: Instruction): InstrLoc = {
for (b <- linearizer.linearizeAt(method, bb)) {
val idx = b.toList indexWhere (_ eq i)
if (idx != -1)
return (b, idx)
}
abort("could not find init in: " + method)
}
private def isPure(sym: Symbol) = (
(sym.isGetter && sym.isEffectivelyFinalOrNotOverridden && !sym.isLazy)
|| (sym.isPrimaryConstructor && (sym.enclosingPackage == RuntimePackage || inliner.isClosureClass(sym.owner)))
)
/** Is 'sym' a side-effecting method? TODO: proper analysis. */
private def isSideEffecting(sym: Symbol) = !isPure(sym)
} /* DeadCode */
}
Other Scala source code examplesHere is a short list of links related to this Scala DeadCodeElimination.scala source code file: |
The search page
Other Scala source code examples at this package level
Click here to learn more about this project
