1193323Sed//===-- llvm/CodeGen/MachineBasicBlock.h ------------------------*- C++ -*-===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// Collect the sequence of machine instructions for a basic block. 11193323Sed// 12193323Sed//===----------------------------------------------------------------------===// 13193323Sed 14193323Sed#ifndef LLVM_CODEGEN_MACHINEBASICBLOCK_H 15193323Sed#define LLVM_CODEGEN_MACHINEBASICBLOCK_H 16193323Sed 17249423Sdim#include "llvm/ADT/GraphTraits.h" 18193323Sed#include "llvm/CodeGen/MachineInstr.h" 19224145Sdim#include "llvm/Support/DataTypes.h" 20221345Sdim#include <functional> 21193323Sed 22193323Sednamespace llvm { 23193323Sed 24210299Sedclass Pass; 25193323Sedclass BasicBlock; 26193323Sedclass MachineFunction; 27203954Srdivackyclass MCSymbol; 28218893Sdimclass SlotIndexes; 29203954Srdivackyclass StringRef; 30198090Srdivackyclass raw_ostream; 31224145Sdimclass MachineBranchProbabilityInfo; 32193323Sed 33193323Sedtemplate <> 34193323Sedstruct ilist_traits<MachineInstr> : public ilist_default_traits<MachineInstr> { 35193323Sedprivate: 36198090Srdivacky mutable ilist_half_node<MachineInstr> Sentinel; 37193323Sed 38193323Sed // this is only set by the MachineBasicBlock owning the LiveList 39193323Sed friend class MachineBasicBlock; 40193323Sed MachineBasicBlock* Parent; 41193323Sed 42193323Sedpublic: 43193323Sed MachineInstr *createSentinel() const { 44193323Sed return static_cast<MachineInstr*>(&Sentinel); 45193323Sed } 46193323Sed void destroySentinel(MachineInstr *) const {} 47193323Sed 48193323Sed MachineInstr *provideInitialHead() const { return createSentinel(); } 49193323Sed MachineInstr *ensureHead(MachineInstr*) const { return createSentinel(); } 50193323Sed static void noteHead(MachineInstr*, MachineInstr*) {} 51193323Sed 52193323Sed void addNodeToList(MachineInstr* N); 53193323Sed void removeNodeFromList(MachineInstr* N); 54193323Sed void transferNodesFromList(ilist_traits &SrcTraits, 55193323Sed ilist_iterator<MachineInstr> first, 56193323Sed ilist_iterator<MachineInstr> last); 57193323Sed void deleteNode(MachineInstr *N); 58193323Sedprivate: 59193323Sed void createNode(const MachineInstr &); 60193323Sed}; 61193323Sed 62193323Sedclass MachineBasicBlock : public ilist_node<MachineBasicBlock> { 63193323Sed typedef ilist<MachineInstr> Instructions; 64193323Sed Instructions Insts; 65193323Sed const BasicBlock *BB; 66193323Sed int Number; 67193323Sed MachineFunction *xParent; 68224145Sdim 69193323Sed /// Predecessors/Successors - Keep track of the predecessor / successor 70193323Sed /// basicblocks. 71193323Sed std::vector<MachineBasicBlock *> Predecessors; 72193323Sed std::vector<MachineBasicBlock *> Successors; 73193323Sed 74224145Sdim /// Weights - Keep track of the weights to the successors. This vector 75224145Sdim /// has the same order as Successors, or it is empty if we don't use it 76224145Sdim /// (disable optimization). 77224145Sdim std::vector<uint32_t> Weights; 78224145Sdim typedef std::vector<uint32_t>::iterator weight_iterator; 79234353Sdim typedef std::vector<uint32_t>::const_iterator const_weight_iterator; 80224145Sdim 81193323Sed /// LiveIns - Keep track of the physical registers that are livein of 82193323Sed /// the basicblock. 83193323Sed std::vector<unsigned> LiveIns; 84193323Sed 85193323Sed /// Alignment - Alignment of the basic block. Zero if the basic block does 86193323Sed /// not need to be aligned. 87234353Sdim /// The alignment is specified as log2(bytes). 88193323Sed unsigned Alignment; 89234353Sdim 90193323Sed /// IsLandingPad - Indicate that this basic block is entered via an 91193323Sed /// exception handler. 92193323Sed bool IsLandingPad; 93193323Sed 94198892Srdivacky /// AddressTaken - Indicate that this basic block is potentially the 95198892Srdivacky /// target of an indirect branch. 96198892Srdivacky bool AddressTaken; 97198892Srdivacky 98251662Sdim /// \brief since getSymbol is a relatively heavy-weight operation, the symbol 99251662Sdim /// is only computed once and is cached. 100251662Sdim mutable MCSymbol *CachedMCSymbol; 101251662Sdim 102193323Sed // Intrusive list support 103193323Sed MachineBasicBlock() {} 104193323Sed 105193323Sed explicit MachineBasicBlock(MachineFunction &mf, const BasicBlock *bb); 106193323Sed 107193323Sed ~MachineBasicBlock(); 108193323Sed 109193323Sed // MachineBasicBlocks are allocated and owned by MachineFunction. 110193323Sed friend class MachineFunction; 111193323Sed 112193323Sedpublic: 113193323Sed /// getBasicBlock - Return the LLVM basic block that this instance 114199989Srdivacky /// corresponded to originally. Note that this may be NULL if this instance 115199989Srdivacky /// does not correspond directly to an LLVM basic block. 116193323Sed /// 117193323Sed const BasicBlock *getBasicBlock() const { return BB; } 118193323Sed 119199989Srdivacky /// getName - Return the name of the corresponding LLVM basic block, or 120199989Srdivacky /// "(null)". 121199989Srdivacky StringRef getName() const; 122199989Srdivacky 123234353Sdim /// getFullName - Return a formatted string to identify this block and its 124234353Sdim /// parent function. 125234353Sdim std::string getFullName() const; 126234353Sdim 127198892Srdivacky /// hasAddressTaken - Test whether this block is potentially the target 128198892Srdivacky /// of an indirect branch. 129198892Srdivacky bool hasAddressTaken() const { return AddressTaken; } 130198892Srdivacky 131198892Srdivacky /// setHasAddressTaken - Set this block to reflect that it potentially 132198892Srdivacky /// is the target of an indirect branch. 133198892Srdivacky void setHasAddressTaken() { AddressTaken = true; } 134198892Srdivacky 135193323Sed /// getParent - Return the MachineFunction containing this basic block. 136193323Sed /// 137193323Sed const MachineFunction *getParent() const { return xParent; } 138193323Sed MachineFunction *getParent() { return xParent; } 139193323Sed 140193323Sed 141234353Sdim /// bundle_iterator - MachineBasicBlock iterator that automatically skips over 142234353Sdim /// MIs that are inside bundles (i.e. walk top level MIs only). 143234353Sdim template<typename Ty, typename IterTy> 144234353Sdim class bundle_iterator 145234353Sdim : public std::iterator<std::bidirectional_iterator_tag, Ty, ptrdiff_t> { 146234353Sdim IterTy MII; 147234353Sdim 148234353Sdim public: 149239462Sdim bundle_iterator(IterTy mii) : MII(mii) {} 150234353Sdim 151234353Sdim bundle_iterator(Ty &mi) : MII(mi) { 152249423Sdim assert(!mi.isBundledWithPred() && 153234353Sdim "It's not legal to initialize bundle_iterator with a bundled MI"); 154234353Sdim } 155234353Sdim bundle_iterator(Ty *mi) : MII(mi) { 156249423Sdim assert((!mi || !mi->isBundledWithPred()) && 157234353Sdim "It's not legal to initialize bundle_iterator with a bundled MI"); 158234353Sdim } 159239462Sdim // Template allows conversion from const to nonconst. 160239462Sdim template<class OtherTy, class OtherIterTy> 161239462Sdim bundle_iterator(const bundle_iterator<OtherTy, OtherIterTy> &I) 162239462Sdim : MII(I.getInstrIterator()) {} 163234353Sdim bundle_iterator() : MII(0) {} 164234353Sdim 165234353Sdim Ty &operator*() const { return *MII; } 166234353Sdim Ty *operator->() const { return &operator*(); } 167234353Sdim 168234353Sdim operator Ty*() const { return MII; } 169234353Sdim 170234353Sdim bool operator==(const bundle_iterator &x) const { 171234353Sdim return MII == x.MII; 172234353Sdim } 173234353Sdim bool operator!=(const bundle_iterator &x) const { 174234353Sdim return !operator==(x); 175234353Sdim } 176234353Sdim 177234353Sdim // Increment and decrement operators... 178234353Sdim bundle_iterator &operator--() { // predecrement - Back up 179239462Sdim do --MII; 180249423Sdim while (MII->isBundledWithPred()); 181234353Sdim return *this; 182234353Sdim } 183234353Sdim bundle_iterator &operator++() { // preincrement - Advance 184249423Sdim while (MII->isBundledWithSucc()) 185249423Sdim ++MII; 186249423Sdim ++MII; 187234353Sdim return *this; 188234353Sdim } 189234353Sdim bundle_iterator operator--(int) { // postdecrement operators... 190234353Sdim bundle_iterator tmp = *this; 191239462Sdim --*this; 192234353Sdim return tmp; 193234353Sdim } 194234353Sdim bundle_iterator operator++(int) { // postincrement operators... 195234353Sdim bundle_iterator tmp = *this; 196239462Sdim ++*this; 197234353Sdim return tmp; 198234353Sdim } 199234353Sdim 200234353Sdim IterTy getInstrIterator() const { 201234353Sdim return MII; 202234353Sdim } 203234353Sdim }; 204234353Sdim 205234353Sdim typedef Instructions::iterator instr_iterator; 206234353Sdim typedef Instructions::const_iterator const_instr_iterator; 207234353Sdim typedef std::reverse_iterator<instr_iterator> reverse_instr_iterator; 208234353Sdim typedef 209234353Sdim std::reverse_iterator<const_instr_iterator> const_reverse_instr_iterator; 210234353Sdim 211234353Sdim typedef 212234353Sdim bundle_iterator<MachineInstr,instr_iterator> iterator; 213234353Sdim typedef 214234353Sdim bundle_iterator<const MachineInstr,const_instr_iterator> const_iterator; 215234353Sdim typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 216234353Sdim typedef std::reverse_iterator<iterator> reverse_iterator; 217234353Sdim 218234353Sdim 219193323Sed unsigned size() const { return (unsigned)Insts.size(); } 220193323Sed bool empty() const { return Insts.empty(); } 221193323Sed 222193323Sed MachineInstr& front() { return Insts.front(); } 223193323Sed MachineInstr& back() { return Insts.back(); } 224193323Sed const MachineInstr& front() const { return Insts.front(); } 225193323Sed const MachineInstr& back() const { return Insts.back(); } 226193323Sed 227234353Sdim instr_iterator instr_begin() { return Insts.begin(); } 228234353Sdim const_instr_iterator instr_begin() const { return Insts.begin(); } 229234353Sdim instr_iterator instr_end() { return Insts.end(); } 230234353Sdim const_instr_iterator instr_end() const { return Insts.end(); } 231234353Sdim reverse_instr_iterator instr_rbegin() { return Insts.rbegin(); } 232234353Sdim const_reverse_instr_iterator instr_rbegin() const { return Insts.rbegin(); } 233234353Sdim reverse_instr_iterator instr_rend () { return Insts.rend(); } 234234353Sdim const_reverse_instr_iterator instr_rend () const { return Insts.rend(); } 235234353Sdim 236239462Sdim iterator begin() { return instr_begin(); } 237239462Sdim const_iterator begin() const { return instr_begin(); } 238239462Sdim iterator end () { return instr_end(); } 239239462Sdim const_iterator end () const { return instr_end(); } 240239462Sdim reverse_iterator rbegin() { return instr_rbegin(); } 241239462Sdim const_reverse_iterator rbegin() const { return instr_rbegin(); } 242239462Sdim reverse_iterator rend () { return instr_rend(); } 243239462Sdim const_reverse_iterator rend () const { return instr_rend(); } 244193323Sed 245234353Sdim 246193323Sed // Machine-CFG iterators 247193323Sed typedef std::vector<MachineBasicBlock *>::iterator pred_iterator; 248193323Sed typedef std::vector<MachineBasicBlock *>::const_iterator const_pred_iterator; 249193323Sed typedef std::vector<MachineBasicBlock *>::iterator succ_iterator; 250193323Sed typedef std::vector<MachineBasicBlock *>::const_iterator const_succ_iterator; 251193323Sed typedef std::vector<MachineBasicBlock *>::reverse_iterator 252193323Sed pred_reverse_iterator; 253193323Sed typedef std::vector<MachineBasicBlock *>::const_reverse_iterator 254193323Sed const_pred_reverse_iterator; 255193323Sed typedef std::vector<MachineBasicBlock *>::reverse_iterator 256193323Sed succ_reverse_iterator; 257193323Sed typedef std::vector<MachineBasicBlock *>::const_reverse_iterator 258193323Sed const_succ_reverse_iterator; 259193323Sed 260193323Sed pred_iterator pred_begin() { return Predecessors.begin(); } 261193323Sed const_pred_iterator pred_begin() const { return Predecessors.begin(); } 262193323Sed pred_iterator pred_end() { return Predecessors.end(); } 263193323Sed const_pred_iterator pred_end() const { return Predecessors.end(); } 264193323Sed pred_reverse_iterator pred_rbegin() 265193323Sed { return Predecessors.rbegin();} 266193323Sed const_pred_reverse_iterator pred_rbegin() const 267193323Sed { return Predecessors.rbegin();} 268193323Sed pred_reverse_iterator pred_rend() 269193323Sed { return Predecessors.rend(); } 270193323Sed const_pred_reverse_iterator pred_rend() const 271193323Sed { return Predecessors.rend(); } 272193323Sed unsigned pred_size() const { 273193323Sed return (unsigned)Predecessors.size(); 274193323Sed } 275193323Sed bool pred_empty() const { return Predecessors.empty(); } 276193323Sed succ_iterator succ_begin() { return Successors.begin(); } 277193323Sed const_succ_iterator succ_begin() const { return Successors.begin(); } 278193323Sed succ_iterator succ_end() { return Successors.end(); } 279193323Sed const_succ_iterator succ_end() const { return Successors.end(); } 280193323Sed succ_reverse_iterator succ_rbegin() 281193323Sed { return Successors.rbegin(); } 282193323Sed const_succ_reverse_iterator succ_rbegin() const 283193323Sed { return Successors.rbegin(); } 284193323Sed succ_reverse_iterator succ_rend() 285193323Sed { return Successors.rend(); } 286193323Sed const_succ_reverse_iterator succ_rend() const 287193323Sed { return Successors.rend(); } 288193323Sed unsigned succ_size() const { 289193323Sed return (unsigned)Successors.size(); 290193323Sed } 291193323Sed bool succ_empty() const { return Successors.empty(); } 292193323Sed 293193323Sed // LiveIn management methods. 294193323Sed 295193323Sed /// addLiveIn - Add the specified register as a live in. Note that it 296193323Sed /// is an error to add the same register to the same set more than once. 297193323Sed void addLiveIn(unsigned Reg) { LiveIns.push_back(Reg); } 298193323Sed 299252720Sdim /// Add PhysReg as live in to this block, and ensure that there is a copy of 300252720Sdim /// PhysReg to a virtual register of class RC. Return the virtual register 301252720Sdim /// that is a copy of the live in PhysReg. 302252720Sdim unsigned addLiveIn(unsigned PhysReg, const TargetRegisterClass *RC); 303252720Sdim 304193323Sed /// removeLiveIn - Remove the specified register from the live in set. 305193323Sed /// 306193323Sed void removeLiveIn(unsigned Reg); 307193323Sed 308193323Sed /// isLiveIn - Return true if the specified register is in the live in set. 309193323Sed /// 310193323Sed bool isLiveIn(unsigned Reg) const; 311193323Sed 312193323Sed // Iteration support for live in sets. These sets are kept in sorted 313193323Sed // order by their register number. 314207618Srdivacky typedef std::vector<unsigned>::const_iterator livein_iterator; 315207618Srdivacky livein_iterator livein_begin() const { return LiveIns.begin(); } 316207618Srdivacky livein_iterator livein_end() const { return LiveIns.end(); } 317193323Sed bool livein_empty() const { return LiveIns.empty(); } 318193323Sed 319193323Sed /// getAlignment - Return alignment of the basic block. 320234353Sdim /// The alignment is specified as log2(bytes). 321193323Sed /// 322193323Sed unsigned getAlignment() const { return Alignment; } 323193323Sed 324193323Sed /// setAlignment - Set alignment of the basic block. 325234353Sdim /// The alignment is specified as log2(bytes). 326193323Sed /// 327193323Sed void setAlignment(unsigned Align) { Alignment = Align; } 328193323Sed 329193323Sed /// isLandingPad - Returns true if the block is a landing pad. That is 330193323Sed /// this basic block is entered via an exception handler. 331193323Sed bool isLandingPad() const { return IsLandingPad; } 332193323Sed 333193323Sed /// setIsLandingPad - Indicates the block is a landing pad. That is 334193323Sed /// this basic block is entered via an exception handler. 335226633Sdim void setIsLandingPad(bool V = true) { IsLandingPad = V; } 336193323Sed 337218893Sdim /// getLandingPadSuccessor - If this block has a successor that is a landing 338218893Sdim /// pad, return it. Otherwise return NULL. 339218893Sdim const MachineBasicBlock *getLandingPadSuccessor() const; 340218893Sdim 341193323Sed // Code Layout methods. 342234353Sdim 343193323Sed /// moveBefore/moveAfter - move 'this' block before or after the specified 344193323Sed /// block. This only moves the block, it does not modify the CFG or adjust 345193323Sed /// potential fall-throughs at the end of the block. 346193323Sed void moveBefore(MachineBasicBlock *NewAfter); 347193323Sed void moveAfter(MachineBasicBlock *NewBefore); 348199481Srdivacky 349199481Srdivacky /// updateTerminator - Update the terminator instructions in block to account 350199481Srdivacky /// for changes to the layout. If the block previously used a fallthrough, 351199481Srdivacky /// it may now need a branch, and if it previously used branching it may now 352199481Srdivacky /// be able to use a fallthrough. 353199481Srdivacky void updateTerminator(); 354199481Srdivacky 355193323Sed // Machine-CFG mutators 356224145Sdim 357193323Sed /// addSuccessor - Add succ as a successor of this MachineBasicBlock. 358224145Sdim /// The Predecessors list of succ is automatically updated. WEIGHT 359224145Sdim /// parameter is stored in Weights list and it may be used by 360224145Sdim /// MachineBranchProbabilityInfo analysis to calculate branch probability. 361193323Sed /// 362243830Sdim /// Note that duplicate Machine CFG edges are not allowed. 363243830Sdim /// 364224145Sdim void addSuccessor(MachineBasicBlock *succ, uint32_t weight = 0); 365193323Sed 366193323Sed /// removeSuccessor - Remove successor from the successors list of this 367193323Sed /// MachineBasicBlock. The Predecessors list of succ is automatically updated. 368193323Sed /// 369193323Sed void removeSuccessor(MachineBasicBlock *succ); 370193323Sed 371193323Sed /// removeSuccessor - Remove specified successor from the successors list of 372193323Sed /// this MachineBasicBlock. The Predecessors list of succ is automatically 373193323Sed /// updated. Return the iterator to the element after the one removed. 374193323Sed /// 375193323Sed succ_iterator removeSuccessor(succ_iterator I); 376224145Sdim 377224145Sdim /// replaceSuccessor - Replace successor OLD with NEW and update weight info. 378224145Sdim /// 379224145Sdim void replaceSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New); 380224145Sdim 381224145Sdim 382193323Sed /// transferSuccessors - Transfers all the successors from MBB to this 383193323Sed /// machine basic block (i.e., copies all the successors fromMBB and 384199481Srdivacky /// remove all the successors from fromMBB). 385193323Sed void transferSuccessors(MachineBasicBlock *fromMBB); 386210299Sed 387210299Sed /// transferSuccessorsAndUpdatePHIs - Transfers all the successors, as 388210299Sed /// in transferSuccessors, and update PHI operands in the successor blocks 389210299Sed /// which refer to fromMBB to refer to this. 390210299Sed void transferSuccessorsAndUpdatePHIs(MachineBasicBlock *fromMBB); 391234353Sdim 392239462Sdim /// isPredecessor - Return true if the specified MBB is a predecessor of this 393239462Sdim /// block. 394239462Sdim bool isPredecessor(const MachineBasicBlock *MBB) const; 395239462Sdim 396193323Sed /// isSuccessor - Return true if the specified MBB is a successor of this 397193323Sed /// block. 398193323Sed bool isSuccessor(const MachineBasicBlock *MBB) const; 399193323Sed 400193323Sed /// isLayoutSuccessor - Return true if the specified MBB will be emitted 401193323Sed /// immediately after this block, such that if this block exits by 402193323Sed /// falling through, control will transfer to the specified MBB. Note 403193323Sed /// that MBB need not be a successor at all, for example if this block 404193323Sed /// ends with an unconditional branch to some other block. 405193323Sed bool isLayoutSuccessor(const MachineBasicBlock *MBB) const; 406193323Sed 407199989Srdivacky /// canFallThrough - Return true if the block can implicitly transfer 408199989Srdivacky /// control to the block after it by falling off the end of it. This should 409199989Srdivacky /// return false if it can reach the block after it, but it uses an explicit 410199989Srdivacky /// branch to do so (e.g., a table jump). True is a conservative answer. 411199989Srdivacky bool canFallThrough(); 412199989Srdivacky 413234353Sdim /// Returns a pointer to the first instructon in this block that is not a 414210299Sed /// PHINode instruction. When adding instruction to the beginning of the 415210299Sed /// basic block, they should be added before the returned value, not before 416210299Sed /// the first instruction, which might be PHI. 417210299Sed /// Returns end() is there's no non-PHI instruction. 418210299Sed iterator getFirstNonPHI(); 419210299Sed 420218893Sdim /// SkipPHIsAndLabels - Return the first instruction in MBB after I that is 421218893Sdim /// not a PHI or a label. This is the correct point to insert copies at the 422218893Sdim /// beginning of a basic block. 423218893Sdim iterator SkipPHIsAndLabels(iterator I); 424218893Sdim 425193323Sed /// getFirstTerminator - returns an iterator to the first terminator 426193323Sed /// instruction of this basic block. If a terminator does not exist, 427193323Sed /// it returns end() 428193323Sed iterator getFirstTerminator(); 429234353Sdim const_iterator getFirstTerminator() const; 430193323Sed 431234353Sdim /// getFirstInstrTerminator - Same getFirstTerminator but it ignores bundles 432234353Sdim /// and return an instr_iterator instead. 433234353Sdim instr_iterator getFirstInstrTerminator(); 434221345Sdim 435218893Sdim /// getLastNonDebugInstr - returns an iterator to the last non-debug 436218893Sdim /// instruction in the basic block, or end() 437218893Sdim iterator getLastNonDebugInstr(); 438234353Sdim const_iterator getLastNonDebugInstr() const; 439218893Sdim 440210299Sed /// SplitCriticalEdge - Split the critical edge from this block to the 441210299Sed /// given successor block, and return the newly created block, or null 442210299Sed /// if splitting is not possible. 443210299Sed /// 444210299Sed /// This function updates LiveVariables, MachineDominatorTree, and 445210299Sed /// MachineLoopInfo, as applicable. 446210299Sed MachineBasicBlock *SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P); 447210299Sed 448193323Sed void pop_front() { Insts.pop_front(); } 449193323Sed void pop_back() { Insts.pop_back(); } 450193323Sed void push_back(MachineInstr *MI) { Insts.push_back(MI); } 451234353Sdim 452249423Sdim /// Insert MI into the instruction list before I, possibly inside a bundle. 453249423Sdim /// 454249423Sdim /// If the insertion point is inside a bundle, MI will be added to the bundle, 455249423Sdim /// otherwise MI will not be added to any bundle. That means this function 456249423Sdim /// alone can't be used to prepend or append instructions to bundles. See 457249423Sdim /// MIBundleBuilder::insert() for a more reliable way of doing that. 458249423Sdim instr_iterator insert(instr_iterator I, MachineInstr *M); 459193323Sed 460249423Sdim /// Insert a range of instructions into the instruction list before I. 461234353Sdim template<typename IT> 462234353Sdim void insert(iterator I, IT S, IT E) { 463234353Sdim Insts.insert(I.getInstrIterator(), S, E); 464234353Sdim } 465249423Sdim 466249423Sdim /// Insert MI into the instruction list before I. 467249423Sdim iterator insert(iterator I, MachineInstr *MI) { 468249423Sdim assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() && 469249423Sdim "Cannot insert instruction with bundle flags"); 470249423Sdim return Insts.insert(I.getInstrIterator(), MI); 471234353Sdim } 472249423Sdim 473249423Sdim /// Insert MI into the instruction list after I. 474249423Sdim iterator insertAfter(iterator I, MachineInstr *MI) { 475249423Sdim assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() && 476249423Sdim "Cannot insert instruction with bundle flags"); 477249423Sdim return Insts.insertAfter(I.getInstrIterator(), MI); 478234353Sdim } 479193323Sed 480249423Sdim /// Remove an instruction from the instruction list and delete it. 481234353Sdim /// 482249423Sdim /// If the instruction is part of a bundle, the other instructions in the 483249423Sdim /// bundle will still be bundled after removing the single instruction. 484249423Sdim instr_iterator erase(instr_iterator I); 485249423Sdim 486249423Sdim /// Remove an instruction from the instruction list and delete it. 487249423Sdim /// 488249423Sdim /// If the instruction is part of a bundle, the other instructions in the 489249423Sdim /// bundle will still be bundled after removing the single instruction. 490234353Sdim instr_iterator erase_instr(MachineInstr *I) { 491249423Sdim return erase(instr_iterator(I)); 492234353Sdim } 493234353Sdim 494249423Sdim /// Remove a range of instructions from the instruction list and delete them. 495234353Sdim iterator erase(iterator I, iterator E) { 496234353Sdim return Insts.erase(I.getInstrIterator(), E.getInstrIterator()); 497234353Sdim } 498249423Sdim 499249423Sdim /// Remove an instruction or bundle from the instruction list and delete it. 500249423Sdim /// 501249423Sdim /// If I points to a bundle of instructions, they are all erased. 502249423Sdim iterator erase(iterator I) { 503249423Sdim return erase(I, llvm::next(I)); 504249423Sdim } 505249423Sdim 506249423Sdim /// Remove an instruction from the instruction list and delete it. 507249423Sdim /// 508249423Sdim /// If I is the head of a bundle of instructions, the whole bundle will be 509249423Sdim /// erased. 510234353Sdim iterator erase(MachineInstr *I) { 511249423Sdim return erase(iterator(I)); 512234353Sdim } 513234353Sdim 514249423Sdim /// Remove the unbundled instruction from the instruction list without 515249423Sdim /// deleting it. 516249423Sdim /// 517249423Sdim /// This function can not be used to remove bundled instructions, use 518249423Sdim /// remove_instr to remove individual instructions from a bundle. 519249423Sdim MachineInstr *remove(MachineInstr *I) { 520249423Sdim assert(!I->isBundled() && "Cannot remove bundled instructions"); 521249423Sdim return Insts.remove(I); 522249423Sdim } 523249423Sdim 524249423Sdim /// Remove the possibly bundled instruction from the instruction list 525249423Sdim /// without deleting it. 526249423Sdim /// 527249423Sdim /// If the instruction is part of a bundle, the other instructions in the 528249423Sdim /// bundle will still be bundled after removing the single instruction. 529249423Sdim MachineInstr *remove_instr(MachineInstr *I); 530249423Sdim 531234353Sdim void clear() { 532234353Sdim Insts.clear(); 533234353Sdim } 534234353Sdim 535249423Sdim /// Take an instruction from MBB 'Other' at the position From, and insert it 536249423Sdim /// into this MBB right before 'Where'. 537249423Sdim /// 538249423Sdim /// If From points to a bundle of instructions, the whole bundle is moved. 539249423Sdim void splice(iterator Where, MachineBasicBlock *Other, iterator From) { 540249423Sdim // The range splice() doesn't allow noop moves, but this one does. 541249423Sdim if (Where != From) 542249423Sdim splice(Where, Other, From, llvm::next(From)); 543193323Sed } 544193323Sed 545249423Sdim /// Take a block of instructions from MBB 'Other' in the range [From, To), 546249423Sdim /// and insert them into this MBB right before 'Where'. 547249423Sdim /// 548249423Sdim /// The instruction at 'Where' must not be included in the range of 549249423Sdim /// instructions to move. 550249423Sdim void splice(iterator Where, MachineBasicBlock *Other, 551249423Sdim iterator From, iterator To) { 552249423Sdim Insts.splice(Where.getInstrIterator(), Other->Insts, 553234353Sdim From.getInstrIterator(), To.getInstrIterator()); 554193323Sed } 555193323Sed 556193323Sed /// removeFromParent - This method unlinks 'this' from the containing 557193323Sed /// function, and returns it, but does not delete it. 558193323Sed MachineBasicBlock *removeFromParent(); 559234353Sdim 560193323Sed /// eraseFromParent - This method unlinks 'this' from the containing 561193323Sed /// function and deletes it. 562193323Sed void eraseFromParent(); 563193323Sed 564193323Sed /// ReplaceUsesOfBlockWith - Given a machine basic block that branched to 565193323Sed /// 'Old', change the code and CFG so that it branches to 'New' instead. 566193323Sed void ReplaceUsesOfBlockWith(MachineBasicBlock *Old, MachineBasicBlock *New); 567193323Sed 568193323Sed /// CorrectExtraCFGEdges - Various pieces of code can cause excess edges in 569193323Sed /// the CFG to be inserted. If we have proven that MBB can only branch to 570193323Sed /// DestA and DestB, remove any other MBB successors from the CFG. DestA and 571193323Sed /// DestB can be null. Besides DestA and DestB, retain other edges leading 572193323Sed /// to LandingPads (currently there can be only one; we don't check or require 573193323Sed /// that here). Note it is possible that DestA and/or DestB are LandingPads. 574193323Sed bool CorrectExtraCFGEdges(MachineBasicBlock *DestA, 575193323Sed MachineBasicBlock *DestB, 576193323Sed bool isCond); 577193323Sed 578202878Srdivacky /// findDebugLoc - find the next valid DebugLoc starting at MBBI, skipping 579203954Srdivacky /// any DBG_VALUE instructions. Return UnknownLoc if there is none. 580234353Sdim DebugLoc findDebugLoc(instr_iterator MBBI); 581234353Sdim DebugLoc findDebugLoc(iterator MBBI) { 582234353Sdim return findDebugLoc(MBBI.getInstrIterator()); 583234353Sdim } 584202878Srdivacky 585243830Sdim /// Possible outcome of a register liveness query to computeRegisterLiveness() 586243830Sdim enum LivenessQueryResult { 587243830Sdim LQR_Live, ///< Register is known to be live. 588243830Sdim LQR_OverlappingLive, ///< Register itself is not live, but some overlapping 589243830Sdim ///< register is. 590243830Sdim LQR_Dead, ///< Register is known to be dead. 591243830Sdim LQR_Unknown ///< Register liveness not decidable from local 592243830Sdim ///< neighborhood. 593243830Sdim }; 594243830Sdim 595243830Sdim /// computeRegisterLiveness - Return whether (physical) register \c Reg 596243830Sdim /// has been <def>ined and not <kill>ed as of just before \c MI. 597243830Sdim /// 598243830Sdim /// Search is localised to a neighborhood of 599243830Sdim /// \c Neighborhood instructions before (searching for defs or kills) and 600243830Sdim /// Neighborhood instructions after (searching just for defs) MI. 601243830Sdim /// 602243830Sdim /// \c Reg must be a physical register. 603243830Sdim LivenessQueryResult computeRegisterLiveness(const TargetRegisterInfo *TRI, 604243830Sdim unsigned Reg, MachineInstr *MI, 605243830Sdim unsigned Neighborhood=10); 606243830Sdim 607193323Sed // Debugging methods. 608193323Sed void dump() const; 609218893Sdim void print(raw_ostream &OS, SlotIndexes* = 0) const; 610193323Sed 611193323Sed /// getNumber - MachineBasicBlocks are uniquely numbered at the function 612193323Sed /// level, unless they're not in a MachineFunction yet, in which case this 613193323Sed /// will return -1. 614193323Sed /// 615193323Sed int getNumber() const { return Number; } 616193323Sed void setNumber(int N) { Number = N; } 617193323Sed 618203954Srdivacky /// getSymbol - Return the MCSymbol for this basic block. 619203954Srdivacky /// 620205218Srdivacky MCSymbol *getSymbol() const; 621224145Sdim 622224145Sdim 623224145Sdimprivate: 624224145Sdim /// getWeightIterator - Return weight iterator corresponding to the I 625224145Sdim /// successor iterator. 626224145Sdim weight_iterator getWeightIterator(succ_iterator I); 627234353Sdim const_weight_iterator getWeightIterator(const_succ_iterator I) const; 628224145Sdim 629224145Sdim friend class MachineBranchProbabilityInfo; 630224145Sdim 631224145Sdim /// getSuccWeight - Return weight of the edge from this block to MBB. This 632224145Sdim /// method should NOT be called directly, but by using getEdgeWeight method 633224145Sdim /// from MachineBranchProbabilityInfo class. 634243830Sdim uint32_t getSuccWeight(const_succ_iterator Succ) const; 635224145Sdim 636224145Sdim 637224145Sdim // Methods used to maintain doubly linked list of blocks... 638193323Sed friend struct ilist_traits<MachineBasicBlock>; 639193323Sed 640193323Sed // Machine-CFG mutators 641193323Sed 642193323Sed /// addPredecessor - Remove pred as a predecessor of this MachineBasicBlock. 643193323Sed /// Don't do this unless you know what you're doing, because it doesn't 644193323Sed /// update pred's successors list. Use pred->addSuccessor instead. 645193323Sed /// 646193323Sed void addPredecessor(MachineBasicBlock *pred); 647193323Sed 648193323Sed /// removePredecessor - Remove pred as a predecessor of this 649193323Sed /// MachineBasicBlock. Don't do this unless you know what you're 650193323Sed /// doing, because it doesn't update pred's successors list. Use 651193323Sed /// pred->removeSuccessor instead. 652193323Sed /// 653193323Sed void removePredecessor(MachineBasicBlock *pred); 654193323Sed}; 655193323Sed 656198090Srdivackyraw_ostream& operator<<(raw_ostream &OS, const MachineBasicBlock &MBB); 657193323Sed 658199481Srdivackyvoid WriteAsOperand(raw_ostream &, const MachineBasicBlock*, bool t); 659199481Srdivacky 660221345Sdim// This is useful when building IndexedMaps keyed on basic block pointers. 661221345Sdimstruct MBB2NumberFunctor : 662221345Sdim public std::unary_function<const MachineBasicBlock*, unsigned> { 663221345Sdim unsigned operator()(const MachineBasicBlock *MBB) const { 664221345Sdim return MBB->getNumber(); 665221345Sdim } 666221345Sdim}; 667221345Sdim 668193323Sed//===--------------------------------------------------------------------===// 669193323Sed// GraphTraits specializations for machine basic block graphs (machine-CFGs) 670193323Sed//===--------------------------------------------------------------------===// 671193323Sed 672193323Sed// Provide specializations of GraphTraits to be able to treat a 673193323Sed// MachineFunction as a graph of MachineBasicBlocks... 674193323Sed// 675193323Sed 676193323Sedtemplate <> struct GraphTraits<MachineBasicBlock *> { 677193323Sed typedef MachineBasicBlock NodeType; 678193323Sed typedef MachineBasicBlock::succ_iterator ChildIteratorType; 679193323Sed 680193323Sed static NodeType *getEntryNode(MachineBasicBlock *BB) { return BB; } 681193323Sed static inline ChildIteratorType child_begin(NodeType *N) { 682193323Sed return N->succ_begin(); 683193323Sed } 684193323Sed static inline ChildIteratorType child_end(NodeType *N) { 685193323Sed return N->succ_end(); 686193323Sed } 687193323Sed}; 688193323Sed 689193323Sedtemplate <> struct GraphTraits<const MachineBasicBlock *> { 690193323Sed typedef const MachineBasicBlock NodeType; 691193323Sed typedef MachineBasicBlock::const_succ_iterator ChildIteratorType; 692193323Sed 693193323Sed static NodeType *getEntryNode(const MachineBasicBlock *BB) { return BB; } 694193323Sed static inline ChildIteratorType child_begin(NodeType *N) { 695193323Sed return N->succ_begin(); 696193323Sed } 697193323Sed static inline ChildIteratorType child_end(NodeType *N) { 698193323Sed return N->succ_end(); 699193323Sed } 700193323Sed}; 701193323Sed 702193323Sed// Provide specializations of GraphTraits to be able to treat a 703193323Sed// MachineFunction as a graph of MachineBasicBlocks... and to walk it 704193323Sed// in inverse order. Inverse order for a function is considered 705193323Sed// to be when traversing the predecessor edges of a MBB 706193323Sed// instead of the successor edges. 707193323Sed// 708193323Sedtemplate <> struct GraphTraits<Inverse<MachineBasicBlock*> > { 709193323Sed typedef MachineBasicBlock NodeType; 710193323Sed typedef MachineBasicBlock::pred_iterator ChildIteratorType; 711193323Sed static NodeType *getEntryNode(Inverse<MachineBasicBlock *> G) { 712193323Sed return G.Graph; 713193323Sed } 714193323Sed static inline ChildIteratorType child_begin(NodeType *N) { 715193323Sed return N->pred_begin(); 716193323Sed } 717193323Sed static inline ChildIteratorType child_end(NodeType *N) { 718193323Sed return N->pred_end(); 719193323Sed } 720193323Sed}; 721193323Sed 722193323Sedtemplate <> struct GraphTraits<Inverse<const MachineBasicBlock*> > { 723193323Sed typedef const MachineBasicBlock NodeType; 724193323Sed typedef MachineBasicBlock::const_pred_iterator ChildIteratorType; 725193323Sed static NodeType *getEntryNode(Inverse<const MachineBasicBlock*> G) { 726193323Sed return G.Graph; 727193323Sed } 728193323Sed static inline ChildIteratorType child_begin(NodeType *N) { 729193323Sed return N->pred_begin(); 730193323Sed } 731193323Sed static inline ChildIteratorType child_end(NodeType *N) { 732193323Sed return N->pred_end(); 733193323Sed } 734193323Sed}; 735193323Sed 736193323Sed} // End llvm namespace 737193323Sed 738193323Sed#endif 739