Lower invoke statepoints and gc.results tied to them.

[igor-laevsky]

Summary

This change builds up on http://reviews.llvm.org/D7756

It teaches lowering to correctly handle invoke statepoint and gc results tied to them. Note that we still can not lower gc.results for invoke statepoints.
Also it extracts getCopyFromRegs helper function in SelectionDAGBuilder as we need to be able to customize type of the register exported from basic block during lowering of gc.result.

[reames]

Comments inline.

You need tests for this.

Also, your code appears to have handling for gc.result even though your description says that's not handled. Which is it?

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

1048 ↗

(On Diff #20296)

I'm a bit uncomfortable signing off on this part of the change since I'm unfamiliar with the details of the codepath. I'll ask that you wait for a signoff from someone more familiar with SelectionDAG as a whole.

lib/CodeGen/SelectionDAG/StatepointLowering.cpp

257 ↗

(On Diff #20296)

I'm still confused about why we need this. Why doesn't the standard export mechanism work here? Simply producing the value and letting it be exported normally seems like it would work?

297 ↗

(On Diff #20296)

Just to be clear, the reason for this is that CallEnd might start with the eh_label which doesn't have a glue node?

669 ↗

(On Diff #20296)

Doesn't this depend on what SDValue we set for a specific instruction? As above, I'm not convinced this is necessary.

Also, CamelCase naming per llvm docs.

[igor-laevsky]

In D7760#126890, @reames wrote:

Also, your code appears to have handling for gc.result even though your description says that's not handled. Which is it?

Sorry I meant that we can not handle gc.relocates.

[igor-laevsky]

In D7760#126890, @reames wrote:

Comments inline.

lib/CodeGen/SelectionDAG/StatepointLowering.cpp

257 ↗

(On Diff #20296)

Main problem here is that value we want to export is 'Tmp' which will be deleted few lines later. Therefore we need to export statepoint call itself, but it has different type than the actual call. Default mechanism for exporting values from BasicBlock calculates type of the register from Value* we are trying to export. So we need to create register with correct type manually.

This probably could be wrapped in a helper function or an overload of a 'ExportFromCurrentBlock(Value*)' but it's the only place such problem appears so probably not worth it.

I have added comment describing this.

297 ↗

(On Diff #20296)

Yes. DAG root will be eh_label in case of invoke and it will not have glued nodes.

669 ↗

(On Diff #20296)

SDValue is live only during processing of a single BasicBlock. We are exporting llvm-ir Value's. And in our case statepoint value has different type than the actual lowered call. This is same problem as in lowerCallFromStatepoint.

[reames]

Summary of offline conversation.

lib/CodeGen/SelectionDAG/StatepointLowering.cpp

257 ↗

(On Diff #20296)

Igor and I talked about this a bit offline. We realized that the heart of the issue here is that we need to export a value whose type does not match the type of the instruction it's associated with. This is a "feature" unique to gc.statepoint.

We think the same issue can be replicated with:

%token = call i32 gc.statepoint....
br label %next

next:

%res = call float gc.result(%token)

Igor is going to investigate and see what it would take to have the export mechanism just handle this case directly.

An alternate approach would be to remove gc.result entirely and just use the result value (if there is one) as the token for gc.result. We could introduce an artificial i32 return when the underlying function has a void return. This may be a better long term approach, but is more churn than we'd prefer right now.

[igor-laevsky]

After a bit of investigation and discussions offline it seems like extending current export mechanism to support statepoints is a bit unreasonable. We will need to add hooks in form of:

Type *t;
if (isStatepoint(I))
  t = <underlying call type>
else
  t = <normal type>

In three places:

1. During InitializeRegForValue in FunctionLowering.
2. Create correct CopyToReg in CopyValueToVirtualRegister in SelectionDAGBuilder
3. Create correct CopyFromReg in getValue in SelectionDAGBuilder

This is more invasive compared to the current approach which is just trivial refactoring in SelectionDAGBuilder.
Also this isStatepoint hooks will seem inappropriate in general handling mechanism. Maybe someday when and if there will be more instructions with such problem we will be able to extract common property from them and use it in this checks.

Another approach would be to remove gc.results completely as Philip stated. However this is a bit more work not directly related to this change. I will add TODO concerning this.

[reames]

You need to add a test.

Once mentioned changes are made, should be good for submission. I would prefer one more updated diff just for an official LGTM.

lib/CodeGen/SelectionDAG/StatepointLowering.cpp

258 ↗

(On Diff #20410)

Given our discussion, this comment is wrong and misleading. It's not the fact that "Tmp" is deleted, it's the fact that the type will not match. Please update.

672 ↗

(On Diff #20410)

CalleeType per llvm style. Same with others.

[igor-laevsky]

lib/CodeGen/SelectionDAG/StatepointLowering.cpp

258 ↗

(On Diff #20410)

It depends on the view point. For 'Tmp' types actually match. So we can look at the problem either as standart mechanism not knowing about statepoints or as our inability to export correct Value*. Anyway it is probably unnecessary details, I updated the comment.

[igor-laevsky]

And the complete test will follow up in the next change - http://reviews.llvm.org/D7798

[reames]

Igor, my comment about a test was not optional. You can and must test this. A couple of simple invoke tests without relocations should work after this change. Or am I misunderstanding something?

[igor-laevsky]

I didn't add code to actually call lowering for invoke statepoints in this change. I was posponing it until the next change (http://reviews.llvm.org/D7798). But anyway I have updated the diff and added a test.

[reames]

LGTM once test case comments are addressed. You can submit once that's done without further review.

test/CodeGen/X86/statepoint-invoke.ll

1 ↗

(On Diff #21228)

Add a target triple.

9 ↗

(On Diff #21228)

My experience has been that using labels like this will be a bit fragile. You should consider using something easier to match on like a call to dummy function.

(Alternatively, you could use FileCheck variables.)

[sanjoy]

Minor comments inline.

llvm/trunk/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

1030

LLVM Coding style is to use CamelCase starting with a upper case letter -- please change res to Result or something like that.

llvm/trunk/lib/CodeGen/SelectionDAG/StatepointLowering.cpp

672

The spacing here looks weird -- can you please run this bit through clang-format?

llvm/trunk/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h

public:
   unsigned getSDNodeOrder() const { return SDNodeOrder; }
 
   void CopyValueToVirtualRegister(const Value *V, unsigned Reg);
 
   void visit(const Instruction &I);
 
   void visit(unsigned Opcode, const User &I);
 
+  /// getCopyFromRegs - If there was virtual register allocated for the value V
+  /// emit CopyFromReg of the specified type Ty. Return empty SDValue() otherwise.
+  SDValue getCopyFromRegs(const Value *V, Type *Ty);
+
   // resolveDanglingDebugInfo - if we saw an earlier dbg_value referring to V,
   // generate the debug data structures now that we've seen its definition.
   void resolveDanglingDebugInfo(const Value *V, SDValue Val);
   SDValue getValue(const Value *V);
   SDValue getNonRegisterValue(const Value *V);
   SDValue getValueImpl(const Value *V);
 
   void setValue(const Value *V, SDValue NewN) {
std::pair<SDValue, SDValue> lowerCallOperands(
           MachineBasicBlock *LandingPad = nullptr,
           bool IsPatchPoint = false);
 
   /// UpdateSplitBlock - When an MBB was split during scheduling, update the
   /// references that need to refer to the last resulting block.
   void UpdateSplitBlock(MachineBasicBlock *First, MachineBasicBlock *Last);
 
   // This function is responsible for the whole statepoint lowering process.
-  void LowerStatepoint(ImmutableStatepoint Statepoint);
+  // It uniformly handles invoke and call statepoints.
+  void LowerStatepoint(ImmutableStatepoint Statepoint,
+                       MachineBasicBlock *LandingPad = nullptr);
 private:
   std::pair<SDValue, SDValue> lowerInvokable(
           TargetLowering::CallLoweringInfo &CLI,
           MachineBasicBlock *LandingPad);
 
   // Terminator instructions.
   void visitRet(const ReturnInst &I);
   void visitBr(const BranchInst &I);

llvm/trunk/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

if (Val.getNode()) {
         DAG.AddDbgValue(SDV, Val.getNode(), false);
       }
     } else
       DEBUG(dbgs() << "Dropping debug info for " << *DI << "\n");
     DanglingDebugInfoMap[V] = DanglingDebugInfo();
   }
 }
 
+/// getCopyFromRegs - If there was virtual register allocated for the value V
+/// emit CopyFromReg of the specified type Ty. Return empty SDValue() otherwise.
+SDValue SelectionDAGBuilder::getCopyFromRegs(const Value *V, Type *Ty) {
+  DenseMap<const Value *, unsigned>::iterator It = FuncInfo.ValueMap.find(V);
+  SDValue res;
+
+  if (It != FuncInfo.ValueMap.end()) {
+    unsigned InReg = It->second;
+    RegsForValue RFV(*DAG.getContext(), DAG.getTargetLoweringInfo(), InReg,
+                     Ty);
+    SDValue Chain = DAG.getEntryNode();
+    res = RFV.getCopyFromRegs(DAG, FuncInfo, getCurSDLoc(), Chain, nullptr, V);
+    resolveDanglingDebugInfo(V, res);
+  }
+
+  return res;
+}
+
 /// getValue - Return an SDValue for the given Value.
 SDValue SelectionDAGBuilder::getValue(const Value *V) {
   // If we already have an SDValue for this value, use it. It's important
   // to do this first, so that we don't create a CopyFromReg if we already
   // have a regular SDValue.
   SDValue &N = NodeMap[V];
   if (N.getNode()) return N;
 
   // If there's a virtual register allocated and initialized for this
   // value, use it.
-  DenseMap<const Value *, unsigned>::iterator It = FuncInfo.ValueMap.find(V);
-  if (It != FuncInfo.ValueMap.end()) {
-    unsigned InReg = It->second;
-    RegsForValue RFV(*DAG.getContext(), DAG.getTargetLoweringInfo(), InReg,
-                     V->getType());
-    SDValue Chain = DAG.getEntryNode();
-    N = RFV.getCopyFromRegs(DAG, FuncInfo, getCurSDLoc(), Chain, nullptr, V);
-    resolveDanglingDebugInfo(V, N);
-    return N;
+  SDValue copyFromReg = getCopyFromRegs(V, V->getType());
+  if (copyFromReg.getNode()) {
+    return copyFromReg;
   }
 
   // Otherwise create a new SDValue and remember it.
   SDValue Val = getValueImpl(V);
   NodeMap[V] = Val;
   resolveDanglingDebugInfo(V, Val);
   return Val;
 }
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, LandingPad);
       break;
+    case Intrinsic::experimental_gc_statepoint:
+      LowerStatepoint(ImmutableStatepoint(&I), LandingPad);
+      break;
     }
   } else
     LowerCallTo(&I, getValue(Callee), false, LandingPad);
 
   // 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);
+  }
 
   // Update successor info
   addSuccessorWithWeight(InvokeMBB, Return);
   addSuccessorWithWeight(InvokeMBB, LandingPad);
 
   // Drop into normal successor.
   DAG.setRoot(DAG.getNode(ISD::BR, getCurSDLoc(),
                           MVT::Other, getControlRoot(),

llvm/trunk/lib/CodeGen/SelectionDAG/StatepointLowering.cpp

static void removeDuplicatesGCPtrs(SmallVectorImpl<const Value *> &Bases,
   assert(Ptrs.size() == Bases.size());
   assert(Ptrs.size() == Relocs.size());
 }
 
 /// Extract call from statepoint, lower it and return pointer to the
 /// call node. Also update NodeMap so that getValue(statepoint) will
 /// reference lowered call result
 static SDNode *lowerCallFromStatepoint(ImmutableStatepoint StatepointSite,
+                                       MachineBasicBlock *LandingPad,
                                        SelectionDAGBuilder &Builder) {
 
   ImmutableCallSite CS(StatepointSite.getCallSite());
 
   // Lower the actual call itself - This is a bit of a hack, but we want to
   // avoid modifying the actual lowering code.  This is similiar in intent to
   // the LowerCallOperands mechanism used by PATCHPOINT, but is structured
   // differently.  Hopefully, this is slightly more robust w.r.t. calling
   // convention, return values, and other function attributes.
   Value *ActualCallee = const_cast<Value *>(StatepointSite.actualCallee());
 
   std::vector<Value *> Args;
   CallInst::const_op_iterator arg_begin = StatepointSite.call_args_begin();
   CallInst::const_op_iterator arg_end = StatepointSite.call_args_end();
   Args.insert(Args.end(), arg_begin, arg_end);
   // TODO: remove the creation of a new instruction!  We should not be
   // modifying the IR (even temporarily) at this point.
   CallInst *Tmp = CallInst::Create(ActualCallee, Args);
   Tmp->setTailCall(CS.isTailCall());
   Tmp->setCallingConv(CS.getCallingConv());
   Tmp->setAttributes(CS.getAttributes());
-  Builder.LowerCallTo(Tmp, Builder.getValue(ActualCallee), false);
+  Builder.LowerCallTo(Tmp, Builder.getValue(ActualCallee), false, LandingPad);
 
   // Handle the return value of the call iff any.
   const bool HasDef = !Tmp->getType()->isVoidTy();
   if (HasDef) {
+    if (CS.isInvoke()) {
+      // Result value will be used in different basic block for invokes
+      // so we need to export it now. But statepoint call has a different type
+      // than the actuall call. It means that standart exporting mechanism will
+      // create register of the wrong type. So instead we need to create
+      // register with correct type and save value into it manually.
+      // TODO: To eliminate this problem we can remove gc.result intrinsics
+      //       completelly and make statepoint call to return a tuple.
+      unsigned reg = Builder.FuncInfo.CreateRegs(Tmp->getType());
+      Builder.CopyValueToVirtualRegister(Tmp, reg);
+      Builder.FuncInfo.ValueMap[CS.getInstruction()] = reg;
+    }
+    else {
       // The value of the statepoint itself will be the value of call itself.
       // We'll replace the actually call node shortly.  gc_result will grab
       // this value.
       Builder.setValue(CS.getInstruction(), Builder.getValue(Tmp));
+    }
   } else {
     // The token value is never used from here on, just generate a poison value
     Builder.setValue(CS.getInstruction(), Builder.DAG.getIntPtrConstant(-1));
   }
   // Remove the fake entry we created so we don't have a hanging reference
   // after we delete this node.
   Builder.removeValue(Tmp);
   delete Tmp;
   Tmp = nullptr;
 
   // Search for the call node
   // The following code is essentially reverse engineering X86's
   // LowerCallTo.
+  // We are expecting DAG to have the following form:
+  // ch = eh_label (only in case of invoke statepoint)
+  //   ch, glue = callseq_start ch
+  //   ch, glue = X86::Call ch, glue
+  //   ch, glue = callseq_end ch, glue
+  // ch = eh_label ch (only in case of invoke statepoint)
+  //
+  // DAG root will be either last eh_label or callseq_end.
+    
   SDNode *CallNode = nullptr;
 
   // We just emitted a call, so it should be last thing generated
   SDValue Chain = Builder.DAG.getRoot();
 
   // Find closest CALLSEQ_END walking back through lowered nodes if needed
   SDNode *CallEnd = Chain.getNode();
   int Sanity = 0;
   while (CallEnd->getOpcode() != ISD::CALLSEQ_END) {
-    CallEnd = CallEnd->getGluedNode();
-    assert(CallEnd && "Can not find call node");
+    assert(CallEnd->getNumOperands() >= 1 &&
+           CallEnd->getOperand(0).getValueType() == MVT::Other);
+
+    CallEnd = CallEnd->getOperand(0).getNode();
+
     assert(Sanity < 20 && "should have found call end already");
     Sanity++;
   }
   assert(CallEnd->getOpcode() == ISD::CALLSEQ_END &&
          "Expected a callseq node.");
   assert(CallEnd->getGluedNode());
 
   // Step back inside the CALLSEQ

 void SelectionDAGBuilder::visitStatepoint(const CallInst &CI) {
   // Check some preconditions for sanity
   assert(isStatepoint(&CI) &&
          "function called must be the statepoint function");
 
   LowerStatepoint(ImmutableStatepoint(&CI));
 }
 
-void SelectionDAGBuilder::LowerStatepoint(ImmutableStatepoint ISP) {
+void
+SelectionDAGBuilder::LowerStatepoint(ImmutableStatepoint ISP,
+                                     MachineBasicBlock *LandingPad/*=nullptr*/) {
   // 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);
 
#ifndef NDEBUG
   // to be optional for backwards compatibility.  This will only last a short
   // period (i.e. a couple of weeks).
   if (GFI) {
     assert(GFI->getStrategy().useStatepoints() &&
            "GCStrategy does not expect to encounter statepoints");
   }
 #endif
 
-
   // Lower statepoint vmstate and gcstate arguments
   SmallVector<SDValue, 10> LoweredArgs;
   lowerStatepointMetaArgs(LoweredArgs, ISP, *this);
 
   // Get call node, we will replace it later with statepoint
-  SDNode *CallNode = lowerCallFromStatepoint(ISP, *this);
+  SDNode *CallNode = lowerCallFromStatepoint(ISP, LandingPad, *this);
 
   // Construct the actual STATEPOINT node with all the appropriate arguments
   // and return values.
 
   // TODO: Currently, all of these operands are being marked as read/write in
   // PrologEpilougeInserter.cpp, we should special case the VMState arguments
   // and flags to be read-only.
   SmallVector<SDValue, 40> Ops;

 
 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 (isa<InvokeInst>(I)) {
+    // For invokes we should have stored call result in a virtual register.
+    // We can not use default getValue() functionality to copy value from this
+    // register because statepoint and actuall call return types can be
+    // different, and getValue() will use CopyFromReg of the wrong type,
+    // which is always i32 in our case.
+    PointerType *CalleeType = cast<PointerType>(
+                                ImmutableStatepoint(I).actualCallee()->getType());
+    Type *RetTy = cast<FunctionType>(
+                                CalleeType->getElementType())->getReturnType();
+    SDValue CopyFromReg = getCopyFromRegs(I, RetTy);
+
+    assert(CopyFromReg.getNode());
+    setValue(&CI, CopyFromReg);
+  }
+  else {
     setValue(&CI, getValue(I));
   }
+}
 
 void SelectionDAGBuilder::visitGCRelocate(const CallInst &CI) {
 #ifndef NDEBUG
   // Consistency check
   StatepointLowering.relocCallVisited(CI);
 #endif
 
   GCRelocateOperands relocateOpers(&CI);

llvm/trunk/test/CodeGen/X86/statepoint-invoke.ll

+; RUN: llc < %s 2>&1 | FileCheck %s
+
+target triple = "x86_64-pc-linux-gnu"
+
+declare i64 addrspace(1)* @"some_other_call"(i64 addrspace(1)*)
+
+declare i32 @"personality_function"()
+
+define i64 addrspace(1)* @test_result(i64 addrspace(1)* %obj, i64 addrspace(1)* %obj1) {
+entry:
+  ; CHECK: .Ltmp{{[0-9]+}}:
+  ; CHECK: callq some_other_call
+  ; CHECK: .Ltmp{{[0-9]+}}:
+  %0 = invoke i32 (i64 addrspace(1)* (i64 addrspace(1)*)*, i32, i32, ...)* @llvm.experimental.gc.statepoint.p0f_p1i64p1i64f(i64 addrspace(1)* (i64 addrspace(1)*)* @some_other_call, i32 1, i32 0, i64 addrspace(1)* %obj, i32 5, i32 0, i32 -1, i32 0, i32 0, i32 0, i64 addrspace(1)* %obj, i64 addrspace(1)* %obj1)
+          to label %normal_return unwind label %exceptional_return
+
+normal_return:
+  ; CHECK: popq 
+  ; CHECK: retq
+  %ret_val = call i64 addrspace(1)* @llvm.experimental.gc.result.p1i64(i32 %0)
+  ret i64 addrspace(1)* %ret_val
+
+exceptional_return:
+  ; CHECK: .Ltmp{{[0-9]+}}:
+  ; CHECK: popq
+  ; CHECK: retq
+  %landing_pad = landingpad { i8*, i32 } personality i32 ()* @personality_function
+          cleanup
+  ret i64 addrspace(1)* %obj
+}
+; CHECK-LABEL: GCC_except_table{{[0-9]+}}:
+; CHECK: .long .Ltmp{{[0-9]+}}-.Ltmp{{[0-9]+}}
+; CHECK: .long .Ltmp{{[0-9]+}}-.Lfunc_begin{{[0-9]+}}
+; CHECK: .byte 0
+; CHECK: .align 4
+
+declare i32 @llvm.experimental.gc.statepoint.p0f_p1i64p1i64f(i64 addrspace(1)* (i64 addrspace(1)*)*, i32, i32, ...)
+declare i64 addrspace(1)* @llvm.experimental.gc.result.p1i64(i32)