Home | History | Annotate | Line # | Download | only in CodeGen 
      1 //===- RDFRegisters.h -------------------------------------------*- C++ -*-===//
      2 //
      3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
      4 // See https://llvm.org/LICENSE.txt for license information.
      5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
      6 //
      7 //===----------------------------------------------------------------------===//
      8 
      9 #ifndef LLVM_CODEGEN_RDFREGISTERS_H
     10 #define LLVM_CODEGEN_RDFREGISTERS_H
     11 
     12 #include "llvm/ADT/BitVector.h"
     13 #include "llvm/ADT/STLExtras.h"
     14 #include "llvm/CodeGen/TargetRegisterInfo.h"
     15 #include "llvm/MC/LaneBitmask.h"
     16 #include <cassert>
     17 #include <cstdint>
     18 #include <map>
     19 #include <set>
     20 #include <vector>
     21 
     22 namespace llvm {
     23 
     24 class MachineFunction;
     25 class raw_ostream;
     26 
     27 namespace rdf {
     28 
     29   using RegisterId = uint32_t;
     30 
     31   // Template class for a map translating uint32_t into arbitrary types.
     32   // The map will act like an indexed set: upon insertion of a new object,
     33   // it will automatically assign a new index to it. Index of 0 is treated
     34   // as invalid and is never allocated.
     35   template <typename T, unsigned N = 32>
     36   struct IndexedSet {
     37     IndexedSet() { Map.reserve(N); }
     38 
     39     T get(uint32_t Idx) const {
     40       // Index Idx corresponds to Map[Idx-1].
     41       assert(Idx != 0 && !Map.empty() && Idx-1 < Map.size());
     42       return Map[Idx-1];
     43     }
     44 
     45     uint32_t insert(T Val) {
     46       // Linear search.
     47       auto F = llvm::find(Map, Val);
     48       if (F != Map.end())
     49         return F - Map.begin() + 1;
     50       Map.push_back(Val);
     51       return Map.size();  // Return actual_index + 1.
     52     }
     53 
     54     uint32_t find(T Val) const {
     55       auto F = llvm::find(Map, Val);
     56       assert(F != Map.end());
     57       return F - Map.begin() + 1;
     58     }
     59 
     60     uint32_t size() const { return Map.size(); }
     61 
     62     using const_iterator = typename std::vector<T>::const_iterator;
     63 
     64     const_iterator begin() const { return Map.begin(); }
     65     const_iterator end() const { return Map.end(); }
     66 
     67   private:
     68     std::vector<T> Map;
     69   };
     70 
     71   struct RegisterRef {
     72     RegisterId Reg = 0;
     73     LaneBitmask Mask = LaneBitmask::getNone();
     74 
     75     RegisterRef() = default;
     76     explicit RegisterRef(RegisterId R, LaneBitmask M = LaneBitmask::getAll())
     77       : Reg(R), Mask(R != 0 ? M : LaneBitmask::getNone()) {}
     78 
     79     operator bool() const {
     80       return Reg != 0 && Mask.any();
     81     }
     82 
     83     bool operator== (const RegisterRef &RR) const {
     84       return Reg == RR.Reg && Mask == RR.Mask;
     85     }
     86 
     87     bool operator!= (const RegisterRef &RR) const {
     88       return !operator==(RR);
     89     }
     90 
     91     bool operator< (const RegisterRef &RR) const {
     92       return Reg < RR.Reg || (Reg == RR.Reg && Mask < RR.Mask);
     93     }
     94 
     95     size_t hash() const {
     96       return std::hash<RegisterId>{}(Reg) ^
     97              std::hash<LaneBitmask::Type>{}(Mask.getAsInteger());
     98     }
     99   };
    100 
    101 
    102   struct PhysicalRegisterInfo {
    103     PhysicalRegisterInfo(const TargetRegisterInfo &tri,
    104                          const MachineFunction &mf);
    105 
    106     static bool isRegMaskId(RegisterId R) {
    107       return Register::isStackSlot(R);
    108     }
    109 
    110     RegisterId getRegMaskId(const uint32_t *RM) const {
    111       return Register::index2StackSlot(RegMasks.find(RM));
    112     }
    113 
    114     const uint32_t *getRegMaskBits(RegisterId R) const {
    115       return RegMasks.get(Register::stackSlot2Index(R));
    116     }
    117 
    118     bool alias(RegisterRef RA, RegisterRef RB) const {
    119       if (!isRegMaskId(RA.Reg))
    120         return !isRegMaskId(RB.Reg) ? aliasRR(RA, RB) : aliasRM(RA, RB);
    121       return !isRegMaskId(RB.Reg) ? aliasRM(RB, RA) : aliasMM(RA, RB);
    122     }
    123 
    124     std::set<RegisterId> getAliasSet(RegisterId Reg) const;
    125 
    126     RegisterRef getRefForUnit(uint32_t U) const {
    127       return RegisterRef(UnitInfos[U].Reg, UnitInfos[U].Mask);
    128     }
    129 
    130     const BitVector &getMaskUnits(RegisterId MaskId) const {
    131       return MaskInfos[Register::stackSlot2Index(MaskId)].Units;
    132     }
    133 
    134     const BitVector &getUnitAliases(uint32_t U) const {
    135       return AliasInfos[U].Regs;
    136     }
    137 
    138     RegisterRef mapTo(RegisterRef RR, unsigned R) const;
    139     const TargetRegisterInfo &getTRI() const { return TRI; }
    140 
    141   private:
    142     struct RegInfo {
    143       const TargetRegisterClass *RegClass = nullptr;
    144     };
    145     struct UnitInfo {
    146       RegisterId Reg = 0;
    147       LaneBitmask Mask;
    148     };
    149     struct MaskInfo {
    150       BitVector Units;
    151     };
    152     struct AliasInfo {
    153       BitVector Regs;
    154     };
    155 
    156     const TargetRegisterInfo &TRI;
    157     IndexedSet<const uint32_t*> RegMasks;
    158     std::vector<RegInfo> RegInfos;
    159     std::vector<UnitInfo> UnitInfos;
    160     std::vector<MaskInfo> MaskInfos;
    161     std::vector<AliasInfo> AliasInfos;
    162 
    163     bool aliasRR(RegisterRef RA, RegisterRef RB) const;
    164     bool aliasRM(RegisterRef RR, RegisterRef RM) const;
    165     bool aliasMM(RegisterRef RM, RegisterRef RN) const;
    166   };
    167 
    168   struct RegisterAggr {
    169     RegisterAggr(const PhysicalRegisterInfo &pri)
    170         : Units(pri.getTRI().getNumRegUnits()), PRI(pri) {}
    171     RegisterAggr(const RegisterAggr &RG) = default;
    172 
    173     unsigned count() const { return Units.count(); }
    174     bool empty() const { return Units.none(); }
    175     bool hasAliasOf(RegisterRef RR) const;
    176     bool hasCoverOf(RegisterRef RR) const;
    177 
    178     bool operator==(const RegisterAggr &A) const {
    179       return DenseMapInfo<BitVector>::isEqual(Units, A.Units);
    180     }
    181 
    182     static bool isCoverOf(RegisterRef RA, RegisterRef RB,
    183                           const PhysicalRegisterInfo &PRI) {
    184       return RegisterAggr(PRI).insert(RA).hasCoverOf(RB);
    185     }
    186 
    187     RegisterAggr &insert(RegisterRef RR);
    188     RegisterAggr &insert(const RegisterAggr &RG);
    189     RegisterAggr &intersect(RegisterRef RR);
    190     RegisterAggr &intersect(const RegisterAggr &RG);
    191     RegisterAggr &clear(RegisterRef RR);
    192     RegisterAggr &clear(const RegisterAggr &RG);
    193 
    194     RegisterRef intersectWith(RegisterRef RR) const;
    195     RegisterRef clearIn(RegisterRef RR) const;
    196     RegisterRef makeRegRef() const;
    197 
    198     size_t hash() const {
    199       return DenseMapInfo<BitVector>::getHashValue(Units);
    200     }
    201 
    202     void print(raw_ostream &OS) const;
    203 
    204     struct rr_iterator {
    205       using MapType = std::map<RegisterId, LaneBitmask>;
    206 
    207     private:
    208       MapType Masks;
    209       MapType::iterator Pos;
    210       unsigned Index;
    211       const RegisterAggr *Owner;
    212 
    213     public:
    214       rr_iterator(const RegisterAggr &RG, bool End);
    215 
    216       RegisterRef operator*() const {
    217         return RegisterRef(Pos->first, Pos->second);
    218       }
    219 
    220       rr_iterator &operator++() {
    221         ++Pos;
    222         ++Index;
    223         return *this;
    224       }
    225 
    226       bool operator==(const rr_iterator &I) const {
    227         assert(Owner == I.Owner);
    228         (void)Owner;
    229         return Index == I.Index;
    230       }
    231 
    232       bool operator!=(const rr_iterator &I) const {
    233         return !(*this == I);
    234       }
    235     };
    236 
    237     rr_iterator rr_begin() const {
    238       return rr_iterator(*this, false);
    239     }
    240     rr_iterator rr_end() const {
    241       return rr_iterator(*this, true);
    242     }
    243 
    244   private:
    245     BitVector Units;
    246     const PhysicalRegisterInfo &PRI;
    247   };
    248 
    249   // Optionally print the lane mask, if it is not ~0.
    250   struct PrintLaneMaskOpt {
    251     PrintLaneMaskOpt(LaneBitmask M) : Mask(M) {}
    252     LaneBitmask Mask;
    253   };
    254   raw_ostream &operator<< (raw_ostream &OS, const PrintLaneMaskOpt &P);
    255 
    256   raw_ostream &operator<< (raw_ostream &OS, const RegisterAggr &A);
    257 } // end namespace rdf
    258 
    259 } // end namespace llvm
    260 
    261 namespace std {
    262   template <> struct hash<llvm::rdf::RegisterRef> {
    263     size_t operator()(llvm::rdf::RegisterRef A) const {
    264       return A.hash();
    265     }
    266   };
    267   template <> struct hash<llvm::rdf::RegisterAggr> {
    268     size_t operator()(const llvm::rdf::RegisterAggr &A) const {
    269       return A.hash();
    270     }
    271   };
    272   template <> struct equal_to<llvm::rdf::RegisterAggr> {
    273     bool operator()(const llvm::rdf::RegisterAggr &A,
    274                     const llvm::rdf::RegisterAggr &B) const {
    275       return A == B;
    276     }
    277   };
    278 }
    279 #endif // LLVM_CODEGEN_RDFREGISTERS_H
    280