Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/RegAllocBasic.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- RegAllocBasic.cpp - Basic Register Allocator ----------------------===//
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
// This file defines the RABasic function pass, which provides a minimal
10
// implementation of the basic register allocator.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#include "AllocationOrder.h"
15
#include "LiveDebugVariables.h"
16
#include "RegAllocBase.h"
17
#include "Spiller.h"
18
#include "llvm/Analysis/AliasAnalysis.h"
19
#include "llvm/CodeGen/CalcSpillWeights.h"
20
#include "llvm/CodeGen/LiveIntervals.h"
21
#include "llvm/CodeGen/LiveRangeEdit.h"
22
#include "llvm/CodeGen/LiveRegMatrix.h"
23
#include "llvm/CodeGen/LiveStacks.h"
24
#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
25
#include "llvm/CodeGen/MachineFunctionPass.h"
26
#include "llvm/CodeGen/MachineInstr.h"
27
#include "llvm/CodeGen/MachineLoopInfo.h"
28
#include "llvm/CodeGen/MachineRegisterInfo.h"
29
#include "llvm/CodeGen/Passes.h"
30
#include "llvm/CodeGen/RegAllocRegistry.h"
31
#include "llvm/CodeGen/TargetRegisterInfo.h"
32
#include "llvm/CodeGen/VirtRegMap.h"
33
#include "llvm/PassAnalysisSupport.h"
34
#include "llvm/Support/Debug.h"
35
#include "llvm/Support/raw_ostream.h"
36
#include <cstdlib>
37
#include <queue>
38
39
using namespace llvm;
40
41
#define DEBUG_TYPE "regalloc"
42
43
static RegisterRegAlloc basicRegAlloc("basic", "basic register allocator",
44
                                      createBasicRegisterAllocator);
45
46
namespace {
47
  struct CompSpillWeight {
48
78.9k
    bool operator()(LiveInterval *A, LiveInterval *B) const {
49
78.9k
      return A->weight < B->weight;
50
78.9k
    }
51
  };
52
}
53
54
namespace {
55
/// RABasic provides a minimal implementation of the basic register allocation
56
/// algorithm. It prioritizes live virtual registers by spill weight and spills
57
/// whenever a register is unavailable. This is not practical in production but
58
/// provides a useful baseline both for measuring other allocators and comparing
59
/// the speed of the basic algorithm against other styles of allocators.
60
class RABasic : public MachineFunctionPass,
61
                public RegAllocBase,
62
                private LiveRangeEdit::Delegate {
63
  // context
64
  MachineFunction *MF;
65
66
  // state
67
  std::unique_ptr<Spiller> SpillerInstance;
68
  std::priority_queue<LiveInterval*, std::vector<LiveInterval*>,
69
                      CompSpillWeight> Queue;
70
71
  // Scratch space.  Allocated here to avoid repeated malloc calls in
72
  // selectOrSplit().
73
  BitVector UsableRegs;
74
75
  bool LRE_CanEraseVirtReg(unsigned) override;
76
  void LRE_WillShrinkVirtReg(unsigned) override;
77
78
public:
79
  RABasic();
80
81
  /// Return the pass name.
82
270
  StringRef getPassName() const override { return "Basic Register Allocator"; }
83
84
  /// RABasic analysis usage.
85
  void getAnalysisUsage(AnalysisUsage &AU) const override;
86
87
  void releaseMemory() override;
88
89
816
  Spiller &spiller() override { return *SpillerInstance; }
90
91
5.03k
  void enqueue(LiveInterval *LI) override {
92
5.03k
    Queue.push(LI);
93
5.03k
  }
94
95
5.26k
  LiveInterval *dequeue() override {
96
5.26k
    if (Queue.empty())
97
225
      return nullptr;
98
5.03k
    LiveInterval *LI = Queue.top();
99
5.03k
    Queue.pop();
100
5.03k
    return LI;
101
5.03k
  }
102
103
  unsigned selectOrSplit(LiveInterval &VirtReg,
104
                         SmallVectorImpl<unsigned> &SplitVRegs) override;
105
106
  /// Perform register allocation.
107
  bool runOnMachineFunction(MachineFunction &mf) override;
108
109
45
  MachineFunctionProperties getRequiredProperties() const override {
110
45
    return MachineFunctionProperties().set(
111
45
        MachineFunctionProperties::Property::NoPHIs);
112
45
  }
113
114
  // Helper for spilling all live virtual registers currently unified under preg
115
  // that interfere with the most recently queried lvr.  Return true if spilling
116
  // was successful, and append any new spilled/split intervals to splitLVRs.
117
  bool spillInterferences(LiveInterval &VirtReg, unsigned PhysReg,
118
                          SmallVectorImpl<unsigned> &SplitVRegs);
119
120
  static char ID;
121
};
122
123
char RABasic::ID = 0;
124
125
} // end anonymous namespace
126
127
char &llvm::RABasicID = RABasic::ID;
128
129
42.3k
INITIALIZE_PASS_BEGIN(RABasic, "regallocbasic", "Basic Register Allocator",
130
42.3k
                      false, false)
131
42.3k
INITIALIZE_PASS_DEPENDENCY(LiveDebugVariables)
132
42.3k
INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
133
42.3k
INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
134
42.3k
INITIALIZE_PASS_DEPENDENCY(RegisterCoalescer)
135
42.3k
INITIALIZE_PASS_DEPENDENCY(MachineScheduler)
136
42.3k
INITIALIZE_PASS_DEPENDENCY(LiveStacks)
137
42.3k
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
138
42.3k
INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
139
42.3k
INITIALIZE_PASS_DEPENDENCY(VirtRegMap)
140
42.3k
INITIALIZE_PASS_DEPENDENCY(LiveRegMatrix)
141
42.3k
INITIALIZE_PASS_END(RABasic, "regallocbasic", "Basic Register Allocator", false,
142
                    false)
143
144
835
bool RABasic::LRE_CanEraseVirtReg(unsigned VirtReg) {
145
835
  LiveInterval &LI = LIS->getInterval(VirtReg);
146
835
  if (VRM->hasPhys(VirtReg)) {
147
0
    Matrix->unassign(LI);
148
0
    aboutToRemoveInterval(LI);
149
0
    return true;
150
0
  }
151
835
  // Unassigned virtreg is probably in the priority queue.
152
835
  // RegAllocBase will erase it after dequeueing.
153
835
  // Nonetheless, clear the live-range so that the debug
154
835
  // dump will show the right state for that VirtReg.
155
835
  LI.clear();
156
835
  return false;
157
835
}
158
159
251
void RABasic::LRE_WillShrinkVirtReg(unsigned VirtReg) {
160
251
  if (!VRM->hasPhys(VirtReg))
161
250
    return;
162
1
163
1
  // Register is assigned, put it back on the queue for reassignment.
164
1
  LiveInterval &LI = LIS->getInterval(VirtReg);
165
1
  Matrix->unassign(LI);
166
1
  enqueue(&LI);
167
1
}
168
169
45
RABasic::RABasic(): MachineFunctionPass(ID) {
170
45
}
171
172
45
void RABasic::getAnalysisUsage(AnalysisUsage &AU) const {
173
45
  AU.setPreservesCFG();
174
45
  AU.addRequired<AAResultsWrapperPass>();
175
45
  AU.addPreserved<AAResultsWrapperPass>();
176
45
  AU.addRequired<LiveIntervals>();
177
45
  AU.addPreserved<LiveIntervals>();
178
45
  AU.addPreserved<SlotIndexes>();
179
45
  AU.addRequired<LiveDebugVariables>();
180
45
  AU.addPreserved<LiveDebugVariables>();
181
45
  AU.addRequired<LiveStacks>();
182
45
  AU.addPreserved<LiveStacks>();
183
45
  AU.addRequired<MachineBlockFrequencyInfo>();
184
45
  AU.addPreserved<MachineBlockFrequencyInfo>();
185
45
  AU.addRequiredID(MachineDominatorsID);
186
45
  AU.addPreservedID(MachineDominatorsID);
187
45
  AU.addRequired<MachineLoopInfo>();
188
45
  AU.addPreserved<MachineLoopInfo>();
189
45
  AU.addRequired<VirtRegMap>();
190
45
  AU.addPreserved<VirtRegMap>();
191
45
  AU.addRequired<LiveRegMatrix>();
192
45
  AU.addPreserved<LiveRegMatrix>();
193
45
  MachineFunctionPass::getAnalysisUsage(AU);
194
45
}
195
196
450
void RABasic::releaseMemory() {
197
450
  SpillerInstance.reset();
198
450
}
199
200
201
// Spill or split all live virtual registers currently unified under PhysReg
202
// that interfere with VirtReg. The newly spilled or split live intervals are
203
// returned by appending them to SplitVRegs.
204
bool RABasic::spillInterferences(LiveInterval &VirtReg, unsigned PhysReg,
205
29.9k
                                 SmallVectorImpl<unsigned> &SplitVRegs) {
206
29.9k
  // Record each interference and determine if all are spillable before mutating
207
29.9k
  // either the union or live intervals.
208
29.9k
  SmallVector<LiveInterval*, 8> Intfs;
209
29.9k
210
29.9k
  // Collect interferences assigned to any alias of the physical register.
211
29.9k
  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); 
++Units21
) {
212
29.9k
    LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units);
213
29.9k
    Q.collectInterferingVRegs();
214
29.9k
    for (unsigned i = Q.interferingVRegs().size(); i; 
--i19
) {
215
29.9k
      LiveInterval *Intf = Q.interferingVRegs()[i - 1];
216
29.9k
      if (!Intf->isSpillable() || 
Intf->weight > VirtReg.weight28.8k
)
217
29.9k
        return false;
218
19
      Intfs.push_back(Intf);
219
19
    }
220
29.9k
  }
221
29.9k
  
LLVM_DEBUG7
(dbgs() << "spilling " << printReg(PhysReg, TRI)
222
7
                    << " interferences with " << VirtReg << "\n");
223
7
  assert(!Intfs.empty() && "expected interference");
224
7
225
7
  // Spill each interfering vreg allocated to PhysReg or an alias.
226
26
  for (unsigned i = 0, e = Intfs.size(); i != e; 
++i19
) {
227
19
    LiveInterval &Spill = *Intfs[i];
228
19
229
19
    // Skip duplicates.
230
19
    if (!VRM->hasPhys(Spill.reg))
231
12
      continue;
232
7
233
7
    // Deallocate the interfering vreg by removing it from the union.
234
7
    // A LiveInterval instance may not be in a union during modification!
235
7
    Matrix->unassign(Spill);
236
7
237
7
    // Spill the extracted interval.
238
7
    LiveRangeEdit LRE(&Spill, SplitVRegs, *MF, *LIS, VRM, this, &DeadRemats);
239
7
    spiller().spill(LRE);
240
7
  }
241
7
  return true;
242
29.9k
}
243
244
// Driver for the register assignment and splitting heuristics.
245
// Manages iteration over the LiveIntervalUnions.
246
//
247
// This is a minimal implementation of register assignment and splitting that
248
// spills whenever we run out of registers.
249
//
250
// selectOrSplit can only be called once per live virtual register. We then do a
251
// single interference test for each register the correct class until we find an
252
// available register. So, the number of interference tests in the worst case is
253
// |vregs| * |machineregs|. And since the number of interference tests is
254
// minimal, there is no value in caching them outside the scope of
255
// selectOrSplit().
256
unsigned RABasic::selectOrSplit(LiveInterval &VirtReg,
257
5.03k
                                SmallVectorImpl<unsigned> &SplitVRegs) {
258
5.03k
  // Populate a list of physical register spill candidates.
259
5.03k
  SmallVector<unsigned, 8> PhysRegSpillCands;
260
5.03k
261
5.03k
  // Check for an available register in this class.
262
5.03k
  AllocationOrder Order(VirtReg.reg, *VRM, RegClassInfo, Matrix);
263
114k
  while (unsigned PhysReg = Order.next()) {
264
113k
    // Check for interference in PhysReg
265
113k
    switch (Matrix->checkInterference(VirtReg, PhysReg)) {
266
113k
    case LiveRegMatrix::IK_Free:
267
4.44k
      // PhysReg is available, allocate it.
268
4.44k
      return PhysReg;
269
113k
270
113k
    case LiveRegMatrix::IK_VirtReg:
271
36.9k
      // Only virtual registers in the way, we may be able to spill them.
272
36.9k
      PhysRegSpillCands.push_back(PhysReg);
273
36.9k
      continue;
274
113k
275
113k
    default:
276
72.5k
      // RegMask or RegUnit interference.
277
72.5k
      continue;
278
113k
    }
279
113k
  }
280
5.03k
281
5.03k
  // Try to spill another interfering reg with less spill weight.
282
5.03k
  for (SmallVectorImpl<unsigned>::iterator PhysRegI = PhysRegSpillCands.begin(),
283
30.5k
       PhysRegE = PhysRegSpillCands.end(); PhysRegI != PhysRegE; 
++PhysRegI29.9k
) {
284
29.9k
    if (!spillInterferences(VirtReg, *PhysRegI, SplitVRegs))
285
29.9k
      continue;
286
7
287
7
    assert(!Matrix->checkInterference(VirtReg, *PhysRegI) &&
288
7
           "Interference after spill.");
289
7
    // Tell the caller to allocate to this newly freed physical register.
290
7
    return *PhysRegI;
291
7
  }
292
594
293
594
  // No other spill candidates were found, so spill the current VirtReg.
294
594
  
LLVM_DEBUG587
(dbgs() << "spilling: " << VirtReg << '\n');
295
587
  if (!VirtReg.isSpillable())
296
3
    return ~0u;
297
584
  LiveRangeEdit LRE(&VirtReg, SplitVRegs, *MF, *LIS, VRM, this, &DeadRemats);
298
584
  spiller().spill(LRE);
299
584
300
584
  // The live virtual register requesting allocation was spilled, so tell
301
584
  // the caller not to allocate anything during this round.
302
584
  return 0;
303
584
}
304
305
225
bool RABasic::runOnMachineFunction(MachineFunction &mf) {
306
225
  LLVM_DEBUG(dbgs() << "********** BASIC REGISTER ALLOCATION **********\n"
307
225
                    << "********** Function: " << mf.getName() << '\n');
308
225
309
225
  MF = &mf;
310
225
  RegAllocBase::init(getAnalysis<VirtRegMap>(),
311
225
                     getAnalysis<LiveIntervals>(),
312
225
                     getAnalysis<LiveRegMatrix>());
313
225
314
225
  calculateSpillWeightsAndHints(*LIS, *MF, VRM,
315
225
                                getAnalysis<MachineLoopInfo>(),
316
225
                                getAnalysis<MachineBlockFrequencyInfo>());
317
225
318
225
  SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM));
319
225
320
225
  allocatePhysRegs();
321
225
  postOptimization();
322
225
323
225
  // Diagnostic output before rewriting
324
225
  LLVM_DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *VRM << "\n");
325
225
326
225
  releaseMemory();
327
225
  return true;
328
225
}
329
330
FunctionPass* llvm::createBasicRegisterAllocator()
331
42
{
332
42
  return new RABasic();
333
42
}