llvm/unittests/Analysis/BasicAliasAnalysisTest.cpp

   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 };
  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(FunctionType::get(B.getVoidTy(), {B.getPtrTy()}, false),
  77                        GlobalValue::ExternalLinkage, "F", &M);
  78
  79   BasicBlock *Entry(BasicBlock::Create(C, "", F));
  80   B.SetInsertPoint(Entry);
  81
  82   Value *IncomingI32Ptr = F->arg_begin();
  83
  84   auto *GlobalPtr =
  85       cast<GlobalVariable>(M.getOrInsertGlobal("some_global", 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(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       FunctionType::get(B.getVoidTy(), {B.getInt64Ty()}, false),
 113       GlobalValue::ExternalLinkage, "F", &M);
 114
 115   BasicBlock *Entry(BasicBlock::Create(C, "", F));
 116   B.SetInsertPoint(Entry);
 117
 118   Value *ArbitraryI32 = F->arg_begin();
 119   AllocaInst *I8 = B.CreateAlloca(B.getInt8Ty(), B.getInt32(2));
 120   auto *I8AtUncertainOffset =
 121       cast<GetElementPtrInst>(B.CreatePtrAdd(I8, 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       FunctionType::get(B.getVoidTy(), {B.getPtrTy(), B.getInt1Ty()}, false),
 142       GlobalValue::ExternalLinkage, "F", &M);
 143
 144   Value *Ptr = F->arg_begin();
 145   Value *I = F->arg_begin() + 1;
 146
 147   BasicBlock *Entry(BasicBlock::Create(C, "", F));
 148   BasicBlock *B1(BasicBlock::Create(C, "", F));
 149   BasicBlock *B2(BasicBlock::Create(C, "", F));
 150   BasicBlock *End(BasicBlock::Create(C, "", F));
 151
 152   B.SetInsertPoint(Entry);
 153   B.CreateCondBr(I, B1, B2);
 154
 155   B.SetInsertPoint(B1);
 156   auto *Ptr1 = cast<GetElementPtrInst>(B.CreatePtrAdd(Ptr, B.getInt32(1)));
 157   B.CreateBr(End);
 158
 159   B.SetInsertPoint(B2);
 160   auto *Ptr2 = cast<GetElementPtrInst>(B.CreatePtrAdd(Ptr, B.getInt32(1)));
 161   B.CreateBr(End);
 162
 163   B.SetInsertPoint(End);
 164   auto *Phi = B.CreatePHI(B.getPtrTy(), 2);
 165   Phi->addIncoming(Ptr1, B1);
 166   Phi->addIncoming(Ptr2, B2);
 167   B.CreateRetVoid();
 168
 169   auto &AllAnalyses = setupAnalyses();
 170   BasicAAResult &BasicAA = AllAnalyses.BAA;
 171   AAQueryInfo &AAQI = AllAnalyses.AAQI;
 172   AliasResult AR = BasicAA.alias(MemoryLocation(Ptr, LocationSize::precise(2)),
 173                                  MemoryLocation(Phi, LocationSize::precise(1)),
 174                                  AAQI, nullptr);
 175   ASSERT_EQ(AR.getOffset(), 1);
 176 }
 177
 178 TEST_F(BasicAATest, PartialAliasOffsetSelect) {
 179   F = Function::Create(
 180       FunctionType::get(B.getVoidTy(), {B.getPtrTy(), B.getInt1Ty()}, false),
 181       GlobalValue::ExternalLinkage, "F", &M);
 182
 183   Value *Ptr = F->arg_begin();
 184   Value *I = F->arg_begin() + 1;
 185
 186   BasicBlock *Entry(BasicBlock::Create(C, "", F));
 187   B.SetInsertPoint(Entry);
 188
 189   auto *Ptr1 = cast<GetElementPtrInst>(B.CreatePtrAdd(Ptr, B.getInt32(1)));
 190   auto *Ptr2 = cast<GetElementPtrInst>(B.CreatePtrAdd(Ptr, B.getInt32(1)));
 191   auto *Select = B.CreateSelect(I, Ptr1, 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       MemoryLocation(Ptr, LocationSize::precise(2)),
 199       MemoryLocation(Select, LocationSize::precise(1)), AAQI, nullptr);
 200   ASSERT_EQ(AR.getOffset(), 1);
 201 }