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