controlFlowGraph.h

/*
 * SPDX-FileCopyrightText: 2013 Barefoot Networks, Inc.
 * Copyright 2013-present Barefoot Networks, Inc.
 *
 * SPDX-License-Identifier: Apache-2.0
 */
 
#ifndef BACKENDS_BMV2_COMMON_CONTROLFLOWGRAPH_H_
#define BACKENDS_BMV2_COMMON_CONTROLFLOWGRAPH_H_
 
#include "frontends/common/resolveReferences/referenceMap.h"
#include "frontends/p4/typeMap.h"
#include "ir/ir.h"
#include "lib/castable.h"
#include "lib/ordered_set.h"
 
namespace P4::BMV2 {

class CFG final : public IHasDbPrint {
 public:
    class Edge;
    class Node;
 
    class EdgeSet final : public IHasDbPrint {
     public:
        ordered_set<CFG::Edge *> edges;
 
        EdgeSet() = default;
        explicit EdgeSet(CFG::Edge *edge) { edges.emplace(edge); }
        explicit EdgeSet(const EdgeSet *other) { mergeWith(other); }
 
        void mergeWith(const EdgeSet *other) {
            edges.insert(other->edges.begin(), other->edges.end());
        }
        void dbprint(std::ostream &out) const;
        void emplace(CFG::Edge *edge) { edges.emplace(edge); }
        size_t size() const { return edges.size(); }
        bool checkSame(const EdgeSet &other) const;
        bool isDestination(const CFG::Node *destination) const;
    };
 
    class Node : public IHasDbPrint, public ICastable {
     protected:
        friend class CFG;
 
        static unsigned crtId;
        EdgeSet predecessors;
        explicit Node(cstring name) : id(crtId++), name(name) {}
        Node() : id(crtId++), name("node_" + Util::toString(id)) {}
        virtual ~Node() {}
 
     public:
        const unsigned id;
        const cstring name;
        EdgeSet successors;
 
        void dbprint(std::ostream &out) const override;
        void addPredecessors(const EdgeSet *set);
        void computeSuccessors();
        cstring toString() const { return name; }
 
        DECLARE_TYPEINFO(Node);
    };
 
 public:
    class TableNode final : public Node {
     public:
        const IR::P4Table *table;
        const IR::Expression *invocation;
        explicit TableNode(const IR::P4Table *table, const IR::Expression *invocation)
            : Node(table->controlPlaneName()), table(table), invocation(invocation) {
            CHECK_NULL(table);
            CHECK_NULL(invocation);
        }
 
        DECLARE_TYPEINFO(TableNode, Node);
    };
 
    class IfNode final : public Node {
     public:
        const IR::IfStatement *statement;
        explicit IfNode(const IR::IfStatement *statement) : statement(statement) {
            CHECK_NULL(statement);
        }
 
        DECLARE_TYPEINFO(IfNode, Node);
    };
 
    class DummyNode final : public Node {
     public:
        explicit DummyNode(cstring name) : Node(name) {}
 
        DECLARE_TYPEINFO(DummyNode, Node);
    };
 
 protected:
    enum class EdgeType { Unconditional, True, False, Label };
 
 public:
    class Edge final {
     protected:
        EdgeType type;
        Edge(Node *node, EdgeType type, cstring label) : type(type), endpoint(node), label(label) {}
 
     public:
        Node *endpoint;
        cstring label;  // only present if type == Label
 
        explicit Edge(Node *node) : type(EdgeType::Unconditional), endpoint(node) {
            CHECK_NULL(node);
        }
        Edge(Node *node, bool b) : type(b ? EdgeType::True : EdgeType::False), endpoint(node) {
            CHECK_NULL(node);
        }
        Edge(Node *node, cstring label) : type(EdgeType::Label), endpoint(node), label(label) {
            CHECK_NULL(node);
        }
        void dbprint(std::ostream &out) const;
        Edge *clone(Node *node) const { return new Edge(node, type, label); }
        Node *getNode() { return endpoint; }
        bool getBool() {
            BUG_CHECK(isBool(), "Edge is not Boolean");
            return type == EdgeType::True;
        }
        bool isBool() const { return type == EdgeType::True || type == EdgeType::False; }
        bool isUnconditional() const { return type == EdgeType::Unconditional; }
    };
 
 public:
    Node *entryPoint;
    Node *exitPoint;
    const IR::P4Control *container;
    ordered_set<Node *> allNodes;
 
    CFG() : entryPoint(nullptr), exitPoint(nullptr), container(nullptr) {}
    Node *makeNode(const IR::P4Table *table, const IR::Expression *invocation) {
        auto result = new TableNode(table, invocation);
        allNodes.emplace(result);
        return result;
    }
    Node *makeNode(const IR::IfStatement *statement) {
        auto result = new IfNode(statement);
        allNodes.emplace(result);
        return result;
    }
    Node *makeNode(cstring name) {
        auto result = new DummyNode(name);
        allNodes.emplace(result);
        return result;
    }
    void build(const IR::P4Control *cc, P4::ReferenceMap *refMap, P4::TypeMap *typeMap);
    void setEntry(Node *entry) {
        BUG_CHECK(entryPoint == nullptr, "Entry already set");
        entryPoint = entry;
    }
    void dbprint(std::ostream &out, Node *node, std::set<Node *> &done) const;  // helper
    void dbprint(std::ostream &out) const;
    void computeSuccessors() {
        for (auto n : allNodes) n->computeSuccessors();
    }
    bool checkImplementable() const;
 
 private:
    bool dfs(Node *node, std::set<Node *> &visited, std::set<const IR::P4Table *> &stack) const;
    bool checkMergeable(std::set<TableNode *> nodes) const;
};
 
}  // namespace P4::BMV2
 
#endif /* BACKENDS_BMV2_COMMON_CONTROLFLOWGRAPH_H_ */