Home | History | Annotate | Download | only in CodeGen 
      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 #include "llvm/Target/TargetMachine.h"
     23 
     24 using namespace llvm;
     25 
     26 /// Increase pressure for each pressure set provided by TargetRegisterInfo.
     27 static void increaseSetPressure(std::vector<unsigned> &CurrSetPressure,
     28                                 std::vector<unsigned> &MaxSetPressure,
     29                                 const int *PSet, unsigned Weight) {
     30   for (; *PSet != -1; ++PSet) {
     31     CurrSetPressure[*PSet] += Weight;
     32     if (&CurrSetPressure != &MaxSetPressure
     33         && CurrSetPressure[*PSet] > MaxSetPressure[*PSet]) {
     34       MaxSetPressure[*PSet] = CurrSetPressure[*PSet];
     35     }
     36   }
     37 }
     38 
     39 /// Decrease pressure for each pressure set provided by TargetRegisterInfo.
     40 static void decreaseSetPressure(std::vector<unsigned> &CurrSetPressure,
     41                                 const int *PSet, unsigned Weight) {
     42   for (; *PSet != -1; ++PSet) {
     43     assert(CurrSetPressure[*PSet] >= Weight && "register pressure underflow");
     44     CurrSetPressure[*PSet] -= Weight;
     45   }
     46 }
     47 
     48 /// Directly increase pressure only within this RegisterPressure result.
     49 void RegisterPressure::increase(unsigned Reg, const TargetRegisterInfo *TRI,
     50                                 const MachineRegisterInfo *MRI) {
     51   if (TargetRegisterInfo::isVirtualRegister(Reg)) {
     52     const TargetRegisterClass *RC = MRI->getRegClass(Reg);
     53     increaseSetPressure(MaxSetPressure, MaxSetPressure,
     54                         TRI->getRegClassPressureSets(RC),
     55                         TRI->getRegClassWeight(RC).RegWeight);
     56   }
     57   else {
     58     increaseSetPressure(MaxSetPressure, MaxSetPressure,
     59                         TRI->getRegUnitPressureSets(Reg),
     60                         TRI->getRegUnitWeight(Reg));
     61   }
     62 }
     63 
     64 /// Directly decrease pressure only within this RegisterPressure result.
     65 void RegisterPressure::decrease(unsigned Reg, const TargetRegisterInfo *TRI,
     66                                 const MachineRegisterInfo *MRI) {
     67   if (TargetRegisterInfo::isVirtualRegister(Reg)) {
     68     const TargetRegisterClass *RC = MRI->getRegClass(Reg);
     69     decreaseSetPressure(MaxSetPressure, TRI->getRegClassPressureSets(RC),
     70                         TRI->getRegClassWeight(RC).RegWeight);
     71   }
     72   else {
     73     decreaseSetPressure(MaxSetPressure, TRI->getRegUnitPressureSets(Reg),
     74                         TRI->getRegUnitWeight(Reg));
     75   }
     76 }
     77 
     78 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
     79 void llvm::dumpRegSetPressure(ArrayRef<unsigned> SetPressure,
     80                               const TargetRegisterInfo *TRI) {
     81   bool Empty = true;
     82   for (unsigned i = 0, e = SetPressure.size(); i < e; ++i) {
     83     if (SetPressure[i] != 0) {
     84       dbgs() << TRI->getRegPressureSetName(i) << "=" << SetPressure[i] << '\n';
     85       Empty = false;
     86     }
     87   }
     88   if (Empty)
     89     dbgs() << "\n";
     90 }
     91 
     92 void RegisterPressure::dump(const TargetRegisterInfo *TRI) const {
     93   dbgs() << "Max Pressure: ";
     94   dumpRegSetPressure(MaxSetPressure, TRI);
     95   dbgs() << "Live In: ";
     96   for (unsigned i = 0, e = LiveInRegs.size(); i < e; ++i)
     97     dbgs() << PrintReg(LiveInRegs[i], TRI) << " ";
     98   dbgs() << '\n';
     99   dbgs() << "Live Out: ";
    100   for (unsigned i = 0, e = LiveOutRegs.size(); i < e; ++i)
    101     dbgs() << PrintReg(LiveOutRegs[i], TRI) << " ";
    102   dbgs() << '\n';
    103 }
    104 
    105 void RegPressureTracker::dump() const {
    106   if (!isTopClosed() || !isBottomClosed()) {
    107     dbgs() << "Curr Pressure: ";
    108     dumpRegSetPressure(CurrSetPressure, TRI);
    109   }
    110   P.dump(TRI);
    111 }
    112 #endif
    113 
    114 /// Increase the current pressure as impacted by these registers and bump
    115 /// the high water mark if needed.
    116 void RegPressureTracker::increaseRegPressure(ArrayRef<unsigned> Regs) {
    117   for (unsigned I = 0, E = Regs.size(); I != E; ++I) {
    118     if (TargetRegisterInfo::isVirtualRegister(Regs[I])) {
    119       const TargetRegisterClass *RC = MRI->getRegClass(Regs[I]);
    120       increaseSetPressure(CurrSetPressure, P.MaxSetPressure,
    121                           TRI->getRegClassPressureSets(RC),
    122                           TRI->getRegClassWeight(RC).RegWeight);
    123     }
    124     else {
    125       increaseSetPressure(CurrSetPressure, P.MaxSetPressure,
    126                           TRI->getRegUnitPressureSets(Regs[I]),
    127                           TRI->getRegUnitWeight(Regs[I]));
    128     }
    129   }
    130 }
    131 
    132 /// Simply decrease the current pressure as impacted by these registers.
    133 void RegPressureTracker::decreaseRegPressure(ArrayRef<unsigned> Regs) {
    134   for (unsigned I = 0, E = Regs.size(); I != E; ++I) {
    135     if (TargetRegisterInfo::isVirtualRegister(Regs[I])) {
    136       const TargetRegisterClass *RC = MRI->getRegClass(Regs[I]);
    137       decreaseSetPressure(CurrSetPressure,
    138                           TRI->getRegClassPressureSets(RC),
    139                           TRI->getRegClassWeight(RC).RegWeight);
    140     }
    141     else {
    142       decreaseSetPressure(CurrSetPressure, TRI->getRegUnitPressureSets(Regs[I]),
    143                           TRI->getRegUnitWeight(Regs[I]));
    144     }
    145   }
    146 }
    147 
    148 /// Clear the result so it can be used for another round of pressure tracking.
    149 void IntervalPressure::reset() {
    150   TopIdx = BottomIdx = SlotIndex();
    151   MaxSetPressure.clear();
    152   LiveInRegs.clear();
    153   LiveOutRegs.clear();
    154 }
    155 
    156 /// Clear the result so it can be used for another round of pressure tracking.
    157 void RegionPressure::reset() {
    158   TopPos = BottomPos = MachineBasicBlock::const_iterator();
    159   MaxSetPressure.clear();
    160   LiveInRegs.clear();
    161   LiveOutRegs.clear();
    162 }
    163 
    164 /// If the current top is not less than or equal to the next index, open it.
    165 /// We happen to need the SlotIndex for the next top for pressure update.
    166 void IntervalPressure::openTop(SlotIndex NextTop) {
    167   if (TopIdx <= NextTop)
    168     return;
    169   TopIdx = SlotIndex();
    170   LiveInRegs.clear();
    171 }
    172 
    173 /// If the current top is the previous instruction (before receding), open it.
    174 void RegionPressure::openTop(MachineBasicBlock::const_iterator PrevTop) {
    175   if (TopPos != PrevTop)
    176     return;
    177   TopPos = MachineBasicBlock::const_iterator();
    178   LiveInRegs.clear();
    179 }
    180 
    181 /// If the current bottom is not greater than the previous index, open it.
    182 void IntervalPressure::openBottom(SlotIndex PrevBottom) {
    183   if (BottomIdx > PrevBottom)
    184     return;
    185   BottomIdx = SlotIndex();
    186   LiveInRegs.clear();
    187 }
    188 
    189 /// If the current bottom is the previous instr (before advancing), open it.
    190 void RegionPressure::openBottom(MachineBasicBlock::const_iterator PrevBottom) {
    191   if (BottomPos != PrevBottom)
    192     return;
    193   BottomPos = MachineBasicBlock::const_iterator();
    194   LiveInRegs.clear();
    195 }
    196 
    197 const LiveInterval *RegPressureTracker::getInterval(unsigned Reg) const {
    198   if (TargetRegisterInfo::isVirtualRegister(Reg))
    199     return &LIS->getInterval(Reg);
    200   return LIS->getCachedRegUnit(Reg);
    201 }
    202 
    203 /// Setup the RegPressureTracker.
    204 ///
    205 /// TODO: Add support for pressure without LiveIntervals.
    206 void RegPressureTracker::init(const MachineFunction *mf,
    207                               const RegisterClassInfo *rci,
    208                               const LiveIntervals *lis,
    209                               const MachineBasicBlock *mbb,
    210                               MachineBasicBlock::const_iterator pos,
    211                               bool ShouldTrackUntiedDefs)
    212 {
    213   MF = mf;
    214   TRI = MF->getTarget().getRegisterInfo();
    215   RCI = rci;
    216   MRI = &MF->getRegInfo();
    217   MBB = mbb;
    218   TrackUntiedDefs = ShouldTrackUntiedDefs;
    219 
    220   if (RequireIntervals) {
    221     assert(lis && "IntervalPressure requires LiveIntervals");
    222     LIS = lis;
    223   }
    224 
    225   CurrPos = pos;
    226   CurrSetPressure.assign(TRI->getNumRegPressureSets(), 0);
    227   LiveThruPressure.clear();
    228 
    229   if (RequireIntervals)
    230     static_cast<IntervalPressure&>(P).reset();
    231   else
    232     static_cast<RegionPressure&>(P).reset();
    233   P.MaxSetPressure = CurrSetPressure;
    234 
    235   LiveRegs.PhysRegs.clear();
    236   LiveRegs.PhysRegs.setUniverse(TRI->getNumRegs());
    237   LiveRegs.VirtRegs.clear();
    238   LiveRegs.VirtRegs.setUniverse(MRI->getNumVirtRegs());
    239   UntiedDefs.clear();
    240   if (TrackUntiedDefs)
    241     UntiedDefs.setUniverse(MRI->getNumVirtRegs());
    242 }
    243 
    244 /// Does this pressure result have a valid top position and live ins.
    245 bool RegPressureTracker::isTopClosed() const {
    246   if (RequireIntervals)
    247     return static_cast<IntervalPressure&>(P).TopIdx.isValid();
    248   return (static_cast<RegionPressure&>(P).TopPos ==
    249           MachineBasicBlock::const_iterator());
    250 }
    251 
    252 /// Does this pressure result have a valid bottom position and live outs.
    253 bool RegPressureTracker::isBottomClosed() const {
    254   if (RequireIntervals)
    255     return static_cast<IntervalPressure&>(P).BottomIdx.isValid();
    256   return (static_cast<RegionPressure&>(P).BottomPos ==
    257           MachineBasicBlock::const_iterator());
    258 }
    259 
    260 
    261 SlotIndex RegPressureTracker::getCurrSlot() const {
    262   MachineBasicBlock::const_iterator IdxPos = CurrPos;
    263   while (IdxPos != MBB->end() && IdxPos->isDebugValue())
    264     ++IdxPos;
    265   if (IdxPos == MBB->end())
    266     return LIS->getMBBEndIdx(MBB);
    267   return LIS->getInstructionIndex(IdxPos).getRegSlot();
    268 }
    269 
    270 /// Set the boundary for the top of the region and summarize live ins.
    271 void RegPressureTracker::closeTop() {
    272   if (RequireIntervals)
    273     static_cast<IntervalPressure&>(P).TopIdx = getCurrSlot();
    274   else
    275     static_cast<RegionPressure&>(P).TopPos = CurrPos;
    276 
    277   assert(P.LiveInRegs.empty() && "inconsistent max pressure result");
    278   P.LiveInRegs.reserve(LiveRegs.PhysRegs.size() + LiveRegs.VirtRegs.size());
    279   P.LiveInRegs.append(LiveRegs.PhysRegs.begin(), LiveRegs.PhysRegs.end());
    280   for (SparseSet<unsigned>::const_iterator I =
    281          LiveRegs.VirtRegs.begin(), E = LiveRegs.VirtRegs.end(); I != E; ++I)
    282     P.LiveInRegs.push_back(*I);
    283   std::sort(P.LiveInRegs.begin(), P.LiveInRegs.end());
    284   P.LiveInRegs.erase(std::unique(P.LiveInRegs.begin(), P.LiveInRegs.end()),
    285                      P.LiveInRegs.end());
    286 }
    287 
    288 /// Set the boundary for the bottom of the region and summarize live outs.
    289 void RegPressureTracker::closeBottom() {
    290   if (RequireIntervals)
    291     static_cast<IntervalPressure&>(P).BottomIdx = getCurrSlot();
    292   else
    293     static_cast<RegionPressure&>(P).BottomPos = CurrPos;
    294 
    295   assert(P.LiveOutRegs.empty() && "inconsistent max pressure result");
    296   P.LiveOutRegs.reserve(LiveRegs.PhysRegs.size() + LiveRegs.VirtRegs.size());
    297   P.LiveOutRegs.append(LiveRegs.PhysRegs.begin(), LiveRegs.PhysRegs.end());
    298   for (SparseSet<unsigned>::const_iterator I =
    299          LiveRegs.VirtRegs.begin(), E = LiveRegs.VirtRegs.end(); I != E; ++I)
    300     P.LiveOutRegs.push_back(*I);
    301   std::sort(P.LiveOutRegs.begin(), P.LiveOutRegs.end());
    302   P.LiveOutRegs.erase(std::unique(P.LiveOutRegs.begin(), P.LiveOutRegs.end()),
    303                       P.LiveOutRegs.end());
    304 }
    305 
    306 /// Finalize the region boundaries and record live ins and live outs.
    307 void RegPressureTracker::closeRegion() {
    308   if (!isTopClosed() && !isBottomClosed()) {
    309     assert(LiveRegs.PhysRegs.empty() && LiveRegs.VirtRegs.empty() &&
    310            "no region boundary");
    311     return;
    312   }
    313   if (!isBottomClosed())
    314     closeBottom();
    315   else if (!isTopClosed())
    316     closeTop();
    317   // If both top and bottom are closed, do nothing.
    318 }
    319 
    320 /// The register tracker is unaware of global liveness so ignores normal
    321 /// live-thru ranges. However, two-address or coalesced chains can also lead
    322 /// to live ranges with no holes. Count these to inform heuristics that we
    323 /// can never drop below this pressure.
    324 void RegPressureTracker::initLiveThru(const RegPressureTracker &RPTracker) {
    325   LiveThruPressure.assign(TRI->getNumRegPressureSets(), 0);
    326   assert(isBottomClosed() && "need bottom-up tracking to intialize.");
    327   for (unsigned i = 0, e = P.LiveOutRegs.size(); i < e; ++i) {
    328     unsigned Reg = P.LiveOutRegs[i];
    329     if (TargetRegisterInfo::isVirtualRegister(Reg)
    330         && !RPTracker.hasUntiedDef(Reg)) {
    331       const TargetRegisterClass *RC = MRI->getRegClass(Reg);
    332       increaseSetPressure(LiveThruPressure, LiveThruPressure,
    333                           TRI->getRegClassPressureSets(RC),
    334                           TRI->getRegClassWeight(RC).RegWeight);
    335     }
    336   }
    337 }
    338 
    339 /// \brief Convenient wrapper for checking membership in RegisterOperands.
    340 static bool containsReg(ArrayRef<unsigned> Regs, unsigned Reg) {
    341   return std::find(Regs.begin(), Regs.end(), Reg) != Regs.end();
    342 }
    343 
    344 /// Collect this instruction's unique uses and defs into SmallVectors for
    345 /// processing defs and uses in order.
    346 class RegisterOperands {
    347   const TargetRegisterInfo *TRI;
    348   const MachineRegisterInfo *MRI;
    349 
    350 public:
    351   SmallVector<unsigned, 8> Uses;
    352   SmallVector<unsigned, 8> Defs;
    353   SmallVector<unsigned, 8> DeadDefs;
    354 
    355   RegisterOperands(const TargetRegisterInfo *tri,
    356                    const MachineRegisterInfo *mri): TRI(tri), MRI(mri) {}
    357 
    358   /// Push this operand's register onto the correct vector.
    359   void collect(const MachineOperand &MO) {
    360     if (!MO.isReg() || !MO.getReg())
    361       return;
    362     if (MO.readsReg())
    363       pushRegUnits(MO.getReg(), Uses);
    364     if (MO.isDef()) {
    365       if (MO.isDead())
    366         pushRegUnits(MO.getReg(), DeadDefs);
    367       else
    368         pushRegUnits(MO.getReg(), Defs);
    369     }
    370   }
    371 
    372 protected:
    373   void pushRegUnits(unsigned Reg, SmallVectorImpl<unsigned> &Regs) {
    374     if (TargetRegisterInfo::isVirtualRegister(Reg)) {
    375       if (containsReg(Regs, Reg))
    376         return;
    377       Regs.push_back(Reg);
    378     }
    379     else if (MRI->isAllocatable(Reg)) {
    380       for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) {
    381         if (containsReg(Regs, *Units))
    382           continue;
    383         Regs.push_back(*Units);
    384       }
    385     }
    386   }
    387 };
    388 
    389 /// Collect physical and virtual register operands.
    390 static void collectOperands(const MachineInstr *MI,
    391                             RegisterOperands &RegOpers) {
    392   for (ConstMIBundleOperands OperI(MI); OperI.isValid(); ++OperI)
    393     RegOpers.collect(*OperI);
    394 
    395   // Remove redundant physreg dead defs.
    396   SmallVectorImpl<unsigned>::iterator I =
    397     std::remove_if(RegOpers.DeadDefs.begin(), RegOpers.DeadDefs.end(),
    398                    std::bind1st(std::ptr_fun(containsReg), RegOpers.Defs));
    399   RegOpers.DeadDefs.erase(I, RegOpers.DeadDefs.end());
    400 }
    401 
    402 /// Force liveness of registers.
    403 void RegPressureTracker::addLiveRegs(ArrayRef<unsigned> Regs) {
    404   for (unsigned i = 0, e = Regs.size(); i != e; ++i) {
    405     if (LiveRegs.insert(Regs[i]))
    406       increaseRegPressure(Regs[i]);
    407   }
    408 }
    409 
    410 /// Add Reg to the live in set and increase max pressure.
    411 void RegPressureTracker::discoverLiveIn(unsigned Reg) {
    412   assert(!LiveRegs.contains(Reg) && "avoid bumping max pressure twice");
    413   if (containsReg(P.LiveInRegs, Reg))
    414     return;
    415 
    416   // At live in discovery, unconditionally increase the high water mark.
    417   P.LiveInRegs.push_back(Reg);
    418   P.increase(Reg, TRI, MRI);
    419 }
    420 
    421 /// Add Reg to the live out set and increase max pressure.
    422 void RegPressureTracker::discoverLiveOut(unsigned Reg) {
    423   assert(!LiveRegs.contains(Reg) && "avoid bumping max pressure twice");
    424   if (containsReg(P.LiveOutRegs, Reg))
    425     return;
    426 
    427   // At live out discovery, unconditionally increase the high water mark.
    428   P.LiveOutRegs.push_back(Reg);
    429   P.increase(Reg, TRI, MRI);
    430 }
    431 
    432 /// Recede across the previous instruction.
    433 bool RegPressureTracker::recede() {
    434   // Check for the top of the analyzable region.
    435   if (CurrPos == MBB->begin()) {
    436     closeRegion();
    437     return false;
    438   }
    439   if (!isBottomClosed())
    440     closeBottom();
    441 
    442   // Open the top of the region using block iterators.
    443   if (!RequireIntervals && isTopClosed())
    444     static_cast<RegionPressure&>(P).openTop(CurrPos);
    445 
    446   // Find the previous instruction.
    447   do
    448     --CurrPos;
    449   while (CurrPos != MBB->begin() && CurrPos->isDebugValue());
    450 
    451   if (CurrPos->isDebugValue()) {
    452     closeRegion();
    453     return false;
    454   }
    455   SlotIndex SlotIdx;
    456   if (RequireIntervals)
    457     SlotIdx = LIS->getInstructionIndex(CurrPos).getRegSlot();
    458 
    459   // Open the top of the region using slot indexes.
    460   if (RequireIntervals && isTopClosed())
    461     static_cast<IntervalPressure&>(P).openTop(SlotIdx);
    462 
    463   RegisterOperands RegOpers(TRI, MRI);
    464   collectOperands(CurrPos, RegOpers);
    465 
    466   // Boost pressure for all dead defs together.
    467   increaseRegPressure(RegOpers.DeadDefs);
    468   decreaseRegPressure(RegOpers.DeadDefs);
    469 
    470   // Kill liveness at live defs.
    471   // TODO: consider earlyclobbers?
    472   for (unsigned i = 0, e = RegOpers.Defs.size(); i < e; ++i) {
    473     unsigned Reg = RegOpers.Defs[i];
    474     if (LiveRegs.erase(Reg))
    475       decreaseRegPressure(Reg);
    476     else
    477       discoverLiveOut(Reg);
    478   }
    479 
    480   // Generate liveness for uses.
    481   for (unsigned i = 0, e = RegOpers.Uses.size(); i < e; ++i) {
    482     unsigned Reg = RegOpers.Uses[i];
    483     if (!LiveRegs.contains(Reg)) {
    484       // Adjust liveouts if LiveIntervals are available.
    485       if (RequireIntervals) {
    486         const LiveInterval *LI = getInterval(Reg);
    487         if (LI && !LI->killedAt(SlotIdx))
    488           discoverLiveOut(Reg);
    489       }
    490       increaseRegPressure(Reg);
    491       LiveRegs.insert(Reg);
    492     }
    493   }
    494   if (TrackUntiedDefs) {
    495     for (unsigned i = 0, e = RegOpers.Defs.size(); i < e; ++i) {
    496       unsigned Reg = RegOpers.Defs[i];
    497       if (TargetRegisterInfo::isVirtualRegister(Reg) && !LiveRegs.contains(Reg))
    498         UntiedDefs.insert(Reg);
    499     }
    500   }
    501   return true;
    502 }
    503 
    504 /// Advance across the current instruction.
    505 bool RegPressureTracker::advance() {
    506   assert(!TrackUntiedDefs && "unsupported mode");
    507 
    508   // Check for the bottom of the analyzable region.
    509   if (CurrPos == MBB->end()) {
    510     closeRegion();
    511     return false;
    512   }
    513   if (!isTopClosed())
    514     closeTop();
    515 
    516   SlotIndex SlotIdx;
    517   if (RequireIntervals)
    518     SlotIdx = getCurrSlot();
    519 
    520   // Open the bottom of the region using slot indexes.
    521   if (isBottomClosed()) {
    522     if (RequireIntervals)
    523       static_cast<IntervalPressure&>(P).openBottom(SlotIdx);
    524     else
    525       static_cast<RegionPressure&>(P).openBottom(CurrPos);
    526   }
    527 
    528   RegisterOperands RegOpers(TRI, MRI);
    529   collectOperands(CurrPos, RegOpers);
    530 
    531   for (unsigned i = 0, e = RegOpers.Uses.size(); i < e; ++i) {
    532     unsigned Reg = RegOpers.Uses[i];
    533     // Discover live-ins.
    534     bool isLive = LiveRegs.contains(Reg);
    535     if (!isLive)
    536       discoverLiveIn(Reg);
    537     // Kill liveness at last uses.
    538     bool lastUse = false;
    539     if (RequireIntervals) {
    540       const LiveInterval *LI = getInterval(Reg);
    541       lastUse = LI && LI->killedAt(SlotIdx);
    542     }
    543     else {
    544       // Allocatable physregs are always single-use before register rewriting.
    545       lastUse = !TargetRegisterInfo::isVirtualRegister(Reg);
    546     }
    547     if (lastUse && isLive) {
    548       LiveRegs.erase(Reg);
    549       decreaseRegPressure(Reg);
    550     }
    551     else if (!lastUse && !isLive)
    552       increaseRegPressure(Reg);
    553   }
    554 
    555   // Generate liveness for defs.
    556   for (unsigned i = 0, e = RegOpers.Defs.size(); i < e; ++i) {
    557     unsigned Reg = RegOpers.Defs[i];
    558     if (LiveRegs.insert(Reg))
    559       increaseRegPressure(Reg);
    560   }
    561 
    562   // Boost pressure for all dead defs together.
    563   increaseRegPressure(RegOpers.DeadDefs);
    564   decreaseRegPressure(RegOpers.DeadDefs);
    565 
    566   // Find the next instruction.
    567   do
    568     ++CurrPos;
    569   while (CurrPos != MBB->end() && CurrPos->isDebugValue());
    570   return true;
    571 }
    572 
    573 /// Find the max change in excess pressure across all sets.
    574 static void computeExcessPressureDelta(ArrayRef<unsigned> OldPressureVec,
    575                                        ArrayRef<unsigned> NewPressureVec,
    576                                        RegPressureDelta &Delta,
    577                                        const RegisterClassInfo *RCI,
    578                                        ArrayRef<unsigned> LiveThruPressureVec) {
    579   int ExcessUnits = 0;
    580   unsigned PSetID = ~0U;
    581   for (unsigned i = 0, e = OldPressureVec.size(); i < e; ++i) {
    582     unsigned POld = OldPressureVec[i];
    583     unsigned PNew = NewPressureVec[i];
    584     int PDiff = (int)PNew - (int)POld;
    585     if (!PDiff) // No change in this set in the common case.
    586       continue;
    587     // Only consider change beyond the limit.
    588     unsigned Limit = RCI->getRegPressureSetLimit(i);
    589     if (!LiveThruPressureVec.empty())
    590       Limit += LiveThruPressureVec[i];
    591 
    592     if (Limit > POld) {
    593       if (Limit > PNew)
    594         PDiff = 0;            // Under the limit
    595       else
    596         PDiff = PNew - Limit; // Just exceeded limit.
    597     }
    598     else if (Limit > PNew)
    599       PDiff = Limit - POld;   // Just obeyed limit.
    600 
    601     if (PDiff) {
    602       ExcessUnits = PDiff;
    603       PSetID = i;
    604       break;
    605     }
    606   }
    607   Delta.Excess.PSetID = PSetID;
    608   Delta.Excess.UnitIncrease = ExcessUnits;
    609 }
    610 
    611 /// Find the max change in max pressure that either surpasses a critical PSet
    612 /// limit or exceeds the current MaxPressureLimit.
    613 ///
    614 /// FIXME: comparing each element of the old and new MaxPressure vectors here is
    615 /// silly. It's done now to demonstrate the concept but will go away with a
    616 /// RegPressureTracker API change to work with pressure differences.
    617 static void computeMaxPressureDelta(ArrayRef<unsigned> OldMaxPressureVec,
    618                                     ArrayRef<unsigned> NewMaxPressureVec,
    619                                     ArrayRef<PressureElement> CriticalPSets,
    620                                     ArrayRef<unsigned> MaxPressureLimit,
    621                                     RegPressureDelta &Delta) {
    622   Delta.CriticalMax = PressureElement();
    623   Delta.CurrentMax = PressureElement();
    624 
    625   unsigned CritIdx = 0, CritEnd = CriticalPSets.size();
    626   for (unsigned i = 0, e = OldMaxPressureVec.size(); i < e; ++i) {
    627     unsigned POld = OldMaxPressureVec[i];
    628     unsigned PNew = NewMaxPressureVec[i];
    629     if (PNew == POld) // No change in this set in the common case.
    630       continue;
    631 
    632     if (!Delta.CriticalMax.isValid()) {
    633       while (CritIdx != CritEnd && CriticalPSets[CritIdx].PSetID < i)
    634         ++CritIdx;
    635 
    636       if (CritIdx != CritEnd && CriticalPSets[CritIdx].PSetID == i) {
    637         int PDiff = (int)PNew - (int)CriticalPSets[CritIdx].UnitIncrease;
    638         if (PDiff > 0) {
    639           Delta.CriticalMax.PSetID = i;
    640           Delta.CriticalMax.UnitIncrease = PDiff;
    641         }
    642       }
    643     }
    644     // Find the first increase above MaxPressureLimit.
    645     // (Ignores negative MDiff).
    646     if (!Delta.CurrentMax.isValid()) {
    647       int MDiff = (int)PNew - (int)MaxPressureLimit[i];
    648       if (MDiff > 0) {
    649         Delta.CurrentMax.PSetID = i;
    650         Delta.CurrentMax.UnitIncrease = MDiff;
    651         if (CritIdx == CritEnd || Delta.CriticalMax.isValid())
    652           break;
    653       }
    654     }
    655   }
    656 }
    657 
    658 /// Record the upward impact of a single instruction on current register
    659 /// pressure. Unlike the advance/recede pressure tracking interface, this does
    660 /// not discover live in/outs.
    661 ///
    662 /// This is intended for speculative queries. It leaves pressure inconsistent
    663 /// with the current position, so must be restored by the caller.
    664 void RegPressureTracker::bumpUpwardPressure(const MachineInstr *MI) {
    665   assert(!MI->isDebugValue() && "Expect a nondebug instruction.");
    666 
    667   // Account for register pressure similar to RegPressureTracker::recede().
    668   RegisterOperands RegOpers(TRI, MRI);
    669   collectOperands(MI, RegOpers);
    670 
    671   // Boost max pressure for all dead defs together.
    672   // Since CurrSetPressure and MaxSetPressure
    673   increaseRegPressure(RegOpers.DeadDefs);
    674   decreaseRegPressure(RegOpers.DeadDefs);
    675 
    676   // Kill liveness at live defs.
    677   for (unsigned i = 0, e = RegOpers.Defs.size(); i < e; ++i) {
    678     unsigned Reg = RegOpers.Defs[i];
    679     if (!containsReg(RegOpers.Uses, Reg))
    680       decreaseRegPressure(Reg);
    681   }
    682   // Generate liveness for uses.
    683   for (unsigned i = 0, e = RegOpers.Uses.size(); i < e; ++i) {
    684     unsigned Reg = RegOpers.Uses[i];
    685     if (!LiveRegs.contains(Reg))
    686       increaseRegPressure(Reg);
    687   }
    688 }
    689 
    690 /// Consider the pressure increase caused by traversing this instruction
    691 /// bottom-up. Find the pressure set with the most change beyond its pressure
    692 /// limit based on the tracker's current pressure, and return the change in
    693 /// number of register units of that pressure set introduced by this
    694 /// instruction.
    695 ///
    696 /// This assumes that the current LiveOut set is sufficient.
    697 ///
    698 /// FIXME: This is expensive for an on-the-fly query. We need to cache the
    699 /// result per-SUnit with enough information to adjust for the current
    700 /// scheduling position. But this works as a proof of concept.
    701 void RegPressureTracker::
    702 getMaxUpwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta,
    703                           ArrayRef<PressureElement> CriticalPSets,
    704                           ArrayRef<unsigned> MaxPressureLimit) {
    705   // Snapshot Pressure.
    706   // FIXME: The snapshot heap space should persist. But I'm planning to
    707   // summarize the pressure effect so we don't need to snapshot at all.
    708   std::vector<unsigned> SavedPressure = CurrSetPressure;
    709   std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
    710 
    711   bumpUpwardPressure(MI);
    712 
    713   computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, RCI,
    714                              LiveThruPressure);
    715   computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets,
    716                           MaxPressureLimit, Delta);
    717   assert(Delta.CriticalMax.UnitIncrease >= 0 &&
    718          Delta.CurrentMax.UnitIncrease >= 0 && "cannot decrease max pressure");
    719 
    720   // Restore the tracker's state.
    721   P.MaxSetPressure.swap(SavedMaxPressure);
    722   CurrSetPressure.swap(SavedPressure);
    723 }
    724 
    725 /// Helper to find a vreg use between two indices [PriorUseIdx, NextUseIdx).
    726 static bool findUseBetween(unsigned Reg,
    727                            SlotIndex PriorUseIdx, SlotIndex NextUseIdx,
    728                            const MachineRegisterInfo *MRI,
    729                            const LiveIntervals *LIS) {
    730   for (MachineRegisterInfo::use_nodbg_iterator
    731          UI = MRI->use_nodbg_begin(Reg), UE = MRI->use_nodbg_end();
    732          UI != UE; UI.skipInstruction()) {
    733       const MachineInstr* MI = &*UI;
    734       if (MI->isDebugValue())
    735         continue;
    736       SlotIndex InstSlot = LIS->getInstructionIndex(MI).getRegSlot();
    737       if (InstSlot >= PriorUseIdx && InstSlot < NextUseIdx)
    738         return true;
    739   }
    740   return false;
    741 }
    742 
    743 /// Record the downward impact of a single instruction on current register
    744 /// pressure. Unlike the advance/recede pressure tracking interface, this does
    745 /// not discover live in/outs.
    746 ///
    747 /// This is intended for speculative queries. It leaves pressure inconsistent
    748 /// with the current position, so must be restored by the caller.
    749 void RegPressureTracker::bumpDownwardPressure(const MachineInstr *MI) {
    750   assert(!MI->isDebugValue() && "Expect a nondebug instruction.");
    751 
    752   // Account for register pressure similar to RegPressureTracker::recede().
    753   RegisterOperands RegOpers(TRI, MRI);
    754   collectOperands(MI, RegOpers);
    755 
    756   // Kill liveness at last uses. Assume allocatable physregs are single-use
    757   // rather than checking LiveIntervals.
    758   SlotIndex SlotIdx;
    759   if (RequireIntervals)
    760     SlotIdx = LIS->getInstructionIndex(MI).getRegSlot();
    761 
    762   for (unsigned i = 0, e = RegOpers.Uses.size(); i < e; ++i) {
    763     unsigned Reg = RegOpers.Uses[i];
    764     if (RequireIntervals) {
    765       // FIXME: allow the caller to pass in the list of vreg uses that remain
    766       // to be bottom-scheduled to avoid searching uses at each query.
    767       SlotIndex CurrIdx = getCurrSlot();
    768       const LiveInterval *LI = getInterval(Reg);
    769       if (LI && LI->killedAt(SlotIdx)
    770           && !findUseBetween(Reg, CurrIdx, SlotIdx, MRI, LIS)) {
    771         decreaseRegPressure(Reg);
    772       }
    773     }
    774     else if (!TargetRegisterInfo::isVirtualRegister(Reg)) {
    775       // Allocatable physregs are always single-use before register rewriting.
    776       decreaseRegPressure(Reg);
    777     }
    778   }
    779 
    780   // Generate liveness for defs.
    781   increaseRegPressure(RegOpers.Defs);
    782 
    783   // Boost pressure for all dead defs together.
    784   increaseRegPressure(RegOpers.DeadDefs);
    785   decreaseRegPressure(RegOpers.DeadDefs);
    786 }
    787 
    788 /// Consider the pressure increase caused by traversing this instruction
    789 /// top-down. Find the register class with the most change in its pressure limit
    790 /// based on the tracker's current pressure, and return the number of excess
    791 /// register units of that pressure set introduced by this instruction.
    792 ///
    793 /// This assumes that the current LiveIn set is sufficient.
    794 void RegPressureTracker::
    795 getMaxDownwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta,
    796                             ArrayRef<PressureElement> CriticalPSets,
    797                             ArrayRef<unsigned> MaxPressureLimit) {
    798   // Snapshot Pressure.
    799   std::vector<unsigned> SavedPressure = CurrSetPressure;
    800   std::vector<unsigned> SavedMaxPressure = P.MaxSetPressure;
    801 
    802   bumpDownwardPressure(MI);
    803 
    804   computeExcessPressureDelta(SavedPressure, CurrSetPressure, Delta, RCI,
    805                              LiveThruPressure);
    806   computeMaxPressureDelta(SavedMaxPressure, P.MaxSetPressure, CriticalPSets,
    807                           MaxPressureLimit, Delta);
    808   assert(Delta.CriticalMax.UnitIncrease >= 0 &&
    809          Delta.CurrentMax.UnitIncrease >= 0 && "cannot decrease max pressure");
    810 
    811   // Restore the tracker's state.
    812   P.MaxSetPressure.swap(SavedMaxPressure);
    813   CurrSetPressure.swap(SavedPressure);
    814 }
    815 
    816 /// Get the pressure of each PSet after traversing this instruction bottom-up.
    817 void RegPressureTracker::
    818 getUpwardPressure(const MachineInstr *MI,
    819                   std::vector<unsigned> &PressureResult,
    820                   std::vector<unsigned> &MaxPressureResult) {
    821   // Snapshot pressure.
    822   PressureResult = CurrSetPressure;
    823   MaxPressureResult = P.MaxSetPressure;
    824 
    825   bumpUpwardPressure(MI);
    826 
    827   // Current pressure becomes the result. Restore current pressure.
    828   P.MaxSetPressure.swap(MaxPressureResult);
    829   CurrSetPressure.swap(PressureResult);
    830 }
    831 
    832 /// Get the pressure of each PSet after traversing this instruction top-down.
    833 void RegPressureTracker::
    834 getDownwardPressure(const MachineInstr *MI,
    835                     std::vector<unsigned> &PressureResult,
    836                     std::vector<unsigned> &MaxPressureResult) {
    837   // Snapshot pressure.
    838   PressureResult = CurrSetPressure;
    839   MaxPressureResult = P.MaxSetPressure;
    840 
    841   bumpDownwardPressure(MI);
    842 
    843   // Current pressure becomes the result. Restore current pressure.
    844   P.MaxSetPressure.swap(MaxPressureResult);
    845   CurrSetPressure.swap(PressureResult);
    846 }
    847