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 ↗

(On Diff #50991)

add "yet" to comment?

2156 ↗

(On Diff #50991)

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.

6114 ↗

(On Diff #50991)

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 ↗

(On Diff #50991)

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

857 ↗

(On Diff #50991)

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

864 ↗

(On Diff #50991)

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

98 ↗

(On Diff #50991)

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

[sanjoy]

test/CodeGen/X86/deopt-bundles.ll

98 ↗

(On Diff #50991)

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

6114 ↗

(On Diff #50991)

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 ↗

(On Diff #50991)

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

857 ↗

(On Diff #50991)

Changed to use getValueOr.

[sanjoy]

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

6118 ↗

(On Diff #51096)

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

6120 ↗

(On Diff #51202)

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 ↗

(On Diff #51202)

minor: I thought you said this could handle funclet?

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

llvm/trunk/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

llvm/trunk/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;
 

llvm/trunk/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);

llvm/trunk/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
+  // Deopt bundles are lowered in LowerCallSiteWithDeoptBundle, and we don't
+  // have to do anything here to lower funclet bundles.
+  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
+  // Deopt bundles are lowered in LowerCallSiteWithDeoptBundle, and we don't
+  // have to do anything here to lower funclet bundles.
+  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:

llvm/trunk/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

llvm/trunk/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:  nopw    512(%rax,%rax)
+; CHECK:  popq  %rcx
+; CHECK:  retq
+; CHECK:  movl  $1, %eax
+; CHECK:  popq  %rcx
+; CHECK:  retq
+}