LLVM  6.0.0svn
HexagonBlockRanges.h
Go to the documentation of this file.
1 //===- HexagonBlockRanges.h -------------------------------------*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #ifndef LLVM_LIB_TARGET_HEXAGON_HEXAGONBLOCKRANGES_H
11 #define LLVM_LIB_TARGET_HEXAGON_HEXAGONBLOCKRANGES_H
12 
13 #include "llvm/ADT/BitVector.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  struct RegisterRef {
35  unsigned Reg, Sub;
36 
37  bool operator<(RegisterRef R) const {
38  return Reg < R.Reg || (Reg == R.Reg && Sub < R.Sub);
39  }
40  };
41  using RegisterSet = std::set<RegisterRef>;
42 
43  // This is to represent an "index", which is an abstraction of a position
44  // of an instruction within a basic block.
45  class IndexType {
46  public:
47  enum : unsigned {
48  None = 0,
49  Entry = 1,
50  Exit = 2,
51  First = 11 // 10th + 1st
52  };
53 
54  IndexType() {}
55  IndexType(unsigned Idx) : Index(Idx) {}
56 
57  static bool isInstr(IndexType X) { return X.Index >= First; }
58 
59  operator unsigned() const;
60  bool operator== (unsigned x) const;
61  bool operator== (IndexType Idx) const;
62  bool operator!= (unsigned x) const;
63  bool operator!= (IndexType Idx) const;
64  IndexType operator++ ();
65  bool operator< (unsigned Idx) const;
66  bool operator< (IndexType Idx) const;
67  bool operator<= (IndexType Idx) const;
68 
69  private:
70  bool operator> (IndexType Idx) const;
71  bool operator>= (IndexType Idx) const;
72 
73  unsigned Index = None;
74  };
75 
76  // A range of indices, essentially a representation of a live range.
77  // This is also used to represent "dead ranges", i.e. ranges where a
78  // register is dead.
79  class IndexRange : public std::pair<IndexType,IndexType> {
80  public:
81  IndexRange() = default;
82  IndexRange(IndexType Start, IndexType End, bool F = false, bool T = false)
83  : std::pair<IndexType,IndexType>(Start, End), Fixed(F), TiedEnd(T) {}
84 
85  IndexType start() const { return first; }
86  IndexType end() const { return second; }
87 
88  bool operator< (const IndexRange &A) const {
89  return start() < A.start();
90  }
91 
92  bool overlaps(const IndexRange &A) const;
93  bool contains(const IndexRange &A) const;
94  void merge(const IndexRange &A);
95 
96  bool Fixed = false; // Can be renamed? "Fixed" means "no".
97  bool TiedEnd = false; // The end is not a use, but a dead def tied to a use.
98 
99  private:
100  void setStart(const IndexType &S) { first = S; }
101  void setEnd(const IndexType &E) { second = E; }
102  };
103 
104  // A list of index ranges. This represents liveness of a register
105  // in a basic block.
106  class RangeList : public std::vector<IndexRange> {
107  public:
108  void add(IndexType Start, IndexType End, bool Fixed, bool TiedEnd) {
109  push_back(IndexRange(Start, End, Fixed, TiedEnd));
110  }
111  void add(const IndexRange &Range) {
112  push_back(Range);
113  }
114 
115  void include(const RangeList &RL);
116  void unionize(bool MergeAdjacent = false);
117  void subtract(const IndexRange &Range);
118 
119  private:
120  void addsub(const IndexRange &A, const IndexRange &B);
121  };
122 
124  public:
126 
127  MachineInstr *getInstr(IndexType Idx) const;
128  IndexType getIndex(MachineInstr *MI) const;
129  MachineBasicBlock &getBlock() const { return Block; }
130  IndexType getPrevIndex(IndexType Idx) const;
131  IndexType getNextIndex(IndexType Idx) const;
132  void replaceInstr(MachineInstr *OldMI, MachineInstr *NewMI);
133 
134  friend raw_ostream &operator<< (raw_ostream &OS, const InstrIndexMap &Map);
135 
136  IndexType First, Last;
137 
138  private:
139  MachineBasicBlock &Block;
140  std::map<IndexType,MachineInstr*> Map;
141  };
142 
143  using RegToRangeMap = std::map<RegisterRef, RangeList>;
144 
148  const MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI);
149 
150  struct PrintRangeMap {
152  : Map(M), TRI(I) {}
153 
154  friend raw_ostream &operator<< (raw_ostream &OS, const PrintRangeMap &P);
155 
156  private:
157  const RegToRangeMap &Map;
158  const TargetRegisterInfo &TRI;
159  };
160 
161 private:
162  RegisterSet getLiveIns(const MachineBasicBlock &B,
163  const MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI);
164 
165  void computeInitialLiveRanges(InstrIndexMap &IndexMap,
166  RegToRangeMap &LiveMap);
167 
168  MachineFunction &MF;
169  const HexagonSubtarget &HST;
170  const TargetInstrInfo &TII;
171  const TargetRegisterInfo &TRI;
172  BitVector Reserved;
173 };
174 
175 inline HexagonBlockRanges::IndexType::operator unsigned() const {
176  assert(Index >= First);
177  return Index;
178 }
179 
180 inline bool HexagonBlockRanges::IndexType::operator== (unsigned x) const {
181  return Index == x;
182 }
183 
185  return Index == Idx.Index;
186 }
187 
188 inline bool HexagonBlockRanges::IndexType::operator!= (unsigned x) const {
189  return Index != x;
190 }
191 
193  return Index != Idx.Index;
194 }
195 
196 inline
198  assert(Index != None);
199  assert(Index != Exit);
200  if (Index == Entry)
201  Index = First;
202  else
203  ++Index;
204  return *this;
205 }
206 
207 inline bool HexagonBlockRanges::IndexType::operator< (unsigned Idx) const {
208  return operator< (IndexType(Idx));
209 }
210 
212  // !(x < x).
213  if (Index == Idx.Index)
214  return false;
215  // !(None < x) for all x.
216  // !(x < None) for all x.
217  if (Index == None || Idx.Index == None)
218  return false;
219  // !(Exit < x) for all x.
220  // !(x < Entry) for all x.
221  if (Index == Exit || Idx.Index == Entry)
222  return false;
223  // Entry < x for all x != Entry.
224  // x < Exit for all x != Exit.
225  if (Index == Entry || Idx.Index == Exit)
226  return true;
227 
228  return Index < Idx.Index;
229 }
230 
232  return operator==(Idx) || operator<(Idx);
233 }
234 
244 
245 } // end namespace llvm
246 
247 #endif // LLVM_LIB_TARGET_HEXAGON_HEXAGONBLOCKRANGES_H
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
bool operator>(int64_t V1, const APSInt &V2)
Definition: APSInt.h:327
static RegisterSet expandToSubRegs(RegisterRef R, const MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI)
unsigned second
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:324
void add(IndexType Start, IndexType End, bool Fixed, bool TiedEnd)
Definition: BitVector.h:920
bool operator<=(IndexType Idx) const
bool operator>=(int64_t V1, const APSInt &V2)
Definition: APSInt.h:325
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")
static const unsigned End
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:1948
Representation of each machine instruction.
Definition: MachineInstr.h:59
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:2018
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:44
IRTranslator LLVM IR MI
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:1946
Statically lint checks LLVM IR
Definition: Lint.cpp:193