[PATCH 13/27] [noalias] [BasicAA] look through noalias intrisics

[jeroen.dobbelaere]

Summary

This is part of the series started by D68484.

BasicAA is allowed to look through noalias intrinsics.

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

[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/IR/Metadata.h

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() = default;
-  explicit AAMDNodes(MDNode *T, MDNode *TS, MDNode *S, MDNode *N)
-      : TBAA(T), TBAAStruct(TS), Scope(S), NoAlias(N) {}
+  explicit AAMDNodes(MDNode *T, MDNode *TS, MDNode *S, MDNode *N, Value *NP)
+      : TBAA(T), TBAAStruct(TS), Scope(S), NoAlias(N), NoAliasProvenance(NP) {}
 
   bool operator==(const AAMDNodes &A) const {
     return TBAA == A.TBAA && TBAAStruct == A.TBAAStruct && Scope == A.Scope &&
-           NoAlias == A.NoAlias;
+           NoAlias == A.NoAlias && NoAliasProvenance == A.NoAliasProvenance;
   }
 
   bool operator!=(const AAMDNodes &A) const { return !(*this == A); }
 
   explicit operator bool() const {
-    return TBAA || TBAAStruct || Scope || NoAlias;
+    return TBAA || TBAAStruct || Scope || NoAlias || NoAliasProvenance;
+  }
+
+  void clearNoAliasInfo() {
+    Scope = nullptr;
+    NoAlias = nullptr;
+    NoAliasProvenance = nullptr;
   }
 
   /// The tag for type-based alias analysis.
   MDNode *TBAA = nullptr;
 
   /// The tag for type-based alias analysis (tbaa struct).
   MDNode *TBAAStruct = nullptr;
 
   /// The tag for alias scope specification (used with noalias).
   MDNode *Scope = nullptr;
 
   /// The tag specifying the noalias scope.
   MDNode *NoAlias = nullptr;
 
+  /// The NoAlias Provenance pointer path
+  Value *NoAliasProvenance = nullptr;
+
   /// 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;
+    Result.NoAliasProvenance = Other.NoAliasProvenance == NoAliasProvenance
+                                   ? NoAliasProvenance
+                                   : nullptr;
     return Result;
   }
 };
 
 // Specialize DenseMapInfo for AAMDNodes.
 template<>
 struct DenseMapInfo<AAMDNodes> {
   static inline AAMDNodes getEmptyKey() {
-    return AAMDNodes(DenseMapInfo<MDNode *>::getEmptyKey(),
-                     nullptr, nullptr, nullptr);
+    return AAMDNodes(DenseMapInfo<MDNode *>::getEmptyKey(), nullptr, nullptr,
+                     nullptr, nullptr);
   }
 
   static inline AAMDNodes getTombstoneKey() {
-    return AAMDNodes(DenseMapInfo<MDNode *>::getTombstoneKey(),
+    return AAMDNodes(DenseMapInfo<MDNode *>::getTombstoneKey(), nullptr,
                      nullptr, nullptr, nullptr);
   }
 
   static unsigned getHashValue(const AAMDNodes &Val) {
     return DenseMapInfo<MDNode *>::getHashValue(Val.TBAA) ^
            DenseMapInfo<MDNode *>::getHashValue(Val.TBAAStruct) ^
            DenseMapInfo<MDNode *>::getHashValue(Val.Scope) ^
-           DenseMapInfo<MDNode *>::getHashValue(Val.NoAlias);
+           DenseMapInfo<MDNode *>::getHashValue(Val.NoAlias) ^
+           DenseMapInfo<Value *>::getHashValue(Val.NoAliasProvenance);
   }
 
   static bool isEqual(const AAMDNodes &LHS, const AAMDNodes &RHS) {
     return LHS == RHS;
   }
 };
 
 /// Tracking metadata reference owned by Metadata.

llvm/include/llvm/IR/Value.h

#include "llvm/IR/Value.def"
   /// value, it returns 'this'. This function should be used only in
   /// Alias analysis.
   const Value *stripPointerCastsAndInvariantGroups() const;
   Value *stripPointerCastsAndInvariantGroups() {
     return const_cast<Value *>(static_cast<const Value *>(this)
                                    ->stripPointerCastsAndInvariantGroups());
   }
 
+  /// Strip off pointer casts, all-zero GEPs, aliases, invariant group
+  /// info and noalias intrinsics.
+  ///
+  /// Returns the original uncasted value.  If this is called on a non-pointer
+  /// value, it returns 'this'.
+  const Value *stripPointerCastsAndInvariantGroupsAndNoAliasIntr() const;
+  Value *stripPointerCastsAndInvariantGroupsAndNoAliasIntr() {
+    return const_cast<Value *>(
+        static_cast<const Value *>(this)
+            ->stripPointerCastsAndInvariantGroupsAndNoAliasIntr());
+  }
+
   /// Strip off pointer casts and all-constant inbounds GEPs.
   ///
   /// Returns the original pointer value.  If this is called on a non-pointer
   /// value, it returns 'this'.
   const Value *stripInBoundsConstantOffsets() const;
   Value *stripInBoundsConstantOffsets() {
     return const_cast<Value *>(
               static_cast<const Value *>(this)->stripInBoundsConstantOffsets());

llvm/lib/Analysis/BasicAliasAnalysis.cpp

 
 /// Provides a bunch of ad-hoc rules to disambiguate in common cases, such as
 /// array references.
 AliasResult BasicAAResult::aliasCheck(const Value *V1, LocationSize V1Size,
                                       AAMDNodes V1AAInfo, const Value *V2,
                                       LocationSize V2Size, AAMDNodes V2AAInfo,
                                       AAQueryInfo &AAQI, const Value *O1,
                                       const Value *O2) {
+  auto hasValidNoAliasProvenance = [](AAMDNodes &AA) {
+    return AA.NoAliasProvenance && !isa<UndefValue>(AA.NoAliasProvenance);
+  };
+
   // If either of the memory references is empty, it doesn't matter what the
   // pointer values are.
   if (V1Size.isZero() || V2Size.isZero())
     return NoAlias;
 
   // Strip off any casts if they exist.
+  if (hasValidNoAliasProvenance(V1AAInfo) ||
+      hasValidNoAliasProvenance(V2AAInfo)) {
     V1 = V1->stripPointerCastsAndInvariantGroups();
     V2 = V2->stripPointerCastsAndInvariantGroups();
+  } else {
+    // No noalias info - look through noalias intrinsics in a safe way
+    V1 = V1->stripPointerCastsAndInvariantGroupsAndNoAliasIntr();
+    V2 = V2->stripPointerCastsAndInvariantGroupsAndNoAliasIntr();
+    V1AAInfo.clearNoAliasInfo();
+    V2AAInfo.clearNoAliasInfo();
+  }
 
   // If V1 or V2 is undef, the result is NoAlias because we can always pick a
   // value for undef that aliases nothing in the program.
   if (isa<UndefValue>(V1) || isa<UndefValue>(V2))
     return NoAlias;
 
   // Are we checking for alias of the same value?
   // Because we look 'through' phi nodes, we could look at "Value" pointers from

llvm/lib/CodeGen/MachineOperand.cpp

void MachineMemOperand::print(raw_ostream &OS, ModuleSlotTracker &MST,
   if (AAInfo.Scope) {
     OS << ", !alias.scope ";
     AAInfo.Scope->printAsOperand(OS, MST);
   }
   if (AAInfo.NoAlias) {
     OS << ", !noalias ";
     AAInfo.NoAlias->printAsOperand(OS, MST);
   }
+  if (AAInfo.NoAliasProvenance) {
+    OS << ", ptr_provenance ";
+    AAInfo.NoAliasProvenance->printAsOperand(OS, true, MST);
+  }
   if (getRanges()) {
     OS << ", !range ";
     getRanges()->printAsOperand(OS, MST);
   }
   // FIXME: Implement addrspace printing/parsing in MIR.
   // For now, print this even though parsing it is not available in MIR.
   if (unsigned AS = getAddrSpace())
     OS << ", addrspace " << AS;
 
   OS << ')';
 }

llvm/lib/IR/Value.cpp

 
 namespace {
 // Various metrics for how much to strip off of pointers.
 enum PointerStripKind {
   PSK_ZeroIndices,
   PSK_ZeroIndicesAndAliases,
   PSK_ZeroIndicesSameRepresentation,
   PSK_ZeroIndicesAndInvariantGroups,
+  PSK_ZeroIndicesAndInvariantGroupsAndNoAliasIntr,
   PSK_InBoundsConstantIndices,
   PSK_InBounds
 };
 
 template <PointerStripKind StripKind> static void NoopCallback(const Value *) {}
 
 template <PointerStripKind StripKind>
 static const Value *stripPointerCastsAndOffsets(
static const Value *stripPointerCastsAndOffsets(
   do {
     Func(V);
     if (auto *GEP = dyn_cast<GEPOperator>(V)) {
       switch (StripKind) {
       case PSK_ZeroIndices:
       case PSK_ZeroIndicesAndAliases:
       case PSK_ZeroIndicesSameRepresentation:
       case PSK_ZeroIndicesAndInvariantGroups:
+      case PSK_ZeroIndicesAndInvariantGroupsAndNoAliasIntr:
         if (!GEP->hasAllZeroIndices())
           return V;
         break;
       case PSK_InBoundsConstantIndices:
         if (!GEP->hasAllConstantIndices())
           return V;
         LLVM_FALLTHROUGH;
       case PSK_InBounds:
if (auto *GEP = dyn_cast<GEPOperator>(V)) {
         // but it can't be marked with returned attribute, that's why it needs
         // special case.
         if (StripKind == PSK_ZeroIndicesAndInvariantGroups &&
             (Call->getIntrinsicID() == Intrinsic::launder_invariant_group ||
              Call->getIntrinsicID() == Intrinsic::strip_invariant_group)) {
           V = Call->getArgOperand(0);
           continue;
         }
+        // Same as above, but also for noalias intrinsics
+        if (StripKind == PSK_ZeroIndicesAndInvariantGroupsAndNoAliasIntr &&
+            (Call->getIntrinsicID() == Intrinsic::launder_invariant_group ||
+             Call->getIntrinsicID() == Intrinsic::strip_invariant_group ||
+             Call->getIntrinsicID() == Intrinsic::noalias ||
+             Call->getIntrinsicID() == Intrinsic::provenance_noalias ||
+             Call->getIntrinsicID() == Intrinsic::noalias_arg_guard ||
+             Call->getIntrinsicID() == Intrinsic::noalias_copy_guard)) {
+          V = Call->getArgOperand(0);
+          continue;
+        }
       }
       return V;
     }
     assert(V->getType()->isPointerTy() && "Unexpected operand type!");
   } while (Visited.insert(V).second);
 
   return V;
 }

 const Value *Value::stripInBoundsConstantOffsets() const {
   return stripPointerCastsAndOffsets<PSK_InBoundsConstantIndices>(this);
 }
 
 const Value *Value::stripPointerCastsAndInvariantGroups() const {
   return stripPointerCastsAndOffsets<PSK_ZeroIndicesAndInvariantGroups>(this);
 }
 
+const Value *Value::stripPointerCastsAndInvariantGroupsAndNoAliasIntr() const {
+  return stripPointerCastsAndOffsets<
+      PSK_ZeroIndicesAndInvariantGroupsAndNoAliasIntr>(this);
+}
+
 const Value *Value::stripAndAccumulateConstantOffsets(
     const DataLayout &DL, APInt &Offset, bool AllowNonInbounds,
     function_ref<bool(Value &, APInt &)> ExternalAnalysis) const {
   if (!getType()->isPtrOrPtrVectorTy())
     return this;
 
   unsigned BitWidth = Offset.getBitWidth();
   assert(BitWidth == DL.getIndexTypeSizeInBits(getType()) &&

llvm/test/Analysis/BasicAA/noalias-intr.ll

+; RUN: opt < %s -basic-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+; Function Attrs: nounwind
+define void @test01() #0 {
+entry:
+  %_pA = alloca i32, align 4
+  %_pB = alloca i32, align 4
+  %t1 = call i8* @llvm.noalias.decl.p0i8.p0p0i32.i32(i32** null, i32 0, metadata !2)
+  %t3 = call i8* @llvm.noalias.decl.p0i8.p0p0i32.i32(i32** null, i32 0, metadata !5)
+  %t5 = call i32* @llvm.noalias.p0i32.p0i8.p0p0i32.i32(i32* %_pA, i8* %t1, i32** null, i32 0, metadata !2), !tbaa !7, !noalias !11
+  store i32 42, i32* %t5, align 4, !tbaa !12, !noalias !11
+  %t7 = call i32* @llvm.noalias.p0i32.p0i8.p0p0i32.i32(i32* %_pB, i8* %t3, i32** null, i32 0, metadata !5), !tbaa !7, !noalias !11
+  store i32 43, i32* %t7, align 4, !tbaa !12, !noalias !11
+  ret void
+}
+; CHECK-LABEL: Function: test01:
+; CHECK: NoAlias:      i32* %t5, i32* %t7
+
+; Function Attrs: nounwind
+define void @test02() #0 {
+entry:
+  %_pA = alloca i32, align 4
+  %_pB = alloca i32, align 4
+  %t1 = call i8* @llvm.noalias.decl.p0i8.p0p0i32.i32(i32** null, i32 0, metadata !2)
+  %t3 = call i8* @llvm.noalias.decl.p0i8.p0p0i32.i32(i32** null, i32 0, metadata !5)
+  %t5 = call i32* @llvm.noalias.p0i32.p0i8.p0p0i32.i32(i32* %_pA, i8* %t1, i32** null, i32 0, metadata !2), !tbaa !7, !noalias !11
+  store i32 42, i32* %t5, align 4, !tbaa !12, !noalias !11
+  %t7 = call i32* @llvm.noalias.p0i32.p0i8.p0p0i32.i32(i32* %_pA, i8* %t3, i32** null, i32 0, metadata !5), !tbaa !7, !noalias !11
+  store i32 43, i32* %t7, align 4, !tbaa !12, !noalias !11
+  ret void
+}
+; CHECK-LABEL: Function: test02:
+; CHECK: MustAlias:      i32* %t5, i32* %t7
+
+
+; Function Attrs: nounwind
+define void @test11() #0 {
+entry:
+  %_pA = alloca i32, align 4
+  %_pB = alloca i32, align 4
+  %t1 = call i8* @llvm.noalias.decl.p0i8.p0p0i32.i32(i32** null, i32 0, metadata !2)
+  %t3 = call i8* @llvm.noalias.decl.p0i8.p0p0i32.i32(i32** null, i32 0, metadata !5)
+  %t5 = tail call i32* @llvm.provenance.noalias.p0i32.p0i8.p0p0i32.p0p0i32.i32(i32* %_pA, i8* %t1, i32** null, i32** undef, i32 0, metadata !2), !tbaa !7, !noalias !11
+  %.guard1 = call i32* @llvm.noalias.arg.guard.p0i32.p0i32(i32* %_pA, i32* %t5)
+  store i32 42, i32* %.guard1, align 4, !tbaa !12, !noalias !11
+  %.guard2 = call i32* @llvm.noalias.arg.guard.p0i32.p0i32(i32* %_pB, i32* %t5)
+  store i32 43, i32* %.guard2, align 4, !tbaa !12, !noalias !11
+  ret void
+}
+; CHECK-LABEL: Function: test11:
+; CHECK: NoAlias:      i32* %.guard1, i32* %.guard2
+
+; Function Attrs: nounwind
+define void @test12() #0 {
+entry:
+  %_pA = alloca i32, align 4
+  %_pB = alloca i32, align 4
+  %t1 = call i8* @llvm.noalias.decl.p0i8.p0p0i32.i32(i32** null, i32 0, metadata !2)
+  %t3 = call i8* @llvm.noalias.decl.p0i8.p0p0i32.i32(i32** null, i32 0, metadata !5)
+  %t5 = tail call i32* @llvm.provenance.noalias.p0i32.p0i8.p0p0i32.p0p0i32.i32(i32* %_pA, i8* %t1, i32** null, i32** undef, i32 0, metadata !2), !tbaa !7, !noalias !11
+  %.guard1 = call i32* @llvm.noalias.arg.guard.p0i32.p0i32(i32* %_pA, i32* %t5)
+  store i32 42, i32* %.guard1, align 4, !tbaa !12, !noalias !11
+  %.guard2 = call i32* @llvm.noalias.arg.guard.p0i32.p0i32(i32* %_pA, i32* %t5)
+  store i32 43, i32* %.guard2, align 4, !tbaa !12, !noalias !11
+  ret void
+}
+; CHECK-LABEL: Function: test12:
+; CHECK: MustAlias:      i32* %.guard1, i32* %.guard2
+
+; Function Attrs: nounwind
+define void @test21() #0 {
+entry:
+  %_pA = alloca i32, align 4
+  %_pB = alloca i32, align 4
+  %t1 = call i8* @llvm.noalias.decl.p0i8.p0p0i32.i32(i32** null, i32 0, metadata !2)
+  %t3 = call i8* @llvm.noalias.decl.p0i8.p0p0i32.i32(i32** null, i32 0, metadata !5)
+  %.guard1 = call i32* @llvm.noalias.copy.guard.p0i32.p0i8(i32* %_pA, i8* %t1, metadata !14, metadata !2)
+  store i32 42, i32* %.guard1, align 4, !tbaa !12, !noalias !11
+  %.guard2 = call i32* @llvm.noalias.copy.guard.p0i32.p0i8(i32* %_pB, i8* %t3, metadata !14, metadata !5)
+  store i32 43, i32* %.guard2, align 4, !tbaa !12, !noalias !11
+  ret void
+}
+; CHECK-LABEL: Function: test21:
+; CHECK: NoAlias:      i32* %.guard1, i32* %.guard2
+
+; Function Attrs: nounwind
+define void @test22() #0 {
+entry:
+  %_pA = alloca i32, align 4
+  %_pB = alloca i32, align 4
+  %t1 = call i8* @llvm.noalias.decl.p0i8.p0p0i32.i32(i32** null, i32 0, metadata !2)
+  %t3 = call i8* @llvm.noalias.decl.p0i8.p0p0i32.i32(i32** null, i32 0, metadata !5)
+  %.guard1 = call i32* @llvm.noalias.copy.guard.p0i32.p0i8(i32* %_pA, i8* %t1, metadata !14, metadata !2)
+  store i32 42, i32* %.guard1, align 4, !tbaa !12, !noalias !11
+  %.guard2 = call i32* @llvm.noalias.copy.guard.p0i32.p0i8(i32* %_pA, i8* %t3, metadata !14, metadata !5)
+  store i32 43, i32* %.guard2, align 4, !tbaa !12, !noalias !11
+  ret void
+}
+; CHECK-LABEL: Function: test22:
+; CHECK: MustAlias:      i32* %.guard1, i32* %.guard2
+
+; Function Attrs: argmemonly nounwind
+declare i8* @llvm.noalias.decl.p0i8.p0p0i32.i32(i32**, i32, metadata) #1
+
+; Function Attrs: argmemonly nounwind speculatable
+declare i32* @llvm.noalias.p0i32.p0i8.p0p0i32.i32(i32*, i8*, i32**, i32, metadata) #2
+
+; Function Attrs: nounwind readnone speculatable
+declare i32* @llvm.provenance.noalias.p0i32.p0i8.p0p0i32.p0p0i32.i32(i32*, i8*, i32**, i32**, i32, metadata) #3
+
+; Function Attrs: nounwind readnone
+declare i32* @llvm.noalias.arg.guard.p0i32.p0i32(i32*, i32*) #4
+
+; Function Attrs: nounwind readnone
+declare i32* @llvm.noalias.copy.guard.p0i32.p0i8(i32*, i8*, metadata, metadata) #4
+
+attributes #0 = { nounwind "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #1 = { argmemonly nounwind }
+attributes #2 = { argmemonly nounwind speculatable }
+attributes #3 = { nounwind readnone speculatable }
+attributes #4 = { nounwind readnone }
+
+!llvm.module.flags = !{!0}
+!llvm.ident = !{!1}
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!1 = !{!"clang"}
+!2 = !{!3}
+!3 = distinct !{!3, !4, !"test01: _pA"}
+!4 = distinct !{!4, !"test01"}
+!5 = !{!6}
+!6 = distinct !{!6, !4, !"test01: _pB"}
+!7 = !{!8, !8, i64 0, i64 4}
+!8 = !{!9, i64 4, !"any pointer"}
+!9 = !{!10, i64 1, !"omnipotent char"}
+!10 = !{!"Simple C/C++ TBAA"}
+!11 = !{!3, !6}
+!12 = !{!13, !13, i64 0, i64 4}
+!13 = !{!9, i64 4, !"int"}
+!14 = !{!15}
+!15 = !{i64 -1, i64 0}