262 lines · cpp
1//===- IVDescriptorsTest.cpp - IVDescriptors 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/IVDescriptors.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/Dominators.h"16#include "llvm/IR/Module.h"17#include "llvm/Support/SourceMgr.h"18#include "gtest/gtest.h"19 20using namespace llvm;21 22/// Build the loop info and scalar evolution for the function and run the Test.23static void runWithLoopInfoAndSE(24 Module &M, StringRef FuncName,25 function_ref<void(Function &F, LoopInfo &LI, ScalarEvolution &SE)> Test) {26 auto *F = M.getFunction(FuncName);27 ASSERT_NE(F, nullptr) << "Could not find " << FuncName;28 29 TargetLibraryInfoImpl TLII(M.getTargetTriple());30 TargetLibraryInfo TLI(TLII);31 AssumptionCache AC(*F);32 DominatorTree DT(*F);33 LoopInfo LI(DT);34 ScalarEvolution SE(*F, TLI, AC, DT, LI);35 36 Test(*F, LI, SE);37}38 39static std::unique_ptr<Module> parseIR(LLVMContext &C, const char *IR) {40 SMDiagnostic Err;41 std::unique_ptr<Module> Mod = parseAssemblyString(IR, Err, C);42 if (!Mod)43 Err.print("IVDescriptorsTests", errs());44 return Mod;45}46 47// This tests that IVDescriptors can obtain the induction binary operator for48// integer induction variables. And getExactFPMathInst() correctly return the49// expected behavior, i.e. no FMF algebra.50TEST(IVDescriptorsTest, LoopWithSingleLatch) {51 // Parse the module.52 LLVMContext Context;53 54 std::unique_ptr<Module> M = parseIR(55 Context,56 R"(define void @foo(ptr %A, i32 %ub) {57entry:58 br label %for.body59for.body:60 %i = phi i32 [ 0, %entry ], [ %inc, %for.body ]61 %idxprom = sext i32 %i to i6462 %arrayidx = getelementptr inbounds i32, ptr %A, i64 %idxprom63 store i32 %i, ptr %arrayidx, align 464 %inc = add nsw i32 %i, 165 %cmp = icmp slt i32 %inc, %ub66 br i1 %cmp, label %for.body, label %for.exit67for.exit:68 br label %for.end69for.end:70 ret void71})"72 );73 74 runWithLoopInfoAndSE(75 *M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {76 Function::iterator FI = F.begin();77 // First basic block is entry - skip it.78 BasicBlock *Header = &*(++FI);79 assert(Header->getName() == "for.body");80 Loop *L = LI.getLoopFor(Header);81 EXPECT_NE(L, nullptr);82 PHINode *Inst_i = dyn_cast<PHINode>(&Header->front());83 assert(Inst_i->getName() == "i");84 InductionDescriptor IndDesc;85 bool IsInductionPHI =86 InductionDescriptor::isInductionPHI(Inst_i, L, &SE, IndDesc);87 EXPECT_TRUE(IsInductionPHI);88 Instruction *Inst_inc = nullptr;89 BasicBlock::iterator BBI = Header->begin();90 do {91 if ((&*BBI)->getName() == "inc")92 Inst_inc = &*BBI;93 ++BBI;94 } while (!Inst_inc);95 assert(Inst_inc->getName() == "inc");96 EXPECT_EQ(IndDesc.getInductionBinOp(), Inst_inc);97 EXPECT_EQ(IndDesc.getExactFPMathInst(), nullptr);98 });99}100 101// Depending on how SCEV deals with ptrtoint cast, the step of a phi could be102// a pointer, and InductionDescriptor used to fail with an assertion.103// So just check that it doesn't assert.104TEST(IVDescriptorsTest, LoopWithPtrToInt) {105 // Parse the module.106 LLVMContext Context;107 108 std::unique_ptr<Module> M = parseIR(Context, R"(109 target datalayout = "e-m:e-p:32:32-Fi8-i64:64-v128:64:128-a:0:32-n32-S64"110 target triple = "thumbv6m-arm-none-eabi"111 112 declare void @widget()113 declare void @wobble(i32)114 115 define void @barney(ptr %arg, ptr %arg18, i32 %arg19) {116 bb:117 %tmp = ptrtoint ptr %arg to i32118 %tmp20 = ptrtoint ptr %arg18 to i32119 %tmp21 = or i32 %tmp20, %tmp120 %tmp22 = and i32 %tmp21, 3121 %tmp23 = icmp eq i32 %tmp22, 0122 br i1 %tmp23, label %bb24, label %bb25123 124 bb24:125 tail call void @widget()126 br label %bb34127 128 bb25:129 %tmp26 = sub i32 %tmp, %tmp20130 %tmp27 = icmp ult i32 %tmp26, %arg19131 br i1 %tmp27, label %bb28, label %bb34132 133 bb28:134 br label %bb29135 136 bb29:137 %tmp30 = phi i32 [ %tmp31, %bb29 ], [ %arg19, %bb28 ]138 tail call void @wobble(i32 %tmp26)139 %tmp31 = sub i32 %tmp30, %tmp26140 %tmp32 = icmp ugt i32 %tmp31, %tmp26141 br i1 %tmp32, label %bb29, label %bb33142 143 bb33:144 br label %bb34145 146 bb34:147 ret void148 })");149 150 runWithLoopInfoAndSE(151 *M, "barney", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {152 Function::iterator FI = F.begin();153 // First basic block is entry - skip it.154 BasicBlock *Header = &*(++(++(++(++FI))));155 assert(Header->getName() == "bb29");156 Loop *L = LI.getLoopFor(Header);157 EXPECT_NE(L, nullptr);158 PHINode *Inst_i = dyn_cast<PHINode>(&Header->front());159 assert(Inst_i->getName() == "tmp30");160 InductionDescriptor IndDesc;161 bool IsInductionPHI =162 InductionDescriptor::isInductionPHI(Inst_i, L, &SE, IndDesc);163 EXPECT_TRUE(IsInductionPHI);164 });165}166 167// This tests that correct identity value is returned for a RecurrenceDescriptor168// that describes FMin reduction idiom.169TEST(IVDescriptorsTest, FMinRednIdentity) {170 // Parse the module.171 LLVMContext Context;172 173 std::unique_ptr<Module> M = parseIR(Context,174 R"(define float @foo(ptr %A, i64 %ub) {175entry:176 br label %for.body177 178for.body:179 %i = phi i64 [ 0, %entry ], [ %i.next, %for.body ]180 %fmin = phi float [ 1.000000e+00, %entry ], [ %fmin.next, %for.body ]181 %arrayidx = getelementptr inbounds float, ptr %A, i64 %i182 %ld = load float, ptr %arrayidx183 %fmin.cmp = fcmp nnan nsz olt float %fmin, %ld184 %fmin.next = select nnan nsz i1 %fmin.cmp, float %fmin, float %ld185 %i.next = add nsw i64 %i, 1186 %cmp = icmp slt i64 %i.next, %ub187 br i1 %cmp, label %for.body, label %for.end188 189for.end:190 %fmin.lcssa = phi float [ %fmin.next, %for.body ]191 ret float %fmin.lcssa192})");193 194 runWithLoopInfoAndSE(195 *M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {196 Function::iterator FI = F.begin();197 // First basic block is entry - skip it.198 BasicBlock *Header = &*(++FI);199 assert(Header->getName() == "for.body");200 Loop *L = LI.getLoopFor(Header);201 EXPECT_NE(L, nullptr);202 BasicBlock::iterator BBI = Header->begin();203 assert((&*BBI)->getName() == "i");204 ++BBI;205 PHINode *Phi = dyn_cast<PHINode>(&*BBI);206 assert(Phi->getName() == "fmin");207 RecurrenceDescriptor Rdx;208 bool IsRdxPhi = RecurrenceDescriptor::isReductionPHI(Phi, L, Rdx);209 EXPECT_TRUE(IsRdxPhi);210 RecurKind Kind = Rdx.getRecurrenceKind();211 EXPECT_EQ(Kind, RecurKind::FMin);212 });213}214 215// This tests that correct identity value is returned for a RecurrenceDescriptor216// that describes FMax reduction idiom.217TEST(IVDescriptorsTest, FMaxRednIdentity) {218 // Parse the module.219 LLVMContext Context;220 221 std::unique_ptr<Module> M = parseIR(Context,222 R"(define float @foo(ptr %A, i64 %ub) {223entry:224 br label %for.body225 226for.body:227 %i = phi i64 [ 0, %entry ], [ %i.next, %for.body ]228 %fmax = phi float [ 1.000000e+00, %entry ], [ %fmax.next, %for.body ]229 %arrayidx = getelementptr inbounds float, ptr %A, i64 %i230 %ld = load float, ptr %arrayidx231 %fmax.cmp = fcmp nnan nsz ogt float %fmax, %ld232 %fmax.next = select nnan nsz i1 %fmax.cmp, float %fmax, float %ld233 %i.next = add nsw i64 %i, 1234 %cmp = icmp slt i64 %i.next, %ub235 br i1 %cmp, label %for.body, label %for.end236 237for.end:238 %fmax.lcssa = phi float [ %fmax.next, %for.body ]239 ret float %fmax.lcssa240})");241 242 runWithLoopInfoAndSE(243 *M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {244 Function::iterator FI = F.begin();245 // First basic block is entry - skip it.246 BasicBlock *Header = &*(++FI);247 assert(Header->getName() == "for.body");248 Loop *L = LI.getLoopFor(Header);249 EXPECT_NE(L, nullptr);250 BasicBlock::iterator BBI = Header->begin();251 assert((&*BBI)->getName() == "i");252 ++BBI;253 PHINode *Phi = dyn_cast<PHINode>(&*BBI);254 assert(Phi->getName() == "fmax");255 RecurrenceDescriptor Rdx;256 bool IsRdxPhi = RecurrenceDescriptor::isReductionPHI(Phi, L, Rdx);257 EXPECT_TRUE(IsRdxPhi);258 RecurKind Kind = Rdx.getRecurrenceKind();259 EXPECT_EQ(Kind, RecurKind::FMax);260 });261}262