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 &F;
 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   /// CodeView label annotations.
 318   std::vector<std::pair<MCSymbol *, MDNode *>> CodeViewAnnotations;
 319
 320   bool CallsEHReturn = false;
 321   bool CallsUnwindInit = false;
 322   bool HasEHFunclets = false;
 323
 324   /// List of C++ TypeInfo used.
 325   std::vector<const GlobalValue *> TypeInfos;
 326
 327   /// List of typeids encoding filters used.
 328   std::vector<unsigned> FilterIds;
 329
 330   /// List of the indices in FilterIds corresponding to filter terminators.
 331   std::vector<unsigned> FilterEnds;
 332
 333   EHPersonality PersonalityTypeCache = EHPersonality::Unknown;
 334
 335   /// \}
 336
 337   /// Clear all the members of this MachineFunction, but the ones used
 338   /// to initialize again the MachineFunction.
 339   /// More specifically, this deallocates all the dynamically allocated
 340   /// objects and get rid of all the XXXInfo data structure, but keep
 341   /// unchanged the references to Fn, Target, MMI, and FunctionNumber.
 342   void clear();
 343   /// Allocate and initialize the different members.
 344   /// In particular, the XXXInfo data structure.
 345   /// \pre Fn, Target, MMI, and FunctionNumber are properly set.
 346   void init();
 347
 348 public:
 349   struct VariableDbgInfo {
 350     const DILocalVariable *Var;
 351     const DIExpression *Expr;
 352     unsigned Slot;
 353     const DILocation *Loc;
 354
 355     VariableDbgInfo(const DILocalVariable *Var, const DIExpression *Expr,
 356                     unsigned Slot, const DILocation *Loc)
 357         : Var(Var), Expr(Expr), Slot(Slot), Loc(Loc) {}
 358   };
 359   using VariableDbgInfoMapTy = SmallVector<VariableDbgInfo, 4>;
 360   VariableDbgInfoMapTy VariableDbgInfos;
 361
 362   MachineFunction(const Function &F, const TargetMachine &TM,
 363                   const TargetSubtargetInfo &STI, unsigned FunctionNum,
 364                   MachineModuleInfo &MMI);
 365   MachineFunction(const MachineFunction &) = delete;
 366   MachineFunction &operator=(const MachineFunction &) = delete;
 367   ~MachineFunction();
 368
 369   /// Reset the instance as if it was just created.
 370   void reset() {
 371     clear();
 372     init();
 373   }
 374
 375   MachineModuleInfo &getMMI() const { return MMI; }
 376   MCContext &getContext() const { return Ctx; }
 377
 378   PseudoSourceValueManager &getPSVManager() const { return *PSVManager; }
 379
 380   /// Return the DataLayout attached to the Module associated to this MF.
 381   const DataLayout &getDataLayout() const;
 382
 383   /// Return the LLVM function that this machine code represents
 384   const Function &getFunction() const { return F; }
 385
 386   /// getName - Return the name of the corresponding LLVM function.
 387   StringRef getName() const;
 388
 389   /// getFunctionNumber - Return a unique ID for the current function.
 390   unsigned getFunctionNumber() const { return FunctionNumber; }
 391
 392   /// getTarget - Return the target machine this machine code is compiled with
 393   const TargetMachine &getTarget() const { return Target; }
 394
 395   /// getSubtarget - Return the subtarget for which this machine code is being
 396   /// compiled.
 397   const TargetSubtargetInfo &getSubtarget() const { return *STI; }
 398   void setSubtarget(const TargetSubtargetInfo *ST) { STI = ST; }
 399
 400   /// getSubtarget - This method returns a pointer to the specified type of
 401   /// TargetSubtargetInfo.  In debug builds, it verifies that the object being
 402   /// returned is of the correct type.
 403   template<typename STC> const STC &getSubtarget() const {
 404     return *static_cast<const STC *>(STI);
 405   }
 406
 407   /// getRegInfo - Return information about the registers currently in use.
 408   MachineRegisterInfo &getRegInfo() { return *RegInfo; }
 409   const MachineRegisterInfo &getRegInfo() const { return *RegInfo; }
 410
 411   /// getFrameInfo - Return the frame info object for the current function.
 412   /// This object contains information about objects allocated on the stack
 413   /// frame of the current function in an abstract way.
 414   MachineFrameInfo &getFrameInfo() { return *FrameInfo; }
 415   const MachineFrameInfo &getFrameInfo() const { return *FrameInfo; }
 416
 417   /// getJumpTableInfo - Return the jump table info object for the current
 418   /// function.  This object contains information about jump tables in the
 419   /// current function.  If the current function has no jump tables, this will
 420   /// return null.
 421   const MachineJumpTableInfo *getJumpTableInfo() const { return JumpTableInfo; }
 422   MachineJumpTableInfo *getJumpTableInfo() { return JumpTableInfo; }
 423
 424   /// getOrCreateJumpTableInfo - Get the JumpTableInfo for this function, if it
 425   /// does already exist, allocate one.
 426   MachineJumpTableInfo *getOrCreateJumpTableInfo(unsigned JTEntryKind);
 427
 428   /// getConstantPool - Return the constant pool object for the current
 429   /// function.
 430   MachineConstantPool *getConstantPool() { return ConstantPool; }
 431   const MachineConstantPool *getConstantPool() const { return ConstantPool; }
 432
 433   /// getWinEHFuncInfo - Return information about how the current function uses
 434   /// Windows exception handling. Returns null for functions that don't use
 435   /// funclets for exception handling.
 436   const WinEHFuncInfo *getWinEHFuncInfo() const { return WinEHInfo; }
 437   WinEHFuncInfo *getWinEHFuncInfo() { return WinEHInfo; }
 438
 439   /// getAlignment - Return the alignment (log2, not bytes) of the function.
 440   unsigned getAlignment() const { return Alignment; }
 441
 442   /// setAlignment - Set the alignment (log2, not bytes) of the function.
 443   void setAlignment(unsigned A) { Alignment = A; }
 444
 445   /// ensureAlignment - Make sure the function is at least 1 << A bytes aligned.
 446   void ensureAlignment(unsigned A) {
 447     if (Alignment < A) Alignment = A;
 448   }
 449
 450   /// exposesReturnsTwice - Returns true if the function calls setjmp or
 451   /// any other similar functions with attribute "returns twice" without
 452   /// having the attribute itself.
 453   bool exposesReturnsTwice() const {
 454     return ExposesReturnsTwice;
 455   }
 456
 457   /// setCallsSetJmp - Set a flag that indicates if there's a call to
 458   /// a "returns twice" function.
 459   void setExposesReturnsTwice(bool B) {
 460     ExposesReturnsTwice = B;
 461   }
 462
 463   /// Returns true if the function contains any inline assembly.
 464   bool hasInlineAsm() const {
 465     return HasInlineAsm;
 466   }
 467
 468   /// Set a flag that indicates that the function contains inline assembly.
 469   void setHasInlineAsm(bool B) {
 470     HasInlineAsm = B;
 471   }
 472
 473   bool hasWinCFI() const {
 474     assert(HasWinCFI.hasValue() && "HasWinCFI not set yet!");
 475     return *HasWinCFI;
 476   }
 477   void setHasWinCFI(bool v) { HasWinCFI = v; }
 478
 479   /// Get the function properties
 480   const MachineFunctionProperties &getProperties() const { return Properties; }
 481   MachineFunctionProperties &getProperties() { return Properties; }
 482
 483   /// getInfo - Keep track of various per-function pieces of information for
 484   /// backends that would like to do so.
 485   ///
 486   template<typename Ty>
 487   Ty *getInfo() {
 488     if (!MFInfo)
 489       MFInfo = Ty::template create<Ty>(Allocator, *this);
 490     return static_cast<Ty*>(MFInfo);
 491   }
 492
 493   template<typename Ty>
 494   const Ty *getInfo() const {
 495      return const_cast<MachineFunction*>(this)->getInfo<Ty>();
 496   }
 497
 498   /// getBlockNumbered - MachineBasicBlocks are automatically numbered when they
 499   /// are inserted into the machine function.  The block number for a machine
 500   /// basic block can be found by using the MBB::getNumber method, this method
 501   /// provides the inverse mapping.
 502   MachineBasicBlock *getBlockNumbered(unsigned N) const {
 503     assert(N < MBBNumbering.size() && "Illegal block number");
 504     assert(MBBNumbering[N] && "Block was removed from the machine function!");
 505     return MBBNumbering[N];
 506   }
 507
 508   /// Should we be emitting segmented stack stuff for the function
 509   bool shouldSplitStack() const;
 510
 511   /// getNumBlockIDs - Return the number of MBB ID's allocated.
 512   unsigned getNumBlockIDs() const { return (unsigned)MBBNumbering.size(); }
 513
 514   /// RenumberBlocks - This discards all of the MachineBasicBlock numbers and
 515   /// recomputes them.  This guarantees that the MBB numbers are sequential,
 516   /// dense, and match the ordering of the blocks within the function.  If a
 517   /// specific MachineBasicBlock is specified, only that block and those after
 518   /// it are renumbered.
 519   void RenumberBlocks(MachineBasicBlock *MBBFrom = nullptr);
 520
 521   /// print - Print out the MachineFunction in a format suitable for debugging
 522   /// to the specified stream.
 523   void print(raw_ostream &OS, const SlotIndexes* = nullptr) const;
 524
 525   /// viewCFG - This function is meant for use from the debugger.  You can just
 526   /// say 'call F->viewCFG()' and a ghostview window should pop up from the
 527   /// program, displaying the CFG of the current function with the code for each
 528   /// basic block inside.  This depends on there being a 'dot' and 'gv' program
 529   /// in your path.
 530   void viewCFG() const;
 531
 532   /// viewCFGOnly - This function is meant for use from the debugger.  It works
 533   /// just like viewCFG, but it does not include the contents of basic blocks
 534   /// into the nodes, just the label.  If you are only interested in the CFG
 535   /// this can make the graph smaller.
 536   ///
 537   void viewCFGOnly() const;
 538
 539   /// dump - Print the current MachineFunction to cerr, useful for debugger use.
 540   void dump() const;
 541
 542   /// Run the current MachineFunction through the machine code verifier, useful
 543   /// for debugger use.
 544   /// \returns true if no problems were found.
 545   bool verify(Pass *p = nullptr, const char *Banner = nullptr,
 546               bool AbortOnError = true) const;
 547
 548   // Provide accessors for the MachineBasicBlock list...
 549   using iterator = BasicBlockListType::iterator;
 550   using const_iterator = BasicBlockListType::const_iterator;
 551   using const_reverse_iterator = BasicBlockListType::const_reverse_iterator;
 552   using reverse_iterator = BasicBlockListType::reverse_iterator;
 553
 554   /// Support for MachineBasicBlock::getNextNode().
 555   static BasicBlockListType MachineFunction::*
 556   getSublistAccess(MachineBasicBlock *) {
 557     return &MachineFunction::BasicBlocks;
 558   }
 559
 560   /// addLiveIn - Add the specified physical register as a live-in value and
 561   /// create a corresponding virtual register for it.
 562   unsigned addLiveIn(unsigned PReg, const TargetRegisterClass *RC);
 563
 564   //===--------------------------------------------------------------------===//
 565   // BasicBlock accessor functions.
 566   //
 567   iterator                 begin()       { return BasicBlocks.begin(); }
 568   const_iterator           begin() const { return BasicBlocks.begin(); }
 569   iterator                 end  ()       { return BasicBlocks.end();   }
 570   const_iterator           end  () const { return BasicBlocks.end();   }
 571
 572   reverse_iterator        rbegin()       { return BasicBlocks.rbegin(); }
 573   const_reverse_iterator  rbegin() const { return BasicBlocks.rbegin(); }
 574   reverse_iterator        rend  ()       { return BasicBlocks.rend();   }
 575   const_reverse_iterator  rend  () const { return BasicBlocks.rend();   }
 576
 577   unsigned                  size() const { return (unsigned)BasicBlocks.size();}
 578   bool                     empty() const { return BasicBlocks.empty(); }
 579   const MachineBasicBlock &front() const { return BasicBlocks.front(); }
 580         MachineBasicBlock &front()       { return BasicBlocks.front(); }
 581   const MachineBasicBlock & back() const { return BasicBlocks.back(); }
 582         MachineBasicBlock & back()       { return BasicBlocks.back(); }
 583
 584   void push_back (MachineBasicBlock *MBB) { BasicBlocks.push_back (MBB); }
 585   void push_front(MachineBasicBlock *MBB) { BasicBlocks.push_front(MBB); }
 586   void insert(iterator MBBI, MachineBasicBlock *MBB) {
 587     BasicBlocks.insert(MBBI, MBB);
 588   }
 589   void splice(iterator InsertPt, iterator MBBI) {
 590     BasicBlocks.splice(InsertPt, BasicBlocks, MBBI);
 591   }
 592   void splice(iterator InsertPt, MachineBasicBlock *MBB) {
 593     BasicBlocks.splice(InsertPt, BasicBlocks, MBB);
 594   }
 595   void splice(iterator InsertPt, iterator MBBI, iterator MBBE) {
 596     BasicBlocks.splice(InsertPt, BasicBlocks, MBBI, MBBE);
 597   }
 598
 599   void remove(iterator MBBI) { BasicBlocks.remove(MBBI); }
 600   void remove(MachineBasicBlock *MBBI) { BasicBlocks.remove(MBBI); }
 601   void erase(iterator MBBI) { BasicBlocks.erase(MBBI); }
 602   void erase(MachineBasicBlock *MBBI) { BasicBlocks.erase(MBBI); }
 603
 604   template <typename Comp>
 605   void sort(Comp comp) {
 606     BasicBlocks.sort(comp);
 607   }
 608
 609   //===--------------------------------------------------------------------===//
 610   // Internal functions used to automatically number MachineBasicBlocks
 611
 612   /// \brief Adds the MBB to the internal numbering. Returns the unique number
 613   /// assigned to the MBB.
 614   unsigned addToMBBNumbering(MachineBasicBlock *MBB) {
 615     MBBNumbering.push_back(MBB);
 616     return (unsigned)MBBNumbering.size()-1;
 617   }
 618
 619   /// removeFromMBBNumbering - Remove the specific machine basic block from our
 620   /// tracker, this is only really to be used by the MachineBasicBlock
 621   /// implementation.
 622   void removeFromMBBNumbering(unsigned N) {
 623     assert(N < MBBNumbering.size() && "Illegal basic block #");
 624     MBBNumbering[N] = nullptr;
 625   }
 626
 627   /// CreateMachineInstr - Allocate a new MachineInstr. Use this instead
 628   /// of `new MachineInstr'.
 629   MachineInstr *CreateMachineInstr(const MCInstrDesc &MCID, const DebugLoc &DL,
 630                                    bool NoImp = false);
 631
 632   /// Create a new MachineInstr which is a copy of \p Orig, identical in all
 633   /// ways except the instruction has no parent, prev, or next. Bundling flags
 634   /// are reset.
 635   ///
 636   /// Note: Clones a single instruction, not whole instruction bundles.
 637   /// Does not perform target specific adjustments; consider using
 638   /// TargetInstrInfo::duplicate() instead.
 639   MachineInstr *CloneMachineInstr(const MachineInstr *Orig);
 640
 641   /// Clones instruction or the whole instruction bundle \p Orig and insert
 642   /// into \p MBB before \p InsertBefore.
 643   ///
 644   /// Note: Does not perform target specific adjustments; consider using
 645   /// TargetInstrInfo::duplicate() intead.
 646   MachineInstr &CloneMachineInstrBundle(MachineBasicBlock &MBB,
 647       MachineBasicBlock::iterator InsertBefore, const MachineInstr &Orig);
 648
 649   /// DeleteMachineInstr - Delete the given MachineInstr.
 650   void DeleteMachineInstr(MachineInstr *MI);
 651
 652   /// CreateMachineBasicBlock - Allocate a new MachineBasicBlock. Use this
 653   /// instead of `new MachineBasicBlock'.
 654   MachineBasicBlock *CreateMachineBasicBlock(const BasicBlock *bb = nullptr);
 655
 656   /// DeleteMachineBasicBlock - Delete the given MachineBasicBlock.
 657   void DeleteMachineBasicBlock(MachineBasicBlock *MBB);
 658
 659   /// getMachineMemOperand - Allocate a new MachineMemOperand.
 660   /// MachineMemOperands are owned by the MachineFunction and need not be
 661   /// explicitly deallocated.
 662   MachineMemOperand *getMachineMemOperand(
 663       MachinePointerInfo PtrInfo, MachineMemOperand::Flags f, uint64_t s,
 664       unsigned base_alignment, const AAMDNodes &AAInfo = AAMDNodes(),
 665       const MDNode *Ranges = nullptr,
 666       SyncScope::ID SSID = SyncScope::System,
 667       AtomicOrdering Ordering = AtomicOrdering::NotAtomic,
 668       AtomicOrdering FailureOrdering = AtomicOrdering::NotAtomic);
 669
 670   /// getMachineMemOperand - Allocate a new MachineMemOperand by copying
 671   /// an existing one, adjusting by an offset and using the given size.
 672   /// MachineMemOperands are owned by the MachineFunction and need not be
 673   /// explicitly deallocated.
 674   MachineMemOperand *getMachineMemOperand(const MachineMemOperand *MMO,
 675                                           int64_t Offset, uint64_t Size);
 676
 677   /// Allocate a new MachineMemOperand by copying an existing one,
 678   /// replacing only AliasAnalysis information. MachineMemOperands are owned
 679   /// by the MachineFunction and need not be explicitly deallocated.
 680   MachineMemOperand *getMachineMemOperand(const MachineMemOperand *MMO,
 681                                           const AAMDNodes &AAInfo);
 682
 683   using OperandCapacity = ArrayRecycler<MachineOperand>::Capacity;
 684
 685   /// Allocate an array of MachineOperands. This is only intended for use by
 686   /// internal MachineInstr functions.
 687   MachineOperand *allocateOperandArray(OperandCapacity Cap) {
 688     return OperandRecycler.allocate(Cap, Allocator);
 689   }
 690
 691   /// Dellocate an array of MachineOperands and recycle the memory. This is
 692   /// only intended for use by internal MachineInstr functions.
 693   /// Cap must be the same capacity that was used to allocate the array.
 694   void deallocateOperandArray(OperandCapacity Cap, MachineOperand *Array) {
 695     OperandRecycler.deallocate(Cap, Array);
 696   }
 697
 698   /// \brief Allocate and initialize a register mask with @p NumRegister bits.
 699   uint32_t *allocateRegisterMask(unsigned NumRegister) {
 700     unsigned Size = (NumRegister + 31) / 32;
 701     uint32_t *Mask = Allocator.Allocate<uint32_t>(Size);
 702     for (unsigned i = 0; i != Size; ++i)
 703       Mask[i] = 0;
 704     return Mask;
 705   }
 706
 707   /// allocateMemRefsArray - Allocate an array to hold MachineMemOperand
 708   /// pointers.  This array is owned by the MachineFunction.
 709   MachineInstr::mmo_iterator allocateMemRefsArray(unsigned long Num);
 710
 711   /// extractLoadMemRefs - Allocate an array and populate it with just the
 712   /// load information from the given MachineMemOperand sequence.
 713   std::pair<MachineInstr::mmo_iterator,
 714             MachineInstr::mmo_iterator>
 715     extractLoadMemRefs(MachineInstr::mmo_iterator Begin,
 716                        MachineInstr::mmo_iterator End);
 717
 718   /// extractStoreMemRefs - Allocate an array and populate it with just the
 719   /// store information from the given MachineMemOperand sequence.
 720   std::pair<MachineInstr::mmo_iterator,
 721             MachineInstr::mmo_iterator>
 722     extractStoreMemRefs(MachineInstr::mmo_iterator Begin,
 723                         MachineInstr::mmo_iterator End);
 724
 725   /// Allocate a string and populate it with the given external symbol name.
 726   const char *createExternalSymbolName(StringRef Name);
 727
 728   //===--------------------------------------------------------------------===//
 729   // Label Manipulation.
 730
 731   /// getJTISymbol - Return the MCSymbol for the specified non-empty jump table.
 732   /// If isLinkerPrivate is specified, an 'l' label is returned, otherwise a
 733   /// normal 'L' label is returned.
 734   MCSymbol *getJTISymbol(unsigned JTI, MCContext &Ctx,
 735                          bool isLinkerPrivate = false) const;
 736
 737   /// getPICBaseSymbol - Return a function-local symbol to represent the PIC
 738   /// base.
 739   MCSymbol *getPICBaseSymbol() const;
 740
 741   /// Returns a reference to a list of cfi instructions in the function's
 742   /// prologue.  Used to construct frame maps for debug and exception handling
 743   /// comsumers.
 744   const std::vector<MCCFIInstruction> &getFrameInstructions() const {
 745     return FrameInstructions;
 746   }
 747
 748   LLVM_NODISCARD unsigned addFrameInst(const MCCFIInstruction &Inst) {
 749     FrameInstructions.push_back(Inst);
 750     return FrameInstructions.size() - 1;
 751   }
 752
 753   /// \name Exception Handling
 754   /// \{
 755
 756   bool callsEHReturn() const { return CallsEHReturn; }
 757   void setCallsEHReturn(bool b) { CallsEHReturn = b; }
 758
 759   bool callsUnwindInit() const { return CallsUnwindInit; }
 760   void setCallsUnwindInit(bool b) { CallsUnwindInit = b; }
 761
 762   bool hasEHFunclets() const { return HasEHFunclets; }
 763   void setHasEHFunclets(bool V) { HasEHFunclets = V; }
 764
 765   /// Find or create an LandingPadInfo for the specified MachineBasicBlock.
 766   LandingPadInfo &getOrCreateLandingPadInfo(MachineBasicBlock *LandingPad);
 767
 768   /// Remap landing pad labels and remove any deleted landing pads.
 769   void tidyLandingPads(DenseMap<MCSymbol*, uintptr_t> *LPMap = nullptr);
 770
 771   /// Return a reference to the landing pad info for the current function.
 772   const std::vector<LandingPadInfo> &getLandingPads() const {
 773     return LandingPads;
 774   }
 775
 776   /// Provide the begin and end labels of an invoke style call and associate it
 777   /// with a try landing pad block.
 778   void addInvoke(MachineBasicBlock *LandingPad,
 779                  MCSymbol *BeginLabel, MCSymbol *EndLabel);
 780
 781   /// Add a new panding pad.  Returns the label ID for the landing pad entry.
 782   MCSymbol *addLandingPad(MachineBasicBlock *LandingPad);
 783
 784   /// Provide the catch typeinfo for a landing pad.
 785   void addCatchTypeInfo(MachineBasicBlock *LandingPad,
 786                         ArrayRef<const GlobalValue *> TyInfo);
 787
 788   /// Provide the filter typeinfo for a landing pad.
 789   void addFilterTypeInfo(MachineBasicBlock *LandingPad,
 790                          ArrayRef<const GlobalValue *> TyInfo);
 791
 792   /// Add a cleanup action for a landing pad.
 793   void addCleanup(MachineBasicBlock *LandingPad);
 794
 795   void addSEHCatchHandler(MachineBasicBlock *LandingPad, const Function *Filter,
 796                           const BlockAddress *RecoverLabel);
 797
 798   void addSEHCleanupHandler(MachineBasicBlock *LandingPad,
 799                             const Function *Cleanup);
 800
 801   /// Return the type id for the specified typeinfo.  This is function wide.
 802   unsigned getTypeIDFor(const GlobalValue *TI);
 803
 804   /// Return the id of the filter encoded by TyIds.  This is function wide.
 805   int getFilterIDFor(std::vector<unsigned> &TyIds);
 806
 807   /// Map the landing pad's EH symbol to the call site indexes.
 808   void setCallSiteLandingPad(MCSymbol *Sym, ArrayRef<unsigned> Sites);
 809
 810   /// Get the call site indexes for a landing pad EH symbol.
 811   SmallVectorImpl<unsigned> &getCallSiteLandingPad(MCSymbol *Sym) {
 812     assert(hasCallSiteLandingPad(Sym) &&
 813            "missing call site number for landing pad!");
 814     return LPadToCallSiteMap[Sym];
 815   }
 816
 817   /// Return true if the landing pad Eh symbol has an associated call site.
 818   bool hasCallSiteLandingPad(MCSymbol *Sym) {
 819     return !LPadToCallSiteMap[Sym].empty();
 820   }
 821
 822   /// Map the begin label for a call site.
 823   void setCallSiteBeginLabel(MCSymbol *BeginLabel, unsigned Site) {
 824     CallSiteMap[BeginLabel] = Site;
 825   }
 826
 827   /// Get the call site number for a begin label.
 828   unsigned getCallSiteBeginLabel(MCSymbol *BeginLabel) const {
 829     assert(hasCallSiteBeginLabel(BeginLabel) &&
 830            "Missing call site number for EH_LABEL!");
 831     return CallSiteMap.lookup(BeginLabel);
 832   }
 833
 834   /// Return true if the begin label has a call site number associated with it.
 835   bool hasCallSiteBeginLabel(MCSymbol *BeginLabel) const {
 836     return CallSiteMap.count(BeginLabel);
 837   }
 838
 839   /// Record annotations associated with a particular label.
 840   void addCodeViewAnnotation(MCSymbol *Label, MDNode *MD) {
 841     CodeViewAnnotations.push_back({Label, MD});
 842   }
 843
 844   ArrayRef<std::pair<MCSymbol *, MDNode *>> getCodeViewAnnotations() const {
 845     return CodeViewAnnotations;
 846   }
 847
 848   /// Return a reference to the C++ typeinfo for the current function.
 849   const std::vector<const GlobalValue *> &getTypeInfos() const {
 850     return TypeInfos;
 851   }
 852
 853   /// Return a reference to the typeids encoding filters used in the current
 854   /// function.
 855   const std::vector<unsigned> &getFilterIds() const {
 856     return FilterIds;
 857   }
 858
 859   /// \}
 860
 861   /// Collect information used to emit debugging information of a variable.
 862   void setVariableDbgInfo(const DILocalVariable *Var, const DIExpression *Expr,
 863                           unsigned Slot, const DILocation *Loc) {
 864     VariableDbgInfos.emplace_back(Var, Expr, Slot, Loc);
 865   }
 866
 867   VariableDbgInfoMapTy &getVariableDbgInfo() { return VariableDbgInfos; }
 868   const VariableDbgInfoMapTy &getVariableDbgInfo() const {
 869     return VariableDbgInfos;
 870   }
 871 };
 872
 873 /// \name Exception Handling
 874 /// \{
 875
 876 /// Extract the exception handling information from the landingpad instruction
 877 /// and add them to the specified machine module info.
 878 void addLandingPadInfo(const LandingPadInst &I, MachineBasicBlock &MBB);
 879
 880 /// \}
 881
 882 //===--------------------------------------------------------------------===//
 883 // GraphTraits specializations for function basic block graphs (CFGs)
 884 //===--------------------------------------------------------------------===//
 885
 886 // Provide specializations of GraphTraits to be able to treat a
 887 // machine function as a graph of machine basic blocks... these are
 888 // the same as the machine basic block iterators, except that the root
 889 // node is implicitly the first node of the function.
 890 //
 891 template <> struct GraphTraits<MachineFunction*> :
 892   public GraphTraits<MachineBasicBlock*> {
 893   static NodeRef getEntryNode(MachineFunction *F) { return &F->front(); }
 894
 895   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
 896   using nodes_iterator = pointer_iterator<MachineFunction::iterator>;
 897
 898   static nodes_iterator nodes_begin(MachineFunction *F) {
 899     return nodes_iterator(F->begin());
 900   }
 901
 902   static nodes_iterator nodes_end(MachineFunction *F) {
 903     return nodes_iterator(F->end());
 904   }
 905
 906   static unsigned       size       (MachineFunction *F) { return F->size(); }
 907 };
 908 template <> struct GraphTraits<const MachineFunction*> :
 909   public GraphTraits<const MachineBasicBlock*> {
 910   static NodeRef getEntryNode(const MachineFunction *F) { return &F->front(); }
 911
 912   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
 913   using nodes_iterator = pointer_iterator<MachineFunction::const_iterator>;
 914
 915   static nodes_iterator nodes_begin(const MachineFunction *F) {
 916     return nodes_iterator(F->begin());
 917   }
 918
 919   static nodes_iterator nodes_end  (const MachineFunction *F) {
 920     return nodes_iterator(F->end());
 921   }
 922
 923   static unsigned       size       (const MachineFunction *F)  {
 924     return F->size();
 925   }
 926 };
 927
 928 // Provide specializations of GraphTraits to be able to treat a function as a
 929 // graph of basic blocks... and to walk it in inverse order.  Inverse order for
 930 // a function is considered to be when traversing the predecessor edges of a BB
 931 // instead of the successor edges.
 932 //
 933 template <> struct GraphTraits<Inverse<MachineFunction*>> :
 934   public GraphTraits<Inverse<MachineBasicBlock*>> {
 935   static NodeRef getEntryNode(Inverse<MachineFunction *> G) {
 936     return &G.Graph->front();
 937   }
 938 };
 939 template <> struct GraphTraits<Inverse<const MachineFunction*>> :
 940   public GraphTraits<Inverse<const MachineBasicBlock*>> {
 941   static NodeRef getEntryNode(Inverse<const MachineFunction *> G) {
 942     return &G.Graph->front();
 943   }
 944 };
 945
 946 } // end namespace llvm
 947
 948 #endif // LLVM_CODEGEN_MACHINEFUNCTION_H