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