midend/def_use.h

/*
 * Copyright 2024 Intel Corp.
 * SPDX-FileCopyrightText: 2024 Intel Corp.
 *
 * SPDX-License-Identifier: Apache-2.0
 */
 
#ifndef MIDEND_DEF_USE_H_
#define MIDEND_DEF_USE_H_
 
#include "frontends/common/resolveReferences/resolveReferences.h"
#include "ir/ir.h"
#include "lib/bitrange.h"
#include "lib/hvec_map.h"
#include "lib/hvec_set.h"
 
namespace P4 {

class ComputeDefUse : public Inspector,
                      public ControlFlowVisitor,
                      public P4WriteContext,
                      public P4::ResolutionContext {
    static int uid_ctr;
    int uid = 0;
    ComputeDefUse *clone() const override {
        auto *rv = new ComputeDefUse(*this);
        rv->uid = ++uid_ctr;
        LOG8("ComputeDefUse::clone " << rv->uid << " <- " << uid);
        return rv;
    }
    void flow_merge(Visitor &) override;
    void flow_copy(ControlFlowVisitor &) override;
    bool operator==(const ControlFlowVisitor &) const override;
 
    enum { SKIPPING, NORMAL, READ_ONLY, WRITE_ONLY } state = SKIPPING;
 
 public:
    // a location in the program.  Includes the context from the visitor, which needs to
    // be copied out of the Visitor::Context objects, as they are allocated on the stack and
    // will become invalid as the IR traversal continues
    struct loc_t {
        const IR::Node *node;
        const loc_t *parent;
        mutable size_t computedHash = 0;
        bool operator<(const loc_t &a) const {
            if (node != a.node) return node->id < a.node->id;
            if (!parent || !a.parent) return parent != nullptr;
            return *parent < *a.parent;
        }
        bool operator==(const loc_t &a) const {
            if (node != a.node) return false;
            if (parent == a.parent) return true;
            if (!parent || !a.parent) return false;
            return *parent == *a.parent;
        }
        std::size_t hash() const {
            if (!computedHash) {
                if (!parent)
                    computedHash = Util::Hash{}(node->id);
                else
                    computedHash = Util::Hash{}(node->id, parent->hash());
            }
            return computedHash;
        }
 
        template <class T>
        const T *find() const {
            for (auto *p = this; p; p = p->parent) {
                if (auto *t = p->node->to<T>()) return t;
            }
            return nullptr;
        }
    };
    typedef hvec_set<const loc_t *> locset_t;
 
 private:
    // DANGER -- pointers to elements of this set must be stable
    std::unordered_set<loc_t> &cached_locs;
    const loc_t *getLoc(const Visitor::Context *ctxt);
    const loc_t *getLoc() { return getLoc(getChildContext()); }
    const loc_t *getLoc(const IR::Node *, const Visitor::Context *);
    const loc_t *getLoc(const IR::Node *n) { return getLoc(n, getChildContext()); }
 
    // flow tracking info about defs live at the point we are currently visiting
    struct def_info_t {
        // definitions of a symbol (or part of a symbol) visible at this point in the
        // program.  `defs` will be empty if `live` is; if not those defs are visible only
        // for those bits/elements/fields where live is set.
        locset_t defs;
        bitvec live;
        // FIXME -- this parent field is never used and is not set consistently, so
        // appears to be useless?
        def_info_t *parent = nullptr;
        // track valid bit access for headers separate from the rest of the header
        locset_t valid_bit_defs;
        // one of these maps will always be empty.
        std::map<cstring, def_info_t> fields;
        std::map<le_bitrange, def_info_t> slices;  // also used for arrays
        // keys in slices are always non-overlapping (checked by slices_sanity)
        void slices_sanity();
        std::map<le_bitrange, def_info_t>::iterator slices_overlap_begin(le_bitrange);
        void erase_slice(le_bitrange);
        void split_slice(le_bitrange);
        void flow_merge(def_info_t &);
        bool operator==(const def_info_t &) const;
        bool operator!=(const def_info_t &a) const { return !(*this == a); }
        def_info_t() = default;
        def_info_t(const def_info_t &);
        def_info_t(def_info_t &&);
        def_info_t &operator=(const def_info_t &);
        def_info_t &operator=(def_info_t &&);
    };
    hvec_map<const IR::IDeclaration *, def_info_t> def_info;
    void add_uses(const loc_t *, def_info_t &);
    void set_live_from_type(def_info_t &di, const IR::Type *type);
 
    // computed defuse info for all uses and defs in the program
    struct defuse_t {
        // defs maps from all uses to their definitions
        // uses maps from all definitions to their uses
        // uses/defs are lvalue expressions, or param declarations.
        hvec_map<const IR::Node *, locset_t> defs;
        hvec_map<const IR::Node *, locset_t> uses;
    } & defuse;
    static const locset_t empty;
 
    profile_t init_apply(const IR::Node *root) override {
        auto rv = Inspector::init_apply(root);
        LOG3("## Midend ComputeDefUse");
        uid_ctr = 0;
        state = SKIPPING;
        clear();
        return rv;
    }
    bool preorder(const IR::P4Control *) override;
    bool preorder(const IR::P4Table *) override;
    bool preorder(const IR::P4Action *) override;
    bool preorder(const IR::P4Parser *) override;
    bool preorder(const IR::Function *) override;
    bool preorder(const IR::ParserState *) override;
    void revisit(const IR::ParserState *) override;
    void loop_revisit(const IR::ParserState *) override;
    void postorder(const IR::ParserState *) override;
    bool preorder(const IR::Type *) override { return false; }
    bool preorder(const IR::Vector<IR::Annotation> *) override { return false; }
    bool preorder(const IR::KeyElement *) override;
    bool preorder(const IR::BaseAssignmentStatement *) override;
    const IR::Expression *do_read(def_info_t &, const IR::Expression *, const Context *);
    const IR::Expression *do_write(def_info_t &, const IR::Expression *, const Context *);
    bool preorder(const IR::PathExpression *) override;
    void loop_revisit(const IR::PathExpression *) override;
    bool preorder(const IR::MethodCallExpression *) override;
    void end_apply() override;
 
    class SetupJoinPoints;
    void applySetupJoinPoints(const IR::Node *root) override;
    bool filter_join_point(const IR::Node *) override;
 
 public:
    ComputeDefUse();
    void clear();
 
    const locset_t &getDefs(const IR::Node *n) const {
        auto it = defuse.defs.find(n);
        return it == defuse.defs.end() ? empty : it->second;
    }
    const locset_t &getUses(const IR::Node *n) const {
        auto it = defuse.uses.find(n);
        return it == defuse.uses.end() ? empty : it->second;
    }
 
    // for debugging
    friend std::ostream &operator<<(std::ostream &, const loc_t &);
    friend std::ostream &operator<<(std::ostream &, const defuse_t &);
    friend std::ostream &operator<<(std::ostream &out, const ComputeDefUse &cdu) {
        return out << cdu.defuse;
    }
};
 
std::ostream &operator<<(std::ostream &, const hvec_set<const ComputeDefUse::loc_t *> &);
 
}  // namespace P4
 
namespace std {
template <>
struct hash<P4::ComputeDefUse::loc_t> {
    std::size_t operator()(const P4::ComputeDefUse::loc_t &loc) const { return loc.hash(); }
};
 
}  // namespace std
 
#endif /* MIDEND_DEF_USE_H_ */