LLVM  14.0.0git
RDFRegisters.h
Go to the documentation of this file.
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"
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 
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 {
74 
75  RegisterRef() = default;
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 
104  const MachineFunction &mf);
105 
106  static bool isRegMaskId(RegisterId R) {
107  return Register::isStackSlot(R);
108  }
109 
111  return Register::index2StackSlot(RegMasks.find(RM));
112  }
113 
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 
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 
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;
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 {
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 
183  const PhysicalRegisterInfo &PRI) {
184  return RegisterAggr(PRI).insert(RA).hasCoverOf(RB);
185  }
186 
188  RegisterAggr &insert(const RegisterAggr &RG);
190  RegisterAggr &intersect(const RegisterAggr &RG);
192  RegisterAggr &clear(const RegisterAggr &RG);
193 
195  RegisterRef clearIn(RegisterRef RR) const;
196  RegisterRef makeRegRef() const;
197 
198  size_t hash() const {
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 
217  return RegisterRef(Pos->first, Pos->second);
218  }
219 
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 
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.
253  };
255 
257 } // end namespace rdf
258 
259 } // end namespace llvm
260 
261 namespace std {
262  template <> struct hash<llvm::rdf::RegisterRef> {
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> {
274  const llvm::rdf::RegisterAggr &B) const {
275  return A == B;
276  }
277  };
278 }
279 #endif // LLVM_CODEGEN_RDFREGISTERS_H
llvm::LaneBitmask
Definition: LaneBitmask.h:40
llvm::rdf::RegisterAggr::rr_end
rr_iterator rr_end() const
Definition: RDFRegisters.h:240
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::rdf::RegisterRef::Reg
RegisterId Reg
Definition: RDFRegisters.h:72
Reg
unsigned Reg
Definition: MachineSink.cpp:1566
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::rdf::RegisterAggr::makeRegRef
RegisterRef makeRegRef() const
Definition: RDFRegisters.cpp:324
llvm::rdf::RegisterAggr::insert
RegisterAggr & insert(RegisterRef RR)
Definition: RDFRegisters.cpp:273
llvm::rdf::RegisterAggr::clear
RegisterAggr & clear(RegisterRef RR)
Definition: RDFRegisters.cpp:301
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::BitVector::none
bool none() const
none - Returns true if none of the bits are set.
Definition: BitVector.h:180
llvm::rdf::IndexedSet::get
T get(uint32_t Idx) const
Definition: RDFRegisters.h:39
llvm::Register::stackSlot2Index
static int stackSlot2Index(Register Reg)
Compute the frame index from a register value representing a stack slot.
Definition: Register.h:52
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:231
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::rdf::RegisterAggr::count
unsigned count() const
Definition: RDFRegisters.h:173
llvm::rdf::RegisterAggr::rr_iterator::operator++
rr_iterator & operator++()
Definition: RDFRegisters.h:220
STLExtras.h
llvm::rdf::PhysicalRegisterInfo::getRegMaskId
RegisterId getRegMaskId(const uint32_t *RM) const
Definition: RDFRegisters.h:110
llvm::BitmaskEnumDetail::Mask
std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
Definition: BitmaskEnum.h:80
std::hash< llvm::rdf::RegisterAggr >::operator()
size_t operator()(const llvm::rdf::RegisterAggr &A) const
Definition: RDFRegisters.h:268
llvm::rdf::RegisterAggr::rr_iterator::operator!=
bool operator!=(const rr_iterator &I) const
Definition: RDFRegisters.h:232
llvm::rdf::PhysicalRegisterInfo::getMaskUnits
const BitVector & getMaskUnits(RegisterId MaskId) const
Definition: RDFRegisters.h:130
llvm::rdf::RegisterRef
Definition: RDFRegisters.h:71
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::rdf::PhysicalRegisterInfo::PhysicalRegisterInfo
PhysicalRegisterInfo(const TargetRegisterInfo &tri, const MachineFunction &mf)
Definition: RDFRegisters.cpp:27
llvm::rdf::RegisterAggr::RegisterAggr
RegisterAggr(const PhysicalRegisterInfo &pri)
Definition: RDFRegisters.h:169
llvm::rdf::RegisterAggr::rr_iterator::operator==
bool operator==(const rr_iterator &I) const
Definition: RDFRegisters.h:226
llvm::DenseMapInfo
Definition: APInt.h:34
llvm::rdf::RegisterRef::Mask
LaneBitmask Mask
Definition: RDFRegisters.h:73
llvm::Register::index2StackSlot
static Register index2StackSlot(int FI)
Convert a non-negative frame index to a stack slot register value.
Definition: Register.h:58
llvm::rdf::RegisterRef::operator<
bool operator<(const RegisterRef &RR) const
Definition: RDFRegisters.h:91
llvm::Register::isStackSlot
static bool isStackSlot(unsigned Reg)
isStackSlot - Sometimes it is useful the be able to store a non-negative frame index in a variable th...
Definition: Register.h:44
llvm::rdf::PhysicalRegisterInfo::isRegMaskId
static bool isRegMaskId(RegisterId R)
Definition: RDFRegisters.h:106
llvm::BitVector::count
size_type count() const
count - Returns the number of bits which are set.
Definition: BitVector.h:154
llvm::rdf::RegisterRef::RegisterRef
RegisterRef(RegisterId R, LaneBitmask M=LaneBitmask::getAll())
Definition: RDFRegisters.h:76
llvm::LaneBitmask::getNone
static constexpr LaneBitmask getNone()
Definition: LaneBitmask.h:83
llvm::TargetRegisterClass
Definition: TargetRegisterInfo.h:46
llvm::rdf::PhysicalRegisterInfo::alias
bool alias(RegisterRef RA, RegisterRef RB) const
Definition: RDFRegisters.h:118
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::rdf::RegisterAggr
Definition: RDFRegisters.h:168
llvm::rdf::IndexedSet::IndexedSet
IndexedSet()
Definition: RDFRegisters.h:37
llvm::rdf::IndexedSet::begin
const_iterator begin() const
Definition: RDFRegisters.h:64
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::rdf::PhysicalRegisterInfo
Definition: RDFRegisters.h:102
BitVector.h
llvm::rdf::IndexedSet< const uint32_t * >::const_iterator
typename std::vector< const uint32_t * >::const_iterator const_iterator
Definition: RDFRegisters.h:62
llvm::rdf::RegisterRef::operator!=
bool operator!=(const RegisterRef &RR) const
Definition: RDFRegisters.h:87
llvm::BitVector
Definition: BitVector.h:74
llvm::rdf::RegisterAggr::isCoverOf
static bool isCoverOf(RegisterRef RA, RegisterRef RB, const PhysicalRegisterInfo &PRI)
Definition: RDFRegisters.h:182
std::hash< llvm::rdf::RegisterRef >::operator()
size_t operator()(llvm::rdf::RegisterRef A) const
Definition: RDFRegisters.h:263
std::equal_to< llvm::rdf::RegisterAggr >::operator()
bool operator()(const llvm::rdf::RegisterAggr &A, const llvm::rdf::RegisterAggr &B) const
Definition: RDFRegisters.h:273
llvm::rdf::PhysicalRegisterInfo::getUnitAliases
const BitVector & getUnitAliases(uint32_t U) const
Definition: RDFRegisters.h:134
llvm::rdf::RegisterAggr::empty
bool empty() const
Definition: RDFRegisters.h:174
llvm::rdf::RegisterAggr::hasCoverOf
bool hasCoverOf(RegisterRef RR) const
Definition: RDFRegisters.cpp:258
llvm::rdf::RegisterRef::RegisterRef
RegisterRef()=default
llvm::rdf::PrintLaneMaskOpt
Definition: RDFRegisters.h:250
llvm::rdf::RegisterAggr::hasAliasOf
bool hasAliasOf(RegisterRef RR) const
Definition: RDFRegisters.cpp:245
llvm::rdf::RegisterAggr::rr_iterator::rr_iterator
rr_iterator(const RegisterAggr &RG, bool End)
Definition: RDFRegisters.cpp:367
llvm::find
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1567
llvm::rdf::RegisterAggr::intersect
RegisterAggr & intersect(RegisterRef RR)
Definition: RDFRegisters.cpp:292
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::LaneBitmask::any
constexpr bool any() const
Definition: LaneBitmask.h:53
llvm::rdf::operator<<
raw_ostream & operator<<(raw_ostream &OS, const Print< RegisterRef > &P)
Definition: RDFGraph.cpp:57
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::rdf::PhysicalRegisterInfo::getAliasSet
std::set< RegisterId > getAliasSet(RegisterId Reg) const
Definition: RDFRegisters.cpp:106
llvm::rdf::IndexedSet::find
uint32_t find(T Val) const
Definition: RDFRegisters.h:54
llvm::rdf::IndexedSet::size
uint32_t size() const
Definition: RDFRegisters.h:60
llvm::rdf::RegisterRef::hash
size_t hash() const
Definition: RDFRegisters.h:95
RA
SI optimize exec mask operations pre RA
Definition: SIOptimizeExecMaskingPreRA.cpp:71
llvm::MachineFunction
Definition: MachineFunction.h:230
llvm::rdf::RegisterAggr::rr_begin
rr_iterator rr_begin() const
Definition: RDFRegisters.h:237
llvm::AArch64::RM
@ RM
Definition: AArch64ISelLowering.h:472
RegInfo
Definition: AMDGPUAsmParser.cpp:2366
uint32_t
llvm::rdf::PrintLaneMaskOpt::PrintLaneMaskOpt
PrintLaneMaskOpt(LaneBitmask M)
Definition: RDFRegisters.h:251
llvm::rdf::RegisterAggr::operator==
bool operator==(const RegisterAggr &A) const
Definition: RDFRegisters.h:178
llvm::LaneBitmask::getAsInteger
constexpr Type getAsInteger() const
Definition: LaneBitmask.h:74
llvm::rdf::PrintLaneMaskOpt::Mask
LaneBitmask Mask
Definition: RDFRegisters.h:252
llvm::rdf::RegisterAggr::intersectWith
RegisterRef intersectWith(RegisterRef RR) const
Definition: RDFRegisters.cpp:310
std
Definition: BitVector.h:838
llvm::rdf::IndexedSet::end
const_iterator end() const
Definition: RDFRegisters.h:65
llvm::rdf::RegisterAggr::hash
size_t hash() const
Definition: RDFRegisters.h:198
llvm::rdf::RegisterAggr::rr_iterator::MapType
std::map< RegisterId, LaneBitmask > MapType
Definition: RDFRegisters.h:205
llvm::rdf::RegisterAggr::rr_iterator::operator*
RegisterRef operator*() const
Definition: RDFRegisters.h:216
isEqual
static bool isEqual(const Function &Caller, const Function &Callee)
Definition: Attributes.cpp:1928
llvm::rdf::RegisterAggr::rr_iterator
Definition: RDFRegisters.h:204
llvm::rdf::IndexedSet
Definition: RDFRegisters.h:36
llvm::rdf::RegisterAggr::clearIn
RegisterRef clearIn(RegisterRef RR) const
Definition: RDFRegisters.cpp:320
llvm::rdf::IndexedSet::insert
uint32_t insert(T Val)
Definition: RDFRegisters.h:45
N
#define N
LaneBitmask.h
llvm::rdf::PhysicalRegisterInfo::getRegMaskBits
const uint32_t * getRegMaskBits(RegisterId R) const
Definition: RDFRegisters.h:114
llvm::rdf::RegisterId
uint32_t RegisterId
Definition: RDFRegisters.h:29
llvm::rdf::RegisterAggr::print
void print(raw_ostream &OS) const
Definition: RDFRegisters.cpp:360
RN
It looks like we only need to define PPCfmarto for these because according to these instructions perform RTO on fma s src2 rnd ← FPSCR RN
Definition: README_P9.txt:262
llvm::rdf::RegisterRef::operator==
bool operator==(const RegisterRef &RR) const
Definition: RDFRegisters.h:83
TargetRegisterInfo.h
llvm::LaneBitmask::getAll
static constexpr LaneBitmask getAll()
Definition: LaneBitmask.h:84
llvm::rdf::PhysicalRegisterInfo::getRefForUnit
RegisterRef getRefForUnit(uint32_t U) const
Definition: RDFRegisters.h:126
llvm::rdf::PhysicalRegisterInfo::mapTo
RegisterRef mapTo(RegisterRef RR, unsigned R) const
Definition: RDFRegisters.cpp:230
llvm::rdf::PhysicalRegisterInfo::getTRI
const TargetRegisterInfo & getTRI() const
Definition: RDFRegisters.h:139