parser_dominator_builder.h

 
#ifndef BACKENDS_TOFINO_BF_P4C_PARDE_PARSER_DOMINATOR_BUILDER_H_
#define BACKENDS_TOFINO_BF_P4C_PARDE_PARSER_DOMINATOR_BUILDER_H_
 
#include <optional>
 
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dominator_tree.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/reverse_graph.hpp>
 
#include "backends/tofino/bf-p4c/logging/event_logger.h"
#include "backends/tofino/bf-p4c/parde/parser_info.h"
#include "ir/ir.h"
#include "ir/visitor.h"
 
class ParserDominatorBuilder : public PardeInspector {
 public:
    using IndexImmediateDominatorMap = ordered_map<int, int>;
    using StateImmediateDominatorMap =
        ordered_map<const IR::BFN::ParserState *, const IR::BFN::ParserState *>;
    using Graph = ReversibleParserGraph::Graph;
    using Vertex = boost::graph_traits<Graph>::vertex_descriptor;
    using IndexMap = boost::property_map<Graph, boost::vertex_index_t>::type;
    using PredMap = boost::iterator_property_map<std::vector<Vertex>::iterator, IndexMap>;
 
 protected:
    ordered_map<gress_t, ReversibleParserGraph> parser_graphs;
    ordered_map<gress_t, StateImmediateDominatorMap> immediate_dominators;
    ordered_map<gress_t, StateImmediateDominatorMap> immediate_post_dominators;
    std::set<const IR::BFN::ParserState *> states;
 
 private:
    bool preorder(const IR::BFN::Parser *parser) override;
 
    bool preorder(const IR::BFN::ParserState *parser_state) override;
 
    template <typename G>
    IndexImmediateDominatorMap get_immediate_dominators(G graph, Vertex entry,
                                                        bool get_post_dominators) {
        std::vector<Vertex> dom_tree_pred_vector;
        IndexMap index_map(boost::get(boost::vertex_index, graph));
        dom_tree_pred_vector =
            std::vector<Vertex>(boost::num_vertices(graph), boost::graph_traits<G>::null_vertex());
        PredMap dom_tree_pred_map =
            boost::make_iterator_property_map(dom_tree_pred_vector.begin(), index_map);
        boost::lengauer_tarjan_dominator_tree(graph, entry, dom_tree_pred_map);
 
        typename boost::graph_traits<G>::vertex_iterator it, end;
        IndexImmediateDominatorMap idom;
        std::string out = get_post_dominators ? "post-dominator" : "dominator";
        LOG7("Building " << out << " int map");
        for (std::tie(it, end) = boost::vertices(graph); it != end; ++it) {
            if (boost::get(dom_tree_pred_map, *it) != boost::graph_traits<G>::null_vertex()) {
                idom[boost::get(index_map, *it)] =
                    boost::get(index_map, boost::get(dom_tree_pred_map, *it));
                LOG7(TAB1 << "Setting " << out << " for " << boost::get(index_map, *it) << " to "
                          << boost::get(index_map, boost::get(dom_tree_pred_map, *it)));
            } else {
                idom[boost::get(index_map, *it)] = -1;
                LOG7(TAB1 << "Setting " << out << " for " << boost::get(index_map, *it)
                          << " to -1");
            }
        }
        return idom;
    }
 
    IndexImmediateDominatorMap get_immediate_dominators(Graph graph, Vertex entry);
 
    IndexImmediateDominatorMap get_immediate_post_dominators(boost::reverse_graph<Graph> graph,
                                                             Vertex entry);
 
    StateImmediateDominatorMap index_map_to_state_map(IndexImmediateDominatorMap &idom,
                                                      ReversibleParserGraph &rpg);
 
    std::set<const IR::BFN::ParserState *> get_all_dominatees(const IR::BFN::ParserState *state,
                                                              gress_t gress,
                                                              bool get_post_dominatees);
 
    std::set<const IR::BFN::ParserState *> get_all_dominators(const IR::BFN::ParserState *state,
                                                              gress_t gress,
                                                              bool get_post_dominators);
 
    void build_dominator_maps();
 
 protected:
    std::set<const IR::BFN::ParserState *> get_all_dominatees(const IR::BFN::ParserState *state,
                                                              gress_t gress = INGRESS);
 
    std::set<const IR::BFN::ParserState *> get_all_post_dominatees(
        const IR::BFN::ParserState *state, gress_t gress = INGRESS);
 
    std::set<const IR::BFN::ParserState *> get_all_dominators(const IR::BFN::ParserState *state,
                                                              gress_t gress = INGRESS);
 
    std::set<const IR::BFN::ParserState *> get_all_post_dominators(
        const IR::BFN::ParserState *state, gress_t gress = INGRESS);
 
    profile_t init_apply(const IR::Node *root) override;
    void end_apply() override;
 
 public:
    ParserDominatorBuilder() {}
};
 
#endif /* BACKENDS_TOFINO_BF_P4C_PARDE_PARSER_DOMINATOR_BUILDER_H_ */