llvm/unittests/Analysis/UnrollAnalyzerTest.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-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 }