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