SLPVectorizer: Move propagateMetadata to VectorUtils

[arsenm]

Summary

This will be re-used by the LoadStoreVectorizer

[mssimpso]

Hi Matt,

There's a similar static function in the loop vectorizer. Do you think it would be beneficial to refactor that one to also use the common interface?

[arsenm]

In D20639#439764, @mssimpso wrote:

Hi Matt,

There's a similar static function in the loop vectorizer. Do you think it would be beneficial to refactor that one to also use the common interface?

I think so. It looks like that one might be buggy since this version seems to be trying to pick the most conservative set of metadata?

[mzolotukhin]

As far as I remember, the version in LoopVectorizer propagates metadata from a single instruction, not from a vector of instructions. However, I think it should be just considered as a special case - i.e. we are still propagating metadata from a vector of instructions, but they all are the same. So, if it doesn't complicate the code much, could you please try refactoring it from there too?

Thanks,
Michael

[arsenm]

Use in loop vectorizer

[arsenm]

ping

[mzolotukhin]

Hi,

Thanks for doing this! Please find some comments inline.

Michael

lib/Analysis/VectorUtils.cpp

452

Maybe make VL ArrayRef<Instruction *> - we always cast its elements to Instruction anyway.

lib/Transforms/Vectorize/LoopVectorize.cpp

481

Why drop const?

485

Ditto.

682

Hmm.. propagateMetadata expects ArrayRef<Value *> VL now instead of Instruction *From, doesn't it? Am I missing something?

[jlebar]

lib/Transforms/Vectorize/LoopVectorize.cpp

682

ArrayRef has a one-element constructor (strangely enough). http://llvm.org/docs/doxygen/html/classllvm_1_1ArrayRef.html#a3b1f44186f9787d7ffacb54b62d6798c

Something does seem to be wrong here, though; the assertion failures I mentioned in http://reviews.llvm.org/D19501#454941 seem to be coming from this patch. Not sure why yet.

[jlebar]

lib/Transforms/Vectorize/LoopVectorize.cpp

690

Oh, I bet I see the problem. There's a difference in behavior between this propagateMetadata and the new one. This one ignores unknown metadata -- leaves it in place on "To". The new one explicitly removes it.

[arsenm]

lib/Transforms/Vectorize/LoopVectorize.cpp

481

I tried to keep the const, but the MDNode::get*s make this non-const.

[jlebar]

lib/Transforms/Vectorize/LoopVectorize.cpp

690

Oh, that's not quite right -- in the event that you pass just one element for "from" to the new propagateMetadata, propagates *everything*. The new propagateMetadata only removes unknown md if there are multiple "from"s.

[jlebar]

This patch seems to fix it for me. https://gist.github.com/7219541341dd9029d0c038ec59246f8b

This is less restrictive than SLPVectorizer's propagateMetadata in that it doesn't touch unknown metadata. But since SLPVectorizer seems to create all its "To" instructions from scratch, that doesn't seem like a material difference.

[arsenm]

In D20639#455104, @jlebar wrote:

This patch seems to fix it for me. https://gist.github.com/7219541341dd9029d0c038ec59246f8b

This is less restrictive than SLPVectorizer's propagateMetadata in that it doesn't touch unknown metadata. But since SLPVectorizer seems to create all its "To" instructions from scratch, that doesn't seem like a material difference.

Do you have a reduced testcase to go with it?

[jlebar]

In D20639#455106, @arsenm wrote:

Do you have a reduced testcase to go with it?

I'll try to come up with one, but I am not very good with bugpoint, so it may take me a bit.

[jlebar]

Many (okay, two) bugs in bugpoint died to bring us this reduced testcase. Turns out it's very close to what I originally tried to write by hand, but subtly different in some way that I don't care to investigate further.

target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

define void @fn(i8* readonly %first.coerce, i8* readnone %last.coerce, i8* nocapture %result) {
for.body.preheader:                           
  br label %for.body

for.body:                                     
  %result.addr.05 = phi i8* [ %incdec.ptr, %for.body ], [ %result, %for.body.preheader ]
  %first.sroa.0.04 = phi i8* [ %incdec.ptr.i.i.i, %for.body ], [ %first.coerce, %for.body.preheader ]
  %0 = load i8, i8* %first.sroa.0.04, align 1, !range !5
  store i8 %0, i8* %result.addr.05, align 1
  %incdec.ptr.i.i.i = getelementptr inbounds i8, i8* %first.sroa.0.04, i64 1
  %incdec.ptr = getelementptr inbounds i8, i8* %result.addr.05, i64 1
  %lnot.i = icmp eq i8* %incdec.ptr.i.i.i, %last.coerce
  br i1 %lnot.i, label %for.end.loopexit, label %for.body

for.end.loopexit:                             
  ret void
}

!5 = !{i8 0, i8 2}

[jlebar]

Things seem to work for me with the patch attached above.

[arsenm]

Merge patch and testcase

[arsenm]

ping

[jlebar]

lgtm. Sorry to keep you waiting -- too many patches.

lib/Analysis/VectorUtils.cpp

459

clang-format?

[arsenm]

r274281

include/llvm/Analysis/VectorUtils.h

 /// will return: {%1: 16, %2: 16, %3: 16, %4: 16, %5: 16, %6: 16, %7: 16}.
 ///
 /// If the optional TargetTransformInfo is provided, this function tries harder
 /// to do less work by only looking at illegal types.
 MapVector<Instruction*, uint64_t>
 computeMinimumValueSizes(ArrayRef<BasicBlock*> Blocks,
                          DemandedBits &DB,
                          const TargetTransformInfo *TTI=nullptr);
-    
+/// Specifically, let Kinds = [MD_tbaa, MD_alias_scope, MD_noalias, MD_fpmath,
+/// MD_nontemporal].  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.
+///
+/// This function always sets a (possibly null) value for each K in Kinds.
+Instruction *propagateMetadata(Instruction *I, ArrayRef<Value *> VL);
+
 } // llvm namespace
 
 #endif

lib/Analysis/VectorUtils.cpp

for (auto MI = ECs.member_begin(I), ME = ECs.member_end(); MI != ME; ++MI) {
         Ty = cast<Instruction>(*MI)->getOperand(0)->getType();
       if (MinBW < Ty->getScalarSizeInBits())
         MinBWs[cast<Instruction>(*MI)] = MinBW;
     }
   }
 
   return MinBWs;
 }
+
+/// \returns \p I after propagating metadata from \p VL.
+Instruction *llvm::propagateMetadata(Instruction *Inst, ArrayRef<Value *> VL) {
+  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 }) {
+    MDNode *MD = I0->getMetadata(Kind);
+
+    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:
+        MD = MDNode::getMostGenericAliasScope(MD, IMD);
+        break;
+      case LLVMContext::MD_noalias:
+        MD = MDNode::intersect(MD, IMD);
+        break;
+      case LLVMContext::MD_fpmath:
+        MD = MDNode::getMostGenericFPMath(MD, IMD);
+        break;
+      case LLVMContext::MD_nontemporal:
+        MD = MDNode::intersect(MD, IMD);
+        break;
+      default:
+        llvm_unreachable("unhandled metadata");
+      }
+    }
+
+    Inst->setMetadata(Kind, MD);
+  }
+
+  return Inst;
+}

lib/Transforms/Vectorize/LoopVectorize.cpp

protected:
   /// vector loop.
   void addNewMetadata(Instruction *To, const Instruction *Orig);
 
   /// Add metadata from one instruction to another.
   ///
   /// This includes both the original MDs from \p From and additional ones (\see
   /// addNewMetadata).  Use this for *newly created* instructions in the vector
   /// loop.
-  void addMetadata(Instruction *To, const Instruction *From);
+  void addMetadata(Instruction *To, Instruction *From);
 
   /// \brief Similar to the previous function but it adds the metadata to a
   /// vector of instructions.
-  void addMetadata(SmallVectorImpl<Value *> &To, const Instruction *From);
+  void addMetadata(ArrayRef<Value *> To, Instruction *From);
 
   /// This is a helper class that holds the vectorizer state. It maps scalar
   /// instructions to vector instructions. When the code is 'unrolled' then
   /// then a single scalar value is mapped to multiple vector parts. The parts
   /// are stored in the VectorPart type.
   struct ValueMap {
     /// C'tor.  UnrollFactor controls the number of vectors ('parts') that
     /// are mapped.
else
       // Just print the module name.
       OS << L->getHeader()->getParent()->getParent()->getModuleIdentifier();
     OS.flush();
   }
   return Result;
 }
 #endif
 
-/// \brief Propagate known metadata from one instruction to another.
-static void propagateMetadata(Instruction *To, const Instruction *From) {
-  SmallVector<std::pair<unsigned, MDNode *>, 4> Metadata;
-  From->getAllMetadataOtherThanDebugLoc(Metadata);
-
-  for (auto M : Metadata) {
-    unsigned Kind = M.first;
-
-    // These are safe to transfer (this is safe for TBAA, even when we
-    // if-convert, because should that metadata have had a control dependency
-    // on the condition, and thus actually aliased with some other
-    // non-speculated memory access when the condition was false, this would be
-    // caught by the runtime overlap checks).
-    if (Kind != LLVMContext::MD_tbaa && Kind != LLVMContext::MD_alias_scope &&
-        Kind != LLVMContext::MD_noalias && Kind != LLVMContext::MD_fpmath &&
-        Kind != LLVMContext::MD_nontemporal)
-      continue;
-
-    To->setMetadata(Kind, M.second);
-  }
-}
-
 void InnerLoopVectorizer::addNewMetadata(Instruction *To,
                                          const Instruction *Orig) {
   // 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,
-                                      const Instruction *From) {
+                                      Instruction *From) {
   propagateMetadata(To, From);
   addNewMetadata(To, From);
 }
 
-void InnerLoopVectorizer::addMetadata(SmallVectorImpl<Value *> &To,
-                                      const Instruction *From) {
-  for (Value *V : To)
+void InnerLoopVectorizer::addMetadata(ArrayRef<Value *> To,
+                                      Instruction *From) {
+  for (Value *V : To) {
     if (Instruction *I = dyn_cast<Instruction>(V))
       addMetadata(I, From);
   }
+}
 
 /// \brief The group of interleaved loads/stores sharing the same stride and
 /// close to each other.
 ///
 /// Each member in this group has an index starting from 0, and the largest
 /// index should be less than interleaved factor, which is equal to the absolute
 /// value of the access's stride.
 ///

lib/Transforms/Vectorize/SLPVectorizer.cpp

if (auto *Intersection = dyn_cast<BinaryOperator>(VL[0])) {
         if (auto *Scalar = dyn_cast<BinaryOperator>(VL[i]))
           Intersection->andIRFlags(Scalar);
       }
       VecOp->copyIRFlags(Intersection);
     }
   }
 }
 
-/// \returns \p I after propagating metadata from \p VL.
-static Instruction *propagateMetadata(Instruction *I, ArrayRef<Value *> VL) {
-  Instruction *I0 = cast<Instruction>(VL[0]);
-  SmallVector<std::pair<unsigned, MDNode *>, 4> Metadata;
-  I0->getAllMetadataOtherThanDebugLoc(Metadata);
-
-  for (unsigned i = 0, n = Metadata.size(); i != n; ++i) {
-    unsigned Kind = Metadata[i].first;
-    MDNode *MD = Metadata[i].second;
-
-    for (int i = 1, e = VL.size(); MD && i != e; i++) {
-      Instruction *I = cast<Instruction>(VL[i]);
-      MDNode *IMD = I->getMetadata(Kind);
-
-      switch (Kind) {
-      default:
-        MD = nullptr; // Remove unknown metadata
-        break;
-      case LLVMContext::MD_tbaa:
-        MD = MDNode::getMostGenericTBAA(MD, IMD);
-        break;
-      case LLVMContext::MD_alias_scope:
-        MD = MDNode::getMostGenericAliasScope(MD, IMD);
-        break;
-      case LLVMContext::MD_noalias:
-        MD = MDNode::intersect(MD, IMD);
-        break;
-      case LLVMContext::MD_fpmath:
-        MD = MDNode::getMostGenericFPMath(MD, IMD);
-        break;
-      case LLVMContext::MD_nontemporal:
-        MD = MDNode::intersect(MD, IMD);
-        break;
-      }
-    }
-    I->setMetadata(Kind, MD);
-  }
-  return I;
-}
-
 /// \returns The type that all of the values in \p VL have or null if there
 /// are different types.
 static Type* getSameType(ArrayRef<Value *> VL) {
   Type *Ty = VL[0]->getType();
   for (int i = 1, e = VL.size(); i < e; i++)
     if (VL[i]->getType() != Ty)
       return nullptr;
 

test/Transforms/LoopVectorize/X86/propagate-metadata.ll

+; RUN: opt -S -mtriple="x86_64-unknown-linux-gnu" -loop-vectorize < %s | FileCheck %s
+
+; Don't crash on unknown metadata
+; CHECK-LABEL: @no_propagate_range_metadata(
+; CHECK: load <16 x i8>
+; CHECK: store <16 x i8>
+define void @no_propagate_range_metadata(i8* readonly %first.coerce, i8* readnone %last.coerce, i8* nocapture %result) {
+for.body.preheader:
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %for.body.preheader
+  %result.addr.05 = phi i8* [ %incdec.ptr, %for.body ], [ %result, %for.body.preheader ]
+  %first.sroa.0.04 = phi i8* [ %incdec.ptr.i.i.i, %for.body ], [ %first.coerce, %for.body.preheader ]
+  %0 = load i8, i8* %first.sroa.0.04, align 1, !range !0
+  store i8 %0, i8* %result.addr.05, align 1
+  %incdec.ptr.i.i.i = getelementptr inbounds i8, i8* %first.sroa.0.04, i64 1
+  %incdec.ptr = getelementptr inbounds i8, i8* %result.addr.05, i64 1
+  %lnot.i = icmp eq i8* %incdec.ptr.i.i.i, %last.coerce
+  br i1 %lnot.i, label %for.end.loopexit, label %for.body
+
+for.end.loopexit:                                 ; preds = %for.body
+  ret void
+}
+
+!0 = !{i8 0, i8 2}