From b4b58babf8095a7a22eb8d878501189a8c31ed48 Mon Sep 17 00:00:00 2001
From: Sanjoy Das <sanjoy@playingwithpointers.com>
Date: Wed, 11 Nov 2015 21:38:02 +0000
Subject: [PATCH] Introduce deoptimization operand bundles

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.

Reviewers: reames, majnemer, chandlerc, dexonsmith

Subscribers: llvm-commits

Differential Revision: http://reviews.llvm.org/D14551

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@252806 91177308-0d34-0410-b5e6-96231b3b80d8
---
 docs/LangRef.rst                 | 21 +++++++++++++++++++++
 include/llvm/IR/LLVMContext.h    |  8 ++++++++
 lib/IR/LLVMContext.cpp           |  5 +++++
 lib/IR/Verifier.cpp              |  9 +++++++++
 test/Verifier/operand-bundles.ll | 13 +++++++++++++
 5 files changed, 56 insertions(+)

diff --git a/docs/LangRef.rst b/docs/LangRef.rst
index d58b7b2e4df..c66df4ef6e9 100644
--- a/docs/LangRef.rst
+++ b/docs/LangRef.rst
@@ -1488,6 +1488,27 @@ operand bundle to not miscompile programs containing it.
   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
diff --git a/include/llvm/IR/LLVMContext.h b/include/llvm/IR/LLVMContext.h
index 24e95f6a62f..c00e3052b59 100644
--- a/include/llvm/IR/LLVMContext.h
+++ b/include/llvm/IR/LLVMContext.h
@@ -67,6 +67,14 @@ public:
     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;
diff --git a/lib/IR/LLVMContext.cpp b/lib/IR/LLVMContext.cpp
index cecc6335ef1..af998c86135 100644
--- a/lib/IR/LLVMContext.cpp
+++ b/lib/IR/LLVMContext.cpp
@@ -127,6 +127,11 @@ LLVMContext::LLVMContext() : pImpl(new LLVMContextImpl(*this)) {
   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; }
 
diff --git a/lib/IR/Verifier.cpp b/lib/IR/Verifier.cpp
index 0fce50e8440..63b91957519 100644
--- a/lib/IR/Verifier.cpp
+++ b/lib/IR/Verifier.cpp
@@ -2324,6 +2324,15 @@ void Verifier::VerifyCallSite(CallSite CS) {
     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);
 }
 
diff --git a/test/Verifier/operand-bundles.ll b/test/Verifier/operand-bundles.ll
index 0aba61cccb8..d822568a044 100644
--- a/test/Verifier/operand-bundles.ll
+++ b/test/Verifier/operand-bundles.ll
@@ -34,3 +34,16 @@ 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
+}
-- 
2.11.0