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::unknown(), P2, 59 LocationSize::unknown()); 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 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(NoAlias, AA.alias(A1Loc, A2Loc)); 251 EXPECT_EQ(MayAlias, AA.alias(PhiLoc, A1Loc)); 252 EXPECT_EQ(MayAlias, AA.alias(S1Loc, S2Loc)); 253 254 BatchAAResults BatchAA(AA); 255 EXPECT_EQ(NoAlias, BatchAA.alias(A1Loc, A2Loc)); 256 EXPECT_EQ(MayAlias, BatchAA.alias(PhiLoc, A1Loc)); 257 EXPECT_EQ(MayAlias, BatchAA.alias(S1Loc, S2Loc)); 258 259 BatchAAResults BatchAA2(AA); 260 EXPECT_EQ(NoAlias, BatchAA2.alias(A1Loc, A2Loc)); 261 EXPECT_EQ(MayAlias, BatchAA2.alias(S1Loc, S2Loc)); 262 EXPECT_EQ(MayAlias, BatchAA2.alias(PhiLoc, A1Loc)); 263 } 264 265 class AAPassInfraTest : public testing::Test { 266 protected: 267 LLVMContext C; 268 SMDiagnostic Err; 269 std::unique_ptr<Module> M; 270 271 public: 272 AAPassInfraTest() 273 : M(parseAssemblyString("define i32 @f(i32* %x, i32* %y) {\n" 274 "entry:\n" 275 " %lx = load i32, i32* %x\n" 276 " %ly = load i32, i32* %y\n" 277 " %sum = add i32 %lx, %ly\n" 278 " ret i32 %sum\n" 279 "}\n", 280 Err, C)) { 281 assert(M && "Failed to build the module!"); 282 } 283 }; 284 285 TEST_F(AAPassInfraTest, injectExternalAA) { 286 legacy::PassManager PM; 287 288 // Register our custom AA's wrapper pass manually. 289 bool IsCustomAAQueried = false; 290 PM.add(new TestCustomAAWrapperPass([&] { IsCustomAAQueried = true; })); 291 292 // Now add the external AA wrapper with a lambda which queries for the 293 // wrapper around our custom AA and adds it to the results. 294 PM.add(createExternalAAWrapperPass([](Pass &P, Function &, AAResults &AAR) { 295 if (auto *WrapperPass = P.getAnalysisIfAvailable<TestCustomAAWrapperPass>()) 296 AAR.addAAResult(WrapperPass->getResult()); 297 })); 298 299 // And run a pass that will make some alias queries. This will automatically 300 // trigger the rest of the alias analysis stack to be run. It is analagous to 301 // building a full pass pipeline with any of the existing pass manager 302 // builders. 303 PM.add(new AATestPass()); 304 PM.run(*M); 305 306 // Finally, ensure that our custom AA was indeed queried. 307 EXPECT_TRUE(IsCustomAAQueried); 308 } 309 310 } // end anonymous namspace 311