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
20namespace llvm {
21
22class HexagonSubtarget;
23class MachineBasicBlock;
24class MachineFunction;
25class MachineInstr;
26class MachineRegisterInfo;
27class raw_ostream;
28class TargetInstrInfo;
29class TargetRegisterInfo;
30
31struct HexagonBlockRanges {
32 HexagonBlockRanges(MachineFunction &MF);
33
34 // FIXME: Consolidate duplicate definitions of RegisterRef
35 struct RegisterRef {
36 llvm::Register Reg;
37 unsigned Sub;
38
39 bool operator<(RegisterRef R) const {
40 return std::tie(args: Reg, args: Sub) < std::tie(args&: R.Reg, args&: 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;
66 IndexType operator++ ();
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(x: IndexRange(Start, End, Fixed, TiedEnd));
112 }
113 void add(const IndexRange &Range) {
114 push_back(x: 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
125 class InstrIndexMap {
126 public:
127 InstrIndexMap(MachineBasicBlock &B);
128
129 MachineInstr *getInstr(IndexType Idx) const;
130 IndexType getIndex(MachineInstr *MI) 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
138 IndexType First, Last;
139
140 private:
141 MachineBasicBlock &Block;
142 std::map<IndexType,MachineInstr*> Map;
143 };
144
145 using RegToRangeMap = std::map<RegisterRef, RangeList>;
146
147 RegToRangeMap computeLiveMap(InstrIndexMap &IndexMap);
148 RegToRangeMap computeDeadMap(InstrIndexMap &IndexMap, RegToRangeMap &LiveMap);
149 static RegisterSet expandToSubRegs(RegisterRef R,
150 const MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI);
151
152 struct PrintRangeMap {
153 PrintRangeMap(const RegToRangeMap &M, const TargetRegisterInfo &I)
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
163private:
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
177inline HexagonBlockRanges::IndexType::operator unsigned() const {
178 assert(Index >= First);
179 return Index;
180}
181
182inline bool HexagonBlockRanges::IndexType::operator== (unsigned x) const {
183 return Index == x;
184}
185
186inline bool HexagonBlockRanges::IndexType::operator== (IndexType Idx) const {
187 return Index == Idx.Index;
188}
189
190inline bool HexagonBlockRanges::IndexType::operator!= (unsigned x) const {
191 return Index != x;
192}
193
194inline bool HexagonBlockRanges::IndexType::operator!= (IndexType Idx) const {
195 return Index != Idx.Index;
196}
197
198inline
199HexagonBlockRanges::IndexType HexagonBlockRanges::IndexType::operator++ () {
200 assert(Index != None);
201 assert(Index != Exit);
202 if (Index == Entry)
203 Index = First;
204 else
205 ++Index;
206 return *this;
207}
208
209inline bool HexagonBlockRanges::IndexType::operator< (unsigned Idx) const {
210 return operator< (Idx: IndexType(Idx));
211}
212
213inline bool HexagonBlockRanges::IndexType::operator< (IndexType Idx) const {
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
233inline bool HexagonBlockRanges::IndexType::operator<= (IndexType Idx) const {
234 return operator==(Idx) || operator<(Idx);
235}
236
237raw_ostream &operator<< (raw_ostream &OS, HexagonBlockRanges::IndexType Idx);
238raw_ostream &operator<< (raw_ostream &OS,
239 const HexagonBlockRanges::IndexRange &IR);
240raw_ostream &operator<< (raw_ostream &OS,
241 const HexagonBlockRanges::RangeList &RL);
242raw_ostream &operator<< (raw_ostream &OS,
243 const HexagonBlockRanges::InstrIndexMap &M);
244raw_ostream &operator<< (raw_ostream &OS,
245 const HexagonBlockRanges::PrintRangeMap &P);
246
247} // end namespace llvm
248
249#endif // LLVM_LIB_TARGET_HEXAGON_HEXAGONBLOCKRANGES_H
250