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