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