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 loop id handling for a loop with multiple latches.
86 TEST(LoopInfoTest, LoopWithMultipleLatches) {
87   const char *ModuleStr =
88       "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n"
89       "define void @foo(i32 %n) {\n"
90       "entry:\n"
91       "  br i1 undef, label %for.cond, label %for.end\n"
92       "for.cond:\n"
93       "  %i.0 = phi i32 [ 0, %entry ], [ %inc, %latch.1 ], [ %inc, %latch.2 ]\n"
94       "  %inc = add nsw i32 %i.0, 1\n"
95       "  %cmp = icmp slt i32 %i.0, %n\n"
96       "  br i1 %cmp, label %latch.1, label %for.end\n"
97       "latch.1:\n"
98       "  br i1 undef, label %for.cond, label %latch.2, !llvm.loop !0\n"
99       "latch.2:\n"
100       "  br label %for.cond, !llvm.loop !0\n"
101       "for.end:\n"
102       "  ret void\n"
103       "}\n"
104       "!0 = distinct !{!0, !1}\n"
105       "!1 = !{!\"llvm.loop.distribute.enable\", i1 true}\n";
106 
107   // Parse the module.
108   LLVMContext Context;
109   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
110 
111   runWithLoopInfo(*M, "foo", [&](Function &F, LoopInfo &LI) {
112     Function::iterator FI = F.begin();
113     // First basic block is entry - skip it.
114     BasicBlock *Header = &*(++FI);
115     assert(Header->getName() == "for.cond");
116     Loop *L = LI.getLoopFor(Header);
117     EXPECT_NE(L, nullptr);
118 
119     // This loop is not in simplified form.
120     EXPECT_FALSE(L->isLoopSimplifyForm());
121 
122     // Try to get and set the metadata id for the loop.
123     MDNode *OldLoopID = L->getLoopID();
124     EXPECT_NE(OldLoopID, nullptr);
125 
126     MDNode *NewLoopID = MDNode::get(Context, {nullptr});
127     // Set operand 0 to refer to the loop id itself.
128     NewLoopID->replaceOperandWith(0, NewLoopID);
129 
130     L->setLoopID(NewLoopID);
131     EXPECT_EQ(L->getLoopID(), NewLoopID);
132     EXPECT_NE(L->getLoopID(), OldLoopID);
133 
134     L->setLoopID(OldLoopID);
135     EXPECT_EQ(L->getLoopID(), OldLoopID);
136     EXPECT_NE(L->getLoopID(), NewLoopID);
137   });
138 }
139 
140 TEST(LoopInfoTest, PreorderTraversals) {
141   const char *ModuleStr = "define void @f() {\n"
142                           "entry:\n"
143                           "  br label %loop.0\n"
144                           "loop.0:\n"
145                           "  br i1 undef, label %loop.0.0, label %loop.1\n"
146                           "loop.0.0:\n"
147                           "  br i1 undef, label %loop.0.0, label %loop.0.1\n"
148                           "loop.0.1:\n"
149                           "  br i1 undef, label %loop.0.1, label %loop.0.2\n"
150                           "loop.0.2:\n"
151                           "  br i1 undef, label %loop.0.2, label %loop.0\n"
152                           "loop.1:\n"
153                           "  br i1 undef, label %loop.1.0, label %end\n"
154                           "loop.1.0:\n"
155                           "  br i1 undef, label %loop.1.0, label %loop.1.1\n"
156                           "loop.1.1:\n"
157                           "  br i1 undef, label %loop.1.1, label %loop.1.2\n"
158                           "loop.1.2:\n"
159                           "  br i1 undef, label %loop.1.2, label %loop.1\n"
160                           "end:\n"
161                           "  ret void\n"
162                           "}\n";
163   // Parse the module.
164   LLVMContext Context;
165   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
166   Function &F = *M->begin();
167 
168   DominatorTree DT(F);
169   LoopInfo LI;
170   LI.analyze(DT);
171 
172   Function::iterator I = F.begin();
173   ASSERT_EQ("entry", I->getName());
174   ++I;
175   Loop &L_0 = *LI.getLoopFor(&*I++);
176   ASSERT_EQ("loop.0", L_0.getHeader()->getName());
177   Loop &L_0_0 = *LI.getLoopFor(&*I++);
178   ASSERT_EQ("loop.0.0", L_0_0.getHeader()->getName());
179   Loop &L_0_1 = *LI.getLoopFor(&*I++);
180   ASSERT_EQ("loop.0.1", L_0_1.getHeader()->getName());
181   Loop &L_0_2 = *LI.getLoopFor(&*I++);
182   ASSERT_EQ("loop.0.2", L_0_2.getHeader()->getName());
183   Loop &L_1 = *LI.getLoopFor(&*I++);
184   ASSERT_EQ("loop.1", L_1.getHeader()->getName());
185   Loop &L_1_0 = *LI.getLoopFor(&*I++);
186   ASSERT_EQ("loop.1.0", L_1_0.getHeader()->getName());
187   Loop &L_1_1 = *LI.getLoopFor(&*I++);
188   ASSERT_EQ("loop.1.1", L_1_1.getHeader()->getName());
189   Loop &L_1_2 = *LI.getLoopFor(&*I++);
190   ASSERT_EQ("loop.1.2", L_1_2.getHeader()->getName());
191 
192   auto Preorder = LI.getLoopsInPreorder();
193   ASSERT_EQ(8u, Preorder.size());
194   EXPECT_EQ(&L_0, Preorder[0]);
195   EXPECT_EQ(&L_0_0, Preorder[1]);
196   EXPECT_EQ(&L_0_1, Preorder[2]);
197   EXPECT_EQ(&L_0_2, Preorder[3]);
198   EXPECT_EQ(&L_1, Preorder[4]);
199   EXPECT_EQ(&L_1_0, Preorder[5]);
200   EXPECT_EQ(&L_1_1, Preorder[6]);
201   EXPECT_EQ(&L_1_2, Preorder[7]);
202 
203   auto ReverseSiblingPreorder = LI.getLoopsInReverseSiblingPreorder();
204   ASSERT_EQ(8u, ReverseSiblingPreorder.size());
205   EXPECT_EQ(&L_1, ReverseSiblingPreorder[0]);
206   EXPECT_EQ(&L_1_2, ReverseSiblingPreorder[1]);
207   EXPECT_EQ(&L_1_1, ReverseSiblingPreorder[2]);
208   EXPECT_EQ(&L_1_0, ReverseSiblingPreorder[3]);
209   EXPECT_EQ(&L_0, ReverseSiblingPreorder[4]);
210   EXPECT_EQ(&L_0_2, ReverseSiblingPreorder[5]);
211   EXPECT_EQ(&L_0_1, ReverseSiblingPreorder[6]);
212   EXPECT_EQ(&L_0_0, ReverseSiblingPreorder[7]);
213 }
214