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(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(Header); 41 BasicBlock *Exiting = L->getExitingBlock(); 42 43 SimplifiedValuesVector.clear(); 44 unsigned TripCount = SE.getSmallConstantTripCount(L, 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(SimplifiedValues); 52 } 53 } 54 55 std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context, 56 const char *ModuleStr) { 57 SMDiagnostic Err; 58 return parseAssemblyString(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, "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(BBI, 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(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(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(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(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, "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(Y1); 164 EXPECT_TRUE(I1 != SimplifiedValuesVector[0].end()); 165 auto I2 = SimplifiedValuesVector[0].find(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, "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(Y1); 205 EXPECT_TRUE(I1 != SimplifiedValuesVector[5].end()); 206 EXPECT_EQ(cast<ConstantInt>((*I1).second)->getZExtValue(), 5U); 207 auto I2 = SimplifiedValuesVector[5].find(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 " %cmp2 = icmp slt i8* %iv2.0, %iv.0\n" 225 " %cmp3 = icmp ult i8* %iv2.0, %iv.0\n" 226 " %iv.1 = getelementptr inbounds i8, i8* %iv.0, i64 1\n" 227 " %iv2.1 = getelementptr inbounds i8, i8* %iv2.0, i64 1\n" 228 " %exitcond = icmp ne i8* %iv.1, %limit\n" 229 " br i1 %exitcond, label %loop.body, label %loop.exit\n" 230 "loop.exit:\n" 231 " ret void\n" 232 "}\n"; 233 LLVMContext Context; 234 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 235 SimplifiedValuesVectorTy SimplifiedValuesVector; 236 runUnrollAnalyzer(*M, "ptr_cmp", SimplifiedValuesVector); 237 238 // Perform checks 239 Module::iterator MI = M->begin(); 240 Function *F = &*MI++; 241 Function::iterator FI = F->begin(); 242 FI++; // First basic block is entry - skip it. 243 BasicBlock *Header = &*FI; 244 245 BasicBlock::iterator BBI = Header->begin(); 246 std::advance(BBI, 2); 247 Instruction *Cmp1 = &*BBI++; 248 Instruction *Cmp2 = &*BBI++; 249 Instruction *Cmp3 = &*BBI++; 250 // Check simplification expected on the 5th iteration. 251 // Check that "%cmp = icmp eq i8* %iv2.0, %iv.0" is simplified to 0. 252 auto I1 = SimplifiedValuesVector[5].find(Cmp1); 253 EXPECT_TRUE(I1 != SimplifiedValuesVector[5].end()); 254 EXPECT_EQ(cast<ConstantInt>((*I1).second)->getZExtValue(), 0U); 255 // Check that "%cmp2 = icmp slt i8* %iv2.0, %iv.0" does not simplify 256 auto I2 = SimplifiedValuesVector[5].find(Cmp2); 257 EXPECT_TRUE(I2 == SimplifiedValuesVector[5].end()); 258 // Check that "%cmp3 = icmp ult i8* %iv2.0, %iv.0" is simplified to 0. 259 auto I3 = SimplifiedValuesVector[5].find(Cmp3); 260 EXPECT_TRUE(I3 != SimplifiedValuesVector[5].end()); 261 EXPECT_EQ(cast<ConstantInt>((*I1).second)->getZExtValue(), 0U); 262 } 263 264 TEST(UnrollAnalyzerTest, CastSimplifications) { 265 const char *ModuleStr = 266 "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n" 267 "@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" 268 "define void @const_load_cast() {\n" 269 "entry:\n" 270 " br label %loop\n" 271 "\n" 272 "loop:\n" 273 " %iv = phi i64 [ 0, %entry ], [ %inc, %loop ]\n" 274 " %array_const_idx = getelementptr inbounds [10 x i32], [10 x i32]* @known_constant, i64 0, i64 %iv\n" 275 " %const_array_element = load i32, i32* %array_const_idx, align 4\n" 276 " %se = sext i32 %const_array_element to i64\n" 277 " %ze = zext i32 %const_array_element to i64\n" 278 " %tr = trunc i32 %const_array_element to i8\n" 279 " %inc = add nuw nsw i64 %iv, 1\n" 280 " %exitcond86.i = icmp eq i64 %inc, 10\n" 281 " br i1 %exitcond86.i, label %loop.end, label %loop\n" 282 "\n" 283 "loop.end:\n" 284 " ret void\n" 285 "}\n"; 286 287 LLVMContext Context; 288 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 289 SimplifiedValuesVectorTy SimplifiedValuesVector; 290 runUnrollAnalyzer(*M, "const_load_cast", SimplifiedValuesVector); 291 292 // Perform checks 293 Module::iterator MI = M->begin(); 294 Function *F = &*MI++; 295 Function::iterator FI = F->begin(); 296 FI++; // First basic block is entry - skip it. 297 BasicBlock *Header = &*FI++; 298 299 BasicBlock::iterator BBI = Header->begin(); 300 std::advance(BBI, 3); 301 Instruction *Y1 = &*BBI++; 302 Instruction *Y2 = &*BBI++; 303 Instruction *Y3 = &*BBI++; 304 // Check simplification expected on the 5th iteration. 305 // "%se = sext i32 %const_array_element to i64" should be simplified to 259, 306 // "%ze = zext i32 %const_array_element to i64" should be simplified to 259, 307 // "%tr = trunc i32 %const_array_element to i8" should be simplified to 3. 308 auto I1 = SimplifiedValuesVector[5].find(Y1); 309 EXPECT_TRUE(I1 != SimplifiedValuesVector[5].end()); 310 EXPECT_EQ(cast<ConstantInt>((*I1).second)->getZExtValue(), 259U); 311 auto I2 = SimplifiedValuesVector[5].find(Y2); 312 EXPECT_TRUE(I2 != SimplifiedValuesVector[5].end()); 313 EXPECT_EQ(cast<ConstantInt>((*I2).second)->getZExtValue(), 259U); 314 auto I3 = SimplifiedValuesVector[5].find(Y3); 315 EXPECT_TRUE(I3 != SimplifiedValuesVector[5].end()); 316 EXPECT_EQ(cast<ConstantInt>((*I3).second)->getZExtValue(), 3U); 317 } 318