|
121
|
1 //===- HexagonBlockRanges.h -------------------------------------*- C++ -*-===//
|
|
120
|
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 //===----------------------------------------------------------------------===//
|
|
121
|
9
|
|
|
10 #ifndef LLVM_LIB_TARGET_HEXAGON_HEXAGONBLOCKRANGES_H
|
|
|
11 #define LLVM_LIB_TARGET_HEXAGON_HEXAGONBLOCKRANGES_H
|
|
120
|
12
|
|
|
13 #include "llvm/ADT/BitVector.h"
|
|
121
|
14 #include <cassert>
|
|
120
|
15 #include <map>
|
|
|
16 #include <set>
|
|
121
|
17 #include <utility>
|
|
120
|
18 #include <vector>
|
|
|
19
|
|
|
20 namespace llvm {
|
|
121
|
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;
|
|
120
|
30
|
|
|
31 struct HexagonBlockRanges {
|
|
|
32 HexagonBlockRanges(MachineFunction &MF);
|
|
|
33
|
|
|
34 struct RegisterRef {
|
|
|
35 unsigned Reg, Sub;
|
|
121
|
36
|
|
120
|
37 bool operator<(RegisterRef R) const {
|
|
|
38 return Reg < R.Reg || (Reg == R.Reg && Sub < R.Sub);
|
|
|
39 }
|
|
|
40 };
|
|
121
|
41 using RegisterSet = std::set<RegisterRef>;
|
|
120
|
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 };
|
|
121
|
53
|
|
|
54 IndexType() {}
|
|
|
55 IndexType(unsigned Idx) : Index(Idx) {}
|
|
|
56
|
|
120
|
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
|
|
121
|
73 unsigned Index = None;
|
|
120
|
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:
|
|
121
|
81 IndexRange() = default;
|
|
120
|
82 IndexRange(IndexType Start, IndexType End, bool F = false, bool T = false)
|
|
|
83 : std::pair<IndexType,IndexType>(Start, End), Fixed(F), TiedEnd(T) {}
|
|
121
|
84
|
|
120
|
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 }
|
|
121
|
91
|
|
120
|
92 bool overlaps(const IndexRange &A) const;
|
|
|
93 bool contains(const IndexRange &A) const;
|
|
|
94 void merge(const IndexRange &A);
|
|
|
95
|
|
121
|
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.
|
|
120
|
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 }
|
|
121
|
114
|
|
120
|
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
|
|
|
123 class InstrIndexMap {
|
|
|
124 public:
|
|
|
125 InstrIndexMap(MachineBasicBlock &B);
|
|
121
|
126
|
|
120
|
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);
|
|
121
|
135
|
|
120
|
136 IndexType First, Last;
|
|
|
137
|
|
|
138 private:
|
|
|
139 MachineBasicBlock &Block;
|
|
|
140 std::map<IndexType,MachineInstr*> Map;
|
|
|
141 };
|
|
|
142
|
|
121
|
143 using RegToRangeMap = std::map<RegisterRef, RangeList>;
|
|
|
144
|
|
120
|
145 RegToRangeMap computeLiveMap(InstrIndexMap &IndexMap);
|
|
|
146 RegToRangeMap computeDeadMap(InstrIndexMap &IndexMap, RegToRangeMap &LiveMap);
|
|
|
147 static RegisterSet expandToSubRegs(RegisterRef R,
|
|
|
148 const MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI);
|
|
|
149
|
|
|
150 struct PrintRangeMap {
|
|
|
151 PrintRangeMap(const RegToRangeMap &M, const TargetRegisterInfo &I)
|
|
|
152 : Map(M), TRI(I) {}
|
|
|
153
|
|
|
154 friend raw_ostream &operator<< (raw_ostream &OS, const PrintRangeMap &P);
|
|
121
|
155
|
|
120
|
156 private:
|
|
|
157 const RegToRangeMap ⤅
|
|
|
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
|
|
|
184 inline bool HexagonBlockRanges::IndexType::operator== (IndexType Idx) const {
|
|
|
185 return Index == Idx.Index;
|
|
|
186 }
|
|
|
187
|
|
|
188 inline bool HexagonBlockRanges::IndexType::operator!= (unsigned x) const {
|
|
|
189 return Index != x;
|
|
|
190 }
|
|
|
191
|
|
|
192 inline bool HexagonBlockRanges::IndexType::operator!= (IndexType Idx) const {
|
|
|
193 return Index != Idx.Index;
|
|
|
194 }
|
|
|
195
|
|
|
196 inline
|
|
|
197 HexagonBlockRanges::IndexType HexagonBlockRanges::IndexType::operator++ () {
|
|
|
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
|
|
|
211 inline bool HexagonBlockRanges::IndexType::operator< (IndexType Idx) const {
|
|
|
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
|
|
|
231 inline bool HexagonBlockRanges::IndexType::operator<= (IndexType Idx) const {
|
|
|
232 return operator==(Idx) || operator<(Idx);
|
|
|
233 }
|
|
|
234
|
|
|
235 raw_ostream &operator<< (raw_ostream &OS, HexagonBlockRanges::IndexType Idx);
|
|
|
236 raw_ostream &operator<< (raw_ostream &OS,
|
|
|
237 const HexagonBlockRanges::IndexRange &IR);
|
|
|
238 raw_ostream &operator<< (raw_ostream &OS,
|
|
|
239 const HexagonBlockRanges::RangeList &RL);
|
|
|
240 raw_ostream &operator<< (raw_ostream &OS,
|
|
|
241 const HexagonBlockRanges::InstrIndexMap &M);
|
|
|
242 raw_ostream &operator<< (raw_ostream &OS,
|
|
|
243 const HexagonBlockRanges::PrintRangeMap &P);
|
|
|
244
|
|
121
|
245 } // end namespace llvm
|
|
120
|
246
|
|
121
|
247 #endif // LLVM_LIB_TARGET_HEXAGON_HEXAGONBLOCKRANGES_H
|
