live_range_split.h

 
#ifndef BACKENDS_TOFINO_BF_P4C_PHV_LIVE_RANGE_SPLIT_H_
#define BACKENDS_TOFINO_BF_P4C_PHV_LIVE_RANGE_SPLIT_H_
 
#include <set>
#include <vector>
 
#include "phv/analysis/dark_live_range.h"
#include "phv/fieldslice_live_range.h"
#include "phv/phv_fields.h"
 
namespace PHV {
 
class AllocUtils;
 
class ContainerOccupancy {
    int minStage;
    int maxStage;
    std::vector<bitvec> vec;
    unsigned containerWidth;
 
    unsigned vecIdx(PHV::StageAndAccess sa) const {
        BUG_CHECK(sa.first >= minStage && sa.first <= maxStage,
                  "vecIdx (%1%) out of stage range [%2%, %3%]", sa.first, minStage, maxStage);
        int stage = sa.first - minStage;
        int offset = sa.second.isWrite() ? 1 : 0;
        int val = stage * 2 + offset;
        BUG_CHECK(val >= 0, "Invalid StageAndAccess stage %1%", val);
        return static_cast<unsigned>(val);
    }
 
    std::vector<le_bitrange> availBitsAt(unsigned i, unsigned minLength);
 
    friend std::ostream &operator<<(std::ostream &, const ContainerOccupancy &);
 
 public:
    ContainerOccupancy() : containerWidth(0) {}
 
    ContainerOccupancy(int minStage, int maxStage, unsigned containerWidth)
        : minStage(minStage),
          maxStage(maxStage),
          vec((maxStage - minStage + 1) * 2),
          containerWidth(containerWidth) {
        BUG_CHECK(minStage >= -1, "ContainerOccupancy minStage (%1%) must be >= -1");
        BUG_CHECK(maxStage >= minStage, "Invalid ContainerOccupancy stage range (%1% > %2%)",
                  minStage, maxStage);
    }
 
    void setRange(StageAndAccess begin, StageAndAccess end, le_bitrange range);
 
    std::vector<le_bitrange> availBitsAt(PHV::StageAndAccess sa, unsigned minLength = 0) {
        return availBitsAt(vecIdx(sa), minLength);
    }
 
    bool isRangeAvailable(StageAndAccess begin, StageAndAccess end, le_bitrange range);
};
 
struct FreeSlice {
    Container container;
    le_bitrange range;
    LiveRange lr;
 
    bool operator==(const FreeSlice &c) const {
        return container == c.container && range == c.range && lr.start == c.lr.start &&
               lr.end == c.lr.end;
    }
    bool operator!=(const FreeSlice &c) const { return !(*this == c); }
    bool operator<(const FreeSlice &c) const {
        if (container != c.container) return container < c.container;
        if (range != c.range) return range < c.range;
        if (lr.start != c.lr.start) return lr.start < c.lr.start;
        if (lr.end != c.lr.end) return lr.end < c.lr.end;
        return false;
    }
 
    bool isFullyAvailableAt(int stage) const {
        if (lr.start.first > stage || (lr.start.first == stage && !lr.start.second.isRead())) {
            return false;
        }
        if (lr.end.first < stage || (lr.end.first == stage && !lr.end.second.isWrite())) {
            return false;
        }
        return true;
    }
 
    friend std::ostream &operator<<(std::ostream &, const FreeSlice &);
};
 
class LiveRangeSplit {
 public:
    using ContainerSequence = ordered_set<FreeSlice>;
    using ContainerSequences = std::set<ContainerSequence>;
 
 private:
    static const FieldUse READ;
    static const FieldUse WRITE;
 
    const Allocation &alloc;
    const PhvInfo &phvInfo;
    const AllocUtils &utils;
    const DependencyGraph &deps;
    const std::list<ContainerGroup *> containerGroups;
    const DarkLiveRangeMap &liveRangeMap;
    const NonMochaDarkFields &nonMochaDark;
 
    std::map<Container, ContainerGroup *> groupForContainer;
    std::map<const Field *, std::set<StageAndAccess>> nonMochaStagesForField;
    std::map<const Field *, std::set<StageAndAccess>> nonDarkStagesForField;
 
    std::set<StageAndAccess> getMochaIncompatibleStagesForField(const Field *field) const;
    std::set<StageAndAccess> getDarkIncompatibleStagesForField(const Field *field) const;
 
 public:
    explicit LiveRangeSplit(const Allocation &alloc, const PhvInfo &phv, const AllocUtils &utils,
                            const DependencyGraph &deps,
                            const std::list<ContainerGroup *> &containerGroups,
                            const DarkLiveRangeMap &liveRangeMap,
                            const NonMochaDarkFields &nonMochaDark);
 
    std::set<FreeSlice> buildContainerOccupancy(StageAndAccess begin, StageAndAccess end,
                                                const FieldSlice &fs) const;
 
    ContainerSequences buildContainerSeqs(const std::set<FreeSlice> &avail, StageAndAccess begin,
                                          StageAndAccess end) const;
 
    ContainerSequences findLiveRangeSplits(StageAndAccess begin, StageAndAccess end,
                                           const FieldSlice &fs) const;
    ContainerSequences findLiveRangeSplits(const LiveRangeInfo &lri, const FieldSlice &fs) const;
 
    static void report(const ContainerSequences &splits);
};
 
class LiveRangeSplitOrFail : public Visitor {
    std::function<const ConcreteAllocation *()> getAllocFn;
    const std::list<const PHV::SuperCluster *> &unallocated;
    PhvInfo &phv;
    const PHV::AllocUtils &utils;
    const DependencyGraph &deps;
    const DarkLiveRangeMap &liveRangeMap;
    const NonMochaDarkFields &nonMochaDark;
 
    const IR::Node *apply_visitor(const IR::Node *root, const char *name = 0) override;
 
 public:
    LiveRangeSplitOrFail(std::function<const ConcreteAllocation *()> getAllocFn,
                         const std::list<const PHV::SuperCluster *> &unallocated, PhvInfo &phv,
                         const PHV::AllocUtils &utils, const DependencyGraph &deps,
                         const DarkLiveRangeMap &liveRangeMap,
                         const NonMochaDarkFields &nonMochaDark)
        : getAllocFn(getAllocFn),
          unallocated(unallocated),
          phv(phv),
          utils(utils),
          deps(deps),
          liveRangeMap(liveRangeMap),
          nonMochaDark(nonMochaDark) {}
};
 
}  // namespace PHV
 
#endif /* BACKENDS_TOFINO_BF_P4C_PHV_LIVE_RANGE_SPLIT_H_ */