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 
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 
31 struct 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 Reg < R.Reg || (Reg == R.Reg && Sub < 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 
IndexTypeHexagonBlockRanges56     IndexType() {}
IndexTypeHexagonBlockRanges57     IndexType(unsigned Idx) : Index(Idx) {}
58 
isInstrHexagonBlockRanges59     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 
startHexagonBlockRanges87     IndexType start() const { return first; }
endHexagonBlockRanges88     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:
setStartHexagonBlockRanges102     void setStart(const IndexType &S) { first = S; }
setEndHexagonBlockRanges103     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:
addHexagonBlockRanges110     void add(IndexType Start, IndexType End, bool Fixed, bool TiedEnd) {
111       push_back(IndexRange(Start, End, Fixed, TiedEnd));
112     }
addHexagonBlockRanges113     void add(const IndexRange &Range) {
114       push_back(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;
getBlockHexagonBlockRanges131     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 {
PrintRangeMapHexagonBlockRanges::PrintRangeMap153     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 
163 private:
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 
177 inline HexagonBlockRanges::IndexType::operator unsigned() const {
178   assert(Index >= First);
179   return Index;
180 }
181 
182 inline bool HexagonBlockRanges::IndexType::operator== (unsigned x) const {
183   return Index == x;
184 }
185 
186 inline bool HexagonBlockRanges::IndexType::operator== (IndexType Idx) const {
187   return Index == Idx.Index;
188 }
189 
190 inline bool HexagonBlockRanges::IndexType::operator!= (unsigned x) const {
191   return Index != x;
192 }
193 
194 inline bool HexagonBlockRanges::IndexType::operator!= (IndexType Idx) const {
195   return Index != Idx.Index;
196 }
197 
198 inline
199 HexagonBlockRanges::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 
209 inline bool HexagonBlockRanges::IndexType::operator< (unsigned Idx) const {
210   return operator< (IndexType(Idx));
211 }
212 
213 inline 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 
233 inline bool HexagonBlockRanges::IndexType::operator<= (IndexType Idx) const {
234   return operator==(Idx) || operator<(Idx);
235 }
236 
237 raw_ostream &operator<< (raw_ostream &OS, HexagonBlockRanges::IndexType Idx);
238 raw_ostream &operator<< (raw_ostream &OS,
239       const HexagonBlockRanges::IndexRange &IR);
240 raw_ostream &operator<< (raw_ostream &OS,
241       const HexagonBlockRanges::RangeList &RL);
242 raw_ostream &operator<< (raw_ostream &OS,
243       const HexagonBlockRanges::InstrIndexMap &M);
244 raw_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