allocate_phv.h

 
#ifndef BF_P4C_PHV_ALLOCATE_PHV_H_
#define BF_P4C_PHV_ALLOCATE_PHV_H_
 
#include <optional>
#include <sstream>
 
#include "backends/tofino/bf-p4c/common/field_defuse.h"
#include "backends/tofino/bf-p4c/ir/bitrange.h"
#include "backends/tofino/bf-p4c/ir/gress.h"
#include "backends/tofino/bf-p4c/parde/clot/clot_info.h"
#include "backends/tofino/bf-p4c/phv/action_phv_constraints.h"
#include "backends/tofino/bf-p4c/phv/action_source_tracker.h"
#include "backends/tofino/bf-p4c/phv/alloc_setting.h"
#include "backends/tofino/bf-p4c/phv/analysis/critical_path_clusters.h"
#include "backends/tofino/bf-p4c/phv/analysis/dark_live_range.h"
#include "backends/tofino/bf-p4c/phv/analysis/live_range_shrinking.h"
#include "backends/tofino/bf-p4c/phv/collect_strided_headers.h"
#include "backends/tofino/bf-p4c/phv/fieldslice_live_range.h"
#include "backends/tofino/bf-p4c/phv/make_clusters.h"
#include "backends/tofino/bf-p4c/phv/mau_backtracker.h"
#include "backends/tofino/bf-p4c/phv/phv.h"
#include "backends/tofino/bf-p4c/phv/phv_fields.h"
#include "backends/tofino/bf-p4c/phv/phv_parde_mau_use.h"
#include "backends/tofino/bf-p4c/phv/pragma/phv_pragmas.h"
#include "backends/tofino/bf-p4c/phv/slicing/types.h"
#include "backends/tofino/bf-p4c/phv/table_phv_constraints.h"
#include "backends/tofino/bf-p4c/phv/utils/slice_alloc.h"
#include "backends/tofino/bf-p4c/phv/utils/tables_to_ids.h"
#include "backends/tofino/bf-p4c/phv/utils/utils.h"
#include "lib/bitvec.h"
#include "lib/symbitmatrix.h"
 
namespace PHV {

class AllocUtils {
 public:
    // PHV fields and clot info.
    const PhvInfo &phv;
    const ClotInfo &clot;
 
    // clustering results (super clusters) and no_pack constraint found during clustering.
    const Clustering &clustering;
 
    // defuses and action constraints.
    const PhvUse &uses;
    const FieldDefUse &defuse;
 
    // action-related constraints
    const ActionPhvConstraints &actions;
    const ActionSourceTracker &source_tracker;
 
    // Metadata initialization possibilities.
    const LiveRangeShrinking &meta_init;
    // Dark overlay possibilities.
    const DarkOverlay &dark_init;
 
    // parser-related
    const MapFieldToParserStates &field_to_parser_states;
    const CalcParserCriticalPath &parser_critical_path;
    const CollectParserInfo &parser_info;
    const CollectStridedHeaders &strided_headers;
 
    // physical live range (available only after table has been allocated)
    const PHV::FieldSliceLiveRangeDB &physical_liverange_db;
 
    // pragma
    const PHV::Pragmas &pragmas;
 
    // misc allocation settings.
    const AllocSetting &settings;
 
    // Collect field packing that table/ixbar would benefit from.
    const TableFieldPackOptimization &tablePackOpt;
 
    AllocUtils(const PhvInfo &phv, const ClotInfo &clot, const Clustering &clustering,
               const PhvUse &uses, const FieldDefUse &defuse, const ActionPhvConstraints &actions,
               const LiveRangeShrinking &meta_init, const DarkOverlay &dark_init,
               const MapFieldToParserStates &field_to_parser_states,
               const CalcParserCriticalPath &parser_critical_path,
               const CollectParserInfo &parser_info, const CollectStridedHeaders &strided_headers,
               const PHV::FieldSliceLiveRangeDB &physical_liverange_db,
               const ActionSourceTracker &source_tracker, const PHV::Pragmas &pragmas,
               const AllocSetting &settings, const TableFieldPackOptimization &tablePackOpt)
        : phv(phv),
          clot(clot),
          clustering(clustering),
          uses(uses),
          defuse(defuse),
          actions(actions),
          source_tracker(source_tracker),
          meta_init(meta_init),
          dark_init(dark_init),
          field_to_parser_states(field_to_parser_states),
          parser_critical_path(parser_critical_path),
          parser_info(parser_info),
          strided_headers(strided_headers),
          physical_liverange_db(physical_liverange_db),
          pragmas(pragmas),
          settings(settings),
          tablePackOpt(tablePackOpt) {}
 
    const SymBitMatrix &mutex() const { return phv.field_mutex(); }
 
    // has_pack_conflict should be used as the only source of pack conflict checks.
    // It checks mutex + pack conflict from mau + no pack constraint from cluster.
    bool has_pack_conflict(const PHV::FieldSlice &fs1, const PHV::FieldSlice &fs2) const {
        if (fs1.field() != fs2.field()) {
            if (mutex()(fs1.field()->id, fs2.field()->id)) return false;
        }
        return clustering.no_pack(fs1.field(), fs2.field()) || actions.hasPackConflict(fs1, fs2);
    }
 
    // return true if field is used and not padding.
    bool is_referenced(const PHV::Field *f) const { return !f->padding && uses.is_referenced(f); };

    std::list<PHV::SuperCluster *> make_superclusters() const {
        return clustering.cluster_groups();
    }
 
    // @returns a slicing iterator.
    PHV::Slicing::IteratorInterface *make_slicing_ctx(const PHV::SuperCluster *sc) const;
 
    // @returns true if @p a and @p b can be overlaid,
    // because of their physical live ranges are disjoint and both fieldslices are
    // qualified to be overlaid:
    // (1) not pov, deparsed_to_tm, nor is_invalidate_from_arch.
    // (2) not in pa_no_overlay.
    bool can_physical_liverange_be_overlaid(const PHV::AllocSlice &a,
                                            const PHV::AllocSlice &b) const;

    static bool is_clot_allocated(const ClotInfo &clots, const PHV::SuperCluster &sc);

    static std::list<PHV::ContainerGroup *> make_device_container_groups();

    static void clear_slices(PhvInfo &phv);

    static void bind_slices(const PHV::ConcreteAllocation &alloc, PhvInfo &phv);

    static void sort_and_merge_alloc_slices(PhvInfo &phv);

    static std::list<PHV::SuperCluster *> remove_singleton_metadata_slicelist(
        const std::list<PHV::SuperCluster *> &cluster_groups);

    static std::list<PHV::SuperCluster *> remove_unref_clusters(
        const PhvUse &uses, const std::list<PHV::SuperCluster *> &cluster_groups_input);

    static std::list<PHV::SuperCluster *> remove_clot_allocated_clusters(
        const ClotInfo &clot, std::list<PHV::SuperCluster *> clusters);

    static std::list<PHV::SuperCluster *> create_strided_clusters(
        const CollectStridedHeaders &strided_headers,
        const std::list<PHV::SuperCluster *> &cluster_groups);

    static bool update_refs(AllocSlice &slc, const PhvInfo &p, const FieldDefUse::LocPairSet &refs,
                            FieldUse fuse);
    static void update_slice_refs(PhvInfo &phv, const FieldDefUse &defuse);
};
 
namespace Diagnostics {
 
std::string printField(const PHV::Field *f);
std::string printSlice(const PHV::FieldSlice &slice);
 
}  // namespace Diagnostics
 
}  // namespace PHV

class FieldPackingOpportunity {
    const ActionPhvConstraints &actions;
    const PhvUse &uses;
    const FieldDefUse &defuse;
    const SymBitMatrix &mutex;
    using FieldPair = std::pair<const PHV::Field *, const PHV::Field *>;
    std::map<const PHV::Field *, int> opportunities;
    std::map<FieldPair, int> opportunities_after;

    std::vector<const PHV::Field *> fieldsInOrder(
        const std::list<PHV::SuperCluster *> &sorted_clusters) const;
 
    bool isExtractedOrUninitialized(const PHV::Field *f) const;
    bool canPack(const PHV::Field *f1, const PHV::Field *f2) const;
 
 public:
    FieldPackingOpportunity(const std::list<PHV::SuperCluster *> &sorted_clusters,
                            const ActionPhvConstraints &actions, const PhvUse &uses,
                            const FieldDefUse &defuse, const SymBitMatrix &mutex);

    int nOpportunities(const PHV::Field *f) const { return opportunities.at(f); }

    int nOpportunitiesAfter(const PHV::Field *f1, const PHV::Field *f2) const;
};

struct AllocScore {
    using ContainerAllocStatus = PHV::Allocation::ContainerAllocStatus;

    using IsBetterFunc = std::function<bool(const AllocScore &left, const AllocScore &right)>;

    typedef cstring MetricName;

    static const std::vector<MetricName> g_general_metrics;
    ordered_map<MetricName, int> general;

    static const std::vector<MetricName> g_by_kind_metrics;
    ordered_map<PHV::Kind, ordered_map<MetricName, int>> by_kind;
 
    AllocScore() {}

    AllocScore(const PHV::Transaction &alloc, const PhvInfo &phv, const ClotInfo &clot,
               const PhvUse &uses, const MapFieldToParserStates &field_to_parser_states,
               const CalcParserCriticalPath &parser_critical_path,
               const TableFieldPackOptimization &tablePackOpt, FieldPackingOpportunity *packing,
               const int bitmasks);
 
    AllocScore &operator=(const AllocScore &other) = default;
    AllocScore operator-(const AllocScore &other) const;
    static AllocScore make_lowest() { return AllocScore(); }
 
 private:
    bitvec calcContainerAllocVec(const ordered_set<PHV::AllocSlice> &slices);
 
    ContainerAllocStatus calcContainerStatus(const PHV::Container &container,
                                             const ordered_set<PHV::AllocSlice> &slices);
 
    void calcParserExtractorBalanceScore(const PHV::Transaction &alloc, const PhvInfo &phv,
                                         const MapFieldToParserStates &field_to_parser_states,
                                         const CalcParserCriticalPath &parser_critical_path);
};
 
std::ostream &operator<<(std::ostream &s, const AllocScore &score);

class ScoreContext {
 private:
    cstring name_i;

    FieldPackingOpportunity *packing_opportunities_i = nullptr;

    bool stop_at_first_i = false;

    AllocScore::IsBetterFunc is_better_i;
 
 public:
    ScoreContext(cstring name, bool stop_at_first, AllocScore::IsBetterFunc is_better)
        : name_i(name), stop_at_first_i(stop_at_first), is_better_i(is_better) {}
 
    AllocScore make_score(const PHV::Transaction &alloc, const PhvInfo &phv, const ClotInfo &clot,
                          const PhvUse &uses, const MapFieldToParserStates &field_to_parser_states,
                          const CalcParserCriticalPath &parser_critical_path,
                          const TableFieldPackOptimization &tablePackOpt,
                          const int bitmasks = 0) const;
 
    bool is_better(const AllocScore &left, const AllocScore &right) const {
        return is_better_i(left, right);
    }
 
    bool stop_at_first() const { return stop_at_first_i; }
 
    ScoreContext with(FieldPackingOpportunity *packing) {
        auto cloned = *this;
        cloned.packing_opportunities_i = packing;
        return cloned;
    }
};

struct AllocAlignment {
    ordered_map<PHV::FieldSlice, int> slice_alignment;
    ordered_map<const PHV::AlignedCluster *, int> cluster_alignment;
};

class CoreAllocation {
    struct OverlayInfo {
        bool control_flow_overlay;
        bool physical_liverange_overlay;
        bool metadata_overlay;
        bool dark_overlay;
    };
    const PHV::AllocUtils &utils_i;
 
    // Table allocation information from the previous round.
    // TODO: legacy, this might actually never be used at all because it is
    // initialized in value instead of references.
    const bool disableMetadataInit;
    // Enforce single gress parser groups
    bool singleGressParserGroups = false;
    // Prioritize use of ARA for overlay inits
    bool prioritizeARAinits = false;
 
    std::optional<PHV::Transaction> alloc_super_cluster_with_alignment(
        const PHV::Allocation &alloc, const PHV::ContainerGroup &container_group,
        PHV::SuperCluster &super_cluster, const AllocAlignment &alignment,
        const std::list<const PHV::SuperCluster::SliceList *> &sorted_slice_lists,
        const ScoreContext &score_ctx) const;

    std::vector<AllocAlignment> build_alignments(int max_n,
                                                 const PHV::ContainerGroup &container_group,
                                                 const PHV::SuperCluster &super_cluster) const;

    std::vector<AllocAlignment> build_slicelist_alignment(
        const PHV::ContainerGroup &container_group, const PHV::SuperCluster &super_cluster,
        const PHV::SuperCluster::SliceList *slice_list) const;
 
    bool check_metadata_and_dark_overlay(
        const PHV::Container &c, std::vector<PHV::AllocSlice> &complex_overlay_slices,
        std::vector<PHV::AllocSlice> &candidate_slices,
        ordered_set<PHV::AllocSlice> &new_candidate_slices, PHV::Transaction &perContainerAlloc,
        ordered_map<const PHV::AllocSlice, OverlayInfo> &overlay_info,
        std::optional<PHV::Allocation::LiveRangeShrinkingMap> &initNodes,
        std::optional<ordered_set<PHV::AllocSlice>> &allocedSlices,
        ordered_set<PHV::AllocSlice> &metaInitSlices,
        PHV::Allocation::LiveRangeShrinkingMap &initActions, bool &new_overlay_container,
        const PHV::ContainerGroup &group, const bool &canDarkInitUseARA) const;
 
    bool update_new_prim(const PHV::AllocSlice &existingSl, PHV::AllocSlice &newSl,
                         ordered_set<PHV::AllocSlice> &toBeRemovedFromAlloc) const;
 
    std::optional<std::vector<PHV::AllocSlice>> prepare_candidate_slices(
        PHV::SuperCluster::SliceList &slices, const PHV::Container &c,
        const PHV::Allocation::ConditionalConstraint &start_positions) const;
 
    bool try_metadata_overlay(const PHV::Container &c,
                              std::optional<ordered_set<PHV::AllocSlice>> &allocedSlices,
                              const PHV::AllocSlice &slice,
                              std::optional<PHV::Allocation::LiveRangeShrinkingMap> &initNodes,
                              ordered_set<PHV::AllocSlice> &new_candidate_slices,
                              ordered_set<PHV::AllocSlice> &metaInitSlices,
                              PHV::Allocation::LiveRangeShrinkingMap &initActions,
                              PHV::Transaction &perContainerAlloc,
                              const PHV::Allocation::MutuallyLiveSlices &alloced_slices,
                              PHV::Allocation::MutuallyLiveSlices &actual_cntr_state) const;
 
    bool try_dark_overlay(std::vector<PHV::AllocSlice> &dark_slices,
                          PHV::Transaction &perContainerAlloc, const PHV::Container &c,
                          std::vector<PHV::AllocSlice> &candidate_slices,
                          ordered_set<PHV::AllocSlice> &new_candidate_slices,
                          bool &new_overlay_container, ordered_set<PHV::AllocSlice> &metaInitSlices,
                          const PHV::ContainerGroup &group, const bool &canDarkInitUseARA) const;
 
    bool try_pack_slice_list(
        std::vector<PHV::AllocSlice> &candidate_slices, PHV::Transaction &perContainerAlloc,
        PHV::Allocation::LiveRangeShrinkingMap &initActions,
        std::optional<PHV::Allocation::LiveRangeShrinkingMap> &initNodes, const PHV::Container &c,
        const PHV::SuperCluster &super_cluster,
        std::optional<PHV::Allocation::ConditionalConstraints> &action_constraints,
        int &num_bitmasks) const;
 
    bool try_place_wide_arith_hi(const PHV::ContainerGroup &group, const PHV::Container &c,
                                 PHV::SuperCluster::SliceList *hi_slice,
                                 const PHV::SuperCluster &super_cluster,
                                 PHV::Transaction &this_alloc, const ScoreContext &score_ctx) const;

    bool find_previous_allocation(
        PHV::Container &previous_container,
        ordered_map<PHV::FieldSlice, PHV::AllocSlice> &previous_allocations,
        const PHV::Allocation::ConditionalConstraint &start_positions,
        PHV::SuperCluster::SliceList &slices, const PHV::ContainerGroup &group,
        const PHV::Allocation &alloc) const;
 
 public:
    CoreAllocation(const PHV::AllocUtils &utils, bool disable_metainit)
        : utils_i(utils), disableMetadataInit(disable_metainit) {}

    static bool can_overlay(const SymBitMatrix &mutually_exclusive_field_ids, const PHV::Field *f,
                            const ordered_set<PHV::AllocSlice> &slices);

    static bool some_overlay(const SymBitMatrix &mutually_exclusive_field_ids, const PHV::Field *f,
                             const ordered_set<PHV::AllocSlice> &slices);

    bool can_physical_liverange_overlay(const PHV::AllocSlice &slice,
                                        const ordered_set<PHV::AllocSlice> &allocated) const;

    bool hasARAinits(ordered_set<PHV::AllocSlice> slices) const;

    bool satisfies_constraints(std::vector<PHV::AllocSlice> slices,
                               const PHV::Allocation &alloc) const;

    bool satisfies_constraints(const PHV::ContainerGroup &group, const PHV::Field *f) const;

    bool satisfies_constraints(const PHV::ContainerGroup &group,
                               const PHV::FieldSlice &slice) const;

    bool satisfies_constraints(const PHV::Allocation &alloc, const PHV::AllocSlice &slice,
                               ordered_set<PHV::AllocSlice> &initFields,
                               std::vector<PHV::AllocSlice> &candidate_slices) const;

    static bool satisfies_constraints(const PHV::ContainerGroup &container_group,
                                      const PHV::SuperCluster &cluster_group);
 
    // Set/Get single-gress Parser groups
    void set_single_gress_parser_group() { singleGressParserGroups = true; }
    bool get_single_gress_parser_group() { return singleGressParserGroups; }
 
    // Set/Get ARA init priority
    void set_prioritize_ARA_inits() { prioritizeARAinits = true; }
    bool get_prioririze_ARA_inits() { return prioritizeARAinits; }

    std::optional<PHV::Transaction> try_alloc(const PHV::Allocation &alloc,
                                              const PHV::ContainerGroup &group,
                                              PHV::SuperCluster &cluster, int max_alignment_tries,
                                              const ScoreContext &score_ctx) const;
 
    std::optional<const PHV::SuperCluster::SliceList *> find_first_unallocated_slicelist(
        const PHV::Allocation &alloc, const std::list<PHV::ContainerGroup *> &container_groups,
        const PHV::SuperCluster &cluster) const;

    std::optional<PHV::Transaction> try_deparser_zero_alloc(const PHV::Allocation &alloc,
                                                            PHV::SuperCluster &cluster,
                                                            PhvInfo &phv) const;
 
    bool checkDarkOverlay(const std::vector<PHV::AllocSlice> &candidate_slices,
                          const PHV::Transaction &alloc) const;

    bool rangesOverlap(const PHV::AllocSlice &slice, const IR::BFN::ParserPrimitive *prim) const;

    bool checkParserExtractions(const std::vector<PHV::AllocSlice> &candidate_slices,
                                const PHV::Transaction &alloc) const;

    std::optional<PHV::Transaction> tryAllocSliceList(
        const PHV::Allocation &alloc, const PHV::ContainerGroup &group,
        const PHV::SuperCluster &super_cluster,
        const PHV::Allocation::ConditionalConstraint &start_positions,
        const ScoreContext &score_ctx) const;

    std::optional<PHV::Transaction> tryAllocSliceList(
        const PHV::Allocation &alloc, const PHV::ContainerGroup &group,
        const PHV::SuperCluster &super_cluster, const PHV::SuperCluster::SliceList &slice_list,
        const ordered_map<PHV::FieldSlice, int> &start_positions,
        const ScoreContext &score_ctx) const;
 
    bool generateNewAllocSlices(const PHV::AllocSlice &origSlice,
                                const ordered_set<PHV::AllocSlice> &alloced_slices,
                                PHV::DarkInitMap &slices,
                                ordered_set<PHV::AllocSlice> &new_candidate_slices,
                                PHV::Transaction &alloc_attempt,
                                const PHV::Allocation::MutuallyLiveSlices &container_state) const;
 
    bool hasCrossingLiveranges(std::vector<PHV::AllocSlice> candidate_slices,
                               ordered_set<PHV::AllocSlice> alloc_slices) const;

    PHV::Transaction make_speculated_alloc(const PHV::Transaction &alloc,
                                           const PHV::SuperCluster &sc,
                                           const std::vector<PHV::AllocSlice> &candidates,
                                           const PHV::Container &c) const;
};
 
enum class AllocResultCode {
    UNKNOWN,            // default value
    SUCCESS,            // All fields allocated
    FAIL,               // Some fields unallocated
    FAIL_UNSAT_SLICING  // Some fields CANNOT be allocated due to slicing
};
 
struct AllocResult {
    AllocResultCode status;
    PHV::Transaction transaction;
    std::list<const PHV::SuperCluster *> remaining_clusters;
    // To avoid copy on those large objects, constructor only takes rvalue,
    // so use std::move() if needed.
    AllocResult(AllocResultCode r, PHV::Transaction &&t,  // NOLINT
                std::list<const PHV::SuperCluster *> &&c)
        : status(r), transaction(t), remaining_clusters(c) {}
};

class AllocationStrategy {
 protected:
    const cstring name;
    const PHV::AllocUtils &utils_i;
    const CoreAllocation &core_alloc_i;
 
 public:
    AllocationStrategy(cstring name, const PHV::AllocUtils &utils, const CoreAllocation &core)
        : name(name), utils_i(utils), core_alloc_i(core) {}

    virtual AllocResult tryAllocation(const PHV::Allocation &alloc,
                                      const std::list<PHV::SuperCluster *> &cluster_groups_input,
                                      const std::list<PHV::ContainerGroup *> &container_groups) = 0;
};
 
struct BruteForceStrategyConfig {
    cstring name;
    // heuristics of alloc score:
    AllocScore::IsBetterFunc is_better;
    // if max_failure_retry > 1, will retry (n-1) times by allocating
    // previsouly failed fields at the beginning of the allocation.
    int max_failure_retry;
    // try to split a supercluster for max_slicing_try times then allocate
    // for best score.
    int max_slicing;
    // the number of alignments of slicelists generated.
    // TODO: currently stopped at the first alloc-able alignment.
    int max_sl_alignment;
    // unsupported devices for this config.
    std::optional<std::unordered_set<Device::Device_t>> unsupported_devices;
    // enable validation on pre-sliced super clusters to avoid creating unallocatable
    // clusters at preslicing.
    bool pre_slicing_validation;
    // enable AlwaysRun Action use for dark spills and zero-initialization during dark overlays
    bool enable_ara_in_overlays;
};
 
class BruteForceAllocationStrategy : public AllocationStrategy {
 private:
    const PHV::Allocation &empty_alloc_i;
    const BruteForceStrategyConfig &config_i;
    std::optional<const PHV::SuperCluster::SliceList *> unallocatable_list_i;
    int pipe_id_i;   
    PhvInfo &phv_i;  // mutable because of deparsed zero allocation.
 
 public:
    BruteForceAllocationStrategy(const cstring name, const PHV::AllocUtils &utils,
                                 const CoreAllocation &core, const PHV::Allocation &empty_alloc,
                                 const BruteForceStrategyConfig &config, int pipeId, PhvInfo &phv);
 
    AllocResult tryAllocation(const PHV::Allocation &alloc,
                              const std::list<PHV::SuperCluster *> &cluster_groups_input,
                              const std::list<PHV::ContainerGroup *> &container_groups) override;
 
    std::optional<const PHV::SuperCluster::SliceList *> get_unallocatable_list() const {
        return unallocatable_list_i;
    }
 
    int getPipeId() const { return pipe_id_i; }
 
 protected:
    AllocResult tryAllocationFailuresFirst(
        const PHV::Allocation &alloc, const std::list<PHV::SuperCluster *> &cluster_groups_input,
        const std::list<PHV::ContainerGroup *> &container_groups,
        const ordered_set<const PHV::Field *> &failures);
 
    std::list<PHV::SuperCluster *> crush_clusters(
        const std::list<PHV::SuperCluster *> &cluster_groups);

    std::list<PHV::SuperCluster *> preslice_clusters(
        const std::list<PHV::SuperCluster *> &cluster_groups,
        const std::list<PHV::ContainerGroup *> &container_groups,
        std::list<const PHV::SuperCluster *> &unsliceable);

    void sortClusters(std::list<PHV::SuperCluster *> &cluster_groups);
 
    bool tryAllocSlicing(const std::list<PHV::SuperCluster *> &slicing,
                         const std::list<PHV::ContainerGroup *> &container_groups,
                         PHV::Transaction &slicing_alloc, const ScoreContext &score_ctx);
 
    bool tryAllocStride(const std::list<PHV::SuperCluster *> &stride,
                        const std::list<PHV::ContainerGroup *> &container_groups,
                        PHV::Transaction &stride_alloc, const ScoreContext &score_ctx);
 
    bool tryAllocStrideWithLeaderAllocated(const std::list<PHV::SuperCluster *> &stride,
                                           PHV::Transaction &leader_alloc,
                                           const ScoreContext &score_ctx);
 
    bool tryAllocSlicingStrided(unsigned num_strides, const std::list<PHV::SuperCluster *> &slicing,
                                const std::list<PHV::ContainerGroup *> &container_groups,
                                PHV::Transaction &slicing_alloc, const ScoreContext &score_ctx);
 
    std::optional<PHV::Transaction> tryVariousSlicing(
        PHV::Transaction &rst, PHV::SuperCluster *cluster_group,
        const std::list<PHV::ContainerGroup *> &container_groups, const ScoreContext &score_ctx,
        std::stringstream &alloc_history);
 
    std::list<PHV::SuperCluster *> allocLoop(
        PHV::Transaction &rst, std::list<PHV::SuperCluster *> &cluster_groups,
        const std::list<PHV::ContainerGroup *> &container_groups, const ScoreContext &score_ctx);

    std::list<PHV::SuperCluster *> allocDeparserZeroSuperclusters(
        PHV::Transaction &rst, std::list<PHV::SuperCluster *> &cluster_groups);

    ordered_set<bitvec> calc_slicing_schemas(const PHV::SuperCluster *sc,
                                             const std::set<PHV::Allocation::AvailableSpot> &spots);

     *
     *  Try to slice and allocate each cluster by trying the slicing schemas returned from
     *  calc_slicing_schema, in order.
     */
    std::list<PHV::SuperCluster *> pounderRoundAllocLoop(
        PHV::Transaction &rst, std::list<PHV::SuperCluster *> &cluster_groups,
        const std::list<PHV::ContainerGroup *> &container_groups);
 
    // return unallocatable slice list by allocating superclusters to an empty PHV.
    std::optional<const PHV::SuperCluster::SliceList *> diagnose_slicing(
        const std::list<PHV::SuperCluster *> &slicing,
        const std::list<PHV::ContainerGroup *> &container_groups) const;
 
    // return unallocatable slice list.
    // It will try to slice @p sliced further and allocate to an empty PHV.
    // The reason why this function will try to split further is because that
    // there can be valid presliced cluster that is too large for a single container group.
    std::optional<const PHV::SuperCluster::SliceList *> preslice_validation(
        const std::list<PHV::SuperCluster *> &sliced,
        const std::list<PHV::ContainerGroup *> &container_groups) const;
 
    friend class BruteForceOptimizationStrategy;
};

class AllocatePHV : public Visitor {
 private:
    const PHV::AllocUtils &utils_i;
    const MauBacktracker &mau_i;
    CoreAllocation core_alloc_i;
    PhvInfo &phv_i;
    const IR::BFN::Pipe *root = nullptr;
    // const DependencyGraph &deps_i;
    PHV::ConcreteAllocation *alloc = nullptr;
    std::list<const PHV::SuperCluster *> &unallocated_i;
    const IR::Node *apply_visitor(const IR::Node *root, const char *name = 0) override;

    static void formatAndThrowUnsat(const std::list<const PHV::SuperCluster *> &unallocated);

    static bool diagnoseSuperCluster(const PHV::SuperCluster *sc, const PHV::AllocUtils &utils);

    AllocResult brute_force_alloc(
        PHV::ConcreteAllocation &alloc, PHV::ConcreteAllocation &empty_alloc,
        std::vector<const PHV::SuperCluster::SliceList *> &unallocatable_lists,
        std::list<PHV::SuperCluster *> &cluster_groups,
        const std::list<PHV::ContainerGroup *> &container_groups, const int pipe_id) const;
 
 public:
    AllocatePHV(const PHV::AllocUtils &utils, const MauBacktracker &mau, PhvInfo &phv,
                // const DependencyGraph &deps,
                std::list<const PHV::SuperCluster *> &unallocated)
        : utils_i(utils),
          mau_i(mau),
          core_alloc_i(utils, mau.disableMetadataInitialization()),
          phv_i(phv),
          // deps_i(deps),
          unallocated_i(unallocated) {}

    static bool diagnoseFailures(const std::list<const PHV::SuperCluster *> &unallocated,
                                 const PHV::AllocUtils &utils);

    static void formatAndThrowError(const PHV::Allocation &alloc,
                                    const std::list<const PHV::SuperCluster *> &unallocated);
 
    PHV::ConcreteAllocation *getAllocation() { return alloc; }
};

class IncrementalPHVAllocation : public Visitor {
    const PHV::AllocUtils &utils_i;
    CoreAllocation core_alloc_i;
    PhvInfo &phv_i;
    PHV::AllocSetting &settings_i;
 
    // fields to be allocated.
    const ordered_set<PHV::Field *> &temp_vars_i;
 
    // This pass does not traverse IR.
    const IR::Node *apply_visitor(const IR::Node *root, const char *name = 0) override;
 
 public:
    explicit IncrementalPHVAllocation(const ordered_set<PHV::Field *> &temp_vars,
                                      const PHV::AllocUtils &utils, PhvInfo &phv,
                                      PHV::AllocSetting &settings)
        : utils_i(utils),
          core_alloc_i(utils, true),
          phv_i(phv),
          settings_i(settings),
          temp_vars_i(temp_vars) {}
};
 
#endif /* BF_P4C_PHV_ALLOCATE_PHV_H_ */