[LoopVectorize] Use OpenMP vector routines.

[fpetrogalli]

Summary

This patch enables the vectorizer to use the vector routines generated by clang with a OpenMP directive "#pragma omp declare simd".

The mapping "scalar name" -> "vector function" in the TargetLibraryInfo (TLI) is enriched with the vector function signature to account for the different vector function that can be associated to a scalar one by specifying "linear" or "uniform" parameter clauses in the "declare simd" directive.

[fpetrogalli]

Rebase plus clang format.

[fhahn]

lib/Analysis/TargetLibraryInfo.cpp

1193

Can this be removed?

1342

It looks like the FTy argument is assigned to (line 1346) before it is used (line 1348). Is this intentional?

[rengolin]

Just a high level question: why can't this extend the same insert mechanism we already use for the other vectorised functions, instead of creating a new one for OpenMP?

[fpetrogalli]

In D27249#610351, @rengolin wrote:

Just a high level question: why can't this extend the same insert mechanism we already use for the other vectorised functions, instead of creating a new one for OpenMP?

Hi Renato,

I am preparing a RFC email for the dev channel explaining my view on
this change. My short answer here is that the mapping ("scalar name" ,
"vectorization factor (VF)") into "vector name" that is currently
implemented in the TLI does not cover all the signatures of the
multiple vector variants that can be associated to a scalar function
by means of attaching "declare simd" directive to the function
declaration or definition.

Consider this example:

#pragma omp declare simd
#pragma omp declare simd uniform(y)
double pow(double x, double y)

In this case the user is asking the compiler to be aware of two vector
version available. With the current mapping it would generate two
entries for each VF (assuming VF = 4):

("pow", 4) -> "pow_vector_vector"
("pow", 4) -> "pow_vector_uniform_vector"

I made up the vector names, but you can see that with this mapping the
vectorizer doesn't have a way to choose the vector_vector version over
the vector_uniform_vector one. Of course, one could implement a "name
generation" in the vectorizer and search over the full triple
(scalar_name, VF, vector_name) until a match is found, but such
vector_name generator in the vectorizer should be target dependent, as
each architecture will come up with it's own vector ABI that mangle
the scalar name into the vector name.

With this solution one could rely in the vector signature of the
function using the multimap that maps scalar names into (vector names,
vector signatures).

In this case, the "pow" example before would generates this item in
the multimap:

"pow" -> [(pow_vector_vector, <double x 4>(<double x 4>,<double x 4>)),
          (pow_vector_uniform_vector, <double x 4>(<double x 4>, double))]

The "pow_vector_uniform_vector" here is clearly different because the
uniform parameter is kept as a scalar. This is just an example, things
can get even more complicated when both "linear" (and associated
modifiers "var", "uval", "val" and "ref") are used in directive.

With this multimap, the vectorizer wouldn't have to make up the vector
name for the matching. I think this is better because it skips the
need to write a target-dependent vector ABI name mangling method in
the vectorizer.

I am aware that the signature mapping method is not complete -
e.g. how do distinguish a step=2 from a step=3 in a linear clause of
the same parameter in the function signature. Nevertheless, even in
this situation using the function signature has the advantage of
providing a structure (the FunctionType) that can be used to attach
linear/uniform descriptors to vector or scalar parameters without
introducing new structures holding the parameter position.

I'll add this comment to the RFC, and extend it with more examples.

Cheers,

Francesco

[fpetrogalli]

I have removed all reviewers, this is not intended for code review.

[fpetrogalli]

Updates:

1. rebase
2. Fix bug in copy constructor of the TargetLibraryInfoImpl class - I have missed copying out the multimap needed in the algorithm
3. Fix bug in the TLII::mangle method (now it returns a std::string instead of a StringRef)

No changes have been introduced in the scalar/vector function matching algorithm.

[xtian]

All, as we discussed, we agree to follow the GCC VectorABI and be GCC VectorABI compatible, right? It could be happened, I am looking at an old patch. Thanks.

[fpetrogalli]

This is just a rebase with a recent llvm codebase.

[fpetrogalli]

In D27249#652734, @xtian wrote:

All, as we discussed, we agree to follow the GCC VectorABI and be GCC VectorABI compatible, right? It could be happened, I am looking at an old patch. Thanks.

Hi Xinmin,

thanks for keeping an eye on this. I have updated the clang patch which now implements the GCC VectorABI - see https://reviews.llvm.org/D27250.

I understand this is not how the community has designed the work to be done around the implementation of "pragma omp declare simd" in the compiler: with my patch set one cannot tests each step of the compiler separately, as the information about the availability of vector function is passed directly from the front-end to the TargetLibraryInfo. What is really needed is something that writes the info in the IR - like the vector names as string attributes - so that the vectorizer in "opt" could be tested without the need of interfacing it with a particular front-end.

Now that I understand this need, I fully agree with you that we should use persistent information in the IR. I only wonder if there is some values in enabling my solution temporarily while the new proposed metadata for parallel metadata finds is way in ([RFC] IR-level Region Annotations [1]), as I think that the TargetLibraryInfo approach enables interfacing clang and teh vectorizer with external libraries.

[1] http://lists.llvm.org/pipermail/llvm-dev/2017-January/108906.html

include/llvm/Analysis/TargetLibraryInfo.h

 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/Triple.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/Pass.h"
+#include <set>
 
 namespace llvm {
 template <typename T> class ArrayRef;
 
 /// Describes a possible vectorization of a function.
 /// Function 'VectorFnName' is equivalent to 'ScalarFnName' vectorized
 /// by a factor 'VectorizationFactor'.
 struct VecDesc {
   StringRef ScalarFnName;
   StringRef VectorFnName;
   unsigned VectorizationFactor;
 };
 
+/// Describes a vector function, by Name and Signature.
+struct VectorFnInfo {
+  std::string Name;
+  FunctionType * Signature;
+};
+
   namespace LibFunc {
     enum Func {
 #define TLI_DEFINE_ENUM
 #include "llvm/Analysis/TargetLibraryInfo.def"
 
       NumLibFuncs
     };
   }
 
 /// Implementation of the target library information.
 ///
 /// This class constructs tables that hold the target library information and
 /// make it available. However, it is somewhat expensive to compute and only
 /// depends on the triple. So users typically interact with the \c
 /// TargetLibraryInfo wrapper below.
 class TargetLibraryInfoImpl {
   friend class TargetLibraryInfo;
 
   unsigned char AvailableArray[(LibFunc::NumLibFuncs+3)/4];
   llvm::DenseMap<unsigned, std::string> CustomNames;
   static StringRef const StandardNames[LibFunc::NumLibFuncs];
   bool ShouldExtI32Param, ShouldExtI32Return, ShouldSignExtI32Param;
 
+  /// Holds the mapping between a scalar function and its available vector
+  /// versions.
+  std::multimap<std::string, VectorFnInfo> VectorFunctionInfo;
+
   enum AvailabilityState {
     StandardName = 3, // (memset to all ones)
     CustomName = 1,
     Unavailable = 0  // (memset to all zeros)
   };
   void setState(LibFunc::Func F, AvailabilityState State) {
     AvailableArray[F/4] &= ~(3 << 2*(F&3));
     AvailableArray[F/4] |= State << 2*(F&3);
public:
   }
 
   /// Return true if the function F has a vector equivalent with any
   /// vectorization factor.
   bool isFunctionVectorizable(StringRef F) const;
 
   /// Return the name of the equivalent of F, vectorized with factor VF. If no
   /// such mapping exists, return the empty string.
-  StringRef getVectorizedFunction(StringRef F, unsigned VF) const;
+  StringRef getVectorizedFunction(StringRef F, unsigned VF,
+                                  FunctionType * Sign = nullptr) const;
 
   /// Return true if the function F has a scalar equivalent, and set VF to be
   /// the vectorization factor.
-  bool isFunctionScalarizable(StringRef F, unsigned &VF) const {
-    return !getScalarizedFunction(F, VF).empty();
+  bool isFunctionVectorizable(StringRef F, unsigned VF,
+                              FunctionType * Sign) const {
+    return !getVectorizedFunction(F, VF, Sign).empty();
   }
 
   /// Return the name of the equivalent of F, scalarized. If no such mapping
   /// exists, return the empty string.
   ///
   /// Set VF to the vectorization factor.
   StringRef getScalarizedFunction(StringRef F, unsigned &VF) const;
 
void setShouldExtI32Return(bool Val) {
     ShouldExtI32Return = Val;
   }
 
   /// Set to true iff i32 parameters to library functions should have signext
   /// attribute if they correspond to C-level int or unsigned int.
   void setShouldSignExtI32Param(bool Val) {
     ShouldSignExtI32Param = Val;
   }
+  /// Adds vector routines that are available as global external function
+  /// pointers in the module \param M.
+  void addOpenMPVectorFunctions(Module * M);
+
+  /// Demangle a scalar/vector mangled name
+  static std::pair<StringRef, StringRef> demangle(const StringRef In);
+
+  /// Checks the validity of a mangled scalar/vector name.
+  static bool isMangledName(StringRef Name);
+
+  /// Check the validity of \param Ty to be used as a vector function
+  /// signature. If so, it sets \param FTy to the vector function signature.
+  static bool isValidSignature(Type *Ty, FunctionType *&FTY);
+
+  /// Mangles \param VecName and \param ScalarName using a prefix, a middlefix
+  /// and a suffix.
+  static StringRef mangle(const StringRef VecName, const StringRef ScalarName);
 };
 
 /// Provides information about what library functions are available for
 /// the current target.
 ///
 /// This both allows optimizations to handle them specially and frontends to
 /// disable such optimizations through -fno-builtin etc.
 class TargetLibraryInfo {
public:
   bool getLibFunc(const Function &FDecl, LibFunc::Func &F) const {
     return Impl->getLibFunc(FDecl, F);
   }
 
   /// Tests whether a library function is available.
   bool has(LibFunc::Func F) const {
     return Impl->getState(F) != TargetLibraryInfoImpl::Unavailable;
   }
-  bool isFunctionVectorizable(StringRef F, unsigned VF) const {
-    return Impl->isFunctionVectorizable(F, VF);
+  bool isFunctionVectorizable(StringRef F, unsigned VF,
+                              FunctionType * Sign) const {
+    return Impl->isFunctionVectorizable(F, VF, Sign);
   }
   bool isFunctionVectorizable(StringRef F) const {
     return Impl->isFunctionVectorizable(F);
   }
-  StringRef getVectorizedFunction(StringRef F, unsigned VF) const {
-    return Impl->getVectorizedFunction(F, VF);
+  StringRef getVectorizedFunction(StringRef F, unsigned VF,
+                                  FunctionType * Sign) const {
+    return Impl->getVectorizedFunction(F, VF, Sign);
   }
 
   /// Tests if the function is both available and a candidate for optimized code
   /// generation.
   bool hasOptimizedCodeGen(LibFunc::Func F) const {
     if (Impl->getState(F) == TargetLibraryInfoImpl::Unavailable)
       return false;
     switch (F) {

lib/Analysis/TargetLibraryInfo.cpp

 bool TargetLibraryInfoImpl::isFunctionVectorizable(StringRef funcName) const {
   funcName = sanitizeFunctionName(funcName);
   if (funcName.empty())
     return false;
 
   std::vector<VecDesc>::const_iterator I = std::lower_bound(
       VectorDescs.begin(), VectorDescs.end(), funcName,
       compareWithScalarFnName);
-  return I != VectorDescs.end() && StringRef(I->ScalarFnName) == funcName;
+  //  return I != VectorDescs.end() && StringRef(I->ScalarFnName) == funcName;
+  if ( I != VectorDescs.end())
+    return StringRef(I->ScalarFnName) == funcName;
+
+  return VectorFunctionInfo.find(funcName.str()) != VectorFunctionInfo.end();
 }
 
 StringRef TargetLibraryInfoImpl::getVectorizedFunction(StringRef F,
-                                                       unsigned VF) const {
+                                                       unsigned VF,
+                                                       FunctionType * Sign) const {
   F = sanitizeFunctionName(F);
   if (F.empty())
     return F;
   std::vector<VecDesc>::const_iterator I = std::lower_bound(
       VectorDescs.begin(), VectorDescs.end(), F, compareWithScalarFnName);
   while (I != VectorDescs.end() && StringRef(I->ScalarFnName) == F) {
     if (I->VectorizationFactor == VF)
       return I->VectorFnName;
     ++I;
   }
+
+  auto Range = llvm::make_range(VectorFunctionInfo.equal_range(F.str()));
+  for (auto VecInfo : Range) {
+    if (VecInfo.second.Signature == Sign)
+      return VecInfo.second.Name;
+  }
+
   return StringRef();
 }
 
 StringRef TargetLibraryInfoImpl::getScalarizedFunction(StringRef F,
                                                        unsigned &VF) const {
   F = sanitizeFunctionName(F);
   if (F.empty())
     return F;

 AnalysisKey TargetLibraryAnalysis::Key;
 
 // Register the basic pass.
 INITIALIZE_PASS(TargetLibraryInfoWrapperPass, "targetlibinfo",
                 "Target Library Information", false, true)
 char TargetLibraryInfoWrapperPass::ID = 0;
 
 void TargetLibraryInfoWrapperPass::anchor() {}
+
+void TargetLibraryInfoImpl::addOpenMPVectorFunctions(Module * M) {
+  for (auto &GV : M->globals()) {
+    auto Name = GV.getName();
+    //Skip invalid names
+    if (!isMangledName(Name))
+      continue;
+
+    const auto Ty = GV.getType();
+    FunctionType * FTy;
+    // Skip invalid types
+    if (!isValidSignature(Ty, FTy))
+      continue;
+
+    const auto Names  = demangle(Name);
+    const VectorFnInfo VecInfo = {Names.first,  FTy};
+    VectorFunctionInfo.emplace(Names.second, VecInfo);
+  }
+}
+
+namespace {
+bool checkTys(ArrayRef<Type *> Params) {
+  for (auto &Ty : Params) {
+    if (Ty->isVectorTy())
+      return true;
+  }
+  return false;
+}
+
+const StringRef Prefix = "vec_prefix_";
+const StringRef Postfix = "_vec_postfix";
+const StringRef Midfix = "_vec_midfix_";
+}
+
+std::pair<StringRef, StringRef>
+TargetLibraryInfoImpl::demangle(const StringRef In) {
+  StringRef Out = In.drop_back(Postfix.size());
+  StringRef Tmp = Out.drop_front(Prefix.size());
+  return Tmp.split(Midfix);
+}
+
+bool TargetLibraryInfoImpl::isMangledName(const StringRef Name) {
+  const bool HasPrefix = Name.startswith(Prefix);
+  const bool HasSuffix = Name.endswith(Postfix);
+  const bool HasMidfix = Name.contains(Midfix);
+
+  if (HasPrefix && HasMidfix && HasSuffix) {
+    auto Split = demangle(Name);
+    return !Split.first.empty() && !Split.second.empty();
+  }
+
+  return false;
+}
+
+bool TargetLibraryInfoImpl::isValidSignature(Type *Ty, FunctionType *&FTy) {
+  if (!Ty->isPointerTy())
+    return false;
+
+  FTy = dyn_cast<FunctionType>(Ty->getPointerElementType());
+
+  if (!FTy)
+    return false;
+
+  auto RetTy = FTy->getReturnType();
+
+  if (RetTy->isVectorTy())
+    return true;
+
+  return RetTy->isVoidTy() && checkTys(FTy->params());
+}
+
+StringRef TargetLibraryInfoImpl::mangle(const StringRef VecName,
+                                        const StringRef ScalarName) {
+  const std::string Ret = Prefix.str() + VecName.str() + Midfix.str() +
+                          ScalarName.str() + Postfix.str();
+  return Ret;
+}

lib/Transforms/Vectorize/LoopVectorize.cpp

   // packing the return values to a vector.
   unsigned ScalarizationCost = getScalarizationOverhead(Tys, RetTy, TTI);
 
   unsigned Cost = ScalarCallCost * VF + ScalarizationCost;
 
   // If we can't emit a vector call for this function, then the currently found
   // cost is the cost we need to return.
   NeedToScalarize = true;
-  if (!TLI || !TLI->isFunctionVectorizable(FnName, VF) || CI->isNoBuiltin())
+  if (!TLI ||
+      !TLI->isFunctionVectorizable(FnName, VF,
+                                   FunctionType::get(RetTy, Tys, false)) ||
+      CI->isNoBuiltin())
+  //  if (!TLI || !TLI->isFunctionVectorizable(FnName, VF) || CI->isNoBuiltin())
     return Cost;
 
   // If the corresponding vector cost is cheaper, return its cost.
   unsigned VectorCallCost = TTI.getCallInstrCost(nullptr, RetTy, Tys);
   if (VectorCallCost < Cost) {
     NeedToScalarize = false;
     return VectorCallCost;
   }

         if (UseVectorIntrinsic) {
           // Use vector version of the intrinsic.
           Type *TysForDecl[] = {CI->getType()};
           if (VF > 1)
             TysForDecl[0] = VectorType::get(CI->getType()->getScalarType(), VF);
           VectorF = Intrinsic::getDeclaration(M, ID, TysForDecl);
         } else {
           // Use vector version of the library call.
-          StringRef VFnName = TLI->getVectorizedFunction(FnName, VF);
+          //          StringRef VFnName = TLI->getVectorizedFunction(FnName, VF);
+          FunctionType *FTy = FunctionType::get(RetTy, Tys, false);
+          StringRef VFnName = TLI->getVectorizedFunction(FnName, VF, FTy);
           assert(!VFnName.empty() && "Vector function name is empty.");
           VectorF = M->getFunction(VFnName);
           if (!VectorF) {
             // Generate a declaration
-            FunctionType *FTy = FunctionType::get(RetTy, Tys, false);
+            //            FunctionType *FTy = FunctionType::get(RetTy, Tys, false);
             VectorF =
                 Function::Create(FTy, Function::ExternalLinkage, VFnName, M);
             VectorF->copyAttributesFrom(F);
           }
         }
         assert(VectorF && "Can't create vector function.");
 
         SmallVector<OperandBundleDef, 1> OpBundles;

unittests/Analysis/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Analysis
   AsmParser
   Core
   Support
   )
 
 add_llvm_unittest(AnalysisTests
   AliasAnalysisTest.cpp
   BlockFrequencyInfoTest.cpp
   CallGraphTest.cpp
   CFGTest.cpp
   CGSCCPassManagerTest.cpp
   LazyCallGraphTest.cpp
   LoopPassManagerTest.cpp
+  OpenMP.cpp
   ScalarEvolutionTest.cpp
   TBAATest.cpp
   ValueTrackingTest.cpp
   UnrollAnalyzer.cpp
   )

unittests/Analysis/OpenMP.cpp

+#include "llvm/Support/SourceMgr.h"
+#include "llvm/AsmParser/Parser.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IRReader/IRReader.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/Analysis/TargetLibraryInfo.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+namespace {
+const std::string Pre = "vec_prefix_";
+const std::string Post = "_vec_postfix";
+const std::string Mid = "_vec_midfix_";
+}
+
+TEST(OpenMP, isMangledName) {
+  using TLI = TargetLibraryInfoImpl;
+
+  // valid names
+  EXPECT_TRUE(TLI::isMangledName("vec_prefix_vfoo_vec_midfix_foo_vec_postfix"));
+  EXPECT_TRUE(TLI::isMangledName("vec_prefix_v_vec_midfix_f_vec_postfix"));
+
+  // wrong prefix/midfix/postfix
+  EXPECT_FALSE(TLI::isMangledName("vec_prefix_vfoo_vec_midfix_foo_ec_postfix"));
+  EXPECT_FALSE(TLI::isMangledName("ec_prefix_vfoo_vec_midfix_foo_vec_postfix"));
+  EXPECT_FALSE(TLI::isMangledName("vec_prefix_vfoo_ve_midfix_foo_vec_postfix"));
+
+  // no function names
+  EXPECT_FALSE(TLI::isMangledName("vec_prefix__vec_midfix__vec_postfix"));
+  EXPECT_FALSE(TLI::isMangledName("vec_prefix__vec_midfix_xxxx_vec_postfix"));
+  EXPECT_FALSE(TLI::isMangledName("vec_prefix_xxxx_vec_midfix__vec_postfix"));
+}
+
+TEST(OpenMPTest, GlobalValueSignatures) {
+  using TLI = TargetLibraryInfoImpl;
+  LLVMContext C;
+  FunctionType *DummyTy;
+
+  // invalid: not pointers to functions
+  EXPECT_FALSE(TLI::isValidSignature(Type::getDoubleTy(C), DummyTy));
+  EXPECT_FALSE(TLI::isValidSignature(Type::getDoublePtrTy(C), DummyTy));
+  auto FTy = FunctionType::get(Type::getDoubleTy(C), false);
+  EXPECT_FALSE(TLI::isValidSignature(FTy, DummyTy));
+
+  // invalid function pointer: not a valid signature
+  EXPECT_FALSE(TLI::isValidSignature(FTy->getPointerTo(), DummyTy));
+
+  // invalid: a function returning void with not valid input parameters
+  const ArrayRef<Type *> NoTys = {Type::getDoublePtrTy(C), Type::getInt64Ty(C)};
+  auto VoidFTy = FunctionType::get(Type::getVoidTy(C), NoTys, false);
+  EXPECT_FALSE(TLI::isValidSignature(VoidFTy->getPointerTo(), DummyTy));
+
+  // valid: pointer to function returning vector
+  auto VFTy =
+      FunctionType::get(VectorType::get(Type::getDoubleTy(C), 4), false);
+  EXPECT_TRUE(TLI::isValidSignature(VFTy->getPointerTo(), DummyTy));
+
+  // valid: pointer to function returning void with at least one vector
+  // parameter
+  const ArrayRef<Type *> Tys = {Type::getDoublePtrTy(C),
+                                VectorType::get(Type::getDoubleTy(C), 4)};
+  auto VoidVFTy = FunctionType::get(Type::getVoidTy(C), Tys, false);
+  EXPECT_TRUE(TLI::isValidSignature(VoidVFTy->getPointerTo(), DummyTy));
+}
+
+TEST(OpenMP, Mangle) {
+  const StringRef VF("vfoo");
+  const StringRef F("foo");
+  const StringRef Out = TargetLibraryInfoImpl::mangle(VF, F);
+
+  EXPECT_STREQ("vec_prefix_vfoo_vec_midfix_foo_vec_postfix", Out.data());
+}
+
+TEST(OpenMP, Demangle) {
+  StringRef In = "vec_prefix_vfoo_vec_midfix_foo_vec_postfix";
+
+  const std::pair<StringRef, StringRef> Out =
+      TargetLibraryInfoImpl::demangle(In);
+
+  const StringRef VF = "vfoo";
+  const StringRef F = "foo";
+
+  EXPECT_EQ(VF, Out.first);
+  EXPECT_EQ(F, Out.second);
+}
+
+TEST(OpenMPTest, NotValidGlobals) {
+  LLVMContext C;
+  std::unique_ptr<Module> M(new Module("Test", C));
+
+  const StringRef Mangled = TargetLibraryInfoImpl::mangle("vector", "scalar");
+  const auto Ty = FunctionType::get(Type::getDoubleTy(C), false);
+  M->getOrInsertGlobal(Mangled, Ty);
+
+  TargetLibraryInfoImpl TLII;
+  TargetLibraryInfo TLI(TLII);
+  TLII.addOpenMPVectorFunctions(M.get());
+  EXPECT_FALSE(TLI.isFunctionVectorizable("scalar"));
+}
+
+TEST(OpenMPTest, ValidGlobals) {
+  LLVMContext C;
+  std::unique_ptr<Module> M(new Module("Test", C));
+
+  const auto VFTy =
+      FunctionType::get(VectorType::get(Type::getDoubleTy(C), 4), false);
+  M->getOrInsertGlobal("vec_prefix_vector_vec_midfix_scalar_vec_postfix", VFTy);
+
+  TargetLibraryInfoImpl TLII;
+  TargetLibraryInfo TLI(TLII);
+  TLII.addOpenMPVectorFunctions(M.get());
+  EXPECT_TRUE(TLI.isFunctionVectorizable("scalar"));
+}