InlineRefactoring: start to capture failures in the inline tree

This change starts capturing information about failed inlines in the
inline tree. Not all failures are captured yet; see below for notes.

Sample trees showing a failure:
```
Inlines into Secant:Inner(byref,byref,double,double,int,byref)
  [IL=0004 TR=000008] [FAILED: exceeds profit threshold] Secant:FF(double):double
  [IL=0023 TR=000036] [native size estimate ok] Secant:FF(double):double
```

InlineContext is revised to have 3 static constructors: one for the
root context, one for successful inlines, and one for failed inlines.
Successful inlines are always captured in the tree, since they are used
to track inline depth and recursion. Failures are only captured in
DEBUG and are just there for diagnostic purposes. The success and
failure constructors also link the new contexts into the tree at the
proper spot.

With this the jit can now capture failures for calls that were
initially identified as candidates. Top-level non-candidates are still
screened out in fgInline, and lower-level non-candidates simply aren't
seen at all by the current code. This will be addressed in a subsequent
change.

New calls can appear in the gap between caller and callee, as the code
for the two is stitched together. These are never candidates and never
given candidate screening. For now, if a new failing context is unable
to find a parent context from the IR, the code assumes the IR was
created in this gap. Down the road we may want to insist that all IR be
covered by some InlineContext (eg for improved debugging of optimized
code).

The InlineContext now also captures and prints the tree ID of the call
to make it easier to relate back to IR dumps.

6 files changed, 267 insertions, 88 deletions

diff --git a/src/jit/flowgraph.cpp b/src/jit/flowgraph.cpp
index 001349aa0d..a8282cacca 100644
--- a/src/jit/flowgraph.cpp
+++ b/src/jit/flowgraph.cpp
@@ -21325,11 +21325,11 @@ bool          Compiler::fgIsUnboundedInlineRecursion(InlineContext*          inl
     DWORD depth = 0;
     bool result = false;
 
-    for (; inlineContext != nullptr; inlineContext = inlineContext->inlParent)
+    for (; inlineContext != nullptr; inlineContext = inlineContext->getParent())
     {
         // Hard limit just to catch pathological cases
         depth++;
-        if  ((inlineContext->inlCode == ilCode) || (depth > MAX_INLINING_RECURSION_DEPTH))
+        if  ((inlineContext->getCode() == ilCode) || (depth > MAX_INLINING_RECURSION_DEPTH))
         {
            result = true;
            break;
@@ -21360,11 +21360,7 @@ void                Compiler::fgInline()
     noway_assert(block != nullptr);
 
     // Set the root inline context on all statements
-    InlineContext* rootContext = new (this, CMK_Inlining) InlineContext;
-
-#if defined(DEBUG)
-    rootContext->inlCallee = info.compMethodHnd;
-#endif
+    InlineContext* rootContext = InlineContext::newRoot(this);
 
     for (; block != nullptr; block = block->bbNext)
     {
@@ -21394,7 +21390,7 @@ void                Compiler::fgInline()
         {
             expr = stmt->gtStmtExpr;
 
-            // See if we can expand the inline candidate.
+            // See if we can expand the inline candidate
             if ((expr->gtOper == GT_CALL) && ((expr->gtFlags & GTF_CALL_INLINE_CANDIDATE) != 0))
             {
                 fgMorphStmt = stmt;
@@ -21924,11 +21920,10 @@ void       Compiler::fgInvokeInlineeCompiler(GenTreeCall*  call,
 
     if (verbose || fgPrintInlinedMethods)
     {
-        printf("Successfully inlined %s (%d IL bytes) (depth %d) into %s [%s]\n",
+        printf("Successfully inlined %s (%d IL bytes) (depth %d) [%s]\n",
                eeGetMethodFullName(fncHandle),
                inlineCandidateInfo->methInfo.ILCodeSize,
                inlineDepth,
-               info.compFullName,
                inlineResult->reasonString());
     }
 
@@ -21991,24 +21986,9 @@ void Compiler::fgInsertInlineeBlocks(InlineInfo* pInlineInfo)
 #endif // defined(DEBUG) || MEASURE_INLINING
 
     //
-    // Obtain the current InlineContext and link in a new child for the callee
+    // Create a new inline context and mark the inlined statements with it
     //
-    InlineContext* calleeContext = new (this, CMK_Inlining) InlineContext;
-    InlineContext* parentContext = iciStmt->gtStmt.gtInlineContext;
-    noway_assert(parentContext != nullptr);
-    BYTE* calleeIL = pInlineInfo->inlineCandidateInfo->methInfo.ILCode;
-    calleeContext->inlCode = calleeIL;
-    calleeContext->inlParent = parentContext;
-    // Push on front here will put siblings in reverse lexical
-    // order which we undo in the dumper
-    calleeContext->inlSibling = parentContext->inlChild;
-    parentContext->inlChild = calleeContext;
-    calleeContext->inlChild = nullptr;
-    calleeContext->inlOffset = iciStmt->AsStmt()->gtStmtILoffsx;
-    calleeContext->inlObservation = pInlineInfo->inlineResult->getObservation();
-#ifdef DEBUG
-    calleeContext->inlCallee = pInlineInfo->fncHandle;
-#endif
+    InlineContext* calleeContext = InlineContext::newSuccess(this, pInlineInfo);
 
     for (block = InlineeCompiler->fgFirstBB;
          block != nullptr;
diff --git a/src/jit/gentree.h b/src/jit/gentree.h
index b452f67eb3..08cc26473f 100644
--- a/src/jit/gentree.h
+++ b/src/jit/gentree.h
@@ -3171,7 +3171,7 @@ struct GenTreeRetExpr: public GenTree
 
 /* gtStmt   -- 'statement expr' (GT_STMT) */
 
-struct InlineContext;
+class InlineContext;
 
 struct GenTreeStmt: public GenTree
 {
diff --git a/src/jit/inline.cpp b/src/jit/inline.cpp
index 7988f628a0..8733ee8cf6 100644
--- a/src/jit/inline.cpp
+++ b/src/jit/inline.cpp
@@ -152,13 +152,8 @@ const char* inlGetImpactString(InlineObservation obs)
     }
 }
 
-
 //------------------------------------------------------------------------
-// InlieContext: default constructor
-//
-// Notes: use for the root instance. We set inlCode to nullptr here
-// (rather than the IL buffer address of the root method) to preserve
-// existing behavior, which is to allow one recursive inline.
+// InlineContext: default constructor
 
 InlineContext::InlineContext()
     : inlParent(nullptr)
@@ -169,14 +164,135 @@ InlineContext::InlineContext()
     , inlObservation(InlineObservation::CALLEE_UNUSED_INITIAL)
 #ifdef DEBUG
     , inlCallee(nullptr)
+    , inlTreeID(0)
+    , inlSuccess(true)
 #endif
 {
     // Empty
 }
 
+//------------------------------------------------------------------------
+// newRoot: construct an InlineContext for the root method
+//
+// Arguments:
+//   compiler - compiler doing the inlining
+//
+// Return Value:
+//    InlineContext for use as the root context
+//
+// Notes:
+//    We leave inlCode as nullptr here (rather than the IL buffer
+//    address of the root method) to preserve existing behavior, which
+//    is to allow one recursive inline.
+
+InlineContext* InlineContext::newRoot(Compiler* compiler)
+{
+    InlineContext* rootContext = new (compiler, CMK_Inlining) InlineContext;
+
+#if defined(DEBUG)
+    rootContext->inlCallee = compiler->info.compMethodHnd;
+#endif
+
+    return rootContext;
+}
+
+//------------------------------------------------------------------------
+// newSuccess: construct an InlineContext for a successful inline
+// and link it into the context tree
+//
+// Arguments:
+//    compiler   - compiler doing the inlining
+//    stmt       - statement containing call being inlined
+//    inlineInfo - information about this inline
+//
+// Return Value:
+//    A new InlineContext for statements brought into the method by
+//    this inline.
+
+InlineContext* InlineContext::newSuccess(Compiler*   compiler,
+                                         InlineInfo* inlineInfo)
+{
+    InlineContext* calleeContext = new (compiler, CMK_Inlining) InlineContext;
+
+    GenTree*       stmt          = inlineInfo->iciStmt;
+    BYTE*          calleeIL      = inlineInfo->inlineCandidateInfo->methInfo.ILCode;
+    InlineContext* parentContext = stmt->gtStmt.gtInlineContext;
+
+    noway_assert(parentContext != nullptr);
+
+    calleeContext->inlCode = calleeIL;
+    calleeContext->inlParent = parentContext;
+    // Push on front here will put siblings in reverse lexical
+    // order which we undo in the dumper
+    calleeContext->inlSibling = parentContext->inlChild;
+    parentContext->inlChild = calleeContext;
+    calleeContext->inlChild = nullptr;
+    calleeContext->inlOffset = stmt->AsStmt()->gtStmtILoffsx;
+    calleeContext->inlObservation = inlineInfo->inlineResult->getObservation();
+#ifdef DEBUG
+    calleeContext->inlCallee = inlineInfo->fncHandle;
+    calleeContext->inlTreeID = inlineInfo->inlineResult->getCall()->gtTreeID;
+#endif
+
+    return calleeContext;
+}
+
 #ifdef DEBUG
 
 //------------------------------------------------------------------------
+// newFailure: construct an InlineContext for a failing inline
+// and link it into the context tree
+//
+// Arguments:
+//    compiler     - compiler doing the inlining
+//    stmt         - statement containing the attempted inline
+//    inlineResult - inlineResult for the attempt
+//
+// Return Value:
+//
+//    A new InlineContext for diagnostic purposes, or nullptr if
+//    the desired context could not be created.
+
+InlineContext* InlineContext::newFailure(Compiler*     compiler,
+                                         GenTree*      stmt,
+                                         InlineResult* inlineResult)
+{
+    // Check for a parent context first. We may insert new statements
+    // between the caller and callee that do not pick up either's
+    // context, and these statements may have calls that we later
+    // examine and fail to inline.
+    //
+    // See fgInlinePrependStatements for examples.
+
+    InlineContext* parentContext = stmt->gtStmt.gtInlineContext;
+
+    if (parentContext == nullptr)
+    {
+        // Assume for now this is a failure to inline a call in a
+        // statement inserted between caller and callee. Just ignore
+        // it for the time being.
+
+        return nullptr;
+    }
+
+    InlineContext* failedContext = new (compiler, CMK_Inlining) InlineContext;
+
+    failedContext->inlParent = parentContext;
+    // Push on front here will put siblings in reverse lexical
+    // order which we undo in the dumper
+    failedContext->inlSibling = parentContext->inlChild;
+    parentContext->inlChild = failedContext;
+    failedContext->inlChild = nullptr;
+    failedContext->inlOffset = stmt->AsStmt()->gtStmtILoffsx;
+    failedContext->inlObservation = inlineResult->getObservation();
+    failedContext->inlCallee = inlineResult->getCallee();
+    failedContext->inlSuccess = false;
+    failedContext->inlTreeID = inlineResult->getCall()->gtTreeID;
+
+    return failedContext;
+}
+
+//------------------------------------------------------------------------
 // Dump: Dump an InlineContext entry and all descendants to stdout
 //
 // Arguments:
@@ -191,7 +307,18 @@ void InlineContext::Dump(Compiler* compiler, int indent)
         inlSibling->Dump(compiler, indent);
     }
 
-    const char* calleeName = compiler->eeGetMethodFullName(inlCallee);
+    // We may not know callee name in some of the failing cases
+    const char* calleeName = nullptr;
+
+    if (inlCallee == nullptr)
+    {
+        assert(!inlSuccess);
+        calleeName = "<unknown>";
+    }
+    else
+    {
+        calleeName = compiler->eeGetMethodFullName(inlCallee);
+    }
 
     // Dump this node
     if (inlParent == nullptr)
@@ -201,8 +328,9 @@ void InlineContext::Dump(Compiler* compiler, int indent)
     }
     else
     {
-        // Successful inline
+        // Inline attempt.
         const char* inlineReason = inlGetDescriptionString(inlObservation);
+        const char* inlineResult = inlSuccess ? "" : "FAILED: ";
 
         for (int i = 0; i < indent; i++)
         {
@@ -211,12 +339,12 @@ void InlineContext::Dump(Compiler* compiler, int indent)
 
         if (inlOffset == BAD_IL_OFFSET)
         {
-            printf("[IL=????] [%s] %s\n", inlineReason, calleeName);
+            printf("[IL=???? TR=%06u] [%s%s] %s\n", inlTreeID, inlineResult, inlineReason, calleeName);
         }
         else
         {
             IL_OFFSET offset = jitGetILoffs(inlOffset);
-            printf("[IL=%04d] [%s] %s\n", offset, inlineReason, calleeName);
+            printf("[IL=%04d TR=%06u] [%s%s] %s\n", offset, inlTreeID, inlineResult, inlineReason, calleeName);
         }
     }
 
@@ -264,17 +392,17 @@ InlineResult::InlineResult(Compiler*    compiler,
 // InlineResult: Construct an InlineResult to evaluate a particular
 // method as a possible inline candidate.
 //
-// Notes:
-//   Used only during prejitting to try and pre-identify methods
-//   that cannot be inlined, to help subsequent jit throughput.
+// Arguments:
+//    compiler - the compiler instance doing the prejitting
+//    method   - the method in question
+//    context  - descrptive string to describe the context of the decision
 //
-//   We use the inlCallee member to track the method since logically
-//   it is the callee here.
+// Notes:
+//    Used only during prejitting to try and pre-identify methods that
+//    cannot be inlined, to help subsequent jit throughput.
 //
-// Arguments
-//   compiler - the compiler instance doing the prejitting
-//   method   - the method in question
-//   context  - descrptive string to describe the context of the decision
+//    We use the inlCallee member to track the method since logically
+//    it is the callee here.
 
 InlineResult::InlineResult(Compiler*              compiler,
                            CORINFO_METHOD_HANDLE  method,
@@ -295,7 +423,6 @@ InlineResult::InlineResult(Compiler*              compiler,
 // report: Dump, log, and report information about an inline decision.
 //
 // Notes:
-//
 //    Called (automatically via the InlineResult dtor) when the inliner
 //    is done evaluating a candidate.
 //
diff --git a/src/jit/inline.def b/src/jit/inline.def
index 7eeb07f0f7..64cb5a166f 100644
--- a/src/jit/inline.def
+++ b/src/jit/inline.def
@@ -103,7 +103,7 @@ INLINE_OBSERVATION(COMPILATION_FAILURE,       bool,   "failed to compile",
 INLINE_OBSERVATION(CONDITIONAL_THROW,         bool,   "conditional throw",             FATAL,       CALLSITE)
 INLINE_OBSERVATION(CROSS_BOUNDARY_CALLI,      bool,   "cross-boundary calli",          FATAL,       CALLSITE)
 INLINE_OBSERVATION(CROSS_BOUNDARY_SECURITY,   bool,   "cross-boundary security check", FATAL,       CALLSITE)
-INLINE_OBSERVATION(EXCEEDS_THRESHOLD,         bool,   "exeeds profit threshold",       FATAL,       CALLSITE)
+INLINE_OBSERVATION(EXCEEDS_THRESHOLD,         bool,   "exceeds profit threshold",      FATAL,       CALLSITE)
 INLINE_OBSERVATION(EXPLICIT_TAIL_PREFIX,      bool,   "explicit tail prefix",          FATAL,       CALLSITE)
 INLINE_OBSERVATION(GENERIC_DICTIONARY_LOOKUP, bool,   "runtime dictionary lookup",     FATAL,       CALLSITE)
 INLINE_OBSERVATION(HAS_CALL_VIA_LDVIRTFTN,    bool,   "call via ldvirtftn",            FATAL,       CALLSITE)
diff --git a/src/jit/inline.h b/src/jit/inline.h
index 9f72edb90b..a2a060fb11 100644
--- a/src/jit/inline.h
+++ b/src/jit/inline.h
@@ -13,13 +13,13 @@
 // InlineTarget -- enum, target of a particular observation
 // InlineImpact -- enum, impact of a particular observation
 // InlineObservation -- enum, facts observed when considering an inline
-// InlineContext -- class, remembers what inlines happened
 // InlineResult -- class, accumulates observations and makes a decision
 // InlineCandidateInfo -- struct, detailed information needed for inlining
 // InlArgInfo -- struct, information about a candidate's argument
 // InlLclVarInfo -- struct, information about a candidate's local variable
 // InlineHints -- enum, alternative form of observations
 // InlineInfo -- struct, basic information needed for inlining
+// InlineContext -- class, remembers what inlines happened
 
 #ifndef _INLINE_H_
 #define _INLINE_H_
@@ -117,42 +117,6 @@ InlineTarget inlGetTarget(InlineObservation obs);
 
 InlineImpact inlGetImpact(InlineObservation obs);
 
-// InlineContext tracks the inline history in a method.
-//
-// Notes:
-//
-// InlineContexts form a tree with the root method as the root and
-// inlines as children. Nested inlines are represented as granchildren
-// and so on.
-//
-// Leaves in the tree represent successful inlines of leaf methods.
-// In DEBUG builds we also keep track of failed inline attempts.
-//
-// During inlining, all statements in the IR refer back to the
-// InlineContext that is responsible for those statements existing.
-// This makes it possible to detect recursion and to keep track of the
-// depth of each inline attempt.
-
-struct InlineContext
-{
-    // Default constructor, suitable for root instance
-    InlineContext();
-
-    InlineContext*        inlParent;      // logical caller (parent)
-    InlineContext*        inlChild;       // first child
-    InlineContext*        inlSibling;     // next child of the parent
-    IL_OFFSETX            inlOffset;      // call site location within parent
-    BYTE*                 inlCode;        // address of IL buffer for the method
-    InlineObservation     inlObservation; // what lead to this inline
-
-#ifdef DEBUG
-    CORINFO_METHOD_HANDLE inlCallee;     // handle to the method
-
-   // Dump this entry and all descendants
-   void Dump(Compiler* compiler, int indent = 0);
-#endif
-};
-
 // InlineResult summarizes what is known about the viability of a
 // particular inline candiate.
 
@@ -361,6 +325,18 @@ public:
         return inlObservation;
     }
 
+    // The callee handle for this result
+    CORINFO_METHOD_HANDLE getCallee() const
+    {
+        return inlCallee;
+    }
+
+    // The call being considered
+    GenTreeCall* getCall() const
+    {
+        return inlCall;
+    }
+
     // The reason for this particular result
     const char * reasonString() const
     {
@@ -537,6 +513,77 @@ struct InlineInfo
     BasicBlock      * iciBlock;      // The basic block iciStmt is in.
 };
 
+// InlineContext tracks the inline history in a method.
+//
+// Notes:
+//
+// InlineContexts form a tree with the root method as the root and
+// inlines as children. Nested inlines are represented as granchildren
+// and so on.
+//
+// Leaves in the tree represent successful inlines of leaf methods.
+// In DEBUG builds we also keep track of failed inline attempts.
+//
+// During inlining, all statements in the IR refer back to the
+// InlineContext that is responsible for those statements existing.
+// This makes it possible to detect recursion and to keep track of the
+// depth of each inline attempt.
+
+class InlineContext
+{
+public:
+
+    // New context for the root instance
+    static InlineContext* newRoot(Compiler* compiler);
+
+    // New context for a successful inline
+    static InlineContext* newSuccess(Compiler*   compiler,
+                                     InlineInfo* inlineInfo);
+
+#ifdef DEBUG
+
+    // New context for a failing inline
+    static InlineContext* newFailure(Compiler *    compiler,
+                                     GenTree*      stmt,
+                                     InlineResult* inlineResult);
+
+    // Dump the context and all descendants
+    void Dump(Compiler* compiler, int indent = 0);
+
+#endif
+
+    // Get the parent context for this context.
+    InlineContext* getParent() const
+    {
+        return inlParent;
+    }
+
+    // Get the code pointer for this context.
+    BYTE* getCode() const
+    {
+        return inlCode;
+    }
+
+private:
+
+    InlineContext();
+
+private:
+
+    InlineContext*        inlParent;      // logical caller (parent)
+    InlineContext*        inlChild;       // first child
+    InlineContext*        inlSibling;     // next child of the parent
+    IL_OFFSETX            inlOffset;      // call site location within parent
+    BYTE*                 inlCode;        // address of IL buffer for the method
+    InlineObservation     inlObservation; // what lead to this inline
+
+#ifdef DEBUG
+    CORINFO_METHOD_HANDLE inlCallee;      // handle to the method
+    unsigned              inlTreeID;      // ID of the GenTreeCall
+    bool                  inlSuccess;     // true if this was a successful inline
+#endif
+
+};
 
 #endif // _INLINE_H_
 
diff --git a/src/jit/morph.cpp b/src/jit/morph.cpp
index ab26617dc9..6183a9d95c 100644
--- a/src/jit/morph.cpp
+++ b/src/jit/morph.cpp
@@ -5626,6 +5626,15 @@ bool        Compiler::fgMorphCallInline(GenTreePtr node)
     // If we failed to inline, we have a bit of work to do to cleanup
     if (inlineResult.isFailure())
     {
+
+#ifdef DEBUG
+
+        // Before we do any cleanup. create a failing InlineContext to
+        // capture details of the inlining attempt.
+        InlineContext::newFailure(this, fgMorphStmt, &inlineResult);
+
+#endif
+
         // It was an inline candidate, but we haven't expanded it.
         if (call->gtCall.gtReturnType != TYP_VOID)
         {
@@ -5693,7 +5702,6 @@ void Compiler::fgMorphCallInlineHelper(GenTreeCall* call, InlineResult* result)
         InlineObservation currentObservation = InlineObservation::CALLSITE_NOT_CANDIDATE;
 
 #ifdef DEBUG
-
         // Try and recover the reason left behind when the jit decided
         // this call was not a candidate.
         InlineObservation priorObservation = call->gtInlineObservation;
@@ -5704,7 +5712,24 @@ void Compiler::fgMorphCallInlineHelper(GenTreeCall* call, InlineResult* result)
         }
 #endif
 
-        result->noteFatal(InlineObservation::CALLSITE_NOT_CANDIDATE);
+        // Would like to just call noteFatal here, since this
+        // observation blocked candidacy, but policy comes into play
+        // here too.  Also note there's no need to re-report these
+        // failures, since we reported them during the initial
+        // candidate scan.
+        InlineImpact impact = inlGetImpact(currentObservation);
+
+        if (impact == InlineImpact::FATAL)
+        {
+            result->noteFatal(currentObservation);
+        }
+        else
+        {
+            result->note(currentObservation);
+        }
+
+        result->setReported();
+
         return;
     }