table_flow_graph.h

 
#ifndef BF_P4C_MAU_TABLE_FLOW_GRAPH_H_
#define BF_P4C_MAU_TABLE_FLOW_GRAPH_H_
 
#include <map>
#include <optional>
#include <set>
 
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/transitive_closure.hpp>
 
#include "bf-p4c/ir/control_flow_visitor.h"
#include "bf-p4c/lib/boost_graph.h"
#include "bf-p4c/mau/mau_visitor.h"
 
namespace boost {
enum vertex_table_t { vertex_table };
BOOST_INSTALL_PROPERTY(vertex, table);
 
enum edge_annotation_t { edge_annotation };
BOOST_INSTALL_PROPERTY(edge, annotation);
}  // namespace boost
 
using namespace P4;
 
struct FlowGraph {
    typedef boost::adjacency_list<boost::vecS, boost::vecS,
                                  boost::bidirectionalS,  // Directed edges.
                                  // Label vertices with tables.
                                  boost::property<boost::vertex_table_t, const IR::MAU::Table *>,
                                  // Label edges with control annotations.
                                  boost::property<boost::edge_annotation_t, cstring>>
        Graph;
 
    class BFSPathFinder : public boost::default_bfs_visitor {
        std::map<typename Graph::vertex_descriptor, typename Graph::vertex_descriptor> *parent =
            nullptr;
 
        struct done {};
 
        const Graph &graph;
 
        typename Graph::vertex_descriptor dst;
 
     public:
        void examine_edge(typename Graph::edge_descriptor e, const Graph &g) {
            auto src = boost::source(e, g);
            auto dst = boost::target(e, g);
 
            if (!parent->count(dst)) (*parent)[dst] = src;
            if (dst == this->dst) throw done{};
        }
 
        explicit BFSPathFinder(const Graph &g) : graph(g) {}
 
        std::vector<typename Graph::vertex_descriptor> find_path(
            typename Graph::vertex_descriptor src, typename Graph::vertex_descriptor dst) {
            std::map<typename Graph::vertex_descriptor, typename Graph::vertex_descriptor> parent;
            this->parent = &parent;
 
            this->dst = dst;
            try {
                boost::breadth_first_search(graph, src, boost::visitor(*this));
            } catch (done const &) {
            }
 
            std::vector<typename Graph::vertex_descriptor> result;
            if (parent.count(dst)) {
                // Search succeeded. Build the path in reverse.
                auto cur = dst;
                result.emplace_back(cur);
                do {
                    cur = parent.at(cur);
                    result.emplace_back(cur);
                } while (cur != src);
 
                // Reverse the result so we get a forward path.
                for (unsigned i = 0; i < result.size() / 2; ++i) {
                    std::swap(result[i], result[result.size() - i - 1]);
                }
            }
 
            // Clean up for the next call.
            this->parent = nullptr;
 
            return result;
        }
    };
 
    Graph g;
 
    typename Graph::vertex_descriptor v_source;
 
    typename Graph::vertex_descriptor v_sink;
 
    std::optional<gress_t> gress;
 
    mutable Reachability<Graph> reachability;
 
    ordered_map<const IR::MAU::Table *, int> tableToVertexIndex;
 
    std::set<const IR::MAU::Table *> tables;
 
    mutable std::optional<std::map<const IR::MAU::Table *, std::set<const IR::MAU::Table *>>>
        dominators;
 
    // By default, emptyFlowGraph is set to true to indicate that there are no vertices in the
    // graph. Only when the first actual table is added to the flow graph is this member set to
    // false.
    bool emptyFlowGraph = true;
 
    const cstring get_ctrl_dependency_info(typename Graph::edge_descriptor edge) const {
        return boost::get(boost::edge_annotation, g)[edge];
    }
 
    FlowGraph(void) : reachability(g), path_finder(g) {
        gress = std::nullopt;
        dominators = std::nullopt;
    }
 
    FlowGraph(FlowGraph &&other)
        : g(std::move(other.g)),
          gress(std::move(other.gress)),
          reachability(g),
          tableToVertexIndex(std::move(other.tableToVertexIndex)),
          tables(std::move(other.tables)),
          dominators(std::move(other.dominators)),
          emptyFlowGraph(std::move(other.emptyFlowGraph)),
          tableToVertex(std::move(other.tableToVertex)),
          path_finder(g) {}
 
    FlowGraph(const FlowGraph &other)
        : g(other.g),
          gress(other.gress),
          reachability(g),
          tableToVertexIndex(other.tableToVertexIndex),
          tables(other.tables),
          dominators(other.dominators),
          emptyFlowGraph(other.emptyFlowGraph),
          tableToVertex(other.tableToVertex),
          path_finder(g) {}
 
    std::map<const IR::MAU::Table *, typename Graph::vertex_descriptor> tableToVertex;
 
    std::map<typename Graph::vertex_descriptor, const IR::MAU::Table *> vertexToTable;
 
    bool is_empty() const {
        auto all_vertices = boost::vertices(g);
        if (++all_vertices.first == all_vertices.second) {
            return true;
        }
        return false;
    }
 
    void clear() {
        g.clear();
        gress = std::nullopt;
        reachability.clear();
        tableToVertexIndex.clear();
        tableToVertex.clear();
        vertexToTable.clear();
        tables.clear();
        emptyFlowGraph = true;
    }
 
    void add_sink_vertex() {
        v_sink = add_vertex(nullptr);
        reachability.setSink(v_sink);
    }
 
    bool can_reach(const IR::MAU::Table *t1, const IR::MAU::Table *t2) const {
        if (t2 == nullptr) return true;
        if (t1 == nullptr) return false;
        const auto v1 = get_vertex(t1);
        const auto v2 = get_vertex(t2);
        return reachability.canReach(v1, v2);
    }
 
    const std::set<const IR::MAU::Table *> get_dominators(const IR::MAU::Table *table) const;
 
    bool is_always_reached(const IR::MAU::Table *) const;
 
    BFSPathFinder path_finder;
 
    std::vector<const IR::MAU::Table *> find_path(const IR::MAU::Table *src,
                                                  const IR::MAU::Table *dst) {
        auto path = path_finder.find_path(get_vertex(src), get_vertex(dst));
        std::vector<const IR::MAU::Table *> result;
        for (auto node : path) {
            result.emplace_back(get_vertex(node));
        }
 
        return result;
    }
 
    const IR::MAU::Table *get_vertex(typename Graph::vertex_descriptor v) const {
        return boost::get(boost::vertex_table, g)[v];
    }
 
    typename Graph::vertex_descriptor get_vertex(const IR::MAU::Table *tbl) const {
        BUG_CHECK(tableToVertexIndex.count(tbl), "Table object not found for %1%",
                  tbl->externalName());
        return tableToVertexIndex.at(tbl);
    }
 
    const std::set<const IR::MAU::Table *> get_tables() const { return tables; }
 
    typename Graph::vertex_descriptor add_vertex(const IR::MAU::Table *table) {
        // Initialize gress if needed.
        if (table != nullptr && gress == std::nullopt) gress = table->gress;
 
        if (tableToVertex.count(table)) {
            return tableToVertex.at(table);
        }
 
        // Create new vertex.
        auto v = boost::add_vertex(table, g);
        tableToVertex[table] = v;
        vertexToTable[v] = table;
        if (table) tables.insert(table);
 
        // If the vertex being added corresponds to a real table (not the sink), then the flow
        // graph is no longer empty; set the emptyFlowGraph member accordingly.
        if (table != nullptr) emptyFlowGraph = false;
 
        return v;
    }
 
    std::pair<typename Graph::edge_descriptor, bool> add_edge(const IR::MAU::Table *src,
                                                              const IR::MAU::Table *dst,
                                                              const cstring edge_label) {
        typename Graph::vertex_descriptor src_v, dst_v;
        src_v = add_vertex(src);
        dst_v = add_vertex(dst);
 
        // Look for a pre-existing edge.
        typename Graph::out_edge_iterator out, end;
        for (boost::tie(out, end) = boost::out_edges(src_v, g); out != end; ++out) {
            if (boost::target(*out, g) == dst_v) return {*out, false};
        }
 
        // No pre-existing edge, so make one.
        auto maybe_new_e = boost::add_edge(src_v, dst_v, g);
        if (!maybe_new_e.second)
            // A vector-based adjacency_list (i.e. Graph) is a multigraph.
            // Inserting edges should always create new edges.
            BUG("Boost Graph Library failed to add edge.");
        boost::get(boost::edge_annotation, g)[maybe_new_e.first] = edge_label;
        return {maybe_new_e.first, true};
    }
 
    std::vector<const IR::MAU::Table *> topological_sort() const {
        std::vector<Graph::vertex_descriptor> internal_result;
        boost::topological_sort(g, std::back_inserter(internal_result));
 
        // Boost produces a reverse order with internal vertices. Reverse the list while converting
        // to tables.
        std::vector<const IR::MAU::Table *> result;
        for (auto it = internal_result.rbegin(); it != internal_result.rend(); ++it) {
            result.push_back(get_vertex(*it));
        }
 
        return result;
    }
 
    friend std::ostream &operator<<(std::ostream &, const FlowGraph &);
 
    struct DumpTableDetails {
        virtual void dump(std::ostream &, const IR::MAU::Table *) const {}
    };
 
    static std::string viz_node_name(const IR::MAU::Table *tbl);
    void dump_viz(std::ostream &out, const DumpTableDetails *details = nullptr);
};
 
//
// FIXME(Jed): This currently only works when gateway conditions are represented as separate table
// objects. After table placement, gateways and match tables are fused into single table objects.
// This pass should be fixed at some point to support this fused representation.
//
// Here are some thoughts on how to this. We can leverage the call structure in
// IR::MAU::Table::visit_children; specifically, the calls to flow_clone, visit(Node, label),
// flow_merge_global_to, and flow_merge. This should give us enough information to track the set of
// tables that could have been the last one to execute before reaching the node being visited. With
// this, we should be able to build the flow graph. Effectively, we would piggyback on the existing
// infrastructure in visit_children for supporting ControlFlowVisitor. We don't actually want to
// write a ControlFlowVisitor here, however, since in its current form, ControlFlowVisitor will
// deadlock when there are cycles in the IR; FindFlowGraph is used in part to check that the IR is
// cycle-free.
class FindFlowGraph : public MauInspector {
 private:
    FlowGraph &fg;
 
    const IR::MAU::Table *next_table;
 
    std::pair<bool, cstring> next_incomplete(const IR::MAU::Table *t);
 
    Visitor::profile_t init_apply(const IR::Node *node) override;
    bool preorder(const IR::MAU::TableSeq *) override;
    bool preorder(const IR::MAU::Table *) override;
    bool preorder(const IR::MAU::Action *) override;
    void end_apply() override;
 
 public:
    explicit FindFlowGraph(FlowGraph &out) : fg(out), next_table(nullptr) {
        // We want to re-visit table nodes here, since the table calls can have different
        // next_tables in different contexts.
        visitDagOnce = false;
    }
};
 
class FindFlowGraphs : public MauInspector {
 private:
    ordered_map<gress_t, FlowGraph> &flow_graphs;
 
    Visitor::profile_t init_apply(const IR::Node *root) override;
    bool preorder(const IR::MAU::TableSeq *) override;
    bool preorder(const IR::BFN::Deparser *) override;
 
 public:
    explicit FindFlowGraphs(ordered_map<gress_t, FlowGraph> &out) : flow_graphs(out) {}
};
 
#endif /* BF_P4C_MAU_TABLE_FLOW_GRAPH_H_ */