[GPGPU] Add support for NVIDIA libdevice

[grosser]

Summary

This allows us to map functions such as exp, expf, expl, for which no
LLVM intrinsics exist. Instead, we link to NVIDIA's libdevice which provides
high-performance implementations of a wide range of (math) functions. We
currently link only a small subset, the exp* and cos functions. Other functions
will be enabled as needed.

[bollu]

lib/CodeGen/PPCGCodeGeneration.cpp

1314

Consider changing to SmallSet? That feels correct in terms of semantics (a set of functions.)

1418

const bool? :)

2131

consider moving computing RequiresLibDevice to a pure function?

2138

I believe we can assert at this point, since this is not a "mis-compile" in the strictest sense of the word?.

2148

nit: trible -> triple.

[tra]

lib/CodeGen/PPCGCodeGeneration.cpp

107–111

This is something that is useful for all NVPTX users and should probably live there and it should not have any hardcoded path -- it's too easy to end up silently picking wrong library otherwise.

Hardcoded compute_20 is also problematic because it should depend on particular GPU arch we're compiling for.

Considering that LLVM has no idea about CUDA SDL location, this is sommething that should always be explicitly specified. Either base path + libdevice name derived from GPU arch, or complete path to specific libdevice variant (i.e. it's completely up to the user to provide correct libdevice).

3020

Bllock -> Block

test/GPGPU/libdevice-functions-copied-into-kernel.ll

38–69

Can the test be reduced to just expf() call?

test/GPGPU/libdevice-functions-copied-into-kernel_libdevice.bc

1–6

This file should be under Inputs/ directory (see NVPTX tests for example) and have .ll extension.

[bollu]

Is there some way to test this without having libdevice? The tests break on my mac.

[bollu]

lib/CodeGen/PPCGCodeGeneration.cpp

1314

could you also please add sqrt to the list? this is present in the COSMO kernel.

[singam-sanjay]

lib/CodeGen/PPCGCodeGeneration.cpp

107

Would it be better to call this CUDALibDevice or CULibDevice instead ? since this applies only to NVPTX

109

Consider changing this to "/usr/local/cuda/nvvm/libdevice/libdevice.compute_20_10.bc". That would work on most Linux platforms by default.

I'm not sure if PTX code for a compute capability 2 device would run on any newer device. Is it possible to initialize this after figuring out the CC of device 0 ?

Also, I heard that CUDA SDK 8 would be the last to support CC 2.x. CUDA 9 supports all CCs from 3.0.

609

Would addCULibDevice be a better name ?

[grosser]

Address review comments

[grosser]

Thank you for all the good reviews. I tried to address all of them.

Best,
Tobias

lib/CodeGen/PPCGCodeGeneration.cpp

107

I use CUDALibDevice

107–111

@tra: Thank you for your comment. This is the very first commit to introduce this feature. We currently are in early beta tests. The library location is supposed to be provided by the user by setting the path with polly-acc-libdevice. I set the option to a very basic default. For now I expect the user to adjust this default. In the future we can add some generic infrastructure to LLVM to derive this path automatically. If a specific fixed path is too confusing I can also use an empty default and always prompt for a path.

109

Changed. using /usr/local/cuda is indeed a good idea.

I would like to start with the oldest library. We can later add support for different library versions. I don't think we can query device 0, as we might compile on different platform as where we run the final code. However, we can make this depend on polly-acc-cuda-version.

609

Changed.

1314

Done.!

1314

I use a std::set. That should be good enough for now.

2131

Done.

2138

I use report_fatal_error as suggested by Michael.

2148

Done!

3020

Fixed in r308715.

test/GPGPU/libdevice-functions-copied-into-kernel.ll

38–69

Unlikely. This is a test for Polly-ACC, where we auto-offload to CUDA. For this we need at least some parallelism, which means some loop.

test/GPGPU/libdevice-functions-copied-into-kernel_libdevice.bc

1–6

Very good idea. I adopted it.

[tstellar]

How is this different from passing libdevice to either of the -mlink-cuda-bitcode or -mlink-bticode-file options ?

lib/CodeGen/PPCGCodeGeneration.cpp

2154

Could this be avoided by implementing Triple::isCompatibleWith() for nvptx?

[tra]

lib/CodeGen/PPCGCodeGeneration.cpp

107–111

I believe no default would be a better option in this case as it minimizes possibility for things to go wrong silently.

113

The variable appears to be unused.

On a side note, please consider that there's already a way to specify GPU variant for NVPTX back-end. This option is either going to be redundant or you'll need a good explanation for what's supposed to happen when its value conflicts with whatever GPU variant NVPTX back-end thinks it's supposed to generate the code for.

118

This also appears to be unused.
Please remove them from this patch and re-introduce them in subsequent patches that really need them.

2122

!empty()

2133

What's supposed to happen in this case? Consider adding a diagnostic message.

2138

But why are you still printing the libdevice name on stderr?

2161

I'm curious -- when would it be OK to proceed if verifier has failed?

Should this option be other way around -- and make LLVM fail by default on verifier failure? That would be my expectation of normal behavior. One could conceivably use this option for debugging purposes to force LLVM to proceed even when verifier has failed, but in general I believe that by default the errors should be reported as early as possible.

test/GPGPU/libdevice-functions-copied-into-kernel.ll

38–69

It may be worth reconsidering your approach and making this functionality generic to NVPTX so it can benefit all users of NVPTX back-end. The functionality is generic enough to benefit CUDA (and possibly OpenCL) which currently fail miserably if any of standard library functions sneak into IR.

[bollu]

Other than nits, LGTM

lib/CodeGen/PPCGCodeGeneration.cpp

1314

this can be const std::set<std::string> ... ? I do not see us mutating this, and it would be nice to communicate this fact.

test/lit.site.cfg.in

37 ↗

(On Diff #107971)

Can we be more explicit and mention that these are for the libdevice tests?

[bollu]

lib/CodeGen/PPCGCodeGeneration.cpp

1314

Could you also add copysign, please?

lib/CMakeLists.txt

target_link_libraries(Polly
     LLVMCore
     LLVMScalarOpts
     LLVMInstCombine
     LLVMTransformUtils
     LLVMAnalysis
     LLVMipo
     LLVMMC
     LLVMPasses
+    LLVMLinker
+    LLVMIRReader
     ${nvptx_libs}
     # The libraries below are required for darwin: http://PR26392
     LLVMBitReader
     LLVMMCParser
     LLVMObject
     LLVMProfileData
     LLVMTarget
     LLVMVectorize

lib/CodeGen/PPCGCodeGeneration.cpp

 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/IR/LegacyPassManager.h"
 #include "llvm/IR/Verifier.h"
+#include "llvm/IRReader/IRReader.h"
+#include "llvm/Linker/Linker.h"
 #include "llvm/Support/TargetRegistry.h"
 #include "llvm/Support/TargetSelect.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Transforms/IPO/PassManagerBuilder.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 
 #include "isl/union_map.h"
 

 static cl::opt<bool>
     FailOnVerifyModuleFailure("polly-acc-fail-on-verify-module-failure",
                               cl::desc("Fail and generate a backtrace if"
                                        " verifyModule fails on the GPU "
                                        " kernel module."),
                               cl::Hidden, cl::init(false), cl::ZeroOrMore,
                               cl::cat(PollyCategory));
 
+static cl::opt<std::string> LibDevice(
+    "polly-acc-libdevice", cl::desc("Path to CUDA libdevice"), cl::Hidden,
+    cl::init("/usr/local/cuda-7.5/nvvm/libdevice/libdevice.compute_20.10.bc"),
+    cl::ZeroOrMore, cl::cat(PollyCategory));
+
 static cl::opt<std::string>
     CudaVersion("polly-acc-cuda-version",
                 cl::desc("The CUDA version to compile for"), cl::Hidden,
                 cl::init("sm_30"), cl::ZeroOrMore, cl::cat(PollyCategory));
 
 static cl::opt<int>
     MinCompute("polly-acc-mincompute",
                cl::desc("Minimal number of compute statements to run on GPU."),
                cl::Hidden, cl::init(10 * 512 * 512));
 
 /// Used to store information PPCG wants for kills. This information is
 /// used by live range reordering.
 ///
 /// @see computeLiveRangeReordering
 /// @see GPUNodeBuilder::createPPCGScop
private:
   /// @param F The function to remove references to.
   void clearScalarEvolution(Function *F);
 
   /// Remove references from loop info to the kernel function @p F.
   ///
   /// @param F The function to remove references to.
   void clearLoops(Function *F);
 
+  /// Link with the NVIDIA libdevice library (if needed and available).
+  void addLibDevice();
+
   /// Finalize the generation of the kernel function.
   ///
   /// Free the LLVM-IR module corresponding to the kernel and -- if requested --
   /// dump its IR to stderr.
   ///
   /// @returns The Assembly string of the kernel.
   std::string finalizeKernelFunction();
 
isl_bool collectReferencesInGPUStmt(__isl_keep isl_ast_node *Node, void *User) {
   auto Stmt = (ScopStmt *)KernelStmt->u.d.stmt->stmt;
   isl_id_free(Id);
 
   addReferencesFromStmt(Stmt, User, false /* CreateScalarRefs */);
 
   return isl_bool_true;
 }
 
+/// A list of functions that are available in NVIDIA's libdevice.
+std::vector<std::string> LibDeviceFunctions = {"exp", "expf", "expl", "cos",
+                                               "cosf"};
+
+/// Return the corresponding CUDA libdevice function name for @p F.
+///
+/// Return "" if we are not compiling for CUDA.
+std::string getLibDeviceFuntion(Function *F) {
+  for (auto Name : LibDeviceFunctions)
+    if (Name == F->getName())
+      return "__nv_" + Name;
+
+  return "";
+}
+
 /// Check if F is a function that we can code-generate in a GPU kernel.
-static bool isValidFunctionInKernel(llvm::Function *F) {
+static bool isValidFunctionInKernel(llvm::Function *F, bool AllowLibDevice) {
   assert(F && "F is an invalid pointer");
   // We string compare against the name of the function to allow
   // all variants of the intrinsic "llvm.sqrt.*", "llvm.fabs", and
   // "llvm.copysign".
   const StringRef Name = F->getName();
+
+  if (AllowLibDevice && getLibDeviceFuntion(F).length() > 0)
+    return true;
+
   return F->isIntrinsic() &&
          (Name.startswith("llvm.sqrt") || Name.startswith("llvm.fabs") ||
           Name.startswith("llvm.copysign"));
 }
 
 /// Do not take `Function` as a subtree value.
 ///
 /// We try to take the reference of all subtree values and pass them along
 /// to the kernel from the host. Taking an address of any function and
 /// trying to pass along is nonsensical. Only allow `Value`s that are not
 /// `Function`s.
 static bool isValidSubtreeValue(llvm::Value *V) { return !isa<Function>(V); }
 
 /// Return `Function`s from `RawSubtreeValues`.
 static SetVector<Function *>
-getFunctionsFromRawSubtreeValues(SetVector<Value *> RawSubtreeValues) {
+getFunctionsFromRawSubtreeValues(SetVector<Value *> RawSubtreeValues,
+                                 bool AllowLibDevice) {
   SetVector<Function *> SubtreeFunctions;
   for (Value *It : RawSubtreeValues) {
     Function *F = dyn_cast<Function>(It);
     if (F) {
-      assert(isValidFunctionInKernel(F) && "Code should have bailed out by "
-                                           "this point if an invalid function "
-                                           "were present in a kernel.");
+      assert(isValidFunctionInKernel(F, AllowLibDevice) &&
+             "Code should have bailed out by "
       SubtreeFunctions.insert(F);
     }
   }
   return SubtreeFunctions;
 }
 
 std::pair<SetVector<Value *>, SetVector<Function *>>
 GPUNodeBuilder::getReferencesInKernel(ppcg_kernel *Kernel) {
GPUNodeBuilder::getReferencesInKernel(ppcg_kernel *Kernel) {
   // SubtreeValues. This is important, because we should not lose any
   // SubtreeValues in the process of constructing the
   // "ValidSubtree{Values, Functions} sets. Nor should the set
   // ValidSubtree{Values, Functions} have any common element.
   auto ValidSubtreeValuesIt =
       make_filter_range(SubtreeValues, isValidSubtreeValue);
   SetVector<Value *> ValidSubtreeValues(ValidSubtreeValuesIt.begin(),
                                         ValidSubtreeValuesIt.end());
+
+  bool AllowLibDevice = Arch == GPUArch::NVPTX64;
+
   SetVector<Function *> ValidSubtreeFunctions(
-      getFunctionsFromRawSubtreeValues(SubtreeValues));
+      getFunctionsFromRawSubtreeValues(SubtreeValues, AllowLibDevice));
 
   // @see IslNodeBuilder::getReferencesInSubtree
   SetVector<Value *> ReplacedValues;
   for (Value *V : ValidSubtreeValues) {
     auto It = ValueMap.find(V);
     if (It == ValueMap.end())
       ReplacedValues.insert(V);
     else
if (TargetM->addPassesToEmitFile(
     return "";
   }
 
   PM.run(*GPUModule);
 
   return ASMStream.str();
 }
 
+void GPUNodeBuilder::addLibDevice() {
+  if (Arch != GPUArch::NVPTX64)
+    return;
+
+  bool RequiresLibDevice = false;
+
+  for (Function &F : GPUModule->functions()) {
+    if (!F.isDeclaration())
+      continue;
+
+    std::string LibDeviceFunc = getLibDeviceFuntion(&F);
+    if (LibDeviceFunc.length() != 0) {
+      F.setName(LibDeviceFunc);
+      RequiresLibDevice = true;
+    }
+  }
+
+  if (RequiresLibDevice) {
+    SMDiagnostic Error;
+    auto LibDeviceModule =
+        parseIRFile(LibDevice, Error, GPUModule->getContext());
+
+    if (!LibDeviceModule) {
+      BuildSuccessful = false;
+      errs() << "Could not find libdevice. Skipping GPU kernel generation. "
+                "Please set -polly-acc-libdevice accordingly.\n";
+      return;
+    }
+
+    Linker L(*GPUModule);
+
+    // Set an nvptx64 target triple to avoid linker warnings. The original
+    // trible of the libdevice files are nvptx-unknown-unknown.
+    LibDeviceModule->setTargetTriple(Triple::normalize("nvptx64-nvidia-cuda"));
+    L.linkInModule(std::move(LibDeviceModule), Linker::LinkOnlyNeeded);
+  }
+}
+
 std::string GPUNodeBuilder::finalizeKernelFunction() {
 
   if (verifyModule(*GPUModule)) {
     DEBUG(dbgs() << "verifyModule failed on module:\n";
           GPUModule->print(dbgs(), nullptr); dbgs() << "\n";);
 
     if (FailOnVerifyModuleFailure)
       llvm_unreachable("VerifyModule failed.");
 
     BuildSuccessful = false;
     return "";
   }
 
+  addLibDevice();
+
   if (DumpKernelIR)
     outs() << *GPUModule << "\n";
 
   // Optimize module.
   llvm::legacy::PassManager OptPasses;
   PassManagerBuilder PassBuilder;
   PassBuilder.OptLevel = 3;
   PassBuilder.SizeLevel = 0;
createSufficientComputeCheck(Scop &S, __isl_keep isl_ast_build *Build) {
     return isl_ast_expr_ge(Iterations, MinComputeExpr);
   }
 
   /// Check if the basic block contains a function we cannot codegen for GPU
   /// kernels.
   ///
   /// If this basic block does something with a `Function` other than calling
   /// a function that we support in a kernel, return true.
-  bool containsInvalidKernelFunctionInBllock(const BasicBlock *BB) {
+  bool containsInvalidKernelFunctionInBllock(const BasicBlock *BB,
+                                             bool AllowLibDevice) {
     for (const Instruction &Inst : *BB) {
       const CallInst *Call = dyn_cast<CallInst>(&Inst);
-      if (Call && isValidFunctionInKernel(Call->getCalledFunction())) {
+      if (Call &&
+          isValidFunctionInKernel(Call->getCalledFunction(), AllowLibDevice)) {
         continue;
       }
 
       for (Value *SrcVal : Inst.operands()) {
         PointerType *p = dyn_cast<PointerType>(SrcVal->getType());
         if (!p)
           continue;
         if (isa<FunctionType>(p->getElementType()))
           return true;
       }
     }
     return false;
   }
 
   /// Return whether the Scop S uses functions in a way that we do not support.
-  bool containsInvalidKernelFunction(const Scop &S) {
+  bool containsInvalidKernelFunction(const Scop &S, bool AllowLibDevice) {
     for (auto &Stmt : S) {
       if (Stmt.isBlockStmt()) {
-        if (containsInvalidKernelFunctionInBllock(Stmt.getBasicBlock()))
+        if (containsInvalidKernelFunctionInBllock(Stmt.getBasicBlock(),
+                                                  AllowLibDevice))
           return true;
       } else {
         assert(Stmt.isRegionStmt() &&
                "Stmt was neither block nor region statement");
         for (const BasicBlock *BB : Stmt.getRegion()->blocks())
-          if (containsInvalidKernelFunctionInBllock(BB))
+          if (containsInvalidKernelFunctionInBllock(BB, AllowLibDevice))
             return true;
       }
     }
     return false;
   }
 
   /// Generate code for a given GPU AST described by @p Root.
   ///
bool runOnScop(Scop &CurrentScop) override {
     DL = &S->getRegion().getEntry()->getModule()->getDataLayout();
     RI = &getAnalysis<RegionInfoPass>().getRegionInfo();
 
     // We currently do not support functions other than intrinsics inside
     // kernels, as code generation will need to offload function calls to the
     // kernel. This may lead to a kernel trying to call a function on the host.
     // This also allows us to prevent codegen from trying to take the
     // address of an intrinsic function to send to the kernel.
-    if (containsInvalidKernelFunction(CurrentScop)) {
+    if (containsInvalidKernelFunction(CurrentScop,
+                                      Architecture == GPUArch::NVPTX64)) {
       DEBUG(
           dbgs()
               << "Scop contains function which cannot be materialised in a GPU "
                  "kernel. Bailing out.\n";);
       return false;
     }
 
     auto PPCGScop = createPPCGScop();

test/GPGPU/libdevice-functions-copied-into-kernel.ll

+; RUN: opt %loadPolly -analyze -polly-scops < %s \
+; RUN: -polly-acc-libdevice=%S/libdevice-functions-copied-into-kernel_libdevice.bc \
+; RUN:     | FileCheck %s --check-prefix=SCOP
+; RUN: opt %loadPolly -analyze -polly-codegen-ppcg -polly-acc-dump-kernel-ir \
+; RUN: -polly-acc-libdevice=%S/libdevice-functions-copied-into-kernel_libdevice.bc \
+; RUN:     < %s | FileCheck %s --check-prefix=KERNEL-IR
+; RUN: opt %loadPolly -S -polly-codegen-ppcg  < %s \
+; RUN: -polly-acc-libdevice=%S/libdevice-functions-copied-into-kernel_libdevice.bc \
+; RUN:     | FileCheck %s --check-prefix=HOST-IR
+
+; Test that we do recognise and codegen a kernel that has functions that can
+; be mapped to NVIDIA's libdevice
+
+; REQUIRES: pollyacc
+
+; Check that we model the kernel as a scop.
+; SCOP:      Function: f
+; SCOP-NEXT:       Region: %entry.split---%for.end
+
+; Check that the intrinsic call is present in the kernel IR.
+; KERNEL-IR:   %p_expf = tail call float @__nv_expf(float %A.arr.i.val_p_scalar_)
+
+; Check that kernel launch is generated in host IR.
+; the declare would not be generated unless a call to a kernel exists.
+; HOST-IR: declare void @polly_launchKernel(i8*, i32, i32, i32, i32, i32, i8*)
+
+
+; void f(float *A, float *B, int N) {
+;   for(int i = 0; i < N; i++) {
+;       float tmp0 = A[i];
+;       float tmp1 = expf(tmp1);
+;       B[i] = tmp1;
+;   }
+; }
+
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(float* %A, float* %B, i32 %N) {
+entry:
+  br label %entry.split
+
+entry.split:                                      ; preds = %entry
+  %cmp1 = icmp sgt i32 %N, 0
+  br i1 %cmp1, label %for.body.lr.ph, label %for.end
+
+for.body.lr.ph:                                   ; preds = %entry.split
+  br label %for.body
+
+for.body:                                         ; preds = %for.body.lr.ph, %for.body
+  %indvars.iv = phi i64 [ 0, %for.body.lr.ph ], [ %indvars.iv.next, %for.body ]
+  %A.arr.i = getelementptr inbounds float, float* %A, i64 %indvars.iv
+  %A.arr.i.val = load float, float* %A.arr.i, align 4
+  ; Call to intrinsics that should be part of the kernel.
+  %expf = tail call float @expf(float %A.arr.i.val)
+  %B.arr.i = getelementptr inbounds float, float* %B, i64 %indvars.iv
+  store float %expf, float* %B.arr.i, align 4
+
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %wide.trip.count = zext i32 %N to i64
+  %exitcond = icmp ne i64 %indvars.iv.next, %wide.trip.count
+  br i1 %exitcond, label %for.body, label %for.cond.for.end_crit_edge
+
+for.cond.for.end_crit_edge:                       ; preds = %for.body
+  br label %for.end
+
+for.end:                                          ; preds = %for.cond.for.end_crit_edge, %entry.split
+  ret void
+}
+
+; Function Attrs: nounwind readnone
+declare float @expf(float) #0
+
+attributes #0 = { nounwind readnone }
+

test/GPGPU/libdevice-functions-copied-into-kernel_libdevice.bc

+definelayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v16:16:16-v32:32:32-v64:64:64-v128:128:128-n16:32:64"
+target triple = "nvptx64-nvidia-cuda"
+
+define float @__nv_expf(float %a) #1 {
+  return %a
+}