Add "first class" lowering for deopt operand bundles

[sanjoy]

Summary

After this change, deopt operand bundles can be lowered directly by
SelectionDAG into STATEPOINT instructions (which are then lowered to a
call or sequence of nop, with an associated __llvm_stackmaps entry0.
This obviates the need to round-trip deoptimization state through
gc.statepoint via RewriteStatepointsForGC.

@majnemer: can you please take a look to check that I haven't botched
handling of "funclet" operand bundles?

[sanjoy]

• fix minor typo in assertion message

[reames]

Mostly minor comments. This looks close to ready to go in.

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

2134

add "yet" to comment?

2156–2162

We talked about this offline, but just for the record...

This code is intentionally not handling deopt operands attached to any intrinsic call. Support for @llvm.experimental.deoptimize will follow in another patch and we actively don't want to support deopt on other intrinsics at this time.

I'd add a comment to make that explicit.

6118

It currently looks like we're actually supporting *either* deopt operands XOR funclet operands. I might remove the loop and just assert that nothing other than deopt operands are available on the deopt path.

Same in the other place this loop exist.

lib/CodeGen/SelectionDAG/StatepointLowering.cpp

844

0 as a magic value is unclear. At least pull out a named constant CallSiteArgOperandBegin.

857

Minor code structure: I'd move the default init immediately before each conditional init to make the value flow obvious.

864

Could this be written as:
if (SDValue ReturnVal = LowerAsStatepoint(SI))

Also, minor, I think it would be good to rename LowerAsStatepoint to either LowerAsSTATEPOINT or LowerAsStatepointPseudo. I keep getting the IR and MI uses of the name when reading the new code structure.

test/CodeGen/X86/deopt-bundles.ll

99

Er, this doesn't look like 9 patchable bytes? Am I missing something?

[sanjoy]

test/CodeGen/X86/deopt-bundles.ll

99

I'm only checking the prefix here, to avoid making the test case fragile around non-semantic instruction selection differences. Should I check for a specific nop encoding here instead?

[sanjoy]

• address review

[sanjoy]

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

6118

IIUC we don't need to do anything to lower the funclet operand bundle, so we're trivially lowering both. @majnemer, @rnk -- can you one of you please point out what the right behavior is here?

lib/CodeGen/SelectionDAG/StatepointLowering.cpp

844

Changed it to CS.arg_begin() - CS.op_begin()

857

Changed to use getValueOr.

[sanjoy]

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

6118

Update: I just confirmed the above with @majnemer on IRC

[sanjoy]

Minor fixes:

• CHECK: for a specific kind of nop
• Add a couple of comments

[reames]

LGTM w/minor comments as follow on commits.

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

6118

Minor: introducing a helper function which asserts if any operand bundle types not passed in are present would be a good cleanup. Please do as a separate change.

assert(!hasOperandBundleOtherThan({OB_deopt, OB_funclet});

lib/CodeGen/SelectionDAG/StatepointLowering.cpp

840

minor: I thought you said this could handle funclet?

If so, please add a test case and weaken the assert in a followon patch.

include/llvm/IR/Statepoint.h

 /// RewriteStatepointsForGC and potentially in other passes in the future) can
 /// have attributes that describe properties of gc.statepoint call they will be
 /// eventually be wrapped in.  This struct is used represent such directives.
 struct StatepointDirectives {
   Optional<uint32_t> NumPatchBytes;
   Optional<uint64_t> StatepointID;
 
   static const uint64_t DefaultStatepointID = 0xABCDEF00;
+  static const uint64_t DeoptBundleStatepointID = 0xABCDEF0F;
 };
 
 /// Parse out statepoint directives from the function attributes present in \p
 /// AS.
 StatepointDirectives parseStatepointDirectivesFromAttrs(AttributeSet AS);
 
 /// Return \c true if the the \p Attr is an attribute that is a statepoint
 /// directive.
 bool isStatepointDirectiveAttr(Attribute Attr);
 }
 
 #endif

lib/CodeGen/SelectionDAG/FastISel.cpp

if (!handlePHINodesInSuccessorBlocks(I->getParent())) {
       // PHI node handling may have generated local value instructions,
       // even though it failed to handle all PHI nodes.
       // We remove these instructions because SelectionDAGISel will generate 
       // them again.
       removeDeadLocalValueCode(SavedLastLocalValue);
       return false;
     }
 
+  // FastISel does not handle any operand bundles except OB_funclet.
+  if (ImmutableCallSite CS = ImmutableCallSite(I))
+    for (unsigned i = 0, e = CS.getNumOperandBundles(); i != e; ++i)
+      if (CS.getOperandBundleAt(i).getTagID() != LLVMContext::OB_funclet)
+        return false;
+
   DbgLoc = I->getDebugLoc();
 
   SavedInsertPt = FuncInfo.InsertPt;
 
   if (const auto *Call = dyn_cast<CallInst>(I)) {
     const Function *F = Call->getCalledFunction();
     LibFunc::Func Func;
 

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h

struct StatepointLoweringInfo {
     /// The exception handling unwind destination, in case this represents an
     /// invoke of gc.statepoint.
     const BasicBlock *EHPadBB = nullptr;
 
     explicit StatepointLoweringInfo(SelectionDAG &DAG) : CLI(DAG) {}
   };
 
   /// Lower \p SLI into a STATEPOINT instruction.
-  SDValue LowerAsStatepoint(StatepointLoweringInfo &SLI);
+  SDValue LowerAsSTATEPOINT(StatepointLoweringInfo &SLI);
 
   // This function is responsible for the whole statepoint lowering process.
   // It uniformly handles invoke and call statepoints.
   void LowerStatepoint(ImmutableStatepoint Statepoint,
                        const BasicBlock *EHPadBB = nullptr);
+
+  void LowerCallSiteWithDeoptBundle(ImmutableCallSite CS, SDValue Callee,
+                                    const BasicBlock *EHPadBB);
+
 private:
   // Terminator instructions.
   void visitRet(const ReturnInst &I);
   void visitBr(const BranchInst &I);
   void visitSwitch(const SwitchInst &I);
   void visitIndirectBr(const IndirectBrInst &I);
   void visitUnreachable(const UnreachableInst &I);
   void visitCleanupRet(const CleanupReturnInst &I);

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

 void SelectionDAGBuilder::visitInvoke(const InvokeInst &I) {
   MachineBasicBlock *InvokeMBB = FuncInfo.MBB;
 
   // Retrieve successors. Look through artificial IR level blocks like
   // catchswitch for successors.
   MachineBasicBlock *Return = FuncInfo.MBBMap[I.getSuccessor(0)];
   const BasicBlock *EHPadBB = I.getSuccessor(1);
 
+#ifndef NDEBUG
+  for (unsigned i = 0, e = I.getNumOperandBundles(); i != e; ++i)
+    assert((I.getOperandBundleAt(i).isDeoptOperandBundle() ||
+            I.getOperandBundleAt(i).isFuncletOperandBundle()) &&
+           "Cannot lower invokes with arbitrary operand bundles yet!");
+#endif
+
   const Value *Callee(I.getCalledValue());
   const Function *Fn = dyn_cast<Function>(Callee);
   if (isa<InlineAsm>(Callee))
     visitInlineAsm(&I);
   else if (Fn && Fn->isIntrinsic()) {
     switch (Fn->getIntrinsicID()) {
     default:
       llvm_unreachable("Cannot invoke this intrinsic");
     case Intrinsic::donothing:
       // Ignore invokes to @llvm.donothing: jump directly to the next BB.
       break;
     case Intrinsic::experimental_patchpoint_void:
     case Intrinsic::experimental_patchpoint_i64:
       visitPatchpoint(&I, EHPadBB);
       break;
     case Intrinsic::experimental_gc_statepoint:
       LowerStatepoint(ImmutableStatepoint(&I), EHPadBB);
       break;
     }
-  } else
+  } else if (I.countOperandBundlesOfType(LLVMContext::OB_deopt)) {
+    // Currently we do not lower any intrinsic calls with deopt operand bundles.
+    // Eventually we will support lowering the @llvm.experimental.deoptimize
+    // intrinsic, and right now there are no plans to support other intrinsics
+    // with deopt state.
+    LowerCallSiteWithDeoptBundle(&I, getValue(Callee), EHPadBB);
+  } else {
     LowerCallTo(&I, getValue(Callee), false, EHPadBB);
+  }
 
   // If the value of the invoke is used outside of its defining block, make it
   // available as a virtual register.
   // We already took care of the exported value for the statepoint instruction
   // during call to the LowerStatepoint.
   if (!isStatepoint(I)) {
     CopyToExportRegsIfNeeded(&I);
   }
void SelectionDAGBuilder::visitCall(const CallInst &I) {
   SDValue Callee;
   if (!RenameFn)
     Callee = getValue(I.getCalledValue());
   else
     Callee = DAG.getExternalSymbol(
         RenameFn,
         DAG.getTargetLoweringInfo().getPointerTy(DAG.getDataLayout()));
 
-  // Check if we can potentially perform a tail call. More detailed checking is
-  // be done within LowerCallTo, after more information about the call is known.
+#ifndef NDEBUG
+  for (unsigned i = 0, e = I.getNumOperandBundles(); i != e; ++i)
+    assert((I.getOperandBundleAt(i).isDeoptOperandBundle() ||
+            I.getOperandBundleAt(i).isFuncletOperandBundle()) &&
+           "Cannot lower calls with arbitrary operand bundles!");
+#endif
+
+  if (I.countOperandBundlesOfType(LLVMContext::OB_deopt))
+    LowerCallSiteWithDeoptBundle(&I, Callee, nullptr);
+  else
+    // Check if we can potentially perform a tail call. More detailed checking
+    // is be done within LowerCallTo, after more information about the call is
+    // known.
     LowerCallTo(&I, Callee, I.isTailCall());
 }
 
 namespace {
 
 /// AsmOperandInfo - This contains information for each constraint that we are
 /// lowering.
 class SDISelAsmOperandInfo : public TargetLowering::AsmOperandInfo {
 public:

lib/CodeGen/SelectionDAG/StatepointLowering.cpp

 /// will be set to the last value spilled (if any were).
 static void
 lowerStatepointMetaArgs(SmallVectorImpl<SDValue> &Ops,
                         SelectionDAGBuilder::StatepointLoweringInfo &SI,
                         SelectionDAGBuilder &Builder) {
   // Lower the deopt and gc arguments for this statepoint.  Layout will be:
   // deopt argument length, deopt arguments.., gc arguments...
 #ifndef NDEBUG
+  if (auto *GFI = Builder.GFI) {
     // Check that each of the gc pointer and bases we've gotten out of the
     // safepoint is something the strategy thinks might be a pointer (or vector
     // of pointers) into the GC heap.  This is basically just here to help catch
     // errors during statepoint insertion. TODO: This should actually be in the
     // Verifier, but we can't get to the GCStrategy from there (yet).
-  GCStrategy &S = Builder.GFI->getStrategy();
+    GCStrategy &S = GFI->getStrategy();
     for (const Value *V : SI.Bases) {
       auto Opt = S.isGCManagedPointer(V->getType()->getScalarType());
       if (Opt.hasValue()) {
         assert(Opt.getValue() &&
                "non gc managed base pointer found in statepoint");
       }
     }
     for (const Value *V : SI.Ptrs) {
       auto Opt = S.isGCManagedPointer(V->getType()->getScalarType());
       if (Opt.hasValue()) {
         assert(Opt.getValue() &&
                "non gc managed derived pointer found in statepoint");
       }
     }
+  } else {
+    assert(SI.Bases.empty() && "No gc specified, so cannot relocate pointers!");
+    assert(SI.Ptrs.empty() && "No gc specified, so cannot relocate pointers!");
+  }
 #endif
 
   // Before we actually start lowering (and allocating spill slots for values),
   // reserve any stack slots which we judge to be profitable to reuse for a
   // particular value.  This is purely an optimization over the code below and
   // doesn't change semantics at all.  It is important for performance that we
   // reserve slots for both deopt and gc values before lowering either.
   for (const Value *V : SI.DeoptState) {
if (Loc.getNode()) {
       // export them. Relocates of the spilled values does not use original
       // value.
       if (Relocate->getParent() != StatepointInstr->getParent())
         Builder.ExportFromCurrentBlock(V);
     }
   }
 }
 
-SDValue SelectionDAGBuilder::LowerAsStatepoint(
+SDValue SelectionDAGBuilder::LowerAsSTATEPOINT(
     SelectionDAGBuilder::StatepointLoweringInfo &SI) {
   // The basic scheme here is that information about both the original call and
   // the safepoint is encoded in the CallInst.  We create a temporary call and
   // lower it, then reverse engineer the calling sequence.
 
   NumOfStatepoints++;
   // Clear state
   StatepointLowering.startNewStatepoint(*this);
#endif
   SI.GCTransitionArgs =
       ArrayRef<const Use>(ISP.gc_args_begin(), ISP.gc_args_end());
   SI.ID = ISP.getID();
   SI.DeoptState = ArrayRef<const Use>(ISP.vm_state_begin(), ISP.vm_state_end());
   SI.StatepointFlags = ISP.getFlags();
   SI.NumPatchBytes = ISP.getNumPatchBytes();
   SI.EHPadBB = EHPadBB;
 
-  SDValue ReturnValue = LowerAsStatepoint(SI);
+  SDValue ReturnValue = LowerAsSTATEPOINT(SI);
 
   // Export the result value if needed
   const Instruction *GCResult = ISP.getGCResult();
   Type *RetTy = ISP.getActualReturnType();
   if (!RetTy->isVoidTy() && GCResult) {
     if (GCResult->getParent() != ISP.getCallSite().getParent()) {
       // Result value will be used in a different basic block so we need to
       // export it now.  Default exporting mechanism will not work here because
if (GCResult->getParent() != ISP.getCallSite().getParent()) {
       setValue(ISP.getInstruction(), ReturnValue);
     }
   } else {
     // The token value is never used from here on, just generate a poison value
     setValue(ISP.getInstruction(), DAG.getIntPtrConstant(-1, getCurSDLoc()));
   }
 }
 
+void SelectionDAGBuilder::LowerCallSiteWithDeoptBundle(
+    ImmutableCallSite CS, SDValue Callee, const BasicBlock *EHPadBB) {
+  assert(CS.getNumOperandBundles() == 1 &&
+         "Only deopt operand bundles can be lowered!");
+
+  StatepointLoweringInfo SI(DAG);
+  unsigned ArgBeginIndex = CS.arg_begin() - CS.getInstruction()->op_begin();
+  populateCallLoweringInfo(SI.CLI, CS, ArgBeginIndex, CS.getNumArgOperands(),
+                           Callee, CS.getType(), false);
+
+  auto DeoptBundle = CS.getOperandBundleAt(0);
+  assert(DeoptBundle.getTagID() == LLVMContext::OB_deopt && "Should be!");
+
+  unsigned DefaultID = StatepointDirectives::DeoptBundleStatepointID;
+
+  auto SD = parseStatepointDirectivesFromAttrs(CS.getAttributes());
+  SI.ID = SD.StatepointID.getValueOr(DefaultID);
+  SI.NumPatchBytes = SD.NumPatchBytes.getValueOr(0);
+
+  SI.DeoptState =
+      ArrayRef<const Use>(DeoptBundle.Inputs.begin(), DeoptBundle.Inputs.end());
+  SI.StatepointFlags = static_cast<uint64_t>(StatepointFlags::None);
+  SI.EHPadBB = EHPadBB;
+
+  if (SDValue ReturnVal = LowerAsSTATEPOINT(SI)) {
+    const Instruction *Inst = CS.getInstruction();
+    ReturnVal = lowerRangeToAssertZExt(DAG, *Inst, ReturnVal);
+    setValue(Inst, ReturnVal);
+  }
+}
+
 void SelectionDAGBuilder::visitGCResult(const CallInst &CI) {
   // The result value of the gc_result is simply the result of the actual
   // call.  We've already emitted this, so just grab the value.
   Instruction *I = cast<Instruction>(CI.getArgOperand(0));
   assert(isStatepoint(I) && "first argument must be a statepoint token");
 
   if (I->getParent() != CI.getParent()) {
     // Statepoint is in different basic block so we should have stored call

test/CodeGen/X86/deopt-bundles.ll

+; RUN: llc -debug-only=stackmaps     < %s 2>&1 | FileCheck %s
+; RUN: llc -debug-only=stackmaps -O3 < %s 2>&1 | FileCheck %s
+; REQUIRES: asserts
+
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.11.0"
+
+
+; CHECK: Stack Maps: callsite 2882400015
+; CHECK-NEXT: Stack Maps:   has 4 locations
+; CHECK-NEXT: Stack Maps:     Loc 0: Constant 0 [encoding: .byte 4, .byte 8, .short 0, .int 0]
+; CHECK-NEXT: Stack Maps:     Loc 1: Constant 0 [encoding: .byte 4, .byte 8, .short 0, .int 0]
+; CHECK-NEXT: Stack Maps:     Loc 2: Constant 1 [encoding: .byte 4, .byte 8, .short 0, .int 1]
+; CHECK-NEXT: Stack Maps:     Loc 3: Constant 0 [encoding: .byte 4, .byte 8, .short 0, .int 0]
+; CHECK-NEXT: Stack Maps:   has 0 live-out registers
+; CHECK-NEXT: Stack Maps: callsite 4242
+; CHECK-NEXT: Stack Maps:   has 4 locations
+; CHECK-NEXT: Stack Maps:     Loc 0: Constant 0 [encoding: .byte 4, .byte 8, .short 0, .int 0]
+; CHECK-NEXT: Stack Maps:     Loc 1: Constant 0 [encoding: .byte 4, .byte 8, .short 0, .int 0]
+; CHECK-NEXT: Stack Maps:     Loc 2: Constant 1 [encoding: .byte 4, .byte 8, .short 0, .int 1]
+; CHECK-NEXT: Stack Maps:     Loc 3: Constant 1 [encoding: .byte 4, .byte 8, .short 0, .int 1]
+; CHECK-NEXT: Stack Maps:   has 0 live-out registers
+; CHECK-NEXT: Stack Maps: callsite 2882400015
+; CHECK-NEXT: Stack Maps:   has 4 locations
+; CHECK-NEXT: Stack Maps:     Loc 0: Constant 0 [encoding: .byte 4, .byte 8, .short 0, .int 0]
+; CHECK-NEXT: Stack Maps:     Loc 1: Constant 0 [encoding: .byte 4, .byte 8, .short 0, .int 0]
+; CHECK-NEXT: Stack Maps:     Loc 2: Constant 1 [encoding: .byte 4, .byte 8, .short 0, .int 1]
+; CHECK-NEXT: Stack Maps:     Loc 3: Constant 2 [encoding: .byte 4, .byte 8, .short 0, .int 2]
+; CHECK-NEXT: Stack Maps:   has 0 live-out registers
+; CHECK-NEXT: Stack Maps: callsite 2882400015
+; CHECK-NEXT: Stack Maps:   has 4 locations
+; CHECK-NEXT: Stack Maps:     Loc 0: Constant 0 [encoding: .byte 4, .byte 8, .short 0, .int 0]
+; CHECK-NEXT: Stack Maps:     Loc 1: Constant 0 [encoding: .byte 4, .byte 8, .short 0, .int 0]
+; CHECK-NEXT: Stack Maps:     Loc 2: Constant 1 [encoding: .byte 4, .byte 8, .short 0, .int 1]
+; CHECK-NEXT: Stack Maps:     Loc 3: Constant 3 [encoding: .byte 4, .byte 8, .short 0, .int 3]
+; CHECK-NEXT: Stack Maps:   has 0 live-out registers
+
+
+declare i32 @callee_0()
+declare i32 @callee_1(i32)
+
+define i32 @caller_0() {
+; CHECK-LABEL: _caller_0
+entry:
+  %v = call i32 @callee_0() [ "deopt"(i32 0) ]
+  %v2 = add i32 %v, 1
+  ret i32 %v2
+; CHECK:  callq _callee_0
+; CHECK:  incl  %eax
+; CHECK:  retq
+}
+
+define i32 @caller_1() {
+; CHECK-LABEL: _caller_1
+entry:
+  %v = call i32 @callee_1(i32 42) "statepoint-id"="4242" [ "deopt"(i32 1) ]
+  ret i32 %v
+; CHECK:  callq _callee_1
+; CHECK:  popq  %rcx
+; CHECK:  retq
+}
+
+define i32 @invoker_0() personality i8 0 {
+; CHECK-LABEL: _invoker_0
+entry:
+  %v = invoke i32 @callee_0() [ "deopt"(i32 2) ]
+          to label %normal unwind label %uw
+
+normal:
+  ret i32 %v
+
+uw:
+  %ehvals = landingpad { i8*, i32 }
+      cleanup
+  ret i32 1
+; CHECK:  callq _callee_0
+; CHECK:  popq  %rcx
+; CHECK:  retq
+; CHECK:  movl  $1, %eax
+; CHECK:  popq  %rcx
+; CHECK:  retq
+}
+
+define i32 @invoker_1() personality i8 0 {
+; CHECK-LABEL: _invoker_1
+entry:
+  %v = invoke i32 @callee_1(i32 45) "statepoint-num-patch-bytes"="9" [ "deopt"(i32 3) ]
+          to label %normal unwind label %uw
+
+normal:
+  ret i32 %v
+
+uw:
+  %ehvals = landingpad { i8*, i32 }
+      cleanup
+  ret i32 1
+; CHECK:  movl  $45, %edi
+; CHECK:  nop
+; CHECK:  popq  %rcx
+; CHECK:  retq
+; CHECK:  movl  $1, %eax
+; CHECK:  popq  %rcx
+; CHECK:  retq
+}