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