Merge pull request #2185 from JamesIry/master_unreachable

SI-7006 Prevent unreachable blocks in GenICode

4 files changed, 123 insertions, 39 deletions

diff --git a/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala b/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala
index 917fe8b292..d772dcb6c4 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala
@@ -17,7 +17,7 @@ trait BasicBlocks {
   self: ICodes =>
 
   import opcodes._
-  import global.{ settings, log, nme }
+  import global.{ settings, debuglog, log, nme }
   import nme.isExceptionResultName
 
   /** Override Array creation for efficiency (to not go through reflection). */
@@ -383,7 +383,6 @@ trait BasicBlocks {
     /** Close the block */
     def close() {
       assert(!closed || ignore, this)
-      assert(instructionList.nonEmpty, "Empty block: " + this)
       if (ignore && closed) { // redundant `ignore &&` for clarity -- we should never be in state `!ignore && closed`
         // not doing anything to this block is important...
         // because the else branch reverses innocent blocks, which is wrong when they're in ignore mode (and closed)
@@ -393,9 +392,38 @@ trait BasicBlocks {
         setFlag(DIRTYSUCCS)
         instructionList = instructionList.reverse
         instrs = instructionList.toArray
+        if (instructionList.isEmpty) {
+          debuglog(s"Removing empty block $this")
+          code removeBlock this
+        }
       }
     }
 
+    /**
+     * if cond is true, closes this block, entersIgnoreMode, and removes the block from
+     * its list of blocks. Used to allow a block to be started and then cancelled when it
+     * is discovered to be unreachable.
+     */
+    def killIf(cond: Boolean) {
+      if (!settings.YdisableUnreachablePrevention.value && cond) {
+        debuglog(s"Killing block $this")
+        assert(instructionList.isEmpty, s"Killing a non empty block $this")
+        // only checked under debug because fetching predecessor list is moderately expensive
+        if (settings.debug.value)
+          assert(predecessors.isEmpty, s"Killing block $this which is referred to from ${predecessors.mkString}")
+
+        close()
+        enterIgnoreMode()
+      }
+    }
+    
+    /**
+     * Same as killIf but with the logic of the condition reversed
+     */
+    def killUnless(cond: Boolean) {
+      this killIf !cond
+    }
+
     def open() {
       assert(closed, this)
       closed = false
diff --git a/src/compiler/scala/tools/nsc/backend/icode/GenICode.scala b/src/compiler/scala/tools/nsc/backend/icode/GenICode.scala
index ed458a4bbe..4f2d248672 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/GenICode.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/GenICode.scala
@@ -376,12 +376,14 @@ abstract class GenICode extends SubComponent  {
         "I produce UNIT in a context where " + expectedType + " is expected!")
 
       // alternatives may be already closed by a tail-recursive jump
+      val contReachable = !(thenCtx.bb.ignore && elseCtx.bb.ignore)
       thenCtx.bb.closeWith(JUMP(contCtx.bb))
       elseCtx.bb.closeWith(
           if (elsep == EmptyTree) JUMP(contCtx.bb)
           else JUMP(contCtx.bb) setPos tree.pos
         )
 
+      contCtx.bb killUnless contReachable
       (contCtx, resKind)
     }
     private def genLoadTry(tree: Try, ctx: Context, setGeneratedType: TypeKind => Unit): Context = {
@@ -477,7 +479,11 @@ abstract class GenICode extends SubComponent  {
       val resCtx: Context = tree match {
         case LabelDef(name, params, rhs) =>
           def genLoadLabelDef = {
-            val ctx1 = ctx.newBlock()
+            val ctx1 = ctx.newBlock() // note: we cannot kill ctx1 if ctx is in ignore mode because 
+                                      // label defs can be the target of jumps from other locations.
+                                      // that means label defs can lead to unreachable code without
+                                      // proper reachability analysis
+            
             if (nme.isLoopHeaderLabel(name))
               ctx1.bb.loopHeader = true
 
@@ -560,6 +566,7 @@ abstract class GenICode extends SubComponent  {
                   // the list, otherwise infinite recursion happens for
                   // finalizers that contain 'return'
                   val fctx = finalizerCtx.newBlock()
+                  fctx.bb killIf ctx1.bb.ignore
                   ctx1.bb.closeWith(JUMP(fctx.bb))
                   ctx1 = genLoad(f1, fctx, UNIT)
               }
@@ -949,6 +956,8 @@ abstract class GenICode extends SubComponent  {
             debuglog("Generating SWITCH statement.")
             val ctx1 = genLoad(selector, ctx, INT) // TODO: Java 7 allows strings in switches (so, don't assume INT and don't convert the literals using intValue)
             val afterCtx = ctx1.newBlock()
+            afterCtx.bb killIf ctx1.bb.ignore
+            var afterCtxReachable = false
             var caseCtx: Context  = null
             generatedType = toTypeKind(tree.tpe)
 
@@ -959,6 +968,7 @@ abstract class GenICode extends SubComponent  {
             for (caze @ CaseDef(pat, guard, body) <- cases) {
               assert(guard == EmptyTree, guard)
               val tmpCtx = ctx1.newBlock()
+              tmpCtx.bb killIf ctx1.bb.ignore
               pat match {
                 case Literal(value) =>
                   tags = value.intValue :: tags
@@ -980,12 +990,15 @@ abstract class GenICode extends SubComponent  {
               }
 
               caseCtx = genLoad(body, tmpCtx, generatedType)
+              afterCtxReachable ||= !caseCtx.bb.ignore
               // close the block unless it's already been closed by the body, which closes the block if it ends in a jump (which is emitted to have alternatives share their body)
               caseCtx.bb.closeWith(JUMP(afterCtx.bb) setPos caze.pos)
             }
+            afterCtxReachable ||= (default == afterCtx)
             ctx1.bb.emitOnly(
               SWITCH(tags.reverse map (x => List(x)), (default :: targets).reverse) setPos tree.pos
             )
+            afterCtx.bb killUnless afterCtxReachable
             afterCtx
           }
           genLoadMatch
@@ -1342,9 +1355,17 @@ abstract class GenICode extends SubComponent  {
     private def genCond(tree: Tree,
                         ctx: Context,
                         thenCtx: Context,
-                        elseCtx: Context): Unit =
-    {
-      def genComparisonOp(l: Tree, r: Tree, code: Int) {
+                        elseCtx: Context): Boolean =
+    {      
+      /**
+       * Generate the de-sugared comparison mechanism that will underly an '=='
+       * 
+       * @param l       left-hand side of the '=='
+       * @param r       right-hand side of the '=='
+       * @param code    the comparison operator to use
+       * @return true if either branch can continue normally to a follow on block, false otherwise
+       */
+      def genComparisonOp(l: Tree, r: Tree, code: Int): Boolean = {
         val op: TestOp = code match {
           case scalaPrimitives.LT => LT
           case scalaPrimitives.LE => LE
@@ -1360,27 +1381,33 @@ abstract class GenICode extends SubComponent  {
         lazy val nonNullSide = ifOneIsNull(l, r)
         if (isReferenceEqualityOp(code) && nonNullSide != null) {
           val ctx1 = genLoad(nonNullSide, ctx, ObjectReference)
+          val branchesReachable = !ctx1.bb.ignore
           ctx1.bb.emitOnly(
             CZJUMP(thenCtx.bb, elseCtx.bb, op, ObjectReference)
           )
+          branchesReachable
         }
         else {
           val kind = getMaxType(l.tpe :: r.tpe :: Nil)
           var ctx1 = genLoad(l, ctx, kind)
           ctx1 = genLoad(r, ctx1, kind)
+          val branchesReachable = !ctx1.bb.ignore
 
           ctx1.bb.emitOnly(
             CJUMP(thenCtx.bb, elseCtx.bb, op, kind) setPos r.pos
           )
+          branchesReachable
         }
       }
 
       debuglog("Entering genCond with tree: " + tree)
 
       // the default emission
-      def default() = {
+      def default(): Boolean = {
         val ctx1 = genLoad(tree, ctx, BOOL)
+        val branchesReachable = !ctx1.bb.ignore
         ctx1.bb.closeWith(CZJUMP(thenCtx.bb, elseCtx.bb, NE, BOOL) setPos tree.pos)
+        branchesReachable
       }
 
       tree match {
@@ -1392,11 +1419,12 @@ abstract class GenICode extends SubComponent  {
           lazy val Select(lhs, _) = fun
           lazy val rhs = args.head
 
-          def genZandOrZor(and: Boolean) = {
+          def genZandOrZor(and: Boolean): Boolean = {
             val ctxInterm = ctx.newBlock()
 
-            if (and) genCond(lhs, ctx, ctxInterm, elseCtx)
+            val branchesReachable = if (and) genCond(lhs, ctx, ctxInterm, elseCtx)
             else genCond(lhs, ctx, thenCtx, ctxInterm)
+            ctxInterm.bb killUnless branchesReachable
 
             genCond(rhs, ctxInterm, thenCtx, elseCtx)
           }
@@ -1435,8 +1463,9 @@ abstract class GenICode extends SubComponent  {
      * @param ctx     current context
      * @param thenCtx target context if the comparison yields true
      * @param elseCtx target context if the comparison yields false
+     * @return true if either branch can continue normally to a follow on block, false otherwise
      */
-    def genEqEqPrimitive(l: Tree, r: Tree, ctx: Context)(thenCtx: Context, elseCtx: Context): Unit = {
+    def genEqEqPrimitive(l: Tree, r: Tree, ctx: Context)(thenCtx: Context, elseCtx: Context): Boolean = {
       def getTempLocal = ctx.method.lookupLocal(nme.EQEQ_LOCAL_VAR) getOrElse {
         ctx.makeLocal(l.pos, AnyRefClass.tpe, nme.EQEQ_LOCAL_VAR.toString)
       }
@@ -1476,26 +1505,40 @@ abstract class GenICode extends SubComponent  {
 
         val ctx1 = genLoad(l, ctx, ObjectReference)
         val ctx2 = genLoad(r, ctx1, ObjectReference)
+        val branchesReachable = !ctx2.bb.ignore
         ctx2.bb.emitOnly(
           CALL_METHOD(equalsMethod, if (settings.optimise.value) Dynamic else Static(onInstance = false)),
           CZJUMP(thenCtx.bb, elseCtx.bb, NE, BOOL)
         )
+        branchesReachable
       }
       else {
-        if (isNull(l))
+        if (isNull(l)) {
           // null == expr -> expr eq null
-          genLoad(r, ctx, ObjectReference).bb emitOnly CZJUMP(thenCtx.bb, elseCtx.bb, EQ, ObjectReference)
-        else if (isNull(r)) {
+          val ctx1 = genLoad(r, ctx, ObjectReference)
+          val branchesReachable = !ctx1.bb.ignore
+          ctx1.bb emitOnly CZJUMP(thenCtx.bb, elseCtx.bb, EQ, ObjectReference)
+          branchesReachable
+        } else if (isNull(r)) {
           // expr == null -> expr eq null
-          genLoad(l, ctx, ObjectReference).bb emitOnly CZJUMP(thenCtx.bb, elseCtx.bb, EQ, ObjectReference)
+          val ctx1 = genLoad(l, ctx, ObjectReference)
+          val branchesReachable = !ctx1.bb.ignore
+          ctx1.bb emitOnly CZJUMP(thenCtx.bb, elseCtx.bb, EQ, ObjectReference)
+          branchesReachable
         } else {
           val eqEqTempLocal = getTempLocal
           var ctx1 = genLoad(l, ctx, ObjectReference)
-          lazy val nonNullCtx = ctx1.newBlock()
+          val branchesReachable = !ctx1.bb.ignore
+          lazy val nonNullCtx = {
+            val block = ctx1.newBlock()
+            block.bb killUnless branchesReachable
+            block
+          }
 
           // l == r -> if (l eq null) r eq null else l.equals(r)
           ctx1 = genLoad(r, ctx1, ObjectReference)
           val nullCtx = ctx1.newBlock()
+          nullCtx.bb killUnless branchesReachable
 
           ctx1.bb.emitOnly(
             STORE_LOCAL(eqEqTempLocal) setPos l.pos,
@@ -1512,6 +1555,7 @@ abstract class GenICode extends SubComponent  {
             CALL_METHOD(Object_equals, Dynamic),
             CZJUMP(thenCtx.bb, elseCtx.bb, NE, BOOL)
           )
+          branchesReachable
         }
       }
     }
@@ -1957,6 +2001,7 @@ abstract class GenICode extends SubComponent  {
         val outerCtx = this.dup       // context for generating exception handlers, covered by the catch-all finalizer
         val finalizerCtx = this.dup   // context for generating finalizer handler
         val normalExitCtx = outerCtx.newBlock() // context where flow will go on a "normal" (non-return, non-throw) exit from a try or catch handler
+        var normalExitReachable = false
         var tmp: Local = null
         val kind = toTypeKind(tree.tpe)
         val guardResult = kind != UNIT && mayCleanStack(finalizer)
@@ -1971,6 +2016,7 @@ abstract class GenICode extends SubComponent  {
 
         def emitFinalizer(ctx: Context): Context = if (!finalizer.isEmpty) {
           val ctx1 = finalizerCtx.dup.newBlock()
+          ctx1.bb killIf ctx.bb.ignore
           ctx.bb.closeWith(JUMP(ctx1.bb))
 
           if (guardResult) {
@@ -1986,32 +2032,38 @@ abstract class GenICode extends SubComponent  {
         // Generate the catch-all exception handler that deals with uncaught exceptions coming
         // from the try or exception handlers. It catches the exception, runs the finally code, then rethrows
         // the exception
-        if (finalizer != EmptyTree) {
-          val exh = outerCtx.newExceptionHandler(NoSymbol, finalizer.pos) // finalizer covers exception handlers
-          this.addActiveHandler(exh)  // .. and body aswell
-          val exhStartCtx = finalizerCtx.enterExceptionHandler(exh)
-          val exception = exhStartCtx.makeLocal(finalizer.pos, ThrowableClass.tpe, "exc")
-          loadException(exhStartCtx, exh, finalizer.pos)
-          exhStartCtx.bb.emit(STORE_LOCAL(exception))
-          val exhEndCtx = genLoad(finalizer, exhStartCtx, UNIT)
-          exhEndCtx.bb.emit(LOAD_LOCAL(exception))
-          exhEndCtx.bb.closeWith(THROW(ThrowableClass))
-          exhEndCtx.bb.enterIgnoreMode()
-          finalizerCtx.endHandler()
-        }
-
-        // Generate each exception handler
-        for ((sym, kind, handler) <- handlers) {
-          val exh = this.newExceptionHandler(sym, tree.pos)
-          val exhStartCtx = outerCtx.enterExceptionHandler(exh)
-          exhStartCtx.addFinalizer(finalizer, finalizerCtx)
-          loadException(exhStartCtx, exh, tree.pos)
-          val exhEndCtx = handler(exhStartCtx)
-          exhEndCtx.bb.closeWith(JUMP(normalExitCtx.bb))
-          outerCtx.endHandler()
+        if (settings.YdisableUnreachablePrevention.value || !outerCtx.bb.ignore) {
+          if (finalizer != EmptyTree) {
+            val exh = outerCtx.newExceptionHandler(NoSymbol, finalizer.pos) // finalizer covers exception handlers
+            this.addActiveHandler(exh)  // .. and body aswell
+            val exhStartCtx = finalizerCtx.enterExceptionHandler(exh)
+            exhStartCtx.bb killIf outerCtx.bb.ignore
+            val exception = exhStartCtx.makeLocal(finalizer.pos, ThrowableClass.tpe, "exc")
+            loadException(exhStartCtx, exh, finalizer.pos)
+            exhStartCtx.bb.emit(STORE_LOCAL(exception))
+            val exhEndCtx = genLoad(finalizer, exhStartCtx, UNIT)
+            exhEndCtx.bb.emit(LOAD_LOCAL(exception))
+            exhEndCtx.bb.closeWith(THROW(ThrowableClass))
+            exhEndCtx.bb.enterIgnoreMode()
+            finalizerCtx.endHandler()
+          }
+  
+          // Generate each exception handler
+          for ((sym, kind, handler) <- handlers) {
+            val exh = this.newExceptionHandler(sym, tree.pos)
+            val exhStartCtx = outerCtx.enterExceptionHandler(exh)
+            exhStartCtx.bb killIf outerCtx.bb.ignore
+            exhStartCtx.addFinalizer(finalizer, finalizerCtx)
+            loadException(exhStartCtx, exh, tree.pos)
+            val exhEndCtx = handler(exhStartCtx)
+            normalExitReachable ||= !exhEndCtx.bb.ignore
+            exhEndCtx.bb.closeWith(JUMP(normalExitCtx.bb))
+            outerCtx.endHandler()
+          }
         }
 
         val bodyCtx = this.newBlock()
+        bodyCtx.bb killIf outerCtx.bb.ignore
         if (finalizer != EmptyTree)
           bodyCtx.addFinalizer(finalizer, finalizerCtx)
 
@@ -2019,6 +2071,8 @@ abstract class GenICode extends SubComponent  {
 
         outerCtx.bb.closeWith(JUMP(bodyCtx.bb))
 
+        normalExitReachable ||= !bodyEndCtx.bb.ignore
+        normalExitCtx.bb killUnless normalExitReachable
         bodyEndCtx.bb.closeWith(JUMP(normalExitCtx.bb))
 
         emitFinalizer(normalExitCtx)
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/GenASM.scala b/src/compiler/scala/tools/nsc/backend/jvm/GenASM.scala
index 55e78df4b7..388efb4625 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/GenASM.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/GenASM.scala
@@ -3298,7 +3298,8 @@ abstract class GenASM extends SubComponent with BytecodeWriters with GenJVMASM {
     def normalize(m: IMethod) {
       if(!m.hasCode) { return }
       collapseJumpOnlyBlocks(m)
-      elimUnreachableBlocks(m)
+      if (settings.optimise.value)
+        elimUnreachableBlocks(m)
       icodes checkValid m
     }
 
diff --git a/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala b/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala
index 702071f906..2aee9bd4bc 100644
--- a/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala
+++ b/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala
@@ -173,6 +173,7 @@ trait ScalaSettings extends AbsScalaSettings
   val Yinvalidate     = StringSetting     ("-Yinvalidate", "classpath-entry", "Invalidate classpath entry before run", "")
   val noSelfCheck     = BooleanSetting    ("-Yno-self-type-checks", "Suppress check for self-type conformance among inherited members.")
   val YvirtClasses    = false // too embryonic to even expose as a -Y //BooleanSetting    ("-Yvirtual-classes", "Support virtual classes")
+  val YdisableUnreachablePrevention = BooleanSetting("-Ydisable-unreachable-prevention", "Disable the prevention of unreachable blocks in code generation.")
 
   val exposeEmptyPackage = BooleanSetting("-Yexpose-empty-package", "Internal only: expose the empty package.").internalOnly()