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/LoopUnrollAnalyzer.h" 10 #include "llvm/AsmParser/Parser.h" 11 #include "llvm/IR/Dominators.h" 12 #include "llvm/IR/LegacyPassManager.h" 13 #include "llvm/InitializePasses.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; 27 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 } 49 void getAnalysisUsage(AnalysisUsage &AU) const override { 50 AU.addRequired<DominatorTreeWrapperPass>(); 51 AU.addRequired<LoopInfoWrapperPass>(); 52 AU.addRequired<ScalarEvolutionWrapperPass>(); 53 AU.setPreservesAll(); 54 } 55 UnrollAnalyzerTest() : FunctionPass(ID) { 56 initializeUnrollAnalyzerTestPass(*PassRegistry::getPassRegistry()); 57 } 58 }; 59 } 60 61 char UnrollAnalyzerTest::ID = 0; 62 63 std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context, 64 const char *ModuleStr) { 65 SMDiagnostic Err; 66 return parseAssemblyString(ModuleStr, Err, Context); 67 } 68 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 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 } 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 } 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 } 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