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(i32* %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, i32* %A, i64 %idxprom
  62   store i32 %i, i32* %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 TEST(IVDescriptorsTest, LoopWithScalableTypes) {
 101   // Parse the module.
 102   LLVMContext Context;
 103
 104   std::unique_ptr<Module> M =
 105       parseIR(Context,
 106               R"(define void @foo(<vscale x 4 x float>* %ptr) {
 107 entry:
 108   br label %for.body
 109
 110 for.body:
 111   %lsr.iv1 = phi <vscale x 4 x float>* [ %0, %for.body ], [ %ptr, %entry ]
 112   %j.0117 = phi i64 [ %inc, %for.body ], [ 0, %entry ]
 113   %lsr.iv12 = bitcast <vscale x 4 x float>* %lsr.iv1 to i8*
 114   %inc = add nuw nsw i64 %j.0117, 1
 115   %uglygep = getelementptr i8, i8* %lsr.iv12, i64 4
 116   %0 = bitcast i8* %uglygep to <vscale x 4 x float>*
 117   %cmp = icmp ne i64 %inc, 1024
 118   br i1 %cmp, label %for.body, label %end
 119
 120 end:
 121   ret void
 122 })");
 123
 124   runWithLoopInfoAndSE(
 125       *M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
 126         Function::iterator FI = F.begin();
 127         // First basic block is entry - skip it.
 128         BasicBlock *Header = &*(++FI);
 129         assert(Header->getName() == "for.body");
 130         Loop *L = LI.getLoopFor(Header);
 131         EXPECT_NE(L, nullptr);
 132         PHINode *Inst_iv = dyn_cast<PHINode>(&Header->front());
 133         assert(Inst_iv->getName() == "lsr.iv1");
 134         InductionDescriptor IndDesc;
 135         bool IsInductionPHI =
 136             InductionDescriptor::isInductionPHI(Inst_iv, L, &SE, IndDesc);
 137         EXPECT_FALSE(IsInductionPHI);
 138       });
 139 }
 140
 141 // Depending on how SCEV deals with ptrtoint cast, the step of a phi could be
 142 // a pointer, and InductionDescriptor used to fail with an assertion.
 143 // So just check that it doesn't assert.
 144 TEST(IVDescriptorsTest, LoopWithPtrToInt) {
 145   // Parse the module.
 146   LLVMContext Context;
 147
 148   std::unique_ptr<Module> M = parseIR(Context, R"(
 149       target datalayout = "e-m:e-p:32:32-Fi8-i64:64-v128:64:128-a:0:32-n32-S64"
 150       target triple = "thumbv6m-arm-none-eabi"
 151
 152       declare void @widget()
 153       declare void @wobble(i32)
 154
 155       define void @barney(i8* %arg, i8* %arg18, i32 %arg19) {
 156       bb:
 157         %tmp = ptrtoint i8* %arg to i32
 158         %tmp20 = ptrtoint i8* %arg18 to i32
 159         %tmp21 = or i32 %tmp20, %tmp
 160         %tmp22 = and i32 %tmp21, 3
 161         %tmp23 = icmp eq i32 %tmp22, 0
 162         br i1 %tmp23, label %bb24, label %bb25
 163
 164       bb24:
 165         tail call void @widget()
 166         br label %bb34
 167
 168       bb25:
 169         %tmp26 = sub i32 %tmp, %tmp20
 170         %tmp27 = icmp ult i32 %tmp26, %arg19
 171         br i1 %tmp27, label %bb28, label %bb34
 172
 173       bb28:
 174         br label %bb29
 175
 176       bb29:
 177         %tmp30 = phi i32 [ %tmp31, %bb29 ], [ %arg19, %bb28 ]
 178         tail call void @wobble(i32 %tmp26)
 179         %tmp31 = sub i32 %tmp30, %tmp26
 180         %tmp32 = icmp ugt i32 %tmp31, %tmp26
 181         br i1 %tmp32, label %bb29, label %bb33
 182
 183       bb33:
 184         br label %bb34
 185
 186       bb34:
 187         ret void
 188       })");
 189
 190   runWithLoopInfoAndSE(
 191       *M, "barney", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
 192         Function::iterator FI = F.begin();
 193         // First basic block is entry - skip it.
 194         BasicBlock *Header = &*(++(++(++(++FI))));
 195         assert(Header->getName() == "bb29");
 196         Loop *L = LI.getLoopFor(Header);
 197         EXPECT_NE(L, nullptr);
 198         PHINode *Inst_i = dyn_cast<PHINode>(&Header->front());
 199         assert(Inst_i->getName() == "tmp30");
 200         InductionDescriptor IndDesc;
 201         bool IsInductionPHI =
 202             InductionDescriptor::isInductionPHI(Inst_i, L, &SE, IndDesc);
 203         EXPECT_TRUE(IsInductionPHI);
 204       });
 205 }