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