[SLPVectorizer] handle vectorized lib functions

[sanwou01]

Summary

Teaches the SLPVectorizer to use vectorized library functions for
non-intrinsic calls.

This already worked for intrinsics that have vectorized library
functions, thanks to D75878, but schedules with library functions with a
vector variant were being rejected early.

• assume that there are no load/store dependencies between lib functions with a vector variant; this would otherwise prevent the bundle from becoming "ready"

• check during legalization that the vector variant can be used

• fix-up where we previously assumed that a call would be an intrinsic

[fhahn]

Thanks for the patch. Some comments inline

llvm/include/llvm/Analysis/VectorUtils.h

227 ↗

(On Diff #273348)

unrelated to the change? If so, better to split it off (and perhaps add a test independent of SLP?)

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

3036

please run clang format-diff on the patch,

3062

Please strip the unrelated whitespace changes.

5092

This is a NFC change, right? Would be good to split off and commit separately. Looks like an independent improvement.

llvm/test/Transforms/SLPVectorizer/AArch64/accelerate-vector-functions.ll

16 ↗

(On Diff #273348)

It would be good to pre-commit the test and then only have the diff of the changes here.

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

3035–3036

Formatting

llvm/test/Transforms/SLPVectorizer/AArch64/accelerate-vector-functions.ll

12 ↗

(On Diff #273348)

Pre-commit the new tests with the current results to see the changes

[sanwou01]

Addressed comments

llvm/include/llvm/Analysis/VectorUtils.h

227 ↗

(On Diff #273348)

The underlying problem here is that if getVFABIMappings is called with an indirect call instruction, it'll call getName() on a nullptr. I suspect other callers take care not to do that, making it a latent bug without the rest of this patch.

Agreed though that it deserves its own patch and test; not sure if I can write a test independent of SLP though.

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

5092

I've split the NFC bit off and will commit that first.

[sanwou01]

Ah, I missed the test changes this time round. Incoming.

[sanwou01]

Now with test changes

[sanwou01]

ping?

[RKSimon]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

3042

NFC rename?

4548

This looks like a separate NFC?

[sanwou01]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

3042

Sure, I can split that off

4548

Not sure if I'd call this NFC. It fixes a crash when !UseIntrinsic and there is no intrinsic, only a LibFunc, for the call. This patch makes that condition possible here.

Could do as a separate patch though, if that makes sense.

[sanwou01]

Split out NFC rename

[RKSimon]

@ABataev any more comments?

[ABataev]

In D82550#2130742, @RKSimon wrote:

@ABataev any more comments?

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

3030

Is this a pointer? Then auto *.

5121

Why do you need to exclude vectorizable library functions here?

[sanwou01]

Comments inline.

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

3030

Surprisingly no! I'll remove auto to avoid the confusion.

5121

For "normal" function calls, we have to assume that the functions may read or write memory any location in memory, which may alias memory read or written by another instruction in the same bundle. For functions with vector variants, we should be able to assume that they are pure: they won't write to memory (except when the function takes pointer arguments, which I'm not handling correctly now that I think about it; I'll fix that up).

Actually, the calculateDependencies function below might be the less-surprising place to handle this.

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

5121

Then it is better to add correct attributes to such functions. Special processing may lead to problems later.

[sanwou01]

Addressed comments.

• Moved handling of vector lib memory dependencies to calculateDependencies

• Fixed memory dependencies of library functions that take pointers as arguments

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

5200

Still, this is a bad solution. Add proper attributes to the vector variants of the functions, so all memory access interfaces could properly handle such functions.

[fpetrogalli]

Hi @sanwou01 , thank you for working on this!

I left a couple of comments.

Additional question: you seem to be testing only math functions. But it seems that your code would be working with any function that has the vector function abi variant attribute attached. Mmight be worth adding a test for a generic function?

Kind regards,

Francesco

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

3031

Please describe the false parameter like you have done for /*HasGlobalPred*/.

4545

M is used only inside getDeclaration, no need to declare a variable for it.

5110

I suspect there are many things that may fail here, other than not having a mapping in VFDatabase or having pointer arguments. I think it would be safer to reverse the logic, and have the function return false by default, and return true if VFDatabase is not empty and there is no pointer arguments.

5200

HI @ABataev, if I understood correctly, you are asking to add a new attribute that guaranteed that the function does not have side effects? If that's the case, that is already guaranteed by the vector-function-abi-variant attribute.

llvm/test/Transforms/SLPVectorizer/AArch64/accelerate-vector-functions.ll

66 ↗

(On Diff #275712)

Nice! :)

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

5200

Hi. No, what I'm asking is to mark the vectorized function versions with attributes that they don't write to the memory (what this change implies), so all attribute interfaces properly handle such functions as no-write functions.

[fpetrogalli]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

5200

I just had a chat with @sanwou01 , we agreed that it is better to use the VFABI variant attribute just to describe the mapping, and have other attributes (like readonly) attached to the function to guarantee the fact that there is not side effects.

@sanwou01 is coming up with a unit test in which a function is marked with both the readonly and vector-function-abi-variant. Is there any other attribute he should add to guarantee that the memory accesses are compatible with a concurrent invocation of the function?

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

5200

Maybe, nosync attribute?

[sanwou01]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

5200

Agreed that relying on the proper attributes is much cleaner.

nosync is too weak, it only guarantees no communication between threads e.g. through the absence of volatile, not between subsequent calls on the main thread.

readonly would be sufficient for most math functions. argmemonly would be the right attribute for functions that take pointers (possibly with readonly), but we'd have to check aliasing in that case.

Also note that the attribute has to be set on the original scalar function (that's what's being checked here); the vector variant, by being an implementation of the scalar function, should also conform to the attribute.

[sanwou01]

Updates to address feedback, in particular:

• use readonly attribute to determine memory dependencies between call instructions, and update tests accordingly

• add a standalone test that does not rely on -vector-library

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

4545

I'm just moving some pre-existing code into an else clause here. I can still tidy this up if you prefer, but perhaps in a follow-up NFC?

5110

As discussed below, we can rely on the existing readonly attribute here, so this helper function is no longer needed, and removed.

[ABataev]

LG

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

case Instruction::Store: {
 
       BS.cancelScheduling(VL, VL0);
       newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx,
                    ReuseShuffleIndicies);
       LLVM_DEBUG(dbgs() << "SLP: Non-consecutive store.\n");
       return;
     }
     case Instruction::Call: {
-      // Check if the calls are all to the same vectorizable intrinsic.
+      // Check if the calls are all to the same vectorizable intrinsic or
+      // library function.
       CallInst *CI = cast<CallInst>(VL0);
-      // Check if this is an Intrinsic call or something that can be
-      // represented by an intrinsic call
       Intrinsic::ID ID = getVectorIntrinsicIDForCall(CI, TLI);
-      if (!isTriviallyVectorizable(ID)) {
+
+      auto Shape =
+          VFShape::get(*CI, {static_cast<unsigned int>(VL.size()), false},
+                       false /*HasGlobalPred*/);
+      Function *VecFunc = VFDatabase(*CI).getVectorizedFunction(Shape);
+
+      if (!VecFunc && !isTriviallyVectorizable(ID)) {
         BS.cancelScheduling(VL, VL0);
         newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx,
                      ReuseShuffleIndicies);
         LLVM_DEBUG(dbgs() << "SLP: Non-vectorizable call.\n");
         return;
       }
-      Function *Int = CI->getCalledFunction();
+      Function *F = CI->getCalledFunction();
       unsigned NumArgs = CI->getNumArgOperands();
       SmallVector<Value*, 4> ScalarArgs(NumArgs, nullptr);
       for (unsigned j = 0; j != NumArgs; ++j)
         if (hasVectorInstrinsicScalarOpd(ID, j))
           ScalarArgs[j] = CI->getArgOperand(j);
       for (Value *V : VL) {
         CallInst *CI2 = dyn_cast<CallInst>(V);
-        if (!CI2 || CI2->getCalledFunction() != Int ||
+        if (!CI2 || CI2->getCalledFunction() != F ||
             getVectorIntrinsicIDForCall(CI2, TLI) != ID ||
+            (VecFunc &&
+             VecFunc != VFDatabase(*CI2).getVectorizedFunction(Shape)) ||
             !CI->hasIdenticalOperandBundleSchema(*CI2)) {
           BS.cancelScheduling(VL, VL0);
           newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx,
                        ReuseShuffleIndicies);
           LLVM_DEBUG(dbgs() << "SLP: mismatched calls:" << *CI << "!=" << *V
                             << "\n");
           return;
         }
         // Some intrinsics have scalar arguments and should be same in order for
         // them to be vectorized.
         for (unsigned j = 0; j != NumArgs; ++j) {
           if (hasVectorInstrinsicScalarOpd(ID, j)) {
             Value *A1J = CI2->getArgOperand(j);
             if (ScalarArgs[j] != A1J) {
               BS.cancelScheduling(VL, VL0);
               newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx,
                            ReuseShuffleIndicies);
case Instruction::Call: {
 
       Intrinsic::ID IID  = Intrinsic::not_intrinsic;
       if (Function *FI = CI->getCalledFunction())
         IID = FI->getIntrinsicID();
 
       Intrinsic::ID ID = getVectorIntrinsicIDForCall(CI, TLI);
 
       auto VecCallCosts = getVectorCallCosts(CI, VecTy, TTI, TLI);
-      bool UseIntrinsic = VecCallCosts.first <= VecCallCosts.second;
+      bool UseIntrinsic = ID != Intrinsic::not_intrinsic &&
+                          VecCallCosts.first <= VecCallCosts.second;
 
       Value *ScalarArg = nullptr;
       std::vector<Value *> OpVecs;
       for (int j = 0, e = CI->getNumArgOperands(); j < e; ++j) {
         ValueList OpVL;
         // Some intrinsics have scalar arguments. This argument should not be
         // vectorized.
         if (UseIntrinsic && hasVectorInstrinsicScalarOpd(IID, j)) {
           CallInst *CEI = cast<CallInst>(VL0);
           ScalarArg = CEI->getArgOperand(j);
           OpVecs.push_back(CEI->getArgOperand(j));
           continue;
         }
 
         Value *OpVec = vectorizeTree(E->getOperand(j));
         LLVM_DEBUG(dbgs() << "SLP: OpVec[" << j << "]: " << *OpVec << "\n");
         OpVecs.push_back(OpVec);
       }
 
-      Module *M = F->getParent();
-      Type *Tys[] = {FixedVectorType::get(CI->getType(), E->Scalars.size())};
-      Function *CF = Intrinsic::getDeclaration(M, ID, Tys);
-
+      Function *CF;
       if (!UseIntrinsic) {
         VFShape Shape = VFShape::get(
             *CI, {static_cast<unsigned>(VecTy->getNumElements()), false},
             false /*HasGlobalPred*/);
         CF = VFDatabase(*CI).getVectorizedFunction(Shape);
+      } else {
+        Module *M = F->getParent();
+        Type *Tys[] = {FixedVectorType::get(CI->getType(), E->Scalars.size())};
+        CF = Intrinsic::getDeclaration(M, ID, Tys);
       }
 
       SmallVector<OperandBundleDef, 1> OpBundles;
       CI->getOperandBundlesAsDefs(OpBundles);
       Value *V = Builder.CreateCall(CF, OpVecs, OpBundles);
 
       // The scalar argument uses an in-tree scalar so we add the new vectorized
       // call to ExternalUses list to make sure that an extract will be
       // generated in the future.
if (DownIter != LowerEnd) {
       ++DownIter;
     }
     assert((UpIter != UpperEnd || DownIter != LowerEnd) &&
            "instruction not found in block");
   }
   return true;
 }
 
 static bool isSideeffectIntrinsic(Instruction *I) {
   auto *II = dyn_cast<IntrinsicInst>(I);
 
   return II && II->getIntrinsicID() == Intrinsic::sideeffect;
 }
 
+static bool isVectorizableLibFunctionCall(Instruction *I) {
+  auto *CI = dyn_cast<CallInst>(I);
+
+  return CI && !VFDatabase::getMappings(*CI).empty();
+}
+
 void BoUpSLP::BlockScheduling::initScheduleData(Instruction *FromI,
                                                 Instruction *ToI,
                                                 ScheduleData *PrevLoadStore,
                                                 ScheduleData *NextLoadStore) {
   ScheduleData *CurrentLoadStore = PrevLoadStore;
   for (Instruction *I = FromI; I != ToI; I = I->getNextNode()) {
     ScheduleData *SD = ScheduleDataMap[I];
     if (!SD) {
       SD = allocateScheduleDataChunks();
       ScheduleDataMap[I] = SD;
       SD->Inst = I;
     }
     assert(!isInSchedulingRegion(SD) &&
            "new ScheduleData already in scheduling region");
     SD->init(SchedulingRegionID, I);
 
-    if (I->mayReadOrWriteMemory() && !isSideeffectIntrinsic(I)) {
+    if (I->mayReadOrWriteMemory() && !isSideeffectIntrinsic(I) &&
+        !isVectorizableLibFunctionCall(I)) {
       // Update the linked list of memory accessing instructions.
       if (CurrentLoadStore) {
         CurrentLoadStore->NextLoadStore = SD;
       } else {
         FirstLoadStoreInRegion = SD;
       }
       CurrentLoadStore = SD;
     }
while (BundleMember) {
         }
 
         // Handle the memory dependencies.
         ScheduleData *DepDest = BundleMember->NextLoadStore;
         if (DepDest) {
           Instruction *SrcInst = BundleMember->Inst;
           MemoryLocation SrcLoc = getLocation(SrcInst, SLP->AA);
           bool SrcMayWrite = BundleMember->Inst->mayWriteToMemory();
           unsigned numAliased = 0;
           unsigned DistToSrc = 1;
 
           while (DepDest) {
             assert(isInSchedulingRegion(DepDest));
 
             // We have two limits to reduce the complexity:
             // 1) AliasedCheckLimit: It's a small limit to reduce calls to
             //    SLP->isAliased (which is the expensive part in this loop).