LLVM  mainline
MachineBasicBlock.h
Go to the documentation of this file.
00001 //===-- llvm/CodeGen/MachineBasicBlock.h ------------------------*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // Collect the sequence of machine instructions for a basic block.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #ifndef LLVM_CODEGEN_MACHINEBASICBLOCK_H
00015 #define LLVM_CODEGEN_MACHINEBASICBLOCK_H
00016 
00017 #include "llvm/ADT/GraphTraits.h"
00018 #include "llvm/CodeGen/MachineInstr.h"
00019 #include "llvm/Support/BranchProbability.h"
00020 #include "llvm/MC/MCRegisterInfo.h"
00021 #include "llvm/Support/DataTypes.h"
00022 #include <functional>
00023 
00024 namespace llvm {
00025 
00026 class Pass;
00027 class BasicBlock;
00028 class MachineFunction;
00029 class MCSymbol;
00030 class MIPrinter;
00031 class SlotIndexes;
00032 class StringRef;
00033 class raw_ostream;
00034 class MachineBranchProbabilityInfo;
00035 
00036 // Forward declaration to avoid circular include problem with TargetRegisterInfo
00037 typedef unsigned LaneBitmask;
00038 
00039 template <>
00040 struct ilist_traits<MachineInstr> : public ilist_default_traits<MachineInstr> {
00041 private:
00042   mutable ilist_half_node<MachineInstr> Sentinel;
00043 
00044   // this is only set by the MachineBasicBlock owning the LiveList
00045   friend class MachineBasicBlock;
00046   MachineBasicBlock* Parent;
00047 
00048 public:
00049   MachineInstr *createSentinel() const {
00050     return static_cast<MachineInstr*>(&Sentinel);
00051   }
00052   void destroySentinel(MachineInstr *) const {}
00053 
00054   MachineInstr *provideInitialHead() const { return createSentinel(); }
00055   MachineInstr *ensureHead(MachineInstr*) const { return createSentinel(); }
00056   static void noteHead(MachineInstr*, MachineInstr*) {}
00057 
00058   void addNodeToList(MachineInstr* N);
00059   void removeNodeFromList(MachineInstr* N);
00060   void transferNodesFromList(ilist_traits &SrcTraits,
00061                              ilist_iterator<MachineInstr> First,
00062                              ilist_iterator<MachineInstr> Last);
00063   void deleteNode(MachineInstr *N);
00064 private:
00065   void createNode(const MachineInstr &);
00066 };
00067 
00068 class MachineBasicBlock
00069     : public ilist_node_with_parent<MachineBasicBlock, MachineFunction> {
00070 public:
00071   /// Pair of physical register and lane mask.
00072   /// This is not simply a std::pair typedef because the members should be named
00073   /// clearly as they both have an integer type.
00074   struct RegisterMaskPair {
00075   public:
00076     MCPhysReg PhysReg;
00077     LaneBitmask LaneMask;
00078 
00079     RegisterMaskPair(MCPhysReg PhysReg, LaneBitmask LaneMask)
00080         : PhysReg(PhysReg), LaneMask(LaneMask) {}
00081   };
00082 
00083 private:
00084   typedef ilist<MachineInstr> Instructions;
00085   Instructions Insts;
00086   const BasicBlock *BB;
00087   int Number;
00088   MachineFunction *xParent;
00089 
00090   /// Keep track of the predecessor / successor basic blocks.
00091   std::vector<MachineBasicBlock *> Predecessors;
00092   std::vector<MachineBasicBlock *> Successors;
00093 
00094   /// Keep track of the probabilities to the successors. This vector has the
00095   /// same order as Successors, or it is empty if we don't use it (disable
00096   /// optimization).
00097   std::vector<BranchProbability> Probs;
00098   typedef std::vector<BranchProbability>::iterator probability_iterator;
00099   typedef std::vector<BranchProbability>::const_iterator
00100       const_probability_iterator;
00101 
00102   /// Keep track of the physical registers that are livein of the basicblock.
00103   typedef std::vector<RegisterMaskPair> LiveInVector;
00104   LiveInVector LiveIns;
00105 
00106   /// Alignment of the basic block. Zero if the basic block does not need to be
00107   /// aligned. The alignment is specified as log2(bytes).
00108   unsigned Alignment = 0;
00109 
00110   /// Indicate that this basic block is entered via an exception handler.
00111   bool IsEHPad = false;
00112 
00113   /// Indicate that this basic block is potentially the target of an indirect
00114   /// branch.
00115   bool AddressTaken = false;
00116 
00117   /// Indicate that this basic block is the entry block of an EH funclet.
00118   bool IsEHFuncletEntry = false;
00119 
00120   /// Indicate that this basic block is the entry block of a cleanup funclet.
00121   bool IsCleanupFuncletEntry = false;
00122 
00123   /// \brief since getSymbol is a relatively heavy-weight operation, the symbol
00124   /// is only computed once and is cached.
00125   mutable MCSymbol *CachedMCSymbol = nullptr;
00126 
00127   // Intrusive list support
00128   MachineBasicBlock() {}
00129 
00130   explicit MachineBasicBlock(MachineFunction &MF, const BasicBlock *BB);
00131 
00132   ~MachineBasicBlock();
00133 
00134   // MachineBasicBlocks are allocated and owned by MachineFunction.
00135   friend class MachineFunction;
00136 
00137 public:
00138   /// Return the LLVM basic block that this instance corresponded to originally.
00139   /// Note that this may be NULL if this instance does not correspond directly
00140   /// to an LLVM basic block.
00141   const BasicBlock *getBasicBlock() const { return BB; }
00142 
00143   /// Return the name of the corresponding LLVM basic block, or "(null)".
00144   StringRef getName() const;
00145 
00146   /// Return a formatted string to identify this block and its parent function.
00147   std::string getFullName() const;
00148 
00149   /// Test whether this block is potentially the target of an indirect branch.
00150   bool hasAddressTaken() const { return AddressTaken; }
00151 
00152   /// Set this block to reflect that it potentially is the target of an indirect
00153   /// branch.
00154   void setHasAddressTaken() { AddressTaken = true; }
00155 
00156   /// Return the MachineFunction containing this basic block.
00157   const MachineFunction *getParent() const { return xParent; }
00158   MachineFunction *getParent() { return xParent; }
00159 
00160   /// MachineBasicBlock iterator that automatically skips over MIs that are
00161   /// inside bundles (i.e. walk top level MIs only).
00162   template<typename Ty, typename IterTy>
00163   class bundle_iterator
00164     : public std::iterator<std::bidirectional_iterator_tag, Ty, ptrdiff_t> {
00165     IterTy MII;
00166 
00167   public:
00168     bundle_iterator(IterTy MI) : MII(MI) {}
00169 
00170     bundle_iterator(Ty &MI) : MII(MI) {
00171       assert(!MI.isBundledWithPred() &&
00172              "It's not legal to initialize bundle_iterator with a bundled MI");
00173     }
00174     bundle_iterator(Ty *MI) : MII(MI) {
00175       assert((!MI || !MI->isBundledWithPred()) &&
00176              "It's not legal to initialize bundle_iterator with a bundled MI");
00177     }
00178     // Template allows conversion from const to nonconst.
00179     template<class OtherTy, class OtherIterTy>
00180     bundle_iterator(const bundle_iterator<OtherTy, OtherIterTy> &I)
00181       : MII(I.getInstrIterator()) {}
00182     bundle_iterator() : MII(nullptr) {}
00183 
00184     Ty &operator*() const { return *MII; }
00185     Ty *operator->() const { return &operator*(); }
00186 
00187     operator Ty *() const { return MII.getNodePtrUnchecked(); }
00188 
00189     bool operator==(const bundle_iterator &X) const {
00190       return MII == X.MII;
00191     }
00192     bool operator!=(const bundle_iterator &X) const {
00193       return !operator==(X);
00194     }
00195 
00196     // Increment and decrement operators...
00197     bundle_iterator &operator--() {      // predecrement - Back up
00198       do --MII;
00199       while (MII->isBundledWithPred());
00200       return *this;
00201     }
00202     bundle_iterator &operator++() {      // preincrement - Advance
00203       while (MII->isBundledWithSucc())
00204         ++MII;
00205       ++MII;
00206       return *this;
00207     }
00208     bundle_iterator operator--(int) {    // postdecrement operators...
00209       bundle_iterator tmp = *this;
00210       --*this;
00211       return tmp;
00212     }
00213     bundle_iterator operator++(int) {    // postincrement operators...
00214       bundle_iterator tmp = *this;
00215       ++*this;
00216       return tmp;
00217     }
00218 
00219     IterTy getInstrIterator() const {
00220       return MII;
00221     }
00222   };
00223 
00224   typedef Instructions::iterator                                 instr_iterator;
00225   typedef Instructions::const_iterator                     const_instr_iterator;
00226   typedef std::reverse_iterator<instr_iterator>          reverse_instr_iterator;
00227   typedef
00228   std::reverse_iterator<const_instr_iterator>      const_reverse_instr_iterator;
00229 
00230   typedef
00231   bundle_iterator<MachineInstr,instr_iterator>                         iterator;
00232   typedef
00233   bundle_iterator<const MachineInstr,const_instr_iterator>       const_iterator;
00234   typedef std::reverse_iterator<const_iterator>          const_reverse_iterator;
00235   typedef std::reverse_iterator<iterator>                      reverse_iterator;
00236 
00237 
00238   unsigned size() const { return (unsigned)Insts.size(); }
00239   bool empty() const { return Insts.empty(); }
00240 
00241   MachineInstr       &instr_front()       { return Insts.front(); }
00242   MachineInstr       &instr_back()        { return Insts.back();  }
00243   const MachineInstr &instr_front() const { return Insts.front(); }
00244   const MachineInstr &instr_back()  const { return Insts.back();  }
00245 
00246   MachineInstr       &front()             { return Insts.front(); }
00247   MachineInstr       &back()              { return *--end();      }
00248   const MachineInstr &front()       const { return Insts.front(); }
00249   const MachineInstr &back()        const { return *--end();      }
00250 
00251   instr_iterator                instr_begin()       { return Insts.begin();  }
00252   const_instr_iterator          instr_begin() const { return Insts.begin();  }
00253   instr_iterator                  instr_end()       { return Insts.end();    }
00254   const_instr_iterator            instr_end() const { return Insts.end();    }
00255   reverse_instr_iterator       instr_rbegin()       { return Insts.rbegin(); }
00256   const_reverse_instr_iterator instr_rbegin() const { return Insts.rbegin(); }
00257   reverse_instr_iterator       instr_rend  ()       { return Insts.rend();   }
00258   const_reverse_instr_iterator instr_rend  () const { return Insts.rend();   }
00259 
00260   iterator                begin()       { return instr_begin();  }
00261   const_iterator          begin() const { return instr_begin();  }
00262   iterator                end  ()       { return instr_end();    }
00263   const_iterator          end  () const { return instr_end();    }
00264   reverse_iterator       rbegin()       { return instr_rbegin(); }
00265   const_reverse_iterator rbegin() const { return instr_rbegin(); }
00266   reverse_iterator       rend  ()       { return instr_rend();   }
00267   const_reverse_iterator rend  () const { return instr_rend();   }
00268 
00269   /// Support for MachineInstr::getNextNode().
00270   static Instructions MachineBasicBlock::*getSublistAccess(MachineInstr *) {
00271     return &MachineBasicBlock::Insts;
00272   }
00273 
00274   inline iterator_range<iterator> terminators() {
00275     return make_range(getFirstTerminator(), end());
00276   }
00277   inline iterator_range<const_iterator> terminators() const {
00278     return make_range(getFirstTerminator(), end());
00279   }
00280 
00281   // Machine-CFG iterators
00282   typedef std::vector<MachineBasicBlock *>::iterator       pred_iterator;
00283   typedef std::vector<MachineBasicBlock *>::const_iterator const_pred_iterator;
00284   typedef std::vector<MachineBasicBlock *>::iterator       succ_iterator;
00285   typedef std::vector<MachineBasicBlock *>::const_iterator const_succ_iterator;
00286   typedef std::vector<MachineBasicBlock *>::reverse_iterator
00287                                                          pred_reverse_iterator;
00288   typedef std::vector<MachineBasicBlock *>::const_reverse_iterator
00289                                                    const_pred_reverse_iterator;
00290   typedef std::vector<MachineBasicBlock *>::reverse_iterator
00291                                                          succ_reverse_iterator;
00292   typedef std::vector<MachineBasicBlock *>::const_reverse_iterator
00293                                                    const_succ_reverse_iterator;
00294   pred_iterator        pred_begin()       { return Predecessors.begin(); }
00295   const_pred_iterator  pred_begin() const { return Predecessors.begin(); }
00296   pred_iterator        pred_end()         { return Predecessors.end();   }
00297   const_pred_iterator  pred_end()   const { return Predecessors.end();   }
00298   pred_reverse_iterator        pred_rbegin()
00299                                           { return Predecessors.rbegin();}
00300   const_pred_reverse_iterator  pred_rbegin() const
00301                                           { return Predecessors.rbegin();}
00302   pred_reverse_iterator        pred_rend()
00303                                           { return Predecessors.rend();  }
00304   const_pred_reverse_iterator  pred_rend()   const
00305                                           { return Predecessors.rend();  }
00306   unsigned             pred_size()  const {
00307     return (unsigned)Predecessors.size();
00308   }
00309   bool                 pred_empty() const { return Predecessors.empty(); }
00310   succ_iterator        succ_begin()       { return Successors.begin();   }
00311   const_succ_iterator  succ_begin() const { return Successors.begin();   }
00312   succ_iterator        succ_end()         { return Successors.end();     }
00313   const_succ_iterator  succ_end()   const { return Successors.end();     }
00314   succ_reverse_iterator        succ_rbegin()
00315                                           { return Successors.rbegin();  }
00316   const_succ_reverse_iterator  succ_rbegin() const
00317                                           { return Successors.rbegin();  }
00318   succ_reverse_iterator        succ_rend()
00319                                           { return Successors.rend();    }
00320   const_succ_reverse_iterator  succ_rend()   const
00321                                           { return Successors.rend();    }
00322   unsigned             succ_size()  const {
00323     return (unsigned)Successors.size();
00324   }
00325   bool                 succ_empty() const { return Successors.empty();   }
00326 
00327   inline iterator_range<pred_iterator> predecessors() {
00328     return make_range(pred_begin(), pred_end());
00329   }
00330   inline iterator_range<const_pred_iterator> predecessors() const {
00331     return make_range(pred_begin(), pred_end());
00332   }
00333   inline iterator_range<succ_iterator> successors() {
00334     return make_range(succ_begin(), succ_end());
00335   }
00336   inline iterator_range<const_succ_iterator> successors() const {
00337     return make_range(succ_begin(), succ_end());
00338   }
00339 
00340   // LiveIn management methods.
00341 
00342   /// Adds the specified register as a live in. Note that it is an error to add
00343   /// the same register to the same set more than once unless the intention is
00344   /// to call sortUniqueLiveIns after all registers are added.
00345   void addLiveIn(MCPhysReg PhysReg, LaneBitmask LaneMask = ~0u) {
00346     LiveIns.push_back(RegisterMaskPair(PhysReg, LaneMask));
00347   }
00348   void addLiveIn(const RegisterMaskPair &RegMaskPair) {
00349     LiveIns.push_back(RegMaskPair);
00350   }
00351 
00352   /// Sorts and uniques the LiveIns vector. It can be significantly faster to do
00353   /// this than repeatedly calling isLiveIn before calling addLiveIn for every
00354   /// LiveIn insertion.
00355   void sortUniqueLiveIns();
00356 
00357   /// Add PhysReg as live in to this block, and ensure that there is a copy of
00358   /// PhysReg to a virtual register of class RC. Return the virtual register
00359   /// that is a copy of the live in PhysReg.
00360   unsigned addLiveIn(MCPhysReg PhysReg, const TargetRegisterClass *RC);
00361 
00362   /// Remove the specified register from the live in set.
00363   void removeLiveIn(MCPhysReg Reg, LaneBitmask LaneMask = ~0u);
00364 
00365   /// Return true if the specified register is in the live in set.
00366   bool isLiveIn(MCPhysReg Reg, LaneBitmask LaneMask = ~0u) const;
00367 
00368   // Iteration support for live in sets.  These sets are kept in sorted
00369   // order by their register number.
00370   typedef LiveInVector::const_iterator livein_iterator;
00371   livein_iterator livein_begin() const { return LiveIns.begin(); }
00372   livein_iterator livein_end()   const { return LiveIns.end(); }
00373   bool            livein_empty() const { return LiveIns.empty(); }
00374   iterator_range<livein_iterator> liveins() const {
00375     return make_range(livein_begin(), livein_end());
00376   }
00377 
00378   /// Get the clobber mask for the start of this basic block. Funclets use this
00379   /// to prevent register allocation across funclet transitions.
00380   const uint32_t *getBeginClobberMask(const TargetRegisterInfo *TRI) const;
00381 
00382   /// Get the clobber mask for the end of the basic block.
00383   /// \see getBeginClobberMask()
00384   const uint32_t *getEndClobberMask(const TargetRegisterInfo *TRI) const;
00385 
00386   /// Return alignment of the basic block. The alignment is specified as
00387   /// log2(bytes).
00388   unsigned getAlignment() const { return Alignment; }
00389 
00390   /// Set alignment of the basic block. The alignment is specified as
00391   /// log2(bytes).
00392   void setAlignment(unsigned Align) { Alignment = Align; }
00393 
00394   /// Returns true if the block is a landing pad. That is this basic block is
00395   /// entered via an exception handler.
00396   bool isEHPad() const { return IsEHPad; }
00397 
00398   /// Indicates the block is a landing pad.  That is this basic block is entered
00399   /// via an exception handler.
00400   void setIsEHPad(bool V = true) { IsEHPad = V; }
00401 
00402   /// If this block has a successor that is a landing pad, return it. Otherwise
00403   /// return NULL.
00404   const MachineBasicBlock *getLandingPadSuccessor() const;
00405 
00406   bool hasEHPadSuccessor() const;
00407 
00408   /// Returns true if this is the entry block of an EH funclet.
00409   bool isEHFuncletEntry() const { return IsEHFuncletEntry; }
00410 
00411   /// Indicates if this is the entry block of an EH funclet.
00412   void setIsEHFuncletEntry(bool V = true) { IsEHFuncletEntry = V; }
00413 
00414   /// Returns true if this is the entry block of a cleanup funclet.
00415   bool isCleanupFuncletEntry() const { return IsCleanupFuncletEntry; }
00416 
00417   /// Indicates if this is the entry block of a cleanup funclet.
00418   void setIsCleanupFuncletEntry(bool V = true) { IsCleanupFuncletEntry = V; }
00419 
00420   // Code Layout methods.
00421 
00422   /// Move 'this' block before or after the specified block.  This only moves
00423   /// the block, it does not modify the CFG or adjust potential fall-throughs at
00424   /// the end of the block.
00425   void moveBefore(MachineBasicBlock *NewAfter);
00426   void moveAfter(MachineBasicBlock *NewBefore);
00427 
00428   /// Update the terminator instructions in block to account for changes to the
00429   /// layout. If the block previously used a fallthrough, it may now need a
00430   /// branch, and if it previously used branching it may now be able to use a
00431   /// fallthrough.
00432   void updateTerminator();
00433 
00434   // Machine-CFG mutators
00435 
00436   /// Add Succ as a successor of this MachineBasicBlock.  The Predecessors list
00437   /// of Succ is automatically updated. PROB parameter is stored in
00438   /// Probabilities list. The default probability is set as unknown. Mixing
00439   /// known and unknown probabilities in successor list is not allowed. When all
00440   /// successors have unknown probabilities, 1 / N is returned as the
00441   /// probability for each successor, where N is the number of successors.
00442   ///
00443   /// Note that duplicate Machine CFG edges are not allowed.
00444   void addSuccessor(MachineBasicBlock *Succ,
00445                     BranchProbability Prob = BranchProbability::getUnknown());
00446 
00447   /// Add Succ as a successor of this MachineBasicBlock.  The Predecessors list
00448   /// of Succ is automatically updated. The probability is not provided because
00449   /// BPI is not available (e.g. -O0 is used), in which case edge probabilities
00450   /// won't be used. Using this interface can save some space.
00451   void addSuccessorWithoutProb(MachineBasicBlock *Succ);
00452 
00453   /// Set successor probability of a given iterator.
00454   void setSuccProbability(succ_iterator I, BranchProbability Prob);
00455 
00456   /// Normalize probabilities of all successors so that the sum of them becomes
00457   /// one. This is usually done when the current update on this MBB is done, and
00458   /// the sum of its successors' probabilities is not guaranteed to be one. The
00459   /// user is responsible for the correct use of this function.
00460   /// MBB::removeSuccessor() has an option to do this automatically.
00461   void normalizeSuccProbs() {
00462     BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end());
00463   }
00464 
00465   /// Validate successors' probabilities and check if the sum of them is
00466   /// approximate one. This only works in DEBUG mode.
00467   void validateSuccProbs() const;
00468 
00469   /// Remove successor from the successors list of this MachineBasicBlock. The
00470   /// Predecessors list of Succ is automatically updated.
00471   /// If NormalizeSuccProbs is true, then normalize successors' probabilities
00472   /// after the successor is removed.
00473   void removeSuccessor(MachineBasicBlock *Succ,
00474                        bool NormalizeSuccProbs = false);
00475 
00476   /// Remove specified successor from the successors list of this
00477   /// MachineBasicBlock. The Predecessors list of Succ is automatically updated.
00478   /// If NormalizeSuccProbs is true, then normalize successors' probabilities
00479   /// after the successor is removed.
00480   /// Return the iterator to the element after the one removed.
00481   succ_iterator removeSuccessor(succ_iterator I,
00482                                 bool NormalizeSuccProbs = false);
00483 
00484   /// Replace successor OLD with NEW and update probability info.
00485   void replaceSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New);
00486 
00487   /// Transfers all the successors from MBB to this machine basic block (i.e.,
00488   /// copies all the successors FromMBB and remove all the successors from
00489   /// FromMBB).
00490   void transferSuccessors(MachineBasicBlock *FromMBB);
00491 
00492   /// Transfers all the successors, as in transferSuccessors, and update PHI
00493   /// operands in the successor blocks which refer to FromMBB to refer to this.
00494   void transferSuccessorsAndUpdatePHIs(MachineBasicBlock *FromMBB);
00495 
00496   /// Return true if any of the successors have probabilities attached to them.
00497   bool hasSuccessorProbabilities() const { return !Probs.empty(); }
00498 
00499   /// Return true if the specified MBB is a predecessor of this block.
00500   bool isPredecessor(const MachineBasicBlock *MBB) const;
00501 
00502   /// Return true if the specified MBB is a successor of this block.
00503   bool isSuccessor(const MachineBasicBlock *MBB) const;
00504 
00505   /// Return true if the specified MBB will be emitted immediately after this
00506   /// block, such that if this block exits by falling through, control will
00507   /// transfer to the specified MBB. Note that MBB need not be a successor at
00508   /// all, for example if this block ends with an unconditional branch to some
00509   /// other block.
00510   bool isLayoutSuccessor(const MachineBasicBlock *MBB) const;
00511 
00512   /// Return true if the block can implicitly transfer control to the block
00513   /// after it by falling off the end of it.  This should return false if it can
00514   /// reach the block after it, but it uses an explicit branch to do so (e.g., a
00515   /// table jump).  True is a conservative answer.
00516   bool canFallThrough();
00517 
00518   /// Returns a pointer to the first instruction in this block that is not a
00519   /// PHINode instruction. When adding instructions to the beginning of the
00520   /// basic block, they should be added before the returned value, not before
00521   /// the first instruction, which might be PHI.
00522   /// Returns end() is there's no non-PHI instruction.
00523   iterator getFirstNonPHI();
00524 
00525   /// Return the first instruction in MBB after I that is not a PHI or a label.
00526   /// This is the correct point to insert copies at the beginning of a basic
00527   /// block.
00528   iterator SkipPHIsAndLabels(iterator I);
00529 
00530   /// Returns an iterator to the first terminator instruction of this basic
00531   /// block. If a terminator does not exist, it returns end().
00532   iterator getFirstTerminator();
00533   const_iterator getFirstTerminator() const {
00534     return const_cast<MachineBasicBlock *>(this)->getFirstTerminator();
00535   }
00536 
00537   /// Same getFirstTerminator but it ignores bundles and return an
00538   /// instr_iterator instead.
00539   instr_iterator getFirstInstrTerminator();
00540 
00541   /// Returns an iterator to the first non-debug instruction in the basic block,
00542   /// or end().
00543   iterator getFirstNonDebugInstr();
00544   const_iterator getFirstNonDebugInstr() const {
00545     return const_cast<MachineBasicBlock *>(this)->getFirstNonDebugInstr();
00546   }
00547 
00548   /// Returns an iterator to the last non-debug instruction in the basic block,
00549   /// or end().
00550   iterator getLastNonDebugInstr();
00551   const_iterator getLastNonDebugInstr() const {
00552     return const_cast<MachineBasicBlock *>(this)->getLastNonDebugInstr();
00553   }
00554 
00555   /// Convenience function that returns true if the block ends in a return
00556   /// instruction.
00557   bool isReturnBlock() const {
00558     return !empty() && back().isReturn();
00559   }
00560 
00561   /// Split the critical edge from this block to the given successor block, and
00562   /// return the newly created block, or null if splitting is not possible.
00563   ///
00564   /// This function updates LiveVariables, MachineDominatorTree, and
00565   /// MachineLoopInfo, as applicable.
00566   MachineBasicBlock *SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P);
00567 
00568   void pop_front() { Insts.pop_front(); }
00569   void pop_back() { Insts.pop_back(); }
00570   void push_back(MachineInstr *MI) { Insts.push_back(MI); }
00571 
00572   /// Insert MI into the instruction list before I, possibly inside a bundle.
00573   ///
00574   /// If the insertion point is inside a bundle, MI will be added to the bundle,
00575   /// otherwise MI will not be added to any bundle. That means this function
00576   /// alone can't be used to prepend or append instructions to bundles. See
00577   /// MIBundleBuilder::insert() for a more reliable way of doing that.
00578   instr_iterator insert(instr_iterator I, MachineInstr *M);
00579 
00580   /// Insert a range of instructions into the instruction list before I.
00581   template<typename IT>
00582   void insert(iterator I, IT S, IT E) {
00583     assert((I == end() || I->getParent() == this) &&
00584            "iterator points outside of basic block");
00585     Insts.insert(I.getInstrIterator(), S, E);
00586   }
00587 
00588   /// Insert MI into the instruction list before I.
00589   iterator insert(iterator I, MachineInstr *MI) {
00590     assert((I == end() || I->getParent() == this) &&
00591            "iterator points outside of basic block");
00592     assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() &&
00593            "Cannot insert instruction with bundle flags");
00594     return Insts.insert(I.getInstrIterator(), MI);
00595   }
00596 
00597   /// Insert MI into the instruction list after I.
00598   iterator insertAfter(iterator I, MachineInstr *MI) {
00599     assert((I == end() || I->getParent() == this) &&
00600            "iterator points outside of basic block");
00601     assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() &&
00602            "Cannot insert instruction with bundle flags");
00603     return Insts.insertAfter(I.getInstrIterator(), MI);
00604   }
00605 
00606   /// Remove an instruction from the instruction list and delete it.
00607   ///
00608   /// If the instruction is part of a bundle, the other instructions in the
00609   /// bundle will still be bundled after removing the single instruction.
00610   instr_iterator erase(instr_iterator I);
00611 
00612   /// Remove an instruction from the instruction list and delete it.
00613   ///
00614   /// If the instruction is part of a bundle, the other instructions in the
00615   /// bundle will still be bundled after removing the single instruction.
00616   instr_iterator erase_instr(MachineInstr *I) {
00617     return erase(instr_iterator(I));
00618   }
00619 
00620   /// Remove a range of instructions from the instruction list and delete them.
00621   iterator erase(iterator I, iterator E) {
00622     return Insts.erase(I.getInstrIterator(), E.getInstrIterator());
00623   }
00624 
00625   /// Remove an instruction or bundle from the instruction list and delete it.
00626   ///
00627   /// If I points to a bundle of instructions, they are all erased.
00628   iterator erase(iterator I) {
00629     return erase(I, std::next(I));
00630   }
00631 
00632   /// Remove an instruction from the instruction list and delete it.
00633   ///
00634   /// If I is the head of a bundle of instructions, the whole bundle will be
00635   /// erased.
00636   iterator erase(MachineInstr *I) {
00637     return erase(iterator(I));
00638   }
00639 
00640   /// Remove the unbundled instruction from the instruction list without
00641   /// deleting it.
00642   ///
00643   /// This function can not be used to remove bundled instructions, use
00644   /// remove_instr to remove individual instructions from a bundle.
00645   MachineInstr *remove(MachineInstr *I) {
00646     assert(!I->isBundled() && "Cannot remove bundled instructions");
00647     return Insts.remove(instr_iterator(I));
00648   }
00649 
00650   /// Remove the possibly bundled instruction from the instruction list
00651   /// without deleting it.
00652   ///
00653   /// If the instruction is part of a bundle, the other instructions in the
00654   /// bundle will still be bundled after removing the single instruction.
00655   MachineInstr *remove_instr(MachineInstr *I);
00656 
00657   void clear() {
00658     Insts.clear();
00659   }
00660 
00661   /// Take an instruction from MBB 'Other' at the position From, and insert it
00662   /// into this MBB right before 'Where'.
00663   ///
00664   /// If From points to a bundle of instructions, the whole bundle is moved.
00665   void splice(iterator Where, MachineBasicBlock *Other, iterator From) {
00666     // The range splice() doesn't allow noop moves, but this one does.
00667     if (Where != From)
00668       splice(Where, Other, From, std::next(From));
00669   }
00670 
00671   /// Take a block of instructions from MBB 'Other' in the range [From, To),
00672   /// and insert them into this MBB right before 'Where'.
00673   ///
00674   /// The instruction at 'Where' must not be included in the range of
00675   /// instructions to move.
00676   void splice(iterator Where, MachineBasicBlock *Other,
00677               iterator From, iterator To) {
00678     Insts.splice(Where.getInstrIterator(), Other->Insts,
00679                  From.getInstrIterator(), To.getInstrIterator());
00680   }
00681 
00682   /// This method unlinks 'this' from the containing function, and returns it,
00683   /// but does not delete it.
00684   MachineBasicBlock *removeFromParent();
00685 
00686   /// This method unlinks 'this' from the containing function and deletes it.
00687   void eraseFromParent();
00688 
00689   /// Given a machine basic block that branched to 'Old', change the code and
00690   /// CFG so that it branches to 'New' instead.
00691   void ReplaceUsesOfBlockWith(MachineBasicBlock *Old, MachineBasicBlock *New);
00692 
00693   /// Various pieces of code can cause excess edges in the CFG to be inserted.
00694   /// If we have proven that MBB can only branch to DestA and DestB, remove any
00695   /// other MBB successors from the CFG. DestA and DestB can be null. Besides
00696   /// DestA and DestB, retain other edges leading to LandingPads (currently
00697   /// there can be only one; we don't check or require that here). Note it is
00698   /// possible that DestA and/or DestB are LandingPads.
00699   bool CorrectExtraCFGEdges(MachineBasicBlock *DestA,
00700                             MachineBasicBlock *DestB,
00701                             bool IsCond);
00702 
00703   /// Find the next valid DebugLoc starting at MBBI, skipping any DBG_VALUE
00704   /// instructions.  Return UnknownLoc if there is none.
00705   DebugLoc findDebugLoc(instr_iterator MBBI);
00706   DebugLoc findDebugLoc(iterator MBBI) {
00707     return findDebugLoc(MBBI.getInstrIterator());
00708   }
00709 
00710   /// Possible outcome of a register liveness query to computeRegisterLiveness()
00711   enum LivenessQueryResult {
00712     LQR_Live,   ///< Register is known to be (at least partially) live.
00713     LQR_Dead,   ///< Register is known to be fully dead.
00714     LQR_Unknown ///< Register liveness not decidable from local neighborhood.
00715   };
00716 
00717   /// Return whether (physical) register \p Reg has been <def>ined and not
00718   /// <kill>ed as of just before \p Before.
00719   ///
00720   /// Search is localised to a neighborhood of \p Neighborhood instructions
00721   /// before (searching for defs or kills) and \p Neighborhood instructions
00722   /// after (searching just for defs) \p Before.
00723   ///
00724   /// \p Reg must be a physical register.
00725   LivenessQueryResult computeRegisterLiveness(const TargetRegisterInfo *TRI,
00726                                               unsigned Reg,
00727                                               const_iterator Before,
00728                                               unsigned Neighborhood=10) const;
00729 
00730   // Debugging methods.
00731   void dump() const;
00732   void print(raw_ostream &OS, SlotIndexes* = nullptr) const;
00733   void print(raw_ostream &OS, ModuleSlotTracker &MST,
00734              SlotIndexes * = nullptr) const;
00735 
00736   // Printing method used by LoopInfo.
00737   void printAsOperand(raw_ostream &OS, bool PrintType = true) const;
00738 
00739   /// MachineBasicBlocks are uniquely numbered at the function level, unless
00740   /// they're not in a MachineFunction yet, in which case this will return -1.
00741   int getNumber() const { return Number; }
00742   void setNumber(int N) { Number = N; }
00743 
00744   /// Return the MCSymbol for this basic block.
00745   MCSymbol *getSymbol() const;
00746 
00747 
00748 private:
00749   /// Return probability iterator corresponding to the I successor iterator.
00750   probability_iterator getProbabilityIterator(succ_iterator I);
00751   const_probability_iterator
00752   getProbabilityIterator(const_succ_iterator I) const;
00753 
00754   friend class MachineBranchProbabilityInfo;
00755   friend class MIPrinter;
00756 
00757   /// Return probability of the edge from this block to MBB. This method should
00758   /// NOT be called directly, but by using getEdgeProbability method from
00759   /// MachineBranchProbabilityInfo class.
00760   BranchProbability getSuccProbability(const_succ_iterator Succ) const;
00761 
00762   // Methods used to maintain doubly linked list of blocks...
00763   friend struct ilist_traits<MachineBasicBlock>;
00764 
00765   // Machine-CFG mutators
00766 
00767   /// Remove Pred as a predecessor of this MachineBasicBlock. Don't do this
00768   /// unless you know what you're doing, because it doesn't update Pred's
00769   /// successors list. Use Pred->addSuccessor instead.
00770   void addPredecessor(MachineBasicBlock *Pred);
00771 
00772   /// Remove Pred as a predecessor of this MachineBasicBlock. Don't do this
00773   /// unless you know what you're doing, because it doesn't update Pred's
00774   /// successors list. Use Pred->removeSuccessor instead.
00775   void removePredecessor(MachineBasicBlock *Pred);
00776 };
00777 
00778 raw_ostream& operator<<(raw_ostream &OS, const MachineBasicBlock &MBB);
00779 
00780 // This is useful when building IndexedMaps keyed on basic block pointers.
00781 struct MBB2NumberFunctor :
00782   public std::unary_function<const MachineBasicBlock*, unsigned> {
00783   unsigned operator()(const MachineBasicBlock *MBB) const {
00784     return MBB->getNumber();
00785   }
00786 };
00787 
00788 //===--------------------------------------------------------------------===//
00789 // GraphTraits specializations for machine basic block graphs (machine-CFGs)
00790 //===--------------------------------------------------------------------===//
00791 
00792 // Provide specializations of GraphTraits to be able to treat a
00793 // MachineFunction as a graph of MachineBasicBlocks.
00794 //
00795 
00796 template <> struct GraphTraits<MachineBasicBlock *> {
00797   typedef MachineBasicBlock NodeType;
00798   typedef MachineBasicBlock::succ_iterator ChildIteratorType;
00799 
00800   static NodeType *getEntryNode(MachineBasicBlock *BB) { return BB; }
00801   static inline ChildIteratorType child_begin(NodeType *N) {
00802     return N->succ_begin();
00803   }
00804   static inline ChildIteratorType child_end(NodeType *N) {
00805     return N->succ_end();
00806   }
00807 };
00808 
00809 template <> struct GraphTraits<const MachineBasicBlock *> {
00810   typedef const MachineBasicBlock NodeType;
00811   typedef MachineBasicBlock::const_succ_iterator ChildIteratorType;
00812 
00813   static NodeType *getEntryNode(const MachineBasicBlock *BB) { return BB; }
00814   static inline ChildIteratorType child_begin(NodeType *N) {
00815     return N->succ_begin();
00816   }
00817   static inline ChildIteratorType child_end(NodeType *N) {
00818     return N->succ_end();
00819   }
00820 };
00821 
00822 // Provide specializations of GraphTraits to be able to treat a
00823 // MachineFunction as a graph of MachineBasicBlocks and to walk it
00824 // in inverse order.  Inverse order for a function is considered
00825 // to be when traversing the predecessor edges of a MBB
00826 // instead of the successor edges.
00827 //
00828 template <> struct GraphTraits<Inverse<MachineBasicBlock*> > {
00829   typedef MachineBasicBlock NodeType;
00830   typedef MachineBasicBlock::pred_iterator ChildIteratorType;
00831   static NodeType *getEntryNode(Inverse<MachineBasicBlock *> G) {
00832     return G.Graph;
00833   }
00834   static inline ChildIteratorType child_begin(NodeType *N) {
00835     return N->pred_begin();
00836   }
00837   static inline ChildIteratorType child_end(NodeType *N) {
00838     return N->pred_end();
00839   }
00840 };
00841 
00842 template <> struct GraphTraits<Inverse<const MachineBasicBlock*> > {
00843   typedef const MachineBasicBlock NodeType;
00844   typedef MachineBasicBlock::const_pred_iterator ChildIteratorType;
00845   static NodeType *getEntryNode(Inverse<const MachineBasicBlock*> G) {
00846     return G.Graph;
00847   }
00848   static inline ChildIteratorType child_begin(NodeType *N) {
00849     return N->pred_begin();
00850   }
00851   static inline ChildIteratorType child_end(NodeType *N) {
00852     return N->pred_end();
00853   }
00854 };
00855 
00856 
00857 
00858 /// MachineInstrSpan provides an interface to get an iteration range
00859 /// containing the instruction it was initialized with, along with all
00860 /// those instructions inserted prior to or following that instruction
00861 /// at some point after the MachineInstrSpan is constructed.
00862 class MachineInstrSpan {
00863   MachineBasicBlock &MBB;
00864   MachineBasicBlock::iterator I, B, E;
00865 public:
00866   MachineInstrSpan(MachineBasicBlock::iterator I)
00867     : MBB(*I->getParent()),
00868       I(I),
00869       B(I == MBB.begin() ? MBB.end() : std::prev(I)),
00870       E(std::next(I)) {}
00871 
00872   MachineBasicBlock::iterator begin() {
00873     return B == MBB.end() ? MBB.begin() : std::next(B);
00874   }
00875   MachineBasicBlock::iterator end() { return E; }
00876   bool empty() { return begin() == end(); }
00877 
00878   MachineBasicBlock::iterator getInitial() { return I; }
00879 };
00880 
00881 } // End llvm namespace
00882 
00883 #endif