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