1193 lines · cpp
1//===- DependencyGraphTest.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/DependencyGraph.h"10#include "llvm/Analysis/AliasAnalysis.h"11#include "llvm/Analysis/AssumptionCache.h"12#include "llvm/Analysis/BasicAliasAnalysis.h"13#include "llvm/Analysis/TargetLibraryInfo.h"14#include "llvm/AsmParser/Parser.h"15#include "llvm/IR/DataLayout.h"16#include "llvm/IR/Dominators.h"17#include "llvm/SandboxIR/Context.h"18#include "llvm/SandboxIR/Function.h"19#include "llvm/SandboxIR/Instruction.h"20#include "llvm/Support/SourceMgr.h"21#include "gmock/gmock-matchers.h"22#include "gtest/gtest.h"23 24using namespace llvm;25 26struct DependencyGraphTest : public testing::Test {27 LLVMContext C;28 std::unique_ptr<Module> M;29 std::unique_ptr<AssumptionCache> AC;30 std::unique_ptr<DominatorTree> DT;31 std::unique_ptr<BasicAAResult> BAA;32 std::unique_ptr<AAResults> AA;33 std::unique_ptr<TargetLibraryInfoImpl> TLII;34 std::unique_ptr<TargetLibraryInfo> TLI;35 36 void parseIR(LLVMContext &C, const char *IR) {37 SMDiagnostic Err;38 M = parseAssemblyString(IR, Err, C);39 if (!M) {40 Err.print("DependencyGraphTest", errs());41 return;42 }43 44 TLII = std::make_unique<TargetLibraryInfoImpl>(M->getTargetTriple());45 TLI = std::make_unique<TargetLibraryInfo>(*TLII);46 }47 48 AAResults &getAA(llvm::Function &LLVMF) {49 AA = std::make_unique<AAResults>(*TLI);50 AC = std::make_unique<AssumptionCache>(LLVMF);51 DT = std::make_unique<DominatorTree>(LLVMF);52 BAA = std::make_unique<BasicAAResult>(M->getDataLayout(), LLVMF, *TLI, *AC,53 DT.get());54 AA->addAAResult(*BAA);55 return *AA;56 }57 /// \Returns true if there is a dependency: SrcN->DstN.58 bool memDependency(sandboxir::DGNode *SrcN, sandboxir::DGNode *DstN) {59 if (auto *MemDstN = dyn_cast<sandboxir::MemDGNode>(DstN))60 return MemDstN->hasMemPred(SrcN);61 return false;62 }63};64 65TEST_F(DependencyGraphTest, isStackSaveOrRestoreIntrinsic) {66 parseIR(C, R"IR(67declare void @llvm.sideeffect()68define void @foo(i8 %v1, ptr %ptr) {69 %add = add i8 %v1, %v170 %stacksave = call ptr @llvm.stacksave()71 call void @llvm.stackrestore(ptr %stacksave)72 call void @llvm.sideeffect()73 ret void74}75)IR");76 llvm::Function *LLVMF = &*M->getFunction("foo");77 sandboxir::Context Ctx(C);78 sandboxir::Function *F = Ctx.createFunction(LLVMF);79 auto *BB = &*F->begin();80 auto It = BB->begin();81 auto *Add = cast<sandboxir::BinaryOperator>(&*It++);82 auto *StackSave = cast<sandboxir::CallInst>(&*It++);83 auto *StackRestore = cast<sandboxir::CallInst>(&*It++);84 auto *Other = cast<sandboxir::CallInst>(&*It++);85 auto *Ret = cast<sandboxir::ReturnInst>(&*It++);86 87 using DGNode = sandboxir::DGNode;88 EXPECT_FALSE(DGNode::isStackSaveOrRestoreIntrinsic(Add));89 EXPECT_TRUE(DGNode::isStackSaveOrRestoreIntrinsic(StackSave));90 EXPECT_TRUE(DGNode::isStackSaveOrRestoreIntrinsic(StackRestore));91 EXPECT_FALSE(DGNode::isStackSaveOrRestoreIntrinsic(Other));92 EXPECT_FALSE(DGNode::isStackSaveOrRestoreIntrinsic(Ret));93}94 95TEST_F(DependencyGraphTest, Instruction_isMemDepCandidate) {96 parseIR(C, R"IR(97declare void @llvm.fake.use(...)98declare void @llvm.sideeffect()99declare void @llvm.pseudoprobe(i64, i64, i32, i64)100declare void @bar()101define void @foo(i8 %v1, ptr %ptr) {102 %add0 = add i8 %v1, %v1103 %ld0 = load i8, ptr %ptr104 store i8 %v1, ptr %ptr105 call void @llvm.sideeffect()106 call void @llvm.pseudoprobe(i64 42, i64 1, i32 0, i64 -1)107 call void @llvm.fake.use(ptr %ptr)108 call void @bar()109 ret void110}111)IR");112 llvm::Function *LLVMF = &*M->getFunction("foo");113 sandboxir::Context Ctx(C);114 sandboxir::Function *F = Ctx.createFunction(LLVMF);115 auto *BB = &*F->begin();116 auto It = BB->begin();117 auto *Add0 = cast<sandboxir::BinaryOperator>(&*It++);118 auto *Ld0 = cast<sandboxir::LoadInst>(&*It++);119 auto *St0 = cast<sandboxir::StoreInst>(&*It++);120 auto *SideEffect0 = cast<sandboxir::CallInst>(&*It++);121 auto *PseudoProbe0 = cast<sandboxir::CallInst>(&*It++);122 auto *OtherIntrinsic0 = cast<sandboxir::CallInst>(&*It++);123 auto *CallBar = cast<sandboxir::CallInst>(&*It++);124 auto *Ret = cast<sandboxir::ReturnInst>(&*It++);125 126 using DGNode = sandboxir::DGNode;127 128 EXPECT_FALSE(DGNode::isMemDepCandidate(Add0));129 EXPECT_TRUE(DGNode::isMemDepCandidate(Ld0));130 EXPECT_TRUE(DGNode::isMemDepCandidate(St0));131 EXPECT_FALSE(DGNode::isMemDepCandidate(SideEffect0));132 EXPECT_FALSE(DGNode::isMemDepCandidate(PseudoProbe0));133 EXPECT_TRUE(DGNode::isMemDepCandidate(OtherIntrinsic0));134 EXPECT_TRUE(DGNode::isMemDepCandidate(CallBar));135 EXPECT_FALSE(DGNode::isMemDepCandidate(Ret));136}137 138TEST_F(DependencyGraphTest, Instruction_isMemIntrinsic) {139 parseIR(C, R"IR(140declare void @llvm.sideeffect()141declare void @llvm.pseudoprobe(i64)142declare void @llvm.assume(i1)143 144define void @foo(ptr %ptr, i1 %cond) {145 call void @llvm.sideeffect()146 call void @llvm.pseudoprobe(i64 42)147 call void @llvm.assume(i1 %cond)148 ret void149}150)IR");151 llvm::Function *LLVMF = &*M->getFunction("foo");152 sandboxir::Context Ctx(C);153 sandboxir::Function *F = Ctx.createFunction(LLVMF);154 auto *BB = &*F->begin();155 auto It = BB->begin();156 auto *SideEffect = cast<sandboxir::IntrinsicInst>(&*It++);157 auto *PseudoProbe = cast<sandboxir::IntrinsicInst>(&*It++);158 auto *OtherIntrinsic = cast<sandboxir::IntrinsicInst>(&*It++);159 160 using DGNode = sandboxir::DGNode;161 EXPECT_FALSE(DGNode::isMemIntrinsic(SideEffect));162 EXPECT_FALSE(DGNode::isMemIntrinsic(PseudoProbe));163 EXPECT_TRUE(DGNode::isMemIntrinsic(OtherIntrinsic));164}165 166TEST_F(DependencyGraphTest, MemDGNode) {167 parseIR(C, R"IR(168declare void @llvm.sideeffect()169declare void @llvm.pseudoprobe(i64, i64, i32, i64)170declare void @llvm.fake.use(...)171declare void @bar()172define void @foo(i8 %v1, ptr %ptr) {173 store i8 %v1, ptr %ptr174 %ld0 = load i8, ptr %ptr175 %add = add i8 %v1, %v1176 %stacksave = call ptr @llvm.stacksave()177 call void @llvm.stackrestore(ptr %stacksave)178 call void @llvm.sideeffect()179 call void @llvm.pseudoprobe(i64 42, i64 1, i32 0, i64 -1)180 call void @llvm.fake.use(ptr %ptr)181 call void @bar()182 ret void183}184)IR");185 llvm::Function *LLVMF = &*M->getFunction("foo");186 sandboxir::Context Ctx(C);187 188 auto *F = Ctx.createFunction(LLVMF);189 auto *BB = &*F->begin();190 auto It = BB->begin();191 auto *Store = cast<sandboxir::StoreInst>(&*It++);192 auto *Load = cast<sandboxir::LoadInst>(&*It++);193 auto *Add = cast<sandboxir::BinaryOperator>(&*It++);194 auto *StackSave = cast<sandboxir::CallInst>(&*It++);195 auto *StackRestore = cast<sandboxir::CallInst>(&*It++);196 auto *SideEffect = cast<sandboxir::CallInst>(&*It++);197 auto *PseudoProbe = cast<sandboxir::CallInst>(&*It++);198 auto *FakeUse = cast<sandboxir::CallInst>(&*It++);199 auto *Call = cast<sandboxir::CallInst>(&*It++);200 auto *Ret = cast<sandboxir::ReturnInst>(&*It++);201 202 sandboxir::DependencyGraph DAG(getAA(*LLVMF), Ctx);203 DAG.extend({&*BB->begin(), BB->getTerminator()});204 EXPECT_TRUE(isa<llvm::sandboxir::MemDGNode>(DAG.getNode(Store)));205 EXPECT_TRUE(isa<llvm::sandboxir::MemDGNode>(DAG.getNode(Load)));206 EXPECT_FALSE(isa<llvm::sandboxir::MemDGNode>(DAG.getNode(Add)));207 EXPECT_TRUE(isa<llvm::sandboxir::MemDGNode>(DAG.getNode(StackSave)));208 EXPECT_TRUE(isa<llvm::sandboxir::MemDGNode>(DAG.getNode(StackRestore)));209 EXPECT_FALSE(isa<llvm::sandboxir::MemDGNode>(DAG.getNode(SideEffect)));210 EXPECT_FALSE(isa<llvm::sandboxir::MemDGNode>(DAG.getNode(PseudoProbe)));211 EXPECT_TRUE(isa<llvm::sandboxir::MemDGNode>(DAG.getNode(FakeUse)));212 EXPECT_TRUE(isa<llvm::sandboxir::MemDGNode>(DAG.getNode(Call)));213 EXPECT_FALSE(isa<llvm::sandboxir::MemDGNode>(DAG.getNode(Ret)));214}215 216TEST_F(DependencyGraphTest, Basic) {217 parseIR(C, R"IR(218define void @foo(ptr %ptr, i8 %v0, i8 %v1) {219 store i8 %v0, ptr %ptr220 store i8 %v1, ptr %ptr221 ret void222}223)IR");224 llvm::Function *LLVMF = &*M->getFunction("foo");225 sandboxir::Context Ctx(C);226 auto *F = Ctx.createFunction(LLVMF);227 auto *BB = &*F->begin();228 auto It = BB->begin();229 auto *S0 = cast<sandboxir::StoreInst>(&*It++);230 auto *S1 = cast<sandboxir::StoreInst>(&*It++);231 auto *Ret = cast<sandboxir::ReturnInst>(&*It++);232 sandboxir::DependencyGraph DAG(getAA(*LLVMF), Ctx);233 auto Span = DAG.extend({&*BB->begin(), BB->getTerminator()});234 // Check extend().235 EXPECT_EQ(Span.top(), &*BB->begin());236 EXPECT_EQ(Span.bottom(), BB->getTerminator());237 238 auto *N0 = cast<sandboxir::MemDGNode>(DAG.getNode(S0));239 auto *N1 = cast<sandboxir::MemDGNode>(DAG.getNode(S1));240 auto *N2 = DAG.getNode(Ret);241 242 // Check getInstruction().243 EXPECT_EQ(N0->getInstruction(), S0);244 EXPECT_EQ(N1->getInstruction(), S1);245 // Check hasMemPred()246 EXPECT_TRUE(N1->hasMemPred(N0));247 EXPECT_FALSE(N0->hasMemPred(N1));248 249 // Check preds().250 EXPECT_TRUE(N0->preds(DAG).empty());251 EXPECT_THAT(N1->preds(DAG), testing::ElementsAre(N0));252 253 // Check memPreds().254 EXPECT_TRUE(N0->memPreds().empty());255 EXPECT_THAT(N1->memPreds(), testing::ElementsAre(N0));256 EXPECT_TRUE(N2->preds(DAG).empty());257 258 // Check memSuccs().259 EXPECT_THAT(N0->memSuccs(), testing::ElementsAre(N1));260 261 // Check UnscheduledSuccs.262 EXPECT_EQ(N0->getNumUnscheduledSuccs(), 1u); // N1263 EXPECT_EQ(N1->getNumUnscheduledSuccs(), 0u);264 EXPECT_EQ(N2->getNumUnscheduledSuccs(), 0u);265 266 // Check decrUnscheduledSuccs.267 N0->decrUnscheduledSuccs();268 EXPECT_EQ(N0->getNumUnscheduledSuccs(), 0u);269#ifndef NDEBUG270 EXPECT_DEATH(N0->decrUnscheduledSuccs(), ".*Counting.*");271#endif // NDEBUG272 273 // Check scheduled(), setScheduled().274 EXPECT_FALSE(N0->scheduled());275 N0->setScheduled(true);276 EXPECT_TRUE(N0->scheduled());277}278 279TEST_F(DependencyGraphTest, AddRemoveMemPred) {280 parseIR(C, R"IR(281define void @foo(ptr %ptr, i8 %v0, i8 %v1) {282 store i8 %v0, ptr %ptr283 store i8 %v1, ptr %ptr284 ret void285}286)IR");287 llvm::Function *LLVMF = &*M->getFunction("foo");288 sandboxir::Context Ctx(C);289 auto *F = Ctx.createFunction(LLVMF);290 auto *BB = &*F->begin();291 auto It = BB->begin();292 auto *S0 = cast<sandboxir::StoreInst>(&*It++);293 auto *S1 = cast<sandboxir::StoreInst>(&*It++);294 295 sandboxir::DependencyGraph DAG(getAA(*LLVMF), Ctx);296 DAG.extend({&*BB->begin(), BB->getTerminator()});297 auto *N0 = cast<sandboxir::MemDGNode>(DAG.getNode(S0));298 auto *N1 = cast<sandboxir::MemDGNode>(DAG.getNode(S1));299 300 // Check removeMemPred().301 EXPECT_FALSE(N0->memSuccs().empty());302 EXPECT_EQ(N0->getNumUnscheduledSuccs(), 1u);303 N1->removeMemPred(N0);304 EXPECT_TRUE(N1->memPreds().empty());305 EXPECT_EQ(N0->getNumUnscheduledSuccs(), 0u);306 307 // Check addMemPred().308 N1->addMemPred(N0);309 EXPECT_THAT(N1->memPreds(), testing::UnorderedElementsAre(N0));310 EXPECT_THAT(N0->memSuccs(), testing::UnorderedElementsAre(N1));311 EXPECT_THAT(N0->getNumUnscheduledSuccs(), 1u);312}313 314TEST_F(DependencyGraphTest, Preds) {315 parseIR(C, R"IR(316declare ptr @bar(i8)317define i8 @foo(i8 %v0, i8 %v1) {318 %add0 = add i8 %v0, %v0319 %add1 = add i8 %v1, %v1320 %add2 = add i8 %add0, %add1321 %ptr = call ptr @bar(i8 %add1)322 store i8 %add2, ptr %ptr323 ret i8 %add2324}325)IR");326 llvm::Function *LLVMF = &*M->getFunction("foo");327 sandboxir::Context Ctx(C);328 auto *F = Ctx.createFunction(LLVMF);329 auto *BB = &*F->begin();330 auto It = BB->begin();331 sandboxir::DependencyGraph DAG(getAA(*LLVMF), Ctx);332 DAG.extend({&*BB->begin(), BB->getTerminator()});333 334 auto *AddN0 = DAG.getNode(cast<sandboxir::BinaryOperator>(&*It++));335 auto *AddN1 = DAG.getNode(cast<sandboxir::BinaryOperator>(&*It++));336 auto *AddN2 = DAG.getNode(cast<sandboxir::BinaryOperator>(&*It++));337 auto *CallN = DAG.getNode(cast<sandboxir::CallInst>(&*It++));338 auto *StN = DAG.getNode(cast<sandboxir::StoreInst>(&*It++));339 auto *RetN = DAG.getNode(cast<sandboxir::ReturnInst>(&*It++));340 341 // Check preds().342 EXPECT_THAT(AddN0->preds(DAG), testing::ElementsAre());343 EXPECT_THAT(AddN1->preds(DAG), testing::ElementsAre());344 EXPECT_THAT(AddN2->preds(DAG), testing::ElementsAre(AddN0, AddN1));345 EXPECT_THAT(CallN->preds(DAG), testing::ElementsAre(AddN1));346 EXPECT_THAT(StN->preds(DAG),347 testing::UnorderedElementsAre(CallN, CallN, AddN2));348 EXPECT_THAT(RetN->preds(DAG), testing::ElementsAre(AddN2));349 350 // Check UnscheduledSuccs.351 EXPECT_EQ(AddN0->getNumUnscheduledSuccs(), 1u); // AddN2352 EXPECT_EQ(AddN1->getNumUnscheduledSuccs(), 2u); // AddN2, CallN353 EXPECT_EQ(AddN2->getNumUnscheduledSuccs(), 2u); // StN, RetN354 EXPECT_EQ(CallN->getNumUnscheduledSuccs(), 2u); // StN, StN355 EXPECT_EQ(StN->getNumUnscheduledSuccs(), 0u);356 EXPECT_EQ(RetN->getNumUnscheduledSuccs(), 0u);357}358 359// Make sure we don't get null predecessors even if they are outside the DAG.360TEST_F(DependencyGraphTest, NonNullPreds) {361 parseIR(C, R"IR(362define void @foo(ptr %ptr, i8 %val) {363 %gep = getelementptr i8, ptr %ptr, i32 0364 store i8 %val, ptr %gep365 ret void366}367)IR");368 llvm::Function *LLVMF = &*M->getFunction("foo");369 sandboxir::Context Ctx(C);370 auto *F = Ctx.createFunction(LLVMF);371 auto *BB = &*F->begin();372 auto It = BB->begin();373 [[maybe_unused]] auto *GEP = cast<sandboxir::GetElementPtrInst>(&*It++);374 auto *S0 = cast<sandboxir::StoreInst>(&*It++);375 auto *Ret = cast<sandboxir::ReturnInst>(&*It++);376 377 sandboxir::DependencyGraph DAG(getAA(*LLVMF), Ctx);378 // The DAG doesn't include GEP.379 DAG.extend({S0, Ret});380 381 auto *S0N = DAG.getNode(S0);382 // S0 has one operand (the GEP) that is outside the DAG and no memory383 // predecessors. So pred_begin() should be == pred_end().384 auto PredIt = S0N->preds_begin(DAG);385 auto PredItE = S0N->preds_end(DAG);386 EXPECT_EQ(PredIt, PredItE);387 // Check preds().388 for (auto *PredN : S0N->preds(DAG))389 EXPECT_NE(PredN, nullptr);390}391 392TEST_F(DependencyGraphTest, MemDGNode_getPrevNode_getNextNode) {393 parseIR(C, R"IR(394define void @foo(ptr %ptr, i8 %v0, i8 %v1) {395 store i8 %v0, ptr %ptr396 add i8 %v0, %v0397 store i8 %v1, ptr %ptr398 ret void399}400)IR");401 llvm::Function *LLVMF = &*M->getFunction("foo");402 sandboxir::Context Ctx(C);403 auto *F = Ctx.createFunction(LLVMF);404 auto *BB = &*F->begin();405 auto It = BB->begin();406 auto *S0 = cast<sandboxir::StoreInst>(&*It++);407 [[maybe_unused]] auto *Add = cast<sandboxir::BinaryOperator>(&*It++);408 auto *S1 = cast<sandboxir::StoreInst>(&*It++);409 [[maybe_unused]] auto *Ret = cast<sandboxir::ReturnInst>(&*It++);410 411 sandboxir::DependencyGraph DAG(getAA(*LLVMF), Ctx);412 DAG.extend({&*BB->begin(), BB->getTerminator()});413 414 auto *S0N = cast<sandboxir::MemDGNode>(DAG.getNode(S0));415 auto *S1N = cast<sandboxir::MemDGNode>(DAG.getNode(S1));416 417 EXPECT_EQ(S0N->getPrevNode(), nullptr);418 EXPECT_EQ(S0N->getNextNode(), S1N);419 420 EXPECT_EQ(S1N->getPrevNode(), S0N);421 EXPECT_EQ(S1N->getNextNode(), nullptr);422}423 424TEST_F(DependencyGraphTest, DGNodeRange) {425 parseIR(C, R"IR(426define void @foo(ptr %ptr, i8 %v0, i8 %v1) {427 add i8 %v0, %v0428 store i8 %v0, ptr %ptr429 add i8 %v0, %v0430 store i8 %v1, ptr %ptr431 ret void432}433)IR");434 llvm::Function *LLVMF = &*M->getFunction("foo");435 sandboxir::Context Ctx(C);436 auto *F = Ctx.createFunction(LLVMF);437 auto *BB = &*F->begin();438 auto It = BB->begin();439 auto *Add0 = cast<sandboxir::BinaryOperator>(&*It++);440 auto *S0 = cast<sandboxir::StoreInst>(&*It++);441 auto *Add1 = cast<sandboxir::BinaryOperator>(&*It++);442 auto *S1 = cast<sandboxir::StoreInst>(&*It++);443 auto *Ret = cast<sandboxir::ReturnInst>(&*It++);444 445 sandboxir::DependencyGraph DAG(getAA(*LLVMF), Ctx);446 DAG.extend({&*BB->begin(), BB->getTerminator()});447 448 auto *S0N = cast<sandboxir::MemDGNode>(DAG.getNode(S0));449 auto *S1N = cast<sandboxir::MemDGNode>(DAG.getNode(S1));450 451 // Check getTopMemDGNode().452 using B = sandboxir::MemDGNodeIntervalBuilder;453 using InstrInterval = sandboxir::Interval<sandboxir::Instruction>;454 EXPECT_EQ(B::getTopMemDGNode(InstrInterval(S0, S0), DAG), S0N);455 EXPECT_EQ(B::getTopMemDGNode(InstrInterval(S0, Ret), DAG), S0N);456 EXPECT_EQ(B::getTopMemDGNode(InstrInterval(Add0, Add1), DAG), S0N);457 EXPECT_EQ(B::getTopMemDGNode(InstrInterval(Add0, Add0), DAG), nullptr);458 459 // Check getBotMemDGNode().460 EXPECT_EQ(B::getBotMemDGNode(InstrInterval(S1, S1), DAG), S1N);461 EXPECT_EQ(B::getBotMemDGNode(InstrInterval(Add0, S1), DAG), S1N);462 EXPECT_EQ(B::getBotMemDGNode(InstrInterval(Add0, Ret), DAG), S1N);463 EXPECT_EQ(B::getBotMemDGNode(InstrInterval(Ret, Ret), DAG), nullptr);464 465 // Check empty range.466 EXPECT_THAT(sandboxir::MemDGNodeIntervalBuilder::makeEmpty(),467 testing::ElementsAre());468 469 // Returns the pointers in Range.470 auto getPtrVec = [](const auto &Range) {471 SmallVector<const sandboxir::DGNode *> Vec;472 for (const sandboxir::DGNode &N : Range)473 Vec.push_back(&N);474 return Vec;475 };476 // Both TopN and BotN are memory.477 EXPECT_THAT(478 getPtrVec(sandboxir::MemDGNodeIntervalBuilder::make({S0, S1}, DAG)),479 testing::ElementsAre(S0N, S1N));480 // Only TopN is memory.481 EXPECT_THAT(482 getPtrVec(sandboxir::MemDGNodeIntervalBuilder::make({S0, Ret}, DAG)),483 testing::ElementsAre(S0N, S1N));484 EXPECT_THAT(485 getPtrVec(sandboxir::MemDGNodeIntervalBuilder::make({S0, Add1}, DAG)),486 testing::ElementsAre(S0N));487 // Only BotN is memory.488 EXPECT_THAT(489 getPtrVec(sandboxir::MemDGNodeIntervalBuilder::make({Add0, S1}, DAG)),490 testing::ElementsAre(S0N, S1N));491 EXPECT_THAT(492 getPtrVec(sandboxir::MemDGNodeIntervalBuilder::make({Add0, S0}, DAG)),493 testing::ElementsAre(S0N));494 // Neither TopN or BotN is memory.495 EXPECT_THAT(496 getPtrVec(sandboxir::MemDGNodeIntervalBuilder::make({Add0, Ret}, DAG)),497 testing::ElementsAre(S0N, S1N));498 EXPECT_THAT(499 getPtrVec(sandboxir::MemDGNodeIntervalBuilder::make({Add0, Add0}, DAG)),500 testing::ElementsAre());501}502 503TEST_F(DependencyGraphTest, AliasingStores) {504 parseIR(C, R"IR(505define void @foo(ptr %ptr, i8 %v0, i8 %v1) {506 store i8 %v0, ptr %ptr507 store i8 %v1, ptr %ptr508 ret void509}510)IR");511 llvm::Function *LLVMF = &*M->getFunction("foo");512 sandboxir::Context Ctx(C);513 auto *F = Ctx.createFunction(LLVMF);514 auto *BB = &*F->begin();515 sandboxir::DependencyGraph DAG(getAA(*LLVMF), Ctx);516 DAG.extend({&*BB->begin(), BB->getTerminator()});517 auto It = BB->begin();518 auto *Store0N = cast<sandboxir::MemDGNode>(519 DAG.getNode(cast<sandboxir::StoreInst>(&*It++)));520 auto *Store1N = cast<sandboxir::MemDGNode>(521 DAG.getNode(cast<sandboxir::StoreInst>(&*It++)));522 auto *RetN = DAG.getNode(cast<sandboxir::ReturnInst>(&*It++));523 EXPECT_TRUE(Store0N->memPreds().empty());524 EXPECT_THAT(Store1N->memPreds(), testing::ElementsAre(Store0N));525 EXPECT_TRUE(RetN->preds(DAG).empty());526}527 528TEST_F(DependencyGraphTest, NonAliasingStores) {529 parseIR(C, R"IR(530define void @foo(ptr noalias %ptr0, ptr noalias %ptr1, i8 %v0, i8 %v1) {531 store i8 %v0, ptr %ptr0532 store i8 %v1, ptr %ptr1533 ret void534}535)IR");536 llvm::Function *LLVMF = &*M->getFunction("foo");537 sandboxir::Context Ctx(C);538 auto *F = Ctx.createFunction(LLVMF);539 auto *BB = &*F->begin();540 sandboxir::DependencyGraph DAG(getAA(*LLVMF), Ctx);541 DAG.extend({&*BB->begin(), BB->getTerminator()});542 auto It = BB->begin();543 auto *Store0N = cast<sandboxir::MemDGNode>(544 DAG.getNode(cast<sandboxir::StoreInst>(&*It++)));545 auto *Store1N = cast<sandboxir::MemDGNode>(546 DAG.getNode(cast<sandboxir::StoreInst>(&*It++)));547 auto *RetN = DAG.getNode(cast<sandboxir::ReturnInst>(&*It++));548 // We expect no dependencies because the stores don't alias.549 EXPECT_TRUE(Store0N->memPreds().empty());550 EXPECT_TRUE(Store1N->memPreds().empty());551 EXPECT_TRUE(RetN->preds(DAG).empty());552}553 554TEST_F(DependencyGraphTest, VolatileLoads) {555 parseIR(C, R"IR(556define void @foo(ptr noalias %ptr0, ptr noalias %ptr1) {557 %ld0 = load volatile i8, ptr %ptr0558 %ld1 = load volatile i8, ptr %ptr1559 ret void560}561)IR");562 llvm::Function *LLVMF = &*M->getFunction("foo");563 sandboxir::Context Ctx(C);564 auto *F = Ctx.createFunction(LLVMF);565 auto *BB = &*F->begin();566 sandboxir::DependencyGraph DAG(getAA(*LLVMF), Ctx);567 DAG.extend({&*BB->begin(), BB->getTerminator()});568 auto It = BB->begin();569 auto *Ld0N = cast<sandboxir::MemDGNode>(570 DAG.getNode(cast<sandboxir::LoadInst>(&*It++)));571 auto *Ld1N = cast<sandboxir::MemDGNode>(572 DAG.getNode(cast<sandboxir::LoadInst>(&*It++)));573 auto *RetN = DAG.getNode(cast<sandboxir::ReturnInst>(&*It++));574 EXPECT_TRUE(Ld0N->memPreds().empty());575 EXPECT_THAT(Ld1N->memPreds(), testing::ElementsAre(Ld0N));576 EXPECT_TRUE(RetN->preds(DAG).empty());577}578 579TEST_F(DependencyGraphTest, VolatileStores) {580 parseIR(C, R"IR(581define void @foo(ptr noalias %ptr0, ptr noalias %ptr1, i8 %v) {582 store volatile i8 %v, ptr %ptr0583 store volatile i8 %v, ptr %ptr1584 ret void585}586)IR");587 llvm::Function *LLVMF = &*M->getFunction("foo");588 sandboxir::Context Ctx(C);589 auto *F = Ctx.createFunction(LLVMF);590 auto *BB = &*F->begin();591 sandboxir::DependencyGraph DAG(getAA(*LLVMF), Ctx);592 DAG.extend({&*BB->begin(), BB->getTerminator()});593 auto It = BB->begin();594 auto *Store0N = cast<sandboxir::MemDGNode>(595 DAG.getNode(cast<sandboxir::StoreInst>(&*It++)));596 auto *Store1N = cast<sandboxir::MemDGNode>(597 DAG.getNode(cast<sandboxir::StoreInst>(&*It++)));598 auto *RetN = DAG.getNode(cast<sandboxir::ReturnInst>(&*It++));599 EXPECT_TRUE(Store0N->memPreds().empty());600 EXPECT_THAT(Store1N->memPreds(), testing::ElementsAre(Store0N));601 EXPECT_TRUE(RetN->preds(DAG).empty());602}603 604TEST_F(DependencyGraphTest, Call) {605 parseIR(C, R"IR(606declare void @bar1()607declare void @bar2()608define void @foo(float %v1, float %v2) {609 call void @bar1()610 %add = fadd float %v1, %v2611 call void @bar2()612 ret void613}614)IR");615 Function *LLVMF = M->getFunction("foo");616 617 sandboxir::Context Ctx(C);618 auto *F = Ctx.createFunction(LLVMF);619 auto *BB = &*F->begin();620 621 sandboxir::DependencyGraph DAG(getAA(*LLVMF), Ctx);622 DAG.extend({&*BB->begin(), BB->getTerminator()->getPrevNode()});623 624 auto It = BB->begin();625 auto *Call1N = cast<sandboxir::MemDGNode>(DAG.getNode(&*It++));626 auto *AddN = DAG.getNode(&*It++);627 auto *Call2N = cast<sandboxir::MemDGNode>(DAG.getNode(&*It++));628 629 EXPECT_THAT(Call1N->memPreds(), testing::ElementsAre());630 EXPECT_THAT(AddN->preds(DAG), testing::ElementsAre());631 EXPECT_THAT(Call2N->memPreds(), testing::ElementsAre(Call1N));632}633 634// Check that there is a dependency: stacksave -> alloca -> stackrestore.635TEST_F(DependencyGraphTest, StackSaveRestoreInAlloca) {636 parseIR(C, R"IR(637declare ptr @llvm.stacksave()638declare void @llvm.stackrestore(ptr %ptr)639 640define void @foo() {641 %stack0 = call ptr @llvm.stacksave() ; Should depend on store642 %alloca0 = alloca inalloca i8 ; Should depend on stacksave643 call void @llvm.stackrestore(ptr %stack0) ; Should depend transiently on %alloca0644 ret void645}646)IR");647 Function *LLVMF = M->getFunction("foo");648 649 sandboxir::Context Ctx(C);650 auto *F = Ctx.createFunction(LLVMF);651 auto *BB = &*F->begin();652 653 sandboxir::DependencyGraph DAG(getAA(*LLVMF), Ctx);654 DAG.extend({&*BB->begin(), BB->getTerminator()->getPrevNode()});655 656 auto It = BB->begin();657 auto *StackSaveN = DAG.getNode(&*It++);658 auto *AllocaN = DAG.getNode(&*It++);659 auto *StackRestoreN = DAG.getNode(&*It++);660 661 EXPECT_TRUE(memDependency(AllocaN, StackRestoreN));662 EXPECT_TRUE(memDependency(StackSaveN, AllocaN));663}664 665// Checks that stacksave and stackrestore depend on other mem instrs.666TEST_F(DependencyGraphTest, StackSaveRestoreDependOnOtherMem) {667 parseIR(C, R"IR(668declare ptr @llvm.stacksave()669declare void @llvm.stackrestore(ptr %ptr)670 671define void @foo(i8 %v0, i8 %v1, ptr %ptr) {672 store volatile i8 %v0, ptr %ptr, align 4673 %stack0 = call ptr @llvm.stacksave() ; Should depend on store674 call void @llvm.stackrestore(ptr %stack0) ; Should depend on stacksave675 store volatile i8 %v1, ptr %ptr, align 4 ; Should depend on stackrestore676 ret void677}678)IR");679 Function *LLVMF = M->getFunction("foo");680 681 sandboxir::Context Ctx(C);682 auto *F = Ctx.createFunction(LLVMF);683 auto *BB = &*F->begin();684 685 sandboxir::DependencyGraph DAG(getAA(*LLVMF), Ctx);686 DAG.extend({&*BB->begin(), BB->getTerminator()->getPrevNode()});687 688 auto It = BB->begin();689 auto *Store0N = DAG.getNode(&*It++);690 auto *StackSaveN = DAG.getNode(&*It++);691 auto *StackRestoreN = DAG.getNode(&*It++);692 auto *Store1N = DAG.getNode(&*It++);693 694 EXPECT_TRUE(memDependency(Store0N, StackSaveN));695 EXPECT_TRUE(memDependency(StackSaveN, StackRestoreN));696 EXPECT_TRUE(memDependency(StackRestoreN, Store1N));697}698 699// Make sure there is a dependency between a stackrestore and an alloca.700TEST_F(DependencyGraphTest, StackRestoreAndInAlloca) {701 parseIR(C, R"IR(702declare void @llvm.stackrestore(ptr %ptr)703 704define void @foo(ptr %ptr) {705 call void @llvm.stackrestore(ptr %ptr)706 %alloca0 = alloca inalloca i8 ; Should depend on stackrestore707 ret void708}709)IR");710 Function *LLVMF = M->getFunction("foo");711 712 sandboxir::Context Ctx(C);713 auto *F = Ctx.createFunction(LLVMF);714 auto *BB = &*F->begin();715 716 sandboxir::DependencyGraph DAG(getAA(*LLVMF), Ctx);717 DAG.extend({&*BB->begin(), BB->getTerminator()->getPrevNode()});718 719 auto It = BB->begin();720 auto *StackRestoreN = DAG.getNode(&*It++);721 auto *AllocaN = DAG.getNode(&*It++);722 723 EXPECT_TRUE(memDependency(StackRestoreN, AllocaN));724}725 726// Make sure there is a dependency between the alloca and stacksave727TEST_F(DependencyGraphTest, StackSaveAndInAlloca) {728 parseIR(C, R"IR(729declare ptr @llvm.stacksave()730 731define void @foo(ptr %ptr) {732 %alloca0 = alloca inalloca i8 ; Should depend on stackrestore733 %stack0 = call ptr @llvm.stacksave() ; Should depend on alloca0734 ret void735}736)IR");737 Function *LLVMF = M->getFunction("foo");738 739 sandboxir::Context Ctx(C);740 auto *F = Ctx.createFunction(LLVMF);741 auto *BB = &*F->begin();742 743 sandboxir::DependencyGraph DAG(getAA(*LLVMF), Ctx);744 DAG.extend({&*BB->begin(), BB->getTerminator()->getPrevNode()});745 746 auto It = BB->begin();747 auto *AllocaN = DAG.getNode(&*It++);748 auto *StackSaveN = DAG.getNode(&*It++);749 750 EXPECT_TRUE(memDependency(AllocaN, StackSaveN));751}752 753// A non-InAlloca in a stacksave-stackrestore region does not need extra754// dependencies.755TEST_F(DependencyGraphTest, StackSaveRestoreNoInAlloca) {756 parseIR(C, R"IR(757declare ptr @llvm.stacksave()758declare void @llvm.stackrestore(ptr %ptr)759declare void @use(ptr %ptr)760 761define void @foo() {762 %stack = call ptr @llvm.stacksave()763 %alloca1 = alloca i8 ; No dependency764 call void @llvm.stackrestore(ptr %stack)765 ret void766}767)IR");768 Function *LLVMF = M->getFunction("foo");769 770 sandboxir::Context Ctx(C);771 auto *F = Ctx.createFunction(LLVMF);772 auto *BB = &*F->begin();773 774 sandboxir::DependencyGraph DAG(getAA(*LLVMF), Ctx);775 DAG.extend({&*BB->begin(), BB->getTerminator()->getPrevNode()});776 777 auto It = BB->begin();778 auto *StackSaveN = DAG.getNode(&*It++);779 auto *AllocaN = DAG.getNode(&*It++);780 auto *StackRestoreN = DAG.getNode(&*It++);781 782 EXPECT_FALSE(memDependency(StackSaveN, AllocaN));783 EXPECT_FALSE(memDependency(AllocaN, StackRestoreN));784}785 786TEST_F(DependencyGraphTest, Extend) {787 parseIR(C, R"IR(788define void @foo(ptr %ptr, i8 %v1, i8 %v2, i8 %v3, i8 %v4, i8 %v5) {789 store i8 %v1, ptr %ptr790 store i8 %v2, ptr %ptr791 store i8 %v3, ptr %ptr792 store i8 %v4, ptr %ptr793 store i8 %v5, ptr %ptr794 ret void795}796)IR");797 llvm::Function *LLVMF = &*M->getFunction("foo");798 sandboxir::Context Ctx(C);799 auto *F = Ctx.createFunction(LLVMF);800 auto *BB = &*F->begin();801 auto It = BB->begin();802 auto *S1 = cast<sandboxir::StoreInst>(&*It++);803 auto *S2 = cast<sandboxir::StoreInst>(&*It++);804 auto *S3 = cast<sandboxir::StoreInst>(&*It++);805 auto *S4 = cast<sandboxir::StoreInst>(&*It++);806 auto *S5 = cast<sandboxir::StoreInst>(&*It++);807 sandboxir::DependencyGraph DAG(getAA(*LLVMF), Ctx);808 {809 // Scenario 1: Build new DAG810 auto NewIntvl = DAG.extend({S3, S3});811 EXPECT_EQ(NewIntvl, sandboxir::Interval<sandboxir::Instruction>(S3, S3));812 EXPECT_EQ(DAG.getInterval().top(), S3);813 EXPECT_EQ(DAG.getInterval().bottom(), S3);814 [[maybe_unused]] auto *S3N = cast<sandboxir::MemDGNode>(DAG.getNode(S3));815 // Check UnscheduledSuccs.816 EXPECT_EQ(S3N->getNumUnscheduledSuccs(), 0u);817 }818 {819 // Scenario 2: Extend below820 auto NewIntvl = DAG.extend({S5, S5});821 EXPECT_EQ(NewIntvl, sandboxir::Interval<sandboxir::Instruction>(S4, S5));822 auto *S3N = cast<sandboxir::MemDGNode>(DAG.getNode(S3));823 auto *S4N = cast<sandboxir::MemDGNode>(DAG.getNode(S4));824 auto *S5N = cast<sandboxir::MemDGNode>(DAG.getNode(S5));825 EXPECT_TRUE(S4N->hasMemPred(S3N));826 EXPECT_TRUE(S5N->hasMemPred(S4N));827 EXPECT_TRUE(S5N->hasMemPred(S3N));828 // Check UnscheduledSuccs.829 EXPECT_EQ(S3N->getNumUnscheduledSuccs(), 2u); // S4N, S5N830 EXPECT_EQ(S4N->getNumUnscheduledSuccs(), 1u); // S5N831 EXPECT_EQ(S5N->getNumUnscheduledSuccs(), 0u);832 }833 {834 // Scenario 3: Extend above835 auto NewIntvl = DAG.extend({S1, S2});836 EXPECT_EQ(NewIntvl, sandboxir::Interval<sandboxir::Instruction>(S1, S2));837 auto *S1N = cast<sandboxir::MemDGNode>(DAG.getNode(S1));838 auto *S2N = cast<sandboxir::MemDGNode>(DAG.getNode(S2));839 auto *S3N = cast<sandboxir::MemDGNode>(DAG.getNode(S3));840 auto *S4N = cast<sandboxir::MemDGNode>(DAG.getNode(S4));841 auto *S5N = cast<sandboxir::MemDGNode>(DAG.getNode(S5));842 843 EXPECT_TRUE(S2N->hasMemPred(S1N));844 845 EXPECT_TRUE(S3N->hasMemPred(S2N));846 EXPECT_TRUE(S3N->hasMemPred(S1N));847 848 EXPECT_TRUE(S4N->hasMemPred(S3N));849 EXPECT_TRUE(S4N->hasMemPred(S2N));850 EXPECT_TRUE(S4N->hasMemPred(S1N));851 852 EXPECT_TRUE(S5N->hasMemPred(S4N));853 EXPECT_TRUE(S5N->hasMemPred(S3N));854 EXPECT_TRUE(S5N->hasMemPred(S2N));855 EXPECT_TRUE(S5N->hasMemPred(S1N));856 857 // Check UnscheduledSuccs.858 EXPECT_EQ(S1N->getNumUnscheduledSuccs(), 4u); // S2N, S3N, S4N, S5N859 EXPECT_EQ(S2N->getNumUnscheduledSuccs(), 3u); // S3N, S4N, S5N860 EXPECT_EQ(S3N->getNumUnscheduledSuccs(), 2u); // S4N, S5N861 EXPECT_EQ(S4N->getNumUnscheduledSuccs(), 1u); // S5N862 EXPECT_EQ(S5N->getNumUnscheduledSuccs(), 0u);863 }864 865 {866 // Check UnscheduledSuccs when a node is scheduled867 sandboxir::DependencyGraph DAG(getAA(*LLVMF), Ctx);868 DAG.extend({S2, S2});869 auto *S2N = cast<sandboxir::MemDGNode>(DAG.getNode(S2));870 S2N->setScheduled(true);871 872 DAG.extend({S1, S1});873 auto *S1N = cast<sandboxir::MemDGNode>(DAG.getNode(S1));874 EXPECT_EQ(S1N->getNumUnscheduledSuccs(), 0u); // S1 is scheduled875 }876}877 878// Check that the DAG gets updated when we create a new instruction.879TEST_F(DependencyGraphTest, CreateInstrCallback) {880 parseIR(C, R"IR(881define void @foo(ptr %ptr, i8 %v1, i8 %v2, i8 %v3, i8 %new1, i8 %new2) {882 store i8 %v1, ptr %ptr883 store i8 %v2, ptr %ptr884 store i8 %v3, ptr %ptr885 ret void886}887)IR");888 llvm::Function *LLVMF = &*M->getFunction("foo");889 sandboxir::Context Ctx(C);890 auto *F = Ctx.createFunction(LLVMF);891 auto *BB = &*F->begin();892 auto It = BB->begin();893 auto *S1 = cast<sandboxir::StoreInst>(&*It++);894 auto *S2 = cast<sandboxir::StoreInst>(&*It++);895 auto *S3 = cast<sandboxir::StoreInst>(&*It++);896 auto *Ret = cast<sandboxir::ReturnInst>(&*It++);897 898 sandboxir::DependencyGraph DAG(getAA(*LLVMF), Ctx);899 // Create a DAG spanning S1 to S3.900 DAG.extend({S1, S3});901 auto *ArgNew1 = F->getArg(4);902 auto *ArgNew2 = F->getArg(5);903 auto *Ptr = S1->getPointerOperand();904 905 auto *S1MemN = cast<sandboxir::MemDGNode>(DAG.getNode(S1));906 auto *S2MemN = cast<sandboxir::MemDGNode>(DAG.getNode(S2));907 auto *S3MemN = cast<sandboxir::MemDGNode>(DAG.getNode(S3));908 sandboxir::MemDGNode *New1MemN = nullptr;909 sandboxir::MemDGNode *New2MemN = nullptr;910 {911 // Create a new store before S3 (within the span of the DAG).912 sandboxir::StoreInst *NewS =913 sandboxir::StoreInst::create(ArgNew1, Ptr, Align(8), S3->getIterator(),914 /*IsVolatile=*/true, Ctx);915 // Check the MemDGNode chain.916 New1MemN = cast<sandboxir::MemDGNode>(DAG.getNode(NewS));917 EXPECT_EQ(S2MemN->getNextNode(), New1MemN);918 EXPECT_EQ(New1MemN->getPrevNode(), S2MemN);919 EXPECT_EQ(New1MemN->getNextNode(), S3MemN);920 EXPECT_EQ(S3MemN->getPrevNode(), New1MemN);921 922 // Check dependencies.923 EXPECT_TRUE(memDependency(S1MemN, New1MemN));924 EXPECT_TRUE(memDependency(S2MemN, New1MemN));925 EXPECT_TRUE(memDependency(New1MemN, S3MemN));926 }927 {928 // Create a new store before Ret (outside the current DAG).929 sandboxir::StoreInst *NewS =930 sandboxir::StoreInst::create(ArgNew2, Ptr, Align(8), Ret->getIterator(),931 /*IsVolatile=*/true, Ctx);932 // Check the MemDGNode chain.933 New2MemN = cast<sandboxir::MemDGNode>(DAG.getNode(NewS));934 EXPECT_EQ(S3MemN->getNextNode(), New2MemN);935 EXPECT_EQ(New2MemN->getPrevNode(), S3MemN);936 EXPECT_EQ(New2MemN->getNextNode(), nullptr);937 938 // Check dependencies.939 EXPECT_TRUE(memDependency(S1MemN, New2MemN));940 EXPECT_TRUE(memDependency(S2MemN, New2MemN));941 EXPECT_TRUE(memDependency(New1MemN, New2MemN));942 EXPECT_TRUE(memDependency(S3MemN, New2MemN));943 }944}945 946TEST_F(DependencyGraphTest, EraseInstrCallback) {947 parseIR(C, R"IR(948define void @foo(ptr %ptr, i8 %v1, i8 %v2, i8 %v3, i8 %v4, i8 %arg) {949 store i8 %v1, ptr %ptr950 store i8 %v2, ptr %ptr951 store i8 %v3, ptr %ptr952 store i8 %v4, ptr %ptr953 ret void954}955)IR");956 llvm::Function *LLVMF = &*M->getFunction("foo");957 sandboxir::Context Ctx(C);958 auto *F = Ctx.createFunction(LLVMF);959 auto *BB = &*F->begin();960 auto It = BB->begin();961 auto *S1 = cast<sandboxir::StoreInst>(&*It++);962 auto *S2 = cast<sandboxir::StoreInst>(&*It++);963 auto *S3 = cast<sandboxir::StoreInst>(&*It++);964 auto *S4NotInDAG = cast<sandboxir::StoreInst>(&*It++);965 966 // Check erase instruction callback.967 sandboxir::DependencyGraph DAG(getAA(*LLVMF), Ctx);968 DAG.extend({S1, S3});969 auto *S1MemN = cast<sandboxir::MemDGNode>(DAG.getNode(S1));970 auto *S2MemN = cast<sandboxir::MemDGNode>(DAG.getNode(S2));971 auto *S3MemN = cast<sandboxir::MemDGNode>(DAG.getNode(S3));972 EXPECT_EQ(S1MemN->getNumUnscheduledSuccs(), 2u);973 EXPECT_EQ(S2MemN->getNumUnscheduledSuccs(), 1u);974 EXPECT_EQ(S3MemN->getNumUnscheduledSuccs(), 0u);975 S2->eraseFromParent();976 // Check that the DAG Node for S2 no longer exists.977 auto *DeletedN = DAG.getNode(S2);978 EXPECT_TRUE(DeletedN == nullptr);979 // Check that dependencies are maintained.980 EXPECT_THAT(S3MemN->preds(DAG), testing::UnorderedElementsAre(S1MemN));981 // Also check that UnscheduledSuccs was updated for S1.982 EXPECT_EQ(S1MemN->getNumUnscheduledSuccs(), 1u);983 984 // Check the MemDGNode chain.985 EXPECT_EQ(S1MemN->getNextNode(), S3MemN);986 EXPECT_EQ(S3MemN->getPrevNode(), S1MemN);987 988 // Check the chain when we erase the top node.989 S1->eraseFromParent();990 EXPECT_EQ(S3MemN->getPrevNode(), nullptr);991 992 // Check that we don't crash if we erase a node not in the DAG.993 S4NotInDAG->eraseFromParent();994}995 996// Same but check that we don't update UnscheduledSuccs when Node is scheduled.997TEST_F(DependencyGraphTest, EraseInstrCallbackScheduled) {998 parseIR(C, R"IR(999define void @foo(ptr %ptr, i8 %v1, i8 %v2, i8 %v3, i8 %v4, i8 %arg) {1000 store i8 %v1, ptr %ptr1001 store i8 %v2, ptr %ptr1002 ret void1003}1004)IR");1005 llvm::Function *LLVMF = &*M->getFunction("foo");1006 sandboxir::Context Ctx(C);1007 auto *F = Ctx.createFunction(LLVMF);1008 auto *BB = &*F->begin();1009 auto It = BB->begin();1010 auto *S1 = cast<sandboxir::StoreInst>(&*It++);1011 auto *S2 = cast<sandboxir::StoreInst>(&*It++);1012 1013 sandboxir::DependencyGraph DAG(getAA(*LLVMF), Ctx);1014 DAG.extend({S1, S2});1015 auto *S1MemN = cast<sandboxir::MemDGNode>(DAG.getNode(S1));1016 auto *S2MemN = cast<sandboxir::MemDGNode>(DAG.getNode(S2));1017 EXPECT_EQ(S1MemN->getNumUnscheduledSuccs(), 1u);1018 EXPECT_EQ(S2MemN->getNumUnscheduledSuccs(), 0u);1019 // Mark S2 as scheduled and erase it.1020 S2MemN->setScheduled(true);1021 S2->eraseFromParent();1022 EXPECT_EQ(DAG.getNode(S2), nullptr);1023 // Check that we did not update S1's UnscheduledSuccs1024 EXPECT_EQ(S1MemN->getNumUnscheduledSuccs(), 1u);1025}1026 1027TEST_F(DependencyGraphTest, MoveInstrCallback) {1028 parseIR(C, R"IR(1029define void @foo(ptr %ptr, ptr %ptr2, i8 %v1, i8 %v2, i8 %v3, i8 %arg) {1030 %ld0 = load i8, ptr %ptr21031 store i8 %v1, ptr %ptr1032 store i8 %v2, ptr %ptr1033 store i8 %v3, ptr %ptr1034 ret void1035}1036)IR");1037 llvm::Function *LLVMF = &*M->getFunction("foo");1038 sandboxir::Context Ctx(C);1039 auto *F = Ctx.createFunction(LLVMF);1040 auto *BB = &*F->begin();1041 auto It = BB->begin();1042 auto *Ld = cast<sandboxir::LoadInst>(&*It++);1043 auto *S1 = cast<sandboxir::StoreInst>(&*It++);1044 auto *S2 = cast<sandboxir::StoreInst>(&*It++);1045 auto *S3 = cast<sandboxir::StoreInst>(&*It++);1046 1047 sandboxir::DependencyGraph DAG(getAA(*LLVMF), Ctx);1048 DAG.extend({Ld, S3});1049 auto *LdN = cast<sandboxir::MemDGNode>(DAG.getNode(Ld));1050 auto *S1N = cast<sandboxir::MemDGNode>(DAG.getNode(S1));1051 auto *S2N = cast<sandboxir::MemDGNode>(DAG.getNode(S2));1052 EXPECT_EQ(S1N->getPrevNode(), LdN);1053 S1->moveBefore(Ld);1054 EXPECT_EQ(S1N->getPrevNode(), nullptr);1055 EXPECT_EQ(S1N->getNextNode(), LdN);1056 EXPECT_EQ(LdN->getPrevNode(), S1N);1057 EXPECT_EQ(LdN->getNextNode(), S2N);1058}1059 1060// Check that the mem chain is maintained correctly when the move destination is1061// not a mem node.1062TEST_F(DependencyGraphTest, MoveInstrCallbackWithNonMemInstrs) {1063 parseIR(C, R"IR(1064define void @foo(ptr %ptr, i8 %v1, i8 %v2, i8 %arg) {1065 %ld = load i8, ptr %ptr1066 %zext1 = zext i8 %arg to i321067 %zext2 = zext i8 %arg to i321068 store i8 %v1, ptr %ptr1069 store i8 %v2, ptr %ptr1070 ret void1071}1072)IR");1073 llvm::Function *LLVMF = &*M->getFunction("foo");1074 sandboxir::Context Ctx(C);1075 auto *F = Ctx.createFunction(LLVMF);1076 auto *BB = &*F->begin();1077 auto It = BB->begin();1078 auto *Ld = cast<sandboxir::LoadInst>(&*It++);1079 [[maybe_unused]] auto *Zext1 = cast<sandboxir::CastInst>(&*It++);1080 auto *Zext2 = cast<sandboxir::CastInst>(&*It++);1081 auto *S1 = cast<sandboxir::StoreInst>(&*It++);1082 auto *S2 = cast<sandboxir::StoreInst>(&*It++);1083 auto *Ret = cast<sandboxir::ReturnInst>(&*It++);1084 1085 sandboxir::DependencyGraph DAG(getAA(*LLVMF), Ctx);1086 DAG.extend({Ld, S2});1087 auto *LdN = cast<sandboxir::MemDGNode>(DAG.getNode(Ld));1088 auto *S1N = cast<sandboxir::MemDGNode>(DAG.getNode(S1));1089 auto *S2N = cast<sandboxir::MemDGNode>(DAG.getNode(S2));1090 EXPECT_EQ(LdN->getNextNode(), S1N);1091 EXPECT_EQ(S1N->getNextNode(), S2N);1092 1093 S1->moveBefore(Zext2);1094 EXPECT_EQ(LdN->getNextNode(), S1N);1095 EXPECT_EQ(S1N->getNextNode(), S2N);1096 1097 // Try move right after the end of the DAGInterval.1098 S1->moveBefore(Ret);1099 EXPECT_EQ(S2N->getNextNode(), S1N);1100 EXPECT_EQ(S1N->getNextNode(), nullptr);1101}1102 1103// Extending an "Old" interval with no mem instructions.1104TEST_F(DependencyGraphTest, ExtendDAGWithNoMem) {1105 parseIR(C, R"IR(1106define void @foo(ptr %ptr, i8 %v, i8 %v0, i8 %v1, i8 %v2, i8 %v3) {1107 store i8 %v0, ptr %ptr1108 store i8 %v1, ptr %ptr1109 %zext1 = zext i8 %v to i321110 %zext2 = zext i8 %v to i321111 store i8 %v2, ptr %ptr1112 store i8 %v3, ptr %ptr1113 ret void1114}1115)IR");1116 llvm::Function *LLVMF = &*M->getFunction("foo");1117 sandboxir::Context Ctx(C);1118 auto *F = Ctx.createFunction(LLVMF);1119 auto *BB = &*F->begin();1120 auto It = BB->begin();1121 auto *S0 = cast<sandboxir::StoreInst>(&*It++);1122 auto *S1 = cast<sandboxir::StoreInst>(&*It++);1123 auto *Z1 = cast<sandboxir::CastInst>(&*It++);1124 auto *Z2 = cast<sandboxir::CastInst>(&*It++);1125 auto *S2 = cast<sandboxir::StoreInst>(&*It++);1126 auto *S3 = cast<sandboxir::StoreInst>(&*It++);1127 1128 sandboxir::DependencyGraph DAG(getAA(*LLVMF), Ctx);1129 // Create a non-empty DAG that contains no memory instructions.1130 DAG.extend({Z1, Z2});1131 // Now extend it downwards.1132 DAG.extend({S2, S3});1133 EXPECT_TRUE(memDependency(DAG.getNode(S2), DAG.getNode(S3)));1134 1135 // Same but upwards.1136 DAG.clear();1137 DAG.extend({Z1, Z2});1138 DAG.extend({S0, S1});1139 EXPECT_TRUE(memDependency(DAG.getNode(S0), DAG.getNode(S1)));1140}1141 1142// Setting a Use with a setOperand(), RUW, RAUW etc. can add/remove use-def1143// edges. This needs to maintain the UnscheduledSuccs counter.1144TEST_F(DependencyGraphTest, MaintainUnscheduledSuccsOnUseSet) {1145 parseIR(C, R"IR(1146define void @foo(i8 %v0, i8 %v1) {1147 %add0 = add i8 %v0, %v11148 %add1 = add i8 %add0, %v11149 ret void1150}1151)IR");1152 llvm::Function *LLVMF = &*M->getFunction("foo");1153 sandboxir::Context Ctx(C);1154 auto *F = Ctx.createFunction(LLVMF);1155 auto *Arg0 = F->getArg(0);1156 auto *BB = &*F->begin();1157 auto It = BB->begin();1158 auto *Add0 = cast<sandboxir::BinaryOperator>(&*It++);1159 auto *Add1 = cast<sandboxir::BinaryOperator>(&*It++);1160 sandboxir::DependencyGraph DAG(getAA(*LLVMF), Ctx);1161 DAG.extend({Add0, Add1});1162 auto *N0 = DAG.getNode(Add0);1163 1164 EXPECT_EQ(N0->getNumUnscheduledSuccs(), 1u);1165 // Now change %add1 operand to not use %add0.1166 Add1->setOperand(0, Arg0);1167 EXPECT_EQ(N0->getNumUnscheduledSuccs(), 0u);1168 // Restore it: %add0 is now used by %add1.1169 Add1->setOperand(0, Add0);1170 EXPECT_EQ(N0->getNumUnscheduledSuccs(), 1u);1171 1172 // RAUW1173 Add0->replaceAllUsesWith(Arg0);1174 EXPECT_EQ(N0->getNumUnscheduledSuccs(), 0u);1175 // Restore it: %add0 is now used by %add1.1176 Add1->setOperand(0, Add0);1177 EXPECT_EQ(N0->getNumUnscheduledSuccs(), 1u);1178 1179 // RUWIf1180 Add0->replaceUsesWithIf(Arg0, [](const auto &U) { return true; });1181 EXPECT_EQ(N0->getNumUnscheduledSuccs(), 0u);1182 // Restore it: %add0 is now used by %add1.1183 Add1->setOperand(0, Add0);1184 EXPECT_EQ(N0->getNumUnscheduledSuccs(), 1u);1185 1186 // RUOW1187 Add1->replaceUsesOfWith(Add0, Arg0);1188 EXPECT_EQ(N0->getNumUnscheduledSuccs(), 0u);1189 // Restore it: %add0 is now used by %add1.1190 Add1->setOperand(0, Add0);1191 EXPECT_EQ(N0->getNumUnscheduledSuccs(), 1u);1192}1193