Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Target/Hexagon/HexagonBlockRanges.h
Line
Count
Source (jump to first uncovered line)
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
16.7M
    bool operator<(RegisterRef R) const {
37
16.7M
      return Reg < R.Reg || 
(8.14M
Reg == R.Reg8.14M
&&
Sub < R.Sub1.37M
);
38
16.7M
    }
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
108k
    IndexType() {}
54
1.18M
    IndexType(unsigned Idx) : Index(Idx) {}
55
56
869
    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
570k
      : std::pair<IndexType,IndexType>(Start, End), Fixed(F), TiedEnd(T) {}
83
84
331k
    IndexType start() const { return first; }
85
282k
    IndexType end() const   { return second; }
86
87
51.3k
    bool operator< (const IndexRange &A) const {
88
51.3k
      return start() < A.start();
89
51.3k
    }
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
0
    void setStart(const IndexType &S) { first = S; }
100
39
    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
570k
    void add(IndexType Start, IndexType End, bool Fixed, bool TiedEnd) {
108
570k
      push_back(IndexRange(Start, End, Fixed, TiedEnd));
109
570k
    }
110
0
    void add(const IndexRange &Range) {
111
0
      push_back(Range);
112
0
    }
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
11.1k
    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
0
        : 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
113k
inline HexagonBlockRanges::IndexType::operator unsigned() const {
175
113k
  assert(Index >= First);
176
113k
  return Index;
177
113k
}
178
179
490k
inline bool HexagonBlockRanges::IndexType::operator== (unsigned x) const {
180
490k
  return Index == x;
181
490k
}
182
183
225k
inline bool HexagonBlockRanges::IndexType::operator== (IndexType Idx) const {
184
225k
  return Index == Idx.Index;
185
225k
}
186
187
359k
inline bool HexagonBlockRanges::IndexType::operator!= (unsigned x) const {
188
359k
  return Index != x;
189
359k
}
190
191
0
inline bool HexagonBlockRanges::IndexType::operator!= (IndexType Idx) const {
192
0
  return Index != Idx.Index;
193
0
}
194
195
inline
196
28.3k
HexagonBlockRanges::IndexType HexagonBlockRanges::IndexType::operator++ () {
197
28.3k
  assert(Index != None);
198
28.3k
  assert(Index != Exit);
199
28.3k
  if (Index == Entry)
200
0
    Index = First;
201
28.3k
  else
202
28.3k
    ++Index;
203
28.3k
  return *this;
204
28.3k
}
205
206
34.5k
inline bool HexagonBlockRanges::IndexType::operator< (unsigned Idx) const {
207
34.5k
  return operator< (IndexType(Idx));
208
34.5k
}
209
210
487k
inline bool HexagonBlockRanges::IndexType::operator< (IndexType Idx) const {
211
487k
  // !(x < x).
212
487k
  if (Index == Idx.Index)
213
14.9k
    return false;
214
472k
  // !(None < x) for all x.
215
472k
  // !(x < None) for all x.
216
472k
  if (Index == None || 
Idx.Index == None460k
)
217
11.4k
    return false;
218
460k
  // !(Exit < x) for all x.
219
460k
  // !(x < Entry) for all x.
220
460k
  if (Index == Exit || 
Idx.Index == Entry460k
)
221
14.9k
    return false;
222
445k
  // Entry < x for all x != Entry.
223
445k
  // x < Exit for all x != Exit.
224
445k
  if (Index == Entry || 
Idx.Index == Exit431k
)
225
39.5k
    return true;
226
406k
227
406k
  return Index < Idx.Index;
228
406k
}
229
230
30.6k
inline bool HexagonBlockRanges::IndexType::operator<= (IndexType Idx) const {
231
30.6k
  return operator==(Idx) || 
operator<(Idx)30.5k
;
232
30.6k
}
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