Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/LiveIntervals.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- LiveIntervals.cpp - Live Interval Analysis -------------------------===//
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
/// \file This file implements the LiveInterval analysis pass which is used
10
/// by the Linear Scan Register allocator. This pass linearizes the
11
/// basic blocks of the function in DFS order and computes live intervals for
12
/// each virtual and physical register.
13
//
14
//===----------------------------------------------------------------------===//
15
16
#include "llvm/CodeGen/LiveIntervals.h"
17
#include "LiveRangeCalc.h"
18
#include "llvm/ADT/ArrayRef.h"
19
#include "llvm/ADT/DepthFirstIterator.h"
20
#include "llvm/ADT/SmallPtrSet.h"
21
#include "llvm/ADT/SmallVector.h"
22
#include "llvm/ADT/iterator_range.h"
23
#include "llvm/Analysis/AliasAnalysis.h"
24
#include "llvm/CodeGen/LiveInterval.h"
25
#include "llvm/CodeGen/LiveVariables.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/MachineInstrBundle.h"
32
#include "llvm/CodeGen/MachineOperand.h"
33
#include "llvm/CodeGen/MachineRegisterInfo.h"
34
#include "llvm/CodeGen/Passes.h"
35
#include "llvm/CodeGen/SlotIndexes.h"
36
#include "llvm/CodeGen/TargetRegisterInfo.h"
37
#include "llvm/CodeGen/TargetSubtargetInfo.h"
38
#include "llvm/CodeGen/VirtRegMap.h"
39
#include "llvm/Config/llvm-config.h"
40
#include "llvm/MC/LaneBitmask.h"
41
#include "llvm/MC/MCRegisterInfo.h"
42
#include "llvm/Pass.h"
43
#include "llvm/Support/BlockFrequency.h"
44
#include "llvm/Support/CommandLine.h"
45
#include "llvm/Support/Compiler.h"
46
#include "llvm/Support/Debug.h"
47
#include "llvm/Support/MathExtras.h"
48
#include "llvm/Support/raw_ostream.h"
49
#include <algorithm>
50
#include <cassert>
51
#include <cstdint>
52
#include <iterator>
53
#include <tuple>
54
#include <utility>
55
56
using namespace llvm;
57
58
#define DEBUG_TYPE "regalloc"
59
60
char LiveIntervals::ID = 0;
61
char &llvm::LiveIntervalsID = LiveIntervals::ID;
62
102k
INITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals",
63
102k
                "Live Interval Analysis", false, false)
64
102k
INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
65
102k
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
66
102k
INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
67
102k
INITIALIZE_PASS_END(LiveIntervals, "liveintervals",
68
                "Live Interval Analysis", false, false)
69
70
#ifndef NDEBUG
71
static cl::opt<bool> EnablePrecomputePhysRegs(
72
  "precompute-phys-liveness", cl::Hidden,
73
  cl::desc("Eagerly compute live intervals for all physreg units."));
74
#else
75
static bool EnablePrecomputePhysRegs = false;
76
#endif // NDEBUG
77
78
namespace llvm {
79
80
cl::opt<bool> UseSegmentSetForPhysRegs(
81
    "use-segment-set-for-physregs", cl::Hidden, cl::init(true),
82
    cl::desc(
83
        "Use segment set for the computation of the live ranges of physregs."));
84
85
} // end namespace llvm
86
87
42.9k
void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const {
88
42.9k
  AU.setPreservesCFG();
89
42.9k
  AU.addRequired<AAResultsWrapperPass>();
90
42.9k
  AU.addPreserved<AAResultsWrapperPass>();
91
42.9k
  AU.addPreserved<LiveVariables>();
92
42.9k
  AU.addPreservedID(MachineLoopInfoID);
93
42.9k
  AU.addRequiredTransitiveID(MachineDominatorsID);
94
42.9k
  AU.addPreservedID(MachineDominatorsID);
95
42.9k
  AU.addPreserved<SlotIndexes>();
96
42.9k
  AU.addRequiredTransitive<SlotIndexes>();
97
42.9k
  MachineFunctionPass::getAnalysisUsage(AU);
98
42.9k
}
99
100
42.9k
LiveIntervals::LiveIntervals() : MachineFunctionPass(ID) {
101
42.9k
  initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
102
42.9k
}
103
104
42.7k
LiveIntervals::~LiveIntervals() {
105
42.7k
  delete LRCalc;
106
42.7k
}
107
108
564k
void LiveIntervals::releaseMemory() {
109
564k
  // Free the live intervals themselves.
110
21.2M
  for (unsigned i = 0, e = VirtRegIntervals.size(); i != e; 
++i20.6M
)
111
20.6M
    delete VirtRegIntervals[TargetRegisterInfo::index2VirtReg(i)];
112
564k
  VirtRegIntervals.clear();
113
564k
  RegMaskSlots.clear();
114
564k
  RegMaskBits.clear();
115
564k
  RegMaskBlocks.clear();
116
564k
117
564k
  for (LiveRange *LR : RegUnitRanges)
118
120M
    delete LR;
119
564k
  RegUnitRanges.clear();
120
564k
121
564k
  // Release VNInfo memory regions, VNInfo objects don't need to be dtor'd.
122
564k
  VNInfoAllocator.Reset();
123
564k
}
124
125
564k
bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
126
564k
  MF = &fn;
127
564k
  MRI = &MF->getRegInfo();
128
564k
  TRI = MF->getSubtarget().getRegisterInfo();
129
564k
  TII = MF->getSubtarget().getInstrInfo();
130
564k
  AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
131
564k
  Indexes = &getAnalysis<SlotIndexes>();
132
564k
  DomTree = &getAnalysis<MachineDominatorTree>();
133
564k
134
564k
  if (!LRCalc)
135
40.6k
    LRCalc = new LiveRangeCalc();
136
564k
137
564k
  // Allocate space for all virtual registers.
138
564k
  VirtRegIntervals.resize(MRI->getNumVirtRegs());
139
564k
140
564k
  computeVirtRegs();
141
564k
  computeRegMasks();
142
564k
  computeLiveInRegUnits();
143
564k
144
564k
  if (EnablePrecomputePhysRegs) {
145
0
    // For stress testing, precompute live ranges of all physical register
146
0
    // units, including reserved registers.
147
0
    for (unsigned i = 0, e = TRI->getNumRegUnits(); i != e; ++i)
148
0
      getRegUnit(i);
149
0
  }
150
564k
  LLVM_DEBUG(dump());
151
564k
  return true;
152
564k
}
153
154
2
void LiveIntervals::print(raw_ostream &OS, const Module* ) const {
155
2
  OS << "********** INTERVALS **********\n";
156
2
157
2
  // Dump the regunits.
158
256
  for (unsigned Unit = 0, UnitE = RegUnitRanges.size(); Unit != UnitE; 
++Unit254
)
159
254
    if (LiveRange *LR = RegUnitRanges[Unit])
160
0
      OS << printRegUnit(Unit, TRI) << ' ' << *LR << '\n';
161
2
162
2
  // Dump the virtregs.
163
8
  for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; 
++i6
) {
164
6
    unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
165
6
    if (hasInterval(Reg))
166
6
      OS << getInterval(Reg) << '\n';
167
6
  }
168
2
169
2
  OS << "RegMasks:";
170
2
  for (SlotIndex Idx : RegMaskSlots)
171
0
    OS << ' ' << Idx;
172
2
  OS << '\n';
173
2
174
2
  printInstrs(OS);
175
2
}
176
177
2
void LiveIntervals::printInstrs(raw_ostream &OS) const {
178
2
  OS << "********** MACHINEINSTRS **********\n";
179
2
  MF->print(OS, Indexes);
180
2
}
181
182
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
183
LLVM_DUMP_METHOD void LiveIntervals::dumpInstrs() const {
184
  printInstrs(dbgs());
185
}
186
#endif
187
188
13.4M
LiveInterval* LiveIntervals::createInterval(unsigned reg) {
189
13.4M
  float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? 
huge_valf0
: 0.0F;
190
13.4M
  return new LiveInterval(reg, Weight);
191
13.4M
}
192
193
/// Compute the live interval of a virtual register, based on defs and uses.
194
12.8M
void LiveIntervals::computeVirtRegInterval(LiveInterval &LI) {
195
12.8M
  assert(LRCalc && "LRCalc not initialized.");
196
12.8M
  assert(LI.empty() && "Should only compute empty intervals.");
197
12.8M
  LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
198
12.8M
  LRCalc->calculate(LI, MRI->shouldTrackSubRegLiveness(LI.reg));
199
12.8M
  computeDeadValues(LI, nullptr);
200
12.8M
}
201
202
564k
void LiveIntervals::computeVirtRegs() {
203
20.2M
  for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; 
++i19.6M
) {
204
19.6M
    unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
205
19.6M
    if (MRI->reg_nodbg_empty(Reg))
206
7.20M
      continue;
207
12.4M
    createAndComputeVirtRegInterval(Reg);
208
12.4M
  }
209
564k
}
210
211
564k
void LiveIntervals::computeRegMasks() {
212
564k
  RegMaskBlocks.resize(MF->getNumBlockIDs());
213
564k
214
564k
  // Find all instructions with regmask operands.
215
2.92M
  for (const MachineBasicBlock &MBB : *MF) {
216
2.92M
    std::pair<unsigned, unsigned> &RMB = RegMaskBlocks[MBB.getNumber()];
217
2.92M
    RMB.first = RegMaskSlots.size();
218
2.92M
219
2.92M
    // Some block starts, such as EH funclets, create masks.
220
2.92M
    if (const uint32_t *Mask = MBB.getBeginClobberMask(TRI)) {
221
131
      RegMaskSlots.push_back(Indexes->getMBBStartIdx(&MBB));
222
131
      RegMaskBits.push_back(Mask);
223
131
    }
224
2.92M
225
27.3M
    for (const MachineInstr &MI : MBB) {
226
86.1M
      for (const MachineOperand &MO : MI.operands()) {
227
86.1M
        if (!MO.isRegMask())
228
84.6M
          continue;
229
1.51M
        RegMaskSlots.push_back(Indexes->getInstructionIndex(MI).getRegSlot());
230
1.51M
        RegMaskBits.push_back(MO.getRegMask());
231
1.51M
      }
232
27.3M
    }
233
2.92M
234
2.92M
    // Some block ends, such as funclet returns, create masks. Put the mask on
235
2.92M
    // the last instruction of the block, because MBB slot index intervals are
236
2.92M
    // half-open.
237
2.92M
    if (const uint32_t *Mask = MBB.getEndClobberMask(TRI)) {
238
82
      assert(!MBB.empty() && "empty return block?");
239
82
      RegMaskSlots.push_back(
240
82
          Indexes->getInstructionIndex(MBB.back()).getRegSlot());
241
82
      RegMaskBits.push_back(Mask);
242
82
    }
243
2.92M
244
2.92M
    // Compute the number of register mask instructions in this block.
245
2.92M
    RMB.second = RegMaskSlots.size() - RMB.first;
246
2.92M
  }
247
564k
}
248
249
//===----------------------------------------------------------------------===//
250
//                           Register Unit Liveness
251
//===----------------------------------------------------------------------===//
252
//
253
// Fixed interference typically comes from ABI boundaries: Function arguments
254
// and return values are passed in fixed registers, and so are exception
255
// pointers entering landing pads. Certain instructions require values to be
256
// present in specific registers. That is also represented through fixed
257
// interference.
258
//
259
260
/// Compute the live range of a register unit, based on the uses and defs of
261
/// aliasing registers.  The range should be empty, or contain only dead
262
/// phi-defs from ABI blocks.
263
4.28M
void LiveIntervals::computeRegUnitRange(LiveRange &LR, unsigned Unit) {
264
4.28M
  assert(LRCalc && "LRCalc not initialized.");
265
4.28M
  LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
266
4.28M
267
4.28M
  // The physregs aliasing Unit are the roots and their super-registers.
268
4.28M
  // Create all values as dead defs before extending to uses. Note that roots
269
4.28M
  // may share super-registers. That's OK because createDeadDefs() is
270
4.28M
  // idempotent. It is very rare for a register unit to have multiple roots, so
271
4.28M
  // uniquing super-registers is probably not worthwhile.
272
4.28M
  bool IsReserved = false;
273
8.57M
  for (MCRegUnitRootIterator Root(Unit, TRI); Root.isValid(); 
++Root4.28M
) {
274
4.28M
    bool IsRootReserved = true;
275
4.28M
    for (MCSuperRegIterator Super(*Root, TRI, /*IncludeSelf=*/true);
276
32.5M
         Super.isValid(); 
++Super28.2M
) {
277
28.2M
      unsigned Reg = *Super;
278
28.2M
      if (!MRI->reg_empty(Reg))
279
2.10M
        LRCalc->createDeadDefs(LR, Reg);
280
28.2M
      // A register unit is considered reserved if all its roots and all their
281
28.2M
      // super registers are reserved.
282
28.2M
      if (!MRI->isReserved(Reg))
283
27.5M
        IsRootReserved = false;
284
28.2M
    }
285
4.28M
    IsReserved |= IsRootReserved;
286
4.28M
  }
287
4.28M
  assert(IsReserved == MRI->isReservedRegUnit(Unit) &&
288
4.28M
         "reserved computation mismatch");
289
4.28M
290
4.28M
  // Now extend LR to reach all uses.
291
4.28M
  // Ignore uses of reserved registers. We only track defs of those.
292
4.28M
  if (!IsReserved) {
293
8.52M
    for (MCRegUnitRootIterator Root(Unit, TRI); Root.isValid(); 
++Root4.26M
) {
294
4.26M
      for (MCSuperRegIterator Super(*Root, TRI, /*IncludeSelf=*/true);
295
32.4M
           Super.isValid(); 
++Super28.2M
) {
296
28.2M
        unsigned Reg = *Super;
297
28.2M
        if (!MRI->reg_empty(Reg))
298
2.08M
          LRCalc->extendToUses(LR, Reg);
299
28.2M
      }
300
4.26M
    }
301
4.26M
  }
302
4.28M
303
4.28M
  // Flush the segment set to the segment vector.
304
4.28M
  if (UseSegmentSetForPhysRegs)
305
4.28M
    LR.flushSegmentSet();
306
4.28M
}
307
308
/// Precompute the live ranges of any register units that are live-in to an ABI
309
/// block somewhere. Register values can appear without a corresponding def when
310
/// entering the entry block or a landing pad.
311
564k
void LiveIntervals::computeLiveInRegUnits() {
312
564k
  RegUnitRanges.resize(TRI->getNumRegUnits());
313
564k
  LLVM_DEBUG(dbgs() << "Computing live-in reg-units in ABI blocks.\n");
314
564k
315
564k
  // Keep track of the live range sets allocated.
316
564k
  SmallVector<unsigned, 8> NewRanges;
317
564k
318
564k
  // Check all basic blocks for live-ins.
319
2.92M
  for (const MachineBasicBlock &MBB : *MF) {
320
2.92M
    // We only care about ABI blocks: Entry + landing pads.
321
2.92M
    if ((&MBB != &MF->front() && 
!MBB.isEHPad()2.35M
) ||
MBB.livein_empty()580k
)
322
2.42M
      continue;
323
499k
324
499k
    // Create phi-defs at Begin for all live-in registers.
325
499k
    SlotIndex Begin = Indexes->getMBBStartIdx(&MBB);
326
499k
    LLVM_DEBUG(dbgs() << Begin << "\t" << printMBBReference(MBB));
327
1.14M
    for (const auto &LI : MBB.liveins()) {
328
2.53M
      for (MCRegUnitIterator Units(LI.PhysReg, TRI); Units.isValid(); 
++Units1.38M
) {
329
1.38M
        unsigned Unit = *Units;
330
1.38M
        LiveRange *LR = RegUnitRanges[Unit];
331
1.38M
        if (!LR) {
332
1.35M
          // Use segment set to speed-up initial computation of the live range.
333
1.35M
          LR = RegUnitRanges[Unit] = new LiveRange(UseSegmentSetForPhysRegs);
334
1.35M
          NewRanges.push_back(Unit);
335
1.35M
        }
336
1.38M
        VNInfo *VNI = LR->createDeadDef(Begin, getVNInfoAllocator());
337
1.38M
        (void)VNI;
338
1.38M
        LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI) << '#' << VNI->id);
339
1.38M
      }
340
1.14M
    }
341
499k
    LLVM_DEBUG(dbgs() << '\n');
342
499k
  }
343
564k
  LLVM_DEBUG(dbgs() << "Created " << NewRanges.size() << " new intervals.\n");
344
564k
345
564k
  // Compute the 'normal' part of the ranges.
346
564k
  for (unsigned Unit : NewRanges)
347
1.35M
    computeRegUnitRange(*RegUnitRanges[Unit], Unit);
348
564k
}
349
350
static void createSegmentsForValues(LiveRange &LR,
351
768k
    iterator_range<LiveInterval::vni_iterator> VNIs) {
352
1.08M
  for (VNInfo *VNI : VNIs) {
353
1.08M
    if (VNI->isUnused())
354
10.6k
      continue;
355
1.07M
    SlotIndex Def = VNI->def;
356
1.07M
    LR.addSegment(LiveRange::Segment(Def, Def.getDeadSlot(), VNI));
357
1.07M
  }
358
768k
}
359
360
void LiveIntervals::extendSegmentsToUses(LiveRange &Segments,
361
                                         ShrinkToUsesWorkList &WorkList,
362
768k
                                         unsigned Reg, LaneBitmask LaneMask) {
363
768k
  // Keep track of the PHIs that are in use.
364
768k
  SmallPtrSet<VNInfo*, 8> UsedPHIs;
365
768k
  // Blocks that have already been added to WorkList as live-out.
366
768k
  SmallPtrSet<const MachineBasicBlock*, 16> LiveOut;
367
768k
368
768k
  auto getSubRange = [](const LiveInterval &I, LaneBitmask M)
369
768k
        -> const LiveRange& {
370
768k
    if (M.none())
371
767k
      return I;
372
2.34k
    
for (const LiveInterval::SubRange &SR : I.subranges())1.08k
{
373
2.34k
      if ((SR.LaneMask & M).any()) {
374
1.08k
        assert(SR.LaneMask == M && "Expecting lane masks to match exactly");
375
1.08k
        return SR;
376
1.08k
      }
377
2.34k
    }
378
1.08k
    
llvm_unreachable0
("Subrange for mask not found");
379
1.08k
  };
380
768k
381
768k
  const LiveInterval &LI = getInterval(Reg);
382
768k
  const LiveRange &OldRange = getSubRange(LI, LaneMask);
383
768k
384
768k
  // Extend intervals to reach all uses in WorkList.
385
15.9M
  while (!WorkList.empty()) {
386
15.1M
    SlotIndex Idx = WorkList.back().first;
387
15.1M
    VNInfo *VNI = WorkList.back().second;
388
15.1M
    WorkList.pop_back();
389
15.1M
    const MachineBasicBlock *MBB = Indexes->getMBBFromIndex(Idx.getPrevSlot());
390
15.1M
    SlotIndex BlockStart = Indexes->getMBBStartIdx(MBB);
391
15.1M
392
15.1M
    // Extend the live range for VNI to be live at Idx.
393
15.1M
    if (VNInfo *ExtVNI = Segments.extendInBlock(BlockStart, Idx)) {
394
2.18M
      assert(ExtVNI == VNI && "Unexpected existing value number");
395
2.18M
      (void)ExtVNI;
396
2.18M
      // Is this a PHIDef we haven't seen before?
397
2.18M
      if (!VNI->isPHIDef() || 
VNI->def != BlockStart152k
||
398
2.18M
          
!UsedPHIs.insert(VNI).second122k
)
399
2.07M
        continue;
400
103k
      // The PHI is live, make sure the predecessors are live-out.
401
378k
      
for (const MachineBasicBlock *Pred : MBB->predecessors())103k
{
402
378k
        if (!LiveOut.insert(Pred).second)
403
28.3k
          continue;
404
349k
        SlotIndex Stop = Indexes->getMBBEndIdx(Pred);
405
349k
        // A predecessor is not required to have a live-out value for a PHI.
406
349k
        if (VNInfo *PVNI = OldRange.getVNInfoBefore(Stop))
407
349k
          WorkList.push_back(std::make_pair(Stop, PVNI));
408
349k
      }
409
103k
      continue;
410
103k
    }
411
12.9M
412
12.9M
    // VNI is live-in to MBB.
413
12.9M
    LLVM_DEBUG(dbgs() << " live-in at " << BlockStart << '\n');
414
12.9M
    Segments.addSegment(LiveRange::Segment(BlockStart, Idx, VNI));
415
12.9M
416
12.9M
    // Make sure VNI is live-out from the predecessors.
417
18.6M
    for (const MachineBasicBlock *Pred : MBB->predecessors()) {
418
18.6M
      if (!LiveOut.insert(Pred).second)
419
6.12M
        continue;
420
12.5M
      SlotIndex Stop = Indexes->getMBBEndIdx(Pred);
421
12.5M
      if (VNInfo *OldVNI = OldRange.getVNInfoBefore(Stop)) {
422
12.5M
        assert(OldVNI == VNI && "Wrong value out of predecessor");
423
12.5M
        (void)OldVNI;
424
12.5M
        WorkList.push_back(std::make_pair(Stop, VNI));
425
12.5M
      } else {
426
#ifndef NDEBUG
427
        // There was no old VNI. Verify that Stop is jointly dominated
428
        // by <undef>s for this live range.
429
        assert(LaneMask.any() &&
430
               "Missing value out of predecessor for main range");
431
        SmallVector<SlotIndex,8> Undefs;
432
        LI.computeSubRangeUndefs(Undefs, LaneMask, *MRI, *Indexes);
433
        assert(LiveRangeCalc::isJointlyDominated(Pred, Undefs, *Indexes) &&
434
               "Missing value out of predecessor for subrange");
435
#endif
436
      }
437
12.5M
    }
438
12.9M
  }
439
768k
}
440
441
bool LiveIntervals::shrinkToUses(LiveInterval *li,
442
767k
                                 SmallVectorImpl<MachineInstr*> *dead) {
443
767k
  LLVM_DEBUG(dbgs() << "Shrink: " << *li << '\n');
444
767k
  assert(TargetRegisterInfo::isVirtualRegister(li->reg)
445
767k
         && "Can only shrink virtual registers");
446
767k
447
767k
  // Shrink subregister live ranges.
448
767k
  bool NeedsCleanup = false;
449
767k
  for (LiveInterval::SubRange &S : li->subranges()) {
450
973
    shrinkToUses(S, li->reg);
451
973
    if (S.empty())
452
1
      NeedsCleanup = true;
453
973
  }
454
767k
  if (NeedsCleanup)
455
1
    li->removeEmptySubRanges();
456
767k
457
767k
  // Find all the values used, including PHI kills.
458
767k
  ShrinkToUsesWorkList WorkList;
459
767k
460
767k
  // Visit all instructions reading li->reg.
461
767k
  unsigned Reg = li->reg;
462
3.18M
  for (MachineInstr &UseMI : MRI->reg_instructions(Reg)) {
463
3.18M
    if (UseMI.isDebugValue() || 
!UseMI.readsVirtualRegister(Reg)3.18M
)
464
920k
      continue;
465
2.26M
    SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot();
466
2.26M
    LiveQueryResult LRQ = li->Query(Idx);
467
2.26M
    VNInfo *VNI = LRQ.valueIn();
468
2.26M
    if (!VNI) {
469
2
      // This shouldn't happen: readsVirtualRegister returns true, but there is
470
2
      // no live value. It is likely caused by a target getting <undef> flags
471
2
      // wrong.
472
2
      LLVM_DEBUG(
473
2
          dbgs() << Idx << '\t' << UseMI
474
2
                 << "Warning: Instr claims to read non-existent value in "
475
2
                 << *li << '\n');
476
2
      continue;
477
2
    }
478
2.26M
    // Special case: An early-clobber tied operand reads and writes the
479
2.26M
    // register one slot early.
480
2.26M
    if (VNInfo *DefVNI = LRQ.valueDefined())
481
64.9k
      Idx = DefVNI->def;
482
2.26M
483
2.26M
    WorkList.push_back(std::make_pair(Idx, VNI));
484
2.26M
  }
485
767k
486
767k
  // Create new live ranges with only minimal live segments per def.
487
767k
  LiveRange NewLR;
488
767k
  createSegmentsForValues(NewLR, make_range(li->vni_begin(), li->vni_end()));
489
767k
  extendSegmentsToUses(NewLR, WorkList, Reg, LaneBitmask::getNone());
490
767k
491
767k
  // Move the trimmed segments back.
492
767k
  li->segments.swap(NewLR.segments);
493
767k
494
767k
  // Handle dead values.
495
767k
  bool CanSeparate = computeDeadValues(*li, dead);
496
767k
  LLVM_DEBUG(dbgs() << "Shrunk: " << *li << '\n');
497
767k
  return CanSeparate;
498
767k
}
499
500
bool LiveIntervals::computeDeadValues(LiveInterval &LI,
501
13.6M
                                      SmallVectorImpl<MachineInstr*> *dead) {
502
13.6M
  bool MayHaveSplitComponents = false;
503
16.0M
  for (VNInfo *VNI : LI.valnos) {
504
16.0M
    if (VNI->isUnused())
505
10.4k
      continue;
506
16.0M
    SlotIndex Def = VNI->def;
507
16.0M
    LiveRange::iterator I = LI.FindSegmentContaining(Def);
508
16.0M
    assert(I != LI.end() && "Missing segment for VNI");
509
16.0M
510
16.0M
    // Is the register live before? Otherwise we may have to add a read-undef
511
16.0M
    // flag for subregister defs.
512
16.0M
    unsigned VReg = LI.reg;
513
16.0M
    if (MRI->shouldTrackSubRegLiveness(VReg)) {
514
661k
      if ((I == LI.begin() || 
std::prev(I)->end < Def206k
) &&
!VNI->isPHIDef()457k
) {
515
457k
        MachineInstr *MI = getInstructionFromIndex(Def);
516
457k
        MI->setRegisterDefReadUndef(VReg);
517
457k
      }
518
661k
    }
519
16.0M
520
16.0M
    if (I->end != Def.getDeadSlot())
521
15.6M
      continue;
522
446k
    if (VNI->isPHIDef()) {
523
13.5k
      // This is a dead PHI. Remove it.
524
13.5k
      VNI->markUnused();
525
13.5k
      LI.removeSegment(I);
526
13.5k
      LLVM_DEBUG(dbgs() << "Dead PHI at " << Def << " may separate interval\n");
527
13.5k
      MayHaveSplitComponents = true;
528
432k
    } else {
529
432k
      // This is a dead def. Make sure the instruction knows.
530
432k
      MachineInstr *MI = getInstructionFromIndex(Def);
531
432k
      assert(MI && "No instruction defining live value");
532
432k
      MI->addRegisterDead(LI.reg, TRI);
533
432k
      if (dead && 
MI->allDefsAreDead()363k
) {
534
363k
        LLVM_DEBUG(dbgs() << "All defs dead: " << Def << '\t' << *MI);
535
363k
        dead->push_back(MI);
536
363k
      }
537
432k
    }
538
446k
  }
539
13.6M
  return MayHaveSplitComponents;
540
13.6M
}
541
542
1.08k
void LiveIntervals::shrinkToUses(LiveInterval::SubRange &SR, unsigned Reg) {
543
1.08k
  LLVM_DEBUG(dbgs() << "Shrink: " << SR << '\n');
544
1.08k
  assert(TargetRegisterInfo::isVirtualRegister(Reg)
545
1.08k
         && "Can only shrink virtual registers");
546
1.08k
  // Find all the values used, including PHI kills.
547
1.08k
  ShrinkToUsesWorkList WorkList;
548
1.08k
549
1.08k
  // Visit all instructions reading Reg.
550
1.08k
  SlotIndex LastIdx;
551
2.11k
  for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
552
2.11k
    // Skip "undef" uses.
553
2.11k
    if (!MO.readsReg())
554
6
      continue;
555
2.11k
    // Maybe the operand is for a subregister we don't care about.
556
2.11k
    unsigned SubReg = MO.getSubReg();
557
2.11k
    if (SubReg != 0) {
558
1.83k
      LaneBitmask LaneMask = TRI->getSubRegIndexLaneMask(SubReg);
559
1.83k
      if ((LaneMask & SR.LaneMask).none())
560
706
        continue;
561
1.40k
    }
562
1.40k
    // We only need to visit each instruction once.
563
1.40k
    MachineInstr *UseMI = MO.getParent();
564
1.40k
    SlotIndex Idx = getInstructionIndex(*UseMI).getRegSlot();
565
1.40k
    if (Idx == LastIdx)
566
38
      continue;
567
1.36k
    LastIdx = Idx;
568
1.36k
569
1.36k
    LiveQueryResult LRQ = SR.Query(Idx);
570
1.36k
    VNInfo *VNI = LRQ.valueIn();
571
1.36k
    // For Subranges it is possible that only undef values are left in that
572
1.36k
    // part of the subregister, so there is no real liverange at the use
573
1.36k
    if (!VNI)
574
8
      continue;
575
1.35k
576
1.35k
    // Special case: An early-clobber tied operand reads and writes the
577
1.35k
    // register one slot early.
578
1.35k
    if (VNInfo *DefVNI = LRQ.valueDefined())
579
53
      Idx = DefVNI->def;
580
1.35k
581
1.35k
    WorkList.push_back(std::make_pair(Idx, VNI));
582
1.35k
  }
583
1.08k
584
1.08k
  // Create a new live ranges with only minimal live segments per def.
585
1.08k
  LiveRange NewLR;
586
1.08k
  createSegmentsForValues(NewLR, make_range(SR.vni_begin(), SR.vni_end()));
587
1.08k
  extendSegmentsToUses(NewLR, WorkList, Reg, SR.LaneMask);
588
1.08k
589
1.08k
  // Move the trimmed ranges back.
590
1.08k
  SR.segments.swap(NewLR.segments);
591
1.08k
592
1.08k
  // Remove dead PHI value numbers
593
1.74k
  for (VNInfo *VNI : SR.valnos) {
594
1.74k
    if (VNI->isUnused())
595
148
      continue;
596
1.60k
    const LiveRange::Segment *Segment = SR.getSegmentContaining(VNI->def);
597
1.60k
    assert(Segment != nullptr && "Missing segment for VNI");
598
1.60k
    if (Segment->end != VNI->def.getDeadSlot())
599
1.37k
      continue;
600
228
    if (VNI->isPHIDef()) {
601
59
      // This is a dead PHI. Remove it.
602
59
      LLVM_DEBUG(dbgs() << "Dead PHI at " << VNI->def
603
59
                        << " may separate interval\n");
604
59
      VNI->markUnused();
605
59
      SR.removeSegment(*Segment);
606
59
    }
607
228
  }
608
1.08k
609
1.08k
  LLVM_DEBUG(dbgs() << "Shrunk: " << SR << '\n');
610
1.08k
}
611
612
void LiveIntervals::extendToIndices(LiveRange &LR,
613
                                    ArrayRef<SlotIndex> Indices,
614
85.3k
                                    ArrayRef<SlotIndex> Undefs) {
615
85.3k
  assert(LRCalc && "LRCalc not initialized.");
616
85.3k
  LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
617
85.3k
  for (SlotIndex Idx : Indices)
618
296k
    LRCalc->extend(LR, Idx, /*PhysReg=*/0, Undefs);
619
85.3k
}
620
621
void LiveIntervals::pruneValue(LiveRange &LR, SlotIndex Kill,
622
202k
                               SmallVectorImpl<SlotIndex> *EndPoints) {
623
202k
  LiveQueryResult LRQ = LR.Query(Kill);
624
202k
  VNInfo *VNI = LRQ.valueOutOrDead();
625
202k
  if (!VNI)
626
58.0k
    return;
627
144k
628
144k
  MachineBasicBlock *KillMBB = Indexes->getMBBFromIndex(Kill);
629
144k
  SlotIndex MBBEnd = Indexes->getMBBEndIdx(KillMBB);
630
144k
631
144k
  // If VNI isn't live out from KillMBB, the value is trivially pruned.
632
144k
  if (LRQ.endPoint() < MBBEnd) {
633
142k
    LR.removeSegment(Kill, LRQ.endPoint());
634
142k
    if (EndPoints) EndPoints->push_back(LRQ.endPoint());
635
142k
    return;
636
142k
  }
637
2.17k
638
2.17k
  // VNI is live out of KillMBB.
639
2.17k
  LR.removeSegment(Kill, MBBEnd);
640
2.17k
  if (EndPoints) EndPoints->push_back(MBBEnd);
641
2.17k
642
2.17k
  // Find all blocks that are reachable from KillMBB without leaving VNI's live
643
2.17k
  // range. It is possible that KillMBB itself is reachable, so start a DFS
644
2.17k
  // from each successor.
645
2.17k
  using VisitedTy = df_iterator_default_set<MachineBasicBlock*,9>;
646
2.17k
  VisitedTy Visited;
647
3.25k
  for (MachineBasicBlock *Succ : KillMBB->successors()) {
648
3.25k
    for (df_ext_iterator<MachineBasicBlock*, VisitedTy>
649
3.25k
         I = df_ext_begin(Succ, Visited), E = df_ext_end(Succ, Visited);
650
8.97k
         I != E;) {
651
5.72k
      MachineBasicBlock *MBB = *I;
652
5.72k
653
5.72k
      // Check if VNI is live in to MBB.
654
5.72k
      SlotIndex MBBStart, MBBEnd;
655
5.72k
      std::tie(MBBStart, MBBEnd) = Indexes->getMBBRange(MBB);
656
5.72k
      LiveQueryResult LRQ = LR.Query(MBBStart);
657
5.72k
      if (LRQ.valueIn() != VNI) {
658
2.57k
        // This block isn't part of the VNI segment. Prune the search.
659
2.57k
        I.skipChildren();
660
2.57k
        continue;
661
2.57k
      }
662
3.15k
663
3.15k
      // Prune the search if VNI is killed in MBB.
664
3.15k
      if (LRQ.endPoint() < MBBEnd) {
665
732
        LR.removeSegment(MBBStart, LRQ.endPoint());
666
732
        if (EndPoints) EndPoints->push_back(LRQ.endPoint());
667
732
        I.skipChildren();
668
732
        continue;
669
732
      }
670
2.41k
671
2.41k
      // VNI is live through MBB.
672
2.41k
      LR.removeSegment(MBBStart, MBBEnd);
673
2.41k
      if (EndPoints) EndPoints->push_back(MBBEnd);
674
2.41k
      ++I;
675
2.41k
    }
676
3.25k
  }
677
2.17k
}
678
679
//===----------------------------------------------------------------------===//
680
// Register allocator hooks.
681
//
682
683
484k
void LiveIntervals::addKillFlags(const VirtRegMap *VRM) {
684
484k
  // Keep track of regunit ranges.
685
484k
  SmallVector<std::pair<const LiveRange*, LiveRange::const_iterator>, 8> RU;
686
484k
  // Keep track of subregister ranges.
687
484k
  SmallVector<std::pair<const LiveInterval::SubRange*,
688
484k
                        LiveRange::const_iterator>, 4> SRs;
689
484k
690
19.1M
  for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; 
++i18.6M
) {
691
18.6M
    unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
692
18.6M
    if (MRI->reg_nodbg_empty(Reg))
693
10.8M
      continue;
694
7.82M
    const LiveInterval &LI = getInterval(Reg);
695
7.82M
    if (LI.empty())
696
10.3k
      continue;
697
7.81M
698
7.81M
    // Find the regunit intervals for the assigned register. They may overlap
699
7.81M
    // the virtual register live range, cancelling any kills.
700
7.81M
    RU.clear();
701
16.9M
    for (MCRegUnitIterator Unit(VRM->getPhys(Reg), TRI); Unit.isValid();
702
9.14M
         ++Unit) {
703
9.14M
      const LiveRange &RURange = getRegUnit(*Unit);
704
9.14M
      if (RURange.empty())
705
5.78M
        continue;
706
3.36M
      RU.push_back(std::make_pair(&RURange, RURange.find(LI.begin()->end)));
707
3.36M
    }
708
7.81M
709
7.81M
    if (MRI->subRegLivenessEnabled()) {
710
308k
      SRs.clear();
711
308k
      for (const LiveInterval::SubRange &SR : LI.subranges()) {
712
214k
        SRs.push_back(std::make_pair(&SR, SR.find(LI.begin()->end)));
713
214k
      }
714
308k
    }
715
7.81M
716
7.81M
    // Every instruction that kills Reg corresponds to a segment range end
717
7.81M
    // point.
718
19.7M
    for (LiveInterval::const_iterator RI = LI.begin(), RE = LI.end(); RI != RE;
719
11.9M
         ++RI) {
720
11.9M
      // A block index indicates an MBB edge.
721
11.9M
      if (RI->end.isBlock())
722
3.56M
        continue;
723
8.34M
      MachineInstr *MI = getInstructionFromIndex(RI->end);
724
8.34M
      if (!MI)
725
0
        continue;
726
8.34M
727
8.34M
      // Check if any of the regunits are live beyond the end of RI. That could
728
8.34M
      // happen when a physreg is defined as a copy of a virtreg:
729
8.34M
      //
730
8.34M
      //   %eax = COPY %5
731
8.34M
      //   FOO %5             <--- MI, cancel kill because %eax is live.
732
8.34M
      //   BAR killed %eax
733
8.34M
      //
734
8.34M
      // There should be no kill flag on FOO when %5 is rewritten as %eax.
735
8.34M
      for (auto &RUP : RU) {
736
3.85M
        const LiveRange &RURange = *RUP.first;
737
3.85M
        LiveRange::const_iterator &I = RUP.second;
738
3.85M
        if (I == RURange.end())
739
851k
          continue;
740
3.00M
        I = RURange.advanceTo(I, RI->end);
741
3.00M
        if (I == RURange.end() || 
I->start >= RI->end2.97M
)
742
2.99M
          continue;
743
15.5k
        // I is overlapping RI.
744
15.5k
        goto CancelKill;
745
15.5k
      }
746
8.34M
747
8.34M
      
if (8.32M
MRI->subRegLivenessEnabled()8.32M
) {
748
393k
        // When reading a partial undefined value we must not add a kill flag.
749
393k
        // The regalloc might have used the undef lane for something else.
750
393k
        // Example:
751
393k
        //     %1 = ...                  ; R32: %1
752
393k
        //     %2:high16 = ...           ; R64: %2
753
393k
        //        = read killed %2        ; R64: %2
754
393k
        //        = read %1              ; R32: %1
755
393k
        // The <kill> flag is correct for %2, but the register allocator may
756
393k
        // assign R0L to %1, and R0 to %2 because the low 32bits of R0
757
393k
        // are actually never written by %2. After assignment the <kill>
758
393k
        // flag at the read instruction is invalid.
759
393k
        LaneBitmask DefinedLanesMask;
760
393k
        if (!SRs.empty()) {
761
154k
          // Compute a mask of lanes that are defined.
762
154k
          DefinedLanesMask = LaneBitmask::getNone();
763
507k
          for (auto &SRP : SRs) {
764
507k
            const LiveInterval::SubRange &SR = *SRP.first;
765
507k
            LiveRange::const_iterator &I = SRP.second;
766
507k
            if (I == SR.end())
767
71.1k
              continue;
768
436k
            I = SR.advanceTo(I, RI->end);
769
436k
            if (I == SR.end() || 
I->start >= RI->end298k
)
770
281k
              continue;
771
154k
            // I is overlapping RI
772
154k
            DefinedLanesMask |= SR.LaneMask;
773
154k
          }
774
154k
        } else
775
239k
          DefinedLanesMask = LaneBitmask::getAll();
776
393k
777
393k
        bool IsFullWrite = false;
778
2.20M
        for (const MachineOperand &MO : MI->operands()) {
779
2.20M
          if (!MO.isReg() || 
MO.getReg() != Reg1.23M
)
780
1.79M
            continue;
781
405k
          if (MO.isUse()) {
782
309k
            // Reading any undefined lanes?
783
309k
            LaneBitmask UseMask = TRI->getSubRegIndexLaneMask(MO.getSubReg());
784
309k
            if ((UseMask & ~DefinedLanesMask).any())
785
72.2k
              goto CancelKill;
786
96.0k
          } else if (MO.getSubReg() == 0) {
787
13.4k
            // Writing to the full register?
788
13.4k
            assert(MO.isDef());
789
13.4k
            IsFullWrite = true;
790
13.4k
          }
791
405k
        }
792
393k
793
393k
        // If an instruction writes to a subregister, a new segment starts in
794
393k
        // the LiveInterval. But as this is only overriding part of the register
795
393k
        // adding kill-flags is not correct here after registers have been
796
393k
        // assigned.
797
393k
        
if (321k
!IsFullWrite321k
) {
798
308k
          // Next segment has to be adjacent in the subregister write case.
799
308k
          LiveRange::const_iterator N = std::next(RI);
800
308k
          if (N != LI.end() && 
N->start == RI->end85.1k
)
801
81.8k
            goto CancelKill;
802
8.17M
        }
803
321k
      }
804
8.17M
805
8.17M
      MI->addRegisterKilled(Reg, nullptr);
806
8.17M
      continue;
807
169k
CancelKill:
808
169k
      MI->clearRegisterKills(Reg, nullptr);
809
169k
    }
810
7.81M
  }
811
484k
}
812
813
MachineBasicBlock*
814
46.7M
LiveIntervals::intervalIsInOneMBB(const LiveInterval &LI) const {
815
46.7M
  // A local live range must be fully contained inside the block, meaning it is
816
46.7M
  // defined and killed at instructions, not at block boundaries. It is not
817
46.7M
  // live in or out of any block.
818
46.7M
  //
819
46.7M
  // It is technically possible to have a PHI-defined live range identical to a
820
46.7M
  // single block, but we are going to return false in that case.
821
46.7M
822
46.7M
  SlotIndex Start = LI.beginIndex();
823
46.7M
  if (Start.isBlock())
824
60.7k
    return nullptr;
825
46.6M
826
46.6M
  SlotIndex Stop = LI.endIndex();
827
46.6M
  if (Stop.isBlock())
828
6.46M
    return nullptr;
829
40.2M
830
40.2M
  // getMBBFromIndex doesn't need to search the MBB table when both indexes
831
40.2M
  // belong to proper instructions.
832
40.2M
  MachineBasicBlock *MBB1 = Indexes->getMBBFromIndex(Start);
833
40.2M
  MachineBasicBlock *MBB2 = Indexes->getMBBFromIndex(Stop);
834
40.2M
  return MBB1 == MBB2 ? 
MBB133.4M
:
nullptr6.78M
;
835
40.2M
}
836
837
bool
838
501
LiveIntervals::hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const {
839
1.73k
  for (const VNInfo *PHI : LI.valnos) {
840
1.73k
    if (PHI->isUnused() || !PHI->isPHIDef())
841
1.59k
      continue;
842
137
    const MachineBasicBlock *PHIMBB = getMBBFromIndex(PHI->def);
843
137
    // Conservatively return true instead of scanning huge predecessor lists.
844
137
    if (PHIMBB->pred_size() > 100)
845
0
      return true;
846
137
    for (const MachineBasicBlock *Pred : PHIMBB->predecessors())
847
383
      if (VNI == LI.getVNInfoBefore(Indexes->getMBBEndIdx(Pred)))
848
5
        return true;
849
137
  }
850
501
  
return false496
;
851
501
}
852
853
float LiveIntervals::getSpillWeight(bool isDef, bool isUse,
854
                                    const MachineBlockFrequencyInfo *MBFI,
855
24.6M
                                    const MachineInstr &MI) {
856
24.6M
  return getSpillWeight(isDef, isUse, MBFI, MI.getParent());
857
24.6M
}
858
859
float LiveIntervals::getSpillWeight(bool isDef, bool isUse,
860
                                    const MachineBlockFrequencyInfo *MBFI,
861
24.6M
                                    const MachineBasicBlock *MBB) {
862
24.6M
  BlockFrequency Freq = MBFI->getBlockFreq(MBB);
863
24.6M
  const float Scale = 1.0f / MBFI->getEntryFreq();
864
24.6M
  return (isDef + isUse) * (Freq.getFrequency() * Scale);
865
24.6M
}
866
867
LiveRange::Segment
868
0
LiveIntervals::addSegmentToEndOfBlock(unsigned reg, MachineInstr &startInst) {
869
0
  LiveInterval& Interval = createEmptyInterval(reg);
870
0
  VNInfo *VN = Interval.getNextValue(
871
0
      SlotIndex(getInstructionIndex(startInst).getRegSlot()),
872
0
      getVNInfoAllocator());
873
0
  LiveRange::Segment S(SlotIndex(getInstructionIndex(startInst).getRegSlot()),
874
0
                       getMBBEndIdx(startInst.getParent()), VN);
875
0
  Interval.addSegment(S);
876
0
877
0
  return S;
878
0
}
879
880
//===----------------------------------------------------------------------===//
881
//                          Register mask functions
882
//===----------------------------------------------------------------------===//
883
884
bool LiveIntervals::checkRegMaskInterference(LiveInterval &LI,
885
9.35M
                                             BitVector &UsableRegs) {
886
9.35M
  if (LI.empty())
887
0
    return false;
888
9.35M
  LiveInterval::iterator LiveI = LI.begin(), LiveE = LI.end();
889
9.35M
890
9.35M
  // Use a smaller arrays for local live ranges.
891
9.35M
  ArrayRef<SlotIndex> Slots;
892
9.35M
  ArrayRef<const uint32_t*> Bits;
893
9.35M
  if (MachineBasicBlock *MBB = intervalIsInOneMBB(LI)) {
894
6.74M
    Slots = getRegMaskSlotsInBlock(MBB->getNumber());
895
6.74M
    Bits = getRegMaskBitsInBlock(MBB->getNumber());
896
6.74M
  } else {
897
2.60M
    Slots = getRegMaskSlots();
898
2.60M
    Bits = getRegMaskBits();
899
2.60M
  }
900
9.35M
901
9.35M
  // We are going to enumerate all the register mask slots contained in LI.
902
9.35M
  // Start with a binary search of RegMaskSlots to find a starting point.
903
9.35M
  ArrayRef<SlotIndex>::iterator SlotI = llvm::lower_bound(Slots, LiveI->start);
904
9.35M
  ArrayRef<SlotIndex>::iterator SlotE = Slots.end();
905
9.35M
906
9.35M
  // No slots in range, LI begins after the last call.
907
9.35M
  if (SlotI == SlotE)
908
4.40M
    return false;
909
4.94M
910
4.94M
  bool Found = false;
911
8.54M
  while (
true8.54M
) {
912
8.54M
    assert(*SlotI >= LiveI->start);
913
8.54M
    // Loop over all slots overlapping this segment.
914
30.9M
    while (*SlotI < LiveI->end) {
915
22.9M
      // *SlotI overlaps LI. Collect mask bits.
916
22.9M
      if (!Found) {
917
2.22M
        // This is the first overlap. Initialize UsableRegs to all ones.
918
2.22M
        UsableRegs.clear();
919
2.22M
        UsableRegs.resize(TRI->getNumRegs(), true);
920
2.22M
        Found = true;
921
2.22M
      }
922
22.9M
      // Remove usable registers clobbered by this mask.
923
22.9M
      UsableRegs.clearBitsNotInMask(Bits[SlotI-Slots.begin()]);
924
22.9M
      if (++SlotI == SlotE)
925
525k
        return Found;
926
22.9M
    }
927
8.54M
    // *SlotI is beyond the current LI segment.
928
8.54M
    LiveI = LI.advanceTo(LiveI, *SlotI);
929
8.02M
    if (LiveI == LiveE)
930
4.25M
      return Found;
931
3.77M
    // Advance SlotI until it overlaps.
932
10.8M
    
while (3.77M
*SlotI < LiveI->start)
933
7.21M
      if (++SlotI == SlotE)
934
163k
        return Found;
935
3.77M
  }
936
4.94M
}
937
938
//===----------------------------------------------------------------------===//
939
//                         IntervalUpdate class.
940
//===----------------------------------------------------------------------===//
941
942
/// Toolkit used by handleMove to trim or extend live intervals.
943
class LiveIntervals::HMEditor {
944
private:
945
  LiveIntervals& LIS;
946
  const MachineRegisterInfo& MRI;
947
  const TargetRegisterInfo& TRI;
948
  SlotIndex OldIdx;
949
  SlotIndex NewIdx;
950
  SmallPtrSet<LiveRange*, 8> Updated;
951
  bool UpdateFlags;
952
953
public:
954
  HMEditor(LiveIntervals& LIS, const MachineRegisterInfo& MRI,
955
           const TargetRegisterInfo& TRI,
956
           SlotIndex OldIdx, SlotIndex NewIdx, bool UpdateFlags)
957
    : LIS(LIS), MRI(MRI), TRI(TRI), OldIdx(OldIdx), NewIdx(NewIdx),
958
838k
      UpdateFlags(UpdateFlags) {}
959
960
  // FIXME: UpdateFlags is a workaround that creates live intervals for all
961
  // physregs, even those that aren't needed for regalloc, in order to update
962
  // kill flags. This is wasteful. Eventually, LiveVariables will strip all kill
963
  // flags, and postRA passes will use a live register utility instead.
964
634k
  LiveRange *getRegUnitLI(unsigned Unit) {
965
634k
    if (UpdateFlags && 
!MRI.isReservedRegUnit(Unit)611k
)
966
325k
      return &LIS.getRegUnit(Unit);
967
309k
    return LIS.getCachedRegUnit(Unit);
968
309k
  }
969
970
  /// Update all live ranges touched by MI, assuming a move from OldIdx to
971
  /// NewIdx.
972
838k
  void updateAllRanges(MachineInstr *MI) {
973
838k
    LLVM_DEBUG(dbgs() << "handleMove " << OldIdx << " -> " << NewIdx << ": "
974
838k
                      << *MI);
975
838k
    bool hasRegMask = false;
976
3.12M
    for (MachineOperand &MO : MI->operands()) {
977
3.12M
      if (MO.isRegMask())
978
0
        hasRegMask = true;
979
3.12M
      if (!MO.isReg())
980
1.08M
        continue;
981
2.03M
      if (MO.isUse()) {
982
1.21M
        if (!MO.readsReg())
983
309
          continue;
984
1.21M
        // Aggressively clear all kill flags.
985
1.21M
        // They are reinserted by VirtRegRewriter.
986
1.21M
        MO.setIsKill(false);
987
1.21M
      }
988
2.03M
989
2.03M
      unsigned Reg = MO.getReg();
990
2.03M
      if (!Reg)
991
18.5k
        continue;
992
2.01M
      if (TargetRegisterInfo::isVirtualRegister(Reg)) {
993
1.50M
        LiveInterval &LI = LIS.getInterval(Reg);
994
1.50M
        if (LI.hasSubRanges()) {
995
103k
          unsigned SubReg = MO.getSubReg();
996
103k
          LaneBitmask LaneMask = SubReg ? 
TRI.getSubRegIndexLaneMask(SubReg)84.5k
997
103k
                                        : 
MRI.getMaxLaneMaskForVReg(Reg)19.0k
;
998
360k
          for (LiveInterval::SubRange &S : LI.subranges()) {
999
360k
            if ((S.LaneMask & LaneMask).none())
1000
218k
              continue;
1001
142k
            updateRange(S, Reg, S.LaneMask);
1002
142k
          }
1003
103k
        }
1004
1.50M
        updateRange(LI, Reg, LaneBitmask::getNone());
1005
1.50M
        continue;
1006
1.50M
      }
1007
514k
1008
514k
      // For physregs, only update the regunits that actually have a
1009
514k
      // precomputed live range.
1010
1.14M
      
for (MCRegUnitIterator Units(Reg, &TRI); 514k
Units.isValid();
++Units634k
)
1011
634k
        if (LiveRange *LR = getRegUnitLI(*Units))
1012
359k
          updateRange(*LR, *Units, LaneBitmask::getNone());
1013
514k
    }
1014
838k
    if (hasRegMask)
1015
0
      updateRegMaskSlots();
1016
838k
  }
1017
1018
private:
1019
  /// Update a single live range, assuming an instruction has been moved from
1020
  /// OldIdx to NewIdx.
1021
2.00M
  void updateRange(LiveRange &LR, unsigned Reg, LaneBitmask LaneMask) {
1022
2.00M
    if (!Updated.insert(&LR).second)
1023
57.4k
      return;
1024
1.94M
    LLVM_DEBUG({
1025
1.94M
      dbgs() << "     ";
1026
1.94M
      if (TargetRegisterInfo::isVirtualRegister(Reg)) {
1027
1.94M
        dbgs() << printReg(Reg);
1028
1.94M
        if (LaneMask.any())
1029
1.94M
          dbgs() << " L" << PrintLaneMask(LaneMask);
1030
1.94M
      } else {
1031
1.94M
        dbgs() << printRegUnit(Reg, &TRI);
1032
1.94M
      }
1033
1.94M
      dbgs() << ":\t" << LR << '\n';
1034
1.94M
    });
1035
1.94M
    if (SlotIndex::isEarlierInstr(OldIdx, NewIdx))
1036
1.76M
      handleMoveDown(LR);
1037
179k
    else
1038
179k
      handleMoveUp(LR, Reg, LaneMask);
1039
1.94M
    LLVM_DEBUG(dbgs() << "        -->\t" << LR << '\n');
1040
1.94M
    LR.verify();
1041
1.94M
  }
1042
1043
  /// Update LR to reflect an instruction has been moved downwards from OldIdx
1044
  /// to NewIdx (OldIdx < NewIdx).
1045
1.76M
  void handleMoveDown(LiveRange &LR) {
1046
1.76M
    LiveRange::iterator E = LR.end();
1047
1.76M
    // Segment going into OldIdx.
1048
1.76M
    LiveRange::iterator OldIdxIn = LR.find(OldIdx.getBaseIndex());
1049
1.76M
1050
1.76M
    // No value live before or after OldIdx? Nothing to do.
1051
1.76M
    if (OldIdxIn == E || 
SlotIndex::isEarlierInstr(OldIdx, OldIdxIn->start)1.76M
)
1052
72.3k
      return;
1053
1.69M
1054
1.69M
    LiveRange::iterator OldIdxOut;
1055
1.69M
    // Do we have a value live-in to OldIdx?
1056
1.69M
    if (SlotIndex::isEarlierInstr(OldIdxIn->start, OldIdx)) {
1057
1.03M
      // If the live-in value already extends to NewIdx, there is nothing to do.
1058
1.03M
      if (SlotIndex::isEarlierEqualInstr(NewIdx, OldIdxIn->end))
1059
454k
        return;
1060
579k
      // Aggressively remove all kill flags from the old kill point.
1061
579k
      // Kill flags shouldn't be used while live intervals exist, they will be
1062
579k
      // reinserted by VirtRegRewriter.
1063
579k
      if (MachineInstr *KillMI = LIS.getInstructionFromIndex(OldIdxIn->end))
1064
236k
        
for (MIBundleOperands MO(*KillMI); 39.0k
MO.isValid();
++MO197k
)
1065
197k
          if (MO->isReg() && 
MO->isUse()105k
)
1066
68.7k
            MO->setIsKill(false);
1067
579k
1068
579k
      // Is there a def before NewIdx which is not OldIdx?
1069
579k
      LiveRange::iterator Next = std::next(OldIdxIn);
1070
579k
      if (Next != E && 
!SlotIndex::isSameInstr(OldIdx, Next->start)111k
&&
1071
579k
          
SlotIndex::isEarlierInstr(Next->start, NewIdx)43.3k
) {
1072
342
        // If we are here then OldIdx was just a use but not a def. We only have
1073
342
        // to ensure liveness extends to NewIdx.
1074
342
        LiveRange::iterator NewIdxIn =
1075
342
          LR.advanceTo(Next, NewIdx.getBaseIndex());
1076
342
        // Extend the segment before NewIdx if necessary.
1077
342
        if (NewIdxIn == E ||
1078
342
            
!SlotIndex::isEarlierInstr(NewIdxIn->start, NewIdx)266
) {
1079
76
          LiveRange::iterator Prev = std::prev(NewIdxIn);
1080
76
          Prev->end = NewIdx.getRegSlot();
1081
76
        }
1082
342
        // Extend OldIdxIn.
1083
342
        OldIdxIn->end = Next->start;
1084
342
        return;
1085
342
      }
1086
578k
1087
578k
      // Adjust OldIdxIn->end to reach NewIdx. This may temporarily make LR
1088
578k
      // invalid by overlapping ranges.
1089
578k
      bool isKill = SlotIndex::isSameInstr(OldIdx, OldIdxIn->end);
1090
578k
      OldIdxIn->end = NewIdx.getRegSlot(OldIdxIn->end.isEarlyClobber());
1091
578k
      // If this was not a kill, then there was no def and we're done.
1092
578k
      if (!isKill)
1093
38.6k
        return;
1094
540k
1095
540k
      // Did we have a Def at OldIdx?
1096
540k
      OldIdxOut = Next;
1097
540k
      if (OldIdxOut == E || 
!SlotIndex::isSameInstr(OldIdx, OldIdxOut->start)104k
)
1098
472k
        return;
1099
660k
    } else {
1100
660k
      OldIdxOut = OldIdxIn;
1101
660k
    }
1102
1.69M
1103
1.69M
    // If we are here then there is a Definition at OldIdx. OldIdxOut points
1104
1.69M
    // to the segment starting there.
1105
1.69M
    assert(OldIdxOut != E && SlotIndex::isSameInstr(OldIdx, OldIdxOut->start) &&
1106
728k
           "No def?");
1107
728k
    VNInfo *OldIdxVNI = OldIdxOut->valno;
1108
728k
    assert(OldIdxVNI->def == OldIdxOut->start && "Inconsistent def");
1109
728k
1110
728k
    // If the defined value extends beyond NewIdx, just move the beginning
1111
728k
    // of the segment to NewIdx.
1112
728k
    SlotIndex NewIdxDef = NewIdx.getRegSlot(OldIdxOut->start.isEarlyClobber());
1113
728k
    if (SlotIndex::isEarlierInstr(NewIdxDef, OldIdxOut->end)) {
1114
698k
      OldIdxVNI->def = NewIdxDef;
1115
698k
      OldIdxOut->start = OldIdxVNI->def;
1116
698k
      return;
1117
698k
    }
1118
30.1k
1119
30.1k
    // If we are here then we have a Definition at OldIdx which ends before
1120
30.1k
    // NewIdx.
1121
30.1k
1122
30.1k
    // Is there an existing Def at NewIdx?
1123
30.1k
    LiveRange::iterator AfterNewIdx
1124
30.1k
      = LR.advanceTo(OldIdxOut, NewIdx.getRegSlot());
1125
30.1k
    bool OldIdxDefIsDead = OldIdxOut->end.isDead();
1126
30.1k
    if (!OldIdxDefIsDead &&
1127
30.1k
        
SlotIndex::isEarlierInstr(OldIdxOut->end, NewIdxDef)5.48k
) {
1128
5.48k
      // OldIdx is not a dead def, and NewIdxDef is inside a new interval.
1129
5.48k
      VNInfo *DefVNI;
1130
5.48k
      if (OldIdxOut != LR.begin() &&
1131
5.48k
          !SlotIndex::isEarlierInstr(std::prev(OldIdxOut)->end,
1132
2.28k
                                     OldIdxOut->start)) {
1133
2.28k
        // There is no gap between OldIdxOut and its predecessor anymore,
1134
2.28k
        // merge them.
1135
2.28k
        LiveRange::iterator IPrev = std::prev(OldIdxOut);
1136
2.28k
        DefVNI = OldIdxVNI;
1137
2.28k
        IPrev->end = OldIdxOut->end;
1138
3.20k
      } else {
1139
3.20k
        // The value is live in to OldIdx
1140
3.20k
        LiveRange::iterator INext = std::next(OldIdxOut);
1141
3.20k
        assert(INext != E && "Must have following segment");
1142
3.20k
        // We merge OldIdxOut and its successor. As we're dealing with subreg
1143
3.20k
        // reordering, there is always a successor to OldIdxOut in the same BB
1144
3.20k
        // We don't need INext->valno anymore and will reuse for the new segment
1145
3.20k
        // we create later.
1146
3.20k
        DefVNI = OldIdxVNI;
1147
3.20k
        INext->start = OldIdxOut->end;
1148
3.20k
        INext->valno->def = INext->start;
1149
3.20k
      }
1150
5.48k
      // If NewIdx is behind the last segment, extend that and append a new one.
1151
5.48k
      if (AfterNewIdx == E) {
1152
0
        // OldIdxOut is undef at this point, Slide (OldIdxOut;AfterNewIdx] up
1153
0
        // one position.
1154
0
        //    |-  ?/OldIdxOut -| |- X0 -| ... |- Xn -| end
1155
0
        // => |- X0/OldIdxOut -| ... |- Xn -| |- undef/NewS -| end
1156
0
        std::copy(std::next(OldIdxOut), E, OldIdxOut);
1157
0
        // The last segment is undefined now, reuse it for a dead def.
1158
0
        LiveRange::iterator NewSegment = std::prev(E);
1159
0
        *NewSegment = LiveRange::Segment(NewIdxDef, NewIdxDef.getDeadSlot(),
1160
0
                                         DefVNI);
1161
0
        DefVNI->def = NewIdxDef;
1162
0
1163
0
        LiveRange::iterator Prev = std::prev(NewSegment);
1164
0
        Prev->end = NewIdxDef;
1165
5.48k
      } else {
1166
5.48k
        // OldIdxOut is undef at this point, Slide (OldIdxOut;AfterNewIdx] up
1167
5.48k
        // one position.
1168
5.48k
        //    |-  ?/OldIdxOut -| |- X0 -| ... |- Xn/AfterNewIdx -| |- Next -|
1169
5.48k
        // => |- X0/OldIdxOut -| ... |- Xn -| |- Xn/AfterNewIdx -| |- Next -|
1170
5.48k
        std::copy(std::next(OldIdxOut), std::next(AfterNewIdx), OldIdxOut);
1171
5.48k
        LiveRange::iterator Prev = std::prev(AfterNewIdx);
1172
5.48k
        // We have two cases:
1173
5.48k
        if (SlotIndex::isEarlierInstr(Prev->start, NewIdxDef)) {
1174
5.48k
          // Case 1: NewIdx is inside a liverange. Split this liverange at
1175
5.48k
          // NewIdxDef into the segment "Prev" followed by "NewSegment".
1176
5.48k
          LiveRange::iterator NewSegment = AfterNewIdx;
1177
5.48k
          *NewSegment = LiveRange::Segment(NewIdxDef, Prev->end, Prev->valno);
1178
5.48k
          Prev->valno->def = NewIdxDef;
1179
5.48k
1180
5.48k
          *Prev = LiveRange::Segment(Prev->start, NewIdxDef, DefVNI);
1181
5.48k
          DefVNI->def = Prev->start;
1182
5.48k
        } else {
1183
0
          // Case 2: NewIdx is in a lifetime hole. Keep AfterNewIdx as is and
1184
0
          // turn Prev into a segment from NewIdx to AfterNewIdx->start.
1185
0
          *Prev = LiveRange::Segment(NewIdxDef, AfterNewIdx->start, DefVNI);
1186
0
          DefVNI->def = NewIdxDef;
1187
0
          assert(DefVNI != AfterNewIdx->valno);
1188
0
        }
1189
5.48k
      }
1190
5.48k
      return;
1191
5.48k
    }
1192
24.6k
1193
24.6k
    if (AfterNewIdx != E &&
1194
24.6k
        
SlotIndex::isSameInstr(AfterNewIdx->start, NewIdxDef)22.6k
) {
1195
0
      // There is an existing def at NewIdx. The def at OldIdx is coalesced into
1196
0
      // that value.
1197
0
      assert(AfterNewIdx->valno != OldIdxVNI && "Multiple defs of value?");
1198
0
      LR.removeValNo(OldIdxVNI);
1199
24.6k
    } else {
1200
24.6k
      // There was no existing def at NewIdx. We need to create a dead def
1201
24.6k
      // at NewIdx. Shift segments over the old OldIdxOut segment, this frees
1202
24.6k
      // a new segment at the place where we want to construct the dead def.
1203
24.6k
      //    |- OldIdxOut -| |- X0 -| ... |- Xn -| |- AfterNewIdx -|
1204
24.6k
      // => |- X0/OldIdxOut -| ... |- Xn -| |- undef/NewS. -| |- AfterNewIdx -|
1205
24.6k
      assert(AfterNewIdx != OldIdxOut && "Inconsistent iterators");
1206
24.6k
      std::copy(std::next(OldIdxOut), AfterNewIdx, OldIdxOut);
1207
24.6k
      // We can reuse OldIdxVNI now.
1208
24.6k
      LiveRange::iterator NewSegment = std::prev(AfterNewIdx);
1209
24.6k
      VNInfo *NewSegmentVNI = OldIdxVNI;
1210
24.6k
      NewSegmentVNI->def = NewIdxDef;
1211
24.6k
      *NewSegment = LiveRange::Segment(NewIdxDef, NewIdxDef.getDeadSlot(),
1212
24.6k
                                       NewSegmentVNI);
1213
24.6k
    }
1214
24.6k
  }
1215
1216
  /// Update LR to reflect an instruction has been moved upwards from OldIdx
1217
  /// to NewIdx (NewIdx < OldIdx).
1218
179k
  void handleMoveUp(LiveRange &LR, unsigned Reg, LaneBitmask LaneMask) {
1219
179k
    LiveRange::iterator E = LR.end();
1220
179k
    // Segment going into OldIdx.
1221
179k
    LiveRange::iterator OldIdxIn = LR.find(OldIdx.getBaseIndex());
1222
179k
1223
179k
    // No value live before or after OldIdx? Nothing to do.
1224
179k
    if (OldIdxIn == E || 
SlotIndex::isEarlierInstr(OldIdx, OldIdxIn->start)177k
)
1225
5.54k
      return;
1226
173k
1227
173k
    LiveRange::iterator OldIdxOut;
1228
173k
    // Do we have a value live-in to OldIdx?
1229
173k
    if (SlotIndex::isEarlierInstr(OldIdxIn->start, OldIdx)) {
1230
83.5k
      // If the live-in value isn't killed here, then we have no Def at
1231
83.5k
      // OldIdx, moreover the value must be live at NewIdx so there is nothing
1232
83.5k
      // to do.
1233
83.5k
      bool isKill = SlotIndex::isSameInstr(OldIdx, OldIdxIn->end);
1234
83.5k
      if (!isKill)
1235
12.4k
        return;
1236
71.1k
1237
71.1k
      // At this point we have to move OldIdxIn->end back to the nearest
1238
71.1k
      // previous use or (dead-)def but no further than NewIdx.
1239
71.1k
      SlotIndex DefBeforeOldIdx
1240
71.1k
        = std::max(OldIdxIn->start.getDeadSlot(),
1241
71.1k
                   NewIdx.getRegSlot(OldIdxIn->end.isEarlyClobber()));
1242
71.1k
      OldIdxIn->end = findLastUseBefore(DefBeforeOldIdx, Reg, LaneMask);
1243
71.1k
1244
71.1k
      // Did we have a Def at OldIdx? If not we are done now.
1245
71.1k
      OldIdxOut = std::next(OldIdxIn);
1246
71.1k
      if (OldIdxOut == E || 
!SlotIndex::isSameInstr(OldIdx, OldIdxOut->start)18.8k
)
1247
66.2k
        return;
1248
90.2k
    } else {
1249
90.2k
      OldIdxOut = OldIdxIn;
1250
90.2k
      OldIdxIn = OldIdxOut != LR.begin() ? 
std::prev(OldIdxOut)20.6k
:
E69.5k
;
1251
90.2k
    }
1252
173k
1253
173k
    // If we are here then there is a Definition at OldIdx. OldIdxOut points
1254
173k
    // to the segment starting there.
1255
173k
    assert(OldIdxOut != E && SlotIndex::isSameInstr(OldIdx, OldIdxOut->start) &&
1256
95.1k
           "No def?");
1257
95.1k
    VNInfo *OldIdxVNI = OldIdxOut->valno;
1258
95.1k
    assert(OldIdxVNI->def == OldIdxOut->start && "Inconsistent def");
1259
95.1k
    bool OldIdxDefIsDead = OldIdxOut->end.isDead();
1260
95.1k
1261
95.1k
    // Is there an existing def at NewIdx?
1262
95.1k
    SlotIndex NewIdxDef = NewIdx.getRegSlot(OldIdxOut->start.isEarlyClobber());
1263
95.1k
    LiveRange::iterator NewIdxOut = LR.find(NewIdx.getRegSlot());
1264
95.1k
    if (SlotIndex::isSameInstr(NewIdxOut->start, NewIdx)) {
1265
0
      assert(NewIdxOut->valno != OldIdxVNI &&
1266
0
             "Same value defined more than once?");
1267
0
      // If OldIdx was a dead def remove it.
1268
0
      if (!OldIdxDefIsDead) {
1269
0
        // Remove segment starting at NewIdx and move begin of OldIdxOut to
1270
0
        // NewIdx so it can take its place.
1271
0
        OldIdxVNI->def = NewIdxDef;
1272
0
        OldIdxOut->start = NewIdxDef;
1273
0
        LR.removeValNo(NewIdxOut->valno);
1274
0
      } else {
1275
0
        // Simply remove the dead def at OldIdx.
1276
0
        LR.removeValNo(OldIdxVNI);
1277
0
      }
1278
95.1k
    } else {
1279
95.1k
      // Previously nothing was live after NewIdx, so all we have to do now is
1280
95.1k
      // move the begin of OldIdxOut to NewIdx.
1281
95.1k
      if (!OldIdxDefIsDead) {
1282
76.0k
        // Do we have any intermediate Defs between OldIdx and NewIdx?
1283
76.0k
        if (OldIdxIn != E &&
1284
76.0k
            
SlotIndex::isEarlierInstr(NewIdxDef, OldIdxIn->start)7.17k
) {
1285
456
          // OldIdx is not a dead def and NewIdx is before predecessor start.
1286
456
          LiveRange::iterator NewIdxIn = NewIdxOut;
1287
456
          assert(NewIdxIn == LR.find(NewIdx.getBaseIndex()));
1288
456
          const SlotIndex SplitPos = NewIdxDef;
1289
456
          OldIdxVNI = OldIdxIn->valno;
1290
456
1291
456
          // Merge the OldIdxIn and OldIdxOut segments into OldIdxOut.
1292
456
          OldIdxOut->valno->def = OldIdxIn->start;
1293
456
          *OldIdxOut = LiveRange::Segment(OldIdxIn->start, OldIdxOut->end,
1294
456
                                          OldIdxOut->valno);
1295
456
          // OldIdxIn and OldIdxVNI are now undef and can be overridden.
1296
456
          // We Slide [NewIdxIn, OldIdxIn) down one position.
1297
456
          //    |- X0/NewIdxIn -| ... |- Xn-1 -||- Xn/OldIdxIn -||- OldIdxOut -|
1298
456
          // => |- undef/NexIdxIn -| |- X0 -| ... |- Xn-1 -| |- Xn/OldIdxOut -|
1299
456
          std::copy_backward(NewIdxIn, OldIdxIn, OldIdxOut);
1300
456
          // NewIdxIn is now considered undef so we can reuse it for the moved
1301
456
          // value.
1302
456
          LiveRange::iterator NewSegment = NewIdxIn;
1303
456
          LiveRange::iterator Next = std::next(NewSegment);
1304
456
          if (SlotIndex::isEarlierInstr(Next->start, NewIdx)) {
1305
219
            // There is no gap between NewSegment and its predecessor.
1306
219
            *NewSegment = LiveRange::Segment(Next->start, SplitPos,
1307
219
                                             Next->valno);
1308
219
            *Next = LiveRange::Segment(SplitPos, Next->end, OldIdxVNI);
1309
219
            Next->valno->def = SplitPos;
1310
237
          } else {
1311
237
            // There is a gap between NewSegment and its predecessor
1312
237
            // Value becomes live in.
1313
237
            *NewSegment = LiveRange::Segment(SplitPos, Next->start, OldIdxVNI);
1314
237
            NewSegment->valno->def = SplitPos;
1315
237
          }
1316
75.6k
        } else {
1317
75.6k
          // Leave the end point of a live def.
1318
75.6k
          OldIdxOut->start = NewIdxDef;
1319
75.6k
          OldIdxVNI->def = NewIdxDef;
1320
75.6k
          if (OldIdxIn != E && 
SlotIndex::isEarlierInstr(NewIdx, OldIdxIn->end)6.71k
)
1321
21
            OldIdxIn->end = NewIdx.getRegSlot();
1322
75.6k
        }
1323
76.0k
      } else 
if (19.0k
OldIdxIn != E19.0k
1324
19.0k
          && 
SlotIndex::isEarlierInstr(NewIdxOut->start, NewIdx)18.3k
1325
19.0k
          && 
SlotIndex::isEarlierInstr(NewIdx, NewIdxOut->end)1
) {
1326
1
        // OldIdxVNI is a dead def that has been moved into the middle of
1327
1
        // another value in LR. That can happen when LR is a whole register,
1328
1
        // but the dead def is a write to a subreg that is dead at NewIdx.
1329
1
        // The dead def may have been moved across other values
1330
1
        // in LR, so move OldIdxOut up to NewIdxOut. Slide [NewIdxOut;OldIdxOut)
1331
1
        // down one position.
1332
1
        //    |- X0/NewIdxOut -| ... |- Xn-1 -| |- Xn/OldIdxOut -| |- next - |
1333
1
        // => |- X0/NewIdxOut -| |- X0 -| ... |- Xn-1 -| |- next -|
1334
1
        std::copy_backward(NewIdxOut, OldIdxOut, std::next(OldIdxOut));
1335
1
        // Modify the segment at NewIdxOut and the following segment to meet at
1336
1
        // the point of the dead def, with the following segment getting
1337
1
        // OldIdxVNI as its value number.
1338
1
        *NewIdxOut = LiveRange::Segment(
1339
1
            NewIdxOut->start, NewIdxDef.getRegSlot(), NewIdxOut->valno);
1340
1
        *(NewIdxOut + 1) = LiveRange::Segment(
1341
1
            NewIdxDef.getRegSlot(), (NewIdxOut + 1)->end, OldIdxVNI);
1342
1
        OldIdxVNI->def = NewIdxDef;
1343
1
        // Modify subsequent segments to be defined by the moved def OldIdxVNI.
1344
1
        for (auto Idx = NewIdxOut + 2; Idx <= OldIdxOut; 
++Idx0
)
1345
0
          Idx->valno = OldIdxVNI;
1346
1
        // Aggressively remove all dead flags from the former dead definition.
1347
1
        // Kill/dead flags shouldn't be used while live intervals exist; they
1348
1
        // will be reinserted by VirtRegRewriter.
1349
1
        if (MachineInstr *KillMI = LIS.getInstructionFromIndex(NewIdx))
1350
6
          
for (MIBundleOperands MO(*KillMI); 1
MO.isValid();
++MO5
)
1351
5
            if (MO->isReg() && !MO->isUse())
1352
1
              MO->setIsDead(false);
1353
19.0k
      } else {
1354
19.0k
        // OldIdxVNI is a dead def. It may have been moved across other values
1355
19.0k
        // in LR, so move OldIdxOut up to NewIdxOut. Slide [NewIdxOut;OldIdxOut)
1356
19.0k
        // down one position.
1357
19.0k
        //    |- X0/NewIdxOut -| ... |- Xn-1 -| |- Xn/OldIdxOut -| |- next - |
1358
19.0k
        // => |- undef/NewIdxOut -| |- X0 -| ... |- Xn-1 -| |- next -|
1359
19.0k
        std::copy_backward(NewIdxOut, OldIdxOut, std::next(OldIdxOut));
1360
19.0k
        // OldIdxVNI can be reused now to build a new dead def segment.
1361
19.0k
        LiveRange::iterator NewSegment = NewIdxOut;
1362
19.0k
        VNInfo *NewSegmentVNI = OldIdxVNI;
1363
19.0k
        *NewSegment = LiveRange::Segment(NewIdxDef, NewIdxDef.getDeadSlot(),
1364
19.0k
                                         NewSegmentVNI);
1365
19.0k
        NewSegmentVNI->def = NewIdxDef;
1366
19.0k
      }
1367
95.1k
    }
1368
95.1k
  }
1369
1370
0
  void updateRegMaskSlots() {
1371
0
    SmallVectorImpl<SlotIndex>::iterator RI =
1372
0
        llvm::lower_bound(LIS.RegMaskSlots, OldIdx);
1373
0
    assert(RI != LIS.RegMaskSlots.end() && *RI == OldIdx.getRegSlot() &&
1374
0
           "No RegMask at OldIdx.");
1375
0
    *RI = NewIdx.getRegSlot();
1376
0
    assert((RI == LIS.RegMaskSlots.begin() ||
1377
0
            SlotIndex::isEarlierInstr(*std::prev(RI), *RI)) &&
1378
0
           "Cannot move regmask instruction above another call");
1379
0
    assert((std::next(RI) == LIS.RegMaskSlots.end() ||
1380
0
            SlotIndex::isEarlierInstr(*RI, *std::next(RI))) &&
1381
0
           "Cannot move regmask instruction below another call");
1382
0
  }
1383
1384
  // Return the last use of reg between NewIdx and OldIdx.
1385
  SlotIndex findLastUseBefore(SlotIndex Before, unsigned Reg,
1386
71.1k
                              LaneBitmask LaneMask) {
1387
71.1k
    if (TargetRegisterInfo::isVirtualRegister(Reg)) {
1388
50.8k
      SlotIndex LastUse = Before;
1389
128k
      for (MachineOperand &MO : MRI.use_nodbg_operands(Reg)) {
1390
128k
        if (MO.isUndef())
1391
3
          continue;
1392
128k
        unsigned SubReg = MO.getSubReg();
1393
128k
        if (SubReg != 0 && 
LaneMask.any()37.1k
1394
128k
            && 
(TRI.getSubRegIndexLaneMask(SubReg) & LaneMask).none()23.4k
)
1395
16.2k
          continue;
1396
112k
1397
112k
        const MachineInstr &MI = *MO.getParent();
1398
112k
        SlotIndex InstSlot = LIS.getSlotIndexes()->getInstructionIndex(MI);
1399
112k
        if (InstSlot > LastUse && 
InstSlot < OldIdx19.5k
)
1400
11.1k
          LastUse = InstSlot.getRegSlot();
1401
112k
      }
1402
50.8k
      return LastUse;
1403
50.8k
    }
1404
20.2k
1405
20.2k
    // This is a regunit interval, so scanning the use list could be very
1406
20.2k
    // expensive. Scan upwards from OldIdx instead.
1407
20.2k
    assert(Before < OldIdx && "Expected upwards move");
1408
20.2k
    SlotIndexes *Indexes = LIS.getSlotIndexes();
1409
20.2k
    MachineBasicBlock *MBB = Indexes->getMBBFromIndex(Before);
1410
20.2k
1411
20.2k
    // OldIdx may not correspond to an instruction any longer, so set MII to
1412
20.2k
    // point to the next instruction after OldIdx, or MBB->end().
1413
20.2k
    MachineBasicBlock::iterator MII = MBB->end();
1414
20.2k
    if (MachineInstr *MI = Indexes->getInstructionFromIndex(
1415
20.2k
                           Indexes->getNextNonNullIndex(OldIdx)))
1416
20.2k
      if (MI->getParent() == MBB)
1417
19.3k
        MII = MI;
1418
20.2k
1419
20.2k
    MachineBasicBlock::iterator Begin = MBB->begin();
1420
86.8k
    while (MII != Begin) {
1421
86.8k
      if ((--MII)->isDebugInstr())
1422
2
        continue;
1423
86.8k
      SlotIndex Idx = Indexes->getInstructionIndex(*MII);
1424
86.8k
1425
86.8k
      // Stop searching when Before is reached.
1426
86.8k
      if (!SlotIndex::isEarlierInstr(Before, Idx))
1427
20.2k
        return Before;
1428
66.5k
1429
66.5k
      // Check if MII uses Reg.
1430
261k
      
for (MIBundleOperands MO(*MII); 66.5k
MO.isValid();
++MO194k
)
1431
194k
        if (MO->isReg() && 
!MO->isUndef()135k
&&
1432
194k
            
TargetRegisterInfo::isPhysicalRegister(MO->getReg())134k
&&
1433
194k
            
TRI.hasRegUnit(MO->getReg(), Reg)63.2k
)
1434
0
          return Idx.getRegSlot();
1435
66.5k
    }
1436
20.2k
    // Didn't reach Before. It must be the first instruction in the block.
1437
20.2k
    
return Before0
;
1438
20.2k
  }
1439
};
1440
1441
838k
void LiveIntervals::handleMove(MachineInstr &MI, bool UpdateFlags) {
1442
838k
  // It is fine to move a bundle as a whole, but not an individual instruction
1443
838k
  // inside it.
1444
838k
  assert((!MI.isBundled() || MI.getOpcode() == TargetOpcode::BUNDLE) &&
1445
838k
         "Cannot move instruction in bundle");
1446
838k
  SlotIndex OldIndex = Indexes->getInstructionIndex(MI);
1447
838k
  Indexes->removeMachineInstrFromMaps(MI);
1448
838k
  SlotIndex NewIndex = Indexes->insertMachineInstrInMaps(MI);
1449
838k
  assert(getMBBStartIdx(MI.getParent()) <= OldIndex &&
1450
838k
         OldIndex < getMBBEndIdx(MI.getParent()) &&
1451
838k
         "Cannot handle moves across basic block boundaries.");
1452
838k
1453
838k
  HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags);
1454
838k
  HME.updateAllRanges(&MI);
1455
838k
}
1456
1457
void LiveIntervals::handleMoveIntoBundle(MachineInstr &MI,
1458
                                         MachineInstr &BundleStart,
1459
0
                                         bool UpdateFlags) {
1460
0
  SlotIndex OldIndex = Indexes->getInstructionIndex(MI);
1461
0
  SlotIndex NewIndex = Indexes->getInstructionIndex(BundleStart);
1462
0
  HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags);
1463
0
  HME.updateAllRanges(&MI);
1464
0
}
1465
1466
void LiveIntervals::repairOldRegInRange(const MachineBasicBlock::iterator Begin,
1467
                                        const MachineBasicBlock::iterator End,
1468
                                        const SlotIndex endIdx,
1469
                                        LiveRange &LR, const unsigned Reg,
1470
57
                                        LaneBitmask LaneMask) {
1471
57
  LiveInterval::iterator LII = LR.find(endIdx);
1472
57
  SlotIndex lastUseIdx;
1473
57
  if (LII == LR.begin()) {
1474
29
    // This happens when the function is called for a subregister that only
1475
29
    // occurs _after_ the range that is to be repaired.
1476
29
    return;
1477
29
  }
1478
28
  if (LII != LR.end() && 
LII->start < endIdx0
)
1479
0
    lastUseIdx = LII->end;
1480
28
  else
1481
28
    --LII;
1482
28
1483
194
  for (MachineBasicBlock::iterator I = End; I != Begin;) {
1484
166
    --I;
1485
166
    MachineInstr &MI = *I;
1486
166
    if (MI.isDebugInstr())
1487
0
      continue;
1488
166
1489
166
    SlotIndex instrIdx = getInstructionIndex(MI);
1490
166
    bool isStartValid = getInstructionFromIndex(LII->start);
1491
166
    bool isEndValid = getInstructionFromIndex(LII->end);
1492
166
1493
166
    // FIXME: This doesn't currently handle early-clobber or multiple removed
1494
166
    // defs inside of the region to repair.
1495
166
    for (MachineInstr::mop_iterator OI = MI.operands_begin(),
1496
166
                                    OE = MI.operands_end();
1497
1.15k
         OI != OE; 
++OI991
) {
1498
991
      const MachineOperand &MO = *OI;
1499
991
      if (!MO.isReg() || 
MO.getReg() != Reg808
)
1500
935
        continue;
1501
56
1502
56
      unsigned SubReg = MO.getSubReg();
1503
56
      LaneBitmask Mask = TRI->getSubRegIndexLaneMask(SubReg);
1504
56
      if ((Mask & LaneMask).none())
1505
0
        continue;
1506
56
1507
56
      if (MO.isDef()) {
1508
28
        if (!isStartValid) {
1509
0
          if (LII->end.isDead()) {
1510
0
            SlotIndex prevStart;
1511
0
            if (LII != LR.begin())
1512
0
              prevStart = std::prev(LII)->start;
1513
0
1514
0
            // FIXME: This could be more efficient if there was a
1515
0
            // removeSegment method that returned an iterator.
1516
0
            LR.removeSegment(*LII, true);
1517
0
            if (prevStart.isValid())
1518
0
              LII = LR.find(prevStart);
1519
0
            else
1520
0
              LII = LR.begin();
1521
0
          } else {
1522
0
            LII->start = instrIdx.getRegSlot();
1523
0
            LII->valno->def = instrIdx.getRegSlot();
1524
0
            if (MO.getSubReg() && !MO.isUndef())
1525
0
              lastUseIdx = instrIdx.getRegSlot();
1526
0
            else
1527
0
              lastUseIdx = SlotIndex();
1528
0
            continue;
1529
0
          }
1530
28
        }
1531
28
1532
28
        if (!lastUseIdx.isValid()) {
1533
0
          VNInfo *VNI = LR.getNextValue(instrIdx.getRegSlot(), VNInfoAllocator);
1534
0
          LiveRange::Segment S(instrIdx.getRegSlot(),
1535
0
                               instrIdx.getDeadSlot(), VNI);
1536
0
          LII = LR.addSegment(S);
1537
28
        } else if (LII->start != instrIdx.getRegSlot()) {
1538
0
          VNInfo *VNI = LR.getNextValue(instrIdx.getRegSlot(), VNInfoAllocator);
1539
0
          LiveRange::Segment S(instrIdx.getRegSlot(), lastUseIdx, VNI);
1540
0
          LII = LR.addSegment(S);
1541
0
        }
1542
28
1543
28
        if (MO.getSubReg() && 
!MO.isUndef()0
)
1544
0
          lastUseIdx = instrIdx.getRegSlot();
1545
28
        else
1546
28
          lastUseIdx = SlotIndex();
1547
28
      } else if (MO.isUse()) {
1548
28
        // FIXME: This should probably be handled outside of this branch,
1549
28
        // either as part of the def case (for defs inside of the region) or
1550
28
        // after the loop over the region.
1551
28
        if (!isEndValid && !LII->end.isBlock())
1552
28
          LII->end = instrIdx.getRegSlot();
1553
28
        if (!lastUseIdx.isValid())
1554
28
          lastUseIdx = instrIdx.getRegSlot();
1555
28
      }
1556
56
    }
1557
166
  }
1558
28
}
1559
1560
void
1561
LiveIntervals::repairIntervalsInRange(MachineBasicBlock *MBB,
1562
                                      MachineBasicBlock::iterator Begin,
1563
                                      MachineBasicBlock::iterator End,
1564
29
                                      ArrayRef<unsigned> OrigRegs) {
1565
29
  // Find anchor points, which are at the beginning/end of blocks or at
1566
29
  // instructions that already have indexes.
1567
86
  while (Begin != MBB->begin() && 
!Indexes->hasIndex(*Begin)75
)
1568
57
    --Begin;
1569
58
  while (End != MBB->end() && !Indexes->hasIndex(*End))
1570
29
    ++End;
1571
29
1572
29
  SlotIndex endIdx;
1573
29
  if (End == MBB->end())
1574
0
    endIdx = getMBBEndIdx(MBB).getPrevSlot();
1575
29
  else
1576
29
    endIdx = getInstructionIndex(*End);
1577
29
1578
29
  Indexes->repairIndexesInRange(MBB, Begin, End);
1579
29
1580
201
  for (MachineBasicBlock::iterator I = End; I != Begin;) {
1581
172
    --I;
1582
172
    MachineInstr &MI = *I;
1583
172
    if (MI.isDebugInstr())
1584
0
      continue;
1585
172
    for (MachineInstr::const_mop_iterator MOI = MI.operands_begin(),
1586
172
                                          MOE = MI.operands_end();
1587
1.19k
         MOI != MOE; 
++MOI1.02k
) {
1588
1.02k
      if (MOI->isReg() &&
1589
1.02k
          
TargetRegisterInfo::isVirtualRegister(MOI->getReg())838
&&
1590
1.02k
          
!hasInterval(MOI->getReg())95
) {
1591
0
        createAndComputeVirtRegInterval(MOI->getReg());
1592
0
      }
1593
1.02k
    }
1594
172
  }
1595
29
1596
87
  for (unsigned Reg : OrigRegs) {
1597
87
    if (!TargetRegisterInfo::isVirtualRegister(Reg))
1598
30
      continue;
1599
57
1600
57
    LiveInterval &LI = getInterval(Reg);
1601
57
    // FIXME: Should we support undefs that gain defs?
1602
57
    if (!LI.hasAtLeastOneValue())
1603
0
      continue;
1604
57
1605
57
    for (LiveInterval::SubRange &S : LI.subranges())
1606
0
      repairOldRegInRange(Begin, End, endIdx, S, Reg, S.LaneMask);
1607
57
1608
57
    repairOldRegInRange(Begin, End, endIdx, LI, Reg);
1609
57
  }
1610
29
}
1611
1612
21.7k
void LiveIntervals::removePhysRegDefAt(unsigned Reg, SlotIndex Pos) {
1613
43.6k
  for (MCRegUnitIterator Unit(Reg, TRI); Unit.isValid(); 
++Unit21.8k
) {
1614
21.8k
    if (LiveRange *LR = getCachedRegUnit(*Unit))
1615
530
      if (VNInfo *VNI = LR->getVNInfoAt(Pos))
1616
460
        LR->removeValNo(VNI);
1617
21.8k
  }
1618
21.7k
}
1619
1620
688k
void LiveIntervals::removeVRegDefAt(LiveInterval &LI, SlotIndex Pos) {
1621
688k
  // LI may not have the main range computed yet, but its subranges may
1622
688k
  // be present.
1623
688k
  VNInfo *VNI = LI.getVNInfoAt(Pos);
1624
688k
  if (VNI != nullptr) {
1625
688k
    assert(VNI->def.getBaseIndex() == Pos.getBaseIndex());
1626
688k
    LI.removeValNo(VNI);
1627
688k
  }
1628
688k
1629
688k
  // Also remove the value defined in subranges.
1630
688k
  for (LiveInterval::SubRange &S : LI.subranges()) {
1631
90
    if (VNInfo *SVNI = S.getVNInfoAt(Pos))
1632
89
      if (SVNI->def.getBaseIndex() == Pos.getBaseIndex())
1633
89
        S.removeValNo(SVNI);
1634
90
  }
1635
688k
  LI.removeEmptySubRanges();
1636
688k
}
1637
1638
void LiveIntervals::splitSeparateComponents(LiveInterval &LI,
1639
444k
    SmallVectorImpl<LiveInterval*> &SplitLIs) {
1640
444k
  ConnectedVNInfoEqClasses ConEQ(*this);
1641
444k
  unsigned NumComp = ConEQ.Classify(LI);
1642
444k
  if (NumComp <= 1)
1643
379k
    return;
1644
64.5k
  LLVM_DEBUG(dbgs() << "  Split " << NumComp << " components: " << LI << '\n');
1645
64.5k
  unsigned Reg = LI.reg;
1646
64.5k
  const TargetRegisterClass *RegClass = MRI->getRegClass(Reg);
1647
147k
  for (unsigned I = 1; I < NumComp; 
++I82.4k
) {
1648
82.4k
    unsigned NewVReg = MRI->createVirtualRegister(RegClass);
1649
82.4k
    LiveInterval &NewLI = createEmptyInterval(NewVReg);
1650
82.4k
    SplitLIs.push_back(&NewLI);
1651
82.4k
  }
1652
64.5k
  ConEQ.Distribute(LI, SplitLIs.data(), *MRI);
1653
64.5k
}
1654
1655
625
void LiveIntervals::constructMainRangeFromSubranges(LiveInterval &LI) {
1656
625
  assert(LRCalc && "LRCalc not initialized.");
1657
625
  LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
1658
625
  LRCalc->constructMainRangeFromSubranges(LI);
1659
625
}