[wip][basicaa] look through phis and selects when searching for underlying object

[reames]

Summary

Warning: Code is a mess, not for real review. This is mostly for @nikic to take a look and tell me if I missed something fundamental.

Background:

• DecomposeGEP needed to be in sync with getUnderlyingObject in a very fragile manner. However, I can't find any good reason for this. Simple recursing through the base of the decomposed gep gives us the same number of recursive calls, and it doesn't seem to matter if the underlying object search is ahead of the recursion. All it does is add a small constant amount of additional work per step, at worst.
• We can often find a single underlying object, even after searching through a phi graph. The existing recursive phi handling is one instance of this (but done in the recursive step).
• If we allow the underlying logic search to traverse phi graphs, even with small limits (e.g. 6) we find interesting cases.

@nikic - I'm mostly looking for a sanity check here. This feels "too easy". Have I managed to miss something fundamental here?

[nikic]

DecomposeGEP needed to be in sync with getUnderlyingObject in a very fragile manner. However, I can't find any good reason for this. Simple recursing through the base of the decomposed gep gives us the same number of recursive calls, and it doesn't seem to matter if the underlying object search is ahead of the recursion. All it does is add a small constant amount of additional work per step, at worst.

Yes, I believe this is just a historical leftover. It should be safe to not have these in sync.

What this patch does generally makes sense to me, but unfortunately the compile-time impact is fairly significant: https://llvm-compile-time-tracker.com/compare.php?from=e81d813717b2ef227c5b995057153d2cca027afb&to=5adf4f2dab6c553151b76929726959759e6bd8dd&stat=instructions The impact is somewhat unexpected to me -- the additional checks done here don't look expensive and tightly limited.

llvm/include/llvm/Analysis/BasicAliasAnalysis.h

private:
   bool isValueEqualInPotentialCycles(const Value *V1, const Value *V2);
 
   void GetIndexDifference(SmallVectorImpl<VariableGEPIndex> &Dest,
                           const SmallVectorImpl<VariableGEPIndex> &Src);
 
   AliasResult aliasGEP(const GEPOperator *V1, LocationSize V1Size,
                        const AAMDNodes &V1AAInfo, const Value *V2,
                        LocationSize V2Size, const AAMDNodes &V2AAInfo,
-                       const Value *UnderlyingV1, const Value *UnderlyingV2,
                        AAQueryInfo &AAQI);
 
   AliasResult aliasPHI(const PHINode *PN, LocationSize PNSize,
                        const AAMDNodes &PNAAInfo, const Value *V2,
                        LocationSize V2Size, const AAMDNodes &V2AAInfo,
                        AAQueryInfo &AAQI);
 
   AliasResult aliasSelect(const SelectInst *SI, LocationSize SISize,

llvm/include/llvm/Analysis/ValueTracking.h

constexpr unsigned MaxAnalysisRecursionDepth = 6;
   /// the MaxLookup value is non-zero, it limits the number of instructions to
   /// be stripped off.
   const Value *getUnderlyingObject(const Value *V, unsigned MaxLookup = 6);
   inline Value *getUnderlyingObject(Value *V, unsigned MaxLookup = 6) {
     // Force const to avoid infinite recursion.
     const Value *VConst = V;
     return const_cast<Value *>(getUnderlyingObject(VConst, MaxLookup));
   }
+  const Value *getUnderlyingObject2(const Value *V,
+                                    unsigned MaxLookup = 6);
 
   /// This method is similar to getUnderlyingObject except that it can
   /// look through phi and select instructions and return multiple objects.
   ///
   /// If LoopInfo is passed, loop phis are further analyzed.  If a pointer
   /// accesses different objects in each iteration, we don't look through the
   /// phi node. E.g. consider this loop nest:
   ///

llvm/lib/Analysis/BasicAliasAnalysis.cpp

 STATISTIC(SearchTimes, "Number of times a GEP is decomposed");
 
 /// Cutoff after which to stop analysing a set of phi nodes potentially involved
 /// in a cycle. Because we are analysing 'through' phi nodes, we need to be
 /// careful with value equivalence. We use reachability to make sure a value
 /// cannot be involved in a cycle.
 const unsigned MaxNumPhiBBsValueReachabilityCheck = 20;
 
-// The max limit of the search depth in DecomposeGEPExpression() and
-// getUnderlyingObject(), both functions need to use the same search
-// depth otherwise the algorithm in aliasGEP will assert.
+// The max limit of the search depth in DecomposeGEPExpression() and,
+// separately, limit used for getUnderlyingObject,  We use to require
+// these be the same, but is no longer required for correctness.
 static const unsigned MaxLookupSearchDepth = 6;
 
 bool BasicAAResult::invalidate(Function &Fn, const PreservedAnalyses &PA,
                                FunctionAnalysisManager::Invalidator &Inv) {
   // We don't care if this analysis itself is preserved, it has no state. But
   // we need to check that the analyses it depends on have been. Note that we
   // may be created without handles to some analyses and in that case don't
   // depend on them.

 /// If V is a symbolic pointer expression, decompose it into a base pointer
 /// with a constant offset and a number of scaled symbolic offsets.
 ///
 /// The scaled symbolic offsets (represented by pairs of a Value* and a scale
 /// in the VarIndices vector) are Value*'s that are known to be scaled by the
 /// specified amount, but which may have other unrepresented high bits. As
 /// such, the gep cannot necessarily be reconstructed from its decomposed form.
 ///
-/// This function is capable of analyzing everything that getUnderlyingObject
-/// can look through. To be able to do that getUnderlyingObject and
-/// DecomposeGEPExpression must use the same search depth
-/// (MaxLookupSearchDepth).
 BasicAAResult::DecomposedGEP
 BasicAAResult::DecomposeGEPExpression(const Value *V, const DataLayout &DL,
                                       AssumptionCache *AC, DominatorTree *DT) {
   // Limit recursion depth to limit compile time in crazy cases.
   unsigned MaxLookup = MaxLookupSearchDepth;
   SearchTimes++;
   const Instruction *CxtI = dyn_cast<Instruction>(V);
 

 }
 
 /// Provides a bunch of ad-hoc rules to disambiguate a GEP instruction against
 /// another pointer.
 ///
 /// We know that V1 is a GEP, but we don't know anything about V2.
 /// UnderlyingV1 is getUnderlyingObject(GEP1), UnderlyingV2 is the same for
 /// V2.
 AliasResult BasicAAResult::aliasGEP(
     const GEPOperator *GEP1, LocationSize V1Size, const AAMDNodes &V1AAInfo,
     const Value *V2, LocationSize V2Size, const AAMDNodes &V2AAInfo,
-    const Value *UnderlyingV1, const Value *UnderlyingV2, AAQueryInfo &AAQI) {
+    AAQueryInfo &AAQI) {
   DecomposedGEP DecompGEP1 = DecomposeGEPExpression(GEP1, DL, &AC, DT);
   DecomposedGEP DecompGEP2 = DecomposeGEPExpression(V2, DL, &AC, DT);
 
   // Don't attempt to analyze the decomposed GEP if index scale is not a
   // compile-time constant.
   if (!DecompGEP1.HasCompileTimeConstantScale ||
       !DecompGEP2.HasCompileTimeConstantScale)
     return MayAlias;
 
-  assert(DecompGEP1.Base == UnderlyingV1 && DecompGEP2.Base == UnderlyingV2 &&
-         "DecomposeGEPExpression returned a result different from "
-         "getUnderlyingObject");
-
   // Subtract the GEP2 pointer from the GEP1 pointer to find out their
   // symbolic difference.
   DecompGEP1.Offset -= DecompGEP2.Offset;
   GetIndexDifference(DecompGEP1.VarIndices, DecompGEP2.VarIndices);
 
   // If an inbounds GEP would have to start from an out of bounds address
   // for the two to alias, then we can assume noalias.
   if (*DecompGEP1.InBounds && DecompGEP1.VarIndices.empty() &&
if (isa<GEPOperator>(V2)) {
     if (!V1Size.hasValue() && !V2Size.hasValue())
       return MayAlias;
   }
 
   // For GEPs with identical offsets, we can preserve the size and AAInfo
   // when performing the alias check on the underlying objects.
   if (DecompGEP1.Offset == 0 && DecompGEP1.VarIndices.empty())
     return getBestAAResults().alias(
-        MemoryLocation(UnderlyingV1, V1Size, V1AAInfo),
-        MemoryLocation(UnderlyingV2, V2Size, V2AAInfo), AAQI);
+        MemoryLocation(DecompGEP1.Base, V1Size, V1AAInfo),
+        MemoryLocation(DecompGEP2.Base, V2Size, V2AAInfo), AAQI);
 
   // Do the base pointers alias?
   AliasResult BaseAlias = getBestAAResults().alias(
-      MemoryLocation::getBeforeOrAfter(UnderlyingV1),
-      MemoryLocation::getBeforeOrAfter(UnderlyingV2), AAQI);
+      MemoryLocation::getBeforeOrAfter(DecompGEP1.Base),
+      MemoryLocation::getBeforeOrAfter(DecompGEP2.Base), AAQI);
 
   // If we get a No or May, then return it immediately, no amount of analysis
   // will improve this situation.
   if (BaseAlias != MustAlias) {
     assert(BaseAlias == NoAlias || BaseAlias == MayAlias);
     return BaseAlias;
   }
 
AliasResult BasicAAResult::aliasCheck(const Value *V1, LocationSize V1Size,
   // reach the value.
   if (isValueEqualInPotentialCycles(V1, V2))
     return MustAlias;
 
   if (!V1->getType()->isPointerTy() || !V2->getType()->isPointerTy())
     return NoAlias; // Scalars cannot alias each other
 
   // Figure out what objects these things are pointing to if we can.
-  const Value *O1 = getUnderlyingObject(V1, MaxLookupSearchDepth);
-  const Value *O2 = getUnderlyingObject(V2, MaxLookupSearchDepth);
+  const Value *O1 = getUnderlyingObject2(V1, MaxLookupSearchDepth);
+  const Value *O2 = getUnderlyingObject2(V2, MaxLookupSearchDepth);
 
   // Null values in the default address space don't point to any object, so they
   // don't alias any other pointer.
   if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O1))
     if (!NullPointerIsDefined(&F, CPN->getType()->getAddressSpace()))
       return NoAlias;
   if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O2))
     if (!NullPointerIsDefined(&F, CPN->getType()->getAddressSpace()))

 }
 
 AliasResult BasicAAResult::aliasCheckRecursive(
     const Value *V1, LocationSize V1Size, const AAMDNodes &V1AAInfo,
     const Value *V2, LocationSize V2Size, const AAMDNodes &V2AAInfo,
     AAQueryInfo &AAQI, const Value *O1, const Value *O2) {
   if (const GEPOperator *GV1 = dyn_cast<GEPOperator>(V1)) {
     AliasResult Result =
-        aliasGEP(GV1, V1Size, V1AAInfo, V2, V2Size, V2AAInfo, O1, O2, AAQI);
+        aliasGEP(GV1, V1Size, V1AAInfo, V2, V2Size, V2AAInfo, AAQI);
     if (Result != MayAlias)
       return Result;
   } else if (const GEPOperator *GV2 = dyn_cast<GEPOperator>(V2)) {
     AliasResult Result =
-        aliasGEP(GV2, V2Size, V2AAInfo, V1, V1Size, V1AAInfo, O2, O1, AAQI);
+        aliasGEP(GV2, V2Size, V2AAInfo, V1, V1Size, V1AAInfo, AAQI);
     if (Result != MayAlias)
       return Result;
   }
 
   if (const PHINode *PN = dyn_cast<PHINode>(V1)) {
     AliasResult Result =
         aliasPHI(PN, V1Size, V1AAInfo, V2, V2Size, V2AAInfo, AAQI);
     if (Result != MayAlias)

llvm/lib/Analysis/ValueTracking.cpp

static bool isSameUnderlyingObjectInLoop(const PHINode *PN,
   //       int *p = a[i];
   //       ...
   if (auto *Load = dyn_cast<LoadInst>(PrevValue))
     if (!L->isLoopInvariant(Load->getPointerOperand()))
       return false;
   return true;
 }
 
-const Value *llvm::getUnderlyingObject(const Value *V, unsigned MaxLookup) {
+/// Look back through the graph at most MaxLookup steps, stop at the first
+/// phi or select encountered.  Update MaxLookup with remaining budget.
+const Value *getUnderlyingObjectStep(const Value *V, unsigned &MaxLookup) {
   if (!V->getType()->isPointerTy())
     return V;
-  for (unsigned Count = 0; MaxLookup == 0 || Count < MaxLookup; ++Count) {
+  for ( ; MaxLookup != 0; MaxLookup--) {
     if (auto *GEP = dyn_cast<GEPOperator>(V)) {
       V = GEP->getPointerOperand();
     } else if (Operator::getOpcode(V) == Instruction::BitCast ||
                Operator::getOpcode(V) == Instruction::AddrSpaceCast) {
       V = cast<Operator>(V)->getOperand(0);
       if (!V->getType()->isPointerTy())
         return V;
     } else if (auto *GA = dyn_cast<GlobalAlias>(V)) {
if (auto *GEP = dyn_cast<GEPOperator>(V)) {
 
       return V;
     }
     assert(V->getType()->isPointerTy() && "Unexpected operand type!");
   }
   return V;
 }
 
+const Value *llvm::getUnderlyingObject(const Value *V,
+                                       unsigned MaxLookup) {
+  return getUnderlyingObjectStep(V, MaxLookup);
+}
+
+const Value *llvm::getUnderlyingObject2(const Value *V,
+                                        unsigned MaxLookup) {
+  auto *FirstStep = getUnderlyingObjectStep(V, MaxLookup);
+  if (MaxLookup == 0)
+    return FirstStep;
+
+  const Value *Object = nullptr;
+  SmallPtrSet<const Value *, 4> Visited;
+  SmallVector<const Value *, 4> Worklist;
+  Worklist.push_back(FirstStep);
+  do {
+    const Value *P = Worklist.pop_back_val();
+    P = getUnderlyingObjectStep(P, MaxLookup);
+    if (MaxLookup == 0)
+      // Exhausted budget
+      return FirstStep;
+
+    if (!Visited.insert(P).second)
+      continue;
+
+    if (auto *SI = dyn_cast<SelectInst>(P)) {
+      Worklist.push_back(SI->getTrueValue());
+      Worklist.push_back(SI->getFalseValue());
+      MaxLookup--;
+      continue;
+    }
+
+    if (auto *PN = dyn_cast<PHINode>(P)) {
+      append_range(Worklist, PN->incoming_values());
+      MaxLookup--;
+      continue;
+    }
+
+    if (Object)
+      // Found at least two objects, fallback to conservative result
+      return FirstStep;
+    Object = P;
+  } while (!Worklist.empty());
+  return Object ? Object : FirstStep;
+}
+
 void llvm::getUnderlyingObjects(const Value *V,
                                 SmallVectorImpl<const Value *> &Objects,
                                 LoopInfo *LI, unsigned MaxLookup) {
   SmallPtrSet<const Value *, 4> Visited;
   SmallVector<const Value *, 4> Worklist;
   Worklist.push_back(V);
   do {
     const Value *P = Worklist.pop_back_val();

llvm/test/Analysis/BasicAA/recphi.ll

-; RUN: opt < %s -basic-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s --check-prefixes=CHECK,NO-PHI-VALUES
-; RUN: opt < %s -phi-values -basic-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s --check-prefixes=CHECK,PHI-VALUES
+; RUN: opt < %s -basic-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+; RUN: opt < %s -phi-values -basic-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
 
 ; CHECK-LABEL: Function: simple: 5 pointers, 0 call sites
 ; CHECK:         NoAlias:      float* %src1, float* %src2
 ; CHECK:         NoAlias:      float* %phi, float* %src1
 ; CHECK:         MayAlias:     float* %phi, float* %src2
 ; CHECK:         NoAlias:      float* %next, float* %src1
 ; CHECK:         MayAlias:     float* %next, float* %src2
 ; CHECK:         NoAlias:      float* %next, float* %phi

 
 ; CHECK-LABEL: Function: notmust: 6 pointers, 0 call sites
 ; CHECK:        MustAlias:    [2 x i32]* %tab, i8* %0
 ; CHECK:        PartialAlias: [2 x i32]* %tab, i32* %arrayidx
 ; CHECK:        NoAlias:      i32* %arrayidx, i8* %0
 ; CHECK:        MustAlias:    [2 x i32]* %tab, i32* %arrayidx1
 ; CHECK:        MustAlias:    i32* %arrayidx1, i8* %0
 ; CHECK:        NoAlias:      i32* %arrayidx, i32* %arrayidx1
-; CHECK:        MayAlias:     [2 x i32]* %tab, i32* %p.addr.05.i
+; CHECK:        PartialAlias: [2 x i32]* %tab, i32* %p.addr.05.i
 ; CHECK:        MayAlias:     i32* %p.addr.05.i, i8* %0
 ; CHECK:        MayAlias:     i32* %arrayidx, i32* %p.addr.05.i
 ; CHECK:        MayAlias:     i32* %arrayidx1, i32* %p.addr.05.i
-; CHECK:        MayAlias:     [2 x i32]* %tab, i32* %incdec.ptr.i
+; CHECK:        PartialAlias: [2 x i32]* %tab, i32* %incdec.ptr.i
 ; CHECK:        NoAlias:      i32* %incdec.ptr.i, i8* %0
 ; CHECK:        MayAlias:     i32* %arrayidx, i32* %incdec.ptr.i
 ; CHECK:        NoAlias:      i32* %arrayidx1, i32* %incdec.ptr.i
 ; CHECK:        NoAlias:      i32* %incdec.ptr.i, i32* %p.addr.05.i
 define i32 @notmust() nounwind {
 entry:
   %tab = alloca [2 x i32], align 4
   %0 = bitcast [2 x i32]* %tab to i8*

 
 ; CHECK-LABEL: Function: reverse: 6 pointers, 0 call sites
 ; CHECK:         MustAlias:    [10 x i32]* %tab, i8* %0
 ; CHECK:         MustAlias:    [10 x i32]* %tab, i32* %arrayidx
 ; CHECK:         MustAlias:    i32* %arrayidx, i8* %0
 ; CHECK:         PartialAlias: [10 x i32]* %tab, i32* %arrayidx1
 ; CHECK:         NoAlias:      i32* %arrayidx1, i8* %0
 ; CHECK:         NoAlias:      i32* %arrayidx, i32* %arrayidx1
-; CHECK:         MayAlias:     [10 x i32]* %tab, i32* %p.addr.05.i
+; CHECK:         PartialAlias: [10 x i32]* %tab, i32* %p.addr.05.i
 ; CHECK:         MayAlias:     i32* %p.addr.05.i, i8* %0
 ; CHECK:         MayAlias:     i32* %arrayidx, i32* %p.addr.05.i
 ; CHECK:         MayAlias:     i32* %arrayidx1, i32* %p.addr.05.i
-; CHECK:         MayAlias:     [10 x i32]* %tab, i32* %incdec.ptr.i
+; CHECK:         PartialAlias: [10 x i32]* %tab, i32* %incdec.ptr.i
 ; CHECK:         MayAlias:     i32* %incdec.ptr.i, i8* %0
 ; CHECK:         MayAlias:     i32* %arrayidx, i32* %incdec.ptr.i
 ; CHECK:         MayAlias:     i32* %arrayidx1, i32* %incdec.ptr.i
 ; CHECK:         NoAlias:      i32* %incdec.ptr.i, i32* %p.addr.05.i
 define i32 @reverse() nounwind {
 entry:
   %tab = alloca [10 x i32], align 4
   %0 = bitcast [10 x i32]* %tab to i8*
if.end: ; preds = %f.exit
   ret i32 0
 }
 
 ; CHECK-LABEL: Function: negative: 6 pointers, 1 call sites
 ; CHECK:         NoAlias:      [3 x i16]* %int_arr.10, i16** %argv.6.par
 ; CHECK:         NoAlias:      i16* %_tmp1, i16** %argv.6.par
 ; CHECK:         PartialAlias: [3 x i16]* %int_arr.10, i16* %_tmp1
 ; CHECK:         NoAlias:      i16* %ls1.9.0, i16** %argv.6.par
-; CHECK:         MayAlias:     [3 x i16]* %int_arr.10, i16* %ls1.9.0
+; CHECK:         PartialAlias: [3 x i16]* %int_arr.10, i16* %ls1.9.0
 ; CHECK:         MayAlias:     i16* %_tmp1, i16* %ls1.9.0
 ; CHECK:         NoAlias:      i16* %_tmp7, i16** %argv.6.par
-; CHECK:         MayAlias:     [3 x i16]* %int_arr.10, i16* %_tmp7
+; CHECK:         PartialAlias: [3 x i16]* %int_arr.10, i16* %_tmp7
 ; CHECK:         MayAlias:     i16* %_tmp1, i16* %_tmp7
 ; CHECK:         NoAlias:      i16* %_tmp7, i16* %ls1.9.0
 ; CHECK:         NoAlias:      i16* %_tmp11, i16** %argv.6.par
 ; CHECK:         PartialAlias: [3 x i16]* %int_arr.10, i16* %_tmp11
 ; CHECK:         NoAlias:      i16* %_tmp1, i16* %_tmp11
 ; CHECK:         MayAlias:     i16* %_tmp11, i16* %ls1.9.0
 ; CHECK:         MayAlias:     i16* %_tmp11, i16* %_tmp7
 ; CHECK:         Both ModRef:  Ptr: i16** %argv.6.par  <->  %_tmp16 = call i16 @call(i32 %_tmp13)
exit:
   %result = phi i32* [ %p.next, %loop ]
   ret i32* %result
 }
 
 ; CHECK-LABEL: Function: nested_loop
 ; CHECK: NoAlias:  i8* %a, i8* %p.base
 ; CHECK: NoAlias:  i8* %a, i8* %p.outer
 ; CHECK: NoAlias:  i8* %a, i8* %p.outer.next
-; NO-PHI-VALUES: MayAlias: i8* %a, i8* %p.inner
-; PHI-VALUES: NoAlias: i8* %a, i8* %p.inner
+; CHECK: NoAlias: i8* %a, i8* %p.inner
 ; CHECK: NoAlias:  i8* %a, i8* %p.inner.next
 define void @nested_loop(i1 %c, i1 %c2, i8* noalias %p.base) {
 entry:
   %a = alloca i8
   br label %outer_loop
 
 outer_loop:
   %p.outer = phi i8* [ %p.base, %entry ], [ %p.outer.next, %outer_loop_latch ]
exit:
   ret void
 }
 
 ; Same as the previous test case, but avoiding phi of phi.
 ; CHECK-LABEL: Function: nested_loop2
 ; CHECK: NoAlias:  i8* %a, i8* %p.base
 ; CHECK: NoAlias:  i8* %a, i8* %p.outer
 ; CHECK: NoAlias:  i8* %a, i8* %p.outer.next
-; CHECK: MayAlias: i8* %a, i8* %p.inner
+; CHECK: NoAlias: i8* %a, i8* %p.inner
 ; CHECK: NoAlias:  i8* %a, i8* %p.inner.next
 ; TODO: (a, p.inner) could be NoAlias
 define void @nested_loop2(i1 %c, i1 %c2, i8* noalias %p.base) {
 entry:
   %a = alloca i8
   br label %outer_loop
 
 outer_loop:

 exit:
   ret void
 }
 
 ; CHECK-LABEL: Function: nested_loop3
 ; CHECK: NoAlias: i8* %a, i8* %p.base
 ; CHECK: NoAlias: i8* %a, i8* %p.outer
 ; CHECK: NoAlias: i8* %a, i8* %p.outer.next
-; NO-PHI-VALUES: NoAlias: i8* %a, i8* %p.inner
-; PHI-VALUES: MayAlias: i8* %a, i8* %p.inner
+; CHECK: NoAlias: i8* %a, i8* %p.inner
 ; CHECK: NoAlias: i8* %a, i8* %p.inner.next
 define void @nested_loop3(i1 %c, i1 %c2, i8* noalias %p.base) {
 entry:
   %a = alloca i8
   br label %outer_loop
 
 outer_loop:
   %p.outer = phi i8* [ %p.base, %entry ], [ %p.outer.next, %outer_loop_latch ]

 exit:
   ret void
 }
 
 ; CHECK-LABEL: Function: sibling_loop
 ; CHECK: NoAlias: i8* %a, i8* %p.base
 ; CHECK: NoAlias: i8* %a, i8* %p1
 ; CHECK: NoAlias: i8* %a, i8* %p1.next
-; CHECK: MayAlias:  i8* %a, i8* %p2
+; CHECK: NoAlias: i8* %a, i8* %p2
 ; CHECK: NoAlias: i8* %a, i8* %p2.next
-; TODO: %p2 does not alias %a
 define void @sibling_loop(i1 %c, i1 %c2, i8* noalias %p.base) {
 entry:
   %a = alloca i8
   br label %loop1
 
 loop1:
   %p1 = phi i8* [ %p.base, %entry ], [ %p1.next, %loop1 ]
   %p1.next = getelementptr inbounds i8, i8* %p1, i64 10
   br i1 %c, label %loop1, label %loop2
 
 loop2:
   %p2 = phi i8* [ %p1.next, %loop1 ], [ %p2.next, %loop2 ]
   %p2.next = getelementptr inbounds i8, i8* %p2, i64 1
   br i1 %c2, label %loop2, label %exit
 
 exit:
   ret void
 }
 
 ; CHECK-LABEL: Function: sibling_loop2
 ; CHECK: NoAlias: i8* %a, i8* %p.base
 ; CHECK: NoAlias: i8* %a, i8* %p1
 ; CHECK: NoAlias: i8* %a, i8* %p1.next
-; NO-PHI-VALUES: NoAlias: i8* %a, i8* %p2
-; PHI-VALUES: MayAlias: i8* %a, i8* %p2
+; CHECK: NoAlias: i8* %a, i8* %p2
 ; CHECK: NoAlias: i8* %a, i8* %p2.next
 define void @sibling_loop2(i1 %c, i1 %c2, i8* noalias %p.base) {
 entry:
   %a = alloca i8
   br label %loop1
 
 loop1:
   %p1 = phi i8* [ %p.base, %entry ], [ %p1.next, %loop1 ]

llvm/test/CodeGen/Hexagon/swp-epilog-phi13.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc -march=hexagon -hexagon-initial-cfg-cleanup=0 -pipeliner-experimental-cg=true < %s | FileCheck %s
 
 ; Test epilogue generation when reading loop-carried dependency in stage 1 from
 ; stage 0. Make sure the illegal phi the expender creates gets cleaned up
 ; correctly during peeling
 
-; CHECK: loop0
-; CHECK: [[REG0:r([0-9]+)]] = add(r{{[0-9]+}},#8)
-; CHECK: memw([[REG0]]+#0)
-; CHECK: endloop0
-
 ; Function Attrs: nounwind
 define i32* @f0(i16* nocapture readonly %a0, i32 %a1, i32 %a2, i32 %a3,  i16* %b) #0 {
+; CHECK-LABEL: f0:
+; CHECK:       // %bb.0: // %b0
+; CHECK-NEXT:    {
+; CHECK-NEXT:     r0 = #0
+; CHECK-NEXT:     if (p0) jumpr r31
+; CHECK-NEXT:    }
+; CHECK-NEXT:  .LBB0_1: // %b1
+; CHECK-NEXT:    {
+; CHECK-NEXT:     r3 = asl(r2,#1)
+; CHECK-NEXT:     r7 = add(r1,#-2)
+; CHECK-NEXT:     r2 = #0
+; CHECK-NEXT:     r5 = memh(r4+#0)
+; CHECK-NEXT:    }
+; CHECK-NEXT:    {
+; CHECK-NEXT:     r6 = r5
+; CHECK-NEXT:     r0 = add(r2,#8)
+; CHECK-NEXT:     p0 = cmp.gtu(r1,#1)
+; CHECK-NEXT:     r8 = add(r4,r3)
+; CHECK-NEXT:    }
+; CHECK-NEXT:    {
+; CHECK-NEXT:     r5 = mpy(r5.l,r5.l)
+; CHECK-NEXT:     r6 += mpy(r0.l,r0.l):sat
+; CHECK-NEXT:     memw(r2+#0) = r6.new
+; CHECK-NEXT:    }
+; CHECK-NEXT:    {
+; CHECK-NEXT:     if (!p0) jump:nt .LBB0_5
+; CHECK-NEXT:    }
+; CHECK-NEXT:  // %bb.2: // %b2
+; CHECK-NEXT:    {
+; CHECK-NEXT:     r4 = mpy(r5.l,r5.l)
+; CHECK-NEXT:     p0 = cmp.gtu(r1,#2)
+; CHECK-NEXT:     r1 = add(r2,#8)
+; CHECK-NEXT:     r9 = memh(r8+#0)
+; CHECK-NEXT:    }
+; CHECK-NEXT:    {
+; CHECK-NEXT:     r5 = r9
+; CHECK-NEXT:     r8 = add(r8,r3)
+; CHECK-NEXT:    }
+; CHECK-NEXT:    {
+; CHECK-NEXT:     r5 += mpy(r0.l,r0.l):sat
+; CHECK-NEXT:     memw(r0+#0) = r5.new
+; CHECK-NEXT:    }
+; CHECK-NEXT:    {
+; CHECK-NEXT:     loop0(.LBB0_3,r7)
+; CHECK-NEXT:     r5 = mpy(r9.l,r9.l)
+; CHECK-NEXT:     r7:6 = combine(#0,#0)
+; CHECK-NEXT:    }
+; CHECK-NEXT:    {
+; CHECK-NEXT:     if (!p0) jump:nt .LBB0_4
+; CHECK-NEXT:    }
+; CHECK-NEXT:    .p2align 4
+; CHECK-NEXT:  .Ltmp0: // Block address taken
+; CHECK-NEXT:  .LBB0_3: // %b2
+; CHECK-NEXT:    // =>This Inner Loop Header: Depth=1
+; CHECK-NEXT:    {
+; CHECK-NEXT:     r7 = r2
+; CHECK-NEXT:     r2 = r0
+; CHECK-NEXT:     r0 = r1
+; CHECK-NEXT:     r9 = memh(r8+#0)
+; CHECK-NEXT:    }
+; CHECK-NEXT:    {
+; CHECK-NEXT:     r1 = mpy(r4.l,r4.l)
+; CHECK-NEXT:     r4 = mpy(r5.l,r5.l)
+; CHECK-NEXT:     r6 = r7
+; CHECK-NEXT:     memw(r6+#8) = r1.new
+; CHECK-NEXT:    }
+; CHECK-NEXT:    {
+; CHECK-NEXT:     r5 = mpy(r9.l,r9.l)
+; CHECK-NEXT:     r9 += mpy(r0.l,r0.l):sat
+; CHECK-NEXT:     r1 = add(r2,#8)
+; CHECK-NEXT:     r8 = add(r8,r3)
+; CHECK-NEXT:    }
+; CHECK-NEXT:    {
+; CHECK-NEXT:     nop
+; CHECK-NEXT:     memw(r0+#0) = r9
+; CHECK-NEXT:    } :endloop0
+; CHECK-NEXT:  .LBB0_4: // %b2
+; CHECK-NEXT:    {
+; CHECK-NEXT:     r1 = mpy(r4.l,r4.l)
+; CHECK-NEXT:     r0 = r1
+; CHECK-NEXT:     memw(r7+#8) = r1.new
+; CHECK-NEXT:    }
+; CHECK-NEXT:  .LBB0_5: // %b2
+; CHECK-NEXT:    {
+; CHECK-NEXT:     r1 = mpy(r5.l,r5.l)
+; CHECK-NEXT:    }
+; CHECK-NEXT:    {
+; CHECK-NEXT:     r1 = mpy(r1.l,r1.l)
+; CHECK-NEXT:     jumpr r31
+; CHECK-NEXT:     memw(r2+#8) = r1.new
+; CHECK-NEXT:    }
 b0:
   br i1 undef, label %b1, label %b3
 
 b1:                                               ; preds = %b0
   br label %b2
 
 b2:                                               ; preds = %b2, %b1
   %v1 = phi i16* [ %a0, %b1 ], [ %v2, %b2 ]

llvm/test/Transforms/LoopVectorize/ARM/pointer_iv.ll

for.body:
   %inc = add nuw nsw i32 %i.07, 1
   %exitcond = icmp eq i32 %inc, 10000
   br i1 %exitcond, label %for.cond.cleanup, label %for.body, !llvm.loop !2
 }
 
 define hidden void @mult_ptr_iv(i8* noalias nocapture readonly %x, i8* noalias nocapture %z) {
 ; CHECK-LABEL: @mult_ptr_iv(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[SCEVGEP:%.*]] = getelementptr i8, i8* [[Z:%.*]], i32 3000
-; CHECK-NEXT:    [[SCEVGEP1:%.*]] = getelementptr i8, i8* [[X:%.*]], i32 3000
-; CHECK-NEXT:    [[BOUND0:%.*]] = icmp ugt i8* [[SCEVGEP1]], [[Z]]
-; CHECK-NEXT:    [[BOUND1:%.*]] = icmp ugt i8* [[SCEVGEP]], [[X]]
-; CHECK-NEXT:    [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]
-; CHECK-NEXT:    br i1 [[FOUND_CONFLICT]], label [[FOR_BODY:%.*]], label [[VECTOR_PH:%.*]]
-; CHECK:       vector.ph:
-; CHECK-NEXT:    [[IND_END:%.*]] = getelementptr i8, i8* [[X]], i32 3000
-; CHECK-NEXT:    [[IND_END3:%.*]] = getelementptr i8, i8* [[Z]], i32 3000
 ; CHECK-NEXT:    br label [[VECTOR_BODY:%.*]]
 ; CHECK:       vector.body:
-; CHECK-NEXT:    [[POINTER_PHI:%.*]] = phi i8* [ [[X]], [[VECTOR_PH]] ], [ [[PTR_IND:%.*]], [[VECTOR_BODY]] ]
-; CHECK-NEXT:    [[POINTER_PHI5:%.*]] = phi i8* [ [[Z]], [[VECTOR_PH]] ], [ [[PTR_IND6:%.*]], [[VECTOR_BODY]] ]
-; CHECK-NEXT:    [[INDEX:%.*]] = phi i32 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]
+; CHECK-NEXT:    [[POINTER_PHI:%.*]] = phi i8* [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[PTR_IND:%.*]], [[VECTOR_BODY]] ]
+; CHECK-NEXT:    [[POINTER_PHI4:%.*]] = phi i8* [ [[Z:%.*]], [[ENTRY]] ], [ [[PTR_IND5:%.*]], [[VECTOR_BODY]] ]
+; CHECK-NEXT:    [[INDEX:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]
 ; CHECK-NEXT:    [[TMP0:%.*]] = getelementptr i8, i8* [[POINTER_PHI]], <4 x i32> <i32 0, i32 3, i32 6, i32 9>
-; CHECK-NEXT:    [[TMP1:%.*]] = getelementptr i8, i8* [[POINTER_PHI5]], <4 x i32> <i32 0, i32 3, i32 6, i32 9>
+; CHECK-NEXT:    [[TMP1:%.*]] = getelementptr i8, i8* [[POINTER_PHI4]], <4 x i32> <i32 0, i32 3, i32 6, i32 9>
 ; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds i8, <4 x i8*> [[TMP0]], i32 1
-; CHECK-NEXT:    [[WIDE_MASKED_GATHER:%.*]] = call <4 x i8> @llvm.masked.gather.v4i8.v4p0i8(<4 x i8*> [[TMP0]], i32 1, <4 x i1> <i1 true, i1 true, i1 true, i1 true>, <4 x i8> undef), !alias.scope !26
+; CHECK-NEXT:    [[WIDE_MASKED_GATHER:%.*]] = call <4 x i8> @llvm.masked.gather.v4i8.v4p0i8(<4 x i8*> [[TMP0]], i32 1, <4 x i1> <i1 true, i1 true, i1 true, i1 true>, <4 x i8> undef)
 ; CHECK-NEXT:    [[TMP3:%.*]] = getelementptr inbounds i8, <4 x i8*> [[TMP0]], i32 2
-; CHECK-NEXT:    [[WIDE_MASKED_GATHER7:%.*]] = call <4 x i8> @llvm.masked.gather.v4i8.v4p0i8(<4 x i8*> [[TMP2]], i32 1, <4 x i1> <i1 true, i1 true, i1 true, i1 true>, <4 x i8> undef), !alias.scope !26
-; CHECK-NEXT:    [[WIDE_MASKED_GATHER8:%.*]] = call <4 x i8> @llvm.masked.gather.v4i8.v4p0i8(<4 x i8*> [[TMP3]], i32 1, <4 x i1> <i1 true, i1 true, i1 true, i1 true>, <4 x i8> undef), !alias.scope !26
+; CHECK-NEXT:    [[WIDE_MASKED_GATHER6:%.*]] = call <4 x i8> @llvm.masked.gather.v4i8.v4p0i8(<4 x i8*> [[TMP2]], i32 1, <4 x i1> <i1 true, i1 true, i1 true, i1 true>, <4 x i8> undef)
+; CHECK-NEXT:    [[WIDE_MASKED_GATHER7:%.*]] = call <4 x i8> @llvm.masked.gather.v4i8.v4p0i8(<4 x i8*> [[TMP3]], i32 1, <4 x i1> <i1 true, i1 true, i1 true, i1 true>, <4 x i8> undef)
 ; CHECK-NEXT:    [[TMP4:%.*]] = mul <4 x i8> [[WIDE_MASKED_GATHER]], <i8 10, i8 10, i8 10, i8 10>
-; CHECK-NEXT:    [[TMP5:%.*]] = mul <4 x i8> [[WIDE_MASKED_GATHER]], [[WIDE_MASKED_GATHER7]]
-; CHECK-NEXT:    [[TMP6:%.*]] = mul <4 x i8> [[WIDE_MASKED_GATHER]], [[WIDE_MASKED_GATHER8]]
+; CHECK-NEXT:    [[TMP5:%.*]] = mul <4 x i8> [[WIDE_MASKED_GATHER]], [[WIDE_MASKED_GATHER6]]
+; CHECK-NEXT:    [[TMP6:%.*]] = mul <4 x i8> [[WIDE_MASKED_GATHER]], [[WIDE_MASKED_GATHER7]]
 ; CHECK-NEXT:    [[TMP7:%.*]] = getelementptr inbounds i8, <4 x i8*> [[TMP1]], i32 1
-; CHECK-NEXT:    call void @llvm.masked.scatter.v4i8.v4p0i8(<4 x i8> [[TMP4]], <4 x i8*> [[TMP1]], i32 1, <4 x i1> <i1 true, i1 true, i1 true, i1 true>), !alias.scope !29, !noalias !26
+; CHECK-NEXT:    call void @llvm.masked.scatter.v4i8.v4p0i8(<4 x i8> [[TMP4]], <4 x i8*> [[TMP1]], i32 1, <4 x i1> <i1 true, i1 true, i1 true, i1 true>)
 ; CHECK-NEXT:    [[TMP8:%.*]] = getelementptr inbounds i8, <4 x i8*> [[TMP1]], i32 2
-; CHECK-NEXT:    call void @llvm.masked.scatter.v4i8.v4p0i8(<4 x i8> [[TMP5]], <4 x i8*> [[TMP7]], i32 1, <4 x i1> <i1 true, i1 true, i1 true, i1 true>), !alias.scope !29, !noalias !26
-; CHECK-NEXT:    call void @llvm.masked.scatter.v4i8.v4p0i8(<4 x i8> [[TMP6]], <4 x i8*> [[TMP8]], i32 1, <4 x i1> <i1 true, i1 true, i1 true, i1 true>), !alias.scope !29, !noalias !26
+; CHECK-NEXT:    call void @llvm.masked.scatter.v4i8.v4p0i8(<4 x i8> [[TMP5]], <4 x i8*> [[TMP7]], i32 1, <4 x i1> <i1 true, i1 true, i1 true, i1 true>)
+; CHECK-NEXT:    call void @llvm.masked.scatter.v4i8.v4p0i8(<4 x i8> [[TMP6]], <4 x i8*> [[TMP8]], i32 1, <4 x i1> <i1 true, i1 true, i1 true, i1 true>)
 ; CHECK-NEXT:    [[INDEX_NEXT]] = add i32 [[INDEX]], 4
 ; CHECK-NEXT:    [[TMP9:%.*]] = icmp eq i32 [[INDEX_NEXT]], 1000
 ; CHECK-NEXT:    [[PTR_IND]] = getelementptr i8, i8* [[POINTER_PHI]], i32 12
-; CHECK-NEXT:    [[PTR_IND6]] = getelementptr i8, i8* [[POINTER_PHI5]], i32 12
-; CHECK-NEXT:    br i1 [[TMP9]], label [[END:%.*]], label [[VECTOR_BODY]], [[LOOP31:!llvm.loop !.*]]
-; CHECK:       for.body:
-; CHECK-NEXT:    [[X_ADDR_050:%.*]] = phi i8* [ [[INCDEC_PTR2:%.*]], [[FOR_BODY]] ], [ [[X]], [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[Z_ADDR_049:%.*]] = phi i8* [ [[INCDEC_PTR34:%.*]], [[FOR_BODY]] ], [ [[Z]], [[ENTRY]] ]
-; CHECK-NEXT:    [[I_048:%.*]] = phi i32 [ [[INC:%.*]], [[FOR_BODY]] ], [ 0, [[ENTRY]] ]
-; CHECK-NEXT:    [[INCDEC_PTR:%.*]] = getelementptr inbounds i8, i8* [[X_ADDR_050]], i32 1
-; CHECK-NEXT:    [[TMP10:%.*]] = load i8, i8* [[X_ADDR_050]], align 1
-; CHECK-NEXT:    [[INCDEC_PTR1:%.*]] = getelementptr inbounds i8, i8* [[X_ADDR_050]], i32 2
-; CHECK-NEXT:    [[TMP11:%.*]] = load i8, i8* [[INCDEC_PTR]], align 1
-; CHECK-NEXT:    [[INCDEC_PTR2]] = getelementptr inbounds i8, i8* [[X_ADDR_050]], i32 3
-; CHECK-NEXT:    [[TMP12:%.*]] = load i8, i8* [[INCDEC_PTR1]], align 1
-; CHECK-NEXT:    [[MUL:%.*]] = mul i8 [[TMP10]], 10
-; CHECK-NEXT:    [[MUL1:%.*]] = mul i8 [[TMP10]], [[TMP11]]
-; CHECK-NEXT:    [[MUL2:%.*]] = mul i8 [[TMP10]], [[TMP12]]
-; CHECK-NEXT:    [[INCDEC_PTR32:%.*]] = getelementptr inbounds i8, i8* [[Z_ADDR_049]], i32 1
-; CHECK-NEXT:    store i8 [[MUL]], i8* [[Z_ADDR_049]], align 1
-; CHECK-NEXT:    [[INCDEC_PTR33:%.*]] = getelementptr inbounds i8, i8* [[Z_ADDR_049]], i32 2
-; CHECK-NEXT:    store i8 [[MUL1]], i8* [[INCDEC_PTR32]], align 1
-; CHECK-NEXT:    [[INCDEC_PTR34]] = getelementptr inbounds i8, i8* [[Z_ADDR_049]], i32 3
-; CHECK-NEXT:    store i8 [[MUL2]], i8* [[INCDEC_PTR33]], align 1
-; CHECK-NEXT:    [[INC]] = add nuw i32 [[I_048]], 1
-; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[INC]], 1000
-; CHECK-NEXT:    br i1 [[EXITCOND]], label [[END]], label [[FOR_BODY]], [[LOOP32:!llvm.loop !.*]]
+; CHECK-NEXT:    [[PTR_IND5]] = getelementptr i8, i8* [[POINTER_PHI4]], i32 12
+; CHECK-NEXT:    br i1 [[TMP9]], label [[END:%.*]], label [[VECTOR_BODY]], [[LOOP26:!llvm.loop !.*]]
 ; CHECK:       end:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %for.body
 
 for.body:
   %x.addr.050 = phi i8* [ %incdec.ptr2, %for.body ], [ %x, %entry ]