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