CGRA-ME
OpGraphProcedures_tests.cpp
Go to the documentation of this file.
1 /*******************************************************************************
2  * The software programs comprising "CGRA-ME" and the documentation provided
3  * with them are copyright by its authors and the University of Toronto. Only
4  * non-commercial, not-for-profit use of this software is permitted without ex-
5  * plicit permission. This software is provided "as is" with no warranties or
6  * guarantees of support. See the LICENCE for more details. You should have re-
7  * ceived a copy of the full licence along with this software. If not, see
8  * <http://cgra-me.ece.utoronto.ca/license/>.
9  ******************************************************************************/
10 
11 #include <CGRA/OpGraphProcedures.h>
12 
13 #include "testutils/OpGraphsForTesting.hpp"
14 
15 #include <catch2/catch.hpp>
16 
17 namespace {
18 
19 struct removeBranchComputation_TestCase {
20  std::string graph_name;
21  OpGraph input;
22  std::vector<std::string> expected_nodes_removed;
23 };
24 
25 } // end anon namespace
26 
27 TEST_CASE("removeBranchComputation Tests", "") {
28  const auto test = GENERATE(values<removeBranchComputation_TestCase>({
29  { "should remove a2 too",
30  []{ // (immediately invoked)
31  OpGraph og = makeDFG_CrossbarWithBranchComp();
32  return og;
33  }(),
34  { "b1", "a2" },
35  },
36  { "should have no effect",
37  []{ // (immediately invoked)
38  OpGraph og = makeDFG_CrossbarWithBranchComp();
39  og.erase(og.getOp("b1")); // remove the only br
40  return og;
41  }(),
42  {},
43  },
44  { "remove everything",
45  []{ // (immediately invoked)
46  OpGraph og = makeDFG_CrossbarWithBranchComp();
47  og.erase(og.getOp("o1"));
48  og.erase(og.getOp("a1"));
49  return og;
50  }(),
51  { "b1", "a2", "i1", "i2" },
52  },
53  { "only remove b1",
54  []{ // (immediately invoked)
55  OpGraph og = makeDFG_CrossbarWithBranchComp();
56  og.insert(og.getOp("a2"), {"o2", 32, OpCode::OUTPUT}, "");
57  return og;
58  }(),
59  { "b1" },
60  },
61  }));
62 
63  GIVEN("A '" << test.graph_name << "' OpGraph") {
64  WHEN("Removing branch computation") {
65  const auto after = removeBranchComputation(test.input);
66  THEN("The right nodes should have been removed") {
67  auto manually_modified_input = test.input;
68  for (const auto op_name : test.expected_nodes_removed) {
69  manually_modified_input.erase(manually_modified_input.getOp(op_name));
70  }
71  CHECK(manually_modified_input == after);
72  }
73  }
74  }
75 }
76 
77 namespace {
78 
79 struct removePhiNodes_TestCase {
80  std::string graph_name;
81  OpGraph input;
82  OpGraph expected;
83 };
84 
85 } // end anon namespace
86 
87 TEST_CASE("removePhiNodes Tests", "") {
88  const auto test = GENERATE(values<removePhiNodes_TestCase>({
89  { "becomes a self-loop -- constants",
90  []{ // (immediately invoked)
91  OpGraph og;
92  const auto c1 = og.emplace("c1", 32, OpCode::CONST, 1);
93  const auto p1 = og.emplace("p1", 32, OpCode::PHI);
94  const auto c2 = og.emplace("c2", 32, OpCode::CONST, 2);
95  const auto a1 = og.emplace("a1", 32, OpCode::ADD);
96  og.link(c1, p1, "");
97  og.link(c2, a1, Operands::BINARY_RHS);
98  og.link(p1, a1, Operands::BINARY_LHS);
99  og.link(a1, p1, "");
100  return og;
101  }(),
102  []{ // (immediately invoked)
103  OpGraph og;
104  const auto c2 = og.emplace("c2", 32, OpCode::CONST, 2);
105  const auto a1 = og.emplace("a1", 32, OpCode::ADD);
106  og.link(c2, a1, Operands::BINARY_RHS);
107  og.link(a1, a1, Operands::BINARY_LHS);
108  return og;
109  }(),
110  },
111  { "becomes a self-loop -- inputs",
112  []{ // (immediately invoked)
113  OpGraph og;
114  const auto i1 = og.emplace("i1", 32, OpCode::INPUT);
115  const auto p1 = og.emplace("p1", 32, OpCode::PHI);
116  const auto i2 = og.emplace("i2", 32, OpCode::INPUT);
117  const auto a1 = og.emplace("a1", 32, OpCode::ADD);
118  og.link(i1, p1, "");
119  og.link(i2, a1, Operands::BINARY_RHS);
120  og.link(p1, a1, Operands::BINARY_LHS);
121  og.link(a1, p1, "");
122  return og;
123  }(),
124  []{ // (immediately invoked)
125  OpGraph og;
126  const auto i2 = og.emplace("i2", 32, OpCode::INPUT);
127  const auto a1 = og.emplace("a1", 32, OpCode::ADD);
128  og.link(i2, a1, Operands::BINARY_RHS);
129  og.link(a1, a1, Operands::BINARY_LHS);
130  return og;
131  }(),
132  },
133  { "phi-to-phi",
134  []{ // (immediately invoked)
135  OpGraph og;
136  const auto i1 = og.emplace("i1", 32, OpCode::INPUT);
137  const auto c1 = og.emplace("c1", 32, OpCode::CONST, 1);
138  const auto c2 = og.emplace("c2", 32, OpCode::CONST, 2);
139  const auto p1 = og.emplace("p1", 32, OpCode::PHI);
140  const auto p2 = og.emplace("p2", 32, OpCode::PHI);
141  const auto a1 = og.emplace("a1", 32, OpCode::ADD);
142  const auto a2 = og.emplace("a2", 32, OpCode::ADD);
143  og.link(i1, p1, "");
144  og.link(p1, a1, Operands::BINARY_LHS);
145  og.link(c1, a1, Operands::BINARY_RHS);
146  og.link(p1, p2, "");
147  og.link(c2, p2, "");
148  og.link(a1, a2, Operands::BINARY_RHS);
149  og.link(p2, a2, Operands::BINARY_LHS);
150  og.link(a2, p1, "");
151  return og;
152  }(),
153  []{ // (immediately invoked)
154  OpGraph og;
155  const auto c1 = og.emplace("c1", 32, OpCode::CONST, 1);
156  const auto a1 = og.emplace("a1", 32, OpCode::ADD);
157  const auto a2 = og.emplace("a2", 32, OpCode::ADD);
158  og.link(a2, a1, Operands::BINARY_LHS);
159  og.link(c1, a1, Operands::BINARY_RHS);
160  og.link(a2, a2, Operands::BINARY_LHS);
161  og.link(a1, a2, Operands::BINARY_RHS);
162  return og;
163  }(),
164  },
165  { "phis with shared external input",
166  []{ // (immediately invoked)
167  OpGraph og;
168  const auto i1 = og.emplace("i1", 32, OpCode::INPUT);
169  const auto c1 = og.emplace("c1", 32, OpCode::CONST, 1);
170  const auto c2 = og.emplace("c2", 32, OpCode::CONST, 2);
171  const auto p1 = og.emplace("p1", 32, OpCode::PHI);
172  const auto p2 = og.emplace("p2", 32, OpCode::PHI);
173  const auto a1 = og.emplace("a1", 32, OpCode::ADD);
174  const auto a2 = og.emplace("a2", 32, OpCode::ADD);
175  og.link(i1, p1, "");
176  og.link(i1, p2, "");
177  og.link(p1, a1, Operands::BINARY_LHS);
178  og.link(c1, a1, Operands::BINARY_RHS);
179  og.link(a1, p1, "");
180  og.link(c2, a2, Operands::BINARY_RHS);
181  og.link(p2, a2, Operands::BINARY_LHS);
182  og.link(a2, p2, "");
183  return og;
184  }(),
185  []{ // (immediately invoked)
186  OpGraph og;
187  const auto c1 = og.emplace("c1", 32, OpCode::CONST, 1);
188  const auto c2 = og.emplace("c2", 32, OpCode::CONST, 2);
189  const auto a1 = og.emplace("a1", 32, OpCode::ADD);
190  const auto a2 = og.emplace("a2", 32, OpCode::ADD);
191  og.link(a1, a1, Operands::BINARY_LHS);
192  og.link(c1, a1, Operands::BINARY_RHS);
193  og.link(a2, a2, Operands::BINARY_LHS);
194  og.link(c2, a2, Operands::BINARY_RHS);
195  return og;
196  }(),
197  },
198  }));
199 
200  GIVEN("A '" << test.graph_name << "' OpGraph") {
201  WHEN("Removing phi nodes") {
202  const auto after = removePhiNodes(test.input);
203  THEN("The resulting graph should be as expected") {
204  CHECK(test.expected == after);
205  }
206  }
207  }
208 }
OpCode::CONST
@ CONST
OpCode::PHI
@ PHI
removeBranchComputation
OpGraph removeBranchComputation(OpGraph opgraph)
Definition: OpGraphProcedures.cpp:305
OpGraphProcedures.h
Operands::BINARY_LHS
static constexpr auto & BINARY_LHS
Definition: OpGraph.h:89
removePhiNodes
OpGraph removePhiNodes(OpGraph opgraph)
Definition: OpGraphProcedures.cpp:334
OpGraph::getOp
OpDescriptor getOp(const std::string &name) const
Definition: OpGraph.h:386
OpCode::ADD
@ ADD
Operands::BINARY_RHS
static constexpr auto & BINARY_RHS
Definition: OpGraph.h:90
TEST_CASE
TEST_CASE("removeBranchComputation Tests", "")
Definition: OpGraphProcedures_tests.cpp:27
OpCode::INPUT
@ INPUT
OpGraph::link
ValDescriptor link(OpDescriptor driver, OpDescriptor fanout, std::string operand_group, int bitwidth=32, int dist=0, EdgeKind kind=EdgeKind::kDataFlow, bool predicate=false)
Definition: OpGraph.cpp:364
OpGraphsForTesting.hpp
OpGraph::insert
OpDescriptor insert(OpGraphOp op)
Definition: OpGraph.cpp:338
OpGraph::emplace
OpDescriptor emplace(Args &&... args)
Definition: OpGraph.h:263
makeDFG_CrossbarWithBranchComp
OpGraph makeDFG_CrossbarWithBranchComp()
Definition: OpGraphsForTesting.cpp:251
OpGraph::erase
void erase(OpDescriptor op)
Definition: OpGraph.cpp:453
OpGraph
Definition: OpGraph.h:215
Generated on Fri Nov 17 2023 12:26:44 for CGRA-ME by   doxygen 1.8.17