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_LIB_TARGET_HEXAGON_RDFREGISTERS_H
10 #define LLVM_LIB_TARGET_HEXAGON_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 
96 
97   struct PhysicalRegisterInfo {
98     PhysicalRegisterInfo(const TargetRegisterInfo &tri,
99                          const MachineFunction &mf);
100 
101     static bool isRegMaskId(RegisterId R) {
102       return Register::isStackSlot(R);
103     }
104 
105     RegisterId getRegMaskId(const uint32_t *RM) const {
106       return Register::index2StackSlot(RegMasks.find(RM));
107     }
108 
109     const uint32_t *getRegMaskBits(RegisterId R) const {
110       return RegMasks.get(Register::stackSlot2Index(R));
111     }
112 
113     RegisterRef normalize(RegisterRef RR) const;
114 
115     bool alias(RegisterRef RA, RegisterRef RB) const {
116       if (!isRegMaskId(RA.Reg))
117         return !isRegMaskId(RB.Reg) ? aliasRR(RA, RB) : aliasRM(RA, RB);
118       return !isRegMaskId(RB.Reg) ? aliasRM(RB, RA) : aliasMM(RA, RB);
119     }
120 
121     std::set<RegisterId> getAliasSet(RegisterId Reg) const;
122 
123     RegisterRef getRefForUnit(uint32_t U) const {
124       return RegisterRef(UnitInfos[U].Reg, UnitInfos[U].Mask);
125     }
126 
127     const BitVector &getMaskUnits(RegisterId MaskId) const {
128       return MaskInfos[Register::stackSlot2Index(MaskId)].Units;
129     }
130 
131     RegisterRef mapTo(RegisterRef RR, unsigned R) const;
132     const TargetRegisterInfo &getTRI() const { return TRI; }
133 
134   private:
135     struct RegInfo {
136       const TargetRegisterClass *RegClass = nullptr;
137     };
138     struct UnitInfo {
139       RegisterId Reg = 0;
140       LaneBitmask Mask;
141     };
142     struct MaskInfo {
143       BitVector Units;
144     };
145 
146     const TargetRegisterInfo &TRI;
147     IndexedSet<const uint32_t*> RegMasks;
148     std::vector<RegInfo> RegInfos;
149     std::vector<UnitInfo> UnitInfos;
150     std::vector<MaskInfo> MaskInfos;
151 
152     bool aliasRR(RegisterRef RA, RegisterRef RB) const;
153     bool aliasRM(RegisterRef RR, RegisterRef RM) const;
154     bool aliasMM(RegisterRef RM, RegisterRef RN) const;
155   };
156 
157   struct RegisterAggr {
158     RegisterAggr(const PhysicalRegisterInfo &pri)
159         : Units(pri.getTRI().getNumRegUnits()), PRI(pri) {}
160     RegisterAggr(const RegisterAggr &RG) = default;
161 
162     bool empty() const { return Units.none(); }
163     bool hasAliasOf(RegisterRef RR) const;
164     bool hasCoverOf(RegisterRef RR) const;
165 
166     static bool isCoverOf(RegisterRef RA, RegisterRef RB,
167                           const PhysicalRegisterInfo &PRI) {
168       return RegisterAggr(PRI).insert(RA).hasCoverOf(RB);
169     }
170 
171     RegisterAggr &insert(RegisterRef RR);
172     RegisterAggr &insert(const RegisterAggr &RG);
173     RegisterAggr &intersect(RegisterRef RR);
174     RegisterAggr &intersect(const RegisterAggr &RG);
175     RegisterAggr &clear(RegisterRef RR);
176     RegisterAggr &clear(const RegisterAggr &RG);
177 
178     RegisterRef intersectWith(RegisterRef RR) const;
179     RegisterRef clearIn(RegisterRef RR) const;
180     RegisterRef makeRegRef() const;
181 
182     void print(raw_ostream &OS) const;
183 
184     struct rr_iterator {
185       using MapType = std::map<RegisterId, LaneBitmask>;
186 
187     private:
188       MapType Masks;
189       MapType::iterator Pos;
190       unsigned Index;
191       const RegisterAggr *Owner;
192 
193     public:
194       rr_iterator(const RegisterAggr &RG, bool End);
195 
196       RegisterRef operator*() const {
197         return RegisterRef(Pos->first, Pos->second);
198       }
199 
200       rr_iterator &operator++() {
201         ++Pos;
202         ++Index;
203         return *this;
204       }
205 
206       bool operator==(const rr_iterator &I) const {
207         assert(Owner == I.Owner);
208         (void)Owner;
209         return Index == I.Index;
210       }
211 
212       bool operator!=(const rr_iterator &I) const {
213         return !(*this == I);
214       }
215     };
216 
217     rr_iterator rr_begin() const {
218       return rr_iterator(*this, false);
219     }
220     rr_iterator rr_end() const {
221       return rr_iterator(*this, true);
222     }
223 
224   private:
225     BitVector Units;
226     const PhysicalRegisterInfo &PRI;
227   };
228 
229   // Optionally print the lane mask, if it is not ~0.
230   struct PrintLaneMaskOpt {
231     PrintLaneMaskOpt(LaneBitmask M) : Mask(M) {}
232     LaneBitmask Mask;
233   };
234   raw_ostream &operator<< (raw_ostream &OS, const PrintLaneMaskOpt &P);
235 
236 } // end namespace rdf
237 
238 } // end namespace llvm
239 
240 #endif // LLVM_LIB_TARGET_HEXAGON_RDFREGISTERS_H
241