[BasicAA] Always strip single-argument phi nodes

[nikic]

Summary

We can always look through single-argument (LCSSA) phi nodes when performing alias analysis. getUnderlyingObject() already does this, but stripPointerCastsAndInvariantGroups() does not. We still look through these phi nodes with the usual aliasPhi() logic, but sometimes get sub-optimal results due to the restrictions on value equivalence when looking through arbitrary phi nodes. I think it's generally beneficial to keep the underlying object logic and the pointer cast stripping logic in sync, insofar as it is possible.

With this patch we get marginally better results:

aa.NumMayAlias | 5010069 | 5009861
aa.NumMustAlias | 347518 | 347674
aa.NumNoAlias | 27201336 | 27201528
...
licm.NumPromoted | 1293 | 1296

I've renamed the relevant strip method to stripPointerCastsForAliasAnalysis(), as we're past the point where we can explicitly spell out everything that's stripped.

[jdoerfert]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

399

we don't want to look through phi with one input?

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

399

It's okay to drop them (and InstCombine will do so independently). The reason why I changed this to not call stripPointerCastsForAliasAnalysis() is that on an abstract level, it's not obvious that the set of things that are legal to strip here, and legal to strip in alias analysis are always the same. So I wanted to limit this only to the transform described in the comment.

[jdoerfert]

LG

llvm/include/llvm/IR/Value.h

public:
   /// Returns the original uncasted value with the same representation. If this
   /// is called on a non-pointer value, it returns 'this'.
   const Value *stripPointerCastsSameRepresentation() const;
   Value *stripPointerCastsSameRepresentation() {
     return const_cast<Value *>(static_cast<const Value *>(this)
                                    ->stripPointerCastsSameRepresentation());
   }
 
-  /// Strip off pointer casts, all-zero GEPs and invariant group info.
+  /// Strip off pointer casts, all-zero GEPs, single-argument phi nodes and
+  /// invariant group info.
   ///
   /// Returns the original uncasted value.  If this is called on a non-pointer
   /// value, it returns 'this'. This function should be used only in
   /// Alias analysis.
-  const Value *stripPointerCastsAndInvariantGroups() const;
-  Value *stripPointerCastsAndInvariantGroups() {
+  const Value *stripPointerCastsForAliasAnalysis() const;
+  Value *stripPointerCastsForAliasAnalysis() {
     return const_cast<Value *>(static_cast<const Value *>(this)
-                                   ->stripPointerCastsAndInvariantGroups());
+                                   ->stripPointerCastsForAliasAnalysis());
   }
 
   /// 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() {

llvm/lib/Analysis/BasicAliasAnalysis.cpp

AliasResult BasicAAResult::aliasCheck(const Value *V1, LocationSize V1Size,
                                       const AAMDNodes &V2AAInfo,
                                       AAQueryInfo &AAQI) {
   // 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.
-  V1 = V1->stripPointerCastsAndInvariantGroups();
-  V2 = V2->stripPointerCastsAndInvariantGroups();
+  V1 = V1->stripPointerCastsForAliasAnalysis();
+  V2 = V2->stripPointerCastsForAliasAnalysis();
 
   // 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/Analysis/GlobalsModRef.cpp

 /// alias - If one of the pointers is to a global that we are tracking, and the
 /// other is some random pointer, we know there cannot be an alias, because the
 /// address of the global isn't taken.
 AliasResult GlobalsAAResult::alias(const MemoryLocation &LocA,
                                    const MemoryLocation &LocB,
                                    AAQueryInfo &AAQI) {
   // Get the base object these pointers point to.
   const Value *UV1 =
-      getUnderlyingObject(LocA.Ptr->stripPointerCastsAndInvariantGroups());
+      getUnderlyingObject(LocA.Ptr->stripPointerCastsForAliasAnalysis());
   const Value *UV2 =
-      getUnderlyingObject(LocB.Ptr->stripPointerCastsAndInvariantGroups());
+      getUnderlyingObject(LocB.Ptr->stripPointerCastsForAliasAnalysis());
 
   // If either of the underlying values is a global, they may be non-addr-taken
   // globals, which we can answer queries about.
   const GlobalValue *GV1 = dyn_cast<GlobalValue>(UV1);
   const GlobalValue *GV2 = dyn_cast<GlobalValue>(UV2);
   if (GV1 || GV2) {
     // If the global's address is taken, pretend we don't know it's a pointer to
     // the global.

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_ForAliasAnalysis,
   PSK_InBoundsConstantIndices,
   PSK_InBounds
 };
 
 template <PointerStripKind StripKind> static void NoopCallback(const Value *) {}
 
 template <PointerStripKind StripKind>
 static const Value *stripPointerCastsAndOffsets(
static const Value *stripPointerCastsAndOffsets(
   Visited.insert(V);
   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_ForAliasAnalysis:
         if (!GEP->hasAllZeroIndices())
           return V;
         break;
       case PSK_InBoundsConstantIndices:
         if (!GEP->hasAllConstantIndices())
           return V;
         LLVM_FALLTHROUGH;
       case PSK_InBounds:
         if (!GEP->isInBounds())
           return V;
         break;
       }
       V = GEP->getPointerOperand();
     } else if (Operator::getOpcode(V) == Instruction::BitCast) {
       V = cast<Operator>(V)->getOperand(0);
       if (!V->getType()->isPointerTy())
         return V;
     } else if (StripKind != PSK_ZeroIndicesSameRepresentation &&
                Operator::getOpcode(V) == Instruction::AddrSpaceCast) {
       // TODO: If we know an address space cast will not change the
       //       representation we could look through it here as well.
       V = cast<Operator>(V)->getOperand(0);
     } else if (StripKind == PSK_ZeroIndicesAndAliases && isa<GlobalAlias>(V)) {
       V = cast<GlobalAlias>(V)->getAliasee();
+    } else if (StripKind == PSK_ForAliasAnalysis && isa<PHINode>(V) &&
+               cast<PHINode>(V)->getNumIncomingValues() == 1) {
+      V = cast<PHINode>(V)->getIncomingValue(0);
     } else {
       if (const auto *Call = dyn_cast<CallBase>(V)) {
         if (const Value *RV = Call->getReturnedArgOperand()) {
           V = RV;
           continue;
         }
         // The result of launder.invariant.group must alias it's argument,
         // but it can't be marked with returned attribute, that's why it needs
         // special case.
-        if (StripKind == PSK_ZeroIndicesAndInvariantGroups &&
+        if (StripKind == PSK_ForAliasAnalysis &&
             (Call->getIntrinsicID() == Intrinsic::launder_invariant_group ||
              Call->getIntrinsicID() == Intrinsic::strip_invariant_group)) {
           V = Call->getArgOperand(0);
           continue;
         }
       }
       return V;
     }

 const Value *Value::stripPointerCastsSameRepresentation() const {
   return stripPointerCastsAndOffsets<PSK_ZeroIndicesSameRepresentation>(this);
 }
 
 const Value *Value::stripInBoundsConstantOffsets() const {
   return stripPointerCastsAndOffsets<PSK_InBoundsConstantIndices>(this);
 }
 
-const Value *Value::stripPointerCastsAndInvariantGroups() const {
-  return stripPointerCastsAndOffsets<PSK_ZeroIndicesAndInvariantGroups>(this);
+const Value *Value::stripPointerCastsForAliasAnalysis() const {
+  return stripPointerCastsAndOffsets<PSK_ForAliasAnalysis>(this);
 }
 
 const Value *Value::stripAndAccumulateConstantOffsets(
     const DataLayout &DL, APInt &Offset, bool AllowNonInbounds,
     function_ref<bool(Value &, APInt &)> ExternalAnalysis) const {
   if (!getType()->isPtrOrPtrVectorTy())
     return this;
 

llvm/lib/Target/AMDGPU/AMDGPUAliasAnalysis.cpp

AliasResult AMDGPUAAResult::alias(const MemoryLocation &LocA,
   // Canonicalize the location order to simplify the following alias check.
   if (asA != AMDGPUAS::FLAT_ADDRESS) {
     std::swap(asA, asB);
     std::swap(A, B);
   }
   if (asA == AMDGPUAS::FLAT_ADDRESS &&
       (asB == AMDGPUAS::LOCAL_ADDRESS || asB == AMDGPUAS::PRIVATE_ADDRESS)) {
     const auto *ObjA =
-        getUnderlyingObject(A.Ptr->stripPointerCastsAndInvariantGroups());
+        getUnderlyingObject(A.Ptr->stripPointerCastsForAliasAnalysis());
     if (const LoadInst *LI = dyn_cast<LoadInst>(ObjA)) {
       // If a generic pointer is loaded from the constant address space, it
       // could only be a GLOBAL or CONSTANT one as that address space is soley
       // prepared on the host side, where only GLOBAL or CONSTANT variables are
       // visible. Note that this even holds for regular functions.
       if (LI->getPointerAddressSpace() == AMDGPUAS::CONSTANT_ADDRESS)
         return NoAlias;
     } else if (const Argument *Arg = dyn_cast<Argument>(ObjA)) {

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

 /// strip(strip(%x)) -> strip(%x)             (the result is not the argument)
 /// strip(launder(%x)) -> strip(%x)
 /// This is legal because it preserves the most recent information about
 /// the presence or absence of invariant.group.
 static Instruction *simplifyInvariantGroupIntrinsic(IntrinsicInst &II,
                                                     InstCombinerImpl &IC) {
   auto *Arg = II.getArgOperand(0);
   auto *StrippedArg = Arg->stripPointerCasts();
-  auto *StrippedInvariantGroupsArg = Arg->stripPointerCastsAndInvariantGroups();
+  auto *StrippedInvariantGroupsArg = StrippedArg;
+  while (auto *Intr = dyn_cast<IntrinsicInst>(StrippedInvariantGroupsArg)) {
+    if (Intr->getIntrinsicID() != Intrinsic::launder_invariant_group &&
+        Intr->getIntrinsicID() != Intrinsic::strip_invariant_group)
+      break;
+    StrippedInvariantGroupsArg = Intr->getArgOperand(0)->stripPointerCasts();
+  }
   if (StrippedArg == StrippedInvariantGroupsArg)
     return nullptr; // No launders/strips to remove.
 
   Value *Result = nullptr;
 
   if (II.getIntrinsicID() == Intrinsic::launder_invariant_group)
     Result = IC.Builder.CreateLaunderInvariantGroup(StrippedInvariantGroupsArg);
   else if (II.getIntrinsicID() == Intrinsic::strip_invariant_group)

llvm/test/Analysis/BasicAA/phi-aa.ll

for.body:                                         ; preds = %for.body, %entry
   store i32 0, i32* %phi, align 4
   %notequal = add i32 %idx, 1
   %arrayidx13 = getelementptr inbounds [100 x i32], [100 x i32]* %oa5, i64 0, i32 %notequal
   store i32 0, i32* %arrayidx13, align 4
   br label %for.body
 } 
 
 ; CHECK-LABEL: single_arg_phi
-; CHECK: MayAlias: i32* %ptr, i32* %ptr.next
+; CHECK: NoAlias: i32* %ptr, i32* %ptr.next
+; CHECK: MustAlias: i32* %ptr, i32* %ptr.phi
 ; CHECK: MustAlias: i32* %ptr.next, i32* %ptr.next.phi
-; TODO: The first one could be MustAlias as well.
 define void @single_arg_phi(i32* %ptr.base) {
 entry:
   br label %loop
 
 loop:
   %ptr = phi i32* [ %ptr.base, %entry ], [ %ptr.next, %split ]
   %ptr.next = getelementptr inbounds i32, i32* %ptr, i64 1
   br label %split
 
 split:
   %ptr.phi = phi i32* [ %ptr, %loop ]
   %ptr.next.phi = phi i32* [ %ptr.next, %loop ]
   br label %loop
 }