627 lines · cpp
1//===--------- WaitingOnGraphTest.cpp - Test WaitingOnGraph APIs ----------===//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/ExecutionEngine/Orc/WaitingOnGraph.h"10#include "gtest/gtest.h"11 12namespace llvm::orc::detail {13 14class WaitingOnGraphTest : public testing::Test {15public:16 using TestGraph = WaitingOnGraph<uintptr_t, uintptr_t>;17 18protected:19 using SuperNode = TestGraph::SuperNode;20 using SuperNodeBuilder = TestGraph::SuperNodeBuilder;21 using ContainerElementsMap = TestGraph::ContainerElementsMap;22 using ElemToSuperNodeMap = TestGraph::ElemToSuperNodeMap;23 using SimplifyResult = TestGraph::SimplifyResult;24 using EmitResult = TestGraph::EmitResult;25 26 static const ContainerElementsMap &getDefs(SuperNode &SN) { return SN.Defs; }27 28 static const ContainerElementsMap &getDeps(SuperNode &SN) { return SN.Deps; }29 30 static std::vector<std::unique_ptr<SuperNode>> &getSNs(SimplifyResult &SR) {31 return SR.SNs;32 }33 34 static ElemToSuperNodeMap &getElemToSN(SimplifyResult &SR) {35 return SR.ElemToSN;36 }37 38 static std::vector<std::unique_ptr<SuperNode>> &getPendingSNs(TestGraph &G) {39 return G.PendingSNs;40 }41 42 static ContainerElementsMap merge(ContainerElementsMap M1,43 const ContainerElementsMap &M2) {44 ContainerElementsMap Result = std::move(M1);45 for (auto &[Container, Elems] : M2)46 Result[Container].insert(Elems.begin(), Elems.end());47 return Result;48 }49 50 ContainerElementsMap51 collapseDefs(std::vector<std::unique_ptr<SuperNode>> &SNs,52 bool DepsMustMatch = true) {53 if (SNs.empty())54 return ContainerElementsMap();55 56 ContainerElementsMap Result = SNs[0]->defs();57#ifndef NDEBUG58 const ContainerElementsMap &Deps = SNs[0]->deps();59#endif // NDEBUG60 61 for (size_t I = 1; I != SNs.size(); ++I) {62 assert(!DepsMustMatch || SNs[I]->deps() == Deps);63 Result = merge(std::move(Result), SNs[I]->defs());64 }65 66 return Result;67 }68 69 EmitResult integrate(EmitResult ER) {70 for (auto &SN : ER.Ready)71 for (auto &[Container, Elems] : SN->defs())72 Ready[Container].insert(Elems.begin(), Elems.end());73 for (auto &SN : ER.Failed)74 for (auto &[Container, Elems] : SN->defs())75 Failed[Container].insert(Elems.begin(), Elems.end());76 return ER;77 }78 79 EmitResult emit(SimplifyResult SR) {80 return integrate(G.emit(std::move(SR), GetExternalState));81 }82 83 TestGraph G;84 ContainerElementsMap Ready;85 ContainerElementsMap Failed;86 87 class ExternalStateGetter {88 public:89 ExternalStateGetter(WaitingOnGraphTest &T) : T(T) {}90 TestGraph::ExternalState operator()(TestGraph::ContainerId C,91 TestGraph::ElementId E) {92 {93 auto I = T.Failed.find(C);94 if (I != T.Failed.end())95 if (I->second.count(E))96 return TestGraph::ExternalState::Failed;97 }98 99 {100 auto I = T.Ready.find(C);101 if (I != T.Ready.end())102 if (I->second.count(E))103 return TestGraph::ExternalState::Ready;104 }105 106 return TestGraph::ExternalState::None;107 }108 109 private:110 WaitingOnGraphTest &T;111 };112 113 ExternalStateGetter GetExternalState{*this};114};115 116} // namespace llvm::orc::detail117 118using namespace llvm;119using namespace llvm::orc;120using namespace llvm::orc::detail;121 122TEST_F(WaitingOnGraphTest, ConstructAndDestroyEmpty) {123 // Nothing to do here -- we're just testing construction and destruction124 // of the WaitingOnGraphTest::G member.125}126 127TEST_F(WaitingOnGraphTest, Build_TrivialSingleSuperNode) {128 // Add one set of trivial defs and empty deps to the builder, make sure that129 // they're passed through to the resulting super-node.130 SuperNodeBuilder B;131 ContainerElementsMap Defs({{0, {0}}});132 ContainerElementsMap Deps;133 B.add(Defs, Deps);134 auto SNs = B.takeSuperNodes();135 EXPECT_EQ(SNs.size(), 1U);136 EXPECT_EQ(getDefs(*SNs[0]), Defs);137 EXPECT_EQ(getDeps(*SNs[0]), Deps);138}139 140TEST_F(WaitingOnGraphTest, Build_EmptyDefs) {141 // Adding empty def sets is ok, but should not result in creation of a142 // SuperNode.143 SuperNodeBuilder B;144 ContainerElementsMap Empty;145 B.add(Empty, Empty);146 auto SNs = B.takeSuperNodes();147 EXPECT_TRUE(SNs.empty());148}149 150TEST_F(WaitingOnGraphTest, Build_NonTrivialSingleSuperNode) {151 // Add one non-trivwial set of defs and deps. Make sure that they're passed152 // through to the resulting super-node.153 SuperNodeBuilder B;154 ContainerElementsMap Defs({{0, {0, 1, 2}}});155 ContainerElementsMap Deps({{1, {3, 4, 5}}});156 B.add(Defs, Deps);157 auto SNs = B.takeSuperNodes();158 EXPECT_EQ(SNs.size(), 1U);159 EXPECT_EQ(getDefs(*SNs[0]), Defs);160 EXPECT_EQ(getDeps(*SNs[0]), Deps);161}162 163TEST_F(WaitingOnGraphTest, Build_CoalesceEmptyDeps) {164 // Add two trivial defs both with empty deps to the builder. Check that165 // they're coalesced into a single super-node.166 SuperNodeBuilder B;167 ContainerElementsMap Defs1({{0, {0}}});168 ContainerElementsMap Defs2({{0, {1}}});169 ContainerElementsMap Deps;170 B.add(Defs1, Deps);171 B.add(Defs2, Deps);172 auto SNs = B.takeSuperNodes();173 EXPECT_EQ(SNs.size(), 1U);174 EXPECT_EQ(getDefs(*SNs[0]), merge(Defs1, Defs2));175 EXPECT_EQ(getDeps(*SNs[0]), Deps);176}177 178TEST_F(WaitingOnGraphTest, Build_CoalesceNonEmptyDeps) {179 // Add two sets trivial of trivial defs with empty deps to the builder. Check180 // that the two coalesce into a single super node.181 SuperNodeBuilder B;182 ContainerElementsMap Defs1({{0, {0}}});183 ContainerElementsMap Defs2({{0, {1}}});184 ContainerElementsMap Deps({{1, {1}}});185 B.add(Defs1, Deps);186 B.add(Defs2, Deps);187 auto SNs = B.takeSuperNodes();188 EXPECT_EQ(SNs.size(), 1U);189 EXPECT_EQ(getDefs(*SNs[0]), merge(Defs1, Defs2));190 EXPECT_EQ(getDeps(*SNs[0]), Deps);191}192 193TEST_F(WaitingOnGraphTest, Build_CoalesceInterleaved) {194 // Add multiple sets of defs, some with the same dep sets. Check that nodes195 // are still coalesced as expected.196 SuperNodeBuilder B;197 198 ContainerElementsMap DefsA1({{0, {0}}});199 ContainerElementsMap DefsA2({{0, {1}}});200 ContainerElementsMap DefsB1({{1, {0}}});201 ContainerElementsMap DefsB2({{1, {1}}});202 ContainerElementsMap DepsA({{2, {0}}, {3, {0}}});203 ContainerElementsMap DepsB({{4, {0}}, {5, {0}}});204 B.add(DefsA1, DepsA);205 B.add(DefsB1, DepsB);206 B.add(DefsA2, DepsA);207 B.add(DefsB2, DepsB);208 auto SNs = B.takeSuperNodes();209 EXPECT_EQ(SNs.size(), 2U);210 EXPECT_EQ(getDefs(*SNs[0]), merge(DefsA1, DefsA2));211 EXPECT_EQ(getDeps(*SNs[0]), DepsA);212 EXPECT_EQ(getDefs(*SNs[1]), merge(DefsB1, DefsB2));213 EXPECT_EQ(getDeps(*SNs[1]), DepsB);214}215 216TEST_F(WaitingOnGraphTest, Build_SelfDepRemoval) {217 // Add multiple sets of defs, some with the same dep sets. Check that nodes218 // are still coalesced as expected.219 SuperNodeBuilder B;220 ContainerElementsMap Defs({{0, {0, 1}}});221 ContainerElementsMap Deps({{0, {1}}});222 ContainerElementsMap Empty;223 B.add(Defs, Deps);224 auto SNs = B.takeSuperNodes();225 EXPECT_EQ(SNs.size(), 1U);226 EXPECT_EQ(getDefs(*SNs[0]), Defs);227 EXPECT_EQ(getDeps(*SNs[0]), Empty);228}229 230TEST_F(WaitingOnGraphTest, Simplification_EmptySimplification) {231 auto SR = TestGraph::simplify({});232 auto &SNs = getSNs(SR);233 EXPECT_EQ(SNs.size(), 0U);234 EXPECT_EQ(getElemToSN(SR), ElemToSuperNodeMap());235}236 237TEST_F(WaitingOnGraphTest, Simplification_TrivialSingleSuperNode) {238 // Test trivial call to simplify.239 SuperNodeBuilder B;240 ContainerElementsMap Defs({{0, {0}}});241 ContainerElementsMap Deps({{0, {0}}});242 B.add(Defs, Deps);243 auto SR = TestGraph::simplify(B.takeSuperNodes());244 ContainerElementsMap Empty;245 246 // Check SNs.247 auto &SNs = getSNs(SR);248 EXPECT_EQ(SNs.size(), 1U);249 EXPECT_EQ(getDefs(*SNs.at(0)), Defs);250 EXPECT_EQ(getDeps(*SNs.at(0)), Empty);251 252 // Check ElemToSNs.253 ElemToSuperNodeMap ExpectedElemToSNs;254 ExpectedElemToSNs[0][0] = SNs[0].get();255 EXPECT_EQ(getElemToSN(SR), ExpectedElemToSNs);256}257 258TEST_F(WaitingOnGraphTest, Simplification_SimplifySingleContainerSimpleCycle) {259 // Test trivial simplification call with two nodes and one internal260 // dependence cycle within a single container:261 // N0: (0, 0) -> (0, 1)262 // N1: (0, 1) -> (0, 0)263 // We expect intra-simplify cycle elimination to clear both dependence sets,264 // and coalescing to join them into one supernode covering both defs.265 SuperNodeBuilder B;266 ContainerElementsMap Defs0({{0, {0}}});267 ContainerElementsMap Deps0({{0, {1}}});268 B.add(Defs0, Deps0);269 ContainerElementsMap Defs1({{0, {1}}});270 ContainerElementsMap Deps1({{0, {0}}});271 B.add(Defs1, Deps1);272 auto SR = TestGraph::simplify(B.takeSuperNodes());273 274 // Check SNs.275 auto &SNs = getSNs(SR);276 ContainerElementsMap Empty;277 EXPECT_EQ(SNs.size(), 1U);278 EXPECT_EQ(getDefs(*SNs.at(0)), merge(Defs0, Defs1));279 EXPECT_EQ(getDeps(*SNs.at(0)), Empty);280 281 // Check ElemToSNs.282 ElemToSuperNodeMap ExpectedElemToSNs;283 ExpectedElemToSNs[0][0] = SNs[0].get();284 ExpectedElemToSNs[0][1] = SNs[0].get();285 286 EXPECT_EQ(getElemToSN(SR), ExpectedElemToSNs);287}288 289TEST_F(WaitingOnGraphTest,290 Simplification_SimplifySingleContainerNElementCycle) {291 // Test trivial simplification call with M nodes and one internal292 // dependence cycle within a single container:293 // N0: (0, 0) -> (0, 1)294 // N1: (0, 1) -> (0, 2)295 // ...296 // NM: (0, M) -> (0, 0)297 // We expect intra-simplify cycle elimination to clear all dependence sets,298 // and coalescing to join them into one supernode covering all defs.299 SuperNodeBuilder B;300 constexpr size_t M = 10;301 for (size_t I = 0; I != M; ++I) {302 ContainerElementsMap Defs({{0, {I}}});303 ContainerElementsMap Deps({{0, {(I + 1) % M}}});304 B.add(Defs, Deps);305 }306 auto InitSNs = B.takeSuperNodes();307 EXPECT_EQ(InitSNs.size(), M);308 309 auto SR = TestGraph::simplify(std::move(InitSNs));310 311 // Check SNs.312 auto &SNs = getSNs(SR);313 ContainerElementsMap ExpectedDefs;314 for (size_t I = 0; I != M; ++I)315 ExpectedDefs[0].insert(I);316 ContainerElementsMap Empty;317 EXPECT_EQ(SNs.size(), 1U);318 EXPECT_EQ(getDefs(*SNs.at(0)), ExpectedDefs);319 EXPECT_EQ(getDeps(*SNs.at(0)), Empty);320 321 // Check ElemToSNs.322 ElemToSuperNodeMap ExpectedElemToSNs;323 for (size_t I = 0; I != M; ++I)324 ExpectedElemToSNs[0][I] = SNs[0].get();325 326 EXPECT_EQ(getElemToSN(SR), ExpectedElemToSNs);327}328 329TEST_F(WaitingOnGraphTest, Simplification_SimplifyIntraSimplifyPropagateDeps) {330 // Test trivial simplification call with two nodes and one internal331 // dependence cycle within a single container:332 // N0: (0, 0) -> (0, {1, 2})333 // N1: (0, 1) -> (0, {3})334 // We expect intra-simplify cycle elimination to replace the dependence of335 // (0, 0) on (0, 1) with a dependence on (0, 3) instead.336 SuperNodeBuilder B;337 ContainerElementsMap Defs0({{0, {0}}});338 ContainerElementsMap Deps0({{0, {1, 2}}});339 B.add(Defs0, Deps0);340 ContainerElementsMap Defs1({{0, {1}}});341 ContainerElementsMap Deps1({{0, {3}}});342 B.add(Defs1, Deps1);343 auto SR = TestGraph::simplify(B.takeSuperNodes());344 345 // Check SNs.346 auto &SNs = getSNs(SR);347 EXPECT_EQ(SNs.size(), 2U);348 349 // ContainerElemenstMap ExpectedDefs0({{0, {0}}});350 // ContainerElemenstMap ExpectedDeps0({{0, {1, 3}}});351 EXPECT_EQ(getDefs(*SNs.at(0)), ContainerElementsMap({{0, {0}}}));352 EXPECT_EQ(getDeps(*SNs.at(0)), ContainerElementsMap({{0, {2, 3}}}));353 354 EXPECT_EQ(getDefs(*SNs.at(1)), ContainerElementsMap({{0, {1}}}));355 EXPECT_EQ(getDeps(*SNs.at(1)), ContainerElementsMap({{0, {3}}}));356 357 // Check ElemToSNs.358 ElemToSuperNodeMap ExpectedElemToSNs;359 ExpectedElemToSNs[0][0] = SNs[0].get();360 ExpectedElemToSNs[0][1] = SNs[1].get();361 362 EXPECT_EQ(getElemToSN(SR), ExpectedElemToSNs);363}364 365TEST_F(WaitingOnGraphTest, Emit_EmptyEmit) {366 // Check that empty emits work as expected.367 auto ER = G.emit(TestGraph::simplify({}), GetExternalState);368 369 EXPECT_EQ(ER.Ready.size(), 0U);370 EXPECT_EQ(ER.Failed.size(), 0U);371}372 373TEST_F(WaitingOnGraphTest, Emit_TrivialSingleNode) {374 // Check that emitting a single node behaves as expected.375 SuperNodeBuilder B;376 ContainerElementsMap Defs({{0, {0}}});377 B.add(Defs, ContainerElementsMap());378 auto ER = emit(TestGraph::simplify(B.takeSuperNodes()));379 EXPECT_EQ(collapseDefs(ER.Ready), Defs);380 EXPECT_EQ(ER.Failed.size(), 0U);381}382 383TEST_F(WaitingOnGraphTest, Emit_TrivialSequence) {384 // Perform a sequence of two emits where the second emit depends on the385 // first. Check that nodes become ready after each emit.386 SuperNodeBuilder B;387 ContainerElementsMap Defs0({{0, {0}}});388 ContainerElementsMap Empty;389 B.add(Defs0, Empty);390 auto ER0 = emit(TestGraph::simplify(B.takeSuperNodes()));391 EXPECT_EQ(collapseDefs(ER0.Ready), Defs0);392 EXPECT_EQ(ER0.Failed.size(), 0U);393 394 ContainerElementsMap Defs1({{0, {1}}});395 ContainerElementsMap Deps1({{0, {0}}});396 B.add(Defs1, Deps1);397 auto ER1 = emit(TestGraph::simplify(B.takeSuperNodes()));398 EXPECT_EQ(collapseDefs(ER1.Ready), Defs1);399 EXPECT_EQ(ER1.Failed.size(), 0U);400}401 402TEST_F(WaitingOnGraphTest, Emit_SingleContainerSimpleCycle) {403 // Test an emit of two nodes with a dependence cycle within a single404 // container:405 // N0: (0, 0) -> (0, 1)406 // N1: (0, 1) -> (0, 0)407 // We expect intra-simplify cycle elimination to clear both dependence sets,408 // and coalescing to join them into one supernode covering both defs.409 SuperNodeBuilder B;410 ContainerElementsMap Defs0({{0, {0}}});411 ContainerElementsMap Deps0({{0, {1}}});412 B.add(Defs0, Deps0);413 414 auto ER0 = emit(TestGraph::simplify(B.takeSuperNodes()));415 EXPECT_EQ(ER0.Ready.size(), 0U);416 EXPECT_EQ(ER0.Failed.size(), 0U);417 418 ContainerElementsMap Defs1({{0, {1}}});419 ContainerElementsMap Deps1({{0, {0}}});420 B.add(Defs1, Deps1);421 auto ER1 = emit(TestGraph::simplify(B.takeSuperNodes()));422 423 EXPECT_EQ(collapseDefs(ER1.Ready), merge(Defs0, Defs1));424 EXPECT_EQ(ER1.Failed.size(), 0U);425}426 427TEST_F(WaitingOnGraphTest, Emit_TrivialReverseSequence) {428 // Perform a sequence of two emits where the first emit depends on the429 // second. Check that both nodes become ready after the second emit.430 SuperNodeBuilder B;431 ContainerElementsMap Defs0({{0, {0}}});432 ContainerElementsMap Deps0({{0, {1}}});433 B.add(Defs0, Deps0);434 auto ER0 = emit(TestGraph::simplify(B.takeSuperNodes()));435 EXPECT_EQ(ER0.Ready.size(), 0U);436 EXPECT_EQ(ER0.Failed.size(), 0U);437 438 ContainerElementsMap Defs1({{0, {1}}});439 ContainerElementsMap Empty;440 B.add(Defs1, Empty);441 auto ER1 = emit(TestGraph::simplify(B.takeSuperNodes()));442 EXPECT_EQ(collapseDefs(ER1.Ready), merge(Defs0, Defs1));443 EXPECT_EQ(ER1.Failed.size(), 0U);444}445 446TEST_F(WaitingOnGraphTest, Emit_Coalescing) {447 SuperNodeBuilder B;448 ContainerElementsMap Defs0({{0, {0}}});449 ContainerElementsMap Deps0({{1, {0}}});450 B.add(Defs0, Deps0);451 auto ER0 = emit(TestGraph::simplify(B.takeSuperNodes()));452 EXPECT_EQ(ER0.Ready.size(), 0U);453 EXPECT_EQ(ER0.Failed.size(), 0U);454 455 ContainerElementsMap Defs1({{0, {1}}});456 ContainerElementsMap Deps1({{1, {0}}});457 B.add(Defs1, Deps1);458 auto ER1 = emit(TestGraph::simplify(B.takeSuperNodes()));459 EXPECT_EQ(ER1.Ready.size(), 0U);460 EXPECT_EQ(ER1.Failed.size(), 0U);461 462 // Check that after emitting two nodes with the same dep set we have only one463 // pending supernode whose defs are the union of the defs in the two emits.464 auto &PendingSNs = getPendingSNs(G);465 EXPECT_EQ(PendingSNs.size(), 1U);466 EXPECT_EQ(getDefs(*PendingSNs.at(0)), merge(Defs0, Defs1));467 468 ContainerElementsMap Defs2({{1, {0}}});469 ContainerElementsMap Empty;470 B.add(Defs2, Empty);471 auto ER2 = emit(TestGraph::simplify(B.takeSuperNodes()));472 EXPECT_EQ(collapseDefs(ER2.Ready), merge(merge(Defs0, Defs1), Defs2));473 EXPECT_EQ(ER2.Failed.size(), 0U);474}475 476TEST_F(WaitingOnGraphTest, Emit_ZigZag) {477 // Perform a sequence of four emits, where the first three contain a zig-zag478 // pattern:479 // 1. (0, 0) -> (0, 1)480 // 2. (0, 2) -> (0, 3)481 // ^ -- At this point we expect two pending supernodes.482 // 3. (0, 1) -> (0, 2)483 // ^ -- Resolution of (0, 1) should cause all three emitted nodes to coalsce484 // into one supernode defining (0, {1, 2, 3}).485 // 4. (0, 3)486 // ^ -- Should cause all four nodes to become ready.487 488 SuperNodeBuilder B;489 ContainerElementsMap Defs0({{0, {0}}});490 ContainerElementsMap Deps0({{0, {1}}});491 B.add(Defs0, Deps0);492 auto ER0 = emit(TestGraph::simplify(B.takeSuperNodes()));493 EXPECT_EQ(ER0.Ready.size(), 0U);494 EXPECT_EQ(ER0.Failed.size(), 0U);495 496 ContainerElementsMap Defs1({{0, {2}}});497 ContainerElementsMap Deps1({{0, {3}}});498 B.add(Defs1, Deps1);499 auto ER1 = emit(TestGraph::simplify(B.takeSuperNodes()));500 EXPECT_EQ(ER1.Ready.size(), 0U);501 EXPECT_EQ(ER1.Failed.size(), 0U);502 503 // Check that after emitting two nodes with the same dep set we have only one504 // pending supernode whose defs are the union of the defs in the two emits.505 auto &PendingSNs = getPendingSNs(G);506 EXPECT_EQ(PendingSNs.size(), 2U);507 EXPECT_EQ(getDefs(*PendingSNs.at(0)), Defs0);508 EXPECT_EQ(getDeps(*PendingSNs.at(0)), Deps0);509 EXPECT_EQ(getDefs(*PendingSNs.at(1)), Defs1);510 EXPECT_EQ(getDeps(*PendingSNs.at(1)), Deps1);511 512 ContainerElementsMap Defs2({{0, {1}}});513 ContainerElementsMap Deps2({{0, {2}}});514 B.add(Defs2, Deps2);515 auto ER2 = emit(TestGraph::simplify(B.takeSuperNodes()));516 EXPECT_EQ(ER2.Ready.size(), 0U);517 EXPECT_EQ(ER2.Failed.size(), 0U);518 519 // Check that after emitting the third node we've coalesced all three.520 EXPECT_EQ(PendingSNs.size(), 1U);521 EXPECT_EQ(getDefs(*PendingSNs.at(0)), merge(merge(Defs0, Defs1), Defs2));522 EXPECT_EQ(getDeps(*PendingSNs.at(0)), Deps1);523 524 ContainerElementsMap Defs3({{0, {3}}});525 ContainerElementsMap Empty;526 B.add(Defs3, Empty);527 auto ER3 = emit(TestGraph::simplify(B.takeSuperNodes()));528 529 EXPECT_EQ(collapseDefs(ER3.Ready),530 merge(merge(merge(Defs0, Defs1), Defs2), Defs3));531 EXPECT_EQ(ER2.Failed.size(), 0U);532 EXPECT_TRUE(PendingSNs.empty());533}534 535TEST_F(WaitingOnGraphTest, Emit_ReEmit) {536 // Test for the bug in https://github.com/llvm/llvm-project/issues/169135,537 // which was caused by stale entries in the ElemsToPendingSNs map.538 //539 // To trigger the bug we need to:540 // 1. Create a SuperNode with an unmet dependence, causing it to be added to541 // ElemsToPendingSNs.542 // 2. Cause that SuperNode to become ready (bug left stale entries in map)543 // 3. Remove the node from the Ready map (this is equivalent to removal of a544 // symbol in an ORC session, and allows new SuperNodes to depend on the545 // stale entry).546 // 4. Add a new node that references the previously emitted/removed SuperNode547 // This triggers access of the stale entry, and should error out in548 // sanitizer builds.549 550 SuperNodeBuilder B;551 552 // 1. Create SuperNode with unmet dependence.553 ContainerElementsMap Defs0({{0, {0}}});554 ContainerElementsMap Deps0({{0, {1}}});555 B.add(Defs0, Deps0);556 emit(TestGraph::simplify(B.takeSuperNodes()));557 558 EXPECT_TRUE(Ready.empty());559 560 // 2. Cause previous SuperNode to become ready.561 ContainerElementsMap Defs1({{0, {1}}});562 B.add(Defs1, ContainerElementsMap());563 emit(TestGraph::simplify(B.takeSuperNodes()));564 565 // Check that both nodes have become ready.566 EXPECT_EQ(Ready, merge(Defs0, Defs1));567 568 // 3. Erase Ready nodes to simulate removal from the graph.569 Ready.clear();570 571 // 4. Emit a new dependence on the original def.572 ContainerElementsMap Defs2({{0, {2}}});573 ContainerElementsMap Deps2({{0, {0}}});574 B.add(Defs2, Deps2);575 auto ER = emit(TestGraph::simplify(B.takeSuperNodes()));576 577 // We expect the new dependence to remain pending.578 EXPECT_TRUE(ER.Ready.empty());579}580 581TEST_F(WaitingOnGraphTest, Fail_Empty) {582 // Check that failing an empty set is a no-op.583 auto FR = G.fail(ContainerElementsMap());584 EXPECT_EQ(FR.size(), 0U);585}586 587TEST_F(WaitingOnGraphTest, Fail_Single) {588 // Check that failing a set with no existing dependencies works.589 auto FR = G.fail({{0, {0}}});590 EXPECT_EQ(FR.size(), 0U);591}592 593TEST_F(WaitingOnGraphTest, Fail_EmitDependenceOnFailure) {594 // Check that emitted nodes that directly depend on failed nodes also fail.595 Failed = {{0, {0}}};596 597 SuperNodeBuilder B;598 ContainerElementsMap Defs({{0, {1}}});599 ContainerElementsMap Deps({{0, {0}}});600 B.add(Defs, Deps);601 auto ER = emit(TestGraph::simplify(B.takeSuperNodes()));602 EXPECT_EQ(ER.Ready.size(), 0U);603 EXPECT_EQ(collapseDefs(ER.Failed, false), Defs);604}605 606TEST_F(WaitingOnGraphTest, Fail_ZigZag) {607 // Check that if an emit introduces a transitive dependence of a failed608 // node, then all nodes that depend on the failed node are also failed.609 SuperNodeBuilder B;610 611 ContainerElementsMap Defs0({{0, {0}}});612 ContainerElementsMap Deps0({{0, {1}}});613 B.add(Defs0, Deps0);614 auto ER0 = emit(TestGraph::simplify(B.takeSuperNodes()));615 EXPECT_EQ(ER0.Ready.size(), 0U);616 EXPECT_EQ(ER0.Failed.size(), 0U);617 618 Failed = {{0, {2}}};619 620 ContainerElementsMap Defs1({{0, {1}}});621 ContainerElementsMap Deps1({{0, {2}}});622 B.add(Defs1, Deps1);623 auto ER1 = emit(TestGraph::simplify(B.takeSuperNodes()));624 EXPECT_EQ(ER1.Ready.size(), 0U);625 EXPECT_EQ(collapseDefs(ER1.Failed, false), merge(Defs0, Defs1));626}627