llvm/CodeGen/RDFRegisters.h

0001 //===- RDFRegisters.h -------------------------------------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008
0009 #ifndef LLVM_CODEGEN_RDFREGISTERS_H
0010 #define LLVM_CODEGEN_RDFREGISTERS_H
0011
0012 #include "llvm/ADT/BitVector.h"
0013 #include "llvm/ADT/STLExtras.h"
0014 #include "llvm/ADT/iterator_range.h"
0015 #include "llvm/CodeGen/TargetRegisterInfo.h"
0016 #include "llvm/MC/LaneBitmask.h"
0017 #include "llvm/MC/MCRegister.h"
0018 #include <cassert>
0019 #include <cstdint>
0020 #include <map>
0021 #include <set>
0022 #include <vector>
0023
0024 namespace llvm {
0025
0026 class MachineFunction;
0027 class raw_ostream;
0028
0029 namespace rdf {
0030 struct RegisterAggr;
0031
0032 using RegisterId = uint32_t;
0033
0034 template <typename T>
0035 bool disjoint(const std::set<T> &A, const std::set<T> &B) {
0036   auto ItA = A.begin(), EndA = A.end();
0037   auto ItB = B.begin(), EndB = B.end();
0038   while (ItA != EndA && ItB != EndB) {
0039     if (*ItA < *ItB)
0040       ++ItA;
0041     else if (*ItB < *ItA)
0042       ++ItB;
0043     else
0044       return false;
0045   }
0046   return true;
0047 }
0048
0049 // Template class for a map translating uint32_t into arbitrary types.
0050 // The map will act like an indexed set: upon insertion of a new object,
0051 // it will automatically assign a new index to it. Index of 0 is treated
0052 // as invalid and is never allocated.
0053 template <typename T, unsigned N = 32> struct IndexedSet {
0054   IndexedSet() { Map.reserve(N); }
0055
0056   T get(uint32_t Idx) const {
0057     // Index Idx corresponds to Map[Idx-1].
0058     assert(Idx != 0 && !Map.empty() && Idx - 1 < Map.size());
0059     return Map[Idx - 1];
0060   }
0061
0062   uint32_t insert(T Val) {
0063     // Linear search.
0064     auto F = llvm::find(Map, Val);
0065     if (F != Map.end())
0066       return F - Map.begin() + 1;
0067     Map.push_back(Val);
0068     return Map.size(); // Return actual_index + 1.
0069   }
0070
0071   uint32_t find(T Val) const {
0072     auto F = llvm::find(Map, Val);
0073     assert(F != Map.end());
0074     return F - Map.begin() + 1;
0075   }
0076
0077   uint32_t size() const { return Map.size(); }
0078
0079   using const_iterator = typename std::vector<T>::const_iterator;
0080
0081   const_iterator begin() const { return Map.begin(); }
0082   const_iterator end() const { return Map.end(); }
0083
0084 private:
0085   std::vector<T> Map;
0086 };
0087
0088 struct RegisterRef {
0089   RegisterId Reg = 0;
0090   LaneBitmask Mask = LaneBitmask::getNone(); // Only for registers.
0091
0092   constexpr RegisterRef() = default;
0093   constexpr explicit RegisterRef(RegisterId R,
0094                                  LaneBitmask M = LaneBitmask::getAll())
0095       : Reg(R), Mask(isRegId(R) && R != 0 ? M : LaneBitmask::getNone()) {}
0096
0097   // Classify null register as a "register".
0098   constexpr bool isReg() const { return Reg == 0 || isRegId(Reg); }
0099   constexpr bool isUnit() const { return isUnitId(Reg); }
0100   constexpr bool isMask() const { return isMaskId(Reg); }
0101
0102   constexpr unsigned idx() const { return toIdx(Reg); }
0103
0104   constexpr operator bool() const {
0105     return !isReg() || (Reg != 0 && Mask.any());
0106   }
0107
0108   size_t hash() const {
0109     return std::hash<RegisterId>{}(Reg) ^
0110            std::hash<LaneBitmask::Type>{}(Mask.getAsInteger());
0111   }
0112
0113   static constexpr bool isRegId(unsigned Id) {
0114     return Register::isPhysicalRegister(Id);
0115   }
0116   static constexpr bool isUnitId(unsigned Id) {
0117     return Register::isVirtualRegister(Id);
0118   }
0119   static constexpr bool isMaskId(unsigned Id) {
0120     return Register::isStackSlot(Id);
0121   }
0122
0123   static constexpr RegisterId toUnitId(unsigned Idx) {
0124     return Idx | MCRegister::VirtualRegFlag;
0125   }
0126
0127   static constexpr unsigned toIdx(RegisterId Id) {
0128     // Not using virtReg2Index or stackSlot2Index, because they are
0129     // not constexpr.
0130     if (isUnitId(Id))
0131       return Id & ~MCRegister::VirtualRegFlag;
0132     // RegId and MaskId are unchanged.
0133     return Id;
0134   }
0135
0136   bool operator<(RegisterRef) const = delete;
0137   bool operator==(RegisterRef) const = delete;
0138   bool operator!=(RegisterRef) const = delete;
0139 };
0140
0141 struct PhysicalRegisterInfo {
0142   PhysicalRegisterInfo(const TargetRegisterInfo &tri,
0143                        const MachineFunction &mf);
0144
0145   RegisterId getRegMaskId(const uint32_t *RM) const {
0146     return Register::index2StackSlot(RegMasks.find(RM));
0147   }
0148
0149   const uint32_t *getRegMaskBits(RegisterId R) const {
0150     return RegMasks.get(Register::stackSlot2Index(R));
0151   }
0152
0153   bool alias(RegisterRef RA, RegisterRef RB) const;
0154
0155   // Returns the set of aliased physical registers.
0156   std::set<RegisterId> getAliasSet(RegisterId Reg) const;
0157
0158   RegisterRef getRefForUnit(uint32_t U) const {
0159     return RegisterRef(UnitInfos[U].Reg, UnitInfos[U].Mask);
0160   }
0161
0162   const BitVector &getMaskUnits(RegisterId MaskId) const {
0163     return MaskInfos[Register::stackSlot2Index(MaskId)].Units;
0164   }
0165
0166   std::set<RegisterId> getUnits(RegisterRef RR) const;
0167
0168   const BitVector &getUnitAliases(uint32_t U) const {
0169     return AliasInfos[U].Regs;
0170   }
0171
0172   RegisterRef mapTo(RegisterRef RR, unsigned R) const;
0173   const TargetRegisterInfo &getTRI() const { return TRI; }
0174
0175   bool equal_to(RegisterRef A, RegisterRef B) const;
0176   bool less(RegisterRef A, RegisterRef B) const;
0177
0178   void print(raw_ostream &OS, RegisterRef A) const;
0179   void print(raw_ostream &OS, const RegisterAggr &A) const;
0180
0181 private:
0182   struct RegInfo {
0183     const TargetRegisterClass *RegClass = nullptr;
0184   };
0185   struct UnitInfo {
0186     RegisterId Reg = 0;
0187     LaneBitmask Mask;
0188   };
0189   struct MaskInfo {
0190     BitVector Units;
0191   };
0192   struct AliasInfo {
0193     BitVector Regs;
0194   };
0195
0196   const TargetRegisterInfo &TRI;
0197   IndexedSet<const uint32_t *> RegMasks;
0198   std::vector<RegInfo> RegInfos;
0199   std::vector<UnitInfo> UnitInfos;
0200   std::vector<MaskInfo> MaskInfos;
0201   std::vector<AliasInfo> AliasInfos;
0202 };
0203
0204 struct RegisterAggr {
0205   RegisterAggr(const PhysicalRegisterInfo &pri)
0206       : Units(pri.getTRI().getNumRegUnits()), PRI(pri) {}
0207   RegisterAggr(const RegisterAggr &RG) = default;
0208
0209   unsigned size() const { return Units.count(); }
0210   bool empty() const { return Units.none(); }
0211   bool hasAliasOf(RegisterRef RR) const;
0212   bool hasCoverOf(RegisterRef RR) const;
0213
0214   const PhysicalRegisterInfo &getPRI() const { return PRI; }
0215
0216   bool operator==(const RegisterAggr &A) const {
0217     return DenseMapInfo<BitVector>::isEqual(Units, A.Units);
0218   }
0219
0220   static bool isCoverOf(RegisterRef RA, RegisterRef RB,
0221                         const PhysicalRegisterInfo &PRI) {
0222     return RegisterAggr(PRI).insert(RA).hasCoverOf(RB);
0223   }
0224
0225   RegisterAggr &insert(RegisterRef RR);
0226   RegisterAggr &insert(const RegisterAggr &RG);
0227   RegisterAggr &intersect(RegisterRef RR);
0228   RegisterAggr &intersect(const RegisterAggr &RG);
0229   RegisterAggr &clear(RegisterRef RR);
0230   RegisterAggr &clear(const RegisterAggr &RG);
0231
0232   RegisterRef intersectWith(RegisterRef RR) const;
0233   RegisterRef clearIn(RegisterRef RR) const;
0234   RegisterRef makeRegRef() const;
0235
0236   size_t hash() const { return DenseMapInfo<BitVector>::getHashValue(Units); }
0237
0238   struct ref_iterator {
0239     using MapType = std::map<RegisterId, LaneBitmask>;
0240
0241   private:
0242     MapType Masks;
0243     MapType::iterator Pos;
0244     unsigned Index;
0245     const RegisterAggr *Owner;
0246
0247   public:
0248     ref_iterator(const RegisterAggr &RG, bool End);
0249
0250     RegisterRef operator*() const {
0251       return RegisterRef(Pos->first, Pos->second);
0252     }
0253
0254     ref_iterator &operator++() {
0255       ++Pos;
0256       ++Index;
0257       return *this;
0258     }
0259
0260     bool operator==(const ref_iterator &I) const {
0261       assert(Owner == I.Owner);
0262       (void)Owner;
0263       return Index == I.Index;
0264     }
0265
0266     bool operator!=(const ref_iterator &I) const { return !(*this == I); }
0267   };
0268
0269   ref_iterator ref_begin() const { return ref_iterator(*this, false); }
0270   ref_iterator ref_end() const { return ref_iterator(*this, true); }
0271
0272   using unit_iterator = typename BitVector::const_set_bits_iterator;
0273   unit_iterator unit_begin() const { return Units.set_bits_begin(); }
0274   unit_iterator unit_end() const { return Units.set_bits_end(); }
0275
0276   iterator_range<ref_iterator> refs() const {
0277     return make_range(ref_begin(), ref_end());
0278   }
0279   iterator_range<unit_iterator> units() const {
0280     return make_range(unit_begin(), unit_end());
0281   }
0282
0283 private:
0284   BitVector Units;
0285   const PhysicalRegisterInfo &PRI;
0286 };
0287
0288 // This is really a std::map, except that it provides a non-trivial
0289 // default constructor to the element accessed via [].
0290 template <typename KeyType> struct RegisterAggrMap {
0291   RegisterAggrMap(const PhysicalRegisterInfo &pri) : Empty(pri) {}
0292
0293   RegisterAggr &operator[](KeyType Key) {
0294     return Map.emplace(Key, Empty).first->second;
0295   }
0296
0297   auto begin() { return Map.begin(); }
0298   auto end() { return Map.end(); }
0299   auto begin() const { return Map.begin(); }
0300   auto end() const { return Map.end(); }
0301   auto find(const KeyType &Key) const { return Map.find(Key); }
0302
0303 private:
0304   RegisterAggr Empty;
0305   std::map<KeyType, RegisterAggr> Map;
0306
0307 public:
0308   using key_type = typename decltype(Map)::key_type;
0309   using mapped_type = typename decltype(Map)::mapped_type;
0310   using value_type = typename decltype(Map)::value_type;
0311 };
0312
0313 raw_ostream &operator<<(raw_ostream &OS, const RegisterAggr &A);
0314
0315 // Print the lane mask in a short form (or not at all if all bits are set).
0316 struct PrintLaneMaskShort {
0317   PrintLaneMaskShort(LaneBitmask M) : Mask(M) {}
0318   LaneBitmask Mask;
0319 };
0320 raw_ostream &operator<<(raw_ostream &OS, const PrintLaneMaskShort &P);
0321
0322 } // end namespace rdf
0323 } // end namespace llvm
0324
0325 namespace std {
0326
0327 template <> struct hash<llvm::rdf::RegisterRef> {
0328   size_t operator()(llvm::rdf::RegisterRef A) const { //
0329     return A.hash();
0330   }
0331 };
0332
0333 template <> struct hash<llvm::rdf::RegisterAggr> {
0334   size_t operator()(const llvm::rdf::RegisterAggr &A) const { //
0335     return A.hash();
0336   }
0337 };
0338
0339 template <> struct equal_to<llvm::rdf::RegisterRef> {
0340   constexpr equal_to(const llvm::rdf::PhysicalRegisterInfo &pri) : PRI(&pri) {}
0341
0342   bool operator()(llvm::rdf::RegisterRef A, llvm::rdf::RegisterRef B) const {
0343     return PRI->equal_to(A, B);
0344   }
0345
0346 private:
0347   // Make it a pointer just in case. See comment in `less` below.
0348   const llvm::rdf::PhysicalRegisterInfo *PRI;
0349 };
0350
0351 template <> struct equal_to<llvm::rdf::RegisterAggr> {
0352   bool operator()(const llvm::rdf::RegisterAggr &A,
0353                   const llvm::rdf::RegisterAggr &B) const {
0354     return A == B;
0355   }
0356 };
0357
0358 template <> struct less<llvm::rdf::RegisterRef> {
0359   constexpr less(const llvm::rdf::PhysicalRegisterInfo &pri) : PRI(&pri) {}
0360
0361   bool operator()(llvm::rdf::RegisterRef A, llvm::rdf::RegisterRef B) const {
0362     return PRI->less(A, B);
0363   }
0364
0365 private:
0366   // Make it a pointer because apparently some versions of MSVC use std::swap
0367   // on the std::less specialization.
0368   const llvm::rdf::PhysicalRegisterInfo *PRI;
0369 };
0370
0371 } // namespace std
0372
0373 namespace llvm::rdf {
0374 using RegisterSet = std::set<RegisterRef, std::less<RegisterRef>>;
0375 } // namespace llvm::rdf
0376
0377 #endif // LLVM_CODEGEN_RDFREGISTERS_H