LCOV - code coverage report
Current view: top level - lib/CodeGen - RegisterScavenging.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 310 340 91.2 %
Date: 2017-09-14 15:23:50 Functions: 22 26 84.6 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- RegisterScavenging.cpp - Machine register scavenging ---------------===//
       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             : /// \file
      11             : /// This file implements the machine register scavenger. It can provide
      12             : /// information, such as unused registers, at any point in a machine basic
      13             : /// block. It also provides a mechanism to make registers available by evicting
      14             : /// them to spill slots.
      15             : //
      16             : //===----------------------------------------------------------------------===//
      17             : 
      18             : #include "llvm/CodeGen/RegisterScavenging.h"
      19             : 
      20             : #include "llvm/ADT/BitVector.h"
      21             : #include "llvm/ADT/SmallVector.h"
      22             : #include "llvm/ADT/Statistic.h"
      23             : #include "llvm/CodeGen/MachineBasicBlock.h"
      24             : #include "llvm/CodeGen/MachineFrameInfo.h"
      25             : #include "llvm/CodeGen/MachineFunction.h"
      26             : #include "llvm/CodeGen/MachineInstr.h"
      27             : #include "llvm/CodeGen/MachineOperand.h"
      28             : #include "llvm/CodeGen/MachineRegisterInfo.h"
      29             : #include "llvm/MC/MCRegisterInfo.h"
      30             : #include "llvm/PassSupport.h"
      31             : #include "llvm/Support/Debug.h"
      32             : #include "llvm/Support/ErrorHandling.h"
      33             : #include "llvm/Support/raw_ostream.h"
      34             : #include "llvm/Target/TargetFrameLowering.h"
      35             : #include "llvm/Target/TargetInstrInfo.h"
      36             : #include "llvm/Target/TargetRegisterInfo.h"
      37             : #include "llvm/Target/TargetSubtargetInfo.h"
      38             : #include <algorithm>
      39             : #include <cassert>
      40             : #include <iterator>
      41             : #include <limits>
      42             : #include <string>
      43             : 
      44             : using namespace llvm;
      45             : 
      46             : #define DEBUG_TYPE "reg-scavenging"
      47             : 
      48             : STATISTIC(NumScavengedRegs, "Number of frame index regs scavenged");
      49             : 
      50        3508 : void RegScavenger::setRegUsed(unsigned Reg, LaneBitmask LaneMask) {
      51        3508 :   LiveUnits.addRegMasked(Reg, LaneMask);
      52        3508 : }
      53             : 
      54        1878 : void RegScavenger::init(MachineBasicBlock &MBB) {
      55        1878 :   MachineFunction &MF = *MBB.getParent();
      56        1878 :   TII = MF.getSubtarget().getInstrInfo();
      57        1878 :   TRI = MF.getSubtarget().getRegisterInfo();
      58        1878 :   MRI = &MF.getRegInfo();
      59        1878 :   LiveUnits.init(*TRI);
      60             : 
      61             :   assert((NumRegUnits == 0 || NumRegUnits == TRI->getNumRegUnits()) &&
      62             :          "Target changed?");
      63             : 
      64             :   // Self-initialize.
      65        1878 :   if (!this->MBB) {
      66         833 :     NumRegUnits = TRI->getNumRegUnits();
      67         833 :     KillRegUnits.resize(NumRegUnits);
      68         833 :     DefRegUnits.resize(NumRegUnits);
      69         833 :     TmpRegUnits.resize(NumRegUnits);
      70             :   }
      71        1878 :   this->MBB = &MBB;
      72             : 
      73        6796 :   for (ScavengedInfo &SI : Scavenged) {
      74        1162 :     SI.Reg = 0;
      75        1162 :     SI.Restore = nullptr;
      76             :   }
      77             : 
      78        1878 :   Tracking = false;
      79        1878 : }
      80             : 
      81         471 : void RegScavenger::enterBasicBlock(MachineBasicBlock &MBB) {
      82         471 :   init(MBB);
      83         471 :   LiveUnits.addLiveIns(MBB);
      84         471 : }
      85             : 
      86        1407 : void RegScavenger::enterBasicBlockEnd(MachineBasicBlock &MBB) {
      87        1407 :   init(MBB);
      88        1407 :   LiveUnits.addLiveOuts(MBB);
      89             : 
      90             :   // Move internal iterator at the last instruction of the block.
      91        4221 :   if (MBB.begin() != MBB.end()) {
      92        2814 :     MBBI = std::prev(MBB.end());
      93        1407 :     Tracking = true;
      94             :   }
      95        1407 : }
      96             : 
      97        5785 : void RegScavenger::addRegUnits(BitVector &BV, unsigned Reg) {
      98       19495 :   for (MCRegUnitIterator RUI(Reg, TRI); RUI.isValid(); ++RUI)
      99       23775 :     BV.set(*RUI);
     100        5785 : }
     101             : 
     102           0 : void RegScavenger::removeRegUnits(BitVector &BV, unsigned Reg) {
     103           0 :   for (MCRegUnitIterator RUI(Reg, TRI); RUI.isValid(); ++RUI)
     104           0 :     BV.reset(*RUI);
     105           0 : }
     106             : 
     107        4962 : void RegScavenger::determineKillsAndDefs() {
     108             :   assert(Tracking && "Must be tracking to determine kills and defs");
     109             : 
     110        9924 :   MachineInstr &MI = *MBBI;
     111             :   assert(!MI.isDebugValue() && "Debug values have no kills or defs");
     112             : 
     113             :   // Find out which registers are early clobbered, killed, defined, and marked
     114             :   // def-dead in this instruction.
     115        9924 :   KillRegUnits.reset();
     116        9924 :   DefRegUnits.reset();
     117       22774 :   for (const MachineOperand &MO : MI.operands()) {
     118       17812 :     if (MO.isRegMask()) {
     119          38 :       TmpRegUnits.clear();
     120        4717 :       for (unsigned RU = 0, RUEnd = TRI->getNumRegUnits(); RU != RUEnd; ++RU) {
     121       10822 :         for (MCRegUnitRootIterator RURI(RU, TRI); RURI.isValid(); ++RURI) {
     122       14037 :           if (MO.clobbersPhysReg(*RURI)) {
     123        3215 :             TmpRegUnits.set(RU);
     124             :             break;
     125             :           }
     126             :         }
     127             :       }
     128             : 
     129             :       // Apply the mask.
     130          38 :       KillRegUnits |= TmpRegUnits;
     131             :     }
     132       17812 :     if (!MO.isReg())
     133        5599 :       continue;
     134       12213 :     unsigned Reg = MO.getReg();
     135       24230 :     if (!TargetRegisterInfo::isPhysicalRegister(Reg) || isReserved(Reg))
     136        4565 :       continue;
     137             : 
     138        7648 :     if (MO.isUse()) {
     139             :       // Ignore undef uses.
     140        4032 :       if (MO.isUndef())
     141          41 :         continue;
     142        3991 :       if (MO.isKill())
     143        2169 :         addRegUnits(KillRegUnits, Reg);
     144             :     } else {
     145             :       assert(MO.isDef());
     146        3616 :       if (MO.isDead())
     147         565 :         addRegUnits(KillRegUnits, Reg);
     148             :       else
     149        3051 :         addRegUnits(DefRegUnits, Reg);
     150             :     }
     151             :   }
     152        4962 : }
     153             : 
     154           0 : void RegScavenger::unprocess() {
     155             :   assert(Tracking && "Cannot unprocess because we're not tracking");
     156             : 
     157           0 :   MachineInstr &MI = *MBBI;
     158           0 :   if (!MI.isDebugValue()) {
     159           0 :     determineKillsAndDefs();
     160             : 
     161             :     // Commit the changes.
     162           0 :     setUsed(KillRegUnits);
     163           0 :     setUnused(DefRegUnits);
     164             :   }
     165             : 
     166           0 :   if (MBBI == MBB->begin()) {
     167           0 :     MBBI = MachineBasicBlock::iterator(nullptr);
     168           0 :     Tracking = false;
     169             :   } else
     170           0 :     --MBBI;
     171           0 : }
     172             : 
     173        4962 : void RegScavenger::forward() {
     174             :   // Move ptr forward.
     175        4962 :   if (!Tracking) {
     176         798 :     MBBI = MBB->begin();
     177         399 :     Tracking = true;
     178             :   } else {
     179             :     assert(MBBI != MBB->end() && "Already past the end of the basic block!");
     180        4563 :     MBBI = std::next(MBBI);
     181             :   }
     182             :   assert(MBBI != MBB->end() && "Already at the end of the basic block!");
     183             : 
     184        9924 :   MachineInstr &MI = *MBBI;
     185             : 
     186       11265 :   for (SmallVectorImpl<ScavengedInfo>::iterator I = Scavenged.begin(),
     187        9924 :          IE = Scavenged.end(); I != IE; ++I) {
     188        1341 :     if (I->Restore != &MI)
     189        1338 :       continue;
     190             : 
     191           3 :     I->Reg = 0;
     192           3 :     I->Restore = nullptr;
     193             :   }
     194             : 
     195        4962 :   if (MI.isDebugValue())
     196             :     return;
     197             : 
     198        4962 :   determineKillsAndDefs();
     199             : 
     200             :   // Verify uses and defs.
     201             : #ifndef NDEBUG
     202             :   for (const MachineOperand &MO : MI.operands()) {
     203             :     if (!MO.isReg())
     204             :       continue;
     205             :     unsigned Reg = MO.getReg();
     206             :     if (!TargetRegisterInfo::isPhysicalRegister(Reg) || isReserved(Reg))
     207             :       continue;
     208             :     if (MO.isUse()) {
     209             :       if (MO.isUndef())
     210             :         continue;
     211             :       if (!isRegUsed(Reg)) {
     212             :         // Check if it's partial live: e.g.
     213             :         // D0 = insert_subreg D0<undef>, S0
     214             :         // ... D0
     215             :         // The problem is the insert_subreg could be eliminated. The use of
     216             :         // D0 is using a partially undef value. This is not *incorrect* since
     217             :         // S1 is can be freely clobbered.
     218             :         // Ideally we would like a way to model this, but leaving the
     219             :         // insert_subreg around causes both correctness and performance issues.
     220             :         bool SubUsed = false;
     221             :         for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs)
     222             :           if (isRegUsed(*SubRegs)) {
     223             :             SubUsed = true;
     224             :             break;
     225             :           }
     226             :         bool SuperUsed = false;
     227             :         for (MCSuperRegIterator SR(Reg, TRI); SR.isValid(); ++SR) {
     228             :           if (isRegUsed(*SR)) {
     229             :             SuperUsed = true;
     230             :             break;
     231             :           }
     232             :         }
     233             :         if (!SubUsed && !SuperUsed) {
     234             :           MBB->getParent()->verify(nullptr, "In Register Scavenger");
     235             :           llvm_unreachable("Using an undefined register!");
     236             :         }
     237             :         (void)SubUsed;
     238             :         (void)SuperUsed;
     239             :       }
     240             :     } else {
     241             :       assert(MO.isDef());
     242             : #if 0
     243             :       // FIXME: Enable this once we've figured out how to correctly transfer
     244             :       // implicit kills during codegen passes like the coalescer.
     245             :       assert((KillRegs.test(Reg) || isUnused(Reg) ||
     246             :               isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) &&
     247             :              "Re-defining a live register!");
     248             : #endif
     249             :     }
     250             :   }
     251             : #endif // NDEBUG
     252             : 
     253             :   // Commit the changes.
     254        9924 :   setUnused(KillRegUnits);
     255        4962 :   setUsed(DefRegUnits);
     256             : }
     257             : 
     258       39553 : void RegScavenger::backward() {
     259             :   assert(Tracking && "Must be tracking to determine kills and defs");
     260             : 
     261       79106 :   const MachineInstr &MI = *MBBI;
     262       39553 :   LiveUnits.stepBackward(MI);
     263             : 
     264             :   // Expire scavenge spill frameindex uses.
     265      141546 :   for (ScavengedInfo &I : Scavenged) {
     266       22887 :     if (I.Restore == &MI) {
     267          21 :       I.Reg = 0;
     268          21 :       I.Restore = nullptr;
     269             :     }
     270             :   }
     271             : 
     272      118659 :   if (MBBI == MBB->begin()) {
     273           0 :     MBBI = MachineBasicBlock::iterator(nullptr);
     274           0 :     Tracking = false;
     275             :   } else
     276       39553 :     --MBBI;
     277       39553 : }
     278             : 
     279        2645 : bool RegScavenger::isRegUsed(unsigned Reg, bool includeReserved) const {
     280        5290 :   if (isReserved(Reg))
     281             :     return includeReserved;
     282        2177 :   return !LiveUnits.available(Reg);
     283             : }
     284             : 
     285           0 : unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RC) const {
     286           0 :   for (unsigned Reg : *RC) {
     287           0 :     if (!isRegUsed(Reg)) {
     288             :       DEBUG(dbgs() << "Scavenger found unused reg: " << TRI->getName(Reg) <<
     289             :             "\n");
     290             :       return Reg;
     291             :     }
     292             :   }
     293             :   return 0;
     294             : }
     295             : 
     296          66 : BitVector RegScavenger::getRegsAvailable(const TargetRegisterClass *RC) {
     297          66 :   BitVector Mask(TRI->getNumRegs());
     298        2535 :   for (unsigned Reg : *RC)
     299        2337 :     if (!isRegUsed(Reg))
     300             :       Mask.set(Reg);
     301          66 :   return Mask;
     302             : }
     303             : 
     304          63 : unsigned RegScavenger::findSurvivorReg(MachineBasicBlock::iterator StartMI,
     305             :                                        BitVector &Candidates,
     306             :                                        unsigned InstrLimit,
     307             :                                        MachineBasicBlock::iterator &UseMI) {
     308          63 :   int Survivor = Candidates.find_first();
     309             :   assert(Survivor > 0 && "No candidates for scavenging");
     310             : 
     311          63 :   MachineBasicBlock::iterator ME = MBB->getFirstTerminator();
     312             :   assert(StartMI != ME && "MI already at terminator");
     313          63 :   MachineBasicBlock::iterator RestorePointMI = StartMI;
     314          63 :   MachineBasicBlock::iterator MI = StartMI;
     315             : 
     316          63 :   bool inVirtLiveRange = false;
     317         906 :   for (++MI; InstrLimit > 0 && MI != ME; ++MI, --InstrLimit) {
     318         552 :     if (MI->isDebugValue()) {
     319           0 :       ++InstrLimit; // Don't count debug instructions
     320           0 :       continue;
     321             :     }
     322         276 :     bool isVirtKillInsn = false;
     323         276 :     bool isVirtDefInsn = false;
     324             :     // Remove any candidates touched by instruction.
     325        1422 :     for (const MachineOperand &MO : MI->operands()) {
     326         870 :       if (MO.isRegMask())
     327           0 :         Candidates.clearBitsNotInMask(MO.getRegMask());
     328        1740 :       if (!MO.isReg() || MO.isUndef() || !MO.getReg())
     329         319 :         continue;
     330        1218 :       if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) {
     331         116 :         if (MO.isDef())
     332             :           isVirtDefInsn = true;
     333          58 :         else if (MO.isKill())
     334           0 :           isVirtKillInsn = true;
     335         116 :         continue;
     336             :       }
     337        1740 :       for (MCRegAliasIterator AI(MO.getReg(), TRI, true); AI.isValid(); ++AI)
     338         870 :         Candidates.reset(*AI);
     339             :     }
     340             :     // If we're not in a virtual reg's live range, this is a valid
     341             :     // restore point.
     342         276 :     if (!inVirtLiveRange) RestorePointMI = MI;
     343             : 
     344             :     // Update whether we're in the live range of a virtual register
     345         276 :     if (isVirtKillInsn) inVirtLiveRange = false;
     346         276 :     if (isVirtDefInsn) inVirtLiveRange = true;
     347             : 
     348             :     // Was our survivor untouched by this instruction?
     349         552 :     if (Candidates.test(Survivor))
     350         216 :       continue;
     351             : 
     352             :     // All candidates gone?
     353          60 :     if (Candidates.none())
     354             :       break;
     355             : 
     356          44 :     Survivor = Candidates.find_first();
     357             :   }
     358             :   // If we ran off the end, that's where we want to restore.
     359          63 :   if (MI == ME) RestorePointMI = ME;
     360             :   assert(RestorePointMI != StartMI &&
     361             :          "No available scavenger restore location!");
     362             : 
     363             :   // We ran out of candidates, so stop the search.
     364          63 :   UseMI = RestorePointMI;
     365          63 :   return Survivor;
     366             : }
     367             : 
     368             : /// Given the bitvector \p Available of free register units at position
     369             : /// \p From. Search backwards to find a register that is part of \p
     370             : /// Candidates and not used/clobbered until the point \p To. If there is
     371             : /// multiple candidates continue searching and pick the one that is not used/
     372             : /// clobbered for the longest time.
     373             : /// Returns the register and the earliest position we know it to be free or
     374             : /// the position MBB.end() if no register is available.
     375             : static std::pair<MCPhysReg, MachineBasicBlock::iterator>
     376        3468 : findSurvivorBackwards(const MachineRegisterInfo &MRI,
     377             :     MachineBasicBlock::iterator From, MachineBasicBlock::iterator To,
     378             :     const LiveRegUnits &LiveOut, ArrayRef<MCPhysReg> AllocationOrder,
     379             :     bool RestoreAfter) {
     380        3468 :   bool FoundTo = false;
     381        3468 :   MCPhysReg Survivor = 0;
     382        3468 :   MachineBasicBlock::iterator Pos;
     383        3468 :   MachineBasicBlock &MBB = *From->getParent();
     384        3468 :   unsigned InstrLimit = 25;
     385        3468 :   unsigned InstrCountDown = InstrLimit;
     386        6936 :   const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
     387        6936 :   LiveRegUnits Used(TRI);
     388             : 
     389        3468 :   for (MachineBasicBlock::iterator I = From;; --I) {
     390        4165 :     const MachineInstr &MI = *I;
     391             : 
     392        4165 :     Used.accumulate(MI);
     393             : 
     394        4165 :     if (I == To) {
     395             :       // See if one of the registers in RC wasn't used so far.
     396       12569 :       for (MCPhysReg Reg : AllocationOrder) {
     397       26525 :         if (!MRI.isReserved(Reg) && Used.available(Reg) &&
     398        8369 :             LiveOut.available(Reg))
     399        6890 :           return std::make_pair(Reg, MBB.end());
     400             :       }
     401             :       // Otherwise we will continue up to InstrLimit instructions to find
     402             :       // the register which is not defined/used for the longest time.
     403          23 :       FoundTo = true;
     404          23 :       Pos = To;
     405             :       // Note: It was fine so far to start our search at From, however now that
     406             :       // we have to spill, and can only place the restore after From then
     407             :       // add the regs used/defed by std::next(From) to the set.
     408          23 :       if (RestoreAfter)
     409          46 :         Used.accumulate(*std::next(From));
     410             :     }
     411         697 :     if (FoundTo) {
     412         365 :       if (Survivor == 0 || !Used.available(Survivor)) {
     413          48 :         MCPhysReg AvilableReg = 0;
     414         344 :         for (MCPhysReg Reg : AllocationOrder) {
     415         574 :           if (!MRI.isReserved(Reg) && Used.available(Reg)) {
     416             :             AvilableReg = Reg;
     417             :             break;
     418             :           }
     419             :         }
     420          48 :         if (AvilableReg == 0)
     421             :           break;
     422             :         Survivor = AvilableReg;
     423             :       }
     424         356 :       if (--InstrCountDown == 0)
     425             :         break;
     426             : 
     427             :       // Keep searching when we find a vreg since the spilled register will
     428             :       // be usefull for this other vreg as well later.
     429         352 :       bool FoundVReg = false;
     430        1212 :       for (const MachineOperand &MO : MI.operands()) {
     431        1588 :         if (MO.isReg() && TargetRegisterInfo::isVirtualRegister(MO.getReg())) {
     432             :           FoundVReg = true;
     433             :           break;
     434             :         }
     435             :       }
     436         352 :       if (FoundVReg) {
     437          45 :         InstrCountDown = InstrLimit;
     438          45 :         Pos = I;
     439             :       }
     440         704 :       if (I == MBB.begin())
     441             :         break;
     442             :     }
     443             :   }
     444             : 
     445          23 :   return std::make_pair(Survivor, Pos);
     446             : }
     447             : 
     448             : static unsigned getFrameIndexOperandNum(MachineInstr &MI) {
     449             :   unsigned i = 0;
     450         300 :   while (!MI.getOperand(i).isFI()) {
     451          52 :     ++i;
     452             :     assert(i < MI.getNumOperands() && "Instr doesn't have FrameIndex operand!");
     453             :   }
     454             :   return i;
     455             : }
     456             : 
     457             : RegScavenger::ScavengedInfo &
     458          27 : RegScavenger::spill(unsigned Reg, const TargetRegisterClass &RC, int SPAdj,
     459             :                     MachineBasicBlock::iterator Before,
     460             :                     MachineBasicBlock::iterator &UseMI) {
     461             :   // Find an available scavenging slot with size and alignment matching
     462             :   // the requirements of the class RC.
     463          27 :   const MachineFunction &MF = *Before->getParent()->getParent();
     464          27 :   const MachineFrameInfo &MFI = MF.getFrameInfo();
     465          54 :   unsigned NeedSize = TRI->getSpillSize(RC);
     466          54 :   unsigned NeedAlign = TRI->getSpillAlignment(RC);
     467             : 
     468          54 :   unsigned SI = Scavenged.size(), Diff = std::numeric_limits<unsigned>::max();
     469          54 :   int FIB = MFI.getObjectIndexBegin(), FIE = MFI.getObjectIndexEnd();
     470         136 :   for (unsigned I = 0; I < Scavenged.size(); ++I) {
     471          82 :     if (Scavenged[I].Reg != 0)
     472           1 :       continue;
     473             :     // Verify that this slot is valid for this register.
     474          80 :     int FI = Scavenged[I].FrameIndex;
     475          40 :     if (FI < FIB || FI >= FIE)
     476           1 :       continue;
     477          39 :     unsigned S = MFI.getObjectSize(FI);
     478          39 :     unsigned A = MFI.getObjectAlignment(FI);
     479          39 :     if (NeedSize > S || NeedAlign > A)
     480           0 :       continue;
     481             :     // Avoid wasting slots with large size and/or large alignment. Pick one
     482             :     // that is the best fit for this register class (in street metric).
     483             :     // Picking a larger slot than necessary could happen if a slot for a
     484             :     // larger register is reserved before a slot for a smaller one. When
     485             :     // trying to spill a smaller register, the large slot would be found
     486             :     // first, thus making it impossible to spill the larger register later.
     487          39 :     unsigned D = (S-NeedSize) + (A-NeedAlign);
     488          39 :     if (D < Diff) {
     489          24 :       SI = I;
     490          24 :       Diff = D;
     491             :     }
     492             :   }
     493             : 
     494          54 :   if (SI == Scavenged.size()) {
     495             :     // We need to scavenge a register but have no spill slot, the target
     496             :     // must know how to do it (if not, we'll assert below).
     497           6 :     Scavenged.push_back(ScavengedInfo(FIE));
     498             :   }
     499             : 
     500             :   // Avoid infinite regress
     501          54 :   Scavenged[SI].Reg = Reg;
     502             : 
     503             :   // If the target knows how to save/restore the register, let it do so;
     504             :   // otherwise, use the emergency stack spill slot.
     505          27 :   if (!TRI->saveScavengerRegister(*MBB, Before, UseMI, &RC, Reg)) {
     506             :     // Spill the scavenged register before \p Before.
     507          50 :     int FI = Scavenged[SI].FrameIndex;
     508          25 :     if (FI < FIB || FI >= FIE) {
     509           6 :       std::string Msg = std::string("Error while trying to spill ") +
     510           5 :           TRI->getName(Reg) + " from class " + TRI->getRegClassName(&RC) +
     511           1 :           ": Cannot scavenge register without an emergency spill slot!";
     512           1 :       report_fatal_error(Msg.c_str());
     513             :     }
     514          72 :     TII->storeRegToStackSlot(*MBB, Before, Reg, true, Scavenged[SI].FrameIndex,
     515          24 :                              &RC, TRI);
     516          24 :     MachineBasicBlock::iterator II = std::prev(Before);
     517             : 
     518          48 :     unsigned FIOperandNum = getFrameIndexOperandNum(*II);
     519          24 :     TRI->eliminateFrameIndex(II, SPAdj, FIOperandNum, this);
     520             : 
     521             :     // Restore the scavenged register before its use (or first terminator).
     522          72 :     TII->loadRegFromStackSlot(*MBB, UseMI, Reg, Scavenged[SI].FrameIndex,
     523          24 :                               &RC, TRI);
     524          24 :     II = std::prev(UseMI);
     525             : 
     526          48 :     FIOperandNum = getFrameIndexOperandNum(*II);
     527          24 :     TRI->eliminateFrameIndex(II, SPAdj, FIOperandNum, this);
     528             :   }
     529          52 :   return Scavenged[SI];
     530             : }
     531             : 
     532          63 : unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC,
     533             :                                         MachineBasicBlock::iterator I,
     534             :                                         int SPAdj) {
     535          63 :   MachineInstr &MI = *I;
     536          63 :   const MachineFunction &MF = *MI.getParent()->getParent();
     537             :   // Consider all allocatable registers in the register class initially
     538         125 :   BitVector Candidates = TRI->getAllocatableSet(MF, RC);
     539             : 
     540             :   // Exclude all the registers being used by the instruction.
     541         194 :   for (const MachineOperand &MO : MI.operands()) {
     542         277 :     if (MO.isReg() && MO.getReg() != 0 && !(MO.isUse() && MO.isUndef()) &&
     543         126 :         !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
     544         136 :       for (MCRegAliasIterator AI(MO.getReg(), TRI, true); AI.isValid(); ++AI)
     545          68 :         Candidates.reset(*AI);
     546             :   }
     547             : 
     548             :   // Try to find a register that's unused if there is one, as then we won't
     549             :   // have to spill.
     550         125 :   BitVector Available = getRegsAvailable(RC);
     551          63 :   Available &= Candidates;
     552          63 :   if (Available.any())
     553          59 :     Candidates = Available;
     554             : 
     555             :   // Find the register whose use is furthest away.
     556          63 :   MachineBasicBlock::iterator UseMI;
     557          63 :   unsigned SReg = findSurvivorReg(I, Candidates, 25, UseMI);
     558             : 
     559             :   // If we found an unused register there is no reason to spill it.
     560          63 :   if (!isRegUsed(SReg)) {
     561             :     DEBUG(dbgs() << "Scavenged register: " << TRI->getName(SReg) << "\n");
     562             :     return SReg;
     563             :   }
     564             : 
     565           4 :   ScavengedInfo &Scavenged = spill(SReg, *RC, SPAdj, I, UseMI);
     566           6 :   Scavenged.Restore = &*std::prev(UseMI);
     567             : 
     568             :   DEBUG(dbgs() << "Scavenged register (with spill): " << TRI->getName(SReg) <<
     569             :         "\n");
     570             : 
     571           3 :   return SReg;
     572             : }
     573             : 
     574        3468 : unsigned RegScavenger::scavengeRegisterBackwards(const TargetRegisterClass &RC,
     575             :                                                  MachineBasicBlock::iterator To,
     576             :                                                  bool RestoreAfter, int SPAdj) {
     577        3468 :   const MachineBasicBlock &MBB = *To->getParent();
     578        3468 :   const MachineFunction &MF = *MBB.getParent();
     579             : 
     580             :   // Find the register whose use is furthest away.
     581        3468 :   MachineBasicBlock::iterator UseMI;
     582        3468 :   ArrayRef<MCPhysReg> AllocationOrder = RC.getRawAllocationOrder(MF);
     583             :   std::pair<MCPhysReg, MachineBasicBlock::iterator> P =
     584        3468 :       findSurvivorBackwards(*MRI, MBBI, To, LiveUnits, AllocationOrder,
     585        6936 :                             RestoreAfter);
     586        3468 :   MCPhysReg Reg = P.first;
     587        3468 :   MachineBasicBlock::iterator SpillBefore = P.second;
     588             :   assert(Reg != 0 && "No register left to scavenge!");
     589             :   // Found an available register?
     590       10404 :   if (SpillBefore != MBB.end()) {
     591             :     MachineBasicBlock::iterator ReloadAfter =
     592          46 :       RestoreAfter ? std::next(MBBI) : MBBI;
     593          23 :     MachineBasicBlock::iterator ReloadBefore = std::next(ReloadAfter);
     594             :     DEBUG(dbgs() << "Reload before: " << *ReloadBefore << '\n');
     595          23 :     ScavengedInfo &Scavenged = spill(Reg, RC, SPAdj, SpillBefore, ReloadBefore);
     596          46 :     Scavenged.Restore = &*std::prev(SpillBefore);
     597          23 :     LiveUnits.removeReg(Reg);
     598             :     DEBUG(dbgs() << "Scavenged register with spill: " << PrintReg(Reg, TRI)
     599             :           << " until " << *SpillBefore);
     600             :   } else {
     601             :     DEBUG(dbgs() << "Scavenged free register: " << PrintReg(Reg, TRI) << '\n');
     602             :   }
     603        3468 :   return Reg;
     604             : }
     605             : 
     606             : /// Allocate a register for the virtual register \p VReg. The last use of
     607             : /// \p VReg is around the current position of the register scavenger \p RS.
     608             : /// \p ReserveAfter controls whether the scavenged register needs to be reserved
     609             : /// after the current instruction, otherwise it will only be reserved before the
     610             : /// current instruction.
     611        3468 : static unsigned scavengeVReg(MachineRegisterInfo &MRI, RegScavenger &RS,
     612             :                              unsigned VReg, bool ReserveAfter) {
     613        6936 :   const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
     614             : #ifndef NDEBUG
     615             :   // Verify that all definitions and uses are in the same basic block.
     616             :   const MachineBasicBlock *CommonMBB = nullptr;
     617             :   // Real definition for the reg, re-definitions are not considered.
     618             :   const MachineInstr *RealDef = nullptr;
     619             :   for (MachineOperand &MO : MRI.reg_nodbg_operands(VReg)) {
     620             :     MachineBasicBlock *MBB = MO.getParent()->getParent();
     621             :     if (CommonMBB == nullptr)
     622             :       CommonMBB = MBB;
     623             :     assert(MBB == CommonMBB && "All defs+uses must be in the same basic block");
     624             :     if (MO.isDef()) {
     625             :       const MachineInstr &MI = *MO.getParent();
     626             :       if (!MI.readsRegister(VReg, &TRI)) {
     627             :         assert((!RealDef || RealDef == &MI) &&
     628             :                "Can have at most one definition which is not a redefinition");
     629             :         RealDef = &MI;
     630             :       }
     631             :     }
     632             :   }
     633             :   assert(RealDef != nullptr && "Must have at least 1 Def");
     634             : #endif
     635             : 
     636             :   // We should only have one definition of the register. However to accommodate
     637             :   // the requirements of two address code we also allow definitions in
     638             :   // subsequent instructions provided they also read the register. That way
     639             :   // we get a single contiguous lifetime.
     640             :   //
     641             :   // Definitions in MRI.def_begin() are unordered, search for the first.
     642             :   MachineRegisterInfo::def_iterator FirstDef =
     643             :     std::find_if(MRI.def_begin(VReg), MRI.def_end(),
     644        3700 :                  [VReg, &TRI](const MachineOperand &MO) {
     645        3700 :       return !MO.getParent()->readsRegister(VReg, &TRI);
     646        6936 :     });
     647             :   assert(FirstDef != MRI.def_end() &&
     648             :          "Must have one definition that does not redefine vreg");
     649        3468 :   MachineInstr &DefMI = *FirstDef->getParent();
     650             : 
     651             :   // The register scavenger will report a free register inserting an emergency
     652             :   // spill/reload if necessary.
     653        3468 :   int SPAdj = 0;
     654        3468 :   const TargetRegisterClass &RC = *MRI.getRegClass(VReg);
     655       13872 :   unsigned SReg = RS.scavengeRegisterBackwards(RC, DefMI.getIterator(),
     656        3468 :                                                ReserveAfter, SPAdj);
     657        3468 :   MRI.replaceRegWith(VReg, SReg);
     658        3468 :   ++NumScavengedRegs;
     659        3468 :   return SReg;
     660             : }
     661             : 
     662             : /// Allocate (scavenge) vregs inside a single basic block.
     663             : /// Returns true if the target spill callback created new vregs and a 2nd pass
     664             : /// is necessary.
     665        1378 : static bool scavengeFrameVirtualRegsInBlock(MachineRegisterInfo &MRI,
     666             :                                             RegScavenger &RS,
     667             :                                             MachineBasicBlock &MBB) {
     668        2756 :   const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
     669        1378 :   RS.enterBasicBlockEnd(MBB);
     670             : 
     671        1378 :   unsigned InitialNumVirtRegs = MRI.getNumVirtRegs();
     672        1378 :   bool NextInstructionReadsVReg = false;
     673       85996 :   for (MachineBasicBlock::iterator I = MBB.end(); I != MBB.begin(); ) {
     674       40931 :     --I;
     675             :     // Move RegScavenger to the position between *I and *std::next(I).
     676       40931 :     RS.backward(I);
     677             : 
     678             :     // Look for unassigned vregs in the uses of *std::next(I).
     679       40931 :     if (NextInstructionReadsVReg) {
     680        3427 :       MachineBasicBlock::iterator N = std::next(I);
     681        3427 :       const MachineInstr &NMI = *N;
     682       18255 :       for (const MachineOperand &MO : NMI.operands()) {
     683       14828 :         if (!MO.isReg())
     684        4444 :           continue;
     685       10384 :         unsigned Reg = MO.getReg();
     686             :         // We only care about virtual registers and ignore virtual registers
     687             :         // created by the target callbacks in the process (those will be handled
     688             :         // in a scavenging round).
     689       13830 :         if (!TargetRegisterInfo::isVirtualRegister(Reg) ||
     690        3446 :             TargetRegisterInfo::virtReg2Index(Reg) >= InitialNumVirtRegs)
     691        6938 :           continue;
     692           0 :         if (!MO.readsReg())
     693           0 :           continue;
     694             : 
     695        3446 :         unsigned SReg = scavengeVReg(MRI, RS, Reg, true);
     696        3446 :         N->addRegisterKilled(SReg, &TRI, false);
     697        3446 :         RS.setRegUsed(SReg);
     698             :       }
     699             :     }
     700             : 
     701             :     // Look for unassigned vregs in the defs of *I.
     702       40931 :     NextInstructionReadsVReg = false;
     703       40931 :     const MachineInstr &MI = *I;
     704      196720 :     for (const MachineOperand &MO : MI.operands()) {
     705      155789 :       if (!MO.isReg())
     706       54482 :         continue;
     707      101307 :       unsigned Reg = MO.getReg();
     708             :       // Only vregs, no newly created vregs (see above).
     709      202614 :       if (!TargetRegisterInfo::isVirtualRegister(Reg) ||
     710        3468 :           TargetRegisterInfo::virtReg2Index(Reg) >= InitialNumVirtRegs)
     711       97839 :         continue;
     712             :       // We have to look at all operands anyway so we can precalculate here
     713             :       // whether there is a reading operand. This allows use to skip the use
     714             :       // step in the next iteration if there was none.
     715             :       assert(!MO.isInternalRead() && "Cannot assign inside bundles");
     716             :       assert((!MO.isUndef() || MO.isDef()) && "Cannot handle undef uses");
     717          22 :       if (MO.readsReg()) {
     718             :         NextInstructionReadsVReg = true;
     719             :       }
     720        3468 :       if (MO.isDef()) {
     721          22 :         unsigned SReg = scavengeVReg(MRI, RS, Reg, false);
     722          22 :         I->addRegisterDead(SReg, &TRI, false);
     723             :       }
     724             :     }
     725             :   }
     726             : #ifndef NDEBUG
     727             :   for (const MachineOperand &MO : MBB.front().operands()) {
     728             :     if (!MO.isReg() || !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
     729             :       continue;
     730             :     assert(!MO.isInternalRead() && "Cannot assign inside bundles");
     731             :     assert((!MO.isUndef() || MO.isDef()) && "Cannot handle undef uses");
     732             :     assert(!MO.readsReg() && "Vreg use in first instruction not allowed");
     733             :   }
     734             : #endif
     735             : 
     736        1378 :   return MRI.getNumVirtRegs() != InitialNumVirtRegs;
     737             : }
     738             : 
     739       53022 : void llvm::scavengeFrameVirtualRegs(MachineFunction &MF, RegScavenger &RS) {
     740             :   // FIXME: Iterating over the instruction stream is unnecessary. We can simply
     741             :   // iterate over the vreg use list, which at this point only contains machine
     742             :   // operands for which eliminateFrameIndex need a new scratch reg.
     743       53022 :   MachineRegisterInfo &MRI = MF.getRegInfo();
     744             :   // Shortcut.
     745       53022 :   if (MRI.getNumVirtRegs() == 0) {
     746       52521 :     MF.getProperties().set(MachineFunctionProperties::Property::NoVRegs);
     747             :     return;
     748             :   }
     749             : 
     750             :   // Run through the instructions and find any virtual registers.
     751        2956 :   for (MachineBasicBlock &MBB : MF) {
     752        1453 :     if (MBB.empty())
     753          75 :       continue;
     754             : 
     755        1378 :     bool Again = scavengeFrameVirtualRegsInBlock(MRI, RS, MBB);
     756        1378 :     if (Again) {
     757             :       DEBUG(dbgs() << "Warning: Required two scavenging passes for block "
     758             :             << MBB.getName() << '\n');
     759           0 :       Again = scavengeFrameVirtualRegsInBlock(MRI, RS, MBB);
     760             :       // The target required a 2nd run (because it created new vregs while
     761             :       // spilling). Refuse to do another pass to keep compiletime in check.
     762           0 :       if (Again)
     763           0 :         report_fatal_error("Incomplete scavenging after 2nd pass");
     764             :     }
     765             :   }
     766             : 
     767         501 :   MRI.clearVirtRegs();
     768         501 :   MF.getProperties().set(MachineFunctionProperties::Property::NoVRegs);
     769             : }
     770             : 
     771             : namespace {
     772             : /// This class runs register scavenging independ of the PrologEpilogInserter.
     773             : /// This is used in for testing.
     774           3 : class ScavengerTest : public MachineFunctionPass {
     775             : public:
     776             :   static char ID;
     777           3 :   ScavengerTest() : MachineFunctionPass(ID) {}
     778           7 :   bool runOnMachineFunction(MachineFunction &MF) {
     779           7 :     const TargetSubtargetInfo &STI = MF.getSubtarget();
     780           7 :     const TargetFrameLowering &TFL = *STI.getFrameLowering();
     781             : 
     782          14 :     RegScavenger RS;
     783             :     // Let's hope that calling those outside of PrologEpilogueInserter works
     784             :     // well enough to initialize the scavenger with some emergency spillslots
     785             :     // for the target.
     786          14 :     BitVector SavedRegs;
     787           7 :     TFL.determineCalleeSaves(MF, SavedRegs, &RS);
     788           7 :     TFL.processFunctionBeforeFrameFinalized(MF, &RS);
     789             : 
     790             :     // Let's scavenge the current function
     791           7 :     scavengeFrameVirtualRegs(MF, RS);
     792          14 :     return true;
     793             :   }
     794             : };
     795             : char ScavengerTest::ID;
     796             : 
     797             : } // end anonymous namespace
     798             : 
     799       82825 : INITIALIZE_PASS(ScavengerTest, "scavenger-test",
     800             :                 "Scavenge virtual registers inside basic blocks", false, false)

Generated by: LCOV version 1.13