diff options
author | Grzegorz Kossakowski <grzegorz.kossakowski@gmail.com> | 2013-02-04 10:53:26 -0800 |
---|---|---|
committer | Grzegorz Kossakowski <grzegorz.kossakowski@gmail.com> | 2013-02-04 10:53:26 -0800 |
commit | 3d318be51f8e8cdec314565920327486212f5020 (patch) | |
tree | 93cd261e7435a9713e61b06aa55a5fdca8f0ae84 /src/compiler | |
parent | 8d25d05e9bf848d763e7b657d9c7e96ea5cb8daf (diff) | |
parent | 4fda83f8b02101a37871eadda9a13c70fd22bd2d (diff) | |
download | scala-3d318be51f8e8cdec314565920327486212f5020.tar.gz scala-3d318be51f8e8cdec314565920327486212f5020.tar.bz2 scala-3d318be51f8e8cdec314565920327486212f5020.zip |
Merge pull request #2001 from JamesIry/2.10.x_SI-5313
SI-5313 Do not eliminate stores that potentially wipe referenes
Diffstat (limited to 'src/compiler')
-rw-r--r-- | src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala | 122 |
1 files changed, 109 insertions, 13 deletions
diff --git a/src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala b/src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala index fee683ce3a..d4a6d18c60 100644 --- a/src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala +++ b/src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala @@ -18,6 +18,9 @@ abstract class DeadCodeElimination extends SubComponent { import icodes.opcodes._ import definitions.RuntimePackage + /** The block and index where an instruction is located */ + type InstrLoc = (BasicBlock, Int) + val phaseName = "dce" /** Create a new phase */ @@ -55,27 +58,35 @@ abstract class DeadCodeElimination extends SubComponent { val rdef = new reachingDefinitions.ReachingDefinitionsAnalysis; /** Use-def chain: give the reaching definitions at the beginning of given instruction. */ - var defs: immutable.Map[(BasicBlock, Int), immutable.Set[rdef.lattice.Definition]] = immutable.HashMap.empty + 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[(BasicBlock, Int)] = new mutable.LinkedHashSet + 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[(BasicBlock, Int), List[(BasicBlock, Int)]] = perRunCaches.newMap() + 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() accessedLocals = m.params.reverse m.code.blocks ++= linearizer.linearize(m) @@ -104,10 +115,10 @@ abstract class DeadCodeElimination extends SubComponent { for (Pair(i, idx) <- bb.toList.zipWithIndex) { i match { - case LOAD_LOCAL(l) => + case LOAD_LOCAL(_) => defs = defs + Pair(((bb, idx)), rd.vars) - case STORE_LOCAL(_) => + 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) @@ -125,6 +136,11 @@ abstract class DeadCodeElimination extends SubComponent { } } if (necessary) worklist += ((bb, idx)) + // 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(_) | @@ -162,11 +178,18 @@ abstract class DeadCodeElimination extends SubComponent { def mark() { // log("Starting with worklist: " + worklist) while (!worklist.isEmpty) { - val (bb, idx) = worklist.iterator.next + 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)) + } + if (!useful(bb)(idx)) { useful(bb) += idx dropOf.get(bb, idx) foreach { @@ -180,6 +203,15 @@ abstract class DeadCodeElimination extends SubComponent { 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) @@ -199,14 +231,72 @@ abstract class DeadCodeElimination extends SubComponent { () case _ => - for ((bb1, idx1) <- rdef.findDefs(bb, idx, instr.consumed) if !useful(bb1)(idx1)) { - debuglog("\tAdding " + bb1(idx1)) - worklist += ((bb1, idx1)) - } + 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) @@ -236,6 +326,12 @@ abstract class DeadCodeElimination extends SubComponent { 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("Skipped: bb_" + bb + ": " + idx + "( " + i + ")") @@ -247,8 +343,8 @@ abstract class DeadCodeElimination extends SubComponent { } } - private def computeCompensations(m: IMethod): mutable.Map[(BasicBlock, Int), List[Instruction]] = { - val compensations: mutable.Map[(BasicBlock, Int), List[Instruction]] = new mutable.HashMap + 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") @@ -287,7 +383,7 @@ abstract class DeadCodeElimination extends SubComponent { res } - private def findInstruction(bb: BasicBlock, i: Instruction): (BasicBlock, Int) = { + private def findInstruction(bb: BasicBlock, i: Instruction): InstrLoc = { for (b <- linearizer.linearizeAt(method, bb)) { val idx = b.toList indexWhere (_ eq i) if (idx != -1) |