llvm/lib/Transforms/HipStdPar/HipStdPar.cpp

   1 //===----- HipStdPar.cpp - HIP C++ Standard Parallelism Support Passes ----===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 // This file implements two passes that enable HIP C++ Standard Parallelism
   9 // Support:
  10 //
  11 // 1. AcceleratorCodeSelection (required): Given that only algorithms are
  12 //    accelerated, and that the accelerated implementation exists in the form of
  13 //    a compute kernel, we assume that only the kernel, and all functions
  14 //    reachable from it, constitute code that the user expects the accelerator
  15 //    to execute. Thus, we identify the set of all functions reachable from
  16 //    kernels, and then remove all unreachable ones. This last part is necessary
  17 //    because it is possible for code that the user did not expect to execute on
  18 //    an accelerator to contain constructs that cannot be handled by the target
  19 //    BE, which cannot be provably demonstrated to be dead code in general, and
  20 //    thus can lead to mis-compilation. The degenerate case of this is when a
  21 //    Module contains no kernels (the parent TU had no algorithm invocations fit
  22 //    for acceleration), which we handle by completely emptying said module.
  23 //    **NOTE**: The above does not handle indirectly reachable functions i.e.
  24 //              it is possible to obtain a case where the target of an indirect
  25 //              call is otherwise unreachable and thus is removed; this
  26 //              restriction is aligned with the current `-hipstdpar` limitations
  27 //              and will be relaxed in the future.
  28 //
  29 // 2. AllocationInterposition (required only when on-demand paging is
  30 //    unsupported): Some accelerators or operating systems might not support
  31 //    transparent on-demand paging. Thus, they would only be able to access
  32 //    memory that is allocated by an accelerator-aware mechanism. For such cases
  33 //    the user can opt into enabling allocation / deallocation interposition,
  34 //    whereby we replace calls to known allocation / deallocation functions with
  35 //    calls to runtime implemented equivalents that forward the requests to
  36 //    accelerator-aware interfaces. We also support freeing system allocated
  37 //    memory that ends up in one of the runtime equivalents, since this can
  38 //    happen if e.g. a library that was compiled without interposition returns
  39 //    an allocation that can be validly passed to `free`.
  40 //===----------------------------------------------------------------------===//
  41
  42 #include "llvm/Transforms/HipStdPar/HipStdPar.h"
  43
  44 #include "llvm/ADT/SmallPtrSet.h"
  45 #include "llvm/ADT/SmallVector.h"
  46 #include "llvm/ADT/STLExtras.h"
  47 #include "llvm/Analysis/CallGraph.h"
  48 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
  49 #include "llvm/IR/Constants.h"
  50 #include "llvm/IR/DebugInfoMetadata.h"
  51 #include "llvm/IR/Function.h"
  52 #include "llvm/IR/Module.h"
  53 #include "llvm/Transforms/Utils/ModuleUtils.h"
  54
  55 #include <cassert>
  56 #include <string>
  57 #include <utility>
  58
  59 using namespace llvm;
  60
  61 template<typename T>
  62 static inline void eraseFromModule(T &ToErase) {
  63   ToErase.replaceAllUsesWith(PoisonValue::get(ToErase.getType()));
  64   ToErase.eraseFromParent();
  65 }
  66
  67 static inline bool checkIfSupported(GlobalVariable &G) {
  68   if (!G.isThreadLocal())
  69     return true;
  70
  71   G.dropDroppableUses();
  72
  73   if (!G.isConstantUsed())
  74     return true;
  75
  76   std::string W;
  77   raw_string_ostream OS(W);
  78
  79   OS << "Accelerator does not support the thread_local variable "
  80     << G.getName();
  81
  82   Instruction *I = nullptr;
  83   SmallVector<User *> Tmp(G.user_begin(), G.user_end());
  84   SmallPtrSet<User *, 5> Visited;
  85   do {
  86     auto U = std::move(Tmp.back());
  87     Tmp.pop_back();
  88
  89     if (Visited.contains(U))
  90       continue;
  91
  92     if (isa<Instruction>(U))
  93       I = cast<Instruction>(U);
  94     else
  95       Tmp.insert(Tmp.end(), U->user_begin(), U->user_end());
  96
  97     Visited.insert(U);
  98   } while (!I && !Tmp.empty());
  99
 100   assert(I && "thread_local global should have at least one non-constant use.");
 101
 102   G.getContext().diagnose(
 103     DiagnosticInfoUnsupported(*I->getParent()->getParent(), W,
 104                               I->getDebugLoc(), DS_Error));
 105
 106   return false;
 107 }
 108
 109 static inline void clearModule(Module &M) { // TODO: simplify.
 110   while (!M.functions().empty())
 111     eraseFromModule(*M.begin());
 112   while (!M.globals().empty())
 113     eraseFromModule(*M.globals().begin());
 114   while (!M.aliases().empty())
 115     eraseFromModule(*M.aliases().begin());
 116   while (!M.ifuncs().empty())
 117     eraseFromModule(*M.ifuncs().begin());
 118 }
 119
 120 static inline void maybeHandleGlobals(Module &M) {
 121   unsigned GlobAS = M.getDataLayout().getDefaultGlobalsAddressSpace();
 122   for (auto &&G : M.globals()) { // TODO: should we handle these in the FE?
 123     if (!checkIfSupported(G))
 124       return clearModule(M);
 125
 126     if (G.isThreadLocal())
 127       continue;
 128     if (G.isConstant())
 129       continue;
 130     if (G.getAddressSpace() != GlobAS)
 131       continue;
 132     if (G.getLinkage() != GlobalVariable::ExternalLinkage)
 133       continue;
 134
 135     G.setLinkage(GlobalVariable::ExternalWeakLinkage);
 136     G.setExternallyInitialized(true);
 137   }
 138 }
 139
 140 template<unsigned N>
 141 static inline void removeUnreachableFunctions(
 142   const SmallPtrSet<const Function *, N>& Reachable, Module &M) {
 143   removeFromUsedLists(M, [&](Constant *C) {
 144     if (auto F = dyn_cast<Function>(C))
 145       return !Reachable.contains(F);
 146
 147     return false;
 148   });
 149
 150   SmallVector<std::reference_wrapper<Function>> ToRemove;
 151   copy_if(M, std::back_inserter(ToRemove), [&](auto &&F) {
 152     return !F.isIntrinsic() && !Reachable.contains(&F);
 153   });
 154
 155   for_each(ToRemove, eraseFromModule<Function>);
 156 }
 157
 158 static inline bool isAcceleratorExecutionRoot(const Function *F) {
 159     if (!F)
 160       return false;
 161
 162     return F->getCallingConv() == CallingConv::AMDGPU_KERNEL;
 163 }
 164
 165 static inline bool checkIfSupported(const Function *F, const CallBase *CB) {
 166   const auto Dx = F->getName().rfind("__hipstdpar_unsupported");
 167
 168   if (Dx == StringRef::npos)
 169     return true;
 170
 171   const auto N = F->getName().substr(0, Dx);
 172
 173   std::string W;
 174   raw_string_ostream OS(W);
 175
 176   if (N == "__ASM")
 177     OS << "Accelerator does not support the ASM block:\n"
 178       << cast<ConstantDataArray>(CB->getArgOperand(0))->getAsCString();
 179   else
 180     OS << "Accelerator does not support the " << N << " function.";
 181
 182   auto Caller = CB->getParent()->getParent();
 183
 184   Caller->getContext().diagnose(
 185     DiagnosticInfoUnsupported(*Caller, W, CB->getDebugLoc(), DS_Error));
 186
 187   return false;
 188 }
 189
 190 PreservedAnalyses
 191   HipStdParAcceleratorCodeSelectionPass::run(Module &M,
 192                                              ModuleAnalysisManager &MAM) {
 193   auto &CGA = MAM.getResult<CallGraphAnalysis>(M);
 194
 195   SmallPtrSet<const Function *, 32> Reachable;
 196   for (auto &&CGN : CGA) {
 197     if (!isAcceleratorExecutionRoot(CGN.first))
 198       continue;
 199
 200     Reachable.insert(CGN.first);
 201
 202     SmallVector<const Function *> Tmp({CGN.first});
 203     do {
 204       auto F = std::move(Tmp.back());
 205       Tmp.pop_back();
 206
 207       for (auto &&N : *CGA[F]) {
 208         if (!N.second)
 209           continue;
 210         if (!N.second->getFunction())
 211           continue;
 212         if (Reachable.contains(N.second->getFunction()))
 213           continue;
 214
 215         if (!checkIfSupported(N.second->getFunction(),
 216                               dyn_cast<CallBase>(*N.first)))
 217           return PreservedAnalyses::none();
 218
 219         Reachable.insert(N.second->getFunction());
 220         Tmp.push_back(N.second->getFunction());
 221       }
 222     } while (!std::empty(Tmp));
 223   }
 224
 225   if (std::empty(Reachable))
 226     clearModule(M);
 227   else
 228     removeUnreachableFunctions(Reachable, M);
 229
 230   maybeHandleGlobals(M);
 231
 232   return PreservedAnalyses::none();
 233 }
 234
 235 static constexpr std::pair<StringLiteral, StringLiteral> ReplaceMap[]{
 236   {"aligned_alloc",             "__hipstdpar_aligned_alloc"},
 237   {"calloc",                    "__hipstdpar_calloc"},
 238   {"free",                      "__hipstdpar_free"},
 239   {"malloc",                    "__hipstdpar_malloc"},
 240   {"memalign",                  "__hipstdpar_aligned_alloc"},
 241   {"posix_memalign",            "__hipstdpar_posix_aligned_alloc"},
 242   {"realloc",                   "__hipstdpar_realloc"},
 243   {"reallocarray",              "__hipstdpar_realloc_array"},
 244   {"_ZdaPv",                    "__hipstdpar_operator_delete"},
 245   {"_ZdaPvm",                   "__hipstdpar_operator_delete_sized"},
 246   {"_ZdaPvSt11align_val_t",     "__hipstdpar_operator_delete_aligned"},
 247   {"_ZdaPvmSt11align_val_t",    "__hipstdpar_operator_delete_aligned_sized"},
 248   {"_ZdlPv",                    "__hipstdpar_operator_delete"},
 249   {"_ZdlPvm",                   "__hipstdpar_operator_delete_sized"},
 250   {"_ZdlPvSt11align_val_t",     "__hipstdpar_operator_delete_aligned"},
 251   {"_ZdlPvmSt11align_val_t",    "__hipstdpar_operator_delete_aligned_sized"},
 252   {"_Znam",                     "__hipstdpar_operator_new"},
 253   {"_ZnamRKSt9nothrow_t",       "__hipstdpar_operator_new_nothrow"},
 254   {"_ZnamSt11align_val_t",      "__hipstdpar_operator_new_aligned"},
 255   {"_ZnamSt11align_val_tRKSt9nothrow_t",
 256                                 "__hipstdpar_operator_new_aligned_nothrow"},
 257
 258   {"_Znwm",                     "__hipstdpar_operator_new"},
 259   {"_ZnwmRKSt9nothrow_t",       "__hipstdpar_operator_new_nothrow"},
 260   {"_ZnwmSt11align_val_t",      "__hipstdpar_operator_new_aligned"},
 261   {"_ZnwmSt11align_val_tRKSt9nothrow_t",
 262                                 "__hipstdpar_operator_new_aligned_nothrow"},
 263   {"__builtin_calloc",          "__hipstdpar_calloc"},
 264   {"__builtin_free",            "__hipstdpar_free"},
 265   {"__builtin_malloc",          "__hipstdpar_malloc"},
 266   {"__builtin_operator_delete", "__hipstdpar_operator_delete"},
 267   {"__builtin_operator_new",    "__hipstdpar_operator_new"},
 268   {"__builtin_realloc",         "__hipstdpar_realloc"},
 269   {"__libc_calloc",             "__hipstdpar_calloc"},
 270   {"__libc_free",               "__hipstdpar_free"},
 271   {"__libc_malloc",             "__hipstdpar_malloc"},
 272   {"__libc_memalign",           "__hipstdpar_aligned_alloc"},
 273   {"__libc_realloc",            "__hipstdpar_realloc"}
 274 };
 275
 276 PreservedAnalyses
 277 HipStdParAllocationInterpositionPass::run(Module &M, ModuleAnalysisManager&) {
 278   SmallDenseMap<StringRef, StringRef> AllocReplacements(std::cbegin(ReplaceMap),
 279                                                         std::cend(ReplaceMap));
 280
 281   for (auto &&F : M) {
 282     if (!F.hasName())
 283       continue;
 284     if (!AllocReplacements.contains(F.getName()))
 285       continue;
 286
 287     if (auto R = M.getFunction(AllocReplacements[F.getName()])) {
 288       F.replaceAllUsesWith(R);
 289     } else {
 290       std::string W;
 291       raw_string_ostream OS(W);
 292
 293       OS << "cannot be interposed, missing: " << AllocReplacements[F.getName()]
 294         << ". Tried to run the allocation interposition pass without the "
 295         << "replacement functions available.";
 296
 297       F.getContext().diagnose(DiagnosticInfoUnsupported(F, W,
 298                                                         F.getSubprogram(),
 299                                                         DS_Warning));
 300     }
 301   }
 302
 303   if (auto F = M.getFunction("__hipstdpar_hidden_free")) {
 304     auto LibcFree = M.getOrInsertFunction("__libc_free", F->getFunctionType(),
 305                                           F->getAttributes());
 306     F->replaceAllUsesWith(LibcFree.getCallee());
 307
 308     eraseFromModule(*F);
 309   }
 310
 311   return PreservedAnalyses::none();
 312 }