simple_power_graph.h

 
#ifndef BF_P4C_MAU_SIMPLE_POWER_GRAPH_H_
#define BF_P4C_MAU_SIMPLE_POWER_GRAPH_H_
 
#include <cstring>
#include <map>
#include <set>
#include <stack>
#include <string>
#include <vector>
 
#include "bf-p4c/mau/mau_power.h"
 
namespace MauPower {
class Node;
class Edge;
 
using ::operator<<;
 
struct NodeAndEdgeSet {
    std::set<const Node *> nodes;
    std::set<const Edge *> edges;
};
 
class Edge {
 public:
    const size_t id_;     // edge id (used for dot output)
    const cstring name_;  // debug name of edge
    cstring to_string() const { return name_; }
    bool is_equivalent(const Edge *other) const;
 
    std::string get_edge_color() const;
 
    explicit Edge(size_t id, cstring name, std::vector<Node *> &child_nodes)
        : id_(id), name_(name) {
        for (auto n : child_nodes) {
            child_nodes_.push_back(n);
        }
    }
    // Encapsulation of what next Node(s) (logical table(s)) this edge connects to.
    std::vector<Node *> child_nodes_;
    void dbprint(std::ostream &out, NodeAndEdgeSet *seen) const;
    void dbprint(std::ostream &out) const {
        NodeAndEdgeSet seen;
        dbprint(out, &seen);
    }
};
 
class Node {
 public:
    const UniqueId unique_id_;
    const int id_;                   // node id (used for dot output)
    std::vector<Edge *> out_edges_;  // collection of outbound edges
 
    explicit Node(UniqueId uniq_id, int id) : unique_id_(uniq_id), id_(id) {}
    ~Node() {
        for (auto e : out_edges_) delete e;
    }
    Node(const Node &n) : unique_id_(n.unique_id_), id_(n.id_) {  // copy
        for (auto e : n.out_edges_) add_edge(e);
    }
    Node &operator=(const Node &n) = delete;   // copy assignment
    Node(const Node &&n) = delete;             // move
    Node &operator=(const Node &&n) = delete;  // move assignment
 
    void create_and_add_edge(cstring edge_name, std::vector<Node *> &child_nodes);
    bool is_equivalent(const Node *other) const;
    cstring to_string() const { return "" + unique_id_.build_name(); }
    void dbprint(std::ostream &out, NodeAndEdgeSet *seen) const;
    void dbprint(std::ostream &out) const {
        NodeAndEdgeSet seen;
        dbprint(out, &seen);
    }
 
 private:
    void add_edge(Edge *e);
};
 
class SimplePowerGraph : public IHasDbPrint {
    std::map<UniqueId, Node *> nodes_ = {};
    std::map<UniqueId, std::set<UniqueId>> pred_ = {};
 
 public:
    const cstring name_;  // graph name, e.g. ingress or egress
 
    explicit SimplePowerGraph(cstring gress) : name_(gress), running_id_(1) {
        UniqueId root_uid;
        root_uid.name = "$root"_cs;
        root_ = new Node(root_uid, 0);
        nodes_.emplace(root_uid, root_);
    }
    Node *get_root() const { return root_; }
    void add_connection(UniqueId parent, ordered_set<UniqueId> activated, cstring edge_name);
    void to_dot(cstring filename);
    void get_leaves(UniqueId n, std::vector<UniqueId> &leaves);
    bool can_reach(UniqueId parent, UniqueId child);
    bool active_simultaneously(UniqueId parent, UniqueId child);
    const std::set<UniqueId> &predecessors(UniqueId child) const {
        if (pred_.count(child)) return pred_.at(child);
        static std::set<UniqueId> empty;
        return empty;
    }
    std::vector<Node *> topo_sort();
    double get_tables_on_worst_path(
        const std::map<UniqueId, PowerMemoryAccess> &table_memory_access, std::set<Node *> &rv);
 
    void dbprint(std::ostream &out, NodeAndEdgeSet *seen) const;
    void dbprint(std::ostream &out) const {
        NodeAndEdgeSet seen;
        dbprint(out, &seen);
    }
 
 private:
    int running_id_;  // For producing unique integer values of graph Nodes.
    Node *root_;
    // Memoize if a parent-child relationship is reachable.
    std::map<std::pair<int, int>, bool> found_reachable_ = {};
    // Memoize if a parent-child pair is active simultaneously.
    std::map<std::pair<int, int>, bool> found_simultaneous_ = {};
    // Memoize worst-case power computed for a node.
    std::map<int, double> computed_power_ = {};
    // Memoize worst_path computed for a node;
    std::map<int, std::set<UniqueId>> computed_worst_path_ = {};
    // Keep track of who parent was on worst-case power path.
    std::map<Node *, Edge *> worst_path_edges_ = {};
 
    Node *create_node(UniqueId id);
    int get_next_id() { return running_id_++; }
    void topo_visit(Node *node, std::stack<Node *> *stack, std::map<Node *, bool> *visited);
    double visit_node_power(Node *n, const std::map<UniqueId, PowerMemoryAccess> &tma,
                            std::set<UniqueId> &worst_path);
};
 
}  // end namespace MauPower
 
#endif /* BF_P4C_MAU_SIMPLE_POWER_GRAPH_H_ */