1 //===- RegAllocGreedy.cpp - greedy register allocator ---------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defines the RAGreedy function pass for register allocation in
10 // optimized builds.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #include "AllocationOrder.h"
15 #include "InterferenceCache.h"
16 #include "LiveDebugVariables.h"
17 #include "RegAllocBase.h"
18 #include "SpillPlacement.h"
19 #include "SplitKit.h"
20 #include "llvm/ADT/ArrayRef.h"
21 #include "llvm/ADT/BitVector.h"
22 #include "llvm/ADT/DenseMap.h"
23 #include "llvm/ADT/IndexedMap.h"
24 #include "llvm/ADT/MapVector.h"
25 #include "llvm/ADT/SetVector.h"
26 #include "llvm/ADT/SmallPtrSet.h"
27 #include "llvm/ADT/SmallSet.h"
28 #include "llvm/ADT/SmallVector.h"
29 #include "llvm/ADT/Statistic.h"
30 #include "llvm/ADT/StringRef.h"
31 #include "llvm/Analysis/AliasAnalysis.h"
32 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
33 #include "llvm/CodeGen/CalcSpillWeights.h"
34 #include "llvm/CodeGen/EdgeBundles.h"
35 #include "llvm/CodeGen/LiveInterval.h"
36 #include "llvm/CodeGen/LiveIntervalUnion.h"
37 #include "llvm/CodeGen/LiveIntervals.h"
38 #include "llvm/CodeGen/LiveRangeEdit.h"
39 #include "llvm/CodeGen/LiveRegMatrix.h"
40 #include "llvm/CodeGen/LiveStacks.h"
41 #include "llvm/CodeGen/MachineBasicBlock.h"
42 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
43 #include "llvm/CodeGen/MachineDominators.h"
44 #include "llvm/CodeGen/MachineFrameInfo.h"
45 #include "llvm/CodeGen/MachineFunction.h"
46 #include "llvm/CodeGen/MachineFunctionPass.h"
47 #include "llvm/CodeGen/MachineInstr.h"
48 #include "llvm/CodeGen/MachineLoopInfo.h"
49 #include "llvm/CodeGen/MachineOperand.h"
50 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
51 #include "llvm/CodeGen/MachineRegisterInfo.h"
52 #include "llvm/CodeGen/RegAllocRegistry.h"
53 #include "llvm/CodeGen/RegisterClassInfo.h"
54 #include "llvm/CodeGen/SlotIndexes.h"
55 #include "llvm/CodeGen/Spiller.h"
56 #include "llvm/CodeGen/TargetInstrInfo.h"
57 #include "llvm/CodeGen/TargetRegisterInfo.h"
58 #include "llvm/CodeGen/TargetSubtargetInfo.h"
59 #include "llvm/CodeGen/VirtRegMap.h"
60 #include "llvm/IR/Function.h"
61 #include "llvm/IR/LLVMContext.h"
62 #include "llvm/MC/MCRegisterInfo.h"
63 #include "llvm/Pass.h"
64 #include "llvm/Support/BlockFrequency.h"
65 #include "llvm/Support/BranchProbability.h"
66 #include "llvm/Support/CommandLine.h"
67 #include "llvm/Support/Debug.h"
68 #include "llvm/Support/MathExtras.h"
69 #include "llvm/Support/Timer.h"
70 #include "llvm/Support/raw_ostream.h"
71 #include "llvm/Target/TargetMachine.h"
72 #include <algorithm>
73 #include <cassert>
74 #include <cstdint>
75 #include <memory>
76 #include <queue>
77 #include <tuple>
78 #include <utility>
79
80 using namespace llvm;
81
82 #define DEBUG_TYPE "regalloc"
83
84 STATISTIC(NumGlobalSplits, "Number of split global live ranges");
85 STATISTIC(NumLocalSplits, "Number of split local live ranges");
86 STATISTIC(NumEvicted, "Number of interferences evicted");
87
88 static cl::opt<SplitEditor::ComplementSpillMode> SplitSpillMode(
89 "split-spill-mode", cl::Hidden,
90 cl::desc("Spill mode for splitting live ranges"),
91 cl::values(clEnumValN(SplitEditor::SM_Partition, "default", "Default"),
92 clEnumValN(SplitEditor::SM_Size, "size", "Optimize for size"),
93 clEnumValN(SplitEditor::SM_Speed, "speed", "Optimize for speed")),
94 cl::init(SplitEditor::SM_Speed));
95
96 static cl::opt<unsigned>
97 LastChanceRecoloringMaxDepth("lcr-max-depth", cl::Hidden,
98 cl::desc("Last chance recoloring max depth"),
99 cl::init(5));
100
101 static cl::opt<unsigned> LastChanceRecoloringMaxInterference(
102 "lcr-max-interf", cl::Hidden,
103 cl::desc("Last chance recoloring maximum number of considered"
104 " interference at a time"),
105 cl::init(8));
106
107 static cl::opt<bool> ExhaustiveSearch(
108 "exhaustive-register-search", cl::NotHidden,
109 cl::desc("Exhaustive Search for registers bypassing the depth "
110 "and interference cutoffs of last chance recoloring"),
111 cl::Hidden);
112
113 static cl::opt<bool> EnableLocalReassignment(
114 "enable-local-reassign", cl::Hidden,
115 cl::desc("Local reassignment can yield better allocation decisions, but "
116 "may be compile time intensive"),
117 cl::init(false));
118
119 static cl::opt<bool> EnableDeferredSpilling(
120 "enable-deferred-spilling", cl::Hidden,
121 cl::desc("Instead of spilling a variable right away, defer the actual "
122 "code insertion to the end of the allocation. That way the "
123 "allocator might still find a suitable coloring for this "
124 "variable because of other evicted variables."),
125 cl::init(false));
126
127 // FIXME: Find a good default for this flag and remove the flag.
128 static cl::opt<unsigned>
129 CSRFirstTimeCost("regalloc-csr-first-time-cost",
130 cl::desc("Cost for first time use of callee-saved register."),
131 cl::init(0), cl::Hidden);
132
133 static cl::opt<bool> ConsiderLocalIntervalCost(
134 "consider-local-interval-cost", cl::Hidden,
135 cl::desc("Consider the cost of local intervals created by a split "
136 "candidate when choosing the best split candidate."),
137 cl::init(false));
138
139 static RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator",
140 createGreedyRegisterAllocator);
141
142 namespace {
143
144 class RAGreedy : public MachineFunctionPass,
145 public RegAllocBase,
146 private LiveRangeEdit::Delegate {
147 // Convenient shortcuts.
148 using PQueue = std::priority_queue<std::pair<unsigned, unsigned>>;
149 using SmallLISet = SmallPtrSet<LiveInterval *, 4>;
150 using SmallVirtRegSet = SmallSet<Register, 16>;
151
152 // context
153 MachineFunction *MF;
154
155 // Shortcuts to some useful interface.
156 const TargetInstrInfo *TII;
157 const TargetRegisterInfo *TRI;
158 RegisterClassInfo RCI;
159
160 // analyses
161 SlotIndexes *Indexes;
162 MachineBlockFrequencyInfo *MBFI;
163 MachineDominatorTree *DomTree;
164 MachineLoopInfo *Loops;
165 MachineOptimizationRemarkEmitter *ORE;
166 EdgeBundles *Bundles;
167 SpillPlacement *SpillPlacer;
168 LiveDebugVariables *DebugVars;
169 AliasAnalysis *AA;
170
171 // state
172 std::unique_ptr<Spiller> SpillerInstance;
173 PQueue Queue;
174 unsigned NextCascade;
175 std::unique_ptr<VirtRegAuxInfo> VRAI;
176
177 // Live ranges pass through a number of stages as we try to allocate them.
178 // Some of the stages may also create new live ranges:
179 //
180 // - Region splitting.
181 // - Per-block splitting.
182 // - Local splitting.
183 // - Spilling.
184 //
185 // Ranges produced by one of the stages skip the previous stages when they are
186 // dequeued. This improves performance because we can skip interference checks
187 // that are unlikely to give any results. It also guarantees that the live
188 // range splitting algorithm terminates, something that is otherwise hard to
189 // ensure.
190 enum LiveRangeStage {
191 /// Newly created live range that has never been queued.
192 RS_New,
193
194 /// Only attempt assignment and eviction. Then requeue as RS_Split.
195 RS_Assign,
196
197 /// Attempt live range splitting if assignment is impossible.
198 RS_Split,
199
200 /// Attempt more aggressive live range splitting that is guaranteed to make
201 /// progress. This is used for split products that may not be making
202 /// progress.
203 RS_Split2,
204
205 /// Live range will be spilled. No more splitting will be attempted.
206 RS_Spill,
207
208
209 /// Live range is in memory. Because of other evictions, it might get moved
210 /// in a register in the end.
211 RS_Memory,
212
213 /// There is nothing more we can do to this live range. Abort compilation
214 /// if it can't be assigned.
215 RS_Done
216 };
217
218 // Enum CutOffStage to keep a track whether the register allocation failed
219 // because of the cutoffs encountered in last chance recoloring.
220 // Note: This is used as bitmask. New value should be next power of 2.
221 enum CutOffStage {
222 // No cutoffs encountered
223 CO_None = 0,
224
225 // lcr-max-depth cutoff encountered
226 CO_Depth = 1,
227
228 // lcr-max-interf cutoff encountered
229 CO_Interf = 2
230 };
231
232 uint8_t CutOffInfo;
233
234 #ifndef NDEBUG
235 static const char *const StageName[];
236 #endif
237
238 // RegInfo - Keep additional information about each live range.
239 struct RegInfo {
240 LiveRangeStage Stage = RS_New;
241
242 // Cascade - Eviction loop prevention. See canEvictInterference().
243 unsigned Cascade = 0;
244
245 RegInfo() = default;
246 };
247
248 IndexedMap<RegInfo, VirtReg2IndexFunctor> ExtraRegInfo;
249
getStage(const LiveInterval & VirtReg) const250 LiveRangeStage getStage(const LiveInterval &VirtReg) const {
251 return ExtraRegInfo[VirtReg.reg()].Stage;
252 }
253
setStage(const LiveInterval & VirtReg,LiveRangeStage Stage)254 void setStage(const LiveInterval &VirtReg, LiveRangeStage Stage) {
255 ExtraRegInfo.resize(MRI->getNumVirtRegs());
256 ExtraRegInfo[VirtReg.reg()].Stage = Stage;
257 }
258
259 template<typename Iterator>
setStage(Iterator Begin,Iterator End,LiveRangeStage NewStage)260 void setStage(Iterator Begin, Iterator End, LiveRangeStage NewStage) {
261 ExtraRegInfo.resize(MRI->getNumVirtRegs());
262 for (;Begin != End; ++Begin) {
263 Register Reg = *Begin;
264 if (ExtraRegInfo[Reg].Stage == RS_New)
265 ExtraRegInfo[Reg].Stage = NewStage;
266 }
267 }
268
269 /// Cost of evicting interference.
270 struct EvictionCost {
271 unsigned BrokenHints = 0; ///< Total number of broken hints.
272 float MaxWeight = 0; ///< Maximum spill weight evicted.
273
274 EvictionCost() = default;
275
isMax__anone112ced50111::RAGreedy::EvictionCost276 bool isMax() const { return BrokenHints == ~0u; }
277
setMax__anone112ced50111::RAGreedy::EvictionCost278 void setMax() { BrokenHints = ~0u; }
279
setBrokenHints__anone112ced50111::RAGreedy::EvictionCost280 void setBrokenHints(unsigned NHints) { BrokenHints = NHints; }
281
operator <__anone112ced50111::RAGreedy::EvictionCost282 bool operator<(const EvictionCost &O) const {
283 return std::tie(BrokenHints, MaxWeight) <
284 std::tie(O.BrokenHints, O.MaxWeight);
285 }
286 };
287
288 /// EvictionTrack - Keeps track of past evictions in order to optimize region
289 /// split decision.
290 class EvictionTrack {
291
292 public:
293 using EvictorInfo =
294 std::pair<Register /* evictor */, MCRegister /* physreg */>;
295 using EvicteeInfo = llvm::DenseMap<Register /* evictee */, EvictorInfo>;
296
297 private:
298 /// Each Vreg that has been evicted in the last stage of selectOrSplit will
299 /// be mapped to the evictor Vreg and the PhysReg it was evicted from.
300 EvicteeInfo Evictees;
301
302 public:
303 /// Clear all eviction information.
clear()304 void clear() { Evictees.clear(); }
305
306 /// Clear eviction information for the given evictee Vreg.
307 /// E.g. when Vreg get's a new allocation, the old eviction info is no
308 /// longer relevant.
309 /// \param Evictee The evictee Vreg for whom we want to clear collected
310 /// eviction info.
clearEvicteeInfo(Register Evictee)311 void clearEvicteeInfo(Register Evictee) { Evictees.erase(Evictee); }
312
313 /// Track new eviction.
314 /// The Evictor vreg has evicted the Evictee vreg from Physreg.
315 /// \param PhysReg The physical register Evictee was evicted from.
316 /// \param Evictor The evictor Vreg that evicted Evictee.
317 /// \param Evictee The evictee Vreg.
addEviction(MCRegister PhysReg,Register Evictor,Register Evictee)318 void addEviction(MCRegister PhysReg, Register Evictor, Register Evictee) {
319 Evictees[Evictee].first = Evictor;
320 Evictees[Evictee].second = PhysReg;
321 }
322
323 /// Return the Evictor Vreg which evicted Evictee Vreg from PhysReg.
324 /// \param Evictee The evictee vreg.
325 /// \return The Evictor vreg which evicted Evictee vreg from PhysReg. 0 if
326 /// nobody has evicted Evictee from PhysReg.
getEvictor(Register Evictee)327 EvictorInfo getEvictor(Register Evictee) {
328 if (Evictees.count(Evictee)) {
329 return Evictees[Evictee];
330 }
331
332 return EvictorInfo(0, 0);
333 }
334 };
335
336 // Keeps track of past evictions in order to optimize region split decision.
337 EvictionTrack LastEvicted;
338
339 // splitting state.
340 std::unique_ptr<SplitAnalysis> SA;
341 std::unique_ptr<SplitEditor> SE;
342
343 /// Cached per-block interference maps
344 InterferenceCache IntfCache;
345
346 /// All basic blocks where the current register has uses.
347 SmallVector<SpillPlacement::BlockConstraint, 8> SplitConstraints;
348
349 /// Global live range splitting candidate info.
350 struct GlobalSplitCandidate {
351 // Register intended for assignment, or 0.
352 MCRegister PhysReg;
353
354 // SplitKit interval index for this candidate.
355 unsigned IntvIdx;
356
357 // Interference for PhysReg.
358 InterferenceCache::Cursor Intf;
359
360 // Bundles where this candidate should be live.
361 BitVector LiveBundles;
362 SmallVector<unsigned, 8> ActiveBlocks;
363
reset__anone112ced50111::RAGreedy::GlobalSplitCandidate364 void reset(InterferenceCache &Cache, MCRegister Reg) {
365 PhysReg = Reg;
366 IntvIdx = 0;
367 Intf.setPhysReg(Cache, Reg);
368 LiveBundles.clear();
369 ActiveBlocks.clear();
370 }
371
372 // Set B[I] = C for every live bundle where B[I] was NoCand.
getBundles__anone112ced50111::RAGreedy::GlobalSplitCandidate373 unsigned getBundles(SmallVectorImpl<unsigned> &B, unsigned C) {
374 unsigned Count = 0;
375 for (unsigned I : LiveBundles.set_bits())
376 if (B[I] == NoCand) {
377 B[I] = C;
378 Count++;
379 }
380 return Count;
381 }
382 };
383
384 /// Candidate info for each PhysReg in AllocationOrder.
385 /// This vector never shrinks, but grows to the size of the largest register
386 /// class.
387 SmallVector<GlobalSplitCandidate, 32> GlobalCand;
388
389 enum : unsigned { NoCand = ~0u };
390
391 /// Candidate map. Each edge bundle is assigned to a GlobalCand entry, or to
392 /// NoCand which indicates the stack interval.
393 SmallVector<unsigned, 32> BundleCand;
394
395 /// Callee-save register cost, calculated once per machine function.
396 BlockFrequency CSRCost;
397
398 /// Run or not the local reassignment heuristic. This information is
399 /// obtained from the TargetSubtargetInfo.
400 bool EnableLocalReassign;
401
402 /// Enable or not the consideration of the cost of local intervals created
403 /// by a split candidate when choosing the best split candidate.
404 bool EnableAdvancedRASplitCost;
405
406 /// Set of broken hints that may be reconciled later because of eviction.
407 SmallSetVector<LiveInterval *, 8> SetOfBrokenHints;
408
409 public:
410 RAGreedy();
411
412 /// Return the pass name.
getPassName() const413 StringRef getPassName() const override { return "Greedy Register Allocator"; }
414
415 /// RAGreedy analysis usage.
416 void getAnalysisUsage(AnalysisUsage &AU) const override;
417 void releaseMemory() override;
spiller()418 Spiller &spiller() override { return *SpillerInstance; }
419 void enqueue(LiveInterval *LI) override;
420 LiveInterval *dequeue() override;
421 MCRegister selectOrSplit(LiveInterval &,
422 SmallVectorImpl<Register> &) override;
423 void aboutToRemoveInterval(LiveInterval &) override;
424
425 /// Perform register allocation.
426 bool runOnMachineFunction(MachineFunction &mf) override;
427
getRequiredProperties() const428 MachineFunctionProperties getRequiredProperties() const override {
429 return MachineFunctionProperties().set(
430 MachineFunctionProperties::Property::NoPHIs);
431 }
432
getClearedProperties() const433 MachineFunctionProperties getClearedProperties() const override {
434 return MachineFunctionProperties().set(
435 MachineFunctionProperties::Property::IsSSA);
436 }
437
438 static char ID;
439
440 private:
441 MCRegister selectOrSplitImpl(LiveInterval &, SmallVectorImpl<Register> &,
442 SmallVirtRegSet &, unsigned = 0);
443
444 bool LRE_CanEraseVirtReg(Register) override;
445 void LRE_WillShrinkVirtReg(Register) override;
446 void LRE_DidCloneVirtReg(Register, Register) override;
447 void enqueue(PQueue &CurQueue, LiveInterval *LI);
448 LiveInterval *dequeue(PQueue &CurQueue);
449
450 BlockFrequency calcSpillCost();
451 bool addSplitConstraints(InterferenceCache::Cursor, BlockFrequency&);
452 bool addThroughConstraints(InterferenceCache::Cursor, ArrayRef<unsigned>);
453 bool growRegion(GlobalSplitCandidate &Cand);
454 bool splitCanCauseEvictionChain(Register Evictee, GlobalSplitCandidate &Cand,
455 unsigned BBNumber,
456 const AllocationOrder &Order);
457 bool splitCanCauseLocalSpill(unsigned VirtRegToSplit,
458 GlobalSplitCandidate &Cand, unsigned BBNumber,
459 const AllocationOrder &Order);
460 BlockFrequency calcGlobalSplitCost(GlobalSplitCandidate &,
461 const AllocationOrder &Order,
462 bool *CanCauseEvictionChain);
463 bool calcCompactRegion(GlobalSplitCandidate&);
464 void splitAroundRegion(LiveRangeEdit&, ArrayRef<unsigned>);
465 void calcGapWeights(MCRegister, SmallVectorImpl<float> &);
466 Register canReassign(LiveInterval &VirtReg, Register PrevReg);
467 bool shouldEvict(LiveInterval &A, bool, LiveInterval &B, bool);
468 bool canEvictInterference(LiveInterval &, MCRegister, bool, EvictionCost &,
469 const SmallVirtRegSet &);
470 bool canEvictInterferenceInRange(LiveInterval &VirtReg, MCRegister PhysReg,
471 SlotIndex Start, SlotIndex End,
472 EvictionCost &MaxCost);
473 MCRegister getCheapestEvicteeWeight(const AllocationOrder &Order,
474 LiveInterval &VirtReg, SlotIndex Start,
475 SlotIndex End, float *BestEvictWeight);
476 void evictInterference(LiveInterval &, MCRegister,
477 SmallVectorImpl<Register> &);
478 bool mayRecolorAllInterferences(MCRegister PhysReg, LiveInterval &VirtReg,
479 SmallLISet &RecoloringCandidates,
480 const SmallVirtRegSet &FixedRegisters);
481
482 Register tryAssign(LiveInterval&, AllocationOrder&,
483 SmallVectorImpl<Register>&,
484 const SmallVirtRegSet&);
485 unsigned tryEvict(LiveInterval&, AllocationOrder&,
486 SmallVectorImpl<Register>&, unsigned,
487 const SmallVirtRegSet&);
488 MCRegister tryRegionSplit(LiveInterval &, AllocationOrder &,
489 SmallVectorImpl<Register> &);
490 /// Calculate cost of region splitting.
491 unsigned calculateRegionSplitCost(LiveInterval &VirtReg,
492 AllocationOrder &Order,
493 BlockFrequency &BestCost,
494 unsigned &NumCands, bool IgnoreCSR,
495 bool *CanCauseEvictionChain = nullptr);
496 /// Perform region splitting.
497 unsigned doRegionSplit(LiveInterval &VirtReg, unsigned BestCand,
498 bool HasCompact,
499 SmallVectorImpl<Register> &NewVRegs);
500 /// Check other options before using a callee-saved register for the first
501 /// time.
502 MCRegister tryAssignCSRFirstTime(LiveInterval &VirtReg,
503 AllocationOrder &Order, MCRegister PhysReg,
504 unsigned &CostPerUseLimit,
505 SmallVectorImpl<Register> &NewVRegs);
506 void initializeCSRCost();
507 unsigned tryBlockSplit(LiveInterval&, AllocationOrder&,
508 SmallVectorImpl<Register>&);
509 unsigned tryInstructionSplit(LiveInterval&, AllocationOrder&,
510 SmallVectorImpl<Register>&);
511 unsigned tryLocalSplit(LiveInterval&, AllocationOrder&,
512 SmallVectorImpl<Register>&);
513 unsigned trySplit(LiveInterval&, AllocationOrder&,
514 SmallVectorImpl<Register>&,
515 const SmallVirtRegSet&);
516 unsigned tryLastChanceRecoloring(LiveInterval &, AllocationOrder &,
517 SmallVectorImpl<Register> &,
518 SmallVirtRegSet &, unsigned);
519 bool tryRecoloringCandidates(PQueue &, SmallVectorImpl<Register> &,
520 SmallVirtRegSet &, unsigned);
521 void tryHintRecoloring(LiveInterval &);
522 void tryHintsRecoloring();
523
524 /// Model the information carried by one end of a copy.
525 struct HintInfo {
526 /// The frequency of the copy.
527 BlockFrequency Freq;
528 /// The virtual register or physical register.
529 Register Reg;
530 /// Its currently assigned register.
531 /// In case of a physical register Reg == PhysReg.
532 MCRegister PhysReg;
533
HintInfo__anone112ced50111::RAGreedy::HintInfo534 HintInfo(BlockFrequency Freq, Register Reg, MCRegister PhysReg)
535 : Freq(Freq), Reg(Reg), PhysReg(PhysReg) {}
536 };
537 using HintsInfo = SmallVector<HintInfo, 4>;
538
539 BlockFrequency getBrokenHintFreq(const HintsInfo &, MCRegister);
540 void collectHintInfo(Register, HintsInfo &);
541
542 bool isUnusedCalleeSavedReg(MCRegister PhysReg) const;
543
544 /// Compute and report the number of spills and reloads for a loop.
545 void reportNumberOfSplillsReloads(MachineLoop *L, unsigned &Reloads,
546 unsigned &FoldedReloads, unsigned &Spills,
547 unsigned &FoldedSpills);
548
549 /// Report the number of spills and reloads for each loop.
reportNumberOfSplillsReloads()550 void reportNumberOfSplillsReloads() {
551 for (MachineLoop *L : *Loops) {
552 unsigned Reloads, FoldedReloads, Spills, FoldedSpills;
553 reportNumberOfSplillsReloads(L, Reloads, FoldedReloads, Spills,
554 FoldedSpills);
555 }
556 }
557 };
558
559 } // end anonymous namespace
560
561 char RAGreedy::ID = 0;
562 char &llvm::RAGreedyID = RAGreedy::ID;
563
564 INITIALIZE_PASS_BEGIN(RAGreedy, "greedy",
565 "Greedy Register Allocator", false, false)
566 INITIALIZE_PASS_DEPENDENCY(LiveDebugVariables)
567 INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
568 INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
569 INITIALIZE_PASS_DEPENDENCY(RegisterCoalescer)
570 INITIALIZE_PASS_DEPENDENCY(MachineScheduler)
571 INITIALIZE_PASS_DEPENDENCY(LiveStacks)
572 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
573 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
574 INITIALIZE_PASS_DEPENDENCY(VirtRegMap)
575 INITIALIZE_PASS_DEPENDENCY(LiveRegMatrix)
576 INITIALIZE_PASS_DEPENDENCY(EdgeBundles)
577 INITIALIZE_PASS_DEPENDENCY(SpillPlacement)
578 INITIALIZE_PASS_DEPENDENCY(MachineOptimizationRemarkEmitterPass)
579 INITIALIZE_PASS_END(RAGreedy, "greedy",
580 "Greedy Register Allocator", false, false)
581
582 #ifndef NDEBUG
583 const char *const RAGreedy::StageName[] = {
584 "RS_New",
585 "RS_Assign",
586 "RS_Split",
587 "RS_Split2",
588 "RS_Spill",
589 "RS_Memory",
590 "RS_Done"
591 };
592 #endif
593
594 // Hysteresis to use when comparing floats.
595 // This helps stabilize decisions based on float comparisons.
596 const float Hysteresis = (2007 / 2048.0f); // 0.97998046875
597
createGreedyRegisterAllocator()598 FunctionPass* llvm::createGreedyRegisterAllocator() {
599 return new RAGreedy();
600 }
601
RAGreedy()602 RAGreedy::RAGreedy(): MachineFunctionPass(ID) {
603 }
604
getAnalysisUsage(AnalysisUsage & AU) const605 void RAGreedy::getAnalysisUsage(AnalysisUsage &AU) const {
606 AU.setPreservesCFG();
607 AU.addRequired<MachineBlockFrequencyInfo>();
608 AU.addPreserved<MachineBlockFrequencyInfo>();
609 AU.addRequired<AAResultsWrapperPass>();
610 AU.addPreserved<AAResultsWrapperPass>();
611 AU.addRequired<LiveIntervals>();
612 AU.addPreserved<LiveIntervals>();
613 AU.addRequired<SlotIndexes>();
614 AU.addPreserved<SlotIndexes>();
615 AU.addRequired<LiveDebugVariables>();
616 AU.addPreserved<LiveDebugVariables>();
617 AU.addRequired<LiveStacks>();
618 AU.addPreserved<LiveStacks>();
619 AU.addRequired<MachineDominatorTree>();
620 AU.addPreserved<MachineDominatorTree>();
621 AU.addRequired<MachineLoopInfo>();
622 AU.addPreserved<MachineLoopInfo>();
623 AU.addRequired<VirtRegMap>();
624 AU.addPreserved<VirtRegMap>();
625 AU.addRequired<LiveRegMatrix>();
626 AU.addPreserved<LiveRegMatrix>();
627 AU.addRequired<EdgeBundles>();
628 AU.addRequired<SpillPlacement>();
629 AU.addRequired<MachineOptimizationRemarkEmitterPass>();
630 MachineFunctionPass::getAnalysisUsage(AU);
631 }
632
633 //===----------------------------------------------------------------------===//
634 // LiveRangeEdit delegate methods
635 //===----------------------------------------------------------------------===//
636
LRE_CanEraseVirtReg(Register VirtReg)637 bool RAGreedy::LRE_CanEraseVirtReg(Register VirtReg) {
638 LiveInterval &LI = LIS->getInterval(VirtReg);
639 if (VRM->hasPhys(VirtReg)) {
640 Matrix->unassign(LI);
641 aboutToRemoveInterval(LI);
642 return true;
643 }
644 // Unassigned virtreg is probably in the priority queue.
645 // RegAllocBase will erase it after dequeueing.
646 // Nonetheless, clear the live-range so that the debug
647 // dump will show the right state for that VirtReg.
648 LI.clear();
649 return false;
650 }
651
LRE_WillShrinkVirtReg(Register VirtReg)652 void RAGreedy::LRE_WillShrinkVirtReg(Register VirtReg) {
653 if (!VRM->hasPhys(VirtReg))
654 return;
655
656 // Register is assigned, put it back on the queue for reassignment.
657 LiveInterval &LI = LIS->getInterval(VirtReg);
658 Matrix->unassign(LI);
659 enqueue(&LI);
660 }
661
LRE_DidCloneVirtReg(Register New,Register Old)662 void RAGreedy::LRE_DidCloneVirtReg(Register New, Register Old) {
663 // Cloning a register we haven't even heard about yet? Just ignore it.
664 if (!ExtraRegInfo.inBounds(Old))
665 return;
666
667 // LRE may clone a virtual register because dead code elimination causes it to
668 // be split into connected components. The new components are much smaller
669 // than the original, so they should get a new chance at being assigned.
670 // same stage as the parent.
671 ExtraRegInfo[Old].Stage = RS_Assign;
672 ExtraRegInfo.grow(New);
673 ExtraRegInfo[New] = ExtraRegInfo[Old];
674 }
675
releaseMemory()676 void RAGreedy::releaseMemory() {
677 SpillerInstance.reset();
678 ExtraRegInfo.clear();
679 GlobalCand.clear();
680 }
681
enqueue(LiveInterval * LI)682 void RAGreedy::enqueue(LiveInterval *LI) { enqueue(Queue, LI); }
683
enqueue(PQueue & CurQueue,LiveInterval * LI)684 void RAGreedy::enqueue(PQueue &CurQueue, LiveInterval *LI) {
685 // Prioritize live ranges by size, assigning larger ranges first.
686 // The queue holds (size, reg) pairs.
687 const unsigned Size = LI->getSize();
688 const Register Reg = LI->reg();
689 assert(Reg.isVirtual() && "Can only enqueue virtual registers");
690 unsigned Prio;
691
692 ExtraRegInfo.grow(Reg);
693 if (ExtraRegInfo[Reg].Stage == RS_New)
694 ExtraRegInfo[Reg].Stage = RS_Assign;
695
696 if (ExtraRegInfo[Reg].Stage == RS_Split) {
697 // Unsplit ranges that couldn't be allocated immediately are deferred until
698 // everything else has been allocated.
699 Prio = Size;
700 } else if (ExtraRegInfo[Reg].Stage == RS_Memory) {
701 // Memory operand should be considered last.
702 // Change the priority such that Memory operand are assigned in
703 // the reverse order that they came in.
704 // TODO: Make this a member variable and probably do something about hints.
705 static unsigned MemOp = 0;
706 Prio = MemOp++;
707 } else {
708 // Giant live ranges fall back to the global assignment heuristic, which
709 // prevents excessive spilling in pathological cases.
710 bool ReverseLocal = TRI->reverseLocalAssignment();
711 const TargetRegisterClass &RC = *MRI->getRegClass(Reg);
712 bool ForceGlobal = !ReverseLocal &&
713 (Size / SlotIndex::InstrDist) > (2 * RC.getNumRegs());
714
715 if (ExtraRegInfo[Reg].Stage == RS_Assign && !ForceGlobal && !LI->empty() &&
716 LIS->intervalIsInOneMBB(*LI)) {
717 // Allocate original local ranges in linear instruction order. Since they
718 // are singly defined, this produces optimal coloring in the absence of
719 // global interference and other constraints.
720 if (!ReverseLocal)
721 Prio = LI->beginIndex().getInstrDistance(Indexes->getLastIndex());
722 else {
723 // Allocating bottom up may allow many short LRGs to be assigned first
724 // to one of the cheap registers. This could be much faster for very
725 // large blocks on targets with many physical registers.
726 Prio = Indexes->getZeroIndex().getInstrDistance(LI->endIndex());
727 }
728 Prio |= RC.AllocationPriority << 24;
729 } else {
730 // Allocate global and split ranges in long->short order. Long ranges that
731 // don't fit should be spilled (or split) ASAP so they don't create
732 // interference. Mark a bit to prioritize global above local ranges.
733 Prio = (1u << 29) + Size;
734 }
735 // Mark a higher bit to prioritize global and local above RS_Split.
736 Prio |= (1u << 31);
737
738 // Boost ranges that have a physical register hint.
739 if (VRM->hasKnownPreference(Reg))
740 Prio |= (1u << 30);
741 }
742 // The virtual register number is a tie breaker for same-sized ranges.
743 // Give lower vreg numbers higher priority to assign them first.
744 CurQueue.push(std::make_pair(Prio, ~Reg));
745 }
746
dequeue()747 LiveInterval *RAGreedy::dequeue() { return dequeue(Queue); }
748
dequeue(PQueue & CurQueue)749 LiveInterval *RAGreedy::dequeue(PQueue &CurQueue) {
750 if (CurQueue.empty())
751 return nullptr;
752 LiveInterval *LI = &LIS->getInterval(~CurQueue.top().second);
753 CurQueue.pop();
754 return LI;
755 }
756
757 //===----------------------------------------------------------------------===//
758 // Direct Assignment
759 //===----------------------------------------------------------------------===//
760
761 /// tryAssign - Try to assign VirtReg to an available register.
tryAssign(LiveInterval & VirtReg,AllocationOrder & Order,SmallVectorImpl<Register> & NewVRegs,const SmallVirtRegSet & FixedRegisters)762 Register RAGreedy::tryAssign(LiveInterval &VirtReg,
763 AllocationOrder &Order,
764 SmallVectorImpl<Register> &NewVRegs,
765 const SmallVirtRegSet &FixedRegisters) {
766 Register PhysReg;
767 for (auto I = Order.begin(), E = Order.end(); I != E && !PhysReg; ++I) {
768 assert(*I);
769 if (!Matrix->checkInterference(VirtReg, *I)) {
770 if (I.isHint())
771 return *I;
772 else
773 PhysReg = *I;
774 }
775 }
776 if (!PhysReg.isValid())
777 return PhysReg;
778
779 // PhysReg is available, but there may be a better choice.
780
781 // If we missed a simple hint, try to cheaply evict interference from the
782 // preferred register.
783 if (Register Hint = MRI->getSimpleHint(VirtReg.reg()))
784 if (Order.isHint(Hint)) {
785 MCRegister PhysHint = Hint.asMCReg();
786 LLVM_DEBUG(dbgs() << "missed hint " << printReg(PhysHint, TRI) << '\n');
787 EvictionCost MaxCost;
788 MaxCost.setBrokenHints(1);
789 if (canEvictInterference(VirtReg, PhysHint, true, MaxCost,
790 FixedRegisters)) {
791 evictInterference(VirtReg, PhysHint, NewVRegs);
792 return PhysHint;
793 }
794 // Record the missed hint, we may be able to recover
795 // at the end if the surrounding allocation changed.
796 SetOfBrokenHints.insert(&VirtReg);
797 }
798
799 // Try to evict interference from a cheaper alternative.
800 unsigned Cost = TRI->getCostPerUse(PhysReg);
801
802 // Most registers have 0 additional cost.
803 if (!Cost)
804 return PhysReg;
805
806 LLVM_DEBUG(dbgs() << printReg(PhysReg, TRI) << " is available at cost "
807 << Cost << '\n');
808 Register CheapReg = tryEvict(VirtReg, Order, NewVRegs, Cost, FixedRegisters);
809 return CheapReg ? CheapReg : PhysReg;
810 }
811
812 //===----------------------------------------------------------------------===//
813 // Interference eviction
814 //===----------------------------------------------------------------------===//
815
canReassign(LiveInterval & VirtReg,Register PrevReg)816 Register RAGreedy::canReassign(LiveInterval &VirtReg, Register PrevReg) {
817 auto Order =
818 AllocationOrder::create(VirtReg.reg(), *VRM, RegClassInfo, Matrix);
819 MCRegister PhysReg;
820 for (auto I = Order.begin(), E = Order.end(); I != E && !PhysReg; ++I) {
821 if ((*I).id() == PrevReg.id())
822 continue;
823
824 MCRegUnitIterator Units(*I, TRI);
825 for (; Units.isValid(); ++Units) {
826 // Instantiate a "subquery", not to be confused with the Queries array.
827 LiveIntervalUnion::Query subQ(VirtReg, Matrix->getLiveUnions()[*Units]);
828 if (subQ.checkInterference())
829 break;
830 }
831 // If no units have interference, break out with the current PhysReg.
832 if (!Units.isValid())
833 PhysReg = *I;
834 }
835 if (PhysReg)
836 LLVM_DEBUG(dbgs() << "can reassign: " << VirtReg << " from "
837 << printReg(PrevReg, TRI) << " to "
838 << printReg(PhysReg, TRI) << '\n');
839 return PhysReg;
840 }
841
842 /// shouldEvict - determine if A should evict the assigned live range B. The
843 /// eviction policy defined by this function together with the allocation order
844 /// defined by enqueue() decides which registers ultimately end up being split
845 /// and spilled.
846 ///
847 /// Cascade numbers are used to prevent infinite loops if this function is a
848 /// cyclic relation.
849 ///
850 /// @param A The live range to be assigned.
851 /// @param IsHint True when A is about to be assigned to its preferred
852 /// register.
853 /// @param B The live range to be evicted.
854 /// @param BreaksHint True when B is already assigned to its preferred register.
shouldEvict(LiveInterval & A,bool IsHint,LiveInterval & B,bool BreaksHint)855 bool RAGreedy::shouldEvict(LiveInterval &A, bool IsHint,
856 LiveInterval &B, bool BreaksHint) {
857 bool CanSplit = getStage(B) < RS_Spill;
858
859 // Be fairly aggressive about following hints as long as the evictee can be
860 // split.
861 if (CanSplit && IsHint && !BreaksHint)
862 return true;
863
864 if (A.weight() > B.weight()) {
865 LLVM_DEBUG(dbgs() << "should evict: " << B << " w= " << B.weight() << '\n');
866 return true;
867 }
868 return false;
869 }
870
871 /// canEvictInterference - Return true if all interferences between VirtReg and
872 /// PhysReg can be evicted.
873 ///
874 /// @param VirtReg Live range that is about to be assigned.
875 /// @param PhysReg Desired register for assignment.
876 /// @param IsHint True when PhysReg is VirtReg's preferred register.
877 /// @param MaxCost Only look for cheaper candidates and update with new cost
878 /// when returning true.
879 /// @returns True when interference can be evicted cheaper than MaxCost.
canEvictInterference(LiveInterval & VirtReg,MCRegister PhysReg,bool IsHint,EvictionCost & MaxCost,const SmallVirtRegSet & FixedRegisters)880 bool RAGreedy::canEvictInterference(LiveInterval &VirtReg, MCRegister PhysReg,
881 bool IsHint, EvictionCost &MaxCost,
882 const SmallVirtRegSet &FixedRegisters) {
883 // It is only possible to evict virtual register interference.
884 if (Matrix->checkInterference(VirtReg, PhysReg) > LiveRegMatrix::IK_VirtReg)
885 return false;
886
887 bool IsLocal = LIS->intervalIsInOneMBB(VirtReg);
888
889 // Find VirtReg's cascade number. This will be unassigned if VirtReg was never
890 // involved in an eviction before. If a cascade number was assigned, deny
891 // evicting anything with the same or a newer cascade number. This prevents
892 // infinite eviction loops.
893 //
894 // This works out so a register without a cascade number is allowed to evict
895 // anything, and it can be evicted by anything.
896 unsigned Cascade = ExtraRegInfo[VirtReg.reg()].Cascade;
897 if (!Cascade)
898 Cascade = NextCascade;
899
900 EvictionCost Cost;
901 for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
902 LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units);
903 // If there is 10 or more interferences, chances are one is heavier.
904 if (Q.collectInterferingVRegs(10) >= 10)
905 return false;
906
907 // Check if any interfering live range is heavier than MaxWeight.
908 for (LiveInterval *Intf : reverse(Q.interferingVRegs())) {
909 assert(Register::isVirtualRegister(Intf->reg()) &&
910 "Only expecting virtual register interference from query");
911
912 // Do not allow eviction of a virtual register if we are in the middle
913 // of last-chance recoloring and this virtual register is one that we
914 // have scavenged a physical register for.
915 if (FixedRegisters.count(Intf->reg()))
916 return false;
917
918 // Never evict spill products. They cannot split or spill.
919 if (getStage(*Intf) == RS_Done)
920 return false;
921 // Once a live range becomes small enough, it is urgent that we find a
922 // register for it. This is indicated by an infinite spill weight. These
923 // urgent live ranges get to evict almost anything.
924 //
925 // Also allow urgent evictions of unspillable ranges from a strictly
926 // larger allocation order.
927 bool Urgent =
928 !VirtReg.isSpillable() &&
929 (Intf->isSpillable() ||
930 RegClassInfo.getNumAllocatableRegs(MRI->getRegClass(VirtReg.reg())) <
931 RegClassInfo.getNumAllocatableRegs(
932 MRI->getRegClass(Intf->reg())));
933 // Only evict older cascades or live ranges without a cascade.
934 unsigned IntfCascade = ExtraRegInfo[Intf->reg()].Cascade;
935 if (Cascade <= IntfCascade) {
936 if (!Urgent)
937 return false;
938 // We permit breaking cascades for urgent evictions. It should be the
939 // last resort, though, so make it really expensive.
940 Cost.BrokenHints += 10;
941 }
942 // Would this break a satisfied hint?
943 bool BreaksHint = VRM->hasPreferredPhys(Intf->reg());
944 // Update eviction cost.
945 Cost.BrokenHints += BreaksHint;
946 Cost.MaxWeight = std::max(Cost.MaxWeight, Intf->weight());
947 // Abort if this would be too expensive.
948 if (!(Cost < MaxCost))
949 return false;
950 if (Urgent)
951 continue;
952 // Apply the eviction policy for non-urgent evictions.
953 if (!shouldEvict(VirtReg, IsHint, *Intf, BreaksHint))
954 return false;
955 // If !MaxCost.isMax(), then we're just looking for a cheap register.
956 // Evicting another local live range in this case could lead to suboptimal
957 // coloring.
958 if (!MaxCost.isMax() && IsLocal && LIS->intervalIsInOneMBB(*Intf) &&
959 (!EnableLocalReassign || !canReassign(*Intf, PhysReg))) {
960 return false;
961 }
962 }
963 }
964 MaxCost = Cost;
965 return true;
966 }
967
968 /// Return true if all interferences between VirtReg and PhysReg between
969 /// Start and End can be evicted.
970 ///
971 /// \param VirtReg Live range that is about to be assigned.
972 /// \param PhysReg Desired register for assignment.
973 /// \param Start Start of range to look for interferences.
974 /// \param End End of range to look for interferences.
975 /// \param MaxCost Only look for cheaper candidates and update with new cost
976 /// when returning true.
977 /// \return True when interference can be evicted cheaper than MaxCost.
canEvictInterferenceInRange(LiveInterval & VirtReg,MCRegister PhysReg,SlotIndex Start,SlotIndex End,EvictionCost & MaxCost)978 bool RAGreedy::canEvictInterferenceInRange(LiveInterval &VirtReg,
979 MCRegister PhysReg, SlotIndex Start,
980 SlotIndex End,
981 EvictionCost &MaxCost) {
982 EvictionCost Cost;
983
984 for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
985 LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units);
986
987 // Check if any interfering live range is heavier than MaxWeight.
988 for (const LiveInterval *Intf : reverse(Q.interferingVRegs())) {
989 // Check if interference overlast the segment in interest.
990 if (!Intf->overlaps(Start, End))
991 continue;
992
993 // Cannot evict non virtual reg interference.
994 if (!Register::isVirtualRegister(Intf->reg()))
995 return false;
996 // Never evict spill products. They cannot split or spill.
997 if (getStage(*Intf) == RS_Done)
998 return false;
999
1000 // Would this break a satisfied hint?
1001 bool BreaksHint = VRM->hasPreferredPhys(Intf->reg());
1002 // Update eviction cost.
1003 Cost.BrokenHints += BreaksHint;
1004 Cost.MaxWeight = std::max(Cost.MaxWeight, Intf->weight());
1005 // Abort if this would be too expensive.
1006 if (!(Cost < MaxCost))
1007 return false;
1008 }
1009 }
1010
1011 if (Cost.MaxWeight == 0)
1012 return false;
1013
1014 MaxCost = Cost;
1015 return true;
1016 }
1017
1018 /// Return the physical register that will be best
1019 /// candidate for eviction by a local split interval that will be created
1020 /// between Start and End.
1021 ///
1022 /// \param Order The allocation order
1023 /// \param VirtReg Live range that is about to be assigned.
1024 /// \param Start Start of range to look for interferences
1025 /// \param End End of range to look for interferences
1026 /// \param BestEvictweight The eviction cost of that eviction
1027 /// \return The PhysReg which is the best candidate for eviction and the
1028 /// eviction cost in BestEvictweight
getCheapestEvicteeWeight(const AllocationOrder & Order,LiveInterval & VirtReg,SlotIndex Start,SlotIndex End,float * BestEvictweight)1029 MCRegister RAGreedy::getCheapestEvicteeWeight(const AllocationOrder &Order,
1030 LiveInterval &VirtReg,
1031 SlotIndex Start, SlotIndex End,
1032 float *BestEvictweight) {
1033 EvictionCost BestEvictCost;
1034 BestEvictCost.setMax();
1035 BestEvictCost.MaxWeight = VirtReg.weight();
1036 MCRegister BestEvicteePhys;
1037
1038 // Go over all physical registers and find the best candidate for eviction
1039 for (MCRegister PhysReg : Order.getOrder()) {
1040
1041 if (!canEvictInterferenceInRange(VirtReg, PhysReg, Start, End,
1042 BestEvictCost))
1043 continue;
1044
1045 // Best so far.
1046 BestEvicteePhys = PhysReg;
1047 }
1048 *BestEvictweight = BestEvictCost.MaxWeight;
1049 return BestEvicteePhys;
1050 }
1051
1052 /// evictInterference - Evict any interferring registers that prevent VirtReg
1053 /// from being assigned to Physreg. This assumes that canEvictInterference
1054 /// returned true.
evictInterference(LiveInterval & VirtReg,MCRegister PhysReg,SmallVectorImpl<Register> & NewVRegs)1055 void RAGreedy::evictInterference(LiveInterval &VirtReg, MCRegister PhysReg,
1056 SmallVectorImpl<Register> &NewVRegs) {
1057 // Make sure that VirtReg has a cascade number, and assign that cascade
1058 // number to every evicted register. These live ranges than then only be
1059 // evicted by a newer cascade, preventing infinite loops.
1060 unsigned Cascade = ExtraRegInfo[VirtReg.reg()].Cascade;
1061 if (!Cascade)
1062 Cascade = ExtraRegInfo[VirtReg.reg()].Cascade = NextCascade++;
1063
1064 LLVM_DEBUG(dbgs() << "evicting " << printReg(PhysReg, TRI)
1065 << " interference: Cascade " << Cascade << '\n');
1066
1067 // Collect all interfering virtregs first.
1068 SmallVector<LiveInterval*, 8> Intfs;
1069 for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
1070 LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units);
1071 // We usually have the interfering VRegs cached so collectInterferingVRegs()
1072 // should be fast, we may need to recalculate if when different physregs
1073 // overlap the same register unit so we had different SubRanges queried
1074 // against it.
1075 Q.collectInterferingVRegs();
1076 ArrayRef<LiveInterval*> IVR = Q.interferingVRegs();
1077 Intfs.append(IVR.begin(), IVR.end());
1078 }
1079
1080 // Evict them second. This will invalidate the queries.
1081 for (LiveInterval *Intf : Intfs) {
1082 // The same VirtReg may be present in multiple RegUnits. Skip duplicates.
1083 if (!VRM->hasPhys(Intf->reg()))
1084 continue;
1085
1086 LastEvicted.addEviction(PhysReg, VirtReg.reg(), Intf->reg());
1087
1088 Matrix->unassign(*Intf);
1089 assert((ExtraRegInfo[Intf->reg()].Cascade < Cascade ||
1090 VirtReg.isSpillable() < Intf->isSpillable()) &&
1091 "Cannot decrease cascade number, illegal eviction");
1092 ExtraRegInfo[Intf->reg()].Cascade = Cascade;
1093 ++NumEvicted;
1094 NewVRegs.push_back(Intf->reg());
1095 }
1096 }
1097
1098 /// Returns true if the given \p PhysReg is a callee saved register and has not
1099 /// been used for allocation yet.
isUnusedCalleeSavedReg(MCRegister PhysReg) const1100 bool RAGreedy::isUnusedCalleeSavedReg(MCRegister PhysReg) const {
1101 MCRegister CSR = RegClassInfo.getLastCalleeSavedAlias(PhysReg);
1102 if (!CSR)
1103 return false;
1104
1105 return !Matrix->isPhysRegUsed(PhysReg);
1106 }
1107
1108 /// tryEvict - Try to evict all interferences for a physreg.
1109 /// @param VirtReg Currently unassigned virtual register.
1110 /// @param Order Physregs to try.
1111 /// @return Physreg to assign VirtReg, or 0.
tryEvict(LiveInterval & VirtReg,AllocationOrder & Order,SmallVectorImpl<Register> & NewVRegs,unsigned CostPerUseLimit,const SmallVirtRegSet & FixedRegisters)1112 unsigned RAGreedy::tryEvict(LiveInterval &VirtReg,
1113 AllocationOrder &Order,
1114 SmallVectorImpl<Register> &NewVRegs,
1115 unsigned CostPerUseLimit,
1116 const SmallVirtRegSet &FixedRegisters) {
1117 NamedRegionTimer T("evict", "Evict", TimerGroupName, TimerGroupDescription,
1118 TimePassesIsEnabled);
1119
1120 // Keep track of the cheapest interference seen so far.
1121 EvictionCost BestCost;
1122 BestCost.setMax();
1123 MCRegister BestPhys;
1124 unsigned OrderLimit = Order.getOrder().size();
1125
1126 // When we are just looking for a reduced cost per use, don't break any
1127 // hints, and only evict smaller spill weights.
1128 if (CostPerUseLimit < ~0u) {
1129 BestCost.BrokenHints = 0;
1130 BestCost.MaxWeight = VirtReg.weight();
1131
1132 // Check of any registers in RC are below CostPerUseLimit.
1133 const TargetRegisterClass *RC = MRI->getRegClass(VirtReg.reg());
1134 unsigned MinCost = RegClassInfo.getMinCost(RC);
1135 if (MinCost >= CostPerUseLimit) {
1136 LLVM_DEBUG(dbgs() << TRI->getRegClassName(RC) << " minimum cost = "
1137 << MinCost << ", no cheaper registers to be found.\n");
1138 return 0;
1139 }
1140
1141 // It is normal for register classes to have a long tail of registers with
1142 // the same cost. We don't need to look at them if they're too expensive.
1143 if (TRI->getCostPerUse(Order.getOrder().back()) >= CostPerUseLimit) {
1144 OrderLimit = RegClassInfo.getLastCostChange(RC);
1145 LLVM_DEBUG(dbgs() << "Only trying the first " << OrderLimit
1146 << " regs.\n");
1147 }
1148 }
1149
1150 for (auto I = Order.begin(), E = Order.getOrderLimitEnd(OrderLimit); I != E;
1151 ++I) {
1152 MCRegister PhysReg = *I;
1153 assert(PhysReg);
1154 if (TRI->getCostPerUse(PhysReg) >= CostPerUseLimit)
1155 continue;
1156 // The first use of a callee-saved register in a function has cost 1.
1157 // Don't start using a CSR when the CostPerUseLimit is low.
1158 if (CostPerUseLimit == 1 && isUnusedCalleeSavedReg(PhysReg)) {
1159 LLVM_DEBUG(
1160 dbgs() << printReg(PhysReg, TRI) << " would clobber CSR "
1161 << printReg(RegClassInfo.getLastCalleeSavedAlias(PhysReg), TRI)
1162 << '\n');
1163 continue;
1164 }
1165
1166 if (!canEvictInterference(VirtReg, PhysReg, false, BestCost,
1167 FixedRegisters))
1168 continue;
1169
1170 // Best so far.
1171 BestPhys = PhysReg;
1172
1173 // Stop if the hint can be used.
1174 if (I.isHint())
1175 break;
1176 }
1177
1178 if (!BestPhys)
1179 return 0;
1180
1181 evictInterference(VirtReg, BestPhys, NewVRegs);
1182 return BestPhys;
1183 }
1184
1185 //===----------------------------------------------------------------------===//
1186 // Region Splitting
1187 //===----------------------------------------------------------------------===//
1188
1189 /// addSplitConstraints - Fill out the SplitConstraints vector based on the
1190 /// interference pattern in Physreg and its aliases. Add the constraints to
1191 /// SpillPlacement and return the static cost of this split in Cost, assuming
1192 /// that all preferences in SplitConstraints are met.
1193 /// Return false if there are no bundles with positive bias.
addSplitConstraints(InterferenceCache::Cursor Intf,BlockFrequency & Cost)1194 bool RAGreedy::addSplitConstraints(InterferenceCache::Cursor Intf,
1195 BlockFrequency &Cost) {
1196 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
1197
1198 // Reset interference dependent info.
1199 SplitConstraints.resize(UseBlocks.size());
1200 BlockFrequency StaticCost = 0;
1201 for (unsigned I = 0; I != UseBlocks.size(); ++I) {
1202 const SplitAnalysis::BlockInfo &BI = UseBlocks[I];
1203 SpillPlacement::BlockConstraint &BC = SplitConstraints[I];
1204
1205 BC.Number = BI.MBB->getNumber();
1206 Intf.moveToBlock(BC.Number);
1207 BC.Entry = BI.LiveIn ? SpillPlacement::PrefReg : SpillPlacement::DontCare;
1208 BC.Exit = (BI.LiveOut &&
1209 !LIS->getInstructionFromIndex(BI.LastInstr)->isImplicitDef())
1210 ? SpillPlacement::PrefReg
1211 : SpillPlacement::DontCare;
1212 BC.ChangesValue = BI.FirstDef.isValid();
1213
1214 if (!Intf.hasInterference())
1215 continue;
1216
1217 // Number of spill code instructions to insert.
1218 unsigned Ins = 0;
1219
1220 // Interference for the live-in value.
1221 if (BI.LiveIn) {
1222 if (Intf.first() <= Indexes->getMBBStartIdx(BC.Number)) {
1223 BC.Entry = SpillPlacement::MustSpill;
1224 ++Ins;
1225 } else if (Intf.first() < BI.FirstInstr) {
1226 BC.Entry = SpillPlacement::PrefSpill;
1227 ++Ins;
1228 } else if (Intf.first() < BI.LastInstr) {
1229 ++Ins;
1230 }
1231
1232 // Abort if the spill cannot be inserted at the MBB' start
1233 if (((BC.Entry == SpillPlacement::MustSpill) ||
1234 (BC.Entry == SpillPlacement::PrefSpill)) &&
1235 SlotIndex::isEarlierInstr(BI.FirstInstr,
1236 SA->getFirstSplitPoint(BC.Number)))
1237 return false;
1238 }
1239
1240 // Interference for the live-out value.
1241 if (BI.LiveOut) {
1242 if (Intf.last() >= SA->getLastSplitPoint(BC.Number)) {
1243 BC.Exit = SpillPlacement::MustSpill;
1244 ++Ins;
1245 } else if (Intf.last() > BI.LastInstr) {
1246 BC.Exit = SpillPlacement::PrefSpill;
1247 ++Ins;
1248 } else if (Intf.last() > BI.FirstInstr) {
1249 ++Ins;
1250 }
1251 }
1252
1253 // Accumulate the total frequency of inserted spill code.
1254 while (Ins--)
1255 StaticCost += SpillPlacer->getBlockFrequency(BC.Number);
1256 }
1257 Cost = StaticCost;
1258
1259 // Add constraints for use-blocks. Note that these are the only constraints
1260 // that may add a positive bias, it is downhill from here.
1261 SpillPlacer->addConstraints(SplitConstraints);
1262 return SpillPlacer->scanActiveBundles();
1263 }
1264
1265 /// addThroughConstraints - Add constraints and links to SpillPlacer from the
1266 /// live-through blocks in Blocks.
addThroughConstraints(InterferenceCache::Cursor Intf,ArrayRef<unsigned> Blocks)1267 bool RAGreedy::addThroughConstraints(InterferenceCache::Cursor Intf,
1268 ArrayRef<unsigned> Blocks) {
1269 const unsigned GroupSize = 8;
1270 SpillPlacement::BlockConstraint BCS[GroupSize];
1271 unsigned TBS[GroupSize];
1272 unsigned B = 0, T = 0;
1273
1274 for (unsigned Number : Blocks) {
1275 Intf.moveToBlock(Number);
1276
1277 if (!Intf.hasInterference()) {
1278 assert(T < GroupSize && "Array overflow");
1279 TBS[T] = Number;
1280 if (++T == GroupSize) {
1281 SpillPlacer->addLinks(makeArrayRef(TBS, T));
1282 T = 0;
1283 }
1284 continue;
1285 }
1286
1287 assert(B < GroupSize && "Array overflow");
1288 BCS[B].Number = Number;
1289
1290 // Abort if the spill cannot be inserted at the MBB' start
1291 MachineBasicBlock *MBB = MF->getBlockNumbered(Number);
1292 if (!MBB->empty() &&
1293 SlotIndex::isEarlierInstr(LIS->getInstructionIndex(MBB->instr_front()),
1294 SA->getFirstSplitPoint(Number)))
1295 return false;
1296 // Interference for the live-in value.
1297 if (Intf.first() <= Indexes->getMBBStartIdx(Number))
1298 BCS[B].Entry = SpillPlacement::MustSpill;
1299 else
1300 BCS[B].Entry = SpillPlacement::PrefSpill;
1301
1302 // Interference for the live-out value.
1303 if (Intf.last() >= SA->getLastSplitPoint(Number))
1304 BCS[B].Exit = SpillPlacement::MustSpill;
1305 else
1306 BCS[B].Exit = SpillPlacement::PrefSpill;
1307
1308 if (++B == GroupSize) {
1309 SpillPlacer->addConstraints(makeArrayRef(BCS, B));
1310 B = 0;
1311 }
1312 }
1313
1314 SpillPlacer->addConstraints(makeArrayRef(BCS, B));
1315 SpillPlacer->addLinks(makeArrayRef(TBS, T));
1316 return true;
1317 }
1318
growRegion(GlobalSplitCandidate & Cand)1319 bool RAGreedy::growRegion(GlobalSplitCandidate &Cand) {
1320 // Keep track of through blocks that have not been added to SpillPlacer.
1321 BitVector Todo = SA->getThroughBlocks();
1322 SmallVectorImpl<unsigned> &ActiveBlocks = Cand.ActiveBlocks;
1323 unsigned AddedTo = 0;
1324 #ifndef NDEBUG
1325 unsigned Visited = 0;
1326 #endif
1327
1328 while (true) {
1329 ArrayRef<unsigned> NewBundles = SpillPlacer->getRecentPositive();
1330 // Find new through blocks in the periphery of PrefRegBundles.
1331 for (unsigned Bundle : NewBundles) {
1332 // Look at all blocks connected to Bundle in the full graph.
1333 ArrayRef<unsigned> Blocks = Bundles->getBlocks(Bundle);
1334 for (ArrayRef<unsigned>::iterator I = Blocks.begin(), E = Blocks.end();
1335 I != E; ++I) {
1336 unsigned Block = *I;
1337 if (!Todo.test(Block))
1338 continue;
1339 Todo.reset(Block);
1340 // This is a new through block. Add it to SpillPlacer later.
1341 ActiveBlocks.push_back(Block);
1342 #ifndef NDEBUG
1343 ++Visited;
1344 #endif
1345 }
1346 }
1347 // Any new blocks to add?
1348 if (ActiveBlocks.size() == AddedTo)
1349 break;
1350
1351 // Compute through constraints from the interference, or assume that all
1352 // through blocks prefer spilling when forming compact regions.
1353 auto NewBlocks = makeArrayRef(ActiveBlocks).slice(AddedTo);
1354 if (Cand.PhysReg) {
1355 if (!addThroughConstraints(Cand.Intf, NewBlocks))
1356 return false;
1357 } else
1358 // Provide a strong negative bias on through blocks to prevent unwanted
1359 // liveness on loop backedges.
1360 SpillPlacer->addPrefSpill(NewBlocks, /* Strong= */ true);
1361 AddedTo = ActiveBlocks.size();
1362
1363 // Perhaps iterating can enable more bundles?
1364 SpillPlacer->iterate();
1365 }
1366 LLVM_DEBUG(dbgs() << ", v=" << Visited);
1367 return true;
1368 }
1369
1370 /// calcCompactRegion - Compute the set of edge bundles that should be live
1371 /// when splitting the current live range into compact regions. Compact
1372 /// regions can be computed without looking at interference. They are the
1373 /// regions formed by removing all the live-through blocks from the live range.
1374 ///
1375 /// Returns false if the current live range is already compact, or if the
1376 /// compact regions would form single block regions anyway.
calcCompactRegion(GlobalSplitCandidate & Cand)1377 bool RAGreedy::calcCompactRegion(GlobalSplitCandidate &Cand) {
1378 // Without any through blocks, the live range is already compact.
1379 if (!SA->getNumThroughBlocks())
1380 return false;
1381
1382 // Compact regions don't correspond to any physreg.
1383 Cand.reset(IntfCache, MCRegister::NoRegister);
1384
1385 LLVM_DEBUG(dbgs() << "Compact region bundles");
1386
1387 // Use the spill placer to determine the live bundles. GrowRegion pretends
1388 // that all the through blocks have interference when PhysReg is unset.
1389 SpillPlacer->prepare(Cand.LiveBundles);
1390
1391 // The static split cost will be zero since Cand.Intf reports no interference.
1392 BlockFrequency Cost;
1393 if (!addSplitConstraints(Cand.Intf, Cost)) {
1394 LLVM_DEBUG(dbgs() << ", none.\n");
1395 return false;
1396 }
1397
1398 if (!growRegion(Cand)) {
1399 LLVM_DEBUG(dbgs() << ", cannot spill all interferences.\n");
1400 return false;
1401 }
1402
1403 SpillPlacer->finish();
1404
1405 if (!Cand.LiveBundles.any()) {
1406 LLVM_DEBUG(dbgs() << ", none.\n");
1407 return false;
1408 }
1409
1410 LLVM_DEBUG({
1411 for (int I : Cand.LiveBundles.set_bits())
1412 dbgs() << " EB#" << I;
1413 dbgs() << ".\n";
1414 });
1415 return true;
1416 }
1417
1418 /// calcSpillCost - Compute how expensive it would be to split the live range in
1419 /// SA around all use blocks instead of forming bundle regions.
calcSpillCost()1420 BlockFrequency RAGreedy::calcSpillCost() {
1421 BlockFrequency Cost = 0;
1422 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
1423 for (const SplitAnalysis::BlockInfo &BI : UseBlocks) {
1424 unsigned Number = BI.MBB->getNumber();
1425 // We normally only need one spill instruction - a load or a store.
1426 Cost += SpillPlacer->getBlockFrequency(Number);
1427
1428 // Unless the value is redefined in the block.
1429 if (BI.LiveIn && BI.LiveOut && BI.FirstDef)
1430 Cost += SpillPlacer->getBlockFrequency(Number);
1431 }
1432 return Cost;
1433 }
1434
1435 /// Check if splitting Evictee will create a local split interval in
1436 /// basic block number BBNumber that may cause a bad eviction chain. This is
1437 /// intended to prevent bad eviction sequences like:
1438 /// movl %ebp, 8(%esp) # 4-byte Spill
1439 /// movl %ecx, %ebp
1440 /// movl %ebx, %ecx
1441 /// movl %edi, %ebx
1442 /// movl %edx, %edi
1443 /// cltd
1444 /// idivl %esi
1445 /// movl %edi, %edx
1446 /// movl %ebx, %edi
1447 /// movl %ecx, %ebx
1448 /// movl %ebp, %ecx
1449 /// movl 16(%esp), %ebp # 4 - byte Reload
1450 ///
1451 /// Such sequences are created in 2 scenarios:
1452 ///
1453 /// Scenario #1:
1454 /// %0 is evicted from physreg0 by %1.
1455 /// Evictee %0 is intended for region splitting with split candidate
1456 /// physreg0 (the reg %0 was evicted from).
1457 /// Region splitting creates a local interval because of interference with the
1458 /// evictor %1 (normally region splitting creates 2 interval, the "by reg"
1459 /// and "by stack" intervals and local interval created when interference
1460 /// occurs).
1461 /// One of the split intervals ends up evicting %2 from physreg1.
1462 /// Evictee %2 is intended for region splitting with split candidate
1463 /// physreg1.
1464 /// One of the split intervals ends up evicting %3 from physreg2, etc.
1465 ///
1466 /// Scenario #2
1467 /// %0 is evicted from physreg0 by %1.
1468 /// %2 is evicted from physreg2 by %3 etc.
1469 /// Evictee %0 is intended for region splitting with split candidate
1470 /// physreg1.
1471 /// Region splitting creates a local interval because of interference with the
1472 /// evictor %1.
1473 /// One of the split intervals ends up evicting back original evictor %1
1474 /// from physreg0 (the reg %0 was evicted from).
1475 /// Another evictee %2 is intended for region splitting with split candidate
1476 /// physreg1.
1477 /// One of the split intervals ends up evicting %3 from physreg2, etc.
1478 ///
1479 /// \param Evictee The register considered to be split.
1480 /// \param Cand The split candidate that determines the physical register
1481 /// we are splitting for and the interferences.
1482 /// \param BBNumber The number of a BB for which the region split process will
1483 /// create a local split interval.
1484 /// \param Order The physical registers that may get evicted by a split
1485 /// artifact of Evictee.
1486 /// \return True if splitting Evictee may cause a bad eviction chain, false
1487 /// otherwise.
splitCanCauseEvictionChain(Register Evictee,GlobalSplitCandidate & Cand,unsigned BBNumber,const AllocationOrder & Order)1488 bool RAGreedy::splitCanCauseEvictionChain(Register Evictee,
1489 GlobalSplitCandidate &Cand,
1490 unsigned BBNumber,
1491 const AllocationOrder &Order) {
1492 EvictionTrack::EvictorInfo VregEvictorInfo = LastEvicted.getEvictor(Evictee);
1493 unsigned Evictor = VregEvictorInfo.first;
1494 MCRegister PhysReg = VregEvictorInfo.second;
1495
1496 // No actual evictor.
1497 if (!Evictor || !PhysReg)
1498 return false;
1499
1500 float MaxWeight = 0;
1501 MCRegister FutureEvictedPhysReg =
1502 getCheapestEvicteeWeight(Order, LIS->getInterval(Evictee),
1503 Cand.Intf.first(), Cand.Intf.last(), &MaxWeight);
1504
1505 // The bad eviction chain occurs when either the split candidate is the
1506 // evicting reg or one of the split artifact will evict the evicting reg.
1507 if ((PhysReg != Cand.PhysReg) && (PhysReg != FutureEvictedPhysReg))
1508 return false;
1509
1510 Cand.Intf.moveToBlock(BBNumber);
1511
1512 // Check to see if the Evictor contains interference (with Evictee) in the
1513 // given BB. If so, this interference caused the eviction of Evictee from
1514 // PhysReg. This suggest that we will create a local interval during the
1515 // region split to avoid this interference This local interval may cause a bad
1516 // eviction chain.
1517 if (!LIS->hasInterval(Evictor))
1518 return false;
1519 LiveInterval &EvictorLI = LIS->getInterval(Evictor);
1520 if (EvictorLI.FindSegmentContaining(Cand.Intf.first()) == EvictorLI.end())
1521 return false;
1522
1523 // Now, check to see if the local interval we will create is going to be
1524 // expensive enough to evict somebody If so, this may cause a bad eviction
1525 // chain.
1526 float splitArtifactWeight =
1527 VRAI->futureWeight(LIS->getInterval(Evictee),
1528 Cand.Intf.first().getPrevIndex(), Cand.Intf.last());
1529 if (splitArtifactWeight >= 0 && splitArtifactWeight < MaxWeight)
1530 return false;
1531
1532 return true;
1533 }
1534
1535 /// Check if splitting VirtRegToSplit will create a local split interval
1536 /// in basic block number BBNumber that may cause a spill.
1537 ///
1538 /// \param VirtRegToSplit The register considered to be split.
1539 /// \param Cand The split candidate that determines the physical
1540 /// register we are splitting for and the interferences.
1541 /// \param BBNumber The number of a BB for which the region split process
1542 /// will create a local split interval.
1543 /// \param Order The physical registers that may get evicted by a
1544 /// split artifact of VirtRegToSplit.
1545 /// \return True if splitting VirtRegToSplit may cause a spill, false
1546 /// otherwise.
splitCanCauseLocalSpill(unsigned VirtRegToSplit,GlobalSplitCandidate & Cand,unsigned BBNumber,const AllocationOrder & Order)1547 bool RAGreedy::splitCanCauseLocalSpill(unsigned VirtRegToSplit,
1548 GlobalSplitCandidate &Cand,
1549 unsigned BBNumber,
1550 const AllocationOrder &Order) {
1551 Cand.Intf.moveToBlock(BBNumber);
1552
1553 // Check if the local interval will find a non interfereing assignment.
1554 for (auto PhysReg : Order.getOrder()) {
1555 if (!Matrix->checkInterference(Cand.Intf.first().getPrevIndex(),
1556 Cand.Intf.last(), PhysReg))
1557 return false;
1558 }
1559
1560 // Check if the local interval will evict a cheaper interval.
1561 float CheapestEvictWeight = 0;
1562 MCRegister FutureEvictedPhysReg = getCheapestEvicteeWeight(
1563 Order, LIS->getInterval(VirtRegToSplit), Cand.Intf.first(),
1564 Cand.Intf.last(), &CheapestEvictWeight);
1565
1566 // Have we found an interval that can be evicted?
1567 if (FutureEvictedPhysReg) {
1568 float splitArtifactWeight =
1569 VRAI->futureWeight(LIS->getInterval(VirtRegToSplit),
1570 Cand.Intf.first().getPrevIndex(), Cand.Intf.last());
1571 // Will the weight of the local interval be higher than the cheapest evictee
1572 // weight? If so it will evict it and will not cause a spill.
1573 if (splitArtifactWeight >= 0 && splitArtifactWeight > CheapestEvictWeight)
1574 return false;
1575 }
1576
1577 // The local interval is not able to find non interferencing assignment and
1578 // not able to evict a less worthy interval, therfore, it can cause a spill.
1579 return true;
1580 }
1581
1582 /// calcGlobalSplitCost - Return the global split cost of following the split
1583 /// pattern in LiveBundles. This cost should be added to the local cost of the
1584 /// interference pattern in SplitConstraints.
1585 ///
calcGlobalSplitCost(GlobalSplitCandidate & Cand,const AllocationOrder & Order,bool * CanCauseEvictionChain)1586 BlockFrequency RAGreedy::calcGlobalSplitCost(GlobalSplitCandidate &Cand,
1587 const AllocationOrder &Order,
1588 bool *CanCauseEvictionChain) {
1589 BlockFrequency GlobalCost = 0;
1590 const BitVector &LiveBundles = Cand.LiveBundles;
1591 Register VirtRegToSplit = SA->getParent().reg();
1592 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
1593 for (unsigned I = 0; I != UseBlocks.size(); ++I) {
1594 const SplitAnalysis::BlockInfo &BI = UseBlocks[I];
1595 SpillPlacement::BlockConstraint &BC = SplitConstraints[I];
1596 bool RegIn = LiveBundles[Bundles->getBundle(BC.Number, false)];
1597 bool RegOut = LiveBundles[Bundles->getBundle(BC.Number, true)];
1598 unsigned Ins = 0;
1599
1600 Cand.Intf.moveToBlock(BC.Number);
1601 // Check wheather a local interval is going to be created during the region
1602 // split. Calculate adavanced spilt cost (cost of local intervals) if option
1603 // is enabled.
1604 if (EnableAdvancedRASplitCost && Cand.Intf.hasInterference() && BI.LiveIn &&
1605 BI.LiveOut && RegIn && RegOut) {
1606
1607 if (CanCauseEvictionChain &&
1608 splitCanCauseEvictionChain(VirtRegToSplit, Cand, BC.Number, Order)) {
1609 // This interference causes our eviction from this assignment, we might
1610 // evict somebody else and eventually someone will spill, add that cost.
1611 // See splitCanCauseEvictionChain for detailed description of scenarios.
1612 GlobalCost += SpillPlacer->getBlockFrequency(BC.Number);
1613 GlobalCost += SpillPlacer->getBlockFrequency(BC.Number);
1614
1615 *CanCauseEvictionChain = true;
1616
1617 } else if (splitCanCauseLocalSpill(VirtRegToSplit, Cand, BC.Number,
1618 Order)) {
1619 // This interference causes local interval to spill, add that cost.
1620 GlobalCost += SpillPlacer->getBlockFrequency(BC.Number);
1621 GlobalCost += SpillPlacer->getBlockFrequency(BC.Number);
1622 }
1623 }
1624
1625 if (BI.LiveIn)
1626 Ins += RegIn != (BC.Entry == SpillPlacement::PrefReg);
1627 if (BI.LiveOut)
1628 Ins += RegOut != (BC.Exit == SpillPlacement::PrefReg);
1629 while (Ins--)
1630 GlobalCost += SpillPlacer->getBlockFrequency(BC.Number);
1631 }
1632
1633 for (unsigned Number : Cand.ActiveBlocks) {
1634 bool RegIn = LiveBundles[Bundles->getBundle(Number, false)];
1635 bool RegOut = LiveBundles[Bundles->getBundle(Number, true)];
1636 if (!RegIn && !RegOut)
1637 continue;
1638 if (RegIn && RegOut) {
1639 // We need double spill code if this block has interference.
1640 Cand.Intf.moveToBlock(Number);
1641 if (Cand.Intf.hasInterference()) {
1642 GlobalCost += SpillPlacer->getBlockFrequency(Number);
1643 GlobalCost += SpillPlacer->getBlockFrequency(Number);
1644
1645 // Check wheather a local interval is going to be created during the
1646 // region split.
1647 if (EnableAdvancedRASplitCost && CanCauseEvictionChain &&
1648 splitCanCauseEvictionChain(VirtRegToSplit, Cand, Number, Order)) {
1649 // This interference cause our eviction from this assignment, we might
1650 // evict somebody else, add that cost.
1651 // See splitCanCauseEvictionChain for detailed description of
1652 // scenarios.
1653 GlobalCost += SpillPlacer->getBlockFrequency(Number);
1654 GlobalCost += SpillPlacer->getBlockFrequency(Number);
1655
1656 *CanCauseEvictionChain = true;
1657 }
1658 }
1659 continue;
1660 }
1661 // live-in / stack-out or stack-in live-out.
1662 GlobalCost += SpillPlacer->getBlockFrequency(Number);
1663 }
1664 return GlobalCost;
1665 }
1666
1667 /// splitAroundRegion - Split the current live range around the regions
1668 /// determined by BundleCand and GlobalCand.
1669 ///
1670 /// Before calling this function, GlobalCand and BundleCand must be initialized
1671 /// so each bundle is assigned to a valid candidate, or NoCand for the
1672 /// stack-bound bundles. The shared SA/SE SplitAnalysis and SplitEditor
1673 /// objects must be initialized for the current live range, and intervals
1674 /// created for the used candidates.
1675 ///
1676 /// @param LREdit The LiveRangeEdit object handling the current split.
1677 /// @param UsedCands List of used GlobalCand entries. Every BundleCand value
1678 /// must appear in this list.
splitAroundRegion(LiveRangeEdit & LREdit,ArrayRef<unsigned> UsedCands)1679 void RAGreedy::splitAroundRegion(LiveRangeEdit &LREdit,
1680 ArrayRef<unsigned> UsedCands) {
1681 // These are the intervals created for new global ranges. We may create more
1682 // intervals for local ranges.
1683 const unsigned NumGlobalIntvs = LREdit.size();
1684 LLVM_DEBUG(dbgs() << "splitAroundRegion with " << NumGlobalIntvs
1685 << " globals.\n");
1686 assert(NumGlobalIntvs && "No global intervals configured");
1687
1688 // Isolate even single instructions when dealing with a proper sub-class.
1689 // That guarantees register class inflation for the stack interval because it
1690 // is all copies.
1691 Register Reg = SA->getParent().reg();
1692 bool SingleInstrs = RegClassInfo.isProperSubClass(MRI->getRegClass(Reg));
1693
1694 // First handle all the blocks with uses.
1695 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
1696 for (const SplitAnalysis::BlockInfo &BI : UseBlocks) {
1697 unsigned Number = BI.MBB->getNumber();
1698 unsigned IntvIn = 0, IntvOut = 0;
1699 SlotIndex IntfIn, IntfOut;
1700 if (BI.LiveIn) {
1701 unsigned CandIn = BundleCand[Bundles->getBundle(Number, false)];
1702 if (CandIn != NoCand) {
1703 GlobalSplitCandidate &Cand = GlobalCand[CandIn];
1704 IntvIn = Cand.IntvIdx;
1705 Cand.Intf.moveToBlock(Number);
1706 IntfIn = Cand.Intf.first();
1707 }
1708 }
1709 if (BI.LiveOut) {
1710 unsigned CandOut = BundleCand[Bundles->getBundle(Number, true)];
1711 if (CandOut != NoCand) {
1712 GlobalSplitCandidate &Cand = GlobalCand[CandOut];
1713 IntvOut = Cand.IntvIdx;
1714 Cand.Intf.moveToBlock(Number);
1715 IntfOut = Cand.Intf.last();
1716 }
1717 }
1718
1719 // Create separate intervals for isolated blocks with multiple uses.
1720 if (!IntvIn && !IntvOut) {
1721 LLVM_DEBUG(dbgs() << printMBBReference(*BI.MBB) << " isolated.\n");
1722 if (SA->shouldSplitSingleBlock(BI, SingleInstrs))
1723 SE->splitSingleBlock(BI);
1724 continue;
1725 }
1726
1727 if (IntvIn && IntvOut)
1728 SE->splitLiveThroughBlock(Number, IntvIn, IntfIn, IntvOut, IntfOut);
1729 else if (IntvIn)
1730 SE->splitRegInBlock(BI, IntvIn, IntfIn);
1731 else
1732 SE->splitRegOutBlock(BI, IntvOut, IntfOut);
1733 }
1734
1735 // Handle live-through blocks. The relevant live-through blocks are stored in
1736 // the ActiveBlocks list with each candidate. We need to filter out
1737 // duplicates.
1738 BitVector Todo = SA->getThroughBlocks();
1739 for (unsigned c = 0; c != UsedCands.size(); ++c) {
1740 ArrayRef<unsigned> Blocks = GlobalCand[UsedCands[c]].ActiveBlocks;
1741 for (unsigned Number : Blocks) {
1742 if (!Todo.test(Number))
1743 continue;
1744 Todo.reset(Number);
1745
1746 unsigned IntvIn = 0, IntvOut = 0;
1747 SlotIndex IntfIn, IntfOut;
1748
1749 unsigned CandIn = BundleCand[Bundles->getBundle(Number, false)];
1750 if (CandIn != NoCand) {
1751 GlobalSplitCandidate &Cand = GlobalCand[CandIn];
1752 IntvIn = Cand.IntvIdx;
1753 Cand.Intf.moveToBlock(Number);
1754 IntfIn = Cand.Intf.first();
1755 }
1756
1757 unsigned CandOut = BundleCand[Bundles->getBundle(Number, true)];
1758 if (CandOut != NoCand) {
1759 GlobalSplitCandidate &Cand = GlobalCand[CandOut];
1760 IntvOut = Cand.IntvIdx;
1761 Cand.Intf.moveToBlock(Number);
1762 IntfOut = Cand.Intf.last();
1763 }
1764 if (!IntvIn && !IntvOut)
1765 continue;
1766 SE->splitLiveThroughBlock(Number, IntvIn, IntfIn, IntvOut, IntfOut);
1767 }
1768 }
1769
1770 ++NumGlobalSplits;
1771
1772 SmallVector<unsigned, 8> IntvMap;
1773 SE->finish(&IntvMap);
1774 DebugVars->splitRegister(Reg, LREdit.regs(), *LIS);
1775
1776 ExtraRegInfo.resize(MRI->getNumVirtRegs());
1777 unsigned OrigBlocks = SA->getNumLiveBlocks();
1778
1779 // Sort out the new intervals created by splitting. We get four kinds:
1780 // - Remainder intervals should not be split again.
1781 // - Candidate intervals can be assigned to Cand.PhysReg.
1782 // - Block-local splits are candidates for local splitting.
1783 // - DCE leftovers should go back on the queue.
1784 for (unsigned I = 0, E = LREdit.size(); I != E; ++I) {
1785 LiveInterval &Reg = LIS->getInterval(LREdit.get(I));
1786
1787 // Ignore old intervals from DCE.
1788 if (getStage(Reg) != RS_New)
1789 continue;
1790
1791 // Remainder interval. Don't try splitting again, spill if it doesn't
1792 // allocate.
1793 if (IntvMap[I] == 0) {
1794 setStage(Reg, RS_Spill);
1795 continue;
1796 }
1797
1798 // Global intervals. Allow repeated splitting as long as the number of live
1799 // blocks is strictly decreasing.
1800 if (IntvMap[I] < NumGlobalIntvs) {
1801 if (SA->countLiveBlocks(&Reg) >= OrigBlocks) {
1802 LLVM_DEBUG(dbgs() << "Main interval covers the same " << OrigBlocks
1803 << " blocks as original.\n");
1804 // Don't allow repeated splitting as a safe guard against looping.
1805 setStage(Reg, RS_Split2);
1806 }
1807 continue;
1808 }
1809
1810 // Other intervals are treated as new. This includes local intervals created
1811 // for blocks with multiple uses, and anything created by DCE.
1812 }
1813
1814 if (VerifyEnabled)
1815 MF->verify(this, "After splitting live range around region");
1816 }
1817
tryRegionSplit(LiveInterval & VirtReg,AllocationOrder & Order,SmallVectorImpl<Register> & NewVRegs)1818 MCRegister RAGreedy::tryRegionSplit(LiveInterval &VirtReg,
1819 AllocationOrder &Order,
1820 SmallVectorImpl<Register> &NewVRegs) {
1821 if (!TRI->shouldRegionSplitForVirtReg(*MF, VirtReg))
1822 return MCRegister::NoRegister;
1823 unsigned NumCands = 0;
1824 BlockFrequency SpillCost = calcSpillCost();
1825 BlockFrequency BestCost;
1826
1827 // Check if we can split this live range around a compact region.
1828 bool HasCompact = calcCompactRegion(GlobalCand.front());
1829 if (HasCompact) {
1830 // Yes, keep GlobalCand[0] as the compact region candidate.
1831 NumCands = 1;
1832 BestCost = BlockFrequency::getMaxFrequency();
1833 } else {
1834 // No benefit from the compact region, our fallback will be per-block
1835 // splitting. Make sure we find a solution that is cheaper than spilling.
1836 BestCost = SpillCost;
1837 LLVM_DEBUG(dbgs() << "Cost of isolating all blocks = ";
1838 MBFI->printBlockFreq(dbgs(), BestCost) << '\n');
1839 }
1840
1841 bool CanCauseEvictionChain = false;
1842 unsigned BestCand =
1843 calculateRegionSplitCost(VirtReg, Order, BestCost, NumCands,
1844 false /*IgnoreCSR*/, &CanCauseEvictionChain);
1845
1846 // Split candidates with compact regions can cause a bad eviction sequence.
1847 // See splitCanCauseEvictionChain for detailed description of scenarios.
1848 // To avoid it, we need to comapre the cost with the spill cost and not the
1849 // current max frequency.
1850 if (HasCompact && (BestCost > SpillCost) && (BestCand != NoCand) &&
1851 CanCauseEvictionChain) {
1852 return MCRegister::NoRegister;
1853 }
1854
1855 // No solutions found, fall back to single block splitting.
1856 if (!HasCompact && BestCand == NoCand)
1857 return MCRegister::NoRegister;
1858
1859 return doRegionSplit(VirtReg, BestCand, HasCompact, NewVRegs);
1860 }
1861
calculateRegionSplitCost(LiveInterval & VirtReg,AllocationOrder & Order,BlockFrequency & BestCost,unsigned & NumCands,bool IgnoreCSR,bool * CanCauseEvictionChain)1862 unsigned RAGreedy::calculateRegionSplitCost(LiveInterval &VirtReg,
1863 AllocationOrder &Order,
1864 BlockFrequency &BestCost,
1865 unsigned &NumCands, bool IgnoreCSR,
1866 bool *CanCauseEvictionChain) {
1867 unsigned BestCand = NoCand;
1868 for (MCPhysReg PhysReg : Order) {
1869 assert(PhysReg);
1870 if (IgnoreCSR && isUnusedCalleeSavedReg(PhysReg))
1871 continue;
1872
1873 // Discard bad candidates before we run out of interference cache cursors.
1874 // This will only affect register classes with a lot of registers (>32).
1875 if (NumCands == IntfCache.getMaxCursors()) {
1876 unsigned WorstCount = ~0u;
1877 unsigned Worst = 0;
1878 for (unsigned CandIndex = 0; CandIndex != NumCands; ++CandIndex) {
1879 if (CandIndex == BestCand || !GlobalCand[CandIndex].PhysReg)
1880 continue;
1881 unsigned Count = GlobalCand[CandIndex].LiveBundles.count();
1882 if (Count < WorstCount) {
1883 Worst = CandIndex;
1884 WorstCount = Count;
1885 }
1886 }
1887 --NumCands;
1888 GlobalCand[Worst] = GlobalCand[NumCands];
1889 if (BestCand == NumCands)
1890 BestCand = Worst;
1891 }
1892
1893 if (GlobalCand.size() <= NumCands)
1894 GlobalCand.resize(NumCands+1);
1895 GlobalSplitCandidate &Cand = GlobalCand[NumCands];
1896 Cand.reset(IntfCache, PhysReg);
1897
1898 SpillPlacer->prepare(Cand.LiveBundles);
1899 BlockFrequency Cost;
1900 if (!addSplitConstraints(Cand.Intf, Cost)) {
1901 LLVM_DEBUG(dbgs() << printReg(PhysReg, TRI) << "\tno positive bundles\n");
1902 continue;
1903 }
1904 LLVM_DEBUG(dbgs() << printReg(PhysReg, TRI) << "\tstatic = ";
1905 MBFI->printBlockFreq(dbgs(), Cost));
1906 if (Cost >= BestCost) {
1907 LLVM_DEBUG({
1908 if (BestCand == NoCand)
1909 dbgs() << " worse than no bundles\n";
1910 else
1911 dbgs() << " worse than "
1912 << printReg(GlobalCand[BestCand].PhysReg, TRI) << '\n';
1913 });
1914 continue;
1915 }
1916 if (!growRegion(Cand)) {
1917 LLVM_DEBUG(dbgs() << ", cannot spill all interferences.\n");
1918 continue;
1919 }
1920
1921 SpillPlacer->finish();
1922
1923 // No live bundles, defer to splitSingleBlocks().
1924 if (!Cand.LiveBundles.any()) {
1925 LLVM_DEBUG(dbgs() << " no bundles.\n");
1926 continue;
1927 }
1928
1929 bool HasEvictionChain = false;
1930 Cost += calcGlobalSplitCost(Cand, Order, &HasEvictionChain);
1931 LLVM_DEBUG({
1932 dbgs() << ", total = ";
1933 MBFI->printBlockFreq(dbgs(), Cost) << " with bundles";
1934 for (int I : Cand.LiveBundles.set_bits())
1935 dbgs() << " EB#" << I;
1936 dbgs() << ".\n";
1937 });
1938 if (Cost < BestCost) {
1939 BestCand = NumCands;
1940 BestCost = Cost;
1941 // See splitCanCauseEvictionChain for detailed description of bad
1942 // eviction chain scenarios.
1943 if (CanCauseEvictionChain)
1944 *CanCauseEvictionChain = HasEvictionChain;
1945 }
1946 ++NumCands;
1947 }
1948
1949 if (CanCauseEvictionChain && BestCand != NoCand) {
1950 // See splitCanCauseEvictionChain for detailed description of bad
1951 // eviction chain scenarios.
1952 LLVM_DEBUG(dbgs() << "Best split candidate of vreg "
1953 << printReg(VirtReg.reg(), TRI) << " may ");
1954 if (!(*CanCauseEvictionChain))
1955 LLVM_DEBUG(dbgs() << "not ");
1956 LLVM_DEBUG(dbgs() << "cause bad eviction chain\n");
1957 }
1958
1959 return BestCand;
1960 }
1961
doRegionSplit(LiveInterval & VirtReg,unsigned BestCand,bool HasCompact,SmallVectorImpl<Register> & NewVRegs)1962 unsigned RAGreedy::doRegionSplit(LiveInterval &VirtReg, unsigned BestCand,
1963 bool HasCompact,
1964 SmallVectorImpl<Register> &NewVRegs) {
1965 SmallVector<unsigned, 8> UsedCands;
1966 // Prepare split editor.
1967 LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this, &DeadRemats);
1968 SE->reset(LREdit, SplitSpillMode);
1969
1970 // Assign all edge bundles to the preferred candidate, or NoCand.
1971 BundleCand.assign(Bundles->getNumBundles(), NoCand);
1972
1973 // Assign bundles for the best candidate region.
1974 if (BestCand != NoCand) {
1975 GlobalSplitCandidate &Cand = GlobalCand[BestCand];
1976 if (unsigned B = Cand.getBundles(BundleCand, BestCand)) {
1977 UsedCands.push_back(BestCand);
1978 Cand.IntvIdx = SE->openIntv();
1979 LLVM_DEBUG(dbgs() << "Split for " << printReg(Cand.PhysReg, TRI) << " in "
1980 << B << " bundles, intv " << Cand.IntvIdx << ".\n");
1981 (void)B;
1982 }
1983 }
1984
1985 // Assign bundles for the compact region.
1986 if (HasCompact) {
1987 GlobalSplitCandidate &Cand = GlobalCand.front();
1988 assert(!Cand.PhysReg && "Compact region has no physreg");
1989 if (unsigned B = Cand.getBundles(BundleCand, 0)) {
1990 UsedCands.push_back(0);
1991 Cand.IntvIdx = SE->openIntv();
1992 LLVM_DEBUG(dbgs() << "Split for compact region in " << B
1993 << " bundles, intv " << Cand.IntvIdx << ".\n");
1994 (void)B;
1995 }
1996 }
1997
1998 splitAroundRegion(LREdit, UsedCands);
1999 return 0;
2000 }
2001
2002 //===----------------------------------------------------------------------===//
2003 // Per-Block Splitting
2004 //===----------------------------------------------------------------------===//
2005
2006 /// tryBlockSplit - Split a global live range around every block with uses. This
2007 /// creates a lot of local live ranges, that will be split by tryLocalSplit if
2008 /// they don't allocate.
tryBlockSplit(LiveInterval & VirtReg,AllocationOrder & Order,SmallVectorImpl<Register> & NewVRegs)2009 unsigned RAGreedy::tryBlockSplit(LiveInterval &VirtReg, AllocationOrder &Order,
2010 SmallVectorImpl<Register> &NewVRegs) {
2011 assert(&SA->getParent() == &VirtReg && "Live range wasn't analyzed");
2012 Register Reg = VirtReg.reg();
2013 bool SingleInstrs = RegClassInfo.isProperSubClass(MRI->getRegClass(Reg));
2014 LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this, &DeadRemats);
2015 SE->reset(LREdit, SplitSpillMode);
2016 ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
2017 for (const SplitAnalysis::BlockInfo &BI : UseBlocks) {
2018 if (SA->shouldSplitSingleBlock(BI, SingleInstrs))
2019 SE->splitSingleBlock(BI);
2020 }
2021 // No blocks were split.
2022 if (LREdit.empty())
2023 return 0;
2024
2025 // We did split for some blocks.
2026 SmallVector<unsigned, 8> IntvMap;
2027 SE->finish(&IntvMap);
2028
2029 // Tell LiveDebugVariables about the new ranges.
2030 DebugVars->splitRegister(Reg, LREdit.regs(), *LIS);
2031
2032 ExtraRegInfo.resize(MRI->getNumVirtRegs());
2033
2034 // Sort out the new intervals created by splitting. The remainder interval
2035 // goes straight to spilling, the new local ranges get to stay RS_New.
2036 for (unsigned I = 0, E = LREdit.size(); I != E; ++I) {
2037 LiveInterval &LI = LIS->getInterval(LREdit.get(I));
2038 if (getStage(LI) == RS_New && IntvMap[I] == 0)
2039 setStage(LI, RS_Spill);
2040 }
2041
2042 if (VerifyEnabled)
2043 MF->verify(this, "After splitting live range around basic blocks");
2044 return 0;
2045 }
2046
2047 //===----------------------------------------------------------------------===//
2048 // Per-Instruction Splitting
2049 //===----------------------------------------------------------------------===//
2050
2051 /// Get the number of allocatable registers that match the constraints of \p Reg
2052 /// on \p MI and that are also in \p SuperRC.
getNumAllocatableRegsForConstraints(const MachineInstr * MI,Register Reg,const TargetRegisterClass * SuperRC,const TargetInstrInfo * TII,const TargetRegisterInfo * TRI,const RegisterClassInfo & RCI)2053 static unsigned getNumAllocatableRegsForConstraints(
2054 const MachineInstr *MI, Register Reg, const TargetRegisterClass *SuperRC,
2055 const TargetInstrInfo *TII, const TargetRegisterInfo *TRI,
2056 const RegisterClassInfo &RCI) {
2057 assert(SuperRC && "Invalid register class");
2058
2059 const TargetRegisterClass *ConstrainedRC =
2060 MI->getRegClassConstraintEffectForVReg(Reg, SuperRC, TII, TRI,
2061 /* ExploreBundle */ true);
2062 if (!ConstrainedRC)
2063 return 0;
2064 return RCI.getNumAllocatableRegs(ConstrainedRC);
2065 }
2066
2067 /// tryInstructionSplit - Split a live range around individual instructions.
2068 /// This is normally not worthwhile since the spiller is doing essentially the
2069 /// same thing. However, when the live range is in a constrained register
2070 /// class, it may help to insert copies such that parts of the live range can
2071 /// be moved to a larger register class.
2072 ///
2073 /// This is similar to spilling to a larger register class.
2074 unsigned
tryInstructionSplit(LiveInterval & VirtReg,AllocationOrder & Order,SmallVectorImpl<Register> & NewVRegs)2075 RAGreedy::tryInstructionSplit(LiveInterval &VirtReg, AllocationOrder &Order,
2076 SmallVectorImpl<Register> &NewVRegs) {
2077 const TargetRegisterClass *CurRC = MRI->getRegClass(VirtReg.reg());
2078 // There is no point to this if there are no larger sub-classes.
2079 if (!RegClassInfo.isProperSubClass(CurRC))
2080 return 0;
2081
2082 // Always enable split spill mode, since we're effectively spilling to a
2083 // register.
2084 LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this, &DeadRemats);
2085 SE->reset(LREdit, SplitEditor::SM_Size);
2086
2087 ArrayRef<SlotIndex> Uses = SA->getUseSlots();
2088 if (Uses.size() <= 1)
2089 return 0;
2090
2091 LLVM_DEBUG(dbgs() << "Split around " << Uses.size()
2092 << " individual instrs.\n");
2093
2094 const TargetRegisterClass *SuperRC =
2095 TRI->getLargestLegalSuperClass(CurRC, *MF);
2096 unsigned SuperRCNumAllocatableRegs = RCI.getNumAllocatableRegs(SuperRC);
2097 // Split around every non-copy instruction if this split will relax
2098 // the constraints on the virtual register.
2099 // Otherwise, splitting just inserts uncoalescable copies that do not help
2100 // the allocation.
2101 for (const auto &Use : Uses) {
2102 if (const MachineInstr *MI = Indexes->getInstructionFromIndex(Use))
2103 if (MI->isFullCopy() ||
2104 SuperRCNumAllocatableRegs ==
2105 getNumAllocatableRegsForConstraints(MI, VirtReg.reg(), SuperRC,
2106 TII, TRI, RCI)) {
2107 LLVM_DEBUG(dbgs() << " skip:\t" << Use << '\t' << *MI);
2108 continue;
2109 }
2110 SE->openIntv();
2111 SlotIndex SegStart = SE->enterIntvBefore(Use);
2112 SlotIndex SegStop = SE->leaveIntvAfter(Use);
2113 SE->useIntv(SegStart, SegStop);
2114 }
2115
2116 if (LREdit.empty()) {
2117 LLVM_DEBUG(dbgs() << "All uses were copies.\n");
2118 return 0;
2119 }
2120
2121 SmallVector<unsigned, 8> IntvMap;
2122 SE->finish(&IntvMap);
2123 DebugVars->splitRegister(VirtReg.reg(), LREdit.regs(), *LIS);
2124 ExtraRegInfo.resize(MRI->getNumVirtRegs());
2125
2126 // Assign all new registers to RS_Spill. This was the last chance.
2127 setStage(LREdit.begin(), LREdit.end(), RS_Spill);
2128 return 0;
2129 }
2130
2131 //===----------------------------------------------------------------------===//
2132 // Local Splitting
2133 //===----------------------------------------------------------------------===//
2134
2135 /// calcGapWeights - Compute the maximum spill weight that needs to be evicted
2136 /// in order to use PhysReg between two entries in SA->UseSlots.
2137 ///
2138 /// GapWeight[I] represents the gap between UseSlots[I] and UseSlots[I + 1].
2139 ///
calcGapWeights(MCRegister PhysReg,SmallVectorImpl<float> & GapWeight)2140 void RAGreedy::calcGapWeights(MCRegister PhysReg,
2141 SmallVectorImpl<float> &GapWeight) {
2142 assert(SA->getUseBlocks().size() == 1 && "Not a local interval");
2143 const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front();
2144 ArrayRef<SlotIndex> Uses = SA->getUseSlots();
2145 const unsigned NumGaps = Uses.size()-1;
2146
2147 // Start and end points for the interference check.
2148 SlotIndex StartIdx =
2149 BI.LiveIn ? BI.FirstInstr.getBaseIndex() : BI.FirstInstr;
2150 SlotIndex StopIdx =
2151 BI.LiveOut ? BI.LastInstr.getBoundaryIndex() : BI.LastInstr;
2152
2153 GapWeight.assign(NumGaps, 0.0f);
2154
2155 // Add interference from each overlapping register.
2156 for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
2157 if (!Matrix->query(const_cast<LiveInterval&>(SA->getParent()), *Units)
2158 .checkInterference())
2159 continue;
2160
2161 // We know that VirtReg is a continuous interval from FirstInstr to
2162 // LastInstr, so we don't need InterferenceQuery.
2163 //
2164 // Interference that overlaps an instruction is counted in both gaps
2165 // surrounding the instruction. The exception is interference before
2166 // StartIdx and after StopIdx.
2167 //
2168 LiveIntervalUnion::SegmentIter IntI =
2169 Matrix->getLiveUnions()[*Units] .find(StartIdx);
2170 for (unsigned Gap = 0; IntI.valid() && IntI.start() < StopIdx; ++IntI) {
2171 // Skip the gaps before IntI.
2172 while (Uses[Gap+1].getBoundaryIndex() < IntI.start())
2173 if (++Gap == NumGaps)
2174 break;
2175 if (Gap == NumGaps)
2176 break;
2177
2178 // Update the gaps covered by IntI.
2179 const float weight = IntI.value()->weight();
2180 for (; Gap != NumGaps; ++Gap) {
2181 GapWeight[Gap] = std::max(GapWeight[Gap], weight);
2182 if (Uses[Gap+1].getBaseIndex() >= IntI.stop())
2183 break;
2184 }
2185 if (Gap == NumGaps)
2186 break;
2187 }
2188 }
2189
2190 // Add fixed interference.
2191 for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
2192 const LiveRange &LR = LIS->getRegUnit(*Units);
2193 LiveRange::const_iterator I = LR.find(StartIdx);
2194 LiveRange::const_iterator E = LR.end();
2195
2196 // Same loop as above. Mark any overlapped gaps as HUGE_VALF.
2197 for (unsigned Gap = 0; I != E && I->start < StopIdx; ++I) {
2198 while (Uses[Gap+1].getBoundaryIndex() < I->start)
2199 if (++Gap == NumGaps)
2200 break;
2201 if (Gap == NumGaps)
2202 break;
2203
2204 for (; Gap != NumGaps; ++Gap) {
2205 GapWeight[Gap] = huge_valf;
2206 if (Uses[Gap+1].getBaseIndex() >= I->end)
2207 break;
2208 }
2209 if (Gap == NumGaps)
2210 break;
2211 }
2212 }
2213 }
2214
2215 /// tryLocalSplit - Try to split VirtReg into smaller intervals inside its only
2216 /// basic block.
2217 ///
tryLocalSplit(LiveInterval & VirtReg,AllocationOrder & Order,SmallVectorImpl<Register> & NewVRegs)2218 unsigned RAGreedy::tryLocalSplit(LiveInterval &VirtReg, AllocationOrder &Order,
2219 SmallVectorImpl<Register> &NewVRegs) {
2220 // TODO: the function currently only handles a single UseBlock; it should be
2221 // possible to generalize.
2222 if (SA->getUseBlocks().size() != 1)
2223 return 0;
2224
2225 const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front();
2226
2227 // Note that it is possible to have an interval that is live-in or live-out
2228 // while only covering a single block - A phi-def can use undef values from
2229 // predecessors, and the block could be a single-block loop.
2230 // We don't bother doing anything clever about such a case, we simply assume
2231 // that the interval is continuous from FirstInstr to LastInstr. We should
2232 // make sure that we don't do anything illegal to such an interval, though.
2233
2234 ArrayRef<SlotIndex> Uses = SA->getUseSlots();
2235 if (Uses.size() <= 2)
2236 return 0;
2237 const unsigned NumGaps = Uses.size()-1;
2238
2239 LLVM_DEBUG({
2240 dbgs() << "tryLocalSplit: ";
2241 for (const auto &Use : Uses)
2242 dbgs() << ' ' << Use;
2243 dbgs() << '\n';
2244 });
2245
2246 // If VirtReg is live across any register mask operands, compute a list of
2247 // gaps with register masks.
2248 SmallVector<unsigned, 8> RegMaskGaps;
2249 if (Matrix->checkRegMaskInterference(VirtReg)) {
2250 // Get regmask slots for the whole block.
2251 ArrayRef<SlotIndex> RMS = LIS->getRegMaskSlotsInBlock(BI.MBB->getNumber());
2252 LLVM_DEBUG(dbgs() << RMS.size() << " regmasks in block:");
2253 // Constrain to VirtReg's live range.
2254 unsigned RI =
2255 llvm::lower_bound(RMS, Uses.front().getRegSlot()) - RMS.begin();
2256 unsigned RE = RMS.size();
2257 for (unsigned I = 0; I != NumGaps && RI != RE; ++I) {
2258 // Look for Uses[I] <= RMS <= Uses[I + 1].
2259 assert(!SlotIndex::isEarlierInstr(RMS[RI], Uses[I]));
2260 if (SlotIndex::isEarlierInstr(Uses[I + 1], RMS[RI]))
2261 continue;
2262 // Skip a regmask on the same instruction as the last use. It doesn't
2263 // overlap the live range.
2264 if (SlotIndex::isSameInstr(Uses[I + 1], RMS[RI]) && I + 1 == NumGaps)
2265 break;
2266 LLVM_DEBUG(dbgs() << ' ' << RMS[RI] << ':' << Uses[I] << '-'
2267 << Uses[I + 1]);
2268 RegMaskGaps.push_back(I);
2269 // Advance ri to the next gap. A regmask on one of the uses counts in
2270 // both gaps.
2271 while (RI != RE && SlotIndex::isEarlierInstr(RMS[RI], Uses[I + 1]))
2272 ++RI;
2273 }
2274 LLVM_DEBUG(dbgs() << '\n');
2275 }
2276
2277 // Since we allow local split results to be split again, there is a risk of
2278 // creating infinite loops. It is tempting to require that the new live
2279 // ranges have less instructions than the original. That would guarantee
2280 // convergence, but it is too strict. A live range with 3 instructions can be
2281 // split 2+3 (including the COPY), and we want to allow that.
2282 //
2283 // Instead we use these rules:
2284 //
2285 // 1. Allow any split for ranges with getStage() < RS_Split2. (Except for the
2286 // noop split, of course).
2287 // 2. Require progress be made for ranges with getStage() == RS_Split2. All
2288 // the new ranges must have fewer instructions than before the split.
2289 // 3. New ranges with the same number of instructions are marked RS_Split2,
2290 // smaller ranges are marked RS_New.
2291 //
2292 // These rules allow a 3 -> 2+3 split once, which we need. They also prevent
2293 // excessive splitting and infinite loops.
2294 //
2295 bool ProgressRequired = getStage(VirtReg) >= RS_Split2;
2296
2297 // Best split candidate.
2298 unsigned BestBefore = NumGaps;
2299 unsigned BestAfter = 0;
2300 float BestDiff = 0;
2301
2302 const float blockFreq =
2303 SpillPlacer->getBlockFrequency(BI.MBB->getNumber()).getFrequency() *
2304 (1.0f / MBFI->getEntryFreq());
2305 SmallVector<float, 8> GapWeight;
2306
2307 for (MCPhysReg PhysReg : Order) {
2308 assert(PhysReg);
2309 // Keep track of the largest spill weight that would need to be evicted in
2310 // order to make use of PhysReg between UseSlots[I] and UseSlots[I + 1].
2311 calcGapWeights(PhysReg, GapWeight);
2312
2313 // Remove any gaps with regmask clobbers.
2314 if (Matrix->checkRegMaskInterference(VirtReg, PhysReg))
2315 for (unsigned I = 0, E = RegMaskGaps.size(); I != E; ++I)
2316 GapWeight[RegMaskGaps[I]] = huge_valf;
2317
2318 // Try to find the best sequence of gaps to close.
2319 // The new spill weight must be larger than any gap interference.
2320
2321 // We will split before Uses[SplitBefore] and after Uses[SplitAfter].
2322 unsigned SplitBefore = 0, SplitAfter = 1;
2323
2324 // MaxGap should always be max(GapWeight[SplitBefore..SplitAfter-1]).
2325 // It is the spill weight that needs to be evicted.
2326 float MaxGap = GapWeight[0];
2327
2328 while (true) {
2329 // Live before/after split?
2330 const bool LiveBefore = SplitBefore != 0 || BI.LiveIn;
2331 const bool LiveAfter = SplitAfter != NumGaps || BI.LiveOut;
2332
2333 LLVM_DEBUG(dbgs() << printReg(PhysReg, TRI) << ' ' << Uses[SplitBefore]
2334 << '-' << Uses[SplitAfter] << " I=" << MaxGap);
2335
2336 // Stop before the interval gets so big we wouldn't be making progress.
2337 if (!LiveBefore && !LiveAfter) {
2338 LLVM_DEBUG(dbgs() << " all\n");
2339 break;
2340 }
2341 // Should the interval be extended or shrunk?
2342 bool Shrink = true;
2343
2344 // How many gaps would the new range have?
2345 unsigned NewGaps = LiveBefore + SplitAfter - SplitBefore + LiveAfter;
2346
2347 // Legally, without causing looping?
2348 bool Legal = !ProgressRequired || NewGaps < NumGaps;
2349
2350 if (Legal && MaxGap < huge_valf) {
2351 // Estimate the new spill weight. Each instruction reads or writes the
2352 // register. Conservatively assume there are no read-modify-write
2353 // instructions.
2354 //
2355 // Try to guess the size of the new interval.
2356 const float EstWeight = normalizeSpillWeight(
2357 blockFreq * (NewGaps + 1),
2358 Uses[SplitBefore].distance(Uses[SplitAfter]) +
2359 (LiveBefore + LiveAfter) * SlotIndex::InstrDist,
2360 1);
2361 // Would this split be possible to allocate?
2362 // Never allocate all gaps, we wouldn't be making progress.
2363 LLVM_DEBUG(dbgs() << " w=" << EstWeight);
2364 if (EstWeight * Hysteresis >= MaxGap) {
2365 Shrink = false;
2366 float Diff = EstWeight - MaxGap;
2367 if (Diff > BestDiff) {
2368 LLVM_DEBUG(dbgs() << " (best)");
2369 BestDiff = Hysteresis * Diff;
2370 BestBefore = SplitBefore;
2371 BestAfter = SplitAfter;
2372 }
2373 }
2374 }
2375
2376 // Try to shrink.
2377 if (Shrink) {
2378 if (++SplitBefore < SplitAfter) {
2379 LLVM_DEBUG(dbgs() << " shrink\n");
2380 // Recompute the max when necessary.
2381 if (GapWeight[SplitBefore - 1] >= MaxGap) {
2382 MaxGap = GapWeight[SplitBefore];
2383 for (unsigned I = SplitBefore + 1; I != SplitAfter; ++I)
2384 MaxGap = std::max(MaxGap, GapWeight[I]);
2385 }
2386 continue;
2387 }
2388 MaxGap = 0;
2389 }
2390
2391 // Try to extend the interval.
2392 if (SplitAfter >= NumGaps) {
2393 LLVM_DEBUG(dbgs() << " end\n");
2394 break;
2395 }
2396
2397 LLVM_DEBUG(dbgs() << " extend\n");
2398 MaxGap = std::max(MaxGap, GapWeight[SplitAfter++]);
2399 }
2400 }
2401
2402 // Didn't find any candidates?
2403 if (BestBefore == NumGaps)
2404 return 0;
2405
2406 LLVM_DEBUG(dbgs() << "Best local split range: " << Uses[BestBefore] << '-'
2407 << Uses[BestAfter] << ", " << BestDiff << ", "
2408 << (BestAfter - BestBefore + 1) << " instrs\n");
2409
2410 LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this, &DeadRemats);
2411 SE->reset(LREdit);
2412
2413 SE->openIntv();
2414 SlotIndex SegStart = SE->enterIntvBefore(Uses[BestBefore]);
2415 SlotIndex SegStop = SE->leaveIntvAfter(Uses[BestAfter]);
2416 SE->useIntv(SegStart, SegStop);
2417 SmallVector<unsigned, 8> IntvMap;
2418 SE->finish(&IntvMap);
2419 DebugVars->splitRegister(VirtReg.reg(), LREdit.regs(), *LIS);
2420
2421 // If the new range has the same number of instructions as before, mark it as
2422 // RS_Split2 so the next split will be forced to make progress. Otherwise,
2423 // leave the new intervals as RS_New so they can compete.
2424 bool LiveBefore = BestBefore != 0 || BI.LiveIn;
2425 bool LiveAfter = BestAfter != NumGaps || BI.LiveOut;
2426 unsigned NewGaps = LiveBefore + BestAfter - BestBefore + LiveAfter;
2427 if (NewGaps >= NumGaps) {
2428 LLVM_DEBUG(dbgs() << "Tagging non-progress ranges: ");
2429 assert(!ProgressRequired && "Didn't make progress when it was required.");
2430 for (unsigned I = 0, E = IntvMap.size(); I != E; ++I)
2431 if (IntvMap[I] == 1) {
2432 setStage(LIS->getInterval(LREdit.get(I)), RS_Split2);
2433 LLVM_DEBUG(dbgs() << printReg(LREdit.get(I)));
2434 }
2435 LLVM_DEBUG(dbgs() << '\n');
2436 }
2437 ++NumLocalSplits;
2438
2439 return 0;
2440 }
2441
2442 //===----------------------------------------------------------------------===//
2443 // Live Range Splitting
2444 //===----------------------------------------------------------------------===//
2445
2446 /// trySplit - Try to split VirtReg or one of its interferences, making it
2447 /// assignable.
2448 /// @return Physreg when VirtReg may be assigned and/or new NewVRegs.
trySplit(LiveInterval & VirtReg,AllocationOrder & Order,SmallVectorImpl<Register> & NewVRegs,const SmallVirtRegSet & FixedRegisters)2449 unsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order,
2450 SmallVectorImpl<Register> &NewVRegs,
2451 const SmallVirtRegSet &FixedRegisters) {
2452 // Ranges must be Split2 or less.
2453 if (getStage(VirtReg) >= RS_Spill)
2454 return 0;
2455
2456 // Local intervals are handled separately.
2457 if (LIS->intervalIsInOneMBB(VirtReg)) {
2458 NamedRegionTimer T("local_split", "Local Splitting", TimerGroupName,
2459 TimerGroupDescription, TimePassesIsEnabled);
2460 SA->analyze(&VirtReg);
2461 Register PhysReg = tryLocalSplit(VirtReg, Order, NewVRegs);
2462 if (PhysReg || !NewVRegs.empty())
2463 return PhysReg;
2464 return tryInstructionSplit(VirtReg, Order, NewVRegs);
2465 }
2466
2467 NamedRegionTimer T("global_split", "Global Splitting", TimerGroupName,
2468 TimerGroupDescription, TimePassesIsEnabled);
2469
2470 SA->analyze(&VirtReg);
2471
2472 // FIXME: SplitAnalysis may repair broken live ranges coming from the
2473 // coalescer. That may cause the range to become allocatable which means that
2474 // tryRegionSplit won't be making progress. This check should be replaced with
2475 // an assertion when the coalescer is fixed.
2476 if (SA->didRepairRange()) {
2477 // VirtReg has changed, so all cached queries are invalid.
2478 Matrix->invalidateVirtRegs();
2479 if (Register PhysReg = tryAssign(VirtReg, Order, NewVRegs, FixedRegisters))
2480 return PhysReg;
2481 }
2482
2483 // First try to split around a region spanning multiple blocks. RS_Split2
2484 // ranges already made dubious progress with region splitting, so they go
2485 // straight to single block splitting.
2486 if (getStage(VirtReg) < RS_Split2) {
2487 MCRegister PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs);
2488 if (PhysReg || !NewVRegs.empty())
2489 return PhysReg;
2490 }
2491
2492 // Then isolate blocks.
2493 return tryBlockSplit(VirtReg, Order, NewVRegs);
2494 }
2495
2496 //===----------------------------------------------------------------------===//
2497 // Last Chance Recoloring
2498 //===----------------------------------------------------------------------===//
2499
2500 /// Return true if \p reg has any tied def operand.
hasTiedDef(MachineRegisterInfo * MRI,unsigned reg)2501 static bool hasTiedDef(MachineRegisterInfo *MRI, unsigned reg) {
2502 for (const MachineOperand &MO : MRI->def_operands(reg))
2503 if (MO.isTied())
2504 return true;
2505
2506 return false;
2507 }
2508
2509 /// mayRecolorAllInterferences - Check if the virtual registers that
2510 /// interfere with \p VirtReg on \p PhysReg (or one of its aliases) may be
2511 /// recolored to free \p PhysReg.
2512 /// When true is returned, \p RecoloringCandidates has been augmented with all
2513 /// the live intervals that need to be recolored in order to free \p PhysReg
2514 /// for \p VirtReg.
2515 /// \p FixedRegisters contains all the virtual registers that cannot be
2516 /// recolored.
mayRecolorAllInterferences(MCRegister PhysReg,LiveInterval & VirtReg,SmallLISet & RecoloringCandidates,const SmallVirtRegSet & FixedRegisters)2517 bool RAGreedy::mayRecolorAllInterferences(
2518 MCRegister PhysReg, LiveInterval &VirtReg, SmallLISet &RecoloringCandidates,
2519 const SmallVirtRegSet &FixedRegisters) {
2520 const TargetRegisterClass *CurRC = MRI->getRegClass(VirtReg.reg());
2521
2522 for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
2523 LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units);
2524 // If there is LastChanceRecoloringMaxInterference or more interferences,
2525 // chances are one would not be recolorable.
2526 if (Q.collectInterferingVRegs(LastChanceRecoloringMaxInterference) >=
2527 LastChanceRecoloringMaxInterference && !ExhaustiveSearch) {
2528 LLVM_DEBUG(dbgs() << "Early abort: too many interferences.\n");
2529 CutOffInfo |= CO_Interf;
2530 return false;
2531 }
2532 for (LiveInterval *Intf : reverse(Q.interferingVRegs())) {
2533 // If Intf is done and sit on the same register class as VirtReg,
2534 // it would not be recolorable as it is in the same state as VirtReg.
2535 // However, if VirtReg has tied defs and Intf doesn't, then
2536 // there is still a point in examining if it can be recolorable.
2537 if (((getStage(*Intf) == RS_Done &&
2538 MRI->getRegClass(Intf->reg()) == CurRC) &&
2539 !(hasTiedDef(MRI, VirtReg.reg()) &&
2540 !hasTiedDef(MRI, Intf->reg()))) ||
2541 FixedRegisters.count(Intf->reg())) {
2542 LLVM_DEBUG(
2543 dbgs() << "Early abort: the interference is not recolorable.\n");
2544 return false;
2545 }
2546 RecoloringCandidates.insert(Intf);
2547 }
2548 }
2549 return true;
2550 }
2551
2552 /// tryLastChanceRecoloring - Try to assign a color to \p VirtReg by recoloring
2553 /// its interferences.
2554 /// Last chance recoloring chooses a color for \p VirtReg and recolors every
2555 /// virtual register that was using it. The recoloring process may recursively
2556 /// use the last chance recoloring. Therefore, when a virtual register has been
2557 /// assigned a color by this mechanism, it is marked as Fixed, i.e., it cannot
2558 /// be last-chance-recolored again during this recoloring "session".
2559 /// E.g.,
2560 /// Let
2561 /// vA can use {R1, R2 }
2562 /// vB can use { R2, R3}
2563 /// vC can use {R1 }
2564 /// Where vA, vB, and vC cannot be split anymore (they are reloads for
2565 /// instance) and they all interfere.
2566 ///
2567 /// vA is assigned R1
2568 /// vB is assigned R2
2569 /// vC tries to evict vA but vA is already done.
2570 /// Regular register allocation fails.
2571 ///
2572 /// Last chance recoloring kicks in:
2573 /// vC does as if vA was evicted => vC uses R1.
2574 /// vC is marked as fixed.
2575 /// vA needs to find a color.
2576 /// None are available.
2577 /// vA cannot evict vC: vC is a fixed virtual register now.
2578 /// vA does as if vB was evicted => vA uses R2.
2579 /// vB needs to find a color.
2580 /// R3 is available.
2581 /// Recoloring => vC = R1, vA = R2, vB = R3
2582 ///
2583 /// \p Order defines the preferred allocation order for \p VirtReg.
2584 /// \p NewRegs will contain any new virtual register that have been created
2585 /// (split, spill) during the process and that must be assigned.
2586 /// \p FixedRegisters contains all the virtual registers that cannot be
2587 /// recolored.
2588 /// \p Depth gives the current depth of the last chance recoloring.
2589 /// \return a physical register that can be used for VirtReg or ~0u if none
2590 /// exists.
tryLastChanceRecoloring(LiveInterval & VirtReg,AllocationOrder & Order,SmallVectorImpl<Register> & NewVRegs,SmallVirtRegSet & FixedRegisters,unsigned Depth)2591 unsigned RAGreedy::tryLastChanceRecoloring(LiveInterval &VirtReg,
2592 AllocationOrder &Order,
2593 SmallVectorImpl<Register> &NewVRegs,
2594 SmallVirtRegSet &FixedRegisters,
2595 unsigned Depth) {
2596 if (!TRI->shouldUseLastChanceRecoloringForVirtReg(*MF, VirtReg))
2597 return ~0u;
2598
2599 LLVM_DEBUG(dbgs() << "Try last chance recoloring for " << VirtReg << '\n');
2600 // Ranges must be Done.
2601 assert((getStage(VirtReg) >= RS_Done || !VirtReg.isSpillable()) &&
2602 "Last chance recoloring should really be last chance");
2603 // Set the max depth to LastChanceRecoloringMaxDepth.
2604 // We may want to reconsider that if we end up with a too large search space
2605 // for target with hundreds of registers.
2606 // Indeed, in that case we may want to cut the search space earlier.
2607 if (Depth >= LastChanceRecoloringMaxDepth && !ExhaustiveSearch) {
2608 LLVM_DEBUG(dbgs() << "Abort because max depth has been reached.\n");
2609 CutOffInfo |= CO_Depth;
2610 return ~0u;
2611 }
2612
2613 // Set of Live intervals that will need to be recolored.
2614 SmallLISet RecoloringCandidates;
2615 // Record the original mapping virtual register to physical register in case
2616 // the recoloring fails.
2617 DenseMap<Register, MCRegister> VirtRegToPhysReg;
2618 // Mark VirtReg as fixed, i.e., it will not be recolored pass this point in
2619 // this recoloring "session".
2620 assert(!FixedRegisters.count(VirtReg.reg()));
2621 FixedRegisters.insert(VirtReg.reg());
2622 SmallVector<Register, 4> CurrentNewVRegs;
2623
2624 for (MCRegister PhysReg : Order) {
2625 assert(PhysReg.isValid());
2626 LLVM_DEBUG(dbgs() << "Try to assign: " << VirtReg << " to "
2627 << printReg(PhysReg, TRI) << '\n');
2628 RecoloringCandidates.clear();
2629 VirtRegToPhysReg.clear();
2630 CurrentNewVRegs.clear();
2631
2632 // It is only possible to recolor virtual register interference.
2633 if (Matrix->checkInterference(VirtReg, PhysReg) >
2634 LiveRegMatrix::IK_VirtReg) {
2635 LLVM_DEBUG(
2636 dbgs() << "Some interferences are not with virtual registers.\n");
2637
2638 continue;
2639 }
2640
2641 // Early give up on this PhysReg if it is obvious we cannot recolor all
2642 // the interferences.
2643 if (!mayRecolorAllInterferences(PhysReg, VirtReg, RecoloringCandidates,
2644 FixedRegisters)) {
2645 LLVM_DEBUG(dbgs() << "Some interferences cannot be recolored.\n");
2646 continue;
2647 }
2648
2649 // RecoloringCandidates contains all the virtual registers that interfer
2650 // with VirtReg on PhysReg (or one of its aliases).
2651 // Enqueue them for recoloring and perform the actual recoloring.
2652 PQueue RecoloringQueue;
2653 for (SmallLISet::iterator It = RecoloringCandidates.begin(),
2654 EndIt = RecoloringCandidates.end();
2655 It != EndIt; ++It) {
2656 Register ItVirtReg = (*It)->reg();
2657 enqueue(RecoloringQueue, *It);
2658 assert(VRM->hasPhys(ItVirtReg) &&
2659 "Interferences are supposed to be with allocated variables");
2660
2661 // Record the current allocation.
2662 VirtRegToPhysReg[ItVirtReg] = VRM->getPhys(ItVirtReg);
2663 // unset the related struct.
2664 Matrix->unassign(**It);
2665 }
2666
2667 // Do as if VirtReg was assigned to PhysReg so that the underlying
2668 // recoloring has the right information about the interferes and
2669 // available colors.
2670 Matrix->assign(VirtReg, PhysReg);
2671
2672 // Save the current recoloring state.
2673 // If we cannot recolor all the interferences, we will have to start again
2674 // at this point for the next physical register.
2675 SmallVirtRegSet SaveFixedRegisters(FixedRegisters);
2676 if (tryRecoloringCandidates(RecoloringQueue, CurrentNewVRegs,
2677 FixedRegisters, Depth)) {
2678 // Push the queued vregs into the main queue.
2679 for (Register NewVReg : CurrentNewVRegs)
2680 NewVRegs.push_back(NewVReg);
2681 // Do not mess up with the global assignment process.
2682 // I.e., VirtReg must be unassigned.
2683 Matrix->unassign(VirtReg);
2684 return PhysReg;
2685 }
2686
2687 LLVM_DEBUG(dbgs() << "Fail to assign: " << VirtReg << " to "
2688 << printReg(PhysReg, TRI) << '\n');
2689
2690 // The recoloring attempt failed, undo the changes.
2691 FixedRegisters = SaveFixedRegisters;
2692 Matrix->unassign(VirtReg);
2693
2694 // For a newly created vreg which is also in RecoloringCandidates,
2695 // don't add it to NewVRegs because its physical register will be restored
2696 // below. Other vregs in CurrentNewVRegs are created by calling
2697 // selectOrSplit and should be added into NewVRegs.
2698 for (SmallVectorImpl<Register>::iterator Next = CurrentNewVRegs.begin(),
2699 End = CurrentNewVRegs.end();
2700 Next != End; ++Next) {
2701 if (RecoloringCandidates.count(&LIS->getInterval(*Next)))
2702 continue;
2703 NewVRegs.push_back(*Next);
2704 }
2705
2706 for (SmallLISet::iterator It = RecoloringCandidates.begin(),
2707 EndIt = RecoloringCandidates.end();
2708 It != EndIt; ++It) {
2709 Register ItVirtReg = (*It)->reg();
2710 if (VRM->hasPhys(ItVirtReg))
2711 Matrix->unassign(**It);
2712 MCRegister ItPhysReg = VirtRegToPhysReg[ItVirtReg];
2713 Matrix->assign(**It, ItPhysReg);
2714 }
2715 }
2716
2717 // Last chance recoloring did not worked either, give up.
2718 return ~0u;
2719 }
2720
2721 /// tryRecoloringCandidates - Try to assign a new color to every register
2722 /// in \RecoloringQueue.
2723 /// \p NewRegs will contain any new virtual register created during the
2724 /// recoloring process.
2725 /// \p FixedRegisters[in/out] contains all the registers that have been
2726 /// recolored.
2727 /// \return true if all virtual registers in RecoloringQueue were successfully
2728 /// recolored, false otherwise.
tryRecoloringCandidates(PQueue & RecoloringQueue,SmallVectorImpl<Register> & NewVRegs,SmallVirtRegSet & FixedRegisters,unsigned Depth)2729 bool RAGreedy::tryRecoloringCandidates(PQueue &RecoloringQueue,
2730 SmallVectorImpl<Register> &NewVRegs,
2731 SmallVirtRegSet &FixedRegisters,
2732 unsigned Depth) {
2733 while (!RecoloringQueue.empty()) {
2734 LiveInterval *LI = dequeue(RecoloringQueue);
2735 LLVM_DEBUG(dbgs() << "Try to recolor: " << *LI << '\n');
2736 MCRegister PhysReg =
2737 selectOrSplitImpl(*LI, NewVRegs, FixedRegisters, Depth + 1);
2738 // When splitting happens, the live-range may actually be empty.
2739 // In that case, this is okay to continue the recoloring even
2740 // if we did not find an alternative color for it. Indeed,
2741 // there will not be anything to color for LI in the end.
2742 if (PhysReg == ~0u || (!PhysReg && !LI->empty()))
2743 return false;
2744
2745 if (!PhysReg) {
2746 assert(LI->empty() && "Only empty live-range do not require a register");
2747 LLVM_DEBUG(dbgs() << "Recoloring of " << *LI
2748 << " succeeded. Empty LI.\n");
2749 continue;
2750 }
2751 LLVM_DEBUG(dbgs() << "Recoloring of " << *LI
2752 << " succeeded with: " << printReg(PhysReg, TRI) << '\n');
2753
2754 Matrix->assign(*LI, PhysReg);
2755 FixedRegisters.insert(LI->reg());
2756 }
2757 return true;
2758 }
2759
2760 //===----------------------------------------------------------------------===//
2761 // Main Entry Point
2762 //===----------------------------------------------------------------------===//
2763
selectOrSplit(LiveInterval & VirtReg,SmallVectorImpl<Register> & NewVRegs)2764 MCRegister RAGreedy::selectOrSplit(LiveInterval &VirtReg,
2765 SmallVectorImpl<Register> &NewVRegs) {
2766 CutOffInfo = CO_None;
2767 LLVMContext &Ctx = MF->getFunction().getContext();
2768 SmallVirtRegSet FixedRegisters;
2769 MCRegister Reg = selectOrSplitImpl(VirtReg, NewVRegs, FixedRegisters);
2770 if (Reg == ~0U && (CutOffInfo != CO_None)) {
2771 uint8_t CutOffEncountered = CutOffInfo & (CO_Depth | CO_Interf);
2772 if (CutOffEncountered == CO_Depth)
2773 Ctx.emitError("register allocation failed: maximum depth for recoloring "
2774 "reached. Use -fexhaustive-register-search to skip "
2775 "cutoffs");
2776 else if (CutOffEncountered == CO_Interf)
2777 Ctx.emitError("register allocation failed: maximum interference for "
2778 "recoloring reached. Use -fexhaustive-register-search "
2779 "to skip cutoffs");
2780 else if (CutOffEncountered == (CO_Depth | CO_Interf))
2781 Ctx.emitError("register allocation failed: maximum interference and "
2782 "depth for recoloring reached. Use "
2783 "-fexhaustive-register-search to skip cutoffs");
2784 }
2785 return Reg;
2786 }
2787
2788 /// Using a CSR for the first time has a cost because it causes push|pop
2789 /// to be added to prologue|epilogue. Splitting a cold section of the live
2790 /// range can have lower cost than using the CSR for the first time;
2791 /// Spilling a live range in the cold path can have lower cost than using
2792 /// the CSR for the first time. Returns the physical register if we decide
2793 /// to use the CSR; otherwise return 0.
2794 MCRegister
tryAssignCSRFirstTime(LiveInterval & VirtReg,AllocationOrder & Order,MCRegister PhysReg,unsigned & CostPerUseLimit,SmallVectorImpl<Register> & NewVRegs)2795 RAGreedy::tryAssignCSRFirstTime(LiveInterval &VirtReg, AllocationOrder &Order,
2796 MCRegister PhysReg, unsigned &CostPerUseLimit,
2797 SmallVectorImpl<Register> &NewVRegs) {
2798 if (getStage(VirtReg) == RS_Spill && VirtReg.isSpillable()) {
2799 // We choose spill over using the CSR for the first time if the spill cost
2800 // is lower than CSRCost.
2801 SA->analyze(&VirtReg);
2802 if (calcSpillCost() >= CSRCost)
2803 return PhysReg;
2804
2805 // We are going to spill, set CostPerUseLimit to 1 to make sure that
2806 // we will not use a callee-saved register in tryEvict.
2807 CostPerUseLimit = 1;
2808 return 0;
2809 }
2810 if (getStage(VirtReg) < RS_Split) {
2811 // We choose pre-splitting over using the CSR for the first time if
2812 // the cost of splitting is lower than CSRCost.
2813 SA->analyze(&VirtReg);
2814 unsigned NumCands = 0;
2815 BlockFrequency BestCost = CSRCost; // Don't modify CSRCost.
2816 unsigned BestCand = calculateRegionSplitCost(VirtReg, Order, BestCost,
2817 NumCands, true /*IgnoreCSR*/);
2818 if (BestCand == NoCand)
2819 // Use the CSR if we can't find a region split below CSRCost.
2820 return PhysReg;
2821
2822 // Perform the actual pre-splitting.
2823 doRegionSplit(VirtReg, BestCand, false/*HasCompact*/, NewVRegs);
2824 return 0;
2825 }
2826 return PhysReg;
2827 }
2828
aboutToRemoveInterval(LiveInterval & LI)2829 void RAGreedy::aboutToRemoveInterval(LiveInterval &LI) {
2830 // Do not keep invalid information around.
2831 SetOfBrokenHints.remove(&LI);
2832 }
2833
initializeCSRCost()2834 void RAGreedy::initializeCSRCost() {
2835 // We use the larger one out of the command-line option and the value report
2836 // by TRI.
2837 CSRCost = BlockFrequency(
2838 std::max((unsigned)CSRFirstTimeCost, TRI->getCSRFirstUseCost()));
2839 if (!CSRCost.getFrequency())
2840 return;
2841
2842 // Raw cost is relative to Entry == 2^14; scale it appropriately.
2843 uint64_t ActualEntry = MBFI->getEntryFreq();
2844 if (!ActualEntry) {
2845 CSRCost = 0;
2846 return;
2847 }
2848 uint64_t FixedEntry = 1 << 14;
2849 if (ActualEntry < FixedEntry)
2850 CSRCost *= BranchProbability(ActualEntry, FixedEntry);
2851 else if (ActualEntry <= UINT32_MAX)
2852 // Invert the fraction and divide.
2853 CSRCost /= BranchProbability(FixedEntry, ActualEntry);
2854 else
2855 // Can't use BranchProbability in general, since it takes 32-bit numbers.
2856 CSRCost = CSRCost.getFrequency() * (ActualEntry / FixedEntry);
2857 }
2858
2859 /// Collect the hint info for \p Reg.
2860 /// The results are stored into \p Out.
2861 /// \p Out is not cleared before being populated.
collectHintInfo(Register Reg,HintsInfo & Out)2862 void RAGreedy::collectHintInfo(Register Reg, HintsInfo &Out) {
2863 for (const MachineInstr &Instr : MRI->reg_nodbg_instructions(Reg)) {
2864 if (!Instr.isFullCopy())
2865 continue;
2866 // Look for the other end of the copy.
2867 Register OtherReg = Instr.getOperand(0).getReg();
2868 if (OtherReg == Reg) {
2869 OtherReg = Instr.getOperand(1).getReg();
2870 if (OtherReg == Reg)
2871 continue;
2872 }
2873 // Get the current assignment.
2874 MCRegister OtherPhysReg =
2875 OtherReg.isPhysical() ? OtherReg.asMCReg() : VRM->getPhys(OtherReg);
2876 // Push the collected information.
2877 Out.push_back(HintInfo(MBFI->getBlockFreq(Instr.getParent()), OtherReg,
2878 OtherPhysReg));
2879 }
2880 }
2881
2882 /// Using the given \p List, compute the cost of the broken hints if
2883 /// \p PhysReg was used.
2884 /// \return The cost of \p List for \p PhysReg.
getBrokenHintFreq(const HintsInfo & List,MCRegister PhysReg)2885 BlockFrequency RAGreedy::getBrokenHintFreq(const HintsInfo &List,
2886 MCRegister PhysReg) {
2887 BlockFrequency Cost = 0;
2888 for (const HintInfo &Info : List) {
2889 if (Info.PhysReg != PhysReg)
2890 Cost += Info.Freq;
2891 }
2892 return Cost;
2893 }
2894
2895 /// Using the register assigned to \p VirtReg, try to recolor
2896 /// all the live ranges that are copy-related with \p VirtReg.
2897 /// The recoloring is then propagated to all the live-ranges that have
2898 /// been recolored and so on, until no more copies can be coalesced or
2899 /// it is not profitable.
2900 /// For a given live range, profitability is determined by the sum of the
2901 /// frequencies of the non-identity copies it would introduce with the old
2902 /// and new register.
tryHintRecoloring(LiveInterval & VirtReg)2903 void RAGreedy::tryHintRecoloring(LiveInterval &VirtReg) {
2904 // We have a broken hint, check if it is possible to fix it by
2905 // reusing PhysReg for the copy-related live-ranges. Indeed, we evicted
2906 // some register and PhysReg may be available for the other live-ranges.
2907 SmallSet<Register, 4> Visited;
2908 SmallVector<unsigned, 2> RecoloringCandidates;
2909 HintsInfo Info;
2910 Register Reg = VirtReg.reg();
2911 MCRegister PhysReg = VRM->getPhys(Reg);
2912 // Start the recoloring algorithm from the input live-interval, then
2913 // it will propagate to the ones that are copy-related with it.
2914 Visited.insert(Reg);
2915 RecoloringCandidates.push_back(Reg);
2916
2917 LLVM_DEBUG(dbgs() << "Trying to reconcile hints for: " << printReg(Reg, TRI)
2918 << '(' << printReg(PhysReg, TRI) << ")\n");
2919
2920 do {
2921 Reg = RecoloringCandidates.pop_back_val();
2922
2923 // We cannot recolor physical register.
2924 if (Register::isPhysicalRegister(Reg))
2925 continue;
2926
2927 assert(VRM->hasPhys(Reg) && "We have unallocated variable!!");
2928
2929 // Get the live interval mapped with this virtual register to be able
2930 // to check for the interference with the new color.
2931 LiveInterval &LI = LIS->getInterval(Reg);
2932 MCRegister CurrPhys = VRM->getPhys(Reg);
2933 // Check that the new color matches the register class constraints and
2934 // that it is free for this live range.
2935 if (CurrPhys != PhysReg && (!MRI->getRegClass(Reg)->contains(PhysReg) ||
2936 Matrix->checkInterference(LI, PhysReg)))
2937 continue;
2938
2939 LLVM_DEBUG(dbgs() << printReg(Reg, TRI) << '(' << printReg(CurrPhys, TRI)
2940 << ") is recolorable.\n");
2941
2942 // Gather the hint info.
2943 Info.clear();
2944 collectHintInfo(Reg, Info);
2945 // Check if recoloring the live-range will increase the cost of the
2946 // non-identity copies.
2947 if (CurrPhys != PhysReg) {
2948 LLVM_DEBUG(dbgs() << "Checking profitability:\n");
2949 BlockFrequency OldCopiesCost = getBrokenHintFreq(Info, CurrPhys);
2950 BlockFrequency NewCopiesCost = getBrokenHintFreq(Info, PhysReg);
2951 LLVM_DEBUG(dbgs() << "Old Cost: " << OldCopiesCost.getFrequency()
2952 << "\nNew Cost: " << NewCopiesCost.getFrequency()
2953 << '\n');
2954 if (OldCopiesCost < NewCopiesCost) {
2955 LLVM_DEBUG(dbgs() << "=> Not profitable.\n");
2956 continue;
2957 }
2958 // At this point, the cost is either cheaper or equal. If it is
2959 // equal, we consider this is profitable because it may expose
2960 // more recoloring opportunities.
2961 LLVM_DEBUG(dbgs() << "=> Profitable.\n");
2962 // Recolor the live-range.
2963 Matrix->unassign(LI);
2964 Matrix->assign(LI, PhysReg);
2965 }
2966 // Push all copy-related live-ranges to keep reconciling the broken
2967 // hints.
2968 for (const HintInfo &HI : Info) {
2969 if (Visited.insert(HI.Reg).second)
2970 RecoloringCandidates.push_back(HI.Reg);
2971 }
2972 } while (!RecoloringCandidates.empty());
2973 }
2974
2975 /// Try to recolor broken hints.
2976 /// Broken hints may be repaired by recoloring when an evicted variable
2977 /// freed up a register for a larger live-range.
2978 /// Consider the following example:
2979 /// BB1:
2980 /// a =
2981 /// b =
2982 /// BB2:
2983 /// ...
2984 /// = b
2985 /// = a
2986 /// Let us assume b gets split:
2987 /// BB1:
2988 /// a =
2989 /// b =
2990 /// BB2:
2991 /// c = b
2992 /// ...
2993 /// d = c
2994 /// = d
2995 /// = a
2996 /// Because of how the allocation work, b, c, and d may be assigned different
2997 /// colors. Now, if a gets evicted later:
2998 /// BB1:
2999 /// a =
3000 /// st a, SpillSlot
3001 /// b =
3002 /// BB2:
3003 /// c = b
3004 /// ...
3005 /// d = c
3006 /// = d
3007 /// e = ld SpillSlot
3008 /// = e
3009 /// This is likely that we can assign the same register for b, c, and d,
3010 /// getting rid of 2 copies.
tryHintsRecoloring()3011 void RAGreedy::tryHintsRecoloring() {
3012 for (LiveInterval *LI : SetOfBrokenHints) {
3013 assert(Register::isVirtualRegister(LI->reg()) &&
3014 "Recoloring is possible only for virtual registers");
3015 // Some dead defs may be around (e.g., because of debug uses).
3016 // Ignore those.
3017 if (!VRM->hasPhys(LI->reg()))
3018 continue;
3019 tryHintRecoloring(*LI);
3020 }
3021 }
3022
selectOrSplitImpl(LiveInterval & VirtReg,SmallVectorImpl<Register> & NewVRegs,SmallVirtRegSet & FixedRegisters,unsigned Depth)3023 MCRegister RAGreedy::selectOrSplitImpl(LiveInterval &VirtReg,
3024 SmallVectorImpl<Register> &NewVRegs,
3025 SmallVirtRegSet &FixedRegisters,
3026 unsigned Depth) {
3027 unsigned CostPerUseLimit = ~0u;
3028 // First try assigning a free register.
3029 auto Order =
3030 AllocationOrder::create(VirtReg.reg(), *VRM, RegClassInfo, Matrix);
3031 if (MCRegister PhysReg =
3032 tryAssign(VirtReg, Order, NewVRegs, FixedRegisters)) {
3033 // If VirtReg got an assignment, the eviction info is no longre relevant.
3034 LastEvicted.clearEvicteeInfo(VirtReg.reg());
3035 // When NewVRegs is not empty, we may have made decisions such as evicting
3036 // a virtual register, go with the earlier decisions and use the physical
3037 // register.
3038 if (CSRCost.getFrequency() && isUnusedCalleeSavedReg(PhysReg) &&
3039 NewVRegs.empty()) {
3040 MCRegister CSRReg = tryAssignCSRFirstTime(VirtReg, Order, PhysReg,
3041 CostPerUseLimit, NewVRegs);
3042 if (CSRReg || !NewVRegs.empty())
3043 // Return now if we decide to use a CSR or create new vregs due to
3044 // pre-splitting.
3045 return CSRReg;
3046 } else
3047 return PhysReg;
3048 }
3049
3050 LiveRangeStage Stage = getStage(VirtReg);
3051 LLVM_DEBUG(dbgs() << StageName[Stage] << " Cascade "
3052 << ExtraRegInfo[VirtReg.reg()].Cascade << '\n');
3053
3054 // Try to evict a less worthy live range, but only for ranges from the primary
3055 // queue. The RS_Split ranges already failed to do this, and they should not
3056 // get a second chance until they have been split.
3057 if (Stage != RS_Split)
3058 if (Register PhysReg =
3059 tryEvict(VirtReg, Order, NewVRegs, CostPerUseLimit,
3060 FixedRegisters)) {
3061 Register Hint = MRI->getSimpleHint(VirtReg.reg());
3062 // If VirtReg has a hint and that hint is broken record this
3063 // virtual register as a recoloring candidate for broken hint.
3064 // Indeed, since we evicted a variable in its neighborhood it is
3065 // likely we can at least partially recolor some of the
3066 // copy-related live-ranges.
3067 if (Hint && Hint != PhysReg)
3068 SetOfBrokenHints.insert(&VirtReg);
3069 // If VirtReg eviction someone, the eviction info for it as an evictee is
3070 // no longre relevant.
3071 LastEvicted.clearEvicteeInfo(VirtReg.reg());
3072 return PhysReg;
3073 }
3074
3075 assert((NewVRegs.empty() || Depth) && "Cannot append to existing NewVRegs");
3076
3077 // The first time we see a live range, don't try to split or spill.
3078 // Wait until the second time, when all smaller ranges have been allocated.
3079 // This gives a better picture of the interference to split around.
3080 if (Stage < RS_Split) {
3081 setStage(VirtReg, RS_Split);
3082 LLVM_DEBUG(dbgs() << "wait for second round\n");
3083 NewVRegs.push_back(VirtReg.reg());
3084 return 0;
3085 }
3086
3087 if (Stage < RS_Spill) {
3088 // Try splitting VirtReg or interferences.
3089 unsigned NewVRegSizeBefore = NewVRegs.size();
3090 Register PhysReg = trySplit(VirtReg, Order, NewVRegs, FixedRegisters);
3091 if (PhysReg || (NewVRegs.size() - NewVRegSizeBefore)) {
3092 // If VirtReg got split, the eviction info is no longer relevant.
3093 LastEvicted.clearEvicteeInfo(VirtReg.reg());
3094 return PhysReg;
3095 }
3096 }
3097
3098 // If we couldn't allocate a register from spilling, there is probably some
3099 // invalid inline assembly. The base class will report it.
3100 if (Stage >= RS_Done || !VirtReg.isSpillable())
3101 return tryLastChanceRecoloring(VirtReg, Order, NewVRegs, FixedRegisters,
3102 Depth);
3103
3104 // Finally spill VirtReg itself.
3105 if ((EnableDeferredSpilling ||
3106 TRI->shouldUseDeferredSpillingForVirtReg(*MF, VirtReg)) &&
3107 getStage(VirtReg) < RS_Memory) {
3108 // TODO: This is experimental and in particular, we do not model
3109 // the live range splitting done by spilling correctly.
3110 // We would need a deep integration with the spiller to do the
3111 // right thing here. Anyway, that is still good for early testing.
3112 setStage(VirtReg, RS_Memory);
3113 LLVM_DEBUG(dbgs() << "Do as if this register is in memory\n");
3114 NewVRegs.push_back(VirtReg.reg());
3115 } else {
3116 NamedRegionTimer T("spill", "Spiller", TimerGroupName,
3117 TimerGroupDescription, TimePassesIsEnabled);
3118 LiveRangeEdit LRE(&VirtReg, NewVRegs, *MF, *LIS, VRM, this, &DeadRemats);
3119 spiller().spill(LRE);
3120 setStage(NewVRegs.begin(), NewVRegs.end(), RS_Done);
3121
3122 // Tell LiveDebugVariables about the new ranges. Ranges not being covered by
3123 // the new regs are kept in LDV (still mapping to the old register), until
3124 // we rewrite spilled locations in LDV at a later stage.
3125 DebugVars->splitRegister(VirtReg.reg(), LRE.regs(), *LIS);
3126
3127 if (VerifyEnabled)
3128 MF->verify(this, "After spilling");
3129 }
3130
3131 // The live virtual register requesting allocation was spilled, so tell
3132 // the caller not to allocate anything during this round.
3133 return 0;
3134 }
3135
reportNumberOfSplillsReloads(MachineLoop * L,unsigned & Reloads,unsigned & FoldedReloads,unsigned & Spills,unsigned & FoldedSpills)3136 void RAGreedy::reportNumberOfSplillsReloads(MachineLoop *L, unsigned &Reloads,
3137 unsigned &FoldedReloads,
3138 unsigned &Spills,
3139 unsigned &FoldedSpills) {
3140 Reloads = 0;
3141 FoldedReloads = 0;
3142 Spills = 0;
3143 FoldedSpills = 0;
3144
3145 // Sum up the spill and reloads in subloops.
3146 for (MachineLoop *SubLoop : *L) {
3147 unsigned SubReloads;
3148 unsigned SubFoldedReloads;
3149 unsigned SubSpills;
3150 unsigned SubFoldedSpills;
3151
3152 reportNumberOfSplillsReloads(SubLoop, SubReloads, SubFoldedReloads,
3153 SubSpills, SubFoldedSpills);
3154 Reloads += SubReloads;
3155 FoldedReloads += SubFoldedReloads;
3156 Spills += SubSpills;
3157 FoldedSpills += SubFoldedSpills;
3158 }
3159
3160 const MachineFrameInfo &MFI = MF->getFrameInfo();
3161 int FI;
3162
3163 for (MachineBasicBlock *MBB : L->getBlocks())
3164 // Handle blocks that were not included in subloops.
3165 if (Loops->getLoopFor(MBB) == L)
3166 for (MachineInstr &MI : *MBB) {
3167 SmallVector<const MachineMemOperand *, 2> Accesses;
3168 auto isSpillSlotAccess = [&MFI](const MachineMemOperand *A) {
3169 return MFI.isSpillSlotObjectIndex(
3170 cast<FixedStackPseudoSourceValue>(A->getPseudoValue())
3171 ->getFrameIndex());
3172 };
3173
3174 if (TII->isLoadFromStackSlot(MI, FI) && MFI.isSpillSlotObjectIndex(FI))
3175 ++Reloads;
3176 else if (TII->hasLoadFromStackSlot(MI, Accesses) &&
3177 llvm::any_of(Accesses, isSpillSlotAccess))
3178 ++FoldedReloads;
3179 else if (TII->isStoreToStackSlot(MI, FI) &&
3180 MFI.isSpillSlotObjectIndex(FI))
3181 ++Spills;
3182 else if (TII->hasStoreToStackSlot(MI, Accesses) &&
3183 llvm::any_of(Accesses, isSpillSlotAccess))
3184 ++FoldedSpills;
3185 }
3186
3187 if (Reloads || FoldedReloads || Spills || FoldedSpills) {
3188 using namespace ore;
3189
3190 ORE->emit([&]() {
3191 MachineOptimizationRemarkMissed R(DEBUG_TYPE, "LoopSpillReload",
3192 L->getStartLoc(), L->getHeader());
3193 if (Spills)
3194 R << NV("NumSpills", Spills) << " spills ";
3195 if (FoldedSpills)
3196 R << NV("NumFoldedSpills", FoldedSpills) << " folded spills ";
3197 if (Reloads)
3198 R << NV("NumReloads", Reloads) << " reloads ";
3199 if (FoldedReloads)
3200 R << NV("NumFoldedReloads", FoldedReloads) << " folded reloads ";
3201 R << "generated in loop";
3202 return R;
3203 });
3204 }
3205 }
3206
runOnMachineFunction(MachineFunction & mf)3207 bool RAGreedy::runOnMachineFunction(MachineFunction &mf) {
3208 LLVM_DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n"
3209 << "********** Function: " << mf.getName() << '\n');
3210
3211 MF = &mf;
3212 TRI = MF->getSubtarget().getRegisterInfo();
3213 TII = MF->getSubtarget().getInstrInfo();
3214 RCI.runOnMachineFunction(mf);
3215
3216 EnableLocalReassign = EnableLocalReassignment ||
3217 MF->getSubtarget().enableRALocalReassignment(
3218 MF->getTarget().getOptLevel());
3219
3220 EnableAdvancedRASplitCost =
3221 ConsiderLocalIntervalCost.getNumOccurrences()
3222 ? ConsiderLocalIntervalCost
3223 : MF->getSubtarget().enableAdvancedRASplitCost();
3224
3225 if (VerifyEnabled)
3226 MF->verify(this, "Before greedy register allocator");
3227
3228 RegAllocBase::init(getAnalysis<VirtRegMap>(),
3229 getAnalysis<LiveIntervals>(),
3230 getAnalysis<LiveRegMatrix>());
3231 Indexes = &getAnalysis<SlotIndexes>();
3232 MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
3233 DomTree = &getAnalysis<MachineDominatorTree>();
3234 ORE = &getAnalysis<MachineOptimizationRemarkEmitterPass>().getORE();
3235 SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM));
3236 Loops = &getAnalysis<MachineLoopInfo>();
3237 Bundles = &getAnalysis<EdgeBundles>();
3238 SpillPlacer = &getAnalysis<SpillPlacement>();
3239 DebugVars = &getAnalysis<LiveDebugVariables>();
3240 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
3241
3242 initializeCSRCost();
3243
3244 VRAI = std::make_unique<VirtRegAuxInfo>(*MF, *LIS, *VRM, *Loops, *MBFI);
3245
3246 VRAI->calculateSpillWeightsAndHints();
3247
3248 LLVM_DEBUG(LIS->dump());
3249
3250 SA.reset(new SplitAnalysis(*VRM, *LIS, *Loops));
3251 SE.reset(new SplitEditor(*SA, *AA, *LIS, *VRM, *DomTree, *MBFI));
3252 ExtraRegInfo.clear();
3253 ExtraRegInfo.resize(MRI->getNumVirtRegs());
3254 NextCascade = 1;
3255 IntfCache.init(MF, Matrix->getLiveUnions(), Indexes, LIS, TRI);
3256 GlobalCand.resize(32); // This will grow as needed.
3257 SetOfBrokenHints.clear();
3258 LastEvicted.clear();
3259
3260 allocatePhysRegs();
3261 tryHintsRecoloring();
3262 postOptimization();
3263 reportNumberOfSplillsReloads();
3264
3265 releaseMemory();
3266 return true;
3267 }
3268