Merge pull request #4375 from AndyAyersMS/UseBudget

Inliner: use time budget to avoid excessive inlining

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;
             }