llvm/unittests/Analysis/IVDescriptorsTest.cpp

   1 //===- IVDescriptorsTest.cpp - IVDescriptors 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/IVDescriptors.h"
  10 #include "llvm/Analysis/AssumptionCache.h"
  11 #include "llvm/Analysis/LoopInfo.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/IR/Module.h"
  17 #include "llvm/Support/SourceMgr.h"
  18 #include "gtest/gtest.h"
  19
  20 using namespace llvm;
  21
  22 /// Build the loop info and scalar evolution for the function and run the Test.
  23 static void runWithLoopInfoAndSE(
  24     Module &M, StringRef FuncName,
  25     function_ref<void(Function &F, LoopInfo &LI, ScalarEvolution &SE)> Test) {
  26   auto *F = M.getFunction(FuncName);
  27   ASSERT_NE(F, nullptr) << "Could not find " << FuncName;
  28
  29   TargetLibraryInfoImpl TLII;
  30   TargetLibraryInfo TLI(TLII);
  31   AssumptionCache AC(*F);
  32   DominatorTree DT(*F);
  33   LoopInfo LI(DT);
  34   ScalarEvolution SE(*F, TLI, AC, DT, LI);
  35
  36   Test(*F, LI, SE);
  37 }
  38
  39 static std::unique_ptr<Module> parseIR(LLVMContext &C, const char *IR) {
  40   SMDiagnostic Err;
  41   std::unique_ptr<Module> Mod = parseAssemblyString(IR, Err, C);
  42   if (!Mod)
  43     Err.print("IVDescriptorsTests", errs());
  44   return Mod;
  45 }
  46
  47 // This tests that IVDescriptors can obtain the induction binary operator for
  48 // integer induction variables. And getExactFPMathInst() correctly return the
  49 // expected behavior, i.e. no FMF algebra.
  50 TEST(IVDescriptorsTest, LoopWithSingleLatch) {
  51   // Parse the module.
  52   LLVMContext Context;
  53
  54   std::unique_ptr<Module> M = parseIR(
  55     Context,
  56     R"(define void @foo(ptr %A, i32 %ub) {
  57 entry:
  58   br label %for.body
  59 for.body:
  60   %i = phi i32 [ 0, %entry ], [ %inc, %for.body ]
  61   %idxprom = sext i32 %i to i64
  62   %arrayidx = getelementptr inbounds i32, ptr %A, i64 %idxprom
  63   store i32 %i, ptr %arrayidx, align 4
  64   %inc = add nsw i32 %i, 1
  65   %cmp = icmp slt i32 %inc, %ub
  66   br i1 %cmp, label %for.body, label %for.exit
  67 for.exit:
  68   br label %for.end
  69 for.end:
  70   ret void
  71 })"
  72     );
  73
  74   runWithLoopInfoAndSE(
  75       *M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
  76         Function::iterator FI = F.begin();
  77         // First basic block is entry - skip it.
  78         BasicBlock *Header = &*(++FI);
  79         assert(Header->getName() == "for.body");
  80         Loop *L = LI.getLoopFor(Header);
  81         EXPECT_NE(L, nullptr);
  82         PHINode *Inst_i = dyn_cast<PHINode>(&Header->front());
  83         assert(Inst_i->getName() == "i");
  84         InductionDescriptor IndDesc;
  85         bool IsInductionPHI =
  86             InductionDescriptor::isInductionPHI(Inst_i, L, &SE, IndDesc);
  87         EXPECT_TRUE(IsInductionPHI);
  88         Instruction *Inst_inc = nullptr;
  89         BasicBlock::iterator BBI = Header->begin();
  90         do {
  91           if ((&*BBI)->getName() == "inc")
  92             Inst_inc = &*BBI;
  93           ++BBI;
  94         } while (!Inst_inc);
  95         assert(Inst_inc->getName() == "inc");
  96         EXPECT_EQ(IndDesc.getInductionBinOp(), Inst_inc);
  97         EXPECT_EQ(IndDesc.getExactFPMathInst(), nullptr);
  98       });
  99 }
 100
 101 // Depending on how SCEV deals with ptrtoint cast, the step of a phi could be
 102 // a pointer, and InductionDescriptor used to fail with an assertion.
 103 // So just check that it doesn't assert.
 104 TEST(IVDescriptorsTest, LoopWithPtrToInt) {
 105   // Parse the module.
 106   LLVMContext Context;
 107
 108   std::unique_ptr<Module> M = parseIR(Context, R"(
 109       target datalayout = "e-m:e-p:32:32-Fi8-i64:64-v128:64:128-a:0:32-n32-S64"
 110       target triple = "thumbv6m-arm-none-eabi"
 111
 112       declare void @widget()
 113       declare void @wobble(i32)
 114
 115       define void @barney(ptr %arg, ptr %arg18, i32 %arg19) {
 116       bb:
 117         %tmp = ptrtoint ptr %arg to i32
 118         %tmp20 = ptrtoint ptr %arg18 to i32
 119         %tmp21 = or i32 %tmp20, %tmp
 120         %tmp22 = and i32 %tmp21, 3
 121         %tmp23 = icmp eq i32 %tmp22, 0
 122         br i1 %tmp23, label %bb24, label %bb25
 123
 124       bb24:
 125         tail call void @widget()
 126         br label %bb34
 127
 128       bb25:
 129         %tmp26 = sub i32 %tmp, %tmp20
 130         %tmp27 = icmp ult i32 %tmp26, %arg19
 131         br i1 %tmp27, label %bb28, label %bb34
 132
 133       bb28:
 134         br label %bb29
 135
 136       bb29:
 137         %tmp30 = phi i32 [ %tmp31, %bb29 ], [ %arg19, %bb28 ]
 138         tail call void @wobble(i32 %tmp26)
 139         %tmp31 = sub i32 %tmp30, %tmp26
 140         %tmp32 = icmp ugt i32 %tmp31, %tmp26
 141         br i1 %tmp32, label %bb29, label %bb33
 142
 143       bb33:
 144         br label %bb34
 145
 146       bb34:
 147         ret void
 148       })");
 149
 150   runWithLoopInfoAndSE(
 151       *M, "barney", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
 152         Function::iterator FI = F.begin();
 153         // First basic block is entry - skip it.
 154         BasicBlock *Header = &*(++(++(++(++FI))));
 155         assert(Header->getName() == "bb29");
 156         Loop *L = LI.getLoopFor(Header);
 157         EXPECT_NE(L, nullptr);
 158         PHINode *Inst_i = dyn_cast<PHINode>(&Header->front());
 159         assert(Inst_i->getName() == "tmp30");
 160         InductionDescriptor IndDesc;
 161         bool IsInductionPHI =
 162             InductionDescriptor::isInductionPHI(Inst_i, L, &SE, IndDesc);
 163         EXPECT_TRUE(IsInductionPHI);
 164       });
 165 }
 166
 167 // This tests that correct identity value is returned for a RecurrenceDescriptor
 168 // that describes FMin reduction idiom.
 169 TEST(IVDescriptorsTest, FMinRednIdentity) {
 170   // Parse the module.
 171   LLVMContext Context;
 172
 173   std::unique_ptr<Module> M = parseIR(Context,
 174                                       R"(define float @foo(ptr %A, i64 %ub) {
 175 entry:
 176   br label %for.body
 177
 178 for.body:
 179   %i = phi i64 [ 0, %entry ], [ %i.next, %for.body ]
 180   %fmin = phi float [ 1.000000e+00, %entry ], [ %fmin.next, %for.body ]
 181   %arrayidx = getelementptr inbounds float, ptr %A, i64 %i
 182   %ld = load float, ptr %arrayidx
 183   %fmin.cmp = fcmp nnan nsz olt float %fmin, %ld
 184   %fmin.next = select nnan nsz i1 %fmin.cmp, float %fmin, float %ld
 185   %i.next = add nsw i64 %i, 1
 186   %cmp = icmp slt i64 %i.next, %ub
 187   br i1 %cmp, label %for.body, label %for.end
 188
 189 for.end:
 190   %fmin.lcssa = phi float [ %fmin.next, %for.body ]
 191   ret float %fmin.lcssa
 192 })");
 193
 194   runWithLoopInfoAndSE(
 195       *M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
 196         Function::iterator FI = F.begin();
 197         // First basic block is entry - skip it.
 198         BasicBlock *Header = &*(++FI);
 199         assert(Header->getName() == "for.body");
 200         Loop *L = LI.getLoopFor(Header);
 201         EXPECT_NE(L, nullptr);
 202         BasicBlock::iterator BBI = Header->begin();
 203         assert((&*BBI)->getName() == "i");
 204         ++BBI;
 205         PHINode *Phi = dyn_cast<PHINode>(&*BBI);
 206         assert(Phi->getName() == "fmin");
 207         RecurrenceDescriptor Rdx;
 208         bool IsRdxPhi = RecurrenceDescriptor::isReductionPHI(Phi, L, Rdx);
 209         EXPECT_TRUE(IsRdxPhi);
 210         RecurKind Kind = Rdx.getRecurrenceKind();
 211         EXPECT_EQ(Kind, RecurKind::FMin);
 212       });
 213 }
 214
 215 // This tests that correct identity value is returned for a RecurrenceDescriptor
 216 // that describes FMax reduction idiom.
 217 TEST(IVDescriptorsTest, FMaxRednIdentity) {
 218   // Parse the module.
 219   LLVMContext Context;
 220
 221   std::unique_ptr<Module> M = parseIR(Context,
 222                                       R"(define float @foo(ptr %A, i64 %ub) {
 223 entry:
 224   br label %for.body
 225
 226 for.body:
 227   %i = phi i64 [ 0, %entry ], [ %i.next, %for.body ]
 228   %fmax = phi float [ 1.000000e+00, %entry ], [ %fmax.next, %for.body ]
 229   %arrayidx = getelementptr inbounds float, ptr %A, i64 %i
 230   %ld = load float, ptr %arrayidx
 231   %fmax.cmp = fcmp nnan nsz ogt float %fmax, %ld
 232   %fmax.next = select nnan nsz i1 %fmax.cmp, float %fmax, float %ld
 233   %i.next = add nsw i64 %i, 1
 234   %cmp = icmp slt i64 %i.next, %ub
 235   br i1 %cmp, label %for.body, label %for.end
 236
 237 for.end:
 238   %fmax.lcssa = phi float [ %fmax.next, %for.body ]
 239   ret float %fmax.lcssa
 240 })");
 241
 242   runWithLoopInfoAndSE(
 243       *M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
 244         Function::iterator FI = F.begin();
 245         // First basic block is entry - skip it.
 246         BasicBlock *Header = &*(++FI);
 247         assert(Header->getName() == "for.body");
 248         Loop *L = LI.getLoopFor(Header);
 249         EXPECT_NE(L, nullptr);
 250         BasicBlock::iterator BBI = Header->begin();
 251         assert((&*BBI)->getName() == "i");
 252         ++BBI;
 253         PHINode *Phi = dyn_cast<PHINode>(&*BBI);
 254         assert(Phi->getName() == "fmax");
 255         RecurrenceDescriptor Rdx;
 256         bool IsRdxPhi = RecurrenceDescriptor::isReductionPHI(Phi, L, Rdx);
 257         EXPECT_TRUE(IsRdxPhi);
 258         RecurKind Kind = Rdx.getRecurrenceKind();
 259         EXPECT_EQ(Kind, RecurKind::FMax);
 260       });
 261 }