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
runWithLoopInfo(Module & M,StringRef FuncName,function_ref<void (Function & F,LoopInfo & LI)> Test)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
makeLLVMModule(LLVMContext & Context,const char * ModuleStr)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.
TEST(LoopInfoTest,LoopWithSingleLatch)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
TEST(LoopInfoTest,PreorderTraversals)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