|
120
|
1 //===--- HexagonBlockRanges.h ---------------------------------------------===//
|
|
|
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 #ifndef HEXAGON_BLOCK_RANGES_H
|
|
|
10 #define HEXAGON_BLOCK_RANGES_H
|
|
|
11
|
|
|
12 #include "llvm/ADT/BitVector.h"
|
|
|
13 #include "llvm/CodeGen/MachineBasicBlock.h"
|
|
|
14 #include "llvm/MC/MCRegisterInfo.h" // For MCPhysReg.
|
|
|
15 #include <map>
|
|
|
16 #include <set>
|
|
|
17 #include <vector>
|
|
|
18
|
|
|
19 namespace llvm {
|
|
|
20 class Function;
|
|
|
21 class HexagonSubtarget;
|
|
|
22 class MachineBasicBlock;
|
|
|
23 class MachineFunction;
|
|
|
24 class MachineInstr;
|
|
|
25 class MCInstrDesc;
|
|
|
26 class raw_ostream;
|
|
|
27 class TargetInstrInfo;
|
|
|
28 class TargetRegisterClass;
|
|
|
29 class TargetRegisterInfo;
|
|
|
30 class Type;
|
|
|
31
|
|
|
32 struct HexagonBlockRanges {
|
|
|
33 HexagonBlockRanges(MachineFunction &MF);
|
|
|
34
|
|
|
35 struct RegisterRef {
|
|
|
36 unsigned Reg, Sub;
|
|
|
37 bool operator<(RegisterRef R) const {
|
|
|
38 return Reg < R.Reg || (Reg == R.Reg && Sub < R.Sub);
|
|
|
39 }
|
|
|
40 };
|
|
|
41 typedef std::set<RegisterRef> RegisterSet;
|
|
|
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 static bool isInstr(IndexType X) { return X.Index >= First; }
|
|
|
54
|
|
|
55 IndexType() : Index(None) {}
|
|
|
56 IndexType(unsigned Idx) : Index(Idx) {}
|
|
|
57 operator unsigned() const;
|
|
|
58 bool operator== (unsigned x) const;
|
|
|
59 bool operator== (IndexType Idx) const;
|
|
|
60 bool operator!= (unsigned x) const;
|
|
|
61 bool operator!= (IndexType Idx) const;
|
|
|
62 IndexType operator++ ();
|
|
|
63 bool operator< (unsigned Idx) const;
|
|
|
64 bool operator< (IndexType Idx) const;
|
|
|
65 bool operator<= (IndexType Idx) const;
|
|
|
66
|
|
|
67 private:
|
|
|
68 bool operator> (IndexType Idx) const;
|
|
|
69 bool operator>= (IndexType Idx) const;
|
|
|
70
|
|
|
71 unsigned Index;
|
|
|
72 };
|
|
|
73
|
|
|
74 // A range of indices, essentially a representation of a live range.
|
|
|
75 // This is also used to represent "dead ranges", i.e. ranges where a
|
|
|
76 // register is dead.
|
|
|
77 class IndexRange : public std::pair<IndexType,IndexType> {
|
|
|
78 public:
|
|
|
79 IndexRange() : Fixed(false), TiedEnd(false) {}
|
|
|
80 IndexRange(IndexType Start, IndexType End, bool F = false, bool T = false)
|
|
|
81 : std::pair<IndexType,IndexType>(Start, End), Fixed(F), TiedEnd(T) {}
|
|
|
82 IndexType start() const { return first; }
|
|
|
83 IndexType end() const { return second; }
|
|
|
84
|
|
|
85 bool operator< (const IndexRange &A) const {
|
|
|
86 return start() < A.start();
|
|
|
87 }
|
|
|
88 bool overlaps(const IndexRange &A) const;
|
|
|
89 bool contains(const IndexRange &A) const;
|
|
|
90 void merge(const IndexRange &A);
|
|
|
91
|
|
|
92 bool Fixed; // Can be renamed? "Fixed" means "no".
|
|
|
93 bool TiedEnd; // The end is not a use, but a dead def tied to a use.
|
|
|
94
|
|
|
95 private:
|
|
|
96 void setStart(const IndexType &S) { first = S; }
|
|
|
97 void setEnd(const IndexType &E) { second = E; }
|
|
|
98 };
|
|
|
99
|
|
|
100 // A list of index ranges. This represents liveness of a register
|
|
|
101 // in a basic block.
|
|
|
102 class RangeList : public std::vector<IndexRange> {
|
|
|
103 public:
|
|
|
104 void add(IndexType Start, IndexType End, bool Fixed, bool TiedEnd) {
|
|
|
105 push_back(IndexRange(Start, End, Fixed, TiedEnd));
|
|
|
106 }
|
|
|
107 void add(const IndexRange &Range) {
|
|
|
108 push_back(Range);
|
|
|
109 }
|
|
|
110 void include(const RangeList &RL);
|
|
|
111 void unionize(bool MergeAdjacent = false);
|
|
|
112 void subtract(const IndexRange &Range);
|
|
|
113
|
|
|
114 private:
|
|
|
115 void addsub(const IndexRange &A, const IndexRange &B);
|
|
|
116 };
|
|
|
117
|
|
|
118 class InstrIndexMap {
|
|
|
119 public:
|
|
|
120 InstrIndexMap(MachineBasicBlock &B);
|
|
|
121 MachineInstr *getInstr(IndexType Idx) const;
|
|
|
122 IndexType getIndex(MachineInstr *MI) const;
|
|
|
123 MachineBasicBlock &getBlock() const { return Block; }
|
|
|
124 IndexType getPrevIndex(IndexType Idx) const;
|
|
|
125 IndexType getNextIndex(IndexType Idx) const;
|
|
|
126 void replaceInstr(MachineInstr *OldMI, MachineInstr *NewMI);
|
|
|
127
|
|
|
128 friend raw_ostream &operator<< (raw_ostream &OS, const InstrIndexMap &Map);
|
|
|
129 IndexType First, Last;
|
|
|
130
|
|
|
131 private:
|
|
|
132 MachineBasicBlock &Block;
|
|
|
133 std::map<IndexType,MachineInstr*> Map;
|
|
|
134 };
|
|
|
135
|
|
|
136 typedef std::map<RegisterRef,RangeList> RegToRangeMap;
|
|
|
137 RegToRangeMap computeLiveMap(InstrIndexMap &IndexMap);
|
|
|
138 RegToRangeMap computeDeadMap(InstrIndexMap &IndexMap, RegToRangeMap &LiveMap);
|
|
|
139 static RegisterSet expandToSubRegs(RegisterRef R,
|
|
|
140 const MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI);
|
|
|
141
|
|
|
142 struct PrintRangeMap {
|
|
|
143 PrintRangeMap(const RegToRangeMap &M, const TargetRegisterInfo &I)
|
|
|
144 : Map(M), TRI(I) {}
|
|
|
145
|
|
|
146 friend raw_ostream &operator<< (raw_ostream &OS, const PrintRangeMap &P);
|
|
|
147 private:
|
|
|
148 const RegToRangeMap ⤅
|
|
|
149 const TargetRegisterInfo &TRI;
|
|
|
150 };
|
|
|
151
|
|
|
152 private:
|
|
|
153 RegisterSet getLiveIns(const MachineBasicBlock &B,
|
|
|
154 const MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI);
|
|
|
155
|
|
|
156 void computeInitialLiveRanges(InstrIndexMap &IndexMap,
|
|
|
157 RegToRangeMap &LiveMap);
|
|
|
158
|
|
|
159 MachineFunction &MF;
|
|
|
160 const HexagonSubtarget &HST;
|
|
|
161 const TargetInstrInfo &TII;
|
|
|
162 const TargetRegisterInfo &TRI;
|
|
|
163 BitVector Reserved;
|
|
|
164 };
|
|
|
165
|
|
|
166
|
|
|
167 inline HexagonBlockRanges::IndexType::operator unsigned() const {
|
|
|
168 assert(Index >= First);
|
|
|
169 return Index;
|
|
|
170 }
|
|
|
171
|
|
|
172 inline bool HexagonBlockRanges::IndexType::operator== (unsigned x) const {
|
|
|
173 return Index == x;
|
|
|
174 }
|
|
|
175
|
|
|
176 inline bool HexagonBlockRanges::IndexType::operator== (IndexType Idx) const {
|
|
|
177 return Index == Idx.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
|
|
|
189 HexagonBlockRanges::IndexType HexagonBlockRanges::IndexType::operator++ () {
|
|
|
190 assert(Index != None);
|
|
|
191 assert(Index != Exit);
|
|
|
192 if (Index == Entry)
|
|
|
193 Index = First;
|
|
|
194 else
|
|
|
195 ++Index;
|
|
|
196 return *this;
|
|
|
197 }
|
|
|
198
|
|
|
199 inline bool HexagonBlockRanges::IndexType::operator< (unsigned Idx) const {
|
|
|
200 return operator< (IndexType(Idx));
|
|
|
201 }
|
|
|
202
|
|
|
203 inline bool HexagonBlockRanges::IndexType::operator< (IndexType Idx) const {
|
|
|
204 // !(x < x).
|
|
|
205 if (Index == Idx.Index)
|
|
|
206 return false;
|
|
|
207 // !(None < x) for all x.
|
|
|
208 // !(x < None) for all x.
|
|
|
209 if (Index == None || Idx.Index == None)
|
|
|
210 return false;
|
|
|
211 // !(Exit < x) for all x.
|
|
|
212 // !(x < Entry) for all x.
|
|
|
213 if (Index == Exit || Idx.Index == Entry)
|
|
|
214 return false;
|
|
|
215 // Entry < x for all x != Entry.
|
|
|
216 // x < Exit for all x != Exit.
|
|
|
217 if (Index == Entry || Idx.Index == Exit)
|
|
|
218 return true;
|
|
|
219
|
|
|
220 return Index < Idx.Index;
|
|
|
221 }
|
|
|
222
|
|
|
223 inline bool HexagonBlockRanges::IndexType::operator<= (IndexType Idx) const {
|
|
|
224 return operator==(Idx) || operator<(Idx);
|
|
|
225 }
|
|
|
226
|
|
|
227
|
|
|
228 raw_ostream &operator<< (raw_ostream &OS, HexagonBlockRanges::IndexType Idx);
|
|
|
229 raw_ostream &operator<< (raw_ostream &OS,
|
|
|
230 const HexagonBlockRanges::IndexRange &IR);
|
|
|
231 raw_ostream &operator<< (raw_ostream &OS,
|
|
|
232 const HexagonBlockRanges::RangeList &RL);
|
|
|
233 raw_ostream &operator<< (raw_ostream &OS,
|
|
|
234 const HexagonBlockRanges::InstrIndexMap &M);
|
|
|
235 raw_ostream &operator<< (raw_ostream &OS,
|
|
|
236 const HexagonBlockRanges::PrintRangeMap &P);
|
|
|
237
|
|
|
238 } // namespace llvm
|
|
|
239
|
|
|
240 #endif
|
