contrib/llvm/include/llvm/CodeGen/MachineFunction.h

   1 //===- llvm/CodeGen/MachineFunction.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 // Collect native machine code for a function.  This class contains a list of
  11 // MachineBasicBlock instances that make up the current compiled function.
  12 //
  13 // This class also contains pointers to various classes which hold
  14 // target-specific information about the generated code.
  15 //
  16 //===----------------------------------------------------------------------===//
  17
  18 #ifndef LLVM_CODEGEN_MACHINEFUNCTION_H
  19 #define LLVM_CODEGEN_MACHINEFUNCTION_H
  20
  21 #include "llvm/ADT/ArrayRef.h"
  22 #include "llvm/ADT/BitVector.h"
  23 #include "llvm/ADT/DenseMap.h"
  24 #include "llvm/ADT/GraphTraits.h"
  25 #include "llvm/ADT/Optional.h"
  26 #include "llvm/ADT/SmallVector.h"
  27 #include "llvm/ADT/StringRef.h"
  28 #include "llvm/ADT/ilist.h"
  29 #include "llvm/ADT/iterator.h"
  30 #include "llvm/Analysis/EHPersonalities.h"
  31 #include "llvm/CodeGen/MachineBasicBlock.h"
  32 #include "llvm/CodeGen/MachineInstr.h"
  33 #include "llvm/CodeGen/MachineMemOperand.h"
  34 #include "llvm/IR/DebugLoc.h"
  35 #include "llvm/IR/Instructions.h"
  36 #include "llvm/IR/Metadata.h"
  37 #include "llvm/MC/MCDwarf.h"
  38 #include "llvm/MC/MCSymbol.h"
  39 #include "llvm/Support/Allocator.h"
  40 #include "llvm/Support/ArrayRecycler.h"
  41 #include "llvm/Support/AtomicOrdering.h"
  42 #include "llvm/Support/Compiler.h"
  43 #include "llvm/Support/ErrorHandling.h"
  44 #include "llvm/Support/Recycler.h"
  45 #include <cassert>
  46 #include <cstdint>
  47 #include <memory>
  48 #include <utility>
  49 #include <vector>
  50
  51 namespace llvm {
  52
  53 class BasicBlock;
  54 class BlockAddress;
  55 class DataLayout;
  56 class DIExpression;
  57 class DILocalVariable;
  58 class DILocation;
  59 class Function;
  60 class GlobalValue;
  61 class MachineConstantPool;
  62 class MachineFrameInfo;
  63 class MachineFunction;
  64 class MachineJumpTableInfo;
  65 class MachineModuleInfo;
  66 class MachineRegisterInfo;
  67 class MCContext;
  68 class MCInstrDesc;
  69 class Pass;
  70 class PseudoSourceValueManager;
  71 class raw_ostream;
  72 class SlotIndexes;
  73 class TargetMachine;
  74 class TargetRegisterClass;
  75 class TargetSubtargetInfo;
  76 struct WinEHFuncInfo;
  77
  78 template <> struct ilist_alloc_traits<MachineBasicBlock> {
  79   void deleteNode(MachineBasicBlock *MBB);
  80 };
  81
  82 template <> struct ilist_callback_traits<MachineBasicBlock> {
  83   void addNodeToList(MachineBasicBlock* MBB);
  84   void removeNodeFromList(MachineBasicBlock* MBB);
  85
  86   template <class Iterator>
  87   void transferNodesFromList(ilist_callback_traits &OldList, Iterator, Iterator) {
  88     llvm_unreachable("Never transfer between lists");
  89   }
  90 };
  91
  92 /// MachineFunctionInfo - This class can be derived from and used by targets to
  93 /// hold private target-specific information for each MachineFunction.  Objects
  94 /// of type are accessed/created with MF::getInfo and destroyed when the
  95 /// MachineFunction is destroyed.
  96 struct MachineFunctionInfo {
  97   virtual ~MachineFunctionInfo();
  98
  99   /// \brief Factory function: default behavior is to call new using the
 100   /// supplied allocator.
 101   ///
 102   /// This function can be overridden in a derive class.
 103   template<typename Ty>
 104   static Ty *create(BumpPtrAllocator &Allocator, MachineFunction &MF) {
 105     return new (Allocator.Allocate<Ty>()) Ty(MF);
 106   }
 107 };
 108
 109 /// Properties which a MachineFunction may have at a given point in time.
 110 /// Each of these has checking code in the MachineVerifier, and passes can
 111 /// require that a property be set.
 112 class MachineFunctionProperties {
 113   // Possible TODO: Allow targets to extend this (perhaps by allowing the
 114   // constructor to specify the size of the bit vector)
 115   // Possible TODO: Allow requiring the negative (e.g. VRegsAllocated could be
 116   // stated as the negative of "has vregs"
 117
 118 public:
 119   // The properties are stated in "positive" form; i.e. a pass could require
 120   // that the property hold, but not that it does not hold.
 121
 122   // Property descriptions:
 123   // IsSSA: True when the machine function is in SSA form and virtual registers
 124   //  have a single def.
 125   // NoPHIs: The machine function does not contain any PHI instruction.
 126   // TracksLiveness: True when tracking register liveness accurately.
 127   //  While this property is set, register liveness information in basic block
 128   //  live-in lists and machine instruction operands (e.g. kill flags, implicit
 129   //  defs) is accurate. This means it can be used to change the code in ways
 130   //  that affect the values in registers, for example by the register
 131   //  scavenger.
 132   //  When this property is clear, liveness is no longer reliable.
 133   // NoVRegs: The machine function does not use any virtual registers.
 134   // Legalized: In GlobalISel: the MachineLegalizer ran and all pre-isel generic
 135   //  instructions have been legalized; i.e., all instructions are now one of:
 136   //   - generic and always legal (e.g., COPY)
 137   //   - target-specific
 138   //   - legal pre-isel generic instructions.
 139   // RegBankSelected: In GlobalISel: the RegBankSelect pass ran and all generic
 140   //  virtual registers have been assigned to a register bank.
 141   // Selected: In GlobalISel: the InstructionSelect pass ran and all pre-isel
 142   //  generic instructions have been eliminated; i.e., all instructions are now
 143   //  target-specific or non-pre-isel generic instructions (e.g., COPY).
 144   //  Since only pre-isel generic instructions can have generic virtual register
 145   //  operands, this also means that all generic virtual registers have been
 146   //  constrained to virtual registers (assigned to register classes) and that
 147   //  all sizes attached to them have been eliminated.
 148   enum class Property : unsigned {
 149     IsSSA,
 150     NoPHIs,
 151     TracksLiveness,
 152     NoVRegs,
 153     FailedISel,
 154     Legalized,
 155     RegBankSelected,
 156     Selected,
 157     LastProperty = Selected,
 158   };
 159
 160   bool hasProperty(Property P) const {
 161     return Properties[static_cast<unsigned>(P)];
 162   }
 163
 164   MachineFunctionProperties &set(Property P) {
 165     Properties.set(static_cast<unsigned>(P));
 166     return *this;
 167   }
 168
 169   MachineFunctionProperties &reset(Property P) {
 170     Properties.reset(static_cast<unsigned>(P));
 171     return *this;
 172   }
 173
 174   /// Reset all the properties.
 175   MachineFunctionProperties &reset() {
 176     Properties.reset();
 177     return *this;
 178   }
 179
 180   MachineFunctionProperties &set(const MachineFunctionProperties &MFP) {
 181     Properties |= MFP.Properties;
 182     return *this;
 183   }
 184
 185   MachineFunctionProperties &reset(const MachineFunctionProperties &MFP) {
 186     Properties.reset(MFP.Properties);
 187     return *this;
 188   }
 189
 190   // Returns true if all properties set in V (i.e. required by a pass) are set
 191   // in this.
 192   bool verifyRequiredProperties(const MachineFunctionProperties &V) const {
 193     return !V.Properties.test(Properties);
 194   }
 195
 196   /// Print the MachineFunctionProperties in human-readable form.
 197   void print(raw_ostream &OS) const;
 198
 199 private:
 200   BitVector Properties =
 201       BitVector(static_cast<unsigned>(Property::LastProperty)+1);
 202 };
 203
 204 struct SEHHandler {
 205   /// Filter or finally function. Null indicates a catch-all.
 206   const Function *FilterOrFinally;
 207
 208   /// Address of block to recover at. Null for a finally handler.
 209   const BlockAddress *RecoverBA;
 210 };
 211
 212 /// This structure is used to retain landing pad info for the current function.
 213 struct LandingPadInfo {
 214   MachineBasicBlock *LandingPadBlock;      // Landing pad block.
 215   SmallVector<MCSymbol *, 1> BeginLabels;  // Labels prior to invoke.
 216   SmallVector<MCSymbol *, 1> EndLabels;    // Labels after invoke.
 217   SmallVector<SEHHandler, 1> SEHHandlers;  // SEH handlers active at this lpad.
 218   MCSymbol *LandingPadLabel = nullptr;     // Label at beginning of landing pad.
 219   std::vector<int> TypeIds;                // List of type ids (filters negative).
 220
 221   explicit LandingPadInfo(MachineBasicBlock *MBB)
 222       : LandingPadBlock(MBB) {}
 223 };
 224
 225 class MachineFunction {
 226   const Function *Fn;
 227   const TargetMachine &Target;
 228   const TargetSubtargetInfo *STI;
 229   MCContext &Ctx;
 230   MachineModuleInfo &MMI;
 231
 232   // RegInfo - Information about each register in use in the function.
 233   MachineRegisterInfo *RegInfo;
 234
 235   // Used to keep track of target-specific per-machine function information for
 236   // the target implementation.
 237   MachineFunctionInfo *MFInfo;
 238
 239   // Keep track of objects allocated on the stack.
 240   MachineFrameInfo *FrameInfo;
 241
 242   // Keep track of constants which are spilled to memory
 243   MachineConstantPool *ConstantPool;
 244
 245   // Keep track of jump tables for switch instructions
 246   MachineJumpTableInfo *JumpTableInfo;
 247
 248   // Keeps track of Windows exception handling related data. This will be null
 249   // for functions that aren't using a funclet-based EH personality.
 250   WinEHFuncInfo *WinEHInfo = nullptr;
 251
 252   // Function-level unique numbering for MachineBasicBlocks.  When a
 253   // MachineBasicBlock is inserted into a MachineFunction is it automatically
 254   // numbered and this vector keeps track of the mapping from ID's to MBB's.
 255   std::vector<MachineBasicBlock*> MBBNumbering;
 256
 257   // Pool-allocate MachineFunction-lifetime and IR objects.
 258   BumpPtrAllocator Allocator;
 259
 260   // Allocation management for instructions in function.
 261   Recycler<MachineInstr> InstructionRecycler;
 262
 263   // Allocation management for operand arrays on instructions.
 264   ArrayRecycler<MachineOperand> OperandRecycler;
 265
 266   // Allocation management for basic blocks in function.
 267   Recycler<MachineBasicBlock> BasicBlockRecycler;
 268
 269   // List of machine basic blocks in function
 270   using BasicBlockListType = ilist<MachineBasicBlock>;
 271   BasicBlockListType BasicBlocks;
 272
 273   /// FunctionNumber - This provides a unique ID for each function emitted in
 274   /// this translation unit.
 275   ///
 276   unsigned FunctionNumber;
 277
 278   /// Alignment - The alignment of the function.
 279   unsigned Alignment;
 280
 281   /// ExposesReturnsTwice - True if the function calls setjmp or related
 282   /// functions with attribute "returns twice", but doesn't have
 283   /// the attribute itself.
 284   /// This is used to limit optimizations which cannot reason
 285   /// about the control flow of such functions.
 286   bool ExposesReturnsTwice = false;
 287
 288   /// True if the function includes any inline assembly.
 289   bool HasInlineAsm = false;
 290
 291   /// True if any WinCFI instruction have been emitted in this function.
 292   Optional<bool> HasWinCFI;
 293
 294   /// Current high-level properties of the IR of the function (e.g. is in SSA
 295   /// form or whether registers have been allocated)
 296   MachineFunctionProperties Properties;
 297
 298   // Allocation management for pseudo source values.
 299   std::unique_ptr<PseudoSourceValueManager> PSVManager;
 300
 301   /// List of moves done by a function's prolog.  Used to construct frame maps
 302   /// by debug and exception handling consumers.
 303   std::vector<MCCFIInstruction> FrameInstructions;
 304
 305   /// \name Exception Handling
 306   /// \{
 307
 308   /// List of LandingPadInfo describing the landing pad information.
 309   std::vector<LandingPadInfo> LandingPads;
 310
 311   /// Map a landing pad's EH symbol to the call site indexes.
 312   DenseMap<MCSymbol*, SmallVector<unsigned, 4>> LPadToCallSiteMap;
 313
 314   /// Map of invoke call site index values to associated begin EH_LABEL.
 315   DenseMap<MCSymbol*, unsigned> CallSiteMap;
 316
 317   bool CallsEHReturn = false;
 318   bool CallsUnwindInit = false;
 319   bool HasEHFunclets = false;
 320
 321   /// List of C++ TypeInfo used.
 322   std::vector<const GlobalValue *> TypeInfos;
 323
 324   /// List of typeids encoding filters used.
 325   std::vector<unsigned> FilterIds;
 326
 327   /// List of the indices in FilterIds corresponding to filter terminators.
 328   std::vector<unsigned> FilterEnds;
 329
 330   EHPersonality PersonalityTypeCache = EHPersonality::Unknown;
 331
 332   /// \}
 333
 334   /// Clear all the members of this MachineFunction, but the ones used
 335   /// to initialize again the MachineFunction.
 336   /// More specifically, this deallocates all the dynamically allocated
 337   /// objects and get rid of all the XXXInfo data structure, but keep
 338   /// unchanged the references to Fn, Target, MMI, and FunctionNumber.
 339   void clear();
 340   /// Allocate and initialize the different members.
 341   /// In particular, the XXXInfo data structure.
 342   /// \pre Fn, Target, MMI, and FunctionNumber are properly set.
 343   void init();
 344
 345 public:
 346   struct VariableDbgInfo {
 347     const DILocalVariable *Var;
 348     const DIExpression *Expr;
 349     unsigned Slot;
 350     const DILocation *Loc;
 351
 352     VariableDbgInfo(const DILocalVariable *Var, const DIExpression *Expr,
 353                     unsigned Slot, const DILocation *Loc)
 354         : Var(Var), Expr(Expr), Slot(Slot), Loc(Loc) {}
 355   };
 356   using VariableDbgInfoMapTy = SmallVector<VariableDbgInfo, 4>;
 357   VariableDbgInfoMapTy VariableDbgInfos;
 358
 359   MachineFunction(const Function *Fn, const TargetMachine &TM,
 360                   unsigned FunctionNum, MachineModuleInfo &MMI);
 361   MachineFunction(const MachineFunction &) = delete;
 362   MachineFunction &operator=(const MachineFunction &) = delete;
 363   ~MachineFunction();
 364
 365   /// Reset the instance as if it was just created.
 366   void reset() {
 367     clear();
 368     init();
 369   }
 370
 371   MachineModuleInfo &getMMI() const { return MMI; }
 372   MCContext &getContext() const { return Ctx; }
 373
 374   PseudoSourceValueManager &getPSVManager() const { return *PSVManager; }
 375
 376   /// Return the DataLayout attached to the Module associated to this MF.
 377   const DataLayout &getDataLayout() const;
 378
 379   /// getFunction - Return the LLVM function that this machine code represents
 380   const Function *getFunction() const { return Fn; }
 381
 382   /// getName - Return the name of the corresponding LLVM function.
 383   StringRef getName() const;
 384
 385   /// getFunctionNumber - Return a unique ID for the current function.
 386   unsigned getFunctionNumber() const { return FunctionNumber; }
 387
 388   /// getTarget - Return the target machine this machine code is compiled with
 389   const TargetMachine &getTarget() const { return Target; }
 390
 391   /// getSubtarget - Return the subtarget for which this machine code is being
 392   /// compiled.
 393   const TargetSubtargetInfo &getSubtarget() const { return *STI; }
 394   void setSubtarget(const TargetSubtargetInfo *ST) { STI = ST; }
 395
 396   /// getSubtarget - This method returns a pointer to the specified type of
 397   /// TargetSubtargetInfo.  In debug builds, it verifies that the object being
 398   /// returned is of the correct type.
 399   template<typename STC> const STC &getSubtarget() const {
 400     return *static_cast<const STC *>(STI);
 401   }
 402
 403   /// getRegInfo - Return information about the registers currently in use.
 404   MachineRegisterInfo &getRegInfo() { return *RegInfo; }
 405   const MachineRegisterInfo &getRegInfo() const { return *RegInfo; }
 406
 407   /// getFrameInfo - Return the frame info object for the current function.
 408   /// This object contains information about objects allocated on the stack
 409   /// frame of the current function in an abstract way.
 410   MachineFrameInfo &getFrameInfo() { return *FrameInfo; }
 411   const MachineFrameInfo &getFrameInfo() const { return *FrameInfo; }
 412
 413   /// getJumpTableInfo - Return the jump table info object for the current
 414   /// function.  This object contains information about jump tables in the
 415   /// current function.  If the current function has no jump tables, this will
 416   /// return null.
 417   const MachineJumpTableInfo *getJumpTableInfo() const { return JumpTableInfo; }
 418   MachineJumpTableInfo *getJumpTableInfo() { return JumpTableInfo; }
 419
 420   /// getOrCreateJumpTableInfo - Get the JumpTableInfo for this function, if it
 421   /// does already exist, allocate one.
 422   MachineJumpTableInfo *getOrCreateJumpTableInfo(unsigned JTEntryKind);
 423
 424   /// getConstantPool - Return the constant pool object for the current
 425   /// function.
 426   MachineConstantPool *getConstantPool() { return ConstantPool; }
 427   const MachineConstantPool *getConstantPool() const { return ConstantPool; }
 428
 429   /// getWinEHFuncInfo - Return information about how the current function uses
 430   /// Windows exception handling. Returns null for functions that don't use
 431   /// funclets for exception handling.
 432   const WinEHFuncInfo *getWinEHFuncInfo() const { return WinEHInfo; }
 433   WinEHFuncInfo *getWinEHFuncInfo() { return WinEHInfo; }
 434
 435   /// getAlignment - Return the alignment (log2, not bytes) of the function.
 436   unsigned getAlignment() const { return Alignment; }
 437
 438   /// setAlignment - Set the alignment (log2, not bytes) of the function.
 439   void setAlignment(unsigned A) { Alignment = A; }
 440
 441   /// ensureAlignment - Make sure the function is at least 1 << A bytes aligned.
 442   void ensureAlignment(unsigned A) {
 443     if (Alignment < A) Alignment = A;
 444   }
 445
 446   /// exposesReturnsTwice - Returns true if the function calls setjmp or
 447   /// any other similar functions with attribute "returns twice" without
 448   /// having the attribute itself.
 449   bool exposesReturnsTwice() const {
 450     return ExposesReturnsTwice;
 451   }
 452
 453   /// setCallsSetJmp - Set a flag that indicates if there's a call to
 454   /// a "returns twice" function.
 455   void setExposesReturnsTwice(bool B) {
 456     ExposesReturnsTwice = B;
 457   }
 458
 459   /// Returns true if the function contains any inline assembly.
 460   bool hasInlineAsm() const {
 461     return HasInlineAsm;
 462   }
 463
 464   /// Set a flag that indicates that the function contains inline assembly.
 465   void setHasInlineAsm(bool B) {
 466     HasInlineAsm = B;
 467   }
 468
 469   bool hasWinCFI() const {
 470     assert(HasWinCFI.hasValue() && "HasWinCFI not set yet!");
 471     return *HasWinCFI;
 472   }
 473   void setHasWinCFI(bool v) { HasWinCFI = v; }
 474
 475   /// Get the function properties
 476   const MachineFunctionProperties &getProperties() const { return Properties; }
 477   MachineFunctionProperties &getProperties() { return Properties; }
 478
 479   /// getInfo - Keep track of various per-function pieces of information for
 480   /// backends that would like to do so.
 481   ///
 482   template<typename Ty>
 483   Ty *getInfo() {
 484     if (!MFInfo)
 485       MFInfo = Ty::template create<Ty>(Allocator, *this);
 486     return static_cast<Ty*>(MFInfo);
 487   }
 488
 489   template<typename Ty>
 490   const Ty *getInfo() const {
 491      return const_cast<MachineFunction*>(this)->getInfo<Ty>();
 492   }
 493
 494   /// getBlockNumbered - MachineBasicBlocks are automatically numbered when they
 495   /// are inserted into the machine function.  The block number for a machine
 496   /// basic block can be found by using the MBB::getNumber method, this method
 497   /// provides the inverse mapping.
 498   MachineBasicBlock *getBlockNumbered(unsigned N) const {
 499     assert(N < MBBNumbering.size() && "Illegal block number");
 500     assert(MBBNumbering[N] && "Block was removed from the machine function!");
 501     return MBBNumbering[N];
 502   }
 503
 504   /// Should we be emitting segmented stack stuff for the function
 505   bool shouldSplitStack() const;
 506
 507   /// getNumBlockIDs - Return the number of MBB ID's allocated.
 508   unsigned getNumBlockIDs() const { return (unsigned)MBBNumbering.size(); }
 509
 510   /// RenumberBlocks - This discards all of the MachineBasicBlock numbers and
 511   /// recomputes them.  This guarantees that the MBB numbers are sequential,
 512   /// dense, and match the ordering of the blocks within the function.  If a
 513   /// specific MachineBasicBlock is specified, only that block and those after
 514   /// it are renumbered.
 515   void RenumberBlocks(MachineBasicBlock *MBBFrom = nullptr);
 516
 517   /// print - Print out the MachineFunction in a format suitable for debugging
 518   /// to the specified stream.
 519   void print(raw_ostream &OS, const SlotIndexes* = nullptr) const;
 520
 521   /// viewCFG - This function is meant for use from the debugger.  You can just
 522   /// say 'call F->viewCFG()' and a ghostview window should pop up from the
 523   /// program, displaying the CFG of the current function with the code for each
 524   /// basic block inside.  This depends on there being a 'dot' and 'gv' program
 525   /// in your path.
 526   void viewCFG() const;
 527
 528   /// viewCFGOnly - This function is meant for use from the debugger.  It works
 529   /// just like viewCFG, but it does not include the contents of basic blocks
 530   /// into the nodes, just the label.  If you are only interested in the CFG
 531   /// this can make the graph smaller.
 532   ///
 533   void viewCFGOnly() const;
 534
 535   /// dump - Print the current MachineFunction to cerr, useful for debugger use.
 536   void dump() const;
 537
 538   /// Run the current MachineFunction through the machine code verifier, useful
 539   /// for debugger use.
 540   /// \returns true if no problems were found.
 541   bool verify(Pass *p = nullptr, const char *Banner = nullptr,
 542               bool AbortOnError = true) const;
 543
 544   // Provide accessors for the MachineBasicBlock list...
 545   using iterator = BasicBlockListType::iterator;
 546   using const_iterator = BasicBlockListType::const_iterator;
 547   using const_reverse_iterator = BasicBlockListType::const_reverse_iterator;
 548   using reverse_iterator = BasicBlockListType::reverse_iterator;
 549
 550   /// Support for MachineBasicBlock::getNextNode().
 551   static BasicBlockListType MachineFunction::*
 552   getSublistAccess(MachineBasicBlock *) {
 553     return &MachineFunction::BasicBlocks;
 554   }
 555
 556   /// addLiveIn - Add the specified physical register as a live-in value and
 557   /// create a corresponding virtual register for it.
 558   unsigned addLiveIn(unsigned PReg, const TargetRegisterClass *RC);
 559
 560   //===--------------------------------------------------------------------===//
 561   // BasicBlock accessor functions.
 562   //
 563   iterator                 begin()       { return BasicBlocks.begin(); }
 564   const_iterator           begin() const { return BasicBlocks.begin(); }
 565   iterator                 end  ()       { return BasicBlocks.end();   }
 566   const_iterator           end  () const { return BasicBlocks.end();   }
 567
 568   reverse_iterator        rbegin()       { return BasicBlocks.rbegin(); }
 569   const_reverse_iterator  rbegin() const { return BasicBlocks.rbegin(); }
 570   reverse_iterator        rend  ()       { return BasicBlocks.rend();   }
 571   const_reverse_iterator  rend  () const { return BasicBlocks.rend();   }
 572
 573   unsigned                  size() const { return (unsigned)BasicBlocks.size();}
 574   bool                     empty() const { return BasicBlocks.empty(); }
 575   const MachineBasicBlock &front() const { return BasicBlocks.front(); }
 576         MachineBasicBlock &front()       { return BasicBlocks.front(); }
 577   const MachineBasicBlock & back() const { return BasicBlocks.back(); }
 578         MachineBasicBlock & back()       { return BasicBlocks.back(); }
 579
 580   void push_back (MachineBasicBlock *MBB) { BasicBlocks.push_back (MBB); }
 581   void push_front(MachineBasicBlock *MBB) { BasicBlocks.push_front(MBB); }
 582   void insert(iterator MBBI, MachineBasicBlock *MBB) {
 583     BasicBlocks.insert(MBBI, MBB);
 584   }
 585   void splice(iterator InsertPt, iterator MBBI) {
 586     BasicBlocks.splice(InsertPt, BasicBlocks, MBBI);
 587   }
 588   void splice(iterator InsertPt, MachineBasicBlock *MBB) {
 589     BasicBlocks.splice(InsertPt, BasicBlocks, MBB);
 590   }
 591   void splice(iterator InsertPt, iterator MBBI, iterator MBBE) {
 592     BasicBlocks.splice(InsertPt, BasicBlocks, MBBI, MBBE);
 593   }
 594
 595   void remove(iterator MBBI) { BasicBlocks.remove(MBBI); }
 596   void remove(MachineBasicBlock *MBBI) { BasicBlocks.remove(MBBI); }
 597   void erase(iterator MBBI) { BasicBlocks.erase(MBBI); }
 598   void erase(MachineBasicBlock *MBBI) { BasicBlocks.erase(MBBI); }
 599
 600   template <typename Comp>
 601   void sort(Comp comp) {
 602     BasicBlocks.sort(comp);
 603   }
 604
 605   //===--------------------------------------------------------------------===//
 606   // Internal functions used to automatically number MachineBasicBlocks
 607
 608   /// \brief Adds the MBB to the internal numbering. Returns the unique number
 609   /// assigned to the MBB.
 610   unsigned addToMBBNumbering(MachineBasicBlock *MBB) {
 611     MBBNumbering.push_back(MBB);
 612     return (unsigned)MBBNumbering.size()-1;
 613   }
 614
 615   /// removeFromMBBNumbering - Remove the specific machine basic block from our
 616   /// tracker, this is only really to be used by the MachineBasicBlock
 617   /// implementation.
 618   void removeFromMBBNumbering(unsigned N) {
 619     assert(N < MBBNumbering.size() && "Illegal basic block #");
 620     MBBNumbering[N] = nullptr;
 621   }
 622
 623   /// CreateMachineInstr - Allocate a new MachineInstr. Use this instead
 624   /// of `new MachineInstr'.
 625   MachineInstr *CreateMachineInstr(const MCInstrDesc &MCID, const DebugLoc &DL,
 626                                    bool NoImp = false);
 627
 628   /// CloneMachineInstr - Create a new MachineInstr which is a copy of the
 629   /// 'Orig' instruction, identical in all ways except the instruction
 630   /// has no parent, prev, or next.
 631   ///
 632   /// See also TargetInstrInfo::duplicate() for target-specific fixes to cloned
 633   /// instructions.
 634   MachineInstr *CloneMachineInstr(const MachineInstr *Orig);
 635
 636   /// DeleteMachineInstr - Delete the given MachineInstr.
 637   void DeleteMachineInstr(MachineInstr *MI);
 638
 639   /// CreateMachineBasicBlock - Allocate a new MachineBasicBlock. Use this
 640   /// instead of `new MachineBasicBlock'.
 641   MachineBasicBlock *CreateMachineBasicBlock(const BasicBlock *bb = nullptr);
 642
 643   /// DeleteMachineBasicBlock - Delete the given MachineBasicBlock.
 644   void DeleteMachineBasicBlock(MachineBasicBlock *MBB);
 645
 646   /// getMachineMemOperand - Allocate a new MachineMemOperand.
 647   /// MachineMemOperands are owned by the MachineFunction and need not be
 648   /// explicitly deallocated.
 649   MachineMemOperand *getMachineMemOperand(
 650       MachinePointerInfo PtrInfo, MachineMemOperand::Flags f, uint64_t s,
 651       unsigned base_alignment, const AAMDNodes &AAInfo = AAMDNodes(),
 652       const MDNode *Ranges = nullptr,
 653       SyncScope::ID SSID = SyncScope::System,
 654       AtomicOrdering Ordering = AtomicOrdering::NotAtomic,
 655       AtomicOrdering FailureOrdering = AtomicOrdering::NotAtomic);
 656
 657   /// getMachineMemOperand - Allocate a new MachineMemOperand by copying
 658   /// an existing one, adjusting by an offset and using the given size.
 659   /// MachineMemOperands are owned by the MachineFunction and need not be
 660   /// explicitly deallocated.
 661   MachineMemOperand *getMachineMemOperand(const MachineMemOperand *MMO,
 662                                           int64_t Offset, uint64_t Size);
 663
 664   using OperandCapacity = ArrayRecycler<MachineOperand>::Capacity;
 665
 666   /// Allocate an array of MachineOperands. This is only intended for use by
 667   /// internal MachineInstr functions.
 668   MachineOperand *allocateOperandArray(OperandCapacity Cap) {
 669     return OperandRecycler.allocate(Cap, Allocator);
 670   }
 671
 672   /// Dellocate an array of MachineOperands and recycle the memory. This is
 673   /// only intended for use by internal MachineInstr functions.
 674   /// Cap must be the same capacity that was used to allocate the array.
 675   void deallocateOperandArray(OperandCapacity Cap, MachineOperand *Array) {
 676     OperandRecycler.deallocate(Cap, Array);
 677   }
 678
 679   /// \brief Allocate and initialize a register mask with @p NumRegister bits.
 680   uint32_t *allocateRegisterMask(unsigned NumRegister) {
 681     unsigned Size = (NumRegister + 31) / 32;
 682     uint32_t *Mask = Allocator.Allocate<uint32_t>(Size);
 683     for (unsigned i = 0; i != Size; ++i)
 684       Mask[i] = 0;
 685     return Mask;
 686   }
 687
 688   /// allocateMemRefsArray - Allocate an array to hold MachineMemOperand
 689   /// pointers.  This array is owned by the MachineFunction.
 690   MachineInstr::mmo_iterator allocateMemRefsArray(unsigned long Num);
 691
 692   /// extractLoadMemRefs - Allocate an array and populate it with just the
 693   /// load information from the given MachineMemOperand sequence.
 694   std::pair<MachineInstr::mmo_iterator,
 695             MachineInstr::mmo_iterator>
 696     extractLoadMemRefs(MachineInstr::mmo_iterator Begin,
 697                        MachineInstr::mmo_iterator End);
 698
 699   /// extractStoreMemRefs - Allocate an array and populate it with just the
 700   /// store information from the given MachineMemOperand sequence.
 701   std::pair<MachineInstr::mmo_iterator,
 702             MachineInstr::mmo_iterator>
 703     extractStoreMemRefs(MachineInstr::mmo_iterator Begin,
 704                         MachineInstr::mmo_iterator End);
 705
 706   /// Allocate a string and populate it with the given external symbol name.
 707   const char *createExternalSymbolName(StringRef Name);
 708
 709   //===--------------------------------------------------------------------===//
 710   // Label Manipulation.
 711
 712   /// getJTISymbol - Return the MCSymbol for the specified non-empty jump table.
 713   /// If isLinkerPrivate is specified, an 'l' label is returned, otherwise a
 714   /// normal 'L' label is returned.
 715   MCSymbol *getJTISymbol(unsigned JTI, MCContext &Ctx,
 716                          bool isLinkerPrivate = false) const;
 717
 718   /// getPICBaseSymbol - Return a function-local symbol to represent the PIC
 719   /// base.
 720   MCSymbol *getPICBaseSymbol() const;
 721
 722   /// Returns a reference to a list of cfi instructions in the function's
 723   /// prologue.  Used to construct frame maps for debug and exception handling
 724   /// comsumers.
 725   const std::vector<MCCFIInstruction> &getFrameInstructions() const {
 726     return FrameInstructions;
 727   }
 728
 729   LLVM_NODISCARD unsigned addFrameInst(const MCCFIInstruction &Inst) {
 730     FrameInstructions.push_back(Inst);
 731     return FrameInstructions.size() - 1;
 732   }
 733
 734   /// \name Exception Handling
 735   /// \{
 736
 737   bool callsEHReturn() const { return CallsEHReturn; }
 738   void setCallsEHReturn(bool b) { CallsEHReturn = b; }
 739
 740   bool callsUnwindInit() const { return CallsUnwindInit; }
 741   void setCallsUnwindInit(bool b) { CallsUnwindInit = b; }
 742
 743   bool hasEHFunclets() const { return HasEHFunclets; }
 744   void setHasEHFunclets(bool V) { HasEHFunclets = V; }
 745
 746   /// Find or create an LandingPadInfo for the specified MachineBasicBlock.
 747   LandingPadInfo &getOrCreateLandingPadInfo(MachineBasicBlock *LandingPad);
 748
 749   /// Remap landing pad labels and remove any deleted landing pads.
 750   void tidyLandingPads(DenseMap<MCSymbol*, uintptr_t> *LPMap = nullptr);
 751
 752   /// Return a reference to the landing pad info for the current function.
 753   const std::vector<LandingPadInfo> &getLandingPads() const {
 754     return LandingPads;
 755   }
 756
 757   /// Provide the begin and end labels of an invoke style call and associate it
 758   /// with a try landing pad block.
 759   void addInvoke(MachineBasicBlock *LandingPad,
 760                  MCSymbol *BeginLabel, MCSymbol *EndLabel);
 761
 762   /// Add a new panding pad.  Returns the label ID for the landing pad entry.
 763   MCSymbol *addLandingPad(MachineBasicBlock *LandingPad);
 764
 765   /// Provide the catch typeinfo for a landing pad.
 766   void addCatchTypeInfo(MachineBasicBlock *LandingPad,
 767                         ArrayRef<const GlobalValue *> TyInfo);
 768
 769   /// Provide the filter typeinfo for a landing pad.
 770   void addFilterTypeInfo(MachineBasicBlock *LandingPad,
 771                          ArrayRef<const GlobalValue *> TyInfo);
 772
 773   /// Add a cleanup action for a landing pad.
 774   void addCleanup(MachineBasicBlock *LandingPad);
 775
 776   void addSEHCatchHandler(MachineBasicBlock *LandingPad, const Function *Filter,
 777                           const BlockAddress *RecoverLabel);
 778
 779   void addSEHCleanupHandler(MachineBasicBlock *LandingPad,
 780                             const Function *Cleanup);
 781
 782   /// Return the type id for the specified typeinfo.  This is function wide.
 783   unsigned getTypeIDFor(const GlobalValue *TI);
 784
 785   /// Return the id of the filter encoded by TyIds.  This is function wide.
 786   int getFilterIDFor(std::vector<unsigned> &TyIds);
 787
 788   /// Map the landing pad's EH symbol to the call site indexes.
 789   void setCallSiteLandingPad(MCSymbol *Sym, ArrayRef<unsigned> Sites);
 790
 791   /// Get the call site indexes for a landing pad EH symbol.
 792   SmallVectorImpl<unsigned> &getCallSiteLandingPad(MCSymbol *Sym) {
 793     assert(hasCallSiteLandingPad(Sym) &&
 794            "missing call site number for landing pad!");
 795     return LPadToCallSiteMap[Sym];
 796   }
 797
 798   /// Return true if the landing pad Eh symbol has an associated call site.
 799   bool hasCallSiteLandingPad(MCSymbol *Sym) {
 800     return !LPadToCallSiteMap[Sym].empty();
 801   }
 802
 803   /// Map the begin label for a call site.
 804   void setCallSiteBeginLabel(MCSymbol *BeginLabel, unsigned Site) {
 805     CallSiteMap[BeginLabel] = Site;
 806   }
 807
 808   /// Get the call site number for a begin label.
 809   unsigned getCallSiteBeginLabel(MCSymbol *BeginLabel) const {
 810     assert(hasCallSiteBeginLabel(BeginLabel) &&
 811            "Missing call site number for EH_LABEL!");
 812     return CallSiteMap.lookup(BeginLabel);
 813   }
 814
 815   /// Return true if the begin label has a call site number associated with it.
 816   bool hasCallSiteBeginLabel(MCSymbol *BeginLabel) const {
 817     return CallSiteMap.count(BeginLabel);
 818   }
 819
 820   /// Return a reference to the C++ typeinfo for the current function.
 821   const std::vector<const GlobalValue *> &getTypeInfos() const {
 822     return TypeInfos;
 823   }
 824
 825   /// Return a reference to the typeids encoding filters used in the current
 826   /// function.
 827   const std::vector<unsigned> &getFilterIds() const {
 828     return FilterIds;
 829   }
 830
 831   /// \}
 832
 833   /// Collect information used to emit debugging information of a variable.
 834   void setVariableDbgInfo(const DILocalVariable *Var, const DIExpression *Expr,
 835                           unsigned Slot, const DILocation *Loc) {
 836     VariableDbgInfos.emplace_back(Var, Expr, Slot, Loc);
 837   }
 838
 839   VariableDbgInfoMapTy &getVariableDbgInfo() { return VariableDbgInfos; }
 840   const VariableDbgInfoMapTy &getVariableDbgInfo() const {
 841     return VariableDbgInfos;
 842   }
 843 };
 844
 845 /// \name Exception Handling
 846 /// \{
 847
 848 /// Extract the exception handling information from the landingpad instruction
 849 /// and add them to the specified machine module info.
 850 void addLandingPadInfo(const LandingPadInst &I, MachineBasicBlock &MBB);
 851
 852 /// \}
 853
 854 //===--------------------------------------------------------------------===//
 855 // GraphTraits specializations for function basic block graphs (CFGs)
 856 //===--------------------------------------------------------------------===//
 857
 858 // Provide specializations of GraphTraits to be able to treat a
 859 // machine function as a graph of machine basic blocks... these are
 860 // the same as the machine basic block iterators, except that the root
 861 // node is implicitly the first node of the function.
 862 //
 863 template <> struct GraphTraits<MachineFunction*> :
 864   public GraphTraits<MachineBasicBlock*> {
 865   static NodeRef getEntryNode(MachineFunction *F) { return &F->front(); }
 866
 867   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
 868   using nodes_iterator = pointer_iterator<MachineFunction::iterator>;
 869
 870   static nodes_iterator nodes_begin(MachineFunction *F) {
 871     return nodes_iterator(F->begin());
 872   }
 873
 874   static nodes_iterator nodes_end(MachineFunction *F) {
 875     return nodes_iterator(F->end());
 876   }
 877
 878   static unsigned       size       (MachineFunction *F) { return F->size(); }
 879 };
 880 template <> struct GraphTraits<const MachineFunction*> :
 881   public GraphTraits<const MachineBasicBlock*> {
 882   static NodeRef getEntryNode(const MachineFunction *F) { return &F->front(); }
 883
 884   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
 885   using nodes_iterator = pointer_iterator<MachineFunction::const_iterator>;
 886
 887   static nodes_iterator nodes_begin(const MachineFunction *F) {
 888     return nodes_iterator(F->begin());
 889   }
 890
 891   static nodes_iterator nodes_end  (const MachineFunction *F) {
 892     return nodes_iterator(F->end());
 893   }
 894
 895   static unsigned       size       (const MachineFunction *F)  {
 896     return F->size();
 897   }
 898 };
 899
 900 // Provide specializations of GraphTraits to be able to treat a function as a
 901 // graph of basic blocks... and to walk it in inverse order.  Inverse order for
 902 // a function is considered to be when traversing the predecessor edges of a BB
 903 // instead of the successor edges.
 904 //
 905 template <> struct GraphTraits<Inverse<MachineFunction*>> :
 906   public GraphTraits<Inverse<MachineBasicBlock*>> {
 907   static NodeRef getEntryNode(Inverse<MachineFunction *> G) {
 908     return &G.Graph->front();
 909   }
 910 };
 911 template <> struct GraphTraits<Inverse<const MachineFunction*>> :
 912   public GraphTraits<Inverse<const MachineBasicBlock*>> {
 913   static NodeRef getEntryNode(Inverse<const MachineFunction *> G) {
 914     return &G.Graph->front();
 915   }
 916 };
 917
 918 } // end namespace llvm
 919
 920 #endif // LLVM_CODEGEN_MACHINEFUNCTION_H