Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/CodeGen/InterferenceCache.h
Line
Count
Source
1
//===- InterferenceCache.h - Caching per-block interference ----*- 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
// InterferenceCache remembers per-block interference from LiveIntervalUnions,
11
// fixed RegUnit interference, and register masks.
12
//
13
//===----------------------------------------------------------------------===//
14
15
#ifndef LLVM_LIB_CODEGEN_INTERFERENCECACHE_H
16
#define LLVM_LIB_CODEGEN_INTERFERENCECACHE_H
17
18
#include "llvm/ADT/SmallVector.h"
19
#include "llvm/CodeGen/LiveInterval.h"
20
#include "llvm/CodeGen/LiveIntervalUnion.h"
21
#include "llvm/CodeGen/SlotIndexes.h"
22
#include "llvm/Support/Compiler.h"
23
#include <cassert>
24
#include <cstddef>
25
#include <cstdlib>
26
27
namespace llvm {
28
29
class LiveIntervals;
30
class MachineFunction;
31
class TargetRegisterInfo;
32
33
class LLVM_LIBRARY_VISIBILITY InterferenceCache {
34
  /// BlockInterference - information about the interference in a single basic
35
  /// block.
36
  struct BlockInterference {
37
    unsigned Tag = 0;
38
    SlotIndex First;
39
    SlotIndex Last;
40
41
31.7M
    BlockInterference() {}
42
  };
43
44
  /// Entry - A cache entry containing interference information for all aliases
45
  /// of PhysReg in all basic blocks.
46
  class Entry {
47
    /// PhysReg - The register currently represented.
48
    unsigned PhysReg = 0;
49
50
    /// Tag - Cache tag is changed when any of the underlying LiveIntervalUnions
51
    /// change.
52
    unsigned Tag = 0;
53
54
    /// RefCount - The total number of Cursor instances referring to this Entry.
55
    unsigned RefCount = 0;
56
57
    /// MF - The current function.
58
    MachineFunction *MF;
59
60
    /// Indexes - Mapping block numbers to SlotIndex ranges.
61
    SlotIndexes *Indexes = nullptr;
62
63
    /// LIS - Used for accessing register mask interference maps.
64
    LiveIntervals *LIS = nullptr;
65
66
    /// PrevPos - The previous position the iterators were moved to.
67
    SlotIndex PrevPos;
68
69
    /// RegUnitInfo - Information tracked about each RegUnit in PhysReg.
70
    /// When PrevPos is set, the iterators are valid as if advanceTo(PrevPos)
71
    /// had just been called.
72
    struct RegUnitInfo {
73
      /// Iterator pointing into the LiveIntervalUnion containing virtual
74
      /// register interference.
75
      LiveIntervalUnion::SegmentIter VirtI;
76
77
      /// Tag of the LIU last time we looked.
78
      unsigned VirtTag;
79
80
      /// Fixed interference in RegUnit.
81
      LiveRange *Fixed = nullptr;
82
83
      /// Iterator pointing into the fixed RegUnit interference.
84
      LiveInterval::iterator FixedI;
85
86
2.91M
      RegUnitInfo(LiveIntervalUnion &LIU) : VirtTag(LIU.getTag()) {
87
2.91M
        VirtI.setMap(LIU.getMap());
88
2.91M
      }
89
    };
90
91
    /// Info for each RegUnit in PhysReg. It is very rare ofr a PHysReg to have
92
    /// more than 4 RegUnits.
93
    SmallVector<RegUnitInfo, 4> RegUnits;
94
95
    /// Blocks - Interference for each block in the function.
96
    SmallVector<BlockInterference, 8> Blocks;
97
98
    /// update - Recompute Blocks[MBBNum]
99
    void update(unsigned MBBNum);
100
101
  public:
102
1.01M
    Entry() = default;
103
104
18.7M
    void clear(MachineFunction *mf, SlotIndexes *indexes, LiveIntervals *lis) {
105
18.7M
      assert(!hasRefs() && "Cannot clear cache entry with references");
106
18.7M
      PhysReg = 0;
107
18.7M
      MF = mf;
108
18.7M
      Indexes = indexes;
109
18.7M
      LIS = lis;
110
18.7M
    }
111
112
9.19M
    unsigned getPhysReg() const { return PhysReg; }
113
114
71.2M
    void addRef(int Delta) { RefCount += Delta; }
115
116
8.95M
    bool hasRefs() const { return RefCount > 0; }
117
118
    void revalidate(LiveIntervalUnion *LIUArray, const TargetRegisterInfo *TRI);
119
120
    /// valid - Return true if this is a valid entry for physReg.
121
    bool valid(LiveIntervalUnion *LIUArray, const TargetRegisterInfo *TRI);
122
123
    /// reset - Initialize entry to represent physReg's aliases.
124
    void reset(unsigned physReg,
125
               LiveIntervalUnion *LIUArray,
126
               const TargetRegisterInfo *TRI,
127
               const MachineFunction *MF);
128
129
    /// get - Return an up to date BlockInterference.
130
251M
    BlockInterference *get(unsigned MBBNum) {
131
251M
      if (Blocks[MBBNum].Tag != Tag)
132
34.8M
        update(MBBNum);
133
251M
      return &Blocks[MBBNum];
134
251M
    }
135
  };
136
137
  // We don't keep a cache entry for every physical register, that would use too
138
  // much memory. Instead, a fixed number of cache entries are used in a round-
139
  // robin manner.
140
  enum { CacheEntries = 32 };
141
142
  const TargetRegisterInfo *TRI = nullptr;
143
  LiveIntervalUnion *LIUArray = nullptr;
144
  MachineFunction *MF = nullptr;
145
146
  // Point to an entry for each physreg. The entry pointed to may not be up to
147
  // date, and it may have been reused for a different physreg.
148
  unsigned char* PhysRegEntries = nullptr;
149
  size_t PhysRegEntriesCount = 0;
150
151
  // Next round-robin entry to be picked.
152
  unsigned RoundRobin = 0;
153
154
  // The actual cache entries.
155
  Entry Entries[CacheEntries];
156
157
  // get - Get a valid entry for PhysReg.
158
  Entry *get(unsigned PhysReg);
159
160
public:
161
  friend class Cursor;
162
163
31.8k
  InterferenceCache() = default;
164
165
31.7k
  ~InterferenceCache() {
166
31.7k
    free(PhysRegEntries);
167
31.7k
  }
168
169
  void reinitPhysRegEntries();
170
171
  /// init - Prepare cache for a new function.
172
  void init(MachineFunction *mf, LiveIntervalUnion *liuarray,
173
            SlotIndexes *indexes, LiveIntervals *lis,
174
            const TargetRegisterInfo *tri);
175
176
  /// getMaxCursors - Return the maximum number of concurrent cursors that can
177
  /// be supported.
178
9.19M
  unsigned getMaxCursors() const { return CacheEntries; }
179
180
  /// Cursor - The primary query interface for the block interference cache.
181
  class Cursor {
182
    Entry *CacheEntry = nullptr;
183
    const BlockInterference *Current = nullptr;
184
    static const BlockInterference NoInterference;
185
186
90.6M
    void setEntry(Entry *E) {
187
90.6M
      Current = nullptr;
188
90.6M
      // Update reference counts. Nothing happens when RefCount reaches 0, so
189
90.6M
      // we don't have to check for E == CacheEntry etc.
190
90.6M
      if (CacheEntry)
191
35.6M
        CacheEntry->addRef(-1);
192
90.6M
      CacheEntry = E;
193
90.6M
      if (CacheEntry)
194
35.6M
        CacheEntry->addRef(+1);
195
90.6M
    }
196
197
  public:
198
    /// Cursor - Create a dangling cursor.
199
18.7M
    Cursor() = default;
200
201
26.6M
    Cursor(const Cursor &O) {
202
26.6M
      setEntry(O.CacheEntry);
203
26.6M
    }
204
205
3.11k
    Cursor &operator=(const Cursor &O) {
206
3.11k
      setEntry(O.CacheEntry);
207
3.11k
      return *this;
208
3.11k
    }
209
210
45.4M
    ~Cursor() { setEntry(nullptr); }
211
212
    /// setPhysReg - Point this cursor to PhysReg's interference.
213
9.40M
    void setPhysReg(InterferenceCache &Cache, unsigned PhysReg) {
214
9.40M
      // Release reference before getting a new one. That guarantees we can
215
9.40M
      // actually have CacheEntries live cursors.
216
9.40M
      setEntry(nullptr);
217
9.40M
      if (PhysReg)
218
9.19M
        setEntry(Cache.get(PhysReg));
219
9.40M
    }
220
221
    /// moveTo - Move cursor to basic block MBBNum.
222
252M
    void moveToBlock(unsigned MBBNum) {
223
252M
      Current = CacheEntry ? 
CacheEntry->get(MBBNum)251M
:
&NoInterference837k
;
224
252M
    }
225
226
    /// hasInterference - Return true if the current block has any interference.
227
248M
    bool hasInterference() {
228
248M
      return Current->First.isValid();
229
248M
    }
230
231
    /// first - Return the starting index of the first interfering range in the
232
    /// current block.
233
63.3M
    SlotIndex first() {
234
63.3M
      return Current->First;
235
63.3M
    }
236
237
    /// last - Return the ending index of the last interfering range in the
238
    /// current block.
239
59.5M
    SlotIndex last() {
240
59.5M
      return Current->Last;
241
59.5M
    }
242
  };
243
};
244
245
} // end namespace llvm
246
247
#endif // LLVM_LIB_CODEGEN_INTERFERENCECACHE_H