Introduce deoptimization operand bundles

[sanjoy]

Summary

This change introduces the notion of "deoptimization" operand bundles.
LLVM can recognize and optimize these in more precise ways than it can a
generic "unknown" operand bundles.

The current form of this special recognition / optimization is an enum
entry in LLVMContext, a LangRef blurb and a verifier rule. Over time we
will teach LLVM to do more aggressive optimization around deoptimization
operand bundles, exploiting known facts about kinds of state
deoptimization operand bundles are allowed to track.

[reames]

docs/LangRef.rst

1508

, unless the current frame is being deoptimized in which case return will never return to the compiled code of the caller function after the call.

lib/IR/LLVMContextImpl.cpp

50 ↗

(On Diff #39847)

Why do this in the Impl rather than the Context as we do for attributes? I'd prefer consistency unless you have a good reason.

test/Verifier/operand-bundles.ll

38

Can you add a passing test case too? Something to show the verifier *doesn't* reject a single valid deopt bundle?

[sanjoy]

• address review

[reames]

LGTM w/minor comment addressed.

include/llvm/IR/LLVMContext.h

70

Doxygen comment /// please

docs/LangRef.rst

 - Calls and invokes with operand bundles have unknown read / write
   effect on the heap on entry and exit (even if the call target is
   ``readnone`` or ``readonly``), unless they're overriden with
   callsite specific attributes.
 - An operand bundle at a call site cannot change the implementation
   of the called function.  Inter-procedural optimizations work as
   usual as long as they take into account the first two properties.
 
+More specific types of operand bundles are described below.
+
+Deoptimization Operand Bundles
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+Deoptimization operand bundles are characterized by the ``"deopt``
+operand bundle tag.  These operand bundles represent an alternate
+"safe" continuation for the call site they're attached to, and can be
+used by a suitable runtime to deoptimize the compiled frame at the
+specified call site.  Exact details of deoptimization is out of scope
+for the language reference, but it usually involves rewriting a
+compiled frame into a set of interpreted frames.
+
+From the compiler's perspective, deoptimization operand bundles make
+the call sites they're attached to at least ``readonly``.  They read
+through all of their pointer typed operands (even if they're not
+otherwise escaped) and the entire visible heap.  Deoptimization
+operand bundles do not capture their operands except during
+deoptimization, in which case control will not be returned to the
+compiled frame.
+
 .. _moduleasm:
 
 Module-Level Inline Assembly
 ----------------------------
 
 Modules may contain "module-level inline asm" blocks, which corresponds
 to the GCC "file scope inline asm" blocks. These blocks are internally
 concatenated by LLVM and treated as a single unit, but may be separated

include/llvm/IR/LLVMContext.h

enum {
     MD_dereferenceable = 12, // "dereferenceable"
     MD_dereferenceable_or_null = 13, // "dereferenceable_or_null"
     MD_make_implicit = 14, // "make.implicit"
     MD_unpredictable = 15, // "unpredictable"
     MD_invariant_group = 16, // "invariant.group"
     MD_align = 17 // "align"
   };
 
+  // Known operand bundle tag IDs, which always have the same value.  All
+  // operand bundle tags that LLVM has special knowledge of are listed here.
+  // Additionally, this scheme allows LLVM to efficiently check for specific
+  // operand bundle tags without comparing strings.
+  enum {
+    OB_deopt = 0,  // "deopt"
+  };
+
   /// getMDKindID - Return a unique non-zero ID for the specified metadata kind.
   /// This ID is uniqued across modules in the current LLVMContext.
   unsigned getMDKindID(StringRef Name) const;
 
   /// getMDKindNames - Populate client supplied SmallVector with the name for
   /// custom metadata IDs registered in this LLVMContext.
   void getMDKindNames(SmallVectorImpl<StringRef> &Result) const;
 

lib/IR/LLVMContext.cpp

LLVMContext::LLVMContext() : pImpl(new LLVMContextImpl(*this)) {
   assert(InvariantGroupId == MD_invariant_group &&
          "invariant.group kind id drifted");
   (void)InvariantGroupId;
 
   // Create the 'align' metadata kind.
   unsigned AlignID = getMDKindID("align");
   assert(AlignID == MD_align && "align kind id drifted");
   (void)AlignID;
+
+  auto *DeoptEntry = pImpl->getOrInsertBundleTag("deopt");
+  assert(DeoptEntry->second == LLVMContext::OB_deopt &&
+         "deopt operand bundle id drifted!");
+  (void)DeoptEntry;
 }
 LLVMContext::~LLVMContext() { delete pImpl; }
 
 void LLVMContext::addModule(Module *M) {
   pImpl->OwnedModules.insert(M);
 }
 
 void LLVMContext::removeModule(Module *M) {

lib/IR/Verifier.cpp

void Verifier::VerifyCallSite(CallSite CS) {
   if (CS.getCalledFunction() == nullptr)
     Assert(!FTy->getReturnType()->isTokenTy(),
            "Return type cannot be token for indirect call!");
 
   if (Function *F = CS.getCalledFunction())
     if (Intrinsic::ID ID = (Intrinsic::ID)F->getIntrinsicID())
       visitIntrinsicCallSite(ID, CS);
 
+  // Verify that a callsite has at most one "deopt" operand bundle.
+  bool FoundDeoptBundle = false;
+  for (unsigned i = 0, e = CS.getNumOperandBundles(); i < e; ++i) {
+    if (CS.getOperandBundleAt(i).getTagID() == LLVMContext::OB_deopt) {
+      Assert(!FoundDeoptBundle, "Multiple deopt operand bundles", I);
+      FoundDeoptBundle = true;
+    }
+  }
+
   visitInstruction(*I);
 }
 
 /// Two types are "congruent" if they are identical, or if they are both pointer
 /// types with different pointee types and the same address space.
 static bool isTypeCongruent(Type *L, Type *R) {
   if (L == R)
     return true;

test/Verifier/operand-bundles.ll

 exception:
   %cleanup = landingpad i8 cleanup
   br label %normal
 
 normal:
   %x = add i32 42, 1
   ret void
 }
+
+define void @f_deopt(i32* %ptr) {
+; CHECK: Multiple deopt operand bundles
+; CHECK-NEXT: call void @g() [ "deopt"(i32 42, i64 100, i32 %x), "deopt"(float 0.000000e+00, i64 100, i32 %l) ]
+; CHECK-NOT: call void @g() [ "deopt"(i32 42, i64 120, i32 %x) ]
+
+ entry:
+  %l = load i32, i32* %ptr
+  call void @g() [ "deopt"(i32 42, i64 100, i32 %x), "deopt"(float 0.0, i64 100, i32 %l) ]
+  call void @g() [ "deopt"(i32 42, i64 120) ]  ;; The verifier should not complain about this one
+  %x = add i32 42, 1
+  ret void
+}