include/llvm/CodeGen/MachineRegisterInfo.h

   1 //===-- llvm/CodeGen/MachineRegisterInfo.h ----------------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines the MachineRegisterInfo class.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_CODEGEN_MACHINEREGISTERINFO_H
  15 #define LLVM_CODEGEN_MACHINEREGISTERINFO_H
  16
  17 #include "llvm/Target/TargetRegisterInfo.h"
  18 #include "llvm/CodeGen/MachineInstrBundle.h"
  19 #include "llvm/ADT/BitVector.h"
  20 #include "llvm/ADT/IndexedMap.h"
  21 #include <vector>
  22
  23 namespace llvm {
  24
  25 /// MachineRegisterInfo - Keep track of information for virtual and physical
  26 /// registers, including vreg register classes, use/def chains for registers,
  27 /// etc.
  28 class MachineRegisterInfo {
  29   const TargetRegisterInfo *const TRI;
  30
  31   /// IsSSA - True when the machine function is in SSA form and virtual
  32   /// registers have a single def.
  33   bool IsSSA;
  34
  35   /// VRegInfo - Information we keep for each virtual register.
  36   ///
  37   /// Each element in this list contains the register class of the vreg and the
  38   /// start of the use/def list for the register.
  39   IndexedMap<std::pair<const TargetRegisterClass*, MachineOperand*>,
  40              VirtReg2IndexFunctor> VRegInfo;
  41
  42   /// RegAllocHints - This vector records register allocation hints for virtual
  43   /// registers. For each virtual register, it keeps a register and hint type
  44   /// pair making up the allocation hint. Hint type is target specific except
  45   /// for the value 0 which means the second value of the pair is the preferred
  46   /// register for allocation. For example, if the hint is <0, 1024>, it means
  47   /// the allocator should prefer the physical register allocated to the virtual
  48   /// register of the hint.
  49   IndexedMap<std::pair<unsigned, unsigned>, VirtReg2IndexFunctor> RegAllocHints;
  50
  51   /// PhysRegUseDefLists - This is an array of the head of the use/def list for
  52   /// physical registers.
  53   MachineOperand **PhysRegUseDefLists;
  54
  55   /// UsedPhysRegs - This is a bit vector that is computed and set by the
  56   /// register allocator, and must be kept up to date by passes that run after
  57   /// register allocation (though most don't modify this).  This is used
  58   /// so that the code generator knows which callee save registers to save and
  59   /// for other target specific uses.
  60   /// This vector only has bits set for registers explicitly used, not their
  61   /// aliases.
  62   BitVector UsedPhysRegs;
  63
  64   /// UsedPhysRegMask - Additional used physregs, but including aliases.
  65   BitVector UsedPhysRegMask;
  66
  67   /// ReservedRegs - This is a bit vector of reserved registers.  The target
  68   /// may change its mind about which registers should be reserved.  This
  69   /// vector is the frozen set of reserved registers when register allocation
  70   /// started.
  71   BitVector ReservedRegs;
  72
  73   /// AllocatableRegs - From TRI->getAllocatableSet.
  74   mutable BitVector AllocatableRegs;
  75
  76   /// LiveIns/LiveOuts - Keep track of the physical registers that are
  77   /// livein/liveout of the function.  Live in values are typically arguments in
  78   /// registers, live out values are typically return values in registers.
  79   /// LiveIn values are allowed to have virtual registers associated with them,
  80   /// stored in the second element.
  81   std::vector<std::pair<unsigned, unsigned> > LiveIns;
  82   std::vector<unsigned> LiveOuts;
  83
  84   MachineRegisterInfo(const MachineRegisterInfo&); // DO NOT IMPLEMENT
  85   void operator=(const MachineRegisterInfo&);      // DO NOT IMPLEMENT
  86 public:
  87   explicit MachineRegisterInfo(const TargetRegisterInfo &TRI);
  88   ~MachineRegisterInfo();
  89
  90   //===--------------------------------------------------------------------===//
  91   // Function State
  92   //===--------------------------------------------------------------------===//
  93
  94   // isSSA - Returns true when the machine function is in SSA form. Early
  95   // passes require the machine function to be in SSA form where every virtual
  96   // register has a single defining instruction.
  97   //
  98   // The TwoAddressInstructionPass and PHIElimination passes take the machine
  99   // function out of SSA form when they introduce multiple defs per virtual
 100   // register.
 101   bool isSSA() const { return IsSSA; }
 102
 103   // leaveSSA - Indicates that the machine function is no longer in SSA form.
 104   void leaveSSA() { IsSSA = false; }
 105
 106   //===--------------------------------------------------------------------===//
 107   // Register Info
 108   //===--------------------------------------------------------------------===//
 109
 110   /// reg_begin/reg_end - Provide iteration support to walk over all definitions
 111   /// and uses of a register within the MachineFunction that corresponds to this
 112   /// MachineRegisterInfo object.
 113   template<bool Uses, bool Defs, bool SkipDebug>
 114   class defusechain_iterator;
 115
 116   /// reg_iterator/reg_begin/reg_end - Walk all defs and uses of the specified
 117   /// register.
 118   typedef defusechain_iterator<true,true,false> reg_iterator;
 119   reg_iterator reg_begin(unsigned RegNo) const {
 120     return reg_iterator(getRegUseDefListHead(RegNo));
 121   }
 122   static reg_iterator reg_end() { return reg_iterator(0); }
 123
 124   /// reg_empty - Return true if there are no instructions using or defining the
 125   /// specified register (it may be live-in).
 126   bool reg_empty(unsigned RegNo) const { return reg_begin(RegNo) == reg_end(); }
 127
 128   /// reg_nodbg_iterator/reg_nodbg_begin/reg_nodbg_end - Walk all defs and uses
 129   /// of the specified register, skipping those marked as Debug.
 130   typedef defusechain_iterator<true,true,true> reg_nodbg_iterator;
 131   reg_nodbg_iterator reg_nodbg_begin(unsigned RegNo) const {
 132     return reg_nodbg_iterator(getRegUseDefListHead(RegNo));
 133   }
 134   static reg_nodbg_iterator reg_nodbg_end() { return reg_nodbg_iterator(0); }
 135
 136   /// reg_nodbg_empty - Return true if the only instructions using or defining
 137   /// Reg are Debug instructions.
 138   bool reg_nodbg_empty(unsigned RegNo) const {
 139     return reg_nodbg_begin(RegNo) == reg_nodbg_end();
 140   }
 141
 142   /// def_iterator/def_begin/def_end - Walk all defs of the specified register.
 143   typedef defusechain_iterator<false,true,false> def_iterator;
 144   def_iterator def_begin(unsigned RegNo) const {
 145     return def_iterator(getRegUseDefListHead(RegNo));
 146   }
 147   static def_iterator def_end() { return def_iterator(0); }
 148
 149   /// def_empty - Return true if there are no instructions defining the
 150   /// specified register (it may be live-in).
 151   bool def_empty(unsigned RegNo) const { return def_begin(RegNo) == def_end(); }
 152
 153   /// use_iterator/use_begin/use_end - Walk all uses of the specified register.
 154   typedef defusechain_iterator<true,false,false> use_iterator;
 155   use_iterator use_begin(unsigned RegNo) const {
 156     return use_iterator(getRegUseDefListHead(RegNo));
 157   }
 158   static use_iterator use_end() { return use_iterator(0); }
 159
 160   /// use_empty - Return true if there are no instructions using the specified
 161   /// register.
 162   bool use_empty(unsigned RegNo) const { return use_begin(RegNo) == use_end(); }
 163
 164   /// hasOneUse - Return true if there is exactly one instruction using the
 165   /// specified register.
 166   bool hasOneUse(unsigned RegNo) const;
 167
 168   /// use_nodbg_iterator/use_nodbg_begin/use_nodbg_end - Walk all uses of the
 169   /// specified register, skipping those marked as Debug.
 170   typedef defusechain_iterator<true,false,true> use_nodbg_iterator;
 171   use_nodbg_iterator use_nodbg_begin(unsigned RegNo) const {
 172     return use_nodbg_iterator(getRegUseDefListHead(RegNo));
 173   }
 174   static use_nodbg_iterator use_nodbg_end() { return use_nodbg_iterator(0); }
 175
 176   /// use_nodbg_empty - Return true if there are no non-Debug instructions
 177   /// using the specified register.
 178   bool use_nodbg_empty(unsigned RegNo) const {
 179     return use_nodbg_begin(RegNo) == use_nodbg_end();
 180   }
 181
 182   /// hasOneNonDBGUse - Return true if there is exactly one non-Debug
 183   /// instruction using the specified register.
 184   bool hasOneNonDBGUse(unsigned RegNo) const;
 185
 186   /// replaceRegWith - Replace all instances of FromReg with ToReg in the
 187   /// machine function.  This is like llvm-level X->replaceAllUsesWith(Y),
 188   /// except that it also changes any definitions of the register as well.
 189   ///
 190   /// Note that it is usually necessary to first constrain ToReg's register
 191   /// class to match the FromReg constraints using:
 192   ///
 193   ///   constrainRegClass(ToReg, getRegClass(FromReg))
 194   ///
 195   /// That function will return NULL if the virtual registers have incompatible
 196   /// constraints.
 197   void replaceRegWith(unsigned FromReg, unsigned ToReg);
 198
 199   /// getRegUseDefListHead - Return the head pointer for the register use/def
 200   /// list for the specified virtual or physical register.
 201   MachineOperand *&getRegUseDefListHead(unsigned RegNo) {
 202     if (TargetRegisterInfo::isVirtualRegister(RegNo))
 203       return VRegInfo[RegNo].second;
 204     return PhysRegUseDefLists[RegNo];
 205   }
 206
 207   MachineOperand *getRegUseDefListHead(unsigned RegNo) const {
 208     if (TargetRegisterInfo::isVirtualRegister(RegNo))
 209       return VRegInfo[RegNo].second;
 210     return PhysRegUseDefLists[RegNo];
 211   }
 212
 213   /// getVRegDef - Return the machine instr that defines the specified virtual
 214   /// register or null if none is found.  This assumes that the code is in SSA
 215   /// form, so there should only be one definition.
 216   MachineInstr *getVRegDef(unsigned Reg) const;
 217
 218   /// clearKillFlags - Iterate over all the uses of the given register and
 219   /// clear the kill flag from the MachineOperand. This function is used by
 220   /// optimization passes which extend register lifetimes and need only
 221   /// preserve conservative kill flag information.
 222   void clearKillFlags(unsigned Reg) const;
 223
 224 #ifndef NDEBUG
 225   void dumpUses(unsigned RegNo) const;
 226 #endif
 227
 228   /// isConstantPhysReg - Returns true if PhysReg is unallocatable and constant
 229   /// throughout the function.  It is safe to move instructions that read such
 230   /// a physreg.
 231   bool isConstantPhysReg(unsigned PhysReg, const MachineFunction &MF) const;
 232
 233   //===--------------------------------------------------------------------===//
 234   // Virtual Register Info
 235   //===--------------------------------------------------------------------===//
 236
 237   /// getRegClass - Return the register class of the specified virtual register.
 238   ///
 239   const TargetRegisterClass *getRegClass(unsigned Reg) const {
 240     return VRegInfo[Reg].first;
 241   }
 242
 243   /// setRegClass - Set the register class of the specified virtual register.
 244   ///
 245   void setRegClass(unsigned Reg, const TargetRegisterClass *RC);
 246
 247   /// constrainRegClass - Constrain the register class of the specified virtual
 248   /// register to be a common subclass of RC and the current register class,
 249   /// but only if the new class has at least MinNumRegs registers.  Return the
 250   /// new register class, or NULL if no such class exists.
 251   /// This should only be used when the constraint is known to be trivial, like
 252   /// GR32 -> GR32_NOSP. Beware of increasing register pressure.
 253   ///
 254   const TargetRegisterClass *constrainRegClass(unsigned Reg,
 255                                                const TargetRegisterClass *RC,
 256                                                unsigned MinNumRegs = 0);
 257
 258   /// recomputeRegClass - Try to find a legal super-class of Reg's register
 259   /// class that still satisfies the constraints from the instructions using
 260   /// Reg.  Returns true if Reg was upgraded.
 261   ///
 262   /// This method can be used after constraints have been removed from a
 263   /// virtual register, for example after removing instructions or splitting
 264   /// the live range.
 265   ///
 266   bool recomputeRegClass(unsigned Reg, const TargetMachine&);
 267
 268   /// createVirtualRegister - Create and return a new virtual register in the
 269   /// function with the specified register class.
 270   ///
 271   unsigned createVirtualRegister(const TargetRegisterClass *RegClass);
 272
 273   /// getNumVirtRegs - Return the number of virtual registers created.
 274   ///
 275   unsigned getNumVirtRegs() const { return VRegInfo.size(); }
 276
 277   /// clearVirtRegs - Remove all virtual registers (after physreg assignment).
 278   void clearVirtRegs();
 279
 280   /// setRegAllocationHint - Specify a register allocation hint for the
 281   /// specified virtual register.
 282   void setRegAllocationHint(unsigned Reg, unsigned Type, unsigned PrefReg) {
 283     RegAllocHints[Reg].first  = Type;
 284     RegAllocHints[Reg].second = PrefReg;
 285   }
 286
 287   /// getRegAllocationHint - Return the register allocation hint for the
 288   /// specified virtual register.
 289   std::pair<unsigned, unsigned>
 290   getRegAllocationHint(unsigned Reg) const {
 291     return RegAllocHints[Reg];
 292   }
 293
 294   /// getSimpleHint - Return the preferred register allocation hint, or 0 if a
 295   /// standard simple hint (Type == 0) is not set.
 296   unsigned getSimpleHint(unsigned Reg) const {
 297     std::pair<unsigned, unsigned> Hint = getRegAllocationHint(Reg);
 298     return Hint.first ? 0 : Hint.second;
 299   }
 300
 301
 302   //===--------------------------------------------------------------------===//
 303   // Physical Register Use Info
 304   //===--------------------------------------------------------------------===//
 305
 306   /// isPhysRegUsed - Return true if the specified register is used in this
 307   /// function.  This only works after register allocation.
 308   bool isPhysRegUsed(unsigned Reg) const {
 309     return UsedPhysRegs.test(Reg) || UsedPhysRegMask.test(Reg);
 310   }
 311
 312   /// isPhysRegOrOverlapUsed - Return true if Reg or any overlapping register
 313   /// is used in this function.
 314   bool isPhysRegOrOverlapUsed(unsigned Reg) const {
 315     if (UsedPhysRegMask.test(Reg))
 316       return true;
 317     for (const uint16_t *AI = TRI->getOverlaps(Reg); *AI; ++AI)
 318       if (UsedPhysRegs.test(*AI))
 319         return true;
 320     return false;
 321   }
 322
 323   /// setPhysRegUsed - Mark the specified register used in this function.
 324   /// This should only be called during and after register allocation.
 325   void setPhysRegUsed(unsigned Reg) { UsedPhysRegs.set(Reg); }
 326
 327   /// addPhysRegsUsed - Mark the specified registers used in this function.
 328   /// This should only be called during and after register allocation.
 329   void addPhysRegsUsed(const BitVector &Regs) { UsedPhysRegs |= Regs; }
 330
 331   /// addPhysRegsUsedFromRegMask - Mark any registers not in RegMask as used.
 332   /// This corresponds to the bit mask attached to register mask operands.
 333   void addPhysRegsUsedFromRegMask(const uint32_t *RegMask) {
 334     UsedPhysRegMask.setBitsNotInMask(RegMask);
 335   }
 336
 337   /// setPhysRegUnused - Mark the specified register unused in this function.
 338   /// This should only be called during and after register allocation.
 339   void setPhysRegUnused(unsigned Reg) {
 340     UsedPhysRegs.reset(Reg);
 341     UsedPhysRegMask.reset(Reg);
 342   }
 343
 344
 345   //===--------------------------------------------------------------------===//
 346   // Reserved Register Info
 347   //===--------------------------------------------------------------------===//
 348   //
 349   // The set of reserved registers must be invariant during register
 350   // allocation.  For example, the target cannot suddenly decide it needs a
 351   // frame pointer when the register allocator has already used the frame
 352   // pointer register for something else.
 353   //
 354   // These methods can be used by target hooks like hasFP() to avoid changing
 355   // the reserved register set during register allocation.
 356
 357   /// freezeReservedRegs - Called by the register allocator to freeze the set
 358   /// of reserved registers before allocation begins.
 359   void freezeReservedRegs(const MachineFunction&);
 360
 361   /// reservedRegsFrozen - Returns true after freezeReservedRegs() was called
 362   /// to ensure the set of reserved registers stays constant.
 363   bool reservedRegsFrozen() const {
 364     return !ReservedRegs.empty();
 365   }
 366
 367   /// canReserveReg - Returns true if PhysReg can be used as a reserved
 368   /// register.  Any register can be reserved before freezeReservedRegs() is
 369   /// called.
 370   bool canReserveReg(unsigned PhysReg) const {
 371     return !reservedRegsFrozen() || ReservedRegs.test(PhysReg);
 372   }
 373
 374
 375   //===--------------------------------------------------------------------===//
 376   // LiveIn/LiveOut Management
 377   //===--------------------------------------------------------------------===//
 378
 379   /// addLiveIn/Out - Add the specified register as a live in/out.  Note that it
 380   /// is an error to add the same register to the same set more than once.
 381   void addLiveIn(unsigned Reg, unsigned vreg = 0) {
 382     LiveIns.push_back(std::make_pair(Reg, vreg));
 383   }
 384   void addLiveOut(unsigned Reg) { LiveOuts.push_back(Reg); }
 385
 386   // Iteration support for live in/out sets.  These sets are kept in sorted
 387   // order by their register number.
 388   typedef std::vector<std::pair<unsigned,unsigned> >::const_iterator
 389   livein_iterator;
 390   typedef std::vector<unsigned>::const_iterator liveout_iterator;
 391   livein_iterator livein_begin() const { return LiveIns.begin(); }
 392   livein_iterator livein_end()   const { return LiveIns.end(); }
 393   bool            livein_empty() const { return LiveIns.empty(); }
 394   liveout_iterator liveout_begin() const { return LiveOuts.begin(); }
 395   liveout_iterator liveout_end()   const { return LiveOuts.end(); }
 396   bool             liveout_empty() const { return LiveOuts.empty(); }
 397
 398   bool isLiveIn(unsigned Reg) const;
 399   bool isLiveOut(unsigned Reg) const;
 400
 401   /// getLiveInPhysReg - If VReg is a live-in virtual register, return the
 402   /// corresponding live-in physical register.
 403   unsigned getLiveInPhysReg(unsigned VReg) const;
 404
 405   /// getLiveInVirtReg - If PReg is a live-in physical register, return the
 406   /// corresponding live-in physical register.
 407   unsigned getLiveInVirtReg(unsigned PReg) const;
 408
 409   /// EmitLiveInCopies - Emit copies to initialize livein virtual registers
 410   /// into the given entry block.
 411   void EmitLiveInCopies(MachineBasicBlock *EntryMBB,
 412                         const TargetRegisterInfo &TRI,
 413                         const TargetInstrInfo &TII);
 414
 415 private:
 416   void HandleVRegListReallocation();
 417
 418 public:
 419   /// defusechain_iterator - This class provides iterator support for machine
 420   /// operands in the function that use or define a specific register.  If
 421   /// ReturnUses is true it returns uses of registers, if ReturnDefs is true it
 422   /// returns defs.  If neither are true then you are silly and it always
 423   /// returns end().  If SkipDebug is true it skips uses marked Debug
 424   /// when incrementing.
 425   template<bool ReturnUses, bool ReturnDefs, bool SkipDebug>
 426   class defusechain_iterator
 427     : public std::iterator<std::forward_iterator_tag, MachineInstr, ptrdiff_t> {
 428     MachineOperand *Op;
 429     explicit defusechain_iterator(MachineOperand *op) : Op(op) {
 430       // If the first node isn't one we're interested in, advance to one that
 431       // we are interested in.
 432       if (op) {
 433         if ((!ReturnUses && op->isUse()) ||
 434             (!ReturnDefs && op->isDef()) ||
 435             (SkipDebug && op->isDebug()))
 436           ++*this;
 437       }
 438     }
 439     friend class MachineRegisterInfo;
 440   public:
 441     typedef std::iterator<std::forward_iterator_tag,
 442                           MachineInstr, ptrdiff_t>::reference reference;
 443     typedef std::iterator<std::forward_iterator_tag,
 444                           MachineInstr, ptrdiff_t>::pointer pointer;
 445
 446     defusechain_iterator(const defusechain_iterator &I) : Op(I.Op) {}
 447     defusechain_iterator() : Op(0) {}
 448
 449     bool operator==(const defusechain_iterator &x) const {
 450       return Op == x.Op;
 451     }
 452     bool operator!=(const defusechain_iterator &x) const {
 453       return !operator==(x);
 454     }
 455
 456     /// atEnd - return true if this iterator is equal to reg_end() on the value.
 457     bool atEnd() const { return Op == 0; }
 458
 459     // Iterator traversal: forward iteration only
 460     defusechain_iterator &operator++() {          // Preincrement
 461       assert(Op && "Cannot increment end iterator!");
 462       Op = Op->getNextOperandForReg();
 463
 464       // If this is an operand we don't care about, skip it.
 465       while (Op && ((!ReturnUses && Op->isUse()) ||
 466                     (!ReturnDefs && Op->isDef()) ||
 467                     (SkipDebug && Op->isDebug())))
 468         Op = Op->getNextOperandForReg();
 469
 470       return *this;
 471     }
 472     defusechain_iterator operator++(int) {        // Postincrement
 473       defusechain_iterator tmp = *this; ++*this; return tmp;
 474     }
 475
 476     /// skipInstruction - move forward until reaching a different instruction.
 477     /// Return the skipped instruction that is no longer pointed to, or NULL if
 478     /// already pointing to end().
 479     MachineInstr *skipInstruction() {
 480       if (!Op) return 0;
 481       MachineInstr *MI = Op->getParent();
 482       do ++*this;
 483       while (Op && Op->getParent() == MI);
 484       return MI;
 485     }
 486
 487     MachineInstr *skipBundle() {
 488       if (!Op) return 0;
 489       MachineInstr *MI = getBundleStart(Op->getParent());
 490       do ++*this;
 491       while (Op && getBundleStart(Op->getParent()) == MI);
 492       return MI;
 493     }
 494
 495     MachineOperand &getOperand() const {
 496       assert(Op && "Cannot dereference end iterator!");
 497       return *Op;
 498     }
 499
 500     /// getOperandNo - Return the operand # of this MachineOperand in its
 501     /// MachineInstr.
 502     unsigned getOperandNo() const {
 503       assert(Op && "Cannot dereference end iterator!");
 504       return Op - &Op->getParent()->getOperand(0);
 505     }
 506
 507     // Retrieve a reference to the current operand.
 508     MachineInstr &operator*() const {
 509       assert(Op && "Cannot dereference end iterator!");
 510       return *Op->getParent();
 511     }
 512
 513     MachineInstr *operator->() const {
 514       assert(Op && "Cannot dereference end iterator!");
 515       return Op->getParent();
 516     }
 517   };
 518
 519 };
 520
 521 } // End llvm namespace
 522
 523 #endif