Coverage Report

Created: 2018-09-17 19:50

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/CodeGen/LiveIntervalUnion.h
Line
Count
Source (jump to first uncovered line)
1
//===- LiveIntervalUnion.h - Live interval union data struct ---*- C++ -*--===//
2
//
3
//                     The LLVM Compiler Infrastructure
4
//
5
// This file is distributed under the University of Illinois Open Source
6
// License. See LICENSE.TXT for details.
7
//
8
//===----------------------------------------------------------------------===//
9
//
10
// LiveIntervalUnion is a union of live segments across multiple live virtual
11
// registers. This may be used during coalescing to represent a congruence
12
// class, or during register allocation to model liveness of a physical
13
// register.
14
//
15
//===----------------------------------------------------------------------===//
16
17
#ifndef LLVM_CODEGEN_LIVEINTERVALUNION_H
18
#define LLVM_CODEGEN_LIVEINTERVALUNION_H
19
20
#include "llvm/ADT/IntervalMap.h"
21
#include "llvm/ADT/SmallVector.h"
22
#include "llvm/CodeGen/LiveInterval.h"
23
#include "llvm/CodeGen/SlotIndexes.h"
24
#include <cassert>
25
#include <limits>
26
27
namespace llvm {
28
29
class raw_ostream;
30
class TargetRegisterInfo;
31
32
#ifndef NDEBUG
33
// forward declaration
34
template <unsigned Element> class SparseBitVector;
35
36
using LiveVirtRegBitSet = SparseBitVector<128>;
37
#endif
38
39
/// Union of live intervals that are strong candidates for coalescing into a
40
/// single register (either physical or virtual depending on the context).  We
41
/// expect the constituent live intervals to be disjoint, although we may
42
/// eventually make exceptions to handle value-based interference.
43
class LiveIntervalUnion {
44
  // A set of live virtual register segments that supports fast insertion,
45
  // intersection, and removal.
46
  // Mapping SlotIndex intervals to virtual register numbers.
47
  using LiveSegments = IntervalMap<SlotIndex, LiveInterval*>;
48
49
public:
50
  // SegmentIter can advance to the next segment ordered by starting position
51
  // which may belong to a different live virtual register. We also must be able
52
  // to reach the current segment's containing virtual register.
53
  using SegmentIter = LiveSegments::iterator;
54
55
  /// Const version of SegmentIter.
56
  using ConstSegmentIter = LiveSegments::const_iterator;
57
58
  // LiveIntervalUnions share an external allocator.
59
  using Allocator = LiveSegments::Allocator;
60
61
private:
62
  unsigned Tag = 0;       // unique tag for current contents.
63
  LiveSegments Segments;  // union of virtual reg segments
64
65
public:
66
4.95M
  explicit LiveIntervalUnion(Allocator &a) : Segments(a) {}
67
68
  // Iterate over all segments in the union of live virtual registers ordered
69
  // by their starting position.
70
  SegmentIter begin() { return Segments.begin(); }
71
  SegmentIter end() { return Segments.end(); }
72
611k
  SegmentIter find(SlotIndex x) { return Segments.find(x); }
73
  ConstSegmentIter begin() const { return Segments.begin(); }
74
  ConstSegmentIter end() const { return Segments.end(); }
75
0
  ConstSegmentIter find(SlotIndex x) const { return Segments.find(x); }
76
77
131M
  bool empty() const { return Segments.empty(); }
78
  SlotIndex startIndex() const { return Segments.start(); }
79
80
  // Provide public access to the underlying map to allow overlap iteration.
81
  using Map = LiveSegments;
82
129M
  const Map &getMap() const { return Segments; }
83
84
  /// getTag - Return an opaque tag representing the current state of the union.
85
43.7M
  unsigned getTag() const { return Tag; }
86
87
  /// changedSince - Return true if the union change since getTag returned tag.
88
32.7M
  bool changedSince(unsigned tag) const { return tag != Tag; }
89
90
  // Add a live virtual register to this union and merge its segments.
91
  void unify(LiveInterval &VirtReg, const LiveRange &Range);
92
93
  // Remove a live virtual register's segments from this union.
94
  void extract(LiveInterval &VirtReg, const LiveRange &Range);
95
96
  // Remove all inserted virtual registers.
97
68.9M
  void clear() { Segments.clear(); ++Tag; }
98
99
  // Print union, using TRI to translate register names
100
  void print(raw_ostream &OS, const TargetRegisterInfo *TRI) const;
101
102
#ifndef NDEBUG
103
  // Verify the live intervals in this union and add them to the visited set.
104
  void verify(LiveVirtRegBitSet& VisitedVRegs);
105
#endif
106
107
  /// Query interferences between a single live virtual register and a live
108
  /// interval union.
109
  class Query {
110
    const LiveIntervalUnion *LiveUnion = nullptr;
111
    const LiveRange *LR = nullptr;
112
    LiveRange::const_iterator LRI;  ///< current position in LR
113
    ConstSegmentIter LiveUnionI;    ///< current position in LiveUnion
114
    SmallVector<LiveInterval*,4> InterferingVRegs;
115
    bool CheckedFirstInterference = false;
116
    bool SeenAllInterferences = false;
117
    unsigned Tag = 0;
118
    unsigned UserTag = 0;
119
120
    void reset(unsigned NewUserTag, const LiveRange &NewLR,
121
40.8M
               const LiveIntervalUnion &NewLiveUnion) {
122
40.8M
      LiveUnion = &NewLiveUnion;
123
40.8M
      LR = &NewLR;
124
40.8M
      InterferingVRegs.clear();
125
40.8M
      CheckedFirstInterference = false;
126
40.8M
      SeenAllInterferences = false;
127
40.8M
      Tag = NewLiveUnion.getTag();
128
40.8M
      UserTag = NewUserTag;
129
40.8M
    }
130
131
  public:
132
4.94M
    Query() = default;
133
    Query(const LiveRange &LR, const LiveIntervalUnion &LIU):
134
89.8M
      LiveUnion(&LIU), LR(&LR) {}
135
    Query(const Query &) = delete;
136
    Query &operator=(const Query &) = delete;
137
138
    void init(unsigned NewUserTag, const LiveRange &NewLR,
139
68.2M
              const LiveIntervalUnion &NewLiveUnion) {
140
68.2M
      if (UserTag == NewUserTag && 
LR == &NewLR27.8M
&&
LiveUnion == &NewLiveUnion27.4M
&&
141
68.2M
          
!NewLiveUnion.changedSince(Tag)27.4M
) {
142
27.4M
        // Retain cached results, e.g. firstInterference.
143
27.4M
        return;
144
27.4M
      }
145
40.8M
      reset(NewUserTag, NewLR, NewLiveUnion);
146
40.8M
    }
147
148
    // Does this live virtual register interfere with the union?
149
142M
    bool checkInterference() { return collectInterferingVRegs(1); }
150
151
    // Count the virtual registers in this union that interfere with this
152
    // query's live virtual register, up to maxInterferingRegs.
153
    unsigned collectInterferingVRegs(
154
        unsigned MaxInterferingRegs = std::numeric_limits<unsigned>::max());
155
156
    // Was this virtual register visited during collectInterferingVRegs?
157
    bool isSeenInterference(LiveInterval *VirtReg) const;
158
159
    // Did collectInterferingVRegs collect all interferences?
160
0
    bool seenAllInterferences() const { return SeenAllInterferences; }
161
162
    // Vector generated by collectInterferingVRegs.
163
28.2M
    const SmallVectorImpl<LiveInterval*> &interferingVRegs() const {
164
28.2M
      return InterferingVRegs;
165
28.2M
    }
166
  };
167
168
  // Array of LiveIntervalUnions.
169
  class Array {
170
    unsigned Size = 0;
171
    LiveIntervalUnion *LIUs = nullptr;
172
173
  public:
174
30.9k
    Array() = default;
175
30.8k
    ~Array() { clear(); }
176
177
    // Initialize the array to have Size entries.
178
    // Reuse an existing allocation if the size matches.
179
    void init(LiveIntervalUnion::Allocator&, unsigned Size);
180
181
911k
    unsigned size() const { return Size; }
182
183
    void clear();
184
185
238M
    LiveIntervalUnion& operator[](unsigned idx) {
186
238M
      assert(idx <  Size && "idx out of bounds");
187
238M
      return LIUs[idx];
188
238M
    }
189
190
1.31M
    const LiveIntervalUnion& operator[](unsigned Idx) const {
191
1.31M
      assert(Idx < Size && "Idx out of bounds");
192
1.31M
      return LIUs[Idx];
193
1.31M
    }
194
  };
195
};
196
197
} // end namespace llvm
198
199
#endif // LLVM_CODEGEN_LIVEINTERVALUNION_H