diff options
| -rw-r--r-- | src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala | 128 | ||||
| -rw-r--r-- | test/files/run/t5313.check | 2 | ||||
| -rw-r--r-- | test/files/run/t5313.scala | 8 |
3 files changed, 87 insertions, 51 deletions
diff --git a/src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala b/src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala index 90d5686bd0..53270c0651 100644 --- a/src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala +++ b/src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala @@ -68,6 +68,9 @@ abstract class DeadCodeElimination extends SubComponent { /** 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]() + + /** Stores that clobber previous stores to array or ref locals. See SI-5313 */ + val clobbers = mutable.Set[(BasicBlock, Int)]() /** the current method. */ var method: IMethod = _ @@ -80,6 +83,7 @@ abstract class DeadCodeElimination extends SubComponent { 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) @@ -201,58 +205,15 @@ abstract class DeadCodeElimination extends SubComponent { worklist += ((bb1, idx1)) } - // Storing to local variables of reference or array type may be indirectly - // observable because 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 also go into the worklist to be marked useful. case STORE_LOCAL(l1) if l1.kind.isRefOrArrayType => addDefs() - // 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 starting at idx1 in bb1. - // if it finds any it adds them clobber to the worklist. - // If not it adds both bb's exception blocks and direct - // successor blocks to the uninspectedBlocks - def findClobber(idx1: Int, bb1: BasicBlock) { - val key = ((l1, 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 $instr") - if (!useful(bb1)(clobberIdx)) worklist += ((bb1, clobberIdx)) - true - } - } - - // if we found a clobber in this block then we don't need to add the successors - // because they'll be picked up when the worklist comes around to work on that clobber - if (!foundClobber) { - blocksToBeInspected ++= (bb1.exceptionSuccessors filterNot inspected) - 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 - findClobber(idx + 1, bb) - // then loop until we've exhausted the set of uninspected blocks - while(!blocksToBeInspected.isEmpty) { - val bb1 = blocksToBeInspected.head - blocksToBeInspected -= bb1 - inspected += bb1 - findClobber(0, bb1) - } - + // 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) @@ -277,6 +238,67 @@ abstract class DeadCodeElimination extends SubComponent { } } } + + /** + * 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) @@ -306,6 +328,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 + ")") diff --git a/test/files/run/t5313.check b/test/files/run/t5313.check index dd8791f109..aa30c0efa5 100644 --- a/test/files/run/t5313.check +++ b/test/files/run/t5313.check @@ -6,3 +6,5 @@ STORE_LOCAL(value kept3) STORE_LOCAL(variable kept2) STORE_LOCAL(variable kept4) STORE_LOCAL(variable kept4) +STORE_LOCAL(variable kept5) +STORE_LOCAL(variable kept5) diff --git a/test/files/run/t5313.scala b/test/files/run/t5313.scala index b65311622a..64009e29af 100644 --- a/test/files/run/t5313.scala +++ b/test/files/run/t5313.scala @@ -13,6 +13,7 @@ object Test extends IcodeTest { 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 @@ -20,7 +21,7 @@ object Test extends IcodeTest { var kept2: Object = new Object // ultimately can't be eliminated while(foo) { val kept3 = kept2 - kept2 = null // this can't, because it clobbers x, which is ultimately used + kept2 = null // this can't, because it clobbers kept2, which is used erased4 = null // safe to eliminate println(kept3) } @@ -30,6 +31,11 @@ object Test extends IcodeTest { 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 result } }""".stripMargin |