1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
|
//===------ RegAllocPBQP.cpp ---- PBQP Register Allocator -------*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file contains a Partitioned Boolean Quadratic Programming (PBQP) based
// register allocator for LLVM. This allocator works by constructing a PBQP
// problem representing the register allocation problem under consideration,
// solving this using a PBQP solver, and mapping the solution back to a
// register assignment. If any variables are selected for spilling then spill
// code is inserted and the process repeated.
//
// The PBQP solver (pbqp.c) provided for this allocator uses a heuristic tuned
// for register allocation. For more information on PBQP for register
// allocation see the following papers:
//
// (1) Hames, L. and Scholz, B. 2006. Nearly optimal register allocation with
// PBQP. In Proceedings of the 7th Joint Modular Languages Conference
// (JMLC'06). LNCS, vol. 4228. Springer, New York, NY, USA. 346-361.
//
// (2) Scholz, B., Eckstein, E. 2002. Register allocation for irregular
// architectures. In Proceedings of the Joint Conference on Languages,
// Compilers and Tools for Embedded Systems (LCTES'02), ACM Press, New York,
// NY, USA, 139-148.
//
// Author: Lang Hames
// Email: lhames@gmail.com
//
//===----------------------------------------------------------------------===//
// TODO:
//
// * Use of std::set in constructPBQPProblem destroys allocation order preference.
// Switch to an order preserving container.
//
// * Coalescing support.
#define DEBUG_TYPE "regalloc"
#include "PBQP.h"
#include "VirtRegMap.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/RegAllocRegistry.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Support/Debug.h"
#include <memory>
#include <map>
#include <set>
#include <vector>
#include <limits>
using namespace llvm;
static RegisterRegAlloc
registerPBQPRepAlloc("pbqp", " PBQP register allocator",
createPBQPRegisterAllocator);
namespace {
//!
//! PBQP based allocators solve the register allocation problem by mapping
//! register allocation problems to Partitioned Boolean Quadratic
//! Programming problems.
class VISIBILITY_HIDDEN PBQPRegAlloc : public MachineFunctionPass {
public:
static char ID;
//! Construct a PBQP register allocator.
PBQPRegAlloc() : MachineFunctionPass((intptr_t)&ID) {}
//! Return the pass name.
virtual const char* getPassName() const throw() {
return "PBQP Register Allocator";
}
//! PBQP analysis usage.
virtual void getAnalysisUsage(AnalysisUsage &au) const {
au.addRequired<LiveIntervals>();
au.addRequired<MachineLoopInfo>();
MachineFunctionPass::getAnalysisUsage(au);
}
//! Perform register allocation
virtual bool runOnMachineFunction(MachineFunction &MF);
private:
typedef std::map<const LiveInterval*, unsigned> LI2NodeMap;
typedef std::vector<const LiveInterval*> Node2LIMap;
typedef std::vector<unsigned> AllowedSet;
typedef std::vector<AllowedSet> AllowedSetMap;
typedef std::set<unsigned> IgnoreSet;
MachineFunction *mf;
const TargetMachine *tm;
const TargetRegisterInfo *tri;
const TargetInstrInfo *tii;
const MachineLoopInfo *loopInfo;
MachineRegisterInfo *mri;
LiveIntervals *li;
VirtRegMap *vrm;
LI2NodeMap li2Node;
Node2LIMap node2LI;
AllowedSetMap allowedSets;
IgnoreSet ignoreSet;
//! Builds a PBQP cost vector.
template <typename Container>
PBQPVector* buildCostVector(const Container &allowed,
PBQPNum spillCost) const;
//! \brief Builds a PBQP interference matrix.
//!
//! @return Either a pointer to a non-zero PBQP matrix representing the
//! allocation option costs, or a null pointer for a zero matrix.
//!
//! Expects allowed sets for two interfering LiveIntervals. These allowed
//! sets should contain only allocable registers from the LiveInterval's
//! register class, with any interfering pre-colored registers removed.
template <typename Container>
PBQPMatrix* buildInterferenceMatrix(const Container &allowed1,
const Container &allowed2) const;
//!
//! Expects allowed sets for two potentially coalescable LiveIntervals,
//! and an estimated benefit due to coalescing. The allowed sets should
//! contain only allocable registers from the LiveInterval's register
//! classes, with any interfering pre-colored registers removed.
template <typename Container>
PBQPMatrix* buildCoalescingMatrix(const Container &allowed1,
const Container &allowed2,
PBQPNum cBenefit) const;
//! \brief Helper function for constructInitialPBQPProblem().
//!
//! This function iterates over the Function we are about to allocate for
//! and computes spill costs.
void calcSpillCosts();
//! \brief Scans the MachineFunction being allocated to find coalescing
// opportunities.
void findCoalescingOpportunities();
//! \brief Constructs a PBQP problem representation of the register
//! allocation problem for this function.
//!
//! @return a PBQP solver object for the register allocation problem.
pbqp* constructPBQPProblem();
//! \brief Given a solved PBQP problem maps this solution back to a register
//! assignment.
bool mapPBQPToRegAlloc(pbqp *problem);
};
char PBQPRegAlloc::ID = 0;
}
template <typename Container>
PBQPVector* PBQPRegAlloc::buildCostVector(const Container &allowed,
PBQPNum spillCost) const {
// Allocate vector. Additional element (0th) used for spill option
PBQPVector *v = new PBQPVector(allowed.size() + 1);
(*v)[0] = spillCost;
return v;
}
template <typename Container>
PBQPMatrix* PBQPRegAlloc::buildInterferenceMatrix(
const Container &allowed1, const Container &allowed2) const {
typedef typename Container::const_iterator ContainerIterator;
// Construct a PBQP matrix representing the cost of allocation options. The
// rows and columns correspond to the allocation options for the two live
// intervals. Elements will be infinite where corresponding registers alias,
// since we cannot allocate aliasing registers to interfering live intervals.
// All other elements (non-aliasing combinations) will have zero cost. Note
// that the spill option (element 0,0) has zero cost, since we can allocate
// both intervals to memory safely (the cost for each individual allocation
// to memory is accounted for by the cost vectors for each live interval).
PBQPMatrix *m = new PBQPMatrix(allowed1.size() + 1, allowed2.size() + 1);
// Assume this is a zero matrix until proven otherwise. Zero matrices occur
// between interfering live ranges with non-overlapping register sets (e.g.
// non-overlapping reg classes, or disjoint sets of allowed regs within the
// same class). The term "overlapping" is used advisedly: sets which do not
// intersect, but contain registers which alias, will have non-zero matrices.
// We optimize zero matrices away to improve solver speed.
bool isZeroMatrix = true;
// Row index. Starts at 1, since the 0th row is for the spill option, which
// is always zero.
unsigned ri = 1;
// Iterate over allowed sets, insert infinities where required.
for (ContainerIterator a1Itr = allowed1.begin(), a1End = allowed1.end();
a1Itr != a1End; ++a1Itr) {
// Column index, starts at 1 as for row index.
unsigned ci = 1;
unsigned reg1 = *a1Itr;
for (ContainerIterator a2Itr = allowed2.begin(), a2End = allowed2.end();
a2Itr != a2End; ++a2Itr) {
unsigned reg2 = *a2Itr;
// If the row/column regs are identical or alias insert an infinity.
if ((reg1 == reg2) || tri->areAliases(reg1, reg2)) {
(*m)[ri][ci] = std::numeric_limits<PBQPNum>::infinity();
isZeroMatrix = false;
}
++ci;
}
++ri;
}
// If this turns out to be a zero matrix...
if (isZeroMatrix) {
// free it and return null.
delete m;
return 0;
}
// ...otherwise return the cost matrix.
return m;
}
void PBQPRegAlloc::calcSpillCosts() {
// Calculate the spill cost for each live interval by iterating over the
// function counting loads and stores, with loop depth taken into account.
for (MachineFunction::const_iterator bbItr = mf->begin(), bbEnd = mf->end();
bbItr != bbEnd; ++bbItr) {
const MachineBasicBlock *mbb = &*bbItr;
float loopDepth = loopInfo->getLoopDepth(mbb);
for (MachineBasicBlock::const_iterator
iItr = mbb->begin(), iEnd = mbb->end(); iItr != iEnd; ++iItr) {
const MachineInstr *instr = &*iItr;
for (unsigned opNo = 0; opNo < instr->getNumOperands(); ++opNo) {
const MachineOperand &mo = instr->getOperand(opNo);
// We're not interested in non-registers...
if (!mo.isReg())
continue;
unsigned moReg = mo.getReg();
// ...Or invalid registers...
if (moReg == 0)
continue;
// ...Or physical registers...
if (TargetRegisterInfo::isPhysicalRegister(moReg))
continue;
assert ((mo.isUse() || mo.isDef()) &&
"Not a use, not a def, what is it?");
//... Just the virtual registers. We treat loads and stores as equal.
li->getInterval(moReg).weight += powf(10.0f, loopDepth);
}
}
}
}
pbqp* PBQPRegAlloc::constructPBQPProblem() {
typedef std::vector<const LiveInterval*> LIVector;
typedef std::set<unsigned> RegSet;
// These will store the physical & virtual intervals, respectively.
LIVector physIntervals, virtIntervals;
// Start by clearing the old node <-> live interval mappings & allowed sets
li2Node.clear();
node2LI.clear();
allowedSets.clear();
// Iterate over intervals classifying them as physical or virtual, and
// constructing live interval <-> node number mappings.
for (LiveIntervals::iterator itr = li->begin(), end = li->end();
itr != end; ++itr) {
if (itr->second->getNumValNums() != 0) {
DOUT << "Live range has " << itr->second->getNumValNums() << ": " << itr->second << "\n";
}
if (TargetRegisterInfo::isPhysicalRegister(itr->first)) {
physIntervals.push_back(itr->second);
mri->setPhysRegUsed(itr->second->reg);
}
else {
// If we've allocated this virtual register interval a stack slot on a
// previous round then it's not an allocation candidate
if (ignoreSet.find(itr->first) != ignoreSet.end())
continue;
li2Node[itr->second] = node2LI.size();
node2LI.push_back(itr->second);
virtIntervals.push_back(itr->second);
}
}
// Early out if there's no regs to allocate for.
if (virtIntervals.empty())
return 0;
// Construct a PBQP solver for this problem
pbqp *solver = alloc_pbqp(virtIntervals.size());
// Resize allowedSets container appropriately.
allowedSets.resize(virtIntervals.size());
// Iterate over virtual register intervals to compute allowed sets...
for (unsigned node = 0; node < node2LI.size(); ++node) {
// Grab pointers to the interval and its register class.
const LiveInterval *li = node2LI[node];
const TargetRegisterClass *liRC = mri->getRegClass(li->reg);
// Start by assuming all allocable registers in the class are allowed...
RegSet liAllowed(liRC->allocation_order_begin(*mf),
liRC->allocation_order_end(*mf));
// If this range is non-empty then eliminate the physical registers which
// overlap with this range, along with all their aliases.
if (!li->empty()) {
for (LIVector::iterator pItr = physIntervals.begin(),
pEnd = physIntervals.end(); pItr != pEnd; ++pItr) {
if (li->overlaps(**pItr)) {
unsigned pReg = (*pItr)->reg;
// Remove the overlapping reg...
liAllowed.erase(pReg);
const unsigned *aliasItr = tri->getAliasSet(pReg);
if (aliasItr != 0) {
// ...and its aliases.
for (; *aliasItr != 0; ++aliasItr) {
liAllowed.erase(*aliasItr);
}
}
}
}
}
// Copy the allowed set into a member vector for use when constructing cost
// vectors & matrices, and mapping PBQP solutions back to assignments.
allowedSets[node] = AllowedSet(liAllowed.begin(), liAllowed.end());
// Set the spill cost to the interval weight, or epsilon if the
// interval weight is zero
PBQPNum spillCost = (li->weight != 0.0) ?
li->weight : std::numeric_limits<PBQPNum>::min();
// Build a cost vector for this interval.
add_pbqp_nodecosts(solver, node,
buildCostVector(allowedSets[node], spillCost));
}
// Now add the cost matrices...
for (unsigned node1 = 0; node1 < node2LI.size(); ++node1) {
const LiveInterval *li = node2LI[node1];
if (li->empty())
continue;
// Test for live range overlaps and insert interference matrices.
for (unsigned node2 = node1 + 1; node2 < node2LI.size(); ++node2) {
const LiveInterval *li2 = node2LI[node2];
if (li2->empty())
continue;
if (li->overlaps(*li2)) {
PBQPMatrix *m =
buildInterferenceMatrix(allowedSets[node1], allowedSets[node2]);
if (m != 0) {
add_pbqp_edgecosts(solver, node1, node2, m);
delete m;
}
}
}
}
// We're done, PBQP problem constructed - return it.
return solver;
}
bool PBQPRegAlloc::mapPBQPToRegAlloc(pbqp *problem) {
// Set to true if we have any spills
bool anotherRoundNeeded = false;
// Clear the existing allocation.
vrm->clearAllVirt();
// Iterate over the nodes mapping the PBQP solution to a register assignment.
for (unsigned node = 0; node < node2LI.size(); ++node) {
unsigned symReg = node2LI[node]->reg,
allocSelection = get_pbqp_solution(problem, node);
// If the PBQP solution is non-zero it's a physical register...
if (allocSelection != 0) {
// Get the physical reg, subtracting 1 to account for the spill option.
unsigned physReg = allowedSets[node][allocSelection - 1];
// Add to the virt reg map and update the used phys regs.
vrm->assignVirt2Phys(symReg, physReg);
mri->setPhysRegUsed(physReg);
}
// ...Otherwise it's a spill.
else {
// Make sure we ignore this virtual reg on the next round
// of allocation
ignoreSet.insert(node2LI[node]->reg);
float SSWeight;
// Insert spill ranges for this live range
SmallVector<LiveInterval*, 8> spillIs;
std::vector<LiveInterval*> newSpills =
li->addIntervalsForSpills(*node2LI[node], spillIs, loopInfo, *vrm,
SSWeight);
// We need another round if spill intervals were added.
anotherRoundNeeded |= !newSpills.empty();
}
}
return !anotherRoundNeeded;
}
bool PBQPRegAlloc::runOnMachineFunction(MachineFunction &MF) {
mf = &MF;
tm = &mf->getTarget();
tri = tm->getRegisterInfo();
mri = &mf->getRegInfo();
li = &getAnalysis<LiveIntervals>();
loopInfo = &getAnalysis<MachineLoopInfo>();
std::auto_ptr<VirtRegMap> vrmAutoPtr(new VirtRegMap(*mf));
vrm = vrmAutoPtr.get();
// Allocator main loop:
//
// * Map current regalloc problem to a PBQP problem
// * Solve the PBQP problem
// * Map the solution back to a register allocation
// * Spill if necessary
//
// This process is continued till no more spills are generated.
bool regallocComplete = false;
// Calculate spill costs for intervals
calcSpillCosts();
while (!regallocComplete) {
pbqp *problem = constructPBQPProblem();
// Fast out if there's no problem to solve.
if (problem == 0)
return true;
solve_pbqp(problem);
regallocComplete = mapPBQPToRegAlloc(problem);
free_pbqp(problem);
}
ignoreSet.clear();
std::auto_ptr<Spiller> spiller(createSpiller());
spiller->runOnMachineFunction(*mf, *vrm);
return true;
}
FunctionPass* llvm::createPBQPRegisterAllocator() {
return new PBQPRegAlloc();
}
#undef DEBUG_TYPE
|