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
19using namespace llvm;
20
21typedef SmallVector<DenseMap<Value *, Value *>, 16> SimplifiedValuesVectorTy;
22
23/// Build loop info and scalar evolution for the function and run the analysis.
24static void
25runUnrollAnalyzer(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 *Header = &*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
55std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context,
56 const char *ModuleStr) {
57 SMDiagnostic Err;
58 return parseAssemblyString(AsmString: ModuleStr, Err, Context);
59}
60
61TEST(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 *Header = &*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
119TEST(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 *Header = &*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
169TEST(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 *Header = &*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
212TEST(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 *Header = &*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
253TEST(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 *Header = &*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

source code of llvm/unittests/Analysis/UnrollAnalyzerTest.cpp