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 }
206