[Polly] [PPCGCodeGeneration] Convert intrinsics to libdevice functions whenever possible.

[bollu]

Summary

This is useful when we face certain intrinsics such as llvm.exp.*
which cannot be lowered by the NVPTX backend while other intrinsics can.

So, we would need to keep blacklists of intrinsics that cannot be
handled by the NVPTX backend. It is much simpler to try and promote
all intrinsics to libdevice versions.

This patch makes function/intrinsic very uniform, and will always try to use
a libdevice version if it exists.

[bollu]

• [Bugfix] add powi to the list of instructions that the NVPTX backend cannot lower.
• [NFC] remove debug code

[bollu]

I should probably split this into two patches, but I wanted to run the idea by. I can split it when I commit (or split it now). Review, please.

[bollu]

• [Test] upadte tests to refect state of exp, powi in PPCGCodeGen

[efriedma]

Why can't the LLVM NVPTX backend handle these intrinsics? If implementations are available, the backend should call them. Or am I missing something obvious?

[bollu]

@efriedma - The NVPTX backend does not lower either llvm.exp.* or llvm.powi.* (Unless I am doing something wrong).

[efriedma]

Hmm, looks like it doesn't work (I get "LLVM ERROR: Cannot select: t14: i32 = ExternalSymbol'__powisf2'"). But that's clearly a bug in the backend rather than something you should try to address in polly.

[bollu]

@grosser ping, review please.

[grosser]

Hi Eli,

you are right. It would be nice if the backend would directly include libdevice. There is some information about libdevice available at https://llvm.org/docs/NVPTXUsage.html#linking-with-libdevice, but it seems it is indeed expected to be linked before things are passed to the LLVM backend.

Siddharth, can you please open a bug report regarding the issue Eli mentioned? Eli, do you think it is OK to move ahead for now, until this issue has been solved in the LLVM backend. (We are happy to add the necessary code, but this likely first needs some discussion.) Siddharth, maybe you can even open a discussion on llvm-dev?

Best,
Tobias

[efriedma]

Yes, it's okay for now.

lib/CodeGen/PPCGCodeGeneration.cpp

1420 ↗

(On Diff #112337)

Instead of trying to parse the name of the intrinsic, could you just map from an exact llvm intrinsic name to the equivalent libdevice function? e.g. map llvm.powi.f32 to __nv_powif, llvm.powi.f64 to __nv_powi, etc.

[bollu]

• Don't parse the function name, keep a static map from intrinsic names to libdevice names

[bollu]

• [Diff update] Update diff with latest master.

[bollu]

@efriedma I made the changes you requested. Could you have a final look, please?

[efriedma]

LGTM

polly/trunk/lib/CodeGen/PPCGCodeGeneration.cpp

isl_bool collectReferencesInGPUStmt(__isl_keep isl_ast_node *Node, void *User) {
 
   addReferencesFromStmt(Stmt, User, false /* CreateScalarRefs */);
 
   return isl_bool_true;
 }
 
 /// A list of functions that are available in NVIDIA's libdevice.
 const std::set<std::string> CUDALibDeviceFunctions = {
-    "exp",   "expf",     "expl",      "cos",       "cosf", "sqrt",
-    "sqrtf", "copysign", "copysignf", "copysignl", "log",  "logf"};
+    "exp",      "expf",      "expl",      "cos", "cosf", "sqrt", "sqrtf",
+    "copysign", "copysignf", "copysignl", "log", "logf", "powi", "powif"};
+
+// A map from intrinsics to their corresponding libdevice functions.
+const std::map<std::string, std::string> IntrinsicToLibdeviceFunc = {
+    {"llvm.exp.f64", "exp"},
+    {"llvm.exp.f32", "expf"},
+    {"llvm.powi.f64", "powi"},
+    {"llvm.powi.f32", "powif"}};
 
 /// Return the corresponding CUDA libdevice function name for @p F.
+/// Note that this function will try to convert instrinsics in the list
+/// IntrinsicToLibdeviceFunc into libdevice functions.
+/// This is because some intrinsics such as `exp`
+/// are not supported by the NVPTX backend.
+/// If this restriction of the backend is lifted, we should refactor our code
+/// so that we use intrinsics whenever possible.
 ///
 /// Return "" if we are not compiling for CUDA.
 std::string getCUDALibDeviceFuntion(Function *F) {
-  if (CUDALibDeviceFunctions.count(F->getName()))
-    return std::string("__nv_") + std::string(F->getName());
+  const std::string FnName = [&] {
+    auto It = IntrinsicToLibdeviceFunc.find(F->getName());
+    if (It != IntrinsicToLibdeviceFunc.end())
+      return It->second;
+
+    return std::string(F->getName());
+  }();
+
+  if (CUDALibDeviceFunctions.count(FnName))
+    return "__nv_" + FnName;
 
   return "";
 }
 
 /// Check if F is a function that we can code-generate in a GPU kernel.
 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 && getCUDALibDeviceFuntion(F).length() > 0)
     return true;
 
   return F->isIntrinsic() &&
          (Name.startswith("llvm.sqrt") || Name.startswith("llvm.fabs") ||
-          Name.startswith("llvm.copysign") || Name.startswith("llvm.powi"));
+          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.

 }
 
 bool GPUNodeBuilder::requiresCUDALibDevice() {
   bool RequiresLibDevice = false;
   for (Function &F : GPUModule->functions()) {
     if (!F.isDeclaration())
       continue;
 
-    std::string CUDALibDeviceFunc = getCUDALibDeviceFuntion(&F);
+    const std::string CUDALibDeviceFunc = getCUDALibDeviceFuntion(&F);
     if (CUDALibDeviceFunc.length() != 0) {
+      // We need to handle the case where a module looks like this:
+      // @expf(..)
+      // @llvm.exp.f64(..)
+      // Both of these functions would be renamed to `__nv_expf`.
+      //
+      // So, we must first check for the existence of the libdevice function.
+      // If this exists, we replace our current function with it.
+      //
+      // If it does not exist, we rename the current function to the
+      // libdevice functiono name.
+      if (Function *Replacement = F.getParent()->getFunction(CUDALibDeviceFunc))
+        F.replaceAllUsesWith(Replacement);
+      else
         F.setName(CUDALibDeviceFunc);
       RequiresLibDevice = true;
     }
   }
 
   return RequiresLibDevice;
 }
 
 void GPUNodeBuilder::addCUDALibDevice() {

polly/trunk/test/GPGPU/intrinsic-copied-into-kernel.ll

 ; RUN: opt %loadPolly -analyze -polly-scops < %s | FileCheck %s --check-prefix=SCOP
 ; RUN: opt %loadPolly -analyze -polly-codegen-ppcg -polly-acc-dump-kernel-ir < %s | FileCheck %s --check-prefix=KERNEL-IR
 ; RUN: opt %loadPolly -S -polly-codegen-ppcg  < %s | FileCheck %s --check-prefix=HOST-IR
 
 ; Test that we do recognise and codegen a kernel that has intrinsics.
 
 ; 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_sqrt = tail call float @llvm.sqrt.f32(float %A.arr.i.val_p_scalar_)
 ; KERNEL-IR:   declare float @llvm.sqrt.f32(float)
 ; KERNEL-IR:   declare float @llvm.fabs.f32(float)
-; KERNEL-IR:   declare float @llvm.powi.f32(float, i32)
+
 
 ; 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 = sqrt(tmp1);
 ;       float tmp2 = fabs(tmp2);
 ;       float tmp3 = copysignf(tmp1, tmp2);
-;       float tmp4 = powi(tmp3, 2);
 ;       B[i] = tmp4;
 ;   }
 ; }
 
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @f(float* %A, float* %B, i32 %N) {
 entry:

 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.
   %sqrt = tail call float @llvm.sqrt.f32(float %A.arr.i.val)
   %fabs = tail call float @llvm.fabs.f32(float %sqrt);
   %copysign = tail call float @llvm.copysign.f32(float %sqrt, float %fabs);
-  %powi = tail call float @llvm.powi.f32(float %copysign, i32 2);
   %B.arr.i = getelementptr inbounds float, float* %B, i64 %indvars.iv
-  store float %powi, float* %B.arr.i, align 4
+  store float %copysign, 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 @llvm.sqrt.f32(float) #0
 declare float @llvm.fabs.f32(float) #0
 declare float @llvm.copysign.f32(float, float) #0
-declare float @llvm.powi.f32(float, i32) #0
 
 attributes #0 = { nounwind readnone }
 

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

 ; 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_)
 ; KERNEL-IR:   %p_cosf = tail call float @__nv_cosf(float %p_expf)
 ; KERNEL-IR:   %p_logf = tail call float @__nv_logf(float %p_cosf)
 
+; Powi and exp cannot be lowered directly. Rather, we expect them to be
+; lowered by libdevice.
+; KERNEL-IR: %p_powi = tail call float @__nv_powif(float %p_logf, i32 2)
+; KERNEL-IR: %p_exp = tail call float @__nv_expf(float %p_powi)
+
 ; 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 expf  = expf(tmp1);
 ;       cosf = cosf(expf);
 ;       logf = logf(cosf);
+;       powi = powi(logf, 2);
+;       exp = exp(powi);
 ;       B[i] = logf;
 ;   }
 ; }
 
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @f(float* %A, float* %B, i32 %N) {
 entry:

 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)
   %cosf = tail call float @cosf(float %expf)
   %logf = tail call float @logf(float %cosf)
+  %powi = tail call float @llvm.powi.f32(float %logf, i32 2)
+  %exp = tail call float @llvm.exp.f32(float %powi)
   %B.arr.i = getelementptr inbounds float, float* %B, i64 %indvars.iv
-  store float %logf, float* %B.arr.i, align 4
+  store float %exp, 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
 declare float @cosf(float) #0
 declare float @logf(float) #0
+declare float @llvm.powi.f32(float, i32) #0
+declare float @llvm.exp.f32(float) #0
 
 attributes #0 = { nounwind readnone }