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