Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/SplitKit.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- SplitKit.cpp - Toolkit for splitting live ranges -------------------===//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
//
9
// This file contains the SplitAnalysis class as well as mutator functions for
10
// live range splitting.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#include "SplitKit.h"
15
#include "LiveRangeCalc.h"
16
#include "llvm/ADT/ArrayRef.h"
17
#include "llvm/ADT/DenseSet.h"
18
#include "llvm/ADT/None.h"
19
#include "llvm/ADT/STLExtras.h"
20
#include "llvm/ADT/SmallPtrSet.h"
21
#include "llvm/ADT/SmallVector.h"
22
#include "llvm/ADT/Statistic.h"
23
#include "llvm/CodeGen/LiveInterval.h"
24
#include "llvm/CodeGen/LiveIntervals.h"
25
#include "llvm/CodeGen/LiveRangeEdit.h"
26
#include "llvm/CodeGen/MachineBasicBlock.h"
27
#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
28
#include "llvm/CodeGen/MachineDominators.h"
29
#include "llvm/CodeGen/MachineFunction.h"
30
#include "llvm/CodeGen/MachineInstr.h"
31
#include "llvm/CodeGen/MachineInstrBuilder.h"
32
#include "llvm/CodeGen/MachineLoopInfo.h"
33
#include "llvm/CodeGen/MachineOperand.h"
34
#include "llvm/CodeGen/MachineRegisterInfo.h"
35
#include "llvm/CodeGen/SlotIndexes.h"
36
#include "llvm/CodeGen/TargetInstrInfo.h"
37
#include "llvm/CodeGen/TargetOpcodes.h"
38
#include "llvm/CodeGen/TargetRegisterInfo.h"
39
#include "llvm/CodeGen/TargetSubtargetInfo.h"
40
#include "llvm/CodeGen/VirtRegMap.h"
41
#include "llvm/Config/llvm-config.h"
42
#include "llvm/IR/DebugLoc.h"
43
#include "llvm/MC/LaneBitmask.h"
44
#include "llvm/Support/Allocator.h"
45
#include "llvm/Support/BlockFrequency.h"
46
#include "llvm/Support/Compiler.h"
47
#include "llvm/Support/Debug.h"
48
#include "llvm/Support/ErrorHandling.h"
49
#include "llvm/Support/raw_ostream.h"
50
#include <algorithm>
51
#include <cassert>
52
#include <iterator>
53
#include <limits>
54
#include <tuple>
55
#include <utility>
56
57
using namespace llvm;
58
59
#define DEBUG_TYPE "regalloc"
60
61
STATISTIC(NumFinished, "Number of splits finished");
62
STATISTIC(NumSimple,   "Number of splits that were simple");
63
STATISTIC(NumCopies,   "Number of copies inserted for splitting");
64
STATISTIC(NumRemats,   "Number of rematerialized defs for splitting");
65
STATISTIC(NumRepairs,  "Number of invalid live ranges repaired");
66
67
//===----------------------------------------------------------------------===//
68
//                     Last Insert Point Analysis
69
//===----------------------------------------------------------------------===//
70
71
InsertPointAnalysis::InsertPointAnalysis(const LiveIntervals &lis,
72
                                         unsigned BBNum)
73
968k
    : LIS(lis), LastInsertPoint(BBNum) {}
74
75
SlotIndex
76
InsertPointAnalysis::computeLastInsertPoint(const LiveInterval &CurLI,
77
1.70M
                                            const MachineBasicBlock &MBB) {
78
1.70M
  unsigned Num = MBB.getNumber();
79
1.70M
  std::pair<SlotIndex, SlotIndex> &LIP = LastInsertPoint[Num];
80
1.70M
  SlotIndex MBBEnd = LIS.getMBBEndIdx(&MBB);
81
1.70M
82
1.70M
  SmallVector<const MachineBasicBlock *, 1> EHPadSuccessors;
83
1.70M
  for (const MachineBasicBlock *SMBB : MBB.successors())
84
3.13M
    if (SMBB->isEHPad())
85
944k
      EHPadSuccessors.push_back(SMBB);
86
1.70M
87
1.70M
  // Compute insert points on the first call. The pair is independent of the
88
1.70M
  // current live interval.
89
1.70M
  if (!LIP.first.isValid()) {
90
775k
    MachineBasicBlock::const_iterator FirstTerm = MBB.getFirstTerminator();
91
775k
    if (FirstTerm == MBB.end())
92
163k
      LIP.first = MBBEnd;
93
612k
    else
94
612k
      LIP.first = LIS.getInstructionIndex(*FirstTerm);
95
775k
96
775k
    // If there is a landing pad successor, also find the call instruction.
97
775k
    if (EHPadSuccessors.empty())
98
762k
      return LIP.first;
99
13.7k
    // There may not be a call instruction (?) in which case we ignore LPad.
100
13.7k
    LIP.second = LIP.first;
101
13.7k
    for (MachineBasicBlock::const_iterator I = MBB.end(), E = MBB.begin();
102
62.3k
         I != E;) {
103
62.3k
      --I;
104
62.3k
      if (I->isCall()) {
105
13.7k
        LIP.second = LIS.getInstructionIndex(*I);
106
13.7k
        break;
107
13.7k
      }
108
62.3k
    }
109
13.7k
  }
110
1.70M
111
1.70M
  // If CurLI is live into a landing pad successor, move the last insert point
112
1.70M
  // back to the call that may throw.
113
1.70M
  
if (944k
!LIP.second944k
)
114
0
    return LIP.first;
115
944k
116
944k
  
if (944k
none_of(EHPadSuccessors, [&](const MachineBasicBlock *EHPad) 944k
{
117
944k
        return LIS.isLiveInToMBB(CurLI, EHPad);
118
944k
      }))
119
845k
    return LIP.first;
120
99.3k
121
99.3k
  // Find the value leaving MBB.
122
99.3k
  const VNInfo *VNI = CurLI.getVNInfoBefore(MBBEnd);
123
99.3k
  if (!VNI)
124
0
    return LIP.first;
125
99.3k
126
99.3k
  // If the value leaving MBB was defined after the call in MBB, it can't
127
99.3k
  // really be live-in to the landing pad.  This can happen if the landing pad
128
99.3k
  // has a PHI, and this register is undef on the exceptional edge.
129
99.3k
  // <rdar://problem/10664933>
130
99.3k
  if (!SlotIndex::isEarlierInstr(VNI->def, LIP.second) && 
VNI->def < MBBEnd4
)
131
4
    return LIP.first;
132
99.3k
133
99.3k
  // Value is properly live-in to the landing pad.
134
99.3k
  // Only allow inserts before the call.
135
99.3k
  return LIP.second;
136
99.3k
}
137
138
MachineBasicBlock::iterator
139
InsertPointAnalysis::getLastInsertPointIter(const LiveInterval &CurLI,
140
251k
                                            MachineBasicBlock &MBB) {
141
251k
  SlotIndex LIP = getLastInsertPoint(CurLI, MBB);
142
251k
  if (LIP == LIS.getMBBEndIdx(&MBB))
143
57.0k
    return MBB.end();
144
194k
  return LIS.getInstructionFromIndex(LIP);
145
194k
}
146
147
//===----------------------------------------------------------------------===//
148
//                                 Split Analysis
149
//===----------------------------------------------------------------------===//
150
151
SplitAnalysis::SplitAnalysis(const VirtRegMap &vrm, const LiveIntervals &lis,
152
                             const MachineLoopInfo &mli)
153
    : MF(vrm.getMachineFunction()), VRM(vrm), LIS(lis), Loops(mli),
154
484k
      TII(*MF.getSubtarget().getInstrInfo()), IPA(lis, MF.getNumBlockIDs()) {}
155
156
430k
void SplitAnalysis::clear() {
157
430k
  UseSlots.clear();
158
430k
  UseBlocks.clear();
159
430k
  ThroughBlocks.clear();
160
430k
  CurLI = nullptr;
161
430k
  DidRepairRange = false;
162
430k
}
163
164
/// analyzeUses - Count instructions, basic blocks, and loops using CurLI.
165
430k
void SplitAnalysis::analyzeUses() {
166
430k
  assert(UseSlots.empty() && "Call clear first");
167
430k
168
430k
  // First get all the defs from the interval values. This provides the correct
169
430k
  // slots for early clobbers.
170
430k
  for (const VNInfo *VNI : CurLI->valnos)
171
611k
    if (!VNI->isPHIDef() && 
!VNI->isUnused()550k
)
172
550k
      UseSlots.push_back(VNI->def);
173
430k
174
430k
  // Get use slots form the use-def chain.
175
430k
  const MachineRegisterInfo &MRI = MF.getRegInfo();
176
430k
  for (MachineOperand &MO : MRI.use_nodbg_operands(CurLI->reg))
177
1.29M
    if (!MO.isUndef())
178
1.29M
      UseSlots.push_back(LIS.getInstructionIndex(*MO.getParent()).getRegSlot());
179
430k
180
430k
  array_pod_sort(UseSlots.begin(), UseSlots.end());
181
430k
182
430k
  // Remove duplicates, keeping the smaller slot for each instruction.
183
430k
  // That is what we want for early clobbers.
184
430k
  UseSlots.erase(std::unique(UseSlots.begin(), UseSlots.end(),
185
430k
                             SlotIndex::isSameInstr),
186
430k
                 UseSlots.end());
187
430k
188
430k
  // Compute per-live block info.
189
430k
  if (!calcLiveBlockInfo()) {
190
0
    // FIXME: calcLiveBlockInfo found inconsistencies in the live range.
191
0
    // I am looking at you, RegisterCoalescer!
192
0
    DidRepairRange = true;
193
0
    ++NumRepairs;
194
0
    LLVM_DEBUG(dbgs() << "*** Fixing inconsistent live interval! ***\n");
195
0
    const_cast<LiveIntervals&>(LIS)
196
0
      .shrinkToUses(const_cast<LiveInterval*>(CurLI));
197
0
    UseBlocks.clear();
198
0
    ThroughBlocks.clear();
199
0
    bool fixed = calcLiveBlockInfo();
200
0
    (void)fixed;
201
0
    assert(fixed && "Couldn't fix broken live interval");
202
0
  }
203
430k
204
430k
  LLVM_DEBUG(dbgs() << "Analyze counted " << UseSlots.size() << " instrs in "
205
430k
                    << UseBlocks.size() << " blocks, through "
206
430k
                    << NumThroughBlocks << " blocks.\n");
207
430k
}
208
209
/// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks
210
/// where CurLI is live.
211
430k
bool SplitAnalysis::calcLiveBlockInfo() {
212
430k
  ThroughBlocks.resize(MF.getNumBlockIDs());
213
430k
  NumThroughBlocks = NumGapBlocks = 0;
214
430k
  if (CurLI->empty())
215
0
    return true;
216
430k
217
430k
  LiveInterval::const_iterator LVI = CurLI->begin();
218
430k
  LiveInterval::const_iterator LVE = CurLI->end();
219
430k
220
430k
  SmallVectorImpl<SlotIndex>::const_iterator UseI, UseE;
221
430k
  UseI = UseSlots.begin();
222
430k
  UseE = UseSlots.end();
223
430k
224
430k
  // Loop over basic blocks where CurLI is live.
225
430k
  MachineFunction::iterator MFI =
226
430k
      LIS.getMBBFromIndex(LVI->start)->getIterator();
227
13.9M
  while (true) {
228
13.9M
    BlockInfo BI;
229
13.9M
    BI.MBB = &*MFI;
230
13.9M
    SlotIndex Start, Stop;
231
13.9M
    std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);
232
13.9M
233
13.9M
    // If the block contains no uses, the range must be live through. At one
234
13.9M
    // point, RegisterCoalescer could create dangling ranges that ended
235
13.9M
    // mid-block.
236
13.9M
    if (UseI == UseE || 
*UseI >= Stop9.78M
) {
237
12.6M
      ++NumThroughBlocks;
238
12.6M
      ThroughBlocks.set(BI.MBB->getNumber());
239
12.6M
      // The range shouldn't end mid-block if there are no uses. This shouldn't
240
12.6M
      // happen.
241
12.6M
      if (LVI->end < Stop)
242
0
        return false;
243
1.25M
    } else {
244
1.25M
      // This block has uses. Find the first and last uses in the block.
245
1.25M
      BI.FirstInstr = *UseI;
246
1.25M
      assert(BI.FirstInstr >= Start);
247
1.79M
      do ++UseI;
248
1.79M
      while (UseI != UseE && 
*UseI < Stop1.36M
);
249
1.25M
      BI.LastInstr = UseI[-1];
250
1.25M
      assert(BI.LastInstr < Stop);
251
1.25M
252
1.25M
      // LVI is the first live segment overlapping MBB.
253
1.25M
      BI.LiveIn = LVI->start <= Start;
254
1.25M
255
1.25M
      // When not live in, the first use should be a def.
256
1.25M
      if (!BI.LiveIn) {
257
476k
        assert(LVI->start == LVI->valno->def && "Dangling Segment start");
258
476k
        assert(LVI->start == BI.FirstInstr && "First instr should be a def");
259
476k
        BI.FirstDef = BI.FirstInstr;
260
476k
      }
261
1.25M
262
1.25M
      // Look for gaps in the live range.
263
1.25M
      BI.LiveOut = true;
264
1.32M
      while (LVI->end < Stop) {
265
396k
        SlotIndex LastStop = LVI->end;
266
396k
        if (++LVI == LVE || 
LVI->start >= Stop151k
) {
267
322k
          BI.LiveOut = false;
268
322k
          BI.LastInstr = LastStop;
269
322k
          break;
270
322k
        }
271
74.0k
272
74.0k
        if (LastStop < LVI->start) {
273
24.6k
          // There is a gap in the live range. Create duplicate entries for the
274
24.6k
          // live-in snippet and the live-out snippet.
275
24.6k
          ++NumGapBlocks;
276
24.6k
277
24.6k
          // Push the Live-in part.
278
24.6k
          BI.LiveOut = false;
279
24.6k
          UseBlocks.push_back(BI);
280
24.6k
          UseBlocks.back().LastInstr = LastStop;
281
24.6k
282
24.6k
          // Set up BI for the live-out part.
283
24.6k
          BI.LiveIn = false;
284
24.6k
          BI.LiveOut = true;
285
24.6k
          BI.FirstInstr = BI.FirstDef = LVI->start;
286
24.6k
        }
287
74.0k
288
74.0k
        // A Segment that starts in the middle of the block must be a def.
289
74.0k
        assert(LVI->start == LVI->valno->def && "Dangling Segment start");
290
74.0k
        if (!BI.FirstDef)
291
14.7k
          BI.FirstDef = LVI->start;
292
74.0k
      }
293
1.25M
294
1.25M
      UseBlocks.push_back(BI);
295
1.25M
296
1.25M
      // LVI is now at LVE or LVI->end >= Stop.
297
1.25M
      if (LVI == LVE)
298
244k
        break;
299
13.6M
    }
300
13.6M
301
13.6M
    // Live segment ends exactly at Stop. Move to the next segment.
302
13.6M
    if (LVI->end == Stop && 
++LVI == LVE955k
)
303
185k
      break;
304
13.5M
305
13.5M
    // Pick the next basic block.
306
13.5M
    if (LVI->start < Stop)
307
12.6M
      ++MFI;
308
847k
    else
309
847k
      MFI = LIS.getMBBFromIndex(LVI->start)->getIterator();
310
13.5M
  }
311
430k
312
430k
  assert(getNumLiveBlocks() == countLiveBlocks(CurLI) && "Bad block count");
313
430k
  return true;
314
430k
}
315
316
154k
unsigned SplitAnalysis::countLiveBlocks(const LiveInterval *cli) const {
317
154k
  if (cli->empty())
318
3.09k
    return 0;
319
151k
  LiveInterval *li = const_cast<LiveInterval*>(cli);
320
151k
  LiveInterval::iterator LVI = li->begin();
321
151k
  LiveInterval::iterator LVE = li->end();
322
151k
  unsigned Count = 0;
323
151k
324
151k
  // Loop over basic blocks where li is live.
325
151k
  MachineFunction::const_iterator MFI =
326
151k
      LIS.getMBBFromIndex(LVI->start)->getIterator();
327
151k
  SlotIndex Stop = LIS.getMBBEndIdx(&*MFI);
328
1.99M
  while (true) {
329
1.99M
    ++Count;
330
1.99M
    LVI = li->advanceTo(LVI, Stop);
331
1.99M
    if (LVI == LVE)
332
151k
      return Count;
333
3.39M
    
do 1.84M
{
334
3.39M
      ++MFI;
335
3.39M
      Stop = LIS.getMBBEndIdx(&*MFI);
336
3.39M
    } while (Stop <= LVI->start);
337
1.84M
  }
338
151k
}
339
340
244
bool SplitAnalysis::isOriginalEndpoint(SlotIndex Idx) const {
341
244
  unsigned OrigReg = VRM.getOriginal(CurLI->reg);
342
244
  const LiveInterval &Orig = LIS.getInterval(OrigReg);
343
244
  assert(!Orig.empty() && "Splitting empty interval?");
344
244
  LiveInterval::const_iterator I = Orig.find(Idx);
345
244
346
244
  // Range containing Idx should begin at Idx.
347
244
  if (I != Orig.end() && 
I->start <= Idx170
)
348
145
    return I->start == Idx;
349
99
350
99
  // Range does not contain Idx, previous must end at Idx.
351
99
  return I != Orig.begin() && (--I)->end == Idx;
352
99
}
353
354
430k
void SplitAnalysis::analyze(const LiveInterval *li) {
355
430k
  clear();
356
430k
  CurLI = li;
357
430k
  analyzeUses();
358
430k
}
359
360
//===----------------------------------------------------------------------===//
361
//                               Split Editor
362
//===----------------------------------------------------------------------===//
363
364
/// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
365
SplitEditor::SplitEditor(SplitAnalysis &sa, AliasAnalysis &aa,
366
                         LiveIntervals &lis, VirtRegMap &vrm,
367
                         MachineDominatorTree &mdt,
368
                         MachineBlockFrequencyInfo &mbfi)
369
    : SA(sa), AA(aa), LIS(lis), VRM(vrm),
370
      MRI(vrm.getMachineFunction().getRegInfo()), MDT(mdt),
371
      TII(*vrm.getMachineFunction().getSubtarget().getInstrInfo()),
372
      TRI(*vrm.getMachineFunction().getSubtarget().getRegisterInfo()),
373
484k
      MBFI(mbfi), RegAssign(Allocator) {}
374
375
291k
void SplitEditor::reset(LiveRangeEdit &LRE, ComplementSpillMode SM) {
376
291k
  Edit = &LRE;
377
291k
  SpillMode = SM;
378
291k
  OpenIdx = 0;
379
291k
  RegAssign.clear();
380
291k
  Values.clear();
381
291k
382
291k
  // Reset the LiveRangeCalc instances needed for this spill mode.
383
291k
  LRCalc[0].reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,
384
291k
                  &LIS.getVNInfoAllocator());
385
291k
  if (SpillMode)
386
257k
    LRCalc[1].reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,
387
257k
                    &LIS.getVNInfoAllocator());
388
291k
389
291k
  // We don't need an AliasAnalysis since we will only be performing
390
291k
  // cheap-as-a-copy remats anyway.
391
291k
  Edit->anyRematerializable(nullptr);
392
291k
}
393
394
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
395
LLVM_DUMP_METHOD void SplitEditor::dump() const {
396
  if (RegAssign.empty()) {
397
    dbgs() << " empty\n";
398
    return;
399
  }
400
401
  for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I)
402
    dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value();
403
  dbgs() << '\n';
404
}
405
#endif
406
407
LiveInterval::SubRange &SplitEditor::getSubRangeForMask(LaneBitmask LM,
408
598
                                                        LiveInterval &LI) {
409
598
  for (LiveInterval::SubRange &S : LI.subranges())
410
1.23k
    if (S.LaneMask == LM)
411
598
      return S;
412
598
  
llvm_unreachable0
("SubRange for this mask not found");
413
598
}
414
415
495k
void SplitEditor::addDeadDef(LiveInterval &LI, VNInfo *VNI, bool Original) {
416
495k
  if (!LI.hasSubRanges()) {
417
495k
    LI.createDeadDef(VNI);
418
495k
    return;
419
495k
  }
420
407
421
407
  SlotIndex Def = VNI->def;
422
407
  if (Original) {
423
208
    // If we are transferring a def from the original interval, make sure
424
208
    // to only update the subranges for which the original subranges had
425
208
    // a def at this location.
426
577
    for (LiveInterval::SubRange &S : LI.subranges()) {
427
577
      auto &PS = getSubRangeForMask(S.LaneMask, Edit->getParent());
428
577
      VNInfo *PV = PS.getVNInfoAt(Def);
429
577
      if (PV != nullptr && 
PV->def == Def511
)
430
457
        S.createDeadDef(Def, LIS.getVNInfoAllocator());
431
577
    }
432
208
  } else {
433
199
    // This is a new def: either from rematerialization, or from an inserted
434
199
    // copy. Since rematerialization can regenerate a definition of a sub-
435
199
    // register, we need to check which subranges need to be updated.
436
199
    const MachineInstr *DefMI = LIS.getInstructionFromIndex(Def);
437
199
    assert(DefMI != nullptr);
438
199
    LaneBitmask LM;
439
199
    for (const MachineOperand &DefOp : DefMI->defs()) {
440
199
      unsigned R = DefOp.getReg();
441
199
      if (R != LI.reg)
442
0
        continue;
443
199
      if (unsigned SR = DefOp.getSubReg())
444
8
        LM |= TRI.getSubRegIndexLaneMask(SR);
445
191
      else {
446
191
        LM = MRI.getMaxLaneMaskForVReg(R);
447
191
        break;
448
191
      }
449
199
    }
450
199
    for (LiveInterval::SubRange &S : LI.subranges())
451
611
      if ((S.LaneMask & LM).any())
452
604
        S.createDeadDef(Def, LIS.getVNInfoAllocator());
453
199
  }
454
407
}
455
456
VNInfo *SplitEditor::defValue(unsigned RegIdx,
457
                              const VNInfo *ParentVNI,
458
                              SlotIndex Idx,
459
806k
                              bool Original) {
460
806k
  assert(ParentVNI && "Mapping  NULL value");
461
806k
  assert(Idx.isValid() && "Invalid SlotIndex");
462
806k
  assert(Edit->getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI");
463
806k
  LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx));
464
806k
465
806k
  // Create a new value.
466
806k
  VNInfo *VNI = LI->getNextValue(Idx, LIS.getVNInfoAllocator());
467
806k
468
806k
  bool Force = LI->hasSubRanges();
469
806k
  ValueForcePair FP(Force ? 
nullptr407
:
VNI806k
, Force);
470
806k
  // Use insert for lookup, so we can add missing values with a second lookup.
471
806k
  std::pair<ValueMap::iterator, bool> InsP =
472
806k
    Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id), FP));
473
806k
474
806k
  // This was the first time (RegIdx, ParentVNI) was mapped, and it is not
475
806k
  // forced. Keep it as a simple def without any liveness.
476
806k
  if (!Force && 
InsP.second806k
)
477
469k
    return VNI;
478
337k
479
337k
  // If the previous value was a simple mapping, add liveness for it now.
480
337k
  if (VNInfo *OldVNI = InsP.first->second.getPointer()) {
481
119k
    addDeadDef(*LI, OldVNI, Original);
482
119k
483
119k
    // No longer a simple mapping.  Switch to a complex mapping. If the
484
119k
    // interval has subranges, make it a forced mapping.
485
119k
    InsP.first->second = ValueForcePair(nullptr, Force);
486
119k
  }
487
337k
488
337k
  // This is a complex mapping, add liveness for VNI
489
337k
  addDeadDef(*LI, VNI, Original);
490
337k
  return VNI;
491
337k
}
492
493
205k
void SplitEditor::forceRecompute(unsigned RegIdx, const VNInfo &ParentVNI) {
494
205k
  ValueForcePair &VFP = Values[std::make_pair(RegIdx, ParentVNI.id)];
495
205k
  VNInfo *VNI = VFP.getPointer();
496
205k
497
205k
  // ParentVNI was either unmapped or already complex mapped. Either way, just
498
205k
  // set the force bit.
499
205k
  if (!VNI) {
500
166k
    VFP.setInt(true);
501
166k
    return;
502
166k
  }
503
38.9k
504
38.9k
  // This was previously a single mapping. Make sure the old def is represented
505
38.9k
  // by a trivial live range.
506
38.9k
  addDeadDef(LIS.getInterval(Edit->get(RegIdx)), VNI, false);
507
38.9k
508
38.9k
  // Mark as complex mapped, forced.
509
38.9k
  VFP = ValueForcePair(nullptr, true);
510
38.9k
}
511
512
SlotIndex SplitEditor::buildSingleSubRegCopy(unsigned FromReg, unsigned ToReg,
513
    MachineBasicBlock &MBB, MachineBasicBlock::iterator InsertBefore,
514
14
    unsigned SubIdx, LiveInterval &DestLI, bool Late, SlotIndex Def) {
515
14
  const MCInstrDesc &Desc = TII.get(TargetOpcode::COPY);
516
14
  bool FirstCopy = !Def.isValid();
517
14
  MachineInstr *CopyMI = BuildMI(MBB, InsertBefore, DebugLoc(), Desc)
518
14
      .addReg(ToReg, RegState::Define | getUndefRegState(FirstCopy)
519
14
              | getInternalReadRegState(!FirstCopy), SubIdx)
520
14
      .addReg(FromReg, 0, SubIdx);
521
14
522
14
  BumpPtrAllocator &Allocator = LIS.getVNInfoAllocator();
523
14
  SlotIndexes &Indexes = *LIS.getSlotIndexes();
524
14
  if (FirstCopy) {
525
7
    Def = Indexes.insertMachineInstrInMaps(*CopyMI, Late).getRegSlot();
526
7
  } else {
527
7
    CopyMI->bundleWithPred();
528
7
  }
529
14
  LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubIdx);
530
14
  DestLI.refineSubRanges(Allocator, LaneMask,
531
14
                         [Def, &Allocator](LiveInterval::SubRange &SR) {
532
14
                           SR.createDeadDef(Def, Allocator);
533
14
                         },
534
14
                         Indexes, TRI);
535
14
  return Def;
536
14
}
537
538
SlotIndex SplitEditor::buildCopy(unsigned FromReg, unsigned ToReg,
539
    LaneBitmask LaneMask, MachineBasicBlock &MBB,
540
382k
    MachineBasicBlock::iterator InsertBefore, bool Late, unsigned RegIdx) {
541
382k
  const MCInstrDesc &Desc = TII.get(TargetOpcode::COPY);
542
382k
  if (LaneMask.all() || 
LaneMask == MRI.getMaxLaneMaskForVReg(FromReg)198
) {
543
382k
    // The full vreg is copied.
544
382k
    MachineInstr *CopyMI =
545
382k
        BuildMI(MBB, InsertBefore, DebugLoc(), Desc, ToReg).addReg(FromReg);
546
382k
    SlotIndexes &Indexes = *LIS.getSlotIndexes();
547
382k
    return Indexes.insertMachineInstrInMaps(*CopyMI, Late).getRegSlot();
548
382k
  }
549
7
550
7
  // Only a subset of lanes needs to be copied. The following is a simple
551
7
  // heuristic to construct a sequence of COPYs. We could add a target
552
7
  // specific callback if this turns out to be suboptimal.
553
7
  LiveInterval &DestLI = LIS.getInterval(Edit->get(RegIdx));
554
7
555
7
  // First pass: Try to find a perfectly matching subregister index. If none
556
7
  // exists find the one covering the most lanemask bits.
557
7
  SmallVector<unsigned, 8> PossibleIndexes;
558
7
  unsigned BestIdx = 0;
559
7
  unsigned BestCover = 0;
560
7
  const TargetRegisterClass *RC = MRI.getRegClass(FromReg);
561
7
  assert(RC == MRI.getRegClass(ToReg) && "Should have same reg class");
562
1.35k
  for (unsigned Idx = 1, E = TRI.getNumSubRegIndices(); Idx < E; 
++Idx1.34k
) {
563
1.34k
    // Is this index even compatible with the given class?
564
1.34k
    if (TRI.getSubClassWithSubReg(RC, Idx) != RC)
565
1.30k
      continue;
566
42
    LaneBitmask SubRegMask = TRI.getSubRegIndexLaneMask(Idx);
567
42
    // Early exit if we found a perfect match.
568
42
    if (SubRegMask == LaneMask) {
569
0
      BestIdx = Idx;
570
0
      break;
571
0
    }
572
42
573
42
    // The index must not cover any lanes outside \p LaneMask.
574
42
    if ((SubRegMask & ~LaneMask).any())
575
28
      continue;
576
14
577
14
    unsigned PopCount = SubRegMask.getNumLanes();
578
14
    PossibleIndexes.push_back(Idx);
579
14
    if (PopCount > BestCover) {
580
7
      BestCover = PopCount;
581
7
      BestIdx = Idx;
582
7
    }
583
14
  }
584
7
585
7
  // Abort if we cannot possibly implement the COPY with the given indexes.
586
7
  if (BestIdx == 0)
587
0
    report_fatal_error("Impossible to implement partial COPY");
588
7
589
7
  SlotIndex Def = buildSingleSubRegCopy(FromReg, ToReg, MBB, InsertBefore,
590
7
                                        BestIdx, DestLI, Late, SlotIndex());
591
7
592
7
  // Greedy heuristic: Keep iterating keeping the best covering subreg index
593
7
  // each time.
594
7
  LaneBitmask LanesLeft = LaneMask & ~(TRI.getSubRegIndexLaneMask(BestIdx));
595
14
  while (LanesLeft.any()) {
596
7
    unsigned BestIdx = 0;
597
7
    int BestCover = std::numeric_limits<int>::min();
598
14
    for (unsigned Idx : PossibleIndexes) {
599
14
      LaneBitmask SubRegMask = TRI.getSubRegIndexLaneMask(Idx);
600
14
      // Early exit if we found a perfect match.
601
14
      if (SubRegMask == LanesLeft) {
602
7
        BestIdx = Idx;
603
7
        break;
604
7
      }
605
7
606
7
      // Try to cover as much of the remaining lanes as possible but
607
7
      // as few of the already covered lanes as possible.
608
7
      int Cover = (SubRegMask & LanesLeft).getNumLanes()
609
7
                - (SubRegMask & ~LanesLeft).getNumLanes();
610
7
      if (Cover > BestCover) {
611
7
        BestCover = Cover;
612
7
        BestIdx = Idx;
613
7
      }
614
7
    }
615
7
616
7
    if (BestIdx == 0)
617
0
      report_fatal_error("Impossible to implement partial COPY");
618
7
619
7
    buildSingleSubRegCopy(FromReg, ToReg, MBB, InsertBefore, BestIdx,
620
7
                          DestLI, Late, Def);
621
7
    LanesLeft &= ~TRI.getSubRegIndexLaneMask(BestIdx);
622
7
  }
623
7
624
7
  return Def;
625
7
}
626
627
VNInfo *SplitEditor::defFromParent(unsigned RegIdx,
628
                                   VNInfo *ParentVNI,
629
                                   SlotIndex UseIdx,
630
                                   MachineBasicBlock &MBB,
631
521k
                                   MachineBasicBlock::iterator I) {
632
521k
  SlotIndex Def;
633
521k
  LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx));
634
521k
635
521k
  // We may be trying to avoid interference that ends at a deleted instruction,
636
521k
  // so always begin RegIdx 0 early and all others late.
637
521k
  bool Late = RegIdx != 0;
638
521k
639
521k
  // Attempt cheap-as-a-copy rematerialization.
640
521k
  unsigned Original = VRM.getOriginal(Edit->get(RegIdx));
641
521k
  LiveInterval &OrigLI = LIS.getInterval(Original);
642
521k
  VNInfo *OrigVNI = OrigLI.getVNInfoAt(UseIdx);
643
521k
644
521k
  unsigned Reg = LI->reg;
645
521k
  bool DidRemat = false;
646
521k
  if (OrigVNI) {
647
521k
    LiveRangeEdit::Remat RM(ParentVNI);
648
521k
    RM.OrigMI = LIS.getInstructionFromIndex(OrigVNI->def);
649
521k
    if (Edit->canRematerializeAt(RM, OrigVNI, UseIdx, true)) {
650
138k
      Def = Edit->rematerializeAt(MBB, I, Reg, RM, TRI, Late);
651
138k
      ++NumRemats;
652
138k
      DidRemat = true;
653
138k
    }
654
521k
  }
655
521k
  if (!DidRemat) {
656
382k
    LaneBitmask LaneMask;
657
382k
    if (LI->hasSubRanges()) {
658
198
      LaneMask = LaneBitmask::getNone();
659
198
      for (LiveInterval::SubRange &S : LI->subranges())
660
610
        LaneMask |= S.LaneMask;
661
382k
    } else {
662
382k
      LaneMask = LaneBitmask::getAll();
663
382k
    }
664
382k
665
382k
    ++NumCopies;
666
382k
    Def = buildCopy(Edit->getReg(), Reg, LaneMask, MBB, I, Late, RegIdx);
667
382k
  }
668
521k
669
521k
  // Define the value in Reg.
670
521k
  return defValue(RegIdx, ParentVNI, Def, false);
671
521k
}
672
673
/// Create a new virtual register and live interval.
674
223k
unsigned SplitEditor::openIntv() {
675
223k
  // Create the complement as index 0.
676
223k
  if (Edit->empty())
677
177k
    Edit->createEmptyInterval();
678
223k
679
223k
  // Create the open interval.
680
223k
  OpenIdx = Edit->size();
681
223k
  Edit->createEmptyInterval();
682
223k
  return OpenIdx;
683
223k
}
684
685
2.26M
void SplitEditor::selectIntv(unsigned Idx) {
686
2.26M
  assert(Idx != 0 && "Cannot select the complement interval");
687
2.26M
  assert(Idx < Edit->size() && "Can only select previously opened interval");
688
2.26M
  LLVM_DEBUG(dbgs() << "    selectIntv " << OpenIdx << " -> " << Idx << '\n');
689
2.26M
  OpenIdx = Idx;
690
2.26M
}
691
692
121k
SlotIndex SplitEditor::enterIntvBefore(SlotIndex Idx) {
693
121k
  assert(OpenIdx && "openIntv not called before enterIntvBefore");
694
121k
  LLVM_DEBUG(dbgs() << "    enterIntvBefore " << Idx);
695
121k
  Idx = Idx.getBaseIndex();
696
121k
  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx);
697
121k
  if (!ParentVNI) {
698
53.6k
    LLVM_DEBUG(dbgs() << ": not live\n");
699
53.6k
    return Idx;
700
53.6k
  }
701
67.6k
  LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
702
67.6k
  MachineInstr *MI = LIS.getInstructionFromIndex(Idx);
703
67.6k
  assert(MI && "enterIntvBefore called with invalid index");
704
67.6k
705
67.6k
  VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), MI);
706
67.6k
  return VNI->def;
707
67.6k
}
708
709
50.2k
SlotIndex SplitEditor::enterIntvAfter(SlotIndex Idx) {
710
50.2k
  assert(OpenIdx && "openIntv not called before enterIntvAfter");
711
50.2k
  LLVM_DEBUG(dbgs() << "    enterIntvAfter " << Idx);
712
50.2k
  Idx = Idx.getBoundaryIndex();
713
50.2k
  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx);
714
50.2k
  if (!ParentVNI) {
715
0
    LLVM_DEBUG(dbgs() << ": not live\n");
716
0
    return Idx;
717
0
  }
718
50.2k
  LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
719
50.2k
  MachineInstr *MI = LIS.getInstructionFromIndex(Idx);
720
50.2k
  assert(MI && "enterIntvAfter called with invalid index");
721
50.2k
722
50.2k
  VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(),
723
50.2k
                              std::next(MachineBasicBlock::iterator(MI)));
724
50.2k
  return VNI->def;
725
50.2k
}
726
727
144k
SlotIndex SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) {
728
144k
  assert(OpenIdx && "openIntv not called before enterIntvAtEnd");
729
144k
  SlotIndex End = LIS.getMBBEndIdx(&MBB);
730
144k
  SlotIndex Last = End.getPrevSlot();
731
144k
  LLVM_DEBUG(dbgs() << "    enterIntvAtEnd " << printMBBReference(MBB) << ", "
732
144k
                    << Last);
733
144k
  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Last);
734
144k
  if (!ParentVNI) {
735
0
    LLVM_DEBUG(dbgs() << ": not live\n");
736
0
    return End;
737
0
  }
738
144k
  LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id);
739
144k
  VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Last, MBB,
740
144k
                              SA.getLastSplitPointIter(&MBB));
741
144k
  RegAssign.insert(VNI->def, End, OpenIdx);
742
144k
  LLVM_DEBUG(dump());
743
144k
  return VNI->def;
744
144k
}
745
746
/// useIntv - indicate that all instructions in MBB should use OpenLI.
747
0
void SplitEditor::useIntv(const MachineBasicBlock &MBB) {
748
0
  useIntv(LIS.getMBBStartIdx(&MBB), LIS.getMBBEndIdx(&MBB));
749
0
}
750
751
2.07M
void SplitEditor::useIntv(SlotIndex Start, SlotIndex End) {
752
2.07M
  assert(OpenIdx && "openIntv not called before useIntv");
753
2.07M
  LLVM_DEBUG(dbgs() << "    useIntv [" << Start << ';' << End << "):");
754
2.07M
  RegAssign.insert(Start, End, OpenIdx);
755
2.07M
  LLVM_DEBUG(dump());
756
2.07M
}
757
758
100k
SlotIndex SplitEditor::leaveIntvAfter(SlotIndex Idx) {
759
100k
  assert(OpenIdx && "openIntv not called before leaveIntvAfter");
760
100k
  LLVM_DEBUG(dbgs() << "    leaveIntvAfter " << Idx);
761
100k
762
100k
  // The interval must be live beyond the instruction at Idx.
763
100k
  SlotIndex Boundary = Idx.getBoundaryIndex();
764
100k
  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Boundary);
765
100k
  if (!ParentVNI) {
766
19.8k
    LLVM_DEBUG(dbgs() << ": not live\n");
767
19.8k
    return Boundary.getNextSlot();
768
19.8k
  }
769
80.6k
  LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
770
80.6k
  MachineInstr *MI = LIS.getInstructionFromIndex(Boundary);
771
80.6k
  assert(MI && "No instruction at index");
772
80.6k
773
80.6k
  // In spill mode, make live ranges as short as possible by inserting the copy
774
80.6k
  // before MI.  This is only possible if that instruction doesn't redefine the
775
80.6k
  // value.  The inserted COPY is not a kill, and we don't need to recompute
776
80.6k
  // the source live range.  The spiller also won't try to hoist this copy.
777
80.6k
  if (SpillMode && 
!SlotIndex::isSameInstr(ParentVNI->def, Idx)53.7k
&&
778
80.6k
      
MI->readsVirtualRegister(Edit->getReg())49.5k
) {
779
49.5k
    forceRecompute(0, *ParentVNI);
780
49.5k
    defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI);
781
49.5k
    return Idx;
782
49.5k
  }
783
31.1k
784
31.1k
  VNInfo *VNI = defFromParent(0, ParentVNI, Boundary, *MI->getParent(),
785
31.1k
                              std::next(MachineBasicBlock::iterator(MI)));
786
31.1k
  return VNI->def;
787
31.1k
}
788
789
43.1k
SlotIndex SplitEditor::leaveIntvBefore(SlotIndex Idx) {
790
43.1k
  assert(OpenIdx && "openIntv not called before leaveIntvBefore");
791
43.1k
  LLVM_DEBUG(dbgs() << "    leaveIntvBefore " << Idx);
792
43.1k
793
43.1k
  // The interval must be live into the instruction at Idx.
794
43.1k
  Idx = Idx.getBaseIndex();
795
43.1k
  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx);
796
43.1k
  if (!ParentVNI) {
797
0
    LLVM_DEBUG(dbgs() << ": not live\n");
798
0
    return Idx.getNextSlot();
799
0
  }
800
43.1k
  LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
801
43.1k
802
43.1k
  MachineInstr *MI = LIS.getInstructionFromIndex(Idx);
803
43.1k
  assert(MI && "No instruction at index");
804
43.1k
  VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI);
805
43.1k
  return VNI->def;
806
43.1k
}
807
808
133k
SlotIndex SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) {
809
133k
  assert(OpenIdx && "openIntv not called before leaveIntvAtTop");
810
133k
  SlotIndex Start = LIS.getMBBStartIdx(&MBB);
811
133k
  LLVM_DEBUG(dbgs() << "    leaveIntvAtTop " << printMBBReference(MBB) << ", "
812
133k
                    << Start);
813
133k
814
133k
  VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start);
815
133k
  if (!ParentVNI) {
816
0
    LLVM_DEBUG(dbgs() << ": not live\n");
817
0
    return Start;
818
0
  }
819
133k
820
133k
  VNInfo *VNI = defFromParent(0, ParentVNI, Start, MBB,
821
133k
                              MBB.SkipPHIsLabelsAndDebug(MBB.begin()));
822
133k
  RegAssign.insert(Start, VNI->def, OpenIdx);
823
133k
  LLVM_DEBUG(dump());
824
133k
  return VNI->def;
825
133k
}
826
827
277
void SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) {
828
277
  assert(OpenIdx && "openIntv not called before overlapIntv");
829
277
  const VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start);
830
277
  assert(ParentVNI == Edit->getParent().getVNInfoBefore(End) &&
831
277
         "Parent changes value in extended range");
832
277
  assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) &&
833
277
         "Range cannot span basic blocks");
834
277
835
277
  // The complement interval will be extended as needed by LRCalc.extend().
836
277
  if (ParentVNI)
837
277
    forceRecompute(0, *ParentVNI);
838
277
  LLVM_DEBUG(dbgs() << "    overlapIntv [" << Start << ';' << End << "):");
839
277
  RegAssign.insert(Start, End, OpenIdx);
840
277
  LLVM_DEBUG(dump());
841
277
}
842
843
//===----------------------------------------------------------------------===//
844
//                                  Spill modes
845
//===----------------------------------------------------------------------===//
846
847
143k
void SplitEditor::removeBackCopies(SmallVectorImpl<VNInfo*> &Copies) {
848
143k
  LiveInterval *LI = &LIS.getInterval(Edit->get(0));
849
143k
  LLVM_DEBUG(dbgs() << "Removing " << Copies.size() << " back-copies.\n");
850
143k
  RegAssignMap::iterator AssignI;
851
143k
  AssignI.setMap(RegAssign);
852
143k
853
184k
  for (unsigned i = 0, e = Copies.size(); i != e; 
++i41.0k
) {
854
41.0k
    SlotIndex Def = Copies[i]->def;
855
41.0k
    MachineInstr *MI = LIS.getInstructionFromIndex(Def);
856
41.0k
    assert(MI && "No instruction for back-copy");
857
41.0k
858
41.0k
    MachineBasicBlock *MBB = MI->getParent();
859
41.0k
    MachineBasicBlock::iterator MBBI(MI);
860
41.0k
    bool AtBegin;
861
41.0k
    do AtBegin = MBBI == MBB->begin();
862
41.0k
    while (!AtBegin && 
(--MBBI)->isDebugInstr()18.9k
);
863
41.0k
864
41.0k
    LLVM_DEBUG(dbgs() << "Removing " << Def << '\t' << *MI);
865
41.0k
    LIS.removeVRegDefAt(*LI, Def);
866
41.0k
    LIS.RemoveMachineInstrFromMaps(*MI);
867
41.0k
    MI->eraseFromParent();
868
41.0k
869
41.0k
    // Adjust RegAssign if a register assignment is killed at Def. We want to
870
41.0k
    // avoid calculating the live range of the source register if possible.
871
41.0k
    AssignI.find(Def.getPrevSlot());
872
41.0k
    if (!AssignI.valid() || AssignI.start() >= Def)
873
0
      continue;
874
41.0k
    // If MI doesn't kill the assigned register, just leave it.
875
41.0k
    if (AssignI.stop() != Def)
876
13.0k
      continue;
877
28.0k
    unsigned RegIdx = AssignI.value();
878
28.0k
    if (AtBegin || 
!MBBI->readsVirtualRegister(Edit->getReg())6.74k
) {
879
27.9k
      LLVM_DEBUG(dbgs() << "  cannot find simple kill of RegIdx " << RegIdx
880
27.9k
                        << '\n');
881
27.9k
      forceRecompute(RegIdx, *Edit->getParent().getVNInfoAt(Def));
882
27.9k
    } else {
883
155
      SlotIndex Kill = LIS.getInstructionIndex(*MBBI).getRegSlot();
884
155
      LLVM_DEBUG(dbgs() << "  move kill to " << Kill << '\t' << *MBBI);
885
155
      AssignI.setStop(Kill);
886
155
    }
887
28.0k
  }
888
143k
}
889
890
MachineBasicBlock*
891
SplitEditor::findShallowDominator(MachineBasicBlock *MBB,
892
26.8k
                                  MachineBasicBlock *DefMBB) {
893
26.8k
  if (MBB == DefMBB)
894
15.5k
    return MBB;
895
11.2k
  assert(MDT.dominates(DefMBB, MBB) && "MBB must be dominated by the def.");
896
11.2k
897
11.2k
  const MachineLoopInfo &Loops = SA.Loops;
898
11.2k
  const MachineLoop *DefLoop = Loops.getLoopFor(DefMBB);
899
11.2k
  MachineDomTreeNode *DefDomNode = MDT[DefMBB];
900
11.2k
901
11.2k
  // Best candidate so far.
902
11.2k
  MachineBasicBlock *BestMBB = MBB;
903
11.2k
  unsigned BestDepth = std::numeric_limits<unsigned>::max();
904
11.2k
905
22.9k
  while (true) {
906
22.9k
    const MachineLoop *Loop = Loops.getLoopFor(MBB);
907
22.9k
908
22.9k
    // MBB isn't in a loop, it doesn't get any better.  All dominators have a
909
22.9k
    // higher frequency by definition.
910
22.9k
    if (!Loop) {
911
10.2k
      LLVM_DEBUG(dbgs() << "Def in " << printMBBReference(*DefMBB)
912
10.2k
                        << " dominates " << printMBBReference(*MBB)
913
10.2k
                        << " at depth 0\n");
914
10.2k
      return MBB;
915
10.2k
    }
916
12.7k
917
12.7k
    // We'll never be able to exit the DefLoop.
918
12.7k
    if (Loop == DefLoop) {
919
1.02k
      LLVM_DEBUG(dbgs() << "Def in " << printMBBReference(*DefMBB)
920
1.02k
                        << " dominates " << printMBBReference(*MBB)
921
1.02k
                        << " in the same loop\n");
922
1.02k
      return MBB;
923
1.02k
    }
924
11.6k
925
11.6k
    // Least busy dominator seen so far.
926
11.6k
    unsigned Depth = Loop->getLoopDepth();
927
11.6k
    if (Depth < BestDepth) {
928
11.6k
      BestMBB = MBB;
929
11.6k
      BestDepth = Depth;
930
11.6k
      LLVM_DEBUG(dbgs() << "Def in " << printMBBReference(*DefMBB)
931
11.6k
                        << " dominates " << printMBBReference(*MBB)
932
11.6k
                        << " at depth " << Depth << '\n');
933
11.6k
    }
934
11.6k
935
11.6k
    // Leave loop by going to the immediate dominator of the loop header.
936
11.6k
    // This is a bigger stride than simply walking up the dominator tree.
937
11.6k
    MachineDomTreeNode *IDom = MDT[Loop->getHeader()]->getIDom();
938
11.6k
939
11.6k
    // Too far up the dominator tree?
940
11.6k
    if (!IDom || !MDT.dominates(DefDomNode, IDom))
941
26
      return BestMBB;
942
11.6k
943
11.6k
    MBB = IDom->getBlock();
944
11.6k
  }
945
11.2k
}
946
947
void SplitEditor::computeRedundantBackCopies(
948
24.6k
    DenseSet<unsigned> &NotToHoistSet, SmallVectorImpl<VNInfo *> &BackCopies) {
949
24.6k
  LiveInterval *LI = &LIS.getInterval(Edit->get(0));
950
24.6k
  LiveInterval *Parent = &Edit->getParent();
951
24.6k
  SmallVector<SmallPtrSet<VNInfo *, 8>, 8> EqualVNs(Parent->getNumValNums());
952
24.6k
  SmallPtrSet<VNInfo *, 8> DominatedVNIs;
953
24.6k
954
24.6k
  // Aggregate VNIs having the same value as ParentVNI.
955
73.0k
  for (VNInfo *VNI : LI->valnos) {
956
73.0k
    if (VNI->isUnused())
957
0
      continue;
958
73.0k
    VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def);
959
73.0k
    EqualVNs[ParentVNI->id].insert(VNI);
960
73.0k
  }
961
24.6k
962
24.6k
  // For VNI aggregation of each ParentVNI, collect dominated, i.e.,
963
24.6k
  // redundant VNIs to BackCopies.
964
62.9k
  for (unsigned i = 0, e = Parent->getNumValNums(); i != e; 
++i38.2k
) {
965
38.2k
    VNInfo *ParentVNI = Parent->getValNumInfo(i);
966
38.2k
    if (!NotToHoistSet.count(ParentVNI->id))
967
13.3k
      continue;
968
24.9k
    SmallPtrSetIterator<VNInfo *> It1 = EqualVNs[ParentVNI->id].begin();
969
24.9k
    SmallPtrSetIterator<VNInfo *> It2 = It1;
970
93.9k
    for (; It1 != EqualVNs[ParentVNI->id].end(); 
++It169.0k
) {
971
69.0k
      It2 = It1;
972
377k
      for (++It2; It2 != EqualVNs[ParentVNI->id].end(); 
++It2308k
) {
973
308k
        if (DominatedVNIs.count(*It1) || 
DominatedVNIs.count(*It2)265k
)
974
51.9k
          continue;
975
256k
976
256k
        MachineBasicBlock *MBB1 = LIS.getMBBFromIndex((*It1)->def);
977
256k
        MachineBasicBlock *MBB2 = LIS.getMBBFromIndex((*It2)->def);
978
256k
        if (MBB1 == MBB2) {
979
0
          DominatedVNIs.insert((*It1)->def < (*It2)->def ? (*It2) : (*It1));
980
256k
        } else if (MDT.dominates(MBB1, MBB2)) {
981
4.97k
          DominatedVNIs.insert(*It2);
982
251k
        } else if (MDT.dominates(MBB2, MBB1)) {
983
1.42k
          DominatedVNIs.insert(*It1);
984
1.42k
        }
985
256k
      }
986
69.0k
    }
987
24.9k
    if (!DominatedVNIs.empty()) {
988
2.48k
      forceRecompute(0, *ParentVNI);
989
6.40k
      for (auto VNI : DominatedVNIs) {
990
6.40k
        BackCopies.push_back(VNI);
991
6.40k
      }
992
2.48k
      DominatedVNIs.clear();
993
2.48k
    }
994
24.9k
  }
995
24.6k
}
996
997
/// For SM_Size mode, find a common dominator for all the back-copies for
998
/// the same ParentVNI and hoist the backcopies to the dominator BB.
999
/// For SM_Speed mode, if the common dominator is hot and it is not beneficial
1000
/// to do the hoisting, simply remove the dominated backcopies for the same
1001
/// ParentVNI.
1002
143k
void SplitEditor::hoistCopies() {
1003
143k
  // Get the complement interval, always RegIdx 0.
1004
143k
  LiveInterval *LI = &LIS.getInterval(Edit->get(0));
1005
143k
  LiveInterval *Parent = &Edit->getParent();
1006
143k
1007
143k
  // Track the nearest common dominator for all back-copies for each ParentVNI,
1008
143k
  // indexed by ParentVNI->id.
1009
143k
  using DomPair = std::pair<MachineBasicBlock *, SlotIndex>;
1010
143k
  SmallVector<DomPair, 8> NearestDom(Parent->getNumValNums());
1011
143k
  // The total cost of all the back-copies for each ParentVNI.
1012
143k
  SmallVector<BlockFrequency, 8> Costs(Parent->getNumValNums());
1013
143k
  // The ParentVNI->id set for which hoisting back-copies are not beneficial
1014
143k
  // for Speed.
1015
143k
  DenseSet<unsigned> NotToHoistSet;
1016
143k
1017
143k
  // Find the nearest common dominator for parent values with multiple
1018
143k
  // back-copies.  If a single back-copy dominates, put it in DomPair.second.
1019
267k
  for (VNInfo *VNI : LI->valnos) {
1020
267k
    if (VNI->isUnused())
1021
0
      continue;
1022
267k
    VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def);
1023
267k
    assert(ParentVNI && "Parent not live at complement def");
1024
267k
1025
267k
    // Don't hoist remats.  The complement is probably going to disappear
1026
267k
    // completely anyway.
1027
267k
    if (Edit->didRematerialize(ParentVNI))
1028
68.3k
      continue;
1029
199k
1030
199k
    MachineBasicBlock *ValMBB = LIS.getMBBFromIndex(VNI->def);
1031
199k
1032
199k
    DomPair &Dom = NearestDom[ParentVNI->id];
1033
199k
1034
199k
    // Keep directly defined parent values.  This is either a PHI or an
1035
199k
    // instruction in the complement range.  All other copies of ParentVNI
1036
199k
    // should be eliminated.
1037
199k
    if (VNI->def == ParentVNI->def) {
1038
27.8k
      LLVM_DEBUG(dbgs() << "Direct complement def at " << VNI->def << '\n');
1039
27.8k
      Dom = DomPair(ValMBB, VNI->def);
1040
27.8k
      continue;
1041
27.8k
    }
1042
171k
    // Skip the singly mapped values.  There is nothing to gain from hoisting a
1043
171k
    // single back-copy.
1044
171k
    if (Values.lookup(std::make_pair(0, ParentVNI->id)).getPointer()) {
1045
42.1k
      LLVM_DEBUG(dbgs() << "Single complement def at " << VNI->def << '\n');
1046
42.1k
      continue;
1047
42.1k
    }
1048
129k
1049
129k
    if (!Dom.first) {
1050
58.9k
      // First time we see ParentVNI.  VNI dominates itself.
1051
58.9k
      Dom = DomPair(ValMBB, VNI->def);
1052
70.2k
    } else if (Dom.first == ValMBB) {
1053
36
      // Two defs in the same block.  Pick the earlier def.
1054
36
      if (!Dom.second.isValid() || 
VNI->def < Dom.second2
)
1055
34
        Dom.second = VNI->def;
1056
70.2k
    } else {
1057
70.2k
      // Different basic blocks. Check if one dominates.
1058
70.2k
      MachineBasicBlock *Near =
1059
70.2k
        MDT.findNearestCommonDominator(Dom.first, ValMBB);
1060
70.2k
      if (Near == ValMBB)
1061
1.23k
        // Def ValMBB dominates.
1062
1.23k
        Dom = DomPair(ValMBB, VNI->def);
1063
69.0k
      else if (Near != Dom.first)
1064
30.5k
        // None dominate. Hoist to common dominator, need new def.
1065
30.5k
        Dom = DomPair(Near, SlotIndex());
1066
70.2k
      Costs[ParentVNI->id] += MBFI.getBlockFreq(ValMBB);
1067
70.2k
    }
1068
129k
1069
129k
    LLVM_DEBUG(dbgs() << "Multi-mapped complement " << VNI->id << '@'
1070
129k
                      << VNI->def << " for parent " << ParentVNI->id << '@'
1071
129k
                      << ParentVNI->def << " hoist to "
1072
129k
                      << printMBBReference(*Dom.first) << ' ' << Dom.second
1073
129k
                      << '\n');
1074
129k
  }
1075
143k
1076
143k
  // Insert the hoisted copies.
1077
369k
  for (unsigned i = 0, e = Parent->getNumValNums(); i != e; 
++i226k
) {
1078
226k
    DomPair &Dom = NearestDom[i];
1079
226k
    if (!Dom.first || 
Dom.second.isValid()80.1k
)
1080
199k
      continue;
1081
26.8k
    // This value needs a hoisted copy inserted at the end of Dom.first.
1082
26.8k
    VNInfo *ParentVNI = Parent->getValNumInfo(i);
1083
26.8k
    MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(ParentVNI->def);
1084
26.8k
    // Get a less loopy dominator than Dom.first.
1085
26.8k
    Dom.first = findShallowDominator(Dom.first, DefMBB);
1086
26.8k
    if (SpillMode == SM_Speed &&
1087
26.8k
        MBFI.getBlockFreq(Dom.first) > Costs[ParentVNI->id]) {
1088
24.9k
      NotToHoistSet.insert(ParentVNI->id);
1089
24.9k
      continue;
1090
24.9k
    }
1091
1.90k
    SlotIndex Last = LIS.getMBBEndIdx(Dom.first).getPrevSlot();
1092
1.90k
    Dom.second =
1093
1.90k
      defFromParent(0, ParentVNI, Last, *Dom.first,
1094
1.90k
                    SA.getLastSplitPointIter(Dom.first))->def;
1095
1.90k
  }
1096
143k
1097
143k
  // Remove redundant back-copies that are now known to be dominated by another
1098
143k
  // def with the same value.
1099
143k
  SmallVector<VNInfo*, 8> BackCopies;
1100
269k
  for (VNInfo *VNI : LI->valnos) {
1101
269k
    if (VNI->isUnused())
1102
0
      continue;
1103
269k
    VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def);
1104
269k
    const DomPair &Dom = NearestDom[ParentVNI->id];
1105
269k
    if (!Dom.first || 
Dom.second == VNI->def158k
||
1106
269k
        
NotToHoistSet.count(ParentVNI->id)103k
)
1107
234k
      continue;
1108
34.6k
    BackCopies.push_back(VNI);
1109
34.6k
    forceRecompute(0, *ParentVNI);
1110
34.6k
  }
1111
143k
1112
143k
  // If it is not beneficial to hoist all the BackCopies, simply remove
1113
143k
  // redundant BackCopies in speed mode.
1114
143k
  if (SpillMode == SM_Speed && 
!NotToHoistSet.empty()143k
)
1115
24.6k
    computeRedundantBackCopies(NotToHoistSet, BackCopies);
1116
143k
1117
143k
  removeBackCopies(BackCopies);
1118
143k
}
1119
1120
/// transferValues - Transfer all possible values to the new live ranges.
1121
/// Values that were rematerialized are left alone, they need LRCalc.extend().
1122
177k
bool SplitEditor::transferValues() {
1123
177k
  bool Skipped = false;
1124
177k
  RegAssignMap::const_iterator AssignI = RegAssign.begin();
1125
627k
  for (const LiveRange::Segment &S : Edit->getParent()) {
1126
627k
    LLVM_DEBUG(dbgs() << "  blit " << S << ':');
1127
627k
    VNInfo *ParentVNI = S.valno;
1128
627k
    // RegAssign has holes where RegIdx 0 should be used.
1129
627k
    SlotIndex Start = S.start;
1130
627k
    AssignI.advanceTo(Start);
1131
1.26M
    do {
1132
1.26M
      unsigned RegIdx;
1133
1.26M
      SlotIndex End = S.end;
1134
1.26M
      if (!AssignI.valid()) {
1135
168k
        RegIdx = 0;
1136
1.09M
      } else if (AssignI.start() <= Start) {
1137
674k
        RegIdx = AssignI.value();
1138
674k
        if (AssignI.stop() < End) {
1139
355k
          End = AssignI.stop();
1140
355k
          ++AssignI;
1141
355k
        }
1142
674k
      } else {
1143
420k
        RegIdx = 0;
1144
420k
        End = std::min(End, AssignI.start());
1145
420k
      }
1146
1.26M
1147
1.26M
      // The interval [Start;End) is continuously mapped to RegIdx, ParentVNI.
1148
1.26M
      LLVM_DEBUG(dbgs() << " [" << Start << ';' << End << ")=" << RegIdx << '('
1149
1.26M
                        << printReg(Edit->get(RegIdx)) << ')');
1150
1.26M
      LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));
1151
1.26M
1152
1.26M
      // Check for a simply defined value that can be blitted directly.
1153
1.26M
      ValueForcePair VFP = Values.lookup(std::make_pair(RegIdx, ParentVNI->id));
1154
1.26M
      if (VNInfo *VNI = VFP.getPointer()) {
1155
422k
        LLVM_DEBUG(dbgs() << ':' << VNI->id);
1156
422k
        LI.addSegment(LiveInterval::Segment(Start, End, VNI));
1157
422k
        Start = End;
1158
422k
        continue;
1159
422k
      }
1160
840k
1161
840k
      // Skip values with forced recomputation.
1162
840k
      if (VFP.getInt()) {
1163
570k
        LLVM_DEBUG(dbgs() << "(recalc)");
1164
570k
        Skipped = true;
1165
570k
        Start = End;
1166
570k
        continue;
1167
570k
      }
1168
269k
1169
269k
      LiveRangeCalc &LRC = getLRCalc(RegIdx);
1170
269k
1171
269k
      // This value has multiple defs in RegIdx, but it wasn't rematerialized,
1172
269k
      // so the live range is accurate. Add live-in blocks in [Start;End) to the
1173
269k
      // LiveInBlocks.
1174
269k
      MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start)->getIterator();
1175
269k
      SlotIndex BlockStart, BlockEnd;
1176
269k
      std::tie(BlockStart, BlockEnd) = LIS.getSlotIndexes()->getMBBRange(&*MBB);
1177
269k
1178
269k
      // The first block may be live-in, or it may have its own def.
1179
269k
      if (Start != BlockStart) {
1180
166k
        VNInfo *VNI = LI.extendInBlock(BlockStart, std::min(BlockEnd, End));
1181
166k
        assert(VNI && "Missing def for complex mapped value");
1182
166k
        LLVM_DEBUG(dbgs() << ':' << VNI->id << "*" << printMBBReference(*MBB));
1183
166k
        // MBB has its own def. Is it also live-out?
1184
166k
        if (BlockEnd <= End)
1185
154k
          LRC.setLiveOutValue(&*MBB, VNI);
1186
166k
1187
166k
        // Skip to the next block for live-in.
1188
166k
        ++MBB;
1189
166k
        BlockStart = BlockEnd;
1190
166k
      }
1191
269k
1192
269k
      // Handle the live-in blocks covered by [Start;End).
1193
269k
      assert(Start <= BlockStart && "Expected live-in block");
1194
1.41M
      while (BlockStart < End) {
1195
1.14M
        LLVM_DEBUG(dbgs() << ">" << printMBBReference(*MBB));
1196
1.14M
        BlockEnd = LIS.getMBBEndIdx(&*MBB);
1197
1.14M
        if (BlockStart == ParentVNI->def) {
1198
4.03k
          // This block has the def of a parent PHI, so it isn't live-in.
1199
4.03k
          assert(ParentVNI->isPHIDef() && "Non-phi defined at block start?");
1200
4.03k
          VNInfo *VNI = LI.extendInBlock(BlockStart, std::min(BlockEnd, End));
1201
4.03k
          assert(VNI && "Missing def for complex mapped parent PHI");
1202
4.03k
          if (End >= BlockEnd)
1203
3.04k
            LRC.setLiveOutValue(&*MBB, VNI); // Live-out as well.
1204
1.13M
        } else {
1205
1.13M
          // This block needs a live-in value.  The last block covered may not
1206
1.13M
          // be live-out.
1207
1.13M
          if (End < BlockEnd)
1208
121k
            LRC.addLiveInBlock(LI, MDT[&*MBB], End);
1209
1.01M
          else {
1210
1.01M
            // Live-through, and we don't know the value.
1211
1.01M
            LRC.addLiveInBlock(LI, MDT[&*MBB]);
1212
1.01M
            LRC.setLiveOutValue(&*MBB, nullptr);
1213
1.01M
          }
1214
1.13M
        }
1215
1.14M
        BlockStart = BlockEnd;
1216
1.14M
        ++MBB;
1217
1.14M
      }
1218
269k
      Start = End;
1219
1.26M
    } while (Start != S.end);
1220
627k
    LLVM_DEBUG(dbgs() << '\n');
1221
627k
  }
1222
177k
1223
177k
  LRCalc[0].calculateValues();
1224
177k
  if (SpillMode)
1225
143k
    LRCalc[1].calculateValues();
1226
177k
1227
177k
  return Skipped;
1228
177k
}
1229
1230
17.2k
static bool removeDeadSegment(SlotIndex Def, LiveRange &LR) {
1231
17.2k
  const LiveRange::Segment *Seg = LR.getSegmentContaining(Def);
1232
17.2k
  if (Seg == nullptr)
1233
0
    return true;
1234
17.2k
  if (Seg->end != Def.getDeadSlot())
1235
16.2k
    return false;
1236
941
  // This is a dead PHI. Remove it.
1237
941
  LR.removeSegment(*Seg, true);
1238
941
  return true;
1239
941
}
1240
1241
void SplitEditor::extendPHIRange(MachineBasicBlock &B, LiveRangeCalc &LRC,
1242
                                 LiveRange &LR, LaneBitmask LM,
1243
16.2k
                                 ArrayRef<SlotIndex> Undefs) {
1244
61.9k
  for (MachineBasicBlock *P : B.predecessors()) {
1245
61.9k
    SlotIndex End = LIS.getMBBEndIdx(P);
1246
61.9k
    SlotIndex LastUse = End.getPrevSlot();
1247
61.9k
    // The predecessor may not have a live-out value. That is OK, like an
1248
61.9k
    // undef PHI operand.
1249
61.9k
    LiveInterval &PLI = Edit->getParent();
1250
61.9k
    // Need the cast because the inputs to ?: would otherwise be deemed
1251
61.9k
    // "incompatible": SubRange vs LiveInterval.
1252
61.9k
    LiveRange &PSR = !LM.all() ? 
getSubRangeForMask(LM, PLI)12
1253
61.9k
                               : 
static_cast<LiveRange&>(PLI)61.9k
;
1254
61.9k
    if (PSR.liveAt(LastUse))
1255
61.9k
      LRC.extend(LR, End, /*PhysReg=*/0, Undefs);
1256
61.9k
  }
1257
16.2k
}
1258
1259
76.1k
void SplitEditor::extendPHIKillRanges() {
1260
76.1k
  // Extend live ranges to be live-out for successor PHI values.
1261
76.1k
1262
76.1k
  // Visit each PHI def slot in the parent live interval. If the def is dead,
1263
76.1k
  // remove it. Otherwise, extend the live interval to reach the end indexes
1264
76.1k
  // of all predecessor blocks.
1265
76.1k
1266
76.1k
  LiveInterval &ParentLI = Edit->getParent();
1267
118k
  for (const VNInfo *V : ParentLI.valnos) {
1268
118k
    if (V->isUnused() || 
!V->isPHIDef()118k
)
1269
101k
      continue;
1270
17.2k
1271
17.2k
    unsigned RegIdx = RegAssign.lookup(V->def);
1272
17.2k
    LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));
1273
17.2k
    LiveRangeCalc &LRC = getLRCalc(RegIdx);
1274
17.2k
    MachineBasicBlock &B = *LIS.getMBBFromIndex(V->def);
1275
17.2k
    if (!removeDeadSegment(V->def, LI))
1276
16.2k
      extendPHIRange(B, LRC, LI, LaneBitmask::getAll(), /*Undefs=*/{});
1277
17.2k
  }
1278
76.1k
1279
76.1k
  SmallVector<SlotIndex, 4> Undefs;
1280
76.1k
  LiveRangeCalc SubLRC;
1281
76.1k
1282
76.1k
  for (LiveInterval::SubRange &PS : ParentLI.subranges()) {
1283
457
    for (const VNInfo *V : PS.valnos) {
1284
457
      if (V->isUnused() || !V->isPHIDef())
1285
448
        continue;
1286
9
      unsigned RegIdx = RegAssign.lookup(V->def);
1287
9
      LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));
1288
9
      LiveInterval::SubRange &S = getSubRangeForMask(PS.LaneMask, LI);
1289
9
      if (removeDeadSegment(V->def, S))
1290
3
        continue;
1291
6
1292
6
      MachineBasicBlock &B = *LIS.getMBBFromIndex(V->def);
1293
6
      SubLRC.reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,
1294
6
                   &LIS.getVNInfoAllocator());
1295
6
      Undefs.clear();
1296
6
      LI.computeSubRangeUndefs(Undefs, PS.LaneMask, MRI, *LIS.getSlotIndexes());
1297
6
      extendPHIRange(B, SubLRC, S, PS.LaneMask, Undefs);
1298
6
    }
1299
439
  }
1300
76.1k
}
1301
1302
/// rewriteAssigned - Rewrite all uses of Edit->getReg().
1303
177k
void SplitEditor::rewriteAssigned(bool ExtendRanges) {
1304
177k
  struct ExtPoint {
1305
177k
    ExtPoint(const MachineOperand &O, unsigned R, SlotIndex N)
1306
177k
      : MO(O), RegIdx(R), Next(N) 
{}690
1307
177k
1308
177k
    MachineOperand MO;
1309
177k
    unsigned RegIdx;
1310
177k
    SlotIndex Next;
1311
177k
  };
1312
177k
1313
177k
  SmallVector<ExtPoint,4> ExtPoints;
1314
177k
1315
177k
  for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit->getReg()),
1316
1.47M
       RE = MRI.reg_end(); RI != RE;) {
1317
1.29M
    MachineOperand &MO = *RI;
1318
1.29M
    MachineInstr *MI = MO.getParent();
1319
1.29M
    ++RI;
1320
1.29M
    // LiveDebugVariables should have handled all DBG_VALUE instructions.
1321
1.29M
    if (MI->isDebugValue()) {
1322
0
      LLVM_DEBUG(dbgs() << "Zapping " << *MI);
1323
0
      MO.setReg(0);
1324
0
      continue;
1325
0
    }
1326
1.29M
1327
1.29M
    // <undef> operands don't really read the register, so it doesn't matter
1328
1.29M
    // which register we choose.  When the use operand is tied to a def, we must
1329
1.29M
    // use the same register as the def, so just do that always.
1330
1.29M
    SlotIndex Idx = LIS.getInstructionIndex(*MI);
1331
1.29M
    if (MO.isDef() || 
MO.isUndef()1.04M
)
1332
252k
      Idx = Idx.getRegSlot(MO.isEarlyClobber());
1333
1.29M
1334
1.29M
    // Rewrite to the mapped register at Idx.
1335
1.29M
    unsigned RegIdx = RegAssign.lookup(Idx);
1336
1.29M
    LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));
1337
1.29M
    MO.setReg(LI.reg);
1338
1.29M
    LLVM_DEBUG(dbgs() << "  rewr " << printMBBReference(*MI->getParent())
1339
1.29M
                      << '\t' << Idx << ':' << RegIdx << '\t' << *MI);
1340
1.29M
1341
1.29M
    // Extend liveness to Idx if the instruction reads reg.
1342
1.29M
    if (!ExtendRanges || 
MO.isUndef()585k
)
1343
715k
      continue;
1344
580k
1345
580k
    // Skip instructions that don't read Reg.
1346
580k
    if (MO.isDef()) {
1347
96.9k
      if (!MO.getSubReg() && 
!MO.isEarlyClobber()96.5k
)
1348
96.4k
        continue;
1349
497
      // We may want to extend a live range for a partial redef, or for a use
1350
497
      // tied to an early clobber.
1351
497
      Idx = Idx.getPrevSlot();
1352
497
      if (!Edit->getParent().liveAt(Idx))
1353
12
        continue;
1354
483k
    } else
1355
483k
      Idx = Idx.getRegSlot(true);
1356
580k
1357
580k
    SlotIndex Next = Idx.getNextSlot();
1358
484k
    if (LI.hasSubRanges()) {
1359
739
      // We have to delay extending subranges until we have seen all operands
1360
739
      // defining the register. This is because a <def,read-undef> operand
1361
739
      // will create an "undef" point, and we cannot extend any subranges
1362
739
      // until all of them have been accounted for.
1363
739
      if (MO.isUse())
1364
690
        ExtPoints.push_back(ExtPoint(MO, RegIdx, Next));
1365
483k
    } else {
1366
483k
      LiveRangeCalc &LRC = getLRCalc(RegIdx);
1367
483k
      LRC.extend(LI, Next, 0, ArrayRef<SlotIndex>());
1368
483k
    }
1369
484k
  }
1370
177k
1371
177k
  for (ExtPoint &EP : ExtPoints) {
1372
690
    LiveInterval &LI = LIS.getInterval(Edit->get(EP.RegIdx));
1373
690
    assert(LI.hasSubRanges());
1374
690
1375
690
    LiveRangeCalc SubLRC;
1376
690
    unsigned Reg = EP.MO.getReg(), Sub = EP.MO.getSubReg();
1377
690
    LaneBitmask LM = Sub != 0 ? 
TRI.getSubRegIndexLaneMask(Sub)348
1378
690
                              : 
MRI.getMaxLaneMaskForVReg(Reg)342
;
1379
2.15k
    for (LiveInterval::SubRange &S : LI.subranges()) {
1380
2.15k
      if ((S.LaneMask & LM).none())
1381
908
        continue;
1382
1.24k
      // The problem here can be that the new register may have been created
1383
1.24k
      // for a partially defined original register. For example:
1384
1.24k
      //   %0:subreg_hireg<def,read-undef> = ...
1385
1.24k
      //   ...
1386
1.24k
      //   %1 = COPY %0
1387
1.24k
      if (S.empty())
1388
3
        continue;
1389
1.24k
      SubLRC.reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,
1390
1.24k
                   &LIS.getVNInfoAllocator());
1391
1.24k
      SmallVector<SlotIndex, 4> Undefs;
1392
1.24k
      LI.computeSubRangeUndefs(Undefs, S.LaneMask, MRI, *LIS.getSlotIndexes());
1393
1.24k
      SubLRC.extend(S, EP.Next, 0, Undefs);
1394
1.24k
    }
1395
690
  }
1396
177k
1397
401k
  for (unsigned R : *Edit) {
1398
401k
    LiveInterval &LI = LIS.getInterval(R);
1399
401k
    if (!LI.hasSubRanges())
1400
401k
      continue;
1401
317
    LI.clear();
1402
317
    LI.removeEmptySubRanges();
1403
317
    LIS.constructMainRangeFromSubranges(LI);
1404
317
  }
1405
177k
}
1406
1407
76.1k
void SplitEditor::deleteRematVictims() {
1408
76.1k
  SmallVector<MachineInstr*, 8> Dead;
1409
254k
  for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; 
++I178k
){
1410
178k
    LiveInterval *LI = &LIS.getInterval(*I);
1411
673k
    for (const LiveRange::Segment &S : LI->segments) {
1412
673k
      // Dead defs end at the dead slot.
1413
673k
      if (S.end != S.valno->def.getDeadSlot())
1414
597k
        continue;
1415
76.4k
      if (S.valno->isPHIDef())
1416
0
        continue;
1417
76.4k
      MachineInstr *MI = LIS.getInstructionFromIndex(S.valno->def);
1418
76.4k
      assert(MI && "Missing instruction for dead def");
1419
76.4k
      MI->addRegisterDead(LI->reg, &TRI);
1420
76.4k
1421
76.4k
      if (!MI->allDefsAreDead())
1422
33
        continue;
1423
76.3k
1424
76.3k
      LLVM_DEBUG(dbgs() << "All defs dead: " << *MI);
1425
76.3k
      Dead.push_back(MI);
1426
76.3k
    }
1427
178k
  }
1428
76.1k
1429
76.1k
  if (Dead.empty())
1430
44.6k
    return;
1431
31.4k
1432
31.4k
  Edit->eliminateDeadDefs(Dead, None, &AA);
1433
31.4k
}
1434
1435
36.6k
void SplitEditor::forceRecomputeVNI(const VNInfo &ParentVNI) {
1436
36.6k
  // Fast-path for common case.
1437
36.6k
  if (!ParentVNI.isPHIDef()) {
1438
114k
    for (unsigned I = 0, E = Edit->size(); I != E; 
++I78.4k
)
1439
78.4k
      forceRecompute(I, ParentVNI);
1440
36.3k
    return;
1441
36.3k
  }
1442
330
1443
330
  // Trace value through phis.
1444
330
  SmallPtrSet<const VNInfo *, 8> Visited; ///< whether VNI was/is in worklist.
1445
330
  SmallVector<const VNInfo *, 4> WorkList;
1446
330
  Visited.insert(&ParentVNI);
1447
330
  WorkList.push_back(&ParentVNI);
1448
330
1449
330
  const LiveInterval &ParentLI = Edit->getParent();
1450
330
  const SlotIndexes &Indexes = *LIS.getSlotIndexes();
1451
4.26k
  do {
1452
4.26k
    const VNInfo &VNI = *WorkList.back();
1453
4.26k
    WorkList.pop_back();
1454
15.9k
    for (unsigned I = 0, E = Edit->size(); I != E; 
++I11.7k
)
1455
11.7k
      forceRecompute(I, VNI);
1456
4.26k
    if (!VNI.isPHIDef())
1457
2.25k
      continue;
1458
2.01k
1459
2.01k
    MachineBasicBlock &MBB = *Indexes.getMBBFromIndex(VNI.def);
1460
6.59k
    for (const MachineBasicBlock *Pred : MBB.predecessors()) {
1461
6.59k
      SlotIndex PredEnd = Indexes.getMBBEndIdx(Pred);
1462
6.59k
      VNInfo *PredVNI = ParentLI.getVNInfoBefore(PredEnd);
1463
6.59k
      assert(PredVNI && "Value available in PhiVNI predecessor");
1464
6.59k
      if (Visited.insert(PredVNI).second)
1465
3.93k
        WorkList.push_back(PredVNI);
1466
6.59k
    }
1467
4.26k
  } while(!WorkList.empty());
1468
330
}
1469
1470
177k
void SplitEditor::finish(SmallVectorImpl<unsigned> *LRMap) {
1471
177k
  ++NumFinished;
1472
177k
1473
177k
  // At this point, the live intervals in Edit contain VNInfos corresponding to
1474
177k
  // the inserted copies.
1475
177k
1476
177k
  // Add the original defs from the parent interval.
1477
285k
  for (const VNInfo *ParentVNI : Edit->getParent().valnos) {
1478
285k
    if (ParentVNI->isUnused())
1479
28
      continue;
1480
285k
    unsigned RegIdx = RegAssign.lookup(ParentVNI->def);
1481
285k
    defValue(RegIdx, ParentVNI, ParentVNI->def, true);
1482
285k
1483
285k
    // Force rematted values to be recomputed everywhere.
1484
285k
    // The new live ranges may be truncated.
1485
285k
    if (Edit->didRematerialize(ParentVNI))
1486
36.6k
      forceRecomputeVNI(*ParentVNI);
1487
285k
  }
1488
177k
1489
177k
  // Hoist back-copies to the complement interval when in spill mode.
1490
177k
  switch (SpillMode) {
1491
177k
  case SM_Partition:
1492
34.8k
    // Leave all back-copies as is.
1493
34.8k
    break;
1494
177k
  case SM_Size:
1495
143k
  case SM_Speed:
1496
143k
    // hoistCopies will behave differently between size and speed.
1497
143k
    hoistCopies();
1498
177k
  }
1499
177k
1500
177k
  // Transfer the simply mapped values, check if any are skipped.
1501
177k
  bool Skipped = transferValues();
1502
177k
1503
177k
  // Rewrite virtual registers, possibly extending ranges.
1504
177k
  rewriteAssigned(Skipped);
1505
177k
1506
177k
  if (Skipped)
1507
76.1k
    extendPHIKillRanges();
1508
101k
  else
1509
101k
    ++NumSimple;
1510
177k
1511
177k
  // Delete defs that were rematted everywhere.
1512
177k
  if (Skipped)
1513
76.1k
    deleteRematVictims();
1514
177k
1515
177k
  // Get rid of unused values and set phi-kill flags.
1516
401k
  for (unsigned Reg : *Edit) {
1517
401k
    LiveInterval &LI = LIS.getInterval(Reg);
1518
401k
    LI.removeEmptySubRanges();
1519
401k
    LI.RenumberValues();
1520
401k
  }
1521
177k
1522
177k
  // Provide a reverse mapping from original indices to Edit ranges.
1523
177k
  if (LRMap) {
1524
177k
    LRMap->clear();
1525
579k
    for (unsigned i = 0, e = Edit->size(); i != e; 
++i401k
)
1526
401k
      LRMap->push_back(i);
1527
177k
  }
1528
177k
1529
177k
  // Now check if any registers were separated into multiple components.
1530
177k
  ConnectedVNInfoEqClasses ConEQ(LIS);
1531
579k
  for (unsigned i = 0, e = Edit->size(); i != e; 
++i401k
) {
1532
401k
    // Don't use iterators, they are invalidated by create() below.
1533
401k
    unsigned VReg = Edit->get(i);
1534
401k
    LiveInterval &LI = LIS.getInterval(VReg);
1535
401k
    SmallVector<LiveInterval*, 8> SplitLIs;
1536
401k
    LIS.splitSeparateComponents(LI, SplitLIs);
1537
401k
    unsigned Original = VRM.getOriginal(VReg);
1538
401k
    for (LiveInterval *SplitLI : SplitLIs)
1539
51.3k
      VRM.setIsSplitFromReg(SplitLI->reg, Original);
1540
401k
1541
401k
    // The new intervals all map back to i.
1542
401k
    if (LRMap)
1543
401k
      LRMap->resize(Edit->size(), i);
1544
401k
  }
1545
177k
1546
177k
  // Calculate spill weight and allocation hints for new intervals.
1547
177k
  Edit->calculateRegClassAndHint(VRM.getMachineFunction(), SA.Loops, MBFI);
1548
177k
1549
177k
  assert(!LRMap || LRMap->size() == Edit->size());
1550
177k
}
1551
1552
//===----------------------------------------------------------------------===//
1553
//                            Single Block Splitting
1554
//===----------------------------------------------------------------------===//
1555
1556
bool SplitAnalysis::shouldSplitSingleBlock(const BlockInfo &BI,
1557
444k
                                           bool SingleInstrs) const {
1558
444k
  // Always split for multiple instructions.
1559
444k
  if (!BI.isOneInstr())
1560
46.2k
    return true;
1561
398k
  // Don't split for single instructions unless explicitly requested.
1562
398k
  if (!SingleInstrs)
1563
398k
    return false;
1564
360
  // Splitting a live-through range always makes progress.
1565
360
  if (BI.LiveIn && 
BI.LiveOut206
)
1566
85
    return true;
1567
275
  // No point in isolating a copy. It has no register class constraints.
1568
275
  if (LIS.getInstructionFromIndex(BI.FirstInstr)->isCopyLike())
1569
31
    return false;
1570
244
  // Finally, don't isolate an end point that was created by earlier splits.
1571
244
  return isOriginalEndpoint(BI.FirstInstr);
1572
244
}
1573
1574
46.6k
void SplitEditor::splitSingleBlock(const SplitAnalysis::BlockInfo &BI) {
1575
46.6k
  openIntv();
1576
46.6k
  SlotIndex LastSplitPoint = SA.getLastSplitPoint(BI.MBB->getNumber());
1577
46.6k
  SlotIndex SegStart = enterIntvBefore(std::min(BI.FirstInstr,
1578
46.6k
    LastSplitPoint));
1579
46.6k
  if (!BI.LiveOut || 
BI.LastInstr < LastSplitPoint38.4k
) {
1580
46.4k
    useIntv(SegStart, leaveIntvAfter(BI.LastInstr));
1581
46.4k
  } else {
1582
207
      // The last use is after the last valid split point.
1583
207
    SlotIndex SegStop = leaveIntvBefore(LastSplitPoint);
1584
207
    useIntv(SegStart, SegStop);
1585
207
    overlapIntv(SegStop, BI.LastInstr);
1586
207
  }
1587
46.6k
}
1588
1589
//===----------------------------------------------------------------------===//
1590
//                    Global Live Range Splitting Support
1591
//===----------------------------------------------------------------------===//
1592
1593
// These methods support a method of global live range splitting that uses a
1594
// global algorithm to decide intervals for CFG edges. They will insert split
1595
// points and color intervals in basic blocks while avoiding interference.
1596
//
1597
// Note that splitSingleBlock is also useful for blocks where both CFG edges
1598
// are on the stack.
1599
1600
void SplitEditor::splitLiveThroughBlock(unsigned MBBNum,
1601
                                        unsigned IntvIn, SlotIndex LeaveBefore,
1602
1.98M
                                        unsigned IntvOut, SlotIndex EnterAfter){
1603
1.98M
  SlotIndex Start, Stop;
1604
1.98M
  std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(MBBNum);
1605
1.98M
1606
1.98M
  LLVM_DEBUG(dbgs() << "%bb." << MBBNum << " [" << Start << ';' << Stop
1607
1.98M
                    << ") intf " << LeaveBefore << '-' << EnterAfter
1608
1.98M
                    << ", live-through " << IntvIn << " -> " << IntvOut);
1609
1.98M
1610
1.98M
  assert((IntvIn || IntvOut) && "Use splitSingleBlock for isolated blocks");
1611
1.98M
1612
1.98M
  assert((!LeaveBefore || LeaveBefore < Stop) && "Interference after block");
1613
1.98M
  assert((!IntvIn || !LeaveBefore || LeaveBefore > Start) && "Impossible intf");
1614
1.98M
  assert((!EnterAfter || EnterAfter >= Start) && "Interference before block");
1615
1.98M
1616
1.98M
  MachineBasicBlock *MBB = VRM.getMachineFunction().getBlockNumbered(MBBNum);
1617
1.98M
1618
1.98M
  if (!IntvOut) {
1619
133k
    LLVM_DEBUG(dbgs() << ", spill on entry.\n");
1620
133k
    //
1621
133k
    //        <<<<<<<<<    Possible LeaveBefore interference.
1622
133k
    //    |-----------|    Live through.
1623
133k
    //    -____________    Spill on entry.
1624
133k
    //
1625
133k
    selectIntv(IntvIn);
1626
133k
    SlotIndex Idx = leaveIntvAtTop(*MBB);
1627
133k
    assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1628
133k
    (void)Idx;
1629
133k
    return;
1630
133k
  }
1631
1.85M
1632
1.85M
  if (!IntvIn) {
1633
138k
    LLVM_DEBUG(dbgs() << ", reload on exit.\n");
1634
138k
    //
1635
138k
    //    >>>>>>>          Possible EnterAfter interference.
1636
138k
    //    |-----------|    Live through.
1637
138k
    //    ___________--    Reload on exit.
1638
138k
    //
1639
138k
    selectIntv(IntvOut);
1640
138k
    SlotIndex Idx = enterIntvAtEnd(*MBB);
1641
138k
    assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1642
138k
    (void)Idx;
1643
138k
    return;
1644
138k
  }
1645
1.71M
1646
1.71M
  if (IntvIn == IntvOut && 
!LeaveBefore1.70M
&&
!EnterAfter1.65M
) {
1647
1.65M
    LLVM_DEBUG(dbgs() << ", straight through.\n");
1648
1.65M
    //
1649
1.65M
    //    |-----------|    Live through.
1650
1.65M
    //    -------------    Straight through, same intv, no interference.
1651
1.65M
    //
1652
1.65M
    selectIntv(IntvOut);
1653
1.65M
    useIntv(Start, Stop);
1654
1.65M
    return;
1655
1.65M
  }
1656
54.4k
1657
54.4k
  // We cannot legally insert splits after LSP.
1658
54.4k
  SlotIndex LSP = SA.getLastSplitPoint(MBBNum);
1659
54.4k
  assert((!IntvOut || !EnterAfter || EnterAfter < LSP) && "Impossible intf");
1660
54.4k
1661
54.4k
  if (IntvIn != IntvOut && 
(11.6k
!LeaveBefore11.6k
||
!EnterAfter6.00k
||
1662
11.6k
                  
LeaveBefore.getBaseIndex() > EnterAfter.getBoundaryIndex()0
)) {
1663
11.6k
    LLVM_DEBUG(dbgs() << ", switch avoiding interference.\n");
1664
11.6k
    //
1665
11.6k
    //    >>>>     <<<<    Non-overlapping EnterAfter/LeaveBefore interference.
1666
11.6k
    //    |-----------|    Live through.
1667
11.6k
    //    ------=======    Switch intervals between interference.
1668
11.6k
    //
1669
11.6k
    selectIntv(IntvOut);
1670
11.6k
    SlotIndex Idx;
1671
11.6k
    if (LeaveBefore && 
LeaveBefore < LSP6.00k
) {
1672
6.00k
      Idx = enterIntvBefore(LeaveBefore);
1673
6.00k
      useIntv(Idx, Stop);
1674
6.00k
    } else {
1675
5.63k
      Idx = enterIntvAtEnd(*MBB);
1676
5.63k
    }
1677
11.6k
    selectIntv(IntvIn);
1678
11.6k
    useIntv(Start, Idx);
1679
11.6k
    assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1680
11.6k
    assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1681
11.6k
    return;
1682
11.6k
  }
1683
42.8k
1684
42.8k
  LLVM_DEBUG(dbgs() << ", create local intv for interference.\n");
1685
42.8k
  //
1686
42.8k
  //    >>><><><><<<<    Overlapping EnterAfter/LeaveBefore interference.
1687
42.8k
  //    |-----------|    Live through.
1688
42.8k
  //    ==---------==    Switch intervals before/after interference.
1689
42.8k
  //
1690
42.8k
  assert(LeaveBefore <= EnterAfter && "Missed case");
1691
42.8k
1692
42.8k
  selectIntv(IntvOut);
1693
42.8k
  SlotIndex Idx = enterIntvAfter(EnterAfter);
1694
42.8k
  useIntv(Idx, Stop);
1695
42.8k
  assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1696
42.8k
1697
42.8k
  selectIntv(IntvIn);
1698
42.8k
  Idx = leaveIntvBefore(LeaveBefore);
1699
42.8k
  useIntv(Start, Idx);
1700
42.8k
  assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1701
42.8k
}
1702
1703
void SplitEditor::splitRegInBlock(const SplitAnalysis::BlockInfo &BI,
1704
79.0k
                                  unsigned IntvIn, SlotIndex LeaveBefore) {
1705
79.0k
  SlotIndex Start, Stop;
1706
79.0k
  std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);
1707
79.0k
1708
79.0k
  LLVM_DEBUG(dbgs() << printMBBReference(*BI.MBB) << " [" << Start << ';'
1709
79.0k
                    << Stop << "), uses " << BI.FirstInstr << '-'
1710
79.0k
                    << BI.LastInstr << ", reg-in " << IntvIn
1711
79.0k
                    << ", leave before " << LeaveBefore
1712
79.0k
                    << (BI.LiveOut ? ", stack-out" : ", killed in block"));
1713
79.0k
1714
79.0k
  assert(IntvIn && "Must have register in");
1715
79.0k
  assert(BI.LiveIn && "Must be live-in");
1716
79.0k
  assert((!LeaveBefore || LeaveBefore > Start) && "Bad interference");
1717
79.0k
1718
79.0k
  if (!BI.LiveOut && 
(63.4k
!LeaveBefore63.4k
||
LeaveBefore >= BI.LastInstr14.0k
)) {
1719
59.8k
    LLVM_DEBUG(dbgs() << " before interference.\n");
1720
59.8k
    //
1721
59.8k
    //               <<<    Interference after kill.
1722
59.8k
    //     |---o---x   |    Killed in block.
1723
59.8k
    //     =========        Use IntvIn everywhere.
1724
59.8k
    //
1725
59.8k
    selectIntv(IntvIn);
1726
59.8k
    useIntv(Start, BI.LastInstr);
1727
59.8k
    return;
1728
59.8k
  }
1729
19.2k
1730
19.2k
  SlotIndex LSP = SA.getLastSplitPoint(BI.MBB->getNumber());
1731
19.2k
1732
19.2k
  if (!LeaveBefore || 
LeaveBefore > BI.LastInstr.getBoundaryIndex()11.7k
) {
1733
13.3k
    //
1734
13.3k
    //               <<<    Possible interference after last use.
1735
13.3k
    //     |---o---o---|    Live-out on stack.
1736
13.3k
    //     =========____    Leave IntvIn after last use.
1737
13.3k
    //
1738
13.3k
    //                 <    Interference after last use.
1739
13.3k
    //     |---o---o--o|    Live-out on stack, late last use.
1740
13.3k
    //     ============     Copy to stack after LSP, overlap IntvIn.
1741
13.3k
    //            \_____    Stack interval is live-out.
1742
13.3k
    //
1743
13.3k
    if (BI.LastInstr < LSP) {
1744
13.2k
      LLVM_DEBUG(dbgs() << ", spill after last use before interference.\n");
1745
13.2k
      selectIntv(IntvIn);
1746
13.2k
      SlotIndex Idx = leaveIntvAfter(BI.LastInstr);
1747
13.2k
      useIntv(Start, Idx);
1748
13.2k
      assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1749
13.2k
    } else {
1750
57
      LLVM_DEBUG(dbgs() << ", spill before last split point.\n");
1751
57
      selectIntv(IntvIn);
1752
57
      SlotIndex Idx = leaveIntvBefore(LSP);
1753
57
      overlapIntv(Idx, BI.LastInstr);
1754
57
      useIntv(Start, Idx);
1755
57
      assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference");
1756
57
    }
1757
13.3k
    return;
1758
13.3k
  }
1759
5.93k
1760
5.93k
  // The interference is overlapping somewhere we wanted to use IntvIn. That
1761
5.93k
  // means we need to create a local interval that can be allocated a
1762
5.93k
  // different register.
1763
5.93k
  unsigned LocalIntv = openIntv();
1764
5.93k
  (void)LocalIntv;
1765
5.93k
  LLVM_DEBUG(dbgs() << ", creating local interval " << LocalIntv << ".\n");
1766
5.93k
1767
5.93k
  if (!BI.LiveOut || 
BI.LastInstr < LSP2.24k
) {
1768
5.92k
    //
1769
5.92k
    //           <<<<<<<    Interference overlapping uses.
1770
5.92k
    //     |---o---o---|    Live-out on stack.
1771
5.92k
    //     =====----____    Leave IntvIn before interference, then spill.
1772
5.92k
    //
1773
5.92k
    SlotIndex To = leaveIntvAfter(BI.LastInstr);
1774
5.92k
    SlotIndex From = enterIntvBefore(LeaveBefore);
1775
5.92k
    useIntv(From, To);
1776
5.92k
    selectIntv(IntvIn);
1777
5.92k
    useIntv(Start, From);
1778
5.92k
    assert((!LeaveBefore || From <= LeaveBefore) && "Interference");
1779
5.92k
    return;
1780
5.92k
  }
1781
13
1782
13
  //           <<<<<<<    Interference overlapping uses.
1783
13
  //     |---o---o--o|    Live-out on stack, late last use.
1784
13
  //     =====-------     Copy to stack before LSP, overlap LocalIntv.
1785
13
  //            \_____    Stack interval is live-out.
1786
13
  //
1787
13
  SlotIndex To = leaveIntvBefore(LSP);
1788
13
  overlapIntv(To, BI.LastInstr);
1789
13
  SlotIndex From = enterIntvBefore(std::min(To, LeaveBefore));
1790
13
  useIntv(From, To);
1791
13
  selectIntv(IntvIn);
1792
13
  useIntv(Start, From);
1793
13
  assert((!LeaveBefore || From <= LeaveBefore) && "Interference");
1794
13
}
1795
1796
void SplitEditor::splitRegOutBlock(const SplitAnalysis::BlockInfo &BI,
1797
142k
                                   unsigned IntvOut, SlotIndex EnterAfter) {
1798
142k
  SlotIndex Start, Stop;
1799
142k
  std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);
1800
142k
1801
142k
  LLVM_DEBUG(dbgs() << printMBBReference(*BI.MBB) << " [" << Start << ';'
1802
142k
                    << Stop << "), uses " << BI.FirstInstr << '-'
1803
142k
                    << BI.LastInstr << ", reg-out " << IntvOut
1804
142k
                    << ", enter after " << EnterAfter
1805
142k
                    << (BI.LiveIn ? ", stack-in" : ", defined in block"));
1806
142k
1807
142k
  SlotIndex LSP = SA.getLastSplitPoint(BI.MBB->getNumber());
1808
142k
1809
142k
  assert(IntvOut && "Must have register out");
1810
142k
  assert(BI.LiveOut && "Must be live-out");
1811
142k
  assert((!EnterAfter || EnterAfter < LSP) && "Bad interference");
1812
142k
1813
142k
  if (!BI.LiveIn && 
(121k
!EnterAfter121k
||
EnterAfter <= BI.FirstInstr20.9k
)) {
1814
114k
    LLVM_DEBUG(dbgs() << " after interference.\n");
1815
114k
    //
1816
114k
    //    >>>>             Interference before def.
1817
114k
    //    |   o---o---|    Defined in block.
1818
114k
    //        =========    Use IntvOut everywhere.
1819
114k
    //
1820
114k
    selectIntv(IntvOut);
1821
114k
    useIntv(BI.FirstInstr, Stop);
1822
114k
    return;
1823
114k
  }
1824
27.8k
1825
27.8k
  if (!EnterAfter || 
EnterAfter < BI.FirstInstr.getBaseIndex()9.64k
) {
1826
20.4k
    LLVM_DEBUG(dbgs() << ", reload after interference.\n");
1827
20.4k
    //
1828
20.4k
    //    >>>>             Interference before def.
1829
20.4k
    //    |---o---o---|    Live-through, stack-in.
1830
20.4k
    //    ____=========    Enter IntvOut before first use.
1831
20.4k
    //
1832
20.4k
    selectIntv(IntvOut);
1833
20.4k
    SlotIndex Idx = enterIntvBefore(std::min(LSP, BI.FirstInstr));
1834
20.4k
    useIntv(Idx, Stop);
1835
20.4k
    assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1836
20.4k
    return;
1837
20.4k
  }
1838
7.39k
1839
7.39k
  // The interference is overlapping somewhere we wanted to use IntvOut. That
1840
7.39k
  // means we need to create a local interval that can be allocated a
1841
7.39k
  // different register.
1842
7.39k
  LLVM_DEBUG(dbgs() << ", interference overlaps uses.\n");
1843
7.39k
  //
1844
7.39k
  //    >>>>>>>          Interference overlapping uses.
1845
7.39k
  //    |---o---o---|    Live-through, stack-in.
1846
7.39k
  //    ____---======    Create local interval for interference range.
1847
7.39k
  //
1848
7.39k
  selectIntv(IntvOut);
1849
7.39k
  SlotIndex Idx = enterIntvAfter(EnterAfter);
1850
7.39k
  useIntv(Idx, Stop);
1851
7.39k
  assert((!EnterAfter || Idx >= EnterAfter) && "Interference");
1852
7.39k
1853
7.39k
  openIntv();
1854
7.39k
  SlotIndex From = enterIntvBefore(std::min(Idx, BI.FirstInstr));
1855
7.39k
  useIntv(From, Idx);
1856
7.39k
}