[BasicAA] Fix order in which we pass MemoryLocations to alias()

[aeubanks]

Summary

D98718 caused the order of Values/MemoryLocations we pass to alias() to
be significant due to storing the offset in the PartialAlias case. But
some callers weren't audited and were still passing swapped arguments,
causing the returned PartialAlias offset to be negative in some
cases. For example, the newly added unittests would return -1
instead of 1.

Fixes #55343, a miscompile.

[aeubanks]

format

[aeubanks]

looks like this isn't the only time this sort of thing has come up: D115927

[nikic]

LGTM

[arichardson]

llvm/include/llvm/IR/IRBuilder.h

544

Would it be possible to drop the default zero argument for new APIs? Defaulting to AS0 instead of explicitly passing address spaces often causes assertion errors for targets such as AVR or the downstream CHERI-RISC-V and Arm Morello targets.

544

o

[aeubanks]

llvm/include/llvm/IR/IRBuilder.h

544

As somebody unfamiliar with those targets, what would be the right thing to pass in various cases?
And if you're interested in dropping the default argument, I think it would be better to do that all at once for all APIs.

Is it possible to add in-tree testing for the sort of thing you're interested in without upstreaming an entire target?

llvm/include/llvm/IR/IRBuilder.h

Type *getDoubleTy() {
     return Type::getDoubleTy(Context);
   }
 
   /// Fetch the type representing void.
   Type *getVoidTy() {
     return Type::getVoidTy(Context);
   }
 
+  /// Fetch the type representing a pointer.
+  PointerType *getPtrTy(unsigned AddrSpace = 0) {
+    return PointerType::get(Context, AddrSpace);
+  }
+
   /// Fetch the type representing a pointer to an 8-bit integer value.
   PointerType *getInt8PtrTy(unsigned AddrSpace = 0) {
     return Type::getInt8PtrTy(Context, AddrSpace);
   }
 
   /// Fetch the type representing a pointer to an integer value.
   IntegerType *getIntPtrTy(const DataLayout &DL, unsigned AddrSpace = 0) {
     return DL.getIntPtrType(Context, AddrSpace);

llvm/lib/Analysis/BasicAliasAnalysis.cpp

if (SI->getCondition() == SI2->getCondition()) {
       AliasResult ThisAlias = getBestAAResults().alias(
           MemoryLocation(SI->getFalseValue(), SISize),
           MemoryLocation(SI2->getFalseValue(), V2Size), AAQI);
       return MergeAliasResults(ThisAlias, Alias);
     }
 
   // If both arms of the Select node NoAlias or MustAlias V2, then returns
   // NoAlias / MustAlias. Otherwise, returns MayAlias.
-  AliasResult Alias = getBestAAResults().alias(
-      MemoryLocation(V2, V2Size),
-      MemoryLocation(SI->getTrueValue(), SISize), AAQI);
+  AliasResult Alias =
+      getBestAAResults().alias(MemoryLocation(SI->getTrueValue(), SISize),
+                               MemoryLocation(V2, V2Size), AAQI);
   if (Alias == AliasResult::MayAlias)
     return AliasResult::MayAlias;
 
-  AliasResult ThisAlias = getBestAAResults().alias(
-      MemoryLocation(V2, V2Size),
-      MemoryLocation(SI->getFalseValue(), SISize), AAQI);
+  AliasResult ThisAlias =
+      getBestAAResults().alias(MemoryLocation(SI->getFalseValue(), SISize),
+                               MemoryLocation(V2, V2Size), AAQI);
   return MergeAliasResults(ThisAlias, Alias);
 }
 
 /// Provide a bunch of ad-hoc rules to disambiguate a PHI instruction against
 /// another.
 AliasResult BasicAAResult::aliasPHI(const PHINode *PN, LocationSize PNSize,
                                     const Value *V2, LocationSize V2Size,
                                     AAQueryInfo &AAQI) {
AliasResult BasicAAResult::aliasPHI(const PHINode *PN, LocationSize PNSize,
 
   // If we inserted a block into VisitedPhiBBs, alias analysis results that
   // have been cached earlier may no longer be valid. Perform recursive queries
   // with a new AAQueryInfo.
   AAQueryInfo NewAAQI = AAQI.withEmptyCache();
   AAQueryInfo *UseAAQI = BlockInserted ? &NewAAQI : &AAQI;
 
   AliasResult Alias = getBestAAResults().alias(
-      MemoryLocation(V2, V2Size),
-      MemoryLocation(V1Srcs[0], PNSize), *UseAAQI);
+      MemoryLocation(V1Srcs[0], PNSize), MemoryLocation(V2, V2Size), *UseAAQI);
 
   // Early exit if the check of the first PHI source against V2 is MayAlias.
   // Other results are not possible.
   if (Alias == AliasResult::MayAlias)
     return AliasResult::MayAlias;
   // With recursive phis we cannot guarantee that MustAlias/PartialAlias will
   // remain valid to all elements and needs to conservatively return MayAlias.
   if (isRecursive && Alias != AliasResult::NoAlias)
     return AliasResult::MayAlias;
 
   // If all sources of the PHI node NoAlias or MustAlias V2, then returns
   // NoAlias / MustAlias. Otherwise, returns MayAlias.
   for (unsigned i = 1, e = V1Srcs.size(); i != e; ++i) {
     Value *V = V1Srcs[i];
 
     AliasResult ThisAlias = getBestAAResults().alias(
-        MemoryLocation(V2, V2Size), MemoryLocation(V, PNSize), *UseAAQI);
+        MemoryLocation(V, PNSize), MemoryLocation(V2, V2Size), *UseAAQI);
     Alias = MergeAliasResults(ThisAlias, Alias);
     if (Alias == AliasResult::MayAlias)
       break;
   }
 
   return Alias;
 }
 

llvm/unittests/Analysis/BasicAliasAnalysisTest.cpp

protected:
   TestAnalyses &setupAnalyses() {
     assert(F);
     Analyses.emplace(*this);
     return Analyses.getValue();
   }
 
 public:
   BasicAATest()
-      : M("BasicAATest", C), B(C), DL(DLString), TLI(TLII), F(nullptr) {}
+      : M("BasicAATest", C), B(C), DL(DLString), TLI(TLII), F(nullptr) {
+    C.setOpaquePointers(true);
+  }
 };
 
 // Check that a function arg can't trivially alias a global when we're accessing
 // >sizeof(global) bytes through that arg, unless the access size is just an
 // upper-bound.
 TEST_F(BasicAATest, AliasInstWithObjectOfImpreciseSize) {
-  F = Function::Create(
-      FunctionType::get(B.getVoidTy(), {B.getInt32Ty()->getPointerTo()}, false),
+  F = Function::Create(FunctionType::get(B.getVoidTy(), {B.getPtrTy()}, false),
                        GlobalValue::ExternalLinkage, "F", &M);
 
   BasicBlock *Entry(BasicBlock::Create(C, "", F));
   B.SetInsertPoint(Entry);
 
   Value *IncomingI32Ptr = F->arg_begin();
 
   auto *GlobalPtr =
       cast<GlobalVariable>(M.getOrInsertGlobal("some_global", B.getInt8Ty()));
ASSERT_EQ(BasicAA.alias(
             AliasResult::PartialAlias);
 
   ASSERT_EQ(BasicAA.alias(
                 MemoryLocation(I8, LocationSize::upperBound(2)),
                 MemoryLocation(I8AtUncertainOffset, LocationSize::precise(1)),
                 AAQI),
             AliasResult::MayAlias);
 }
+
+TEST_F(BasicAATest, PartialAliasOffsetPhi) {
+  F = Function::Create(
+      FunctionType::get(B.getVoidTy(), {B.getPtrTy(), B.getInt1Ty()}, false),
+      GlobalValue::ExternalLinkage, "F", &M);
+
+  Value *Ptr = F->arg_begin();
+  Value *I = F->arg_begin() + 1;
+
+  BasicBlock *Entry(BasicBlock::Create(C, "", F));
+  BasicBlock *B1(BasicBlock::Create(C, "", F));
+  BasicBlock *B2(BasicBlock::Create(C, "", F));
+  BasicBlock *End(BasicBlock::Create(C, "", F));
+
+  B.SetInsertPoint(Entry);
+  B.CreateCondBr(I, B1, B2);
+
+  B.SetInsertPoint(B1);
+  auto *Ptr1 =
+      cast<GetElementPtrInst>(B.CreateGEP(B.getInt8Ty(), Ptr, B.getInt32(1)));
+  B.CreateBr(End);
+
+  B.SetInsertPoint(B2);
+  auto *Ptr2 =
+      cast<GetElementPtrInst>(B.CreateGEP(B.getInt8Ty(), Ptr, B.getInt32(1)));
+  B.CreateBr(End);
+
+  B.SetInsertPoint(End);
+  auto *Phi = B.CreatePHI(B.getPtrTy(), 2);
+  Phi->addIncoming(Ptr1, B1);
+  Phi->addIncoming(Ptr2, B2);
+  B.CreateRetVoid();
+
+  auto &AllAnalyses = setupAnalyses();
+  BasicAAResult &BasicAA = AllAnalyses.BAA;
+  AAQueryInfo &AAQI = AllAnalyses.AAQI;
+  AliasResult AR =
+      BasicAA.alias(MemoryLocation(Ptr, LocationSize::precise(2)),
+                    MemoryLocation(Phi, LocationSize::precise(1)), AAQI);
+  ASSERT_EQ(AR.getOffset(), 1);
+}
+
+TEST_F(BasicAATest, PartialAliasOffsetSelect) {
+  F = Function::Create(
+      FunctionType::get(B.getVoidTy(), {B.getPtrTy(), B.getInt1Ty()}, false),
+      GlobalValue::ExternalLinkage, "F", &M);
+
+  Value *Ptr = F->arg_begin();
+  Value *I = F->arg_begin() + 1;
+
+  BasicBlock *Entry(BasicBlock::Create(C, "", F));
+  B.SetInsertPoint(Entry);
+
+  auto *Ptr1 =
+      cast<GetElementPtrInst>(B.CreateGEP(B.getInt8Ty(), Ptr, B.getInt32(1)));
+  auto *Ptr2 =
+      cast<GetElementPtrInst>(B.CreateGEP(B.getInt8Ty(), Ptr, B.getInt32(1)));
+  auto *Select = B.CreateSelect(I, Ptr1, Ptr2);
+  B.CreateRetVoid();
+
+  auto &AllAnalyses = setupAnalyses();
+  BasicAAResult &BasicAA = AllAnalyses.BAA;
+  AAQueryInfo &AAQI = AllAnalyses.AAQI;
+  AliasResult AR =
+      BasicAA.alias(MemoryLocation(Ptr, LocationSize::precise(2)),
+                    MemoryLocation(Select, LocationSize::precise(1)), AAQI);
+  ASSERT_EQ(AR.getOffset(), 1);
+}