live_range_shrinking.h

 
#ifndef BACKENDS_TOFINO_BF_P4C_PHV_ANALYSIS_LIVE_RANGE_SHRINKING_H_
#define BACKENDS_TOFINO_BF_P4C_PHV_ANALYSIS_LIVE_RANGE_SHRINKING_H_
 
#include "backends/tofino/bf-p4c/common/field_defuse.h"
#include "backends/tofino/bf-p4c/common/map_tables_to_actions.h"
#include "backends/tofino/bf-p4c/mau/table_dependency_graph.h"
#include "backends/tofino/bf-p4c/mau/table_flow_graph.h"
#include "backends/tofino/bf-p4c/mau/table_mutex.h"
#include "backends/tofino/bf-p4c/phv/action_phv_constraints.h"
#include "backends/tofino/bf-p4c/phv/analysis/dominator_tree.h"
#include "backends/tofino/bf-p4c/phv/analysis/meta_live_range.h"
#include "backends/tofino/bf-p4c/phv/mau_backtracker.h"
#include "backends/tofino/bf-p4c/phv/phv_fields.h"
#include "backends/tofino/bf-p4c/phv/pragma/pa_no_init.h"
#include "backends/tofino/bf-p4c/phv/transforms/auto_alias.h"
#include "backends/tofino/bf-p4c/phv/utils/utils.h"
 
class FindInitializationNode : public Inspector {
 private:
    const BuildDominatorTree &domTree;
    const PhvInfo &phv;
    const FieldDefUse &defuse;
    const DependencyGraph &dg;
    const ordered_set<const PHV::Field *> &noInit;
    const MapTablesToActions &tablesToActions;
    const MetadataLiveRange &metaLiveMap;
    const ActionPhvConstraints &actionConstraints;
    const TablesMutuallyExclusive &tableMutex;
    const ordered_map<gress_t, FlowGraph> &flowGraph;
    const DetermineCandidateHeaders &noInitPacketFields;
    const MauBacktracker &tableAlloc;
 
    // therefore, cannot have a bitmasked-set operation in them).
    // TODO: For now, disable initialization at all such actions (and tables that contain those
    // actions). In the longer term, change this to recognize when a bitmasked-set operation/action
    // data is necessary to realize the initialization operation.
    ordered_set<const IR::MAU::Action *> doNotInitActions;
 
    int maxStages = -1;
 
    profile_t init_apply(const IR::Node *root) override;
    bool preorder(const IR::MAU::Table *tbl) override;
    bool preorder(const IR::MAU::Action *act) override;
 
    bool ignoreDeparserUseForPacketField(const PHV::Field *f,
                                         const PHV::UnitSet &f_dominators) const;
 
    bool summarizeUseDefs(
        const PHV::Field *f, const ordered_set<const IR::BFN::Unit *> &initPoints,
        ordered_map<const PHV::Field *, ordered_map<const IR::BFN::Unit *, unsigned>> &units,
        PHV::UnitSet &f_dominators) const;
 
    bool canInitTableReachGUnits(const IR::MAU::Table *table, const PHV::UnitSet &g_units) const;
 
    bool canFUsesReachInitTable(const IR::MAU::Table *initTable, const PHV::UnitSet &f_units) const;
 
    std::optional<const PHV::ActionSet> getInitializationCandidates(
        const PHV::Container &c, const PHV::Field *f, const IR::MAU::Table *t,
        const ordered_map<const IR::BFN::Unit *, unsigned> &u, const int lastAllowedStage,
        const ordered_set<const IR::MAU::Table *> &fStrictDominators, const PHV::Field *prevField,
        const ordered_map<const PHV::Field *, PHV::UnitSet> &g_units,
        const PHV::Allocation::MutuallyLiveSlices &container_state,
        const PHV::Transaction &alloc) const;
 
    bool mayViolatePackConflict(const IR::MAU::Table *initTable, const PHV::Field *initField,
                                const PHV::Allocation::MutuallyLiveSlices &container_state,
                                const PHV::Transaction &alloc) const;
 
    std::optional<const PHV::ActionSet> getInitPointsForTable(
        const PHV::Container &c, const IR::MAU::Table *t, const PHV::Field *f,
        const ordered_set<const IR::MAU::Table *> &prevUses,
        const PHV::Allocation::MutuallyLiveSlices &container_state, const PHV::Transaction &alloc,
        bool ignoreMutex = false) const;
 
    bool increasesDependenceCriticalPath(const IR::MAU::Table *use,
                                         const IR::MAU::Table *init) const;
 
    ordered_set<const IR::MAU::Table *> getTableUsesForField(const PHV::Field *f, bool uses = true,
                                                             bool defs = true) const;
 
    bool filterOutMutexFields(std::vector<const PHV::Field *> &fields,
                              const ordered_map<int, std::pair<int, int>> &livemap) const;
 
    bool cannotInitInAction(const PHV::Container &c, const IR::MAU::Action *action,
                            const PHV::Transaction &alloc) const;
 
 public:
    std::optional<PHV::Allocation::LiveRangeShrinkingMap> findInitializationNodes(
        const PHV::Container c, const ordered_set<PHV::AllocSlice> &alloced,
        const PHV::Transaction &alloc,
        const PHV::Allocation::MutuallyLiveSlices &container_state) const;
 
    cstring printLiveRangeShrinkingMap(const PHV::Allocation::LiveRangeShrinkingMap &m,
                                       cstring indent) const;
 
    explicit FindInitializationNode(const BuildDominatorTree &d, const PhvInfo &p,
                                    const FieldDefUse &u, const DependencyGraph &g,
                                    const ordered_set<const PHV::Field *> &i,
                                    const MapTablesToActions &t, const MetadataLiveRange &l,
                                    const ActionPhvConstraints &a, const TablesMutuallyExclusive &m,
                                    const ordered_map<gress_t, FlowGraph> &fg,
                                    const DetermineCandidateHeaders &c, const MauBacktracker &bt)
        : domTree(d),
          phv(p),
          defuse(u),
          dg(g),
          noInit(i),
          tablesToActions(t),
          metaLiveMap(l),
          actionConstraints(a),
          tableMutex(m),
          flowGraph(fg),
          noInitPacketFields(c),
          tableAlloc(bt) {}
};
 
class LiveRangeShrinking : public PassManager {
 private:
    TablesMutuallyExclusive tableMutex;
    MapTablesToActions tableActionsMap;
    DetermineCandidateHeaders noInitPacketFields;
    FindInitializationNode initNode;
 
 public:
    const MapTablesToActions &getTableActionsMap() const { return tableActionsMap; }
 
    std::optional<PHV::Allocation::LiveRangeShrinkingMap> findInitializationNodes(
        const ordered_set<PHV::AllocSlice> &alloced, const PHV::Transaction &alloc,
        const PHV::Allocation::MutuallyLiveSlices &container_state) const {
        PHV::Container c;
        for (auto &sl : alloced) {
            if (c == PHV::Container()) {
                c = sl.container();
            } else {
                BUG_CHECK(c == sl.container(),
                          "Containers for metadata overlay candidates are different");
            }
        }
        BUG_CHECK(c != PHV::Container(),
                  "Container candidate for metadata overlay cannot be NULL.");
        return initNode.findInitializationNodes(c, alloced, alloc, container_state);
    }
 
    std::optional<PHV::Allocation::LiveRangeShrinkingMap> findInitializationNodes(
        const ordered_set<PHV::AllocSlice> &alloced, const PHV::AllocSlice &slice,
        const PHV::Transaction &alloc,
        const PHV::Allocation::MutuallyLiveSlices &container_state) const {
        ordered_set<PHV::AllocSlice> candidates;
        candidates.insert(alloced.begin(), alloced.end());
        candidates.insert(slice);
        return findInitializationNodes(candidates, alloc, container_state);
    }
 
    cstring printLiveRangeShrinkingMap(const PHV::Allocation::LiveRangeShrinkingMap &m,
                                       cstring indent) const {
        return initNode.printLiveRangeShrinkingMap(m, indent);
    }
 
    explicit LiveRangeShrinking(const PhvInfo &p, const FieldDefUse &u, const DependencyGraph &g,
                                const PragmaNoInit &i, const MetadataLiveRange &l,
                                const ActionPhvConstraints &a, const BuildDominatorTree &d,
                                const MauBacktracker &bt);
};
 
#endif /* BACKENDS_TOFINO_BF_P4C_PHV_ANALYSIS_LIVE_RANGE_SHRINKING_H_ */