[Metadata] Add TBAA struct metadata to `AAMDNode`

[anton-afanasyev]

Summary

Make AAMDNodes' getAAMetadata() and setAAMetadata() to take !tbaa.struct
into account like for !tbaa. This impacts llvm.org/pr42022.
This is a temprorary fix needed to keep !tbaa.struct tag by SROA pass. New field TBAAStruct should be deleted when !tbaa tag replaces !tbaa.struct. Merging two !tbaa.struct's to one is conservatively considered to be nullptr (giving MayAlias) -- this could be enhanced, but relying on the said replacement.

[hfinkel]

llvm/lib/Analysis/TypeBasedAliasAnalysis.cpp

527

Does MDNode::getMostGenericTBAA actually support struct.tbaa metadata? I didn't think that it did.

[anton-afanasyev]

llvm/lib/Analysis/TypeBasedAliasAnalysis.cpp

527

No, it really didn't. Fixing it.

[anton-afanasyev]

Hi @hfinkel, I've investigated the current state of TBAA support in LLVM. AFAIU (see D40975, but it is still uncommited) the new format of tbaa tag replaces tbaa.struct tag. Does it mean tbaa.struct tag will be deprecated soon?

[anton-afanasyev]

Updated getAAMetadata() with Merge=true

[anton-afanasyev]

llvm/lib/Analysis/TypeBasedAliasAnalysis.cpp

527

Updated. I conservatively suppose that merging two !tbaa.struct's turns to MayAlias.

[anton-afanasyev]

Fixed

[anton-afanasyev]

In D70924#1780145, @anton-afanasyev wrote:

Hi @hfinkel, I've investigated the current state of TBAA support in LLVM. AFAIU (see D40975, but it is still uncommited) the new format of tbaa tag replaces tbaa.struct tag. Does it mean tbaa.struct tag will be deprecated soon?

This replacing !tbaa.struct->!tbaa is described at the topic http://lists.llvm.org/pipermail/llvm-dev/2017-October/118284.html started by @kosarev, and I see it has already been supported and almost commited (but not announced). So my patch looks like temprorary bug fixing until this transfer is finished.

[anton-afanasyev]

Fix

[hfinkel]

In D70924#1780145, @anton-afanasyev wrote:

Hi @hfinkel, I've investigated the current state of TBAA support in LLVM. AFAIU (see D40975, but it is still uncommited) the new format of tbaa tag replaces tbaa.struct tag. Does it mean tbaa.struct tag will be deprecated soon?

It might, but it depends on the progress on the new TBAA format. This is not a large change, and I think that we can proceed with this regardless.

Can you please explain what will end up using this information? That should be present in the description.

[anton-afanasyev]

In D70924#1782238, @hfinkel wrote:

In D70924#1780145, @anton-afanasyev wrote:

Hi @hfinkel, I've investigated the current state of TBAA support in LLVM. AFAIU (see D40975, but it is still uncommited) the new format of tbaa tag replaces tbaa.struct tag. Does it mean tbaa.struct tag will be deprecated soon?

It might, but it depends on the progress on the new TBAA format. This is not a large change, and I think that we can proceed with this regardless.

Can you please explain what will end up using this information? That should be present in the description.

Ok, updated summary.

[anton-afanasyev]

Gently ping. Is it ok now?

[anton-afanasyev]

Gently ping again.

[anton-afanasyev]

Ping!

[RKSimon]

llvm/include/llvm/IR/Metadata.h

647

I always get worried when constructors with default args get rearranged like this. Maybe change to this:

explicit AAMDNodes() = default;
explicit AAMDNodes(MDNode *T, MDNode *TS, MDNode *S, MDNode *N)
    : TBAA(T), TBAAStruct(TS), Scope(S), NoAlias(N) {}

MDNode *TBAA = nullptr; // etc.

[anton-afanasyev]

Update AAMDNodes constructors

[anton-afanasyev]

llvm/include/llvm/IR/Metadata.h

647

Ok, done.

[RKSimon]

@hfinkel Any more comments?

[hfinkel]

In D70924#1804715, @RKSimon wrote:

@hfinkel Any more comments?

Nope. LGTM.

llvm/include/llvm/IR/Metadata.h

public:
   static bool classof(const Metadata *MD) {
     return MD->getMetadataID() == MDStringKind;
   }
 };
 
 /// A collection of metadata nodes that might be associated with a
 /// memory access used by the alias-analysis infrastructure.
 struct AAMDNodes {
-  explicit AAMDNodes(MDNode *T = nullptr, MDNode *S = nullptr,
-                     MDNode *N = nullptr)
-      : TBAA(T), Scope(S), NoAlias(N) {}
+  explicit AAMDNodes(MDNode *T = nullptr, MDNode *TS = nullptr,
+                     MDNode *S = nullptr, MDNode *N = nullptr)
+      : TBAA(T), TBAAStruct(TS), Scope(S), NoAlias(N) {}
 
   bool operator==(const AAMDNodes &A) const {
-    return TBAA == A.TBAA && Scope == A.Scope && NoAlias == A.NoAlias;
+    return TBAA == A.TBAA && TBAAStruct == A.TBAAStruct && Scope == A.Scope &&
+           NoAlias == A.NoAlias;
   }
 
   bool operator!=(const AAMDNodes &A) const { return !(*this == A); }
 
-  explicit operator bool() const { return TBAA || Scope || NoAlias; }
+  explicit operator bool() const {
+    return TBAA || TBAAStruct || Scope || NoAlias;
+  }
 
   /// The tag for type-based alias analysis.
   MDNode *TBAA;
 
+  /// The tag for type-based alias analysis (tbaa struct).
+  MDNode *TBAAStruct;
+
   /// The tag for alias scope specification (used with noalias).
   MDNode *Scope;
 
   /// The tag specifying the noalias scope.
   MDNode *NoAlias;
 
   /// Given two sets of AAMDNodes that apply to the same pointer,
   /// give the best AAMDNodes that are compatible with both (i.e. a set of
   /// nodes whose allowable aliasing conclusions are a subset of those
   /// allowable by both of the inputs). However, for efficiency
   /// reasons, do not create any new MDNodes.
   AAMDNodes intersect(const AAMDNodes &Other) {
     AAMDNodes Result;
     Result.TBAA = Other.TBAA == TBAA ? TBAA : nullptr;
+    Result.TBAAStruct = Other.TBAAStruct == TBAAStruct ? TBAAStruct : nullptr;
     Result.Scope = Other.Scope == Scope ? Scope : nullptr;
     Result.NoAlias = Other.NoAlias == NoAlias ? NoAlias : nullptr;
     return Result;
   }
 };
 
 // Specialize DenseMapInfo for AAMDNodes.
 template<>

llvm/lib/Analysis/TypeBasedAliasAnalysis.cpp

while (IA >= 0 && IB >= 0) {
     --IA;
     --IB;
   }
 
   return Ret;
 }
 
 void Instruction::getAAMetadata(AAMDNodes &N, bool Merge) const {
-  if (Merge)
+  if (Merge) {
     N.TBAA =
         MDNode::getMostGenericTBAA(N.TBAA, getMetadata(LLVMContext::MD_tbaa));
-  else
-    N.TBAA = getMetadata(LLVMContext::MD_tbaa);
-
-  if (Merge)
+    N.TBAAStruct = nullptr;
     N.Scope = MDNode::getMostGenericAliasScope(
         N.Scope, getMetadata(LLVMContext::MD_alias_scope));
-  else
-    N.Scope = getMetadata(LLVMContext::MD_alias_scope);
-
-  if (Merge)
     N.NoAlias =
         MDNode::intersect(N.NoAlias, getMetadata(LLVMContext::MD_noalias));
-  else
+  } else {
+    N.TBAA = getMetadata(LLVMContext::MD_tbaa);
+    N.TBAAStruct = getMetadata(LLVMContext::MD_tbaa_struct);
+    N.Scope = getMetadata(LLVMContext::MD_alias_scope);
     N.NoAlias = getMetadata(LLVMContext::MD_noalias);
   }
+}
 
 static const MDNode *createAccessTag(const MDNode *AccessType) {
   // If there is no access type or the access type is the root node, then
   // we don't have any useful access tag to return.
   if (!AccessType || AccessType->getNumOperands() < 2)
     return nullptr;
 
   Type *Int64 = IntegerType::get(AccessType->getContext(), 64);

llvm/lib/IR/Metadata.cpp

if (!Info.empty())
     return;
 
   getContext().pImpl->InstructionMetadata.erase(this);
   setHasMetadataHashEntry(false);
 }
 
 void Instruction::setAAMetadata(const AAMDNodes &N) {
   setMetadata(LLVMContext::MD_tbaa, N.TBAA);
+  setMetadata(LLVMContext::MD_tbaa_struct, N.TBAAStruct);
   setMetadata(LLVMContext::MD_alias_scope, N.Scope);
   setMetadata(LLVMContext::MD_noalias, N.NoAlias);
 }
 
 MDNode *Instruction::getMetadataImpl(unsigned KindID) const {
   // Handle 'dbg' as a special case since it is not stored in the hash table.
   if (KindID == LLVMContext::MD_dbg)
     return DbgLoc.getAsMDNode();

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

isShuffle(ArrayRef<Value *> VL) {
   // If we're not crossing lanes in different vectors, consider it as blending.
   if (CommonShuffleMode == Select && Vec2)
     return TargetTransformInfo::SK_Select;
   // If Vec2 was never used, we have a permutation of a single vector, otherwise
   // we have permutation of 2 vectors.
   return Vec2 ? TargetTransformInfo::SK_PermuteTwoSrc
               : TargetTransformInfo::SK_PermuteSingleSrc;
 }
+static bool findBuildAggregate(Value *LastInsertInst, TargetTransformInfo *TTI,
+                               SmallVectorImpl<Value *> &BuildVectorOpds,
+                               int &UserCost);
 
 namespace {
 
 /// Main data required for vectorization of instructions.
 struct InstructionsState {
   /// The very first instruction in the list with the main opcode.
   Value *OpValue = nullptr;
 
void BoUpSLP::buildTree_rec(ArrayRef<Value *> VL, unsigned Depth,
   InstructionsState S = getSameOpcode(VL);
   if (Depth == RecursionMaxDepth) {
     LLVM_DEBUG(dbgs() << "SLP: Gathering due to max recursion depth.\n");
     newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx);
     return;
   }
 
   // Don't handle vectors.
-  if (S.OpValue->getType()->isVectorTy()) {
-    LLVM_DEBUG(dbgs() << "SLP: Gathering due to vector type.\n");
-    newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx);
-    return;
-  }
-
-  if (StoreInst *SI = dyn_cast<StoreInst>(S.OpValue))
-    if (SI->getValueOperand()->getType()->isVectorTy()) {
-      LLVM_DEBUG(dbgs() << "SLP: Gathering due to store vector type.\n");
-      newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx);
-      return;
-    }
+  // if (S.OpValue->getType()->isVectorTy()) {
+  //   LLVM_DEBUG(dbgs() << "SLP: Gathering due to vector type.\n");
+  //   newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx);
+  //   return;
+  // }
+
+  //  if (StoreInst *SI = dyn_cast<StoreInst>(S.OpValue))
+  //    if (SI->getValueOperand()->getType()->isVectorTy()) {
+  //      LLVM_DEBUG(dbgs() << "SLP: Gathering due to store vector type.\n");
+  //      newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx);
+  //      return;
+  //    }
 
   // If all of the operands are identical or constant we have a simple solution.
   if (allConstant(VL) || isSplat(VL) || !allSameBlock(VL) || !S.getOpcode()) {
     LLVM_DEBUG(dbgs() << "SLP: Gathering due to C,S,B,O. \n");
     newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx);
     return;
   }
 
case Instruction::ExtractElement: {
         return;
       }
       LLVM_DEBUG(dbgs() << "SLP: Gather extract sequence.\n");
       newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx,
                    ReuseShuffleIndicies);
       BS.cancelScheduling(VL, VL0);
       return;
     }
+    case Instruction::InsertElement: {
+      int UserCost = 0;
+      ValueList Inserts;
+      ValueList Operands;
+      for (Value *V : VL) {
+        if (!findBuildAggregate(V, TTI, Inserts, UserCost)) {
+          BS.cancelScheduling(VL, VL0);
+          newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx,
+                       ReuseShuffleIndicies);
+          LLVM_DEBUG(dbgs() << "SLP: Gathering insertelement's.\n");
+          return;
+        }
+      }
+
+      TreeEntry *TE = newTreeEntry(VL/*Inserts*/, Bundle /*vectorized*/, S,
+                                   UserTreeIdx, ReuseShuffleIndicies);
+
+      TE->setOperandsInOrder();
+      //      for (Value *V : Inserts)
+      //        Operands.push_back(cast<Instruction>(V)->getOperand(1));
+      buildTree_rec(Inserts, Depth + 1, {TE, 0});
+      return;
+      
+    }
+
+    //   auto POIter = PointerOps.begin();
+    //   auto OIter = Operands.begin();
+
+    //     auto *SI = cast<StoreInst>(V);
+    //     if (!SI->isSimple()) {
+    //     *POIter = SI->getPointerOperand();
+    //     *OIter = SI->getValueOperand();
+    //     ++POIter;
+    //     ++OIter;
+    //   }
+
+    //   {
+    //     newTreeEntry(VL, Bundle /*vectorized*/, S, UserTreeIdx,
+    //                  ReuseShuffleIndicies,
+    //                  StoredCurrentOrderAndNum->getFirst());
+    //     // This is a special case, as it does not gather, but at the same time
+    //     // we are not extending buildTree_rec() towards the operands.
+    //     ValueList Op0;
+    //     Op0.assign(VL.size(), VL0->getOperand(0));
+    //     VectorizableTree.back()->setOperand(0, Op0);
+    //     return;
+    //   }
+    //   LLVM_DEBUG(dbgs() << "SLP: Gather extract sequence.\n");
+    //   newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx,
+    //                ReuseShuffleIndicies);
+    //   BS.cancelScheduling(VL, VL0);
+    //   return;
+
     case Instruction::Load: {
       // Check that a vectorized load would load the same memory as a scalar
       // load. For example, we don't want to vectorize loads that are smaller
       // than 8-bit. Even though we have a packed struct {<i2, i2, i2, i2>} LLVM
       // treats loading/storing it as an i8 struct. If we vectorize loads/stores
       // from such a struct, we read/write packed bits disagreeing with the
       // unvectorized version.
       Type *ScalarTy = VL0->getType();
void SLPVectorizerPass::collectSeedInstructions(BasicBlock *BB) {
   // Stores and GEPs according to the underlying objects of their pointer
   // operands.
   for (Instruction &I : *BB) {
     // Ignore store instructions that are volatile or have a pointer operand
     // that doesn't point to a scalar type.
     if (auto *SI = dyn_cast<StoreInst>(&I)) {
       if (!SI->isSimple())
         continue;
-      if (!isValidElementType(SI->getValueOperand()->getType()))
-        continue;
+      if (isValidElementType(SI->getValueOperand()->getType()) ||
+          isa<VectorType>(SI->getValueOperand()->getType()))
         Stores[GetUnderlyingObject(SI->getPointerOperand(), *DL)].push_back(SI);
+      continue;
     }
 
     // Ignore getelementptr instructions that have more than one index, a
     // constant index, or a pointer operand that doesn't point to a scalar
     // type.
     else if (auto *GEP = dyn_cast<GetElementPtrInst>(&I)) {
       auto Idx = GEP->idx_begin()->get();
       if (GEP->getNumIndices() > 1 || isa<Constant>(Idx))
if (auto *IE = dyn_cast<InsertElementInst>(LastInsertInst)) {
       }
     } else {
       auto *IV = cast<InsertValueInst>(LastInsertInst);
       InsertedOperand = IV->getInsertedValueOperand();
       LastInsertInst = IV->getAggregateOperand();
     }
     if (isa<InsertElementInst>(InsertedOperand) ||
         isa<InsertValueInst>(InsertedOperand)) {
-      int TmpUserCost;
-      SmallVector<Value *, 8> TmpBuildVectorOpds;
-      if (!findBuildAggregate(InsertedOperand, TTI, TmpBuildVectorOpds,
-                              TmpUserCost))
-        return false;
-      BuildVectorOpds.append(TmpBuildVectorOpds.rbegin(),
-                             TmpBuildVectorOpds.rend());
-      UserCost += TmpUserCost;
+      if (!findBuildAggregate(InsertedOperand, TTI, BuildVectorOpds, UserCost))
+        return false;
     } else {
       BuildVectorOpds.push_back(InsertedOperand);
     }
     if (isa<UndefValue>(LastInsertInst))
       break;
     if ((!isa<InsertValueInst>(LastInsertInst) &&
          !isa<InsertElementInst>(LastInsertInst)) ||
         !LastInsertInst->hasOneUse())
       return false;
   } while (true);
-  std::reverse(BuildVectorOpds.begin(), BuildVectorOpds.end());
   return true;
 }
 
 static bool PhiTypeSorterFunc(Value *V, Value *V2) {
   return V->getType() < V2->getType();
 }
 
 /// Try and get a reduction value from a phi node.
bool SLPVectorizerPass::vectorizeInsertValueInst(InsertValueInst *IVI,
   int UserCost = 0;
   const DataLayout &DL = BB->getModule()->getDataLayout();
   if (!R.canMapToVector(IVI->getType(), DL))
     return false;
 
   SmallVector<Value *, 16> BuildVectorOpds;
   if (!findBuildAggregate(IVI, TTI, BuildVectorOpds, UserCost))
     return false;
+  std::reverse(BuildVectorOpds.begin(), BuildVectorOpds.end());
 
   LLVM_DEBUG(dbgs() << "SLP: array mappable to vector: " << *IVI << "\n");
   // Aggregate value is unlikely to be processed in vector register, we need to
   // extract scalars into scalar registers, so NeedExtraction is set true.
   return tryToVectorizeList(BuildVectorOpds, R, UserCost);
 }
 
 bool SLPVectorizerPass::vectorizeInsertElementInst(InsertElementInst *IEI,
                                                    BasicBlock *BB, BoUpSLP &R) {
-  int UserCost;
+  int UserCost = 0;
   SmallVector<Value *, 16> BuildVectorOpds;
   if (!findBuildAggregate(IEI, TTI, BuildVectorOpds, UserCost) ||
       (llvm::all_of(BuildVectorOpds,
                     [](Value *V) { return isa<ExtractElementInst>(V); }) &&
        isShuffle(BuildVectorOpds)))
     return false;
+  std::reverse(BuildVectorOpds.begin(), BuildVectorOpds.end());
 
   // Vectorize starting with the build vector operands ignoring the BuildVector
   // instructions for the purpose of scheduling and user extraction.
   return tryToVectorizeList(BuildVectorOpds, R, UserCost);
 }
 
 bool SLPVectorizerPass::vectorizeCmpInst(CmpInst *CI, BasicBlock *BB,
                                          BoUpSLP &R) {

llvm/test/Transforms/SROA/tbaa-struct.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -sroa %s | FileCheck %s
 
 ; SROA should keep `!tbaa.struct` metadata
 
 %vector = type { float, float }
 declare void @llvm.memcpy.p0i8.p0i8.i64(i8* writeonly, i8* readonly, i64, i1 immarg)
 declare <2 x float> @foo(%vector* %0)
 
 define void @bar(%vector* %y2) {
 ; CHECK-LABEL: @bar(
 ; CHECK-NEXT:    [[X14:%.*]] = call <2 x float> @foo(%vector* [[Y2:%.*]])
 ; CHECK-NEXT:    [[X7_SROA_0_0_X18_SROA_CAST:%.*]] = bitcast %vector* [[Y2]] to <2 x float>*
-; CHECK-NEXT:    store <2 x float> [[X14]], <2 x float>* [[X7_SROA_0_0_X18_SROA_CAST]], align 4
+; CHECK-NEXT:    store <2 x float> [[X14]], <2 x float>* [[X7_SROA_0_0_X18_SROA_CAST]], align 4, !tbaa.struct !0
 ; CHECK-NEXT:    ret void
 ;
   %x7 = alloca %vector
   %x14 = call <2 x float> @foo(%vector* %y2)
   %x15 = bitcast %vector* %x7 to <2 x float>*
   store <2 x float> %x14, <2 x float>* %x15
   %x19 = bitcast %vector* %x7 to i8*
   %x18 = bitcast %vector* %y2 to i8*