MachineBasicBlock.h revision 296417
1228753Smm//===-- llvm/CodeGen/MachineBasicBlock.h ------------------------*- C++ -*-===// 2228753Smm// 3228753Smm// The LLVM Compiler Infrastructure 4228753Smm// 5228753Smm// This file is distributed under the University of Illinois Open Source 6228753Smm// License. See LICENSE.TXT for details. 7228753Smm// 8228753Smm//===----------------------------------------------------------------------===// 9228753Smm// 10228753Smm// Collect the sequence of machine instructions for a basic block. 11228753Smm// 12228753Smm//===----------------------------------------------------------------------===// 13228753Smm 14228753Smm#ifndef LLVM_CODEGEN_MACHINEBASICBLOCK_H 15228753Smm#define LLVM_CODEGEN_MACHINEBASICBLOCK_H 16228753Smm 17228753Smm#include "llvm/ADT/GraphTraits.h" 18228753Smm#include "llvm/CodeGen/MachineInstr.h" 19228753Smm#include "llvm/Support/BranchProbability.h" 20228753Smm#include "llvm/MC/MCRegisterInfo.h" 21228753Smm#include "llvm/Support/DataTypes.h" 22228753Smm#include <functional> 23228753Smm 24228753Smmnamespace llvm { 25228753Smm 26228753Smmclass Pass; 27228753Smmclass BasicBlock; 28229592Smmclass MachineFunction; 29228753Smmclass MCSymbol; 30228753Smmclass MIPrinter; 31228753Smmclass SlotIndexes; 32228753Smmclass StringRef; 33228753Smmclass raw_ostream; 34228753Smmclass MachineBranchProbabilityInfo; 35228753Smm 36228753Smm// Forward declaration to avoid circular include problem with TargetRegisterInfo 37228753Smmtypedef unsigned LaneBitmask; 38228753Smm 39228753Smmtemplate <> 40228753Smmstruct ilist_traits<MachineInstr> : public ilist_default_traits<MachineInstr> { 41228753Smmprivate: 42228753Smm mutable ilist_half_node<MachineInstr> Sentinel; 43228753Smm 44228753Smm // this is only set by the MachineBasicBlock owning the LiveList 45228753Smm friend class MachineBasicBlock; 46228753Smm MachineBasicBlock* Parent; 47228753Smm 48228753Smmpublic: 49228753Smm MachineInstr *createSentinel() const { 50228753Smm return static_cast<MachineInstr*>(&Sentinel); 51228753Smm } 52228753Smm void destroySentinel(MachineInstr *) const {} 53228753Smm 54228753Smm MachineInstr *provideInitialHead() const { return createSentinel(); } 55228753Smm MachineInstr *ensureHead(MachineInstr*) const { return createSentinel(); } 56228753Smm static void noteHead(MachineInstr*, MachineInstr*) {} 57228753Smm 58228753Smm void addNodeToList(MachineInstr* N); 59228753Smm void removeNodeFromList(MachineInstr* N); 60228753Smm void transferNodesFromList(ilist_traits &SrcTraits, 61228753Smm ilist_iterator<MachineInstr> First, 62228753Smm ilist_iterator<MachineInstr> Last); 63228753Smm void deleteNode(MachineInstr *N); 64228753Smmprivate: 65228753Smm void createNode(const MachineInstr &); 66228753Smm}; 67228753Smm 68228753Smmclass MachineBasicBlock 69228753Smm : public ilist_node_with_parent<MachineBasicBlock, MachineFunction> { 70228753Smmpublic: 71228753Smm /// Pair of physical register and lane mask. 72228753Smm /// This is not simply a std::pair typedef because the members should be named 73228753Smm /// clearly as they both have an integer type. 74228753Smm struct RegisterMaskPair { 75228753Smm public: 76228753Smm MCPhysReg PhysReg; 77228753Smm LaneBitmask LaneMask; 78228753Smm 79228753Smm RegisterMaskPair(MCPhysReg PhysReg, LaneBitmask LaneMask) 80228753Smm : PhysReg(PhysReg), LaneMask(LaneMask) {} 81228753Smm }; 82228753Smm 83228753Smmprivate: 84228753Smm typedef ilist<MachineInstr> Instructions; 85228753Smm Instructions Insts; 86228753Smm const BasicBlock *BB; 87228753Smm int Number; 88228753Smm MachineFunction *xParent; 89228753Smm 90228753Smm /// Keep track of the predecessor / successor basic blocks. 91228753Smm std::vector<MachineBasicBlock *> Predecessors; 92228753Smm std::vector<MachineBasicBlock *> Successors; 93228753Smm 94228753Smm /// Keep track of the probabilities to the successors. This vector has the 95228753Smm /// same order as Successors, or it is empty if we don't use it (disable 96228753Smm /// optimization). 97228753Smm std::vector<BranchProbability> Probs; 98228753Smm typedef std::vector<BranchProbability>::iterator probability_iterator; 99228753Smm typedef std::vector<BranchProbability>::const_iterator 100228753Smm const_probability_iterator; 101228753Smm 102228753Smm /// Keep track of the physical registers that are livein of the basicblock. 103228753Smm typedef std::vector<RegisterMaskPair> LiveInVector; 104228753Smm LiveInVector LiveIns; 105228753Smm 106228753Smm /// Alignment of the basic block. Zero if the basic block does not need to be 107228753Smm /// aligned. The alignment is specified as log2(bytes). 108228753Smm unsigned Alignment = 0; 109228753Smm 110228753Smm /// Indicate that this basic block is entered via an exception handler. 111228753Smm bool IsEHPad = false; 112228753Smm 113228753Smm /// Indicate that this basic block is potentially the target of an indirect 114228753Smm /// branch. 115228753Smm bool AddressTaken = false; 116228753Smm 117228753Smm /// Indicate that this basic block is the entry block of an EH funclet. 118228753Smm bool IsEHFuncletEntry = false; 119228753Smm 120228753Smm /// Indicate that this basic block is the entry block of a cleanup funclet. 121228753Smm bool IsCleanupFuncletEntry = false; 122228753Smm 123228753Smm /// \brief since getSymbol is a relatively heavy-weight operation, the symbol 124228753Smm /// is only computed once and is cached. 125228753Smm mutable MCSymbol *CachedMCSymbol = nullptr; 126228753Smm 127228753Smm // Intrusive list support 128228753Smm MachineBasicBlock() {} 129228753Smm 130228753Smm explicit MachineBasicBlock(MachineFunction &MF, const BasicBlock *BB); 131228753Smm 132228753Smm ~MachineBasicBlock(); 133228753Smm 134228753Smm // MachineBasicBlocks are allocated and owned by MachineFunction. 135228753Smm friend class MachineFunction; 136228753Smm 137228753Smmpublic: 138228753Smm /// Return the LLVM basic block that this instance corresponded to originally. 139228753Smm /// Note that this may be NULL if this instance does not correspond directly 140228753Smm /// to an LLVM basic block. 141228753Smm const BasicBlock *getBasicBlock() const { return BB; } 142228753Smm 143228753Smm /// Return the name of the corresponding LLVM basic block, or "(null)". 144228753Smm StringRef getName() const; 145228753Smm 146228753Smm /// Return a formatted string to identify this block and its parent function. 147228753Smm std::string getFullName() const; 148228753Smm 149228753Smm /// Test whether this block is potentially the target of an indirect branch. 150228753Smm bool hasAddressTaken() const { return AddressTaken; } 151228753Smm 152228753Smm /// Set this block to reflect that it potentially is the target of an indirect 153228753Smm /// branch. 154228753Smm void setHasAddressTaken() { AddressTaken = true; } 155228753Smm 156228753Smm /// Return the MachineFunction containing this basic block. 157228753Smm const MachineFunction *getParent() const { return xParent; } 158228753Smm MachineFunction *getParent() { return xParent; } 159228753Smm 160228753Smm /// MachineBasicBlock iterator that automatically skips over MIs that are 161228753Smm /// inside bundles (i.e. walk top level MIs only). 162228753Smm template<typename Ty, typename IterTy> 163228753Smm class bundle_iterator 164228753Smm : public std::iterator<std::bidirectional_iterator_tag, Ty, ptrdiff_t> { 165228753Smm IterTy MII; 166228753Smm 167228753Smm public: 168228753Smm bundle_iterator(IterTy MI) : MII(MI) {} 169228753Smm 170228753Smm bundle_iterator(Ty &MI) : MII(MI) { 171228753Smm assert(!MI.isBundledWithPred() && 172228753Smm "It's not legal to initialize bundle_iterator with a bundled MI"); 173228753Smm } 174228753Smm bundle_iterator(Ty *MI) : MII(MI) { 175228753Smm assert((!MI || !MI->isBundledWithPred()) && 176228753Smm "It's not legal to initialize bundle_iterator with a bundled MI"); 177228753Smm } 178228753Smm // Template allows conversion from const to nonconst. 179228753Smm template<class OtherTy, class OtherIterTy> 180228753Smm bundle_iterator(const bundle_iterator<OtherTy, OtherIterTy> &I) 181228753Smm : MII(I.getInstrIterator()) {} 182228753Smm bundle_iterator() : MII(nullptr) {} 183228753Smm 184228753Smm Ty &operator*() const { return *MII; } 185228753Smm Ty *operator->() const { return &operator*(); } 186228753Smm 187228753Smm operator Ty *() const { return MII.getNodePtrUnchecked(); } 188228753Smm 189228753Smm bool operator==(const bundle_iterator &X) const { 190228753Smm return MII == X.MII; 191228753Smm } 192228753Smm bool operator!=(const bundle_iterator &X) const { 193228753Smm return !operator==(X); 194228753Smm } 195228753Smm 196228753Smm // Increment and decrement operators... 197228753Smm bundle_iterator &operator--() { // predecrement - Back up 198228753Smm do --MII; 199228753Smm while (MII->isBundledWithPred()); 200228753Smm return *this; 201228753Smm } 202228753Smm bundle_iterator &operator++() { // preincrement - Advance 203228753Smm while (MII->isBundledWithSucc()) 204228753Smm ++MII; 205228753Smm ++MII; 206228753Smm return *this; 207228753Smm } 208228753Smm bundle_iterator operator--(int) { // postdecrement operators... 209228753Smm bundle_iterator tmp = *this; 210228753Smm --*this; 211228753Smm return tmp; 212228753Smm } 213228753Smm bundle_iterator operator++(int) { // postincrement operators... 214228753Smm bundle_iterator tmp = *this; 215228753Smm ++*this; 216228753Smm return tmp; 217228753Smm } 218228753Smm 219228753Smm IterTy getInstrIterator() const { 220228753Smm return MII; 221228753Smm } 222228753Smm }; 223228753Smm 224228753Smm typedef Instructions::iterator instr_iterator; 225228753Smm typedef Instructions::const_iterator const_instr_iterator; 226228753Smm typedef std::reverse_iterator<instr_iterator> reverse_instr_iterator; 227228753Smm typedef 228228753Smm std::reverse_iterator<const_instr_iterator> const_reverse_instr_iterator; 229228753Smm 230228753Smm typedef 231228753Smm bundle_iterator<MachineInstr,instr_iterator> iterator; 232228753Smm typedef 233228753Smm bundle_iterator<const MachineInstr,const_instr_iterator> const_iterator; 234228753Smm typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 235228753Smm typedef std::reverse_iterator<iterator> reverse_iterator; 236228753Smm 237228753Smm 238228753Smm unsigned size() const { return (unsigned)Insts.size(); } 239228753Smm bool empty() const { return Insts.empty(); } 240228753Smm 241228753Smm MachineInstr &instr_front() { return Insts.front(); } 242228753Smm MachineInstr &instr_back() { return Insts.back(); } 243228753Smm const MachineInstr &instr_front() const { return Insts.front(); } 244228753Smm const MachineInstr &instr_back() const { return Insts.back(); } 245228753Smm 246228753Smm MachineInstr &front() { return Insts.front(); } 247228753Smm MachineInstr &back() { return *--end(); } 248228753Smm const MachineInstr &front() const { return Insts.front(); } 249228753Smm const MachineInstr &back() const { return *--end(); } 250228753Smm 251228753Smm instr_iterator instr_begin() { return Insts.begin(); } 252228753Smm const_instr_iterator instr_begin() const { return Insts.begin(); } 253228753Smm instr_iterator instr_end() { return Insts.end(); } 254228753Smm const_instr_iterator instr_end() const { return Insts.end(); } 255228753Smm reverse_instr_iterator instr_rbegin() { return Insts.rbegin(); } 256228753Smm const_reverse_instr_iterator instr_rbegin() const { return Insts.rbegin(); } 257228753Smm reverse_instr_iterator instr_rend () { return Insts.rend(); } 258228753Smm const_reverse_instr_iterator instr_rend () const { return Insts.rend(); } 259228753Smm 260228753Smm iterator begin() { return instr_begin(); } 261228753Smm const_iterator begin() const { return instr_begin(); } 262228753Smm iterator end () { return instr_end(); } 263228753Smm const_iterator end () const { return instr_end(); } 264228753Smm reverse_iterator rbegin() { return instr_rbegin(); } 265228753Smm const_reverse_iterator rbegin() const { return instr_rbegin(); } 266228753Smm reverse_iterator rend () { return instr_rend(); } 267228753Smm const_reverse_iterator rend () const { return instr_rend(); } 268228753Smm 269228753Smm /// Support for MachineInstr::getNextNode(). 270228753Smm static Instructions MachineBasicBlock::*getSublistAccess(MachineInstr *) { 271228753Smm return &MachineBasicBlock::Insts; 272228753Smm } 273228753Smm 274228753Smm inline iterator_range<iterator> terminators() { 275228753Smm return make_range(getFirstTerminator(), end()); 276228753Smm } 277228753Smm inline iterator_range<const_iterator> terminators() const { 278228753Smm return make_range(getFirstTerminator(), end()); 279228753Smm } 280228753Smm 281228753Smm // Machine-CFG iterators 282228753Smm typedef std::vector<MachineBasicBlock *>::iterator pred_iterator; 283228753Smm typedef std::vector<MachineBasicBlock *>::const_iterator const_pred_iterator; 284228753Smm typedef std::vector<MachineBasicBlock *>::iterator succ_iterator; 285228753Smm typedef std::vector<MachineBasicBlock *>::const_iterator const_succ_iterator; 286228753Smm typedef std::vector<MachineBasicBlock *>::reverse_iterator 287228753Smm pred_reverse_iterator; 288228753Smm typedef std::vector<MachineBasicBlock *>::const_reverse_iterator 289228753Smm const_pred_reverse_iterator; 290228753Smm typedef std::vector<MachineBasicBlock *>::reverse_iterator 291228753Smm succ_reverse_iterator; 292228753Smm typedef std::vector<MachineBasicBlock *>::const_reverse_iterator 293228753Smm const_succ_reverse_iterator; 294228753Smm pred_iterator pred_begin() { return Predecessors.begin(); } 295228753Smm const_pred_iterator pred_begin() const { return Predecessors.begin(); } 296228753Smm pred_iterator pred_end() { return Predecessors.end(); } 297228753Smm const_pred_iterator pred_end() const { return Predecessors.end(); } 298228753Smm pred_reverse_iterator pred_rbegin() 299228753Smm { return Predecessors.rbegin();} 300228753Smm const_pred_reverse_iterator pred_rbegin() const 301228753Smm { return Predecessors.rbegin();} 302228753Smm pred_reverse_iterator pred_rend() 303228753Smm { return Predecessors.rend(); } 304228753Smm const_pred_reverse_iterator pred_rend() const 305228753Smm { return Predecessors.rend(); } 306228753Smm unsigned pred_size() const { 307228753Smm return (unsigned)Predecessors.size(); 308228753Smm } 309228753Smm bool pred_empty() const { return Predecessors.empty(); } 310228753Smm succ_iterator succ_begin() { return Successors.begin(); } 311228753Smm const_succ_iterator succ_begin() const { return Successors.begin(); } 312228753Smm succ_iterator succ_end() { return Successors.end(); } 313228753Smm const_succ_iterator succ_end() const { return Successors.end(); } 314228753Smm succ_reverse_iterator succ_rbegin() 315228753Smm { return Successors.rbegin(); } 316228753Smm const_succ_reverse_iterator succ_rbegin() const 317228753Smm { return Successors.rbegin(); } 318228753Smm succ_reverse_iterator succ_rend() 319228753Smm { return Successors.rend(); } 320228753Smm const_succ_reverse_iterator succ_rend() const 321228753Smm { return Successors.rend(); } 322228753Smm unsigned succ_size() const { 323228753Smm return (unsigned)Successors.size(); 324228753Smm } 325228753Smm bool succ_empty() const { return Successors.empty(); } 326228753Smm 327228753Smm inline iterator_range<pred_iterator> predecessors() { 328228753Smm return make_range(pred_begin(), pred_end()); 329228753Smm } 330228753Smm inline iterator_range<const_pred_iterator> predecessors() const { 331228753Smm return make_range(pred_begin(), pred_end()); 332228753Smm } 333228753Smm inline iterator_range<succ_iterator> successors() { 334228753Smm return make_range(succ_begin(), succ_end()); 335228753Smm } 336228753Smm inline iterator_range<const_succ_iterator> successors() const { 337228753Smm return make_range(succ_begin(), succ_end()); 338228753Smm } 339228753Smm 340228753Smm // LiveIn management methods. 341228753Smm 342228753Smm /// Adds the specified register as a live in. Note that it is an error to add 343228753Smm /// the same register to the same set more than once unless the intention is 344228753Smm /// to call sortUniqueLiveIns after all registers are added. 345228753Smm void addLiveIn(MCPhysReg PhysReg, LaneBitmask LaneMask = ~0u) { 346228753Smm LiveIns.push_back(RegisterMaskPair(PhysReg, LaneMask)); 347228753Smm } 348228753Smm void addLiveIn(const RegisterMaskPair &RegMaskPair) { 349228753Smm LiveIns.push_back(RegMaskPair); 350228753Smm } 351228753Smm 352228753Smm /// Sorts and uniques the LiveIns vector. It can be significantly faster to do 353228753Smm /// this than repeatedly calling isLiveIn before calling addLiveIn for every 354228753Smm /// LiveIn insertion. 355228753Smm void sortUniqueLiveIns(); 356228753Smm 357228753Smm /// Add PhysReg as live in to this block, and ensure that there is a copy of 358228753Smm /// PhysReg to a virtual register of class RC. Return the virtual register 359228753Smm /// that is a copy of the live in PhysReg. 360228753Smm unsigned addLiveIn(MCPhysReg PhysReg, const TargetRegisterClass *RC); 361228753Smm 362228753Smm /// Remove the specified register from the live in set. 363228753Smm void removeLiveIn(MCPhysReg Reg, LaneBitmask LaneMask = ~0u); 364228753Smm 365228753Smm /// Return true if the specified register is in the live in set. 366228753Smm bool isLiveIn(MCPhysReg Reg, LaneBitmask LaneMask = ~0u) const; 367228753Smm 368228753Smm // Iteration support for live in sets. These sets are kept in sorted 369228753Smm // order by their register number. 370228753Smm typedef LiveInVector::const_iterator livein_iterator; 371228753Smm livein_iterator livein_begin() const { return LiveIns.begin(); } 372228753Smm livein_iterator livein_end() const { return LiveIns.end(); } 373228753Smm bool livein_empty() const { return LiveIns.empty(); } 374228753Smm iterator_range<livein_iterator> liveins() const { 375228753Smm return make_range(livein_begin(), livein_end()); 376228753Smm } 377228753Smm 378228753Smm /// Get the clobber mask for the start of this basic block. Funclets use this 379228753Smm /// to prevent register allocation across funclet transitions. 380228753Smm const uint32_t *getBeginClobberMask(const TargetRegisterInfo *TRI) const; 381228753Smm 382228753Smm /// Get the clobber mask for the end of the basic block. 383228753Smm /// \see getBeginClobberMask() 384228753Smm const uint32_t *getEndClobberMask(const TargetRegisterInfo *TRI) const; 385228753Smm 386228753Smm /// Return alignment of the basic block. The alignment is specified as 387228753Smm /// log2(bytes). 388228753Smm unsigned getAlignment() const { return Alignment; } 389228753Smm 390228753Smm /// Set alignment of the basic block. The alignment is specified as 391228753Smm /// log2(bytes). 392228753Smm void setAlignment(unsigned Align) { Alignment = Align; } 393228753Smm 394228753Smm /// Returns true if the block is a landing pad. That is this basic block is 395228753Smm /// entered via an exception handler. 396228753Smm bool isEHPad() const { return IsEHPad; } 397228753Smm 398228753Smm /// Indicates the block is a landing pad. That is this basic block is entered 399228753Smm /// via an exception handler. 400228753Smm void setIsEHPad(bool V = true) { IsEHPad = V; } 401228753Smm 402228753Smm /// If this block has a successor that is a landing pad, return it. Otherwise 403228753Smm /// return NULL. 404228753Smm const MachineBasicBlock *getLandingPadSuccessor() const; 405228753Smm 406228753Smm bool hasEHPadSuccessor() const; 407228753Smm 408228753Smm /// Returns true if this is the entry block of an EH funclet. 409228753Smm bool isEHFuncletEntry() const { return IsEHFuncletEntry; } 410228753Smm 411228753Smm /// Indicates if this is the entry block of an EH funclet. 412228753Smm void setIsEHFuncletEntry(bool V = true) { IsEHFuncletEntry = V; } 413228753Smm 414228753Smm /// Returns true if this is the entry block of a cleanup funclet. 415228753Smm bool isCleanupFuncletEntry() const { return IsCleanupFuncletEntry; } 416228753Smm 417228753Smm /// Indicates if this is the entry block of a cleanup funclet. 418228753Smm void setIsCleanupFuncletEntry(bool V = true) { IsCleanupFuncletEntry = V; } 419228753Smm 420228753Smm // Code Layout methods. 421228753Smm 422228753Smm /// Move 'this' block before or after the specified block. This only moves 423228753Smm /// the block, it does not modify the CFG or adjust potential fall-throughs at 424228753Smm /// the end of the block. 425228753Smm void moveBefore(MachineBasicBlock *NewAfter); 426228753Smm void moveAfter(MachineBasicBlock *NewBefore); 427228753Smm 428228753Smm /// Update the terminator instructions in block to account for changes to the 429228753Smm /// layout. If the block previously used a fallthrough, it may now need a 430228753Smm /// branch, and if it previously used branching it may now be able to use a 431228753Smm /// fallthrough. 432228753Smm void updateTerminator(); 433228753Smm 434228753Smm // Machine-CFG mutators 435228753Smm 436228753Smm /// Add Succ as a successor of this MachineBasicBlock. The Predecessors list 437228753Smm /// of Succ is automatically updated. PROB parameter is stored in 438228753Smm /// Probabilities list. The default probability is set as unknown. Mixing 439228753Smm /// known and unknown probabilities in successor list is not allowed. When all 440228753Smm /// successors have unknown probabilities, 1 / N is returned as the 441228753Smm /// probability for each successor, where N is the number of successors. 442228753Smm /// 443228753Smm /// Note that duplicate Machine CFG edges are not allowed. 444228753Smm void addSuccessor(MachineBasicBlock *Succ, 445228753Smm BranchProbability Prob = BranchProbability::getUnknown()); 446228753Smm 447228753Smm /// Add Succ as a successor of this MachineBasicBlock. The Predecessors list 448228753Smm /// of Succ is automatically updated. The probability is not provided because 449228753Smm /// BPI is not available (e.g. -O0 is used), in which case edge probabilities 450228753Smm /// won't be used. Using this interface can save some space. 451228753Smm void addSuccessorWithoutProb(MachineBasicBlock *Succ); 452228753Smm 453228753Smm /// Set successor probability of a given iterator. 454228753Smm void setSuccProbability(succ_iterator I, BranchProbability Prob); 455228753Smm 456228753Smm /// Normalize probabilities of all successors so that the sum of them becomes 457228753Smm /// one. This is usually done when the current update on this MBB is done, and 458228753Smm /// the sum of its successors' probabilities is not guaranteed to be one. The 459228753Smm /// user is responsible for the correct use of this function. 460228753Smm /// MBB::removeSuccessor() has an option to do this automatically. 461228753Smm void normalizeSuccProbs() { 462228753Smm BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end()); 463228753Smm } 464228753Smm 465228753Smm /// Validate successors' probabilities and check if the sum of them is 466228753Smm /// approximate one. This only works in DEBUG mode. 467228753Smm void validateSuccProbs() const; 468228753Smm 469228753Smm /// Remove successor from the successors list of this MachineBasicBlock. The 470228753Smm /// Predecessors list of Succ is automatically updated. 471228753Smm /// If NormalizeSuccProbs is true, then normalize successors' probabilities 472228753Smm /// after the successor is removed. 473228753Smm void removeSuccessor(MachineBasicBlock *Succ, 474228753Smm bool NormalizeSuccProbs = false); 475228753Smm 476228753Smm /// Remove specified successor from the successors list of this 477228753Smm /// MachineBasicBlock. The Predecessors list of Succ is automatically updated. 478 /// If NormalizeSuccProbs is true, then normalize successors' probabilities 479 /// after the successor is removed. 480 /// Return the iterator to the element after the one removed. 481 succ_iterator removeSuccessor(succ_iterator I, 482 bool NormalizeSuccProbs = false); 483 484 /// Replace successor OLD with NEW and update probability info. 485 void replaceSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New); 486 487 /// Transfers all the successors from MBB to this machine basic block (i.e., 488 /// copies all the successors FromMBB and remove all the successors from 489 /// FromMBB). 490 void transferSuccessors(MachineBasicBlock *FromMBB); 491 492 /// Transfers all the successors, as in transferSuccessors, and update PHI 493 /// operands in the successor blocks which refer to FromMBB to refer to this. 494 void transferSuccessorsAndUpdatePHIs(MachineBasicBlock *FromMBB); 495 496 /// Return true if any of the successors have probabilities attached to them. 497 bool hasSuccessorProbabilities() const { return !Probs.empty(); } 498 499 /// Return true if the specified MBB is a predecessor of this block. 500 bool isPredecessor(const MachineBasicBlock *MBB) const; 501 502 /// Return true if the specified MBB is a successor of this block. 503 bool isSuccessor(const MachineBasicBlock *MBB) const; 504 505 /// Return true if the specified MBB will be emitted immediately after this 506 /// block, such that if this block exits by falling through, control will 507 /// transfer to the specified MBB. Note that MBB need not be a successor at 508 /// all, for example if this block ends with an unconditional branch to some 509 /// other block. 510 bool isLayoutSuccessor(const MachineBasicBlock *MBB) const; 511 512 /// Return true if the block can implicitly transfer control to the block 513 /// after it by falling off the end of it. This should return false if it can 514 /// reach the block after it, but it uses an explicit branch to do so (e.g., a 515 /// table jump). True is a conservative answer. 516 bool canFallThrough(); 517 518 /// Returns a pointer to the first instruction in this block that is not a 519 /// PHINode instruction. When adding instructions to the beginning of the 520 /// basic block, they should be added before the returned value, not before 521 /// the first instruction, which might be PHI. 522 /// Returns end() is there's no non-PHI instruction. 523 iterator getFirstNonPHI(); 524 525 /// Return the first instruction in MBB after I that is not a PHI or a label. 526 /// This is the correct point to insert copies at the beginning of a basic 527 /// block. 528 iterator SkipPHIsAndLabels(iterator I); 529 530 /// Returns an iterator to the first terminator instruction of this basic 531 /// block. If a terminator does not exist, it returns end(). 532 iterator getFirstTerminator(); 533 const_iterator getFirstTerminator() const { 534 return const_cast<MachineBasicBlock *>(this)->getFirstTerminator(); 535 } 536 537 /// Same getFirstTerminator but it ignores bundles and return an 538 /// instr_iterator instead. 539 instr_iterator getFirstInstrTerminator(); 540 541 /// Returns an iterator to the first non-debug instruction in the basic block, 542 /// or end(). 543 iterator getFirstNonDebugInstr(); 544 const_iterator getFirstNonDebugInstr() const { 545 return const_cast<MachineBasicBlock *>(this)->getFirstNonDebugInstr(); 546 } 547 548 /// Returns an iterator to the last non-debug instruction in the basic block, 549 /// or end(). 550 iterator getLastNonDebugInstr(); 551 const_iterator getLastNonDebugInstr() const { 552 return const_cast<MachineBasicBlock *>(this)->getLastNonDebugInstr(); 553 } 554 555 /// Convenience function that returns true if the block ends in a return 556 /// instruction. 557 bool isReturnBlock() const { 558 return !empty() && back().isReturn(); 559 } 560 561 /// Split the critical edge from this block to the given successor block, and 562 /// return the newly created block, or null if splitting is not possible. 563 /// 564 /// This function updates LiveVariables, MachineDominatorTree, and 565 /// MachineLoopInfo, as applicable. 566 MachineBasicBlock *SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P); 567 568 void pop_front() { Insts.pop_front(); } 569 void pop_back() { Insts.pop_back(); } 570 void push_back(MachineInstr *MI) { Insts.push_back(MI); } 571 572 /// Insert MI into the instruction list before I, possibly inside a bundle. 573 /// 574 /// If the insertion point is inside a bundle, MI will be added to the bundle, 575 /// otherwise MI will not be added to any bundle. That means this function 576 /// alone can't be used to prepend or append instructions to bundles. See 577 /// MIBundleBuilder::insert() for a more reliable way of doing that. 578 instr_iterator insert(instr_iterator I, MachineInstr *M); 579 580 /// Insert a range of instructions into the instruction list before I. 581 template<typename IT> 582 void insert(iterator I, IT S, IT E) { 583 assert((I == end() || I->getParent() == this) && 584 "iterator points outside of basic block"); 585 Insts.insert(I.getInstrIterator(), S, E); 586 } 587 588 /// Insert MI into the instruction list before I. 589 iterator insert(iterator I, MachineInstr *MI) { 590 assert((I == end() || I->getParent() == this) && 591 "iterator points outside of basic block"); 592 assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() && 593 "Cannot insert instruction with bundle flags"); 594 return Insts.insert(I.getInstrIterator(), MI); 595 } 596 597 /// Insert MI into the instruction list after I. 598 iterator insertAfter(iterator I, MachineInstr *MI) { 599 assert((I == end() || I->getParent() == this) && 600 "iterator points outside of basic block"); 601 assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() && 602 "Cannot insert instruction with bundle flags"); 603 return Insts.insertAfter(I.getInstrIterator(), MI); 604 } 605 606 /// Remove an instruction from the instruction list and delete it. 607 /// 608 /// If the instruction is part of a bundle, the other instructions in the 609 /// bundle will still be bundled after removing the single instruction. 610 instr_iterator erase(instr_iterator I); 611 612 /// Remove an instruction from the instruction list and delete it. 613 /// 614 /// If the instruction is part of a bundle, the other instructions in the 615 /// bundle will still be bundled after removing the single instruction. 616 instr_iterator erase_instr(MachineInstr *I) { 617 return erase(instr_iterator(I)); 618 } 619 620 /// Remove a range of instructions from the instruction list and delete them. 621 iterator erase(iterator I, iterator E) { 622 return Insts.erase(I.getInstrIterator(), E.getInstrIterator()); 623 } 624 625 /// Remove an instruction or bundle from the instruction list and delete it. 626 /// 627 /// If I points to a bundle of instructions, they are all erased. 628 iterator erase(iterator I) { 629 return erase(I, std::next(I)); 630 } 631 632 /// Remove an instruction from the instruction list and delete it. 633 /// 634 /// If I is the head of a bundle of instructions, the whole bundle will be 635 /// erased. 636 iterator erase(MachineInstr *I) { 637 return erase(iterator(I)); 638 } 639 640 /// Remove the unbundled instruction from the instruction list without 641 /// deleting it. 642 /// 643 /// This function can not be used to remove bundled instructions, use 644 /// remove_instr to remove individual instructions from a bundle. 645 MachineInstr *remove(MachineInstr *I) { 646 assert(!I->isBundled() && "Cannot remove bundled instructions"); 647 return Insts.remove(instr_iterator(I)); 648 } 649 650 /// Remove the possibly bundled instruction from the instruction list 651 /// without deleting it. 652 /// 653 /// If the instruction is part of a bundle, the other instructions in the 654 /// bundle will still be bundled after removing the single instruction. 655 MachineInstr *remove_instr(MachineInstr *I); 656 657 void clear() { 658 Insts.clear(); 659 } 660 661 /// Take an instruction from MBB 'Other' at the position From, and insert it 662 /// into this MBB right before 'Where'. 663 /// 664 /// If From points to a bundle of instructions, the whole bundle is moved. 665 void splice(iterator Where, MachineBasicBlock *Other, iterator From) { 666 // The range splice() doesn't allow noop moves, but this one does. 667 if (Where != From) 668 splice(Where, Other, From, std::next(From)); 669 } 670 671 /// Take a block of instructions from MBB 'Other' in the range [From, To), 672 /// and insert them into this MBB right before 'Where'. 673 /// 674 /// The instruction at 'Where' must not be included in the range of 675 /// instructions to move. 676 void splice(iterator Where, MachineBasicBlock *Other, 677 iterator From, iterator To) { 678 Insts.splice(Where.getInstrIterator(), Other->Insts, 679 From.getInstrIterator(), To.getInstrIterator()); 680 } 681 682 /// This method unlinks 'this' from the containing function, and returns it, 683 /// but does not delete it. 684 MachineBasicBlock *removeFromParent(); 685 686 /// This method unlinks 'this' from the containing function and deletes it. 687 void eraseFromParent(); 688 689 /// Given a machine basic block that branched to 'Old', change the code and 690 /// CFG so that it branches to 'New' instead. 691 void ReplaceUsesOfBlockWith(MachineBasicBlock *Old, MachineBasicBlock *New); 692 693 /// Various pieces of code can cause excess edges in the CFG to be inserted. 694 /// If we have proven that MBB can only branch to DestA and DestB, remove any 695 /// other MBB successors from the CFG. DestA and DestB can be null. Besides 696 /// DestA and DestB, retain other edges leading to LandingPads (currently 697 /// there can be only one; we don't check or require that here). Note it is 698 /// possible that DestA and/or DestB are LandingPads. 699 bool CorrectExtraCFGEdges(MachineBasicBlock *DestA, 700 MachineBasicBlock *DestB, 701 bool IsCond); 702 703 /// Find the next valid DebugLoc starting at MBBI, skipping any DBG_VALUE 704 /// instructions. Return UnknownLoc if there is none. 705 DebugLoc findDebugLoc(instr_iterator MBBI); 706 DebugLoc findDebugLoc(iterator MBBI) { 707 return findDebugLoc(MBBI.getInstrIterator()); 708 } 709 710 /// Possible outcome of a register liveness query to computeRegisterLiveness() 711 enum LivenessQueryResult { 712 LQR_Live, ///< Register is known to be (at least partially) live. 713 LQR_Dead, ///< Register is known to be fully dead. 714 LQR_Unknown ///< Register liveness not decidable from local neighborhood. 715 }; 716 717 /// Return whether (physical) register \p Reg has been <def>ined and not 718 /// <kill>ed as of just before \p Before. 719 /// 720 /// Search is localised to a neighborhood of \p Neighborhood instructions 721 /// before (searching for defs or kills) and \p Neighborhood instructions 722 /// after (searching just for defs) \p Before. 723 /// 724 /// \p Reg must be a physical register. 725 LivenessQueryResult computeRegisterLiveness(const TargetRegisterInfo *TRI, 726 unsigned Reg, 727 const_iterator Before, 728 unsigned Neighborhood=10) const; 729 730 // Debugging methods. 731 void dump() const; 732 void print(raw_ostream &OS, SlotIndexes* = nullptr) const; 733 void print(raw_ostream &OS, ModuleSlotTracker &MST, 734 SlotIndexes * = nullptr) const; 735 736 // Printing method used by LoopInfo. 737 void printAsOperand(raw_ostream &OS, bool PrintType = true) const; 738 739 /// MachineBasicBlocks are uniquely numbered at the function level, unless 740 /// they're not in a MachineFunction yet, in which case this will return -1. 741 int getNumber() const { return Number; } 742 void setNumber(int N) { Number = N; } 743 744 /// Return the MCSymbol for this basic block. 745 MCSymbol *getSymbol() const; 746 747 748private: 749 /// Return probability iterator corresponding to the I successor iterator. 750 probability_iterator getProbabilityIterator(succ_iterator I); 751 const_probability_iterator 752 getProbabilityIterator(const_succ_iterator I) const; 753 754 friend class MachineBranchProbabilityInfo; 755 friend class MIPrinter; 756 757 /// Return probability of the edge from this block to MBB. This method should 758 /// NOT be called directly, but by using getEdgeProbability method from 759 /// MachineBranchProbabilityInfo class. 760 BranchProbability getSuccProbability(const_succ_iterator Succ) const; 761 762 // Methods used to maintain doubly linked list of blocks... 763 friend struct ilist_traits<MachineBasicBlock>; 764 765 // Machine-CFG mutators 766 767 /// Remove Pred as a predecessor of this MachineBasicBlock. Don't do this 768 /// unless you know what you're doing, because it doesn't update Pred's 769 /// successors list. Use Pred->addSuccessor instead. 770 void addPredecessor(MachineBasicBlock *Pred); 771 772 /// Remove Pred as a predecessor of this MachineBasicBlock. Don't do this 773 /// unless you know what you're doing, because it doesn't update Pred's 774 /// successors list. Use Pred->removeSuccessor instead. 775 void removePredecessor(MachineBasicBlock *Pred); 776}; 777 778raw_ostream& operator<<(raw_ostream &OS, const MachineBasicBlock &MBB); 779 780// This is useful when building IndexedMaps keyed on basic block pointers. 781struct MBB2NumberFunctor : 782 public std::unary_function<const MachineBasicBlock*, unsigned> { 783 unsigned operator()(const MachineBasicBlock *MBB) const { 784 return MBB->getNumber(); 785 } 786}; 787 788//===--------------------------------------------------------------------===// 789// GraphTraits specializations for machine basic block graphs (machine-CFGs) 790//===--------------------------------------------------------------------===// 791 792// Provide specializations of GraphTraits to be able to treat a 793// MachineFunction as a graph of MachineBasicBlocks. 794// 795 796template <> struct GraphTraits<MachineBasicBlock *> { 797 typedef MachineBasicBlock NodeType; 798 typedef MachineBasicBlock::succ_iterator ChildIteratorType; 799 800 static NodeType *getEntryNode(MachineBasicBlock *BB) { return BB; } 801 static inline ChildIteratorType child_begin(NodeType *N) { 802 return N->succ_begin(); 803 } 804 static inline ChildIteratorType child_end(NodeType *N) { 805 return N->succ_end(); 806 } 807}; 808 809template <> struct GraphTraits<const MachineBasicBlock *> { 810 typedef const MachineBasicBlock NodeType; 811 typedef MachineBasicBlock::const_succ_iterator ChildIteratorType; 812 813 static NodeType *getEntryNode(const MachineBasicBlock *BB) { return BB; } 814 static inline ChildIteratorType child_begin(NodeType *N) { 815 return N->succ_begin(); 816 } 817 static inline ChildIteratorType child_end(NodeType *N) { 818 return N->succ_end(); 819 } 820}; 821 822// Provide specializations of GraphTraits to be able to treat a 823// MachineFunction as a graph of MachineBasicBlocks and to walk it 824// in inverse order. Inverse order for a function is considered 825// to be when traversing the predecessor edges of a MBB 826// instead of the successor edges. 827// 828template <> struct GraphTraits<Inverse<MachineBasicBlock*> > { 829 typedef MachineBasicBlock NodeType; 830 typedef MachineBasicBlock::pred_iterator ChildIteratorType; 831 static NodeType *getEntryNode(Inverse<MachineBasicBlock *> G) { 832 return G.Graph; 833 } 834 static inline ChildIteratorType child_begin(NodeType *N) { 835 return N->pred_begin(); 836 } 837 static inline ChildIteratorType child_end(NodeType *N) { 838 return N->pred_end(); 839 } 840}; 841 842template <> struct GraphTraits<Inverse<const MachineBasicBlock*> > { 843 typedef const MachineBasicBlock NodeType; 844 typedef MachineBasicBlock::const_pred_iterator ChildIteratorType; 845 static NodeType *getEntryNode(Inverse<const MachineBasicBlock*> G) { 846 return G.Graph; 847 } 848 static inline ChildIteratorType child_begin(NodeType *N) { 849 return N->pred_begin(); 850 } 851 static inline ChildIteratorType child_end(NodeType *N) { 852 return N->pred_end(); 853 } 854}; 855 856 857 858/// MachineInstrSpan provides an interface to get an iteration range 859/// containing the instruction it was initialized with, along with all 860/// those instructions inserted prior to or following that instruction 861/// at some point after the MachineInstrSpan is constructed. 862class MachineInstrSpan { 863 MachineBasicBlock &MBB; 864 MachineBasicBlock::iterator I, B, E; 865public: 866 MachineInstrSpan(MachineBasicBlock::iterator I) 867 : MBB(*I->getParent()), 868 I(I), 869 B(I == MBB.begin() ? MBB.end() : std::prev(I)), 870 E(std::next(I)) {} 871 872 MachineBasicBlock::iterator begin() { 873 return B == MBB.end() ? MBB.begin() : std::next(B); 874 } 875 MachineBasicBlock::iterator end() { return E; } 876 bool empty() { return begin() == end(); } 877 878 MachineBasicBlock::iterator getInitial() { return I; } 879}; 880 881} // End llvm namespace 882 883#endif 884