bringing down -Yinline time by 33%

After inlining one ore more callsites, Inliner runs anew a type-flow analysis for the same method, ie. the previous solution is discarded although it's a subset of that needed after the inlining(s). Background in: http://lamp.epfl.ch/~magarcia/ScalaCompilerCornerReloaded/2011Q4/Inliner.pdf

Instead, we invalidate only the fragment of the CFG affected by inlining (the basic block where inlining occurred and newly added basic blocks) and let the iterative dataflow analysis start from there. It reaches the fixpoint faster.

The inlining decisions thus made are exactly the same as with the slower version, see -Ylog:inliner, with a focus on lines starting with "[log inliner] Inlining"

review by @VladUreche @dragos @paulp

2 files changed, 88 insertions, 26 deletions

diff --git a/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala b/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala
index 937b0bdc3d..6421d6c8ef 100644
--- a/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala
+++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala
@@ -619,6 +619,50 @@ abstract class TypeFlowAnalysis {
 	}
   }
 
+  class MTFAGrowable extends MethodTFA {
+
+    import icodes._
+
+    /** discards what must be discarded, blanks what needs to be blanked out, and keeps the rest. */
+    def reinit(m: icodes.IMethod, staleOut: List[BasicBlock], inlined: collection.Set[BasicBlock], staleIn: collection.Set[BasicBlock]) {
+      if (this.method == null || this.method.symbol != m.symbol) {
+        init(m)
+        return
+      } else if(staleOut.isEmpty && inlined.isEmpty && staleIn.isEmpty) {
+        // this promotes invoking reinit if in doubt, no performance degradation will ensue!
+        return;
+      }
+
+      reinit {
+        // asserts conveying an idea what CFG shapes arrive here.
+        // staleIn foreach (p => assert( !in.isDefinedAt(p), p))
+        // staleIn foreach (p => assert(!out.isDefinedAt(p), p))
+        // inlined foreach (p => assert( !in.isDefinedAt(p), p))
+        // inlined foreach (p => assert(!out.isDefinedAt(p), p))
+        // inlined foreach (p => assert(!p.successors.isEmpty || p.lastInstruction.isInstanceOf[icodes.opcodes.THROW], p))
+        // staleOut foreach (p => assert(  in.isDefinedAt(p), p))
+
+        // never rewrite in(m.startBlock)
+        staleOut foreach { b =>
+          if(!inlined.contains(b)) { worklist += b }
+          out(b)    = typeFlowLattice.bottom
+        }
+        // nothing else is added to the worklist, bb's reachable via succs will be tfa'ed
+        blankOut(inlined)
+        blankOut(staleIn)
+        // no need to add startBlocks from m.exh
+      }
+    }
+
+    private def blankOut(blocks: collection.Set[BasicBlock]) {
+      blocks foreach { b =>
+        in(b)     = typeFlowLattice.bottom
+        out(b)    = typeFlowLattice.bottom
+      }
+    }
+
+  }
+
   class Timer {
     var millis = 0L
 
diff --git a/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala b/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala
index 88bbb16e34..3e8ef3f611 100644
--- a/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala
+++ b/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala
@@ -102,11 +102,21 @@ abstract class Inliners extends SubComponent {
         debuglog("Analyzing " + cls)
 
         this.currentIClazz = cls
-        cls.methods filterNot (_.symbol.isConstructor) foreach analyzeMethod
+        val ms = cls.methods filterNot { _.symbol.isConstructor }
+        ms foreach { im =>
+          if(hasInline(im.symbol)) {
+            log("Not inlining into " + im.symbol.originalName.decode + " because it is marked @inline.")
+          } else if(im.hasCode) {
+            analyzeMethod(im)
+          }
+        }
       }
 
-    val tfa   = new analysis.MethodTFA()
+    val tfa   = new analysis.MTFAGrowable()
     tfa.stat  = global.opt.printStats
+    val staleOut = new mutable.ListBuffer[BasicBlock]
+    val splicedBlocks = mutable.Set.empty[BasicBlock]
+    val staleIn  = mutable.Set.empty[BasicBlock]
 
     // how many times have we already inlined this method here?
     private val inlinedMethodCount = perRunCaches.newMap[Symbol, Int]() withDefaultValue 0
@@ -208,34 +218,35 @@ abstract class Inliners extends SubComponent {
       import scala.util.control.Breaks._
       do {
         retry = false
-        if (caller.inline) {
-          log("Not inlining into " + caller.sym.originalName.decode + " because it is marked @inline.")
-        }
-        else if (caller.m.hasCode) {
-          log("Analyzing " + m + " count " + count + " with " + caller.length + " blocks")
-          tfa init m
-          tfa.run
-          caller.m.linearizedBlocks() foreach { bb =>
-            info = tfa in bb
-
-            breakable {
-              for (i <- bb) {
-                i match {
-                  // Dynamic == normal invocations
-                  // Static(true) == calls to private members
-                  case CALL_METHOD(msym, Dynamic | Static(true)) if !msym.isConstructor =>
-                    if (analyzeInc(msym, i, bb))
-                      break
-                  case _ => ()
-                }
-                info = tfa.interpret(info, i)
+        log("Analyzing " + m + " count " + count + " with " + caller.length + " blocks")
+        tfa.reinit(m, staleOut.toList, splicedBlocks, staleIn)
+        tfa.run
+        staleOut.clear()
+        splicedBlocks.clear()
+        staleIn.clear()
+
+        caller.m.linearizedBlocks() foreach { bb =>
+          info = tfa in bb
+
+          breakable {
+            for (i <- bb) {
+              i match {
+                // Dynamic == normal invocations
+                // Static(true) == calls to private members
+                case CALL_METHOD(msym, Dynamic | Static(true)) if !msym.isConstructor =>
+                  if (analyzeInc(msym, i, bb)) {
+                    break
+                  }
+                case _ => ()
               }
+              info = tfa.interpret(info, i)
             }
           }
 
-          if (tfa.stat)
-            log(m.symbol.fullName + " iterations: " + tfa.iterations + " (size: " + caller.length + ")")
         }
+
+        if (tfa.stat)
+          log(m.symbol.fullName + " iterations: " + tfa.iterations + " (size: " + caller.length + ")")
       }
       while (retry && count < MAX_INLINE_RETRY)
 
@@ -343,6 +354,9 @@ abstract class Inliners extends SubComponent {
        *  The instruction must be a CALL_METHOD.
        */
       def doInline(block: BasicBlock, instr: Instruction) {
+
+        staleOut += block
+
         val targetPos = instr.pos
         log("Inlining " + inc.m + " in " + caller.m + " at pos: " + posToStr(targetPos))
 
@@ -478,7 +492,8 @@ abstract class Inliners extends SubComponent {
         block.close
 
         // duplicate the other blocks in the callee
-        inc.m.linearizedBlocks() foreach { bb => 
+        val calleeLin = inc.m.linearizedBlocks()
+        calleeLin foreach { bb =>
           var info = a in bb
           def emitInlined(i: Instruction) = inlinedBlock(bb).emit(i, targetPos)
           def emitDrops(toDrop: Int)      = info.stack.types drop toDrop foreach (t => emitInlined(DROP(t)))
@@ -503,6 +518,9 @@ abstract class Inliners extends SubComponent {
         afterBlock emit instrAfter
         afterBlock.close
 
+        staleIn        += afterBlock
+        splicedBlocks ++= (calleeLin map inlinedBlock)
+
         // add exception handlers of the callee
         caller addHandlers (inc.handlers map translateExh)
         assert(pending.isEmpty, "Pending NEW elements: " + pending)