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