lib/CodeGen/MachineRegisterInfo.cpp

   1 //===-- lib/Codegen/MachineRegisterInfo.cpp -------------------------------===//
   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 // Implementation of the MachineRegisterInfo class.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/CodeGen/MachineRegisterInfo.h"
  15 #include "llvm/CodeGen/MachineInstrBuilder.h"
  16 #include "llvm/Target/TargetInstrInfo.h"
  17 #include "llvm/Target/TargetMachine.h"
  18 #include "llvm/Support/raw_os_ostream.h"
  19
  20 using namespace llvm;
  21
  22 // Pin the vtable to this file.
  23 void MachineRegisterInfo::Delegate::anchor() {}
  24
  25 MachineRegisterInfo::MachineRegisterInfo(const TargetMachine &TM)
  26   : TM(TM), TheDelegate(0), IsSSA(true), TracksLiveness(true) {
  27   VRegInfo.reserve(256);
  28   RegAllocHints.reserve(256);
  29   UsedRegUnits.resize(getTargetRegisterInfo()->getNumRegUnits());
  30   UsedPhysRegMask.resize(getTargetRegisterInfo()->getNumRegs());
  31
  32   // Create the physreg use/def lists.
  33   PhysRegUseDefLists =
  34     new MachineOperand*[getTargetRegisterInfo()->getNumRegs()];
  35   memset(PhysRegUseDefLists, 0,
  36          sizeof(MachineOperand*)*getTargetRegisterInfo()->getNumRegs());
  37 }
  38
  39 MachineRegisterInfo::~MachineRegisterInfo() {
  40   delete [] PhysRegUseDefLists;
  41 }
  42
  43 /// setRegClass - Set the register class of the specified virtual register.
  44 ///
  45 void
  46 MachineRegisterInfo::setRegClass(unsigned Reg, const TargetRegisterClass *RC) {
  47   assert(RC && RC->isAllocatable() && "Invalid RC for virtual register");
  48   VRegInfo[Reg].first = RC;
  49 }
  50
  51 const TargetRegisterClass *
  52 MachineRegisterInfo::constrainRegClass(unsigned Reg,
  53                                        const TargetRegisterClass *RC,
  54                                        unsigned MinNumRegs) {
  55   const TargetRegisterClass *OldRC = getRegClass(Reg);
  56   if (OldRC == RC)
  57     return RC;
  58   const TargetRegisterClass *NewRC =
  59     getTargetRegisterInfo()->getCommonSubClass(OldRC, RC);
  60   if (!NewRC || NewRC == OldRC)
  61     return NewRC;
  62   if (NewRC->getNumRegs() < MinNumRegs)
  63     return 0;
  64   setRegClass(Reg, NewRC);
  65   return NewRC;
  66 }
  67
  68 bool
  69 MachineRegisterInfo::recomputeRegClass(unsigned Reg, const TargetMachine &TM) {
  70   const TargetInstrInfo *TII = TM.getInstrInfo();
  71   const TargetRegisterClass *OldRC = getRegClass(Reg);
  72   const TargetRegisterClass *NewRC =
  73     getTargetRegisterInfo()->getLargestLegalSuperClass(OldRC);
  74
  75   // Stop early if there is no room to grow.
  76   if (NewRC == OldRC)
  77     return false;
  78
  79   // Accumulate constraints from all uses.
  80   for (reg_nodbg_iterator I = reg_nodbg_begin(Reg), E = reg_nodbg_end(); I != E;
  81        ++I) {
  82     const TargetRegisterClass *OpRC =
  83       I->getRegClassConstraint(I.getOperandNo(), TII,
  84                                getTargetRegisterInfo());
  85     if (unsigned SubIdx = I.getOperand().getSubReg()) {
  86       if (OpRC)
  87         NewRC = getTargetRegisterInfo()->getMatchingSuperRegClass(NewRC, OpRC,
  88                                                                   SubIdx);
  89       else
  90         NewRC = getTargetRegisterInfo()->getSubClassWithSubReg(NewRC, SubIdx);
  91     } else if (OpRC)
  92       NewRC = getTargetRegisterInfo()->getCommonSubClass(NewRC, OpRC);
  93     if (!NewRC || NewRC == OldRC)
  94       return false;
  95   }
  96   setRegClass(Reg, NewRC);
  97   return true;
  98 }
  99
 100 /// createVirtualRegister - Create and return a new virtual register in the
 101 /// function with the specified register class.
 102 ///
 103 unsigned
 104 MachineRegisterInfo::createVirtualRegister(const TargetRegisterClass *RegClass){
 105   assert(RegClass && "Cannot create register without RegClass!");
 106   assert(RegClass->isAllocatable() &&
 107          "Virtual register RegClass must be allocatable.");
 108
 109   // New virtual register number.
 110   unsigned Reg = TargetRegisterInfo::index2VirtReg(getNumVirtRegs());
 111   VRegInfo.grow(Reg);
 112   VRegInfo[Reg].first = RegClass;
 113   RegAllocHints.grow(Reg);
 114   if (TheDelegate)
 115     TheDelegate->MRI_NoteNewVirtualRegister(Reg);
 116   return Reg;
 117 }
 118
 119 /// clearVirtRegs - Remove all virtual registers (after physreg assignment).
 120 void MachineRegisterInfo::clearVirtRegs() {
 121 #ifndef NDEBUG
 122   for (unsigned i = 0, e = getNumVirtRegs(); i != e; ++i) {
 123     unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
 124     if (!VRegInfo[Reg].second)
 125       continue;
 126     verifyUseList(Reg);
 127     llvm_unreachable("Remaining virtual register operands");
 128   }
 129 #endif
 130   VRegInfo.clear();
 131 }
 132
 133 void MachineRegisterInfo::verifyUseList(unsigned Reg) const {
 134 #ifndef NDEBUG
 135   bool Valid = true;
 136   for (reg_iterator I = reg_begin(Reg), E = reg_end(); I != E; ++I) {
 137     MachineOperand *MO = &I.getOperand();
 138     MachineInstr *MI = MO->getParent();
 139     if (!MI) {
 140       errs() << PrintReg(Reg, getTargetRegisterInfo())
 141              << " use list MachineOperand " << MO
 142              << " has no parent instruction.\n";
 143       Valid = false;
 144     }
 145     MachineOperand *MO0 = &MI->getOperand(0);
 146     unsigned NumOps = MI->getNumOperands();
 147     if (!(MO >= MO0 && MO < MO0+NumOps)) {
 148       errs() << PrintReg(Reg, getTargetRegisterInfo())
 149              << " use list MachineOperand " << MO
 150              << " doesn't belong to parent MI: " << *MI;
 151       Valid = false;
 152     }
 153     if (!MO->isReg()) {
 154       errs() << PrintReg(Reg, getTargetRegisterInfo())
 155              << " MachineOperand " << MO << ": " << *MO
 156              << " is not a register\n";
 157       Valid = false;
 158     }
 159     if (MO->getReg() != Reg) {
 160       errs() << PrintReg(Reg, getTargetRegisterInfo())
 161              << " use-list MachineOperand " << MO << ": "
 162              << *MO << " is the wrong register\n";
 163       Valid = false;
 164     }
 165   }
 166   assert(Valid && "Invalid use list");
 167 #endif
 168 }
 169
 170 void MachineRegisterInfo::verifyUseLists() const {
 171 #ifndef NDEBUG
 172   for (unsigned i = 0, e = getNumVirtRegs(); i != e; ++i)
 173     verifyUseList(TargetRegisterInfo::index2VirtReg(i));
 174   for (unsigned i = 1, e = getTargetRegisterInfo()->getNumRegs(); i != e; ++i)
 175     verifyUseList(i);
 176 #endif
 177 }
 178
 179 /// Add MO to the linked list of operands for its register.
 180 void MachineRegisterInfo::addRegOperandToUseList(MachineOperand *MO) {
 181   assert(!MO->isOnRegUseList() && "Already on list");
 182   MachineOperand *&HeadRef = getRegUseDefListHead(MO->getReg());
 183   MachineOperand *const Head = HeadRef;
 184
 185   // Head points to the first list element.
 186   // Next is NULL on the last list element.
 187   // Prev pointers are circular, so Head->Prev == Last.
 188
 189   // Head is NULL for an empty list.
 190   if (!Head) {
 191     MO->Contents.Reg.Prev = MO;
 192     MO->Contents.Reg.Next = 0;
 193     HeadRef = MO;
 194     return;
 195   }
 196   assert(MO->getReg() == Head->getReg() && "Different regs on the same list!");
 197
 198   // Insert MO between Last and Head in the circular Prev chain.
 199   MachineOperand *Last = Head->Contents.Reg.Prev;
 200   assert(Last && "Inconsistent use list");
 201   assert(MO->getReg() == Last->getReg() && "Different regs on the same list!");
 202   Head->Contents.Reg.Prev = MO;
 203   MO->Contents.Reg.Prev = Last;
 204
 205   // Def operands always precede uses. This allows def_iterator to stop early.
 206   // Insert def operands at the front, and use operands at the back.
 207   if (MO->isDef()) {
 208     // Insert def at the front.
 209     MO->Contents.Reg.Next = Head;
 210     HeadRef = MO;
 211   } else {
 212     // Insert use at the end.
 213     MO->Contents.Reg.Next = 0;
 214     Last->Contents.Reg.Next = MO;
 215   }
 216 }
 217
 218 /// Remove MO from its use-def list.
 219 void MachineRegisterInfo::removeRegOperandFromUseList(MachineOperand *MO) {
 220   assert(MO->isOnRegUseList() && "Operand not on use list");
 221   MachineOperand *&HeadRef = getRegUseDefListHead(MO->getReg());
 222   MachineOperand *const Head = HeadRef;
 223   assert(Head && "List already empty");
 224
 225   // Unlink this from the doubly linked list of operands.
 226   MachineOperand *Next = MO->Contents.Reg.Next;
 227   MachineOperand *Prev = MO->Contents.Reg.Prev;
 228
 229   // Prev links are circular, next link is NULL instead of looping back to Head.
 230   if (MO == Head)
 231     HeadRef = Next;
 232   else
 233     Prev->Contents.Reg.Next = Next;
 234
 235   (Next ? Next : Head)->Contents.Reg.Prev = Prev;
 236
 237   MO->Contents.Reg.Prev = 0;
 238   MO->Contents.Reg.Next = 0;
 239 }
 240
 241 /// Move NumOps operands from Src to Dst, updating use-def lists as needed.
 242 ///
 243 /// The Dst range is assumed to be uninitialized memory. (Or it may contain
 244 /// operands that won't be destroyed, which is OK because the MO destructor is
 245 /// trivial anyway).
 246 ///
 247 /// The Src and Dst ranges may overlap.
 248 void MachineRegisterInfo::moveOperands(MachineOperand *Dst,
 249                                        MachineOperand *Src,
 250                                        unsigned NumOps) {
 251   assert(Src != Dst && NumOps && "Noop moveOperands");
 252
 253   // Copy backwards if Dst is within the Src range.
 254   int Stride = 1;
 255   if (Dst >= Src && Dst < Src + NumOps) {
 256     Stride = -1;
 257     Dst += NumOps - 1;
 258     Src += NumOps - 1;
 259   }
 260
 261   // Copy one operand at a time.
 262   do {
 263     new (Dst) MachineOperand(*Src);
 264
 265     // Dst takes Src's place in the use-def chain.
 266     if (Src->isReg()) {
 267       MachineOperand *&Head = getRegUseDefListHead(Src->getReg());
 268       MachineOperand *Prev = Src->Contents.Reg.Prev;
 269       MachineOperand *Next = Src->Contents.Reg.Next;
 270       assert(Head && "List empty, but operand is chained");
 271       assert(Prev && "Operand was not on use-def list");
 272
 273       // Prev links are circular, next link is NULL instead of looping back to
 274       // Head.
 275       if (Src == Head)
 276         Head = Dst;
 277       else
 278         Prev->Contents.Reg.Next = Dst;
 279
 280       // Update Prev pointer. This also works when Src was pointing to itself
 281       // in a 1-element list. In that case Head == Dst.
 282       (Next ? Next : Head)->Contents.Reg.Prev = Dst;
 283     }
 284
 285     Dst += Stride;
 286     Src += Stride;
 287   } while (--NumOps);
 288 }
 289
 290 /// replaceRegWith - Replace all instances of FromReg with ToReg in the
 291 /// machine function.  This is like llvm-level X->replaceAllUsesWith(Y),
 292 /// except that it also changes any definitions of the register as well.
 293 void MachineRegisterInfo::replaceRegWith(unsigned FromReg, unsigned ToReg) {
 294   assert(FromReg != ToReg && "Cannot replace a reg with itself");
 295
 296   // TODO: This could be more efficient by bulk changing the operands.
 297   for (reg_iterator I = reg_begin(FromReg), E = reg_end(); I != E; ) {
 298     MachineOperand &O = I.getOperand();
 299     ++I;
 300     O.setReg(ToReg);
 301   }
 302 }
 303
 304
 305 /// getVRegDef - Return the machine instr that defines the specified virtual
 306 /// register or null if none is found.  This assumes that the code is in SSA
 307 /// form, so there should only be one definition.
 308 MachineInstr *MachineRegisterInfo::getVRegDef(unsigned Reg) const {
 309   // Since we are in SSA form, we can use the first definition.
 310   def_iterator I = def_begin(Reg);
 311   assert((I.atEnd() || llvm::next(I) == def_end()) &&
 312          "getVRegDef assumes a single definition or no definition");
 313   return !I.atEnd() ? &*I : 0;
 314 }
 315
 316 /// getUniqueVRegDef - Return the unique machine instr that defines the
 317 /// specified virtual register or null if none is found.  If there are
 318 /// multiple definitions or no definition, return null.
 319 MachineInstr *MachineRegisterInfo::getUniqueVRegDef(unsigned Reg) const {
 320   if (def_empty(Reg)) return 0;
 321   def_iterator I = def_begin(Reg);
 322   if (llvm::next(I) != def_end())
 323     return 0;
 324   return &*I;
 325 }
 326
 327 bool MachineRegisterInfo::hasOneNonDBGUse(unsigned RegNo) const {
 328   use_nodbg_iterator UI = use_nodbg_begin(RegNo);
 329   if (UI == use_nodbg_end())
 330     return false;
 331   return ++UI == use_nodbg_end();
 332 }
 333
 334 /// clearKillFlags - Iterate over all the uses of the given register and
 335 /// clear the kill flag from the MachineOperand. This function is used by
 336 /// optimization passes which extend register lifetimes and need only
 337 /// preserve conservative kill flag information.
 338 void MachineRegisterInfo::clearKillFlags(unsigned Reg) const {
 339   for (use_iterator UI = use_begin(Reg), UE = use_end(); UI != UE; ++UI)
 340     UI.getOperand().setIsKill(false);
 341 }
 342
 343 bool MachineRegisterInfo::isLiveIn(unsigned Reg) const {
 344   for (livein_iterator I = livein_begin(), E = livein_end(); I != E; ++I)
 345     if (I->first == Reg || I->second == Reg)
 346       return true;
 347   return false;
 348 }
 349
 350 /// getLiveInPhysReg - If VReg is a live-in virtual register, return the
 351 /// corresponding live-in physical register.
 352 unsigned MachineRegisterInfo::getLiveInPhysReg(unsigned VReg) const {
 353   for (livein_iterator I = livein_begin(), E = livein_end(); I != E; ++I)
 354     if (I->second == VReg)
 355       return I->first;
 356   return 0;
 357 }
 358
 359 /// getLiveInVirtReg - If PReg is a live-in physical register, return the
 360 /// corresponding live-in physical register.
 361 unsigned MachineRegisterInfo::getLiveInVirtReg(unsigned PReg) const {
 362   for (livein_iterator I = livein_begin(), E = livein_end(); I != E; ++I)
 363     if (I->first == PReg)
 364       return I->second;
 365   return 0;
 366 }
 367
 368 /// EmitLiveInCopies - Emit copies to initialize livein virtual registers
 369 /// into the given entry block.
 370 void
 371 MachineRegisterInfo::EmitLiveInCopies(MachineBasicBlock *EntryMBB,
 372                                       const TargetRegisterInfo &TRI,
 373                                       const TargetInstrInfo &TII) {
 374   // Emit the copies into the top of the block.
 375   for (unsigned i = 0, e = LiveIns.size(); i != e; ++i)
 376     if (LiveIns[i].second) {
 377       if (use_empty(LiveIns[i].second)) {
 378         // The livein has no uses. Drop it.
 379         //
 380         // It would be preferable to have isel avoid creating live-in
 381         // records for unused arguments in the first place, but it's
 382         // complicated by the debug info code for arguments.
 383         LiveIns.erase(LiveIns.begin() + i);
 384         --i; --e;
 385       } else {
 386         // Emit a copy.
 387         BuildMI(*EntryMBB, EntryMBB->begin(), DebugLoc(),
 388                 TII.get(TargetOpcode::COPY), LiveIns[i].second)
 389           .addReg(LiveIns[i].first);
 390
 391         // Add the register to the entry block live-in set.
 392         EntryMBB->addLiveIn(LiveIns[i].first);
 393       }
 394     } else {
 395       // Add the register to the entry block live-in set.
 396       EntryMBB->addLiveIn(LiveIns[i].first);
 397     }
 398 }
 399
 400 #ifndef NDEBUG
 401 void MachineRegisterInfo::dumpUses(unsigned Reg) const {
 402   for (use_iterator I = use_begin(Reg), E = use_end(); I != E; ++I)
 403     I.getOperand().getParent()->dump();
 404 }
 405 #endif
 406
 407 void MachineRegisterInfo::freezeReservedRegs(const MachineFunction &MF) {
 408   ReservedRegs = getTargetRegisterInfo()->getReservedRegs(MF);
 409   assert(ReservedRegs.size() == getTargetRegisterInfo()->getNumRegs() &&
 410          "Invalid ReservedRegs vector from target");
 411 }
 412
 413 bool MachineRegisterInfo::isConstantPhysReg(unsigned PhysReg,
 414                                             const MachineFunction &MF) const {
 415   assert(TargetRegisterInfo::isPhysicalRegister(PhysReg));
 416
 417   // Check if any overlapping register is modified, or allocatable so it may be
 418   // used later.
 419   for (MCRegAliasIterator AI(PhysReg, getTargetRegisterInfo(), true);
 420        AI.isValid(); ++AI)
 421     if (!def_empty(*AI) || isAllocatable(*AI))
 422       return false;
 423   return true;
 424 }