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