1//===- RegAllocPBQP.cpp ---- PBQP 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 contains a Partitioned Boolean Quadratic Programming (PBQP) based
10// register allocator for LLVM. This allocator works by constructing a PBQP
11// problem representing the register allocation problem under consideration,
12// solving this using a PBQP solver, and mapping the solution back to a
13// register assignment. If any variables are selected for spilling then spill
14// code is inserted and the process repeated.
15//
16// The PBQP solver (pbqp.c) provided for this allocator uses a heuristic tuned
17// for register allocation. For more information on PBQP for register
18// allocation, see the following papers:
19//
20// (1) Hames, L. and Scholz, B. 2006. Nearly optimal register allocation with
21// PBQP. In Proceedings of the 7th Joint Modular Languages Conference
22// (JMLC'06). LNCS, vol. 4228. Springer, New York, NY, USA. 346-361.
23//
24// (2) Scholz, B., Eckstein, E. 2002. Register allocation for irregular
25// architectures. In Proceedings of the Joint Conference on Languages,
26// Compilers and Tools for Embedded Systems (LCTES'02), ACM Press, New York,
27// NY, USA, 139-148.
28//
29//===----------------------------------------------------------------------===//
30
31#include "llvm/CodeGen/RegAllocPBQP.h"
32#include "RegisterCoalescer.h"
33#include "llvm/ADT/ArrayRef.h"
34#include "llvm/ADT/BitVector.h"
35#include "llvm/ADT/DenseMap.h"
36#include "llvm/ADT/DenseSet.h"
37#include "llvm/ADT/STLExtras.h"
38#include "llvm/ADT/SmallPtrSet.h"
39#include "llvm/ADT/SmallVector.h"
40#include "llvm/ADT/StringRef.h"
41#include "llvm/Analysis/AliasAnalysis.h"
42#include "llvm/CodeGen/CalcSpillWeights.h"
43#include "llvm/CodeGen/LiveInterval.h"
44#include "llvm/CodeGen/LiveIntervals.h"
45#include "llvm/CodeGen/LiveRangeEdit.h"
46#include "llvm/CodeGen/LiveStacks.h"
47#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
48#include "llvm/CodeGen/MachineDominators.h"
49#include "llvm/CodeGen/MachineFunction.h"
50#include "llvm/CodeGen/MachineFunctionPass.h"
51#include "llvm/CodeGen/MachineInstr.h"
52#include "llvm/CodeGen/MachineLoopInfo.h"
53#include "llvm/CodeGen/MachineRegisterInfo.h"
54#include "llvm/CodeGen/PBQP/Graph.h"
55#include "llvm/CodeGen/PBQP/Math.h"
56#include "llvm/CodeGen/PBQP/Solution.h"
57#include "llvm/CodeGen/PBQPRAConstraint.h"
58#include "llvm/CodeGen/RegAllocRegistry.h"
59#include "llvm/CodeGen/SlotIndexes.h"
60#include "llvm/CodeGen/Spiller.h"
61#include "llvm/CodeGen/TargetRegisterInfo.h"
62#include "llvm/CodeGen/TargetSubtargetInfo.h"
63#include "llvm/CodeGen/VirtRegMap.h"
64#include "llvm/Config/llvm-config.h"
65#include "llvm/IR/Function.h"
66#include "llvm/IR/Module.h"
67#include "llvm/Pass.h"
68#include "llvm/Support/CommandLine.h"
69#include "llvm/Support/Compiler.h"
70#include "llvm/Support/Debug.h"
71#include "llvm/Support/FileSystem.h"
72#include "llvm/Support/Printable.h"
73#include "llvm/Support/raw_ostream.h"
74#include <algorithm>
75#include <cassert>
76#include <cstddef>
77#include <limits>
78#include <map>
79#include <memory>
80#include <queue>
81#include <set>
82#include <sstream>
83#include <string>
84#include <system_error>
85#include <tuple>
86#include <utility>
87#include <vector>
88
89using namespace llvm;
90
91#define DEBUG_TYPE "regalloc"
92
93static RegisterRegAlloc
94RegisterPBQPRepAlloc("pbqp", "PBQP register allocator",
95 createDefaultPBQPRegisterAllocator);
96
97static cl::opt<bool>
98PBQPCoalescing("pbqp-coalescing",
99 cl::desc("Attempt coalescing during PBQP register allocation."),
100 cl::init(Val: false), cl::Hidden);
101
102#ifndef NDEBUG
103static cl::opt<bool>
104PBQPDumpGraphs("pbqp-dump-graphs",
105 cl::desc("Dump graphs for each function/round in the compilation unit."),
106 cl::init(false), cl::Hidden);
107#endif
108
109namespace {
110
111///
112/// PBQP based allocators solve the register allocation problem by mapping
113/// register allocation problems to Partitioned Boolean Quadratic
114/// Programming problems.
115class RegAllocPBQP : public MachineFunctionPass {
116public:
117 static char ID;
118
119 /// Construct a PBQP register allocator.
120 RegAllocPBQP(char *cPassID = nullptr)
121 : MachineFunctionPass(ID), customPassID(cPassID) {}
122
123 /// Return the pass name.
124 StringRef getPassName() const override { return "PBQP Register Allocator"; }
125
126 /// PBQP analysis usage.
127 void getAnalysisUsage(AnalysisUsage &au) const override;
128
129 /// Perform register allocation
130 bool runOnMachineFunction(MachineFunction &MF) override;
131
132 MachineFunctionProperties getRequiredProperties() const override {
133 return MachineFunctionProperties().setNoPHIs();
134 }
135
136 MachineFunctionProperties getClearedProperties() const override {
137 return MachineFunctionProperties().setIsSSA();
138 }
139
140private:
141 using RegSet = std::set<Register>;
142
143 char *customPassID;
144
145 RegSet VRegsToAlloc, EmptyIntervalVRegs;
146
147 /// Inst which is a def of an original reg and whose defs are already all
148 /// dead after remat is saved in DeadRemats. The deletion of such inst is
149 /// postponed till all the allocations are done, so its remat expr is
150 /// always available for the remat of all the siblings of the original reg.
151 SmallPtrSet<MachineInstr *, 32> DeadRemats;
152
153 /// Finds the initial set of vreg intervals to allocate.
154 void findVRegIntervalsToAlloc(const MachineFunction &MF, LiveIntervals &LIS);
155
156 /// Constructs an initial graph.
157 void initializeGraph(PBQPRAGraph &G, VirtRegMap &VRM, Spiller &VRegSpiller);
158
159 /// Spill the given VReg.
160 void spillVReg(Register VReg, SmallVectorImpl<Register> &NewIntervals,
161 MachineFunction &MF, LiveIntervals &LIS, VirtRegMap &VRM,
162 Spiller &VRegSpiller);
163
164 /// Given a solved PBQP problem maps this solution back to a register
165 /// assignment.
166 bool mapPBQPToRegAlloc(const PBQPRAGraph &G,
167 const PBQP::Solution &Solution,
168 VirtRegMap &VRM,
169 Spiller &VRegSpiller);
170
171 /// Postprocessing before final spilling. Sets basic block "live in"
172 /// variables.
173 void finalizeAlloc(MachineFunction &MF, LiveIntervals &LIS,
174 VirtRegMap &VRM) const;
175
176 void postOptimization(Spiller &VRegSpiller, LiveIntervals &LIS);
177};
178
179char RegAllocPBQP::ID = 0;
180
181/// Set spill costs for each node in the PBQP reg-alloc graph.
182class SpillCosts : public PBQPRAConstraint {
183public:
184 void apply(PBQPRAGraph &G) override {
185 LiveIntervals &LIS = G.getMetadata().LIS;
186
187 // A minimum spill costs, so that register constraints can be set
188 // without normalization in the [0.0:MinSpillCost( interval.
189 const PBQP::PBQPNum MinSpillCost = 10.0;
190
191 for (auto NId : G.nodeIds()) {
192 PBQP::PBQPNum SpillCost =
193 LIS.getInterval(Reg: G.getNodeMetadata(NId).getVReg()).weight();
194 if (SpillCost == 0.0)
195 SpillCost = std::numeric_limits<PBQP::PBQPNum>::min();
196 else
197 SpillCost += MinSpillCost;
198 PBQPRAGraph::RawVector NodeCosts(G.getNodeCosts(NId));
199 NodeCosts[PBQP::RegAlloc::getSpillOptionIdx()] = SpillCost;
200 G.setNodeCosts(NId, Costs: std::move(NodeCosts));
201 }
202 }
203};
204
205/// Add interference edges between overlapping vregs.
206class Interference : public PBQPRAConstraint {
207private:
208 using AllowedRegVecPtr = const PBQP::RegAlloc::AllowedRegVector *;
209 using IKey = std::pair<AllowedRegVecPtr, AllowedRegVecPtr>;
210 using IMatrixCache = DenseMap<IKey, PBQPRAGraph::MatrixPtr>;
211 using DisjointAllowedRegsCache = DenseSet<IKey>;
212 using IEdgeKey = std::pair<PBQP::GraphBase::NodeId, PBQP::GraphBase::NodeId>;
213 using IEdgeCache = DenseSet<IEdgeKey>;
214
215 bool haveDisjointAllowedRegs(const PBQPRAGraph &G, PBQPRAGraph::NodeId NId,
216 PBQPRAGraph::NodeId MId,
217 const DisjointAllowedRegsCache &D) const {
218 const auto *NRegs = &G.getNodeMetadata(NId).getAllowedRegs();
219 const auto *MRegs = &G.getNodeMetadata(NId: MId).getAllowedRegs();
220
221 if (NRegs == MRegs)
222 return false;
223
224 if (NRegs < MRegs)
225 return D.contains(V: IKey(NRegs, MRegs));
226
227 return D.contains(V: IKey(MRegs, NRegs));
228 }
229
230 void setDisjointAllowedRegs(const PBQPRAGraph &G, PBQPRAGraph::NodeId NId,
231 PBQPRAGraph::NodeId MId,
232 DisjointAllowedRegsCache &D) {
233 const auto *NRegs = &G.getNodeMetadata(NId).getAllowedRegs();
234 const auto *MRegs = &G.getNodeMetadata(NId: MId).getAllowedRegs();
235
236 assert(NRegs != MRegs && "AllowedRegs can not be disjoint with itself");
237
238 if (NRegs < MRegs)
239 D.insert(V: IKey(NRegs, MRegs));
240 else
241 D.insert(V: IKey(MRegs, NRegs));
242 }
243
244 // Holds (Interval, CurrentSegmentID, and NodeId). The first two are required
245 // for the fast interference graph construction algorithm. The last is there
246 // to save us from looking up node ids via the VRegToNode map in the graph
247 // metadata.
248 using IntervalInfo =
249 std::tuple<LiveInterval*, size_t, PBQP::GraphBase::NodeId>;
250
251 static SlotIndex getStartPoint(const IntervalInfo &I) {
252 return std::get<0>(t: I)->segments[std::get<1>(t: I)].start;
253 }
254
255 static SlotIndex getEndPoint(const IntervalInfo &I) {
256 return std::get<0>(t: I)->segments[std::get<1>(t: I)].end;
257 }
258
259 static PBQP::GraphBase::NodeId getNodeId(const IntervalInfo &I) {
260 return std::get<2>(t: I);
261 }
262
263 static bool lowestStartPoint(const IntervalInfo &I1,
264 const IntervalInfo &I2) {
265 // Condition reversed because priority queue has the *highest* element at
266 // the front, rather than the lowest.
267 return getStartPoint(I: I1) > getStartPoint(I: I2);
268 }
269
270 static bool lowestEndPoint(const IntervalInfo &I1,
271 const IntervalInfo &I2) {
272 SlotIndex E1 = getEndPoint(I: I1);
273 SlotIndex E2 = getEndPoint(I: I2);
274
275 if (E1 < E2)
276 return true;
277
278 if (E1 > E2)
279 return false;
280
281 // If two intervals end at the same point, we need a way to break the tie or
282 // the set will assume they're actually equal and refuse to insert a
283 // "duplicate". Just compare the vregs - fast and guaranteed unique.
284 return std::get<0>(t: I1)->reg() < std::get<0>(t: I2)->reg();
285 }
286
287 static bool isAtLastSegment(const IntervalInfo &I) {
288 return std::get<1>(t: I) == std::get<0>(t: I)->size() - 1;
289 }
290
291 static IntervalInfo nextSegment(const IntervalInfo &I) {
292 return std::make_tuple(args: std::get<0>(t: I), args: std::get<1>(t: I) + 1, args: std::get<2>(t: I));
293 }
294
295public:
296 void apply(PBQPRAGraph &G) override {
297 // The following is loosely based on the linear scan algorithm introduced in
298 // "Linear Scan Register Allocation" by Poletto and Sarkar. This version
299 // isn't linear, because the size of the active set isn't bound by the
300 // number of registers, but rather the size of the largest clique in the
301 // graph. Still, we expect this to be better than N^2.
302 LiveIntervals &LIS = G.getMetadata().LIS;
303
304 // Interferenc matrices are incredibly regular - they're only a function of
305 // the allowed sets, so we cache them to avoid the overhead of constructing
306 // and uniquing them.
307 IMatrixCache C;
308
309 // Finding an edge is expensive in the worst case (O(max_clique(G))). So
310 // cache locally edges we have already seen.
311 IEdgeCache EC;
312
313 // Cache known disjoint allowed registers pairs
314 DisjointAllowedRegsCache D;
315
316 using IntervalSet = std::set<IntervalInfo, decltype(&lowestEndPoint)>;
317 using IntervalQueue =
318 std::priority_queue<IntervalInfo, std::vector<IntervalInfo>,
319 decltype(&lowestStartPoint)>;
320 IntervalSet Active(lowestEndPoint);
321 IntervalQueue Inactive(lowestStartPoint);
322
323 // Start by building the inactive set.
324 for (auto NId : G.nodeIds()) {
325 Register VReg = G.getNodeMetadata(NId).getVReg();
326 LiveInterval &LI = LIS.getInterval(Reg: VReg);
327 assert(!LI.empty() && "PBQP graph contains node for empty interval");
328 Inactive.push(x: std::make_tuple(args: &LI, args: 0, args&: NId));
329 }
330
331 while (!Inactive.empty()) {
332 // Tentatively grab the "next" interval - this choice may be overriden
333 // below.
334 IntervalInfo Cur = Inactive.top();
335
336 // Retire any active intervals that end before Cur starts.
337 IntervalSet::iterator RetireItr = Active.begin();
338 while (RetireItr != Active.end() &&
339 (getEndPoint(I: *RetireItr) <= getStartPoint(I: Cur))) {
340 // If this interval has subsequent segments, add the next one to the
341 // inactive list.
342 if (!isAtLastSegment(I: *RetireItr))
343 Inactive.push(x: nextSegment(I: *RetireItr));
344
345 ++RetireItr;
346 }
347 Active.erase(first: Active.begin(), last: RetireItr);
348
349 // One of the newly retired segments may actually start before the
350 // Cur segment, so re-grab the front of the inactive list.
351 Cur = Inactive.top();
352 Inactive.pop();
353
354 // At this point we know that Cur overlaps all active intervals. Add the
355 // interference edges.
356 PBQP::GraphBase::NodeId NId = getNodeId(I: Cur);
357 for (const auto &A : Active) {
358 PBQP::GraphBase::NodeId MId = getNodeId(I: A);
359
360 // Do not add an edge when the nodes' allowed registers do not
361 // intersect: there is obviously no interference.
362 if (haveDisjointAllowedRegs(G, NId, MId, D))
363 continue;
364
365 // Check that we haven't already added this edge
366 IEdgeKey EK(std::min(a: NId, b: MId), std::max(a: NId, b: MId));
367 if (EC.count(V: EK))
368 continue;
369
370 // This is a new edge - add it to the graph.
371 if (!createInterferenceEdge(G, NId, MId, C))
372 setDisjointAllowedRegs(G, NId, MId, D);
373 else
374 EC.insert(V: EK);
375 }
376
377 // Finally, add Cur to the Active set.
378 Active.insert(x: Cur);
379 }
380 }
381
382private:
383 // Create an Interference edge and add it to the graph, unless it is
384 // a null matrix, meaning the nodes' allowed registers do not have any
385 // interference. This case occurs frequently between integer and floating
386 // point registers for example.
387 // return true iff both nodes interferes.
388 bool createInterferenceEdge(PBQPRAGraph &G,
389 PBQPRAGraph::NodeId NId, PBQPRAGraph::NodeId MId,
390 IMatrixCache &C) {
391 const TargetRegisterInfo &TRI =
392 *G.getMetadata().MF.getSubtarget().getRegisterInfo();
393 const auto &NRegs = G.getNodeMetadata(NId).getAllowedRegs();
394 const auto &MRegs = G.getNodeMetadata(NId: MId).getAllowedRegs();
395
396 // Try looking the edge costs up in the IMatrixCache first.
397 IKey K(&NRegs, &MRegs);
398 IMatrixCache::iterator I = C.find(Val: K);
399 if (I != C.end()) {
400 G.addEdgeBypassingCostAllocator(N1Id: NId, N2Id: MId, Costs: I->second);
401 return true;
402 }
403
404 PBQPRAGraph::RawMatrix M(NRegs.size() + 1, MRegs.size() + 1, 0);
405 bool NodesInterfere = false;
406 for (unsigned I = 0; I != NRegs.size(); ++I) {
407 MCRegister PRegN = NRegs[I];
408 for (unsigned J = 0; J != MRegs.size(); ++J) {
409 MCRegister PRegM = MRegs[J];
410 if (TRI.regsOverlap(RegA: PRegN, RegB: PRegM)) {
411 M[I + 1][J + 1] = std::numeric_limits<PBQP::PBQPNum>::infinity();
412 NodesInterfere = true;
413 }
414 }
415 }
416
417 if (!NodesInterfere)
418 return false;
419
420 PBQPRAGraph::EdgeId EId = G.addEdge(N1Id: NId, N2Id: MId, Costs: std::move(M));
421 C[K] = G.getEdgeCostsPtr(EId);
422
423 return true;
424 }
425};
426
427class Coalescing : public PBQPRAConstraint {
428public:
429 void apply(PBQPRAGraph &G) override {
430 MachineFunction &MF = G.getMetadata().MF;
431 MachineBlockFrequencyInfo &MBFI = G.getMetadata().MBFI;
432 CoalescerPair CP(*MF.getSubtarget().getRegisterInfo());
433
434 // Scan the machine function and add a coalescing cost whenever CoalescerPair
435 // gives the Ok.
436 for (const auto &MBB : MF) {
437 for (const auto &MI : MBB) {
438 // Skip not-coalescable or already coalesced copies.
439 if (!CP.setRegisters(&MI) || CP.getSrcReg() == CP.getDstReg())
440 continue;
441
442 Register DstReg = CP.getDstReg();
443 Register SrcReg = CP.getSrcReg();
444
445 PBQP::PBQPNum CBenefit = MBFI.getBlockFreqRelativeToEntryBlock(MBB: &MBB);
446
447 if (CP.isPhys()) {
448 if (!MF.getRegInfo().isAllocatable(PhysReg: DstReg))
449 continue;
450
451 PBQPRAGraph::NodeId NId = G.getMetadata().getNodeIdForVReg(VReg: SrcReg);
452
453 const PBQPRAGraph::NodeMetadata::AllowedRegVector &Allowed =
454 G.getNodeMetadata(NId).getAllowedRegs();
455
456 unsigned PRegOpt = 0;
457 while (PRegOpt < Allowed.size() && Allowed[PRegOpt].id() != DstReg)
458 ++PRegOpt;
459
460 if (PRegOpt < Allowed.size()) {
461 PBQPRAGraph::RawVector NewCosts(G.getNodeCosts(NId));
462 NewCosts[PRegOpt + 1] -= CBenefit;
463 G.setNodeCosts(NId, Costs: std::move(NewCosts));
464 }
465 } else {
466 PBQPRAGraph::NodeId N1Id = G.getMetadata().getNodeIdForVReg(VReg: DstReg);
467 PBQPRAGraph::NodeId N2Id = G.getMetadata().getNodeIdForVReg(VReg: SrcReg);
468 const PBQPRAGraph::NodeMetadata::AllowedRegVector *Allowed1 =
469 &G.getNodeMetadata(NId: N1Id).getAllowedRegs();
470 const PBQPRAGraph::NodeMetadata::AllowedRegVector *Allowed2 =
471 &G.getNodeMetadata(NId: N2Id).getAllowedRegs();
472
473 PBQPRAGraph::EdgeId EId = G.findEdge(N1Id, N2Id);
474 if (EId == G.invalidEdgeId()) {
475 PBQPRAGraph::RawMatrix Costs(Allowed1->size() + 1,
476 Allowed2->size() + 1, 0);
477 addVirtRegCoalesce(CostMat&: Costs, Allowed1: *Allowed1, Allowed2: *Allowed2, Benefit: CBenefit);
478 G.addEdge(N1Id, N2Id, Costs: std::move(Costs));
479 } else {
480 if (G.getEdgeNode1Id(EId) == N2Id) {
481 std::swap(a&: N1Id, b&: N2Id);
482 std::swap(a&: Allowed1, b&: Allowed2);
483 }
484 PBQPRAGraph::RawMatrix Costs(G.getEdgeCosts(EId));
485 addVirtRegCoalesce(CostMat&: Costs, Allowed1: *Allowed1, Allowed2: *Allowed2, Benefit: CBenefit);
486 G.updateEdgeCosts(EId, Costs: std::move(Costs));
487 }
488 }
489 }
490 }
491 }
492
493private:
494 void addVirtRegCoalesce(
495 PBQPRAGraph::RawMatrix &CostMat,
496 const PBQPRAGraph::NodeMetadata::AllowedRegVector &Allowed1,
497 const PBQPRAGraph::NodeMetadata::AllowedRegVector &Allowed2,
498 PBQP::PBQPNum Benefit) {
499 assert(CostMat.getRows() == Allowed1.size() + 1 && "Size mismatch.");
500 assert(CostMat.getCols() == Allowed2.size() + 1 && "Size mismatch.");
501 for (unsigned I = 0; I != Allowed1.size(); ++I) {
502 MCRegister PReg1 = Allowed1[I];
503 for (unsigned J = 0; J != Allowed2.size(); ++J) {
504 MCRegister PReg2 = Allowed2[J];
505 if (PReg1 == PReg2)
506 CostMat[I + 1][J + 1] -= Benefit;
507 }
508 }
509 }
510};
511
512/// PBQP-specific implementation of weight normalization.
513class PBQPVirtRegAuxInfo final : public VirtRegAuxInfo {
514 float normalize(float UseDefFreq, unsigned Size, unsigned NumInstr) override {
515 // All intervals have a spill weight that is mostly proportional to the
516 // number of uses, with uses in loops having a bigger weight.
517 return NumInstr * VirtRegAuxInfo::normalize(UseDefFreq, Size, NumInstr: 1);
518 }
519
520public:
521 PBQPVirtRegAuxInfo(MachineFunction &MF, LiveIntervals &LIS, VirtRegMap &VRM,
522 const MachineLoopInfo &Loops,
523 const MachineBlockFrequencyInfo &MBFI)
524 : VirtRegAuxInfo(MF, LIS, VRM, Loops, MBFI) {}
525};
526} // end anonymous namespace
527
528// Out-of-line destructor/anchor for PBQPRAConstraint.
529PBQPRAConstraint::~PBQPRAConstraint() = default;
530
531void PBQPRAConstraint::anchor() {}
532
533void PBQPRAConstraintList::anchor() {}
534
535INITIALIZE_PASS_BEGIN(RegAllocPBQP, "regallocpbqp", "PBQP Register Allocator",
536 false, false)
537INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
538INITIALIZE_PASS_DEPENDENCY(SlotIndexesWrapperPass)
539INITIALIZE_PASS_DEPENDENCY(LiveIntervalsWrapperPass)
540INITIALIZE_PASS_DEPENDENCY(LiveStacksWrapperLegacy)
541INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfoWrapperPass)
542INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)
543INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
544INITIALIZE_PASS_DEPENDENCY(VirtRegMapWrapperLegacy)
545INITIALIZE_PASS_END(RegAllocPBQP, "regallocpbqp", "PBQP Register Allocator",
546 false, false)
547
548void RegAllocPBQP::getAnalysisUsage(AnalysisUsage &au) const {
549 au.setPreservesCFG();
550 au.addRequired<AAResultsWrapperPass>();
551 au.addPreserved<AAResultsWrapperPass>();
552 au.addRequired<SlotIndexesWrapperPass>();
553 au.addPreserved<SlotIndexesWrapperPass>();
554 au.addRequired<LiveIntervalsWrapperPass>();
555 au.addPreserved<LiveIntervalsWrapperPass>();
556 //au.addRequiredID(SplitCriticalEdgesID);
557 if (customPassID)
558 au.addRequiredID(ID&: *customPassID);
559 au.addRequired<LiveStacksWrapperLegacy>();
560 au.addPreserved<LiveStacksWrapperLegacy>();
561 au.addRequired<MachineBlockFrequencyInfoWrapperPass>();
562 au.addRequired<MachineLoopInfoWrapperPass>();
563 au.addRequired<MachineDominatorTreeWrapperPass>();
564 au.addRequired<VirtRegMapWrapperLegacy>();
565 au.addPreserved<VirtRegMapWrapperLegacy>();
566 MachineFunctionPass::getAnalysisUsage(AU&: au);
567}
568
569void RegAllocPBQP::findVRegIntervalsToAlloc(const MachineFunction &MF,
570 LiveIntervals &LIS) {
571 const MachineRegisterInfo &MRI = MF.getRegInfo();
572
573 // Iterate over all live ranges.
574 for (unsigned I = 0, E = MRI.getNumVirtRegs(); I != E; ++I) {
575 Register Reg = Register::index2VirtReg(Index: I);
576 if (MRI.reg_nodbg_empty(RegNo: Reg))
577 continue;
578 VRegsToAlloc.insert(x: Reg);
579 }
580}
581
582static bool isACalleeSavedRegister(MCRegister Reg,
583 const TargetRegisterInfo &TRI,
584 const MachineFunction &MF) {
585 const MCPhysReg *CSR = MF.getRegInfo().getCalleeSavedRegs();
586 for (unsigned i = 0; CSR[i] != 0; ++i)
587 if (TRI.regsOverlap(RegA: Reg, RegB: CSR[i]))
588 return true;
589 return false;
590}
591
592void RegAllocPBQP::initializeGraph(PBQPRAGraph &G, VirtRegMap &VRM,
593 Spiller &VRegSpiller) {
594 MachineFunction &MF = G.getMetadata().MF;
595
596 LiveIntervals &LIS = G.getMetadata().LIS;
597 const MachineRegisterInfo &MRI = G.getMetadata().MF.getRegInfo();
598 const TargetRegisterInfo &TRI =
599 *G.getMetadata().MF.getSubtarget().getRegisterInfo();
600
601 std::vector<Register> Worklist(VRegsToAlloc.begin(), VRegsToAlloc.end());
602
603 std::map<Register, std::vector<MCRegister>> VRegAllowedMap;
604
605 while (!Worklist.empty()) {
606 Register VReg = Worklist.back();
607 Worklist.pop_back();
608
609 LiveInterval &VRegLI = LIS.getInterval(Reg: VReg);
610
611 // If this is an empty interval move it to the EmptyIntervalVRegs set then
612 // continue.
613 if (VRegLI.empty()) {
614 EmptyIntervalVRegs.insert(x: VRegLI.reg());
615 VRegsToAlloc.erase(x: VRegLI.reg());
616 continue;
617 }
618
619 const TargetRegisterClass *TRC = MRI.getRegClass(Reg: VReg);
620
621 // Record any overlaps with regmask operands.
622 BitVector RegMaskOverlaps;
623 LIS.checkRegMaskInterference(LI: VRegLI, UsableRegs&: RegMaskOverlaps);
624
625 // Compute an initial allowed set for the current vreg.
626 std::vector<MCRegister> VRegAllowed;
627 ArrayRef<MCPhysReg> RawPRegOrder = TRI.getRawAllocationOrder(RC: *TRC, MF);
628 for (MCPhysReg R : RawPRegOrder) {
629 MCRegister PReg(R);
630 if (MRI.isReserved(PhysReg: PReg))
631 continue;
632
633 // vregLI crosses a regmask operand that clobbers preg.
634 if (!RegMaskOverlaps.empty() && !RegMaskOverlaps.test(Idx: PReg))
635 continue;
636
637 // vregLI overlaps fixed regunit interference.
638 bool Interference = false;
639 for (MCRegUnit Unit : TRI.regunits(Reg: PReg)) {
640 if (VRegLI.overlaps(other: LIS.getRegUnit(Unit))) {
641 Interference = true;
642 break;
643 }
644 }
645 if (Interference)
646 continue;
647
648 // preg is usable for this virtual register.
649 VRegAllowed.push_back(x: PReg);
650 }
651
652 // Check for vregs that have no allowed registers. These should be
653 // pre-spilled and the new vregs added to the worklist.
654 if (VRegAllowed.empty()) {
655 SmallVector<Register, 8> NewVRegs;
656 spillVReg(VReg, NewIntervals&: NewVRegs, MF, LIS, VRM, VRegSpiller);
657 llvm::append_range(C&: Worklist, R&: NewVRegs);
658 continue;
659 }
660
661 VRegAllowedMap[VReg.id()] = std::move(VRegAllowed);
662 }
663
664 for (auto &KV : VRegAllowedMap) {
665 auto VReg = KV.first;
666
667 // Move empty intervals to the EmptyIntervalVReg set.
668 if (LIS.getInterval(Reg: VReg).empty()) {
669 EmptyIntervalVRegs.insert(x: VReg);
670 VRegsToAlloc.erase(x: VReg);
671 continue;
672 }
673
674 auto &VRegAllowed = KV.second;
675
676 PBQPRAGraph::RawVector NodeCosts(VRegAllowed.size() + 1, 0);
677
678 // Tweak cost of callee saved registers, as using then force spilling and
679 // restoring them. This would only happen in the prologue / epilogue though.
680 for (unsigned i = 0; i != VRegAllowed.size(); ++i)
681 if (isACalleeSavedRegister(Reg: VRegAllowed[i], TRI, MF))
682 NodeCosts[1 + i] += 1.0;
683
684 PBQPRAGraph::NodeId NId = G.addNode(Costs: std::move(NodeCosts));
685 G.getNodeMetadata(NId).setVReg(VReg);
686 G.getNodeMetadata(NId).setAllowedRegs(
687 G.getMetadata().getAllowedRegs(Allowed: std::move(VRegAllowed)));
688 G.getMetadata().setNodeIdForVReg(VReg, NId);
689 }
690}
691
692void RegAllocPBQP::spillVReg(Register VReg,
693 SmallVectorImpl<Register> &NewIntervals,
694 MachineFunction &MF, LiveIntervals &LIS,
695 VirtRegMap &VRM, Spiller &VRegSpiller) {
696 VRegsToAlloc.erase(x: VReg);
697 LiveRangeEdit LRE(&LIS.getInterval(Reg: VReg), NewIntervals, MF, LIS, &VRM,
698 nullptr, &DeadRemats);
699 VRegSpiller.spill(LRE);
700
701 const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo();
702 (void)TRI;
703 LLVM_DEBUG(dbgs() << "VREG " << printReg(VReg, &TRI) << " -> SPILLED (Cost: "
704 << LRE.getParent().weight() << ", New vregs: ");
705
706 // Copy any newly inserted live intervals into the list of regs to
707 // allocate.
708 for (const Register &R : LRE) {
709 const LiveInterval &LI = LIS.getInterval(Reg: R);
710 assert(!LI.empty() && "Empty spill range.");
711 LLVM_DEBUG(dbgs() << printReg(LI.reg(), &TRI) << " ");
712 VRegsToAlloc.insert(x: LI.reg());
713 }
714
715 LLVM_DEBUG(dbgs() << ")\n");
716}
717
718bool RegAllocPBQP::mapPBQPToRegAlloc(const PBQPRAGraph &G,
719 const PBQP::Solution &Solution,
720 VirtRegMap &VRM,
721 Spiller &VRegSpiller) {
722 MachineFunction &MF = G.getMetadata().MF;
723 LiveIntervals &LIS = G.getMetadata().LIS;
724 const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo();
725 (void)TRI;
726
727 // Set to true if we have any spills
728 bool AnotherRoundNeeded = false;
729
730 // Clear the existing allocation.
731 VRM.clearAllVirt();
732
733 // Iterate over the nodes mapping the PBQP solution to a register
734 // assignment.
735 for (auto NId : G.nodeIds()) {
736 Register VReg = G.getNodeMetadata(NId).getVReg();
737 unsigned AllocOpt = Solution.getSelection(nodeId: NId);
738
739 if (AllocOpt != PBQP::RegAlloc::getSpillOptionIdx()) {
740 MCRegister PReg = G.getNodeMetadata(NId).getAllowedRegs()[AllocOpt - 1];
741 LLVM_DEBUG(dbgs() << "VREG " << printReg(VReg, &TRI) << " -> "
742 << TRI.getName(PReg) << "\n");
743 assert(PReg != 0 && "Invalid preg selected.");
744 VRM.assignVirt2Phys(virtReg: VReg, physReg: PReg);
745 } else {
746 // Spill VReg. If this introduces new intervals we'll need another round
747 // of allocation.
748 SmallVector<Register, 8> NewVRegs;
749 spillVReg(VReg, NewIntervals&: NewVRegs, MF, LIS, VRM, VRegSpiller);
750 AnotherRoundNeeded |= !NewVRegs.empty();
751 }
752 }
753
754 return !AnotherRoundNeeded;
755}
756
757void RegAllocPBQP::finalizeAlloc(MachineFunction &MF,
758 LiveIntervals &LIS,
759 VirtRegMap &VRM) const {
760 const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo();
761 MachineRegisterInfo &MRI = MF.getRegInfo();
762
763 // First allocate registers for the empty intervals.
764 for (const Register &R : EmptyIntervalVRegs) {
765 LiveInterval &LI = LIS.getInterval(Reg: R);
766
767 Register PReg = MRI.getSimpleHint(VReg: LI.reg());
768
769 if (PReg == 0) {
770 const TargetRegisterClass &RC = *MRI.getRegClass(Reg: LI.reg());
771 ArrayRef<MCPhysReg> RawPRegOrder = TRI.getRawAllocationOrder(RC, MF);
772 for (MCRegister CandidateReg : RawPRegOrder) {
773 if (!VRM.getRegInfo().isReserved(PhysReg: CandidateReg)) {
774 PReg = CandidateReg;
775 break;
776 }
777 }
778 assert(PReg &&
779 "No un-reserved physical registers in this register class");
780 }
781
782 VRM.assignVirt2Phys(virtReg: LI.reg(), physReg: PReg);
783 }
784}
785
786void RegAllocPBQP::postOptimization(Spiller &VRegSpiller, LiveIntervals &LIS) {
787 VRegSpiller.postOptimization();
788 /// Remove dead defs because of rematerialization.
789 for (auto *DeadInst : DeadRemats) {
790 LIS.RemoveMachineInstrFromMaps(MI&: *DeadInst);
791 DeadInst->eraseFromParent();
792 }
793 DeadRemats.clear();
794}
795
796bool RegAllocPBQP::runOnMachineFunction(MachineFunction &MF) {
797 LiveIntervals &LIS = getAnalysis<LiveIntervalsWrapperPass>().getLIS();
798 MachineBlockFrequencyInfo &MBFI =
799 getAnalysis<MachineBlockFrequencyInfoWrapperPass>().getMBFI();
800
801 auto &LiveStks = getAnalysis<LiveStacksWrapperLegacy>().getLS();
802 auto &MDT = getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
803
804 VirtRegMap &VRM = getAnalysis<VirtRegMapWrapperLegacy>().getVRM();
805
806 PBQPVirtRegAuxInfo VRAI(
807 MF, LIS, VRM, getAnalysis<MachineLoopInfoWrapperPass>().getLI(), MBFI);
808 VRAI.calculateSpillWeightsAndHints();
809
810 // FIXME: we create DefaultVRAI here to match existing behavior pre-passing
811 // the VRAI through the spiller to the live range editor. However, it probably
812 // makes more sense to pass the PBQP VRAI. The existing behavior had
813 // LiveRangeEdit make its own VirtRegAuxInfo object.
814 VirtRegAuxInfo DefaultVRAI(
815 MF, LIS, VRM, getAnalysis<MachineLoopInfoWrapperPass>().getLI(), MBFI);
816 std::unique_ptr<Spiller> VRegSpiller(
817 createInlineSpiller(Analyses: {.LIS: LIS, .LSS: LiveStks, .MDT: MDT, .MBFI: MBFI}, MF, VRM, VRAI&: DefaultVRAI));
818
819 MF.getRegInfo().freezeReservedRegs();
820
821 LLVM_DEBUG(dbgs() << "PBQP Register Allocating for " << MF.getName() << "\n");
822
823 // Allocator main loop:
824 //
825 // * Map current regalloc problem to a PBQP problem
826 // * Solve the PBQP problem
827 // * Map the solution back to a register allocation
828 // * Spill if necessary
829 //
830 // This process is continued till no more spills are generated.
831
832 // Find the vreg intervals in need of allocation.
833 findVRegIntervalsToAlloc(MF, LIS);
834
835#ifndef NDEBUG
836 const Function &F = MF.getFunction();
837 std::string FullyQualifiedName =
838 F.getParent()->getModuleIdentifier() + "." + F.getName().str();
839#endif
840
841 // If there are non-empty intervals allocate them using pbqp.
842 if (!VRegsToAlloc.empty()) {
843 const TargetSubtargetInfo &Subtarget = MF.getSubtarget();
844 std::unique_ptr<PBQPRAConstraintList> ConstraintsRoot =
845 std::make_unique<PBQPRAConstraintList>();
846 ConstraintsRoot->addConstraint(C: std::make_unique<SpillCosts>());
847 ConstraintsRoot->addConstraint(C: std::make_unique<Interference>());
848 if (PBQPCoalescing)
849 ConstraintsRoot->addConstraint(C: std::make_unique<Coalescing>());
850 ConstraintsRoot->addConstraint(C: Subtarget.getCustomPBQPConstraints());
851
852 bool PBQPAllocComplete = false;
853 unsigned Round = 0;
854
855 while (!PBQPAllocComplete) {
856 LLVM_DEBUG(dbgs() << " PBQP Regalloc round " << Round << ":\n");
857 (void) Round;
858
859 PBQPRAGraph G(PBQPRAGraph::GraphMetadata(MF, LIS, MBFI));
860 initializeGraph(G, VRM, VRegSpiller&: *VRegSpiller);
861 ConstraintsRoot->apply(G);
862
863#ifndef NDEBUG
864 if (PBQPDumpGraphs) {
865 std::ostringstream RS;
866 RS << Round;
867 std::string GraphFileName = FullyQualifiedName + "." + RS.str() +
868 ".pbqpgraph";
869 std::error_code EC;
870 raw_fd_ostream OS(GraphFileName, EC, sys::fs::OF_TextWithCRLF);
871 LLVM_DEBUG(dbgs() << "Dumping graph for round " << Round << " to \""
872 << GraphFileName << "\"\n");
873 G.dump(OS);
874 }
875#endif
876
877 PBQP::Solution Solution = PBQP::RegAlloc::solve(G);
878 PBQPAllocComplete = mapPBQPToRegAlloc(G, Solution, VRM, VRegSpiller&: *VRegSpiller);
879 ++Round;
880 }
881 }
882
883 // Finalise allocation, allocate empty ranges.
884 finalizeAlloc(MF, LIS, VRM);
885 postOptimization(VRegSpiller&: *VRegSpiller, LIS);
886 VRegsToAlloc.clear();
887 EmptyIntervalVRegs.clear();
888
889 LLVM_DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << VRM << "\n");
890
891 return true;
892}
893
894/// Create Printable object for node and register info.
895static Printable PrintNodeInfo(PBQP::RegAlloc::PBQPRAGraph::NodeId NId,
896 const PBQP::RegAlloc::PBQPRAGraph &G) {
897 return Printable([NId, &G](raw_ostream &OS) {
898 const MachineRegisterInfo &MRI = G.getMetadata().MF.getRegInfo();
899 const TargetRegisterInfo *TRI = MRI.getTargetRegisterInfo();
900 Register VReg = G.getNodeMetadata(NId).getVReg();
901 const char *RegClassName = TRI->getRegClassName(Class: MRI.getRegClass(Reg: VReg));
902 OS << NId << " (" << RegClassName << ':' << printReg(Reg: VReg, TRI) << ')';
903 });
904}
905
906#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
907LLVM_DUMP_METHOD void PBQP::RegAlloc::PBQPRAGraph::dump(raw_ostream &OS) const {
908 for (auto NId : nodeIds()) {
909 const Vector &Costs = getNodeCosts(NId);
910 assert(Costs.getLength() != 0 && "Empty vector in graph.");
911 OS << PrintNodeInfo(NId, *this) << ": " << Costs << '\n';
912 }
913 OS << '\n';
914
915 for (auto EId : edgeIds()) {
916 NodeId N1Id = getEdgeNode1Id(EId);
917 NodeId N2Id = getEdgeNode2Id(EId);
918 assert(N1Id != N2Id && "PBQP graphs should not have self-edges.");
919 const Matrix &M = getEdgeCosts(EId);
920 assert(M.getRows() != 0 && "No rows in matrix.");
921 assert(M.getCols() != 0 && "No cols in matrix.");
922 OS << PrintNodeInfo(N1Id, *this) << ' ' << M.getRows() << " rows / ";
923 OS << PrintNodeInfo(N2Id, *this) << ' ' << M.getCols() << " cols:\n";
924 OS << M << '\n';
925 }
926}
927
928LLVM_DUMP_METHOD void PBQP::RegAlloc::PBQPRAGraph::dump() const {
929 dump(dbgs());
930}
931#endif
932
933void PBQP::RegAlloc::PBQPRAGraph::printDot(raw_ostream &OS) const {
934 OS << "graph {\n";
935 for (auto NId : nodeIds()) {
936 OS << " node" << NId << " [ label=\""
937 << PrintNodeInfo(NId, G: *this) << "\\n"
938 << getNodeCosts(NId) << "\" ]\n";
939 }
940
941 OS << " edge [ len=" << nodeIds().size() << " ]\n";
942 for (auto EId : edgeIds()) {
943 OS << " node" << getEdgeNode1Id(EId)
944 << " -- node" << getEdgeNode2Id(EId)
945 << " [ label=\"";
946 const Matrix &EdgeCosts = getEdgeCosts(EId);
947 for (unsigned i = 0; i < EdgeCosts.getRows(); ++i) {
948 OS << EdgeCosts.getRowAsVector(R: i) << "\\n";
949 }
950 OS << "\" ]\n";
951 }
952 OS << "}\n";
953}
954
955FunctionPass *llvm::createPBQPRegisterAllocator(char *customPassID) {
956 return new RegAllocPBQP(customPassID);
957}
958
959FunctionPass* llvm::createDefaultPBQPRegisterAllocator() {
960 return createPBQPRegisterAllocator();
961}
962