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, UnguardedLoop) { 872 const char *ModuleStr = 873 "define void @foo(i32* %A, i32 %ub) {\n" 874 "entry:\n" 875 " br label %for.body\n" 876 "for.body:\n" 877 " %i = phi i32 [ 0, %entry ], [ %inc, %for.body ]\n" 878 " %idxprom = sext i32 %i to i64\n" 879 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" 880 " store i32 %i, i32* %arrayidx, align 4\n" 881 " %inc = add nsw i32 %i, 1\n" 882 " %cmp = icmp slt i32 %inc, %ub\n" 883 " br i1 %cmp, label %for.body, label %for.exit\n" 884 "for.exit:\n" 885 " br label %for.end\n" 886 "for.end:\n" 887 " ret void\n" 888 "}\n"; 889 890 // Parse the module. 891 LLVMContext Context; 892 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 893 894 runWithLoopInfoPlus( 895 *M, "foo", 896 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 897 Function::iterator FI = F.begin(); 898 // First basic block is entry - skip it. 899 BasicBlock *Header = &*(++FI); 900 assert(Header->getName() == "for.body"); 901 Loop *L = LI.getLoopFor(Header); 902 EXPECT_NE(L, nullptr); 903 904 Optional<Loop::LoopBounds> Bounds = L->getBounds(SE); 905 EXPECT_NE(Bounds, None); 906 ConstantInt *InitialIVValue = 907 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue()); 908 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); 909 EXPECT_EQ(Bounds->getStepInst().getName(), "inc"); 910 ConstantInt *StepValue = 911 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue()); 912 EXPECT_TRUE(StepValue && StepValue->isOne()); 913 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub"); 914 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT); 915 EXPECT_EQ(Bounds->getDirection(), 916 Loop::LoopBounds::Direction::Increasing); 917 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); 918 EXPECT_EQ(L->getLoopGuardBranch(), nullptr); 919 EXPECT_FALSE(L->isGuarded()); 920 }); 921 } 922 923 TEST(LoopInfoTest, UnguardedLoopWithControlFlow) { 924 const char *ModuleStr = 925 "define void @foo(i32* %A, i32 %ub, i1 %cond) {\n" 926 "entry:\n" 927 " br i1 %cond, label %for.preheader, label %for.end\n" 928 "for.preheader:\n" 929 " br label %for.body\n" 930 "for.body:\n" 931 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n" 932 " %idxprom = sext i32 %i to i64\n" 933 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" 934 " store i32 %i, i32* %arrayidx, align 4\n" 935 " %inc = add nsw i32 %i, 1\n" 936 " %cmp = icmp slt i32 %inc, %ub\n" 937 " br i1 %cmp, label %for.body, label %for.exit\n" 938 "for.exit:\n" 939 " br label %for.end\n" 940 "for.end:\n" 941 " ret void\n" 942 "}\n"; 943 944 // Parse the module. 945 LLVMContext Context; 946 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 947 948 runWithLoopInfoPlus( 949 *M, "foo", 950 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 951 Function::iterator FI = F.begin(); 952 BasicBlock *Entry = &*(FI); 953 BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator()); 954 // First two basic block are entry and for.preheader - skip them. 955 ++FI; 956 BasicBlock *Header = &*(++FI); 957 assert(Header->getName() == "for.body"); 958 Loop *L = LI.getLoopFor(Header); 959 EXPECT_NE(L, nullptr); 960 961 Optional<Loop::LoopBounds> Bounds = L->getBounds(SE); 962 EXPECT_NE(Bounds, None); 963 ConstantInt *InitialIVValue = 964 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue()); 965 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); 966 EXPECT_EQ(Bounds->getStepInst().getName(), "inc"); 967 ConstantInt *StepValue = 968 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue()); 969 EXPECT_TRUE(StepValue && StepValue->isOne()); 970 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub"); 971 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT); 972 EXPECT_EQ(Bounds->getDirection(), 973 Loop::LoopBounds::Direction::Increasing); 974 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); 975 EXPECT_EQ(L->getLoopGuardBranch(), Guard); 976 EXPECT_TRUE(L->isGuarded()); 977 }); 978 } 979 980 TEST(LoopInfoTest, LoopNest) { 981 const char *ModuleStr = 982 "define void @foo(i32* %A, i32 %ub) {\n" 983 "entry:\n" 984 " %guardcmp = icmp slt i32 0, %ub\n" 985 " br i1 %guardcmp, label %for.outer.preheader, label %for.end\n" 986 "for.outer.preheader:\n" 987 " br label %for.outer\n" 988 "for.outer:\n" 989 " %j = phi i32 [ 0, %for.outer.preheader ], [ %inc.outer, %for.outer.latch ]\n" 990 " br i1 %guardcmp, label %for.inner.preheader, label %for.outer.latch\n" 991 "for.inner.preheader:\n" 992 " br label %for.inner\n" 993 "for.inner:\n" 994 " %i = phi i32 [ 0, %for.inner.preheader ], [ %inc, %for.inner ]\n" 995 " %idxprom = sext i32 %i to i64\n" 996 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" 997 " store i32 %i, i32* %arrayidx, align 4\n" 998 " %inc = add nsw i32 %i, 1\n" 999 " %cmp = icmp slt i32 %inc, %ub\n" 1000 " br i1 %cmp, label %for.inner, label %for.inner.exit\n" 1001 "for.inner.exit:\n" 1002 " br label %for.outer.latch\n" 1003 "for.outer.latch:\n" 1004 " %inc.outer = add nsw i32 %j, 1\n" 1005 " %cmp.outer = icmp slt i32 %inc.outer, %ub\n" 1006 " br i1 %cmp.outer, label %for.outer, label %for.outer.exit\n" 1007 "for.outer.exit:\n" 1008 " br label %for.end\n" 1009 "for.end:\n" 1010 " ret void\n" 1011 "}\n"; 1012 1013 // Parse the module. 1014 LLVMContext Context; 1015 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 1016 1017 runWithLoopInfoPlus( 1018 *M, "foo", 1019 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1020 Function::iterator FI = F.begin(); 1021 BasicBlock *Entry = &*(FI); 1022 BranchInst *OuterGuard = dyn_cast<BranchInst>(Entry->getTerminator()); 1023 // First two basic block are entry and for.outer.preheader - skip them. 1024 ++FI; 1025 BasicBlock *Header = &*(++FI); 1026 assert(Header->getName() == "for.outer"); 1027 BranchInst *InnerGuard = dyn_cast<BranchInst>(Header->getTerminator()); 1028 Loop *L = LI.getLoopFor(Header); 1029 EXPECT_NE(L, nullptr); 1030 1031 Optional<Loop::LoopBounds> Bounds = L->getBounds(SE); 1032 EXPECT_NE(Bounds, None); 1033 ConstantInt *InitialIVValue = 1034 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue()); 1035 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); 1036 EXPECT_EQ(Bounds->getStepInst().getName(), "inc.outer"); 1037 ConstantInt *StepValue = 1038 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue()); 1039 EXPECT_TRUE(StepValue && StepValue->isOne()); 1040 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub"); 1041 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT); 1042 EXPECT_EQ(Bounds->getDirection(), 1043 Loop::LoopBounds::Direction::Increasing); 1044 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "j"); 1045 EXPECT_EQ(L->getLoopGuardBranch(), OuterGuard); 1046 EXPECT_TRUE(L->isGuarded()); 1047 1048 // Next two basic blocks are for.outer and for.inner.preheader - skip 1049 // them. 1050 ++FI; 1051 Header = &*(++FI); 1052 assert(Header->getName() == "for.inner"); 1053 L = LI.getLoopFor(Header); 1054 EXPECT_NE(L, nullptr); 1055 1056 Optional<Loop::LoopBounds> InnerBounds = L->getBounds(SE); 1057 EXPECT_NE(InnerBounds, None); 1058 InitialIVValue = 1059 dyn_cast<ConstantInt>(&InnerBounds->getInitialIVValue()); 1060 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); 1061 EXPECT_EQ(InnerBounds->getStepInst().getName(), "inc"); 1062 StepValue = dyn_cast_or_null<ConstantInt>(InnerBounds->getStepValue()); 1063 EXPECT_TRUE(StepValue && StepValue->isOne()); 1064 EXPECT_EQ(InnerBounds->getFinalIVValue().getName(), "ub"); 1065 EXPECT_EQ(InnerBounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT); 1066 EXPECT_EQ(InnerBounds->getDirection(), 1067 Loop::LoopBounds::Direction::Increasing); 1068 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); 1069 EXPECT_EQ(L->getLoopGuardBranch(), InnerGuard); 1070 EXPECT_TRUE(L->isGuarded()); 1071 }); 1072 } 1073 1074 TEST(LoopInfoTest, AuxiliaryIV) { 1075 const char *ModuleStr = 1076 "define void @foo(i32* %A, i32 %ub) {\n" 1077 "entry:\n" 1078 " %guardcmp = icmp slt i32 0, %ub\n" 1079 " br i1 %guardcmp, label %for.preheader, label %for.end\n" 1080 "for.preheader:\n" 1081 " br label %for.body\n" 1082 "for.body:\n" 1083 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n" 1084 " %aux = phi i32 [ 0, %for.preheader ], [ %auxinc, %for.body ]\n" 1085 " %loopvariant = phi i32 [ 0, %for.preheader ], [ %loopvariantinc, %for.body ]\n" 1086 " %usedoutside = phi i32 [ 0, %for.preheader ], [ %usedoutsideinc, %for.body ]\n" 1087 " %mulopcode = phi i32 [ 0, %for.preheader ], [ %mulopcodeinc, %for.body ]\n" 1088 " %idxprom = sext i32 %i to i64\n" 1089 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" 1090 " store i32 %i, i32* %arrayidx, align 4\n" 1091 " %mulopcodeinc = mul nsw i32 %mulopcode, 5\n" 1092 " %usedoutsideinc = add nsw i32 %usedoutside, 5\n" 1093 " %loopvariantinc = add nsw i32 %loopvariant, %i\n" 1094 " %auxinc = add nsw i32 %aux, 5\n" 1095 " %inc = add nsw i32 %i, 1\n" 1096 " %cmp = icmp slt i32 %inc, %ub\n" 1097 " br i1 %cmp, label %for.body, label %for.exit\n" 1098 "for.exit:\n" 1099 " %lcssa = phi i32 [ %usedoutside, %for.body ]\n" 1100 " br label %for.end\n" 1101 "for.end:\n" 1102 " ret void\n" 1103 "}\n"; 1104 1105 // Parse the module. 1106 LLVMContext Context; 1107 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 1108 1109 runWithLoopInfoPlus( 1110 *M, "foo", 1111 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1112 Function::iterator FI = F.begin(); 1113 BasicBlock *Entry = &*(FI); 1114 BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator()); 1115 // First two basic block are entry and for.preheader - skip them. 1116 ++FI; 1117 BasicBlock *Header = &*(++FI); 1118 assert(Header->getName() == "for.body"); 1119 Loop *L = LI.getLoopFor(Header); 1120 EXPECT_NE(L, nullptr); 1121 1122 Optional<Loop::LoopBounds> Bounds = L->getBounds(SE); 1123 EXPECT_NE(Bounds, None); 1124 ConstantInt *InitialIVValue = 1125 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue()); 1126 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); 1127 EXPECT_EQ(Bounds->getStepInst().getName(), "inc"); 1128 ConstantInt *StepValue = 1129 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue()); 1130 EXPECT_TRUE(StepValue && StepValue->isOne()); 1131 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub"); 1132 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT); 1133 EXPECT_EQ(Bounds->getDirection(), 1134 Loop::LoopBounds::Direction::Increasing); 1135 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); 1136 BasicBlock::iterator II = Header->begin(); 1137 PHINode &Instruction_i = cast<PHINode>(*(II)); 1138 EXPECT_TRUE(L->isAuxiliaryInductionVariable(Instruction_i, SE)); 1139 PHINode &Instruction_aux = cast<PHINode>(*(++II)); 1140 EXPECT_TRUE(L->isAuxiliaryInductionVariable(Instruction_aux, SE)); 1141 PHINode &Instruction_loopvariant = cast<PHINode>(*(++II)); 1142 EXPECT_FALSE( 1143 L->isAuxiliaryInductionVariable(Instruction_loopvariant, SE)); 1144 PHINode &Instruction_usedoutside = cast<PHINode>(*(++II)); 1145 EXPECT_FALSE( 1146 L->isAuxiliaryInductionVariable(Instruction_usedoutside, SE)); 1147 PHINode &Instruction_mulopcode = cast<PHINode>(*(++II)); 1148 EXPECT_FALSE( 1149 L->isAuxiliaryInductionVariable(Instruction_mulopcode, SE)); 1150 EXPECT_EQ(L->getLoopGuardBranch(), Guard); 1151 EXPECT_TRUE(L->isGuarded()); 1152 }); 1153 } 1154 1155 // Examine getUniqueExitBlocks/getUniqueNonLatchExitBlocks functions. 1156 TEST(LoopInfoTest, LoopUniqueExitBlocks) { 1157 const char *ModuleStr = 1158 "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n" 1159 "define void @foo(i32 %n, i1 %cond) {\n" 1160 "entry:\n" 1161 " br label %for.cond\n" 1162 "for.cond:\n" 1163 " %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]\n" 1164 " %cmp = icmp slt i32 %i.0, %n\n" 1165 " br i1 %cond, label %for.inc, label %for.end1\n" 1166 "for.inc:\n" 1167 " %inc = add nsw i32 %i.0, 1\n" 1168 " br i1 %cmp, label %for.cond, label %for.end2, !llvm.loop !0\n" 1169 "for.end1:\n" 1170 " br label %for.end\n" 1171 "for.end2:\n" 1172 " br label %for.end\n" 1173 "for.end:\n" 1174 " ret void\n" 1175 "}\n" 1176 "!0 = distinct !{!0, !1}\n" 1177 "!1 = !{!\"llvm.loop.distribute.enable\", i1 true}\n"; 1178 1179 // Parse the module. 1180 LLVMContext Context; 1181 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 1182 1183 runWithLoopInfo(*M, "foo", [&](Function &F, LoopInfo &LI) { 1184 Function::iterator FI = F.begin(); 1185 // First basic block is entry - skip it. 1186 BasicBlock *Header = &*(++FI); 1187 assert(Header->getName() == "for.cond"); 1188 Loop *L = LI.getLoopFor(Header); 1189 1190 SmallVector<BasicBlock *, 2> Exits; 1191 // This loop has 2 unique exits. 1192 L->getUniqueExitBlocks(Exits); 1193 EXPECT_TRUE(Exits.size() == 2); 1194 // And one unique non latch exit. 1195 Exits.clear(); 1196 L->getUniqueNonLatchExitBlocks(Exits); 1197 EXPECT_TRUE(Exits.size() == 1); 1198 }); 1199 } 1200 1201 // Regression test for getUniqueNonLatchExitBlocks functions. 1202 // It should detect the exit if it comes from both latch and non-latch blocks. 1203 TEST(LoopInfoTest, LoopNonLatchUniqueExitBlocks) { 1204 const char *ModuleStr = 1205 "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n" 1206 "define void @foo(i32 %n, i1 %cond) {\n" 1207 "entry:\n" 1208 " br label %for.cond\n" 1209 "for.cond:\n" 1210 " %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]\n" 1211 " %cmp = icmp slt i32 %i.0, %n\n" 1212 " br i1 %cond, label %for.inc, label %for.end\n" 1213 "for.inc:\n" 1214 " %inc = add nsw i32 %i.0, 1\n" 1215 " br i1 %cmp, label %for.cond, label %for.end, !llvm.loop !0\n" 1216 "for.end:\n" 1217 " ret void\n" 1218 "}\n" 1219 "!0 = distinct !{!0, !1}\n" 1220 "!1 = !{!\"llvm.loop.distribute.enable\", i1 true}\n"; 1221 1222 // Parse the module. 1223 LLVMContext Context; 1224 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 1225 1226 runWithLoopInfo(*M, "foo", [&](Function &F, LoopInfo &LI) { 1227 Function::iterator FI = F.begin(); 1228 // First basic block is entry - skip it. 1229 BasicBlock *Header = &*(++FI); 1230 assert(Header->getName() == "for.cond"); 1231 Loop *L = LI.getLoopFor(Header); 1232 1233 SmallVector<BasicBlock *, 2> Exits; 1234 // This loop has 1 unique exit. 1235 L->getUniqueExitBlocks(Exits); 1236 EXPECT_TRUE(Exits.size() == 1); 1237 // And one unique non latch exit. 1238 Exits.clear(); 1239 L->getUniqueNonLatchExitBlocks(Exits); 1240 EXPECT_TRUE(Exits.size() == 1); 1241 }); 1242 } 1243