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 SimpleAAQueryInfo AAQI;
50
TestAnalysesBasicAATest::TestAnalyses51 TestAnalyses(BasicAATest &Test)
52 : DT(*Test.F), AC(*Test.F), BAA(Test.DL, *Test.F, Test.TLI, AC, &DT),
53 AAQI() {}
54 };
55
56 llvm::Optional<TestAnalyses> Analyses;
57
setupAnalyses()58 TestAnalyses &setupAnalyses() {
59 assert(F);
60 Analyses.emplace(*this);
61 return *Analyses;
62 }
63
64 public:
BasicAATest()65 BasicAATest()
66 : M("BasicAATest", C), B(C), DL(DLString), TLI(TLII), F(nullptr) {
67 C.setOpaquePointers(true);
68 }
69 };
70
71 // Check that a function arg can't trivially alias a global when we're accessing
72 // >sizeof(global) bytes through that arg, unless the access size is just an
73 // upper-bound.
TEST_F(BasicAATest,AliasInstWithObjectOfImpreciseSize)74 TEST_F(BasicAATest, AliasInstWithObjectOfImpreciseSize) {
75 F = Function::Create(FunctionType::get(B.getVoidTy(), {B.getPtrTy()}, false),
76 GlobalValue::ExternalLinkage, "F", &M);
77
78 BasicBlock *Entry(BasicBlock::Create(C, "", F));
79 B.SetInsertPoint(Entry);
80
81 Value *IncomingI32Ptr = F->arg_begin();
82
83 auto *GlobalPtr =
84 cast<GlobalVariable>(M.getOrInsertGlobal("some_global", B.getInt8Ty()));
85
86 // Without sufficiently restricted linkage/an init, some of the object size
87 // checking bits get more conservative.
88 GlobalPtr->setLinkage(GlobalValue::LinkageTypes::InternalLinkage);
89 GlobalPtr->setInitializer(B.getInt8(0));
90
91 auto &AllAnalyses = setupAnalyses();
92 BasicAAResult &BasicAA = AllAnalyses.BAA;
93 AAQueryInfo &AAQI = AllAnalyses.AAQI;
94 ASSERT_EQ(
95 BasicAA.alias(MemoryLocation(IncomingI32Ptr, LocationSize::precise(4)),
96 MemoryLocation(GlobalPtr, LocationSize::precise(1)), AAQI),
97 AliasResult::NoAlias);
98
99 ASSERT_EQ(
100 BasicAA.alias(MemoryLocation(IncomingI32Ptr, LocationSize::upperBound(4)),
101 MemoryLocation(GlobalPtr, LocationSize::precise(1)), AAQI),
102 AliasResult::MayAlias);
103 }
104
105 // Check that we fall back to MayAlias if we see an access of an entire object
106 // that's just an upper-bound.
TEST_F(BasicAATest,AliasInstWithFullObjectOfImpreciseSize)107 TEST_F(BasicAATest, AliasInstWithFullObjectOfImpreciseSize) {
108 F = Function::Create(
109 FunctionType::get(B.getVoidTy(), {B.getInt64Ty()}, false),
110 GlobalValue::ExternalLinkage, "F", &M);
111
112 BasicBlock *Entry(BasicBlock::Create(C, "", F));
113 B.SetInsertPoint(Entry);
114
115 Value *ArbitraryI32 = F->arg_begin();
116 AllocaInst *I8 = B.CreateAlloca(B.getInt8Ty(), B.getInt32(2));
117 auto *I8AtUncertainOffset =
118 cast<GetElementPtrInst>(B.CreateGEP(B.getInt8Ty(), I8, ArbitraryI32));
119
120 auto &AllAnalyses = setupAnalyses();
121 BasicAAResult &BasicAA = AllAnalyses.BAA;
122 AAQueryInfo &AAQI = AllAnalyses.AAQI;
123 ASSERT_EQ(BasicAA.alias(
124 MemoryLocation(I8, LocationSize::precise(2)),
125 MemoryLocation(I8AtUncertainOffset, LocationSize::precise(1)),
126 AAQI),
127 AliasResult::PartialAlias);
128
129 ASSERT_EQ(BasicAA.alias(
130 MemoryLocation(I8, LocationSize::upperBound(2)),
131 MemoryLocation(I8AtUncertainOffset, LocationSize::precise(1)),
132 AAQI),
133 AliasResult::MayAlias);
134 }
135
TEST_F(BasicAATest,PartialAliasOffsetPhi)136 TEST_F(BasicAATest, PartialAliasOffsetPhi) {
137 F = Function::Create(
138 FunctionType::get(B.getVoidTy(), {B.getPtrTy(), B.getInt1Ty()}, false),
139 GlobalValue::ExternalLinkage, "F", &M);
140
141 Value *Ptr = F->arg_begin();
142 Value *I = F->arg_begin() + 1;
143
144 BasicBlock *Entry(BasicBlock::Create(C, "", F));
145 BasicBlock *B1(BasicBlock::Create(C, "", F));
146 BasicBlock *B2(BasicBlock::Create(C, "", F));
147 BasicBlock *End(BasicBlock::Create(C, "", F));
148
149 B.SetInsertPoint(Entry);
150 B.CreateCondBr(I, B1, B2);
151
152 B.SetInsertPoint(B1);
153 auto *Ptr1 =
154 cast<GetElementPtrInst>(B.CreateGEP(B.getInt8Ty(), Ptr, B.getInt32(1)));
155 B.CreateBr(End);
156
157 B.SetInsertPoint(B2);
158 auto *Ptr2 =
159 cast<GetElementPtrInst>(B.CreateGEP(B.getInt8Ty(), Ptr, B.getInt32(1)));
160 B.CreateBr(End);
161
162 B.SetInsertPoint(End);
163 auto *Phi = B.CreatePHI(B.getPtrTy(), 2);
164 Phi->addIncoming(Ptr1, B1);
165 Phi->addIncoming(Ptr2, B2);
166 B.CreateRetVoid();
167
168 auto &AllAnalyses = setupAnalyses();
169 BasicAAResult &BasicAA = AllAnalyses.BAA;
170 AAQueryInfo &AAQI = AllAnalyses.AAQI;
171 AliasResult AR =
172 BasicAA.alias(MemoryLocation(Ptr, LocationSize::precise(2)),
173 MemoryLocation(Phi, LocationSize::precise(1)), AAQI);
174 ASSERT_EQ(AR.getOffset(), 1);
175 }
176
TEST_F(BasicAATest,PartialAliasOffsetSelect)177 TEST_F(BasicAATest, PartialAliasOffsetSelect) {
178 F = Function::Create(
179 FunctionType::get(B.getVoidTy(), {B.getPtrTy(), B.getInt1Ty()}, false),
180 GlobalValue::ExternalLinkage, "F", &M);
181
182 Value *Ptr = F->arg_begin();
183 Value *I = F->arg_begin() + 1;
184
185 BasicBlock *Entry(BasicBlock::Create(C, "", F));
186 B.SetInsertPoint(Entry);
187
188 auto *Ptr1 =
189 cast<GetElementPtrInst>(B.CreateGEP(B.getInt8Ty(), Ptr, B.getInt32(1)));
190 auto *Ptr2 =
191 cast<GetElementPtrInst>(B.CreateGEP(B.getInt8Ty(), Ptr, B.getInt32(1)));
192 auto *Select = B.CreateSelect(I, Ptr1, Ptr2);
193 B.CreateRetVoid();
194
195 auto &AllAnalyses = setupAnalyses();
196 BasicAAResult &BasicAA = AllAnalyses.BAA;
197 AAQueryInfo &AAQI = AllAnalyses.AAQI;
198 AliasResult AR =
199 BasicAA.alias(MemoryLocation(Ptr, LocationSize::precise(2)),
200 MemoryLocation(Select, LocationSize::precise(1)), AAQI);
201 ASSERT_EQ(AR.getOffset(), 1);
202 }
203