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