llvm.org GIT mirror llvm / eaa7353 lib / CodeGen / SplitKit.h
eaa7353

Tree @eaa7353 (Download .tar.gz)

SplitKit.h @eaa7353

7cf6af5
8ae0263
 
 
 
 
 
 
 
 
 
 
 
 
00e08fc
 
6796e4f
b5a457c
db529a8
7cf6af5
8ae0263
815b02e
0f43811
7cf6af5
8d0963f
7cf6af5
 
5bcb2da
7cf6af5
 
 
 
 
 
8ae0263
 
 
 
a17768f
4eed756
7cf6af5
8ae0263
f017900
6a0dc07
cfa7134
f017900
8ae0263
723d45a
 
 
 
 
 
 
 
 
 
 
 
14a29ca
 
723d45a
 
 
 
14a29ca
 
 
723d45a
 
 
 
 
14a29ca
723d45a
 
14a29ca
 
 
5bcb2da
 
 
 
 
 
 
 
 
 
 
 
723d45a
 
f017900
 
b453775
08e93b1
0786284
1b847de
0786284
 
 
8ae0263
f0ac26c
 
 
 
 
 
a2e79ef
f0ac26c
a2e79ef
 
 
 
 
 
 
 
f0ac26c
 
 
fe62d92
 
77ee114
f0ac26c
 
87360f7
 
 
 
fe62d92
87360f7
f0ac26c
 
f1b05f2
 
7cf6af5
f1b05f2
723d45a
 
 
b20b518
 
 
db529a8
 
 
a2e79ef
 
 
 
db529a8
f4afdfc
 
 
 
db529a8
7d6b6a0
 
 
0786284
abff280
8ae0263
f0ac26c
2b0f9e7
f0ac26c
8ae0263
1b847de
f2c6e36
8ae0263
0786284
8ae0263
 
 
7d6b6a0
 
 
 
 
8ae0263
 
 
 
034a80d
 
 
06c0f25
 
 
 
 
 
 
b20b518
 
 
 
db529a8
 
b2abfa0
db529a8
f4afdfc
 
 
 
 
db529a8
5db4289
 
 
b2abfa0
 
a2e79ef
b2abfa0
 
 
 
 
9f4b893
 
7cf6af5
6a0dc07
2d6d86b
 
 
 
 
 
 
 
 
723d45a
 
14a29ca
723d45a
 
 
14a29ca
723d45a
5bcb2da
 
 
 
8ae0263
 
f017900
 
 
5eb308b
7536f72
 
af7b183
7536f72
 
7466927
f017900
b453775
0eeca44
4eae278
0786284
 
 
0f43811
0786284
 
4eed756
f017900
708d06f
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
0786284
7cf6af5
a17768f
0f43811
 
 
7cf6af5
0f43811
708d06f
7cf6af5
708d06f
7cf6af5
0f43811
 
 
 
 
 
 
 
 
f017900
7cf6af5
 
670ccd1
 
 
 
 
393bfcb
 
 
 
 
 
 
670ccd1
 
 
c1c622e
 
 
 
 
 
 
 
 
 
 
44b7ae2
31a5f88
 
 
 
 
 
 
 
 
 
 
 
 
 
670ccd1
 
 
31a5f88
 
 
 
670ccd1
31a5f88
 
670ccd1
393bfcb
 
 
 
ffc6b46
 
 
 
 
e5a2e36
cfa7134
 
0f43811
cfa7134
 
 
 
 
b21abfe
 
 
 
c4c6338
 
 
 
 
815b02e
 
 
 
 
 
4449a75
815b02e
b21abfe
44b7ae2
 
 
4670353
f5fef36
 
 
 
 
31a5f88
f5fef36
 
31a5f88
e2dc0c9
 
 
 
0f43811
4670353
5fa42a4
5881799
 
 
94ebfcb
 
 
 
 
 
 
 
 
7d88286
94ebfcb
f017900
 
7536f72
7cf6af5
 
 
f017900
bece06f
708d06f
f017900
7536f72
e1b43c3
 
 
 
 
 
 
 
 
f017900
207c868
 
 
 
f1b05f2
87360f7
 
 
 
207c868
68c7a1c
207c868
 
f017900
0786284
7536f72
f017900
0786284
7536f72
f017900
207c868
 
 
f1b05f2
9b05777
 
 
 
7536f72
207c868
 
 
f017900
5c716bd
 
 
 
 
 
 
 
 
 
 
 
7466927
 
5928046
 
 
695aa80
f017900
000564c
0f43811
 
f017900
 
fd5c513
 
 
 
 
b4ddedc
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
fc412d8
8ae0263
7cf6af5
6796e4f
7cf6af5
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
//===- SplitKit.h - Toolkit for splitting live ranges -----------*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file contains the SplitAnalysis class as well as mutator functions for
// live range splitting.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_LIB_CODEGEN_SPLITKIT_H
#define LLVM_LIB_CODEGEN_SPLITKIT_H

#include "LiveRangeCalc.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/IntervalMap.h"
#include "llvm/ADT/PointerIntPair.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/CodeGen/LiveInterval.h"
#include "llvm/CodeGen/LiveIntervals.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/SlotIndexes.h"
#include "llvm/MC/LaneBitmask.h"
#include "llvm/Support/Compiler.h"
#include <utility>

namespace llvm {

class LiveIntervals;
class LiveRangeEdit;
class MachineBlockFrequencyInfo;
class MachineDominatorTree;
class MachineLoopInfo;
class MachineRegisterInfo;
class TargetInstrInfo;
class TargetRegisterInfo;
class VirtRegMap;

/// Determines the latest safe point in a block in which we can insert a split,
/// spill or other instruction related with CurLI.
class LLVM_LIBRARY_VISIBILITY InsertPointAnalysis {
private:
  const LiveIntervals &LIS;

  /// Last legal insert point in each basic block in the current function.
  /// The first entry is the first terminator, the second entry is the
  /// last valid point to insert a split or spill for a variable that is
  /// live into a landing pad successor.
  SmallVector<std::pair<SlotIndex, SlotIndex>, 8> LastInsertPoint;

  SlotIndex computeLastInsertPoint(const LiveInterval &CurLI,
                                   const MachineBasicBlock &MBB);

public:
  InsertPointAnalysis(const LiveIntervals &lis, unsigned BBNum);

  /// Return the base index of the last valid insert point for \pCurLI in \pMBB.
  SlotIndex getLastInsertPoint(const LiveInterval &CurLI,
                               const MachineBasicBlock &MBB) {
    unsigned Num = MBB.getNumber();
    // Inline the common simple case.
    if (LastInsertPoint[Num].first.isValid() &&
        !LastInsertPoint[Num].second.isValid())
      return LastInsertPoint[Num].first;
    return computeLastInsertPoint(CurLI, MBB);
  }

  /// Returns the last insert point as an iterator for \pCurLI in \pMBB.
  MachineBasicBlock::iterator getLastInsertPointIter(const LiveInterval &CurLI,
                                                     MachineBasicBlock &MBB);

  /// Return the base index of the first insert point in \pMBB.
  SlotIndex getFirstInsertPoint(MachineBasicBlock &MBB) {
    SlotIndex Res = LIS.getMBBStartIdx(&MBB);
    if (!MBB.empty()) {
      MachineBasicBlock::iterator MII = MBB.SkipPHIsLabelsAndDebug(MBB.begin());
      if (MII != MBB.end())
        Res = LIS.getInstructionIndex(*MII);
    }
    return Res;
  }

};

/// SplitAnalysis - Analyze a LiveInterval, looking for live range splitting
/// opportunities.
class LLVM_LIBRARY_VISIBILITY SplitAnalysis {
public:
  const MachineFunction &MF;
  const VirtRegMap &VRM;
  const LiveIntervals &LIS;
  const MachineLoopInfo &Loops;
  const TargetInstrInfo &TII;

  /// Additional information about basic blocks where the current variable is
  /// live. Such a block will look like one of these templates:
  ///
  ///  1. |   o---x   | Internal to block. Variable is only live in this block.
  ///  2. |---x       | Live-in, kill.
  ///  3. |       o---| Def, live-out.
  ///  4. |---x   o---| Live-in, kill, def, live-out. Counted by NumGapBlocks.
  ///  5. |---o---o---| Live-through with uses or defs.
  ///  6. |-----------| Live-through without uses. Counted by NumThroughBlocks.
  ///
  /// Two BlockInfo entries are created for template 4. One for the live-in
  /// segment, and one for the live-out segment. These entries look as if the
  /// block were split in the middle where the live range isn't live.
  ///
  /// Live-through blocks without any uses don't get BlockInfo entries. They
  /// are simply listed in ThroughBlocks instead.
  ///
  struct BlockInfo {
    MachineBasicBlock *MBB;
    SlotIndex FirstInstr; ///< First instr accessing current reg.
    SlotIndex LastInstr;  ///< Last instr accessing current reg.
    SlotIndex FirstDef;   ///< First non-phi valno->def, or SlotIndex().
    bool LiveIn;          ///< Current reg is live in.
    bool LiveOut;         ///< Current reg is live out.

    /// isOneInstr - Returns true when this BlockInfo describes a single
    /// instruction.
    bool isOneInstr() const {
      return SlotIndex::isSameInstr(FirstInstr, LastInstr);
    }
  };

private:
  // Current live interval.
  const LiveInterval *CurLI = nullptr;

  /// Insert Point Analysis.
  InsertPointAnalysis IPA;

  // Sorted slot indexes of using instructions.
  SmallVector<SlotIndex, 8> UseSlots;

  /// UseBlocks - Blocks where CurLI has uses.
  SmallVector<BlockInfo, 8> UseBlocks;

  /// NumGapBlocks - Number of duplicate entries in UseBlocks for blocks where
  /// the live range has a gap.
  unsigned NumGapBlocks;

  /// ThroughBlocks - Block numbers where CurLI is live through without uses.
  BitVector ThroughBlocks;

  /// NumThroughBlocks - Number of live-through blocks.
  unsigned NumThroughBlocks;

  /// DidRepairRange - analyze was forced to shrinkToUses().
  bool DidRepairRange;

  // Sumarize statistics by counting instructions using CurLI.
  void analyzeUses();

  /// calcLiveBlockInfo - Compute per-block information about CurLI.
  bool calcLiveBlockInfo();

public:
  SplitAnalysis(const VirtRegMap &vrm, const LiveIntervals &lis,
                const MachineLoopInfo &mli);

  /// analyze - set CurLI to the specified interval, and analyze how it may be
  /// split.
  void analyze(const LiveInterval *li);

  /// didRepairRange() - Returns true if CurLI was invalid and has been repaired
  /// by analyze(). This really shouldn't happen, but sometimes the coalescer
  /// can create live ranges that end in mid-air.
  bool didRepairRange() const { return DidRepairRange; }

  /// clear - clear all data structures so SplitAnalysis is ready to analyze a
  /// new interval.
  void clear();

  /// getParent - Return the last analyzed interval.
  const LiveInterval &getParent() const { return *CurLI; }

  /// isOriginalEndpoint - Return true if the original live range was killed or
  /// (re-)defined at Idx. Idx should be the 'def' slot for a normal kill/def,
  /// and 'use' for an early-clobber def.
  /// This can be used to recognize code inserted by earlier live range
  /// splitting.
  bool isOriginalEndpoint(SlotIndex Idx) const;

  /// getUseSlots - Return an array of SlotIndexes of instructions using CurLI.
  /// This include both use and def operands, at most one entry per instruction.
  ArrayRef<SlotIndex> getUseSlots() const { return UseSlots; }

  /// getUseBlocks - Return an array of BlockInfo objects for the basic blocks
  /// where CurLI has uses.
  ArrayRef<BlockInfo> getUseBlocks() const { return UseBlocks; }

  /// getNumThroughBlocks - Return the number of through blocks.
  unsigned getNumThroughBlocks() const { return NumThroughBlocks; }

  /// isThroughBlock - Return true if CurLI is live through MBB without uses.
  bool isThroughBlock(unsigned MBB) const { return ThroughBlocks.test(MBB); }

  /// getThroughBlocks - Return the set of through blocks.
  const BitVector &getThroughBlocks() const { return ThroughBlocks; }

  /// getNumLiveBlocks - Return the number of blocks where CurLI is live.
  unsigned getNumLiveBlocks() const {
    return getUseBlocks().size() - NumGapBlocks + getNumThroughBlocks();
  }

  /// countLiveBlocks - Return the number of blocks where li is live. This is
  /// guaranteed to return the same number as getNumLiveBlocks() after calling
  /// analyze(li).
  unsigned countLiveBlocks(const LiveInterval *li) const;

  using BlockPtrSet = SmallPtrSet<const MachineBasicBlock *, 16>;

  /// shouldSplitSingleBlock - Returns true if it would help to create a local
  /// live range for the instructions in BI. There is normally no benefit to
  /// creating a live range for a single instruction, but it does enable
  /// register class inflation if the instruction has a restricted register
  /// class.
  ///
  /// @param BI           The block to be isolated.
  /// @param SingleInstrs True when single instructions should be isolated.
  bool shouldSplitSingleBlock(const BlockInfo &BI, bool SingleInstrs) const;

  SlotIndex getLastSplitPoint(unsigned Num) {
    return IPA.getLastInsertPoint(*CurLI, *MF.getBlockNumbered(Num));
  }

  MachineBasicBlock::iterator getLastSplitPointIter(MachineBasicBlock *BB) {
    return IPA.getLastInsertPointIter(*CurLI, *BB);
  }

  SlotIndex getFirstSplitPoint(unsigned Num) {
    return IPA.getFirstInsertPoint(*MF.getBlockNumbered(Num));
  }
};

/// SplitEditor - Edit machine code and LiveIntervals for live range
/// splitting.
///
/// - Create a SplitEditor from a SplitAnalysis.
/// - Start a new live interval with openIntv.
/// - Mark the places where the new interval is entered using enterIntv*
/// - Mark the ranges where the new interval is used with useIntv*
/// - Mark the places where the interval is exited with exitIntv*.
/// - Finish the current interval with closeIntv and repeat from 2.
/// - Rewrite instructions with finish().
///
class LLVM_LIBRARY_VISIBILITY SplitEditor {
  SplitAnalysis &SA;
  AliasAnalysis &AA;
  LiveIntervals &LIS;
  VirtRegMap &VRM;
  MachineRegisterInfo &MRI;
  MachineDominatorTree &MDT;
  const TargetInstrInfo &TII;
  const TargetRegisterInfo &TRI;
  const MachineBlockFrequencyInfo &MBFI;

public:
  /// ComplementSpillMode - Select how the complement live range should be
  /// created.  SplitEditor automatically creates interval 0 to contain
  /// anything that isn't added to another interval.  This complement interval
  /// can get quite complicated, and it can sometimes be an advantage to allow
  /// it to overlap the other intervals.  If it is going to spill anyway, no
  /// registers are wasted by keeping a value in two places at the same time.
  enum ComplementSpillMode {
    /// SM_Partition(Default) - Try to create the complement interval so it
    /// doesn't overlap any other intervals, and the original interval is
    /// partitioned.  This may require a large number of back copies and extra
    /// PHI-defs.  Only segments marked with overlapIntv will be overlapping.
    SM_Partition,

    /// SM_Size - Overlap intervals to minimize the number of inserted COPY
    /// instructions.  Copies to the complement interval are hoisted to their
    /// common dominator, so only one COPY is required per value in the
    /// complement interval.  This also means that no extra PHI-defs need to be
    /// inserted in the complement interval.
    SM_Size,

    /// SM_Speed - Overlap intervals to minimize the expected execution
    /// frequency of the inserted copies.  This is very similar to SM_Size, but
    /// the complement interval may get some extra PHI-defs.
    SM_Speed
  };

private:
  /// Edit - The current parent register and new intervals created.
  LiveRangeEdit *Edit = nullptr;

  /// Index into Edit of the currently open interval.
  /// The index 0 is used for the complement, so the first interval started by
  /// openIntv will be 1.
  unsigned OpenIdx = 0;

  /// The current spill mode, selected by reset().
  ComplementSpillMode SpillMode = SM_Partition;

  using RegAssignMap = IntervalMap<SlotIndex, unsigned>;

  /// Allocator for the interval map. This will eventually be shared with
  /// SlotIndexes and LiveIntervals.
  RegAssignMap::Allocator Allocator;

  /// RegAssign - Map of the assigned register indexes.
  /// Edit.get(RegAssign.lookup(Idx)) is the register that should be live at
  /// Idx.
  RegAssignMap RegAssign;

  using ValueForcePair = PointerIntPair<VNInfo *, 1>;
  using ValueMap = DenseMap<std::pair<unsigned, unsigned>, ValueForcePair>;

  /// Values - keep track of the mapping from parent values to values in the new
  /// intervals. Given a pair (RegIdx, ParentVNI->id), Values contains:
  ///
  /// 1. No entry - the value is not mapped to Edit.get(RegIdx).
  /// 2. (Null, false) - the value is mapped to multiple values in
  ///    Edit.get(RegIdx).  Each value is represented by a minimal live range at
  ///    its def.  The full live range can be inferred exactly from the range
  ///    of RegIdx in RegAssign.
  /// 3. (Null, true).  As above, but the ranges in RegAssign are too large, and
  ///    the live range must be recomputed using LiveRangeCalc::extend().
  /// 4. (VNI, false) The value is mapped to a single new value.
  ///    The new value has no live ranges anywhere.
  ValueMap Values;

  /// LRCalc - Cache for computing live ranges and SSA update.  Each instance
  /// can only handle non-overlapping live ranges, so use a separate
  /// LiveRangeCalc instance for the complement interval when in spill mode.
  LiveRangeCalc LRCalc[2];

  /// getLRCalc - Return the LRCalc to use for RegIdx.  In spill mode, the
  /// complement interval can overlap the other intervals, so it gets its own
  /// LRCalc instance.  When not in spill mode, all intervals can share one.
  LiveRangeCalc &getLRCalc(unsigned RegIdx) {
    return LRCalc[SpillMode != SM_Partition && RegIdx != 0];
  }

  /// Find a subrange corresponding to the lane mask @p LM in the live
  /// interval @p LI. The interval @p LI is assumed to contain such a subrange.
  /// This function is used to find corresponding subranges between the
  /// original interval and the new intervals.
  LiveInterval::SubRange &getSubRangeForMask(LaneBitmask LM, LiveInterval &LI);

  /// Add a segment to the interval LI for the value number VNI. If LI has
  /// subranges, corresponding segments will be added to them as well, but
  /// with newly created value numbers. If Original is true, dead def will
  /// only be added a subrange of LI if the corresponding subrange of the
  /// original interval has a def at this index. Otherwise, all subranges
  /// of LI will be updated.
  void addDeadDef(LiveInterval &LI, VNInfo *VNI, bool Original);

  /// defValue - define a value in RegIdx from ParentVNI at Idx.
  /// Idx does not have to be ParentVNI->def, but it must be contained within
  /// ParentVNI's live range in ParentLI. The new value is added to the value
  /// map. The value being defined may either come from rematerialization
  /// (or an inserted copy), or it may be coming from the original interval.
  /// The parameter Original should be true in the latter case, otherwise
  /// it should be false.
  /// Return the new LI value.
  VNInfo *defValue(unsigned RegIdx, const VNInfo *ParentVNI, SlotIndex Idx,
                   bool Original);

  /// forceRecompute - Force the live range of ParentVNI in RegIdx to be
  /// recomputed by LiveRangeCalc::extend regardless of the number of defs.
  /// This is used for values whose live range doesn't match RegAssign exactly.
  /// They could have rematerialized, or back-copies may have been moved.
  void forceRecompute(unsigned RegIdx, const VNInfo &ParentVNI);

  /// Calls forceRecompute() on any affected regidx and on ParentVNI
  /// predecessors in case of a phi definition.
  void forceRecomputeVNI(const VNInfo &ParentVNI);

  /// defFromParent - Define Reg from ParentVNI at UseIdx using either
  /// rematerialization or a COPY from parent. Return the new value.
  VNInfo *defFromParent(unsigned RegIdx,
                        VNInfo *ParentVNI,
                        SlotIndex UseIdx,
                        MachineBasicBlock &MBB,
                        MachineBasicBlock::iterator I);

  /// removeBackCopies - Remove the copy instructions that defines the values
  /// in the vector in the complement interval.
  void removeBackCopies(SmallVectorImpl<VNInfo*> &Copies);

  /// getShallowDominator - Returns the least busy dominator of MBB that is
  /// also dominated by DefMBB.  Busy is measured by loop depth.
  MachineBasicBlock *findShallowDominator(MachineBasicBlock *MBB,
                                          MachineBasicBlock *DefMBB);

  /// Find out all the backCopies dominated by others.
  void computeRedundantBackCopies(DenseSet<unsigned> &NotToHoistSet,
                                  SmallVectorImpl<VNInfo *> &BackCopies);

  /// Hoist back-copies to the complement interval. It tries to hoist all
  /// the back-copies to one BB if it is beneficial, or else simply remove
  /// redundant backcopies dominated by others.
  void hoistCopies();

  /// transferValues - Transfer values to the new ranges.
  /// Return true if any ranges were skipped.
  bool transferValues();

  /// Live range @p LR corresponding to the lane Mask @p LM has a live
  /// PHI def at the beginning of block @p B. Extend the range @p LR of
  /// all predecessor values that reach this def. If @p LR is a subrange,
  /// the array @p Undefs is the set of all locations where it is undefined
  /// via <def,read-undef> in other subranges for the same register.
  void extendPHIRange(MachineBasicBlock &B, LiveRangeCalc &LRC,
                      LiveRange &LR, LaneBitmask LM,
                      ArrayRef<SlotIndex> Undefs);

  /// extendPHIKillRanges - Extend the ranges of all values killed by original
  /// parent PHIDefs.
  void extendPHIKillRanges();

  /// rewriteAssigned - Rewrite all uses of Edit.getReg() to assigned registers.
  void rewriteAssigned(bool ExtendRanges);

  /// deleteRematVictims - Delete defs that are dead after rematerializing.
  void deleteRematVictims();

  /// Add a copy instruction copying \p FromReg to \p ToReg before
  /// \p InsertBefore. This can be invoked with a \p LaneMask which may make it
  /// necessary to construct a sequence of copies to cover it exactly.
  SlotIndex buildCopy(unsigned FromReg, unsigned ToReg, LaneBitmask LaneMask,
      MachineBasicBlock &MBB, MachineBasicBlock::iterator InsertBefore,
      bool Late, unsigned RegIdx);

  SlotIndex buildSingleSubRegCopy(unsigned FromReg, unsigned ToReg,
      MachineBasicBlock &MB, MachineBasicBlock::iterator InsertBefore,
      unsigned SubIdx, LiveInterval &DestLI, bool Late, SlotIndex Def);

public:
  /// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
  /// Newly created intervals will be appended to newIntervals.
  SplitEditor(SplitAnalysis &sa, AliasAnalysis &aa, LiveIntervals &lis,
              VirtRegMap &vrm, MachineDominatorTree &mdt,
              MachineBlockFrequencyInfo &mbfi);

  /// reset - Prepare for a new split.
  void reset(LiveRangeEdit&, ComplementSpillMode = SM_Partition);

  /// Create a new virtual register and live interval.
  /// Return the interval index, starting from 1. Interval index 0 is the
  /// implicit complement interval.
  unsigned openIntv();

  /// currentIntv - Return the current interval index.
  unsigned currentIntv() const { return OpenIdx; }

  /// selectIntv - Select a previously opened interval index.
  void selectIntv(unsigned Idx);

  /// enterIntvBefore - Enter the open interval before the instruction at Idx.
  /// If the parent interval is not live before Idx, a COPY is not inserted.
  /// Return the beginning of the new live range.
  SlotIndex enterIntvBefore(SlotIndex Idx);

  /// enterIntvAfter - Enter the open interval after the instruction at Idx.
  /// Return the beginning of the new live range.
  SlotIndex enterIntvAfter(SlotIndex Idx);

  /// enterIntvAtEnd - Enter the open interval at the end of MBB.
  /// Use the open interval from the inserted copy to the MBB end.
  /// Return the beginning of the new live range.
  SlotIndex enterIntvAtEnd(MachineBasicBlock &MBB);

  /// useIntv - indicate that all instructions in MBB should use OpenLI.
  void useIntv(const MachineBasicBlock &MBB);

  /// useIntv - indicate that all instructions in range should use OpenLI.
  void useIntv(SlotIndex Start, SlotIndex End);

  /// leaveIntvAfter - Leave the open interval after the instruction at Idx.
  /// Return the end of the live range.
  SlotIndex leaveIntvAfter(SlotIndex Idx);

  /// leaveIntvBefore - Leave the open interval before the instruction at Idx.
  /// Return the end of the live range.
  SlotIndex leaveIntvBefore(SlotIndex Idx);

  /// leaveIntvAtTop - Leave the interval at the top of MBB.
  /// Add liveness from the MBB top to the copy.
  /// Return the end of the live range.
  SlotIndex leaveIntvAtTop(MachineBasicBlock &MBB);

  /// overlapIntv - Indicate that all instructions in range should use the open
  /// interval, but also let the complement interval be live.
  ///
  /// This doubles the register pressure, but is sometimes required to deal with
  /// register uses after the last valid split point.
  ///
  /// The Start index should be a return value from a leaveIntv* call, and End
  /// should be in the same basic block. The parent interval must have the same
  /// value across the range.
  ///
  void overlapIntv(SlotIndex Start, SlotIndex End);

  /// finish - after all the new live ranges have been created, compute the
  /// remaining live range, and rewrite instructions to use the new registers.
  /// @param LRMap When not null, this vector will map each live range in Edit
  ///              back to the indices returned by openIntv.
  ///              There may be extra indices created by dead code elimination.
  void finish(SmallVectorImpl<unsigned> *LRMap = nullptr);

  /// dump - print the current interval mapping to dbgs().
  void dump() const;

  // ===--- High level methods ---===

  /// splitSingleBlock - Split CurLI into a separate live interval around the
  /// uses in a single block. This is intended to be used as part of a larger
  /// split, and doesn't call finish().
  void splitSingleBlock(const SplitAnalysis::BlockInfo &BI);

  /// splitLiveThroughBlock - Split CurLI in the given block such that it
  /// enters the block in IntvIn and leaves it in IntvOut. There may be uses in
  /// the block, but they will be ignored when placing split points.
  ///
  /// @param MBBNum      Block number.
  /// @param IntvIn      Interval index entering the block.
  /// @param LeaveBefore When set, leave IntvIn before this point.
  /// @param IntvOut     Interval index leaving the block.
  /// @param EnterAfter  When set, enter IntvOut after this point.
  void splitLiveThroughBlock(unsigned MBBNum,
                             unsigned IntvIn, SlotIndex LeaveBefore,
                             unsigned IntvOut, SlotIndex EnterAfter);

  /// splitRegInBlock - Split CurLI in the given block such that it enters the
  /// block in IntvIn and leaves it on the stack (or not at all). Split points
  /// are placed in a way that avoids putting uses in the stack interval. This
  /// may require creating a local interval when there is interference.
  ///
  /// @param BI          Block descriptor.
  /// @param IntvIn      Interval index entering the block. Not 0.
  /// @param LeaveBefore When set, leave IntvIn before this point.
  void splitRegInBlock(const SplitAnalysis::BlockInfo &BI,
                       unsigned IntvIn, SlotIndex LeaveBefore);

  /// splitRegOutBlock - Split CurLI in the given block such that it enters the
  /// block on the stack (or isn't live-in at all) and leaves it in IntvOut.
  /// Split points are placed to avoid interference and such that the uses are
  /// not in the stack interval. This may require creating a local interval
  /// when there is interference.
  ///
  /// @param BI          Block descriptor.
  /// @param IntvOut     Interval index leaving the block.
  /// @param EnterAfter  When set, enter IntvOut after this point.
  void splitRegOutBlock(const SplitAnalysis::BlockInfo &BI,
                        unsigned IntvOut, SlotIndex EnterAfter);
};

} // end namespace llvm

#endif // LLVM_LIB_CODEGEN_SPLITKIT_H