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