contrib/llvm/lib/CodeGen/RegisterScavenging.cpp

   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/ADT/BitVector.h"
  19 #include "llvm/ADT/SmallVector.h"
  20 #include "llvm/CodeGen/RegisterScavenging.h"
  21 #include "llvm/CodeGen/MachineBasicBlock.h"
  22 #include "llvm/CodeGen/MachineFrameInfo.h"
  23 #include "llvm/CodeGen/MachineFunction.h"
  24 #include "llvm/CodeGen/MachineInstr.h"
  25 #include "llvm/CodeGen/MachineOperand.h"
  26 #include "llvm/MC/MCRegisterInfo.h"
  27 #include "llvm/Support/Debug.h"
  28 #include "llvm/Support/ErrorHandling.h"
  29 #include "llvm/Support/raw_ostream.h"
  30 #include "llvm/Target/TargetInstrInfo.h"
  31 #include "llvm/Target/TargetRegisterInfo.h"
  32 #include "llvm/Target/TargetSubtargetInfo.h"
  33 #include <cassert>
  34 #include <iterator>
  35 #include <limits>
  36 #include <string>
  37
  38 using namespace llvm;
  39
  40 #define DEBUG_TYPE "reg-scavenging"
  41
  42 void RegScavenger::setRegUsed(unsigned Reg, LaneBitmask LaneMask) {
  43   LiveUnits.addRegMasked(Reg, LaneMask);
  44 }
  45
  46 void RegScavenger::init(MachineBasicBlock &MBB) {
  47   MachineFunction &MF = *MBB.getParent();
  48   TII = MF.getSubtarget().getInstrInfo();
  49   TRI = MF.getSubtarget().getRegisterInfo();
  50   MRI = &MF.getRegInfo();
  51   LiveUnits.init(*TRI);
  52
  53   assert((NumRegUnits == 0 || NumRegUnits == TRI->getNumRegUnits()) &&
  54          "Target changed?");
  55
  56   // Self-initialize.
  57   if (!this->MBB) {
  58     NumRegUnits = TRI->getNumRegUnits();
  59     KillRegUnits.resize(NumRegUnits);
  60     DefRegUnits.resize(NumRegUnits);
  61     TmpRegUnits.resize(NumRegUnits);
  62   }
  63   this->MBB = &MBB;
  64
  65   for (ScavengedInfo &SI : Scavenged) {
  66     SI.Reg = 0;
  67     SI.Restore = nullptr;
  68   }
  69
  70   Tracking = false;
  71 }
  72
  73 void RegScavenger::enterBasicBlock(MachineBasicBlock &MBB) {
  74   init(MBB);
  75   LiveUnits.addLiveIns(MBB);
  76 }
  77
  78 void RegScavenger::enterBasicBlockEnd(MachineBasicBlock &MBB) {
  79   init(MBB);
  80   LiveUnits.addLiveOuts(MBB);
  81
  82   // Move internal iterator at the last instruction of the block.
  83   if (MBB.begin() != MBB.end()) {
  84     MBBI = std::prev(MBB.end());
  85     Tracking = true;
  86   }
  87 }
  88
  89 void RegScavenger::addRegUnits(BitVector &BV, unsigned Reg) {
  90   for (MCRegUnitIterator RUI(Reg, TRI); RUI.isValid(); ++RUI)
  91     BV.set(*RUI);
  92 }
  93
  94 void RegScavenger::removeRegUnits(BitVector &BV, unsigned Reg) {
  95   for (MCRegUnitIterator RUI(Reg, TRI); RUI.isValid(); ++RUI)
  96     BV.reset(*RUI);
  97 }
  98
  99 void RegScavenger::determineKillsAndDefs() {
 100   assert(Tracking && "Must be tracking to determine kills and defs");
 101
 102   MachineInstr &MI = *MBBI;
 103   assert(!MI.isDebugValue() && "Debug values have no kills or defs");
 104
 105   // Find out which registers are early clobbered, killed, defined, and marked
 106   // def-dead in this instruction.
 107   KillRegUnits.reset();
 108   DefRegUnits.reset();
 109   for (const MachineOperand &MO : MI.operands()) {
 110     if (MO.isRegMask()) {
 111       TmpRegUnits.clear();
 112       for (unsigned RU = 0, RUEnd = TRI->getNumRegUnits(); RU != RUEnd; ++RU) {
 113         for (MCRegUnitRootIterator RURI(RU, TRI); RURI.isValid(); ++RURI) {
 114           if (MO.clobbersPhysReg(*RURI)) {
 115             TmpRegUnits.set(RU);
 116             break;
 117           }
 118         }
 119       }
 120
 121       // Apply the mask.
 122       KillRegUnits |= TmpRegUnits;
 123     }
 124     if (!MO.isReg())
 125       continue;
 126     unsigned Reg = MO.getReg();
 127     if (!TargetRegisterInfo::isPhysicalRegister(Reg) || isReserved(Reg))
 128       continue;
 129
 130     if (MO.isUse()) {
 131       // Ignore undef uses.
 132       if (MO.isUndef())
 133         continue;
 134       if (MO.isKill())
 135         addRegUnits(KillRegUnits, Reg);
 136     } else {
 137       assert(MO.isDef());
 138       if (MO.isDead())
 139         addRegUnits(KillRegUnits, Reg);
 140       else
 141         addRegUnits(DefRegUnits, Reg);
 142     }
 143   }
 144 }
 145
 146 void RegScavenger::unprocess() {
 147   assert(Tracking && "Cannot unprocess because we're not tracking");
 148
 149   MachineInstr &MI = *MBBI;
 150   if (!MI.isDebugValue()) {
 151     determineKillsAndDefs();
 152
 153     // Commit the changes.
 154     setUsed(KillRegUnits);
 155     setUnused(DefRegUnits);
 156   }
 157
 158   if (MBBI == MBB->begin()) {
 159     MBBI = MachineBasicBlock::iterator(nullptr);
 160     Tracking = false;
 161   } else
 162     --MBBI;
 163 }
 164
 165 void RegScavenger::forward() {
 166   // Move ptr forward.
 167   if (!Tracking) {
 168     MBBI = MBB->begin();
 169     Tracking = true;
 170   } else {
 171     assert(MBBI != MBB->end() && "Already past the end of the basic block!");
 172     MBBI = std::next(MBBI);
 173   }
 174   assert(MBBI != MBB->end() && "Already at the end of the basic block!");
 175
 176   MachineInstr &MI = *MBBI;
 177
 178   for (SmallVectorImpl<ScavengedInfo>::iterator I = Scavenged.begin(),
 179          IE = Scavenged.end(); I != IE; ++I) {
 180     if (I->Restore != &MI)
 181       continue;
 182
 183     I->Reg = 0;
 184     I->Restore = nullptr;
 185   }
 186
 187   if (MI.isDebugValue())
 188     return;
 189
 190   determineKillsAndDefs();
 191
 192   // Verify uses and defs.
 193 #ifndef NDEBUG
 194   for (const MachineOperand &MO : MI.operands()) {
 195     if (!MO.isReg())
 196       continue;
 197     unsigned Reg = MO.getReg();
 198     if (!TargetRegisterInfo::isPhysicalRegister(Reg) || isReserved(Reg))
 199       continue;
 200     if (MO.isUse()) {
 201       if (MO.isUndef())
 202         continue;
 203       if (!isRegUsed(Reg)) {
 204         // Check if it's partial live: e.g.
 205         // D0 = insert_subreg D0<undef>, S0
 206         // ... D0
 207         // The problem is the insert_subreg could be eliminated. The use of
 208         // D0 is using a partially undef value. This is not *incorrect* since
 209         // S1 is can be freely clobbered.
 210         // Ideally we would like a way to model this, but leaving the
 211         // insert_subreg around causes both correctness and performance issues.
 212         bool SubUsed = false;
 213         for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs)
 214           if (isRegUsed(*SubRegs)) {
 215             SubUsed = true;
 216             break;
 217           }
 218         bool SuperUsed = false;
 219         for (MCSuperRegIterator SR(Reg, TRI); SR.isValid(); ++SR) {
 220           if (isRegUsed(*SR)) {
 221             SuperUsed = true;
 222             break;
 223           }
 224         }
 225         if (!SubUsed && !SuperUsed) {
 226           MBB->getParent()->verify(nullptr, "In Register Scavenger");
 227           llvm_unreachable("Using an undefined register!");
 228         }
 229         (void)SubUsed;
 230         (void)SuperUsed;
 231       }
 232     } else {
 233       assert(MO.isDef());
 234 #if 0
 235       // FIXME: Enable this once we've figured out how to correctly transfer
 236       // implicit kills during codegen passes like the coalescer.
 237       assert((KillRegs.test(Reg) || isUnused(Reg) ||
 238               isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) &&
 239              "Re-defining a live register!");
 240 #endif
 241     }
 242   }
 243 #endif // NDEBUG
 244
 245   // Commit the changes.
 246   setUnused(KillRegUnits);
 247   setUsed(DefRegUnits);
 248 }
 249
 250 void RegScavenger::backward() {
 251   assert(Tracking && "Must be tracking to determine kills and defs");
 252
 253   const MachineInstr &MI = *MBBI;
 254   LiveUnits.stepBackward(MI);
 255
 256   if (MBBI == MBB->begin()) {
 257     MBBI = MachineBasicBlock::iterator(nullptr);
 258     Tracking = false;
 259   } else
 260     --MBBI;
 261 }
 262
 263 bool RegScavenger::isRegUsed(unsigned Reg, bool includeReserved) const {
 264   if (isReserved(Reg))
 265     return includeReserved;
 266   return !LiveUnits.available(Reg);
 267 }
 268
 269 unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RC) const {
 270   for (unsigned Reg : *RC) {
 271     if (!isRegUsed(Reg)) {
 272       DEBUG(dbgs() << "Scavenger found unused reg: " << TRI->getName(Reg) <<
 273             "\n");
 274       return Reg;
 275     }
 276   }
 277   return 0;
 278 }
 279
 280 BitVector RegScavenger::getRegsAvailable(const TargetRegisterClass *RC) {
 281   BitVector Mask(TRI->getNumRegs());
 282   for (unsigned Reg : *RC)
 283     if (!isRegUsed(Reg))
 284       Mask.set(Reg);
 285   return Mask;
 286 }
 287
 288 unsigned RegScavenger::findSurvivorReg(MachineBasicBlock::iterator StartMI,
 289                                        BitVector &Candidates,
 290                                        unsigned InstrLimit,
 291                                        MachineBasicBlock::iterator &UseMI) {
 292   int Survivor = Candidates.find_first();
 293   assert(Survivor > 0 && "No candidates for scavenging");
 294
 295   MachineBasicBlock::iterator ME = MBB->getFirstTerminator();
 296   assert(StartMI != ME && "MI already at terminator");
 297   MachineBasicBlock::iterator RestorePointMI = StartMI;
 298   MachineBasicBlock::iterator MI = StartMI;
 299
 300   bool inVirtLiveRange = false;
 301   for (++MI; InstrLimit > 0 && MI != ME; ++MI, --InstrLimit) {
 302     if (MI->isDebugValue()) {
 303       ++InstrLimit; // Don't count debug instructions
 304       continue;
 305     }
 306     bool isVirtKillInsn = false;
 307     bool isVirtDefInsn = false;
 308     // Remove any candidates touched by instruction.
 309     for (const MachineOperand &MO : MI->operands()) {
 310       if (MO.isRegMask())
 311         Candidates.clearBitsNotInMask(MO.getRegMask());
 312       if (!MO.isReg() || MO.isUndef() || !MO.getReg())
 313         continue;
 314       if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) {
 315         if (MO.isDef())
 316           isVirtDefInsn = true;
 317         else if (MO.isKill())
 318           isVirtKillInsn = true;
 319         continue;
 320       }
 321       for (MCRegAliasIterator AI(MO.getReg(), TRI, true); AI.isValid(); ++AI)
 322         Candidates.reset(*AI);
 323     }
 324     // If we're not in a virtual reg's live range, this is a valid
 325     // restore point.
 326     if (!inVirtLiveRange) RestorePointMI = MI;
 327
 328     // Update whether we're in the live range of a virtual register
 329     if (isVirtKillInsn) inVirtLiveRange = false;
 330     if (isVirtDefInsn) inVirtLiveRange = true;
 331
 332     // Was our survivor untouched by this instruction?
 333     if (Candidates.test(Survivor))
 334       continue;
 335
 336     // All candidates gone?
 337     if (Candidates.none())
 338       break;
 339
 340     Survivor = Candidates.find_first();
 341   }
 342   // If we ran off the end, that's where we want to restore.
 343   if (MI == ME) RestorePointMI = ME;
 344   assert(RestorePointMI != StartMI &&
 345          "No available scavenger restore location!");
 346
 347   // We ran out of candidates, so stop the search.
 348   UseMI = RestorePointMI;
 349   return Survivor;
 350 }
 351
 352 static unsigned getFrameIndexOperandNum(MachineInstr &MI) {
 353   unsigned i = 0;
 354   while (!MI.getOperand(i).isFI()) {
 355     ++i;
 356     assert(i < MI.getNumOperands() && "Instr doesn't have FrameIndex operand!");
 357   }
 358   return i;
 359 }
 360
 361 unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC,
 362                                         MachineBasicBlock::iterator I,
 363                                         int SPAdj) {
 364   MachineInstr &MI = *I;
 365   const MachineFunction &MF = *MI.getParent()->getParent();
 366   // Consider all allocatable registers in the register class initially
 367   BitVector Candidates = TRI->getAllocatableSet(MF, RC);
 368
 369   // Exclude all the registers being used by the instruction.
 370   for (const MachineOperand &MO : MI.operands()) {
 371     if (MO.isReg() && MO.getReg() != 0 && !(MO.isUse() && MO.isUndef()) &&
 372         !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
 373       for (MCRegAliasIterator AI(MO.getReg(), TRI, true); AI.isValid(); ++AI)
 374         Candidates.reset(*AI);
 375   }
 376
 377   // Try to find a register that's unused if there is one, as then we won't
 378   // have to spill.
 379   BitVector Available = getRegsAvailable(RC);
 380   Available &= Candidates;
 381   if (Available.any())
 382     Candidates = Available;
 383
 384   // Find the register whose use is furthest away.
 385   MachineBasicBlock::iterator UseMI;
 386   unsigned SReg = findSurvivorReg(I, Candidates, 25, UseMI);
 387
 388   // If we found an unused register there is no reason to spill it.
 389   if (!isRegUsed(SReg)) {
 390     DEBUG(dbgs() << "Scavenged register: " << TRI->getName(SReg) << "\n");
 391     return SReg;
 392   }
 393
 394   // Find an available scavenging slot with size and alignment matching
 395   // the requirements of the class RC.
 396   const MachineFrameInfo &MFI = MF.getFrameInfo();
 397   unsigned NeedSize = TRI->getSpillSize(*RC);
 398   unsigned NeedAlign = TRI->getSpillAlignment(*RC);
 399
 400   unsigned SI = Scavenged.size(), Diff = std::numeric_limits<unsigned>::max();
 401   int FIB = MFI.getObjectIndexBegin(), FIE = MFI.getObjectIndexEnd();
 402   for (unsigned I = 0; I < Scavenged.size(); ++I) {
 403     if (Scavenged[I].Reg != 0)
 404       continue;
 405     // Verify that this slot is valid for this register.
 406     int FI = Scavenged[I].FrameIndex;
 407     if (FI < FIB || FI >= FIE)
 408       continue;
 409     unsigned S = MFI.getObjectSize(FI);
 410     unsigned A = MFI.getObjectAlignment(FI);
 411     if (NeedSize > S || NeedAlign > A)
 412       continue;
 413     // Avoid wasting slots with large size and/or large alignment. Pick one
 414     // that is the best fit for this register class (in street metric).
 415     // Picking a larger slot than necessary could happen if a slot for a
 416     // larger register is reserved before a slot for a smaller one. When
 417     // trying to spill a smaller register, the large slot would be found
 418     // first, thus making it impossible to spill the larger register later.
 419     unsigned D = (S-NeedSize) + (A-NeedAlign);
 420     if (D < Diff) {
 421       SI = I;
 422       Diff = D;
 423     }
 424   }
 425
 426   if (SI == Scavenged.size()) {
 427     // We need to scavenge a register but have no spill slot, the target
 428     // must know how to do it (if not, we'll assert below).
 429     Scavenged.push_back(ScavengedInfo(FIE));
 430   }
 431
 432   // Avoid infinite regress
 433   Scavenged[SI].Reg = SReg;
 434
 435   // If the target knows how to save/restore the register, let it do so;
 436   // otherwise, use the emergency stack spill slot.
 437   if (!TRI->saveScavengerRegister(*MBB, I, UseMI, RC, SReg)) {
 438     // Spill the scavenged register before I.
 439     int FI = Scavenged[SI].FrameIndex;
 440     if (FI < FIB || FI >= FIE) {
 441       std::string Msg = std::string("Error while trying to spill ") +
 442           TRI->getName(SReg) + " from class " + TRI->getRegClassName(RC) +
 443           ": Cannot scavenge register without an emergency spill slot!";
 444       report_fatal_error(Msg.c_str());
 445     }
 446     TII->storeRegToStackSlot(*MBB, I, SReg, true, Scavenged[SI].FrameIndex,
 447                              RC, TRI);
 448     MachineBasicBlock::iterator II = std::prev(I);
 449
 450     unsigned FIOperandNum = getFrameIndexOperandNum(*II);
 451     TRI->eliminateFrameIndex(II, SPAdj, FIOperandNum, this);
 452
 453     // Restore the scavenged register before its use (or first terminator).
 454     TII->loadRegFromStackSlot(*MBB, UseMI, SReg, Scavenged[SI].FrameIndex,
 455                               RC, TRI);
 456     II = std::prev(UseMI);
 457
 458     FIOperandNum = getFrameIndexOperandNum(*II);
 459     TRI->eliminateFrameIndex(II, SPAdj, FIOperandNum, this);
 460   }
 461
 462   Scavenged[SI].Restore = &*std::prev(UseMI);
 463
 464   // Doing this here leads to infinite regress.
 465   // Scavenged[SI].Reg = SReg;
 466
 467   DEBUG(dbgs() << "Scavenged register (with spill): " << TRI->getName(SReg) <<
 468         "\n");
 469
 470   return SReg;
 471 }