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 EXPECT_TRUE(L->isRotated()); 289 }); 290 } 291 292 TEST(LoopInfoTest, LoopWithInverseGuardSuccs) { 293 const char *ModuleStr = 294 "define void @foo(i32* %A, i32 %ub) {\n" 295 "entry:\n" 296 " %guardcmp = icmp sge i32 0, %ub\n" 297 " br i1 %guardcmp, label %for.end, label %for.preheader\n" 298 "for.preheader:\n" 299 " br label %for.body\n" 300 "for.body:\n" 301 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n" 302 " %idxprom = sext i32 %i to i64\n" 303 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" 304 " store i32 %i, i32* %arrayidx, align 4\n" 305 " %inc = add nsw i32 %i, 1\n" 306 " %cmp = icmp slt i32 %inc, %ub\n" 307 " br i1 %cmp, label %for.body, label %for.exit\n" 308 "for.exit:\n" 309 " br label %for.end\n" 310 "for.end:\n" 311 " ret void\n" 312 "}\n"; 313 314 // Parse the module. 315 LLVMContext Context; 316 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 317 318 runWithLoopInfoPlus( 319 *M, "foo", 320 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 321 Function::iterator FI = F.begin(); 322 BasicBlock *Entry = &*(FI); 323 BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator()); 324 // First two basic block are entry and for.preheader - skip them. 325 ++FI; 326 BasicBlock *Header = &*(++FI); 327 assert(Header->getName() == "for.body"); 328 Loop *L = LI.getLoopFor(Header); 329 EXPECT_NE(L, nullptr); 330 331 Optional<Loop::LoopBounds> Bounds = L->getBounds(SE); 332 EXPECT_NE(Bounds, None); 333 ConstantInt *InitialIVValue = 334 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue()); 335 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); 336 EXPECT_EQ(Bounds->getStepInst().getName(), "inc"); 337 ConstantInt *StepValue = 338 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue()); 339 EXPECT_TRUE(StepValue && StepValue->isOne()); 340 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub"); 341 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT); 342 EXPECT_EQ(Bounds->getDirection(), 343 Loop::LoopBounds::Direction::Increasing); 344 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); 345 EXPECT_EQ(L->getLoopGuardBranch(), Guard); 346 EXPECT_TRUE(L->isGuarded()); 347 EXPECT_TRUE(L->isRotated()); 348 }); 349 } 350 351 TEST(LoopInfoTest, LoopWithSwappedGuardCmp) { 352 const char *ModuleStr = 353 "define void @foo(i32* %A, i32 %ub) {\n" 354 "entry:\n" 355 " %guardcmp = icmp sgt i32 %ub, 0\n" 356 " br i1 %guardcmp, label %for.preheader, label %for.end\n" 357 "for.preheader:\n" 358 " br label %for.body\n" 359 "for.body:\n" 360 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n" 361 " %idxprom = sext i32 %i to i64\n" 362 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" 363 " store i32 %i, i32* %arrayidx, align 4\n" 364 " %inc = add nsw i32 %i, 1\n" 365 " %cmp = icmp sge i32 %inc, %ub\n" 366 " br i1 %cmp, label %for.exit, label %for.body\n" 367 "for.exit:\n" 368 " br label %for.end\n" 369 "for.end:\n" 370 " ret void\n" 371 "}\n"; 372 373 // Parse the module. 374 LLVMContext Context; 375 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 376 377 runWithLoopInfoPlus( 378 *M, "foo", 379 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 380 Function::iterator FI = F.begin(); 381 BasicBlock *Entry = &*(FI); 382 BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator()); 383 // First two basic block are entry and for.preheader - skip them. 384 ++FI; 385 BasicBlock *Header = &*(++FI); 386 assert(Header->getName() == "for.body"); 387 Loop *L = LI.getLoopFor(Header); 388 EXPECT_NE(L, nullptr); 389 390 Optional<Loop::LoopBounds> Bounds = L->getBounds(SE); 391 EXPECT_NE(Bounds, None); 392 ConstantInt *InitialIVValue = 393 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue()); 394 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); 395 EXPECT_EQ(Bounds->getStepInst().getName(), "inc"); 396 ConstantInt *StepValue = 397 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue()); 398 EXPECT_TRUE(StepValue && StepValue->isOne()); 399 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub"); 400 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT); 401 EXPECT_EQ(Bounds->getDirection(), 402 Loop::LoopBounds::Direction::Increasing); 403 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); 404 EXPECT_EQ(L->getLoopGuardBranch(), Guard); 405 EXPECT_TRUE(L->isGuarded()); 406 EXPECT_TRUE(L->isRotated()); 407 }); 408 } 409 410 TEST(LoopInfoTest, LoopWithInverseLatchSuccs) { 411 const char *ModuleStr = 412 "define void @foo(i32* %A, i32 %ub) {\n" 413 "entry:\n" 414 " %guardcmp = icmp slt i32 0, %ub\n" 415 " br i1 %guardcmp, label %for.preheader, label %for.end\n" 416 "for.preheader:\n" 417 " br label %for.body\n" 418 "for.body:\n" 419 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n" 420 " %idxprom = sext i32 %i to i64\n" 421 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" 422 " store i32 %i, i32* %arrayidx, align 4\n" 423 " %inc = add nsw i32 %i, 1\n" 424 " %cmp = icmp sge i32 %inc, %ub\n" 425 " br i1 %cmp, label %for.exit, label %for.body\n" 426 "for.exit:\n" 427 " br label %for.end\n" 428 "for.end:\n" 429 " ret void\n" 430 "}\n"; 431 432 // Parse the module. 433 LLVMContext Context; 434 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 435 436 runWithLoopInfoPlus( 437 *M, "foo", 438 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 439 Function::iterator FI = F.begin(); 440 BasicBlock *Entry = &*(FI); 441 BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator()); 442 // First two basic block are entry and for.preheader - skip them. 443 ++FI; 444 BasicBlock *Header = &*(++FI); 445 assert(Header->getName() == "for.body"); 446 Loop *L = LI.getLoopFor(Header); 447 EXPECT_NE(L, nullptr); 448 449 Optional<Loop::LoopBounds> Bounds = L->getBounds(SE); 450 EXPECT_NE(Bounds, None); 451 ConstantInt *InitialIVValue = 452 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue()); 453 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); 454 EXPECT_EQ(Bounds->getStepInst().getName(), "inc"); 455 ConstantInt *StepValue = 456 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue()); 457 EXPECT_TRUE(StepValue && StepValue->isOne()); 458 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub"); 459 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT); 460 EXPECT_EQ(Bounds->getDirection(), 461 Loop::LoopBounds::Direction::Increasing); 462 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); 463 EXPECT_EQ(L->getLoopGuardBranch(), Guard); 464 EXPECT_TRUE(L->isGuarded()); 465 EXPECT_TRUE(L->isRotated()); 466 }); 467 } 468 469 TEST(LoopInfoTest, LoopWithLatchCmpNE) { 470 const char *ModuleStr = 471 "define void @foo(i32* %A, i32 %ub) {\n" 472 "entry:\n" 473 " %guardcmp = icmp slt i32 0, %ub\n" 474 " br i1 %guardcmp, label %for.preheader, label %for.end\n" 475 "for.preheader:\n" 476 " br label %for.body\n" 477 "for.body:\n" 478 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n" 479 " %idxprom = sext i32 %i to i64\n" 480 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" 481 " store i32 %i, i32* %arrayidx, align 4\n" 482 " %inc = add nsw i32 %i, 1\n" 483 " %cmp = icmp ne i32 %i, %ub\n" 484 " br i1 %cmp, label %for.body, label %for.exit\n" 485 "for.exit:\n" 486 " br label %for.end\n" 487 "for.end:\n" 488 " ret void\n" 489 "}\n"; 490 491 // Parse the module. 492 LLVMContext Context; 493 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 494 495 runWithLoopInfoPlus( 496 *M, "foo", 497 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 498 Function::iterator FI = F.begin(); 499 BasicBlock *Entry = &*(FI); 500 BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator()); 501 // First two basic block are entry and for.preheader - skip them. 502 ++FI; 503 BasicBlock *Header = &*(++FI); 504 assert(Header->getName() == "for.body"); 505 Loop *L = LI.getLoopFor(Header); 506 EXPECT_NE(L, nullptr); 507 508 Optional<Loop::LoopBounds> Bounds = L->getBounds(SE); 509 EXPECT_NE(Bounds, None); 510 ConstantInt *InitialIVValue = 511 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue()); 512 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); 513 EXPECT_EQ(Bounds->getStepInst().getName(), "inc"); 514 ConstantInt *StepValue = 515 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue()); 516 EXPECT_TRUE(StepValue && StepValue->isOne()); 517 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub"); 518 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT); 519 EXPECT_EQ(Bounds->getDirection(), 520 Loop::LoopBounds::Direction::Increasing); 521 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); 522 EXPECT_EQ(L->getLoopGuardBranch(), Guard); 523 EXPECT_TRUE(L->isGuarded()); 524 EXPECT_TRUE(L->isRotated()); 525 }); 526 } 527 528 TEST(LoopInfoTest, LoopWithGuardCmpSLE) { 529 const char *ModuleStr = 530 "define void @foo(i32* %A, i32 %ub) {\n" 531 "entry:\n" 532 " %ubPlusOne = add i32 %ub, 1\n" 533 " %guardcmp = icmp sle i32 0, %ub\n" 534 " br i1 %guardcmp, label %for.preheader, label %for.end\n" 535 "for.preheader:\n" 536 " br label %for.body\n" 537 "for.body:\n" 538 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n" 539 " %idxprom = sext i32 %i to i64\n" 540 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" 541 " store i32 %i, i32* %arrayidx, align 4\n" 542 " %inc = add nsw i32 %i, 1\n" 543 " %cmp = icmp ne i32 %i, %ubPlusOne\n" 544 " br i1 %cmp, label %for.body, label %for.exit\n" 545 "for.exit:\n" 546 " br label %for.end\n" 547 "for.end:\n" 548 " ret void\n" 549 "}\n"; 550 551 // Parse the module. 552 LLVMContext Context; 553 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 554 555 runWithLoopInfoPlus( 556 *M, "foo", 557 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 558 Function::iterator FI = F.begin(); 559 BasicBlock *Entry = &*(FI); 560 BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator()); 561 // First two basic block are entry and for.preheader - skip them. 562 ++FI; 563 BasicBlock *Header = &*(++FI); 564 assert(Header->getName() == "for.body"); 565 Loop *L = LI.getLoopFor(Header); 566 EXPECT_NE(L, nullptr); 567 568 Optional<Loop::LoopBounds> Bounds = L->getBounds(SE); 569 EXPECT_NE(Bounds, None); 570 ConstantInt *InitialIVValue = 571 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue()); 572 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); 573 EXPECT_EQ(Bounds->getStepInst().getName(), "inc"); 574 ConstantInt *StepValue = 575 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue()); 576 EXPECT_TRUE(StepValue && StepValue->isOne()); 577 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ubPlusOne"); 578 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT); 579 EXPECT_EQ(Bounds->getDirection(), 580 Loop::LoopBounds::Direction::Increasing); 581 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); 582 EXPECT_EQ(L->getLoopGuardBranch(), Guard); 583 EXPECT_TRUE(L->isGuarded()); 584 EXPECT_TRUE(L->isRotated()); 585 }); 586 } 587 588 TEST(LoopInfoTest, LoopNonConstantStep) { 589 const char *ModuleStr = 590 "define void @foo(i32* %A, i32 %ub, i32 %step) {\n" 591 "entry:\n" 592 " %guardcmp = icmp slt i32 0, %ub\n" 593 " br i1 %guardcmp, label %for.preheader, label %for.end\n" 594 "for.preheader:\n" 595 " br label %for.body\n" 596 "for.body:\n" 597 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n" 598 " %idxprom = zext i32 %i to i64\n" 599 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" 600 " store i32 %i, i32* %arrayidx, align 4\n" 601 " %inc = add nsw i32 %i, %step\n" 602 " %cmp = icmp slt i32 %inc, %ub\n" 603 " br i1 %cmp, label %for.body, label %for.exit\n" 604 "for.exit:\n" 605 " br label %for.end\n" 606 "for.end:\n" 607 " ret void\n" 608 "}\n"; 609 610 // Parse the module. 611 LLVMContext Context; 612 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 613 614 runWithLoopInfoPlus( 615 *M, "foo", 616 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 617 Function::iterator FI = F.begin(); 618 BasicBlock *Entry = &*(FI); 619 BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator()); 620 // First two basic block are entry and for.preheader - skip them. 621 ++FI; 622 BasicBlock *Header = &*(++FI); 623 assert(Header->getName() == "for.body"); 624 Loop *L = LI.getLoopFor(Header); 625 EXPECT_NE(L, nullptr); 626 627 Optional<Loop::LoopBounds> Bounds = L->getBounds(SE); 628 EXPECT_NE(Bounds, None); 629 ConstantInt *InitialIVValue = 630 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue()); 631 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); 632 EXPECT_EQ(Bounds->getStepInst().getName(), "inc"); 633 EXPECT_EQ(Bounds->getStepValue()->getName(), "step"); 634 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub"); 635 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT); 636 EXPECT_EQ(Bounds->getDirection(), Loop::LoopBounds::Direction::Unknown); 637 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); 638 EXPECT_EQ(L->getLoopGuardBranch(), Guard); 639 EXPECT_TRUE(L->isGuarded()); 640 EXPECT_TRUE(L->isRotated()); 641 }); 642 } 643 644 TEST(LoopInfoTest, LoopUnsignedBounds) { 645 const char *ModuleStr = 646 "define void @foo(i32* %A, i32 %ub) {\n" 647 "entry:\n" 648 " %guardcmp = icmp ult i32 0, %ub\n" 649 " br i1 %guardcmp, label %for.preheader, label %for.end\n" 650 "for.preheader:\n" 651 " br label %for.body\n" 652 "for.body:\n" 653 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n" 654 " %idxprom = zext i32 %i to i64\n" 655 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" 656 " store i32 %i, i32* %arrayidx, align 4\n" 657 " %inc = add i32 %i, 1\n" 658 " %cmp = icmp ult i32 %inc, %ub\n" 659 " br i1 %cmp, label %for.body, label %for.exit\n" 660 "for.exit:\n" 661 " br label %for.end\n" 662 "for.end:\n" 663 " ret void\n" 664 "}\n"; 665 666 // Parse the module. 667 LLVMContext Context; 668 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 669 670 runWithLoopInfoPlus( 671 *M, "foo", 672 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 673 Function::iterator FI = F.begin(); 674 BasicBlock *Entry = &*(FI); 675 BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator()); 676 // First two basic block are entry and for.preheader - skip them. 677 ++FI; 678 BasicBlock *Header = &*(++FI); 679 assert(Header->getName() == "for.body"); 680 Loop *L = LI.getLoopFor(Header); 681 EXPECT_NE(L, nullptr); 682 683 Optional<Loop::LoopBounds> Bounds = L->getBounds(SE); 684 EXPECT_NE(Bounds, None); 685 ConstantInt *InitialIVValue = 686 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue()); 687 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); 688 EXPECT_EQ(Bounds->getStepInst().getName(), "inc"); 689 ConstantInt *StepValue = 690 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue()); 691 EXPECT_TRUE(StepValue && StepValue->isOne()); 692 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub"); 693 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_ULT); 694 EXPECT_EQ(Bounds->getDirection(), 695 Loop::LoopBounds::Direction::Increasing); 696 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); 697 EXPECT_EQ(L->getLoopGuardBranch(), Guard); 698 EXPECT_TRUE(L->isGuarded()); 699 EXPECT_TRUE(L->isRotated()); 700 }); 701 } 702 703 TEST(LoopInfoTest, DecreasingLoop) { 704 const char *ModuleStr = 705 "define void @foo(i32* %A, i32 %ub) {\n" 706 "entry:\n" 707 " %guardcmp = icmp slt i32 0, %ub\n" 708 " br i1 %guardcmp, label %for.preheader, label %for.end\n" 709 "for.preheader:\n" 710 " br label %for.body\n" 711 "for.body:\n" 712 " %i = phi i32 [ %ub, %for.preheader ], [ %inc, %for.body ]\n" 713 " %idxprom = sext i32 %i to i64\n" 714 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" 715 " store i32 %i, i32* %arrayidx, align 4\n" 716 " %inc = sub nsw i32 %i, 1\n" 717 " %cmp = icmp sgt i32 %inc, 0\n" 718 " br i1 %cmp, label %for.body, label %for.exit\n" 719 "for.exit:\n" 720 " br label %for.end\n" 721 "for.end:\n" 722 " ret void\n" 723 "}\n"; 724 725 // Parse the module. 726 LLVMContext Context; 727 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 728 729 runWithLoopInfoPlus( 730 *M, "foo", 731 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 732 Function::iterator FI = F.begin(); 733 BasicBlock *Entry = &*(FI); 734 BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator()); 735 // First two basic block are entry and for.preheader - skip them. 736 ++FI; 737 BasicBlock *Header = &*(++FI); 738 assert(Header->getName() == "for.body"); 739 Loop *L = LI.getLoopFor(Header); 740 EXPECT_NE(L, nullptr); 741 742 Optional<Loop::LoopBounds> Bounds = L->getBounds(SE); 743 EXPECT_NE(Bounds, None); 744 EXPECT_EQ(Bounds->getInitialIVValue().getName(), "ub"); 745 EXPECT_EQ(Bounds->getStepInst().getName(), "inc"); 746 ConstantInt *StepValue = 747 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue()); 748 EXPECT_EQ(StepValue, nullptr); 749 ConstantInt *FinalIVValue = 750 dyn_cast<ConstantInt>(&Bounds->getFinalIVValue()); 751 EXPECT_TRUE(FinalIVValue && FinalIVValue->isZero()); 752 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SGT); 753 EXPECT_EQ(Bounds->getDirection(), 754 Loop::LoopBounds::Direction::Decreasing); 755 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); 756 EXPECT_EQ(L->getLoopGuardBranch(), Guard); 757 EXPECT_TRUE(L->isGuarded()); 758 EXPECT_TRUE(L->isRotated()); 759 }); 760 } 761 762 TEST(LoopInfoTest, CannotFindDirection) { 763 const char *ModuleStr = 764 "define void @foo(i32* %A, i32 %ub, i32 %step) {\n" 765 "entry:\n" 766 " %guardcmp = icmp slt i32 0, %ub\n" 767 " br i1 %guardcmp, label %for.preheader, label %for.end\n" 768 "for.preheader:\n" 769 " br label %for.body\n" 770 "for.body:\n" 771 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n" 772 " %idxprom = sext i32 %i to i64\n" 773 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" 774 " store i32 %i, i32* %arrayidx, align 4\n" 775 " %inc = add nsw i32 %i, %step\n" 776 " %cmp = icmp ne i32 %i, %ub\n" 777 " br i1 %cmp, label %for.body, label %for.exit\n" 778 "for.exit:\n" 779 " br label %for.end\n" 780 "for.end:\n" 781 " ret void\n" 782 "}\n"; 783 784 // Parse the module. 785 LLVMContext Context; 786 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 787 788 runWithLoopInfoPlus( 789 *M, "foo", 790 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 791 Function::iterator FI = F.begin(); 792 BasicBlock *Entry = &*(FI); 793 BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator()); 794 // First two basic block are entry and for.preheader 795 // - skip them. 796 ++FI; 797 BasicBlock *Header = &*(++FI); 798 assert(Header->getName() == "for.body"); 799 Loop *L = LI.getLoopFor(Header); 800 EXPECT_NE(L, nullptr); 801 802 Optional<Loop::LoopBounds> Bounds = L->getBounds(SE); 803 EXPECT_NE(Bounds, None); 804 ConstantInt *InitialIVValue = 805 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue()); 806 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); 807 EXPECT_EQ(Bounds->getStepInst().getName(), "inc"); 808 EXPECT_EQ(Bounds->getStepValue()->getName(), "step"); 809 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub"); 810 EXPECT_EQ(Bounds->getCanonicalPredicate(), 811 ICmpInst::BAD_ICMP_PREDICATE); 812 EXPECT_EQ(Bounds->getDirection(), Loop::LoopBounds::Direction::Unknown); 813 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); 814 EXPECT_EQ(L->getLoopGuardBranch(), Guard); 815 EXPECT_TRUE(L->isGuarded()); 816 EXPECT_TRUE(L->isRotated()); 817 }); 818 } 819 820 TEST(LoopInfoTest, ZextIndVar) { 821 const char *ModuleStr = 822 "define void @foo(i32* %A, i32 %ub) {\n" 823 "entry:\n" 824 " %guardcmp = icmp slt i32 0, %ub\n" 825 " br i1 %guardcmp, label %for.preheader, label %for.end\n" 826 "for.preheader:\n" 827 " br label %for.body\n" 828 "for.body:\n" 829 " %indvars.iv = phi i64 [ 0, %for.preheader ], [ %indvars.iv.next, %for.body ]\n" 830 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n" 831 " %idxprom = sext i32 %i to i64\n" 832 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" 833 " store i32 %i, i32* %arrayidx, align 4\n" 834 " %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1\n" 835 " %inc = add nsw i32 %i, 1\n" 836 " %wide.trip.count = zext i32 %ub to i64\n" 837 " %exitcond = icmp ne i64 %indvars.iv.next, %wide.trip.count\n" 838 " br i1 %exitcond, label %for.body, label %for.exit\n" 839 "for.exit:\n" 840 " br label %for.end\n" 841 "for.end:\n" 842 " ret void\n" 843 "}\n"; 844 845 // Parse the module. 846 LLVMContext Context; 847 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 848 849 runWithLoopInfoPlus( 850 *M, "foo", 851 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 852 Function::iterator FI = F.begin(); 853 BasicBlock *Entry = &*(FI); 854 BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator()); 855 // First two basic block are entry and for.preheader - skip them. 856 ++FI; 857 BasicBlock *Header = &*(++FI); 858 assert(Header->getName() == "for.body"); 859 Loop *L = LI.getLoopFor(Header); 860 EXPECT_NE(L, nullptr); 861 862 Optional<Loop::LoopBounds> Bounds = L->getBounds(SE); 863 EXPECT_NE(Bounds, None); 864 ConstantInt *InitialIVValue = 865 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue()); 866 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); 867 EXPECT_EQ(Bounds->getStepInst().getName(), "indvars.iv.next"); 868 ConstantInt *StepValue = 869 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue()); 870 EXPECT_TRUE(StepValue && StepValue->isOne()); 871 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "wide.trip.count"); 872 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_NE); 873 EXPECT_EQ(Bounds->getDirection(), 874 Loop::LoopBounds::Direction::Increasing); 875 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "indvars.iv"); 876 EXPECT_EQ(L->getLoopGuardBranch(), Guard); 877 EXPECT_TRUE(L->isGuarded()); 878 EXPECT_TRUE(L->isRotated()); 879 }); 880 } 881 882 TEST(LoopInfoTest, MultiExitingLoop) { 883 const char *ModuleStr = 884 "define void @foo(i32* %A, i32 %ub, i1 %cond) {\n" 885 "entry:\n" 886 " %guardcmp = icmp slt i32 0, %ub\n" 887 " br i1 %guardcmp, label %for.preheader, label %for.end\n" 888 "for.preheader:\n" 889 " br label %for.body\n" 890 "for.body:\n" 891 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body.1 ]\n" 892 " br i1 %cond, label %for.body.1, label %for.exit\n" 893 "for.body.1:\n" 894 " %idxprom = sext i32 %i to i64\n" 895 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" 896 " store i32 %i, i32* %arrayidx, align 4\n" 897 " %inc = add nsw i32 %i, 1\n" 898 " %cmp = icmp slt i32 %inc, %ub\n" 899 " br i1 %cmp, label %for.body, label %for.exit\n" 900 "for.exit:\n" 901 " br label %for.end\n" 902 "for.end:\n" 903 " ret void\n" 904 "}\n"; 905 906 // Parse the module. 907 LLVMContext Context; 908 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 909 910 runWithLoopInfoPlus( 911 *M, "foo", 912 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 913 Function::iterator FI = F.begin(); 914 BasicBlock *Entry = &*(FI); 915 BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator()); 916 // First two basic block are entry and for.preheader - skip them. 917 ++FI; 918 BasicBlock *Header = &*(++FI); 919 assert(Header->getName() == "for.body"); 920 Loop *L = LI.getLoopFor(Header); 921 EXPECT_NE(L, nullptr); 922 923 Optional<Loop::LoopBounds> Bounds = L->getBounds(SE); 924 EXPECT_NE(Bounds, None); 925 ConstantInt *InitialIVValue = 926 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue()); 927 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); 928 EXPECT_EQ(Bounds->getStepInst().getName(), "inc"); 929 ConstantInt *StepValue = 930 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue()); 931 EXPECT_TRUE(StepValue && StepValue->isOne()); 932 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub"); 933 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT); 934 EXPECT_EQ(Bounds->getDirection(), 935 Loop::LoopBounds::Direction::Increasing); 936 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); 937 EXPECT_EQ(L->getLoopGuardBranch(), Guard); 938 EXPECT_TRUE(L->isGuarded()); 939 }); 940 } 941 942 TEST(LoopInfoTest, MultiExitLoop) { 943 const char *ModuleStr = 944 "define void @foo(i32* %A, i32 %ub, i1 %cond) {\n" 945 "entry:\n" 946 " %guardcmp = icmp slt i32 0, %ub\n" 947 " br i1 %guardcmp, label %for.preheader, label %for.end\n" 948 "for.preheader:\n" 949 " br label %for.body\n" 950 "for.body:\n" 951 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body.1 ]\n" 952 " br i1 %cond, label %for.body.1, label %for.exit\n" 953 "for.body.1:\n" 954 " %idxprom = sext i32 %i to i64\n" 955 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" 956 " store i32 %i, i32* %arrayidx, align 4\n" 957 " %inc = add nsw i32 %i, 1\n" 958 " %cmp = icmp slt i32 %inc, %ub\n" 959 " br i1 %cmp, label %for.body, label %for.exit.1\n" 960 "for.exit:\n" 961 " br label %for.end\n" 962 "for.exit.1:\n" 963 " br label %for.end\n" 964 "for.end:\n" 965 " ret void\n" 966 "}\n"; 967 968 // Parse the module. 969 LLVMContext Context; 970 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 971 972 runWithLoopInfoPlus( 973 *M, "foo", 974 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 975 Function::iterator FI = F.begin(); 976 // First two basic block are entry and for.preheader - skip them. 977 ++FI; 978 BasicBlock *Header = &*(++FI); 979 assert(Header->getName() == "for.body"); 980 Loop *L = LI.getLoopFor(Header); 981 EXPECT_NE(L, nullptr); 982 983 Optional<Loop::LoopBounds> Bounds = L->getBounds(SE); 984 EXPECT_NE(Bounds, None); 985 ConstantInt *InitialIVValue = 986 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue()); 987 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); 988 EXPECT_EQ(Bounds->getStepInst().getName(), "inc"); 989 ConstantInt *StepValue = 990 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue()); 991 EXPECT_TRUE(StepValue && StepValue->isOne()); 992 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub"); 993 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT); 994 EXPECT_EQ(Bounds->getDirection(), 995 Loop::LoopBounds::Direction::Increasing); 996 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); 997 EXPECT_EQ(L->getLoopGuardBranch(), nullptr); 998 EXPECT_FALSE(L->isGuarded()); 999 }); 1000 } 1001 1002 TEST(LoopInfoTest, UnguardedLoop) { 1003 const char *ModuleStr = 1004 "define void @foo(i32* %A, i32 %ub) {\n" 1005 "entry:\n" 1006 " br label %for.body\n" 1007 "for.body:\n" 1008 " %i = phi i32 [ 0, %entry ], [ %inc, %for.body ]\n" 1009 " %idxprom = sext i32 %i to i64\n" 1010 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" 1011 " store i32 %i, i32* %arrayidx, align 4\n" 1012 " %inc = add nsw i32 %i, 1\n" 1013 " %cmp = icmp slt i32 %inc, %ub\n" 1014 " br i1 %cmp, label %for.body, label %for.exit\n" 1015 "for.exit:\n" 1016 " br label %for.end\n" 1017 "for.end:\n" 1018 " ret void\n" 1019 "}\n"; 1020 1021 // Parse the module. 1022 LLVMContext Context; 1023 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 1024 1025 runWithLoopInfoPlus( 1026 *M, "foo", 1027 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1028 Function::iterator FI = F.begin(); 1029 // First basic block is entry - skip it. 1030 BasicBlock *Header = &*(++FI); 1031 assert(Header->getName() == "for.body"); 1032 Loop *L = LI.getLoopFor(Header); 1033 EXPECT_NE(L, nullptr); 1034 1035 Optional<Loop::LoopBounds> Bounds = L->getBounds(SE); 1036 EXPECT_NE(Bounds, None); 1037 ConstantInt *InitialIVValue = 1038 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue()); 1039 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); 1040 EXPECT_EQ(Bounds->getStepInst().getName(), "inc"); 1041 ConstantInt *StepValue = 1042 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue()); 1043 EXPECT_TRUE(StepValue && StepValue->isOne()); 1044 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub"); 1045 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT); 1046 EXPECT_EQ(Bounds->getDirection(), 1047 Loop::LoopBounds::Direction::Increasing); 1048 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); 1049 EXPECT_EQ(L->getLoopGuardBranch(), nullptr); 1050 EXPECT_FALSE(L->isGuarded()); 1051 EXPECT_TRUE(L->isRotated()); 1052 }); 1053 } 1054 1055 TEST(LoopInfoTest, UnguardedLoopWithControlFlow) { 1056 const char *ModuleStr = 1057 "define void @foo(i32* %A, i32 %ub, i1 %cond) {\n" 1058 "entry:\n" 1059 " br i1 %cond, label %for.preheader, label %for.end\n" 1060 "for.preheader:\n" 1061 " br label %for.body\n" 1062 "for.body:\n" 1063 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n" 1064 " %idxprom = sext i32 %i to i64\n" 1065 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" 1066 " store i32 %i, i32* %arrayidx, align 4\n" 1067 " %inc = add nsw i32 %i, 1\n" 1068 " %cmp = icmp slt i32 %inc, %ub\n" 1069 " br i1 %cmp, label %for.body, label %for.exit\n" 1070 "for.exit:\n" 1071 " br label %for.end\n" 1072 "for.end:\n" 1073 " ret void\n" 1074 "}\n"; 1075 1076 // Parse the module. 1077 LLVMContext Context; 1078 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 1079 1080 runWithLoopInfoPlus( 1081 *M, "foo", 1082 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1083 Function::iterator FI = F.begin(); 1084 BasicBlock *Entry = &*(FI); 1085 BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator()); 1086 // First two basic block are entry and for.preheader - skip them. 1087 ++FI; 1088 BasicBlock *Header = &*(++FI); 1089 assert(Header->getName() == "for.body"); 1090 Loop *L = LI.getLoopFor(Header); 1091 EXPECT_NE(L, nullptr); 1092 1093 Optional<Loop::LoopBounds> Bounds = L->getBounds(SE); 1094 EXPECT_NE(Bounds, None); 1095 ConstantInt *InitialIVValue = 1096 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue()); 1097 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); 1098 EXPECT_EQ(Bounds->getStepInst().getName(), "inc"); 1099 ConstantInt *StepValue = 1100 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue()); 1101 EXPECT_TRUE(StepValue && StepValue->isOne()); 1102 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub"); 1103 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT); 1104 EXPECT_EQ(Bounds->getDirection(), 1105 Loop::LoopBounds::Direction::Increasing); 1106 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); 1107 EXPECT_EQ(L->getLoopGuardBranch(), Guard); 1108 EXPECT_TRUE(L->isGuarded()); 1109 EXPECT_TRUE(L->isRotated()); 1110 }); 1111 } 1112 1113 TEST(LoopInfoTest, LoopNest) { 1114 const char *ModuleStr = 1115 "define void @foo(i32* %A, i32 %ub) {\n" 1116 "entry:\n" 1117 " %guardcmp = icmp slt i32 0, %ub\n" 1118 " br i1 %guardcmp, label %for.outer.preheader, label %for.end\n" 1119 "for.outer.preheader:\n" 1120 " br label %for.outer\n" 1121 "for.outer:\n" 1122 " %j = phi i32 [ 0, %for.outer.preheader ], [ %inc.outer, %for.outer.latch ]\n" 1123 " br i1 %guardcmp, label %for.inner.preheader, label %for.outer.latch\n" 1124 "for.inner.preheader:\n" 1125 " br label %for.inner\n" 1126 "for.inner:\n" 1127 " %i = phi i32 [ 0, %for.inner.preheader ], [ %inc, %for.inner ]\n" 1128 " %idxprom = sext i32 %i to i64\n" 1129 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" 1130 " store i32 %i, i32* %arrayidx, align 4\n" 1131 " %inc = add nsw i32 %i, 1\n" 1132 " %cmp = icmp slt i32 %inc, %ub\n" 1133 " br i1 %cmp, label %for.inner, label %for.inner.exit\n" 1134 "for.inner.exit:\n" 1135 " br label %for.outer.latch\n" 1136 "for.outer.latch:\n" 1137 " %inc.outer = add nsw i32 %j, 1\n" 1138 " %cmp.outer = icmp slt i32 %inc.outer, %ub\n" 1139 " br i1 %cmp.outer, label %for.outer, label %for.outer.exit\n" 1140 "for.outer.exit:\n" 1141 " br label %for.end\n" 1142 "for.end:\n" 1143 " ret void\n" 1144 "}\n"; 1145 1146 // Parse the module. 1147 LLVMContext Context; 1148 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 1149 1150 runWithLoopInfoPlus( 1151 *M, "foo", 1152 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1153 Function::iterator FI = F.begin(); 1154 BasicBlock *Entry = &*(FI); 1155 BranchInst *OuterGuard = dyn_cast<BranchInst>(Entry->getTerminator()); 1156 // First two basic block are entry and for.outer.preheader - skip them. 1157 ++FI; 1158 BasicBlock *Header = &*(++FI); 1159 assert(Header->getName() == "for.outer"); 1160 BranchInst *InnerGuard = dyn_cast<BranchInst>(Header->getTerminator()); 1161 Loop *L = LI.getLoopFor(Header); 1162 EXPECT_NE(L, nullptr); 1163 1164 Optional<Loop::LoopBounds> Bounds = L->getBounds(SE); 1165 EXPECT_NE(Bounds, None); 1166 ConstantInt *InitialIVValue = 1167 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue()); 1168 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); 1169 EXPECT_EQ(Bounds->getStepInst().getName(), "inc.outer"); 1170 ConstantInt *StepValue = 1171 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue()); 1172 EXPECT_TRUE(StepValue && StepValue->isOne()); 1173 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub"); 1174 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT); 1175 EXPECT_EQ(Bounds->getDirection(), 1176 Loop::LoopBounds::Direction::Increasing); 1177 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "j"); 1178 EXPECT_EQ(L->getLoopGuardBranch(), OuterGuard); 1179 EXPECT_TRUE(L->isGuarded()); 1180 EXPECT_TRUE(L->isRotated()); 1181 1182 // Next two basic blocks are for.outer and for.inner.preheader - skip 1183 // them. 1184 ++FI; 1185 Header = &*(++FI); 1186 assert(Header->getName() == "for.inner"); 1187 L = LI.getLoopFor(Header); 1188 EXPECT_NE(L, nullptr); 1189 1190 Optional<Loop::LoopBounds> InnerBounds = L->getBounds(SE); 1191 EXPECT_NE(InnerBounds, None); 1192 InitialIVValue = 1193 dyn_cast<ConstantInt>(&InnerBounds->getInitialIVValue()); 1194 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); 1195 EXPECT_EQ(InnerBounds->getStepInst().getName(), "inc"); 1196 StepValue = dyn_cast_or_null<ConstantInt>(InnerBounds->getStepValue()); 1197 EXPECT_TRUE(StepValue && StepValue->isOne()); 1198 EXPECT_EQ(InnerBounds->getFinalIVValue().getName(), "ub"); 1199 EXPECT_EQ(InnerBounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT); 1200 EXPECT_EQ(InnerBounds->getDirection(), 1201 Loop::LoopBounds::Direction::Increasing); 1202 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); 1203 EXPECT_EQ(L->getLoopGuardBranch(), InnerGuard); 1204 EXPECT_TRUE(L->isGuarded()); 1205 EXPECT_TRUE(L->isRotated()); 1206 }); 1207 } 1208 1209 TEST(LoopInfoTest, AuxiliaryIV) { 1210 const char *ModuleStr = 1211 "define void @foo(i32* %A, i32 %ub) {\n" 1212 "entry:\n" 1213 " %guardcmp = icmp slt i32 0, %ub\n" 1214 " br i1 %guardcmp, label %for.preheader, label %for.end\n" 1215 "for.preheader:\n" 1216 " br label %for.body\n" 1217 "for.body:\n" 1218 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n" 1219 " %aux = phi i32 [ 0, %for.preheader ], [ %auxinc, %for.body ]\n" 1220 " %loopvariant = phi i32 [ 0, %for.preheader ], [ %loopvariantinc, %for.body ]\n" 1221 " %usedoutside = phi i32 [ 0, %for.preheader ], [ %usedoutsideinc, %for.body ]\n" 1222 " %mulopcode = phi i32 [ 0, %for.preheader ], [ %mulopcodeinc, %for.body ]\n" 1223 " %idxprom = sext i32 %i to i64\n" 1224 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" 1225 " store i32 %i, i32* %arrayidx, align 4\n" 1226 " %mulopcodeinc = mul nsw i32 %mulopcode, 5\n" 1227 " %usedoutsideinc = add nsw i32 %usedoutside, 5\n" 1228 " %loopvariantinc = add nsw i32 %loopvariant, %i\n" 1229 " %auxinc = add nsw i32 %aux, 5\n" 1230 " %inc = add nsw i32 %i, 1\n" 1231 " %cmp = icmp slt i32 %inc, %ub\n" 1232 " br i1 %cmp, label %for.body, label %for.exit\n" 1233 "for.exit:\n" 1234 " %lcssa = phi i32 [ %usedoutside, %for.body ]\n" 1235 " br label %for.end\n" 1236 "for.end:\n" 1237 " ret void\n" 1238 "}\n"; 1239 1240 // Parse the module. 1241 LLVMContext Context; 1242 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 1243 1244 runWithLoopInfoPlus( 1245 *M, "foo", 1246 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1247 Function::iterator FI = F.begin(); 1248 BasicBlock *Entry = &*(FI); 1249 BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator()); 1250 // First two basic block are entry and for.preheader - skip them. 1251 ++FI; 1252 BasicBlock *Header = &*(++FI); 1253 assert(Header->getName() == "for.body"); 1254 Loop *L = LI.getLoopFor(Header); 1255 EXPECT_NE(L, nullptr); 1256 1257 Optional<Loop::LoopBounds> Bounds = L->getBounds(SE); 1258 EXPECT_NE(Bounds, None); 1259 ConstantInt *InitialIVValue = 1260 dyn_cast<ConstantInt>(&Bounds->getInitialIVValue()); 1261 EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero()); 1262 EXPECT_EQ(Bounds->getStepInst().getName(), "inc"); 1263 ConstantInt *StepValue = 1264 dyn_cast_or_null<ConstantInt>(Bounds->getStepValue()); 1265 EXPECT_TRUE(StepValue && StepValue->isOne()); 1266 EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub"); 1267 EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT); 1268 EXPECT_EQ(Bounds->getDirection(), 1269 Loop::LoopBounds::Direction::Increasing); 1270 EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i"); 1271 BasicBlock::iterator II = Header->begin(); 1272 PHINode &Instruction_i = cast<PHINode>(*(II)); 1273 EXPECT_TRUE(L->isAuxiliaryInductionVariable(Instruction_i, SE)); 1274 PHINode &Instruction_aux = cast<PHINode>(*(++II)); 1275 EXPECT_TRUE(L->isAuxiliaryInductionVariable(Instruction_aux, SE)); 1276 PHINode &Instruction_loopvariant = cast<PHINode>(*(++II)); 1277 EXPECT_FALSE( 1278 L->isAuxiliaryInductionVariable(Instruction_loopvariant, SE)); 1279 PHINode &Instruction_usedoutside = cast<PHINode>(*(++II)); 1280 EXPECT_FALSE( 1281 L->isAuxiliaryInductionVariable(Instruction_usedoutside, SE)); 1282 PHINode &Instruction_mulopcode = cast<PHINode>(*(++II)); 1283 EXPECT_FALSE( 1284 L->isAuxiliaryInductionVariable(Instruction_mulopcode, SE)); 1285 EXPECT_EQ(L->getLoopGuardBranch(), Guard); 1286 EXPECT_TRUE(L->isGuarded()); 1287 EXPECT_TRUE(L->isRotated()); 1288 }); 1289 } 1290 1291 TEST(LoopInfoTest, LoopNotInSimplifyForm) { 1292 const char *ModuleStr = 1293 "define void @foo(i32 %n) {\n" 1294 "entry:\n" 1295 " %guard.cmp = icmp sgt i32 %n, 0\n" 1296 " br i1 %guard.cmp, label %for.cond, label %for.end\n" 1297 "for.cond:\n" 1298 " %i.0 = phi i32 [ 0, %entry ], [ %inc, %latch.1 ], [ %inc, %latch.2 ]\n" 1299 " %inc = add nsw i32 %i.0, 1\n" 1300 " %cmp = icmp slt i32 %i.0, %n\n" 1301 " br i1 %cmp, label %latch.1, label %for.end\n" 1302 "latch.1:\n" 1303 " br i1 undef, label %for.cond, label %latch.2\n" 1304 "latch.2:\n" 1305 " br label %for.cond\n" 1306 "for.end:\n" 1307 " ret void\n" 1308 "}\n"; 1309 1310 // Parse the module. 1311 LLVMContext Context; 1312 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 1313 1314 runWithLoopInfo(*M, "foo", [&](Function &F, LoopInfo &LI) { 1315 Function::iterator FI = F.begin(); 1316 // First basic block is entry - skip it. 1317 BasicBlock *Header = &*(++FI); 1318 assert(Header && "No header"); 1319 Loop *L = LI.getLoopFor(Header); 1320 EXPECT_NE(L, nullptr); 1321 EXPECT_FALSE(L->isLoopSimplifyForm()); 1322 // No loop guard because loop in not in simplify form. 1323 EXPECT_EQ(L->getLoopGuardBranch(), nullptr); 1324 EXPECT_FALSE(L->isGuarded()); 1325 }); 1326 } 1327 1328 TEST(LoopInfoTest, LoopLatchNotExiting) { 1329 const char *ModuleStr = 1330 "define void @foo(i32* %A, i32 %ub) {\n" 1331 "entry:\n" 1332 " %guardcmp = icmp slt i32 0, %ub\n" 1333 " br i1 %guardcmp, label %for.preheader, label %for.end\n" 1334 "for.preheader:\n" 1335 " br label %for.body\n" 1336 "for.body:\n" 1337 " %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n" 1338 " %idxprom = sext i32 %i to i64\n" 1339 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n" 1340 " store i32 %i, i32* %arrayidx, align 4\n" 1341 " %inc = add nsw i32 %i, 1\n" 1342 " %cmp = icmp slt i32 %inc, %ub\n" 1343 " br i1 %cmp, label %for.latch, label %for.exit\n" 1344 "for.latch:\n" 1345 " br label %for.body\n" 1346 "for.exit:\n" 1347 " br label %for.end\n" 1348 "for.end:\n" 1349 " ret void\n" 1350 "}\n"; 1351 1352 // Parse the module. 1353 LLVMContext Context; 1354 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 1355 1356 runWithLoopInfoPlus( 1357 *M, "foo", 1358 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1359 Function::iterator FI = F.begin(); 1360 // First two basic block are entry and for.preheader - skip them. 1361 ++FI; 1362 BasicBlock *Header = &*(++FI); 1363 BasicBlock *Latch = &*(++FI); 1364 assert(Header && "No header"); 1365 Loop *L = LI.getLoopFor(Header); 1366 EXPECT_NE(L, nullptr); 1367 EXPECT_TRUE(L->isLoopSimplifyForm()); 1368 EXPECT_EQ(L->getLoopLatch(), Latch); 1369 EXPECT_FALSE(L->isLoopExiting(Latch)); 1370 // No loop guard becuase loop is not exiting on latch. 1371 EXPECT_EQ(L->getLoopGuardBranch(), nullptr); 1372 EXPECT_FALSE(L->isGuarded()); 1373 }); 1374 } 1375 1376 // Examine getUniqueExitBlocks/getUniqueNonLatchExitBlocks functions. 1377 TEST(LoopInfoTest, LoopUniqueExitBlocks) { 1378 const char *ModuleStr = 1379 "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n" 1380 "define void @foo(i32 %n, i1 %cond) {\n" 1381 "entry:\n" 1382 " br label %for.cond\n" 1383 "for.cond:\n" 1384 " %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]\n" 1385 " %cmp = icmp slt i32 %i.0, %n\n" 1386 " br i1 %cond, label %for.inc, label %for.end1\n" 1387 "for.inc:\n" 1388 " %inc = add nsw i32 %i.0, 1\n" 1389 " br i1 %cmp, label %for.cond, label %for.end2, !llvm.loop !0\n" 1390 "for.end1:\n" 1391 " br label %for.end\n" 1392 "for.end2:\n" 1393 " br label %for.end\n" 1394 "for.end:\n" 1395 " ret void\n" 1396 "}\n" 1397 "!0 = distinct !{!0, !1}\n" 1398 "!1 = !{!\"llvm.loop.distribute.enable\", i1 true}\n"; 1399 1400 // Parse the module. 1401 LLVMContext Context; 1402 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 1403 1404 runWithLoopInfo(*M, "foo", [&](Function &F, LoopInfo &LI) { 1405 Function::iterator FI = F.begin(); 1406 // First basic block is entry - skip it. 1407 BasicBlock *Header = &*(++FI); 1408 assert(Header->getName() == "for.cond"); 1409 Loop *L = LI.getLoopFor(Header); 1410 1411 SmallVector<BasicBlock *, 2> Exits; 1412 // This loop has 2 unique exits. 1413 L->getUniqueExitBlocks(Exits); 1414 EXPECT_TRUE(Exits.size() == 2); 1415 // And one unique non latch exit. 1416 Exits.clear(); 1417 L->getUniqueNonLatchExitBlocks(Exits); 1418 EXPECT_TRUE(Exits.size() == 1); 1419 }); 1420 } 1421 1422 // Regression test for getUniqueNonLatchExitBlocks functions. 1423 // It should detect the exit if it comes from both latch and non-latch blocks. 1424 TEST(LoopInfoTest, LoopNonLatchUniqueExitBlocks) { 1425 const char *ModuleStr = 1426 "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n" 1427 "define void @foo(i32 %n, i1 %cond) {\n" 1428 "entry:\n" 1429 " br label %for.cond\n" 1430 "for.cond:\n" 1431 " %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]\n" 1432 " %cmp = icmp slt i32 %i.0, %n\n" 1433 " br i1 %cond, label %for.inc, label %for.end\n" 1434 "for.inc:\n" 1435 " %inc = add nsw i32 %i.0, 1\n" 1436 " br i1 %cmp, label %for.cond, label %for.end, !llvm.loop !0\n" 1437 "for.end:\n" 1438 " ret void\n" 1439 "}\n" 1440 "!0 = distinct !{!0, !1}\n" 1441 "!1 = !{!\"llvm.loop.distribute.enable\", i1 true}\n"; 1442 1443 // Parse the module. 1444 LLVMContext Context; 1445 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 1446 1447 runWithLoopInfo(*M, "foo", [&](Function &F, LoopInfo &LI) { 1448 Function::iterator FI = F.begin(); 1449 // First basic block is entry - skip it. 1450 BasicBlock *Header = &*(++FI); 1451 assert(Header->getName() == "for.cond"); 1452 Loop *L = LI.getLoopFor(Header); 1453 1454 SmallVector<BasicBlock *, 2> Exits; 1455 // This loop has 1 unique exit. 1456 L->getUniqueExitBlocks(Exits); 1457 EXPECT_TRUE(Exits.size() == 1); 1458 // And one unique non latch exit. 1459 Exits.clear(); 1460 L->getUniqueNonLatchExitBlocks(Exits); 1461 EXPECT_TRUE(Exits.size() == 1); 1462 }); 1463 } 1464 1465 // Test that a pointer-chasing loop is not rotated. 1466 TEST(LoopInfoTest, LoopNotRotated) { 1467 const char *ModuleStr = 1468 "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n" 1469 "define void @foo(i32* %elem) {\n" 1470 "entry:\n" 1471 " br label %while.cond\n" 1472 "while.cond:\n" 1473 " %elem.addr.0 = phi i32* [ %elem, %entry ], [ %incdec.ptr, %while.body " 1474 "]\n" 1475 " %tobool = icmp eq i32* %elem.addr.0, null\n" 1476 " br i1 %tobool, label %while.end, label %while.body\n" 1477 "while.body:\n" 1478 " %incdec.ptr = getelementptr inbounds i32, i32* %elem.addr.0, i64 1\n" 1479 " br label %while.cond\n" 1480 "while.end:\n" 1481 " ret void\n" 1482 "}\n"; 1483 1484 // Parse the module. 1485 LLVMContext Context; 1486 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 1487 1488 runWithLoopInfo(*M, "foo", [&](Function &F, LoopInfo &LI) { 1489 Function::iterator FI = F.begin(); 1490 // First basic block is entry - skip it. 1491 BasicBlock *Header = &*(++FI); 1492 assert(Header->getName() == "while.cond"); 1493 Loop *L = LI.getLoopFor(Header); 1494 EXPECT_NE(L, nullptr); 1495 1496 // This loop is in simplified form. 1497 EXPECT_TRUE(L->isLoopSimplifyForm()); 1498 1499 // This loop is not rotated. 1500 EXPECT_FALSE(L->isRotated()); 1501 }); 1502 } 1503