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 // 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(i8* %arg, i8* %arg18, i32 %arg19) {
115       bb:
116         %tmp = ptrtoint i8* %arg to i32
117         %tmp20 = ptrtoint i8* %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