commonInlining.h

/*
 * Copyright 2018 VMware, Inc.
 * SPDX-FileCopyrightText: 2018 VMware, Inc.
 *
 * SPDX-License-Identifier: Apache-2.0
 */
 
#ifndef FRONTENDS_P4_COMMONINLINING_H_
#define FRONTENDS_P4_COMMONINLINING_H_
 
#include "frontends/common/resolveReferences/resolveReferences.h"
#define DEBUG_INLINER 0
 
#if DEBUG_INLINER
#include "frontends/p4/toP4/toP4.h"
#endif
#include "frontends/p4/callGraph.h"
#include "ir/ir.h"

 
namespace P4 {
 
using namespace literals;
 
template <class CallableT, class CallNodeT, class CallExpressionT = IR::MethodCallExpression>
class SimpleCallInfo : public IHasDbPrint {
    // Callable can be P4Action, Function, P4Control, P4Parser
 public:
    using Callable = CallableT;
    using CallNode = CallNodeT;
    using CallExpression = CallExpressionT;
 
    const Callable *caller;  // object that performs the call
    const Callable *callee;  // object that is called
    const CallNode *call;
    const CallExpression *callExpr;
 
    SimpleCallInfo(const Callable *caller, const Callable *callee, const CallNode *call,
                   const CallExpression *expr)
        : caller(caller), callee(callee), call(call), callExpr(expr) {
        CHECK_NULL(caller);
        CHECK_NULL(callee);
        CHECK_NULL(call);
        CHECK_NULL(callExpr);
    }
    void dbprint(std::ostream &out) const {
        out << dbp(callee) << " into " << dbp(caller) << " at " << dbp(call) << " via "
            << dbp(callExpr);
    }
};
 
template <class CallInfo>
class SimpleInlineWorkList : public IHasDbPrint {
 public:
    using ReplacementMap = std::map<
        const typename CallInfo::CallNode *,
        std::pair<const typename CallInfo::Callable *, const typename CallInfo::CallExpression *>>;
    // Map caller -> statement -> callee
    std::map<const typename CallInfo::Callable *, ReplacementMap> sites;
    void add(CallInfo *info) {
        CHECK_NULL(info);
        LOG3(info);
        sites[info->caller][info->call] = {info->callee, info->callExpr};
    }
    void dbprint(std::ostream &out) const {
        for (auto t : sites) {
            out << dbp(t.first);
            for (auto c : t.second) {
                out << std::endl
                    << "\t" << dbp(c.first) << " => " << dbp(c.second.first) << " via "
                    << dbp(c.second.second);
            }
        }
    }
    bool empty() const { return sites.empty(); }
};
 
template <class Callable, class CallInfo, class InlineWorkList>
class SimpleInlineList {
    std::vector<CallInfo *> toInline;     // initial data
    std::vector<CallInfo *> inlineOrder;  // sorted in inlining order
 
 public:
    // generate the inlining order
    void analyze() {
        // We only keep the call graph between objects of the same kind.
        P4::CallGraph<const Callable *> cg("Call-graph");
        for (auto c : toInline) cg.calls(c->caller, c->callee);
 
        // must inline from leaves up
        std::vector<const Callable *> order;
        cg.sort(order);
        for (auto c : order) {
            // This is quadratic, but hopefully the call graph is not too large
            for (auto ci : toInline) {
                if (ci->caller == c) inlineOrder.push_back(ci);
            }
        }
 
        std::reverse(inlineOrder.begin(), inlineOrder.end());
    }
 
    size_t size() const { return toInline.size(); }
    void clear() {
        toInline.clear();
        inlineOrder.clear();
    }

    InlineWorkList *next() {
        if (inlineOrder.size() == 0) return nullptr;
 
        std::set<const Callable *> callers;
        auto result = new InlineWorkList();
 
        // Find callables that can be inlined simultaneously.
        // This traversal is in topological order starting from leaf callees.
        // We stop at the first callable which calls one of the callables
        // we have already selected.
        while (!inlineOrder.empty()) {
            auto last = inlineOrder.back();
            if (callers.find(last->callee) != callers.end()) break;
            inlineOrder.pop_back();
            result->add(last);
            callers.emplace(last->caller);
        }
        BUG_CHECK(!result->empty(), "Empty list of methods to inline");
        return result;
    }
 
    void add(CallInfo *aci) { toInline.push_back(aci); }
 
    void replace(const Callable *container, const Callable *replacement) {
        LOG2("Substituting " << container << " with " << replacement);
        for (auto e : inlineOrder) {
            if (e->callee == container) e->callee = replacement;
            if (e->caller == container) e->caller = replacement;
        }
    }
};
 
// Base class for inliners
template <class InlineList, class InlineWorkList>
class AbstractInliner : public Transform, public ResolutionContext {
 protected:
    InlineList *list;
    InlineWorkList *toInline;
    AbstractInliner() : list(nullptr), toInline(nullptr) {}
 
 public:
    void prepare(InlineList *list, InlineWorkList *toInline) {
        CHECK_NULL(list);
        CHECK_NULL(toInline);
        this->list = list;
        this->toInline = toInline;
    }
    Visitor::profile_t init_apply(const IR::Node *node) {
        LOG2("AbstractInliner " << toInline);
        return Transform::init_apply(node);
    }
    virtual ~AbstractInliner() {}
};
 
template <class InlineList, class InlineWorkList>
class InlineDriver : public Visitor {
    InlineList *toInline;
    AbstractInliner<InlineList, InlineWorkList> *inliner;
 
 public:
    InlineDriver(InlineList *toInline, AbstractInliner<InlineList, InlineWorkList> *inliner)
        : toInline(toInline), inliner(inliner) {
        CHECK_NULL(toInline);
        CHECK_NULL(inliner);
        setName(("InlineDriver_"_cs + cstring(inliner->name())).c_str());
    }
    const IR::Node *apply_visitor(const IR::Node *program, const char * = 0) override {
        LOG2("InlineDriver");
        toInline->analyze();
        LOG3("InlineList size " << toInline->size());
        while (auto todo = toInline->next()) {
            LOG2("Processing " << todo);
            inliner->prepare(toInline, todo);
            program = program->apply(*inliner);
            if (::P4::errorCount() > 0) break;
 
#if DEBUG_INLINER
            // debugging code; we don't have an easy way to dump the program here,
            // since we are not between passes
            ToP4 top4(&std::cout, false, nullptr);
            program->apply(top4);
#endif
        }
        return program;
    }
};
 
}  // namespace P4
 
#endif /* FRONTENDS_P4_COMMONINLINING_H_ */