callGraph.h

/*
 * SPDX-FileCopyrightText: 2013 Barefoot Networks, Inc.
 * Copyright 2013-present Barefoot Networks, Inc.
 *
 * SPDX-License-Identifier: Apache-2.0
 */
 
#ifndef FRONTENDS_P4_CALLGRAPH_H_
#define FRONTENDS_P4_CALLGRAPH_H_
 
#include <algorithm>
#include <unordered_set>
#include <vector>
 
#include "ir/ir.h"
#include "lib/exceptions.h"
#include "lib/log.h"
#include "lib/map.h"  // IWYU pragma: keep
#include "lib/null.h"
#include "lib/ordered_map.h"
#include "lib/ordered_set.h"
 
namespace P4 {
 
// I could not get Util::toString() to work properly
cstring cgMakeString(cstring s);
cstring cgMakeString(char c);
cstring cgMakeString(const IR::Node *node);
cstring cgMakeString(const IR::INode *node);
 
template <class T>
class CallGraph {
 protected:
    cstring name;
    // Use an ordered map to make this deterministic
    ordered_map<T, std::vector<T> *> out_edges;  // map caller to list of callees
    ordered_map<T, std::vector<T> *> in_edges;
 
 public:
    ordered_set<T> nodes;  // all nodes; do not modify this directly
    using const_iterator = typename ordered_map<T, std::vector<T> *>::const_iterator;
 
    explicit CallGraph(std::string_view name) : name(name) {}

    [[nodiscard]] const cstring &getName() const { return name; }

    [[nodiscard]] bool empty() const { return nodes.empty(); }

    [[nodiscard]] size_t size() const { return nodes.size(); }

    [[nodiscard]] const ordered_map<T, std::vector<T> *> &getOutEdges() const { return out_edges; }

    [[nodiscard]] const ordered_map<T, std::vector<T> *> &getInEdges() const { return in_edges; }

    [[nodiscard]] const ordered_set<T> &getNodes() const { return nodes; }
 
    // Graph construction.
 
    // node that may call no-one
    void add(T caller) {
        if (nodes.find(caller) != nodes.end()) return;
        LOG1(name << ": " << cgMakeString(caller));
        out_edges[caller] = new std::vector<T>();
        in_edges[caller] = new std::vector<T>();
        nodes.emplace(caller);
    }
    void calls(T caller, T callee) {
        LOG1(name << ": " << cgMakeString(callee) << " is called by " << cgMakeString(caller));
        add(caller);
        add(callee);
        out_edges[caller]->push_back(callee);
        in_edges[callee]->push_back(caller);
    }
    void remove(T node) {
        auto n = nodes.find(node);
        BUG_CHECK(n != nodes.end(), "%1%: Node not in graph", node);
        nodes.erase(n);
        auto in = in_edges.find(node);
        if (in != in_edges.end()) {
            // remove all edges pointing to this node
            for (auto n : *in->second) {
                auto out = out_edges[n];
                CHECK_NULL(out);
                auto oe = std::find(out->begin(), out->end(), node);
                out->erase(oe);
            }
            in_edges.erase(in);
        }
        auto it = out_edges.find(node);
        if (it != out_edges.end()) {
            // Remove all edges that point from this node
            for (auto n : *it->second) {
                auto in = in_edges[n];
                CHECK_NULL(in);
                auto ie = std::find(in->begin(), in->end(), node);
                in->erase(ie);
            }
            out_edges.erase(it);
        }
    }
 
    // Graph querying
 
    bool isCallee(T callee) const {
        auto callees = ::P4::get(in_edges, callee);
        return callees != nullptr && !callees->empty();
    }
    bool isCaller(T caller) const {
        auto edges = ::P4::get(out_edges, caller);
        if (edges == nullptr) return false;
        return !edges->empty();
    }
    // Iterators over the out_edges
    const_iterator begin() const { return out_edges.cbegin(); }
    const_iterator end() const { return out_edges.cend(); }
    std::vector<T> *getCallees(T caller) { return out_edges[caller]; }
    std::vector<T> *getCallers(T callee) { return in_edges[callee]; }
    // Callees are appended to 'toAppend'
    void getCallees(T caller, std::set<T> &toAppend) {
        if (isCaller(caller)) toAppend.insert(out_edges[caller]->begin(), out_edges[caller]->end());
    }
    // out will contain all nodes reachable from start
    void reachable(T start, std::set<T> &out) const {
        std::set<T> work;
        work.emplace(start);
        while (!work.empty()) {
            T node = *work.begin();
            work.erase(node);
            if (out.find(node) != out.end()) continue;
            out.emplace(node);
            auto edges = out_edges.find(node);
            if (edges == out_edges.end()) continue;
            for (auto c : *(edges->second)) work.emplace(c);
        }
    }
    // remove all nodes not in 'to'
    void restrict(const std::set<T> &to) {
        std::vector<T> toRemove;
        for (auto n : nodes)
            if (to.find(n) == to.end()) toRemove.push_back(n);
        for (auto n : toRemove) remove(n);
    }
 
    using Set = std::unordered_set<T>;
 
    // Compute for each node the set of dominators with the indicated start node.
    // Node d dominates node n if all paths from the start to n go through d
    // Result is deposited in 'dominators'.
    // 'dominators' should be empty when calling this function.
    void dominators(T start, std::map<T, Set> &dominators) {
        // initialize
        for (auto n : nodes) {
            if (n == start)
                dominators[n].emplace(start);
            else
                dominators[n].insert(nodes.begin(), nodes.end());
        }
 
        // There are faster but more complicated algorithms.
        bool changes = true;
        while (changes) {
            changes = false;
            for (auto node : nodes) {
                auto vec = in_edges[node];
                if (vec == nullptr) continue;
                auto size = dominators[node].size();
                for (auto c : *vec) insersectWith(dominators[node], dominators[c]);
                dominators[node].emplace(node);
                if (dominators[node].size() != size) changes = true;
            }
        }
    }
 
    class Loop {
     public:
        T entry;
        std::set<T> body;
        // multiple back-edges could go to the same loop head
        std::set<T> back_edge_heads;
 
        explicit Loop(T entry) : entry(entry) {}
    };
 
    // All natural loops in a call-graph.
    struct Loops {
        std::vector<Loop *> loops;
 
        // Return loop index if 'node' is a loop entry point
        // else return -1
        int isLoopEntryPoint(T node) const {
            for (size_t i = 0; i < loops.size(); i++) {
                auto loop = loops.at(i);
                if (loop->entry == node) return i;
            }
            return -1;
        }
        bool isInLoop(int loopIndex, T node) const {
            if (loopIndex == -1) return false;
            auto loop = loops.at(loopIndex);
            return (loop->body.find(node) != loop->body.end());
        }
    };
 
    Loops *compute_loops(T start) {
        auto result = new Loops();
        std::map<T, Set> dom;
        dominators(start, dom);
 
        std::map<T, Loop *> entryToLoop;
 
        for (auto e : nodes) {
            auto next = out_edges[e];
            auto dome = dom[e];
            for (auto n : *next) {
                if (dome.find(n) != dome.end()) {
                    // n is a loop head
                    auto loop = get(entryToLoop, n);
                    if (loop == nullptr) {
                        loop = new Loop(n);
                        entryToLoop[n] = loop;
                        result->loops.push_back(loop);
                    }
                    loop->back_edge_heads.emplace(e);
                    // reverse DFS from e to n
 
                    std::set<T> work;
                    work.emplace(e);
                    while (!work.empty()) {
                        auto crt = *work.begin();
                        work.erase(crt);
                        loop->body.emplace(crt);
                        if (crt == n) continue;
                        for (auto i : *in_edges[crt])
                            if (loop->body.find(i) == loop->body.end()) work.emplace(i);
                    }
                }
            }
        }
        return result;
    }
 
 protected:
    // intersect in place
    static void insersectWith(Set &set, Set &with) {
        std::vector<T> toRemove;
        for (auto e : set)
            if (with.find(e) == with.end()) toRemove.push_back(e);
        for (auto e : toRemove) set.erase(e);
    }
 
    // Helper for computing strongly-connected components
    // using Tarjan's algorithm.
    struct sccInfo {
        unsigned crtIndex;
        std::vector<T> stack;
        std::set<T> onStack;
        std::map<T, unsigned> index;
        std::map<T, unsigned> lowlink;
 
        sccInfo() : crtIndex(0) {}
        void push(T node) {
            stack.push_back(node);
            onStack.emplace(node);
        }
        bool isOnStack(T node) { return onStack.count(node) != 0; }
        bool unknown(T node) { return index.count(node) == 0; }
        void setLowLink(T node, unsigned value) {
            lowlink[node] = value;
            LOG1(node << ".lowlink = " << value << " = " << get(lowlink, node));
        }
        void setLowLink(T node, T successor) {
            unsigned nlink = get(lowlink, node);
            unsigned slink = get(lowlink, successor);
            if (slink < nlink) setLowLink(node, slink);
        }
        T pop() {
            T result = stack.back();
            stack.pop_back();
            onStack.erase(result);
            return result;
        }
    };
 
    // helper for scSort
    bool strongConnect(T node, sccInfo &helper, std::vector<T> &out) {
        bool loop = false;
 
        LOG1("scc " << cgMakeString(node));
        helper.index.emplace(node, helper.crtIndex);
        helper.setLowLink(node, helper.crtIndex);
        helper.crtIndex++;
        helper.push(node);
        auto oe = out_edges[node];
        if (oe != nullptr) {
            for (auto next : *oe) {
                LOG1(cgMakeString(node) << " => " << cgMakeString(next));
                if (helper.unknown(next)) {
                    bool l = strongConnect(next, helper, out);
                    loop = loop | l;
                    helper.setLowLink(node, next);
                } else if (helper.isOnStack(next)) {
                    helper.setLowLink(node, next);
                    if (next == node)
                        // the check below does not find self-loops
                        loop = true;
                }
            }
        }
 
        if (get(helper.lowlink, node) == get(helper.index, node)) {
            LOG1(cgMakeString(node) << " index=" << get(helper.index, node)
                                    << " lowlink=" << get(helper.lowlink, node));
            while (true) {
                T sccMember = helper.pop();
                LOG1("Scc order " << cgMakeString(sccMember) << "[" << cgMakeString(node) << "]");
                out.push_back(sccMember);
                if (sccMember == node) break;
                loop = true;
            }
        }
 
        return loop;
    }
 
 public:
    // Sort that computes strongly-connected components - all nodes in
    // a strongly-connected components will be consecutive in the
    // sort.  Returns true if the graph contains at least one
    // cycle.  Ignores nodes not reachable from 'start'.
    bool sccSort(T start, std::vector<T> &out) {
        sccInfo helper;
        return strongConnect(start, helper, out);
    }
    bool sort(std::vector<T> &start, std::vector<T> &out) {
        sccInfo helper;
        bool cycles = false;
        for (auto n : start) {
            if (std::find(out.begin(), out.end(), n) == out.end()) {
                bool c = strongConnect(n, helper, out);
                cycles = cycles || c;
            }
        }
        return cycles;
    }
    bool sort(std::vector<T> &out) {
        sccInfo helper;
        bool cycles = false;
        for (auto n : nodes) {
            if (std::find(out.begin(), out.end(), n) == out.end()) {
                bool c = strongConnect(n, helper, out);
                cycles = cycles || c;
            }
        }
        return cycles;
    }
};
 
}  // namespace P4
 
#endif /* FRONTENDS_P4_CALLGRAPH_H_ */