Guarded devirtualization foundations (#21270)

Lay the groundwork for guarded devirtualization of virtual and interface
calls in the jit.

Introduce the notion of a guarded devirtualization candidate and identify
these if regular devirtualization fails. Use simple heuristics to produce
a class to guess for. Require that the method that would be invoked if the class
guess is correct be a plausible inline candidate.

Generalize the calli transformer to become an indirect call transformer.
This runs after importation because it needs to introduce control flow and
runs before inlining so that the new direct calls it introduces can be inlined.

Implement the transformation to duplicate the call site, devirtualize on the side
where the class is now known exactly, and turn the resulting direct call into an
inline candidate.

Add a motivation and design document.

1 files changed, 44 insertions, 20 deletions

diff --git a/src/jit/morph.cpp b/src/jit/morph.cpp
index 20e378ed16..566714f276 100644
--- a/src/jit/morph.cpp
+++ b/src/jit/morph.cpp
@@ -6614,42 +6614,59 @@ GenTree* Compiler::fgMorphField(GenTree* tree, MorphAddrContext* mac)
 
 void Compiler::fgMorphCallInline(GenTreeCall* call, InlineResult* inlineResult)
 {
-    // The call must be a candiate for inlining.
-    assert((call->gtFlags & GTF_CALL_INLINE_CANDIDATE) != 0);
+    bool inliningFailed = false;
 
-    // Attempt the inline
-    fgMorphCallInlineHelper(call, inlineResult);
+    // Is this call an inline candidate?
+    if (call->IsInlineCandidate())
+    {
+        // Attempt the inline
+        fgMorphCallInlineHelper(call, inlineResult);
 
-    // We should have made up our minds one way or another....
-    assert(inlineResult->IsDecided());
+        // We should have made up our minds one way or another....
+        assert(inlineResult->IsDecided());
 
-    // If we failed to inline, we have a bit of work to do to cleanup
-    if (inlineResult->IsFailure())
-    {
+        // 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.
-        m_inlineStrategy->NewFailure(fgMorphStmt, inlineResult);
+            // Before we do any cleanup, create a failing InlineContext to
+            // capture details of the inlining attempt.
+            m_inlineStrategy->NewFailure(fgMorphStmt, inlineResult);
 
 #endif
 
-        // It was an inline candidate, but we haven't expanded it.
-        if (call->gtCall.gtReturnType != TYP_VOID)
+            inliningFailed = true;
+
+            // Clear the Inline Candidate flag so we can ensure later we tried
+            // inlining all candidates.
+            //
+            call->gtFlags &= ~GTF_CALL_INLINE_CANDIDATE;
+        }
+    }
+    else
+    {
+        // This wasn't an inline candidate. So it must be a GDV candidate.
+        assert(call->IsGuardedDevirtualizationCandidate());
+
+        // We already know we can't inline this call, so don't even bother to try.
+        inliningFailed = true;
+    }
+
+    // If we failed to inline (or didn't even try), do some cleanup.
+    if (inliningFailed)
+    {
+        if (call->gtReturnType != TYP_VOID)
         {
+            JITDUMP("Inlining [%06u] failed, so bashing [%06u] to NOP\n", dspTreeID(call), dspTreeID(fgMorphStmt));
+
             // Detach the GT_CALL tree from the original statement by
             // hanging a "nothing" node to it. Later the "nothing" node will be removed
             // and the original GT_CALL tree will be picked up by the GT_RET_EXPR node.
-
             noway_assert(fgMorphStmt->gtStmtExpr == call);
             fgMorphStmt->gtStmtExpr = gtNewNothingNode();
         }
-
-        // Clear the Inline Candidate flag so we can ensure later we tried
-        // inlining all candidates.
-        //
-        call->gtFlags &= ~GTF_CALL_INLINE_CANDIDATE;
     }
 }
 
@@ -6682,6 +6699,13 @@ void Compiler::fgMorphCallInlineHelper(GenTreeCall* call, InlineResult* result)
         return;
     }
 
+    // Re-check this because guarded devirtualization may allow these through.
+    if (gtIsRecursiveCall(call) && call->IsImplicitTailCall())
+    {
+        result->NoteFatal(InlineObservation::CALLSITE_IMPLICIT_REC_TAIL_CALL);
+        return;
+    }
+
     // impMarkInlineCandidate() is expected not to mark tail prefixed calls
     // and recursive tail calls as inline candidates.
     noway_assert(!call->IsTailPrefixedCall());