1 //===- LoopInfoTest.cpp - LoopInfo 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/LoopInfo.h" 10 #include "llvm/Analysis/AssumptionCache.h" 11 #include "llvm/Analysis/ScalarEvolution.h" 12 #include "llvm/Analysis/TargetLibraryInfo.h" 13 #include "llvm/AsmParser/Parser.h" 14 #include "llvm/IR/Dominators.h" 15 #include "llvm/Support/SourceMgr.h" 16 #include "gtest/gtest.h" 17 18 using namespace llvm; 19 20 /// Build the loop info for the function and run the Test. 21 static void 22 runWithLoopInfo(Module &M, StringRef FuncName, 23 function_ref<void(Function &F, LoopInfo &LI)> Test) { 24 auto *F = M.getFunction(FuncName); 25 ASSERT_NE(F, nullptr) << "Could not find " << FuncName; 26 // Compute the dominator tree and the loop info for the function. 27 DominatorTree DT(*F); 28 LoopInfo LI(DT); 29 Test(*F, LI); 30 } 31 32 /// Build the loop info and scalar evolution for the function and run the Test. 33 static void runWithLoopInfoPlus( 34 Module &M, StringRef FuncName, 35 function_ref<void(Function &F, LoopInfo &LI, ScalarEvolution &SE)> Test) { 36 auto *F = M.getFunction(FuncName); 37 ASSERT_NE(F, nullptr) << "Could not find " << FuncName; 38 39 TargetLibraryInfoImpl TLII; 40 TargetLibraryInfo TLI(TLII); 41 AssumptionCache AC(*F); 42 DominatorTree DT(*F); 43 LoopInfo LI(DT); 44 ScalarEvolution SE(*F, TLI, AC, DT, LI); 45 Test(*F, LI, SE); 46 } 47 48 static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context, 49 const char *ModuleStr) { 50 SMDiagnostic Err; 51 return parseAssemblyString(ModuleStr, Err, Context); 52 } 53 54 // This tests that for a loop with a single latch, we get the loop id from 55 // its only latch, even in case the loop may not be in a simplified form. 56 TEST(LoopInfoTest, LoopWithSingleLatch) { 57 const char *ModuleStr = 58 "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n" 59 "define void @foo(i32 %n) {\n" 60 "entry:\n" 61 " br i1 undef, label %for.cond, label %for.end\n" 62 "for.cond:\n" 63 " %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]\n" 64 " %cmp = icmp slt i32 %i.0, %n\n" 65 " br i1 %cmp, label %for.inc, label %for.end\n" 66 "for.inc:\n" 67 " %inc = add nsw i32 %i.0, 1\n" 68 " br label %for.cond, !llvm.loop !0\n" 69 "for.end:\n" 70 " ret void\n" 71 "}\n" 72 "!0 = distinct !{!0, !1}\n" 73 "!1 = !{!\"llvm.loop.distribute.enable\", i1 true}\n"; 74 75 // Parse the module. 76 LLVMContext Context; 77 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 78 79 runWithLoopInfo(*M, "foo", [&](Function &F, LoopInfo &LI) { 80 Function::iterator FI = F.begin(); 81 // First basic block is entry - skip it. 82 BasicBlock *Header = &*(++FI); 83 assert(Header->getName() == "for.cond"); 84 Loop *L = LI.getLoopFor(Header); 85 86 // This loop is not in simplified form. 87 EXPECT_FALSE(L->isLoopSimplifyForm()); 88 89 // Analyze the loop metadata id. 90 bool loopIDFoundAndSet = false; 91 // Try to get and set the metadata id for the loop. 92 if (MDNode *D = L->getLoopID()) { 93 L->setLoopID(D); 94 loopIDFoundAndSet = true; 95 } 96 97 // We must have successfully found and set the loop id in the 98 // only latch the loop has. 99 EXPECT_TRUE(loopIDFoundAndSet); 100 }); 101 } 102 103 // Test loop id handling for a loop with multiple latches. 104 TEST(LoopInfoTest, LoopWithMultipleLatches) { 105 const char *ModuleStr = 106 "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n" 107 "define void @foo(i32 %n) {\n" 108 "entry:\n" 109 " br i1 undef, label %for.cond, label %for.end\n" 110 "for.cond:\n" 111 " %i.0 = phi i32 [ 0, %entry ], [ %inc, %latch.1 ], [ %inc, %latch.2 ]\n" 112 " %inc = add nsw i32 %i.0, 1\n" 113 " %cmp = icmp slt i32 %i.0, %n\n" 114 " br i1 %cmp, label %latch.1, label %for.end\n" 115 "latch.1:\n" 116 " br i1 undef, label %for.cond, label %latch.2, !llvm.loop !0\n" 117 "latch.2:\n" 118 " br label %for.cond, !llvm.loop !0\n" 119 "for.end:\n" 120 " ret void\n" 121 "}\n" 122 "!0 = distinct !{!0, !1}\n" 123 "!1 = !{!\"llvm.loop.distribute.enable\", i1 true}\n"; 124 125 // Parse the module. 126 LLVMContext Context; 127 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 128 129 runWithLoopInfo(*M, "foo", [&](Function &F, LoopInfo &LI) { 130 Function::iterator FI = F.begin(); 131 // First basic block is entry - skip it. 132 BasicBlock *Header = &*(++FI); 133 assert(Header->getName() == "for.cond"); 134 Loop *L = LI.getLoopFor(Header); 135 EXPECT_NE(L, nullptr); 136 137 // This loop is not in simplified form. 138 EXPECT_FALSE(L->isLoopSimplifyForm()); 139 140 // Try to get and set the metadata id for the loop. 141 MDNode *OldLoopID = L->getLoopID(); 142 EXPECT_NE(OldLoopID, nullptr); 143 144 MDNode *NewLoopID = MDNode::get(Context, {nullptr}); 145 // Set operand 0 to refer to the loop id itself. 146 NewLoopID->replaceOperandWith(0, NewLoopID); 147 148 L->setLoopID(NewLoopID); 149 EXPECT_EQ(L->getLoopID(), NewLoopID); 150 EXPECT_NE(L->getLoopID(), OldLoopID); 151 152 L->setLoopID(OldLoopID); 153 EXPECT_EQ(L->getLoopID(), OldLoopID); 154 EXPECT_NE(L->getLoopID(), NewLoopID); 155 }); 156 } 157 158 TEST(LoopInfoTest, PreorderTraversals) { 159 const char *ModuleStr = "define void @f() {\n" 160 "entry:\n" 161 " br label %loop.0\n" 162 "loop.0:\n" 163 " br i1 undef, label %loop.0.0, label %loop.1\n" 164 "loop.0.0:\n" 165 " br i1 undef, label %loop.0.0, label %loop.0.1\n" 166 "loop.0.1:\n" 167 " br i1 undef, label %loop.0.1, label %loop.0.2\n" 168 "loop.0.2:\n" 169 " br i1 undef, label %loop.0.2, label %loop.0\n" 170 "loop.1:\n" 171 " br i1 undef, label %loop.1.0, label %end\n" 172 "loop.1.0:\n" 173 " br i1 undef, label %loop.1.0, label %loop.1.1\n" 174 "loop.1.1:\n" 175 " br i1 undef, label %loop.1.1, label %loop.1.2\n" 176 "loop.1.2:\n" 177 " br i1 undef, label %loop.1.2, label %loop.1\n" 178 "end:\n" 179 " ret void\n" 180 "}\n"; 181 // Parse the module. 182 LLVMContext Context; 183 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 184 Function &F = *M->begin(); 185 186 DominatorTree DT(F); 187 LoopInfo LI; 188 LI.analyze(DT); 189 190 Function::iterator I = F.begin(); 191 ASSERT_EQ("entry", I->getName()); 192 ++I; 193 Loop &L_0 = *LI.getLoopFor(&*I++); 194 ASSERT_EQ("loop.0", L_0.getHeader()->getName()); 195 Loop &L_0_0 = *LI.getLoopFor(&*I++); 196 ASSERT_EQ("loop.0.0", L_0_0.getHeader()->getName()); 197 Loop &L_0_1 = *LI.getLoopFor(&*I++); 198 ASSERT_EQ("loop.0.1", L_0_1.getHeader()->getName()); 199 Loop &L_0_2 = *LI.getLoopFor(&*I++); 200 ASSERT_EQ("loop.0.2", L_0_2.getHeader()->getName()); 201 Loop &L_1 = *LI.getLoopFor(&*I++); 202 ASSERT_EQ("loop.1", L_1.getHeader()->getName()); 203 Loop &L_1_0 = *LI.getLoopFor(&*I++); 204 ASSERT_EQ("loop.1.0", L_1_0.getHeader()->getName()); 205 Loop &L_1_1 = *LI.getLoopFor(&*I++); 206 ASSERT_EQ("loop.1.1", L_1_1.getHeader()->getName()); 207 Loop &L_1_2 = *LI.getLoopFor(&*I++); 208 ASSERT_EQ("loop.1.2", L_1_2.getHeader()->getName()); 209 210 auto Preorder = LI.getLoopsInPreorder(); 211 ASSERT_EQ(8u, Preorder.size()); 212 EXPECT_EQ(&L_0, Preorder[0]); 213 EXPECT_EQ(&L_0_0, Preorder[1]); 214 EXPECT_EQ(&L_0_1, Preorder[2]); 215 EXPECT_EQ(&L_0_2, Preorder[3]); 216 EXPECT_EQ(&L_1, Preorder[4]); 217 EXPECT_EQ(&L_1_0, Preorder[5]); 218 EXPECT_EQ(&L_1_1, Preorder[6]); 219 EXPECT_EQ(&L_1_2, Preorder[7]); 220 221 auto ReverseSiblingPreorder = LI.getLoopsInReverseSiblingPreorder(); 222 ASSERT_EQ(8u, ReverseSiblingPreorder.size()); 223 EXPECT_EQ(&L_1, ReverseSiblingPreorder[0]); 224 EXPECT_EQ(&L_1_2, ReverseSiblingPreorder[1]); 225 EXPECT_EQ(&L_1_1, ReverseSiblingPreorder[2]); 226 EXPECT_EQ(&L_1_0, ReverseSiblingPreorder[3]); 227 EXPECT_EQ(&L_0, ReverseSiblingPreorder[4]); 228 EXPECT_EQ(&L_0_2, ReverseSiblingPreorder[5]); 229 EXPECT_EQ(&L_0_1, ReverseSiblingPreorder[6]); 230 EXPECT_EQ(&L_0_0, ReverseSiblingPreorder[7]); 231 } 232 233 TEST(LoopInfoTest, CanonicalLoop) { 234 const char *ModuleStr = 235 "define void @foo(i32* %A, i32 %ub) {\n" 236 "entry:\n" 237 " %guardcmp = icmp slt i32 0, %ub\n" 238 " br i1 %guardcmp, label %for.preheader, label %for.end\n" 239 "for.preheader:\n" 240 " br label %for.body\n" 241 "for.body:\n" 242 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n" 243 " %idxprom = sext i32 %i to i64\n" 244 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" 245 " store i32 %i, i32* %arrayidx, align 4\n" 246 " %inc = add nsw i32 %i, 1\n" 247 " %cmp = icmp slt i32 %inc, %ub\n" 248 " br i1 %cmp, label %for.body, label %for.exit\n" 249 "for.exit:\n" 250 " br label %for.end\n" 251 "for.end:\n" 252 " ret void\n" 253 "}\n"; 254 255 // Parse the module. 256 LLVMContext Context; 257 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 258 259 runWithLoopInfoPlus( 260 *M, "foo", 261 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 262 Function::iterator FI = F.begin(); 263 BasicBlock *Entry = &*(FI); 264 BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator()); 265 // First two basic block are entry and for.preheader - skip them. 266 ++FI; 267 BasicBlock *Header = &*(++FI); 268 assert(Header->getName() == "for.body"); 269 Loop *L = LI.getLoopFor(Header); 270 EXPECT_NE(L, nullptr); 271 272 Optional<Loop::LoopBounds> Bounds = L->getBounds(SE); 273 EXPECT_NE(Bounds, None); 274 ConstantInt *InitialIVValue = 275 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue()); 276 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); 277 EXPECT_EQ(Bounds->getStepInst().getName(), "inc"); 278 ConstantInt *StepValue = 279 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue()); 280 EXPECT_TRUE(StepValue && StepValue->isOne()); 281 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub"); 282 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT); 283 EXPECT_EQ(Bounds->getDirection(), 284 Loop::LoopBounds::Direction::Increasing); 285 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); 286 EXPECT_EQ(L->getLoopGuardBranch(), Guard); 287 EXPECT_TRUE(L->isGuarded()); 288 }); 289 } 290 291 TEST(LoopInfoTest, LoopWithInverseGuardSuccs) { 292 const char *ModuleStr = 293 "define void @foo(i32* %A, i32 %ub) {\n" 294 "entry:\n" 295 " %guardcmp = icmp sge i32 0, %ub\n" 296 " br i1 %guardcmp, label %for.end, label %for.preheader\n" 297 "for.preheader:\n" 298 " br label %for.body\n" 299 "for.body:\n" 300 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n" 301 " %idxprom = sext i32 %i to i64\n" 302 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" 303 " store i32 %i, i32* %arrayidx, align 4\n" 304 " %inc = add nsw i32 %i, 1\n" 305 " %cmp = icmp slt i32 %inc, %ub\n" 306 " br i1 %cmp, label %for.body, label %for.exit\n" 307 "for.exit:\n" 308 " br label %for.end\n" 309 "for.end:\n" 310 " ret void\n" 311 "}\n"; 312 313 // Parse the module. 314 LLVMContext Context; 315 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 316 317 runWithLoopInfoPlus( 318 *M, "foo", 319 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 320 Function::iterator FI = F.begin(); 321 BasicBlock *Entry = &*(FI); 322 BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator()); 323 // First two basic block are entry and for.preheader - skip them. 324 ++FI; 325 BasicBlock *Header = &*(++FI); 326 assert(Header->getName() == "for.body"); 327 Loop *L = LI.getLoopFor(Header); 328 EXPECT_NE(L, nullptr); 329 330 Optional<Loop::LoopBounds> Bounds = L->getBounds(SE); 331 EXPECT_NE(Bounds, None); 332 ConstantInt *InitialIVValue = 333 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue()); 334 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); 335 EXPECT_EQ(Bounds->getStepInst().getName(), "inc"); 336 ConstantInt *StepValue = 337 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue()); 338 EXPECT_TRUE(StepValue && StepValue->isOne()); 339 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub"); 340 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT); 341 EXPECT_EQ(Bounds->getDirection(), 342 Loop::LoopBounds::Direction::Increasing); 343 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); 344 EXPECT_EQ(L->getLoopGuardBranch(), Guard); 345 EXPECT_TRUE(L->isGuarded()); 346 }); 347 } 348 349 TEST(LoopInfoTest, LoopWithSwappedGuardCmp) { 350 const char *ModuleStr = 351 "define void @foo(i32* %A, i32 %ub) {\n" 352 "entry:\n" 353 " %guardcmp = icmp sgt i32 %ub, 0\n" 354 " br i1 %guardcmp, label %for.preheader, label %for.end\n" 355 "for.preheader:\n" 356 " br label %for.body\n" 357 "for.body:\n" 358 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n" 359 " %idxprom = sext i32 %i to i64\n" 360 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" 361 " store i32 %i, i32* %arrayidx, align 4\n" 362 " %inc = add nsw i32 %i, 1\n" 363 " %cmp = icmp sge i32 %inc, %ub\n" 364 " br i1 %cmp, label %for.exit, label %for.body\n" 365 "for.exit:\n" 366 " br label %for.end\n" 367 "for.end:\n" 368 " ret void\n" 369 "}\n"; 370 371 // Parse the module. 372 LLVMContext Context; 373 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 374 375 runWithLoopInfoPlus( 376 *M, "foo", 377 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 378 Function::iterator FI = F.begin(); 379 BasicBlock *Entry = &*(FI); 380 BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator()); 381 // First two basic block are entry and for.preheader - skip them. 382 ++FI; 383 BasicBlock *Header = &*(++FI); 384 assert(Header->getName() == "for.body"); 385 Loop *L = LI.getLoopFor(Header); 386 EXPECT_NE(L, nullptr); 387 388 Optional<Loop::LoopBounds> Bounds = L->getBounds(SE); 389 EXPECT_NE(Bounds, None); 390 ConstantInt *InitialIVValue = 391 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue()); 392 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); 393 EXPECT_EQ(Bounds->getStepInst().getName(), "inc"); 394 ConstantInt *StepValue = 395 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue()); 396 EXPECT_TRUE(StepValue && StepValue->isOne()); 397 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub"); 398 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT); 399 EXPECT_EQ(Bounds->getDirection(), 400 Loop::LoopBounds::Direction::Increasing); 401 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); 402 EXPECT_EQ(L->getLoopGuardBranch(), Guard); 403 EXPECT_TRUE(L->isGuarded()); 404 }); 405 } 406 407 TEST(LoopInfoTest, LoopWithInverseLatchSuccs) { 408 const char *ModuleStr = 409 "define void @foo(i32* %A, i32 %ub) {\n" 410 "entry:\n" 411 " %guardcmp = icmp slt i32 0, %ub\n" 412 " br i1 %guardcmp, label %for.preheader, label %for.end\n" 413 "for.preheader:\n" 414 " br label %for.body\n" 415 "for.body:\n" 416 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n" 417 " %idxprom = sext i32 %i to i64\n" 418 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" 419 " store i32 %i, i32* %arrayidx, align 4\n" 420 " %inc = add nsw i32 %i, 1\n" 421 " %cmp = icmp sge i32 %inc, %ub\n" 422 " br i1 %cmp, label %for.exit, label %for.body\n" 423 "for.exit:\n" 424 " br label %for.end\n" 425 "for.end:\n" 426 " ret void\n" 427 "}\n"; 428 429 // Parse the module. 430 LLVMContext Context; 431 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 432 433 runWithLoopInfoPlus( 434 *M, "foo", 435 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 436 Function::iterator FI = F.begin(); 437 BasicBlock *Entry = &*(FI); 438 BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator()); 439 // First two basic block are entry and for.preheader - skip them. 440 ++FI; 441 BasicBlock *Header = &*(++FI); 442 assert(Header->getName() == "for.body"); 443 Loop *L = LI.getLoopFor(Header); 444 EXPECT_NE(L, nullptr); 445 446 Optional<Loop::LoopBounds> Bounds = L->getBounds(SE); 447 EXPECT_NE(Bounds, None); 448 ConstantInt *InitialIVValue = 449 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue()); 450 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); 451 EXPECT_EQ(Bounds->getStepInst().getName(), "inc"); 452 ConstantInt *StepValue = 453 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue()); 454 EXPECT_TRUE(StepValue && StepValue->isOne()); 455 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub"); 456 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT); 457 EXPECT_EQ(Bounds->getDirection(), 458 Loop::LoopBounds::Direction::Increasing); 459 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); 460 EXPECT_EQ(L->getLoopGuardBranch(), Guard); 461 EXPECT_TRUE(L->isGuarded()); 462 }); 463 } 464 465 TEST(LoopInfoTest, LoopWithLatchCmpNE) { 466 const char *ModuleStr = 467 "define void @foo(i32* %A, i32 %ub) {\n" 468 "entry:\n" 469 " %guardcmp = icmp slt i32 0, %ub\n" 470 " br i1 %guardcmp, label %for.preheader, label %for.end\n" 471 "for.preheader:\n" 472 " br label %for.body\n" 473 "for.body:\n" 474 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n" 475 " %idxprom = sext i32 %i to i64\n" 476 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" 477 " store i32 %i, i32* %arrayidx, align 4\n" 478 " %inc = add nsw i32 %i, 1\n" 479 " %cmp = icmp ne i32 %i, %ub\n" 480 " br i1 %cmp, label %for.body, label %for.exit\n" 481 "for.exit:\n" 482 " br label %for.end\n" 483 "for.end:\n" 484 " ret void\n" 485 "}\n"; 486 487 // Parse the module. 488 LLVMContext Context; 489 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 490 491 runWithLoopInfoPlus( 492 *M, "foo", 493 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 494 Function::iterator FI = F.begin(); 495 BasicBlock *Entry = &*(FI); 496 BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator()); 497 // First two basic block are entry and for.preheader - skip them. 498 ++FI; 499 BasicBlock *Header = &*(++FI); 500 assert(Header->getName() == "for.body"); 501 Loop *L = LI.getLoopFor(Header); 502 EXPECT_NE(L, nullptr); 503 504 Optional<Loop::LoopBounds> Bounds = L->getBounds(SE); 505 EXPECT_NE(Bounds, None); 506 ConstantInt *InitialIVValue = 507 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue()); 508 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); 509 EXPECT_EQ(Bounds->getStepInst().getName(), "inc"); 510 ConstantInt *StepValue = 511 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue()); 512 EXPECT_TRUE(StepValue && StepValue->isOne()); 513 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub"); 514 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT); 515 EXPECT_EQ(Bounds->getDirection(), 516 Loop::LoopBounds::Direction::Increasing); 517 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); 518 EXPECT_EQ(L->getLoopGuardBranch(), Guard); 519 EXPECT_TRUE(L->isGuarded()); 520 }); 521 } 522 523 TEST(LoopInfoTest, LoopWithGuardCmpSLE) { 524 const char *ModuleStr = 525 "define void @foo(i32* %A, i32 %ub) {\n" 526 "entry:\n" 527 " %ubPlusOne = add i32 %ub, 1\n" 528 " %guardcmp = icmp sle i32 0, %ub\n" 529 " br i1 %guardcmp, label %for.preheader, label %for.end\n" 530 "for.preheader:\n" 531 " br label %for.body\n" 532 "for.body:\n" 533 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n" 534 " %idxprom = sext i32 %i to i64\n" 535 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" 536 " store i32 %i, i32* %arrayidx, align 4\n" 537 " %inc = add nsw i32 %i, 1\n" 538 " %cmp = icmp ne i32 %i, %ubPlusOne\n" 539 " br i1 %cmp, label %for.body, label %for.exit\n" 540 "for.exit:\n" 541 " br label %for.end\n" 542 "for.end:\n" 543 " ret void\n" 544 "}\n"; 545 546 // Parse the module. 547 LLVMContext Context; 548 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 549 550 runWithLoopInfoPlus( 551 *M, "foo", 552 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 553 Function::iterator FI = F.begin(); 554 BasicBlock *Entry = &*(FI); 555 BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator()); 556 // First two basic block are entry and for.preheader - skip them. 557 ++FI; 558 BasicBlock *Header = &*(++FI); 559 assert(Header->getName() == "for.body"); 560 Loop *L = LI.getLoopFor(Header); 561 EXPECT_NE(L, nullptr); 562 563 Optional<Loop::LoopBounds> Bounds = L->getBounds(SE); 564 EXPECT_NE(Bounds, None); 565 ConstantInt *InitialIVValue = 566 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue()); 567 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); 568 EXPECT_EQ(Bounds->getStepInst().getName(), "inc"); 569 ConstantInt *StepValue = 570 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue()); 571 EXPECT_TRUE(StepValue && StepValue->isOne()); 572 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ubPlusOne"); 573 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT); 574 EXPECT_EQ(Bounds->getDirection(), 575 Loop::LoopBounds::Direction::Increasing); 576 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); 577 EXPECT_EQ(L->getLoopGuardBranch(), Guard); 578 EXPECT_TRUE(L->isGuarded()); 579 }); 580 } 581 582 TEST(LoopInfoTest, LoopNonConstantStep) { 583 const char *ModuleStr = 584 "define void @foo(i32* %A, i32 %ub, i32 %step) {\n" 585 "entry:\n" 586 " %guardcmp = icmp slt i32 0, %ub\n" 587 " br i1 %guardcmp, label %for.preheader, label %for.end\n" 588 "for.preheader:\n" 589 " br label %for.body\n" 590 "for.body:\n" 591 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n" 592 " %idxprom = zext i32 %i to i64\n" 593 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" 594 " store i32 %i, i32* %arrayidx, align 4\n" 595 " %inc = add nsw i32 %i, %step\n" 596 " %cmp = icmp slt i32 %inc, %ub\n" 597 " br i1 %cmp, label %for.body, label %for.exit\n" 598 "for.exit:\n" 599 " br label %for.end\n" 600 "for.end:\n" 601 " ret void\n" 602 "}\n"; 603 604 // Parse the module. 605 LLVMContext Context; 606 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 607 608 runWithLoopInfoPlus( 609 *M, "foo", 610 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 611 Function::iterator FI = F.begin(); 612 BasicBlock *Entry = &*(FI); 613 BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator()); 614 // First two basic block are entry and for.preheader - skip them. 615 ++FI; 616 BasicBlock *Header = &*(++FI); 617 assert(Header->getName() == "for.body"); 618 Loop *L = LI.getLoopFor(Header); 619 EXPECT_NE(L, nullptr); 620 621 Optional<Loop::LoopBounds> Bounds = L->getBounds(SE); 622 EXPECT_NE(Bounds, None); 623 ConstantInt *InitialIVValue = 624 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue()); 625 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); 626 EXPECT_EQ(Bounds->getStepInst().getName(), "inc"); 627 EXPECT_EQ(Bounds->getStepValue()->getName(), "step"); 628 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub"); 629 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT); 630 EXPECT_EQ(Bounds->getDirection(), Loop::LoopBounds::Direction::Unknown); 631 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); 632 EXPECT_EQ(L->getLoopGuardBranch(), Guard); 633 EXPECT_TRUE(L->isGuarded()); 634 }); 635 } 636 637 TEST(LoopInfoTest, LoopUnsignedBounds) { 638 const char *ModuleStr = 639 "define void @foo(i32* %A, i32 %ub) {\n" 640 "entry:\n" 641 " %guardcmp = icmp ult i32 0, %ub\n" 642 " br i1 %guardcmp, label %for.preheader, label %for.end\n" 643 "for.preheader:\n" 644 " br label %for.body\n" 645 "for.body:\n" 646 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n" 647 " %idxprom = zext i32 %i to i64\n" 648 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" 649 " store i32 %i, i32* %arrayidx, align 4\n" 650 " %inc = add i32 %i, 1\n" 651 " %cmp = icmp ult i32 %inc, %ub\n" 652 " br i1 %cmp, label %for.body, label %for.exit\n" 653 "for.exit:\n" 654 " br label %for.end\n" 655 "for.end:\n" 656 " ret void\n" 657 "}\n"; 658 659 // Parse the module. 660 LLVMContext Context; 661 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 662 663 runWithLoopInfoPlus( 664 *M, "foo", 665 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 666 Function::iterator FI = F.begin(); 667 BasicBlock *Entry = &*(FI); 668 BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator()); 669 // First two basic block are entry and for.preheader - skip them. 670 ++FI; 671 BasicBlock *Header = &*(++FI); 672 assert(Header->getName() == "for.body"); 673 Loop *L = LI.getLoopFor(Header); 674 EXPECT_NE(L, nullptr); 675 676 Optional<Loop::LoopBounds> Bounds = L->getBounds(SE); 677 EXPECT_NE(Bounds, None); 678 ConstantInt *InitialIVValue = 679 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue()); 680 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); 681 EXPECT_EQ(Bounds->getStepInst().getName(), "inc"); 682 ConstantInt *StepValue = 683 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue()); 684 EXPECT_TRUE(StepValue && StepValue->isOne()); 685 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub"); 686 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_ULT); 687 EXPECT_EQ(Bounds->getDirection(), 688 Loop::LoopBounds::Direction::Increasing); 689 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); 690 EXPECT_EQ(L->getLoopGuardBranch(), Guard); 691 EXPECT_TRUE(L->isGuarded()); 692 }); 693 } 694 695 TEST(LoopInfoTest, DecreasingLoop) { 696 const char *ModuleStr = 697 "define void @foo(i32* %A, i32 %ub) {\n" 698 "entry:\n" 699 " %guardcmp = icmp slt i32 0, %ub\n" 700 " br i1 %guardcmp, label %for.preheader, label %for.end\n" 701 "for.preheader:\n" 702 " br label %for.body\n" 703 "for.body:\n" 704 " %i = phi i32 [ %ub, %for.preheader ], [ %inc, %for.body ]\n" 705 " %idxprom = sext i32 %i to i64\n" 706 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" 707 " store i32 %i, i32* %arrayidx, align 4\n" 708 " %inc = sub nsw i32 %i, 1\n" 709 " %cmp = icmp sgt i32 %inc, 0\n" 710 " br i1 %cmp, label %for.body, label %for.exit\n" 711 "for.exit:\n" 712 " br label %for.end\n" 713 "for.end:\n" 714 " ret void\n" 715 "}\n"; 716 717 // Parse the module. 718 LLVMContext Context; 719 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 720 721 runWithLoopInfoPlus( 722 *M, "foo", 723 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 724 Function::iterator FI = F.begin(); 725 BasicBlock *Entry = &*(FI); 726 BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator()); 727 // First two basic block are entry and for.preheader - skip them. 728 ++FI; 729 BasicBlock *Header = &*(++FI); 730 assert(Header->getName() == "for.body"); 731 Loop *L = LI.getLoopFor(Header); 732 EXPECT_NE(L, nullptr); 733 734 Optional<Loop::LoopBounds> Bounds = L->getBounds(SE); 735 EXPECT_NE(Bounds, None); 736 EXPECT_EQ(Bounds->getInitialIVValue().getName(), "ub"); 737 EXPECT_EQ(Bounds->getStepInst().getName(), "inc"); 738 ConstantInt *StepValue = 739 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue()); 740 EXPECT_EQ(StepValue, nullptr); 741 ConstantInt *FinalIVValue = 742 dyn_cast<ConstantInt>(&Bounds->getFinalIVValue()); 743 EXPECT_TRUE(FinalIVValue && FinalIVValue->isZero()); 744 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SGT); 745 EXPECT_EQ(Bounds->getDirection(), 746 Loop::LoopBounds::Direction::Decreasing); 747 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); 748 EXPECT_EQ(L->getLoopGuardBranch(), Guard); 749 EXPECT_TRUE(L->isGuarded()); 750 }); 751 } 752 753 TEST(LoopInfoTest, CannotFindDirection) { 754 const char *ModuleStr = 755 "define void @foo(i32* %A, i32 %ub, i32 %step) {\n" 756 "entry:\n" 757 " %guardcmp = icmp slt i32 0, %ub\n" 758 " br i1 %guardcmp, label %for.preheader, label %for.end\n" 759 "for.preheader:\n" 760 " br label %for.body\n" 761 "for.body:\n" 762 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n" 763 " %idxprom = sext i32 %i to i64\n" 764 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" 765 " store i32 %i, i32* %arrayidx, align 4\n" 766 " %inc = add nsw i32 %i, %step\n" 767 " %cmp = icmp ne i32 %i, %ub\n" 768 " br i1 %cmp, label %for.body, label %for.exit\n" 769 "for.exit:\n" 770 " br label %for.end\n" 771 "for.end:\n" 772 " ret void\n" 773 "}\n"; 774 775 // Parse the module. 776 LLVMContext Context; 777 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 778 779 runWithLoopInfoPlus( 780 *M, "foo", 781 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 782 Function::iterator FI = F.begin(); 783 BasicBlock *Entry = &*(FI); 784 BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator()); 785 // First two basic block are entry and for.preheader 786 // - skip them. 787 ++FI; 788 BasicBlock *Header = &*(++FI); 789 assert(Header->getName() == "for.body"); 790 Loop *L = LI.getLoopFor(Header); 791 EXPECT_NE(L, nullptr); 792 793 Optional<Loop::LoopBounds> Bounds = L->getBounds(SE); 794 EXPECT_NE(Bounds, None); 795 ConstantInt *InitialIVValue = 796 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue()); 797 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); 798 EXPECT_EQ(Bounds->getStepInst().getName(), "inc"); 799 EXPECT_EQ(Bounds->getStepValue()->getName(), "step"); 800 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub"); 801 EXPECT_EQ(Bounds->getCanonicalPredicate(), 802 ICmpInst::BAD_ICMP_PREDICATE); 803 EXPECT_EQ(Bounds->getDirection(), Loop::LoopBounds::Direction::Unknown); 804 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); 805 EXPECT_EQ(L->getLoopGuardBranch(), Guard); 806 EXPECT_TRUE(L->isGuarded()); 807 }); 808 } 809 810 TEST(LoopInfoTest, ZextIndVar) { 811 const char *ModuleStr = 812 "define void @foo(i32* %A, i32 %ub) {\n" 813 "entry:\n" 814 " %guardcmp = icmp slt i32 0, %ub\n" 815 " br i1 %guardcmp, label %for.preheader, label %for.end\n" 816 "for.preheader:\n" 817 " br label %for.body\n" 818 "for.body:\n" 819 " %indvars.iv = phi i64 [ 0, %for.preheader ], [ %indvars.iv.next, %for.body ]\n" 820 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n" 821 " %idxprom = sext i32 %i to i64\n" 822 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" 823 " store i32 %i, i32* %arrayidx, align 4\n" 824 " %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1\n" 825 " %inc = add nsw i32 %i, 1\n" 826 " %wide.trip.count = zext i32 %ub to i64\n" 827 " %exitcond = icmp ne i64 %indvars.iv.next, %wide.trip.count\n" 828 " br i1 %exitcond, label %for.body, label %for.exit\n" 829 "for.exit:\n" 830 " br label %for.end\n" 831 "for.end:\n" 832 " ret void\n" 833 "}\n"; 834 835 // Parse the module. 836 LLVMContext Context; 837 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 838 839 runWithLoopInfoPlus( 840 *M, "foo", 841 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 842 Function::iterator FI = F.begin(); 843 BasicBlock *Entry = &*(FI); 844 BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator()); 845 // First two basic block are entry and for.preheader - skip them. 846 ++FI; 847 BasicBlock *Header = &*(++FI); 848 assert(Header->getName() == "for.body"); 849 Loop *L = LI.getLoopFor(Header); 850 EXPECT_NE(L, nullptr); 851 852 Optional<Loop::LoopBounds> Bounds = L->getBounds(SE); 853 EXPECT_NE(Bounds, None); 854 ConstantInt *InitialIVValue = 855 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue()); 856 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); 857 EXPECT_EQ(Bounds->getStepInst().getName(), "indvars.iv.next"); 858 ConstantInt *StepValue = 859 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue()); 860 EXPECT_TRUE(StepValue && StepValue->isOne()); 861 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "wide.trip.count"); 862 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_NE); 863 EXPECT_EQ(Bounds->getDirection(), 864 Loop::LoopBounds::Direction::Increasing); 865 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "indvars.iv"); 866 EXPECT_EQ(L->getLoopGuardBranch(), Guard); 867 EXPECT_TRUE(L->isGuarded()); 868 }); 869 } 870 871 TEST(LoopInfoTest, MultiExitingLoop) { 872 const char *ModuleStr = 873 "define void @foo(i32* %A, i32 %ub, i1 %cond) {\n" 874 "entry:\n" 875 " %guardcmp = icmp slt i32 0, %ub\n" 876 " br i1 %guardcmp, label %for.preheader, label %for.end\n" 877 "for.preheader:\n" 878 " br label %for.body\n" 879 "for.body:\n" 880 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body.1 ]\n" 881 " br i1 %cond, label %for.body.1, label %for.exit\n" 882 "for.body.1:\n" 883 " %idxprom = sext i32 %i to i64\n" 884 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" 885 " store i32 %i, i32* %arrayidx, align 4\n" 886 " %inc = add nsw i32 %i, 1\n" 887 " %cmp = icmp slt i32 %inc, %ub\n" 888 " br i1 %cmp, label %for.body, label %for.exit\n" 889 "for.exit:\n" 890 " br label %for.end\n" 891 "for.end:\n" 892 " ret void\n" 893 "}\n"; 894 895 // Parse the module. 896 LLVMContext Context; 897 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 898 899 runWithLoopInfoPlus( 900 *M, "foo", 901 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 902 Function::iterator FI = F.begin(); 903 BasicBlock *Entry = &*(FI); 904 BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator()); 905 // First two basic block are entry and for.preheader - skip them. 906 ++FI; 907 BasicBlock *Header = &*(++FI); 908 assert(Header->getName() == "for.body"); 909 Loop *L = LI.getLoopFor(Header); 910 EXPECT_NE(L, nullptr); 911 912 Optional<Loop::LoopBounds> Bounds = L->getBounds(SE); 913 EXPECT_NE(Bounds, None); 914 ConstantInt *InitialIVValue = 915 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue()); 916 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); 917 EXPECT_EQ(Bounds->getStepInst().getName(), "inc"); 918 ConstantInt *StepValue = 919 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue()); 920 EXPECT_TRUE(StepValue && StepValue->isOne()); 921 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub"); 922 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT); 923 EXPECT_EQ(Bounds->getDirection(), 924 Loop::LoopBounds::Direction::Increasing); 925 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); 926 EXPECT_EQ(L->getLoopGuardBranch(), Guard); 927 EXPECT_TRUE(L->isGuarded()); 928 }); 929 } 930 931 TEST(LoopInfoTest, MultiExitLoop) { 932 const char *ModuleStr = 933 "define void @foo(i32* %A, i32 %ub, i1 %cond) {\n" 934 "entry:\n" 935 " %guardcmp = icmp slt i32 0, %ub\n" 936 " br i1 %guardcmp, label %for.preheader, label %for.end\n" 937 "for.preheader:\n" 938 " br label %for.body\n" 939 "for.body:\n" 940 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body.1 ]\n" 941 " br i1 %cond, label %for.body.1, label %for.exit\n" 942 "for.body.1:\n" 943 " %idxprom = sext i32 %i to i64\n" 944 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" 945 " store i32 %i, i32* %arrayidx, align 4\n" 946 " %inc = add nsw i32 %i, 1\n" 947 " %cmp = icmp slt i32 %inc, %ub\n" 948 " br i1 %cmp, label %for.body, label %for.exit.1\n" 949 "for.exit:\n" 950 " br label %for.end\n" 951 "for.exit.1:\n" 952 " br label %for.end\n" 953 "for.end:\n" 954 " ret void\n" 955 "}\n"; 956 957 // Parse the module. 958 LLVMContext Context; 959 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 960 961 runWithLoopInfoPlus( 962 *M, "foo", 963 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 964 Function::iterator FI = F.begin(); 965 // First two basic block are entry and for.preheader - skip them. 966 ++FI; 967 BasicBlock *Header = &*(++FI); 968 assert(Header->getName() == "for.body"); 969 Loop *L = LI.getLoopFor(Header); 970 EXPECT_NE(L, nullptr); 971 972 Optional<Loop::LoopBounds> Bounds = L->getBounds(SE); 973 EXPECT_NE(Bounds, None); 974 ConstantInt *InitialIVValue = 975 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue()); 976 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); 977 EXPECT_EQ(Bounds->getStepInst().getName(), "inc"); 978 ConstantInt *StepValue = 979 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue()); 980 EXPECT_TRUE(StepValue && StepValue->isOne()); 981 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub"); 982 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT); 983 EXPECT_EQ(Bounds->getDirection(), 984 Loop::LoopBounds::Direction::Increasing); 985 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); 986 EXPECT_EQ(L->getLoopGuardBranch(), nullptr); 987 EXPECT_FALSE(L->isGuarded()); 988 }); 989 } 990 991 TEST(LoopInfoTest, UnguardedLoop) { 992 const char *ModuleStr = 993 "define void @foo(i32* %A, i32 %ub) {\n" 994 "entry:\n" 995 " br label %for.body\n" 996 "for.body:\n" 997 " %i = phi i32 [ 0, %entry ], [ %inc, %for.body ]\n" 998 " %idxprom = sext i32 %i to i64\n" 999 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" 1000 " store i32 %i, i32* %arrayidx, align 4\n" 1001 " %inc = add nsw i32 %i, 1\n" 1002 " %cmp = icmp slt i32 %inc, %ub\n" 1003 " br i1 %cmp, label %for.body, label %for.exit\n" 1004 "for.exit:\n" 1005 " br label %for.end\n" 1006 "for.end:\n" 1007 " ret void\n" 1008 "}\n"; 1009 1010 // Parse the module. 1011 LLVMContext Context; 1012 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 1013 1014 runWithLoopInfoPlus( 1015 *M, "foo", 1016 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1017 Function::iterator FI = F.begin(); 1018 // First basic block is entry - skip it. 1019 BasicBlock *Header = &*(++FI); 1020 assert(Header->getName() == "for.body"); 1021 Loop *L = LI.getLoopFor(Header); 1022 EXPECT_NE(L, nullptr); 1023 1024 Optional<Loop::LoopBounds> Bounds = L->getBounds(SE); 1025 EXPECT_NE(Bounds, None); 1026 ConstantInt *InitialIVValue = 1027 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue()); 1028 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); 1029 EXPECT_EQ(Bounds->getStepInst().getName(), "inc"); 1030 ConstantInt *StepValue = 1031 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue()); 1032 EXPECT_TRUE(StepValue && StepValue->isOne()); 1033 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub"); 1034 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT); 1035 EXPECT_EQ(Bounds->getDirection(), 1036 Loop::LoopBounds::Direction::Increasing); 1037 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); 1038 EXPECT_EQ(L->getLoopGuardBranch(), nullptr); 1039 EXPECT_FALSE(L->isGuarded()); 1040 }); 1041 } 1042 1043 TEST(LoopInfoTest, UnguardedLoopWithControlFlow) { 1044 const char *ModuleStr = 1045 "define void @foo(i32* %A, i32 %ub, i1 %cond) {\n" 1046 "entry:\n" 1047 " br i1 %cond, label %for.preheader, label %for.end\n" 1048 "for.preheader:\n" 1049 " br label %for.body\n" 1050 "for.body:\n" 1051 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n" 1052 " %idxprom = sext i32 %i to i64\n" 1053 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" 1054 " store i32 %i, i32* %arrayidx, align 4\n" 1055 " %inc = add nsw i32 %i, 1\n" 1056 " %cmp = icmp slt i32 %inc, %ub\n" 1057 " br i1 %cmp, label %for.body, label %for.exit\n" 1058 "for.exit:\n" 1059 " br label %for.end\n" 1060 "for.end:\n" 1061 " ret void\n" 1062 "}\n"; 1063 1064 // Parse the module. 1065 LLVMContext Context; 1066 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 1067 1068 runWithLoopInfoPlus( 1069 *M, "foo", 1070 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1071 Function::iterator FI = F.begin(); 1072 BasicBlock *Entry = &*(FI); 1073 BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator()); 1074 // First two basic block are entry and for.preheader - skip them. 1075 ++FI; 1076 BasicBlock *Header = &*(++FI); 1077 assert(Header->getName() == "for.body"); 1078 Loop *L = LI.getLoopFor(Header); 1079 EXPECT_NE(L, nullptr); 1080 1081 Optional<Loop::LoopBounds> Bounds = L->getBounds(SE); 1082 EXPECT_NE(Bounds, None); 1083 ConstantInt *InitialIVValue = 1084 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue()); 1085 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); 1086 EXPECT_EQ(Bounds->getStepInst().getName(), "inc"); 1087 ConstantInt *StepValue = 1088 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue()); 1089 EXPECT_TRUE(StepValue && StepValue->isOne()); 1090 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub"); 1091 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT); 1092 EXPECT_EQ(Bounds->getDirection(), 1093 Loop::LoopBounds::Direction::Increasing); 1094 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); 1095 EXPECT_EQ(L->getLoopGuardBranch(), Guard); 1096 EXPECT_TRUE(L->isGuarded()); 1097 }); 1098 } 1099 1100 TEST(LoopInfoTest, LoopNest) { 1101 const char *ModuleStr = 1102 "define void @foo(i32* %A, i32 %ub) {\n" 1103 "entry:\n" 1104 " %guardcmp = icmp slt i32 0, %ub\n" 1105 " br i1 %guardcmp, label %for.outer.preheader, label %for.end\n" 1106 "for.outer.preheader:\n" 1107 " br label %for.outer\n" 1108 "for.outer:\n" 1109 " %j = phi i32 [ 0, %for.outer.preheader ], [ %inc.outer, %for.outer.latch ]\n" 1110 " br i1 %guardcmp, label %for.inner.preheader, label %for.outer.latch\n" 1111 "for.inner.preheader:\n" 1112 " br label %for.inner\n" 1113 "for.inner:\n" 1114 " %i = phi i32 [ 0, %for.inner.preheader ], [ %inc, %for.inner ]\n" 1115 " %idxprom = sext i32 %i to i64\n" 1116 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" 1117 " store i32 %i, i32* %arrayidx, align 4\n" 1118 " %inc = add nsw i32 %i, 1\n" 1119 " %cmp = icmp slt i32 %inc, %ub\n" 1120 " br i1 %cmp, label %for.inner, label %for.inner.exit\n" 1121 "for.inner.exit:\n" 1122 " br label %for.outer.latch\n" 1123 "for.outer.latch:\n" 1124 " %inc.outer = add nsw i32 %j, 1\n" 1125 " %cmp.outer = icmp slt i32 %inc.outer, %ub\n" 1126 " br i1 %cmp.outer, label %for.outer, label %for.outer.exit\n" 1127 "for.outer.exit:\n" 1128 " br label %for.end\n" 1129 "for.end:\n" 1130 " ret void\n" 1131 "}\n"; 1132 1133 // Parse the module. 1134 LLVMContext Context; 1135 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 1136 1137 runWithLoopInfoPlus( 1138 *M, "foo", 1139 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1140 Function::iterator FI = F.begin(); 1141 BasicBlock *Entry = &*(FI); 1142 BranchInst *OuterGuard = dyn_cast<BranchInst>(Entry->getTerminator()); 1143 // First two basic block are entry and for.outer.preheader - skip them. 1144 ++FI; 1145 BasicBlock *Header = &*(++FI); 1146 assert(Header->getName() == "for.outer"); 1147 BranchInst *InnerGuard = dyn_cast<BranchInst>(Header->getTerminator()); 1148 Loop *L = LI.getLoopFor(Header); 1149 EXPECT_NE(L, nullptr); 1150 1151 Optional<Loop::LoopBounds> Bounds = L->getBounds(SE); 1152 EXPECT_NE(Bounds, None); 1153 ConstantInt *InitialIVValue = 1154 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue()); 1155 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); 1156 EXPECT_EQ(Bounds->getStepInst().getName(), "inc.outer"); 1157 ConstantInt *StepValue = 1158 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue()); 1159 EXPECT_TRUE(StepValue && StepValue->isOne()); 1160 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub"); 1161 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT); 1162 EXPECT_EQ(Bounds->getDirection(), 1163 Loop::LoopBounds::Direction::Increasing); 1164 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "j"); 1165 EXPECT_EQ(L->getLoopGuardBranch(), OuterGuard); 1166 EXPECT_TRUE(L->isGuarded()); 1167 1168 // Next two basic blocks are for.outer and for.inner.preheader - skip 1169 // them. 1170 ++FI; 1171 Header = &*(++FI); 1172 assert(Header->getName() == "for.inner"); 1173 L = LI.getLoopFor(Header); 1174 EXPECT_NE(L, nullptr); 1175 1176 Optional<Loop::LoopBounds> InnerBounds = L->getBounds(SE); 1177 EXPECT_NE(InnerBounds, None); 1178 InitialIVValue = 1179 dyn_cast<ConstantInt>(&InnerBounds->getInitialIVValue()); 1180 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); 1181 EXPECT_EQ(InnerBounds->getStepInst().getName(), "inc"); 1182 StepValue = dyn_cast_or_null<ConstantInt>(InnerBounds->getStepValue()); 1183 EXPECT_TRUE(StepValue && StepValue->isOne()); 1184 EXPECT_EQ(InnerBounds->getFinalIVValue().getName(), "ub"); 1185 EXPECT_EQ(InnerBounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT); 1186 EXPECT_EQ(InnerBounds->getDirection(), 1187 Loop::LoopBounds::Direction::Increasing); 1188 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); 1189 EXPECT_EQ(L->getLoopGuardBranch(), InnerGuard); 1190 EXPECT_TRUE(L->isGuarded()); 1191 }); 1192 } 1193 1194 TEST(LoopInfoTest, AuxiliaryIV) { 1195 const char *ModuleStr = 1196 "define void @foo(i32* %A, i32 %ub) {\n" 1197 "entry:\n" 1198 " %guardcmp = icmp slt i32 0, %ub\n" 1199 " br i1 %guardcmp, label %for.preheader, label %for.end\n" 1200 "for.preheader:\n" 1201 " br label %for.body\n" 1202 "for.body:\n" 1203 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n" 1204 " %aux = phi i32 [ 0, %for.preheader ], [ %auxinc, %for.body ]\n" 1205 " %loopvariant = phi i32 [ 0, %for.preheader ], [ %loopvariantinc, %for.body ]\n" 1206 " %usedoutside = phi i32 [ 0, %for.preheader ], [ %usedoutsideinc, %for.body ]\n" 1207 " %mulopcode = phi i32 [ 0, %for.preheader ], [ %mulopcodeinc, %for.body ]\n" 1208 " %idxprom = sext i32 %i to i64\n" 1209 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" 1210 " store i32 %i, i32* %arrayidx, align 4\n" 1211 " %mulopcodeinc = mul nsw i32 %mulopcode, 5\n" 1212 " %usedoutsideinc = add nsw i32 %usedoutside, 5\n" 1213 " %loopvariantinc = add nsw i32 %loopvariant, %i\n" 1214 " %auxinc = add nsw i32 %aux, 5\n" 1215 " %inc = add nsw i32 %i, 1\n" 1216 " %cmp = icmp slt i32 %inc, %ub\n" 1217 " br i1 %cmp, label %for.body, label %for.exit\n" 1218 "for.exit:\n" 1219 " %lcssa = phi i32 [ %usedoutside, %for.body ]\n" 1220 " br label %for.end\n" 1221 "for.end:\n" 1222 " ret void\n" 1223 "}\n"; 1224 1225 // Parse the module. 1226 LLVMContext Context; 1227 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 1228 1229 runWithLoopInfoPlus( 1230 *M, "foo", 1231 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1232 Function::iterator FI = F.begin(); 1233 BasicBlock *Entry = &*(FI); 1234 BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator()); 1235 // First two basic block are entry and for.preheader - skip them. 1236 ++FI; 1237 BasicBlock *Header = &*(++FI); 1238 assert(Header->getName() == "for.body"); 1239 Loop *L = LI.getLoopFor(Header); 1240 EXPECT_NE(L, nullptr); 1241 1242 Optional<Loop::LoopBounds> Bounds = L->getBounds(SE); 1243 EXPECT_NE(Bounds, None); 1244 ConstantInt *InitialIVValue = 1245 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue()); 1246 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); 1247 EXPECT_EQ(Bounds->getStepInst().getName(), "inc"); 1248 ConstantInt *StepValue = 1249 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue()); 1250 EXPECT_TRUE(StepValue && StepValue->isOne()); 1251 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub"); 1252 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT); 1253 EXPECT_EQ(Bounds->getDirection(), 1254 Loop::LoopBounds::Direction::Increasing); 1255 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); 1256 BasicBlock::iterator II = Header->begin(); 1257 PHINode &Instruction_i = cast<PHINode>(*(II)); 1258 EXPECT_TRUE(L->isAuxiliaryInductionVariable(Instruction_i, SE)); 1259 PHINode &Instruction_aux = cast<PHINode>(*(++II)); 1260 EXPECT_TRUE(L->isAuxiliaryInductionVariable(Instruction_aux, SE)); 1261 PHINode &Instruction_loopvariant = cast<PHINode>(*(++II)); 1262 EXPECT_FALSE( 1263 L->isAuxiliaryInductionVariable(Instruction_loopvariant, SE)); 1264 PHINode &Instruction_usedoutside = cast<PHINode>(*(++II)); 1265 EXPECT_FALSE( 1266 L->isAuxiliaryInductionVariable(Instruction_usedoutside, SE)); 1267 PHINode &Instruction_mulopcode = cast<PHINode>(*(++II)); 1268 EXPECT_FALSE( 1269 L->isAuxiliaryInductionVariable(Instruction_mulopcode, SE)); 1270 EXPECT_EQ(L->getLoopGuardBranch(), Guard); 1271 EXPECT_TRUE(L->isGuarded()); 1272 }); 1273 } 1274 1275 // Examine getUniqueExitBlocks/getUniqueNonLatchExitBlocks functions. 1276 TEST(LoopInfoTest, LoopUniqueExitBlocks) { 1277 const char *ModuleStr = 1278 "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n" 1279 "define void @foo(i32 %n, i1 %cond) {\n" 1280 "entry:\n" 1281 " br label %for.cond\n" 1282 "for.cond:\n" 1283 " %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]\n" 1284 " %cmp = icmp slt i32 %i.0, %n\n" 1285 " br i1 %cond, label %for.inc, label %for.end1\n" 1286 "for.inc:\n" 1287 " %inc = add nsw i32 %i.0, 1\n" 1288 " br i1 %cmp, label %for.cond, label %for.end2, !llvm.loop !0\n" 1289 "for.end1:\n" 1290 " br label %for.end\n" 1291 "for.end2:\n" 1292 " br label %for.end\n" 1293 "for.end:\n" 1294 " ret void\n" 1295 "}\n" 1296 "!0 = distinct !{!0, !1}\n" 1297 "!1 = !{!\"llvm.loop.distribute.enable\", i1 true}\n"; 1298 1299 // Parse the module. 1300 LLVMContext Context; 1301 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 1302 1303 runWithLoopInfo(*M, "foo", [&](Function &F, LoopInfo &LI) { 1304 Function::iterator FI = F.begin(); 1305 // First basic block is entry - skip it. 1306 BasicBlock *Header = &*(++FI); 1307 assert(Header->getName() == "for.cond"); 1308 Loop *L = LI.getLoopFor(Header); 1309 1310 SmallVector<BasicBlock *, 2> Exits; 1311 // This loop has 2 unique exits. 1312 L->getUniqueExitBlocks(Exits); 1313 EXPECT_TRUE(Exits.size() == 2); 1314 // And one unique non latch exit. 1315 Exits.clear(); 1316 L->getUniqueNonLatchExitBlocks(Exits); 1317 EXPECT_TRUE(Exits.size() == 1); 1318 }); 1319 } 1320 1321 // Regression test for getUniqueNonLatchExitBlocks functions. 1322 // It should detect the exit if it comes from both latch and non-latch blocks. 1323 TEST(LoopInfoTest, LoopNonLatchUniqueExitBlocks) { 1324 const char *ModuleStr = 1325 "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n" 1326 "define void @foo(i32 %n, i1 %cond) {\n" 1327 "entry:\n" 1328 " br label %for.cond\n" 1329 "for.cond:\n" 1330 " %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]\n" 1331 " %cmp = icmp slt i32 %i.0, %n\n" 1332 " br i1 %cond, label %for.inc, label %for.end\n" 1333 "for.inc:\n" 1334 " %inc = add nsw i32 %i.0, 1\n" 1335 " br i1 %cmp, label %for.cond, label %for.end, !llvm.loop !0\n" 1336 "for.end:\n" 1337 " ret void\n" 1338 "}\n" 1339 "!0 = distinct !{!0, !1}\n" 1340 "!1 = !{!\"llvm.loop.distribute.enable\", i1 true}\n"; 1341 1342 // Parse the module. 1343 LLVMContext Context; 1344 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 1345 1346 runWithLoopInfo(*M, "foo", [&](Function &F, LoopInfo &LI) { 1347 Function::iterator FI = F.begin(); 1348 // First basic block is entry - skip it. 1349 BasicBlock *Header = &*(++FI); 1350 assert(Header->getName() == "for.cond"); 1351 Loop *L = LI.getLoopFor(Header); 1352 1353 SmallVector<BasicBlock *, 2> Exits; 1354 // This loop has 1 unique exit. 1355 L->getUniqueExitBlocks(Exits); 1356 EXPECT_TRUE(Exits.size() == 1); 1357 // And one unique non latch exit. 1358 Exits.clear(); 1359 L->getUniqueNonLatchExitBlocks(Exits); 1360 EXPECT_TRUE(Exits.size() == 1); 1361 }); 1362 } 1363