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 415