make_clusters.h

 
#ifndef BF_P4C_PHV_MAKE_CLUSTERS_H_
#define BF_P4C_PHV_MAKE_CLUSTERS_H_
 
#include "bf-p4c/common/field_defuse.h"
#include "bf-p4c/ir/bitrange.h"
#include "bf-p4c/ir/thread_visitor.h"
#include "bf-p4c/ir/tofino_write_context.h"
#include "bf-p4c/lib/union_find.hpp"
#include "bf-p4c/mau/gateway.h"
#include "bf-p4c/mau/table_dependency_graph.h"
#include "bf-p4c/mau/table_mutex.h"
#include "bf-p4c/phv/action_phv_constraints.h"
#include "bf-p4c/phv/alloc_setting.h"
#include "bf-p4c/phv/analysis/pack_conflicts.h"
#include "bf-p4c/phv/phv.h"
#include "bf-p4c/phv/phv_parde_mau_use.h"
#include "bf-p4c/phv/pragma/pa_byte_pack.h"
#include "bf-p4c/phv/pragma/pa_container_size.h"
#include "bf-p4c/phv/utils/utils.h"
#include "ir/ir.h"
#include "ir/visitor.h"
#include "lib/map.h"
#include "lib/ordered_map.h"
#include "lib/ordered_set.h"
#include "lib/range.h"
 
namespace PHV {
class Field;
}  // namespace PHV
 
class PhvInfo;
 
class Clustering : public PassManager {
    PhvInfo &phv_i;
    PhvUse &uses_i;
    const PackConflicts &conflicts_i;
    const PragmaContainerSize &pa_container_sizes_i;
    const PragmaBytePack &pa_byte_pack_i;
    const FieldDefUse &defuse_i;
    const DependencyGraph &deps_i;
    const TablesMutuallyExclusive &table_mutex_i;
    const PHV::AllocSetting &settings_i;
 
    std::list<PHV::AlignedCluster *> aligned_clusters_i;
 
    std::list<PHV::RotationalCluster *> rotational_clusters_i;
 
    std::list<PHV::SuperCluster *> super_clusters_i;
 
    assoc::hash_map<const PHV::Field *, assoc::hash_set<const PHV::Field *>>
        inconsistent_extract_no_packs_i;
 
    ordered_map<const PHV::Field *, std::list<PHV::FieldSlice>> fields_to_slices_i;
 
    UnionFind<const PHV::Field *> complex_validity_bits_i;
 
    std::vector<PHV::FieldSlice> slices(const PHV::Field *field, le_bitrange range) const;
 
    PHV::RotationalCluster *insert_rotational_cluster(PHV::Field *f);
 
    class ClearClusteringStructs : public Inspector {
        Clustering &self;
        Visitor::profile_t init_apply(const IR::Node *node) override;
 
     public:
        explicit ClearClusteringStructs(Clustering &self) : self(self) {}
    };
 
    class FindComplexValidityBits : public Inspector {
        Clustering &self;
        PhvInfo &phv_i;
 
        bool preorder(const IR::MAU::Instruction *) override;
        void end_apply() override;
 
     public:
        explicit FindComplexValidityBits(Clustering &self) : self(self), phv_i(self.phv_i) {}
    };
 
    class MakeSlices : public Inspector {
        Clustering &self;
        PhvInfo &phv_i;
        const PragmaContainerSize &pa_sizes_i;
 
        std::vector<ordered_set<PHV::FieldSlice>> equivalences_i;
 
        profile_t init_apply(const IR::Node *root) override;
 
        bool preorder(const IR::MAU::Table *tbl) override;
 
        bool preorder(const IR::Expression *) override;
 
        void postorder(const IR::MAU::Instruction *) override;
 
        // TODO: Add a check for shrinking casts that fails if any are
        // detected.
 
        void end_apply() override;
 
     public:
        explicit MakeSlices(Clustering &self, const PragmaContainerSize &pa)
            : self(self), phv_i(self.phv_i), pa_sizes_i(pa) {}
 
        bool updateSlices(const PHV::Field *field, le_bitrange range);
    };
 
    MakeSlices slice_i;
 
    class MakeAlignedClusters : public Inspector {
        Clustering &self;
        PhvInfo &phv_i;
        const PhvUse &uses_i;
 
        UnionFind<PHV::FieldSlice> union_find_i;
 
        profile_t init_apply(const IR::Node *root) override;
 
        bool preorder(const IR::MAU::Instruction *inst) override;
 
        bool preorder(const IR::MAU::Table *tbl) override;
 
        void end_apply() override;
 
     public:
        explicit MakeAlignedClusters(Clustering &self)
            : self(self), phv_i(self.phv_i), uses_i(self.uses_i) {}
    };
 
    class MakeRotationalClusters : public Inspector {
        Clustering &self;
        PhvInfo &phv_i;
 
        UnionFind<PHV::AlignedCluster *> union_find_i;
 
        ordered_map<const PHV::FieldSlice, PHV::AlignedCluster *> slices_to_clusters_i;
 
        Visitor::profile_t init_apply(const IR::Node *) override;
 
        bool preorder(const IR::MAU::Instruction *) override;
 
        void end_apply() override;
 
     public:
        explicit MakeRotationalClusters(Clustering &self) : self(self), phv_i(self.phv_i) {}
    };
 
    class CollectInconsistentFlexibleFieldExtract : public Inspector {
        Clustering &self;
        const PhvInfo &phv_i;
        std::map<int, std::vector<const PHV::Field *>> headers_i;
        using ExtractVec = std::set<std::pair<nw_bitrange, const PHV::Field *>>;
        std::vector<ExtractVec> extracts_i;
 
        Visitor::profile_t init_apply(const IR::Node *root) override {
            auto rv = Inspector::init_apply(root);
            headers_i.clear();
            extracts_i.clear();
            return rv;
        }
 
        void save_header_layout(const IR::HeaderRef *hr);
        bool preorder(const IR::ConcreteHeaderRef *) override;
        bool preorder(const IR::HeaderStackItemRef *) override;
        bool preorder(const IR::BFN::ParserState *state) override;
        void end_apply() override;
 
     public:
        explicit CollectInconsistentFlexibleFieldExtract(Clustering &self, const PhvInfo &phv)
            : self(self), phv_i(phv) {}
    };
 
    class CollectPlaceTogetherConstraints : public Inspector {
        Clustering &self;
        PhvInfo &phv_i;
        const PackConflicts &conflicts_i;
        const ActionPhvConstraints &actions_i;
        const CollectInconsistentFlexibleFieldExtract &inconsistent_extract_i;
 
        // Reason of why fieldslices must be placed together.
        // NOTE: the lower the number, the higher the priority(more constraints).
        // This priority is used by the solver algorithm.
        enum class Reason : int {
            PaBytePack = 0,       // pa_byte_pack pragma
            Header = 1,           // parsed + deparsed
            Resubmit = 2,         // 8-bytes limit + deparsed
            Mirror = 3,           // deparsed
            Learning = 4,         // no_pack in same byte, handled in phv_fields: aligment = 0
            Pktgen = 5,           // unknown
            BridgedTogether = 6,  // egress metadata that are bridged together
            ConstrainedMeta = 7,  // metadata with constraints like solitary needs to in a list.
            PaContainerSize = 8,  // metadata with pa_container_size pragmas.
        };
 
        std::map<Reason, std::vector<PHV::SuperCluster::SliceList *>> place_together_i;
 
        ordered_set<PHV::SuperCluster::SliceList *> slice_lists_i;
 
        ordered_set<int> headers_i;
 
        ordered_set<PHV::SuperCluster::SliceList *> bridged_extracted_together_i;
 
        Visitor::profile_t init_apply(const IR::Node *root) override {
            auto rv = Inspector::init_apply(root);
            place_together_i.clear();
            slice_lists_i.clear();
            headers_i.clear();
            bridged_extracted_together_i.clear();
            return rv;
        };
 
        void end_apply() override;
 
        void solve_place_together_constraints();
 
        void pack_pa_byte_pack_and_update_alignment();
 
        void pack_pa_container_sized_metadata();
 
        void pack_constrained_metadata();
 
        void pack_bridged_extracted_together();
 
        void pack_pov_bits();
 
        void visit_header_ref(const IR::HeaderRef *hr);
 
        void visit_digest_fieldlist(const IR::BFN::DigestFieldList *fl, int skip, Reason reason);
 
        bool preorder(const IR::ConcreteHeaderRef *) override;
 
        bool preorder(const IR::HeaderStackItemRef *) override;
 
        bool preorder(const IR::BFN::Digest *) override;
 
        bool preorder(const IR::BFN::ParserState *state) override;
 
     public:
        explicit CollectPlaceTogetherConstraints(
            Clustering &self, const ActionPhvConstraints &actions,
            const CollectInconsistentFlexibleFieldExtract &inconsistent)
            : self(self),
              phv_i(self.phv_i),
              conflicts_i(self.conflicts_i),
              actions_i(actions),
              inconsistent_extract_i(inconsistent) {}
 
        ordered_set<PHV::SuperCluster::SliceList *> get_slice_lists() const {
            return slice_lists_i;
        }
    };
 
    class MakeSuperClusters : public Inspector {
        Clustering &self;
        PhvInfo &phv_i;
        const CollectPlaceTogetherConstraints &place_togethers_i;
 
        Visitor::profile_t init_apply(const IR::Node *) override;
 
        void end_apply() override;
 
        void addPaddingForMarshaledFields(ordered_set<const PHV::RotationalCluster *> &cluster_set,
                                          ordered_set<PHV::SuperCluster::SliceList *> &slice_lists);
 
     public:
        explicit MakeSuperClusters(Clustering &self,
                                   const CollectPlaceTogetherConstraints &place_togethers)
            : self(self), phv_i(self.phv_i), place_togethers_i(place_togethers) {}
    };
 
    class ValidateClusters : public Inspector {
     private:
        Clustering &self;
        const MauBacktracker &mau_bt;
 
        profile_t init_apply(const IR::Node *root) override;
 
        // basic checks: slicelist is not empty, no duplicated fieldslices.
        static void validate_basics(const std::list<PHV::SuperCluster *> &clusters);
 
        static void validate_deparsed_zero_clusters(const std::list<PHV::SuperCluster *> &clusters);
 
        // size % 8 = 0 if exact_containers
        static std::optional<cstring> validate_exact_container_lists(
            const std::list<PHV::SuperCluster *> &clusters, const PhvUse &uses);
 
        // alignments of fieldslices in list must be all sat.
        static void validate_alignments(const std::list<PHV::SuperCluster *> &clusters,
                                        const PhvUse &uses);
 
        // inconsistent extractions cannot share fields in a same byte of a header.
        static void validate_extract_from_flexible(
            const std::list<PHV::SuperCluster *> &clusters,
            std::function<bool(const PHV::Field *a, const PHV::Field *b)> no_pack);
 
        // if field->same_container_group, then all the fieldslices of the field must
        // be in the same super cluster.
        static void validate_same_container_group_fields(
            const std::list<PHV::SuperCluster *> &clusters,
            const ordered_map<const PHV::Field *, std::list<PHV::FieldSlice>> &field_to_slices);
 
     public:
        explicit ValidateClusters(Clustering &c, const MauBacktracker &mau_bt)
            : self(c), mau_bt(mau_bt) {}
    };
 
    class UpdateSameContainerAllocConstraint : public Inspector {
     private:
        Clustering &self;
 
        profile_t init_apply(const IR::Node *root) override;
 
     public:
        explicit UpdateSameContainerAllocConstraint(Clustering &c) : self(c) {}
    };
 
 public:
    Clustering(PhvInfo &p, PhvUse &u, const PackConflicts &c, const PragmaContainerSize &pa_sz,
               const PragmaBytePack &pa_byte_pack, const ActionPhvConstraints &a,
               const FieldDefUse &defuse, const DependencyGraph &deps,
               const TablesMutuallyExclusive &table_mutex, const PHV::AllocSetting &settings,
               const MauBacktracker &mau_bt)
        : phv_i(p),
          uses_i(u),
          conflicts_i(c),
          pa_container_sizes_i(pa_sz),
          pa_byte_pack_i(pa_byte_pack),
          defuse_i(defuse),
          deps_i(deps),
          table_mutex_i(table_mutex),
          settings_i(settings),
          slice_i(*this, pa_sz) {
        auto *inconsistent_extracts =
            new CollectInconsistentFlexibleFieldExtract(*this, this->phv_i);
        auto *place_togethers =
            new CollectPlaceTogetherConstraints(*this, a, *inconsistent_extracts);
        addPasses({
            new ClearClusteringStructs(*this),   // clears pre-existing maps
            new FindComplexValidityBits(*this),  // populates complex_validity_bits_i
            &slice_i,
            new MakeAlignedClusters(*this),     // populates aligned_clusters_i
            new MakeRotationalClusters(*this),  // populates rotational_clusters_i
            inconsistent_extracts, place_togethers,
            new MakeSuperClusters(*this, *place_togethers),  // populates super_clusters_i
            new ValidateClusters(*this, mau_bt),             // validate clustering is correct.
            new UpdateSameContainerAllocConstraint(*this)    // update SameContainerAllocConstraint
        });
    }
 
    const std::list<PHV::SuperCluster *> &cluster_groups() const { return super_clusters_i; }
 
    bool no_pack(const PHV::Field *a, const PHV::Field *b) const {
        return inconsistent_extract_no_packs_i.count(a) &&
               inconsistent_extract_no_packs_i.at(a).count(b);
    }
};
 
#endif /* BF_P4C_PHV_MAKE_CLUSTERS_H_ */