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