Coverage Report

Created: 2019-07-24 05:18

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