xref: /llvm-project/llvm/unittests/Transforms/Vectorize/SandboxVectorizer/IntervalTest.cpp (revision 3769fcb3e78eba5f3e34d1c2dfa994625edb005a) 
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     // Check comesBefore().
128     sandboxir::Interval<sandboxir::Instruction> Intvl1(I0, I0);
129     sandboxir::Interval<sandboxir::Instruction> Intvl2(I2, I2);
130     EXPECT_TRUE(Intvl1.comesBefore(Intvl2));
131     EXPECT_FALSE(Intvl2.comesBefore(Intvl1));
132 
133     sandboxir::Interval<sandboxir::Instruction> Intvl12(I1, I2);
134     EXPECT_TRUE(Intvl1.comesBefore(Intvl12));
135     EXPECT_FALSE(Intvl12.comesBefore(Intvl1));
136     {
137 #ifndef NDEBUG
138       // Check comesBefore() with non-disjoint intervals.
139       sandboxir::Interval<sandboxir::Instruction> Intvl1(I0, I2);
140       sandboxir::Interval<sandboxir::Instruction> Intvl2(I2, I2);
141       EXPECT_DEATH(Intvl1.comesBefore(Intvl2), ".*disjoint.*");
142 #endif // NDEBUG
143     }
144   }
145 }
146 
147 // Helper function for returning a vector of instruction pointers from a range
148 // of references.
149 template <typename RangeT>
150 static SmallVector<sandboxir::Instruction *> getPtrVec(RangeT Range) {
151   SmallVector<sandboxir::Instruction *> PtrVec;
152   for (sandboxir::Instruction &I : Range)
153     PtrVec.push_back(&I);
154   return PtrVec;
155 }
156 
157 TEST_F(IntervalTest, Difference) {
158   parseIR(C, R"IR(
159 define void @foo(i8 %v0) {
160   %I0 = add i8 %v0, %v0
161   %I1 = add i8 %v0, %v0
162   %I2 = add i8 %v0, %v0
163   ret void
164 }
165 )IR");
166   Function &LLVMF = *M->getFunction("foo");
167   sandboxir::Context Ctx(C);
168   auto &F = *Ctx.createFunction(&LLVMF);
169   auto *BB = &*F.begin();
170   auto It = BB->begin();
171   auto *I0 = &*It++;
172   auto *I1 = &*It++;
173   auto *I2 = &*It++;
174   auto *Ret = &*It++;
175 
176   {
177     // Check [I0,Ret] - []
178     sandboxir::Interval<sandboxir::Instruction> I0Ret(I0, Ret);
179     sandboxir::Interval<sandboxir::Instruction> Empty;
180     auto Diffs = I0Ret - Empty;
181     EXPECT_EQ(Diffs.size(), 1u);
182     const sandboxir::Interval<sandboxir::Instruction> &Diff = Diffs[0];
183     EXPECT_THAT(getPtrVec(Diff), testing::ElementsAre(I0, I1, I2, Ret));
184 
185     // Check getSingleDiff().
186     EXPECT_EQ(I0Ret.getSingleDiff(Empty), Diff);
187   }
188   {
189     // Check [] - [I0,Ret]
190     sandboxir::Interval<sandboxir::Instruction> Empty;
191     sandboxir::Interval<sandboxir::Instruction> I0Ret(I0, Ret);
192     auto Diffs = Empty - I0Ret;
193     EXPECT_EQ(Diffs.size(), 1u);
194     const sandboxir::Interval<sandboxir::Instruction> &Diff = Diffs[0];
195     EXPECT_TRUE(Diff.empty());
196 
197     // Check getSingleDiff().
198     EXPECT_EQ(Empty.getSingleDiff(I0Ret), Diff);
199   }
200   {
201     // Check [I0,Ret] - [I0].
202     sandboxir::Interval<sandboxir::Instruction> I0Ret(I0, Ret);
203     sandboxir::Interval<sandboxir::Instruction> I0I0(I0, I0);
204     auto Diffs = I0Ret - I0I0;
205     EXPECT_EQ(Diffs.size(), 1u);
206     const sandboxir::Interval<sandboxir::Instruction> &Diff = Diffs[0];
207     EXPECT_THAT(getPtrVec(Diff), testing::ElementsAre(I1, I2, Ret));
208 
209     // Check getSingleDiff().
210     EXPECT_EQ(I0Ret.getSingleDiff(I0I0), Diff);
211   }
212   {
213     // Check [I0,Ret] - [I1].
214     sandboxir::Interval<sandboxir::Instruction> I0Ret(I0, Ret);
215     sandboxir::Interval<sandboxir::Instruction> I1I1(I1, I1);
216     auto Diffs = I0Ret - I1I1;
217     EXPECT_EQ(Diffs.size(), 2u);
218     const sandboxir::Interval<sandboxir::Instruction> &Diff0 = Diffs[0];
219     EXPECT_THAT(getPtrVec(Diff0), testing::ElementsAre(I0));
220     const sandboxir::Interval<sandboxir::Instruction> &Diff1 = Diffs[1];
221     EXPECT_THAT(getPtrVec(Diff1), testing::ElementsAre(I2, Ret));
222 
223 #ifndef NDEBUG
224     // Check getSingleDiff().
225     EXPECT_DEATH(I0Ret.getSingleDiff(I1I1), ".*single.*");
226 #endif // NDEBUG
227   }
228 }
229 
230 TEST_F(IntervalTest, Intersection) {
231   parseIR(C, R"IR(
232 define void @foo(i8 %v0) {
233   %I0 = add i8 %v0, %v0
234   %I1 = add i8 %v0, %v0
235   %I2 = add i8 %v0, %v0
236   ret void
237 }
238 )IR");
239   Function &LLVMF = *M->getFunction("foo");
240   sandboxir::Context Ctx(C);
241   auto &F = *Ctx.createFunction(&LLVMF);
242   auto *BB = &*F.begin();
243   auto It = BB->begin();
244   auto *I0 = &*It++;
245   auto *I1 = &*It++;
246   [[maybe_unused]] auto *I2 = &*It++;
247   auto *Ret = &*It++;
248 
249   {
250     // Check [I0,Ret] ^ []
251     sandboxir::Interval<sandboxir::Instruction> I0Ret(I0, Ret);
252     sandboxir::Interval<sandboxir::Instruction> Empty;
253     auto Intersection = I0Ret.intersection(Empty);
254     EXPECT_TRUE(Intersection.empty());
255   }
256   {
257     // Check [] ^ [I0,Ret]
258     sandboxir::Interval<sandboxir::Instruction> Empty;
259     sandboxir::Interval<sandboxir::Instruction> I0Ret(I0, Ret);
260     auto Intersection = Empty.intersection(I0Ret);
261     EXPECT_TRUE(Intersection.empty());
262   }
263   {
264     // Check [I0,Ret] ^ [I0]
265     sandboxir::Interval<sandboxir::Instruction> I0Ret(I0, Ret);
266     sandboxir::Interval<sandboxir::Instruction> I0I0(I0, I0);
267     auto Intersection = I0Ret.intersection(I0I0);
268     EXPECT_THAT(getPtrVec(Intersection), testing::ElementsAre(I0));
269   }
270   {
271     // Check [I0] ^ [I0,Ret]
272     sandboxir::Interval<sandboxir::Instruction> I0I0(I0, I0);
273     sandboxir::Interval<sandboxir::Instruction> I0Ret(I0, Ret);
274     auto Intersection = I0I0.intersection(I0Ret);
275     EXPECT_THAT(getPtrVec(Intersection), testing::ElementsAre(I0));
276   }
277   {
278     // Check [I0,Ret] ^ [I1].
279     sandboxir::Interval<sandboxir::Instruction> I0Ret(I0, Ret);
280     sandboxir::Interval<sandboxir::Instruction> I1I1(I1, I1);
281     auto Intersection = I0Ret.intersection(I1I1);
282     EXPECT_THAT(getPtrVec(Intersection), testing::ElementsAre(I1));
283   }
284 }
285 
286 TEST_F(IntervalTest, UnionInterval) {
287   parseIR(C, R"IR(
288 define void @foo(i8 %v0) {
289   %I0 = add i8 %v0, %v0
290   %I1 = add i8 %v0, %v0
291   %I2 = add i8 %v0, %v0
292   ret void
293 }
294 )IR");
295   Function &LLVMF = *M->getFunction("foo");
296   sandboxir::Context Ctx(C);
297   auto &F = *Ctx.createFunction(&LLVMF);
298   auto *BB = &*F.begin();
299   auto It = BB->begin();
300   auto *I0 = &*It++;
301   auto *I1 = &*It++;
302   [[maybe_unused]] auto *I2 = &*It++;
303   auto *Ret = &*It++;
304 
305   {
306     // Check [I0] unionInterval [I2].
307     sandboxir::Interval<sandboxir::Instruction> I0I0(I0, I0);
308     sandboxir::Interval<sandboxir::Instruction> I2I2(I2, I2);
309     auto SingleUnion = I0I0.getUnionInterval(I2I2);
310     EXPECT_THAT(getPtrVec(SingleUnion), testing::ElementsAre(I0, I1, I2));
311   }
312   {
313     // Check [I0] unionInterval Empty.
314     sandboxir::Interval<sandboxir::Instruction> I0I0(I0, I0);
315     sandboxir::Interval<sandboxir::Instruction> Empty;
316     auto SingleUnion = I0I0.getUnionInterval(Empty);
317     EXPECT_THAT(getPtrVec(SingleUnion), testing::ElementsAre(I0));
318   }
319   {
320     // Check [I0,I1] unionInterval [I1].
321     sandboxir::Interval<sandboxir::Instruction> I0I1(I0, I1);
322     sandboxir::Interval<sandboxir::Instruction> I1I1(I1, I1);
323     auto SingleUnion = I0I1.getUnionInterval(I1I1);
324     EXPECT_THAT(getPtrVec(SingleUnion), testing::ElementsAre(I0, I1));
325   }
326   {
327     // Check [I2,Ret] unionInterval [I0].
328     sandboxir::Interval<sandboxir::Instruction> I2Ret(I2, Ret);
329     sandboxir::Interval<sandboxir::Instruction> I0I0(I0, I0);
330     auto SingleUnion = I2Ret.getUnionInterval(I0I0);
331     EXPECT_THAT(getPtrVec(SingleUnion), testing::ElementsAre(I0, I1, I2, Ret));
332   }
333 }
334 
335 TEST_F(IntervalTest, NotifyMoveInstr) {
336   parseIR(C, R"IR(
337 define void @foo(i8 %v0) {
338   %I0 = add i8 %v0, %v0
339   %I1 = add i8 %v0, %v0
340   %I2 = add i8 %v0, %v0
341   ret void
342 }
343 )IR");
344   Function &LLVMF = *M->getFunction("foo");
345   sandboxir::Context Ctx(C);
346   auto &F = *Ctx.createFunction(&LLVMF);
347   auto *BB = &*F.begin();
348   auto It = BB->begin();
349   auto *I0 = &*It++;
350   auto *I1 = &*It++;
351   auto *I2 = &*It++;
352   auto *Ret = &*It++;
353   {
354     // Assert that we don't try to move external instr to the interval.
355     sandboxir::Interval<sandboxir::Instruction> I2Ret(I2, Ret);
356 #ifndef NDEBUG
357     EXPECT_DEATH(I2Ret.notifyMoveInstr(I0, Ret->getIterator()), ".*interval.*");
358 #endif // NDEBUG
359   }
360   {
361     // Assert that we don't move before self.
362     sandboxir::Interval<sandboxir::Instruction> I2Ret(I2, Ret);
363 #ifndef NDEBUG
364     EXPECT_DEATH(I2Ret.notifyMoveInstr(Ret, Ret->getIterator()), ".*self.*");
365 #endif // NDEBUG
366   }
367   {
368     // Single-element interval.
369     sandboxir::Interval<sandboxir::Instruction> I2I2(I2, I2);
370     I2I2.notifyMoveInstr(I2, Ret->getIterator());
371     EXPECT_EQ(I2I2.top(), I2);
372     EXPECT_EQ(I2I2.bottom(), I2);
373   }
374   {
375     // Two-element interval swap.
376     sandboxir::Interval<sandboxir::Instruction> I1I2(I1, I2);
377     I1I2.notifyMoveInstr(I2, I1->getIterator());
378     I2->moveBefore(I1);
379     EXPECT_EQ(I1I2.top(), I2);
380     EXPECT_EQ(I1I2.bottom(), I1);
381 
382     I2->moveAfter(I1);
383   }
384   {
385     // Move to same position.
386     sandboxir::Interval<sandboxir::Instruction> I0Ret(I0, Ret);
387     I0Ret.notifyMoveInstr(I0, I1->getIterator());
388     I0->moveBefore(I1);
389     EXPECT_EQ(I0Ret.top(), I0);
390     EXPECT_EQ(I0Ret.bottom(), Ret);
391   }
392   {
393     // Move internal to internal.
394     sandboxir::Interval<sandboxir::Instruction> I0Ret(I0, Ret);
395     I0Ret.notifyMoveInstr(I2, I1->getIterator());
396     I2->moveBefore(I1);
397     EXPECT_EQ(I0Ret.top(), I0);
398     EXPECT_EQ(I0Ret.bottom(), Ret);
399 
400     I2->moveAfter(I1);
401   }
402   {
403     // Move internal before top.
404     sandboxir::Interval<sandboxir::Instruction> I0Ret(I0, Ret);
405     I0Ret.notifyMoveInstr(I2, I0->getIterator());
406     I2->moveBefore(I0);
407     EXPECT_EQ(I0Ret.top(), I2);
408     EXPECT_EQ(I0Ret.bottom(), Ret);
409 
410     I2->moveAfter(I1);
411   }
412   {
413     // Move internal to bottom.
414     sandboxir::Interval<sandboxir::Instruction> I0Ret(I0, Ret);
415     I0Ret.notifyMoveInstr(I2, BB->end());
416     I2->moveAfter(Ret);
417     EXPECT_EQ(I0Ret.top(), I0);
418     EXPECT_EQ(I0Ret.bottom(), I2);
419 
420     I2->moveAfter(I1);
421   }
422   {
423     // Move bottom before internal.
424     sandboxir::Interval<sandboxir::Instruction> I0Ret(I0, Ret);
425     I0Ret.notifyMoveInstr(Ret, I2->getIterator());
426     Ret->moveBefore(I2);
427     EXPECT_EQ(I0Ret.top(), I0);
428     EXPECT_EQ(I0Ret.bottom(), I2);
429 
430     Ret->moveAfter(I2);
431   }
432   {
433     // Move bottom before top.
434     sandboxir::Interval<sandboxir::Instruction> I0Ret(I0, Ret);
435     I0Ret.notifyMoveInstr(Ret, I0->getIterator());
436     Ret->moveBefore(I0);
437     EXPECT_EQ(I0Ret.top(), Ret);
438     EXPECT_EQ(I0Ret.bottom(), I2);
439 
440     Ret->moveAfter(I2);
441   }
442 }
443