LLVM  9.0.0svn
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 <cassert>
14 #include <map>
15 #include <set>
16 #include <utility>
17 #include <vector>
18 
19 namespace llvm {
20 
21 class HexagonSubtarget;
22 class MachineBasicBlock;
23 class MachineFunction;
24 class MachineInstr;
25 class MachineRegisterInfo;
26 class raw_ostream;
27 class TargetInstrInfo;
28 class TargetRegisterInfo;
29 
32 
33  struct RegisterRef {
34  unsigned Reg, Sub;
35 
36  bool operator<(RegisterRef R) const {
37  return Reg < R.Reg || (Reg == R.Reg && Sub < R.Sub);
38  }
39  };
40  using RegisterSet = std::set<RegisterRef>;
41 
42  // This is to represent an "index", which is an abstraction of a position
43  // of an instruction within a basic block.
44  class IndexType {
45  public:
46  enum : unsigned {
47  None = 0,
48  Entry = 1,
49  Exit = 2,
50  First = 11 // 10th + 1st
51  };
52 
53  IndexType() {}
54  IndexType(unsigned Idx) : Index(Idx) {}
55 
56  static bool isInstr(IndexType X) { return X.Index >= First; }
57 
58  operator unsigned() const;
59  bool operator== (unsigned x) const;
60  bool operator== (IndexType Idx) const;
61  bool operator!= (unsigned x) const;
62  bool operator!= (IndexType Idx) const;
63  IndexType operator++ ();
64  bool operator< (unsigned Idx) const;
65  bool operator< (IndexType Idx) const;
66  bool operator<= (IndexType Idx) const;
67 
68  private:
69  bool operator> (IndexType Idx) const;
70  bool operator>= (IndexType Idx) const;
71 
72  unsigned Index = None;
73  };
74 
75  // A range of indices, essentially a representation of a live range.
76  // This is also used to represent "dead ranges", i.e. ranges where a
77  // register is dead.
78  class IndexRange : public std::pair<IndexType,IndexType> {
79  public:
80  IndexRange() = default;
81  IndexRange(IndexType Start, IndexType End, bool F = false, bool T = false)
82  : std::pair<IndexType,IndexType>(Start, End), Fixed(F), TiedEnd(T) {}
83 
84  IndexType start() const { return first; }
85  IndexType end() const { return second; }
86 
87  bool operator< (const IndexRange &A) const {
88  return start() < A.start();
89  }
90 
91  bool overlaps(const IndexRange &A) const;
92  bool contains(const IndexRange &A) const;
93  void merge(const IndexRange &A);
94 
95  bool Fixed = false; // Can be renamed? "Fixed" means "no".
96  bool TiedEnd = false; // The end is not a use, but a dead def tied to a use.
97 
98  private:
99  void setStart(const IndexType &S) { first = S; }
100  void setEnd(const IndexType &E) { second = E; }
101  };
102 
103  // A list of index ranges. This represents liveness of a register
104  // in a basic block.
105  class RangeList : public std::vector<IndexRange> {
106  public:
107  void add(IndexType Start, IndexType End, bool Fixed, bool TiedEnd) {
108  push_back(IndexRange(Start, End, Fixed, TiedEnd));
109  }
110  void add(const IndexRange &Range) {
111  push_back(Range);
112  }
113 
114  void include(const RangeList &RL);
115  void unionize(bool MergeAdjacent = false);
116  void subtract(const IndexRange &Range);
117 
118  private:
119  void addsub(const IndexRange &A, const IndexRange &B);
120  };
121 
123  public:
125 
126  MachineInstr *getInstr(IndexType Idx) const;
127  IndexType getIndex(MachineInstr *MI) const;
128  MachineBasicBlock &getBlock() const { return Block; }
129  IndexType getPrevIndex(IndexType Idx) const;
130  IndexType getNextIndex(IndexType Idx) const;
131  void replaceInstr(MachineInstr *OldMI, MachineInstr *NewMI);
132 
133  friend raw_ostream &operator<< (raw_ostream &OS, const InstrIndexMap &Map);
134 
135  IndexType First, Last;
136 
137  private:
138  MachineBasicBlock &Block;
139  std::map<IndexType,MachineInstr*> Map;
140  };
141 
142  using RegToRangeMap = std::map<RegisterRef, RangeList>;
143 
147  const MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI);
148 
149  struct PrintRangeMap {
151  : Map(M), TRI(I) {}
152 
153  friend raw_ostream &operator<< (raw_ostream &OS, const PrintRangeMap &P);
154 
155  private:
156  const RegToRangeMap &Map;
157  const TargetRegisterInfo &TRI;
158  };
159 
160 private:
161  RegisterSet getLiveIns(const MachineBasicBlock &B,
163 
164  void computeInitialLiveRanges(InstrIndexMap &IndexMap,
165  RegToRangeMap &LiveMap);
166 
167  MachineFunction &MF;
168  const HexagonSubtarget &HST;
169  const TargetInstrInfo &TII;
170  const TargetRegisterInfo &TRI;
171  BitVector Reserved;
172 };
173 
174 inline HexagonBlockRanges::IndexType::operator unsigned() const {
175  assert(Index >= First);
176  return Index;
177 }
178 
179 inline bool HexagonBlockRanges::IndexType::operator== (unsigned x) const {
180  return Index == x;
181 }
182 
184  return Index == Idx.Index;
185 }
186 
187 inline bool HexagonBlockRanges::IndexType::operator!= (unsigned x) const {
188  return Index != x;
189 }
190 
192  return Index != Idx.Index;
193 }
194 
195 inline
197  assert(Index != None);
198  assert(Index != Exit);
199  if (Index == Entry)
200  Index = First;
201  else
202  ++Index;
203  return *this;
204 }
205 
206 inline bool HexagonBlockRanges::IndexType::operator< (unsigned Idx) const {
207  return operator< (IndexType(Idx));
208 }
209 
211  // !(x < x).
212  if (Index == Idx.Index)
213  return false;
214  // !(None < x) for all x.
215  // !(x < None) for all x.
216  if (Index == None || Idx.Index == None)
217  return false;
218  // !(Exit < x) for all x.
219  // !(x < Entry) for all x.
220  if (Index == Exit || Idx.Index == Entry)
221  return false;
222  // Entry < x for all x != Entry.
223  // x < Exit for all x != Exit.
224  if (Index == Entry || Idx.Index == Exit)
225  return true;
226 
227  return Index < Idx.Index;
228 }
229 
231  return operator==(Idx) || operator<(Idx);
232 }
233 
243 
244 } // end namespace llvm
245 
246 #endif // LLVM_LIB_TARGET_HEXAGON_HEXAGONBLOCKRANGES_H
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
This class represents lattice values for constants.
Definition: AllocatorList.h:23
bool operator>(int64_t V1, const APSInt &V2)
Definition: APSInt.h:344
static RegisterSet expandToSubRegs(RegisterRef R, const MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI)
unsigned second
unsigned const TargetRegisterInfo * TRI
F(f)
std::set< RegisterRef > RegisterSet
void add(const IndexRange &Range)
return AArch64::GPR64RegClass contains(Reg)
std::map< RegisterRef, RangeList > RegToRangeMap
bool operator<=(int64_t V1, const APSInt &V2)
Definition: APSInt.h:341
void add(IndexType Start, IndexType End, bool Fixed, bool TiedEnd)
Definition: BitVector.h:937
bool operator<=(IndexType Idx) const
bool operator>=(int64_t V1, const APSInt &V2)
Definition: APSInt.h:342
const HexagonInstrInfo * TII
TargetInstrInfo - Interface to description of machine instruction set.
#define P(N)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
unsigned const MachineRegisterInfo * MRI
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
unsigned first
IndexRange(IndexType Start, IndexType End, bool F=false, bool T=false)
HexagonBlockRanges(MachineFunction &MF)
PrintRangeMap(const RegToRangeMap &M, const TargetRegisterInfo &I)
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
bool operator!=(uint64_t V1, const APInt &V2)
Definition: APInt.h:1968
Representation of each machine instruction.
Definition: MachineInstr.h:64
RegToRangeMap computeLiveMap(InstrIndexMap &IndexMap)
#define I(x, y, z)
Definition: MD5.cpp:58
RegToRangeMap computeDeadMap(InstrIndexMap &IndexMap, RegToRangeMap &LiveMap)
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2038
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
IRTranslator LLVM IR MI
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:1966
Statically lint checks LLVM IR
Definition: Lint.cpp:192