LLVM  14.0.0git
HexagonBlockRanges.h
Go to the documentation of this file.
1 //===- HexagonBlockRanges.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_HEXAGONBLOCKRANGES_H
10 #define LLVM_LIB_TARGET_HEXAGON_HEXAGONBLOCKRANGES_H
11 
12 #include "llvm/ADT/BitVector.h"
13 #include "llvm/CodeGen/Register.h"
14 #include <cassert>
15 #include <map>
16 #include <set>
17 #include <utility>
18 #include <vector>
19 
20 namespace llvm {
21 
22 class HexagonSubtarget;
23 class MachineBasicBlock;
24 class MachineFunction;
25 class MachineInstr;
26 class MachineRegisterInfo;
27 class raw_ostream;
28 class TargetInstrInfo;
29 class TargetRegisterInfo;
30 
33 
34  // FIXME: Consolidate duplicate definitions of RegisterRef
35  struct RegisterRef {
37  unsigned Sub;
38 
39  bool operator<(RegisterRef R) const {
40  return Reg < R.Reg || (Reg == R.Reg && Sub < R.Sub);
41  }
42  };
43  using RegisterSet = std::set<RegisterRef>;
44 
45  // This is to represent an "index", which is an abstraction of a position
46  // of an instruction within a basic block.
47  class IndexType {
48  public:
49  enum : unsigned {
50  None = 0,
51  Entry = 1,
52  Exit = 2,
53  First = 11 // 10th + 1st
54  };
55 
56  IndexType() {}
57  IndexType(unsigned Idx) : Index(Idx) {}
58 
59  static bool isInstr(IndexType X) { return X.Index >= First; }
60 
61  operator unsigned() const;
62  bool operator== (unsigned x) const;
63  bool operator== (IndexType Idx) const;
64  bool operator!= (unsigned x) const;
65  bool operator!= (IndexType Idx) const;
67  bool operator< (unsigned Idx) const;
68  bool operator< (IndexType Idx) const;
69  bool operator<= (IndexType Idx) const;
70 
71  private:
72  bool operator> (IndexType Idx) const;
73  bool operator>= (IndexType Idx) const;
74 
75  unsigned Index = None;
76  };
77 
78  // A range of indices, essentially a representation of a live range.
79  // This is also used to represent "dead ranges", i.e. ranges where a
80  // register is dead.
81  class IndexRange : public std::pair<IndexType,IndexType> {
82  public:
83  IndexRange() = default;
84  IndexRange(IndexType Start, IndexType End, bool F = false, bool T = false)
85  : std::pair<IndexType,IndexType>(Start, End), Fixed(F), TiedEnd(T) {}
86 
87  IndexType start() const { return first; }
88  IndexType end() const { return second; }
89 
90  bool operator< (const IndexRange &A) const {
91  return start() < A.start();
92  }
93 
94  bool overlaps(const IndexRange &A) const;
95  bool contains(const IndexRange &A) const;
96  void merge(const IndexRange &A);
97 
98  bool Fixed = false; // Can be renamed? "Fixed" means "no".
99  bool TiedEnd = false; // The end is not a use, but a dead def tied to a use.
100 
101  private:
102  void setStart(const IndexType &S) { first = S; }
103  void setEnd(const IndexType &E) { second = E; }
104  };
105 
106  // A list of index ranges. This represents liveness of a register
107  // in a basic block.
108  class RangeList : public std::vector<IndexRange> {
109  public:
110  void add(IndexType Start, IndexType End, bool Fixed, bool TiedEnd) {
111  push_back(IndexRange(Start, End, Fixed, TiedEnd));
112  }
113  void add(const IndexRange &Range) {
114  push_back(Range);
115  }
116 
117  void include(const RangeList &RL);
118  void unionize(bool MergeAdjacent = false);
119  void subtract(const IndexRange &Range);
120 
121  private:
122  void addsub(const IndexRange &A, const IndexRange &B);
123  };
124 
126  public:
128 
129  MachineInstr *getInstr(IndexType Idx) const;
131  MachineBasicBlock &getBlock() const { return Block; }
132  IndexType getPrevIndex(IndexType Idx) const;
133  IndexType getNextIndex(IndexType Idx) const;
134  void replaceInstr(MachineInstr *OldMI, MachineInstr *NewMI);
135 
136  friend raw_ostream &operator<< (raw_ostream &OS, const InstrIndexMap &Map);
137 
139 
140  private:
141  MachineBasicBlock &Block;
142  std::map<IndexType,MachineInstr*> Map;
143  };
144 
145  using RegToRangeMap = std::map<RegisterRef, RangeList>;
146 
150  const MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI);
151 
152  struct PrintRangeMap {
154  : Map(M), TRI(I) {}
155 
156  friend raw_ostream &operator<< (raw_ostream &OS, const PrintRangeMap &P);
157 
158  private:
159  const RegToRangeMap &Map;
160  const TargetRegisterInfo &TRI;
161  };
162 
163 private:
164  RegisterSet getLiveIns(const MachineBasicBlock &B,
165  const MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI);
166 
167  void computeInitialLiveRanges(InstrIndexMap &IndexMap,
168  RegToRangeMap &LiveMap);
169 
170  MachineFunction &MF;
171  const HexagonSubtarget &HST;
172  const TargetInstrInfo &TII;
173  const TargetRegisterInfo &TRI;
174  BitVector Reserved;
175 };
176 
177 inline HexagonBlockRanges::IndexType::operator unsigned() const {
178  assert(Index >= First);
179  return Index;
180 }
181 
182 inline bool HexagonBlockRanges::IndexType::operator== (unsigned x) const {
183  return Index == x;
184 }
185 
187  return Index == Idx.Index;
188 }
189 
190 inline bool HexagonBlockRanges::IndexType::operator!= (unsigned x) const {
191  return Index != x;
192 }
193 
195  return Index != Idx.Index;
196 }
197 
198 inline
200  assert(Index != None);
201  assert(Index != Exit);
202  if (Index == Entry)
203  Index = First;
204  else
205  ++Index;
206  return *this;
207 }
208 
209 inline bool HexagonBlockRanges::IndexType::operator< (unsigned Idx) const {
210  return operator< (IndexType(Idx));
211 }
212 
214  // !(x < x).
215  if (Index == Idx.Index)
216  return false;
217  // !(None < x) for all x.
218  // !(x < None) for all x.
219  if (Index == None || Idx.Index == None)
220  return false;
221  // !(Exit < x) for all x.
222  // !(x < Entry) for all x.
223  if (Index == Exit || Idx.Index == Entry)
224  return false;
225  // Entry < x for all x != Entry.
226  // x < Exit for all x != Exit.
227  if (Index == Entry || Idx.Index == Exit)
228  return true;
229 
230  return Index < Idx.Index;
231 }
232 
234  return operator==(Idx) || operator<(Idx);
235 }
236 
246 
247 } // end namespace llvm
248 
249 #endif // LLVM_LIB_TARGET_HEXAGON_HEXAGONBLOCKRANGES_H
llvm::HexagonBlockRanges::InstrIndexMap::Last
IndexType Last
Definition: HexagonBlockRanges.h:138
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:103
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::HexagonBlockRanges::IndexType::operator<=
bool operator<=(IndexType Idx) const
Definition: HexagonBlockRanges.h:233
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::HexagonBlockRanges::RegisterRef::operator<
bool operator<(RegisterRef R) const
Definition: HexagonBlockRanges.h:39
llvm::HexagonBlockRanges::IndexType::operator<
bool operator<(unsigned Idx) const
Definition: HexagonBlockRanges.h:209
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:52
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::HexagonBlockRanges::RangeList::include
void include(const RangeList &RL)
Definition: HexagonBlockRanges.cpp:75
llvm::HexagonBlockRanges::IndexType::operator==
bool operator==(unsigned x) const
Definition: HexagonBlockRanges.h:182
llvm::HexagonBlockRanges::IndexRange
Definition: HexagonBlockRanges.h:81
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:233
llvm::HexagonBlockRanges::RangeList::unionize
void unionize(bool MergeAdjacent=false)
Definition: HexagonBlockRanges.cpp:83
llvm::HexagonBlockRanges::RegisterSet
std::set< RegisterRef > RegisterSet
Definition: HexagonBlockRanges.h:43
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::HexagonBlockRanges::IndexRange::contains
bool contains(const IndexRange &A) const
Definition: HexagonBlockRanges.cpp:47
llvm::HexagonBlockRanges::IndexType::Entry
@ Entry
Definition: HexagonBlockRanges.h:51
llvm::HexagonBlockRanges::InstrIndexMap::getBlock
MachineBasicBlock & getBlock() const
Definition: HexagonBlockRanges.h:131
llvm::HexagonBlockRanges::HexagonBlockRanges
HexagonBlockRanges(MachineFunction &MF)
Definition: HexagonBlockRanges.cpp:219
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::HexagonBlockRanges::computeLiveMap
RegToRangeMap computeLiveMap(InstrIndexMap &IndexMap)
Definition: HexagonBlockRanges.cpp:421
llvm::TargetInstrInfo
TargetInstrInfo - Interface to description of machine instruction set.
Definition: TargetInstrInfo.h:97
llvm::HexagonBlockRanges::RangeList::add
void add(const IndexRange &Range)
Definition: HexagonBlockRanges.h:113
llvm::HexagonBlockRanges::RegisterRef::Reg
llvm::Register Reg
Definition: HexagonBlockRanges.h:36
llvm::HexagonBlockRanges::IndexType::operator!=
bool operator!=(unsigned x) const
Definition: HexagonBlockRanges.h:190
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::HexagonBlockRanges::IndexRange::IndexRange
IndexRange(IndexType Start, IndexType End, bool F=false, bool T=false)
Definition: HexagonBlockRanges.h:84
llvm::HexagonBlockRanges::RegisterRef
Definition: HexagonBlockRanges.h:35
llvm::HexagonBlockRanges::IndexRange::end
IndexType end() const
Definition: HexagonBlockRanges.h:88
llvm::HexagonBlockRanges::PrintRangeMap
Definition: HexagonBlockRanges.h:152
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
First
into llvm powi allowing the code generator to produce balanced multiplication trees First
Definition: README.txt:54
llvm::HexagonBlockRanges::InstrIndexMap::InstrIndexMap
InstrIndexMap(MachineBasicBlock &B)
Definition: HexagonBlockRanges.cpp:157
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::HexagonBlockRanges::IndexRange::IndexRange
IndexRange()=default
llvm::operator<<
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:230
BitVector.h
llvm::HexagonBlockRanges::IndexRange::start
IndexType start() const
Definition: HexagonBlockRanges.h:87
IR
Statically lint checks LLVM IR
Definition: Lint.cpp:744
llvm::BitVector
Definition: BitVector.h:74
llvm::HexagonBlockRanges::RegisterRef::Sub
unsigned Sub
Definition: HexagonBlockRanges.h:37
llvm::None
const NoneType None
Definition: None.h:23
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
llvm::HexagonBlockRanges::RangeList
Definition: HexagonBlockRanges.h:108
llvm::HexagonBlockRanges::InstrIndexMap::getNextIndex
IndexType getNextIndex(IndexType Idx) const
Definition: HexagonBlockRanges.cpp:196
llvm::HexagonBlockRanges::IndexType::operator++
IndexType operator++()
Definition: HexagonBlockRanges.h:199
llvm::HexagonBlockRanges::InstrIndexMap::replaceInstr
void replaceInstr(MachineInstr *OldMI, MachineInstr *NewMI)
Definition: HexagonBlockRanges.cpp:206
Index
uint32_t Index
Definition: ELFObjHandler.cpp:84
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
llvm::HexagonBlockRanges::IndexRange::TiedEnd
bool TiedEnd
Definition: HexagonBlockRanges.h:99
llvm::operator<
bool operator<(int64_t V1, const APSInt &V2)
Definition: APSInt.h:338
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::HexagonBlockRanges::RangeList::add
void add(IndexType Start, IndexType End, bool Fixed, bool TiedEnd)
Definition: HexagonBlockRanges.h:110
llvm::HexagonBlockRanges::IndexRange::Fixed
bool Fixed
Definition: HexagonBlockRanges.h:98
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::operator==
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:1974
llvm::HexagonBlockRanges::InstrIndexMap::First
IndexType First
Definition: HexagonBlockRanges.h:138
llvm::MachineFunction
Definition: MachineFunction.h:230
llvm::HexagonBlockRanges::IndexType::IndexType
IndexType()
Definition: HexagonBlockRanges.h:56
llvm::HexagonBlockRanges::InstrIndexMap::operator<<
friend raw_ostream & operator<<(raw_ostream &OS, const InstrIndexMap &Map)
llvm::HexagonBlockRanges::RangeList::subtract
void subtract(const IndexRange &Range)
Definition: HexagonBlockRanges.cpp:141
llvm::HexagonBlockRanges::expandToSubRegs
static RegisterSet expandToSubRegs(RegisterRef R, const MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI)
Definition: HexagonBlockRanges.cpp:261
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::HexagonBlockRanges::IndexRange::operator<
bool operator<(const IndexRange &A) const
Definition: HexagonBlockRanges.h:90
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
llvm::HexagonBlockRanges::IndexType::IndexType
IndexType(unsigned Idx)
Definition: HexagonBlockRanges.h:57
llvm::HexagonBlockRanges::computeDeadMap
RegToRangeMap computeDeadMap(InstrIndexMap &IndexMap, RegToRangeMap &LiveMap)
Definition: HexagonBlockRanges.cpp:431
std
Definition: BitVector.h:838
llvm::HexagonBlockRanges::RegToRangeMap
std::map< RegisterRef, RangeList > RegToRangeMap
Definition: HexagonBlockRanges.h:145
llvm::HexagonBlockRanges::InstrIndexMap
Definition: HexagonBlockRanges.h:125
llvm::HexagonBlockRanges::IndexType::First
@ First
Definition: HexagonBlockRanges.h:53
x
TODO unsigned x
Definition: README.txt:10
llvm::HexagonBlockRanges::InstrIndexMap::getIndex
IndexType getIndex(MachineInstr *MI) const
Definition: HexagonBlockRanges.cpp:176
llvm::HexagonBlockRanges::IndexType
Definition: HexagonBlockRanges.h:47
llvm::HexagonBlockRanges::IndexType::None
@ None
Definition: HexagonBlockRanges.h:50
llvm::HexagonBlockRanges::InstrIndexMap::getPrevIndex
IndexType getPrevIndex(IndexType Idx) const
Definition: HexagonBlockRanges.cpp:184
llvm::HexagonBlockRanges::IndexType::isInstr
static bool isInstr(IndexType X)
Definition: HexagonBlockRanges.h:59
llvm::HexagonBlockRanges::IndexType::Exit
@ Exit
Definition: HexagonBlockRanges.h:52
llvm::HexagonBlockRanges::PrintRangeMap::operator<<
friend raw_ostream & operator<<(raw_ostream &OS, const PrintRangeMap &P)
llvm::HexagonSubtarget
Definition: HexagonSubtarget.h:43
llvm::HexagonBlockRanges
Definition: HexagonBlockRanges.h:31
llvm::HexagonBlockRanges::InstrIndexMap::getInstr
MachineInstr * getInstr(IndexType Idx) const
Definition: HexagonBlockRanges.cpp:171
llvm::HexagonBlockRanges::PrintRangeMap::PrintRangeMap
PrintRangeMap(const RegToRangeMap &M, const TargetRegisterInfo &I)
Definition: HexagonBlockRanges.h:153
Register.h
llvm::HexagonBlockRanges::IndexRange::merge
void merge(const IndexRange &A)
Definition: HexagonBlockRanges.cpp:58
llvm::HexagonBlockRanges::IndexRange::overlaps
bool overlaps(const IndexRange &A) const
Definition: HexagonBlockRanges.cpp:34
llvm::FloatStyle::Fixed
@ Fixed