Inliner: use time budget to avoid excessive inlining

Use the time budget and time estimates to stop inlining once the
overall jit time increase estimate for the method is 10x the initial
jit time estimate.

This is implemented as part of `LegacyPolicy` and so can impact
the current inline behavior.

The budget is intentionally set quite high so that it only kicks in
for very rare cases where the call tree below the root is deep and wide
with many small methods. In extended testing on desktop this limit
fires in exactly two cases, both HFA tests.

In CoreCLR tests 12 of the HFA tests hit this limit. I've added
a directed test case here that came from the original bug report.

Closes #2472.

4 files changed, 107 insertions, 6 deletions

diff --git a/src/jit/inline.cpp b/src/jit/inline.cpp
index 188d21caf7..4477fd2d14 100644
--- a/src/jit/inline.cpp
+++ b/src/jit/inline.cpp
@@ -663,6 +663,9 @@ InlineStrategy::InlineStrategy(Compiler* compiler)
 //------------------------------------------------------------------------
 // GetRootContext: get the InlineContext for the root method
 //
+// Return Value:
+//    Root context; describes the method being jitted.
+//
 // Note:
 //    Also initializes the jit time estimate and budget.
 
@@ -698,26 +701,68 @@ void InlineStrategy::NoteCandidate()
 
 //------------------------------------------------------------------------
 // EstimateTime: estimate impact of this inline on the method jit time
+//
+// Arguments:
+//     context - context describing this inline
+//
+// Return Value:
+//    Nominal estimate of  jit time.
 
 int InlineStrategy::EstimateTime(InlineContext* context)
 {
-    unsigned ILSize = context->GetCodeSize();
-
     // Simple linear models based on observations
+    // show time is fairly well predicted by IL size.
+    unsigned ilSize = context->GetCodeSize();
 
+    // Prediction varies for root and inlines.
     if (context == m_RootContext)
     {
-        // Root method
-        return 60 + 3 * ILSize;
+        return EstimateRootTime(ilSize);
     }
     else
     {
-        // Inline
-        return -14 + 2 * ILSize;
+        return EstimateInlineTime(ilSize);
     }
 }
 
 //------------------------------------------------------------------------
+// EstimteRootTime: estimate jit time for method of this size with
+// no inlining.
+//
+// Arguments:
+//    ilSize - size of the method's IL
+//
+// Return Value:
+//    Nominal estimate of jit time.
+//
+// Notes:
+//    Based on observational data. Time is nominally microseconds.
+
+int InlineStrategy::EstimateRootTime(unsigned ilSize)
+{
+    return 60 + 3 * ilSize;
+}
+
+//------------------------------------------------------------------------
+// EstimteInlineTime: estimate time impact on jitting for an inline
+// of this size.
+//
+// Arguments:
+//    ilSize - size of the method's IL
+//
+// Return Value:
+//    Nominal increase in jit time.
+//
+// Notes:
+//    Based on observational data. Time is nominally microseconds.
+//    Small inlines will make the jit a bit faster.
+
+int InlineStrategy::EstimateInlineTime(unsigned ilSize)
+{
+    return -14 + 2 * ilSize;
+}
+
+//------------------------------------------------------------------------
 // NoteOutcome: do bookkeeping for an inline
 //
 // Arguments:
@@ -789,6 +834,22 @@ void InlineStrategy::NoteOutcome(InlineContext* context)
 }
 
 //------------------------------------------------------------------------
+// BudgetCheck: return true if as inline of this size would exceed the
+// jit time budget for this method
+//
+// Arguments:
+//     ilSize - size of the method's IL
+//
+// Return Value:
+//     true if the inline would go over budget
+
+bool InlineStrategy::BudgetCheck(unsigned ilSize)
+{
+    int timeDelta = EstimateInlineTime(ilSize);
+    return (timeDelta + m_CurrentTimeEstimate > m_CurrentTimeBudget);
+}
+
+//------------------------------------------------------------------------
 // NewRoot: construct an InlineContext for the root method
 //
 // Return Value:
diff --git a/src/jit/inline.def b/src/jit/inline.def
index 03979b116d..6684891726 100644
--- a/src/jit/inline.def
+++ b/src/jit/inline.def
@@ -138,6 +138,7 @@ INLINE_OBSERVATION(LDFLD_NEEDS_HELPER,        bool,   "ldfld needs helper",
 INLINE_OBSERVATION(LDVIRTFN_ON_NON_VIRTUAL,   bool,   "ldvirtfn on non-virtual",       FATAL,       CALLSITE)
 INLINE_OBSERVATION(NOT_CANDIDATE,             bool,   "not inline candidate",          FATAL,       CALLSITE)
 INLINE_OBSERVATION(NOT_PROFITABLE_INLINE,     bool,   "unprofitable inline",           FATAL,       CALLSITE)
+INLINE_OBSERVATION(OVER_BUDGET,               bool,   "inline exceeds budget",         FATAL,       CALLSITE)
 INLINE_OBSERVATION(OVER_INLINE_LIMIT,         bool,   "limited by JitInlineLimit",     FATAL,       CALLSITE)
 INLINE_OBSERVATION(RANDOM_REJECT,             bool,   "random reject",                 FATAL,       CALLSITE)
 INLINE_OBSERVATION(REQUIRES_SAME_THIS,        bool,   "requires same this",            FATAL,       CALLSITE)
diff --git a/src/jit/inline.h b/src/jit/inline.h
index 8dfed325b6..efc2db4586 100644
--- a/src/jit/inline.h
+++ b/src/jit/inline.h
@@ -660,6 +660,10 @@ public:
     // Inform strategy that there's a new inline candidate.
     void NoteCandidate();
 
+    // See if an inline of this size would fit within the current jit
+    // time budget.
+    bool BudgetCheck(unsigned ilSize);
+
 #if defined(DEBUG) || defined(INLINE_DATA)
 
     // Dump textual description of inlines done so far.
@@ -687,6 +691,10 @@ private:
     // Estimate the jit time change because of this inline.
     int EstimateTime(InlineContext* context);
 
+    // EstimateTime helpers
+    int EstimateRootTime(unsigned ilSize);
+    int EstimateInlineTime(unsigned ilSize);
+
 #if defined(DEBUG) || defined(INLINE_DATA)
     static bool    s_DumpDataHeader;
 #endif // defined(DEBUG) || defined(INLINE_DATA)
diff --git a/src/jit/inlinepolicy.cpp b/src/jit/inlinepolicy.cpp
index bc1385512a..d27a21caaa 100644
--- a/src/jit/inlinepolicy.cpp
+++ b/src/jit/inlinepolicy.cpp
@@ -321,6 +321,37 @@ void LegacyPolicy::NoteBool(InlineObservation obs, bool value)
                     m_MethodIsMostlyLoadStore = true;
                 }
 
+                // Budget check.
+                //
+                // Conceptually this should happen when we
+                // observe the candidate's IL size.
+                //
+                // However, we do this here to avoid potential
+                // inconsistency between the state of the budget
+                // during candidate scan and the state when the IL is
+                // being scanned.
+                //
+                // Consider the case where we're just below the budget
+                // during candidate scan, and we have three possible
+                // inlines, any two of which put us over budget. We
+                // allow them all to become candidates. We then move
+                // on to inlining and the first two get inlined and
+                // put us over budget. Now the third can't be inlined
+                // anymore, but we have a policy that when we replay
+                // the candidate IL size during the inlining pass it
+                // "reestablishes" candidacy rather than alters
+                // candidacy ... so instead we bail out here.
+
+                if (!m_IsPrejitRoot)
+                {
+                    InlineStrategy* strategy = m_RootCompiler->m_inlineStrategy;
+                    bool overBudget = strategy->BudgetCheck(m_CodeSize);
+                    if (overBudget)
+                    {
+                        SetFailure(InlineObservation::CALLSITE_OVER_BUDGET);
+                    }
+                }
+
                 break;
             }