dominator_tree.h

 
#ifndef BACKENDS_TOFINO_BF_P4C_PHV_ANALYSIS_DOMINATOR_TREE_H_
#define BACKENDS_TOFINO_BF_P4C_PHV_ANALYSIS_DOMINATOR_TREE_H_
 
#include "bf-p4c/mau/mau_visitor.h"
#include "bf-p4c/mau/table_flow_graph.h"
#include "ir/ir.h"
 
class BuildDominatorTree : public MauInspector {
 public:
    using ImmediateDominatorMap = ordered_map<const IR::MAU::Table *, const IR::MAU::Table *>;
    using G = FlowGraph::Graph;
    using Vertex = boost::graph_traits<G>::vertex_descriptor;
    using IndexMap = boost::property_map<G, boost::vertex_index_t>::type;
    using PredMap = boost::iterator_property_map<std::vector<Vertex>::iterator, IndexMap>;
 
 private:
    ordered_map<gress_t, FlowGraph> &flowGraph;
    ordered_map<gress_t, ImmediateDominatorMap *> iDominator;
 
    profile_t init_apply(const IR::Node *root) override;
    bool preorder(const IR::BFN::Pipe *pipe) override;
    bool preorder(const IR::MAU::Table *tbl) override;
 
    void generateIndexToTableMap(const FlowGraph &fg,
                                 ordered_map<int, const IR::MAU::Table *> &indexMap) const;
 
    void generateDominatorTree(const FlowGraph &fg,
                               const ordered_map<int, const IR::MAU::Table *> &indexToTableMap,
                               ImmediateDominatorMap &iDom);
 
    void printDominatorTree(const ImmediateDominatorMap &idom) const;
 
 public:
    const ordered_map<gress_t, FlowGraph> &getFlowGraph() const { return flowGraph; }
 
    /* setup dominator tree using flowGraph
     */
    void setupDomTree();
 
    std::optional<const IR::MAU::Table *> getImmediateDominator(const IR::MAU::Table *t,
                                                                gress_t gress) const;
 
    std::optional<const IR::MAU::Table *> getNonGatewayImmediateDominator(const IR::MAU::Table *t,
                                                                          gress_t gress) const;
 
    bool strictlyDominates(const IR::BFN::Unit *u1, const IR::BFN::Unit *u2) const;
 
    bool strictlyDominates(const IR::MAU::Table *t1, const IR::MAU::Table *t2) const;
 
    const IR::MAU::Table *getNonGatewayGroupDominator(
        ordered_set<const IR::MAU::Table *> &tables) const;
 
    const std::vector<const IR::MAU::Table *> getAllDominators(const IR::MAU::Table *t,
                                                               gress_t gress) const;
 
    explicit BuildDominatorTree(ordered_map<gress_t, FlowGraph> &fg) : flowGraph(fg) {}
 
 
    cstring hasImmediateDominator(gress_t g, cstring t) const;
 
    bool strictlyDominates(cstring t1, cstring t2, gress_t gress) const;
 
    bool isDominator(cstring t1, gress_t gress, cstring t2) const;
};
#endif /* BACKENDS_TOFINO_BF_P4C_PHV_ANALYSIS_DOMINATOR_TREE_H_ */