[PATCH 22/27] [noalias] SLPVectorizer: load/store can have a ptr_provenance parameter.

[jeroen.dobbelaere]

Summary

This is part of the series started by D68484.

Accept that the ptr_provenance parameter can be there and ignore it. Make sure to omit !noalias metadata when a ptr_provenance was present.

Note: this is a stable point and tests should run fine with the patches applied up to this point.

[jeroen.dobbelaere]

This fixes a build issue in the llvm 'test-suite'.

[jeroen.dobbelaere]

Rebased

[jeroen.dobbelaere]

Rebased to c06b7e2ab5167ad031745a706204abed1aefd823 (July 14, 2020)

[jeroen.dobbelaere]

Rebased to 9fb46a452d4e5666828c95610ceac8dcd9e4ce16 (September 7, 2020)

[jeroen.dobbelaere]

Rebased to f8dbd61074176bae92ec360a093ac7bc498c9321.

llvm/include/llvm/Analysis/VectorUtils.h

 
 /// Specifically, let Kinds = [MD_tbaa, MD_alias_scope, MD_noalias, MD_fpmath,
 /// MD_nontemporal, MD_access_group].
 /// For K in Kinds, we get the MDNode for K from each of the
 /// elements of VL, compute their "intersection" (i.e., the most generic
 /// metadata value that covers all of the individual values), and set I's
 /// metadata for M equal to the intersection value.
 ///
+/// When RemoveNoAlias is true, MD_noalias will always get a null value.
+///
 /// This function always sets a (possibly null) value for each K in Kinds.
-Instruction *propagateMetadata(Instruction *I, ArrayRef<Value *> VL);
+Instruction *propagateMetadata(Instruction *I, ArrayRef<Value *> VL,
+                               bool RemoveNoAlias = true);
 
 /// Create a mask that filters the members of an interleave group where there
 /// are gaps.
 ///
 /// For example, the mask for \p Group with interleave-factor 3
 /// and \p VF 4, that has only its first member present is:
 ///
 ///   <1,0,0,1,0,0,1,0,0,1,0,0>

llvm/lib/Analysis/VectorUtils.cpp

MDNode *llvm::intersectAccessGroups(const Instruction *Inst1,
   if (Intersection.size() == 1)
     return cast<MDNode>(Intersection.front());
 
   LLVMContext &Ctx = Inst1->getContext();
   return MDNode::get(Ctx, Intersection);
 }
 
 /// \returns \p I after propagating metadata from \p VL.
-Instruction *llvm::propagateMetadata(Instruction *Inst, ArrayRef<Value *> VL) {
+Instruction *llvm::propagateMetadata(Instruction *Inst, ArrayRef<Value *> VL,
+                                     bool RemoveNoAlias) {
   Instruction *I0 = cast<Instruction>(VL[0]);
   SmallVector<std::pair<unsigned, MDNode *>, 4> Metadata;
   I0->getAllMetadataOtherThanDebugLoc(Metadata);
 
   for (auto Kind : {LLVMContext::MD_tbaa, LLVMContext::MD_alias_scope,
                     LLVMContext::MD_noalias, LLVMContext::MD_fpmath,
                     LLVMContext::MD_nontemporal, LLVMContext::MD_invariant_load,
                     LLVMContext::MD_access_group}) {
     MDNode *MD = I0->getMetadata(Kind);
 
+    if (RemoveNoAlias && (Kind == LLVMContext::MD_noalias))
+      MD = nullptr;
     for (int J = 1, E = VL.size(); MD && J != E; ++J) {
       const Instruction *IJ = cast<Instruction>(VL[J]);
       MDNode *IMD = IJ->getMetadata(Kind);
       switch (Kind) {
       case LLVMContext::MD_tbaa:
         MD = MDNode::getMostGenericTBAA(MD, IMD);
         break;
       case LLVMContext::MD_alias_scope:
for (int J = 1, E = VL.size(); MD && J != E; ++J) {
         break;
       case LLVMContext::MD_access_group:
         MD = intersectAccessGroups(Inst, IJ);
         break;
       default:
         llvm_unreachable("unhandled metadata");
       }
     }
-
     Inst->setMetadata(Kind, MD);
   }
 
   return Inst;
 }
 
 Constant *
 llvm::createBitMaskForGaps(IRBuilderBase &Builder, unsigned VF,

llvm/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp

PreservedAnalyses LoadStoreVectorizerPass::run(Function &F, FunctionAnalysisManager &AM) {
   bool Changed = V.run();
   PreservedAnalyses PA;
   PA.preserveSet<CFGAnalyses>();
   return Changed ? PA : PreservedAnalyses::all();
 }
 
 // The real propagateMetadata expects a SmallVector<Value*>, but we deal in
 // vectors of Instructions.
-static void propagateMetadata(Instruction *I, ArrayRef<Instruction *> IL) {
+static void propagateMetadata(Instruction *I, ArrayRef<Instruction *> IL,
+                              bool RemoveNoAlias) {
   SmallVector<Value *, 8> VL(IL.begin(), IL.end());
-  propagateMetadata(I, VL);
+  propagateMetadata(I, VL, RemoveNoAlias);
 }
 
 // Vectorizer Implementation
 bool Vectorizer::run() {
   bool Changed = false;
 
   // Scan the blocks in the function in post order.
   for (BasicBlock *BB : post_order(&F)) {
for (unsigned I = 0, E = Chain.size(); I != E; ++I) {
             Builder.CreateBitOrPointerCast(Extract, StoreTy->getScalarType());
 
       Value *Insert =
           Builder.CreateInsertElement(Vec, Extract, Builder.getInt32(I));
       Vec = Insert;
     }
   }
 
+  bool HasProvenance =
+      std::any_of(Chain.begin(), Chain.end(), [](const auto &I) {
+        return cast<StoreInst>(I)->hasNoaliasProvenanceOperand();
+      });
   StoreInst *SI = Builder.CreateAlignedStore(
     Vec,
     Builder.CreateBitCast(S0->getPointerOperand(), VecTy->getPointerTo(AS)),
     Alignment);
-  propagateMetadata(SI, Chain);
+  propagateMetadata(SI, Chain, HasProvenance);
 
   eraseInstructions(Chain);
   ++NumVectorInstructions;
   NumScalarsVectorized += Chain.size();
   return true;
 }
 
 bool Vectorizer::vectorizeLoadChain(
bool Vectorizer::vectorizeLoadChain(
 
   // getVectorizablePrefix already computed getBoundaryInstrs.  The value of
   // Last may have changed since then, but the value of First won't have.  If it
   // matters, we could compute getBoundaryInstrs only once and reuse it here.
   BasicBlock::iterator First, Last;
   std::tie(First, Last) = getBoundaryInstrs(Chain);
   Builder.SetInsertPoint(&*First);
 
+  bool HasProvenance =
+      std::any_of(Chain.begin(), Chain.end(), [](const auto &I) {
+        return cast<LoadInst>(I)->hasNoaliasProvenanceOperand();
+      });
   Value *Bitcast =
       Builder.CreateBitCast(L0->getPointerOperand(), VecTy->getPointerTo(AS));
   LoadInst *LI =
       Builder.CreateAlignedLoad(VecTy, Bitcast, MaybeAlign(Alignment));
-  propagateMetadata(LI, Chain);
+  propagateMetadata(LI, Chain, HasProvenance);
 
   if (VecLoadTy) {
     SmallVector<Instruction *, 16> InstrsToErase;
 
     unsigned VecWidth = VecLoadTy->getNumElements();
     for (unsigned I = 0, E = Chain.size(); I != E; ++I) {
       for (auto Use : Chain[I]->users()) {
         // All users of vector loads are ExtractElement instructions with

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

void InnerLoopVectorizer::addNewMetadata(Instruction *To,
   // If the loop was versioned with memchecks, add the corresponding no-alias
   // metadata.
   if (LVer && (isa<LoadInst>(Orig) || isa<StoreInst>(Orig)))
     LVer->annotateInstWithNoAlias(To, Orig);
 }
 
 void InnerLoopVectorizer::addMetadata(Instruction *To,
                                       Instruction *From) {
-  propagateMetadata(To, From);
+  bool HasProvenance = true;
+  if (auto *SI = dyn_cast<StoreInst>(From)) {
+    HasProvenance = SI->hasNoaliasProvenanceOperand();
+  } else if (auto *LI = dyn_cast<LoadInst>(From)) {
+    HasProvenance = LI->hasNoaliasProvenanceOperand();
+  }
+  propagateMetadata(To, From, HasProvenance);
   addNewMetadata(To, From);
 }
 
 void InnerLoopVectorizer::addMetadata(ArrayRef<Value *> To,
                                       Instruction *From) {
   for (Value *V : To) {
     if (Instruction *I = dyn_cast<Instruction>(V))
       addMetadata(I, From);

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

void setOperandsInOrder() {
           auto *I = cast<Instruction>(Scalars[Lane]);
           assert(I->getNumOperands() == NumOperands &&
                  "Expected same number of operands");
           Operands[OpIdx][Lane] = I->getOperand(OpIdx);
         }
       }
     }
 
+    /// Set the operands of this bundle of load or store instructions in their
+    /// original order.
+    void setLoadStoreOperandsInOrder() {
+      assert(Operands.empty() && "Already initialized?");
+      auto *I0 = cast<Instruction>(Scalars[0]);
+      assert((isa<LoadInst>(I0) || isa<StoreInst>(I0)) &&
+             "Expect a load or store instruction");
+      unsigned NumOperands = isa<LoadInst>(I0) ? 1 : 2;
+
+      // Check if any instruction has a ptr_provenance
+      bool HasProvenance =
+          std::any_of(Scalars.begin(), Scalars.end(), [&](auto *V) {
+            return cast<Instruction>(V)->getNumOperands() != NumOperands;
+          });
+
+      Operands.resize(NumOperands + HasProvenance);
+      unsigned NumLanes = Scalars.size();
+      for (unsigned OpIdx = 0; OpIdx != NumOperands; ++OpIdx) {
+        Operands[OpIdx].resize(NumLanes);
+        for (unsigned Lane = 0; Lane != NumLanes; ++Lane) {
+          auto *I = cast<Instruction>(Scalars[Lane]);
+          assert(((I->getNumOperands() == NumOperands) ||
+                  (I->getNumOperands() == NumOperands + 1)) &&
+                 "Expected same number of operands (ignoring the "
+                 "ptr_provenance");
+          Operands[OpIdx][Lane] = I->getOperand(OpIdx);
+        }
+      }
+
+      if (HasProvenance) {
+        // At least one instruction has a ptr_provenance.
+        // Keep track of the dependencies brought in by it. Later on we will
+        // omit the noalias information.
+        unsigned OpIdx = NumOperands;
+        Operands[OpIdx].resize(NumLanes);
+        for (unsigned Lane = 0; Lane != NumLanes; ++Lane) {
+          auto *I = cast<Instruction>(Scalars[Lane]);
+          if (I->getNumOperands() != NumOperands) {
+            Operands[OpIdx][Lane] = I->getOperand(OpIdx);
+          } else {
+            Operands[OpIdx][Lane] =
+                UndefValue::get(I->getOperand(OpIdx - 1)->getType());
+          }
+        }
+      }
+    }
+
     /// \returns the \p OpIdx operand of this TreeEntry.
     ValueList &getOperand(unsigned OpIdx) {
       assert(OpIdx < Operands.size() && "Off bounds");
       return Operands[OpIdx];
     }
 
     /// \returns the number of operands.
     unsigned getNumOperands() const { return Operands.size(); }
void schedule(ScheduleData *SD, ReadyListType &ReadyList) {
           // ensures that the tree entry has all operands set before reaching
           // this code. Couple of exceptions known at the moment are extracts
           // where their second (immediate) operand is not added. Since
           // immediates do not affect scheduler behavior this is considered
           // okay.
           auto *In = TE->getMainOp();
           assert(In &&
                  (isa<ExtractValueInst>(In) || isa<ExtractElementInst>(In) ||
+                  isa<LoadInst>(In) || isa<StoreInst>(In) ||
                   In->getNumOperands() == TE->getNumOperands()) &&
                  "Missed TreeEntry operands?");
           (void)In; // fake use to avoid build failure when assertions disabled
 
           for (unsigned OpIdx = 0, NumOperands = TE->getNumOperands();
                OpIdx != NumOperands; ++OpIdx)
             if (auto *I = dyn_cast<Instruction>(TE->getOperand(OpIdx)[Lane]))
               DecrUnsched(I);
case Instruction::Load: {
         uint64_t Size = DL->getTypeAllocSize(ScalarTy);
         // Check that the sorted loads are consecutive.
         if (Diff && Diff->getAPInt() == (VL.size() - 1) * Size) {
           if (CurrentOrder.empty()) {
             // Original loads are consecutive and does not require reordering.
             ++NumOpsWantToKeepOriginalOrder;
             TreeEntry *TE = newTreeEntry(VL, Bundle /*vectorized*/, S,
                                          UserTreeIdx, ReuseShuffleIndicies);
-            TE->setOperandsInOrder();
+            TE->setLoadStoreOperandsInOrder();
             LLVM_DEBUG(dbgs() << "SLP: added a vector of loads.\n");
           } else {
             // Need to reorder.
             auto I = NumOpsWantToKeepOrder.try_emplace(CurrentOrder).first;
             ++I->getSecond();
             TreeEntry *TE =
                 newTreeEntry(VL, Bundle /*vectorized*/, S, UserTreeIdx,
                              ReuseShuffleIndicies, I->getFirst());
-            TE->setOperandsInOrder();
+            TE->setLoadStoreOperandsInOrder();
             LLVM_DEBUG(dbgs() << "SLP: added a vector of jumbled loads.\n");
           }
           return;
         }
       }
 
       LLVM_DEBUG(dbgs() << "SLP: Gathering non-consecutive loads.\n");
       BS.cancelScheduling(VL, VL0);
case Instruction::Store: {
         uint64_t Size = DL->getTypeAllocSize(ScalarTy);
         // Check that the sorted pointer operands are consecutive.
         if (Diff && Diff->getAPInt() == (VL.size() - 1) * Size) {
           if (CurrentOrder.empty()) {
             // Original stores are consecutive and does not require reordering.
             ++NumOpsWantToKeepOriginalOrder;
             TreeEntry *TE = newTreeEntry(VL, Bundle /*vectorized*/, S,
                                          UserTreeIdx, ReuseShuffleIndicies);
-            TE->setOperandsInOrder();
+            TE->setLoadStoreOperandsInOrder();
             buildTree_rec(Operands, Depth + 1, {TE, 0});
             LLVM_DEBUG(dbgs() << "SLP: added a vector of stores.\n");
           } else {
             // Need to reorder.
             auto I = NumOpsWantToKeepOrder.try_emplace(CurrentOrder).first;
             ++(I->getSecond());
             TreeEntry *TE =
                 newTreeEntry(VL, Bundle /*vectorized*/, S, UserTreeIdx,
                              ReuseShuffleIndicies, I->getFirst());
-            TE->setOperandsInOrder();
+            TE->setLoadStoreOperandsInOrder();
             buildTree_rec(Operands, Depth + 1, {TE, 0});
             LLVM_DEBUG(dbgs() << "SLP: added a vector of jumbled stores.\n");
           }
           return;
         }
       }
 
       BS.cancelScheduling(VL, VL0);
switch (ShuffleOrOp) {
     }
     case Instruction::ExtractValue: {
       LoadInst *LI = cast<LoadInst>(E->getSingleOperand(0));
       Builder.SetInsertPoint(LI);
       PointerType *PtrTy =
           PointerType::get(VecTy, LI->getPointerAddressSpace());
       Value *Ptr = Builder.CreateBitCast(LI->getOperand(0), PtrTy);
       LoadInst *V = Builder.CreateAlignedLoad(VecTy, Ptr, LI->getAlign());
-      Value *NewV = propagateMetadata(V, E->Scalars);
+      Value *NewV = propagateMetadata(V, E->Scalars, true);
       if (!E->ReorderIndices.empty()) {
         SmallVector<int, 4> Mask;
         inversePermutation(E->ReorderIndices, Mask);
         NewV = Builder.CreateShuffleVector(NewV, UndefValue::get(VecTy), Mask,
                                            "reorder_shuffle");
       }
       if (NeedToShuffleReuses) {
         // TODO: Merge this shuffle with the ReorderShuffleMask.
case Instruction::Load: {
       // The pointer operand uses an in-tree scalar so we add the new BitCast to
       // ExternalUses list to make sure that an extract will be generated in the
       // future.
       Value *PO = LI->getPointerOperand();
       if (getTreeEntry(PO))
         ExternalUses.push_back(ExternalUser(PO, cast<User>(VecPtr), 0));
 
       LI = Builder.CreateAlignedLoad(VecTy, VecPtr, LI->getAlign());
-      Value *V = propagateMetadata(LI, E->Scalars);
+      Value *V = propagateMetadata(LI, E->Scalars, (E->getNumOperands() == 2));
       if (IsReorder) {
         SmallVector<int, 4> Mask;
         inversePermutation(E->ReorderIndices, Mask);
         V = Builder.CreateShuffleVector(V, UndefValue::get(V->getType()),
                                         Mask, "reorder_shuffle");
       }
       if (NeedToShuffleReuses) {
         // TODO: Merge this shuffle with the ReorderShuffleMask.
case Instruction::Store: {
                                                  SI->getAlign());
 
       // The pointer operand uses an in-tree scalar, so add the new BitCast to
       // ExternalUses to make sure that an extract will be generated in the
       // future.
       if (getTreeEntry(ScalarPtr))
         ExternalUses.push_back(ExternalUser(ScalarPtr, cast<User>(VecPtr), 0));
 
-      Value *V = propagateMetadata(ST, E->Scalars);
+      Value *V = propagateMetadata(ST, E->Scalars, (E->getNumOperands() == 3));
       if (NeedToShuffleReuses) {
         V = Builder.CreateShuffleVector(V, UndefValue::get(VecTy),
                                         E->ReuseShuffleIndices, "shuffle");
       }
       E->VectorizedValue = V;
       ++NumVectorInstructions;
       return V;
     }

llvm/test/Transforms/SLPVectorizer/noalias.ll

+; RUN: opt -S < %s -slp-vectorizer -slp-max-reg-size=128 -slp-min-reg-size=128 | FileCheck %s
+
+; SLP vectorization across a @llvm.provenance.noalias and provenance
+
+; Function Attrs: inaccessiblememonly nounwind willreturn
+declare void @llvm.sideeffect() #0
+
+define void @test(float* %p) {
+; CHECK-LABEL: @test(
+; CHECK-NEXT:    [[P1_DECL:%.*]] = tail call i8* @llvm.noalias.decl.p0i8.p0p0f32.i32(float** null, i32 0, metadata !0)
+; CHECK-NEXT:    [[P0:%.*]] = getelementptr float, float* [[P:%.*]], i64 0
+; CHECK-NEXT:    [[P1:%.*]] = getelementptr float, float* [[P]], i64 1
+; CHECK-NEXT:    [[PROVENANCE_P1:%.*]] = tail call float* @llvm.provenance.noalias.p0f32.p0i8.p0p0f32.p0p0f32.i32(float* [[P1]], i8* [[P1_DECL]], float** null, float** undef, i32 0, metadata !0), !noalias !0
+; CHECK-NEXT:    [[P2:%.*]] = getelementptr float, float* [[P]], i64 2
+; CHECK-NEXT:    [[P3:%.*]] = getelementptr float, float* [[P]], i64 3
+; CHECK-NEXT:    call void @llvm.sideeffect()
+; CHECK-NEXT:    [[TMP1:%.*]] = bitcast float* [[P0]] to <4 x float>*
+; CHECK-NEXT:    [[TMP2:%.*]] = load <4 x float>, <4 x float>* [[TMP1]], align 4
+; CHECK-NEXT:    call void @llvm.sideeffect()
+; CHECK-NEXT:    [[TMP3:%.*]] = bitcast float* [[P0]] to <4 x float>*
+; CHECK-NEXT:    store <4 x float> [[TMP2]], <4 x float>* [[TMP3]], align 4
+; CHECK-NEXT:    ret void
+;
+  %p1.decl = tail call i8* @llvm.noalias.decl.p0i8.p0p0f32.i32(float** null, i32 0, metadata !0)
+  %p0 = getelementptr float, float* %p, i64 0
+  %p1 = getelementptr float, float* %p, i64 1
+  %prov.p1 = tail call float* @llvm.provenance.noalias.p0f32.p0i8.p0p0f32.p0p0f32.i32(float* %p1, i8* %p1.decl, float** null, float** undef, i32 0, metadata !0), !noalias !0
+  %p2 = getelementptr float, float* %p, i64 2
+  %p3 = getelementptr float, float* %p, i64 3
+  %l0 = load float, float* %p0, !noalias !0
+  %l1 = load float, float* %p1, ptr_provenance float* %prov.p1, !noalias !0
+  %l2 = load float, float* %p2, !noalias !0
+  call void @llvm.sideeffect()
+  %l3 = load float, float* %p3, !noalias !0
+  store float %l0, float* %p0, !noalias !0
+  call void @llvm.sideeffect()
+  store float %l1, float* %p1, ptr_provenance float* %prov.p1, !noalias !0
+  store float %l2, float* %p2, !noalias !0
+  store float %l3, float* %p3, !noalias !0
+  ret void
+}
+
+; Function Attrs: argmemonly nounwind
+declare i8* @llvm.noalias.decl.p0i8.p0p0f32.i32(float**, i32, metadata) #1
+
+; Function Attrs: nounwind readnone speculatable
+declare float* @llvm.provenance.noalias.p0f32.p0i8.p0p0f32.p0p0f32.i32(float*, i8*, float**, float**, i32, metadata) #2
+
+attributes #0 = { inaccessiblememonly nounwind willreturn }
+attributes #1 = { argmemonly nounwind }
+attributes #2 = { nounwind readnone speculatable }
+
+!0 = !{!1}
+!1 = distinct !{!1, !2, !"test_f: p"}
+!2 = distinct !{!2, !"test_f"}