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/ADT/BitVector.h"
  18 #include "llvm/ADT/IndexedMap.h"
  19 #include "llvm/ADT/iterator_range.h"
  20 #include "llvm/CodeGen/MachineInstrBundle.h"
  21 #include "llvm/Target/TargetMachine.h"
  22 #include "llvm/Target/TargetRegisterInfo.h"
  23 #include <vector>
  24
  25 namespace llvm {
  26 class PSetIterator;
  27
  28 /// MachineRegisterInfo - Keep track of information for virtual and physical
  29 /// registers, including vreg register classes, use/def chains for registers,
  30 /// etc.
  31 class MachineRegisterInfo {
  32 public:
  33   class Delegate {
  34     virtual void anchor();
  35   public:
  36     virtual void MRI_NoteNewVirtualRegister(unsigned Reg) = 0;
  37
  38     virtual ~Delegate() {}
  39   };
  40
  41 private:
  42   const TargetMachine &TM;
  43   Delegate *TheDelegate;
  44
  45   /// IsSSA - True when the machine function is in SSA form and virtual
  46   /// registers have a single def.
  47   bool IsSSA;
  48
  49   /// TracksLiveness - True while register liveness is being tracked accurately.
  50   /// Basic block live-in lists, kill flags, and implicit defs may not be
  51   /// accurate when after this flag is cleared.
  52   bool TracksLiveness;
  53
  54   /// VRegInfo - Information we keep for each virtual register.
  55   ///
  56   /// Each element in this list contains the register class of the vreg and the
  57   /// start of the use/def list for the register.
  58   IndexedMap<std::pair<const TargetRegisterClass*, MachineOperand*>,
  59              VirtReg2IndexFunctor> VRegInfo;
  60
  61   /// RegAllocHints - This vector records register allocation hints for virtual
  62   /// registers. For each virtual register, it keeps a register and hint type
  63   /// pair making up the allocation hint. Hint type is target specific except
  64   /// for the value 0 which means the second value of the pair is the preferred
  65   /// register for allocation. For example, if the hint is <0, 1024>, it means
  66   /// the allocator should prefer the physical register allocated to the virtual
  67   /// register of the hint.
  68   IndexedMap<std::pair<unsigned, unsigned>, VirtReg2IndexFunctor> RegAllocHints;
  69
  70   /// PhysRegUseDefLists - This is an array of the head of the use/def list for
  71   /// physical registers.
  72   MachineOperand **PhysRegUseDefLists;
  73
  74   /// getRegUseDefListHead - Return the head pointer for the register use/def
  75   /// list for the specified virtual or physical register.
  76   MachineOperand *&getRegUseDefListHead(unsigned RegNo) {
  77     if (TargetRegisterInfo::isVirtualRegister(RegNo))
  78       return VRegInfo[RegNo].second;
  79     return PhysRegUseDefLists[RegNo];
  80   }
  81
  82   MachineOperand *getRegUseDefListHead(unsigned RegNo) const {
  83     if (TargetRegisterInfo::isVirtualRegister(RegNo))
  84       return VRegInfo[RegNo].second;
  85     return PhysRegUseDefLists[RegNo];
  86   }
  87
  88   /// Get the next element in the use-def chain.
  89   static MachineOperand *getNextOperandForReg(const MachineOperand *MO) {
  90     assert(MO && MO->isReg() && "This is not a register operand!");
  91     return MO->Contents.Reg.Next;
  92   }
  93
  94   /// UsedRegUnits - This is a bit vector that is computed and set by the
  95   /// register allocator, and must be kept up to date by passes that run after
  96   /// register allocation (though most don't modify this).  This is used
  97   /// so that the code generator knows which callee save registers to save and
  98   /// for other target specific uses.
  99   /// This vector has bits set for register units that are modified in the
 100   /// current function. It doesn't include registers clobbered by function
 101   /// calls with register mask operands.
 102   BitVector UsedRegUnits;
 103
 104   /// UsedPhysRegMask - Additional used physregs including aliases.
 105   /// This bit vector represents all the registers clobbered by function calls.
 106   /// It can model things that UsedRegUnits can't, such as function calls that
 107   /// clobber ymm7 but preserve the low half in xmm7.
 108   BitVector UsedPhysRegMask;
 109
 110   /// ReservedRegs - This is a bit vector of reserved registers.  The target
 111   /// may change its mind about which registers should be reserved.  This
 112   /// vector is the frozen set of reserved registers when register allocation
 113   /// started.
 114   BitVector ReservedRegs;
 115
 116   /// Keep track of the physical registers that are live in to the function.
 117   /// Live in values are typically arguments in registers.  LiveIn values are
 118   /// allowed to have virtual registers associated with them, stored in the
 119   /// second element.
 120   std::vector<std::pair<unsigned, unsigned> > LiveIns;
 121
 122   MachineRegisterInfo(const MachineRegisterInfo&) LLVM_DELETED_FUNCTION;
 123   void operator=(const MachineRegisterInfo&) LLVM_DELETED_FUNCTION;
 124 public:
 125   explicit MachineRegisterInfo(const TargetMachine &TM);
 126   ~MachineRegisterInfo();
 127
 128   const TargetRegisterInfo *getTargetRegisterInfo() const {
 129     return TM.getRegisterInfo();
 130   }
 131
 132   void resetDelegate(Delegate *delegate) {
 133     // Ensure another delegate does not take over unless the current
 134     // delegate first unattaches itself. If we ever need to multicast
 135     // notifications, we will need to change to using a list.
 136     assert(TheDelegate == delegate &&
 137            "Only the current delegate can perform reset!");
 138     TheDelegate = 0;
 139   }
 140
 141   void setDelegate(Delegate *delegate) {
 142     assert(delegate && !TheDelegate &&
 143            "Attempted to set delegate to null, or to change it without "
 144            "first resetting it!");
 145
 146     TheDelegate = delegate;
 147   }
 148
 149   //===--------------------------------------------------------------------===//
 150   // Function State
 151   //===--------------------------------------------------------------------===//
 152
 153   // isSSA - Returns true when the machine function is in SSA form. Early
 154   // passes require the machine function to be in SSA form where every virtual
 155   // register has a single defining instruction.
 156   //
 157   // The TwoAddressInstructionPass and PHIElimination passes take the machine
 158   // function out of SSA form when they introduce multiple defs per virtual
 159   // register.
 160   bool isSSA() const { return IsSSA; }
 161
 162   // leaveSSA - Indicates that the machine function is no longer in SSA form.
 163   void leaveSSA() { IsSSA = false; }
 164
 165   /// tracksLiveness - Returns true when tracking register liveness accurately.
 166   ///
 167   /// While this flag is true, register liveness information in basic block
 168   /// live-in lists and machine instruction operands is accurate. This means it
 169   /// can be used to change the code in ways that affect the values in
 170   /// registers, for example by the register scavenger.
 171   ///
 172   /// When this flag is false, liveness is no longer reliable.
 173   bool tracksLiveness() const { return TracksLiveness; }
 174
 175   /// invalidateLiveness - Indicates that register liveness is no longer being
 176   /// tracked accurately.
 177   ///
 178   /// This should be called by late passes that invalidate the liveness
 179   /// information.
 180   void invalidateLiveness() { TracksLiveness = false; }
 181
 182   //===--------------------------------------------------------------------===//
 183   // Register Info
 184   //===--------------------------------------------------------------------===//
 185
 186   // Strictly for use by MachineInstr.cpp.
 187   void addRegOperandToUseList(MachineOperand *MO);
 188
 189   // Strictly for use by MachineInstr.cpp.
 190   void removeRegOperandFromUseList(MachineOperand *MO);
 191
 192   // Strictly for use by MachineInstr.cpp.
 193   void moveOperands(MachineOperand *Dst, MachineOperand *Src, unsigned NumOps);
 194
 195   /// Verify the sanity of the use list for Reg.
 196   void verifyUseList(unsigned Reg) const;
 197
 198   /// Verify the use list of all registers.
 199   void verifyUseLists() const;
 200
 201   /// reg_begin/reg_end - Provide iteration support to walk over all definitions
 202   /// and uses of a register within the MachineFunction that corresponds to this
 203   /// MachineRegisterInfo object.
 204   template<bool Uses, bool Defs, bool SkipDebug,
 205            bool ByOperand, bool ByInstr, bool ByBundle>
 206   class defusechain_iterator;
 207   template<bool Uses, bool Defs, bool SkipDebug,
 208            bool ByOperand, bool ByInstr, bool ByBundle>
 209   class defusechain_instr_iterator;
 210
 211   // Make it a friend so it can access getNextOperandForReg().
 212   template<bool, bool, bool, bool, bool, bool>
 213     friend class defusechain_iterator;
 214   template<bool, bool, bool, bool, bool, bool>
 215     friend class defusechain_instr_iterator;
 216
 217
 218
 219   /// reg_iterator/reg_begin/reg_end - Walk all defs and uses of the specified
 220   /// register.
 221   typedef defusechain_iterator<true,true,false,true,false,false>
 222           reg_iterator;
 223   reg_iterator reg_begin(unsigned RegNo) const {
 224     return reg_iterator(getRegUseDefListHead(RegNo));
 225   }
 226   static reg_iterator reg_end() { return reg_iterator(0); }
 227
 228   inline iterator_range<reg_iterator>  reg_operands(unsigned Reg) {
 229     return iterator_range<reg_iterator>(reg_begin(Reg), reg_end());
 230   }
 231
 232   /// reg_instr_iterator/reg_instr_begin/reg_instr_end - Walk all defs and uses
 233   /// of the specified register, stepping by MachineInstr.
 234   typedef defusechain_instr_iterator<true,true,false,false,true,false>
 235           reg_instr_iterator;
 236   reg_instr_iterator reg_instr_begin(unsigned RegNo) const {
 237     return reg_instr_iterator(getRegUseDefListHead(RegNo));
 238   }
 239   static reg_instr_iterator reg_instr_end() { return reg_instr_iterator(0); }
 240
 241   inline iterator_range<reg_instr_iterator>  reg_instructions(unsigned Reg) {
 242     return iterator_range<reg_instr_iterator>(reg_instr_begin(Reg),
 243                                               reg_instr_end());
 244   }
 245
 246   /// reg_bundle_iterator/reg_bundle_begin/reg_bundle_end - Walk all defs and uses
 247   /// of the specified register, stepping by bundle.
 248   typedef defusechain_instr_iterator<true,true,false,false,false,true>
 249           reg_bundle_iterator;
 250   reg_bundle_iterator reg_bundle_begin(unsigned RegNo) const {
 251     return reg_bundle_iterator(getRegUseDefListHead(RegNo));
 252   }
 253   static reg_bundle_iterator reg_bundle_end() { return reg_bundle_iterator(0); }
 254
 255   inline iterator_range<reg_bundle_iterator>  reg_bundles(unsigned Reg) {
 256     return iterator_range<reg_bundle_iterator>(reg_bundle_begin(Reg),
 257                                                reg_bundle_end());
 258   }
 259
 260   /// reg_empty - Return true if there are no instructions using or defining the
 261   /// specified register (it may be live-in).
 262   bool reg_empty(unsigned RegNo) const { return reg_begin(RegNo) == reg_end(); }
 263
 264   /// reg_nodbg_iterator/reg_nodbg_begin/reg_nodbg_end - Walk all defs and uses
 265   /// of the specified register, skipping those marked as Debug.
 266   typedef defusechain_iterator<true,true,true,true,false,false>
 267           reg_nodbg_iterator;
 268   reg_nodbg_iterator reg_nodbg_begin(unsigned RegNo) const {
 269     return reg_nodbg_iterator(getRegUseDefListHead(RegNo));
 270   }
 271   static reg_nodbg_iterator reg_nodbg_end() { return reg_nodbg_iterator(0); }
 272
 273   inline iterator_range<reg_nodbg_iterator>  reg_nodbg_operands(unsigned Reg) {
 274     return iterator_range<reg_nodbg_iterator>(reg_nodbg_begin(Reg),
 275                                               reg_nodbg_end());
 276   }
 277
 278   /// reg_instr_nodbg_iterator/reg_instr_nodbg_begin/reg_instr_nodbg_end - Walk
 279   /// all defs and uses of the specified register, stepping by MachineInstr,
 280   /// skipping those marked as Debug.
 281   typedef defusechain_instr_iterator<true,true,true,false,true,false>
 282           reg_instr_nodbg_iterator;
 283   reg_instr_nodbg_iterator reg_instr_nodbg_begin(unsigned RegNo) const {
 284     return reg_instr_nodbg_iterator(getRegUseDefListHead(RegNo));
 285   }
 286   static reg_instr_nodbg_iterator reg_instr_nodbg_end() {
 287     return reg_instr_nodbg_iterator(0);
 288   }
 289
 290   inline iterator_range<reg_instr_nodbg_iterator>
 291   reg_nodbg_instructions(unsigned Reg) {
 292     return iterator_range<reg_instr_nodbg_iterator>(reg_instr_nodbg_begin(Reg),
 293                                                     reg_instr_nodbg_end());
 294   }
 295
 296   /// reg_bundle_nodbg_iterator/reg_bundle_nodbg_begin/reg_bundle_nodbg_end - Walk
 297   /// all defs and uses of the specified register, stepping by bundle,
 298   /// skipping those marked as Debug.
 299   typedef defusechain_instr_iterator<true,true,true,false,false,true>
 300           reg_bundle_nodbg_iterator;
 301   reg_bundle_nodbg_iterator reg_bundle_nodbg_begin(unsigned RegNo) const {
 302     return reg_bundle_nodbg_iterator(getRegUseDefListHead(RegNo));
 303   }
 304   static reg_bundle_nodbg_iterator reg_bundle_nodbg_end() {
 305     return reg_bundle_nodbg_iterator(0);
 306   }
 307
 308   inline iterator_range<reg_bundle_nodbg_iterator>
 309   reg_nodbg_bundles(unsigned Reg) {
 310     return iterator_range<reg_bundle_nodbg_iterator>(reg_bundle_nodbg_begin(Reg),
 311                                                      reg_bundle_nodbg_end());
 312   }
 313
 314   /// reg_nodbg_empty - Return true if the only instructions using or defining
 315   /// Reg are Debug instructions.
 316   bool reg_nodbg_empty(unsigned RegNo) const {
 317     return reg_nodbg_begin(RegNo) == reg_nodbg_end();
 318   }
 319
 320   /// def_iterator/def_begin/def_end - Walk all defs of the specified register.
 321   typedef defusechain_iterator<false,true,false,true,false,false>
 322           def_iterator;
 323   def_iterator def_begin(unsigned RegNo) const {
 324     return def_iterator(getRegUseDefListHead(RegNo));
 325   }
 326   static def_iterator def_end() { return def_iterator(0); }
 327
 328   inline iterator_range<def_iterator> def_operands(unsigned Reg) const {
 329     return iterator_range<def_iterator>(def_begin(Reg), def_end());
 330   }
 331
 332   /// def_instr_iterator/def_instr_begin/def_instr_end - Walk all defs of the
 333   /// specified register, stepping by MachineInst.
 334   typedef defusechain_instr_iterator<false,true,false,false,true,false>
 335           def_instr_iterator;
 336   def_instr_iterator def_instr_begin(unsigned RegNo) const {
 337     return def_instr_iterator(getRegUseDefListHead(RegNo));
 338   }
 339   static def_instr_iterator def_instr_end() { return def_instr_iterator(0); }
 340
 341   inline iterator_range<def_instr_iterator>
 342   def_instructions(unsigned Reg) const {
 343     return iterator_range<def_instr_iterator>(def_instr_begin(Reg),
 344                                               def_instr_end());
 345   }
 346
 347   /// def_bundle_iterator/def_bundle_begin/def_bundle_end - Walk all defs of the
 348   /// specified register, stepping by bundle.
 349   typedef defusechain_instr_iterator<false,true,false,false,false,true>
 350           def_bundle_iterator;
 351   def_bundle_iterator def_bundle_begin(unsigned RegNo) const {
 352     return def_bundle_iterator(getRegUseDefListHead(RegNo));
 353   }
 354   static def_bundle_iterator def_bundle_end() { return def_bundle_iterator(0); }
 355
 356   inline iterator_range<def_bundle_iterator> def_bundles(unsigned Reg) const {
 357     return iterator_range<def_bundle_iterator>(def_bundle_begin(Reg),
 358                                                def_bundle_end());
 359   }
 360
 361   /// def_empty - Return true if there are no instructions defining the
 362   /// specified register (it may be live-in).
 363   bool def_empty(unsigned RegNo) const { return def_begin(RegNo) == def_end(); }
 364
 365   /// hasOneDef - Return true if there is exactly one instruction defining the
 366   /// specified register.
 367   bool hasOneDef(unsigned RegNo) const {
 368     def_iterator DI = def_begin(RegNo);
 369     if (DI == def_end())
 370       return false;
 371     return ++DI == def_end();
 372   }
 373
 374   /// use_iterator/use_begin/use_end - Walk all uses of the specified register.
 375   typedef defusechain_iterator<true,false,false,true,false,false>
 376           use_iterator;
 377   use_iterator use_begin(unsigned RegNo) const {
 378     return use_iterator(getRegUseDefListHead(RegNo));
 379   }
 380   static use_iterator use_end() { return use_iterator(0); }
 381
 382   inline iterator_range<use_iterator> use_operands(unsigned Reg) const {
 383     return iterator_range<use_iterator>(use_begin(Reg), use_end());
 384   }
 385
 386   /// use_instr_iterator/use_instr_begin/use_instr_end - Walk all uses of the
 387   /// specified register, stepping by MachineInstr.
 388   typedef defusechain_instr_iterator<true,false,false,false,true,false>
 389           use_instr_iterator;
 390   use_instr_iterator use_instr_begin(unsigned RegNo) const {
 391     return use_instr_iterator(getRegUseDefListHead(RegNo));
 392   }
 393   static use_instr_iterator use_instr_end() { return use_instr_iterator(0); }
 394
 395   inline iterator_range<use_instr_iterator>
 396   use_instructions(unsigned Reg) const {
 397     return iterator_range<use_instr_iterator>(use_instr_begin(Reg),
 398                                               use_instr_end());
 399   }
 400
 401   /// use_bundle_iterator/use_bundle_begin/use_bundle_end - Walk all uses of the
 402   /// specified register, stepping by bundle.
 403   typedef defusechain_instr_iterator<true,false,false,false,false,true>
 404           use_bundle_iterator;
 405   use_bundle_iterator use_bundle_begin(unsigned RegNo) const {
 406     return use_bundle_iterator(getRegUseDefListHead(RegNo));
 407   }
 408   static use_bundle_iterator use_bundle_end() { return use_bundle_iterator(0); }
 409
 410   inline iterator_range<use_bundle_iterator> use_bundles(unsigned Reg) const {
 411     return iterator_range<use_bundle_iterator>(use_bundle_begin(Reg),
 412                                                use_bundle_end());
 413   }
 414
 415   /// use_empty - Return true if there are no instructions using the specified
 416   /// register.
 417   bool use_empty(unsigned RegNo) const { return use_begin(RegNo) == use_end(); }
 418
 419   /// hasOneUse - Return true if there is exactly one instruction using the
 420   /// specified register.
 421   bool hasOneUse(unsigned RegNo) const {
 422     use_iterator UI = use_begin(RegNo);
 423     if (UI == use_end())
 424       return false;
 425     return ++UI == use_end();
 426   }
 427
 428   /// use_nodbg_iterator/use_nodbg_begin/use_nodbg_end - Walk all uses of the
 429   /// specified register, skipping those marked as Debug.
 430   typedef defusechain_iterator<true,false,true,true,false,false>
 431           use_nodbg_iterator;
 432   use_nodbg_iterator use_nodbg_begin(unsigned RegNo) const {
 433     return use_nodbg_iterator(getRegUseDefListHead(RegNo));
 434   }
 435   static use_nodbg_iterator use_nodbg_end() { return use_nodbg_iterator(0); }
 436
 437   inline iterator_range<use_nodbg_iterator>
 438   use_nodbg_operands(unsigned Reg) const {
 439     return iterator_range<use_nodbg_iterator>(use_nodbg_begin(Reg),
 440                                               use_nodbg_end());
 441   }
 442
 443   /// use_instr_nodbg_iterator/use_instr_nodbg_begin/use_instr_nodbg_end - Walk
 444   /// all uses of the specified register, stepping by MachineInstr, skipping
 445   /// those marked as Debug.
 446   typedef defusechain_instr_iterator<true,false,true,false,true,false>
 447           use_instr_nodbg_iterator;
 448   use_instr_nodbg_iterator use_instr_nodbg_begin(unsigned RegNo) const {
 449     return use_instr_nodbg_iterator(getRegUseDefListHead(RegNo));
 450   }
 451   static use_instr_nodbg_iterator use_instr_nodbg_end() {
 452     return use_instr_nodbg_iterator(0);
 453   }
 454
 455   inline iterator_range<use_instr_nodbg_iterator>
 456   use_nodbg_instructions(unsigned Reg) const {
 457     return iterator_range<use_instr_nodbg_iterator>(use_instr_nodbg_begin(Reg),
 458                                                     use_instr_nodbg_end());
 459   }
 460
 461   /// use_bundle_nodbg_iterator/use_bundle_nodbg_begin/use_bundle_nodbg_end - Walk
 462   /// all uses of the specified register, stepping by bundle, skipping
 463   /// those marked as Debug.
 464   typedef defusechain_instr_iterator<true,false,true,false,false,true>
 465           use_bundle_nodbg_iterator;
 466   use_bundle_nodbg_iterator use_bundle_nodbg_begin(unsigned RegNo) const {
 467     return use_bundle_nodbg_iterator(getRegUseDefListHead(RegNo));
 468   }
 469   static use_bundle_nodbg_iterator use_bundle_nodbg_end() {
 470     return use_bundle_nodbg_iterator(0);
 471   }
 472
 473   inline iterator_range<use_bundle_nodbg_iterator>
 474   use_nodbg_bundles(unsigned Reg) const {
 475     return iterator_range<use_bundle_nodbg_iterator>(use_bundle_nodbg_begin(Reg),
 476                                                      use_bundle_nodbg_end());
 477   }
 478
 479   /// use_nodbg_empty - Return true if there are no non-Debug instructions
 480   /// using the specified register.
 481   bool use_nodbg_empty(unsigned RegNo) const {
 482     return use_nodbg_begin(RegNo) == use_nodbg_end();
 483   }
 484
 485   /// hasOneNonDBGUse - Return true if there is exactly one non-Debug
 486   /// instruction using the specified register.
 487   bool hasOneNonDBGUse(unsigned RegNo) const;
 488
 489   /// replaceRegWith - Replace all instances of FromReg with ToReg in the
 490   /// machine function.  This is like llvm-level X->replaceAllUsesWith(Y),
 491   /// except that it also changes any definitions of the register as well.
 492   ///
 493   /// Note that it is usually necessary to first constrain ToReg's register
 494   /// class to match the FromReg constraints using:
 495   ///
 496   ///   constrainRegClass(ToReg, getRegClass(FromReg))
 497   ///
 498   /// That function will return NULL if the virtual registers have incompatible
 499   /// constraints.
 500   void replaceRegWith(unsigned FromReg, unsigned ToReg);
 501
 502   /// getVRegDef - Return the machine instr that defines the specified virtual
 503   /// register or null if none is found.  This assumes that the code is in SSA
 504   /// form, so there should only be one definition.
 505   MachineInstr *getVRegDef(unsigned Reg) const;
 506
 507   /// getUniqueVRegDef - Return the unique machine instr that defines the
 508   /// specified virtual register or null if none is found.  If there are
 509   /// multiple definitions or no definition, return null.
 510   MachineInstr *getUniqueVRegDef(unsigned Reg) const;
 511
 512   /// clearKillFlags - Iterate over all the uses of the given register and
 513   /// clear the kill flag from the MachineOperand. This function is used by
 514   /// optimization passes which extend register lifetimes and need only
 515   /// preserve conservative kill flag information.
 516   void clearKillFlags(unsigned Reg) const;
 517
 518 #ifndef NDEBUG
 519   void dumpUses(unsigned RegNo) const;
 520 #endif
 521
 522   /// isConstantPhysReg - Returns true if PhysReg is unallocatable and constant
 523   /// throughout the function.  It is safe to move instructions that read such
 524   /// a physreg.
 525   bool isConstantPhysReg(unsigned PhysReg, const MachineFunction &MF) const;
 526
 527   /// Get an iterator over the pressure sets affected by the given physical or
 528   /// virtual register. If RegUnit is physical, it must be a register unit (from
 529   /// MCRegUnitIterator).
 530   PSetIterator getPressureSets(unsigned RegUnit) const;
 531
 532   //===--------------------------------------------------------------------===//
 533   // Virtual Register Info
 534   //===--------------------------------------------------------------------===//
 535
 536   /// getRegClass - Return the register class of the specified virtual register.
 537   ///
 538   const TargetRegisterClass *getRegClass(unsigned Reg) const {
 539     return VRegInfo[Reg].first;
 540   }
 541
 542   /// setRegClass - Set the register class of the specified virtual register.
 543   ///
 544   void setRegClass(unsigned Reg, const TargetRegisterClass *RC);
 545
 546   /// constrainRegClass - Constrain the register class of the specified virtual
 547   /// register to be a common subclass of RC and the current register class,
 548   /// but only if the new class has at least MinNumRegs registers.  Return the
 549   /// new register class, or NULL if no such class exists.
 550   /// This should only be used when the constraint is known to be trivial, like
 551   /// GR32 -> GR32_NOSP. Beware of increasing register pressure.
 552   ///
 553   const TargetRegisterClass *constrainRegClass(unsigned Reg,
 554                                                const TargetRegisterClass *RC,
 555                                                unsigned MinNumRegs = 0);
 556
 557   /// recomputeRegClass - Try to find a legal super-class of Reg's register
 558   /// class that still satisfies the constraints from the instructions using
 559   /// Reg.  Returns true if Reg was upgraded.
 560   ///
 561   /// This method can be used after constraints have been removed from a
 562   /// virtual register, for example after removing instructions or splitting
 563   /// the live range.
 564   ///
 565   bool recomputeRegClass(unsigned Reg, const TargetMachine&);
 566
 567   /// createVirtualRegister - Create and return a new virtual register in the
 568   /// function with the specified register class.
 569   ///
 570   unsigned createVirtualRegister(const TargetRegisterClass *RegClass);
 571
 572   /// getNumVirtRegs - Return the number of virtual registers created.
 573   ///
 574   unsigned getNumVirtRegs() const { return VRegInfo.size(); }
 575
 576   /// clearVirtRegs - Remove all virtual registers (after physreg assignment).
 577   void clearVirtRegs();
 578
 579   /// setRegAllocationHint - Specify a register allocation hint for the
 580   /// specified virtual register.
 581   void setRegAllocationHint(unsigned Reg, unsigned Type, unsigned PrefReg) {
 582     RegAllocHints[Reg].first  = Type;
 583     RegAllocHints[Reg].second = PrefReg;
 584   }
 585
 586   /// getRegAllocationHint - Return the register allocation hint for the
 587   /// specified virtual register.
 588   std::pair<unsigned, unsigned>
 589   getRegAllocationHint(unsigned Reg) const {
 590     return RegAllocHints[Reg];
 591   }
 592
 593   /// getSimpleHint - Return the preferred register allocation hint, or 0 if a
 594   /// standard simple hint (Type == 0) is not set.
 595   unsigned getSimpleHint(unsigned Reg) const {
 596     std::pair<unsigned, unsigned> Hint = getRegAllocationHint(Reg);
 597     return Hint.first ? 0 : Hint.second;
 598   }
 599
 600   /// markUsesInDebugValueAsUndef - Mark every DBG_VALUE referencing the
 601   /// specified register as undefined which causes the DBG_VALUE to be
 602   /// deleted during LiveDebugVariables analysis.
 603   void markUsesInDebugValueAsUndef(unsigned Reg) const;
 604
 605   //===--------------------------------------------------------------------===//
 606   // Physical Register Use Info
 607   //===--------------------------------------------------------------------===//
 608
 609   /// isPhysRegUsed - Return true if the specified register is used in this
 610   /// function. Also check for clobbered aliases and registers clobbered by
 611   /// function calls with register mask operands.
 612   ///
 613   /// This only works after register allocation. It is primarily used by
 614   /// PrologEpilogInserter to determine which callee-saved registers need
 615   /// spilling.
 616   bool isPhysRegUsed(unsigned Reg) const {
 617     if (UsedPhysRegMask.test(Reg))
 618       return true;
 619     for (MCRegUnitIterator Units(Reg, getTargetRegisterInfo());
 620          Units.isValid(); ++Units)
 621       if (UsedRegUnits.test(*Units))
 622         return true;
 623     return false;
 624   }
 625
 626   /// Mark the specified register unit as used in this function.
 627   /// This should only be called during and after register allocation.
 628   void setRegUnitUsed(unsigned RegUnit) {
 629     UsedRegUnits.set(RegUnit);
 630   }
 631
 632   /// setPhysRegUsed - Mark the specified register used in this function.
 633   /// This should only be called during and after register allocation.
 634   void setPhysRegUsed(unsigned Reg) {
 635     for (MCRegUnitIterator Units(Reg, getTargetRegisterInfo());
 636          Units.isValid(); ++Units)
 637       UsedRegUnits.set(*Units);
 638   }
 639
 640   /// addPhysRegsUsedFromRegMask - Mark any registers not in RegMask as used.
 641   /// This corresponds to the bit mask attached to register mask operands.
 642   void addPhysRegsUsedFromRegMask(const uint32_t *RegMask) {
 643     UsedPhysRegMask.setBitsNotInMask(RegMask);
 644   }
 645
 646   /// setPhysRegUnused - Mark the specified register unused in this function.
 647   /// This should only be called during and after register allocation.
 648   void setPhysRegUnused(unsigned Reg) {
 649     UsedPhysRegMask.reset(Reg);
 650     for (MCRegUnitIterator Units(Reg, getTargetRegisterInfo());
 651          Units.isValid(); ++Units)
 652       UsedRegUnits.reset(*Units);
 653   }
 654
 655
 656   //===--------------------------------------------------------------------===//
 657   // Reserved Register Info
 658   //===--------------------------------------------------------------------===//
 659   //
 660   // The set of reserved registers must be invariant during register
 661   // allocation.  For example, the target cannot suddenly decide it needs a
 662   // frame pointer when the register allocator has already used the frame
 663   // pointer register for something else.
 664   //
 665   // These methods can be used by target hooks like hasFP() to avoid changing
 666   // the reserved register set during register allocation.
 667
 668   /// freezeReservedRegs - Called by the register allocator to freeze the set
 669   /// of reserved registers before allocation begins.
 670   void freezeReservedRegs(const MachineFunction&);
 671
 672   /// reservedRegsFrozen - Returns true after freezeReservedRegs() was called
 673   /// to ensure the set of reserved registers stays constant.
 674   bool reservedRegsFrozen() const {
 675     return !ReservedRegs.empty();
 676   }
 677
 678   /// canReserveReg - Returns true if PhysReg can be used as a reserved
 679   /// register.  Any register can be reserved before freezeReservedRegs() is
 680   /// called.
 681   bool canReserveReg(unsigned PhysReg) const {
 682     return !reservedRegsFrozen() || ReservedRegs.test(PhysReg);
 683   }
 684
 685   /// getReservedRegs - Returns a reference to the frozen set of reserved
 686   /// registers. This method should always be preferred to calling
 687   /// TRI::getReservedRegs() when possible.
 688   const BitVector &getReservedRegs() const {
 689     assert(reservedRegsFrozen() &&
 690            "Reserved registers haven't been frozen yet. "
 691            "Use TRI::getReservedRegs().");
 692     return ReservedRegs;
 693   }
 694
 695   /// isReserved - Returns true when PhysReg is a reserved register.
 696   ///
 697   /// Reserved registers may belong to an allocatable register class, but the
 698   /// target has explicitly requested that they are not used.
 699   ///
 700   bool isReserved(unsigned PhysReg) const {
 701     return getReservedRegs().test(PhysReg);
 702   }
 703
 704   /// isAllocatable - Returns true when PhysReg belongs to an allocatable
 705   /// register class and it hasn't been reserved.
 706   ///
 707   /// Allocatable registers may show up in the allocation order of some virtual
 708   /// register, so a register allocator needs to track its liveness and
 709   /// availability.
 710   bool isAllocatable(unsigned PhysReg) const {
 711     return getTargetRegisterInfo()->isInAllocatableClass(PhysReg) &&
 712       !isReserved(PhysReg);
 713   }
 714
 715   //===--------------------------------------------------------------------===//
 716   // LiveIn Management
 717   //===--------------------------------------------------------------------===//
 718
 719   /// addLiveIn - Add the specified register as a live-in.  Note that it
 720   /// is an error to add the same register to the same set more than once.
 721   void addLiveIn(unsigned Reg, unsigned vreg = 0) {
 722     LiveIns.push_back(std::make_pair(Reg, vreg));
 723   }
 724
 725   // Iteration support for the live-ins set.  It's kept in sorted order
 726   // by register number.
 727   typedef std::vector<std::pair<unsigned,unsigned> >::const_iterator
 728   livein_iterator;
 729   livein_iterator livein_begin() const { return LiveIns.begin(); }
 730   livein_iterator livein_end()   const { return LiveIns.end(); }
 731   bool            livein_empty() const { return LiveIns.empty(); }
 732
 733   bool isLiveIn(unsigned Reg) const;
 734
 735   /// getLiveInPhysReg - If VReg is a live-in virtual register, return the
 736   /// corresponding live-in physical register.
 737   unsigned getLiveInPhysReg(unsigned VReg) const;
 738
 739   /// getLiveInVirtReg - If PReg is a live-in physical register, return the
 740   /// corresponding live-in physical register.
 741   unsigned getLiveInVirtReg(unsigned PReg) const;
 742
 743   /// EmitLiveInCopies - Emit copies to initialize livein virtual registers
 744   /// into the given entry block.
 745   void EmitLiveInCopies(MachineBasicBlock *EntryMBB,
 746                         const TargetRegisterInfo &TRI,
 747                         const TargetInstrInfo &TII);
 748
 749   /// defusechain_iterator - This class provides iterator support for machine
 750   /// operands in the function that use or define a specific register.  If
 751   /// ReturnUses is true it returns uses of registers, if ReturnDefs is true it
 752   /// returns defs.  If neither are true then you are silly and it always
 753   /// returns end().  If SkipDebug is true it skips uses marked Debug
 754   /// when incrementing.
 755   template<bool ReturnUses, bool ReturnDefs, bool SkipDebug,
 756            bool ByOperand, bool ByInstr, bool ByBundle>
 757   class defusechain_iterator
 758     : public std::iterator<std::forward_iterator_tag, MachineInstr, ptrdiff_t> {
 759     MachineOperand *Op;
 760     explicit defusechain_iterator(MachineOperand *op) : Op(op) {
 761       // If the first node isn't one we're interested in, advance to one that
 762       // we are interested in.
 763       if (op) {
 764         if ((!ReturnUses && op->isUse()) ||
 765             (!ReturnDefs && op->isDef()) ||
 766             (SkipDebug && op->isDebug()))
 767           advance();
 768       }
 769     }
 770     friend class MachineRegisterInfo;
 771
 772     void advance() {
 773       assert(Op && "Cannot increment end iterator!");
 774       Op = getNextOperandForReg(Op);
 775
 776       // All defs come before the uses, so stop def_iterator early.
 777       if (!ReturnUses) {
 778         if (Op) {
 779           if (Op->isUse())
 780             Op = 0;
 781           else
 782             assert(!Op->isDebug() && "Can't have debug defs");
 783         }
 784       } else {
 785         // If this is an operand we don't care about, skip it.
 786         while (Op && ((!ReturnDefs && Op->isDef()) ||
 787                       (SkipDebug && Op->isDebug())))
 788           Op = getNextOperandForReg(Op);
 789       }
 790     }
 791   public:
 792     typedef std::iterator<std::forward_iterator_tag,
 793                           MachineInstr, ptrdiff_t>::reference reference;
 794     typedef std::iterator<std::forward_iterator_tag,
 795                           MachineInstr, ptrdiff_t>::pointer pointer;
 796
 797     defusechain_iterator(const defusechain_iterator &I) : Op(I.Op) {}
 798     defusechain_iterator() : Op(0) {}
 799
 800     bool operator==(const defusechain_iterator &x) const {
 801       return Op == x.Op;
 802     }
 803     bool operator!=(const defusechain_iterator &x) const {
 804       return !operator==(x);
 805     }
 806
 807     /// atEnd - return true if this iterator is equal to reg_end() on the value.
 808     bool atEnd() const { return Op == 0; }
 809
 810     // Iterator traversal: forward iteration only
 811     defusechain_iterator &operator++() {          // Preincrement
 812       assert(Op && "Cannot increment end iterator!");
 813       if (ByOperand)
 814         advance();
 815       else if (ByInstr) {
 816         MachineInstr *P = Op->getParent();
 817         do {
 818           advance();
 819         } while (Op && Op->getParent() == P);
 820       } else if (ByBundle) {
 821         MachineInstr *P = getBundleStart(Op->getParent());
 822         do {
 823           advance();
 824         } while (Op && getBundleStart(Op->getParent()) == P);
 825       }
 826
 827       return *this;
 828     }
 829     defusechain_iterator operator++(int) {        // Postincrement
 830       defusechain_iterator tmp = *this; ++*this; return tmp;
 831     }
 832
 833     /// getOperandNo - Return the operand # of this MachineOperand in its
 834     /// MachineInstr.
 835     unsigned getOperandNo() const {
 836       assert(Op && "Cannot dereference end iterator!");
 837       return Op - &Op->getParent()->getOperand(0);
 838     }
 839
 840     // Retrieve a reference to the current operand.
 841     MachineOperand &operator*() const {
 842       assert(Op && "Cannot dereference end iterator!");
 843       return *Op;
 844     }
 845
 846     MachineOperand *operator->() const {
 847       assert(Op && "Cannot dereference end iterator!");
 848       return Op;
 849     }
 850   };
 851
 852   /// defusechain_iterator - This class provides iterator support for machine
 853   /// operands in the function that use or define a specific register.  If
 854   /// ReturnUses is true it returns uses of registers, if ReturnDefs is true it
 855   /// returns defs.  If neither are true then you are silly and it always
 856   /// returns end().  If SkipDebug is true it skips uses marked Debug
 857   /// when incrementing.
 858   template<bool ReturnUses, bool ReturnDefs, bool SkipDebug,
 859            bool ByOperand, bool ByInstr, bool ByBundle>
 860   class defusechain_instr_iterator
 861     : public std::iterator<std::forward_iterator_tag, MachineInstr, ptrdiff_t> {
 862     MachineOperand *Op;
 863     explicit defusechain_instr_iterator(MachineOperand *op) : Op(op) {
 864       // If the first node isn't one we're interested in, advance to one that
 865       // we are interested in.
 866       if (op) {
 867         if ((!ReturnUses && op->isUse()) ||
 868             (!ReturnDefs && op->isDef()) ||
 869             (SkipDebug && op->isDebug()))
 870           advance();
 871       }
 872     }
 873     friend class MachineRegisterInfo;
 874
 875     void advance() {
 876       assert(Op && "Cannot increment end iterator!");
 877       Op = getNextOperandForReg(Op);
 878
 879       // All defs come before the uses, so stop def_iterator early.
 880       if (!ReturnUses) {
 881         if (Op) {
 882           if (Op->isUse())
 883             Op = 0;
 884           else
 885             assert(!Op->isDebug() && "Can't have debug defs");
 886         }
 887       } else {
 888         // If this is an operand we don't care about, skip it.
 889         while (Op && ((!ReturnDefs && Op->isDef()) ||
 890                       (SkipDebug && Op->isDebug())))
 891           Op = getNextOperandForReg(Op);
 892       }
 893     }
 894   public:
 895     typedef std::iterator<std::forward_iterator_tag,
 896                           MachineInstr, ptrdiff_t>::reference reference;
 897     typedef std::iterator<std::forward_iterator_tag,
 898                           MachineInstr, ptrdiff_t>::pointer pointer;
 899
 900     defusechain_instr_iterator(const defusechain_instr_iterator &I) : Op(I.Op){}
 901     defusechain_instr_iterator() : Op(0) {}
 902
 903     bool operator==(const defusechain_instr_iterator &x) const {
 904       return Op == x.Op;
 905     }
 906     bool operator!=(const defusechain_instr_iterator &x) const {
 907       return !operator==(x);
 908     }
 909
 910     /// atEnd - return true if this iterator is equal to reg_end() on the value.
 911     bool atEnd() const { return Op == 0; }
 912
 913     // Iterator traversal: forward iteration only
 914     defusechain_instr_iterator &operator++() {          // Preincrement
 915       assert(Op && "Cannot increment end iterator!");
 916       if (ByOperand)
 917         advance();
 918       else if (ByInstr) {
 919         MachineInstr *P = Op->getParent();
 920         do {
 921           advance();
 922         } while (Op && Op->getParent() == P);
 923       } else if (ByBundle) {
 924         MachineInstr *P = getBundleStart(Op->getParent());
 925         do {
 926           advance();
 927         } while (Op && getBundleStart(Op->getParent()) == P);
 928       }
 929
 930       return *this;
 931     }
 932     defusechain_instr_iterator operator++(int) {        // Postincrement
 933       defusechain_instr_iterator tmp = *this; ++*this; return tmp;
 934     }
 935
 936     // Retrieve a reference to the current operand.
 937     MachineInstr &operator*() const {
 938       assert(Op && "Cannot dereference end iterator!");
 939       if (ByBundle) return *(getBundleStart(Op->getParent()));
 940       return *Op->getParent();
 941     }
 942
 943     MachineInstr *operator->() const {
 944       assert(Op && "Cannot dereference end iterator!");
 945       if (ByBundle) return getBundleStart(Op->getParent());
 946       return Op->getParent();
 947     }
 948   };
 949 };
 950
 951 /// Iterate over the pressure sets affected by the given physical or virtual
 952 /// register. If Reg is physical, it must be a register unit (from
 953 /// MCRegUnitIterator).
 954 class PSetIterator {
 955   const int *PSet;
 956   unsigned Weight;
 957 public:
 958   PSetIterator(): PSet(0), Weight(0) {}
 959   PSetIterator(unsigned RegUnit, const MachineRegisterInfo *MRI) {
 960     const TargetRegisterInfo *TRI = MRI->getTargetRegisterInfo();
 961     if (TargetRegisterInfo::isVirtualRegister(RegUnit)) {
 962       const TargetRegisterClass *RC = MRI->getRegClass(RegUnit);
 963       PSet = TRI->getRegClassPressureSets(RC);
 964       Weight = TRI->getRegClassWeight(RC).RegWeight;
 965     }
 966     else {
 967       PSet = TRI->getRegUnitPressureSets(RegUnit);
 968       Weight = TRI->getRegUnitWeight(RegUnit);
 969     }
 970     if (*PSet == -1)
 971       PSet = 0;
 972   }
 973   bool isValid() const { return PSet; }
 974
 975   unsigned getWeight() const { return Weight; }
 976
 977   unsigned operator*() const { return *PSet; }
 978
 979   void operator++() {
 980     assert(isValid() && "Invalid PSetIterator.");
 981     ++PSet;
 982     if (*PSet == -1)
 983       PSet = 0;
 984   }
 985 };
 986
 987 inline PSetIterator MachineRegisterInfo::
 988 getPressureSets(unsigned RegUnit) const {
 989   return PSetIterator(RegUnit, this);
 990 }
 991
 992 } // End llvm namespace
 993
 994 #endif