xref: /llvm-project/llvm/unittests/Transforms/Vectorize/SandboxVectorizer/IntervalTest.cpp (revision c214af8454345a7986bce1395aad7f06b186352e) 
1 //===- IntervalTest.cpp ---------------------------------------------------===//
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/Transforms/Vectorize/SandboxVectorizer/Interval.h"
10 #include "llvm/AsmParser/Parser.h"
11 #include "llvm/SandboxIR/Context.h"
12 #include "llvm/SandboxIR/Function.h"
13 #include "llvm/SandboxIR/Instruction.h"
14 #include "llvm/Support/SourceMgr.h"
15 #include "gmock/gmock-matchers.h"
16 #include "gtest/gtest.h"
17 
18 using namespace llvm;
19 
20 struct IntervalTest : public testing::Test {
21   LLVMContext C;
22   std::unique_ptr<Module> M;
23 
24   void parseIR(LLVMContext &C, const char *IR) {
25     SMDiagnostic Err;
26     M = parseAssemblyString(IR, Err, C);
27     if (!M)
28       Err.print("InstrIntervalTest", errs());
29   }
30 };
31 
32 TEST_F(IntervalTest, Basic) {
33   parseIR(C, R"IR(
34 define void @foo(i8 %v0) {
35   %add0 = add i8 %v0, %v0
36   %add1 = add i8 %v0, %v0
37   %add2 = add i8 %v0, %v0
38   ret void
39 }
40 )IR");
41   Function &LLVMF = *M->getFunction("foo");
42   sandboxir::Context Ctx(C);
43   auto &F = *Ctx.createFunction(&LLVMF);
44   auto *BB = &*F.begin();
45   auto It = BB->begin();
46   auto *I0 = &*It++;
47   auto *I1 = &*It++;
48   auto *I2 = &*It++;
49   auto *Ret = &*It++;
50 
51   sandboxir::Interval<sandboxir::Instruction> Intvl(I0, Ret);
52 #ifndef NDEBUG
53   EXPECT_DEATH(sandboxir::Interval<sandboxir::Instruction>(I1, I0),
54                ".*before.*");
55 #endif // NDEBUG
56   // Check Interval<sandboxir::Instruction>(ArrayRef), from(), to().
57   {
58     sandboxir::Interval<sandboxir::Instruction> Intvl(
59         SmallVector<sandboxir::Instruction *>({I0, Ret}));
60     EXPECT_EQ(Intvl.top(), I0);
61     EXPECT_EQ(Intvl.bottom(), Ret);
62   }
63   {
64     sandboxir::Interval<sandboxir::Instruction> Intvl(
65         SmallVector<sandboxir::Instruction *>({Ret, I0}));
66     EXPECT_EQ(Intvl.top(), I0);
67     EXPECT_EQ(Intvl.bottom(), Ret);
68   }
69   {
70     sandboxir::Interval<sandboxir::Instruction> Intvl(
71         SmallVector<sandboxir::Instruction *>({I0, I0}));
72     EXPECT_EQ(Intvl.top(), I0);
73     EXPECT_EQ(Intvl.bottom(), I0);
74   }
75 
76   // Check empty().
77   EXPECT_FALSE(Intvl.empty());
78   sandboxir::Interval<sandboxir::Instruction> Empty;
79   EXPECT_TRUE(Empty.empty());
80   sandboxir::Interval<sandboxir::Instruction> One(I0, I0);
81   EXPECT_FALSE(One.empty());
82   // Check contains().
83   for (auto &I : *BB) {
84     EXPECT_TRUE(Intvl.contains(&I));
85     EXPECT_FALSE(Empty.contains(&I));
86   }
87   EXPECT_FALSE(One.contains(I1));
88   EXPECT_FALSE(One.contains(I2));
89   EXPECT_FALSE(One.contains(Ret));
90   // Check iterator.
91   auto BBIt = BB->begin();
92   for (auto &I : Intvl)
93     EXPECT_EQ(&I, &*BBIt++);
94   {
95     // Check equality.
96     EXPECT_TRUE(Empty == Empty);
97     EXPECT_FALSE(Empty == One);
98     EXPECT_TRUE(One == One);
99     sandboxir::Interval<sandboxir::Instruction> Intvl1(I0, I2);
100     sandboxir::Interval<sandboxir::Instruction> Intvl2(I0, I2);
101     EXPECT_TRUE(Intvl1 == Intvl1);
102     EXPECT_TRUE(Intvl1 == Intvl2);
103   }
104   {
105     // Check inequality.
106     EXPECT_FALSE(Empty != Empty);
107     EXPECT_TRUE(Empty != One);
108     EXPECT_FALSE(One != One);
109     sandboxir::Interval<sandboxir::Instruction> Intvl1(I0, I2);
110     sandboxir::Interval<sandboxir::Instruction> Intvl2(I0, I2);
111     EXPECT_FALSE(Intvl1 != Intvl1);
112     EXPECT_FALSE(Intvl1 != Intvl2);
113   }
114   {
115     // Check disjoint().
116     EXPECT_TRUE(Empty.disjoint(Empty));
117     EXPECT_TRUE(One.disjoint(Empty));
118     EXPECT_TRUE(Empty.disjoint(One));
119     sandboxir::Interval<sandboxir::Instruction> Intvl1(I0, I2);
120     sandboxir::Interval<sandboxir::Instruction> Intvl2(I1, Ret);
121     EXPECT_FALSE(Intvl1.disjoint(Intvl2));
122     sandboxir::Interval<sandboxir::Instruction> Intvl3(I2, I2);
123     EXPECT_FALSE(Intvl1.disjoint(Intvl3));
124     EXPECT_TRUE(Intvl1.disjoint(Empty));
125   }
126 }
127 
128 // Helper function for returning a vector of instruction pointers from a range
129 // of references.
130 template <typename RangeT>
131 static SmallVector<sandboxir::Instruction *> getPtrVec(RangeT Range) {
132   SmallVector<sandboxir::Instruction *> PtrVec;
133   for (sandboxir::Instruction &I : Range)
134     PtrVec.push_back(&I);
135   return PtrVec;
136 }
137 
138 TEST_F(IntervalTest, Difference) {
139   parseIR(C, R"IR(
140 define void @foo(i8 %v0) {
141   %I0 = add i8 %v0, %v0
142   %I1 = add i8 %v0, %v0
143   %I2 = add i8 %v0, %v0
144   ret void
145 }
146 )IR");
147   Function &LLVMF = *M->getFunction("foo");
148   sandboxir::Context Ctx(C);
149   auto &F = *Ctx.createFunction(&LLVMF);
150   auto *BB = &*F.begin();
151   auto It = BB->begin();
152   auto *I0 = &*It++;
153   auto *I1 = &*It++;
154   auto *I2 = &*It++;
155   auto *Ret = &*It++;
156 
157   {
158     // Check [I0,Ret] - []
159     sandboxir::Interval<sandboxir::Instruction> I0Ret(I0, Ret);
160     sandboxir::Interval<sandboxir::Instruction> Empty;
161     auto Diffs = I0Ret - Empty;
162     EXPECT_EQ(Diffs.size(), 1u);
163     const sandboxir::Interval<sandboxir::Instruction> &Diff = Diffs[0];
164     EXPECT_THAT(getPtrVec(Diff), testing::ElementsAre(I0, I1, I2, Ret));
165   }
166   {
167     // Check [] - [I0,Ret]
168     sandboxir::Interval<sandboxir::Instruction> Empty;
169     sandboxir::Interval<sandboxir::Instruction> I0Ret(I0, Ret);
170     auto Diffs = Empty - I0Ret;
171     EXPECT_EQ(Diffs.size(), 1u);
172     const sandboxir::Interval<sandboxir::Instruction> &Diff = Diffs[0];
173     EXPECT_TRUE(Diff.empty());
174   }
175   {
176     // Check [I0,Ret] - [I0].
177     sandboxir::Interval<sandboxir::Instruction> I0Ret(I0, Ret);
178     sandboxir::Interval<sandboxir::Instruction> I0I0(I0, I0);
179     auto Diffs = I0Ret - I0I0;
180     EXPECT_EQ(Diffs.size(), 1u);
181     const sandboxir::Interval<sandboxir::Instruction> &Diff = Diffs[0];
182     EXPECT_THAT(getPtrVec(Diff), testing::ElementsAre(I1, I2, Ret));
183   }
184   {
185     // Check [I0,Ret] - [I1].
186     sandboxir::Interval<sandboxir::Instruction> I0Ret(I0, Ret);
187     sandboxir::Interval<sandboxir::Instruction> I1I1(I1, I1);
188     auto Diffs = I0Ret - I1I1;
189     EXPECT_EQ(Diffs.size(), 2u);
190     const sandboxir::Interval<sandboxir::Instruction> &Diff0 = Diffs[0];
191     EXPECT_THAT(getPtrVec(Diff0), testing::ElementsAre(I0));
192     const sandboxir::Interval<sandboxir::Instruction> &Diff1 = Diffs[1];
193     EXPECT_THAT(getPtrVec(Diff1), testing::ElementsAre(I2, Ret));
194   }
195 }
196 
197 TEST_F(IntervalTest, Intersection) {
198   parseIR(C, R"IR(
199 define void @foo(i8 %v0) {
200   %I0 = add i8 %v0, %v0
201   %I1 = add i8 %v0, %v0
202   %I2 = add i8 %v0, %v0
203   ret void
204 }
205 )IR");
206   Function &LLVMF = *M->getFunction("foo");
207   sandboxir::Context Ctx(C);
208   auto &F = *Ctx.createFunction(&LLVMF);
209   auto *BB = &*F.begin();
210   auto It = BB->begin();
211   auto *I0 = &*It++;
212   auto *I1 = &*It++;
213   [[maybe_unused]] auto *I2 = &*It++;
214   auto *Ret = &*It++;
215 
216   {
217     // Check [I0,Ret] ^ []
218     sandboxir::Interval<sandboxir::Instruction> I0Ret(I0, Ret);
219     sandboxir::Interval<sandboxir::Instruction> Empty;
220     auto Intersection = I0Ret.intersection(Empty);
221     EXPECT_TRUE(Intersection.empty());
222   }
223   {
224     // Check [] ^ [I0,Ret]
225     sandboxir::Interval<sandboxir::Instruction> Empty;
226     sandboxir::Interval<sandboxir::Instruction> I0Ret(I0, Ret);
227     auto Intersection = Empty.intersection(I0Ret);
228     EXPECT_TRUE(Intersection.empty());
229   }
230   {
231     // Check [I0,Ret] ^ [I0]
232     sandboxir::Interval<sandboxir::Instruction> I0Ret(I0, Ret);
233     sandboxir::Interval<sandboxir::Instruction> I0I0(I0, I0);
234     auto Intersection = I0Ret.intersection(I0I0);
235     EXPECT_THAT(getPtrVec(Intersection), testing::ElementsAre(I0));
236   }
237   {
238     // Check [I0] ^ [I0,Ret]
239     sandboxir::Interval<sandboxir::Instruction> I0I0(I0, I0);
240     sandboxir::Interval<sandboxir::Instruction> I0Ret(I0, Ret);
241     auto Intersection = I0I0.intersection(I0Ret);
242     EXPECT_THAT(getPtrVec(Intersection), testing::ElementsAre(I0));
243   }
244   {
245     // Check [I0,Ret] ^ [I1].
246     sandboxir::Interval<sandboxir::Instruction> I0Ret(I0, Ret);
247     sandboxir::Interval<sandboxir::Instruction> I1I1(I1, I1);
248     auto Intersection = I0Ret.intersection(I1I1);
249     EXPECT_THAT(getPtrVec(Intersection), testing::ElementsAre(I1));
250   }
251 }
252