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
24using namespace llvm;
25
26// FIXME: This is duplicated between this file and MemorySSATest. Refactor.
27const 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().
32class BasicAATest : public testing::Test {
33protected:
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
67public:
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.
75TEST_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.
110TEST_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
139TEST_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
178TEST_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

source code of llvm/unittests/Analysis/BasicAliasAnalysisTest.cpp