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 
51     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 
58   TestAnalyses &setupAnalyses() {
59     assert(F);
60     Analyses.emplace(*this);
61     return *Analyses;
62   }
63 
64 public:
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.
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.
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 
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 
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