phv/utils/utils.h

 
#ifndef BF_P4C_PHV_UTILS_UTILS_H_
#define BF_P4C_PHV_UTILS_UTILS_H_
 
#include <optional>
 
#include "bf-p4c/ir/bitrange.h"
#include "bf-p4c/ir/gress.h"
#include "bf-p4c/phv/error.h"
#include "bf-p4c/phv/phv.h"
#include "bf-p4c/phv/phv_fields.h"
#include "bf-p4c/phv/pragma/pa_no_init.h"
#include "bf-p4c/phv/utils/slice_alloc.h"
#include "lib/bitvec.h"
#include "lib/symbitmatrix.h"
 
namespace PHV {
 
class ContainerGroup {
    const PHV::Size size_i;
 
    std::set<PHV::Type> types_i;
 
    std::vector<PHV::Container> containers_i;
 
    bitvec ids_i;
 
 public:
    ContainerGroup(PHV::Size size, const std::vector<PHV::Container> containers);
 
    ContainerGroup(PHV::Size size, bitvec container_group);
 
    using const_iterator = std::vector<PHV::Container>::const_iterator;
    const_iterator begin() const { return containers_i.begin(); }
    const_iterator end() const { return containers_i.end(); }
 
    bool empty() const { return containers_i.empty(); }
 
    size_t size() const { return containers_i.size(); }
 
    PHV::Size width() const { return size_i; }
 
    const std::set<PHV::Type> types() const { return types_i; }
 
    bool hasType(PHV::Type t) const { return types_i.count(t); }
 
    bool is(PHV::Kind k) const {
        for (auto t : types_i)
            if (t.kind() == k) return true;
        return false;
    }
 
    bool is(PHV::Size s) const { return s == size_i; }
 
    bitvec ids() const { return ids_i; }
 
    bool contains(PHV::Container c) const {
        return std::find(containers_i.begin(), containers_i.end(), c) != containers_i.end();
    }
 
    const ordered_set<PHV::Container> getAllContainersOfKind(PHV::Kind kind) const {
        ordered_set<PHV::Container> rs;
        for (auto c : containers_i)
            if (c.is(kind)) rs.insert(c);
        return rs;
    }
};
 
using DarkInitMap = std::vector<DarkInitEntry>;
 
// TODO: Better way to structure Transactions to avoid this circular
// dependency?
class Transaction;
 
class Allocation {
 public:
    friend class AllocationReport;
 
    using GressAssignment = std::optional<gress_t>;
    using MutuallyLiveSlices = ordered_set<AllocSlice>;
    using LiveRangeShrinkingMap = ordered_map<const PHV::Field *, ActionSet>;
    enum class ContainerAllocStatus { EMPTY, PARTIAL, FULL };
    enum class ExtractSource { NONE, PACKET, NON_PACKET };
 
    struct ContainerStatus {
        GressAssignment gress;
        GressAssignment parserGroupGress;
        GressAssignment deparserGroupGress;
        ordered_set<AllocSlice> slices;
        ContainerAllocStatus alloc_status;
        ExtractSource parserExtractGroupSource;
    };
 
    using const_iterator = ordered_map<PHV::Container, ContainerStatus>::const_iterator;
 
    struct ConditionalConstraintData {
        int bitPosition;
        bool rotationAllowed;
        std::optional<PHV::Container> container;
 
        explicit ConditionalConstraintData(int bit, PHV::Container c, bool rotate = false)
            : bitPosition(bit), rotationAllowed(rotate), container(c) {}
 
        explicit ConditionalConstraintData(int bit, bool rotate = false)
            : bitPosition(bit), rotationAllowed(rotate), container(std::nullopt) {}
 
        ConditionalConstraintData()
            : bitPosition(-1), rotationAllowed(false), container(std::nullopt) {}
 
        bool operator==(ConditionalConstraintData &other) const {
            return bitPosition == other.bitPosition && rotationAllowed == other.rotationAllowed &&
                   container == other.container;
        }
    };
 
    using ConditionalConstraint = ordered_map<PHV::FieldSlice, ConditionalConstraintData>;
    using ConditionalConstraints = ordered_map<int, ConditionalConstraint>;
 
    using FieldStatus = ordered_set<AllocSlice>;
 
 protected:
    // These are copied from parent to child on creating a transaction, and
    // from child to parent on committing.
    const PhvInfo *phv_i;
    const PhvUse *uses_i;
    assoc::hash_map<PHV::Size, ordered_map<ContainerAllocStatus, int>> count_by_status_i;
 
    // For efficiency, these are NOT copied from parent to child.  Changes in
    // the child are copied back to the parent on commit.  However, parent info
    // is copied to the child when queried, as a caching optimization.
    mutable ordered_map<PHV::Container, ContainerStatus> container_status_i;
    mutable ordered_map<const PHV::Field *, FieldStatus> field_status_i;
    mutable ordered_map<AllocSlice, ActionSet> meta_init_points_i;
    mutable ordered_map<const IR::MAU::Action *, ordered_set<const PHV::Field *>> init_writes_i;
    mutable ordered_map<const IR::BFN::ParserState *, std::set<PHV::Container>>
        state_to_containers_i;
    mutable ordered_map<PHV::Container, bitvec> dark_containers_write_allocated_i;
    mutable ordered_map<PHV::Container, bitvec> dark_containers_read_allocated_i;
    mutable DarkInitMap init_map_i;
 
    mutable ordered_map<gress_t,
                        ordered_map<const IR::MAU::Table *, std::set<const IR::MAU::Table *>>>
        ara_edges;
 
    bool isTrivial;
 
    Allocation(const PhvInfo &phv, const PhvUse &uses, bool isTrivial = false)
        : phv_i(&phv), uses_i(&uses), isTrivial(isTrivial) {}
 
    ordered_map<AllocSlice, ActionSet> &get_meta_init_points() const { return meta_init_points_i; }
 
 private:
    virtual bool addStatus(PHV::Container c, const ContainerStatus &status);
 
    virtual void addMetaInitPoints(const AllocSlice &slice, const ActionSet &actions);
 
    virtual void addSlice(PHV::Container c, AllocSlice slice);
 
    virtual void setGress(PHV::Container c, GressAssignment gress);
 
    virtual void setParserGroupGress(PHV::Container c, GressAssignment gress);
 
    virtual void setDeparserGroupGress(PHV::Container c, GressAssignment gress);
 
    virtual void setParserExtractGroupSource(PHV::Container c, ExtractSource source);
 
 public:
    virtual const ContainerStatus *getStatus(const PHV::Container &c) const = 0;
 
    virtual FieldStatus getStatus(const PHV::Field *f) const = 0;
    virtual void foreach_slice(const PHV::Field *f,
                               std::function<void(const AllocSlice &)> cb) const = 0;
 
    friend class Transaction;
 
    virtual const_iterator begin() const = 0;
    virtual const_iterator end() const = 0;
 
    virtual std::optional<ActionSet> getInitPoints(const AllocSlice &slice) const;
 
    virtual size_t size() const = 0;
 
    virtual bool contains(PHV::Container c) const = 0;
 
    virtual const ordered_set<const PHV::Field *> getMetadataInits(
        const IR::MAU::Action *act) const;
 
    virtual ActionSet getInitPointsForField(const PHV::Field *f) const;
 
    const ordered_set<unsigned> getTagalongCollectionsUsed() const;
 
    const ordered_map<const IR::BFN::ParserState *, std::set<PHV::Container>> &
    getParserStateToContainers(const PhvInfo &phv,
                               const MapFieldToParserStates &field_to_parser_states) const;
 
    ordered_set<AllocSlice> slices(PHV::Container c) const;
    void foreach_slice(PHV::Container c, std::function<void(const AllocSlice &)> cb) const;
 
    ordered_set<AllocSlice> slices(PHV::Container c, int stage, PHV::FieldUse access) const;
    void foreach_slice(PHV::Container c, int stage, PHV::FieldUse access,
                       std::function<void(const AllocSlice &)> cb) const;
 
    bool addDarkAllocation(const AllocSlice &slice);
 
    virtual bool isDarkReadAvailable(PHV::Container c, unsigned minStage, unsigned maxStage) const {
        if (!dark_containers_write_allocated_i.count(c)) return true;
        for (unsigned i = minStage; i <= maxStage; i++)
            if (dark_containers_write_allocated_i.at(c)[i]) return false;
        return true;
    }
 
    virtual bool isDarkWriteAvailable(PHV::Container c, unsigned minStage,
                                      unsigned maxStage) const {
        if (!dark_containers_read_allocated_i.count(c)) return true;
        for (unsigned i = minStage; i <= maxStage; i++)
            if (dark_containers_read_allocated_i.at(c)[i]) return false;
        return true;
    }
 
    ordered_set<AllocSlice> slices(PHV::Container c, le_bitrange range) const;
    ordered_set<AllocSlice> slices(PHV::Container c, le_bitrange range, int stage,
                                   PHV::FieldUse access) const;
    void foreach_slice(PHV::Container c, le_bitrange range,
                       std::function<void(const AllocSlice &)> cb) const;
 
    void foreach_slice(PHV::Container c, le_bitrange range, int stage, PHV::FieldUse access,
                       std::function<void(const AllocSlice &)> cb) const;
 
    virtual std::vector<MutuallyLiveSlices> slicesByLiveness(PHV::Container c) const;
 
    virtual MutuallyLiveSlices slicesByLiveness(const PHV::Container c, const AllocSlice &sl) const;
    virtual MutuallyLiveSlices byteSlicesByLiveness(const PHV::Container c, const AllocSlice &sl,
                                                    const PragmaNoInit &noInit) const;
    virtual MutuallyLiveSlices slicesByLiveness(const PHV::Container c,
                                                std::vector<AllocSlice> &slices) const;
 
    virtual MutuallyLiveSlices liverange_overlapped_slices(
        const PHV::Container c, const std::vector<AllocSlice> &slices) const;
 
    ordered_set<PHV::AllocSlice> slices(const PHV::Field *f, le_bitrange range) const;
    ordered_set<PHV::AllocSlice> slices(const PHV::Field *f, le_bitrange range, int stage,
                                        PHV::FieldUse access) const;
 
    void foreach_slice(const PHV::Field *f, le_bitrange range,
                       std::function<void(const AllocSlice &)> cb) const;
    void foreach_slice(const PHV::Field *f, le_bitrange range, int stage, PHV::FieldUse access,
                       std::function<void(const AllocSlice &)> cb) const;
 
    ordered_set<PHV::AllocSlice> slices(const PHV::Field *f) const {
        return slices(f, StartLen(0, f->size));
    }
 
    ordered_set<PHV::AllocSlice> slices(const PHV::Field *f, int stage,
                                        PHV::FieldUse access) const {
        return slices(f, StartLen(0, f->size), stage, access);
    }
 
    virtual GressAssignment gress(const PHV::Container &c) const;
 
    virtual GressAssignment parserGroupGress(PHV::Container c) const;
 
    virtual GressAssignment deparserGroupGress(PHV::Container c) const;
 
    virtual ContainerAllocStatus alloc_status(PHV::Container c) const;
 
    virtual ExtractSource parserExtractGroupSource(PHV::Container c) const;
 
    int empty_containers(PHV::Size size) const;
 
    virtual void allocate(const AllocSlice slice, LiveRangeShrinkingMap *initNodes = nullptr,
                          bool singleGressParserGroup = false);
 
    virtual void removeAllocatedSlice(const ordered_set<PHV::AllocSlice> &slices);
 
    virtual void addMetadataInitialization(AllocSlice slice, LiveRangeShrinkingMap initNodes);
 
    void addARAedge(gress_t grs, const IR::MAU::Table *src, const IR::MAU::Table *dst) const;
 
    const ordered_map<gress_t,
                      ordered_map<const IR::MAU::Table *, std::set<const IR::MAU::Table *>>> &
    getARAedges() const {
        return ara_edges;
    }
 
    std::string printARAedges() const;
 
    virtual cstring toString() const;
 
    virtual Transaction makeTransaction() const;
 
    cstring commit(Transaction &view);
 
    Transaction *clone(const Allocation &parent) const;
 
    struct AvailableSpot {
        PHV::Container container;
        GressAssignment gress;
        GressAssignment parserGroupGress;
        GressAssignment deparserGroupGress;
        ExtractSource parserExtractGroupSource;
        int n_bits;
        AvailableSpot(const PHV::Container &c, const GressAssignment &gress,
                      const GressAssignment &parserGroupGress,
                      const GressAssignment &deparserGroupGress,
                      const ExtractSource &parserExtractGroupSource, int n_bits)
            : container(c),
              gress(gress),
              parserGroupGress(parserGroupGress),
              deparserGroupGress(deparserGroupGress),
              parserExtractGroupSource(parserExtractGroupSource),
              n_bits(n_bits) {}
        bool operator<(const AvailableSpot &other) const { return n_bits < other.n_bits; }
    };
 
    std::set<AvailableSpot> available_spots() const;
};
 
class ConcreteAllocation : public Allocation {
    static ContainerStatus emptyContainerStatus;
 
    ConcreteAllocation(const PhvInfo &phv, const PhvUse &, bitvec containers, bool trivial);
 
 public:
    const ContainerStatus *getStatus(const PHV::Container &c) const override;
 
    FieldStatus getStatus(const PHV::Field *f) const override;
    void foreach_slice(const PHV::Field *f,
                       std::function<void(const AllocSlice &)> cb) const override;
 
    explicit ConcreteAllocation(const PhvInfo &, const PhvUse &, bool trivial = false);
 
    const_iterator begin() const override { return container_status_i.begin(); }
    const_iterator end() const override { return container_status_i.end(); }
 
    size_t size() const override { return container_status_i.size(); }
 
    bool contains(PHV::Container c) const override;
 
    void deallocate(const ordered_set<PHV::AllocSlice> &slices);
};
 
class Transaction : public Allocation {
    const Allocation *parent_i;
 
 public:
    const ContainerStatus *getStatus(const PHV::Container &c) const override;
 
    FieldStatus getStatus(const PHV::Field *f) const override;
    void foreach_slice(const PHV::Field *f,
                       std::function<void(const AllocSlice &)> cb) const override;
 
 public:
    explicit Transaction(const Allocation &parent)
        : Allocation(*parent.phv_i, *parent.uses_i), parent_i(&parent) {
        BUG_CHECK(&parent != this, "Creating transaction with self as parent");
 
        for (const auto &map_entry : parent.getARAedges()) {
            auto grs = map_entry.first;
 
            for (const auto &src2dsts : map_entry.second) {
                auto *src_tbl = src2dsts.first;
 
                for (auto *dst_tbl : src2dsts.second) {
                    this->addARAedge(grs, src_tbl, dst_tbl);
                }
            }
        }
    }
 
    void printMetaInitPoints() const;
 
    virtual ~Transaction() {}
 
    const_iterator begin() const override;
 
    const_iterator end() const override;
 
    size_t size() const override { return parent_i->size(); }
 
    bool contains(PHV::Container c) const override { return parent_i->contains(c); }
 
    cstring getTransactionDiff() const;
 
    cstring getTransactionSummary() const;
 
    std::optional<ActionSet> getInitPoints(const AllocSlice &slice) const override;
 
    const ordered_map<PHV::Container, ContainerStatus> &getTransactionStatus() const {
        return container_status_i;
    }
 
    ordered_map<PHV::Container, ContainerStatus> get_actual_diff() const;
 
    const ordered_map<const PHV::Field *, FieldStatus> &getFieldStatus() const {
        return field_status_i;
    }
 
    const ordered_map<AllocSlice, ActionSet> &getMetaInitPoints() const {
        return meta_init_points_i;
    }
 
    const ordered_map<const IR::MAU::Action *, ordered_set<const PHV::Field *>> &getInitWrites()
        const {
        return init_writes_i;
    }
 
    const ordered_set<const PHV::Field *> getMetadataInits(
        const IR::MAU::Action *act) const override {
        const ordered_set<const PHV::Field *> parentInits = parent_i->getMetadataInits(act);
        if (!init_writes_i.count(act)) return parentInits;
        ordered_set<const PHV::Field *> rv;
        rv.insert(parentInits.begin(), parentInits.end());
        auto inits = init_writes_i.at(act);
        rv.insert(inits.begin(), inits.end());
        return rv;
    }
 
    ActionSet getInitPointsForField(const PHV::Field *f) const override {
        ActionSet rs = parent_i->getInitPointsForField(f);
        for (auto kv : meta_init_points_i) {
            if (kv.first.field() != f) continue;
            rs.insert(kv.second.begin(), kv.second.end());
        }
        return rs;
    }
 
    const ordered_map<gress_t,
                      ordered_map<const IR::MAU::Table *, std::set<const IR::MAU::Table *>>> &
    getARAedges() const {
        // if (ara_edges.count(grs)) return ara_edges.at(grs);
        return ara_edges;
 
        // ordered_map<IR::MAU::Table*, std::set<IR::MAU::Table*>> empty_map;
        // return empty_map;
    }
 
    bool isDarkReadAvailable(PHV::Container c, unsigned minStage,
                             unsigned maxStage) const override {
        return (Allocation::isDarkReadAvailable(c, minStage, maxStage) ||
                parent_i->isDarkReadAvailable(c, minStage, maxStage));
    }
 
    bool isDarkWriteAvailable(PHV::Container c, unsigned minStage,
                              unsigned maxStage) const override {
        return (Allocation::isDarkWriteAvailable(c, minStage, maxStage) ||
                parent_i->isDarkWriteAvailable(c, minStage, maxStage));
    }
 
    void clearTransactionStatus() {
        container_status_i.clear();
        meta_init_points_i.clear();
        init_writes_i.clear();
        field_status_i.clear();
        dark_containers_write_allocated_i.clear();
        dark_containers_read_allocated_i.clear();
        init_map_i.clear();
        state_to_containers_i.clear();
        count_by_status_i = parent_i->count_by_status_i;
        ara_edges.clear();
    }
 
    const Allocation *getParent() const { return parent_i; }
};
 
class ClusterStats {
 private:
    static int nextId;
 
 public:
    int uid = nextId++;
    virtual bool okIn(PHV::Kind kind) const = 0;
 
    virtual int exact_containers() const = 0;
 
    virtual int max_width() const = 0;
 
    virtual int num_constraints() const = 0;
 
    virtual size_t aggregate_size() const = 0;
 
    virtual bool deparsed() const = 0;
 
    virtual bool contains(const PHV::Field *f) const = 0;
 
    virtual bool contains(const PHV::FieldSlice &slice) const = 0;
 
    virtual gress_t gress() const = 0;
};
 
template <typename Cluster>
struct SliceResult {
    using OptFieldSlice = std::optional<PHV::FieldSlice>;
    ordered_map<PHV::FieldSlice, std::pair<PHV::FieldSlice, OptFieldSlice>> slice_map;
    Cluster *lo;
    Cluster *hi;
};
 
class AlignedCluster : public ClusterStats {
    PHV::Kind kind_i;
    gress_t gress_i = INGRESS;
 
    ordered_set<PHV::FieldSlice> slices_i;
 
    int id_i;  // this cluster's id
    int exact_containers_i;
    int max_width_i;
    int num_constraints_i;
    size_t aggregate_size_i;
    bool hasDeparsedFields_i;
 
    std::optional<FieldAlignment> alignment_i;
 
    std::optional<le_bitrange> validContainerStartRange(PHV::Size container_size) const;
 
    static std::optional<le_bitrange> validContainerStartRange(const PHV::FieldSlice &slice,
                                                               PHV::Size container_size);
 
    void set_cluster_id();
 
    void initialize_constraints();
 
 public:
    template <typename Iterable>
    AlignedCluster(PHV::Kind kind, Iterable slices) : kind_i(kind) {
        set_cluster_id();
        for (auto &slice : slices) slices_i.insert(slice);
        initialize_constraints();
    }
 
    bool operator==(const AlignedCluster &other) const;
 
    int id() const { return id_i; }
 
    bool okIn(PHV::Kind kind) const override;
 
    std::optional<unsigned> alignment() const {
        if (alignment_i) return alignment_i->align;
        return std::nullopt;
    }
 
    bitvec validContainerStart(PHV::Size container_size) const;
 
    static bitvec validContainerStart(PHV::FieldSlice slice, PHV::Size container_size);
 
    const ordered_set<PHV::FieldSlice> &slices() const { return slices_i; }
 
    using const_iterator = ordered_set<PHV::FieldSlice>::const_iterator;
    const_iterator begin() const { return slices_i.begin(); }
    const_iterator end() const { return slices_i.end(); }
 
    // TODO: Revisit the following stats/constraints getters.
 
    int exact_containers() const override { return exact_containers_i; }
 
    int max_width() const override { return max_width_i; }
 
    int num_constraints() const override { return num_constraints_i; }
 
    size_t aggregate_size() const override { return aggregate_size_i; }
 
    bool deparsed() const override { return hasDeparsedFields_i; }
 
    bool contains(const PHV::Field *f) const override;
 
    bool contains(const PHV::FieldSlice &slice) const override;
 
    gress_t gress() const override { return gress_i; }
 
    std::optional<SliceResult<AlignedCluster>> slice(int pos) const;
 
    PHV::Kind kind() { return kind_i; }
};
 
class RotationalCluster : public ClusterStats {
    ordered_set<PHV::FieldSlice> slices_i;
 
    ordered_set<AlignedCluster *> clusters_i;
 
    ordered_map<const PHV::FieldSlice, AlignedCluster *> slices_to_clusters_i;
 
    // Statstics gathered from clusters.
    PHV::Kind kind_i = PHV::Kind::tagalong;
    gress_t gress_i = INGRESS;
    int exact_containers_i = 0;
    int max_width_i = 0;
    int num_constraints_i = 0;
    size_t aggregate_size_i = 0;
    bool hasDeparsedFields_i = false;
 
 public:
    explicit RotationalCluster(ordered_set<PHV::AlignedCluster *> clusters);
 
    bool operator==(const RotationalCluster &other) const;
 
    const ordered_set<PHV::FieldSlice> &slices() const { return slices_i; }
 
    const ordered_set<AlignedCluster *> &clusters() const { return clusters_i; }
 
    const AlignedCluster &cluster(const PHV::FieldSlice &slice) const {
        auto it = slices_to_clusters_i.find(slice);
        BUG_CHECK(it != slices_to_clusters_i.end(), "Field %1% not in cluster group",
                  cstring::to_cstring(slice));
        return *it->second;
    }
 
    bool okIn(PHV::Kind kind) const override;
 
    int exact_containers() const override { return exact_containers_i; }
 
    int max_width() const override { return max_width_i; }
 
    int num_constraints() const override { return num_constraints_i; }
 
    size_t aggregate_size() const override { return aggregate_size_i; }
 
    bool deparsed() const override { return hasDeparsedFields_i; }
 
    bool contains(const PHV::Field *f) const override;
 
    bool contains(const PHV::FieldSlice &slice) const override;
 
    gress_t gress() const override { return gress_i; }
 
    std::optional<SliceResult<RotationalCluster>> slice(int pos) const;
};
 
class SuperCluster : public ClusterStats {
 public:
    using SliceList = std::list<PHV::FieldSlice>;
 
 private:
    ordered_set<const RotationalCluster *> clusters_i;
    ordered_set<SliceList *> slice_lists_i;
 
    ordered_map<const PHV::FieldSlice, const RotationalCluster *> slices_to_clusters_i;
 
    assoc::hash_map<const PHV::FieldSlice, ordered_set<const SliceList *>> slices_to_slice_lists_i;
 
    // Statstics gathered from clusters.
    PHV::Kind kind_i = PHV::Kind::tagalong;
    gress_t gress_i = INGRESS;
    int exact_containers_i = 0;
    int max_width_i = 0;
    int num_constraints_i = 0;
    size_t aggregate_size_i = 0;
    size_t num_pack_conflicts_i = 0;
    bool hasDeparsedFields_i = false;
    bool needsStridedAlloc_i = false;
 
 public:
    SuperCluster(ordered_set<const PHV::RotationalCluster *> clusters,
                 ordered_set<SliceList *> slice_lists);
 
    bool operator==(const SuperCluster &other) const;
 
    const ordered_set<const RotationalCluster *> &clusters() const { return clusters_i; }
 
    const ordered_set<SliceList *> &slice_lists() const { return slice_lists_i; }
 
    const ordered_set<const SliceList *> &slice_list(const PHV::FieldSlice &slice) const;
 
    const RotationalCluster &cluster(const PHV::FieldSlice &slice) const {
        auto it = slices_to_clusters_i.find(slice);
        BUG_CHECK(it != slices_to_clusters_i.end(), "Field %1% not in cluster group %2%",
                  cstring::to_cstring(slice), cstring::to_cstring(this));
        return *it->second;
    }
 
    const AlignedCluster &aligned_cluster(const PHV::FieldSlice &slice) const {
        BUG_CHECK(slices_to_clusters_i.find(slice) != slices_to_clusters_i.end(),
                  "Field %1% not in cluster group", cstring::to_cstring(slice));
        return slices_to_clusters_i.at(slice)->cluster(slice);
    }
 
    SuperCluster *merge(const SuperCluster *sc1) {
        ordered_set<const RotationalCluster *> new_clusters_i;
        ordered_set<SliceList *> new_slice_lists;
        for (auto *c1 : clusters_i) {
            new_clusters_i.insert(c1);
        }
        for (auto *c2 : sc1->clusters_i) {
            new_clusters_i.insert(c2);
        }
        for (auto *sl1 : slice_lists_i) {
            new_slice_lists.insert(sl1);
        }
        for (auto *sl2 : sc1->slice_lists_i) {
            new_slice_lists.insert(sl2);
        }
        return new SuperCluster(new_clusters_i, new_slice_lists);
    }
 
    SuperCluster *merge(const SuperCluster *sc1) const;
 
    SuperCluster *mergeAndSortBasedOnWideArith(const SuperCluster *sc1) const;
 
    bool needToMergeForWideArith(const SuperCluster *sc) const;
 
    SuperCluster::SliceList *findLinkedWideArithSliceList(const SuperCluster::SliceList *sl) const;
 
    bool okIn(PHV::Kind kind) const override;
 
    int exact_containers() const override { return exact_containers_i; }
 
    int max_width() const override { return max_width_i; }
 
    int num_constraints() const override { return num_constraints_i; }
 
    size_t aggregate_size() const override { return aggregate_size_i; }
 
    size_t num_pack_conflicts() const { return num_pack_conflicts_i; }
 
    void calc_pack_conflicts();
 
    bool deparsed() const override { return hasDeparsedFields_i; }
 
    bool needsStridedAlloc() const { return needsStridedAlloc_i; }
 
    void needsStridedAlloc(bool val) { needsStridedAlloc_i = val; }
 
    bool contains(const PHV::Field *f) const override;
 
    bool contains(const PHV::FieldSlice &slice) const override;
 
    ordered_set<PHV::FieldSlice> slices() const;
 
    gress_t gress() const override { return gress_i; }
 
    void forall_fieldslices(const std::function<void(const PHV::FieldSlice &)> func) const {
        for (const auto &kv : slices_to_clusters_i) {
            func(kv.first);
        }
    }
 
    bool any_of_fieldslices(const std::function<bool(const PHV::FieldSlice &)> func) const {
        for (const auto &kv : slices_to_clusters_i) {
            if (func(kv.first)) return true;
        }
        return false;
    }
 
    bool all_of_fieldslices(const std::function<bool(const PHV::FieldSlice &)> func) const {
        for (const auto &kv : slices_to_clusters_i) {
            if (!func(kv.first)) return false;
        }
        return true;
    }
 
    bool is_deparser_zero_candidate() const;
 
    static bool is_well_formed(const SuperCluster *sc, PHV::Error *err = new PHV::Error());
 
    static int slice_list_total_bits(const SliceList &list);
 
    static std::vector<le_bitrange> slice_list_exact_containers(const SliceList &list);
 
    static bool slice_list_has_exact_containers(const SliceList &list);
 
    static std::vector<SuperCluster::SliceList *> slice_list_split_by_byte(
        const SuperCluster::SliceList &sl);
};
 
std::ostream &operator<<(std::ostream &out, const Allocation &);
std::ostream &operator<<(std::ostream &out, const Allocation *);
std::ostream &operator<<(std::ostream &out, const Allocation::ExtractSource &);
std::ostream &operator<<(std::ostream &out, const ContainerGroup &);
std::ostream &operator<<(std::ostream &out, const ContainerGroup *);
std::ostream &operator<<(std::ostream &out, const AlignedCluster &);
std::ostream &operator<<(std::ostream &out, const AlignedCluster *);
std::ostream &operator<<(std::ostream &out, const RotationalCluster &);
std::ostream &operator<<(std::ostream &out, const RotationalCluster *);
std::ostream &operator<<(std::ostream &out, const SuperCluster &);
std::ostream &operator<<(std::ostream &out, const SuperCluster *);
std::ostream &operator<<(std::ostream &out, const SuperCluster::SliceList &);
std::ostream &operator<<(std::ostream &out, const SuperCluster::SliceList *);
 
bool operator<(PHV::Allocation::ContainerAllocStatus, PHV::Allocation::ContainerAllocStatus);
bool operator<=(PHV::Allocation::ContainerAllocStatus, PHV::Allocation::ContainerAllocStatus);
bool operator>(PHV::Allocation::ContainerAllocStatus, PHV::Allocation::ContainerAllocStatus);
bool operator>=(PHV::Allocation::ContainerAllocStatus, PHV::Allocation::ContainerAllocStatus);
 
}  // namespace PHV
 
namespace P4 {
// TODO: This should go in the public repo, in `p4c/lib/ordered_set.h`.
template <typename T>
std::ostream &operator<<(std::ostream &out, const ordered_set<T> &set) {
    out << "{ ";
    unsigned count = 0U;
    for (const auto &elt : set) {
        out << elt;
        count++;
        if (count < set.size()) out << ", ";
    }
    out << " }";
    return out;
}
}  // namespace P4
 
#endif /* BF_P4C_PHV_UTILS_UTILS_H_ */