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 
30 struct HexagonBlockRanges {
31   HexagonBlockRanges(MachineFunction &MF);
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 
IndexTypeHexagonBlockRanges53     IndexType() {}
IndexTypeHexagonBlockRanges54     IndexType(unsigned Idx) : Index(Idx) {}
55 
isInstrHexagonBlockRanges56     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 
startHexagonBlockRanges84     IndexType start() const { return first; }
endHexagonBlockRanges85     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:
setStartHexagonBlockRanges99     void setStart(const IndexType &S) { first = S; }
setEndHexagonBlockRanges100     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:
addHexagonBlockRanges107     void add(IndexType Start, IndexType End, bool Fixed, bool TiedEnd) {
108       push_back(IndexRange(Start, End, Fixed, TiedEnd));
109     }
addHexagonBlockRanges110     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 
122   class InstrIndexMap {
123   public:
124     InstrIndexMap(MachineBasicBlock &B);
125 
126     MachineInstr *getInstr(IndexType Idx) const;
127     IndexType getIndex(MachineInstr *MI) const;
getBlockHexagonBlockRanges128     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 
144   RegToRangeMap computeLiveMap(InstrIndexMap &IndexMap);
145   RegToRangeMap computeDeadMap(InstrIndexMap &IndexMap, RegToRangeMap &LiveMap);
146   static RegisterSet expandToSubRegs(RegisterRef R,
147       const MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI);
148 
149   struct PrintRangeMap {
PrintRangeMapHexagonBlockRanges::PrintRangeMap150     PrintRangeMap(const RegToRangeMap &M, const TargetRegisterInfo &I)
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,
162       const MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI);
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 
183 inline bool HexagonBlockRanges::IndexType::operator== (IndexType Idx) const {
184   return Index == Idx.Index;
185 }
186 
187 inline bool HexagonBlockRanges::IndexType::operator!= (unsigned x) const {
188   return Index != x;
189 }
190 
191 inline bool HexagonBlockRanges::IndexType::operator!= (IndexType Idx) const {
192   return Index != Idx.Index;
193 }
194 
195 inline
196 HexagonBlockRanges::IndexType HexagonBlockRanges::IndexType::operator++ () {
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 
210 inline bool HexagonBlockRanges::IndexType::operator< (IndexType Idx) const {
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 
230 inline bool HexagonBlockRanges::IndexType::operator<= (IndexType Idx) const {
231   return operator==(Idx) || operator<(Idx);
232 }
233 
234 raw_ostream &operator<< (raw_ostream &OS, HexagonBlockRanges::IndexType Idx);
235 raw_ostream &operator<< (raw_ostream &OS,
236       const HexagonBlockRanges::IndexRange &IR);
237 raw_ostream &operator<< (raw_ostream &OS,
238       const HexagonBlockRanges::RangeList &RL);
239 raw_ostream &operator<< (raw_ostream &OS,
240       const HexagonBlockRanges::InstrIndexMap &M);
241 raw_ostream &operator<< (raw_ostream &OS,
242       const HexagonBlockRanges::PrintRangeMap &P);
243 
244 } // end namespace llvm
245 
246 #endif // LLVM_LIB_TARGET_HEXAGON_HEXAGONBLOCKRANGES_H
247