llvm/unittests/Analysis/AliasAnalysisTest.cpp

   1 //===--- AliasAnalysisTest.cpp - Mixed TBAA unit tests --------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/Analysis/AliasAnalysis.h"
  10 #include "llvm/ADT/SetVector.h"
  11 #include "llvm/Analysis/AssumptionCache.h"
  12 #include "llvm/Analysis/BasicAliasAnalysis.h"
  13 #include "llvm/Analysis/TargetLibraryInfo.h"
  14 #include "llvm/AsmParser/Parser.h"
  15 #include "llvm/IR/Constants.h"
  16 #include "llvm/IR/InstIterator.h"
  17 #include "llvm/IR/Instructions.h"
  18 #include "llvm/IR/LLVMContext.h"
  19 #include "llvm/IR/LegacyPassManager.h"
  20 #include "llvm/IR/Module.h"
  21 #include "llvm/InitializePasses.h"
  22 #include "llvm/Support/SourceMgr.h"
  23 #include "gtest/gtest.h"
  24
  25 using namespace llvm;
  26
  27 // Set up some test passes.
  28 namespace llvm {
  29 void initializeAATestPassPass(PassRegistry&);
  30 void initializeTestCustomAAWrapperPassPass(PassRegistry&);
  31 }
  32
  33 namespace {
  34 struct AATestPass : FunctionPass {
  35   static char ID;
  36   AATestPass() : FunctionPass(ID) {
  37     initializeAATestPassPass(*PassRegistry::getPassRegistry());
  38   }
  39
  40   void getAnalysisUsage(AnalysisUsage &AU) const override {
  41     AU.addRequired<AAResultsWrapperPass>();
  42     AU.setPreservesAll();
  43   }
  44
  45   bool runOnFunction(Function &F) override {
  46     AliasAnalysis &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
  47
  48     SetVector<Value *> Pointers;
  49     for (Argument &A : F.args())
  50       if (A.getType()->isPointerTy())
  51         Pointers.insert(&A);
  52     for (Instruction &I : instructions(F))
  53       if (I.getType()->isPointerTy())
  54         Pointers.insert(&I);
  55
  56     for (Value *P1 : Pointers)
  57       for (Value *P2 : Pointers)
  58         (void)AA.alias(P1, LocationSize::beforeOrAfterPointer(), P2,
  59                        LocationSize::beforeOrAfterPointer());
  60
  61     return false;
  62   }
  63 };
  64 }
  65
  66 char AATestPass::ID = 0;
  67 INITIALIZE_PASS_BEGIN(AATestPass, "aa-test-pas", "Alias Analysis Test Pass",
  68                       false, true)
  69 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
  70 INITIALIZE_PASS_END(AATestPass, "aa-test-pass", "Alias Analysis Test Pass",
  71                     false, true)
  72
  73 namespace {
  74 /// A test customizable AA result. It merely accepts a callback to run whenever
  75 /// it receives an alias query. Useful for testing that a particular AA result
  76 /// is reached.
  77 struct TestCustomAAResult : AAResultBase {
  78   std::function<void()> CB;
  79
  80   explicit TestCustomAAResult(std::function<void()> CB)
  81       : AAResultBase(), CB(std::move(CB)) {}
  82   TestCustomAAResult(TestCustomAAResult &&Arg)
  83       : AAResultBase(std::move(Arg)), CB(std::move(Arg.CB)) {}
  84
  85   bool invalidate(Function &, const PreservedAnalyses &) { return false; }
  86
  87   AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB,
  88                     AAQueryInfo &AAQI, const Instruction *) {
  89     CB();
  90     return AliasResult::MayAlias;
  91   }
  92 };
  93 }
  94
  95 namespace {
  96 /// A wrapper pass for the legacy pass manager to use with the above custom AA
  97 /// result.
  98 class TestCustomAAWrapperPass : public ImmutablePass {
  99   std::function<void()> CB;
 100   std::unique_ptr<TestCustomAAResult> Result;
 101
 102 public:
 103   static char ID;
 104
 105   explicit TestCustomAAWrapperPass(
 106       std::function<void()> CB = std::function<void()>())
 107       : ImmutablePass(ID), CB(std::move(CB)) {
 108     initializeTestCustomAAWrapperPassPass(*PassRegistry::getPassRegistry());
 109   }
 110
 111   void getAnalysisUsage(AnalysisUsage &AU) const override {
 112     AU.setPreservesAll();
 113     AU.addRequired<TargetLibraryInfoWrapperPass>();
 114   }
 115
 116   bool doInitialization(Module &M) override {
 117     Result.reset(new TestCustomAAResult(std::move(CB)));
 118     return true;
 119   }
 120
 121   bool doFinalization(Module &M) override {
 122     Result.reset();
 123     return true;
 124   }
 125
 126   TestCustomAAResult &getResult() { return *Result; }
 127   const TestCustomAAResult &getResult() const { return *Result; }
 128 };
 129 }
 130
 131 char TestCustomAAWrapperPass::ID = 0;
 132 INITIALIZE_PASS_BEGIN(TestCustomAAWrapperPass, "test-custom-aa",
 133                 "Test Custom AA Wrapper Pass", false, true)
 134 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
 135 INITIALIZE_PASS_END(TestCustomAAWrapperPass, "test-custom-aa",
 136                 "Test Custom AA Wrapper Pass", false, true)
 137
 138 namespace {
 139
 140 class AliasAnalysisTest : public testing::Test {
 141 protected:
 142   LLVMContext C;
 143   Module M;
 144   TargetLibraryInfoImpl TLII;
 145   TargetLibraryInfo TLI;
 146   std::unique_ptr<AssumptionCache> AC;
 147   std::unique_ptr<BasicAAResult> BAR;
 148   std::unique_ptr<AAResults> AAR;
 149
 150   AliasAnalysisTest() : M("AliasAnalysisTest", C), TLI(TLII) {}
 151
 152   AAResults &getAAResults(Function &F) {
 153     // Reset the Function AA results first to clear out any references.
 154     AAR.reset(new AAResults(TLI));
 155
 156     // Build the various AA results and register them.
 157     AC.reset(new AssumptionCache(F));
 158     BAR.reset(new BasicAAResult(M.getDataLayout(), F, TLI, *AC));
 159     AAR->addAAResult(*BAR);
 160
 161     return *AAR;
 162   }
 163 };
 164
 165 TEST_F(AliasAnalysisTest, getModRefInfo) {
 166   // Setup function.
 167   FunctionType *FTy =
 168       FunctionType::get(Type::getVoidTy(C), std::vector<Type *>(), false);
 169   auto *F = Function::Create(FTy, Function::ExternalLinkage, "f", M);
 170   auto *BB = BasicBlock::Create(C, "entry", F);
 171   auto IntType = Type::getInt32Ty(C);
 172   auto PtrType = PointerType::get(C, 0);
 173   auto *Value = ConstantInt::get(IntType, 42);
 174   auto *Addr = ConstantPointerNull::get(PtrType);
 175   auto Alignment = Align(IntType->getBitWidth() / 8);
 176
 177   auto *Store1 = new StoreInst(Value, Addr, BB);
 178   auto *Load1 = new LoadInst(IntType, Addr, "load", BB);
 179   auto *Add1 = BinaryOperator::CreateAdd(Value, Value, "add", BB);
 180   auto *VAArg1 = new VAArgInst(Addr, PtrType, "vaarg", BB);
 181   auto *CmpXChg1 = new AtomicCmpXchgInst(
 182       Addr, ConstantInt::get(IntType, 0), ConstantInt::get(IntType, 1),
 183       Alignment, AtomicOrdering::Monotonic, AtomicOrdering::Monotonic,
 184       SyncScope::System, BB);
 185   auto *AtomicRMW = new AtomicRMWInst(
 186       AtomicRMWInst::Xchg, Addr, ConstantInt::get(IntType, 1), Alignment,
 187       AtomicOrdering::Monotonic, SyncScope::System, BB);
 188
 189   ReturnInst::Create(C, nullptr, BB);
 190
 191   auto &AA = getAAResults(*F);
 192
 193   // Check basic results
 194   EXPECT_EQ(AA.getModRefInfo(Store1, MemoryLocation()), ModRefInfo::Mod);
 195   EXPECT_EQ(AA.getModRefInfo(Store1, std::nullopt), ModRefInfo::Mod);
 196   EXPECT_EQ(AA.getModRefInfo(Load1, MemoryLocation()), ModRefInfo::Ref);
 197   EXPECT_EQ(AA.getModRefInfo(Load1, std::nullopt), ModRefInfo::Ref);
 198   EXPECT_EQ(AA.getModRefInfo(Add1, MemoryLocation()), ModRefInfo::NoModRef);
 199   EXPECT_EQ(AA.getModRefInfo(Add1, std::nullopt), ModRefInfo::NoModRef);
 200   EXPECT_EQ(AA.getModRefInfo(VAArg1, MemoryLocation()), ModRefInfo::ModRef);
 201   EXPECT_EQ(AA.getModRefInfo(VAArg1, std::nullopt), ModRefInfo::ModRef);
 202   EXPECT_EQ(AA.getModRefInfo(CmpXChg1, MemoryLocation()), ModRefInfo::ModRef);
 203   EXPECT_EQ(AA.getModRefInfo(CmpXChg1, std::nullopt), ModRefInfo::ModRef);
 204   EXPECT_EQ(AA.getModRefInfo(AtomicRMW, MemoryLocation()), ModRefInfo::ModRef);
 205   EXPECT_EQ(AA.getModRefInfo(AtomicRMW, std::nullopt), ModRefInfo::ModRef);
 206 }
 207
 208 static Instruction *getInstructionByName(Function &F, StringRef Name) {
 209   for (auto &I : instructions(F))
 210     if (I.getName() == Name)
 211       return &I;
 212   llvm_unreachable("Expected to find instruction!");
 213 }
 214
 215 TEST_F(AliasAnalysisTest, BatchAAPhiCycles) {
 216   LLVMContext C;
 217   SMDiagnostic Err;
 218   std::unique_ptr<Module> M = parseAssemblyString(R"(
 219     define void @f(i8* noalias %a, i1 %c) {
 220     entry:
 221       br label %loop
 222
 223     loop:
 224       %phi = phi i8* [ null, %entry ], [ %a2, %loop ]
 225       %offset1 = phi i64 [ 0, %entry ], [ %offset2, %loop]
 226       %offset2 = add i64 %offset1, 1
 227       %a1 = getelementptr i8, i8* %a, i64 %offset1
 228       %a2 = getelementptr i8, i8* %a, i64 %offset2
 229       %s1 = select i1 %c, i8* %a1, i8* %phi
 230       %s2 = select i1 %c, i8* %a2, i8* %a1
 231       br label %loop
 232     }
 233   )", Err, C);
 234
 235   Function *F = M->getFunction("f");
 236   Instruction *Phi = getInstructionByName(*F, "phi");
 237   Instruction *A1 = getInstructionByName(*F, "a1");
 238   Instruction *A2 = getInstructionByName(*F, "a2");
 239   Instruction *S1 = getInstructionByName(*F, "s1");
 240   Instruction *S2 = getInstructionByName(*F, "s2");
 241   MemoryLocation PhiLoc(Phi, LocationSize::precise(1));
 242   MemoryLocation A1Loc(A1, LocationSize::precise(1));
 243   MemoryLocation A2Loc(A2, LocationSize::precise(1));
 244   MemoryLocation S1Loc(S1, LocationSize::precise(1));
 245   MemoryLocation S2Loc(S2, LocationSize::precise(1));
 246
 247   auto &AA = getAAResults(*F);
 248   EXPECT_EQ(AliasResult::NoAlias, AA.alias(A1Loc, A2Loc));
 249   EXPECT_EQ(AliasResult::MayAlias, AA.alias(PhiLoc, A1Loc));
 250   EXPECT_EQ(AliasResult::MayAlias, AA.alias(S1Loc, S2Loc));
 251
 252   BatchAAResults BatchAA(AA);
 253   EXPECT_EQ(AliasResult::NoAlias, BatchAA.alias(A1Loc, A2Loc));
 254   EXPECT_EQ(AliasResult::MayAlias, BatchAA.alias(PhiLoc, A1Loc));
 255   EXPECT_EQ(AliasResult::MayAlias, BatchAA.alias(S1Loc, S2Loc));
 256
 257   BatchAAResults BatchAA2(AA);
 258   EXPECT_EQ(AliasResult::NoAlias, BatchAA2.alias(A1Loc, A2Loc));
 259   EXPECT_EQ(AliasResult::MayAlias, BatchAA2.alias(S1Loc, S2Loc));
 260   EXPECT_EQ(AliasResult::MayAlias, BatchAA2.alias(PhiLoc, A1Loc));
 261 }
 262
 263 TEST_F(AliasAnalysisTest, BatchAAPhiAssumption) {
 264   LLVMContext C;
 265   SMDiagnostic Err;
 266   std::unique_ptr<Module> M = parseAssemblyString(R"(
 267     define void @f(i8* %a.base, i8* %b.base, i1 %c) {
 268     entry:
 269       br label %loop
 270
 271     loop:
 272       %a = phi i8* [ %a.next, %loop ], [ %a.base, %entry ]
 273       %b = phi i8* [ %b.next, %loop ], [ %b.base, %entry ]
 274       %a.next = getelementptr i8, i8* %a, i64 1
 275       %b.next = getelementptr i8, i8* %b, i64 1
 276       br label %loop
 277     }
 278   )", Err, C);
 279
 280   Function *F = M->getFunction("f");
 281   Instruction *A = getInstructionByName(*F, "a");
 282   Instruction *B = getInstructionByName(*F, "b");
 283   Instruction *ANext = getInstructionByName(*F, "a.next");
 284   Instruction *BNext = getInstructionByName(*F, "b.next");
 285   MemoryLocation ALoc(A, LocationSize::precise(1));
 286   MemoryLocation BLoc(B, LocationSize::precise(1));
 287   MemoryLocation ANextLoc(ANext, LocationSize::precise(1));
 288   MemoryLocation BNextLoc(BNext, LocationSize::precise(1));
 289
 290   auto &AA = getAAResults(*F);
 291   EXPECT_EQ(AliasResult::MayAlias, AA.alias(ALoc, BLoc));
 292   EXPECT_EQ(AliasResult::MayAlias, AA.alias(ANextLoc, BNextLoc));
 293
 294   BatchAAResults BatchAA(AA);
 295   EXPECT_EQ(AliasResult::MayAlias, BatchAA.alias(ALoc, BLoc));
 296   EXPECT_EQ(AliasResult::MayAlias, BatchAA.alias(ANextLoc, BNextLoc));
 297 }
 298
 299 // Check that two aliased GEPs with non-constant offsets are correctly
 300 // analyzed and their relative offset can be requested from AA.
 301 TEST_F(AliasAnalysisTest, PartialAliasOffset) {
 302   LLVMContext C;
 303   SMDiagnostic Err;
 304   std::unique_ptr<Module> M = parseAssemblyString(R"(
 305     define void @foo(float* %arg, i32 %i) {
 306     bb:
 307       %i2 = zext i32 %i to i64
 308       %i3 = getelementptr inbounds float, float* %arg, i64 %i2
 309       %i4 = bitcast float* %i3 to <2 x float>*
 310       %L1 = load <2 x float>, <2 x float>* %i4, align 16
 311       %i7 = add nuw nsw i32 %i, 1
 312       %i8 = zext i32 %i7 to i64
 313       %i9 = getelementptr inbounds float, float* %arg, i64 %i8
 314       %L2 = load float, float* %i9, align 4
 315       ret void
 316     }
 317   )",
 318                                                   Err, C);
 319
 320   if (!M)
 321     Err.print("PartialAliasOffset", errs());
 322
 323   Function *F = M->getFunction("foo");
 324   const auto Loc1 = MemoryLocation::get(getInstructionByName(*F, "L1"));
 325   const auto Loc2 = MemoryLocation::get(getInstructionByName(*F, "L2"));
 326
 327   auto &AA = getAAResults(*F);
 328
 329   const auto AR = AA.alias(Loc1, Loc2);
 330   EXPECT_EQ(AR, AliasResult::PartialAlias);
 331   EXPECT_EQ(4, AR.getOffset());
 332 }
 333
 334 // Check that swapping the order of parameters to `AA.alias()` changes offset
 335 // sign and that the sign is such that FirstLoc + Offset == SecondLoc.
 336 TEST_F(AliasAnalysisTest, PartialAliasOffsetSign) {
 337   LLVMContext C;
 338   SMDiagnostic Err;
 339   std::unique_ptr<Module> M = parseAssemblyString(R"(
 340     define void @f(i64* %p) {
 341       %L1 = load i64, i64* %p
 342       %p.i8 = bitcast i64* %p to i8*
 343       %q = getelementptr i8,  i8* %p.i8, i32 1
 344       %L2 = load i8, i8* %q
 345       ret void
 346     }
 347   )",
 348                                                   Err, C);
 349
 350   if (!M)
 351     Err.print("PartialAliasOffsetSign", errs());
 352
 353   Function *F = M->getFunction("f");
 354   const auto Loc1 = MemoryLocation::get(getInstructionByName(*F, "L1"));
 355   const auto Loc2 = MemoryLocation::get(getInstructionByName(*F, "L2"));
 356
 357   auto &AA = getAAResults(*F);
 358
 359   auto AR = AA.alias(Loc1, Loc2);
 360   EXPECT_EQ(AR, AliasResult::PartialAlias);
 361   EXPECT_EQ(1, AR.getOffset());
 362
 363   AR = AA.alias(Loc2, Loc1);
 364   EXPECT_EQ(AR, AliasResult::PartialAlias);
 365   EXPECT_EQ(-1, AR.getOffset());
 366 }
 367 class AAPassInfraTest : public testing::Test {
 368 protected:
 369   LLVMContext C;
 370   SMDiagnostic Err;
 371   std::unique_ptr<Module> M;
 372
 373 public:
 374   AAPassInfraTest()
 375       : M(parseAssemblyString("define i32 @f(i32* %x, i32* %y) {\n"
 376                               "entry:\n"
 377                               "  %lx = load i32, i32* %x\n"
 378                               "  %ly = load i32, i32* %y\n"
 379                               "  %sum = add i32 %lx, %ly\n"
 380                               "  ret i32 %sum\n"
 381                               "}\n",
 382                               Err, C)) {
 383     assert(M && "Failed to build the module!");
 384   }
 385 };
 386
 387 TEST_F(AAPassInfraTest, injectExternalAA) {
 388   legacy::PassManager PM;
 389
 390   // Register our custom AA's wrapper pass manually.
 391   bool IsCustomAAQueried = false;
 392   PM.add(new TestCustomAAWrapperPass([&] { IsCustomAAQueried = true; }));
 393
 394   // Now add the external AA wrapper with a lambda which queries for the
 395   // wrapper around our custom AA and adds it to the results.
 396   PM.add(createExternalAAWrapperPass([](Pass &P, Function &, AAResults &AAR) {
 397     if (auto *WrapperPass = P.getAnalysisIfAvailable<TestCustomAAWrapperPass>())
 398       AAR.addAAResult(WrapperPass->getResult());
 399   }));
 400
 401   // And run a pass that will make some alias queries. This will automatically
 402   // trigger the rest of the alias analysis stack to be run. It is analagous to
 403   // building a full pass pipeline with any of the existing pass manager
 404   // builders.
 405   PM.add(new AATestPass());
 406   PM.run(*M);
 407
 408   // Finally, ensure that our custom AA was indeed queried.
 409   EXPECT_TRUE(IsCustomAAQueried);
 410 }
 411
 412 } // end anonymous namspace