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-exception 6 // 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 20 using namespace llvm; 21 22 /// Build the loop info and scalar evolution for the function and run the Test. 23 static 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; 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 39 static 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 for 48 // integer induction variables. And getExactFPMathInst() correctly return the 49 // expected behavior, i.e. no FMF algebra. 50 TEST(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) { 57 entry: 58 br label %for.body 59 for.body: 60 %i = phi i32 [ 0, %entry ], [ %inc, %for.body ] 61 %idxprom = sext i32 %i to i64 62 %arrayidx = getelementptr inbounds i32, ptr %A, i64 %idxprom 63 store i32 %i, ptr %arrayidx, align 4 64 %inc = add nsw i32 %i, 1 65 %cmp = icmp slt i32 %inc, %ub 66 br i1 %cmp, label %for.body, label %for.exit 67 for.exit: 68 br label %for.end 69 for.end: 70 ret void 71 })" 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 be 102 // a pointer, and InductionDescriptor used to fail with an assertion. 103 // So just check that it doesn't assert. 104 TEST(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 i32 118 %tmp20 = ptrtoint ptr %arg18 to i32 119 %tmp21 = or i32 %tmp20, %tmp 120 %tmp22 = and i32 %tmp21, 3 121 %tmp23 = icmp eq i32 %tmp22, 0 122 br i1 %tmp23, label %bb24, label %bb25 123 124 bb24: 125 tail call void @widget() 126 br label %bb34 127 128 bb25: 129 %tmp26 = sub i32 %tmp, %tmp20 130 %tmp27 = icmp ult i32 %tmp26, %arg19 131 br i1 %tmp27, label %bb28, label %bb34 132 133 bb28: 134 br label %bb29 135 136 bb29: 137 %tmp30 = phi i32 [ %tmp31, %bb29 ], [ %arg19, %bb28 ] 138 tail call void @wobble(i32 %tmp26) 139 %tmp31 = sub i32 %tmp30, %tmp26 140 %tmp32 = icmp ugt i32 %tmp31, %tmp26 141 br i1 %tmp32, label %bb29, label %bb33 142 143 bb33: 144 br label %bb34 145 146 bb34: 147 ret void 148 })"); 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 RecurrenceDescriptor 168 // that describes FMin reduction idiom. 169 TEST(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) { 175 entry: 176 br label %for.body 177 178 for.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 %i 182 %ld = load float, ptr %arrayidx 183 %fmin.cmp = fcmp nnan nsz olt float %fmin, %ld 184 %fmin.next = select nnan nsz i1 %fmin.cmp, float %fmin, float %ld 185 %i.next = add nsw i64 %i, 1 186 %cmp = icmp slt i64 %i.next, %ub 187 br i1 %cmp, label %for.body, label %for.end 188 189 for.end: 190 %fmin.lcssa = phi float [ %fmin.next, %for.body ] 191 ret float %fmin.lcssa 192 })"); 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 RecurrenceDescriptor 216 // that describes FMax reduction idiom. 217 TEST(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) { 223 entry: 224 br label %for.body 225 226 for.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 %i 230 %ld = load float, ptr %arrayidx 231 %fmax.cmp = fcmp nnan nsz ogt float %fmax, %ld 232 %fmax.next = select nnan nsz i1 %fmax.cmp, float %fmax, float %ld 233 %i.next = add nsw i64 %i, 1 234 %cmp = icmp slt i64 %i.next, %ub 235 br i1 %cmp, label %for.body, label %for.end 236 237 for.end: 238 %fmax.lcssa = phi float [ %fmax.next, %for.body ] 239 ret float %fmax.lcssa 240 })"); 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