callGraph.h

/*
Copyright 2013-present Barefoot Networks, Inc.
 
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
 
    http://www.apache.org/licenses/LICENSE-2.0
 
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
*/
 
#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
    typedef typename ordered_map<T, std::vector<T> *>::const_iterator const_iterator;
 
    explicit CallGraph(std::string_view name) : name(name) {}
 
    const cstring &getName() const { return name; }
 
    // 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 = ::get(in_edges, callee);
        return callees != nullptr && !callees->empty();
    }
    bool isCaller(T caller) const {
        auto edges = ::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());
    }
    size_t size() const { return nodes.size(); }
    // 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);
    }
 
    typedef std::unordered_set<T> Set;
 
    // 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_ */