Merge pull request #2001 from JamesIry/2.10.x_SI-5313

SI-5313 Do not eliminate stores that potentially wipe referenes

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)