209 lines · 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-exception6//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 23using namespace llvm;24 25static 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 33TEST(LoadsTest, FindAvailableLoadedValueSameBasePtrConstantOffsetsNullAA) {34 LLVMContext C;35 std::unique_ptr<Module> M = parseIR(C,36 R"IR(37target datalayout = "p:64:64:64:32"38%class = type <{ i32, i32 }>39 40define i32 @f() {41entry:42 %o = alloca %class43 %f1 = getelementptr inbounds %class, %class* %o, i32 0, i32 044 store i32 42, i32* %f145 %f2 = getelementptr inbounds %class, %class* %o, i32 0, i32 146 store i32 43, i32* %f247 %v = load i32, i32* %f148 ret i32 %v49}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 70TEST(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 475@x = common global [1 x i32] zeroinitializer, align 476declare void @use(i32*)77 78define 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 %i82 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 i6486 ret void87}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 are102 // replacing with null, a constant dereferencable pointer or they have the103 // 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 123TEST(LoadsTest, IsReadOnlyLoop) {124 LLVMContext C;125 std::unique_ptr<Module> M = parseIR(C,126 R"IR(127define i64 @f1() {128entry:129 %p1 = alloca [1024 x i8]130 %p2 = alloca [1024 x i8]131 br label %loop132 133loop:134 %index = phi i64 [ %index.next, %loop.inc ], [ 3, %entry ]135 %arrayidx = getelementptr inbounds i8, ptr %p1, i64 %index136 %ld1 = load i8, ptr %arrayidx, align 1137 %arrayidx1 = getelementptr inbounds i8, ptr %p2, i64 %index138 %ld2 = load i8, ptr %arrayidx1, align 1139 %cmp3 = icmp eq i8 %ld1, %ld2140 br i1 %cmp3, label %loop.inc, label %loop.end141 142loop.inc:143 %index.next = add i64 %index, 1144 %exitcond = icmp ne i64 %index.next, 67145 br i1 %exitcond, label %loop, label %loop.end146 147loop.end:148 %retval = phi i64 [ %index, %loop ], [ 67, %loop.inc ]149 ret i64 %retval150}151 152define i64 @f2(ptr %p1) {153entry:154 %p2 = alloca [1024 x i8]155 br label %loop156 157loop:158 %index = phi i64 [ %index.next, %loop.inc ], [ 3, %entry ]159 %arrayidx = getelementptr inbounds i8, ptr %p1, i64 %index160 %ld1 = load i8, ptr %arrayidx, align 1161 %arrayidx1 = getelementptr inbounds i8, ptr %p2, i64 %index162 %ld2 = load i8, ptr %arrayidx1, align 1163 %cmp3 = icmp eq i8 %ld1, %ld2164 br i1 %cmp3, label %loop.inc, label %loop.end165 166loop.inc:167 %index.next = add i64 %index, 1168 %exitcond = icmp ne i64 %index.next, 67169 br i1 %exitcond, label %loop, label %loop.end170 171loop.end:172 %retval = phi i64 [ %index, %loop ], [ 67, %loop.inc ]173 ret i64 %retval174}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(M->getTargetTriple());184 TargetLibraryInfo TLI(TLII);185 186 auto IsReadOnlyLoop =187 [&TLI](Function *F, SmallVector<LoadInst *, 4> &NonDerefLoads) -> bool {188 AssumptionCache AC(*F);189 DominatorTree DT(*F);190 LoopInfo LI(DT);191 ScalarEvolution SE(*F, TLI, AC, DT, LI);192 193 Function::iterator FI = F->begin();194 // First basic block is entry - skip it.195 BasicBlock *Header = &*(++FI);196 assert(Header->getName() == "loop");197 Loop *L = LI.getLoopFor(Header);198 199 return isReadOnlyLoop(L, &SE, &DT, &AC, NonDerefLoads);200 };201 202 SmallVector<LoadInst *, 4> NonDerefLoads;203 ASSERT_TRUE(IsReadOnlyLoop(F1, NonDerefLoads));204 ASSERT_TRUE(NonDerefLoads.empty());205 ASSERT_TRUE(IsReadOnlyLoop(F2, NonDerefLoads));206 ASSERT_TRUE((NonDerefLoads.size() == 1) &&207 (NonDerefLoads[0]->getName() == "ld1"));208}209