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(X: &A); |
52 | for (Instruction &I : instructions(F)) |
53 | if (I.getType()->isPointerTy()) |
54 | Pointers.insert(X: &I); |
55 | |
56 | for (Value *P1 : Pointers) |
57 | for (Value *P2 : Pointers) |
58 | (void)AA.alias(V1: P1, V1Size: LocationSize::beforeOrAfterPointer(), V2: P2, |
59 | V2Size: 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(p: 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(p: new AAResults(TLI)); |
155 | |
156 | // Build the various AA results and register them. |
157 | AC.reset(p: new AssumptionCache(F)); |
158 | BAR.reset(p: new BasicAAResult(M.getDataLayout(), F, TLI, *AC)); |
159 | AAR->addAAResult(AAResult&: *BAR); |
160 | |
161 | return *AAR; |
162 | } |
163 | }; |
164 | |
165 | TEST_F(AliasAnalysisTest, getModRefInfo) { |
166 | // Setup function. |
167 | FunctionType *FTy = |
168 | FunctionType::get(Result: Type::getVoidTy(C), Params: std::vector<Type *>(), isVarArg: false); |
169 | auto *F = Function::Create(Ty: FTy, Linkage: Function::ExternalLinkage, N: "f" , M); |
170 | auto *BB = BasicBlock::Create(Context&: C, Name: "entry" , Parent: F); |
171 | auto IntType = Type::getInt32Ty(C); |
172 | auto PtrType = PointerType::get(C, AddressSpace: 0); |
173 | auto *Value = ConstantInt::get(Ty: IntType, V: 42); |
174 | auto *Addr = ConstantPointerNull::get(T: 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(V1: Value, V2: Value, Name: "add" , BB); |
180 | auto *VAArg1 = new VAArgInst(Addr, PtrType, "vaarg" , BB); |
181 | auto *CmpXChg1 = new AtomicCmpXchgInst( |
182 | Addr, ConstantInt::get(Ty: IntType, V: 0), ConstantInt::get(Ty: IntType, V: 1), |
183 | Alignment, AtomicOrdering::Monotonic, AtomicOrdering::Monotonic, |
184 | SyncScope::System, BB); |
185 | auto *AtomicRMW = new AtomicRMWInst( |
186 | AtomicRMWInst::Xchg, Addr, ConstantInt::get(Ty: IntType, V: 1), Alignment, |
187 | AtomicOrdering::Monotonic, SyncScope::System, BB); |
188 | |
189 | ReturnInst::Create(C, retVal: nullptr, InsertAtEnd: BB); |
190 | |
191 | auto &AA = getAAResults(F&: *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(AsmString: 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, Context&: C); |
234 | |
235 | Function *F = M->getFunction(Name: "f" ); |
236 | Instruction *Phi = getInstructionByName(F&: *F, Name: "phi" ); |
237 | Instruction *A1 = getInstructionByName(F&: *F, Name: "a1" ); |
238 | Instruction *A2 = getInstructionByName(F&: *F, Name: "a2" ); |
239 | Instruction *S1 = getInstructionByName(F&: *F, Name: "s1" ); |
240 | Instruction *S2 = getInstructionByName(F&: *F, Name: "s2" ); |
241 | MemoryLocation PhiLoc(Phi, LocationSize::precise(Value: 1)); |
242 | MemoryLocation A1Loc(A1, LocationSize::precise(Value: 1)); |
243 | MemoryLocation A2Loc(A2, LocationSize::precise(Value: 1)); |
244 | MemoryLocation S1Loc(S1, LocationSize::precise(Value: 1)); |
245 | MemoryLocation S2Loc(S2, LocationSize::precise(Value: 1)); |
246 | |
247 | auto &AA = getAAResults(F&: *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(AsmString: 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, Context&: C); |
279 | |
280 | Function *F = M->getFunction(Name: "f" ); |
281 | Instruction *A = getInstructionByName(F&: *F, Name: "a" ); |
282 | Instruction *B = getInstructionByName(F&: *F, Name: "b" ); |
283 | Instruction *ANext = getInstructionByName(F&: *F, Name: "a.next" ); |
284 | Instruction *BNext = getInstructionByName(F&: *F, Name: "b.next" ); |
285 | MemoryLocation ALoc(A, LocationSize::precise(Value: 1)); |
286 | MemoryLocation BLoc(B, LocationSize::precise(Value: 1)); |
287 | MemoryLocation ANextLoc(ANext, LocationSize::precise(Value: 1)); |
288 | MemoryLocation BNextLoc(BNext, LocationSize::precise(Value: 1)); |
289 | |
290 | auto &AA = getAAResults(F&: *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(AsmString: 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, Context&: C); |
319 | |
320 | if (!M) |
321 | Err.print(ProgName: "PartialAliasOffset" , S&: errs()); |
322 | |
323 | Function *F = M->getFunction(Name: "foo" ); |
324 | const auto Loc1 = MemoryLocation::get(Inst: getInstructionByName(F&: *F, Name: "L1" )); |
325 | const auto Loc2 = MemoryLocation::get(Inst: getInstructionByName(F&: *F, Name: "L2" )); |
326 | |
327 | auto &AA = getAAResults(F&: *F); |
328 | |
329 | const auto AR = AA.alias(LocA: Loc1, LocB: 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(AsmString: 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, Context&: C); |
349 | |
350 | if (!M) |
351 | Err.print(ProgName: "PartialAliasOffsetSign" , S&: errs()); |
352 | |
353 | Function *F = M->getFunction(Name: "f" ); |
354 | const auto Loc1 = MemoryLocation::get(Inst: getInstructionByName(F&: *F, Name: "L1" )); |
355 | const auto Loc2 = MemoryLocation::get(Inst: getInstructionByName(F&: *F, Name: "L2" )); |
356 | |
357 | auto &AA = getAAResults(F&: *F); |
358 | |
359 | auto AR = AA.alias(LocA: Loc1, LocB: Loc2); |
360 | EXPECT_EQ(AR, AliasResult::PartialAlias); |
361 | EXPECT_EQ(1, AR.getOffset()); |
362 | |
363 | AR = AA.alias(LocA: Loc2, LocB: 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(AsmString: "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, Context&: 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(P: 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(P: createExternalAAWrapperPass(Callback: [](Pass &P, Function &, AAResults &AAR) { |
397 | if (auto *WrapperPass = P.getAnalysisIfAvailable<TestCustomAAWrapperPass>()) |
398 | AAR.addAAResult(AAResult&: 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(P: new AATestPass()); |
406 | PM.run(M&: *M); |
407 | |
408 | // Finally, ensure that our custom AA was indeed queried. |
409 | EXPECT_TRUE(IsCustomAAQueried); |
410 | } |
411 | |
412 | } // end anonymous namspace |
413 | |