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/AsmParser/Parser.h" 11 #include "llvm/IR/Dominators.h" 12 #include "llvm/Support/SourceMgr.h" 13 #include "gtest/gtest.h" 14 15 using namespace llvm; 16 17 /// Build the loop info for the function and run the Test. 18 static void 19 runWithLoopInfo(Module &M, StringRef FuncName, 20 function_ref<void(Function &F, LoopInfo &LI)> Test) { 21 auto *F = M.getFunction(FuncName); 22 ASSERT_NE(F, nullptr) << "Could not find " << FuncName; 23 // Compute the dominator tree and the loop info for the function. 24 DominatorTree DT(*F); 25 LoopInfo LI(DT); 26 Test(*F, LI); 27 } 28 29 static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context, 30 const char *ModuleStr) { 31 SMDiagnostic Err; 32 return parseAssemblyString(ModuleStr, Err, Context); 33 } 34 35 // This tests that for a loop with a single latch, we get the loop id from 36 // its only latch, even in case the loop may not be in a simplified form. 37 TEST(LoopInfoTest, LoopWithSingleLatch) { 38 const char *ModuleStr = 39 "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n" 40 "define void @foo(i32 %n) {\n" 41 "entry:\n" 42 " br i1 undef, label %for.cond, label %for.end\n" 43 "for.cond:\n" 44 " %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]\n" 45 " %cmp = icmp slt i32 %i.0, %n\n" 46 " br i1 %cmp, label %for.inc, label %for.end\n" 47 "for.inc:\n" 48 " %inc = add nsw i32 %i.0, 1\n" 49 " br label %for.cond, !llvm.loop !0\n" 50 "for.end:\n" 51 " ret void\n" 52 "}\n" 53 "!0 = distinct !{!0, !1}\n" 54 "!1 = !{!\"llvm.loop.distribute.enable\", i1 true}\n"; 55 56 // Parse the module. 57 LLVMContext Context; 58 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 59 60 runWithLoopInfo(*M, "foo", [&](Function &F, LoopInfo &LI) { 61 Function::iterator FI = F.begin(); 62 // First basic block is entry - skip it. 63 BasicBlock *Header = &*(++FI); 64 assert(Header->getName() == "for.cond"); 65 Loop *L = LI.getLoopFor(Header); 66 67 // This loop is not in simplified form. 68 EXPECT_FALSE(L->isLoopSimplifyForm()); 69 70 // Analyze the loop metadata id. 71 bool loopIDFoundAndSet = false; 72 // Try to get and set the metadata id for the loop. 73 if (MDNode *D = L->getLoopID()) { 74 L->setLoopID(D); 75 loopIDFoundAndSet = true; 76 } 77 78 // We must have successfully found and set the loop id in the 79 // only latch the loop has. 80 EXPECT_TRUE(loopIDFoundAndSet); 81 }); 82 } 83 84 // Test loop id handling for a loop with multiple latches. 85 TEST(LoopInfoTest, LoopWithMultipleLatches) { 86 const char *ModuleStr = 87 "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n" 88 "define void @foo(i32 %n) {\n" 89 "entry:\n" 90 " br i1 undef, label %for.cond, label %for.end\n" 91 "for.cond:\n" 92 " %i.0 = phi i32 [ 0, %entry ], [ %inc, %latch.1 ], [ %inc, %latch.2 ]\n" 93 " %inc = add nsw i32 %i.0, 1\n" 94 " %cmp = icmp slt i32 %i.0, %n\n" 95 " br i1 %cmp, label %latch.1, label %for.end\n" 96 "latch.1:\n" 97 " br i1 undef, label %for.cond, label %latch.2, !llvm.loop !0\n" 98 "latch.2:\n" 99 " br label %for.cond, !llvm.loop !0\n" 100 "for.end:\n" 101 " ret void\n" 102 "}\n" 103 "!0 = distinct !{!0, !1}\n" 104 "!1 = !{!\"llvm.loop.distribute.enable\", i1 true}\n"; 105 106 // Parse the module. 107 LLVMContext Context; 108 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 109 110 runWithLoopInfo(*M, "foo", [&](Function &F, LoopInfo &LI) { 111 Function::iterator FI = F.begin(); 112 // First basic block is entry - skip it. 113 BasicBlock *Header = &*(++FI); 114 assert(Header->getName() == "for.cond"); 115 Loop *L = LI.getLoopFor(Header); 116 EXPECT_NE(L, nullptr); 117 118 // This loop is not in simplified form. 119 EXPECT_FALSE(L->isLoopSimplifyForm()); 120 121 // Try to get and set the metadata id for the loop. 122 MDNode *OldLoopID = L->getLoopID(); 123 EXPECT_NE(OldLoopID, nullptr); 124 125 MDNode *NewLoopID = MDNode::get(Context, {nullptr}); 126 // Set operand 0 to refer to the loop id itself. 127 NewLoopID->replaceOperandWith(0, NewLoopID); 128 129 L->setLoopID(NewLoopID); 130 EXPECT_EQ(L->getLoopID(), NewLoopID); 131 EXPECT_NE(L->getLoopID(), OldLoopID); 132 133 L->setLoopID(OldLoopID); 134 EXPECT_EQ(L->getLoopID(), OldLoopID); 135 EXPECT_NE(L->getLoopID(), NewLoopID); 136 }); 137 } 138 139 TEST(LoopInfoTest, PreorderTraversals) { 140 const char *ModuleStr = "define void @f() {\n" 141 "entry:\n" 142 " br label %loop.0\n" 143 "loop.0:\n" 144 " br i1 undef, label %loop.0.0, label %loop.1\n" 145 "loop.0.0:\n" 146 " br i1 undef, label %loop.0.0, label %loop.0.1\n" 147 "loop.0.1:\n" 148 " br i1 undef, label %loop.0.1, label %loop.0.2\n" 149 "loop.0.2:\n" 150 " br i1 undef, label %loop.0.2, label %loop.0\n" 151 "loop.1:\n" 152 " br i1 undef, label %loop.1.0, label %end\n" 153 "loop.1.0:\n" 154 " br i1 undef, label %loop.1.0, label %loop.1.1\n" 155 "loop.1.1:\n" 156 " br i1 undef, label %loop.1.1, label %loop.1.2\n" 157 "loop.1.2:\n" 158 " br i1 undef, label %loop.1.2, label %loop.1\n" 159 "end:\n" 160 " ret void\n" 161 "}\n"; 162 // Parse the module. 163 LLVMContext Context; 164 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 165 Function &F = *M->begin(); 166 167 DominatorTree DT(F); 168 LoopInfo LI; 169 LI.analyze(DT); 170 171 Function::iterator I = F.begin(); 172 ASSERT_EQ("entry", I->getName()); 173 ++I; 174 Loop &L_0 = *LI.getLoopFor(&*I++); 175 ASSERT_EQ("loop.0", L_0.getHeader()->getName()); 176 Loop &L_0_0 = *LI.getLoopFor(&*I++); 177 ASSERT_EQ("loop.0.0", L_0_0.getHeader()->getName()); 178 Loop &L_0_1 = *LI.getLoopFor(&*I++); 179 ASSERT_EQ("loop.0.1", L_0_1.getHeader()->getName()); 180 Loop &L_0_2 = *LI.getLoopFor(&*I++); 181 ASSERT_EQ("loop.0.2", L_0_2.getHeader()->getName()); 182 Loop &L_1 = *LI.getLoopFor(&*I++); 183 ASSERT_EQ("loop.1", L_1.getHeader()->getName()); 184 Loop &L_1_0 = *LI.getLoopFor(&*I++); 185 ASSERT_EQ("loop.1.0", L_1_0.getHeader()->getName()); 186 Loop &L_1_1 = *LI.getLoopFor(&*I++); 187 ASSERT_EQ("loop.1.1", L_1_1.getHeader()->getName()); 188 Loop &L_1_2 = *LI.getLoopFor(&*I++); 189 ASSERT_EQ("loop.1.2", L_1_2.getHeader()->getName()); 190 191 auto Preorder = LI.getLoopsInPreorder(); 192 ASSERT_EQ(8u, Preorder.size()); 193 EXPECT_EQ(&L_0, Preorder[0]); 194 EXPECT_EQ(&L_0_0, Preorder[1]); 195 EXPECT_EQ(&L_0_1, Preorder[2]); 196 EXPECT_EQ(&L_0_2, Preorder[3]); 197 EXPECT_EQ(&L_1, Preorder[4]); 198 EXPECT_EQ(&L_1_0, Preorder[5]); 199 EXPECT_EQ(&L_1_1, Preorder[6]); 200 EXPECT_EQ(&L_1_2, Preorder[7]); 201 202 auto ReverseSiblingPreorder = LI.getLoopsInReverseSiblingPreorder(); 203 ASSERT_EQ(8u, ReverseSiblingPreorder.size()); 204 EXPECT_EQ(&L_1, ReverseSiblingPreorder[0]); 205 EXPECT_EQ(&L_1_2, ReverseSiblingPreorder[1]); 206 EXPECT_EQ(&L_1_1, ReverseSiblingPreorder[2]); 207 EXPECT_EQ(&L_1_0, ReverseSiblingPreorder[3]); 208 EXPECT_EQ(&L_0, ReverseSiblingPreorder[4]); 209 EXPECT_EQ(&L_0_2, ReverseSiblingPreorder[5]); 210 EXPECT_EQ(&L_0_1, ReverseSiblingPreorder[6]); 211 EXPECT_EQ(&L_0_0, ReverseSiblingPreorder[7]); 212 } 213