llvm.noalias - The AA implementaton

[hfinkel]

Summary

This is part of the series started by D9375, and adds the actual AA implementation which uses the intrinsics.

Roughly, we need to check for an access through pointer derived from a llvm.noalias call, which compatible noalias metadata, where the other access also has compatible metadata, but is not derived from that llvm.noalias call (or any other with the same scope). This needs to include the possibility that the pointer has been captured and we're deriving from some use of the captured pointer. Precise capturing analysis requires a DT to be available, and if it is not, and there are captures, the answers will not be as good (as demonstrated by the noalias-dup-scope.ll test case). When looking for compatible llvm.noalias calls, we might need to look through others. If we hit a PHI or select, we need to combine the compatibility results from all possible inputs.

[reames]

Resigning as a reviewer to get a very stale review off my list of blocking tasks in phabricator. Please reopen when desired.

[hfinkel]

Rebased.

Note that there is some hackery around making the DominatorTree available to the pass when run through its legacy-pass-manager wrapper; this can be removed once legacy-pass-manager support goes away.

[majnemer]

lib/Analysis/ScopedNoAliasAA.cpp

283

llvm::find_if ?

305–308

const auto *

309–310

The following would be a little more compact:

for (Value *IncommingValue : PN->incoming_values())

Children.push_back(IncommingValue);

356

Perhaps:

for (Value *Arg : CSA.args())

406

Ditto.

438

auto *

464

Ditto.

[hfinkel]

lib/Analysis/ScopedNoAliasAA.cpp

283

Nice! I didn't know we had that :-)

305–308

Sure, and I'll make all of the updates you've suggested below. Thanks!

[hfinkel]

Updated per review comments.

[majnemer]

I've reviewed this to my satisfaction but you will need a more thorough review by an AA expert.

lib/Analysis/ScopedNoAliasAA.cpp

317

Might be good to hoist this out of the loop and clear it at the start of the loop. Saves you having to reallocate if the set goes big.

320

Ditto with this vector.

[hfinkel]

Rebased (and addressed reviewer feedback).

[hfinkel]

Ping.

[jeroen.dobbelaere]

lib/Analysis/ScopedNoAliasAA.cpp

150–155

Use CS2NoAlias and CS1NoAlias, in stead of CS2.getInstru.... and CS1.getInstru....

[jeroen.dobbelaere]

Hi Hal, I found an issue with this part when analyzing two pointers that are 'derived from each other', but are used in different loops.
Following code would go wrong:

int* restrict p=malloc(sizeof(int)*20);
int i;
for (i=0; i<20; ++i) {p[i]=i; }
for (i=0; i<20; ++i) { if (p[i] != i) should_never_happen(); }

Do you think that the proposed fix is ok ?

lib/Analysis/ScopedNoAliasAA.cpp

454

We need an extra check here to see if APtr is directly depending on BPtr. Something like following code should do the trick:

{
  // Check if A depends directly on B
  SmallVector<Value *, 8> AObjs;
  GetUnderlyingObjects(const_cast<Value*>(APtr), AObjs, DL, nullptr, 0, nullptr);
  DEBUG(dbgs() << "SNA: underlying objects:\n");
#ifndef NDEBUG
  for (auto *A : AObjs)
    DEBUG(dbgs() << "\t" << *A << "\n");
  DEBUG(dbgs() << "\n"); 
#endif
  if (CSB) {
    for (Value* Arg : CSB.args())
      if (llvm::is_contained(AObjs, Arg)) {
        DEBUG(dbgs() << "SNA : A depends directly on B:"; Arg->dump());

        return false;
      }
  } else if (llvm::is_contained(AObjs, BPtr)) {
    DEBUG(dbgs() << "SNA : A depends directly on B:"; BPtr->dump());
    return false;
  }
}

[hfinkel]

In D9401#833714, @jeroen.dobbelaere wrote:

Hi Hal, I found an issue with this part when analyzing two pointers that are 'derived from each other', but are used in different loops.
Following code would go wrong:

int* restrict p=malloc(sizeof(int)*20);
int i;
for (i=0; i<20; ++i) {p[i]=i; }
for (i=0; i<20; ++i) { if (p[i] != i) should_never_happen(); }

Do you think that the proposed fix is ok ?

I don't yet understand what's wrong. Can you provide a full test case? Locally, the results on this look fine.

FYI: There is currently some problem because the current patchset miscompiles MultiSource/Benchmarks/tramp3d-v4.

lib/Analysis/ScopedNoAliasAA.cpp

454

I don't see why this should be needed. If A is derived from B, and A is also derived from some some noalias intrinsic N, then either B is derived from N or N is derived from B. The former case is one for which we explicitly check (it checks whether B is derived from the same intrinsic, or any other compatible one) and the latter case correctly returns noalias.

[hfinkel]

Rebased.

[amehsan]

lib/Analysis/ScopedNoAliasAA.cpp

382

I think it should be if (CSB)

436–451

IIUC, with the logic that we have here, removing a llvm.noalias from the IR could be a functional problem. The example below can expose the issue (AFAICT, the example has no UB...but please double check.

void foo(int *a, int *b, int *c, int *d, int n)  {

  int *restrict s;

  for (int i = 10; i < 800; ++i) {
    s = c + b[i];
    *a += *s;
  }


  int *r = s;
  s = d + 8;

  *s = *r + *s;

}

I compile this with the following options: -O2 -S -emit-llvm -fno-unroll-loops. Then I manually remove the llvm.noalias intrinsic inside the loop body and make necessary changes. This is the interesting parts of the IR

entry:
  br label %for.body

for.cond.cleanup:                                 ; preds = %for.body
  %add.ptr1 = getelementptr inbounds i32, i32* %d, i64 8
  %0 = tail call i32* @llvm.noalias.p0i32(i32* %add.ptr1, metadata !1)

for.body:                                         ; preds = %for.body, %entry
  %add.ptr = getelementptr inbounds i32, i32* %c, i64 %idx.ext
}

Then I feed the manually modified IR to opt, with options -O2 -debug and I see this debug msg:

SNA: A:   %0 = tail call i32* @llvm.noalias.p0i32(i32* %add.ptr1, metadata !5)
SNA: B:   %add.ptr = getelementptr inbounds i32, i32* %c, i64 %idx.ext
SNA: Found a compatible set!
          %0 = tail call i32* @llvm.noalias.p0i32(i32* %add.ptr1, metadata !5)

SNA: B/CSB noalias:

SNA: B does not derive from the compatible set!
SNA: DT is available
 SNA: noalias!

So we seem to prove %0 and %add.ptr are not aliased, but they might be aliased legally, IIUC.

For some more interesting examples, the problem is not exposed because currently at the very end of BasicAAResult::aliasGEP we conservatively return PartialAlias.

include/llvm/Analysis/ScopedNoAliasAA.h

 
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Pass.h"
 
 namespace llvm {
+class DominatorTree;
 
 /// A simple AA result which uses scoped-noalias metadata to answer queries.
 class ScopedNoAliasAAResult : public AAResultBase<ScopedNoAliasAAResult> {
   friend AAResultBase<ScopedNoAliasAAResult>;
 
 public:
+  ScopedNoAliasAAResult(DominatorTree *DT) : AAResultBase(), DT(DT) {}
+
   /// Handle invalidation events from the new pass manager.
   ///
   /// By definition, this result is stateless and so remains valid.
   bool invalidate(Function &, const PreservedAnalyses &,
                   FunctionAnalysisManager::Invalidator &) {
     return false;
   }
 
   AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB);
   ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc);
   ModRefInfo getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2);
 
+  // FIXME: This interface can be removed once the legacy-pass-manager support
+  // is removed.
+  void setDT(DominatorTree *DT) {
+    this->DT = DT;
+  }
+
 private:
   bool mayAliasInScopes(const MDNode *Scopes, const MDNode *NoAlias) const;
+
+  bool findCompatibleNoAlias(const Value *P,
+                             const MDNode *ANoAlias, const MDNode *BNoAlias,
+                             const DataLayout &DL,
+                             SmallPtrSetImpl<const Value *> &Visited,
+                             SmallVectorImpl<Instruction *> &CompatibleSet,
+                             int Depth = 0);
+  bool noAliasByIntrinsic(const MDNode *ANoAlias,
+                          const Value *APtr,
+                          const MDNode *BNoAlias,
+                          const Value *BPtr,
+                          ImmutableCallSite CSA = ImmutableCallSite(),
+                          ImmutableCallSite CSB = ImmutableCallSite());
+
+  DominatorTree *DT;
 };
 
 /// Analysis pass providing a never-invalidated alias analysis result.
 class ScopedNoAliasAA : public AnalysisInfoMixin<ScopedNoAliasAA> {
   friend AnalysisInfoMixin<ScopedNoAliasAA>;
   static AnalysisKey Key;
 
 public:
   typedef ScopedNoAliasAAResult Result;
 
   ScopedNoAliasAAResult run(Function &F, FunctionAnalysisManager &AM);
 };
 
 /// Legacy wrapper pass to provide the ScopedNoAliasAAResult object.
 class ScopedNoAliasAAWrapperPass : public ImmutablePass {
   std::unique_ptr<ScopedNoAliasAAResult> Result;
 
 public:
   static char ID;
 
   ScopedNoAliasAAWrapperPass();
 
-  ScopedNoAliasAAResult &getResult() { return *Result; }
+  ScopedNoAliasAAResult &getResult() { setDT(); return *Result; }
   const ScopedNoAliasAAResult &getResult() const { return *Result; }
 
   bool doInitialization(Module &M) override;
   bool doFinalization(Module &M) override;
   void getAnalysisUsage(AnalysisUsage &AU) const override;
+
+private:
+  void setDT();
 };
 
 //===--------------------------------------------------------------------===//
 //
 // createScopedNoAliasAAWrapperPass - This pass implements metadata-based
 // scoped noalias analysis.
 //
 ImmutablePass *createScopedNoAliasAAWrapperPass();
 }
 
 #endif

lib/Analysis/ScopedNoAliasAA.cpp

 // When evaluating an aliasing query, if one of the instructions is associated
 // has a set of noalias scopes in some domain that is a superset of the alias
 // scopes in that domain of some other instruction, then the two memory
 // accesses are assumed not to alias.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/ScopedNoAliasAA.h"
+#include "llvm/Analysis/CaptureTracking.h"
+#include "llvm/Analysis/ValueTracking.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/IR/Constants.h"
+#include "llvm/IR/Dominators.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
 
 using namespace llvm;
 
+#define DEBUG_TYPE "scoped-noalias"
+
 // A handy option for disabling scoped no-alias functionality. The same effect
 // can also be achieved by stripping the associated metadata tags from IR, but
 // this option is sometimes more convenient.
 static cl::opt<bool> EnableScopedNoAlias("enable-scoped-noalias",
-                                         cl::init(true));
+  cl::init(true), cl::Hidden,
+  cl::desc("Enable use of scoped-noalias metadata"));
+
+static cl::opt<int>
+MaxNoAliasDepth("scoped-noalias-max-depth", cl::init(12), cl::Hidden,
+  cl::desc("Maximum depth for noalias intrinsic search"));
 
 namespace {
 /// This is a simple wrapper around an MDNode which provides a higher-level
 /// interface by hiding the details of how alias analysis information is encoded
 /// in its operands.
 class AliasScopeNode {
   const MDNode *Node;
 
AliasResult ScopedNoAliasAAResult::alias(const MemoryLocation &LocA,
   const MDNode *ANoAlias = LocA.AATags.NoAlias, *BNoAlias = LocB.AATags.NoAlias;
 
   if (!mayAliasInScopes(AScopes, BNoAlias))
     return NoAlias;
 
   if (!mayAliasInScopes(BScopes, ANoAlias))
     return NoAlias;
 
+  if (noAliasByIntrinsic(ANoAlias, LocA.Ptr, BNoAlias, LocB.Ptr))
+    return NoAlias;
+
+  if (noAliasByIntrinsic(BNoAlias, LocB.Ptr, ANoAlias, LocA.Ptr))
+    return NoAlias;
+
   // If they may alias, chain to the next AliasAnalysis.
   return AAResultBase::alias(LocA, LocB);
 }
 
 ModRefInfo ScopedNoAliasAAResult::getModRefInfo(ImmutableCallSite CS,
                                                 const MemoryLocation &Loc) {
   if (!EnableScopedNoAlias)
     return AAResultBase::getModRefInfo(CS, Loc);
 
-  if (!mayAliasInScopes(Loc.AATags.Scope, CS.getInstruction()->getMetadata(
-                                              LLVMContext::MD_noalias)))
+  const MDNode *CSNoAlias =
+    CS.getInstruction()->getMetadata(LLVMContext::MD_noalias);
+  if (!mayAliasInScopes(Loc.AATags.Scope, CSNoAlias))
+    return MRI_NoModRef;
+
+  const MDNode *CSScopes =
+    CS.getInstruction()->getMetadata(LLVMContext::MD_alias_scope);
+  if (!mayAliasInScopes(CSScopes, Loc.AATags.NoAlias))
+    return MRI_NoModRef;
+
+  if (noAliasByIntrinsic(Loc.AATags.NoAlias, Loc.Ptr, CSNoAlias,
+                         nullptr, ImmutableCallSite(), CS))
     return MRI_NoModRef;
 
-  if (!mayAliasInScopes(
-          CS.getInstruction()->getMetadata(LLVMContext::MD_alias_scope),
-          Loc.AATags.NoAlias))
+  if (noAliasByIntrinsic(CSNoAlias, nullptr, Loc.AATags.NoAlias, Loc.Ptr, CS))
     return MRI_NoModRef;
 
   return AAResultBase::getModRefInfo(CS, Loc);
 }
 
 ModRefInfo ScopedNoAliasAAResult::getModRefInfo(ImmutableCallSite CS1,
                                                 ImmutableCallSite CS2) {
   if (!EnableScopedNoAlias)
     return AAResultBase::getModRefInfo(CS1, CS2);
 
-  if (!mayAliasInScopes(
-          CS1.getInstruction()->getMetadata(LLVMContext::MD_alias_scope),
+  const MDNode *CS1Scopes =
+    CS1.getInstruction()->getMetadata(LLVMContext::MD_alias_scope);
+  const MDNode *CS2Scopes =
+    CS2.getInstruction()->getMetadata(LLVMContext::MD_alias_scope);
+  const MDNode *CS1NoAlias =
+    CS1.getInstruction()->getMetadata(LLVMContext::MD_noalias);
+  const MDNode *CS2NoAlias =
+    CS2.getInstruction()->getMetadata(LLVMContext::MD_noalias);
+  if (!mayAliasInScopes(CS1Scopes,
           CS2.getInstruction()->getMetadata(LLVMContext::MD_noalias)))
     return MRI_NoModRef;
 
-  if (!mayAliasInScopes(
-          CS2.getInstruction()->getMetadata(LLVMContext::MD_alias_scope),
+  if (!mayAliasInScopes(CS2Scopes,
           CS1.getInstruction()->getMetadata(LLVMContext::MD_noalias)))
     return MRI_NoModRef;
 
+  if (noAliasByIntrinsic(CS1NoAlias, nullptr, CS2NoAlias, nullptr, CS1, CS2))
+    return MRI_NoModRef;
+
+  if (noAliasByIntrinsic(CS2NoAlias, nullptr, CS1NoAlias, nullptr, CS2, CS1))
+    return MRI_NoModRef;
+
   return AAResultBase::getModRefInfo(CS1, CS2);
 }
 
 static void collectMDInDomain(const MDNode *List, const MDNode *Domain,
                               SmallPtrSetImpl<const MDNode *> &Nodes) {
   for (const MDOperand &MDOp : List->operands())
     if (const MDNode *MD = dyn_cast<MDNode>(MDOp))
       if (AliasScopeNode(MD).getDomain() == Domain)
for (const MDNode *Domain : Domains) {
 
     if (FoundAll)
       return false;
   }
 
   return true;
 }
 
+bool ScopedNoAliasAAResult::findCompatibleNoAlias(const Value *P,
+  const MDNode *ANoAlias, const MDNode *BNoAlias, const DataLayout &DL,
+  SmallPtrSetImpl<const Value *> &Visited,
+  SmallVectorImpl<Instruction *> &CompatibleSet, int Depth) {
+  // When a pointer is derived from multiple noalias calls, there are two
+  // potential reasons:
+  //   1. The path of derivation is uncertain (because of a select, PHI, etc.).
+  //   2. Some noalias calls are derived from other noalias calls.
+  // Logically, we need to treat (1) as an "and" and (2) as an "or" when
+  // checking for scope compatibility. If we don't know from which noalias call
+  // a pointer is derived, then we need to require compatibility with all of
+  // them. If we're derived from a noalias call that is derived from another
+  // noalias call, then we need the ability to effectively ignore the inner one
+  // in favor of the outer one (thus, we only need compatibility with one or
+  // the other).
+  //
+  // Scope compatibility means that, as with the noalias metadata, within each
+  // domain, the set of noalias intrinsic scopes is a subset of the noalias
+  // scopes.
+  //
+  // Given this, we check compatibility of the relevant sets of noalias calls
+  // from which LocA.Ptr might derive with both LocA.AATags.NoAlias and
+  // LocB.AATags.NoAlias, and LocB.Ptr does not derive from any of the noalias
+  // calls in some set, then we can conclude NoAlias.
+  //
+  // So if we have:
+  //   noalias1  noalias3
+  //      |         |
+  //   noalias2  noalias4
+  //      |         |
+  //       \       /
+  //        \     /
+  //         \   /
+  //          \ /
+  //         select
+  //           |
+  //        noalias5
+  //           |
+  //        noalias6
+  //           |
+  //          PtrA
+  //
+  //  - If PtrA is compatible with noalias6, and PtrB is also compatible,
+  //    but does not derive from noalias6, then NoAlias.
+  //  - If PtrA is compatible with noalias5, and PtrB is also compatible,
+  //    but does not derive from noalias5, then NoAlias.
+  //  - If PtrA is compatible with noalias2 and noalias4, and PtrB is also
+  //    compatible, but does not derive from either, then NoAlias.
+  //  - If PtrA is compatible with noalias2 and noalias3, and PtrB is also
+  //    compatible, but does not derive from either, then NoAlias.
+  //  - If PtrA is compatible with noalias1 and noalias4, and PtrB is also
+  //    compatible, but does not derive from either, then NoAlias.
+  //  - If PtrA is compatible with noalias1 and noalias3, and PtrB is also
+  //    compatible, but does not derive from either, then NoAlias.
+  //
+  //  We don't need, or want, to explicitly build N! sets to check for scope
+  //  compatibility. Instead, recurse through the tree of underlying objects.
+
+  SmallVector<Instruction *, 8> NoAliasCalls;
+  P = GetUnderlyingObject(P, DL, 0, &NoAliasCalls);
+
+  // If we've already visited this underlying value (likely because this is a
+  // PHI that depends on itself, directly or indirectly), we must not have
+  // returned false the first time, so don't do so this time either.
+  if (!Visited.insert(P).second)
+    return true;
+
+  // Our pointer is derived from P, with NoAliasCalls along the way.
+  // Compatibility with any of them is fine.
+  auto NAI =
+    find_if(NoAliasCalls,
+                 [&](Instruction *A) {
+                  return !mayAliasInScopes(
+                             dyn_cast<MDNode>(
+                               cast<MetadataAsValue>(A->getOperand(1))->
+                                 getMetadata()), ANoAlias) &&
+                         !mayAliasInScopes(
+                             dyn_cast<MDNode>(
+                               cast<MetadataAsValue>(A->getOperand(1))->
+                                 getMetadata()), BNoAlias);
+                 });
+  if (NAI != NoAliasCalls.end()) {
+    CompatibleSet.push_back(*NAI);
+    return true;
+  }
+
+  // We've not found a compatible noalias call, but we might be able to keep
+  // looking. If this underlying object is really a PHI or a select, we can
+  // check the incoming values. They all need to be compatible, and if so, we
+  // can take the union of all of the compatible noalias calls as the set to
+  // return for further validation.
+  SmallVector<const Value *, 8> Children;
+  if (const auto *SI = dyn_cast<SelectInst>(P)) {
+    Children.push_back(SI->getTrueValue());
+    Children.push_back(SI->getFalseValue());
+  } else if (const auto *PN = dyn_cast<PHINode>(P)) {
+    for (Value *IncommingValue : PN->incoming_values())
+      Children.push_back(IncommingValue);
+  }
+
+  if (Children.empty() || Depth == MaxNoAliasDepth)
+    return false;
+
+  SmallPtrSet<const Value *, 16> ChildVisited;
+  SmallVector<Instruction *, 8> ChildCompatSet;
+  for (auto &C : Children) {
+    ChildVisited.clear();
+    ChildVisited.insert(Visited.begin(), Visited.end());
+    ChildVisited.insert(P);
+
+    ChildCompatSet.clear();
+    if (!findCompatibleNoAlias(C, ANoAlias, BNoAlias, DL, ChildVisited,
+                               ChildCompatSet, Depth+1))
+      return false;
+
+    CompatibleSet.insert(CompatibleSet.end(),
+                         ChildCompatSet.begin(), ChildCompatSet.end());
+  }
+
+  // All children were compatible, and we've added them to CompatibleSet.
+  return true;
+}
+
+bool ScopedNoAliasAAResult::noAliasByIntrinsic(const MDNode *ANoAlias,
+                                               const Value *APtr,
+                                               const MDNode *BNoAlias,
+                                               const Value *BPtr,
+                                               ImmutableCallSite CSA,
+                                               ImmutableCallSite CSB) {
+  if (!ANoAlias || !BNoAlias)
+    return false;
+
+  if (CSA) {
+    // We're querying a callsite against something else, where we want to know
+    // if the callsite (CSA) is derived from some noalias call(s) and the other
+    // thing is not derived from those noalias call(s). This can be determined
+    // only if CSA only accesses memory through its arguments.
+    FunctionModRefBehavior MRB = getModRefBehavior(CSA);
+    if (MRB != FMRB_OnlyAccessesArgumentPointees &&
+        MRB != FMRB_OnlyReadsArgumentPointees)
+      return false;
+
+    DEBUG(dbgs() << "SNA: CSA: " << *CSA.getInstruction() << "\n");
+    // Since the memory-access behavior of CSA is determined only by its
+    // arguments, we can answer this query in the affirmative if we can prove a
+    // lack of aliasing for all pointer arguments.
+    for (Value *Arg : CSA.args()) {
+      if (!Arg->getType()->isPointerTy())
+        continue;
+
+      if (!noAliasByIntrinsic(ANoAlias, Arg, BNoAlias, BPtr,
+                              ImmutableCallSite(), CSB)) {
+        DEBUG(dbgs() << "SNA: CSA: noalias fail for arg: " << *Arg << "\n");
+        return false;
+      }
+    }
+
+    return true;
+  }
+
+  const auto *AInst = dyn_cast<Instruction>(APtr);
+  if (!AInst || !AInst->getParent())
+    return false;
+  const DataLayout &DL = AInst->getParent()->getModule()->getDataLayout();
+
+  if (!CSB && !BPtr)
+    return false;
+
+  DEBUG(dbgs() << "SNA: A: " << *APtr << "\n");
+  DEBUG(dbgs() << "SNA: "; if (CSA) dbgs() << "CSB: " << *CSB.getInstruction();
+                           else dbgs() << "B: " << *BPtr; dbgs() << "\n");
+
+  SmallPtrSet<const Value *, 8> Visited;
+  SmallVector<Instruction *, 8> CompatibleSet;
+  if (!findCompatibleNoAlias(APtr, ANoAlias, BNoAlias, DL, Visited,
+                             CompatibleSet))
+    return false;
+
+  assert(!CompatibleSet.empty() &&
+         "Fould an empty set of compatible intrinsics?");
+
+  DEBUG(dbgs() << "SNA: Found a compatible set!\n");
+#ifndef NDEBUG
+  for (auto &C : CompatibleSet)
+    DEBUG(dbgs() << "\t" << *C << "\n");
+  DEBUG(dbgs() << "\n");
+#endif
+
+  // We have a set of compatible noalias calls (compatible with the scopes from
+  // both LocA and LocB) from which LocA.Ptr potentially derives. We now need
+  // to make sure that LocB.Ptr does not derive from any in that set. For
+  // correctness, there cannot be a depth limit here (if a pointer is derived
+  // from a noalias call, we must know).
+  SmallVector<Value *, 8> BObjs;
+  SmallVector<Instruction *, 8> BNoAliasCalls;
+  if (CSB) {
+    for (Value *Arg : CSB.args())
+      GetUnderlyingObjects(Arg, BObjs, DL, nullptr, 0, &BNoAliasCalls);
+  } else {
+    GetUnderlyingObjects(const_cast<Value*>(BPtr), BObjs, DL, nullptr, 0,
+                         &BNoAliasCalls);
+  }
+
+  DEBUG(dbgs() << "SNA: B/CSB noalias:\n");
+#ifndef NDEBUG
+  for (auto &B : BNoAliasCalls)
+    DEBUG(dbgs() << "\t" << *B << "\n");
+  DEBUG(dbgs() << "\n");
+#endif
+
+  // The noalias scope from the compatible intrinsics are really identified by
+  // their scope argument, and we need to make sure that LocB.Ptr is not only
+  // not derived from the calls currently in CompatibleSet, but also from any
+  // other intrinsic with the same scope. We can't just search the list of
+  // noalias intrinsics in BNoAliasCalls because we care not just about those
+  // direct dependence, but also dependence through capturing. Metadata
+  // do not have use lists, but MetadataAsValue objects do (and they are
+  // uniqued), so we can search their use list. As a result, however,
+  // correctness demands that the scope list has only one element (so that we
+  // can find all uses of that scope by noalias intrinsics by looking at the
+  // use list of the associated scope list).
+  SmallPtrSet<Instruction *, 8> CompatibleSetMembers(CompatibleSet.begin(),
+                                                     CompatibleSet.end());
+  SmallVector<MetadataAsValue *, 8> CompatibleSetMVs;
+  for (auto &C : CompatibleSet)
+    CompatibleSetMVs.push_back(cast<MetadataAsValue>(C->getOperand(1)));
+  for (auto &MV : CompatibleSetMVs)
+    for (Use &U : MV->uses())
+      if (auto *UI = dyn_cast<Instruction>(U.getUser()))
+        if (CompatibleSetMembers.insert(UI).second) {
+          CompatibleSet.push_back(UI);
+          DEBUG(dbgs() << "SNA: Adding to compatible set based on MD use: " <<
+                          *UI << "\n");
+        }
+
+  if (std::find_first_of(CompatibleSet.begin(), CompatibleSet.end(),
+                         BNoAliasCalls.begin(), BNoAliasCalls.end()) !=
+        CompatibleSet.end())
+    return false;
+
+  DEBUG(dbgs() << "SNA: B does not derive from the compatible set!\n");
+
+  // Note: This can be removed when legacy-pass-manager support is removed;
+  // BasicAA always has a DT available, and only under the hack where this is
+  // an immutable pass, not a function pass, might we not have one.
+  DEBUG(dbgs() << "SNA: DT is " << (DT ? "available" : "unavailable") << "\n");
+
+  // We now know that LocB.Ptr does not derive from any of the noalias calls in
+  // CompatibleSet directly. We do, however, need to make sure that it cannot
+  // derive from them by capture.
+  for (auto &V  : BObjs) {
+    // If the underlying object is not an instruction, then it can't be
+    // capturing the output value of an instruction (specifically, the noalias
+    // intrinsic call), and we can ignore it.
+    auto *I = dyn_cast<Instruction>(V);
+    if (!I)
+      continue;
+    if (isIdentifiedFunctionLocal(I))
+      continue;
+
+    DEBUG(dbgs() << "SNA: Capture check for B/CSB UO: " << *I << "\n");
+
+    // If the value from the noalias intrinsic has been captured prior to the
+    // instruction defining the underlying object, then LocB.Ptr might yet be
+    // derived from the return value of the noalias intrinsic, and we cannot
+    // conclude anything about the aliasing.
+    for (auto &C : CompatibleSet)
+      if (PointerMayBeCapturedBefore(C, /* ReturnCaptures */false,
+                                        /* StoreCaptures */false, I, DT)) {
+        DEBUG(dbgs() << "SNA: Pointer " << *C << " might be captured!\n");
+        return false;
+      }
+  }
+
+  if (CSB) {
+    FunctionModRefBehavior MRB = getModRefBehavior(CSB);
+    if (MRB != FMRB_OnlyAccessesArgumentPointees &&
+        MRB != FMRB_OnlyReadsArgumentPointees) {
+      // If we're querying against a callsite, and it might read from memory
+      // not based on its arguments, then we need to check whether or not the
+      // relevant noalias results have been captured prior to the callsite.
+      for (auto &C : CompatibleSet)
+        if (PointerMayBeCapturedBefore(C, /* ReturnCaptures */false,
+                                          /* StoreCaptures */false,
+                                          CSB.getInstruction(), DT)) {
+          DEBUG(dbgs() << "SNA: CSB: Pointer " << *C <<
+                          " might be captured!\n");
+          return false;
+        }
+    }
+  }
+
+  DEBUG(dbgs() << " SNA: noalias!\n");
+  return true;
+}
+
 AnalysisKey ScopedNoAliasAA::Key;
 
 ScopedNoAliasAAResult ScopedNoAliasAA::run(Function &F,
                                            FunctionAnalysisManager &AM) {
-  return ScopedNoAliasAAResult();
+  return ScopedNoAliasAAResult(&AM.getResult<DominatorTreeAnalysis>(F));
 }
 
 char ScopedNoAliasAAWrapperPass::ID = 0;
 INITIALIZE_PASS(ScopedNoAliasAAWrapperPass, "scoped-noalias",
                 "Scoped NoAlias Alias Analysis", false, true)
 
 ImmutablePass *llvm::createScopedNoAliasAAWrapperPass() {
   return new ScopedNoAliasAAWrapperPass();
 }
 
 ScopedNoAliasAAWrapperPass::ScopedNoAliasAAWrapperPass() : ImmutablePass(ID) {
   initializeScopedNoAliasAAWrapperPassPass(*PassRegistry::getPassRegistry());
 }
 
 bool ScopedNoAliasAAWrapperPass::doInitialization(Module &M) {
-  Result.reset(new ScopedNoAliasAAResult());
+  Result.reset(new ScopedNoAliasAAResult(nullptr));
   return false;
 }
 
 bool ScopedNoAliasAAWrapperPass::doFinalization(Module &M) {
   Result.reset();
   return false;
 }
 
+void ScopedNoAliasAAWrapperPass::setDT() {
+  auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
+  if (DTWP)
+    Result->setDT(&DTWP->getDomTree());
+}
+
 void ScopedNoAliasAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesAll();
 }

test/Analysis/ScopedNoAliasAA/noalias-calls.ll

+; RUN: opt < %s -basicaa -scoped-noalias -aa-eval -evaluate-aa-metadata -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Function Attrs: nounwind
+declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture, i8* nocapture readonly, i64, i32, i1) #1
+
+; Function Attrs: nounwind
+declare void @hey() #1
+
+; Function Attrs: nounwind uwtable
+define void @foo(i8* nocapture %a, i8* nocapture readonly %c, i8* nocapture %b) #2 {
+entry:
+  %l.i = alloca i8, i32 512, align 1
+  %0 = call i8* @llvm.noalias.p0i8(i8* %a, metadata !0) #0
+  %1 = call i8* @llvm.noalias.p0i8(i8* %c, metadata !3) #0
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %0, i8* %b, i64 16, i32 16, i1 false) #1, !noalias !5
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %b, i8* %1, i64 16, i32 16, i1 false) #1, !noalias !5
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %0, i8* %1, i64 16, i32 16, i1 false) #1, !noalias !5
+  call void @hey() #1, !noalias !5
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %l.i, i8* %1, i64 16, i32 16, i1 false) #1, !noalias !5
+  ret void
+}
+
+; CHECK-LABEL: Function: foo:
+; CHECK: Just Ref:   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %0, i8* %b, i64 16, i32 16, i1 false) #1, !noalias !5 <->   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %b, i8* %1, i64 16, i32 16, i1 false) #1, !noalias !5
+; CHECK: Just Mod:   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %0, i8* %b, i64 16, i32 16, i1 false) #1, !noalias !5 <->   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %0, i8* %1, i64 16, i32 16, i1 false) #1, !noalias !5
+; CHECK: Just Ref:   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %0, i8* %b, i64 16, i32 16, i1 false) #1, !noalias !5 <->   call void @hey() #1, !noalias !5
+; CHECK: NoModRef:   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %0, i8* %b, i64 16, i32 16, i1 false) #1, !noalias !5 <->   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %l.i, i8* %1, i64 16, i32 16, i1 false) #1, !noalias !5
+; CHECK: Just Mod:   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %b, i8* %1, i64 16, i32 16, i1 false) #1, !noalias !5 <->   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %0, i8* %b, i64 16, i32 16, i1 false) #1, !noalias !5
+; CHECK: NoModRef:   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %b, i8* %1, i64 16, i32 16, i1 false) #1, !noalias !5 <->   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %0, i8* %1, i64 16, i32 16, i1 false) #1, !noalias !5
+; CHECK: Just Mod:   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %b, i8* %1, i64 16, i32 16, i1 false) #1, !noalias !5 <->   call void @hey() #1, !noalias !5
+; CHECK: NoModRef:   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %b, i8* %1, i64 16, i32 16, i1 false) #1, !noalias !5 <->   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %l.i, i8* %1, i64 16, i32 16, i1 false) #1, !noalias !5
+; CHECK: Just Mod:   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %0, i8* %1, i64 16, i32 16, i1 false) #1, !noalias !5 <->   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %0, i8* %b, i64 16, i32 16, i1 false) #1, !noalias !5
+; CHECK: NoModRef:   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %0, i8* %1, i64 16, i32 16, i1 false) #1, !noalias !5 <->   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %b, i8* %1, i64 16, i32 16, i1 false) #1, !noalias !5
+; CHECK: NoModRef:   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %0, i8* %1, i64 16, i32 16, i1 false) #1, !noalias !5 <->   call void @hey() #1, !noalias !5
+; CHECK: NoModRef:   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %0, i8* %1, i64 16, i32 16, i1 false) #1, !noalias !5 <->   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %l.i, i8* %1, i64 16, i32 16, i1 false) #1, !noalias !5
+; CHECK: Just Mod:   call void @hey() #1, !noalias !5 <->   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %0, i8* %b, i64 16, i32 16, i1 false) #1, !noalias !5
+; CHECK: Both ModRef:   call void @hey() #1, !noalias !5 <->   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %b, i8* %1, i64 16, i32 16, i1 false) #1, !noalias !5
+; CHECK: NoModRef:   call void @hey() #1, !noalias !5 <->   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %0, i8* %1, i64 16, i32 16, i1 false) #1, !noalias !5
+; CHECK: NoModRef:   call void @hey() #1, !noalias !5 <->   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %l.i, i8* %1, i64 16, i32 16, i1 false) #1, !noalias !5
+; CHECK: NoModRef:   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %l.i, i8* %1, i64 16, i32 16, i1 false) #1, !noalias !5 <->   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %0, i8* %b, i64 16, i32 16, i1 false) #1, !noalias !5
+; CHECK: NoModRef:   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %l.i, i8* %1, i64 16, i32 16, i1 false) #1, !noalias !5 <->   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %b, i8* %1, i64 16, i32 16, i1 false) #1, !noalias !5
+; CHECK: NoModRef:   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %l.i, i8* %1, i64 16, i32 16, i1 false) #1, !noalias !5 <->   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %0, i8* %1, i64 16, i32 16, i1 false) #1, !noalias !5
+; CHECK: NoModRef:   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %l.i, i8* %1, i64 16, i32 16, i1 false) #1, !noalias !5 <->   call void @hey() #1, !noalias !5
+
+; Function Attrs: nounwind
+declare i8* @llvm.noalias.p0i8(i8*, metadata) #0
+
+attributes #0 = { argmemonly nounwind }
+attributes #1 = { nounwind }
+attributes #2 = { nounwind uwtable }
+
+
+!0 = !{!1}
+!1 = distinct !{!1, !2, !"hello: %a"}
+!2 = distinct !{!2, !"hello"}
+!3 = !{!4}
+!4 = distinct !{!4, !2, !"hello: %c"}
+!5 = !{!1, !4}

test/Analysis/ScopedNoAliasAA/noalias-dup-scope.ll

+; RUN: opt < %s -basicaa -domtree -scoped-noalias -aa-eval -loops -evaluate-aa-metadata -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s -check-prefix=WITHDT
+; Note: The -loops above can be anything that requires the domtree, and is
+; necessary to work around a pass-manager bug.
+
+target datalayout = "E-m:e-i64:64-n32:64"
+target triple = "powerpc64-unknown-linux-gnu"
+
+@a = common global i32* null, align 8
+@r = common global i32 0, align 4
+@a2 = common global i32* null, align 8
+
+; Function Attrs: nounwind
+define i32* @foo() #0 {
+entry:
+  %0 = load i32*, i32** @a, align 8, !tbaa !1, !noalias !5
+  %1 = tail call i32* @llvm.noalias.p0i32(i32* %0, metadata !5) #0
+  ret i32* %1
+}
+
+; Function Attrs: nounwind
+declare i32* @llvm.noalias.p0i32(i32*, metadata) #0
+
+; Function Attrs: nounwind
+define i32* @foo1(i32 signext %b) #0 {
+entry:
+  %tobool = icmp eq i32 %b, 0
+  br i1 %tobool, label %if.else, label %if.then
+
+if.then:                                          ; preds = %entry
+  %0 = load i32*, i32** @a, align 8, !tbaa !1, !noalias !8
+  %1 = tail call i32* @llvm.noalias.p0i32(i32* %0, metadata !12) #0
+  %2 = load i32, i32* %1, align 4, !tbaa !13, !noalias !8
+  %3 = load i32, i32* @r, align 4, !tbaa !13, !noalias !8
+  %add = add nsw i32 %3, %2
+  store i32 %add, i32* @r, align 4, !tbaa !13, !noalias !8
+  tail call void @ex1(i32* %1) #0, !noalias !8
+  %incdec.ptr = getelementptr inbounds i32, i32* %1, i64 1
+  %4 = tail call i32* @llvm.noalias.p0i32(i32* %incdec.ptr, metadata !12) #0
+  %5 = load i32, i32* @r, align 4, !tbaa !13, !noalias !8
+  store i32 %5, i32* %4, align 4, !tbaa !13, !noalias !8
+  tail call void @ex1(i32* %4) #0, !noalias !8
+  %idx.ext = sext i32 %b to i64
+  %add.ptr = getelementptr inbounds i32, i32* %4, i64 %idx.ext
+  %6 = tail call i32* @llvm.noalias.p0i32(i32* %add.ptr, metadata !12) #0
+  %7 = load i32, i32* @r, align 4, !tbaa !13, !noalias !8
+  store i32 %7, i32* %6, align 4, !tbaa !13, !noalias !8
+  tail call void @ex1(i32* %6) #0, !noalias !8
+  %8 = load i32*, i32** @a2, align 8, !tbaa !1, !noalias !8
+  %9 = tail call i32* @llvm.noalias.p0i32(i32* %8, metadata !15) #0
+  %10 = load i32, i32* @r, align 4, !tbaa !13, !noalias !8
+  store i32 %10, i32* %9, align 4, !tbaa !13, !noalias !8
+  tail call void @ex1(i32* %9) #0, !noalias !8
+  br label %if.end
+
+if.else:                                          ; preds = %entry
+  %11 = load i32*, i32** @a2, align 8, !tbaa !1, !noalias !12
+  %12 = tail call i32* @llvm.noalias.p0i32(i32* %11, metadata !12) #0
+  %13 = load i32, i32* %12, align 4, !tbaa !13, !noalias !12
+  %14 = load i32, i32* @r, align 4, !tbaa !13, !noalias !12
+  %add1 = add nsw i32 %14, %13
+  store i32 %add1, i32* @r, align 4, !tbaa !13, !noalias !12
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  %x.0 = phi i32* [ %6, %if.then ], [ %12, %if.else ]
+  ret i32* %x.0
+}
+
+; WITHDT: NoAlias:   %0 = load i32*, i32** @a, align 8, !tbaa !1, !noalias !5 <->   store i32 %add, i32* @r, align 4, !tbaa !10, !noalias !5
+; WITHDT: NoAlias:   %0 = load i32*, i32** @a, align 8, !tbaa !1, !noalias !5 <->   store i32 %5, i32* %4, align 4, !tbaa !10, !noalias !5
+; WITHDT: NoAlias:   %0 = load i32*, i32** @a, align 8, !tbaa !1, !noalias !5 <->   store i32 %7, i32* %6, align 4, !tbaa !10, !noalias !5
+; WITHDT: NoAlias:   %0 = load i32*, i32** @a, align 8, !tbaa !1, !noalias !5 <->   store i32 %10, i32* %9, align 4, !tbaa !10, !noalias !5
+; WITHDT: NoAlias:   %0 = load i32*, i32** @a, align 8, !tbaa !1, !noalias !5 <->   store i32 %add1, i32* @r, align 4, !tbaa !10, !noalias !9
+; WITHDT: NoAlias:   %2 = load i32, i32* %1, align 4, !tbaa !10, !noalias !5 <->   store i32 %add, i32* @r, align 4, !tbaa !10, !noalias !5
+; WITHDT: NoAlias:   %2 = load i32, i32* %1, align 4, !tbaa !10, !noalias !5 <->   store i32 %5, i32* %4, align 4, !tbaa !10, !noalias !5
+; WITHDT: NoAlias:   %2 = load i32, i32* %1, align 4, !tbaa !10, !noalias !5 <->   store i32 %7, i32* %6, align 4, !tbaa !10, !noalias !5
+; WITHDT: NoAlias:   %2 = load i32, i32* %1, align 4, !tbaa !10, !noalias !5 <->   store i32 %10, i32* %9, align 4, !tbaa !10, !noalias !5
+; WITHDT: NoAlias:   %2 = load i32, i32* %1, align 4, !tbaa !10, !noalias !5 <->   store i32 %add1, i32* @r, align 4, !tbaa !10, !noalias !9
+; WITHDT: MustAlias:   %3 = load i32, i32* @r, align 4, !tbaa !10, !noalias !5 <->   store i32 %add, i32* @r, align 4, !tbaa !10, !noalias !5
+; WITHDT: NoAlias:   %3 = load i32, i32* @r, align 4, !tbaa !10, !noalias !5 <->   store i32 %5, i32* %4, align 4, !tbaa !10, !noalias !5
+; WITHDT: NoAlias:   %3 = load i32, i32* @r, align 4, !tbaa !10, !noalias !5 <->   store i32 %7, i32* %6, align 4, !tbaa !10, !noalias !5
+; WITHDT: NoAlias:   %3 = load i32, i32* @r, align 4, !tbaa !10, !noalias !5 <->   store i32 %10, i32* %9, align 4, !tbaa !10, !noalias !5
+; WITHDT: MustAlias:   %3 = load i32, i32* @r, align 4, !tbaa !10, !noalias !5 <->   store i32 %add1, i32* @r, align 4, !tbaa !10, !noalias !9
+; WITHDT: MustAlias:   %5 = load i32, i32* @r, align 4, !tbaa !10, !noalias !5 <->   store i32 %add, i32* @r, align 4, !tbaa !10, !noalias !5
+; WITHDT: NoAlias:   %5 = load i32, i32* @r, align 4, !tbaa !10, !noalias !5 <->   store i32 %5, i32* %4, align 4, !tbaa !10, !noalias !5
+; WITHDT: NoAlias:   %5 = load i32, i32* @r, align 4, !tbaa !10, !noalias !5 <->   store i32 %7, i32* %6, align 4, !tbaa !10, !noalias !5
+; WITHDT: NoAlias:   %5 = load i32, i32* @r, align 4, !tbaa !10, !noalias !5 <->   store i32 %10, i32* %9, align 4, !tbaa !10, !noalias !5
+; WITHDT: MustAlias:   %5 = load i32, i32* @r, align 4, !tbaa !10, !noalias !5 <->   store i32 %add1, i32* @r, align 4, !tbaa !10, !noalias !9
+; WITHDT: MustAlias:   %7 = load i32, i32* @r, align 4, !tbaa !10, !noalias !5 <->   store i32 %add, i32* @r, align 4, !tbaa !10, !noalias !5
+; WITHDT: NoAlias:   %7 = load i32, i32* @r, align 4, !tbaa !10, !noalias !5 <->   store i32 %5, i32* %4, align 4, !tbaa !10, !noalias !5
+; WITHDT: NoAlias:   %7 = load i32, i32* @r, align 4, !tbaa !10, !noalias !5 <->   store i32 %7, i32* %6, align 4, !tbaa !10, !noalias !5
+; WITHDT: NoAlias:   %7 = load i32, i32* @r, align 4, !tbaa !10, !noalias !5 <->   store i32 %10, i32* %9, align 4, !tbaa !10, !noalias !5
+; WITHDT: MustAlias:   %7 = load i32, i32* @r, align 4, !tbaa !10, !noalias !5 <->   store i32 %add1, i32* @r, align 4, !tbaa !10, !noalias !9
+; WITHDT: NoAlias:   %8 = load i32*, i32** @a2, align 8, !tbaa !1, !noalias !5 <->   store i32 %add, i32* @r, align 4, !tbaa !10, !noalias !5
+; WITHDT: NoAlias:   %8 = load i32*, i32** @a2, align 8, !tbaa !1, !noalias !5 <->   store i32 %5, i32* %4, align 4, !tbaa !10, !noalias !5
+; WITHDT: NoAlias:   %8 = load i32*, i32** @a2, align 8, !tbaa !1, !noalias !5 <->   store i32 %7, i32* %6, align 4, !tbaa !10, !noalias !5
+; WITHDT: NoAlias:   %8 = load i32*, i32** @a2, align 8, !tbaa !1, !noalias !5 <->   store i32 %10, i32* %9, align 4, !tbaa !10, !noalias !5
+; WITHDT: NoAlias:   %8 = load i32*, i32** @a2, align 8, !tbaa !1, !noalias !5 <->   store i32 %add1, i32* @r, align 4, !tbaa !10, !noalias !9
+; WITHDT: MustAlias:   %10 = load i32, i32* @r, align 4, !tbaa !10, !noalias !5 <->   store i32 %add, i32* @r, align 4, !tbaa !10, !noalias !5
+; WITHDT: NoAlias:   %10 = load i32, i32* @r, align 4, !tbaa !10, !noalias !5 <->   store i32 %5, i32* %4, align 4, !tbaa !10, !noalias !5
+; WITHDT: NoAlias:   %10 = load i32, i32* @r, align 4, !tbaa !10, !noalias !5 <->   store i32 %7, i32* %6, align 4, !tbaa !10, !noalias !5
+; WITHDT: NoAlias:   %10 = load i32, i32* @r, align 4, !tbaa !10, !noalias !5 <->   store i32 %10, i32* %9, align 4, !tbaa !10, !noalias !5
+; WITHDT: MustAlias:   %10 = load i32, i32* @r, align 4, !tbaa !10, !noalias !5 <->   store i32 %add1, i32* @r, align 4, !tbaa !10, !noalias !9
+; WITHDT: NoAlias:   %11 = load i32*, i32** @a2, align 8, !tbaa !1, !noalias !9 <->   store i32 %add, i32* @r, align 4, !tbaa !10, !noalias !5
+; WITHDT: NoAlias:   %11 = load i32*, i32** @a2, align 8, !tbaa !1, !noalias !9 <->   store i32 %5, i32* %4, align 4, !tbaa !10, !noalias !5
+; WITHDT: NoAlias:   %11 = load i32*, i32** @a2, align 8, !tbaa !1, !noalias !9 <->   store i32 %7, i32* %6, align 4, !tbaa !10, !noalias !5
+; WITHDT: MayAlias:   %11 = load i32*, i32** @a2, align 8, !tbaa !1, !noalias !9 <->   store i32 %10, i32* %9, align 4, !tbaa !10, !noalias !5
+; WITHDT: NoAlias:   %11 = load i32*, i32** @a2, align 8, !tbaa !1, !noalias !9 <->   store i32 %add1, i32* @r, align 4, !tbaa !10, !noalias !9
+; WITHDT: NoAlias:   %13 = load i32, i32* %12, align 4, !tbaa !10, !noalias !9 <->   store i32 %add, i32* @r, align 4, !tbaa !10, !noalias !5
+; WITHDT: MayAlias:   %13 = load i32, i32* %12, align 4, !tbaa !10, !noalias !9 <->   store i32 %5, i32* %4, align 4, !tbaa !10, !noalias !5
+; WITHDT: MayAlias:   %13 = load i32, i32* %12, align 4, !tbaa !10, !noalias !9 <->   store i32 %7, i32* %6, align 4, !tbaa !10, !noalias !5
+; WITHDT: MayAlias:   %13 = load i32, i32* %12, align 4, !tbaa !10, !noalias !9 <->   store i32 %10, i32* %9, align 4, !tbaa !10, !noalias !5
+; WITHDT: NoAlias:   %13 = load i32, i32* %12, align 4, !tbaa !10, !noalias !9 <->   store i32 %add1, i32* @r, align 4, !tbaa !10, !noalias !9
+; WITHDT: MustAlias:   %14 = load i32, i32* @r, align 4, !tbaa !10, !noalias !9 <->   store i32 %add, i32* @r, align 4, !tbaa !10, !noalias !5
+; WITHDT: NoAlias:   %14 = load i32, i32* @r, align 4, !tbaa !10, !noalias !9 <->   store i32 %5, i32* %4, align 4, !tbaa !10, !noalias !5
+; WITHDT: NoAlias:   %14 = load i32, i32* @r, align 4, !tbaa !10, !noalias !9 <->   store i32 %7, i32* %6, align 4, !tbaa !10, !noalias !5
+; WITHDT: MayAlias:   %14 = load i32, i32* @r, align 4, !tbaa !10, !noalias !9 <->   store i32 %10, i32* %9, align 4, !tbaa !10, !noalias !5
+; WITHDT: MustAlias:   %14 = load i32, i32* @r, align 4, !tbaa !10, !noalias !9 <->   store i32 %add1, i32* @r, align 4, !tbaa !10, !noalias !9
+; WITHDT: NoAlias:   store i32 %5, i32* %4, align 4, !tbaa !10, !noalias !5 <->   store i32 %add, i32* @r, align 4, !tbaa !10, !noalias !5
+; WITHDT: NoAlias:   store i32 %7, i32* %6, align 4, !tbaa !10, !noalias !5 <->   store i32 %add, i32* @r, align 4, !tbaa !10, !noalias !5
+; WITHDT: MayAlias:   store i32 %7, i32* %6, align 4, !tbaa !10, !noalias !5 <->   store i32 %5, i32* %4, align 4, !tbaa !10, !noalias !5
+; WITHDT: NoAlias:   store i32 %10, i32* %9, align 4, !tbaa !10, !noalias !5 <->   store i32 %add, i32* @r, align 4, !tbaa !10, !noalias !5
+; WITHDT: NoAlias:   store i32 %10, i32* %9, align 4, !tbaa !10, !noalias !5 <->   store i32 %5, i32* %4, align 4, !tbaa !10, !noalias !5
+; WITHDT: NoAlias:   store i32 %10, i32* %9, align 4, !tbaa !10, !noalias !5 <->   store i32 %7, i32* %6, align 4, !tbaa !10, !noalias !5
+; WITHDT: MustAlias:   store i32 %add1, i32* @r, align 4, !tbaa !10, !noalias !9 <->   store i32 %add, i32* @r, align 4, !tbaa !10, !noalias !5
+; WITHDT: NoAlias:   store i32 %add1, i32* @r, align 4, !tbaa !10, !noalias !9 <->   store i32 %5, i32* %4, align 4, !tbaa !10, !noalias !5
+; WITHDT: NoAlias:   store i32 %add1, i32* @r, align 4, !tbaa !10, !noalias !9 <->   store i32 %7, i32* %6, align 4, !tbaa !10, !noalias !5
+; WITHDT: MayAlias:   store i32 %add1, i32* @r, align 4, !tbaa !10, !noalias !9 <->   store i32 %10, i32* %9, align 4, !tbaa !10, !noalias !5
+
+declare void @ex1(i32*)
+
+attributes #0 = { nounwind }
+
+!llvm.ident = !{!0}
+
+!0 = !{!"clang"}
+!1 = !{!2, !2, i64 0}
+!2 = !{!"any pointer", !3, i64 0}
+!3 = !{!"omnipotent char", !4, i64 0}
+!4 = !{!"Simple C/C++ TBAA"}
+!5 = !{!6}
+!6 = distinct !{!6, !7, !"foo: x"}
+!7 = distinct !{!7, !"foo"}
+!8 = !{!9, !11}
+!9 = distinct !{!9, !10, !"foo1: x2"}
+!10 = distinct !{!10, !"foo1"}
+!11 = distinct !{!11, !10, !"foo1: x"}
+!12 = !{!11}
+!13 = !{!14, !14, i64 0}
+!14 = !{!"int", !3, i64 0}
+!15 = !{!9}

test/Analysis/ScopedNoAliasAA/noalias.ll

+; RUN: opt < %s -basicaa -scoped-noalias -aa-eval -evaluate-aa-metadata -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Function Attrs: nounwind uwtable
+define void @foo(float* nocapture %a, float* nocapture readonly %c) #0 {
+entry:
+  %0 = call float* @llvm.noalias.p0f32(float* %a, metadata !0) #1
+  %1 = load float, float* %c, align 4, !noalias !0
+  %arrayidx.i = getelementptr inbounds float, float* %0, i64 5
+  store float %1, float* %arrayidx.i, align 4, !noalias !0
+  %2 = load float, float* %c, align 4
+  %arrayidx = getelementptr inbounds float, float* %a, i64 7
+  store float %2, float* %arrayidx, align 4
+  ret void
+}
+
+; CHECK-LABEL: Function: foo:
+; CHECK: NoAlias:   %1 = load float, float* %c, align 4, !noalias !0 <->   store float %1, float* %arrayidx.i, align 4, !noalias !0
+; CHECK: MayAlias:   %1 = load float, float* %c, align 4, !noalias !0 <->   store float %2, float* %arrayidx, align 4
+; CHECK: MayAlias:   %2 = load float, float* %c, align 4 <->   store float %1, float* %arrayidx.i, align 4, !noalias !0
+; CHECK: MayAlias:   %2 = load float, float* %c, align 4 <->   store float %2, float* %arrayidx, align 4
+; CHECK: NoAlias:   store float %2, float* %arrayidx, align 4 <->   store float %1, float* %arrayidx.i, align 4, !noalias !0
+
+
+; Function Attrs: nounwind uwtable
+define void @foo2(float* nocapture %a, float* nocapture %b, float* nocapture readonly %c) #0 {
+entry:
+  %0 = call float* @llvm.noalias.p0f32(float* %a, metadata !3) #1
+  %1 = call float* @llvm.noalias.p0f32(float* %b, metadata !6) #1
+  %2 = load float, float* %c, align 4, !noalias !8
+  %arrayidx.i = getelementptr inbounds float, float* %0, i64 5
+  store float %2, float* %arrayidx.i, align 4, !noalias !8
+  %arrayidx1.i = getelementptr inbounds float, float* %1, i64 8
+  store float %2, float* %arrayidx1.i, align 4, !noalias !8
+  %3 = load float, float* %c, align 4
+  %arrayidx = getelementptr inbounds float, float* %a, i64 7
+  store float %3, float* %arrayidx, align 4
+  ret void
+}
+
+; CHECK-LABEL: Function: foo2:
+; CHECK: NoAlias:   %2 = load float, float* %c, align 4, !noalias !5 <->   store float %2, float* %arrayidx.i, align 4, !noalias !5
+; CHECK: NoAlias:   %2 = load float, float* %c, align 4, !noalias !5 <->   store float %2, float* %arrayidx1.i, align 4, !noalias !5
+; CHECK: MayAlias:   %2 = load float, float* %c, align 4, !noalias !5 <->   store float %3, float* %arrayidx, align 4
+; CHECK: MayAlias:   %3 = load float, float* %c, align 4 <->   store float %2, float* %arrayidx.i, align 4, !noalias !5
+; CHECK: MayAlias:   %3 = load float, float* %c, align 4 <->   store float %2, float* %arrayidx1.i, align 4, !noalias !5
+; CHECK: MayAlias:   %3 = load float, float* %c, align 4 <->   store float %3, float* %arrayidx, align 4
+; CHECK: NoAlias:   store float %2, float* %arrayidx1.i, align 4, !noalias !5 <->   store float %2, float* %arrayidx.i, align 4, !noalias !5
+; CHECK: NoAlias:   store float %3, float* %arrayidx, align 4 <->   store float %2, float* %arrayidx.i, align 4, !noalias !5
+; CHECK: MayAlias:   store float %3, float* %arrayidx, align 4 <->   store float %2, float* %arrayidx1.i, align 4, !noalias !5
+
+; Function Attrs: nounwind
+declare float* @llvm.noalias.p0f32(float*, metadata) #1
+
+attributes #0 = { nounwind uwtable }
+attributes #1 = { nounwind }
+
+!0 = !{!1}
+!1 = distinct !{!1, !2, !"hello: %a"}
+!2 = distinct !{!2, !"hello"}
+!3 = !{!4}
+!4 = distinct !{!4, !5, !"hello2: %a"}
+!5 = distinct !{!5, !"hello2"}
+!6 = !{!7}
+!7 = distinct !{!7, !5, !"hello2: %b"}
+!8 = !{!4, !7}

test/Analysis/ScopedNoAliasAA/noalias2.ll

+; RUN: opt < %s -basicaa -scoped-noalias -aa-eval -evaluate-aa-metadata -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Function Attrs: nounwind uwtable
+define void @foo(float* noalias nocapture %a, float* noalias nocapture readonly %c) #0 {
+entry:
+  %0 = call float* @llvm.noalias.p0f32(float* %a, metadata !0) #1
+  %1 = call float* @llvm.noalias.p0f32(float* %c, metadata !3) #1
+  %2 = load float, float* %1, align 4, !noalias !5
+  %arrayidx.i = getelementptr inbounds float, float* %0, i64 5
+  store float %2, float* %arrayidx.i, align 4, !noalias !5
+  %3 = load float, float* %c, align 4
+  %arrayidx = getelementptr inbounds float, float* %a, i64 7
+  store float %3, float* %arrayidx, align 4
+  ret void
+}
+
+; CHECK-LABEL: Function: foo:
+; CHECK: NoAlias:   %2 = load float, float* %1, align 4, !noalias !5 <->   store float %2, float* %arrayidx.i, align 4, !noalias !5
+; CHECK: NoAlias:   %2 = load float, float* %1, align 4, !noalias !5 <->   store float %3, float* %arrayidx, align 4
+; CHECK: NoAlias:   %3 = load float, float* %c, align 4 <->   store float %2, float* %arrayidx.i, align 4, !noalias !5
+; CHECK: NoAlias:   %3 = load float, float* %c, align 4 <->   store float %3, float* %arrayidx, align 4
+; CHECK: NoAlias:   store float %3, float* %arrayidx, align 4 <->   store float %2, float* %arrayidx.i, align 4, !noalias !5
+
+; Function Attrs: nounwind uwtable
+define void @foo2(float* nocapture %a, float* nocapture %b, float* nocapture readonly %c) #0 {
+entry:
+  %0 = call float* @llvm.noalias.p0f32(float* %a, metadata !6) #1
+  %1 = call float* @llvm.noalias.p0f32(float* %c, metadata !9) #1
+  %2 = call float* @llvm.noalias.p0f32(float* %0, metadata !11) #1, !noalias !14
+  %3 = call float* @llvm.noalias.p0f32(float* %1, metadata !15) #1, !noalias !14
+  %4 = load float, float* %3, align 4, !noalias !17
+  %arrayidx.i.i = getelementptr inbounds float, float* %2, i64 5
+  store float %4, float* %arrayidx.i.i, align 4, !noalias !17
+  %5 = load float, float* %1, align 4, !noalias !14
+  %arrayidx.i = getelementptr inbounds float, float* %0, i64 7
+  store float %5, float* %arrayidx.i, align 4, !noalias !14
+  %6 = call float* @llvm.noalias.p0f32(float* %a, metadata !18) #1
+  %7 = call float* @llvm.noalias.p0f32(float* %b, metadata !21) #1
+  %8 = load float, float* %c, align 4, !noalias !23
+  %arrayidx.i1 = getelementptr inbounds float, float* %6, i64 6
+  store float %8, float* %arrayidx.i1, align 4, !noalias !23
+  %arrayidx1.i = getelementptr inbounds float, float* %7, i64 8
+  store float %8, float* %arrayidx1.i, align 4, !noalias !23
+  %9 = load float, float* %c, align 4
+  %arrayidx = getelementptr inbounds float, float* %a, i64 7
+  store float %9, float* %arrayidx, align 4
+  ret void
+}
+
+; CHECK-LABEL: Function: foo2:
+; CHECK: NoAlias:   %4 = load float, float* %3, align 4, !noalias !11 <->   store float %4, float* %arrayidx.i.i, align 4, !noalias !11
+; CHECK: NoAlias:   %4 = load float, float* %3, align 4, !noalias !11 <->   store float %5, float* %arrayidx.i, align 4, !noalias !8
+; CHECK: MayAlias:   %4 = load float, float* %3, align 4, !noalias !11 <->   store float %8, float* %arrayidx.i1, align 4, !noalias !17
+; CHECK: MayAlias:   %4 = load float, float* %3, align 4, !noalias !11 <->   store float %8, float* %arrayidx1.i, align 4, !noalias !17
+; CHECK: MayAlias:   %4 = load float, float* %3, align 4, !noalias !11 <->   store float %9, float* %arrayidx, align 4
+; CHECK: NoAlias:   %5 = load float, float* %1, align 4, !noalias !8 <->   store float %4, float* %arrayidx.i.i, align 4, !noalias !11
+; CHECK: NoAlias:   %5 = load float, float* %1, align 4, !noalias !8 <->   store float %5, float* %arrayidx.i, align 4, !noalias !8
+; CHECK: MayAlias:   %5 = load float, float* %1, align 4, !noalias !8 <->   store float %8, float* %arrayidx.i1, align 4, !noalias !17
+; CHECK: MayAlias:   %5 = load float, float* %1, align 4, !noalias !8 <->   store float %8, float* %arrayidx1.i, align 4, !noalias !17
+; CHECK: MayAlias:   %5 = load float, float* %1, align 4, !noalias !8 <->   store float %9, float* %arrayidx, align 4
+; CHECK: MayAlias:   %8 = load float, float* %c, align 4, !noalias !17 <->   store float %4, float* %arrayidx.i.i, align 4, !noalias !11
+; CHECK: MayAlias:   %8 = load float, float* %c, align 4, !noalias !17 <->   store float %5, float* %arrayidx.i, align 4, !noalias !8
+; CHECK: NoAlias:   %8 = load float, float* %c, align 4, !noalias !17 <->   store float %8, float* %arrayidx.i1, align 4, !noalias !17
+; CHECK: NoAlias:   %8 = load float, float* %c, align 4, !noalias !17 <->   store float %8, float* %arrayidx1.i, align 4, !noalias !17
+; CHECK: MayAlias:   %8 = load float, float* %c, align 4, !noalias !17 <->   store float %9, float* %arrayidx, align 4
+; CHECK: MayAlias:   %9 = load float, float* %c, align 4 <->   store float %4, float* %arrayidx.i.i, align 4, !noalias !11
+; CHECK: MayAlias:   %9 = load float, float* %c, align 4 <->   store float %5, float* %arrayidx.i, align 4, !noalias !8
+; CHECK: MayAlias:   %9 = load float, float* %c, align 4 <->   store float %8, float* %arrayidx.i1, align 4, !noalias !17
+; CHECK: MayAlias:   %9 = load float, float* %c, align 4 <->   store float %8, float* %arrayidx1.i, align 4, !noalias !17
+; CHECK: MayAlias:   %9 = load float, float* %c, align 4 <->   store float %9, float* %arrayidx, align 4
+; CHECK: NoAlias:   store float %5, float* %arrayidx.i, align 4, !noalias !8 <->   store float %4, float* %arrayidx.i.i, align 4, !noalias !11
+; CHECK: NoAlias:   store float %8, float* %arrayidx.i1, align 4, !noalias !17 <->   store float %4, float* %arrayidx.i.i, align 4, !noalias !11
+; CHECK: NoAlias:   store float %8, float* %arrayidx.i1, align 4, !noalias !17 <->   store float %5, float* %arrayidx.i, align 4, !noalias !8
+; CHECK: MayAlias:   store float %8, float* %arrayidx1.i, align 4, !noalias !17 <->   store float %4, float* %arrayidx.i.i, align 4, !noalias !11
+; CHECK: MayAlias:   store float %8, float* %arrayidx1.i, align 4, !noalias !17 <->   store float %5, float* %arrayidx.i, align 4, !noalias !8
+; CHECK: NoAlias:   store float %8, float* %arrayidx1.i, align 4, !noalias !17 <->   store float %8, float* %arrayidx.i1, align 4, !noalias !17
+; CHECK: NoAlias:   store float %9, float* %arrayidx, align 4 <->   store float %4, float* %arrayidx.i.i, align 4, !noalias !11
+; CHECK: MustAlias:   store float %9, float* %arrayidx, align 4 <->   store float %5, float* %arrayidx.i, align 4, !noalias !8
+; CHECK: NoAlias:   store float %9, float* %arrayidx, align 4 <->   store float %8, float* %arrayidx.i1, align 4, !noalias !17
+; CHECK: MayAlias:   store float %9, float* %arrayidx, align 4 <->   store float %8, float* %arrayidx1.i, align 4, !noalias !17
+
+; Function Attrs: nounwind
+declare float* @llvm.noalias.p0f32(float*, metadata) #1
+
+attributes #0 = { nounwind uwtable }
+attributes #1 = { nounwind }
+
+!0 = !{!1}
+!1 = distinct !{!1, !2, !"hello: %a"}
+!2 = distinct !{!2, !"hello"}
+!3 = !{!4}
+!4 = distinct !{!4, !2, !"hello: %c"}
+!5 = !{!1, !4}
+!6 = !{!7}
+!7 = distinct !{!7, !8, !"foo: %a"}
+!8 = distinct !{!8, !"foo"}
+!9 = !{!10}
+!10 = distinct !{!10, !8, !"foo: %c"}
+!11 = !{!12}
+!12 = distinct !{!12, !13, !"hello: %a"}
+!13 = distinct !{!13, !"hello"}
+!14 = !{!7, !10}
+!15 = !{!16}
+!16 = distinct !{!16, !13, !"hello: %c"}
+!17 = !{!12, !16, !7, !10}
+!18 = !{!19}
+!19 = distinct !{!19, !20, !"hello2: %a"}
+!20 = distinct !{!20, !"hello2"}
+!21 = !{!22}
+!22 = distinct !{!22, !20, !"hello2: %b"}
+!23 = !{!19, !22}