MRRGProcedures.h

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/>.
 ******************************************************************************/
 
#ifndef MRRG_PROCEDURES__H_
#define MRRG_PROCEDURES__H_
 
#include <CGRA/MRRG.h>
#include <CGRA/MRRGProcedureCache.h>
#include <CGRA/utility/Collections.h>
#include <CGRA/impl/GraphAlgorithmHelpers.h>
#include <CGRA/Mapping.h>
 
#include <unordered_map>
#include <unordered_set>
#include <vector>
 
/*******************
 * Begin forward declarations and simple/small types
 *******************/
 
struct InterMRRGMap;
struct MRRGTransformationResult;
struct FindNeighbourFUsVisitor;
struct NodeExclusions;
 
struct MRRGNodeClassLists {
    std::vector<MRRG::NodeDescriptor> function_nodes = {};
    std::vector<MRRG::NodeDescriptor> routing_nodes = {};
};
 
struct MRRGNodeClassListsByCycle {
    std::vector<std::vector<MRRG::NodeDescriptor>> function_nodes = {};
    std::vector<std::vector<MRRG::NodeDescriptor>> routing_nodes = {};
};
 
struct FunctionalUnitNeighbours {
    struct NodeInfo {
        MRRG::NodeDescriptor node;
        int distance;
 
        operator MRRG::NodeDescriptor() const { return node; }
        bool operator==(const MRRG::NodeDescriptor& ndesc) const { return node == ndesc; }
    };
    using NodeInfoList = std::unordered_map<MRRG::NodeDescriptor, NodeInfo>;
 
    bool isReachableFrom(MRRG::NodeDescriptor src, MRRG::NodeDescriptor dest) const;
    const NodeInfo& getInfoFor(MRRG::NodeDescriptor src, MRRG::NodeDescriptor dest) const { return neighbours.at(src).at(dest); }
    friend std::ostream& operator<<(std::ostream& os, const FunctionalUnitNeighbours& fu_neighbours);
 
    std::unordered_map<MRRG::NodeDescriptor, NodeInfoList> neighbours = {};
 
    auto begin() const { return neighbours.begin(); }
    auto end() const { return neighbours.end(); }
    auto begin()       { return neighbours.begin(); }
    auto end()         { return neighbours.end(); }
};
 
struct MRRGTransformFlags {
};
 
/*******************
 * Begin function prototypes
 *******************/
 
MRRGNodeClassLists computeNodeClassLists(const MRRG& mrrg);
 
MRRGNodeClassListsByCycle computeNodeClassListsByCycle(const MRRG& mrrg);
 
std::unordered_map<OpGraph::OpDescriptor, std::vector<MRRG::NodeDescriptor>> findAllCompatibleFUs(const OpGraph& opgraph, const MRRG& base_mrrg);
 
FunctionalUnitNeighbours::NodeInfoList findNeighbourFUs(const MRRG& mrrg, MRRG::NodeDescriptor source, int min_neighbours_to_find);
 
template<typename NodeList = std::vector<MRRG::NodeDescriptor>, typename NEIGHBOUR_FINDER = FunctionalUnitNeighbours::NodeInfoList(const MRRG&, MRRG::NodeDescriptor,int)>
FunctionalUnitNeighbours findAllNeighbourFUs(const MRRG& mrrg, const NodeList& sources, int min_neighbours_to_find = -1, NEIGHBOUR_FINDER&& neighbour_finder = findNeighbourFUs) {
    FunctionalUnitNeighbours result;
    for(auto& n : sources) result.neighbours.emplace(n, std::forward<NEIGHBOUR_FINDER>(neighbour_finder)(mrrg, n, min_neighbours_to_find));
    return result;
}
 
inline auto makeNClosestNeighbourFinder(int min_neighbours) {
    return [=](const MRRG& mrrg, const std::vector<MRRG::NodeDescriptor>& all_compatible_nodes_list) -> FunctionalUnitNeighbours {
        auto result = findAllNeighbourFUs(mrrg, all_compatible_nodes_list, min_neighbours);
        // std::cout << result << std::endl;
        return result;
    };
}
 
std::vector<std::vector<MRRG::NodeDescriptor>> findNRoutingPathsBetween(
    int num_paths, const MRRG& mrrg, MRRG::NodeDescriptor source, MRRG::NodeDescriptor sink,
    std::pair<int,int> cycle_trip_count_min_max, const OperandTag& operand_tag,
    MRRGProcedureCacheHandle* cache_handle
);
 
std::vector<std::vector<MRRG::NodeDescriptor>> mergeMRRGWalks(
    const MRRG& mrrg, const std::vector<MrrgNodeSpan>& walks);
 
inline auto mergeMRRGWalks(
    const MRRG& mrrg, const std::vector<std::vector<MRRG::NodeDescriptor>>& walks
) {
    std::vector<MrrgNodeSpan> with_pointers;
    with_pointers.reserve(walks.size());
    auto to_span = [](auto& e) -> MrrgNodeSpan { return {e.data(), e.size()}; };
    std::transform(walks.begin(), walks.end(), std::back_inserter(with_pointers), to_span);
    return mergeMRRGWalks(mrrg, with_pointers);
}
 
int tripCountOfWalk(const MRRG& mrrg, const std::vector<MRRG::NodeDescriptor>& walk);
 
bool nodeIsCompatibleWithOperand(const MRRG& mrrg, MRRG::NodeDescriptor node, const OperandTag& operand_tag);
 
bool walkIsCompatibleWithOperand(const MRRG& mrrg, const std::vector<MRRG::NodeDescriptor>& walk, const OperandTag& operand_tag);
 
void recordNodeMerge(
    MRRGTransformationResult& transformation_result, const MRRG& src_mrrg,
    MRRG::NodeDescriptor into, MRRG::NodeDescriptor from
);
 
MRRGTransformationResult reduceLosslessly(const MRRG& src_mrrg, const MRRGTransformFlags& flags);
 
MRRGTransformationResult muxExNodeInsertion(const MRRG& src_mrrg);
 
/*******************
 * Simple node/graph functions
 *******************/
 
bool isNodeFanoutOf(const MRRG& mrrg, MRRG::NodeDescriptor driver_ndesc, MRRG::NodeDescriptor test_ndesc);
bool isNodeFaninOf(const MRRG& mrrg, MRRG::NodeDescriptor driven_ndesc, MRRG::NodeDescriptor test_ndesc);
void assertNodeIsFanoutOf(const MRRG& mrrg, MRRG::NodeDescriptor driver_ndesc, MRRG::NodeDescriptor test_ndesc, const char* action_name = " -- ");
void assertNodeIsFaninOf(const MRRG& mrrg, MRRG::NodeDescriptor driven_ndesc, MRRG::NodeDescriptor test_ndesc, const char* action_name = " -- ");
void assertNodeIsExcusiveFanout(const MRRG& mrrg, MRRG::NodeDescriptor driver_ndesc, MRRG::NodeDescriptor test_ndesc, const char* action_name = " -- ");
void assertNodeIsExcusiveFanin(const MRRG& mrrg, MRRG::NodeDescriptor driven_ndesc, MRRG::NodeDescriptor test_ndesc, const char* action_name = " -- ");
void assertHasNoOps(const MRRGNode& n, const char* action_name = "");
 
void assertHasSingleFanout(const MRRGNode& n, const char* action_name);
 
void mergeNodeConnections(MRRG& mrrg, MRRG::NodeDescriptor into_ndesc, MRRG::NodeDescriptor from_ndesc);
 
void mergeNodePropertiesOfExclusiveFanoutToExclusiveFanin(MRRG& mrrg, MRRG::NodeDescriptor into_ndesc, MRRG::NodeDescriptor from_ndesc);
 
void collapseSingleFaninFanoutNodeIntoFanin(MRRG& mrrg, MRRG::NodeDescriptor into_ndesc, MRRG::NodeDescriptor from_ndesc);
 
/*******************
 * Begin type definitions
 *******************/
 
struct InterMRRGMap {
    using NodeSet = std::unordered_set<MRRG::NodeDescriptor>;
 
    // Get the nodes in the tranformed MRRG that correspond to node `n` in the src MRRG
    const NodeSet& newNodesForOldNode(MRRG::NodeDescriptor n) const { return value_for_key_or(forward_map, n, empty_node_list); }
 
    // Get the nodes in the src MRRG that correspond to node `n` in the transformed MRRG
    const NodeSet& oldNodesForNewNode(MRRG::NodeDescriptor n) const { return value_for_key_or(reverse_map, n, empty_node_list); }
 
    void addMapping(MRRG::NodeDescriptor old_node, MRRG::NodeDescriptor new_node) {
        forward_map[old_node].emplace(new_node);
        reverse_map[new_node].emplace(old_node);
    }
 
    template<typename NodeList = std::vector<MRRG::NodeDescriptor>>
    void addMappingMulti(MRRG::NodeDescriptor old_node, const NodeList& new_nodes) { for (auto& nn : new_nodes) { addMapping(old_node, nn); } }
    template<typename NodeList = std::vector<MRRG::NodeDescriptor>>
    void addMappingMulti(const NodeList& old_nodes, MRRG::NodeDescriptor new_node) { for (auto& on : old_nodes) { addMapping(on, new_node); } }
 
    // Adds mapping from node in src MRRG to its copy in the transformed MRRG.
    void addAllByMatchingProperties(const MRRG& src_mrrg, const MRRG& transformed_mrrg);
 
    void mergeDescriptors(MRRG::NodeDescriptor from, MRRG::NodeDescriptor into);
 
    bool operator==(const InterMRRGMap& rhs) const { return forward_map == rhs.forward_map && reverse_map == rhs.reverse_map; }
    friend std::ostream& operator<<(std::ostream& os, const InterMRRGMap& imm);
private:
    std::unordered_map<MRRG::NodeDescriptor, NodeSet> forward_map = {};
    std::unordered_map<MRRG::NodeDescriptor, NodeSet> reverse_map = {};
    NodeSet empty_node_list = {};
};
 
struct MRRGTransformationResult {
    MRRG transformed_mrrg;
    InterMRRGMap mapping = {};
};
 
struct FindNeighbourFUsVisitor : DoNothingGraphVisitor<MRRG::NodeDescriptor> {
    std::unordered_set<MRRG::NodeDescriptor> discovered_fu_nodes = {};
 
    bool shouldIgnore(const MRRG::NodeDescriptor& v) {
        return discovered_fu_nodes.find(v) != end(discovered_fu_nodes);
    }
 
    void onExamineEdge(const MRRG::NodeDescriptor&, const MRRG::NodeDescriptor& fanout) {
        if (fanout->type == MRRG_NODE_FUNCTION || fanout->type == MRRG_NODE_ROUTING_FUNCTION) {
            discovered_fu_nodes.insert(fanout);
        }
    }
};
 
Mapping transformToOriginalMRRG(const Mapping & map, const MRRGTransformationResult & transformation);
 
Mapping removeMuxExNodeInsertion(const Mapping & map, const MRRGTransformationResult & transformation);
 
#endif /* MRRG_PROCEDURES__H_ */