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