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
19namespace llvm {
20
21class HexagonSubtarget;
22class MachineBasicBlock;
23class MachineFunction;
24class MachineInstr;
25class MachineRegisterInfo;
26class raw_ostream;
27class TargetInstrInfo;
28class TargetRegisterInfo;
29
30struct 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
53    IndexType() {}
54    IndexType(unsigned Idx) : Index(Idx) {}
55
56    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
84    IndexType start() const { return first; }
85    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:
99    void setStart(const IndexType &S) { first = S; }
100    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:
107    void add(IndexType Start, IndexType End, bool Fixed, bool TiedEnd) {
108      push_back(IndexRange(Start, End, Fixed, TiedEnd));
109    }
110    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;
128    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 {
150    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
160private:
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
174inline HexagonBlockRanges::IndexType::operator unsigned() const {
175  assert(Index >= First);
176  return Index;
177}
178
179inline bool HexagonBlockRanges::IndexType::operator== (unsigned x) const {
180  return Index == x;
181}
182
183inline bool HexagonBlockRanges::IndexType::operator== (IndexType Idx) const {
184  return Index == Idx.Index;
185}
186
187inline bool HexagonBlockRanges::IndexType::operator!= (unsigned x) const {
188  return Index != x;
189}
190
191inline bool HexagonBlockRanges::IndexType::operator!= (IndexType Idx) const {
192  return Index != Idx.Index;
193}
194
195inline
196HexagonBlockRanges::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
206inline bool HexagonBlockRanges::IndexType::operator< (unsigned Idx) const {
207  return operator< (IndexType(Idx));
208}
209
210inline 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
230inline bool HexagonBlockRanges::IndexType::operator<= (IndexType Idx) const {
231  return operator==(Idx) || operator<(Idx);
232}
233
234raw_ostream &operator<< (raw_ostream &OS, HexagonBlockRanges::IndexType Idx);
235raw_ostream &operator<< (raw_ostream &OS,
236      const HexagonBlockRanges::IndexRange &IR);
237raw_ostream &operator<< (raw_ostream &OS,
238      const HexagonBlockRanges::RangeList &RL);
239raw_ostream &operator<< (raw_ostream &OS,
240      const HexagonBlockRanges::InstrIndexMap &M);
241raw_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