1 //===- LoopInfoTest.cpp - LoopInfo unit tests -----------------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 10 #include "llvm/Analysis/LoopInfo.h" 11 #include "llvm/AsmParser/Parser.h" 12 #include "llvm/IR/Dominators.h" 13 #include "llvm/Support/SourceMgr.h" 14 #include "gtest/gtest.h" 15 16 using namespace llvm; 17 18 /// Build the loop info for the function and run the Test. 19 static void 20 runWithLoopInfo(Module &M, StringRef FuncName, 21 function_ref<void(Function &F, LoopInfo &LI)> Test) { 22 auto *F = M.getFunction(FuncName); 23 ASSERT_NE(F, nullptr) << "Could not find " << FuncName; 24 // Compute the dominator tree and the loop info for the function. 25 DominatorTree DT(*F); 26 LoopInfo LI(DT); 27 Test(*F, LI); 28 } 29 30 static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context, 31 const char *ModuleStr) { 32 SMDiagnostic Err; 33 return parseAssemblyString(ModuleStr, Err, Context); 34 } 35 36 // This tests that for a loop with a single latch, we get the loop id from 37 // its only latch, even in case the loop may not be in a simplified form. 38 TEST(LoopInfoTest, LoopWithSingleLatch) { 39 const char *ModuleStr = 40 "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n" 41 "define void @foo(i32 %n) {\n" 42 "entry:\n" 43 " br i1 undef, label %for.cond, label %for.end\n" 44 "for.cond:\n" 45 " %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]\n" 46 " %cmp = icmp slt i32 %i.0, %n\n" 47 " br i1 %cmp, label %for.inc, label %for.end\n" 48 "for.inc:\n" 49 " %inc = add nsw i32 %i.0, 1\n" 50 " br label %for.cond, !llvm.loop !0\n" 51 "for.end:\n" 52 " ret void\n" 53 "}\n" 54 "!0 = distinct !{!0, !1}\n" 55 "!1 = !{!\"llvm.loop.distribute.enable\", i1 true}\n"; 56 57 // Parse the module. 58 LLVMContext Context; 59 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 60 61 runWithLoopInfo(*M, "foo", [&](Function &F, LoopInfo &LI) { 62 Function::iterator FI = F.begin(); 63 // First basic block is entry - skip it. 64 BasicBlock *Header = &*(++FI); 65 assert(Header->getName() == "for.cond"); 66 Loop *L = LI.getLoopFor(Header); 67 68 // This loop is not in simplified form. 69 EXPECT_FALSE(L->isLoopSimplifyForm()); 70 71 // Analyze the loop metadata id. 72 bool loopIDFoundAndSet = false; 73 // Try to get and set the metadata id for the loop. 74 if (MDNode *D = L->getLoopID()) { 75 L->setLoopID(D); 76 loopIDFoundAndSet = true; 77 } 78 79 // We must have successfully found and set the loop id in the 80 // only latch the loop has. 81 EXPECT_TRUE(loopIDFoundAndSet); 82 }); 83 } 84 85 TEST(LoopInfoTest, PreorderTraversals) { 86 const char *ModuleStr = "define void @f() {\n" 87 "entry:\n" 88 " br label %loop.0\n" 89 "loop.0:\n" 90 " br i1 undef, label %loop.0.0, label %loop.1\n" 91 "loop.0.0:\n" 92 " br i1 undef, label %loop.0.0, label %loop.0.1\n" 93 "loop.0.1:\n" 94 " br i1 undef, label %loop.0.1, label %loop.0.2\n" 95 "loop.0.2:\n" 96 " br i1 undef, label %loop.0.2, label %loop.0\n" 97 "loop.1:\n" 98 " br i1 undef, label %loop.1.0, label %end\n" 99 "loop.1.0:\n" 100 " br i1 undef, label %loop.1.0, label %loop.1.1\n" 101 "loop.1.1:\n" 102 " br i1 undef, label %loop.1.1, label %loop.1.2\n" 103 "loop.1.2:\n" 104 " br i1 undef, label %loop.1.2, label %loop.1\n" 105 "end:\n" 106 " ret void\n" 107 "}\n"; 108 // Parse the module. 109 LLVMContext Context; 110 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 111 Function &F = *M->begin(); 112 113 DominatorTree DT(F); 114 LoopInfo LI; 115 LI.analyze(DT); 116 117 Function::iterator I = F.begin(); 118 ASSERT_EQ("entry", I->getName()); 119 ++I; 120 Loop &L_0 = *LI.getLoopFor(&*I++); 121 ASSERT_EQ("loop.0", L_0.getHeader()->getName()); 122 Loop &L_0_0 = *LI.getLoopFor(&*I++); 123 ASSERT_EQ("loop.0.0", L_0_0.getHeader()->getName()); 124 Loop &L_0_1 = *LI.getLoopFor(&*I++); 125 ASSERT_EQ("loop.0.1", L_0_1.getHeader()->getName()); 126 Loop &L_0_2 = *LI.getLoopFor(&*I++); 127 ASSERT_EQ("loop.0.2", L_0_2.getHeader()->getName()); 128 Loop &L_1 = *LI.getLoopFor(&*I++); 129 ASSERT_EQ("loop.1", L_1.getHeader()->getName()); 130 Loop &L_1_0 = *LI.getLoopFor(&*I++); 131 ASSERT_EQ("loop.1.0", L_1_0.getHeader()->getName()); 132 Loop &L_1_1 = *LI.getLoopFor(&*I++); 133 ASSERT_EQ("loop.1.1", L_1_1.getHeader()->getName()); 134 Loop &L_1_2 = *LI.getLoopFor(&*I++); 135 ASSERT_EQ("loop.1.2", L_1_2.getHeader()->getName()); 136 137 auto Preorder = LI.getLoopsInPreorder(); 138 ASSERT_EQ(8u, Preorder.size()); 139 EXPECT_EQ(&L_0, Preorder[0]); 140 EXPECT_EQ(&L_0_0, Preorder[1]); 141 EXPECT_EQ(&L_0_1, Preorder[2]); 142 EXPECT_EQ(&L_0_2, Preorder[3]); 143 EXPECT_EQ(&L_1, Preorder[4]); 144 EXPECT_EQ(&L_1_0, Preorder[5]); 145 EXPECT_EQ(&L_1_1, Preorder[6]); 146 EXPECT_EQ(&L_1_2, Preorder[7]); 147 148 auto ReverseSiblingPreorder = LI.getLoopsInReverseSiblingPreorder(); 149 ASSERT_EQ(8u, ReverseSiblingPreorder.size()); 150 EXPECT_EQ(&L_1, ReverseSiblingPreorder[0]); 151 EXPECT_EQ(&L_1_2, ReverseSiblingPreorder[1]); 152 EXPECT_EQ(&L_1_1, ReverseSiblingPreorder[2]); 153 EXPECT_EQ(&L_1_0, ReverseSiblingPreorder[3]); 154 EXPECT_EQ(&L_0, ReverseSiblingPreorder[4]); 155 EXPECT_EQ(&L_0_2, ReverseSiblingPreorder[5]); 156 EXPECT_EQ(&L_0_1, ReverseSiblingPreorder[6]); 157 EXPECT_EQ(&L_0_0, ReverseSiblingPreorder[7]); 158 } 159