[AliasSetTracker] Don't drop AA MD so eagerly

[loladiro]

Summary

When we have patterns like
loop:

%la = load %ptr, !tbaa
%lba = load %ptr, !tbaa !noalias

AliasSetTracker would previously think that the two types of annotation for
the pointer conflict, dropping both for the purpose of determining alias sets.
That is clearly way too conservative, as the tbaa is still valid whether or
not one of the memory accesses has additional AA metadata. We could go
one step further and attempt to properly merge the noalias metadata,
but it's not clear that that would be worth it since that may introduce
additional MD nodes, which may be undesirable since this is merely an
Analysis. For now, just take care of the simple case above, and keep
dropping conflicting noalias and alias.scope metadata, but keep tbaa
if it matches.

[loladiro]

Bump

[hfinkel]

include/llvm/Analysis/AliasSetTracker.h

77

I'd prefer that we handle this in a way that the symmetric between the TBAA and NoAlias metadata. If TBAA conflict, set TBAA to nullptr. If NoAlias conflict, set NoAlias to nullptr, same with Scope. Please put this part of the logic into a member function on AAMDNodes (so that we can keep it in sync with anything else we add there). If there's nothing left (i.e. AAMDNodes's operator bool returns false), then set AAInfo to getTombstoneKey().

[loladiro]

Factor out intersection code into a method of AAMDNodes

[hfinkel]

LGTM

include/llvm/Analysis/AliasSetTracker.h

bool updateSizeAndAAInfo(uint64_t NewSize, const AAMDNodes &NewAAInfo) {
       if (NewSize > Size) {
         Size = NewSize;
         SizeChanged = true;
       }
 
       if (AAInfo == DenseMapInfo<AAMDNodes>::getEmptyKey())
         // We don't have a AAInfo yet. Set it to NewAAInfo.
         AAInfo = NewAAInfo;
-      else if (AAInfo != NewAAInfo)
+      else {
+        AAMDNodes Intersection(AAInfo.intersect(NewAAInfo));
+        if (!Intersection) {
           // NewAAInfo conflicts with AAInfo.
           AAInfo = DenseMapInfo<AAMDNodes>::getTombstoneKey();
-
+          return SizeChanged;
+        }
+        AAInfo = Intersection;
+      }
       return SizeChanged;
     }
 
     uint64_t getSize() const { return Size; }
 
     /// Return the AAInfo, or null if there is no information or conflicting
     /// information.
     AAMDNodes getAAInfo() const {

include/llvm/IR/Metadata.h

struct AAMDNodes {
   /// \brief The tag for type-based alias analysis.
   MDNode *TBAA;
 
   /// \brief The tag for alias scope specification (used with noalias).
   MDNode *Scope;
 
   /// \brief The tag specifying the noalias scope.
   MDNode *NoAlias;
+
+  /// \brief 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.Scope = Other.Scope == Scope ? Scope : nullptr;
+    Result.NoAlias = Other.NoAlias == NoAlias ? NoAlias : nullptr;
+    return Result;
+  }
 };
 
 // Specialize DenseMapInfo for AAMDNodes.
 template<>
 struct DenseMapInfo<AAMDNodes> {
   static inline AAMDNodes getEmptyKey() {
     return AAMDNodes(DenseMapInfo<MDNode *>::getEmptyKey(),
                      nullptr, nullptr);

test/Transforms/LICM/dropped-tbaa.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -scoped-noalias -tbaa -licm -S | FileCheck %s
+
+; This test case case is generated from the following C code with -fstrict-aliasing,
+; and after passing through -inline -mem2reg -loop-rotate -instcombine
+; void add(double *restrict data, int *restrict addend) {
+;    *data += *addend;
+; }
+;
+; void foo(double *data, int *addend) {
+;    for (int i = 0; i < 1000; ++i) {
+;        *data += *addend;
+;        add(data, addend);
+;    }
+; }
+; We want to make sure the load of addend gets hoisted, independent of the second load
+; load having different noalias metadata.
+
+define void @foo(double* %data, i32* %addend) #0 {
+; CHECK:       for.body.lr.ph:
+; CHECK-NEXT:    [[TMP1:%.*]] = load i32, i32* [[ADDEND:%.*]], align 4, !tbaa !1
+; CHECK-NEXT:    [[CONV:%.*]] = sitofp i32 [[TMP1]] to double
+; CHECK-NEXT:    [[TMP2:%.*]] = load i32, i32* [[ADDEND]], align 4, !tbaa !1, !alias.scope !5, !noalias !8
+; CHECK-NEXT:    [[CONV_I:%.*]] = sitofp i32 [[TMP2]] to double
+entry:
+  %i = alloca i32, align 4
+  %0 = bitcast i32* %i to i8*
+  call void @llvm.lifetime.start.p0i8(i64 4, i8* %0) #2
+  store i32 0, i32* %i, align 4, !tbaa !1
+  br i1 true, label %for.body.lr.ph, label %for.cond.cleanup
+
+for.body.lr.ph:                                   ; preds = %entry
+  br label %for.body
+
+for.cond.for.cond.cleanup_crit_edge:              ; preds = %for.inc
+  br label %for.cond.cleanup
+
+for.cond.cleanup:                                 ; preds = %for.cond.for.cond.cleanup_crit_edge, %entry
+  %1 = bitcast i32* %i to i8*
+  call void @llvm.lifetime.end.p0i8(i64 4, i8* %1) #2
+  br label %for.end
+
+for.body:                                         ; preds = %for.body.lr.ph, %for.inc
+  %2 = load i32, i32* %addend, align 4, !tbaa !1
+  %conv = sitofp i32 %2 to double
+  %3 = load i32, i32* %i, align 4, !tbaa !1
+  %idxprom = sext i32 %3 to i64
+  %arrayidx = getelementptr inbounds double, double* %data, i64 %idxprom
+  %4 = load double, double* %arrayidx, align 8, !tbaa !5
+  %add = fadd double %4, %conv
+  store double %add, double* %arrayidx, align 8, !tbaa !5
+  %idxprom1 = sext i32 %3 to i64
+  %arrayidx2 = getelementptr inbounds double, double* %data, i64 %idxprom1
+  %5 = load i32, i32* %addend, align 4, !tbaa !1, !alias.scope !7, !noalias !10
+  %conv.i = sitofp i32 %5 to double
+  %6 = load double, double* %arrayidx2, align 8, !tbaa !5, !alias.scope !10, !noalias !7
+  %add.i = fadd double %6, %conv.i
+  store double %add.i, double* %arrayidx2, align 8, !tbaa !5, !alias.scope !10, !noalias !7
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %7 = load i32, i32* %i, align 4, !tbaa !1
+  %inc = add nsw i32 %7, 1
+  store i32 %inc, i32* %i, align 4, !tbaa !1
+  %cmp = icmp slt i32 %inc, 1000
+  br i1 %cmp, label %for.body, label %for.cond.for.cond.cleanup_crit_edge
+
+for.end:                                          ; preds = %for.cond.cleanup
+  ret void
+}
+
+declare void @llvm.lifetime.start.p0i8(i64, i8* nocapture) #0
+declare void @llvm.lifetime.end.p0i8(i64, i8* nocapture) #0
+
+attributes #0 = { argmemonly nounwind }
+
+!llvm.ident = !{!0}
+
+!0 = !{!"clang version 5.0.0  (llvm/trunk 299971)"}
+!1 = !{!2, !2, i64 0}
+!2 = !{!"int", !3, i64 0}
+!3 = !{!"omnipotent char", !4, i64 0}
+!4 = !{!"Simple C/C++ TBAA"}
+!5 = !{!6, !6, i64 0}
+!6 = !{!"double", !3, i64 0}
+!7 = !{!8}
+!8 = distinct !{!8, !9, !"add: %addend"}
+!9 = distinct !{!9, !"add"}
+!10 = !{!11}
+!11 = distinct !{!11, !9, !"add: %data"}