allocator_base.h

 
#ifndef BF_P4C_PHV_V2_ALLOCATOR_BASE_H_
#define BF_P4C_PHV_V2_ALLOCATOR_BASE_H_
 
#include "backends/tofino/bf-p4c/phv/phv.h"
#include "backends/tofino/bf-p4c/phv/phv_fields.h"
#include "backends/tofino/bf-p4c/phv/utils/utils.h"
#include "backends/tofino/bf-p4c/phv/v2/allocator_metrics.h"
#include "backends/tofino/bf-p4c/phv/v2/copacker.h"
#include "backends/tofino/bf-p4c/phv/v2/phv_kit.h"
#include "backends/tofino/bf-p4c/phv/v2/utils_v2.h"
 
namespace PHV {
namespace v2 {

struct ContScopeAllocResult : public AllocResult {
    ActionSourceCoPackMap action_hints;
    Container c;
    bool is_packing = false;
    ContScopeAllocResult() : AllocResult(new AllocError(ErrorCode::NOT_ENOUGH_SPACE, ""_cs)) {}
    explicit ContScopeAllocResult(const AllocError *err) : AllocResult(err) {}
    ContScopeAllocResult(const Transaction &tx, const ActionSourceCoPackMap &hints, Container c,
                         bool is_packing)
        : AllocResult(tx), action_hints(hints), c(c), is_packing(is_packing) {}
    bool cont_is_whole_container_set_only() const {
        BUG_CHECK(ok(), "cannot query this status on error");
        return c.type().kind() == Kind::mocha || c.type().kind() == Kind::dark;
    }
};

struct SomeContScopeAllocResult {
    const AllocError *err = nullptr;
    std::vector<const TxScore *> scores;
    std::vector<ContScopeAllocResult> results;
    explicit SomeContScopeAllocResult(const AllocError *default_err) : err(default_err) {}
    explicit SomeContScopeAllocResult(ContScopeAllocResult &rst, const TxScore *score)
        : scores{score}, results{rst} {}
    void collect(const ContScopeAllocResult &rst, const TxScore *score);
    bool ok() const { return !results.empty(); }
    ContScopeAllocResult &front() { return results.front(); }
    size_t size() const { return results.size(); }
};

class AllocatorBase {
 protected:
    const PhvKit &kit_i;

 protected:
    const AllocError *is_container_type_ok(const AllocSlice &sl, const Container &c) const;

    const AllocError *is_container_gress_ok(const Allocation &alloc, const AllocSlice &sl,
                                            const Container &c) const;

    const AllocError *is_container_write_mode_ok(const Allocation &alloc, const AllocSlice &sl,
                                                 const Container &c) const;

    const AllocError *is_container_solitary_ok(const Allocation &alloc, const AllocSlice &candidate,
                                               const Container &c) const;

    const AllocError *is_container_bytes_ok(const Allocation &alloc,
                                            const std::vector<AllocSlice> &candidates,
                                            const Container &c) const;

    const AllocError *check_container_scope_constraints(const Allocation &alloc,
                                                        const std::vector<AllocSlice> &candidates,
                                                        const Container &c) const;

    std::vector<const SuperCluster::SliceList *> *make_alloc_order(const ScoreContext &ctx,
                                                                   const SuperCluster *sc,
                                                                   const PHV::Size width) const;

    const AllocError *verify_can_pack(const ScoreContext &ctx, const Allocation &alloc,
                                      const SuperCluster *sc,
                                      const std::vector<AllocSlice> &candidates, const Container &c,
                                      ActionSourceCoPackMap &co_pack_hints) const;

    Transaction make_speculated_alloc(const ScoreContext &ctx, const Allocation &alloc,
                                      const SuperCluster *sc,
                                      const std::vector<AllocSlice> &candidates,
                                      const Container &candidates_cont) const;

    std::vector<int> make_start_positions(const ScoreContext &ctx,
                                          const SuperCluster::SliceList *sl,
                                          const PHV::Size width) const;

    std::set<PHV::Size> compute_valid_container_sizes(const SuperCluster *sc) const;

    ContScopeAllocResult try_slices_to_container(const ScoreContext &ctx, const Allocation &alloc,
                                                 const FieldSliceAllocStartMap &fs_starts,
                                                 const Container &c,
                                                 AllocatorMetrics &alloc_metrics,
                                                 const bool skip_mau_checks = false) const;

    SomeContScopeAllocResult try_slices_to_container_group(const ScoreContext &ctx,
                                                           const Allocation &alloc,
                                                           const FieldSliceAllocStartMap &fs_starts,
                                                           const ContainerGroup &group,
                                                           AllocatorMetrics &alloc_metrics) const;

    SomeContScopeAllocResult try_slices_adapter(const ScoreContext &ctx, const Allocation &alloc,
                                                const FieldSliceAllocStartMap &fs_starts,
                                                const ContainerGroup &group,
                                                std::optional<Container> c,
                                                AllocatorMetrics &alloc_metrics) const;

    std::optional<Transaction> try_hints(const ScoreContext &ctx, const Allocation &alloc,
                                         const ContainerGroup &group,
                                         const ActionSourceCoPackMap &action_hints_map,
                                         ordered_set<PHV::FieldSlice> &allocated,
                                         ScAllocAlignment &hint_enforced_alignments,
                                         AllocatorMetrics &alloc_metrics) const;

    AllocResult try_wide_arith_slices_to_container_group(
        const ScoreContext &ctx, const Allocation &alloc, const ScAllocAlignment &alignment,
        const SuperCluster::SliceList *lo, const SuperCluster::SliceList *hi,
        const ContainerGroup &group, AllocatorMetrics &alloc_metrics) const;

    AllocResult try_super_cluster_to_container_group(const ScoreContext &ctx,
                                                     const Allocation &alloc,
                                                     const SuperCluster *sc,
                                                     const ContainerGroup &group,
                                                     AllocatorMetrics &alloc_metrics) const;

    using DfsAllocCb = std::function<bool(const Transaction &)>;
    struct DfsState {
        ScAllocAlignment alignment;
        std::vector<const SuperCluster::SliceList *> allocated;
        std::vector<const SuperCluster::SliceList *> to_allocate;
        DfsState(const ScAllocAlignment &alignment,
                 const std::vector<const SuperCluster::SliceList *> &allocated,
                 const std::vector<const SuperCluster::SliceList *> &to_allocate)
            : alignment(alignment), allocated(allocated), to_allocate(to_allocate) {}
        bool done() const { return to_allocate.empty(); }
        const SuperCluster::SliceList *next_to_allocate() const { return to_allocate.front(); }
        DfsState next_state(
            const ScAllocAlignment &updated_alignment,
            const ordered_set<const SuperCluster::SliceList *> &just_allocated) const;
    };
    class DfsListsAllocator {
        const AllocatorBase &base;
        const int n_step_limit;
        DfsAllocCb yield;
        int n_steps = 0;
        bool caller_pruned = false;               // pruned by caller.
        const AllocError *deepest_err = nullptr;  // will not be nullptr unless succeeded.
        int deepest_depth = -1;
        bool pruned() const { return caller_pruned || n_steps > n_step_limit; }
        std::string depth_prefix(const int depth) const;
        std::optional<ScAllocAlignment> new_alignment_with_start(
            const ScoreContext &ctx, const SuperCluster::SliceList *target, const int sl_start,
            const PHV::Size &width, const ScAllocAlignment &alignment) const;
        bool allocate(const ScoreContext &ctx, const Transaction &tx, const DfsState &state,
                      const int depth, AllocatorMetrics &alloc_metrics);
 
     public:
        DfsListsAllocator(const AllocatorBase &base, int n_step_limit)
            : base(base), n_step_limit(n_step_limit) {}
        bool search_allocate(const ScoreContext &ctx, const Transaction &tx,
                             const ScAllocAlignment &alignment,
                             const std::vector<const SuperCluster::SliceList *> &allocated,
                             const std::vector<const SuperCluster::SliceList *> &to_allocate,
                             const DfsAllocCb &yield, AllocatorMetrics &alloc_metrics);
        const AllocError *get_deepest_err() const { return deepest_err; }
    };
 
    AllocResult alloc_stride(const ScoreContext &ctx, const Allocation &alloc,
                             const std::vector<FieldSlice> &stride,
                             const ContainerGroupsBySize &groups,
                             AllocatorMetrics &alloc_metrics) const;
 
 public:
    explicit AllocatorBase(const PhvKit &kit) : kit_i(kit) {
        kit_i.parser_packing_validator->set_trivial_pass(kit.settings.trivial_alloc);
    };
    virtual ~AllocatorBase(){};


    AllocResult try_sliced_super_cluster(const ScoreContext &ctx, const Allocation &alloc,
                                         const SuperCluster *sc,
                                         const ContainerGroupsBySize &groups,
                                         AllocatorMetrics &alloc_metrics) const;

    PHV::Transaction alloc_deparser_zero_cluster(const ScoreContext &ctx,
                                                 const PHV::Allocation &alloc,
                                                 const PHV::SuperCluster *sc, PhvInfo &phv) const;

    AllocResult alloc_strided_super_clusters(const ScoreContext &ctx, const Allocation &alloc,
                                             const SuperCluster *sc,
                                             const ContainerGroupsBySize &groups,
                                             AllocatorMetrics &alloc_metrics,
                                             const int max_n_slicings = 64) const;
};
 
}  // namespace v2
}  // namespace PHV
 
#endif /* BF_P4C_PHV_V2_ALLOCATOR_BASE_H_ */