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     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 }