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