450 lines · cpp
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-exception6//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 18using namespace llvm;19 20struct 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 32TEST_F(IntervalTest, Basic) {33 parseIR(C, R"IR(34define void @foo(i8 %v0) {35 %add0 = add i8 %v0, %v036 %add1 = add i8 %v0, %v037 %add2 = add i8 %v0, %v038 ret void39}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 NDEBUG53 EXPECT_DEATH(sandboxir::Interval<sandboxir::Instruction>(I1, I0),54 ".*before.*");55#endif // NDEBUG56 // 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 touches().91 {92 sandboxir::Interval<sandboxir::Instruction> Intvl(I2, I2);93 EXPECT_TRUE(Intvl.touches(I1));94 EXPECT_TRUE(Intvl.contains(I2));95 EXPECT_FALSE(Intvl.touches(I2));96 EXPECT_TRUE(Intvl.touches(Ret));97 EXPECT_FALSE(Intvl.touches(I0));98 }99 // Check iterator.100 auto BBIt = BB->begin();101 for (auto &I : Intvl)102 EXPECT_EQ(&I, &*BBIt++);103 {104 // Check equality.105 EXPECT_TRUE(Empty == Empty);106 EXPECT_FALSE(Empty == One);107 EXPECT_TRUE(One == One);108 sandboxir::Interval<sandboxir::Instruction> Intvl1(I0, I2);109 sandboxir::Interval<sandboxir::Instruction> Intvl2(I0, I2);110 EXPECT_TRUE(Intvl1 == Intvl1);111 EXPECT_TRUE(Intvl1 == Intvl2);112 }113 {114 // Check inequality.115 EXPECT_FALSE(Empty != Empty);116 EXPECT_TRUE(Empty != One);117 EXPECT_FALSE(One != One);118 sandboxir::Interval<sandboxir::Instruction> Intvl1(I0, I2);119 sandboxir::Interval<sandboxir::Instruction> Intvl2(I0, I2);120 EXPECT_FALSE(Intvl1 != Intvl1);121 EXPECT_FALSE(Intvl1 != Intvl2);122 }123 {124 // Check disjoint().125 EXPECT_TRUE(Empty.disjoint(Empty));126 EXPECT_TRUE(One.disjoint(Empty));127 EXPECT_TRUE(Empty.disjoint(One));128 sandboxir::Interval<sandboxir::Instruction> Intvl1(I0, I2);129 sandboxir::Interval<sandboxir::Instruction> Intvl2(I1, Ret);130 EXPECT_FALSE(Intvl1.disjoint(Intvl2));131 sandboxir::Interval<sandboxir::Instruction> Intvl3(I2, I2);132 EXPECT_FALSE(Intvl1.disjoint(Intvl3));133 EXPECT_TRUE(Intvl1.disjoint(Empty));134 }135 {136 // Check comesBefore().137 sandboxir::Interval<sandboxir::Instruction> Intvl1(I0, I0);138 sandboxir::Interval<sandboxir::Instruction> Intvl2(I2, I2);139 EXPECT_TRUE(Intvl1.comesBefore(Intvl2));140 EXPECT_FALSE(Intvl2.comesBefore(Intvl1));141 142 sandboxir::Interval<sandboxir::Instruction> Intvl12(I1, I2);143 EXPECT_TRUE(Intvl1.comesBefore(Intvl12));144 EXPECT_FALSE(Intvl12.comesBefore(Intvl1));145 {146#ifndef NDEBUG147 // Check comesBefore() with non-disjoint intervals.148 sandboxir::Interval<sandboxir::Instruction> Intvl1(I0, I2);149 sandboxir::Interval<sandboxir::Instruction> Intvl2(I2, I2);150 EXPECT_DEATH(Intvl1.comesBefore(Intvl2), ".*disjoint.*");151#endif // NDEBUG152 }153 }154}155 156// Helper function for returning a vector of instruction pointers from a range157// of references.158template <typename RangeT>159static SmallVector<sandboxir::Instruction *> getPtrVec(RangeT Range) {160 SmallVector<sandboxir::Instruction *> PtrVec(llvm::make_pointer_range(Range));161 return PtrVec;162}163 164TEST_F(IntervalTest, Difference) {165 parseIR(C, R"IR(166define void @foo(i8 %v0) {167 %I0 = add i8 %v0, %v0168 %I1 = add i8 %v0, %v0169 %I2 = add i8 %v0, %v0170 ret void171}172)IR");173 Function &LLVMF = *M->getFunction("foo");174 sandboxir::Context Ctx(C);175 auto &F = *Ctx.createFunction(&LLVMF);176 auto *BB = &*F.begin();177 auto It = BB->begin();178 auto *I0 = &*It++;179 auto *I1 = &*It++;180 auto *I2 = &*It++;181 auto *Ret = &*It++;182 183 {184 // Check [I0,Ret] - []185 sandboxir::Interval<sandboxir::Instruction> I0Ret(I0, Ret);186 sandboxir::Interval<sandboxir::Instruction> Empty;187 auto Diffs = I0Ret - Empty;188 EXPECT_EQ(Diffs.size(), 1u);189 const sandboxir::Interval<sandboxir::Instruction> &Diff = Diffs[0];190 EXPECT_THAT(getPtrVec(Diff), testing::ElementsAre(I0, I1, I2, Ret));191 192 // Check getSingleDiff().193 EXPECT_EQ(I0Ret.getSingleDiff(Empty), Diff);194 }195 {196 // Check [] - [I0,Ret]197 sandboxir::Interval<sandboxir::Instruction> Empty;198 sandboxir::Interval<sandboxir::Instruction> I0Ret(I0, Ret);199 auto Diffs = Empty - I0Ret;200 EXPECT_EQ(Diffs.size(), 1u);201 const sandboxir::Interval<sandboxir::Instruction> &Diff = Diffs[0];202 EXPECT_TRUE(Diff.empty());203 204 // Check getSingleDiff().205 EXPECT_EQ(Empty.getSingleDiff(I0Ret), Diff);206 }207 {208 // Check [I0,Ret] - [I0].209 sandboxir::Interval<sandboxir::Instruction> I0Ret(I0, Ret);210 sandboxir::Interval<sandboxir::Instruction> I0I0(I0, I0);211 auto Diffs = I0Ret - I0I0;212 EXPECT_EQ(Diffs.size(), 1u);213 const sandboxir::Interval<sandboxir::Instruction> &Diff = Diffs[0];214 EXPECT_THAT(getPtrVec(Diff), testing::ElementsAre(I1, I2, Ret));215 216 // Check getSingleDiff().217 EXPECT_EQ(I0Ret.getSingleDiff(I0I0), Diff);218 }219 {220 // Check [I0,Ret] - [I1].221 sandboxir::Interval<sandboxir::Instruction> I0Ret(I0, Ret);222 sandboxir::Interval<sandboxir::Instruction> I1I1(I1, I1);223 auto Diffs = I0Ret - I1I1;224 EXPECT_EQ(Diffs.size(), 2u);225 const sandboxir::Interval<sandboxir::Instruction> &Diff0 = Diffs[0];226 EXPECT_THAT(getPtrVec(Diff0), testing::ElementsAre(I0));227 const sandboxir::Interval<sandboxir::Instruction> &Diff1 = Diffs[1];228 EXPECT_THAT(getPtrVec(Diff1), testing::ElementsAre(I2, Ret));229 230#ifndef NDEBUG231 // Check getSingleDiff().232 EXPECT_DEATH(I0Ret.getSingleDiff(I1I1), ".*single.*");233#endif // NDEBUG234 }235}236 237TEST_F(IntervalTest, Intersection) {238 parseIR(C, R"IR(239define void @foo(i8 %v0) {240 %I0 = add i8 %v0, %v0241 %I1 = add i8 %v0, %v0242 %I2 = add i8 %v0, %v0243 ret void244}245)IR");246 Function &LLVMF = *M->getFunction("foo");247 sandboxir::Context Ctx(C);248 auto &F = *Ctx.createFunction(&LLVMF);249 auto *BB = &*F.begin();250 auto It = BB->begin();251 auto *I0 = &*It++;252 auto *I1 = &*It++;253 [[maybe_unused]] auto *I2 = &*It++;254 auto *Ret = &*It++;255 256 {257 // Check [I0,Ret] ^ []258 sandboxir::Interval<sandboxir::Instruction> I0Ret(I0, Ret);259 sandboxir::Interval<sandboxir::Instruction> Empty;260 auto Intersection = I0Ret.intersection(Empty);261 EXPECT_TRUE(Intersection.empty());262 }263 {264 // Check [] ^ [I0,Ret]265 sandboxir::Interval<sandboxir::Instruction> Empty;266 sandboxir::Interval<sandboxir::Instruction> I0Ret(I0, Ret);267 auto Intersection = Empty.intersection(I0Ret);268 EXPECT_TRUE(Intersection.empty());269 }270 {271 // Check [I0,Ret] ^ [I0]272 sandboxir::Interval<sandboxir::Instruction> I0Ret(I0, Ret);273 sandboxir::Interval<sandboxir::Instruction> I0I0(I0, I0);274 auto Intersection = I0Ret.intersection(I0I0);275 EXPECT_THAT(getPtrVec(Intersection), testing::ElementsAre(I0));276 }277 {278 // Check [I0] ^ [I0,Ret]279 sandboxir::Interval<sandboxir::Instruction> I0I0(I0, I0);280 sandboxir::Interval<sandboxir::Instruction> I0Ret(I0, Ret);281 auto Intersection = I0I0.intersection(I0Ret);282 EXPECT_THAT(getPtrVec(Intersection), testing::ElementsAre(I0));283 }284 {285 // Check [I0,Ret] ^ [I1].286 sandboxir::Interval<sandboxir::Instruction> I0Ret(I0, Ret);287 sandboxir::Interval<sandboxir::Instruction> I1I1(I1, I1);288 auto Intersection = I0Ret.intersection(I1I1);289 EXPECT_THAT(getPtrVec(Intersection), testing::ElementsAre(I1));290 }291}292 293TEST_F(IntervalTest, UnionInterval) {294 parseIR(C, R"IR(295define void @foo(i8 %v0) {296 %I0 = add i8 %v0, %v0297 %I1 = add i8 %v0, %v0298 %I2 = add i8 %v0, %v0299 ret void300}301)IR");302 Function &LLVMF = *M->getFunction("foo");303 sandboxir::Context Ctx(C);304 auto &F = *Ctx.createFunction(&LLVMF);305 auto *BB = &*F.begin();306 auto It = BB->begin();307 auto *I0 = &*It++;308 auto *I1 = &*It++;309 [[maybe_unused]] auto *I2 = &*It++;310 auto *Ret = &*It++;311 312 {313 // Check [I0] unionInterval [I2].314 sandboxir::Interval<sandboxir::Instruction> I0I0(I0, I0);315 sandboxir::Interval<sandboxir::Instruction> I2I2(I2, I2);316 auto SingleUnion = I0I0.getUnionInterval(I2I2);317 EXPECT_THAT(getPtrVec(SingleUnion), testing::ElementsAre(I0, I1, I2));318 }319 {320 // Check [I0] unionInterval Empty.321 sandboxir::Interval<sandboxir::Instruction> I0I0(I0, I0);322 sandboxir::Interval<sandboxir::Instruction> Empty;323 auto SingleUnion = I0I0.getUnionInterval(Empty);324 EXPECT_THAT(getPtrVec(SingleUnion), testing::ElementsAre(I0));325 }326 {327 // Check [I0,I1] unionInterval [I1].328 sandboxir::Interval<sandboxir::Instruction> I0I1(I0, I1);329 sandboxir::Interval<sandboxir::Instruction> I1I1(I1, I1);330 auto SingleUnion = I0I1.getUnionInterval(I1I1);331 EXPECT_THAT(getPtrVec(SingleUnion), testing::ElementsAre(I0, I1));332 }333 {334 // Check [I2,Ret] unionInterval [I0].335 sandboxir::Interval<sandboxir::Instruction> I2Ret(I2, Ret);336 sandboxir::Interval<sandboxir::Instruction> I0I0(I0, I0);337 auto SingleUnion = I2Ret.getUnionInterval(I0I0);338 EXPECT_THAT(getPtrVec(SingleUnion), testing::ElementsAre(I0, I1, I2, Ret));339 }340}341 342TEST_F(IntervalTest, NotifyMoveInstr) {343 parseIR(C, R"IR(344define void @foo(i8 %v0) {345 %I0 = add i8 %v0, %v0346 %I1 = add i8 %v0, %v0347 %I2 = add i8 %v0, %v0348 ret void349}350)IR");351 Function &LLVMF = *M->getFunction("foo");352 sandboxir::Context Ctx(C);353 auto &F = *Ctx.createFunction(&LLVMF);354 auto *BB = &*F.begin();355 auto It = BB->begin();356 auto *I0 = &*It++;357 auto *I1 = &*It++;358 auto *I2 = &*It++;359 auto *Ret = &*It++;360 {361 // Assert that we don't try to move external instr to the interval.362 sandboxir::Interval<sandboxir::Instruction> I2Ret(I2, Ret);363#ifndef NDEBUG364 EXPECT_DEATH(I2Ret.notifyMoveInstr(I0, Ret->getIterator()), ".*interval.*");365#endif // NDEBUG366 }367 {368 // Assert that we don't move before self.369 sandboxir::Interval<sandboxir::Instruction> I2Ret(I2, Ret);370#ifndef NDEBUG371 EXPECT_DEATH(I2Ret.notifyMoveInstr(Ret, Ret->getIterator()), ".*self.*");372#endif // NDEBUG373 }374 {375 // Single-element interval.376 sandboxir::Interval<sandboxir::Instruction> I2I2(I2, I2);377 I2I2.notifyMoveInstr(I2, Ret->getIterator());378 EXPECT_EQ(I2I2.top(), I2);379 EXPECT_EQ(I2I2.bottom(), I2);380 }381 {382 // Two-element interval swap.383 sandboxir::Interval<sandboxir::Instruction> I1I2(I1, I2);384 I1I2.notifyMoveInstr(I2, I1->getIterator());385 I2->moveBefore(I1);386 EXPECT_EQ(I1I2.top(), I2);387 EXPECT_EQ(I1I2.bottom(), I1);388 389 I2->moveAfter(I1);390 }391 {392 // Move to same position.393 sandboxir::Interval<sandboxir::Instruction> I0Ret(I0, Ret);394 I0Ret.notifyMoveInstr(I0, I1->getIterator());395 I0->moveBefore(I1);396 EXPECT_EQ(I0Ret.top(), I0);397 EXPECT_EQ(I0Ret.bottom(), Ret);398 }399 {400 // Move internal to internal.401 sandboxir::Interval<sandboxir::Instruction> I0Ret(I0, Ret);402 I0Ret.notifyMoveInstr(I2, I1->getIterator());403 I2->moveBefore(I1);404 EXPECT_EQ(I0Ret.top(), I0);405 EXPECT_EQ(I0Ret.bottom(), Ret);406 407 I2->moveAfter(I1);408 }409 {410 // Move internal before top.411 sandboxir::Interval<sandboxir::Instruction> I0Ret(I0, Ret);412 I0Ret.notifyMoveInstr(I2, I0->getIterator());413 I2->moveBefore(I0);414 EXPECT_EQ(I0Ret.top(), I2);415 EXPECT_EQ(I0Ret.bottom(), Ret);416 417 I2->moveAfter(I1);418 }419 {420 // Move internal to bottom.421 sandboxir::Interval<sandboxir::Instruction> I0Ret(I0, Ret);422 I0Ret.notifyMoveInstr(I2, BB->end());423 I2->moveAfter(Ret);424 EXPECT_EQ(I0Ret.top(), I0);425 EXPECT_EQ(I0Ret.bottom(), I2);426 427 I2->moveAfter(I1);428 }429 {430 // Move bottom before internal.431 sandboxir::Interval<sandboxir::Instruction> I0Ret(I0, Ret);432 I0Ret.notifyMoveInstr(Ret, I2->getIterator());433 Ret->moveBefore(I2);434 EXPECT_EQ(I0Ret.top(), I0);435 EXPECT_EQ(I0Ret.bottom(), I2);436 437 Ret->moveAfter(I2);438 }439 {440 // Move bottom before top.441 sandboxir::Interval<sandboxir::Instruction> I0Ret(I0, Ret);442 I0Ret.notifyMoveInstr(Ret, I0->getIterator());443 Ret->moveBefore(I0);444 EXPECT_EQ(I0Ret.top(), Ret);445 EXPECT_EQ(I0Ret.bottom(), I2);446 447 Ret->moveAfter(I2);448 }449}450