1 //===- UnrollAnalyzerTest.cpp - UnrollAnalyzer 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/LoopUnrollAnalyzer.h"
11 #include "llvm/AsmParser/Parser.h"
12 #include "llvm/IR/Dominators.h"
13 #include "llvm/IR/LegacyPassManager.h"
14 #include "llvm/Support/SourceMgr.h"
15 #include "gtest/gtest.h"
16
17 using namespace llvm;
18 namespace llvm {
19 void initializeUnrollAnalyzerTestPass(PassRegistry &);
20
21 static SmallVector<DenseMap<Value *, Constant *>, 16> SimplifiedValuesVector;
22 static unsigned TripCount = 0;
23
24 namespace {
25 struct UnrollAnalyzerTest : public FunctionPass {
26 static char ID;
runOnFunctionllvm::__anoncb0a0a840111::UnrollAnalyzerTest27 bool runOnFunction(Function &F) override {
28 LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
29 ScalarEvolution *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
30
31 Function::iterator FI = F.begin();
32 FI++; // First basic block is entry - skip it.
33 BasicBlock *Header = &*FI++;
34 Loop *L = LI->getLoopFor(Header);
35 BasicBlock *Exiting = L->getExitingBlock();
36
37 SimplifiedValuesVector.clear();
38 TripCount = SE->getSmallConstantTripCount(L, Exiting);
39 for (unsigned Iteration = 0; Iteration < TripCount; Iteration++) {
40 DenseMap<Value *, Constant *> SimplifiedValues;
41 UnrolledInstAnalyzer Analyzer(Iteration, SimplifiedValues, *SE, L);
42 for (auto *BB : L->getBlocks())
43 for (Instruction &I : *BB)
44 Analyzer.visit(I);
45 SimplifiedValuesVector.push_back(SimplifiedValues);
46 }
47 return false;
48 }
getAnalysisUsagellvm::__anoncb0a0a840111::UnrollAnalyzerTest49 void getAnalysisUsage(AnalysisUsage &AU) const override {
50 AU.addRequired<DominatorTreeWrapperPass>();
51 AU.addRequired<LoopInfoWrapperPass>();
52 AU.addRequired<ScalarEvolutionWrapperPass>();
53 AU.setPreservesAll();
54 }
UnrollAnalyzerTestllvm::__anoncb0a0a840111::UnrollAnalyzerTest55 UnrollAnalyzerTest() : FunctionPass(ID) {
56 initializeUnrollAnalyzerTestPass(*PassRegistry::getPassRegistry());
57 }
58 };
59 }
60
61 char UnrollAnalyzerTest::ID = 0;
62
makeLLVMModule(LLVMContext & Context,const char * ModuleStr)63 std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context,
64 const char *ModuleStr) {
65 SMDiagnostic Err;
66 return parseAssemblyString(ModuleStr, Err, Context);
67 }
68
TEST(UnrollAnalyzerTest,BasicSimplifications)69 TEST(UnrollAnalyzerTest, BasicSimplifications) {
70 const char *ModuleStr =
71 "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n"
72 "define i64 @propagate_loop_phis() {\n"
73 "entry:\n"
74 " br label %loop\n"
75 "loop:\n"
76 " %iv = phi i64 [ 0, %entry ], [ %inc, %loop ]\n"
77 " %x0 = phi i64 [ 0, %entry ], [ %x2, %loop ]\n"
78 " %x1 = or i64 %x0, 1\n"
79 " %x2 = or i64 %x1, 2\n"
80 " %inc = add nuw nsw i64 %iv, 1\n"
81 " %cond = icmp sge i64 %inc, 8\n"
82 " br i1 %cond, label %loop.end, label %loop\n"
83 "loop.end:\n"
84 " %x.lcssa = phi i64 [ %x2, %loop ]\n"
85 " ret i64 %x.lcssa\n"
86 "}\n";
87 UnrollAnalyzerTest *P = new UnrollAnalyzerTest();
88 LLVMContext Context;
89 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
90 legacy::PassManager Passes;
91 Passes.add(P);
92 Passes.run(*M);
93
94 // Perform checks
95 Module::iterator MI = M->begin();
96 Function *F = &*MI++;
97 Function::iterator FI = F->begin();
98 FI++; // First basic block is entry - skip it.
99 BasicBlock *Header = &*FI++;
100
101 BasicBlock::iterator BBI = Header->begin();
102 std::advance(BBI, 4);
103 Instruction *Y1 = &*BBI++;
104 Instruction *Y2 = &*BBI++;
105 // Check simplification expected on the 1st iteration.
106 // Check that "%inc = add nuw nsw i64 %iv, 1" is simplified to 1
107 auto I1 = SimplifiedValuesVector[0].find(Y1);
108 EXPECT_TRUE(I1 != SimplifiedValuesVector[0].end());
109 EXPECT_EQ(cast<ConstantInt>((*I1).second)->getZExtValue(), 1U);
110
111 // Check that "%cond = icmp sge i64 %inc, 10" is simplified to false
112 auto I2 = SimplifiedValuesVector[0].find(Y2);
113 EXPECT_TRUE(I2 != SimplifiedValuesVector[0].end());
114 EXPECT_FALSE(cast<ConstantInt>((*I2).second)->getZExtValue());
115
116 // Check simplification expected on the last iteration.
117 // Check that "%inc = add nuw nsw i64 %iv, 1" is simplified to 8
118 I1 = SimplifiedValuesVector[TripCount - 1].find(Y1);
119 EXPECT_TRUE(I1 != SimplifiedValuesVector[TripCount - 1].end());
120 EXPECT_EQ(cast<ConstantInt>((*I1).second)->getZExtValue(), TripCount);
121
122 // Check that "%cond = icmp sge i64 %inc, 10" is simplified to false
123 I2 = SimplifiedValuesVector[TripCount - 1].find(Y2);
124 EXPECT_TRUE(I2 != SimplifiedValuesVector[TripCount - 1].end());
125 EXPECT_TRUE(cast<ConstantInt>((*I2).second)->getZExtValue());
126 }
127
TEST(UnrollAnalyzerTest,OuterLoopSimplification)128 TEST(UnrollAnalyzerTest, OuterLoopSimplification) {
129 const char *ModuleStr =
130 "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n"
131 "define void @foo() {\n"
132 "entry:\n"
133 " br label %outer.loop\n"
134 "outer.loop:\n"
135 " %iv.outer = phi i64 [ 0, %entry ], [ %iv.outer.next, %outer.loop.latch ]\n"
136 " %iv.outer.next = add nuw nsw i64 %iv.outer, 1\n"
137 " br label %inner.loop\n"
138 "inner.loop:\n"
139 " %iv.inner = phi i64 [ 0, %outer.loop ], [ %iv.inner.next, %inner.loop ]\n"
140 " %iv.inner.next = add nuw nsw i64 %iv.inner, 1\n"
141 " %exitcond.inner = icmp eq i64 %iv.inner.next, 1000\n"
142 " br i1 %exitcond.inner, label %outer.loop.latch, label %inner.loop\n"
143 "outer.loop.latch:\n"
144 " %exitcond.outer = icmp eq i64 %iv.outer.next, 40\n"
145 " br i1 %exitcond.outer, label %exit, label %outer.loop\n"
146 "exit:\n"
147 " ret void\n"
148 "}\n";
149
150 UnrollAnalyzerTest *P = new UnrollAnalyzerTest();
151 LLVMContext Context;
152 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
153 legacy::PassManager Passes;
154 Passes.add(P);
155 Passes.run(*M);
156
157 Module::iterator MI = M->begin();
158 Function *F = &*MI++;
159 Function::iterator FI = F->begin();
160 FI++;
161 BasicBlock *Header = &*FI++;
162 BasicBlock *InnerBody = &*FI++;
163
164 BasicBlock::iterator BBI = Header->begin();
165 BBI++;
166 Instruction *Y1 = &*BBI;
167 BBI = InnerBody->begin();
168 BBI++;
169 Instruction *Y2 = &*BBI;
170 // Check that we can simplify IV of the outer loop, but can't simplify the IV
171 // of the inner loop if we only know the iteration number of the outer loop.
172 //
173 // Y1 is %iv.outer.next, Y2 is %iv.inner.next
174 auto I1 = SimplifiedValuesVector[0].find(Y1);
175 EXPECT_TRUE(I1 != SimplifiedValuesVector[0].end());
176 auto I2 = SimplifiedValuesVector[0].find(Y2);
177 EXPECT_TRUE(I2 == SimplifiedValuesVector[0].end());
178 }
TEST(UnrollAnalyzerTest,CmpSimplifications)179 TEST(UnrollAnalyzerTest, CmpSimplifications) {
180 const char *ModuleStr =
181 "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n"
182 "define void @branch_iv_trunc() {\n"
183 "entry:\n"
184 " br label %for.body\n"
185 "for.body:\n"
186 " %indvars.iv = phi i64 [ 0, %entry ], [ %tmp3, %for.body ]\n"
187 " %tmp2 = trunc i64 %indvars.iv to i32\n"
188 " %cmp3 = icmp eq i32 %tmp2, 5\n"
189 " %tmp3 = add nuw nsw i64 %indvars.iv, 1\n"
190 " %exitcond = icmp eq i64 %tmp3, 10\n"
191 " br i1 %exitcond, label %for.end, label %for.body\n"
192 "for.end:\n"
193 " ret void\n"
194 "}\n";
195 UnrollAnalyzerTest *P = new UnrollAnalyzerTest();
196 LLVMContext Context;
197 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
198 legacy::PassManager Passes;
199 Passes.add(P);
200 Passes.run(*M);
201
202 // Perform checks
203 Module::iterator MI = M->begin();
204 Function *F = &*MI++;
205 Function::iterator FI = F->begin();
206 FI++; // First basic block is entry - skip it.
207 BasicBlock *Header = &*FI++;
208
209 BasicBlock::iterator BBI = Header->begin();
210 BBI++;
211 Instruction *Y1 = &*BBI++;
212 Instruction *Y2 = &*BBI++;
213 // Check simplification expected on the 5th iteration.
214 // Check that "%tmp2 = trunc i64 %indvars.iv to i32" is simplified to 5
215 // and "%cmp3 = icmp eq i32 %tmp2, 5" is simplified to 1 (i.e. true).
216 auto I1 = SimplifiedValuesVector[5].find(Y1);
217 EXPECT_TRUE(I1 != SimplifiedValuesVector[5].end());
218 EXPECT_EQ(cast<ConstantInt>((*I1).second)->getZExtValue(), 5U);
219 auto I2 = SimplifiedValuesVector[5].find(Y2);
220 EXPECT_TRUE(I2 != SimplifiedValuesVector[5].end());
221 EXPECT_EQ(cast<ConstantInt>((*I2).second)->getZExtValue(), 1U);
222 }
TEST(UnrollAnalyzerTest,PtrCmpSimplifications)223 TEST(UnrollAnalyzerTest, PtrCmpSimplifications) {
224 const char *ModuleStr =
225 "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n"
226 "define void @ptr_cmp(i8 *%a) {\n"
227 "entry:\n"
228 " %limit = getelementptr i8, i8* %a, i64 40\n"
229 " %start.iv2 = getelementptr i8, i8* %a, i64 7\n"
230 " br label %loop.body\n"
231 "loop.body:\n"
232 " %iv.0 = phi i8* [ %a, %entry ], [ %iv.1, %loop.body ]\n"
233 " %iv2.0 = phi i8* [ %start.iv2, %entry ], [ %iv2.1, %loop.body ]\n"
234 " %cmp = icmp eq i8* %iv2.0, %iv.0\n"
235 " %iv.1 = getelementptr inbounds i8, i8* %iv.0, i64 1\n"
236 " %iv2.1 = getelementptr inbounds i8, i8* %iv2.0, i64 1\n"
237 " %exitcond = icmp ne i8* %iv.1, %limit\n"
238 " br i1 %exitcond, label %loop.body, label %loop.exit\n"
239 "loop.exit:\n"
240 " ret void\n"
241 "}\n";
242 UnrollAnalyzerTest *P = new UnrollAnalyzerTest();
243 LLVMContext Context;
244 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
245 legacy::PassManager Passes;
246 Passes.add(P);
247 Passes.run(*M);
248
249 // Perform checks
250 Module::iterator MI = M->begin();
251 Function *F = &*MI++;
252 Function::iterator FI = F->begin();
253 FI++; // First basic block is entry - skip it.
254 BasicBlock *Header = &*FI;
255
256 BasicBlock::iterator BBI = Header->begin();
257 std::advance(BBI, 2);
258 Instruction *Y1 = &*BBI;
259 // Check simplification expected on the 5th iteration.
260 // Check that "%cmp = icmp eq i8* %iv2.0, %iv.0" is simplified to 0.
261 auto I1 = SimplifiedValuesVector[5].find(Y1);
262 EXPECT_TRUE(I1 != SimplifiedValuesVector[5].end());
263 EXPECT_EQ(cast<ConstantInt>((*I1).second)->getZExtValue(), 0U);
264 }
TEST(UnrollAnalyzerTest,CastSimplifications)265 TEST(UnrollAnalyzerTest, CastSimplifications) {
266 const char *ModuleStr =
267 "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n"
268 "@known_constant = internal unnamed_addr constant [10 x i32] [i32 0, i32 1, i32 0, i32 1, i32 0, i32 259, i32 0, i32 1, i32 0, i32 1], align 16\n"
269 "define void @const_load_cast() {\n"
270 "entry:\n"
271 " br label %loop\n"
272 "\n"
273 "loop:\n"
274 " %iv = phi i64 [ 0, %entry ], [ %inc, %loop ]\n"
275 " %array_const_idx = getelementptr inbounds [10 x i32], [10 x i32]* @known_constant, i64 0, i64 %iv\n"
276 " %const_array_element = load i32, i32* %array_const_idx, align 4\n"
277 " %se = sext i32 %const_array_element to i64\n"
278 " %ze = zext i32 %const_array_element to i64\n"
279 " %tr = trunc i32 %const_array_element to i8\n"
280 " %inc = add nuw nsw i64 %iv, 1\n"
281 " %exitcond86.i = icmp eq i64 %inc, 10\n"
282 " br i1 %exitcond86.i, label %loop.end, label %loop\n"
283 "\n"
284 "loop.end:\n"
285 " ret void\n"
286 "}\n";
287
288 UnrollAnalyzerTest *P = new UnrollAnalyzerTest();
289 LLVMContext Context;
290 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
291 legacy::PassManager Passes;
292 Passes.add(P);
293 Passes.run(*M);
294
295 // Perform checks
296 Module::iterator MI = M->begin();
297 Function *F = &*MI++;
298 Function::iterator FI = F->begin();
299 FI++; // First basic block is entry - skip it.
300 BasicBlock *Header = &*FI++;
301
302 BasicBlock::iterator BBI = Header->begin();
303 std::advance(BBI, 3);
304 Instruction *Y1 = &*BBI++;
305 Instruction *Y2 = &*BBI++;
306 Instruction *Y3 = &*BBI++;
307 // Check simplification expected on the 5th iteration.
308 // "%se = sext i32 %const_array_element to i64" should be simplified to 259,
309 // "%ze = zext i32 %const_array_element to i64" should be simplified to 259,
310 // "%tr = trunc i32 %const_array_element to i8" should be simplified to 3.
311 auto I1 = SimplifiedValuesVector[5].find(Y1);
312 EXPECT_TRUE(I1 != SimplifiedValuesVector[5].end());
313 EXPECT_EQ(cast<ConstantInt>((*I1).second)->getZExtValue(), 259U);
314 auto I2 = SimplifiedValuesVector[5].find(Y2);
315 EXPECT_TRUE(I2 != SimplifiedValuesVector[5].end());
316 EXPECT_EQ(cast<ConstantInt>((*I2).second)->getZExtValue(), 259U);
317 auto I3 = SimplifiedValuesVector[5].find(Y3);
318 EXPECT_TRUE(I3 != SimplifiedValuesVector[5].end());
319 EXPECT_EQ(cast<ConstantInt>((*I3).second)->getZExtValue(), 3U);
320 }
321
322 } // end namespace llvm
323
324 INITIALIZE_PASS_BEGIN(UnrollAnalyzerTest, "unrollanalyzertestpass",
325 "unrollanalyzertestpass", false, false)
326 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
327 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
328 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
329 INITIALIZE_PASS_END(UnrollAnalyzerTest, "unrollanalyzertestpass",
330 "unrollanalyzertestpass", false, false)
331