Coverage Report

Created: 2017-10-03 07:32

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