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