OpGraph_tests.cpp

Go to the documentation of this file.

/*******************************************************************************
 * The software programs comprising "CGRA-ME" and the documentation provided
 * with them are copyright by its authors and the University of Toronto. Only
 * non-commercial, not-for-profit use of this software is permitted without ex-
 * plicit permission. This software is provided "as is" with no warranties or
 * guarantees of support. See the LICENCE for more details. You should have re-
 * ceived a copy of the full licence along with this software. If not, see
 * <http://cgra-me.ece.utoronto.ca/license/>.
 ******************************************************************************/
 
#include <CGRA/OpGraph.h>
 
#include "testutils/OpGraphsForTesting.hpp"
#include <catch2/catch.hpp>
 
void then_verify_should_pass(const OpGraph& opgraph) {
    THEN("OpGraph::verify should pass") {
        CHECK(verifyAndPrintReport(opgraph, std::cout, true, false));
    }
}
 
SCENARIO ("removing nodes and links from OpGraphs", "") {
    GIVEN("A linear 3-node DFG") {
        auto opgraph = makeDFG_Linear3Node();
        WHEN("Removing a link") {
            const auto target_op = opgraph.getOp("op_b");
            opgraph.unLink(opgraph.outputVal(target_op), opgraph.fanout(target_op).at(0));
            then_verify_should_pass(opgraph);
        }
        WHEN("Removing an internal node") {
            opgraph.erase(opgraph.getOp("op_b"));
            then_verify_should_pass(opgraph);
        }
        WHEN("Removing a inpupt node") {
            opgraph.erase(opgraph.getOp("op_a"));
            then_verify_should_pass(opgraph);
        }
        WHEN("Removing a output node") {
            opgraph.erase(opgraph.getOp("op_c"));
            then_verify_should_pass(opgraph);
        }
    }
 
    GIVEN("A self loop 3-node DFG") {
        auto opgraph = makeDFG_SelfLoop3Node();
        WHEN("Removing a link") {
            const auto target_op = opgraph.getOp("op_l");
            opgraph.unLink(opgraph.outputVal(target_op), opgraph.fanout(target_op).at(0));
            then_verify_should_pass(opgraph);
        }
        WHEN("Removing an internal node") {
            opgraph.erase(opgraph.getOp("op_l"));
            then_verify_should_pass(opgraph);
        }
        WHEN("Removing a inpupt node") {
            opgraph.erase(opgraph.getOp("op_a"));
            then_verify_should_pass(opgraph);
        }
        WHEN("Removing a output node") {
            opgraph.erase(opgraph.getOp("op_c"));
            then_verify_should_pass(opgraph);
        }
    }
 
    GIVEN("A loop 4-node DFG") {
        auto opgraph = makeDFG_2NodeLoop4Node();
        WHEN("Removing a link") {
            const auto target_op = opgraph.getOp("op_l");
            opgraph.unLink(opgraph.outputVal(target_op), opgraph.fanout(target_op).at(0));
            then_verify_should_pass(opgraph);
        }
        WHEN("Removing an internal node") {
            opgraph.erase(opgraph.getOp("op_l"));
            then_verify_should_pass(opgraph);
        }
        WHEN("Removing a inpupt node") {
            opgraph.erase(opgraph.getOp("op_a"));
            then_verify_should_pass(opgraph);
        }
        WHEN("Removing a output node") {
            opgraph.erase(opgraph.getOp("op_d"));
            then_verify_should_pass(opgraph);
        }
    }
 
    GIVEN("A Tree 112 DFG") {
        auto opgraph = makeDFG_Tree112();
        WHEN("Removing a link") {
            const auto target_op = opgraph.getOp("op_b");
            opgraph.unLink(opgraph.outputVal(target_op), opgraph.fanout(target_op).at(0));
            then_verify_should_pass(opgraph);
        }
        WHEN("Removing an internal node") {
            opgraph.erase(opgraph.getOp("op_b"));
            then_verify_should_pass(opgraph);
        }
        WHEN("Removing a inpupt node") {
            opgraph.erase(opgraph.getOp("op_a"));
            then_verify_should_pass(opgraph);
        }
        WHEN("Removing a output node") {
            opgraph.erase(opgraph.getOp("op_c"));
            then_verify_should_pass(opgraph);
        }
    }
 
    GIVEN("A Converging 121 DFG") {
        auto opgraph = makeDFG_Converging121();
        WHEN("Removing a link") {
            const auto target_op = opgraph.getOp("op_a");
            opgraph.unLink(opgraph.outputVal(target_op), opgraph.fanout(target_op).at(0));
            then_verify_should_pass(opgraph);
        }
        WHEN("Removing an internal node") {
            opgraph.erase(opgraph.getOp("op_a"));
            then_verify_should_pass(opgraph);
        }
        WHEN("Removing a inpupt node") {
            opgraph.erase(opgraph.getOp("op_a"));
            then_verify_should_pass(opgraph);
        }
        WHEN("Removing a output node") {
            opgraph.erase(opgraph.getOp("op_c"));
            then_verify_should_pass(opgraph);
        }
    }
}
 
TEST_CASE("OpGraphOpCode to and from Strings") {
    GIVEN("An opcode") {
        const auto expected_opcode = GENERATE(values<OpGraphOpCode>({
            OpCode::NOP,
            OpCode::SEXT,
            OpCode::ZEXT,
            OpCode::TRUNC,
            OpCode::INPUT,
            OpCode::OUTPUT,
            OpCode::PHI,
            OpCode::CONST,
            OpCode::ADD,
            OpCode::SUB,
            OpCode::MUL,
            OpCode::DIV,
            OpCode::AND,
            OpCode::OR,
            OpCode::XOR,
            OpCode::SHL,
            OpCode::ASHR,
            OpCode::LSHR,
            OpCode::LOAD,
            OpCode::STORE,
            OpCode::GEP,
            OpCode::ICMP,
            OpCode::BR,
        }));
 
        THEN("Converting it to a string should work") {
            const auto as_str = to_string(expected_opcode);
            AND_THEN("Converting back to an opcode should give the same thing") {
                const auto actual_opcode = opcode_from_string(as_str);
                CHECK(actual_opcode == expected_opcode);
            }
        }
    }
 
    GIVEN("A bogus string") {
        THEN("to_string should throw") {
            REQUIRE_THROWS(opcode_from_string("aoeuidhtns"));
        }
    }
}
 
TEST_CASE("OpGraph Equality and Copying Tests") {
    std::map<std::string, std::function<OpGraph(ConfigStore)>> og_generators {
        {"a;",[](ConfigStore params) {
            OpGraph og;
            og.insert({params.getString("name_a"), 32, opcode_from_string(params.getStringOr("op_a","add"))});
            return finalFixup(std::move(og));
        }},
        {"a;b",[](ConfigStore params) {
            OpGraph og;
            og.insert({params.getString("name_a"), 32, opcode_from_string(params.getStringOr("op_a","add"))});
            og.insert({params.getString("name_b"), 32, opcode_from_string(params.getStringOr("op_a","add"))});
            return finalFixup(std::move(og));
        }},
        {"a->b",[](ConfigStore params) {
            OpGraph og;
            const auto a = og.insert({params.getString("name_a"), 32, opcode_from_string(params.getStringOr("op_a","add"))});
            og.insert(a, {params.getString("name_b"), 32, opcode_from_string(params.getStringOr("op_b","add"))}, params.getString("ab_oper"));
            return finalFixup(std::move(og));
        }},
        {"a->b with b erased",[](ConfigStore params) {
            OpGraph og;
            const auto a = og.insert({params.getString("name_a"), 32, opcode_from_string(params.getStringOr("op_a","add"))});
            const auto b = og.insert(a, {params.getString("name_b"), 32, opcode_from_string(params.getStringOr("op_b","add"))}, params.getString("ab_oper")).newOp;
            og.erase(b);
            return finalFixup(std::move(og));
        }},
        {"a->{b c}",[](ConfigStore params) {
            OpGraph og;
            const auto a = og.insert({params.getString("name_a"), 32, opcode_from_string(params.getStringOr("op_a","add"))});
            og.insert(a, {params.getString("name_b"), 32, opcode_from_string(params.getStringOr("op_b","add"))}, params.getString("ab_oper"));
            og.insert(a, {params.getString("name_c"), 32, opcode_from_string(params.getStringOr("op_c","add"))}, params.getString("ac_oper"));
            return finalFixup(std::move(og));
        }},
        {"a->{b c} with c erased",[](ConfigStore params) {
            OpGraph og;
            const auto a = og.insert({params.getString("name_a"), 32, opcode_from_string(params.getStringOr("op_a","add"))});
            og.insert(a, {params.getString("name_b"), 32, opcode_from_string(params.getStringOr("op_b","add"))}, params.getString("ab_oper"));
            const auto c = og.insert(a, {params.getString("name_c"), 32, opcode_from_string(params.getStringOr("op_c","add"))}, params.getString("ac_oper")).newOp;
            og.erase(c);
            return finalFixup(std::move(og));
        }},
        {"const_a;",[](ConfigStore params) {
            OpGraph og;
            og.insert({params.getString("name_a"), 32, opcode_from_string(params.getStringOr("op_const","const")), (unsigned)params.getInt("constVal")});
            return finalFixup(std::move(og));
        }},
    };
 
    struct OpGraphEqualityTest {
        std::string test_description;
        bool expect_to_be_same;
        OpGraph graph1;
        OpGraph graph2;
    };
 
    const OpGraphEqualityTest tests[] { // opgraph is move only...
        { "one op vs. one op -- same name", true,
            og_generators.at("a;")({{"name_a","a"}}),
            og_generators.at("a;")({{"name_a","a"}}),
        },
        { "one op vs. one op -- same name, different op", false,
            og_generators.at("a;")({{"name_a","a"},{"op_a","add"}}),
            og_generators.at("a;")({{"name_a","a"},{"op_a","mul"}}),
        },
        { "one op vs. one op -- different name", false,
            og_generators.at("a;")({{"name_a","a"}}),
            og_generators.at("a;")({{"name_a","b"}}),
        },
        { "two ops vs. two ops -- same names", true,
            og_generators.at("a;b")({{"name_a","a"},{"name_b","b"}}),
            og_generators.at("a;b")({{"name_a","a"},{"name_b","b"}}),
        },
        { "two ops vs. two ops -- 1 different name", false,
            og_generators.at("a;b")({{"name_a","a"},{"name_b","b"}}),
            og_generators.at("a;b")({{"name_a","a"},{"name_b","c"}}),
        },
        { "a->b vs. a;b", false,
            og_generators.at("a->b")({{"name_a","a"},{"name_b","b"},{"ab_oper",Operands::BINARY_ANY}}),
            og_generators.at("a;b" )({{"name_a","b"},{"name_b","c"}}),
        },
        { "a->b vs. a->b", true,
            og_generators.at("a->b")({{"name_a","a"},{"name_b","b"},{"ab_oper",Operands::BINARY_ANY}}),
            og_generators.at("a->b")({{"name_a","a"},{"name_b","b"},{"ab_oper",Operands::BINARY_ANY}}),
        },
        { "a->b vs. a->b, but operand tag is different", false,
            og_generators.at("a->b")({{"name_a","a"},{"name_b","b"},{"ab_oper",Operands::BINARY_LHS}}),
            og_generators.at("a->b")({{"name_a","a"},{"name_b","b"},{"ab_oper",Operands::BINARY_RHS}}),
        },
        { "a->{b c} vs. a->{b c}", true,
            og_generators.at("a->{b c}")({{"name_a","a"},{"name_b","b"},{"name_c","c"},{"ab_oper",Operands::BINARY_ANY},{"ac_oper",Operands::BINARY_ANY}}),
            og_generators.at("a->{b c}")({{"name_a","a"},{"name_b","b"},{"name_c","c"},{"ab_oper",Operands::BINARY_ANY},{"ac_oper",Operands::BINARY_ANY}}),
        },
        { "a->{b c} vs. a->{b d}", false,
            og_generators.at("a->{b c}")({{"name_a","a"},{"name_b","b"},{"name_c","c"},{"ab_oper",Operands::BINARY_ANY},{"ac_oper",Operands::BINARY_ANY}}),
            og_generators.at("a->{b c}")({{"name_a","a"},{"name_b","b"},{"name_c","d"},{"ab_oper",Operands::BINARY_ANY},{"ac_oper",Operands::BINARY_ANY}}),
        },
        { "a->{b c} vs. a->{b c}, but operand tag is different", false,
            og_generators.at("a->{b c}")({{"name_a","a"},{"name_b","b"},{"name_c","c"},{"ab_oper",Operands::BINARY_ANY},{"ac_oper",Operands::BINARY_ANY}}),
            og_generators.at("a->{b c}")({{"name_a","a"},{"name_b","b"},{"name_c",Operands::BINARY_ANY},{"ab_oper",Operands::BINARY_LHS},{"ac_oper",Operands::BINARY_RHS}}),
        },
        { "one const vs. one const -- same value", true,
            og_generators.at("const_a;")({{"name_a","a"}, {"constVal", "4"}}),
            og_generators.at("const_a;")({{"name_a","a"}, {"constVal", "4"}}),
        },
        { "one const vs. one const -- different value", false,
            og_generators.at("const_a;")({{"name_a","a"}, {"constVal", "1"}}),
            og_generators.at("const_a;")({{"name_a","a"}, {"constVal", "4"}}),
        },
        { "After erasing a node and a val", true,
            og_generators.at("a->b with b erased")({{"name_a","a"},{"name_b","b"},{"ab_oper",Operands::BINARY_ANY}}),
            og_generators.at("a;")(                {{"name_a","a"},{"name_b","b"},{"ab_oper",Operands::BINARY_ANY}}),
        },
        { "After erasing just a node", true,
            og_generators.at("a->{b c} with c erased")({{"name_a","a"},{"name_b","b"},{"name_c","c"},{"ab_oper",Operands::BINARY_ANY},{"ac_oper",Operands::BINARY_ANY}}),
            og_generators.at("a->b")(                  {{"name_a","a"},{"name_b","b"},{"name_c","c"},{"ab_oper",Operands::BINARY_ANY},{"ac_oper",Operands::BINARY_ANY}}),
        },
    };
 
    using std::begin; using std::end;
    const auto& test_it = GENERATE_REF(range((std::ptrdiff_t)0, std::distance(begin(tests), end(tests))));
    const auto& test = tests[test_it];
 
    GIVEN("A '" << test.test_description << "' test case") {
        THEN("The OpGraphs should " << (test.expect_to_be_same?"":"not ") << "compare equal") {
            if (test.expect_to_be_same) {
                CHECK(test.graph1 == test.graph2);
                CHECK_FALSE(test.graph1 != test.graph2);
            } else {
                CHECK(test.graph1 != test.graph2);
                CHECK_FALSE(test.graph1 == test.graph2);
            }
        }
        THEN("A copies should compare as expected") {
            const auto graph1_copy = test.graph1;
            CHECK(graph1_copy == test.graph1);
            if (test.expect_to_be_same) {
                CHECK(graph1_copy == test.graph2);
                CHECK_FALSE(graph1_copy != test.graph2);
            } else {
                CHECK(graph1_copy != test.graph2);
                CHECK_FALSE(graph1_copy == test.graph2);
            }
 
            const auto graph2_copy = test.graph2;
            CHECK(graph2_copy == test.graph2);
            if (test.expect_to_be_same) {
                CHECK(test.graph1 == graph2_copy);
                CHECK_FALSE(test.graph1 != graph2_copy);
            } else {
                CHECK(test.graph1 != graph2_copy);
                CHECK_FALSE(test.graph1 == graph2_copy);
            }
        }
    }
}