318 lines · cpp
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-exception6//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 void25runUnrollAnalyzer(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(M.getTargetTriple());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 55std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context,56 const char *ModuleStr) {57 SMDiagnostic Err;58 return parseAssemblyString(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, "propagate_loop_phis", SimplifiedValuesVector);83 unsigned TripCount = SimplifiedValuesVector.size();84 85 // Perform checks86 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 198 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 false103 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 8109 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 false114 I2 = SimplifiedValuesVector[TripCount - 1].find(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, "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 IV160 // 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.next163 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 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, "branch_iv_trunc", SimplifiedValuesVector);189 190 // Perform checks191 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 5203 // 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 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, ptr %a, i64 40\n"218 " %start.iv2 = getelementptr i8, ptr %a, i64 7\n"219 " br label %loop.body\n"220 "loop.body:\n"221 " %iv.0 = phi ptr [ %a, %entry ], [ %iv.1, %loop.body ]\n"222 " %iv2.0 = phi ptr [ %start.iv2, %entry ], [ %iv2.1, %loop.body ]\n"223 " %cmp = icmp eq ptr %iv2.0, %iv.0\n"224 " %cmp2 = icmp slt ptr %iv2.0, %iv.0\n"225 " %cmp3 = icmp ult ptr %iv2.0, %iv.0\n"226 " %iv.1 = getelementptr inbounds i8, ptr %iv.0, i64 1\n"227 " %iv2.1 = getelementptr inbounds i8, ptr %iv2.0, i64 1\n"228 " %exitcond = icmp ne ptr %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 checks239 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 ptr %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 ptr %iv2.0, %iv.0" does not simplify256 auto I2 = SimplifiedValuesVector[5].find(Cmp2);257 EXPECT_TRUE(I2 == SimplifiedValuesVector[5].end());258 // Check that "%cmp3 = icmp ult ptr %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 264TEST(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], ptr @known_constant, i64 0, i64 %iv\n"275 " %const_array_element = load i32, ptr %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 checks293 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