1 | //===- BasicAliasAnalysisTest.cpp - Unit tests for BasicAA ----------------===// |
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 | // Targeted tests that are hard/convoluted to make happen with just `opt`. |
10 | // |
11 | |
12 | #include "llvm/Analysis/BasicAliasAnalysis.h" |
13 | #include "llvm/Analysis/AliasAnalysis.h" |
14 | #include "llvm/Analysis/AssumptionCache.h" |
15 | #include "llvm/Analysis/TargetLibraryInfo.h" |
16 | #include "llvm/AsmParser/Parser.h" |
17 | #include "llvm/IR/Dominators.h" |
18 | #include "llvm/IR/IRBuilder.h" |
19 | #include "llvm/IR/LLVMContext.h" |
20 | #include "llvm/IR/Module.h" |
21 | #include "llvm/Support/SourceMgr.h" |
22 | #include "gtest/gtest.h" |
23 | |
24 | using namespace llvm; |
25 | |
26 | // FIXME: This is duplicated between this file and MemorySSATest. Refactor. |
27 | const static char DLString[] = "e-i64:64-f80:128-n8:16:32:64-S128" ; |
28 | |
29 | /// There's a lot of common setup between these tests. This fixture helps reduce |
30 | /// that. Tests should mock up a function, store it in F, and then call |
31 | /// setupAnalyses(). |
32 | class BasicAATest : public testing::Test { |
33 | protected: |
34 | // N.B. Many of these members depend on each other (e.g. the Module depends on |
35 | // the Context, etc.). So, order matters here (and in TestAnalyses). |
36 | LLVMContext C; |
37 | Module M; |
38 | IRBuilder<> B; |
39 | DataLayout DL; |
40 | TargetLibraryInfoImpl TLII; |
41 | TargetLibraryInfo TLI; |
42 | Function *F; |
43 | |
44 | // Things that we need to build after the function is created. |
45 | struct TestAnalyses { |
46 | DominatorTree DT; |
47 | AssumptionCache AC; |
48 | BasicAAResult BAA; |
49 | AAResults AAR; |
50 | SimpleAAQueryInfo AAQI; |
51 | |
52 | TestAnalyses(BasicAATest &Test) |
53 | : DT(*Test.F), AC(*Test.F), BAA(Test.DL, *Test.F, Test.TLI, AC, &DT), |
54 | AAR(Test.TLI), AAQI(AAR) { |
55 | AAR.addAAResult(AAResult&: BAA); |
56 | } |
57 | }; |
58 | |
59 | std::optional<TestAnalyses> Analyses; |
60 | |
61 | TestAnalyses &setupAnalyses() { |
62 | assert(F); |
63 | Analyses.emplace(args&: *this); |
64 | return *Analyses; |
65 | } |
66 | |
67 | public: |
68 | BasicAATest() |
69 | : M("BasicAATest" , C), B(C), DL(DLString), TLI(TLII), F(nullptr) {} |
70 | }; |
71 | |
72 | // Check that a function arg can't trivially alias a global when we're accessing |
73 | // >sizeof(global) bytes through that arg, unless the access size is just an |
74 | // upper-bound. |
75 | TEST_F(BasicAATest, AliasInstWithObjectOfImpreciseSize) { |
76 | F = Function::Create(Ty: FunctionType::get(Result: B.getVoidTy(), Params: {B.getPtrTy()}, isVarArg: false), |
77 | Linkage: GlobalValue::ExternalLinkage, N: "F" , M: &M); |
78 | |
79 | BasicBlock *Entry(BasicBlock::Create(Context&: C, Name: "" , Parent: F)); |
80 | B.SetInsertPoint(Entry); |
81 | |
82 | Value *IncomingI32Ptr = F->arg_begin(); |
83 | |
84 | auto *GlobalPtr = |
85 | cast<GlobalVariable>(Val: M.getOrInsertGlobal(Name: "some_global" , Ty: B.getInt8Ty())); |
86 | |
87 | // Without sufficiently restricted linkage/an init, some of the object size |
88 | // checking bits get more conservative. |
89 | GlobalPtr->setLinkage(GlobalValue::LinkageTypes::InternalLinkage); |
90 | GlobalPtr->setInitializer(B.getInt8(C: 0)); |
91 | |
92 | auto &AllAnalyses = setupAnalyses(); |
93 | BasicAAResult &BasicAA = AllAnalyses.BAA; |
94 | AAQueryInfo &AAQI = AllAnalyses.AAQI; |
95 | ASSERT_EQ( |
96 | BasicAA.alias(MemoryLocation(IncomingI32Ptr, LocationSize::precise(4)), |
97 | MemoryLocation(GlobalPtr, LocationSize::precise(1)), AAQI, |
98 | nullptr), |
99 | AliasResult::NoAlias); |
100 | |
101 | ASSERT_EQ( |
102 | BasicAA.alias(MemoryLocation(IncomingI32Ptr, LocationSize::upperBound(4)), |
103 | MemoryLocation(GlobalPtr, LocationSize::precise(1)), AAQI, |
104 | nullptr), |
105 | AliasResult::MayAlias); |
106 | } |
107 | |
108 | // Check that we fall back to MayAlias if we see an access of an entire object |
109 | // that's just an upper-bound. |
110 | TEST_F(BasicAATest, AliasInstWithFullObjectOfImpreciseSize) { |
111 | F = Function::Create( |
112 | Ty: FunctionType::get(Result: B.getVoidTy(), Params: {B.getInt64Ty()}, isVarArg: false), |
113 | Linkage: GlobalValue::ExternalLinkage, N: "F" , M: &M); |
114 | |
115 | BasicBlock *Entry(BasicBlock::Create(Context&: C, Name: "" , Parent: F)); |
116 | B.SetInsertPoint(Entry); |
117 | |
118 | Value *ArbitraryI32 = F->arg_begin(); |
119 | AllocaInst *I8 = B.CreateAlloca(Ty: B.getInt8Ty(), ArraySize: B.getInt32(C: 2)); |
120 | auto *I8AtUncertainOffset = |
121 | cast<GetElementPtrInst>(Val: B.CreatePtrAdd(Ptr: I8, Offset: ArbitraryI32)); |
122 | |
123 | auto &AllAnalyses = setupAnalyses(); |
124 | BasicAAResult &BasicAA = AllAnalyses.BAA; |
125 | AAQueryInfo &AAQI = AllAnalyses.AAQI; |
126 | ASSERT_EQ(BasicAA.alias( |
127 | MemoryLocation(I8, LocationSize::precise(2)), |
128 | MemoryLocation(I8AtUncertainOffset, LocationSize::precise(1)), |
129 | AAQI, nullptr), |
130 | AliasResult::PartialAlias); |
131 | |
132 | ASSERT_EQ(BasicAA.alias( |
133 | MemoryLocation(I8, LocationSize::upperBound(2)), |
134 | MemoryLocation(I8AtUncertainOffset, LocationSize::precise(1)), |
135 | AAQI, nullptr), |
136 | AliasResult::MayAlias); |
137 | } |
138 | |
139 | TEST_F(BasicAATest, PartialAliasOffsetPhi) { |
140 | F = Function::Create( |
141 | Ty: FunctionType::get(Result: B.getVoidTy(), Params: {B.getPtrTy(), B.getInt1Ty()}, isVarArg: false), |
142 | Linkage: GlobalValue::ExternalLinkage, N: "F" , M: &M); |
143 | |
144 | Value *Ptr = F->arg_begin(); |
145 | Value *I = F->arg_begin() + 1; |
146 | |
147 | BasicBlock *Entry(BasicBlock::Create(Context&: C, Name: "" , Parent: F)); |
148 | BasicBlock *B1(BasicBlock::Create(Context&: C, Name: "" , Parent: F)); |
149 | BasicBlock *B2(BasicBlock::Create(Context&: C, Name: "" , Parent: F)); |
150 | BasicBlock *End(BasicBlock::Create(Context&: C, Name: "" , Parent: F)); |
151 | |
152 | B.SetInsertPoint(Entry); |
153 | B.CreateCondBr(Cond: I, True: B1, False: B2); |
154 | |
155 | B.SetInsertPoint(B1); |
156 | auto *Ptr1 = cast<GetElementPtrInst>(Val: B.CreatePtrAdd(Ptr, Offset: B.getInt32(C: 1))); |
157 | B.CreateBr(Dest: End); |
158 | |
159 | B.SetInsertPoint(B2); |
160 | auto *Ptr2 = cast<GetElementPtrInst>(Val: B.CreatePtrAdd(Ptr, Offset: B.getInt32(C: 1))); |
161 | B.CreateBr(Dest: End); |
162 | |
163 | B.SetInsertPoint(End); |
164 | auto *Phi = B.CreatePHI(Ty: B.getPtrTy(), NumReservedValues: 2); |
165 | Phi->addIncoming(V: Ptr1, BB: B1); |
166 | Phi->addIncoming(V: Ptr2, BB: B2); |
167 | B.CreateRetVoid(); |
168 | |
169 | auto &AllAnalyses = setupAnalyses(); |
170 | BasicAAResult &BasicAA = AllAnalyses.BAA; |
171 | AAQueryInfo &AAQI = AllAnalyses.AAQI; |
172 | AliasResult AR = BasicAA.alias(LocA: MemoryLocation(Ptr, LocationSize::precise(Value: 2)), |
173 | LocB: MemoryLocation(Phi, LocationSize::precise(Value: 1)), |
174 | AAQI, CtxI: nullptr); |
175 | ASSERT_EQ(AR.getOffset(), 1); |
176 | } |
177 | |
178 | TEST_F(BasicAATest, PartialAliasOffsetSelect) { |
179 | F = Function::Create( |
180 | Ty: FunctionType::get(Result: B.getVoidTy(), Params: {B.getPtrTy(), B.getInt1Ty()}, isVarArg: false), |
181 | Linkage: GlobalValue::ExternalLinkage, N: "F" , M: &M); |
182 | |
183 | Value *Ptr = F->arg_begin(); |
184 | Value *I = F->arg_begin() + 1; |
185 | |
186 | BasicBlock *Entry(BasicBlock::Create(Context&: C, Name: "" , Parent: F)); |
187 | B.SetInsertPoint(Entry); |
188 | |
189 | auto *Ptr1 = cast<GetElementPtrInst>(Val: B.CreatePtrAdd(Ptr, Offset: B.getInt32(C: 1))); |
190 | auto *Ptr2 = cast<GetElementPtrInst>(Val: B.CreatePtrAdd(Ptr, Offset: B.getInt32(C: 1))); |
191 | auto *Select = B.CreateSelect(C: I, True: Ptr1, False: Ptr2); |
192 | B.CreateRetVoid(); |
193 | |
194 | auto &AllAnalyses = setupAnalyses(); |
195 | BasicAAResult &BasicAA = AllAnalyses.BAA; |
196 | AAQueryInfo &AAQI = AllAnalyses.AAQI; |
197 | AliasResult AR = BasicAA.alias( |
198 | LocA: MemoryLocation(Ptr, LocationSize::precise(Value: 2)), |
199 | LocB: MemoryLocation(Select, LocationSize::precise(Value: 1)), AAQI, CtxI: nullptr); |
200 | ASSERT_EQ(AR.getOffset(), 1); |
201 | } |
202 | |