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