diff options
| -rw-r--r-- | src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala | 122 | ||||
| -rw-r--r-- | test/files/run/t5313.check | 12 | ||||
| -rw-r--r-- | test/files/run/t5313.scala | 54 |
3 files changed, 175 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) diff --git a/test/files/run/t5313.check b/test/files/run/t5313.check new file mode 100644 index 0000000000..7a48b2b711 --- /dev/null +++ b/test/files/run/t5313.check @@ -0,0 +1,12 @@ +STORE_LOCAL(variable kept1) +STORE_LOCAL(value result) +STORE_LOCAL(variable kept1) +STORE_LOCAL(variable kept2) +STORE_LOCAL(value kept3) +STORE_LOCAL(variable kept2) +STORE_LOCAL(variable kept4) +STORE_LOCAL(variable kept4) +STORE_LOCAL(variable kept5) +STORE_LOCAL(variable kept5) +STORE_LOCAL(variable kept6) +STORE_LOCAL(variable kept6) diff --git a/test/files/run/t5313.scala b/test/files/run/t5313.scala new file mode 100644 index 0000000000..7da8726a1f --- /dev/null +++ b/test/files/run/t5313.scala @@ -0,0 +1,54 @@ +import scala.tools.partest.IcodeTest + +object Test extends IcodeTest { + override def printIcodeAfterPhase = "dce" + + override def extraSettings: String = super.extraSettings + " -optimize" + + override def code = + """class Foo { + def randomBoolean = util.Random.nextInt % 2 == 0 + def bar = { + var kept1 = new Object + val result = new java.lang.ref.WeakReference(kept1) + kept1 = null // we can't eliminate this assigment because result can observe + // when the object has no more references. See SI-5313 + kept1 = new Object // but we can eliminate this one because kept1 has already been clobbered + var erased2 = null // we can eliminate this store because it's never used + val erased3 = erased2 // and this + var erased4 = erased2 // and this + val erased5 = erased4 // and this + var kept2: Object = new Object // ultimately can't be eliminated + while(randomBoolean) { + val kept3 = kept2 + kept2 = null // this can't, because it clobbers kept2, which is used + erased4 = null // safe to eliminate + println(kept3) + } + var kept4 = new Object // have to keep, it's used + try + println(kept4) + catch { + case _ : Throwable => kept4 = null // have to keep, it clobbers kept4 which is used + } + var kept5 = new Object + print(kept5) + kept5 = null // can't eliminate it's a clobber and it's used + print(kept5) + kept5 = null // can eliminate because we don't care about clobbers of nulls + while(randomBoolean) { + var kept6: AnyRef = null // not used, but have to keep because it clobbers the next used store + // on the back edge of the loop + kept6 = new Object // used + println(kept6) + } + result + } + }""".stripMargin + + override def show() { + val storeLocal = "STORE_LOCAL" + val lines1 = collectIcode("") filter (_ contains storeLocal) map (x => x.drop(x.indexOf(storeLocal))) + println(lines1 mkString "\n") + } +} |