midend/def_use.h

/*
Copyright 2024 Intel Corp.
 
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 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);
        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::AssignmentStatement *) 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;
    }
};
 
}  // 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_ */