1 //===- RegisterPressure.cpp - Dynamic Register Pressure -------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements the RegisterPressure class which can be used to track
10 // MachineInstr level register pressure.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #include "llvm/CodeGen/RegisterPressure.h"
15 #include "llvm/ADT/ArrayRef.h"
16 #include "llvm/ADT/STLExtras.h"
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/CodeGen/LiveInterval.h"
19 #include "llvm/CodeGen/LiveIntervals.h"
20 #include "llvm/CodeGen/MachineBasicBlock.h"
21 #include "llvm/CodeGen/MachineFunction.h"
22 #include "llvm/CodeGen/MachineInstr.h"
23 #include "llvm/CodeGen/MachineInstrBundle.h"
24 #include "llvm/CodeGen/MachineOperand.h"
25 #include "llvm/CodeGen/MachineRegisterInfo.h"
26 #include "llvm/CodeGen/RegisterClassInfo.h"
27 #include "llvm/CodeGen/SlotIndexes.h"
28 #include "llvm/CodeGen/TargetRegisterInfo.h"
29 #include "llvm/CodeGen/TargetSubtargetInfo.h"
30 #include "llvm/Config/llvm-config.h"
31 #include "llvm/MC/LaneBitmask.h"
32 #include "llvm/MC/MCRegisterInfo.h"
33 #include "llvm/Support/Compiler.h"
34 #include "llvm/Support/Debug.h"
35 #include "llvm/Support/ErrorHandling.h"
36 #include "llvm/Support/raw_ostream.h"
37 #include <algorithm>
38 #include <cassert>
39 #include <cstdint>
40 #include <cstdlib>
41 #include <cstring>
42 #include <iterator>
43 #include <limits>
44 #include <utility>
45 #include <vector>
46
47 using namespace llvm;
48
49 /// Increase pressure for each pressure set provided by TargetRegisterInfo.
increaseSetPressure(std::vector<unsigned> & CurrSetPressure,const MachineRegisterInfo & MRI,unsigned Reg,LaneBitmask PrevMask,LaneBitmask NewMask)50 static void increaseSetPressure(std::vector<unsigned> &CurrSetPressure,
51 const MachineRegisterInfo &MRI, unsigned Reg,
52 LaneBitmask PrevMask, LaneBitmask NewMask) {
53 assert((PrevMask & ~NewMask).none() && "Must not remove bits");
54 if (PrevMask.any() || NewMask.none())
55 return;
56
57 PSetIterator PSetI = MRI.getPressureSets(Reg);
58 unsigned Weight = PSetI.getWeight();
59 for (; PSetI.isValid(); ++PSetI)
60 CurrSetPressure[*PSetI] += Weight;
61 }
62
63 /// Decrease pressure for each pressure set provided by TargetRegisterInfo.
decreaseSetPressure(std::vector<unsigned> & CurrSetPressure,const MachineRegisterInfo & MRI,Register Reg,LaneBitmask PrevMask,LaneBitmask NewMask)64 static void decreaseSetPressure(std::vector<unsigned> &CurrSetPressure,
65 const MachineRegisterInfo &MRI, Register Reg,
66 LaneBitmask PrevMask, LaneBitmask NewMask) {
67 //assert((NewMask & !PrevMask) == 0 && "Must not add bits");
68 if (NewMask.any() || PrevMask.none())
69 return;
70
71 PSetIterator PSetI = MRI.getPressureSets(Reg);
72 unsigned Weight = PSetI.getWeight();
73 for (; PSetI.isValid(); ++PSetI) {
74 assert(CurrSetPressure[*PSetI] >= Weight && "register pressure underflow");
75 CurrSetPressure[*PSetI] -= Weight;
76 }
77 }
78
79 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
80 LLVM_DUMP_METHOD
dumpRegSetPressure(ArrayRef<unsigned> SetPressure,const TargetRegisterInfo * TRI)81 void llvm::dumpRegSetPressure(ArrayRef<unsigned> SetPressure,
82 const TargetRegisterInfo *TRI) {
83 bool Empty = true;
84 for (unsigned i = 0, e = SetPressure.size(); i < e; ++i) {
85 if (SetPressure[i] != 0) {
86 dbgs() << TRI->getRegPressureSetName(i) << "=" << SetPressure[i] << '\n';
87 Empty = false;
88 }
89 }
90 if (Empty)
91 dbgs() << "\n";
92 }
93
94 LLVM_DUMP_METHOD
dump(const TargetRegisterInfo * TRI) const95 void RegisterPressure::dump(const TargetRegisterInfo *TRI) const {
96 dbgs() << "Max Pressure: ";
97 dumpRegSetPressure(MaxSetPressure, TRI);
98 dbgs() << "Live In: ";
99 for (const RegisterMaskPair &P : LiveInRegs) {
100 dbgs() << printVRegOrUnit(P.RegUnit, TRI);
101 if (!P.LaneMask.all())
102 dbgs() << ':' << PrintLaneMask(P.LaneMask);
103 dbgs() << ' ';
104 }
105 dbgs() << '\n';
106 dbgs() << "Live Out: ";
107 for (const RegisterMaskPair &P : LiveOutRegs) {
108 dbgs() << printVRegOrUnit(P.RegUnit, TRI);
109 if (!P.LaneMask.all())
110 dbgs() << ':' << PrintLaneMask(P.LaneMask);
111 dbgs() << ' ';
112 }
113 dbgs() << '\n';
114 }
115
116 LLVM_DUMP_METHOD
dump() const117 void RegPressureTracker::dump() const {
118 if (!isTopClosed() || !isBottomClosed()) {
119 dbgs() << "Curr Pressure: ";
120 dumpRegSetPressure(CurrSetPressure, TRI);
121 }
122 P.dump(TRI);
123 }
124
125 LLVM_DUMP_METHOD
dump(const TargetRegisterInfo & TRI) const126 void PressureDiff::dump(const TargetRegisterInfo &TRI) const {
127 const char *sep = "";
128 for (const PressureChange &Change : *this) {
129 if (!Change.isValid())
130 break;
131 dbgs() << sep << TRI.getRegPressureSetName(Change.getPSet())
132 << " " << Change.getUnitInc();
133 sep = " ";
134 }
135 dbgs() << '\n';
136 }
137
138 LLVM_DUMP_METHOD
dump() const139 void PressureChange::dump() const {
140 dbgs() << "[" << getPSetOrMax() << ", " << getUnitInc() << "]\n";
141 }
142
dump() const143 void RegPressureDelta::dump() const {
144 dbgs() << "[Excess=";
145 Excess.dump();
146 dbgs() << ", CriticalMax=";
147 CriticalMax.dump();
148 dbgs() << ", CurrentMax=";
149 CurrentMax.dump();
150 dbgs() << "]\n";
151 }
152
153 #endif
154
increaseRegPressure(Register RegUnit,LaneBitmask PreviousMask,LaneBitmask NewMask)155 void RegPressureTracker::increaseRegPressure(Register RegUnit,
156 LaneBitmask PreviousMask,
157 LaneBitmask NewMask) {
158 if (PreviousMask.any() || NewMask.none())
159 return;
160
161 PSetIterator PSetI = MRI->getPressureSets(RegUnit);
162 unsigned Weight = PSetI.getWeight();
163 for (; PSetI.isValid(); ++PSetI) {
164 CurrSetPressure[*PSetI] += Weight;
165 P.MaxSetPressure[*PSetI] =
166 std::max(P.MaxSetPressure[*PSetI], CurrSetPressure[*PSetI]);
167 }
168 }
169
decreaseRegPressure(Register RegUnit,LaneBitmask PreviousMask,LaneBitmask NewMask)170 void RegPressureTracker::decreaseRegPressure(Register RegUnit,
171 LaneBitmask PreviousMask,
172 LaneBitmask NewMask) {
173 decreaseSetPressure(CurrSetPressure, *MRI, RegUnit, PreviousMask, NewMask);
174 }
175
176 /// Clear the result so it can be used for another round of pressure tracking.
reset()177 void IntervalPressure::reset() {
178 TopIdx = BottomIdx = SlotIndex();
179 MaxSetPressure.clear();
180 LiveInRegs.clear();
181 LiveOutRegs.clear();
182 }
183
184 /// Clear the result so it can be used for another round of pressure tracking.
reset()185 void RegionPressure::reset() {
186 TopPos = BottomPos = MachineBasicBlock::const_iterator();
187 MaxSetPressure.clear();
188 LiveInRegs.clear();
189 LiveOutRegs.clear();
190 }
191
192 /// If the current top is not less than or equal to the next index, open it.
193 /// We happen to need the SlotIndex for the next top for pressure update.
openTop(SlotIndex NextTop)194 void IntervalPressure::openTop(SlotIndex NextTop) {
195 if (TopIdx <= NextTop)
196 return;
197 TopIdx = SlotIndex();
198 LiveInRegs.clear();
199 }
200
201 /// If the current top is the previous instruction (before receding), open it.
openTop(MachineBasicBlock::const_iterator PrevTop)202 void RegionPressure::openTop(MachineBasicBlock::const_iterator PrevTop) {
203 if (TopPos != PrevTop)
204 return;
205 TopPos = MachineBasicBlock::const_iterator();
206 LiveInRegs.clear();
207 }
208
209 /// If the current bottom is not greater than the previous index, open it.
openBottom(SlotIndex PrevBottom)210 void IntervalPressure::openBottom(SlotIndex PrevBottom) {
211 if (BottomIdx > PrevBottom)
212 return;
213 BottomIdx = SlotIndex();
214 LiveInRegs.clear();
215 }
216
217 /// If the current bottom is the previous instr (before advancing), open it.
openBottom(MachineBasicBlock::const_iterator PrevBottom)218 void RegionPressure::openBottom(MachineBasicBlock::const_iterator PrevBottom) {
219 if (BottomPos != PrevBottom)
220 return;
221 BottomPos = MachineBasicBlock::const_iterator();
222 LiveInRegs.clear();
223 }
224
init(const MachineRegisterInfo & MRI)225 void LiveRegSet::init(const MachineRegisterInfo &MRI) {
226 const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
227 unsigned NumRegUnits = TRI.getNumRegs();
228 unsigned NumVirtRegs = MRI.getNumVirtRegs();
229 Regs.setUniverse(NumRegUnits + NumVirtRegs);
230 this->NumRegUnits = NumRegUnits;
231 }
232
clear()233 void LiveRegSet::clear() {
234 Regs.clear();
235 }
236
getLiveRange(const LiveIntervals & LIS,unsigned Reg)237 static const LiveRange *getLiveRange(const LiveIntervals &LIS, unsigned Reg) {
238 if (Register::isVirtualRegister(Reg))
239 return &LIS.getInterval(Reg);
240 return LIS.getCachedRegUnit(Reg);
241 }
242
reset()243 void RegPressureTracker::reset() {
244 MBB = nullptr;
245 LIS = nullptr;
246
247 CurrSetPressure.clear();
248 LiveThruPressure.clear();
249 P.MaxSetPressure.clear();
250
251 if (RequireIntervals)
252 static_cast<IntervalPressure&>(P).reset();
253 else
254 static_cast<RegionPressure&>(P).reset();
255
256 LiveRegs.clear();
257 UntiedDefs.clear();
258 }
259
260 /// Setup the RegPressureTracker.
261 ///
262 /// TODO: Add support for pressure without LiveIntervals.
init(const MachineFunction * mf,const RegisterClassInfo * rci,const LiveIntervals * lis,const MachineBasicBlock * mbb,MachineBasicBlock::const_iterator pos,bool TrackLaneMasks,bool TrackUntiedDefs)263 void RegPressureTracker::init(const MachineFunction *mf,
264 const RegisterClassInfo *rci,
265 const LiveIntervals *lis,
266 const MachineBasicBlock *mbb,
267 MachineBasicBlock::const_iterator pos,
268 bool TrackLaneMasks, bool TrackUntiedDefs) {
269 reset();
270
271 MF = mf;
272 TRI = MF->getSubtarget().getRegisterInfo();
273 RCI = rci;
274 MRI = &MF->getRegInfo();
275 MBB = mbb;
276 this->TrackUntiedDefs = TrackUntiedDefs;
277 this->TrackLaneMasks = TrackLaneMasks;
278
279 if (RequireIntervals) {
280 assert(lis && "IntervalPressure requires LiveIntervals");
281 LIS = lis;
282 }
283
284 CurrPos = pos;
285 CurrSetPressure.assign(TRI->getNumRegPressureSets(), 0);
286
287 P.MaxSetPressure = CurrSetPressure;
288
289 LiveRegs.init(*MRI);
290 if (TrackUntiedDefs)
291 UntiedDefs.setUniverse(MRI->getNumVirtRegs());
292 }
293
294 /// Does this pressure result have a valid top position and live ins.
isTopClosed() const295 bool RegPressureTracker::isTopClosed() const {
296 if (RequireIntervals)
297 return static_cast<IntervalPressure&>(P).TopIdx.isValid();
298 return (static_cast<RegionPressure&>(P).TopPos ==
299 MachineBasicBlock::const_iterator());
300 }
301
302 /// Does this pressure result have a valid bottom position and live outs.
isBottomClosed() const303 bool RegPressureTracker::isBottomClosed() const {
304 if (RequireIntervals)
305 return static_cast<IntervalPressure&>(P).BottomIdx.isValid();
306 return (static_cast<RegionPressure&>(P).BottomPos ==
307 MachineBasicBlock::const_iterator());
308 }
309
getCurrSlot() const310 SlotIndex RegPressureTracker::getCurrSlot() const {
311 MachineBasicBlock::const_iterator IdxPos =
312 skipDebugInstructionsForward(CurrPos, MBB->end());
313 if (IdxPos == MBB->end())
314 return LIS->getMBBEndIdx(MBB);
315 return LIS->getInstructionIndex(*IdxPos).getRegSlot();
316 }
317
318 /// Set the boundary for the top of the region and summarize live ins.
closeTop()319 void RegPressureTracker::closeTop() {
320 if (RequireIntervals)
321 static_cast<IntervalPressure&>(P).TopIdx = getCurrSlot();
322 else
323 static_cast<RegionPressure&>(P).TopPos = CurrPos;
324
325 assert(P.LiveInRegs.empty() && "inconsistent max pressure result");
326 P.LiveInRegs.reserve(LiveRegs.size());
327 LiveRegs.appendTo(P.LiveInRegs);
328 }
329
330 /// Set the boundary for the bottom of the region and summarize live outs.
closeBottom()331 void RegPressureTracker::closeBottom() {
332 if (RequireIntervals)
333 static_cast<IntervalPressure&>(P).BottomIdx = getCurrSlot();
334 else
335 static_cast<RegionPressure&>(P).BottomPos = CurrPos;
336
337 assert(P.LiveOutRegs.empty() && "inconsistent max pressure result");
338 P.LiveOutRegs.reserve(LiveRegs.size());
339 LiveRegs.appendTo(P.LiveOutRegs);
340 }
341
342 /// Finalize the region boundaries and record live ins and live outs.
closeRegion()343 void RegPressureTracker::closeRegion() {
344 if (!isTopClosed() && !isBottomClosed()) {
345 assert(LiveRegs.size() == 0 && "no region boundary");
346 return;
347 }
348 if (!isBottomClosed())
349 closeBottom();
350 else if (!isTopClosed())
351 closeTop();
352 // If both top and bottom are closed, do nothing.
353 }
354
355 /// The register tracker is unaware of global liveness so ignores normal
356 /// live-thru ranges. However, two-address or coalesced chains can also lead
357 /// to live ranges with no holes. Count these to inform heuristics that we
358 /// can never drop below this pressure.
initLiveThru(const RegPressureTracker & RPTracker)359 void RegPressureTracker::initLiveThru(const RegPressureTracker &RPTracker) {
360 LiveThruPressure.assign(TRI->getNumRegPressureSets(), 0);
361 assert(isBottomClosed() && "need bottom-up tracking to intialize.");
362 for (const RegisterMaskPair &Pair : P.LiveOutRegs) {
363 Register RegUnit = Pair.RegUnit;
364 if (Register::isVirtualRegister(RegUnit)
365 && !RPTracker.hasUntiedDef(RegUnit))
366 increaseSetPressure(LiveThruPressure, *MRI, RegUnit,
367 LaneBitmask::getNone(), Pair.LaneMask);
368 }
369 }
370
getRegLanes(ArrayRef<RegisterMaskPair> RegUnits,Register RegUnit)371 static LaneBitmask getRegLanes(ArrayRef<RegisterMaskPair> RegUnits,
372 Register RegUnit) {
373 auto I = llvm::find_if(RegUnits, [RegUnit](const RegisterMaskPair Other) {
374 return Other.RegUnit == RegUnit;
375 });
376 if (I == RegUnits.end())
377 return LaneBitmask::getNone();
378 return I->LaneMask;
379 }
380
addRegLanes(SmallVectorImpl<RegisterMaskPair> & RegUnits,RegisterMaskPair Pair)381 static void addRegLanes(SmallVectorImpl<RegisterMaskPair> &RegUnits,
382 RegisterMaskPair Pair) {
383 Register RegUnit = Pair.RegUnit;
384 assert(Pair.LaneMask.any());
385 auto I = llvm::find_if(RegUnits, [RegUnit](const RegisterMaskPair Other) {
386 return Other.RegUnit == RegUnit;
387 });
388 if (I == RegUnits.end()) {
389 RegUnits.push_back(Pair);
390 } else {
391 I->LaneMask |= Pair.LaneMask;
392 }
393 }
394
setRegZero(SmallVectorImpl<RegisterMaskPair> & RegUnits,Register RegUnit)395 static void setRegZero(SmallVectorImpl<RegisterMaskPair> &RegUnits,
396 Register RegUnit) {
397 auto I = llvm::find_if(RegUnits, [RegUnit](const RegisterMaskPair Other) {
398 return Other.RegUnit == RegUnit;
399 });
400 if (I == RegUnits.end()) {
401 RegUnits.push_back(RegisterMaskPair(RegUnit, LaneBitmask::getNone()));
402 } else {
403 I->LaneMask = LaneBitmask::getNone();
404 }
405 }
406
removeRegLanes(SmallVectorImpl<RegisterMaskPair> & RegUnits,RegisterMaskPair Pair)407 static void removeRegLanes(SmallVectorImpl<RegisterMaskPair> &RegUnits,
408 RegisterMaskPair Pair) {
409 Register RegUnit = Pair.RegUnit;
410 assert(Pair.LaneMask.any());
411 auto I = llvm::find_if(RegUnits, [RegUnit](const RegisterMaskPair Other) {
412 return Other.RegUnit == RegUnit;
413 });
414 if (I != RegUnits.end()) {
415 I->LaneMask &= ~Pair.LaneMask;
416 if (I->LaneMask.none())
417 RegUnits.erase(I);
418 }
419 }
420
421 static LaneBitmask
getLanesWithProperty(const LiveIntervals & LIS,const MachineRegisterInfo & MRI,bool TrackLaneMasks,Register RegUnit,SlotIndex Pos,LaneBitmask SafeDefault,bool (* Property)(const LiveRange & LR,SlotIndex Pos))422 getLanesWithProperty(const LiveIntervals &LIS, const MachineRegisterInfo &MRI,
423 bool TrackLaneMasks, Register RegUnit, SlotIndex Pos,
424 LaneBitmask SafeDefault,
425 bool (*Property)(const LiveRange &LR, SlotIndex Pos)) {
426 if (RegUnit.isVirtual()) {
427 const LiveInterval &LI = LIS.getInterval(RegUnit);
428 LaneBitmask Result;
429 if (TrackLaneMasks && LI.hasSubRanges()) {
430 for (const LiveInterval::SubRange &SR : LI.subranges()) {
431 if (Property(SR, Pos))
432 Result |= SR.LaneMask;
433 }
434 } else if (Property(LI, Pos)) {
435 Result = TrackLaneMasks ? MRI.getMaxLaneMaskForVReg(RegUnit)
436 : LaneBitmask::getAll();
437 }
438
439 return Result;
440 } else {
441 const LiveRange *LR = LIS.getCachedRegUnit(RegUnit);
442 // Be prepared for missing liveranges: We usually do not compute liveranges
443 // for physical registers on targets with many registers (GPUs).
444 if (LR == nullptr)
445 return SafeDefault;
446 return Property(*LR, Pos) ? LaneBitmask::getAll() : LaneBitmask::getNone();
447 }
448 }
449
getLiveLanesAt(const LiveIntervals & LIS,const MachineRegisterInfo & MRI,bool TrackLaneMasks,Register RegUnit,SlotIndex Pos)450 static LaneBitmask getLiveLanesAt(const LiveIntervals &LIS,
451 const MachineRegisterInfo &MRI,
452 bool TrackLaneMasks, Register RegUnit,
453 SlotIndex Pos) {
454 return getLanesWithProperty(LIS, MRI, TrackLaneMasks, RegUnit, Pos,
455 LaneBitmask::getAll(),
456 [](const LiveRange &LR, SlotIndex Pos) {
457 return LR.liveAt(Pos);
458 });
459 }
460
461 namespace {
462
463 /// Collect this instruction's unique uses and defs into SmallVectors for
464 /// processing defs and uses in order.
465 ///
466 /// FIXME: always ignore tied opers
467 class RegisterOperandsCollector {
468 friend class llvm::RegisterOperands;
469
470 RegisterOperands &RegOpers;
471 const TargetRegisterInfo &TRI;
472 const MachineRegisterInfo &MRI;
473 bool IgnoreDead;
474
RegisterOperandsCollector(RegisterOperands & RegOpers,const TargetRegisterInfo & TRI,const MachineRegisterInfo & MRI,bool IgnoreDead)475 RegisterOperandsCollector(RegisterOperands &RegOpers,
476 const TargetRegisterInfo &TRI,
477 const MachineRegisterInfo &MRI, bool IgnoreDead)
478 : RegOpers(RegOpers), TRI(TRI), MRI(MRI), IgnoreDead(IgnoreDead) {}
479
collectInstr(const MachineInstr & MI) const480 void collectInstr(const MachineInstr &MI) const {
481 for (ConstMIBundleOperands OperI(MI); OperI.isValid(); ++OperI)
482 collectOperand(*OperI);
483
484 // Remove redundant physreg dead defs.
485 for (const RegisterMaskPair &P : RegOpers.Defs)
486 removeRegLanes(RegOpers.DeadDefs, P);
487 }
488
collectInstrLanes(const MachineInstr & MI) const489 void collectInstrLanes(const MachineInstr &MI) const {
490 for (ConstMIBundleOperands OperI(MI); OperI.isValid(); ++OperI)
491 collectOperandLanes(*OperI);
492
493 // Remove redundant physreg dead defs.
494 for (const RegisterMaskPair &P : RegOpers.Defs)
495 removeRegLanes(RegOpers.DeadDefs, P);
496 }
497
498 /// Push this operand's register onto the correct vectors.
collectOperand(const MachineOperand & MO) const499 void collectOperand(const MachineOperand &MO) const {
500 if (!MO.isReg() || !MO.getReg())
501 return;
502 Register Reg = MO.getReg();
503 if (MO.isUse()) {
504 if (!MO.isUndef() && !MO.isInternalRead())
505 pushReg(Reg, RegOpers.Uses);
506 } else {
507 assert(MO.isDef());
508 // Subregister definitions may imply a register read.
509 if (MO.readsReg())
510 pushReg(Reg, RegOpers.Uses);
511
512 if (MO.isDead()) {
513 if (!IgnoreDead)
514 pushReg(Reg, RegOpers.DeadDefs);
515 } else
516 pushReg(Reg, RegOpers.Defs);
517 }
518 }
519
pushReg(Register Reg,SmallVectorImpl<RegisterMaskPair> & RegUnits) const520 void pushReg(Register Reg,
521 SmallVectorImpl<RegisterMaskPair> &RegUnits) const {
522 if (Reg.isVirtual()) {
523 addRegLanes(RegUnits, RegisterMaskPair(Reg, LaneBitmask::getAll()));
524 } else if (MRI.isAllocatable(Reg)) {
525 for (MCRegUnitIterator Units(Reg.asMCReg(), &TRI); Units.isValid();
526 ++Units)
527 addRegLanes(RegUnits, RegisterMaskPair(*Units, LaneBitmask::getAll()));
528 }
529 }
530
collectOperandLanes(const MachineOperand & MO) const531 void collectOperandLanes(const MachineOperand &MO) const {
532 if (!MO.isReg() || !MO.getReg())
533 return;
534 Register Reg = MO.getReg();
535 unsigned SubRegIdx = MO.getSubReg();
536 if (MO.isUse()) {
537 if (!MO.isUndef() && !MO.isInternalRead())
538 pushRegLanes(Reg, SubRegIdx, RegOpers.Uses);
539 } else {
540 assert(MO.isDef());
541 // Treat read-undef subreg defs as definitions of the whole register.
542 if (MO.isUndef())
543 SubRegIdx = 0;
544
545 if (MO.isDead()) {
546 if (!IgnoreDead)
547 pushRegLanes(Reg, SubRegIdx, RegOpers.DeadDefs);
548 } else
549 pushRegLanes(Reg, SubRegIdx, RegOpers.Defs);
550 }
551 }
552
pushRegLanes(Register Reg,unsigned SubRegIdx,SmallVectorImpl<RegisterMaskPair> & RegUnits) const553 void pushRegLanes(Register Reg, unsigned SubRegIdx,
554 SmallVectorImpl<RegisterMaskPair> &RegUnits) const {
555 if (Reg.isVirtual()) {
556 LaneBitmask LaneMask = SubRegIdx != 0
557 ? TRI.getSubRegIndexLaneMask(SubRegIdx)
558 : MRI.getMaxLaneMaskForVReg(Reg);
559 addRegLanes(RegUnits, RegisterMaskPair(Reg, LaneMask));
560 } else if (MRI.isAllocatable(Reg)) {
561 for (MCRegUnitIterator Units(Reg.asMCReg(), &TRI); Units.isValid();
562 ++Units)
563 addRegLanes(RegUnits, RegisterMaskPair(*Units, LaneBitmask::getAll()));
564 }
565 }
566 };
567
568 } // end anonymous namespace
569
collect(const MachineInstr & MI,const TargetRegisterInfo & TRI,const MachineRegisterInfo & MRI,bool TrackLaneMasks,bool IgnoreDead)570 void RegisterOperands::collect(const MachineInstr &MI,
571 const TargetRegisterInfo &TRI,
572 const MachineRegisterInfo &MRI,
573 bool TrackLaneMasks, bool IgnoreDead) {
574 RegisterOperandsCollector Collector(*this, TRI, MRI, IgnoreDead);
575 if (TrackLaneMasks)
576 Collector.collectInstrLanes(MI);
577 else
578 Collector.collectInstr(MI);
579 }
580
detectDeadDefs(const MachineInstr & MI,const LiveIntervals & LIS)581 void RegisterOperands::detectDeadDefs(const MachineInstr &MI,
582 const LiveIntervals &LIS) {
583 SlotIndex SlotIdx = LIS.getInstructionIndex(MI);
584 for (auto RI = Defs.begin(); RI != Defs.end(); /*empty*/) {
585 Register Reg = RI->RegUnit;
586 const LiveRange *LR = getLiveRange(LIS, Reg);
587 if (LR != nullptr) {
588 LiveQueryResult LRQ = LR->Query(SlotIdx);
589 if (LRQ.isDeadDef()) {
590 // LiveIntervals knows this is a dead even though it's MachineOperand is
591 // not flagged as such.
592 DeadDefs.push_back(*RI);
593 RI = Defs.erase(RI);
594 continue;
595 }
596 }
597 ++RI;
598 }
599 }
600
adjustLaneLiveness(const LiveIntervals & LIS,const MachineRegisterInfo & MRI,SlotIndex Pos,MachineInstr * AddFlagsMI)601 void RegisterOperands::adjustLaneLiveness(const LiveIntervals &LIS,
602 const MachineRegisterInfo &MRI,
603 SlotIndex Pos,
604 MachineInstr *AddFlagsMI) {
605 for (auto I = Defs.begin(); I != Defs.end(); ) {
606 LaneBitmask LiveAfter = getLiveLanesAt(LIS, MRI, true, I->RegUnit,
607 Pos.getDeadSlot());
608 // If the def is all that is live after the instruction, then in case
609 // of a subregister def we need a read-undef flag.
610 Register RegUnit = I->RegUnit;
611 if (Register::isVirtualRegister(RegUnit) &&
612 AddFlagsMI != nullptr && (LiveAfter & ~I->LaneMask).none())
613 AddFlagsMI->setRegisterDefReadUndef(RegUnit);
614
615 LaneBitmask ActualDef = I->LaneMask & LiveAfter;
616 if (ActualDef.none()) {
617 I = Defs.erase(I);
618 } else {
619 I->LaneMask = ActualDef;
620 ++I;
621 }
622 }
623 for (auto I = Uses.begin(); I != Uses.end(); ) {
624 LaneBitmask LiveBefore = getLiveLanesAt(LIS, MRI, true, I->RegUnit,
625 Pos.getBaseIndex());
626 LaneBitmask LaneMask = I->LaneMask & LiveBefore;
627 if (LaneMask.none()) {
628 I = Uses.erase(I);
629 } else {
630 I->LaneMask = LaneMask;
631 ++I;
632 }
633 }
634 if (AddFlagsMI != nullptr) {
635 for (const RegisterMaskPair &P : DeadDefs) {
636 Register RegUnit = P.RegUnit;
637 if (!Register::isVirtualRegister(RegUnit))
638 continue;
639 LaneBitmask LiveAfter = getLiveLanesAt(LIS, MRI, true, RegUnit,
640 Pos.getDeadSlot());
641 if (LiveAfter.none())
642 AddFlagsMI->setRegisterDefReadUndef(RegUnit);
643 }
644 }
645 }
646
647 /// Initialize an array of N PressureDiffs.
init(unsigned N)648 void PressureDiffs::init(unsigned N) {
649 Size = N;
650 if (N <= Max) {
651 memset(PDiffArray, 0, N * sizeof(PressureDiff));
652 return;
653 }
654 Max = Size;
655 free(PDiffArray);
656 PDiffArray = static_cast<PressureDiff*>(safe_calloc(N, sizeof(PressureDiff)));
657 }
658
addInstruction(unsigned Idx,const RegisterOperands & RegOpers,const MachineRegisterInfo & MRI)659 void PressureDiffs::addInstruction(unsigned Idx,
660 const RegisterOperands &RegOpers,
661 const MachineRegisterInfo &MRI) {
662 PressureDiff &PDiff = (*this)[Idx];
663 assert(!PDiff.begin()->isValid() && "stale PDiff");
664 for (const RegisterMaskPair &P : RegOpers.Defs)
665 PDiff.addPressureChange(P.RegUnit, true, &MRI);
666
667 for (const RegisterMaskPair &P : RegOpers.Uses)
668 PDiff.addPressureChange(P.RegUnit, false, &MRI);
669 }
670
671 /// Add a change in pressure to the pressure diff of a given instruction.
addPressureChange(Register RegUnit,bool IsDec,const MachineRegisterInfo * MRI)672 void PressureDiff::addPressureChange(Register RegUnit, bool IsDec,
673 const MachineRegisterInfo *MRI) {
674 PSetIterator PSetI = MRI->getPressureSets(RegUnit);
675 int Weight = IsDec ? -PSetI.getWeight() : PSetI.getWeight();
676 for (; PSetI.isValid(); ++PSetI) {
677 // Find an existing entry in the pressure diff for this PSet.
678 PressureDiff::iterator I = nonconst_begin(), E = nonconst_end();
679 for (; I != E && I->isValid(); ++I) {
680 if (I->getPSet() >= *PSetI)
681 break;
682 }
683 // If all pressure sets are more constrained, skip the remaining PSets.
684 if (I == E)
685 break;
686 // Insert this PressureChange.
687 if (!I->isValid() || I->getPSet() != *PSetI) {
688 PressureChange PTmp = PressureChange(*PSetI);
689 for (PressureDiff::iterator J = I; J != E && PTmp.isValid(); ++J)
690 std::swap(*J, PTmp);
691 }
692 // Update the units for this pressure set.
693 unsigned NewUnitInc = I->getUnitInc() + Weight;
694 if (NewUnitInc != 0) {
695 I->setUnitInc(NewUnitInc);
696 } else {
697 // Remove entry
698 PressureDiff::iterator J;
699 for (J = std::next(I); J != E && J->isValid(); ++J, ++I)
700 *I = *J;
701 *I = PressureChange();
702 }
703 }
704 }
705
706 /// Force liveness of registers.
addLiveRegs(ArrayRef<RegisterMaskPair> Regs)707 void RegPressureTracker::addLiveRegs(ArrayRef<RegisterMaskPair> Regs) {
708 for (const RegisterMaskPair &P : Regs) {
709 LaneBitmask PrevMask = LiveRegs.insert(P);
710 LaneBitmask NewMask = PrevMask | P.LaneMask;
711 increaseRegPressure(P.RegUnit, PrevMask, NewMask);
712 }
713 }
714
discoverLiveInOrOut(RegisterMaskPair Pair,SmallVectorImpl<RegisterMaskPair> & LiveInOrOut)715 void RegPressureTracker::discoverLiveInOrOut(RegisterMaskPair Pair,
716 SmallVectorImpl<RegisterMaskPair> &LiveInOrOut) {
717 assert(Pair.LaneMask.any());
718
719 Register RegUnit = Pair.RegUnit;
720 auto I = llvm::find_if(LiveInOrOut, [RegUnit](const RegisterMaskPair &Other) {
721 return Other.RegUnit == RegUnit;
722 });
723 LaneBitmask PrevMask;
724 LaneBitmask NewMask;
725 if (I == LiveInOrOut.end()) {
726 PrevMask = LaneBitmask::getNone();
727 NewMask = Pair.LaneMask;
728 LiveInOrOut.push_back(Pair);
729 } else {
730 PrevMask = I->LaneMask;
731 NewMask = PrevMask | Pair.LaneMask;
732 I->LaneMask = NewMask;
733 }
734 increaseSetPressure(P.MaxSetPressure, *MRI, RegUnit, PrevMask, NewMask);
735 }
736
discoverLiveIn(RegisterMaskPair Pair)737 void RegPressureTracker::discoverLiveIn(RegisterMaskPair Pair) {
738 discoverLiveInOrOut(Pair, P.LiveInRegs);
739 }
740
discoverLiveOut(RegisterMaskPair Pair)741 void RegPressureTracker::discoverLiveOut(RegisterMaskPair Pair) {
742 discoverLiveInOrOut(Pair, P.LiveOutRegs);
743 }
744
bumpDeadDefs(ArrayRef<RegisterMaskPair> DeadDefs)745 void RegPressureTracker::bumpDeadDefs(ArrayRef<RegisterMaskPair> DeadDefs) {
746 for (const RegisterMaskPair &P : DeadDefs) {
747 Register Reg = P.RegUnit;
748 LaneBitmask LiveMask = LiveRegs.contains(Reg);
749 LaneBitmask BumpedMask = LiveMask | P.LaneMask;
750 increaseRegPressure(Reg, LiveMask, BumpedMask);
751 }
752 for (const RegisterMaskPair &P : DeadDefs) {
753 Register Reg = P.RegUnit;
754 LaneBitmask LiveMask = LiveRegs.contains(Reg);
755 LaneBitmask BumpedMask = LiveMask | P.LaneMask;
756 decreaseRegPressure(Reg, BumpedMask, LiveMask);
757 }
758 }
759
760 /// Recede across the previous instruction. If LiveUses is provided, record any
761 /// RegUnits that are made live by the current instruction's uses. This includes
762 /// registers that are both defined and used by the instruction. If a pressure
763 /// difference pointer is provided record the changes is pressure caused by this
764 /// instruction independent of liveness.
recede(const RegisterOperands & RegOpers,SmallVectorImpl<RegisterMaskPair> * LiveUses)765 void RegPressureTracker::recede(const RegisterOperands &RegOpers,
766 SmallVectorImpl<RegisterMaskPair> *LiveUses) {
767 assert(!CurrPos->isDebugOrPseudoInstr());
768
769 // Boost pressure for all dead defs together.
770 bumpDeadDefs(RegOpers.DeadDefs);
771
772 // Kill liveness at live defs.
773 // TODO: consider earlyclobbers?
774 for (const RegisterMaskPair &Def : RegOpers.Defs) {
775 Register Reg = Def.RegUnit;
776
777 LaneBitmask PreviousMask = LiveRegs.erase(Def);
778 LaneBitmask NewMask = PreviousMask & ~Def.LaneMask;
779
780 LaneBitmask LiveOut = Def.LaneMask & ~PreviousMask;
781 if (LiveOut.any()) {
782 discoverLiveOut(RegisterMaskPair(Reg, LiveOut));
783 // Retroactively model effects on pressure of the live out lanes.
784 increaseSetPressure(CurrSetPressure, *MRI, Reg, LaneBitmask::getNone(),
785 LiveOut);
786 PreviousMask = LiveOut;
787 }
788
789 if (NewMask.none()) {
790 // Add a 0 entry to LiveUses as a marker that the complete vreg has become
791 // dead.
792 if (TrackLaneMasks && LiveUses != nullptr)
793 setRegZero(*LiveUses, Reg);
794 }
795
796 decreaseRegPressure(Reg, PreviousMask, NewMask);
797 }
798
799 SlotIndex SlotIdx;
800 if (RequireIntervals)
801 SlotIdx = LIS->getInstructionIndex(*CurrPos).getRegSlot();
802
803 // Generate liveness for uses.
804 for (const RegisterMaskPair &Use : RegOpers.Uses) {
805 Register Reg = Use.RegUnit;
806 assert(Use.LaneMask.any());
807 LaneBitmask PreviousMask = LiveRegs.insert(Use);
808 LaneBitmask NewMask = PreviousMask | Use.LaneMask;
809 if (NewMask == PreviousMask)
810 continue;
811
812 // Did the register just become live?
813 if (PreviousMask.none()) {
814 if (LiveUses != nullptr) {
815 if (!TrackLaneMasks) {
816 addRegLanes(*LiveUses, RegisterMaskPair(Reg, NewMask));
817 } else {
818 auto I =
819 llvm::find_if(*LiveUses, [Reg](const RegisterMaskPair Other) {
820 return Other.RegUnit == Reg;
821 });
822 bool IsRedef = I != LiveUses->end();
823 if (IsRedef) {
824 // ignore re-defs here...
825 assert(I->LaneMask.none());
826 removeRegLanes(*LiveUses, RegisterMaskPair(Reg, NewMask));
827 } else {
828 addRegLanes(*LiveUses, RegisterMaskPair(Reg, NewMask));
829 }
830 }
831 }
832
833 // Discover live outs if this may be the first occurance of this register.
834 if (RequireIntervals) {
835 LaneBitmask LiveOut = getLiveThroughAt(Reg, SlotIdx);
836 if (LiveOut.any())
837 discoverLiveOut(RegisterMaskPair(Reg, LiveOut));
838 }
839 }
840
841 increaseRegPressure(Reg, PreviousMask, NewMask);
842 }
843 if (TrackUntiedDefs) {
844 for (const RegisterMaskPair &Def : RegOpers.Defs) {
845 Register RegUnit = Def.RegUnit;
846 if (Register::isVirtualRegister(RegUnit) &&
847 (LiveRegs.contains(RegUnit) & Def.LaneMask).none())
848 UntiedDefs.insert(RegUnit);
849 }
850 }
851 }
852
recedeSkipDebugValues()853 void RegPressureTracker::recedeSkipDebugValues() {
854 assert(CurrPos != MBB->begin());
855 if (!isBottomClosed())
856 closeBottom();
857
858 // Open the top of the region using block iterators.
859 if (!RequireIntervals && isTopClosed())
860 static_cast<RegionPressure&>(P).openTop(CurrPos);
861
862 // Find the previous instruction.
863 CurrPos = prev_nodbg(CurrPos, MBB->begin());
864
865 SlotIndex SlotIdx;
866 if (RequireIntervals && !CurrPos->isDebugOrPseudoInstr())
867 SlotIdx = LIS->getInstructionIndex(*CurrPos).getRegSlot();
868
869 // Open the top of the region using slot indexes.
870 if (RequireIntervals && isTopClosed())
871 static_cast<IntervalPressure&>(P).openTop(SlotIdx);
872 }
873
recede(SmallVectorImpl<RegisterMaskPair> * LiveUses)874 void RegPressureTracker::recede(SmallVectorImpl<RegisterMaskPair> *LiveUses) {
875 recedeSkipDebugValues();
876 if (CurrPos->isDebugInstr() || CurrPos->isPseudoProbe()) {
877 // It's possible to only have debug_value and pseudo probe instructions and
878 // hit the start of the block.
879 assert(CurrPos == MBB->begin());
880 return;
881 }
882
883 const MachineInstr &MI = *CurrPos;
884 RegisterOperands RegOpers;
885 RegOpers.collect(MI, *TRI, *MRI, TrackLaneMasks, false);
886 if (TrackLaneMasks) {
887 SlotIndex SlotIdx = LIS->getInstructionIndex(*CurrPos).getRegSlot();
888 RegOpers.adjustLaneLiveness(*LIS, *MRI, SlotIdx);
889 } else if (RequireIntervals) {
890 RegOpers.detectDeadDefs(MI, *LIS);
891 }
892
893 recede(RegOpers, LiveUses);
894 }
895
896 /// Advance across the current instruction.
advance(const RegisterOperands & RegOpers)897 void RegPressureTracker::advance(const RegisterOperands &RegOpers) {
898 assert(!TrackUntiedDefs && "unsupported mode");
899 assert(CurrPos != MBB->end());
900 if (!isTopClosed())
901 closeTop();
902
903 SlotIndex SlotIdx;
904 if (RequireIntervals)
905 SlotIdx = getCurrSlot();
906
907 // Open the bottom of the region using slot indexes.
908 if (isBottomClosed()) {
909 if (RequireIntervals)
910 static_cast<IntervalPressure&>(P).openBottom(SlotIdx);
911 else
912 static_cast<RegionPressure&>(P).openBottom(CurrPos);
913 }
914
915 for (const RegisterMaskPair &Use : RegOpers.Uses) {
916 Register Reg = Use.RegUnit;
917 LaneBitmask LiveMask = LiveRegs.contains(Reg);
918 LaneBitmask LiveIn = Use.LaneMask & ~LiveMask;
919 if (LiveIn.any()) {
920 discoverLiveIn(RegisterMaskPair(Reg, LiveIn));
921 increaseRegPressure(Reg, LiveMask, LiveMask | LiveIn);
922 LiveRegs.insert(RegisterMaskPair(Reg, LiveIn));
923 }
924 // Kill liveness at last uses.
925 if (RequireIntervals) {
926 LaneBitmask LastUseMask = getLastUsedLanes(Reg, SlotIdx);
927 if (LastUseMask.any()) {
928 LiveRegs.erase(RegisterMaskPair(Reg, LastUseMask));
929 decreaseRegPressure(Reg, LiveMask, LiveMask & ~LastUseMask);
930 }
931 }
932 }
933
934 // Generate liveness for defs.
935 for (const RegisterMaskPair &Def : RegOpers.Defs) {
936 LaneBitmask PreviousMask = LiveRegs.insert(Def);
937 LaneBitmask NewMask = PreviousMask | Def.LaneMask;
938 increaseRegPressure(Def.RegUnit, PreviousMask, NewMask);
939 }
940
941 // Boost pressure for all dead defs together.
942 bumpDeadDefs(RegOpers.DeadDefs);
943
944 // Find the next instruction.
945 CurrPos = next_nodbg(CurrPos, MBB->end());
946 }
947
advance()948 void RegPressureTracker::advance() {
949 const MachineInstr &MI = *CurrPos;
950 RegisterOperands RegOpers;
951 RegOpers.collect(MI, *TRI, *MRI, TrackLaneMasks, false);
952 if (TrackLaneMasks) {
953 SlotIndex SlotIdx = getCurrSlot();
954 RegOpers.adjustLaneLiveness(*LIS, *MRI, SlotIdx);
955 }
956 advance(RegOpers);
957 }
958
959 /// Find the max change in excess pressure across all sets.
computeExcessPressureDelta(ArrayRef<unsigned> OldPressureVec,ArrayRef<unsigned> NewPressureVec,RegPressureDelta & Delta,const RegisterClassInfo * RCI,ArrayRef<unsigned> LiveThruPressureVec)960 static void computeExcessPressureDelta(ArrayRef<unsigned> OldPressureVec,
961 ArrayRef<unsigned> NewPressureVec,
962 RegPressureDelta &Delta,
963 const RegisterClassInfo *RCI,
964 ArrayRef<unsigned> LiveThruPressureVec) {
965 Delta.Excess = PressureChange();
966 for (unsigned i = 0, e = OldPressureVec.size(); i < e; ++i) {
967 unsigned POld = OldPressureVec[i];
968 unsigned PNew = NewPressureVec[i];
969 int PDiff = (int)PNew - (int)POld;
970 if (!PDiff) // No change in this set in the common case.
971 continue;
972 // Only consider change beyond the limit.
973 unsigned Limit = RCI->getRegPressureSetLimit(i);
974 if (!LiveThruPressureVec.empty())
975 Limit += LiveThruPressureVec[i];
976
977 if (Limit > POld) {
978 if (Limit > PNew)
979 PDiff = 0; // Under the limit
980 else
981 PDiff = PNew - Limit; // Just exceeded limit.
982 } else if (Limit > PNew)
983 PDiff = Limit - POld; // Just obeyed limit.
984
985 if (PDiff) {
986 Delta.Excess = PressureChange(i);
987 Delta.Excess.setUnitInc(PDiff);
988 break;
989 }
990 }
991 }
992
993 /// Find the max change in max pressure that either surpasses a critical PSet
994 /// limit or exceeds the current MaxPressureLimit.
995 ///
996 /// FIXME: comparing each element of the old and new MaxPressure vectors here is
997 /// silly. It's done now to demonstrate the concept but will go away with a
998 /// RegPressureTracker API change to work with pressure differences.
computeMaxPressureDelta(ArrayRef<unsigned> OldMaxPressureVec,ArrayRef<unsigned> NewMaxPressureVec,ArrayRef<PressureChange> CriticalPSets,ArrayRef<unsigned> MaxPressureLimit,RegPressureDelta & Delta)999 static void computeMaxPressureDelta(ArrayRef<unsigned> OldMaxPressureVec,
1000 ArrayRef<unsigned> NewMaxPressureVec,
1001 ArrayRef<PressureChange> CriticalPSets,
1002 ArrayRef<unsigned> MaxPressureLimit,
1003 RegPressureDelta &Delta) {
1004 Delta.CriticalMax = PressureChange();
1005 Delta.CurrentMax = PressureChange();
1006
1007 unsigned CritIdx = 0, CritEnd = CriticalPSets.size();
1008 for (unsigned i = 0, e = OldMaxPressureVec.size(); i < e; ++i) {
1009 unsigned POld = OldMaxPressureVec[i];
1010 unsigned PNew = NewMaxPressureVec[i];
1011 if (PNew == POld) // No change in this set in the common case.
1012 continue;
1013
1014 if (!Delta.CriticalMax.isValid()) {
1015 while (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() < i)
1016 ++CritIdx;
1017
1018 if (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() == i) {
1019 int PDiff = (int)PNew - (int)CriticalPSets[CritIdx].getUnitInc();
1020 if (PDiff > 0) {
1021 Delta.CriticalMax = PressureChange(i);
1022 Delta.CriticalMax.setUnitInc(PDiff);
1023 }
1024 }
1025 }
1026 // Find the first increase above MaxPressureLimit.
1027 // (Ignores negative MDiff).
1028 if (!Delta.CurrentMax.isValid() && PNew > MaxPressureLimit[i]) {
1029 Delta.CurrentMax = PressureChange(i);
1030 Delta.CurrentMax.setUnitInc(PNew - POld);
1031 if (CritIdx == CritEnd || Delta.CriticalMax.isValid())
1032 break;
1033 }
1034 }
1035 }
1036
1037 /// Record the upward impact of a single instruction on current register
1038 /// pressure. Unlike the advance/recede pressure tracking interface, this does
1039 /// not discover live in/outs.
1040 ///
1041 /// This is intended for speculative queries. It leaves pressure inconsistent
1042 /// with the current position, so must be restored by the caller.
bumpUpwardPressure(const MachineInstr * MI)1043 void RegPressureTracker::bumpUpwardPressure(const MachineInstr *MI) {
1044 assert(!MI->isDebugOrPseudoInstr() && "Expect a nondebug instruction.");
1045
1046 SlotIndex SlotIdx;
1047 if (RequireIntervals)
1048 SlotIdx = LIS->getInstructionIndex(*MI).getRegSlot();
1049
1050 // Account for register pressure similar to RegPressureTracker::recede().
1051 RegisterOperands RegOpers;
1052 RegOpers.collect(*MI, *TRI, *MRI, TrackLaneMasks, /*IgnoreDead=*/true);
1053 assert(RegOpers.DeadDefs.size() == 0);
1054 if (TrackLaneMasks)
1055 RegOpers.adjustLaneLiveness(*LIS, *MRI, SlotIdx);
1056 else if (RequireIntervals)
1057 RegOpers.detectDeadDefs(*MI, *LIS);
1058
1059 // Boost max pressure for all dead defs together.
1060 // Since CurrSetPressure and MaxSetPressure
1061 bumpDeadDefs(RegOpers.DeadDefs);
1062
1063 // Kill liveness at live defs.
1064 for (const RegisterMaskPair &P : RegOpers.Defs) {
1065 Register Reg = P.RegUnit;
1066 LaneBitmask LiveLanes = LiveRegs.contains(Reg);
1067 LaneBitmask UseLanes = getRegLanes(RegOpers.Uses, Reg);
1068 LaneBitmask DefLanes = P.LaneMask;
1069 LaneBitmask LiveAfter = (LiveLanes & ~DefLanes) | UseLanes;
1070 decreaseRegPressure(Reg, LiveLanes, LiveAfter);
1071 }
1072 // Generate liveness for uses.
1073 for (const RegisterMaskPair &P : RegOpers.Uses) {
1074 Register Reg = P.RegUnit;
1075 LaneBitmask LiveLanes = LiveRegs.contains(Reg);
1076 LaneBitmask LiveAfter = LiveLanes | P.LaneMask;
1077 increaseRegPressure(Reg, LiveLanes, LiveAfter);
1078 }
1079 }
1080
1081 /// Consider the pressure increase caused by traversing this instruction
1082 /// bottom-up. Find the pressure set with the most change beyond its pressure
1083 /// limit based on the tracker's current pressure, and return the change in
1084 /// number of register units of that pressure set introduced by this
1085 /// instruction.
1086 ///
1087 /// This assumes that the current LiveOut set is sufficient.
1088 ///
1089 /// This is expensive for an on-the-fly query because it calls
1090 /// bumpUpwardPressure to recompute the pressure sets based on current
1091 /// liveness. This mainly exists to verify correctness, e.g. with
1092 /// -verify-misched. getUpwardPressureDelta is the fast version of this query
1093 /// that uses the per-SUnit cache of the PressureDiff.
1094 void RegPressureTracker::
getMaxUpwardPressureDelta(const MachineInstr * MI,PressureDiff * PDiff,RegPressureDelta & Delta,ArrayRef<PressureChange> CriticalPSets,ArrayRef<unsigned> MaxPressureLimit)1095 getMaxUpwardPressureDelta(const MachineInstr *MI, PressureDiff *PDiff,
1096 RegPressureDelta &Delta,
1097 ArrayRef<PressureChange> CriticalPSets,
1098 ArrayRef<unsigned> MaxPressureLimit) {
1099 // Snapshot Pressure.
1100 // FIXME: The snapshot heap space should persist. But I'm planning to
1101 // summarize the pressure effect so we don't need to snapshot at all.
1102 std::vector<unsigned> SavedPressure = CurrSetPressure;
1103 std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
1104
1105 bumpUpwardPressure(MI);
1106
1107 computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, RCI,
1108 LiveThruPressure);
1109 computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets,
1110 MaxPressureLimit, Delta);
1111 assert(Delta.CriticalMax.getUnitInc() >= 0 &&
1112 Delta.CurrentMax.getUnitInc() >= 0 && "cannot decrease max pressure");
1113
1114 // Restore the tracker's state.
1115 P.MaxSetPressure.swap(SavedMaxPressure);
1116 CurrSetPressure.swap(SavedPressure);
1117
1118 #ifndef NDEBUG
1119 if (!PDiff)
1120 return;
1121
1122 // Check if the alternate algorithm yields the same result.
1123 RegPressureDelta Delta2;
1124 getUpwardPressureDelta(MI, *PDiff, Delta2, CriticalPSets, MaxPressureLimit);
1125 if (Delta != Delta2) {
1126 dbgs() << "PDiff: ";
1127 PDiff->dump(*TRI);
1128 dbgs() << "DELTA: " << *MI;
1129 if (Delta.Excess.isValid())
1130 dbgs() << "Excess1 " << TRI->getRegPressureSetName(Delta.Excess.getPSet())
1131 << " " << Delta.Excess.getUnitInc() << "\n";
1132 if (Delta.CriticalMax.isValid())
1133 dbgs() << "Critic1 " << TRI->getRegPressureSetName(Delta.CriticalMax.getPSet())
1134 << " " << Delta.CriticalMax.getUnitInc() << "\n";
1135 if (Delta.CurrentMax.isValid())
1136 dbgs() << "CurrMx1 " << TRI->getRegPressureSetName(Delta.CurrentMax.getPSet())
1137 << " " << Delta.CurrentMax.getUnitInc() << "\n";
1138 if (Delta2.Excess.isValid())
1139 dbgs() << "Excess2 " << TRI->getRegPressureSetName(Delta2.Excess.getPSet())
1140 << " " << Delta2.Excess.getUnitInc() << "\n";
1141 if (Delta2.CriticalMax.isValid())
1142 dbgs() << "Critic2 " << TRI->getRegPressureSetName(Delta2.CriticalMax.getPSet())
1143 << " " << Delta2.CriticalMax.getUnitInc() << "\n";
1144 if (Delta2.CurrentMax.isValid())
1145 dbgs() << "CurrMx2 " << TRI->getRegPressureSetName(Delta2.CurrentMax.getPSet())
1146 << " " << Delta2.CurrentMax.getUnitInc() << "\n";
1147 llvm_unreachable("RegP Delta Mismatch");
1148 }
1149 #endif
1150 }
1151
1152 /// This is the fast version of querying register pressure that does not
1153 /// directly depend on current liveness.
1154 ///
1155 /// @param Delta captures information needed for heuristics.
1156 ///
1157 /// @param CriticalPSets Are the pressure sets that are known to exceed some
1158 /// limit within the region, not necessarily at the current position.
1159 ///
1160 /// @param MaxPressureLimit Is the max pressure within the region, not
1161 /// necessarily at the current position.
1162 void RegPressureTracker::
getUpwardPressureDelta(const MachineInstr * MI,PressureDiff & PDiff,RegPressureDelta & Delta,ArrayRef<PressureChange> CriticalPSets,ArrayRef<unsigned> MaxPressureLimit) const1163 getUpwardPressureDelta(const MachineInstr *MI, /*const*/ PressureDiff &PDiff,
1164 RegPressureDelta &Delta,
1165 ArrayRef<PressureChange> CriticalPSets,
1166 ArrayRef<unsigned> MaxPressureLimit) const {
1167 unsigned CritIdx = 0, CritEnd = CriticalPSets.size();
1168 for (PressureDiff::const_iterator
1169 PDiffI = PDiff.begin(), PDiffE = PDiff.end();
1170 PDiffI != PDiffE && PDiffI->isValid(); ++PDiffI) {
1171
1172 unsigned PSetID = PDiffI->getPSet();
1173 unsigned Limit = RCI->getRegPressureSetLimit(PSetID);
1174 if (!LiveThruPressure.empty())
1175 Limit += LiveThruPressure[PSetID];
1176
1177 unsigned POld = CurrSetPressure[PSetID];
1178 unsigned MOld = P.MaxSetPressure[PSetID];
1179 unsigned MNew = MOld;
1180 // Ignore DeadDefs here because they aren't captured by PressureChange.
1181 unsigned PNew = POld + PDiffI->getUnitInc();
1182 assert((PDiffI->getUnitInc() >= 0) == (PNew >= POld)
1183 && "PSet overflow/underflow");
1184 if (PNew > MOld)
1185 MNew = PNew;
1186 // Check if current pressure has exceeded the limit.
1187 if (!Delta.Excess.isValid()) {
1188 unsigned ExcessInc = 0;
1189 if (PNew > Limit)
1190 ExcessInc = POld > Limit ? PNew - POld : PNew - Limit;
1191 else if (POld > Limit)
1192 ExcessInc = Limit - POld;
1193 if (ExcessInc) {
1194 Delta.Excess = PressureChange(PSetID);
1195 Delta.Excess.setUnitInc(ExcessInc);
1196 }
1197 }
1198 // Check if max pressure has exceeded a critical pressure set max.
1199 if (MNew == MOld)
1200 continue;
1201 if (!Delta.CriticalMax.isValid()) {
1202 while (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() < PSetID)
1203 ++CritIdx;
1204
1205 if (CritIdx != CritEnd && CriticalPSets[CritIdx].getPSet() == PSetID) {
1206 int CritInc = (int)MNew - (int)CriticalPSets[CritIdx].getUnitInc();
1207 if (CritInc > 0 && CritInc <= std::numeric_limits<int16_t>::max()) {
1208 Delta.CriticalMax = PressureChange(PSetID);
1209 Delta.CriticalMax.setUnitInc(CritInc);
1210 }
1211 }
1212 }
1213 // Check if max pressure has exceeded the current max.
1214 if (!Delta.CurrentMax.isValid() && MNew > MaxPressureLimit[PSetID]) {
1215 Delta.CurrentMax = PressureChange(PSetID);
1216 Delta.CurrentMax.setUnitInc(MNew - MOld);
1217 }
1218 }
1219 }
1220
1221 /// Helper to find a vreg use between two indices [PriorUseIdx, NextUseIdx).
1222 /// The query starts with a lane bitmask which gets lanes/bits removed for every
1223 /// use we find.
findUseBetween(unsigned Reg,LaneBitmask LastUseMask,SlotIndex PriorUseIdx,SlotIndex NextUseIdx,const MachineRegisterInfo & MRI,const LiveIntervals * LIS)1224 static LaneBitmask findUseBetween(unsigned Reg, LaneBitmask LastUseMask,
1225 SlotIndex PriorUseIdx, SlotIndex NextUseIdx,
1226 const MachineRegisterInfo &MRI,
1227 const LiveIntervals *LIS) {
1228 const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
1229 for (const MachineOperand &MO : MRI.use_nodbg_operands(Reg)) {
1230 if (MO.isUndef())
1231 continue;
1232 const MachineInstr *MI = MO.getParent();
1233 SlotIndex InstSlot = LIS->getInstructionIndex(*MI).getRegSlot();
1234 if (InstSlot >= PriorUseIdx && InstSlot < NextUseIdx) {
1235 unsigned SubRegIdx = MO.getSubReg();
1236 LaneBitmask UseMask = TRI.getSubRegIndexLaneMask(SubRegIdx);
1237 LastUseMask &= ~UseMask;
1238 if (LastUseMask.none())
1239 return LaneBitmask::getNone();
1240 }
1241 }
1242 return LastUseMask;
1243 }
1244
getLiveLanesAt(Register RegUnit,SlotIndex Pos) const1245 LaneBitmask RegPressureTracker::getLiveLanesAt(Register RegUnit,
1246 SlotIndex Pos) const {
1247 assert(RequireIntervals);
1248 return getLanesWithProperty(*LIS, *MRI, TrackLaneMasks, RegUnit, Pos,
1249 LaneBitmask::getAll(),
1250 [](const LiveRange &LR, SlotIndex Pos) {
1251 return LR.liveAt(Pos);
1252 });
1253 }
1254
getLastUsedLanes(Register RegUnit,SlotIndex Pos) const1255 LaneBitmask RegPressureTracker::getLastUsedLanes(Register RegUnit,
1256 SlotIndex Pos) const {
1257 assert(RequireIntervals);
1258 return getLanesWithProperty(*LIS, *MRI, TrackLaneMasks, RegUnit,
1259 Pos.getBaseIndex(), LaneBitmask::getNone(),
1260 [](const LiveRange &LR, SlotIndex Pos) {
1261 const LiveRange::Segment *S = LR.getSegmentContaining(Pos);
1262 return S != nullptr && S->end == Pos.getRegSlot();
1263 });
1264 }
1265
getLiveThroughAt(Register RegUnit,SlotIndex Pos) const1266 LaneBitmask RegPressureTracker::getLiveThroughAt(Register RegUnit,
1267 SlotIndex Pos) const {
1268 assert(RequireIntervals);
1269 return getLanesWithProperty(*LIS, *MRI, TrackLaneMasks, RegUnit, Pos,
1270 LaneBitmask::getNone(),
1271 [](const LiveRange &LR, SlotIndex Pos) {
1272 const LiveRange::Segment *S = LR.getSegmentContaining(Pos);
1273 return S != nullptr && S->start < Pos.getRegSlot(true) &&
1274 S->end != Pos.getDeadSlot();
1275 });
1276 }
1277
1278 /// Record the downward impact of a single instruction on current register
1279 /// pressure. Unlike the advance/recede pressure tracking interface, this does
1280 /// not discover live in/outs.
1281 ///
1282 /// This is intended for speculative queries. It leaves pressure inconsistent
1283 /// with the current position, so must be restored by the caller.
bumpDownwardPressure(const MachineInstr * MI)1284 void RegPressureTracker::bumpDownwardPressure(const MachineInstr *MI) {
1285 assert(!MI->isDebugOrPseudoInstr() && "Expect a nondebug instruction.");
1286
1287 SlotIndex SlotIdx;
1288 if (RequireIntervals)
1289 SlotIdx = LIS->getInstructionIndex(*MI).getRegSlot();
1290
1291 // Account for register pressure similar to RegPressureTracker::recede().
1292 RegisterOperands RegOpers;
1293 RegOpers.collect(*MI, *TRI, *MRI, TrackLaneMasks, false);
1294 if (TrackLaneMasks)
1295 RegOpers.adjustLaneLiveness(*LIS, *MRI, SlotIdx);
1296
1297 if (RequireIntervals) {
1298 for (const RegisterMaskPair &Use : RegOpers.Uses) {
1299 Register Reg = Use.RegUnit;
1300 LaneBitmask LastUseMask = getLastUsedLanes(Reg, SlotIdx);
1301 if (LastUseMask.none())
1302 continue;
1303 // The LastUseMask is queried from the liveness information of instruction
1304 // which may be further down the schedule. Some lanes may actually not be
1305 // last uses for the current position.
1306 // FIXME: allow the caller to pass in the list of vreg uses that remain
1307 // to be bottom-scheduled to avoid searching uses at each query.
1308 SlotIndex CurrIdx = getCurrSlot();
1309 LastUseMask
1310 = findUseBetween(Reg, LastUseMask, CurrIdx, SlotIdx, *MRI, LIS);
1311 if (LastUseMask.none())
1312 continue;
1313
1314 LaneBitmask LiveMask = LiveRegs.contains(Reg);
1315 LaneBitmask NewMask = LiveMask & ~LastUseMask;
1316 decreaseRegPressure(Reg, LiveMask, NewMask);
1317 }
1318 }
1319
1320 // Generate liveness for defs.
1321 for (const RegisterMaskPair &Def : RegOpers.Defs) {
1322 Register Reg = Def.RegUnit;
1323 LaneBitmask LiveMask = LiveRegs.contains(Reg);
1324 LaneBitmask NewMask = LiveMask | Def.LaneMask;
1325 increaseRegPressure(Reg, LiveMask, NewMask);
1326 }
1327
1328 // Boost pressure for all dead defs together.
1329 bumpDeadDefs(RegOpers.DeadDefs);
1330 }
1331
1332 /// Consider the pressure increase caused by traversing this instruction
1333 /// top-down. Find the register class with the most change in its pressure limit
1334 /// based on the tracker's current pressure, and return the number of excess
1335 /// register units of that pressure set introduced by this instruction.
1336 ///
1337 /// This assumes that the current LiveIn set is sufficient.
1338 ///
1339 /// This is expensive for an on-the-fly query because it calls
1340 /// bumpDownwardPressure to recompute the pressure sets based on current
1341 /// liveness. We don't yet have a fast version of downward pressure tracking
1342 /// analogous to getUpwardPressureDelta.
1343 void RegPressureTracker::
getMaxDownwardPressureDelta(const MachineInstr * MI,RegPressureDelta & Delta,ArrayRef<PressureChange> CriticalPSets,ArrayRef<unsigned> MaxPressureLimit)1344 getMaxDownwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta,
1345 ArrayRef<PressureChange> CriticalPSets,
1346 ArrayRef<unsigned> MaxPressureLimit) {
1347 // Snapshot Pressure.
1348 std::vector<unsigned> SavedPressure = CurrSetPressure;
1349 std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
1350
1351 bumpDownwardPressure(MI);
1352
1353 computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, RCI,
1354 LiveThruPressure);
1355 computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets,
1356 MaxPressureLimit, Delta);
1357 assert(Delta.CriticalMax.getUnitInc() >= 0 &&
1358 Delta.CurrentMax.getUnitInc() >= 0 && "cannot decrease max pressure");
1359
1360 // Restore the tracker's state.
1361 P.MaxSetPressure.swap(SavedMaxPressure);
1362 CurrSetPressure.swap(SavedPressure);
1363 }
1364
1365 /// Get the pressure of each PSet after traversing this instruction bottom-up.
1366 void RegPressureTracker::
getUpwardPressure(const MachineInstr * MI,std::vector<unsigned> & PressureResult,std::vector<unsigned> & MaxPressureResult)1367 getUpwardPressure(const MachineInstr *MI,
1368 std::vector<unsigned> &PressureResult,
1369 std::vector<unsigned> &MaxPressureResult) {
1370 // Snapshot pressure.
1371 PressureResult = CurrSetPressure;
1372 MaxPressureResult = P.MaxSetPressure;
1373
1374 bumpUpwardPressure(MI);
1375
1376 // Current pressure becomes the result. Restore current pressure.
1377 P.MaxSetPressure.swap(MaxPressureResult);
1378 CurrSetPressure.swap(PressureResult);
1379 }
1380
1381 /// Get the pressure of each PSet after traversing this instruction top-down.
1382 void RegPressureTracker::
getDownwardPressure(const MachineInstr * MI,std::vector<unsigned> & PressureResult,std::vector<unsigned> & MaxPressureResult)1383 getDownwardPressure(const MachineInstr *MI,
1384 std::vector<unsigned> &PressureResult,
1385 std::vector<unsigned> &MaxPressureResult) {
1386 // Snapshot pressure.
1387 PressureResult = CurrSetPressure;
1388 MaxPressureResult = P.MaxSetPressure;
1389
1390 bumpDownwardPressure(MI);
1391
1392 // Current pressure becomes the result. Restore current pressure.
1393 P.MaxSetPressure.swap(MaxPressureResult);
1394 CurrSetPressure.swap(PressureResult);
1395 }
1396