celerity-runtime/test/intrusive_graph_tests.cc at master · celerity/celerity-runtime · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <catch2/catch_test_macros.hpp>

#include "intrusive_graph.h"

namespace celerity {
namespace detail {

	struct my_graph_node : intrusive_graph_node<my_graph_node> {};

	TEST_CASE("intrusive_graph_node correctly handles adding and removing of", "[intrusive_graph_node]") {
		SECTION("true dependencies") {
			// Adding and removing true dependency
			{
				my_graph_node n0, n1;
				n0.add_dependency({&n1, dependency_kind::true_dep, dependency_origin::dataflow});
				REQUIRE(n0.has_dependency(&n1, dependency_kind::true_dep));
				REQUIRE(n1.has_dependent(&n0, dependency_kind::true_dep));
				n0.remove_dependency(&n1);
				REQUIRE_FALSE(n0.has_dependency(&n1));
				REQUIRE_FALSE(n1.has_dependent(&n0));
			}
			// Pseudo- or anti-dependency is upgraded to true dependency
			{
				my_graph_node n0, n1, n2;
				n0.add_dependency({&n1, dependency_kind::anti_dep, dependency_origin::dataflow});
				n0.add_dependency({&n2, dependency_kind::true_dep, dependency_origin::dataflow});
				CHECK(n0.has_dependency(&n1, dependency_kind::anti_dep));
				CHECK(n1.has_dependent(&n0, dependency_kind::anti_dep));
				n0.add_dependency({&n1, dependency_kind::true_dep, dependency_origin::dataflow});
				n0.add_dependency({&n2, dependency_kind::anti_dep, dependency_origin::dataflow});
				REQUIRE_FALSE(n0.has_dependency(&n1, dependency_kind::anti_dep));
				REQUIRE_FALSE(n1.has_dependent(&n0, dependency_kind::anti_dep));
				REQUIRE(n0.has_dependency(&n1, dependency_kind::true_dep));
				REQUIRE(n1.has_dependent(&n0, dependency_kind::true_dep));
				REQUIRE_FALSE(n0.has_dependency(&n2, dependency_kind::anti_dep));
				REQUIRE_FALSE(n2.has_dependent(&n0, dependency_kind::anti_dep));
			}
		}

		SECTION("anti-dependencies") {
			// True dependency cannot be downgraded to anti-dependency
			{
				my_graph_node n0, n1;
				n0.add_dependency({&n1, dependency_kind::true_dep, dependency_origin::dataflow});
				CHECK(n0.has_dependency(&n1, dependency_kind::true_dep));
				CHECK(n1.has_dependent(&n0, dependency_kind::true_dep));
				n0.add_dependency({&n1, dependency_kind::anti_dep, dependency_origin::dataflow});
				REQUIRE_FALSE(n0.has_dependency(&n1, dependency_kind::anti_dep));
				REQUIRE_FALSE(n1.has_dependent(&n0, dependency_kind::anti_dep));
				REQUIRE(n0.has_dependency(&n1, dependency_kind::true_dep));
				REQUIRE(n1.has_dependent(&n0, dependency_kind::true_dep));
				n0.add_dependency({&n1, dependency_kind::true_dep, dependency_origin::dataflow});
				REQUIRE_FALSE(n0.has_dependency(&n1, dependency_kind::anti_dep));
				REQUIRE_FALSE(n1.has_dependent(&n0, dependency_kind::anti_dep));
				REQUIRE(n0.has_dependency(&n1, dependency_kind::true_dep));
				REQUIRE(n1.has_dependent(&n0, dependency_kind::true_dep));
			}
		}
	}

	TEST_CASE("intrusive_graph_node removes itself from all connected nodes upon destruction", "[intrusive_graph_node]") {
		my_graph_node n0, n2;
		auto n1 = std::make_unique<my_graph_node>();
		n0.add_dependency({n1.get(), dependency_kind::true_dep, dependency_origin::dataflow});
		n1->add_dependency({&n2, dependency_kind::true_dep, dependency_origin::dataflow});
		CHECK(n0.has_dependency(n1.get(), dependency_kind::true_dep));
		CHECK(n2.has_dependent(n1.get(), dependency_kind::true_dep));
		n1.reset();
		REQUIRE(std::distance(n0.get_dependencies().begin(), n0.get_dependencies().end()) == 0);
		REQUIRE(std::distance(n2.get_dependents().begin(), n2.get_dependents().end()) == 0);
	}

	TEST_CASE("intrusive_graph_node keeps track of the pseudo critical path length", "[intrusive_graph_node]") {
		my_graph_node n0, n1, n2, n3;
		REQUIRE(n3.get_pseudo_critical_path_length() == 0);
		n3.add_dependency({&n2, dependency_kind::true_dep, dependency_origin::dataflow});
		REQUIRE(n3.get_pseudo_critical_path_length() == 1);
		n3.add_dependency({&n0, dependency_kind::true_dep, dependency_origin::dataflow});
		REQUIRE(n3.get_pseudo_critical_path_length() == 1);
		n1.add_dependency({&n0, dependency_kind::true_dep, dependency_origin::dataflow});
		n3.add_dependency({&n1, dependency_kind::true_dep, dependency_origin::dataflow});
		REQUIRE(n3.get_pseudo_critical_path_length() == 2);
	}

} // namespace detail
} // namespace celerity