llvm/unittests/Analysis/LoadsTest.cpp

   1 //===- LoadsTest.cpp - local load analysis unit tests ---------------------===//
   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 #include "llvm/Analysis/Loads.h"
  10 #include "llvm/Analysis/AssumptionCache.h"
  11 #include "llvm/Analysis/LoopInfo.h"
  12 #include "llvm/Analysis/ScalarEvolution.h"
  13 #include "llvm/Analysis/TargetLibraryInfo.h"
  14 #include "llvm/AsmParser/Parser.h"
  15 #include "llvm/IR/Constants.h"
  16 #include "llvm/IR/Dominators.h"
  17 #include "llvm/IR/Instructions.h"
  18 #include "llvm/IR/LLVMContext.h"
  19 #include "llvm/IR/Module.h"
  20 #include "llvm/Support/SourceMgr.h"
  21 #include "gtest/gtest.h"
  22
  23 using namespace llvm;
  24
  25 static std::unique_ptr<Module> parseIR(LLVMContext &C, const char *IR) {
  26   SMDiagnostic Err;
  27   std::unique_ptr<Module> Mod = parseAssemblyString(IR, Err, C);
  28   if (!Mod)
  29     Err.print("AnalysisTests", errs());
  30   return Mod;
  31 }
  32
  33 TEST(LoadsTest, FindAvailableLoadedValueSameBasePtrConstantOffsetsNullAA) {
  34   LLVMContext C;
  35   std::unique_ptr<Module> M = parseIR(C,
  36                                       R"IR(
  37 target datalayout = "p:64:64:64:32"
  38 %class = type <{ i32, i32 }>
  39
  40 define i32 @f() {
  41 entry:
  42   %o = alloca %class
  43   %f1 = getelementptr inbounds %class, %class* %o, i32 0, i32 0
  44   store i32 42, i32* %f1
  45   %f2 = getelementptr inbounds %class, %class* %o, i32 0, i32 1
  46   store i32 43, i32* %f2
  47   %v = load i32, i32* %f1
  48   ret i32 %v
  49 }
  50 )IR");
  51   auto *GV = M->getNamedValue("f");
  52   ASSERT_TRUE(GV);
  53   auto *F = dyn_cast<Function>(GV);
  54   ASSERT_TRUE(F);
  55   Instruction *Inst = &F->front().front();
  56   auto *AI = dyn_cast<AllocaInst>(Inst);
  57   ASSERT_TRUE(AI);
  58   Inst = &*++F->front().rbegin();
  59   auto *LI = dyn_cast<LoadInst>(Inst);
  60   ASSERT_TRUE(LI);
  61   BasicBlock::iterator BBI(LI);
  62   Value *Loaded = FindAvailableLoadedValue(
  63       LI, LI->getParent(), BBI, 0, nullptr, nullptr);
  64   ASSERT_TRUE(Loaded);
  65   auto *CI = dyn_cast<ConstantInt>(Loaded);
  66   ASSERT_TRUE(CI);
  67   ASSERT_TRUE(CI->equalsInt(42));
  68 }
  69
  70 TEST(LoadsTest, CanReplacePointersIfEqual) {
  71   LLVMContext C;
  72   std::unique_ptr<Module> M = parseIR(C,
  73                                       R"IR(
  74 @y = common global [1 x i32] zeroinitializer, align 4
  75 @x = common global [1 x i32] zeroinitializer, align 4
  76 declare void @use(i32*)
  77
  78 define void @f(i32* %p1, i32* %p2, i64 %i) {
  79   call void @use(i32* getelementptr inbounds ([1 x i32], [1 x i32]* @y, i64 0, i64 0))
  80
  81   %p1_idx = getelementptr inbounds i32, i32* %p1, i64 %i
  82   call void @use(i32* %p1_idx)
  83
  84   %icmp = icmp eq i32* %p1, getelementptr inbounds ([1 x i32], [1 x i32]* @y, i64 0, i64 0)
  85   %ptrInt = ptrtoint i32* %p1 to i64
  86   ret void
  87 }
  88 )IR");
  89   const DataLayout &DL = M->getDataLayout();
  90   auto *GV = M->getNamedValue("f");
  91   ASSERT_TRUE(GV);
  92   auto *F = dyn_cast<Function>(GV);
  93   ASSERT_TRUE(F);
  94
  95   Value *P1 = &*F->arg_begin();
  96   Value *P2 = F->getArg(1);
  97   Value *NullPtr = Constant::getNullValue(P1->getType());
  98   auto InstIter = F->front().begin();
  99   CallInst *UserOfY = cast<CallInst>(&*InstIter);
 100   Value *ConstDerefPtr = UserOfY->getArgOperand(0);
 101   // We cannot replace two pointers in arbitrary instructions unless we are
 102   // replacing with null, a constant dereferencable pointer or they have the
 103   // same underlying object.
 104   EXPECT_FALSE(canReplacePointersIfEqual(ConstDerefPtr, P1, DL));
 105   EXPECT_FALSE(canReplacePointersIfEqual(P1, P2, DL));
 106   EXPECT_TRUE(canReplacePointersIfEqual(P1, ConstDerefPtr, DL));
 107   EXPECT_TRUE(canReplacePointersIfEqual(P1, NullPtr, DL));
 108
 109   GetElementPtrInst *BasedOnP1 = cast<GetElementPtrInst>(&*++InstIter);
 110   EXPECT_TRUE(canReplacePointersIfEqual(BasedOnP1, P1, DL));
 111   EXPECT_FALSE(canReplacePointersIfEqual(BasedOnP1, P2, DL));
 112
 113   // We can replace two arbitrary pointers in icmp and ptrtoint instructions.
 114   auto P1UseIter = P1->use_begin();
 115   const Use &PtrToIntUse = *P1UseIter;
 116   const Use &IcmpUse = *++P1UseIter;
 117   const Use &GEPUse = *++P1UseIter;
 118   EXPECT_FALSE(canReplacePointersInUseIfEqual(GEPUse, P2, DL));
 119   EXPECT_TRUE(canReplacePointersInUseIfEqual(PtrToIntUse, P2, DL));
 120   EXPECT_TRUE(canReplacePointersInUseIfEqual(IcmpUse, P2, DL));
 121 }
 122
 123 TEST(LoadsTest, IsDerefReadOnlyLoop) {
 124   LLVMContext C;
 125   std::unique_ptr<Module> M = parseIR(C,
 126                                       R"IR(
 127 define i64 @f1() {
 128 entry:
 129   %p1 = alloca [1024 x i8]
 130   %p2 = alloca [1024 x i8]
 131   br label %loop
 132
 133 loop:
 134   %index = phi i64 [ %index.next, %loop.inc ], [ 3, %entry ]
 135   %arrayidx = getelementptr inbounds i8, ptr %p1, i64 %index
 136   %ld1 = load i8, ptr %arrayidx, align 1
 137   %arrayidx1 = getelementptr inbounds i8, ptr %p2, i64 %index
 138   %ld2 = load i8, ptr %arrayidx1, align 1
 139   %cmp3 = icmp eq i8 %ld1, %ld2
 140   br i1 %cmp3, label %loop.inc, label %loop.end
 141
 142 loop.inc:
 143   %index.next = add i64 %index, 1
 144   %exitcond = icmp ne i64 %index.next, 67
 145   br i1 %exitcond, label %loop, label %loop.end
 146
 147 loop.end:
 148   %retval = phi i64 [ %index, %loop ], [ 67, %loop.inc ]
 149   ret i64 %retval
 150 }
 151
 152 define i64 @f2(ptr %p1) {
 153 entry:
 154   %p2 = alloca [1024 x i8]
 155   br label %loop
 156
 157 loop:
 158   %index = phi i64 [ %index.next, %loop.inc ], [ 3, %entry ]
 159   %arrayidx = getelementptr inbounds i8, ptr %p1, i64 %index
 160   %ld1 = load i8, ptr %arrayidx, align 1
 161   %arrayidx1 = getelementptr inbounds i8, ptr %p2, i64 %index
 162   %ld2 = load i8, ptr %arrayidx1, align 1
 163   %cmp3 = icmp eq i8 %ld1, %ld2
 164   br i1 %cmp3, label %loop.inc, label %loop.end
 165
 166 loop.inc:
 167   %index.next = add i64 %index, 1
 168   %exitcond = icmp ne i64 %index.next, 67
 169   br i1 %exitcond, label %loop, label %loop.end
 170
 171 loop.end:
 172   %retval = phi i64 [ %index, %loop ], [ 67, %loop.inc ]
 173   ret i64 %retval
 174 }
 175 )IR");
 176   auto *GV1 = M->getNamedValue("f1");
 177   auto *GV2 = M->getNamedValue("f2");
 178   ASSERT_TRUE(GV1 && GV2);
 179   auto *F1 = dyn_cast<Function>(GV1);
 180   auto *F2 = dyn_cast<Function>(GV2);
 181   ASSERT_TRUE(F1 && F2);
 182
 183   TargetLibraryInfoImpl TLII;
 184   TargetLibraryInfo TLI(TLII);
 185
 186   auto IsDerefReadOnlyLoop = [&TLI](Function *F) -> bool {
 187     AssumptionCache AC(*F);
 188     DominatorTree DT(*F);
 189     LoopInfo LI(DT);
 190     ScalarEvolution SE(*F, TLI, AC, DT, LI);
 191
 192     Function::iterator FI = F->begin();
 193     // First basic block is entry - skip it.
 194     BasicBlock *Header = &*(++FI);
 195     assert(Header->getName() == "loop");
 196     Loop *L = LI.getLoopFor(Header);
 197
 198     return isDereferenceableReadOnlyLoop(L, &SE, &DT, &AC);
 199   };
 200
 201   ASSERT_TRUE(IsDerefReadOnlyLoop(F1));
 202   ASSERT_FALSE(IsDerefReadOnlyLoop(F2));
 203 }