Introduce a @llvm.experimental.guard.on intrinsic

[sanjoy]

Summary

As discussed on llvm-dev[1].

This change adds the basic boilerplate code around having this intrinsic
in LLVM:

• Changes in Intrinsics.td, and the IR Verifier
• A lowering pass to lower @llvm.experimental.guard.on to normal control flow
• Inliner support

[1]: http://lists.llvm.org/pipermail/llvm-dev/2016-February/095523.html

[reames]

A bunch of small comments. Looks close to ready to go in.

I think it would also help to layout a quick sketch of what comes next. How does this fit into the standard pipeline? What optimization passes are going to be changed? How does this interact with assume?

docs/LangRef.rst

12184

Minor: I'd drop on from the name. The extra punctuation is distracting.

12206

<args...>

Make a note about the var args part..

12207

minor: instead of undef, maybe a volatile load from an unmodeled location?

12218

wording: I wouldn't use deoptimize in this sense. It could be confused with policy choices like what to do with the code.

12220

Mention widening explicitly as motivation for the guard.

lib/Transforms/Scalar/LowerGuardIntrinsic.cpp

12

Clarify that after lowering, the guards can no longer be widened.

16

Include sort.

40

Possibly add a fastpath of the form:
if (getFunction(guard)->uses_empty())

return;

I'd like this to be on by default in the standard pipeline.

55

I find this comment more confusing then helpful.

61

Pulling out a helper function which inserts the new control flow, calling it, then dropping the original call might be clearer.

71

possibly: "guarded"

74

Two suggestions:

• Use IRBuilder?
• Explicitly branch on whether there's a return type rather than using two ternaries (one explicit, one implicit).

test/Transforms/LowerGuardIntrinsic/basic.ll

2

Hm, it looks like the lowering pass is not part of the standard pipeline right now. I'd like to see this become part of the standard LLC pipeline. Doesn't have to be in this change specifically, but I will expect to see lowering tests showing the a guard gets lowered correctly all the way to assembly at some point.

6

Why alwaysinline?

20

Can you comment what each is testing?

[sanjoy]

• address review

docs/LangRef.rst

12207

I think that'd be the opposite of what we want. "volatile load from an unmodeled location" => the optimizer needs to model it most conservatively (i.e. can be any value the programmer wants), "undef" => the optimizer can model it least conservatively (i.e. can be any value the optimizer wants).

lib/Transforms/Scalar/LowerGuardIntrinsic.cpp

16

The convention in the other files (that include Scalar.h) seem to be to include Scalar.h and then have the rest of the list sorted.

40

Done, but that's not enough to switch this on in the standard pipeline. As written, in the old pass manager, this will still break all analyses in the no-op case. We can consider fixing that, but not in this change.

55

Removed.

test/Transforms/LowerGuardIntrinsic/basic.ll

2

As mentioned earlier, adding this pass as is to the default pipeline is probably going to be a compile time regression.

6

Leftover from where I copied the test from, removed.

20

I didn't add comments, but renamed the functions to add some context.

[reames]

LGTM. This will probably evolve more as we explore how to actually use it, but doing that evolution in tree seems completely reasonable.

lib/Transforms/Scalar/LowerGuardIntrinsic.cpp

73

Minor: also check uses.

docs/LangRef.rst

 
 Calls to ``@llvm.experimental.deoptimize`` are lowered to calls to the
 symbol ``__llvm_deoptimize`` (it is the frontend's responsibility to
 ensure that this symbol is defined).  The call arguments to
 ``@llvm.experimental.deoptimize`` are lowered as if they were formal
 arguments of the specified types, and not as varargs.
 
 
+'``llvm.experimental.guard``' Intrinsic
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+Syntax:
+"""""""
+
+::
+
+      declare void @llvm.experimental.guard(i1, ...) [ "deopt"(...) ]
+
+Overview:
+"""""""""
+
+This intrinsic, together with :ref:`deoptimization operand bundles
+<deopt_opbundles>`, allows frontends to express guards or checks on
+optimistic assumptions made during compilation.  The semantics of
+``@llvm.experimental.guard`` is defined in terms of
+``@llvm.experimental.deoptimize`` -- its body is defined to be
+equivalent to:
+
+.. code-block:: llvm
+
+  define void @llvm.experimental.guard(i1 %pred, <args...>) {
+    %realPred = and i1 %pred, undef
+    br i1 %realPred, label %continue, label %leave
+
+  leave:
+    call void @llvm.experimental.deoptimize(<args...>) [ "deopt"() ]
+    ret void
+
+  continue:
+    ret void
+  }
+
+In words, ``@llvm.experimental.guard`` executes the attached
+``"deopt"`` continuation if (but **not** only if) its first argument
+is ``false``.  Since the optimizer is allowed to replace the ``undef``
+with an arbitrary value, it can optimize guard to fail "spuriously",
+i.e. without the original condition being false (hence the "not only
+if"); and this allows for "check widening" type optimizations.
+
+``@llvm.experimental.guard`` cannot be invoked.
+
+
 Stack Map Intrinsics
 --------------------
 
 LLVM provides experimental intrinsics to support runtime patching
 mechanisms commonly desired in dynamic language JITs. These intrinsics
 are described in :doc:`StackMaps`.

include/llvm/IR/Intrinsics.td

def int_trap : Intrinsic<[], [], [IntrNoReturn]>,
                GCCBuiltin<"__builtin_trap">;
 def int_debugtrap : Intrinsic<[]>,
                     GCCBuiltin<"__builtin_debugtrap">;
 
 // Support for dynamic deoptimization (or de-specialization)
 def int_experimental_deoptimize : Intrinsic<[llvm_any_ty], [llvm_vararg_ty],
                                             [Throws]>;
 
+// Support for speculative runtime guards
+def int_experimental_guard : Intrinsic<[], [llvm_i1_ty, llvm_vararg_ty],
+                                       [Throws]>;
+
 // NOP: calls/invokes to this intrinsic are removed by codegen
 def int_donothing : Intrinsic<[], [], [IntrNoMem]>;
 
 // Intrisics to support half precision floating point format
 let IntrProperties = [IntrNoMem] in {
 def int_convert_to_fp16   : Intrinsic<[llvm_i16_ty], [llvm_anyfloat_ty]>;
 def int_convert_from_fp16 : Intrinsic<[llvm_anyfloat_ty], [llvm_i16_ty]>;
 }

include/llvm/InitializePasses.h

 void initializeLoopRerollPass(PassRegistry&);
 void initializeLoopUnrollPass(PassRegistry&);
 void initializeLoopUnswitchPass(PassRegistry&);
 void initializeLoopVersioningLICMPass(PassRegistry&);
 void initializeLoopIdiomRecognizePass(PassRegistry&);
 void initializeLowerAtomicPass(PassRegistry&);
 void initializeLowerBitSetsPass(PassRegistry&);
 void initializeLowerExpectIntrinsicPass(PassRegistry&);
+void initializeLowerGuardIntrinsicPass(PassRegistry&);
 void initializeLowerIntrinsicsPass(PassRegistry&);
 void initializeLowerInvokePass(PassRegistry&);
 void initializeLowerSwitchPass(PassRegistry&);
 void initializeLowerEmuTLSPass(PassRegistry&);
 void initializeMachineBlockFrequencyInfoPass(PassRegistry&);
 void initializeMachineBlockPlacementPass(PassRegistry&);
 void initializeMachineBlockPlacementStatsPass(PassRegistry&);
 void initializeMachineBranchProbabilityInfoPass(PassRegistry&);

include/llvm/Transforms/Scalar.h

 //===----------------------------------------------------------------------===//
 //
 // LowerAtomic - Lower atomic intrinsics to non-atomic form
 //
 Pass *createLowerAtomicPass();
 
 //===----------------------------------------------------------------------===//
 //
+// LowerGuardIntrinsic - Lower guard intrinsics to normal control flow.
+//
+Pass *createLowerGuardIntrinsicPass();
+
+//===----------------------------------------------------------------------===//
+//
 // ValuePropagation - Propagate CFG-derived value information
 //
 Pass *createCorrelatedValuePropagationPass();
 
 //===----------------------------------------------------------------------===//
 //
 // InstructionSimplifier - Remove redundant instructions.
 //

lib/IR/Verifier.cpp

case Intrinsic::masked_store: {
     Assert(DataTy == Val->getType(), 
            "masked_store: storee must match pointer type", CS);
     Assert(Mask->getType()->getVectorNumElements() ==
            DataTy->getVectorNumElements(), 
            "masked_store: vector mask must be same length as data", CS);
     break;
   }
 
+  case Intrinsic::experimental_guard: {
+    Assert(CS.isCall(), "experimental_guard cannot be invoked", CS);
+    Assert(CS.countOperandBundlesOfType(LLVMContext::OB_deopt) == 1,
+           "experimental_guard must have exactly one "
+           "\"deopt\" operand bundle");
+    break;
+  }
+
   case Intrinsic::experimental_deoptimize: {
     Assert(CS.isCall(), "experimental_deoptimize cannot be invoked", CS);
     Assert(CS.countOperandBundlesOfType(LLVMContext::OB_deopt) == 1,
            "experimental_deoptimize must have exactly one "
            "\"deopt\" operand bundle");
     Assert(CS.getType() == CS.getInstruction()->getFunction()->getReturnType(),
            "experimental_deoptimize return type must match caller return type");
 

lib/Transforms/Scalar/CMakeLists.txt

add_llvm_library(LLVMScalarOpts
   LoopRotation.cpp
   LoopSimplifyCFG.cpp
   LoopStrengthReduce.cpp
   LoopUnrollPass.cpp
   LoopUnswitch.cpp
   LoopVersioningLICM.cpp
   LowerAtomic.cpp
   LowerExpectIntrinsic.cpp
+  LowerGuardIntrinsic.cpp
   MemCpyOptimizer.cpp
   MergedLoadStoreMotion.cpp
   NaryReassociate.cpp
   PartiallyInlineLibCalls.cpp
   PlaceSafepoints.cpp
   Reassociate.cpp
   Reg2Mem.cpp
   RewriteStatepointsForGC.cpp

lib/Transforms/Scalar/LowerGuardIntrinsic.cpp

+//===- LowerGuardIntrinsic.cpp - Lower the guard intrinsic ---------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass lowers the llvm.experimental.guard intrinsic to a conditional call
+// to @llvm.experimental.deoptimize.  Once this happens, the guard can no longer
+// be widened.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/Scalar.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/InstIterator.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/Intrinsics.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Pass.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
+
+using namespace llvm;
+
+namespace {
+struct LowerGuardIntrinsic : public FunctionPass {
+  static char ID;
+  LowerGuardIntrinsic() : FunctionPass(ID) {
+    initializeLowerGuardIntrinsicPass(*PassRegistry::getPassRegistry());
+  }
+
+  bool runOnFunction(Function &F) override;
+};
+}
+
+static void MakeGuardControlFlowExplicit(Function *DeoptIntrinsic,
+                                         CallInst *CI) {
+  OperandBundleDef DeoptOB(*CI->getOperandBundle(LLVMContext::OB_deopt));
+  SmallVector<Value *, 4> Args(std::next(CI->arg_begin()), CI->arg_end());
+
+  auto *CheckBB = CI->getParent();
+  auto *DeoptBlockTerm =
+      SplitBlockAndInsertIfThen(CI->getArgOperand(0), CI, true);
+
+  auto *CheckBI = cast<BranchInst>(CheckBB->getTerminator());
+
+  // SplitBlockAndInsertIfThen inserts control flow that branches to
+  // DeoptBlockTerm if the condition is true.  We want the opposite.
+  CheckBI->swapSuccessors();
+
+  CheckBI->getSuccessor(0)->setName("guarded");
+  CheckBI->getSuccessor(1)->setName("deopt");
+
+  IRBuilder<> B(DeoptBlockTerm);
+  auto *DeoptCall = B.CreateCall(DeoptIntrinsic, Args, {DeoptOB}, "");
+
+  if (DeoptIntrinsic->getReturnType()->isVoidTy()) {
+    B.CreateRetVoid();
+  } else {
+    DeoptCall->setName("deoptcall");
+    B.CreateRet(DeoptCall);
+  }
+
+  DeoptBlockTerm->eraseFromParent();
+}
+
+bool LowerGuardIntrinsic::runOnFunction(Function &F) {
+  if (!F.getParent()->getFunction(
+          Intrinsic::getName(Intrinsic::experimental_guard))) {
+    // No need to scan F, since we obviously have no calls to guard.
+    return false;
+  }
+
+  SmallVector<CallInst *, 8> ToLower;
+  for (auto &I : instructions(F))
+    if (auto *CI = dyn_cast<CallInst>(&I))
+      if (auto *F = CI->getCalledFunction())
+        if (F->getIntrinsicID() == Intrinsic::experimental_guard)
+          ToLower.push_back(CI);
+
+  if (ToLower.empty())
+    return false;
+
+  auto *DeoptIntrinsic = Intrinsic::getDeclaration(
+      F.getParent(), Intrinsic::experimental_deoptimize, {F.getReturnType()});
+
+  for (auto *CI : ToLower) {
+    MakeGuardControlFlowExplicit(DeoptIntrinsic, CI);
+    CI->eraseFromParent();
+  }
+
+  return true;
+}
+
+char LowerGuardIntrinsic::ID = 0;
+INITIALIZE_PASS(LowerGuardIntrinsic, "lower-guard-intrinsic",
+                "Lower the guard intrinsic to normal control flow", false,
+                false)
+
+Pass *llvm::createLowerGuardIntrinsicPass() {
+  return new LowerGuardIntrinsic();
+}

lib/Transforms/Scalar/Scalar.cpp

void llvm::initializeScalarOpts(PassRegistry &Registry) {
   initializeLoopStrengthReducePass(Registry);
   initializeLoopRerollPass(Registry);
   initializeLoopUnrollPass(Registry);
   initializeLoopUnswitchPass(Registry);
   initializeLoopVersioningLICMPass(Registry);
   initializeLoopIdiomRecognizePass(Registry);
   initializeLowerAtomicPass(Registry);
   initializeLowerExpectIntrinsicPass(Registry);
+  initializeLowerGuardIntrinsicPass(Registry);
   initializeMemCpyOptPass(Registry);
   initializeMergedLoadStoreMotionPass(Registry);
   initializeNaryReassociatePass(Registry);
   initializePartiallyInlineLibCallsPass(Registry);
   initializeReassociatePass(Registry);
   initializeRegToMemPass(Registry);
   initializeRewriteStatepointsForGCPass(Registry);
   initializeSCCPPass(Registry);

lib/Transforms/Utils/InlineFunction.cpp

for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E; ) {
     // We only need to check for function calls: inlined invoke
     // instructions require no special handling.
     CallInst *CI = dyn_cast<CallInst>(I);
 
     if (!CI || CI->doesNotThrow() || isa<InlineAsm>(CI->getCalledValue()))
       continue;
 
     // We do not need to (and in fact, cannot) convert possibly throwing calls
-    // to @llvm.experimental_deoptimize into invokes.  The caller's "segment" of
-    // the deoptimization continuation attached to the newly inlined
-    // @llvm.experimental_deoptimize call should contain the exception handling
-    // logic, if any.
+    // to @llvm.experimental_deoptimize (resp. @llvm.experimental.guard) into
+    // invokes.  The caller's "segment" of the deoptimization continuation
+    // attached to the newly inlined @llvm.experimental_deoptimize
+    // (resp. @llvm.experimental.guard) call should contain the exception
+    // handling logic, if any.
     if (auto *F = CI->getCalledFunction())
-      if (F->getIntrinsicID() == Intrinsic::experimental_deoptimize)
+      if (F->getIntrinsicID() == Intrinsic::experimental_deoptimize ||
+          F->getIntrinsicID() == Intrinsic::experimental_guard)
         continue;
 
     if (auto FuncletBundle = CI->getOperandBundle(LLVMContext::OB_funclet)) {
       // This call is nested inside a funclet.  If that funclet has an unwind
       // destination within the inlinee, then unwinding out of this call would
       // be UB.  Rewriting this call to an invoke which targets the inlined
       // invoke's unwind dest would give the call's parent funclet multiple
       // unwind destinations, which is something that subsequent EH table

test/Transforms/Inline/guard-intrinsic.ll

+; RUN: opt -S -always-inline < %s | FileCheck %s
+
+declare void @llvm.experimental.guard(i1, ...)
+
+define i8 @callee(i1* %c_ptr) alwaysinline {
+  %c = load volatile i1, i1* %c_ptr
+  call void(i1, ...) @llvm.experimental.guard(i1 %c, i32 1) [ "deopt"(i32 1) ]
+  ret i8 5
+}
+
+define void @caller_0(i1* %c, i8* %ptr) {
+; CHECK-LABEL: @caller_0(
+entry:
+; CHECK:  [[COND:%[^ ]+]] = load volatile i1, i1* %c
+; CHECK-NEXT:  call void (i1, ...) @llvm.experimental.guard(i1 [[COND]], i32 1) [ "deopt"(i32 2, i32 1) ]
+; CHECK-NEXT:  store i8 5, i8* %ptr
+
+  %v = call i8 @callee(i1* %c)  [ "deopt"(i32 2) ]
+  store i8 %v, i8* %ptr
+  ret void
+}
+
+define i32 @caller_1(i1* %c, i8* %ptr) personality i8 3 {
+; CHECK-LABEL: @caller_1(
+; CHECK:  [[COND:%[^ ]+]] = load volatile i1, i1* %c
+; CHECK-NEXT:  call void (i1, ...) @llvm.experimental.guard(i1 [[COND]], i32 1) [ "deopt"(i32 3, i32 1) ]
+; CHECK-NEXT:  br label %normal
+entry:
+  %v = invoke i8 @callee(i1* %c)  [ "deopt"(i32 3) ] to label %normal
+       unwind label %unwind
+
+unwind:
+  %lp = landingpad i32 cleanup
+  ret i32 43
+
+normal:
+  store i8 %v, i8* %ptr
+  ret i32 42
+}

test/Transforms/LowerGuardIntrinsic/basic.ll

+; RUN: opt -S -lower-guard-intrinsic < %s | FileCheck %s
+
+declare void @llvm.experimental.guard(i1, ...)
+
+define i8 @f_basic(i1* %c_ptr) {
+; CHECK-LABEL: @f_basic(
+
+  %c = load volatile i1, i1* %c_ptr
+  call void(i1, ...) @llvm.experimental.guard(i1 %c, i32 1) [ "deopt"(i32 1) ]
+  ret i8 5
+
+; CHECK:  br i1 %c, label %guarded, label %deopt
+; CHECK: deopt:
+; CHECK-NEXT:  %deoptcall = call i8 (...) @llvm.experimental.deoptimize.i8(i32 1) [ "deopt"(i32 1) ]
+; CHECK-NEXT:  ret i8 %deoptcall
+; CHECK: guarded:
+; CHECK-NEXT:  ret i8 5
+}
+
+define void @f_void_return_ty(i1* %c_ptr) {
+; CHECK-LABEL: @f_void_return_ty(
+
+  %c = load volatile i1, i1* %c_ptr
+  call void(i1, ...) @llvm.experimental.guard(i1 %c, i32 1) [ "deopt"() ]
+  ret void
+
+; CHECK:  br i1 %c, label %guarded, label %deopt
+; CHECK: deopt:
+; CHECK-NEXT:  call void (...) @llvm.experimental.deoptimize.isVoid(i32 1) [ "deopt"() ]
+; CHECK-NEXT:  ret void
+; CHECK: guarded:
+; CHECK-NEXT:  ret void
+}
+
+define void @f_multiple_args(i1* %c_ptr) {
+; CHECK-LABEL: @f_multiple_args(
+
+  %c = load volatile i1, i1* %c_ptr
+  call void(i1, ...) @llvm.experimental.guard(i1 %c, i32 1, i32 2, double 500.0) [ "deopt"(i32 2, i32 3) ]
+  ret void
+
+; CHECK: br i1 %c, label %guarded, label %deopt
+; CHECK: deopt:
+; CHECK-NEXT:  call void (...) @llvm.experimental.deoptimize.isVoid(i32 1, i32 2, double 5.000000e+02) [ "deopt"(i32 2, i32 3) ]
+; CHECK-NEXT:  ret void
+; CHECK: guarded:
+; CHECK-NEXT:  ret void
+}
+
+define i32 @f_zero_args(i1* %c_ptr) {
+; CHECK-LABEL: @f_zero_args(
+  %c = load volatile i1, i1* %c_ptr
+  call void(i1, ...) @llvm.experimental.guard(i1 %c) [ "deopt"(i32 2, i32 3) ]
+  ret i32 500
+
+; CHECK: br i1 %c, label %guarded, label %deopt
+; CHECK: deopt:
+; CHECK-NEXT:  %deoptcall = call i32 (...) @llvm.experimental.deoptimize.i32() [ "deopt"(i32 2, i32 3) ]
+; CHECK-NEXT:  ret i32 %deoptcall
+; CHECK: guarded:
+; CHECK-NEXT:  ret i32 500
+}

test/Verifier/guard-intrinsic.ll

+; RUN: not opt -S -verify < %s 2>&1 | FileCheck %s
+
+declare void @llvm.experimental.guard(i1, ...)
+
+declare void @unknown()
+
+define void @f_nodeopt() {
+entry:
+  call void(i1, ...) @llvm.experimental.guard(i1 undef, i32 1, i32 2)
+; CHECK: guard must have exactly one "deopt" operand bundle
+  ret void
+}
+
+define void @f_invoke() personality i8 3 {
+entry:
+  invoke void(i1, ...) @llvm.experimental.guard(i1 undef, i32 0, float 0.0) [ "deopt"() ] to label %ok unwind label %not_ok
+; CHECK: guard cannot be invoked
+
+ok:
+  ret void
+
+not_ok:
+  %0 = landingpad { i8*, i32 }
+          filter [0 x i8*] zeroinitializer
+  ret void
+}