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.
runWithLoopInfoAndSE(Module & M,StringRef FuncName,function_ref<void (Function & F,LoopInfo & LI,ScalarEvolution & SE)> 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
parseIR(LLVMContext & C,const char * IR)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 hasUnsafeAlgebra() and
48 // getUnsafeAlgebraInst() correctly return the expected behavior, i.e. no unsafe
49 // algebra.
TEST(IVDescriptorsTest,LoopWithSingleLatch)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(i32* %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, i32* %A, i64 %idxprom
63 store i32 %i, i32* %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_FALSE(IndDesc.hasUnsafeAlgebra());
98 EXPECT_EQ(IndDesc.getUnsafeAlgebraInst(), nullptr);
99 });
100 }
101
102 // Depending on how SCEV deals with ptrtoint cast, the step of a phi could be
103 // a pointer, and InductionDescriptor used to fail with an assertion.
104 // So just check that it doesn't assert.
TEST(IVDescriptorsTest,LoopWithPtrToInt)105 TEST(IVDescriptorsTest, LoopWithPtrToInt) {
106 // Parse the module.
107 LLVMContext Context;
108
109 std::unique_ptr<Module> M = parseIR(Context, R"(
110 target datalayout = "e-m:e-p:32:32-Fi8-i64:64-v128:64:128-a:0:32-n32-S64"
111 target triple = "thumbv6m-arm-none-eabi"
112
113 declare void @widget()
114 declare void @wobble(i32)
115
116 define void @barney(i8* %arg, i8* %arg18, i32 %arg19) {
117 bb:
118 %tmp = ptrtoint i8* %arg to i32
119 %tmp20 = ptrtoint i8* %arg18 to i32
120 %tmp21 = or i32 %tmp20, %tmp
121 %tmp22 = and i32 %tmp21, 3
122 %tmp23 = icmp eq i32 %tmp22, 0
123 br i1 %tmp23, label %bb24, label %bb25
124
125 bb24:
126 tail call void @widget()
127 br label %bb34
128
129 bb25:
130 %tmp26 = sub i32 %tmp, %tmp20
131 %tmp27 = icmp ult i32 %tmp26, %arg19
132 br i1 %tmp27, label %bb28, label %bb34
133
134 bb28:
135 br label %bb29
136
137 bb29:
138 %tmp30 = phi i32 [ %tmp31, %bb29 ], [ %arg19, %bb28 ]
139 tail call void @wobble(i32 %tmp26)
140 %tmp31 = sub i32 %tmp30, %tmp26
141 %tmp32 = icmp ugt i32 %tmp31, %tmp26
142 br i1 %tmp32, label %bb29, label %bb33
143
144 bb33:
145 br label %bb34
146
147 bb34:
148 ret void
149 })");
150
151 runWithLoopInfoAndSE(
152 *M, "barney", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
153 Function::iterator FI = F.begin();
154 // First basic block is entry - skip it.
155 BasicBlock *Header = &*(++(++(++(++FI))));
156 assert(Header->getName() == "bb29");
157 Loop *L = LI.getLoopFor(Header);
158 EXPECT_NE(L, nullptr);
159 PHINode *Inst_i = dyn_cast<PHINode>(&Header->front());
160 assert(Inst_i->getName() == "tmp30");
161 InductionDescriptor IndDesc;
162 bool IsInductionPHI =
163 InductionDescriptor::isInductionPHI(Inst_i, L, &SE, IndDesc);
164 EXPECT_TRUE(IsInductionPHI);
165 });
166 }
167