Coverage Report

Created: 2019-07-24 05:18

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