[NVPTX] Allow to make libcalls that are defined in the current module.

[denzp]

Summary

The patch adds a possibility to make library calls.
An important thing about library functions - they must be defined within the current module. This basically should guarantee that we produce a valid PTX assembly (without calls to not defined functions). The one who wants to use the libcalls is probably will have to link against compiler-rt or any other implementation.

Currently, it's completely impossible to make library calls because of error LLVM ERROR: Cannot select: i32 = ExternalSymbol '...'. But we can lower ExternalSymbol to TargetExternalSymbol and verify if the function definition is available.

Also, there was an issue with a DAG during legalisation. When we expand instruction into libcall, the inner call-chain isn't being "integrated" into outer chain. Since the last "data-flow" (call retval load) node is located in call-chain earlier than CALLSEQ_END node, the latter becomes a leaf and therefore a dead node (and is being removed quite fast). Proposed here solution relies on another data-flow pseudo nodes (ProxyReg) which purpose is only to keep CALLSEQ_END at legalisation and instruction selection phases - we remove the pseudo instructions before register scheduling phase.

[jlebar]

It's been a while since I've looked at this code, so forgive me, but isn't there a big file somewhere that lists which libcalls each target supports? Is LLVM going to be unhappy with us if sometimes NVPTX allows libcalls and sometimes it doesn't?

[arsenm]

This is something I've thought about doing before. Does this work with the TLI lib call simplification as is, and this is the only required codegen part?

lib/Target/NVPTX/NVPTXISelLowering.cpp

1841–1848

This is probably the wrong way to do this. You probably want to do a getMergeValues with the returned value and the entry chain

2313–2315

Can you move this to generic DAG code?

[denzp]

In D34708#792747, @jlebar wrote:

It's been a while since I've looked at this code, so forgive me, but isn't there a big file somewhere that lists which libcalls each target supports? Is LLVM going to be unhappy with us if sometimes NVPTX allows libcalls and sometimes it doesn't?

Depending on "operation action" some instructions are legal and some are not for the target. Illegal instructions should be expanded into other (probably legal ones) or lowered to libcalls. For example, for i128 values %a = mul i128 %0, %1 can be expanded into sequence of mul.lo and mul.hi instructions, but %a = sdiv i128 %0, %1 can only be lowered into libcall to __divti3. And without patch it's completely impossible to perform sdiv i128. But now users are able to do it when they provide __divti3 implementation.

And also some targets has restrictions on libcalls, disabling some of them. But in our case, we don't have any runtime lib (don't we?) so it's up to a user to define the implementations.

[denzp]

In D34708#792791, @arsenm wrote:

This is something I've thought about doing before. Does this work with the TLI lib call simplification as is, and this is the only required codegen part?

As far as I understood, we can make libcall either with:

• TargetLowering::makeLibCall
• SelectionDAGLegalize::ExpandLibCall

And I both should work. I'm going to add one more test case for TargetLowering::makeLibCall path.

lib/Target/NVPTX/NVPTXISelLowering.cpp

1841–1848

Thanks, it's a good idea and a right way. But... we are still losing reference during legalization:

Legalizing: t28: f64,ch = merge_values t25, t27
t28: f64,ch = merge_values t25, t27 ... replacing: t28: f64,ch = merge_values t25, t27
     with:      t25: f64,ch,glue = NVPTXISD::LoadParam<LD8[<unknown>]> t24, Constant:i32<1>, Constant:i32<0>, t24:1
      and:      t27: ch,glue = callseq_end t25:1, TargetConstant:i32<0>, TargetConstant:i32<1>, t25:2

Unfortunately, nobody is referencing t27 and it's being removed as a dead node.

2313–2315

It has quite specific for NVPTX logic, usually other backends don't have restrictions on presence of function definition in current module. Are there another use cases for this?

[tra]

lib/Target/NVPTX/NVPTXISelLowering.cpp

1314–1315

Nit. these should be on the same line.

1631–1632

I'd move it down to where isIndirectCall is used.

Also, I'd rephrase the comment along the lines of

Both indirect calls and libcalls have nullptr Func. In order to distinguish between them we must rely on the call site value which is valid for indirect calls but is always null for libcalls.

I wonder if there's any way to explicitly mark the call as libcall, so we don't have to rely on callsite for that.

1841–1848

I guess we could modify NVPTXISD::StoreRetval so it takes additional 'glue' argument and explicitly make it depend on glue returned by callseq_end. Perhaps in a separate patch.

[denzp]

My apologies, it has been a while since the revision was created. I've finally changed the approach - from a hack with keeping a reference to a CALLSEQ_END to a better one (at least by a personal feeling) with pseudo instructions to keep the nodes alive. The summary was changed to reflect the current approach. Also, the code is rebased on top of the fresh source tree.

[arsenm]

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

7294

This needs to preserve the address space of the function

[denzp]

@arsenm thanks for pointing out. Is this the right way to do it?
TLI->getPointerTy(getDataLayout(), Function->getAddressSpace());

[tra]

You probably want to remove libcalls.patch from the patch diff.

lib/Target/NVPTX/NVPTXInstrInfo.td

2257–2258 ↗

(On Diff #178748)

If we ever get here, I think correct asm to generate here should be a move from one register to another.

If we do not expect ProxyReg to ever make it to this point, then we should make the error visible. E.g. fail to lower ProxyReg at all which will cause llvm error.

test/CodeGen/NVPTX/libcall-instruction.ll

2 ↗

(On Diff #178748)

Typo/grammar nits:
asse*r*tion
a*n* "Undefined..." (same issue in in the libcall-intrinsic.ll)

[denzp]

@tra Thank you, I've addressed the mentioned issues.

You are right, the implementation is more reliable when ProxyReg produces a correct PTX assembly even when it's still present.

Also, I noticed missing function declarations for libcall implementors. I didn't find a common way how to dynamically add "usage" to implementors, so I ended up assigning nvptx-libcall-callee attribute and then forcefully emitting declarations in NVPTXAsmPrinter.

[tra]

The tests you have only check the end result and do not directly verify the new functionality the patch adds.

Ideally, it would be great if we could verify that your changes that add and remove RegProxy do the right thing.
Could you check if it would make sense to add couple of MIR tests: https://llvm.org/docs/MIRLangRef.html#testing-individual-code-generation-passes

I can think of three interesting tests:

• verify that RegProxy is inserted in the right places.
• verify that RegProxy gets removed by NVPTXProxyRegErasure
• verify that we correctly lower libcalls with and without NVPTXProxyRegErasure

Other than that the patch looks good to me.

lib/Target/NVPTX/NVPTXInstrInfo.td

2258 ↗

(On Diff #178971)

Couple of nits:

• !strconcat accepts multiple arguments, so you only need one !strconcat to do the job.
• There's also a # which is a very convenient shortcut for concatenating strings. "a" # "b" is the same as !strconcat("a", "b")

Either of those could be used here.

[denzp]

Thanks, @tra that was a great idea!

I've added thorough PTX tests with and without the pass. And MIR test before and after the pass.

[tra]

Nice. Thank you for adding the tests.
LGTM.

include/llvm/CodeGen/SelectionDAG.h

public:
 
   /// \returns true if \p N is any kind of constant or build_vector of
   /// constants, int or float. If a vector, it may not necessarily be a splat.
   inline bool isConstantValueOfAnyType(SDValue N) {
     return isConstantIntBuildVectorOrConstantInt(N) ||
            isConstantFPBuildVectorOrConstantFP(N);
   }
 
+  /// KeepNodeAlive - Depends on \p ShouldKeep parameter starts or ends
+  /// considering node \p N as alive (i.e. being referenced) even if the node
+  /// is actually dead.
+  void KeepNodeAlive(SDNode *N, bool ShouldKeep);
+
 private:
   void InsertNode(SDNode *N);
   bool RemoveNodeFromCSEMaps(SDNode *N);
   void AddModifiedNodeToCSEMaps(SDNode *N);
   SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op, void *&InsertPos);
   SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op1, SDValue Op2,
                                void *&InsertPos);
   SDNode *FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
private:
   std::vector<CondCodeSDNode*> CondCodeNodes;
 
   std::vector<SDNode*> ValueTypeNodes;
   std::map<EVT, SDNode*, EVT::compareRawBits> ExtendedValueTypeNodes;
   StringMap<SDNode*> ExternalSymbols;
 
   std::map<std::pair<std::string, unsigned char>,SDNode*> TargetExternalSymbols;
   DenseMap<MCSymbol *, SDNode *> MCSymbols;
+  SmallDenseMap<SDNode *, std::unique_ptr<HandleSDNode>, 16> PreservedNodes;
 };
 
 template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> {
   using nodes_iterator = pointer_iterator<SelectionDAG::allnodes_iterator>;
 
   static nodes_iterator nodes_begin(SelectionDAG *G) {
     return nodes_iterator(G->allnodes_begin());
   }

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

for (auto &Val: I->second)
     Val->setIsInvalidated();
   DbgValMap.erase(I);
 }
 
 void SelectionDAG::DeallocateNode(SDNode *N) {
   // If we have operands, deallocate them.
   removeOperands(N);
 
+  // No need to keep it alive anymore.
+  PreservedNodes.erase(N);
+
   NodeAllocator.Deallocate(AllNodes.remove(N));
 
   // Set the opcode to DELETED_NODE to help catch bugs when node
   // memory is reallocated.
   // FIXME: There are places in SDag that have grown a dependency on the opcode
   // value in the released node.
   __asan_unpoison_memory_region(&N->NodeType, sizeof(N->NodeType));
   N->NodeType = ISD::DELETED_NODE;
void SelectionDAG::clear() {
   OperandRecycler.clear(OperandAllocator);
   OperandAllocator.Reset();
   CSEMap.clear();
 
   ExtendedValueTypeNodes.clear();
   ExternalSymbols.clear();
   TargetExternalSymbols.clear();
   MCSymbols.clear();
+  PreservedNodes.clear();
   std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
             static_cast<CondCodeSDNode*>(nullptr));
   std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
             static_cast<SDNode*>(nullptr));
 
   EntryNode.UseList = nullptr;
   InsertNode(&EntryNode);
   Root = getEntryNode();

 //===----------------------------------------------------------------------===//
 //                              SDNode Class
 //===----------------------------------------------------------------------===//
 
 bool llvm::isNullConstant(SDValue V) {
   ConstantSDNode *Const = dyn_cast<ConstantSDNode>(V);
   return Const != nullptr && Const->isNullValue();
 }
 
 bool llvm::isNullFPConstant(SDValue V) {
   ConstantFPSDNode *Const = dyn_cast<ConstantFPSDNode>(V);
   return Const != nullptr && Const->isZero() && !Const->isNegative();
 }
 
 bool llvm::isAllOnesConstant(SDValue V) {
   ConstantSDNode *Const = dyn_cast<ConstantSDNode>(V);
   return Const != nullptr && Const->isAllOnesValue();
if (isa<ConstantFPSDNode>(N))
     return N.getNode();
 
   if (ISD::isBuildVectorOfConstantFPSDNodes(N.getNode()))
     return N.getNode();
 
   return nullptr;
 }
 
+/// KeepNodeAlive - Depends on \p ShouldKeep parameter starts or ends
+/// considering node \p N as alive (i.e. being referenced) even if the node
+/// is actually dead.
+void SelectionDAG::KeepNodeAlive(SDNode *N, bool ShouldKeep) {
+  if (ShouldKeep && PreservedNodes.count(N) == 0) {
+    auto user = std::unique_ptr<HandleSDNode>(new HandleSDNode(SDValue(N, 0)));
+    PreservedNodes.insert(std::make_pair(N, std::move(user)));
+  }
+
+  if (!ShouldKeep)
+    PreservedNodes.erase(N);
+}
+
 #ifndef NDEBUG
 static void checkForCyclesHelper(const SDNode *N,
                                  SmallPtrSetImpl<const SDNode*> &Visited,
                                  SmallPtrSetImpl<const SDNode*> &Checked,
                                  const llvm::SelectionDAG *DAG) {
   // If this node has already been checked, don't check it again.
   if (Checked.count(N))
     return;

lib/Target/NVPTX/NVPTXISelLowering.h

private:
   SDValue LowerSTORE(SDValue Op, SelectionDAG &DAG) const;
   SDValue LowerSTOREi1(SDValue Op, SelectionDAG &DAG) const;
   SDValue LowerSTOREVector(SDValue Op, SelectionDAG &DAG) const;
 
   SDValue LowerShiftRightParts(SDValue Op, SelectionDAG &DAG) const;
   SDValue LowerShiftLeftParts(SDValue Op, SelectionDAG &DAG) const;
 
   SDValue LowerSelect(SDValue Op, SelectionDAG &DAG) const;
+  SDValue LowerLibcallFnNameSymbol(SDValue Op, SelectionDAG &DAG) const;
 
   void ReplaceNodeResults(SDNode *N, SmallVectorImpl<SDValue> &Results,
                           SelectionDAG &DAG) const override;
   SDValue PerformDAGCombine(SDNode *N, DAGCombinerInfo &DCI) const override;
 
   unsigned getArgumentAlignment(SDValue Callee, const ImmutableCallSite *CS,
                                 Type *Ty, unsigned Idx,
                                 const DataLayout &DL) const;
 };
 } // namespace llvm
 
 #endif

lib/Target/NVPTX/NVPTXISelLowering.cpp

for (unsigned i = 0, e = Args.size(); i != e; ++i, ++OIdx) {
     if (!first) {
       O << ", ";
     }
     first = false;
 
     if (!Outs[OIdx].Flags.isByVal()) {
       if (Ty->isAggregateType() || Ty->isVectorTy()) {
         unsigned align = 0;
+        // Call site is empty for libcall.
+        if (CS) {
           const CallInst *CallI = cast<CallInst>(CS->getInstruction());
           // +1 because index 0 is reserved for return type alignment
           if (!getAlign(*CallI, i + 1, align))
             align = DL.getABITypeAlignment(Ty);
+        }
+        else {
+           align = DL.getABITypeAlignment(Ty);
+        }
         unsigned sz = DL.getTypeAllocSize(Ty);
         O << ".param .align " << align << " .b8 ";
         O << "_";
         O << "[" << sz << "]";
         // update the index for Outs
         SmallVector<EVT, 16> vtparts;
         ComputeValueVTs(*this, DL, Ty, vtparts);
         if (unsigned len = vtparts.size())
for (unsigned j = 0, je = VTs.size(); j != je; ++j) {
       InFlag = Chain.getValue(1);
     }
     ++paramCount;
   }
 
   GlobalAddressSDNode *Func = dyn_cast<GlobalAddressSDNode>(Callee.getNode());
   unsigned retAlignment = 0;
 
+  // Libcalls doesn't have call site and but they still are NOT indirect calls.  
+  bool isIndirectCall = !Func && CS;
+
   // Handle Result
   if (Ins.size() > 0) {
     SmallVector<EVT, 16> resvtparts;
     ComputeValueVTs(*this, DL, RetTy, resvtparts);
 
     // Declare
     //  .param .align 16 .b8 retval0[<size-in-bytes>], or
     //  .param .b<size-in-bits> retval0
if (RetTy->isFloatingPointTy() || RetTy->isIntegerTy() ||
                                   DAG.getConstant(resultsz / 8, dl, MVT::i32),
                                   DAG.getConstant(0, dl, MVT::i32), InFlag };
       Chain = DAG.getNode(NVPTXISD::DeclareRetParam, dl, DeclareRetVTs,
                           DeclareRetOps);
       InFlag = Chain.getValue(1);
     }
   }
 
-  if (!Func) {
+  if (isa<ExternalSymbolSDNode>(Callee)) {
+    // Try to find the callee in the current module.
+    Callee = LowerLibcallFnNameSymbol(Callee, DAG);
+  }
+
+  if (isIndirectCall) {
     // This is indirect function call case : PTX requires a prototype of the
     // form
     // proto_0 : .callprototype(.param .b32 _) _ (.param .b32 _);
     // to be emitted, and the label has to used as the last arg of call
     // instruction.
     // The prototype is embedded in a string and put as the operand for a
     // CallPrototype SDNode which will print out to the value of the string.
     SDVTList ProtoVTs = DAG.getVTList(MVT::Other, MVT::Glue);
     std::string Proto = getPrototype(DL, RetTy, Args, Outs, retAlignment, CS);
     const char *ProtoStr =
       nvTM->getManagedStrPool()->getManagedString(Proto.c_str())->c_str();
     SDValue ProtoOps[] = {
       Chain, DAG.getTargetExternalSymbol(ProtoStr, MVT::i32), InFlag,
     };
     Chain = DAG.getNode(NVPTXISD::CallPrototype, dl, ProtoVTs, ProtoOps);
     InFlag = Chain.getValue(1);
   }
   // Op to just print "call"
   SDVTList PrintCallVTs = DAG.getVTList(MVT::Other, MVT::Glue);
   SDValue PrintCallOps[] = {
     Chain, DAG.getConstant((Ins.size() == 0) ? 0 : 1, dl, MVT::i32), InFlag
   };
   // We model convergent calls as separate opcodes.
-  unsigned Opcode = Func ? NVPTXISD::PrintCallUni : NVPTXISD::PrintCall;
+  unsigned Opcode = !isIndirectCall ? NVPTXISD::PrintCallUni : NVPTXISD::PrintCall;
   if (CLI.IsConvergent)
     Opcode = Opcode == NVPTXISD::PrintCallUni ? NVPTXISD::PrintConvergentCallUni
                                               : NVPTXISD::PrintConvergentCall;
   Chain = DAG.getNode(Opcode, dl, PrintCallVTs, PrintCallOps);
   InFlag = Chain.getValue(1);
 
   // Ops to print out the function name
   SDVTList CallVoidVTs = DAG.getVTList(MVT::Other, MVT::Glue);
for (unsigned i = 0, e = paramCount; i != e; ++i) {
     SDVTList CallArgVTs = DAG.getVTList(MVT::Other, MVT::Glue);
     SDValue CallArgOps[] = { Chain, DAG.getConstant(1, dl, MVT::i32),
                              DAG.getConstant(i, dl, MVT::i32), InFlag };
     Chain = DAG.getNode(opcode, dl, CallArgVTs, CallArgOps);
     InFlag = Chain.getValue(1);
   }
   SDVTList CallArgEndVTs = DAG.getVTList(MVT::Other, MVT::Glue);
   SDValue CallArgEndOps[] = { Chain,
-                              DAG.getConstant(Func ? 1 : 0, dl, MVT::i32),
+                              DAG.getConstant(!isIndirectCall, dl, MVT::i32),
                               InFlag };
   Chain = DAG.getNode(NVPTXISD::CallArgEnd, dl, CallArgEndVTs, CallArgEndOps);
   InFlag = Chain.getValue(1);
 
-  if (!Func) {
+  if (isIndirectCall) {
     SDVTList PrototypeVTs = DAG.getVTList(MVT::Other, MVT::Glue);
     SDValue PrototypeOps[] = { Chain,
                                DAG.getConstant(uniqueCallSite, dl, MVT::i32),
                                InFlag };
     Chain = DAG.getNode(NVPTXISD::Prototype, dl, PrototypeVTs, PrototypeOps);
     InFlag = Chain.getValue(1);
   }
 
SDValue NVPTXTargetLowering::LowerCall(TargetLowering::CallLoweringInfo &CLI,
 
   Chain = DAG.getCALLSEQ_END(Chain,
                              DAG.getIntPtrConstant(uniqueCallSite, dl, true),
                              DAG.getIntPtrConstant(uniqueCallSite + 1, dl,
                                                    true),
                              InFlag, dl);
   uniqueCallSite++;
 
+  if (!CS) {
+    // Unfortunately, libcall expansion does not respect `Chain`...
+    // Our `CALLSEQ_END` becomes dead node (i.e. nobody references it) because
+    // only retval `LoadParam`s will be used after expansion. That means the
+    // node will be deleted at the next iteration of legalization and we have
+    // to make effors to keep it alive.
+    DAG.KeepNodeAlive(Chain.getNode(), true);
+  }
+
   // set isTailCall to false for now, until we figure out how to express
   // tail call optimization in PTX
   isTailCall = false;
   return Chain;
 }
 
 // By default CONCAT_VECTORS is lowered by ExpandVectorBuildThroughStack()
 // (see LegalizeDAG.cpp). This is slow and uses local memory.
NVPTXTargetLowering::getParamSymbol(SelectionDAG &DAG, int idx, EVT v) const {
   ParamStr << DAG.getMachineFunction().getName() << "_param_" << idx;
   ParamStr.flush();
 
   std::string *SavedStr =
     nvTM->getManagedStrPool()->getManagedString(ParamSym.c_str());
   return DAG.getTargetExternalSymbol(SavedStr->c_str(), v);
 }
 
+SDValue
+NVPTXTargetLowering::LowerLibcallFnNameSymbol(SDValue Op,
+                                              SelectionDAG &DAG) const {
+  auto *Symbol = cast<ExternalSymbolSDNode>(Op)->getSymbol();
+  auto *Module = DAG.getMachineFunction().getFunction()->getParent();
+  auto PtrVT = getPointerTy(DAG.getDataLayout());
+
+  if (Module->getFunction(Symbol) != nullptr) {
+    return DAG.getTargetExternalSymbol(Symbol, PtrVT);
+  }
+
+  std::string ErrorStr;
+  raw_string_ostream ErrorFormatter(ErrorStr);
+
+  ErrorFormatter << "Undefined external symbol ";
+  ErrorFormatter << '"' << Symbol << '"';
+  ErrorFormatter.flush();
+
+  report_fatal_error(ErrorStr);
+}
+
 // Check to see if the kernel argument is image*_t or sampler_t
 
 static bool isImageOrSamplerVal(const Value *arg, const Module *context) {
   static const char *const specialTypes[] = { "struct._image2d_t",
                                               "struct._image3d_t",
                                               "struct._sampler_t" };
 
   Type *Ty = arg->getType();

test/CodeGen/NVPTX/libcall.ll

+; RUN: llc < %s -march=nvptx | FileCheck %s
+; Allow to make libcalls that are defined in current module
+
+; An intrinsic
+declare double @llvm.powi.f64(double, i32) nounwind readnone
+
+; Underlying libcall
+define double @__powidf2(double, i32) {
+  ret double 0.0
+}
+
+define double @powi() {
+  ; CHECK:      { // callseq 0, 0
+  ; CHECK:      call.uni (retval0),
+  ; CHECK-NEXT: __powidf2,
+  ; CHECK-NEXT: (
+  ; CHECK-NEXT: param0,
+  ; CHECK-NEXT: param1
+  ; CHECK-NEXT: );
+  ; CHECK-NEXT: ld.param.f64 %fd{{[0-9]+}}, [retval0+0];
+  ; CHECK-NEXT: } // callseq 0
+  %1 = call double @llvm.powi.f64(double 1.0, i32 undef)
+  ret double %1
+}

test/CodeGen/NVPTX/zero-cs.ll

 ; RUN: not llc < %s -march=nvptx 2>&1 | FileCheck %s
-; used to seqfault and now fails with a "Cannot select"
+; used to seqfault and now fails with a "Undefined external symbol"
 
-; CHECK: LLVM ERROR: Cannot select: {{t7|0x[0-9a-f]+}}: i32 = ExternalSymbol'__powidf2'
+; CHECK: Undefined external symbol "__powidf2"
 define double @powi() {
   %1 = call double @llvm.powi.f64(double 1.000000e+00, i32 undef)
   ret double %1
 }
 
 declare double @llvm.powi.f64(double, i32) nounwind readnone