From eab288442931f01b5bad2dcfa244a6183db0f4b6 Mon Sep 17 00:00:00 2001 From: James Iry Date: Wed, 23 Jan 2013 16:01:59 -0800 Subject: SI-5313 Do not eliminate stores that potentially wipe referenes Storing to local variables of reference or array type is indirectly observable because it potentially allows gc to collect an object. So this commit makes DeadCodeElimination mark a store necessary if it assigns to a local that potentially stored by a previous necessary store. --- test/files/run/t5313.check | 8 ++++++++ test/files/run/t5313.scala | 42 ++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 50 insertions(+) create mode 100644 test/files/run/t5313.check create mode 100644 test/files/run/t5313.scala (limited to 'test/files/run') diff --git a/test/files/run/t5313.check b/test/files/run/t5313.check new file mode 100644 index 0000000000..dd8791f109 --- /dev/null +++ b/test/files/run/t5313.check @@ -0,0 +1,8 @@ +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) diff --git a/test/files/run/t5313.scala b/test/files/run/t5313.scala new file mode 100644 index 0000000000..b65311622a --- /dev/null +++ b/test/files/run/t5313.scala @@ -0,0 +1,42 @@ +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 foo = true + 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 + 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(foo) { + val kept3 = kept2 + kept2 = null // this can't, because it clobbers x, which is ultimately 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 + } + 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") + } +} -- cgit v1.2.3 From 9b4fa8382fe0ed6fef3ff91e2c153a1840c954b9 Mon Sep 17 00:00:00 2001 From: James Iry Date: Tue, 29 Jan 2013 09:13:30 -0800 Subject: SI-5313 Eliminate more stores by replacing clobbers with null stores When an unused store clobbers a previous store, replace it with storing a null. Don't mark clobbers as "used" so that the original clobber and all following clobbers can still be eliminated. --- .../nsc/backend/opt/DeadCodeElimination.scala | 128 +++++++++++++-------- test/files/run/t5313.check | 2 + test/files/run/t5313.scala | 8 +- 3 files changed, 87 insertions(+), 51 deletions(-) (limited to 'test/files/run') 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 -- cgit v1.2.3 From c7d489e21f234bf1a2ea04c6b68990c53b5b387d Mon Sep 17 00:00:00 2001 From: James Iry Date: Sat, 2 Feb 2013 09:27:21 -0800 Subject: SI-5313 Test clobbers on the back edge of a loop I realized I was missing a test case for a local store early in a loop that was unused but turned out to be a clobber of a store later in the loop. --- test/files/run/t5313.check | 2 ++ test/files/run/t5313.scala | 10 ++++++++-- 2 files changed, 10 insertions(+), 2 deletions(-) (limited to 'test/files/run') diff --git a/test/files/run/t5313.check b/test/files/run/t5313.check index aa30c0efa5..7a48b2b711 100644 --- a/test/files/run/t5313.check +++ b/test/files/run/t5313.check @@ -8,3 +8,5 @@ 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 index 64009e29af..7da8726a1f 100644 --- a/test/files/run/t5313.scala +++ b/test/files/run/t5313.scala @@ -7,7 +7,7 @@ object Test extends IcodeTest { override def code = """class Foo { - def foo = true + def randomBoolean = util.Random.nextInt % 2 == 0 def bar = { var kept1 = new Object val result = new java.lang.ref.WeakReference(kept1) @@ -19,7 +19,7 @@ object Test extends IcodeTest { var erased4 = erased2 // and this val erased5 = erased4 // and this var kept2: Object = new Object // ultimately can't be eliminated - while(foo) { + while(randomBoolean) { val kept3 = kept2 kept2 = null // this can't, because it clobbers kept2, which is used erased4 = null // safe to eliminate @@ -36,6 +36,12 @@ object Test extends IcodeTest { 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 -- cgit v1.2.3