MachineBasicBlock.h revision 288943
1139749Simp//===-- llvm/CodeGen/MachineBasicBlock.h ------------------------*- C++ -*-===// 278346Sbenno// 378346Sbenno// The LLVM Compiler Infrastructure 478346Sbenno// 578346Sbenno// This file is distributed under the University of Illinois Open Source 678346Sbenno// License. See LICENSE.TXT for details. 778346Sbenno// 878346Sbenno//===----------------------------------------------------------------------===// 978346Sbenno// 1078346Sbenno// Collect the sequence of machine instructions for a basic block. 1178346Sbenno// 1278346Sbenno//===----------------------------------------------------------------------===// 1378346Sbenno 1478346Sbenno#ifndef LLVM_CODEGEN_MACHINEBASICBLOCK_H 1578346Sbenno#define LLVM_CODEGEN_MACHINEBASICBLOCK_H 1678346Sbenno 1778346Sbenno#include "llvm/ADT/GraphTraits.h" 1878346Sbenno#include "llvm/CodeGen/MachineInstr.h" 1978346Sbenno#include "llvm/Support/DataTypes.h" 2078346Sbenno#include <functional> 2178346Sbenno 2278346Sbennonamespace llvm { 2378346Sbenno 2478346Sbennoclass Pass; 2578346Sbennoclass BasicBlock; 26113038Sobrienclass MachineFunction; 27113038Sobrienclass MCSymbol; 2878346Sbennoclass SlotIndexes; 29131016Sobrienclass StringRef; 30110509Sharticlass raw_ostream; 3178346Sbennoclass MachineBranchProbabilityInfo; 32131916Smarcel 3378346Sbennotemplate <> 34164049Srwatsonstruct ilist_traits<MachineInstr> : public ilist_default_traits<MachineInstr> { 3578346Sbennoprivate: 3678346Sbenno mutable ilist_half_node<MachineInstr> Sentinel; 3778346Sbenno 3878346Sbenno // this is only set by the MachineBasicBlock owning the LiveList 3978346Sbenno friend class MachineBasicBlock; 4078346Sbenno MachineBasicBlock* Parent; 4178346Sbenno 4278346Sbennopublic: 4378346Sbenno MachineInstr *createSentinel() const { 44110509Sharti return static_cast<MachineInstr*>(&Sentinel); 45110509Sharti } 46131016Sobrien void destroySentinel(MachineInstr *) const {} 47131016Sobrien 48131016Sobrien MachineInstr *provideInitialHead() const { return createSentinel(); } 49131016Sobrien MachineInstr *ensureHead(MachineInstr*) const { return createSentinel(); } 5078346Sbenno static void noteHead(MachineInstr*, MachineInstr*) {} 51181905Sed 52181905Sed void addNodeToList(MachineInstr* N); 53181905Sed void removeNodeFromList(MachineInstr* N); 5478346Sbenno void transferNodesFromList(ilist_traits &SrcTraits, 55181905Sed ilist_iterator<MachineInstr> first, 56181905Sed ilist_iterator<MachineInstr> last); 57181905Sed void deleteNode(MachineInstr *N); 58181905Sedprivate: 59181905Sed void createNode(const MachineInstr &); 6078346Sbenno}; 6178346Sbenno 6278346Sbennoclass MachineBasicBlock : public ilist_node<MachineBasicBlock> { 6378346Sbenno typedef ilist<MachineInstr> Instructions; 6478346Sbenno Instructions Insts; 6578346Sbenno const BasicBlock *BB; 66225203Srwatson int Number; 67110509Sharti MachineFunction *xParent; 68110509Sharti 69110509Sharti /// Predecessors/Successors - Keep track of the predecessor / successor 7078346Sbenno /// basicblocks. 7178346Sbenno std::vector<MachineBasicBlock *> Predecessors; 72158964Sphk std::vector<MachineBasicBlock *> Successors; 73158964Sphk 74158964Sphk /// Weights - Keep track of the weights to the successors. This vector 75158964Sphk /// has the same order as Successors, or it is empty if we don't use it 76158964Sphk /// (disable optimization). 77228631Savg std::vector<uint32_t> Weights; 78228631Savg typedef std::vector<uint32_t>::iterator weight_iterator; 7978346Sbenno typedef std::vector<uint32_t>::const_iterator const_weight_iterator; 80159065Sphk 8178346Sbenno /// LiveIns - Keep track of the physical registers that are livein of 8289115Sjake /// the basicblock. 8389115Sjake std::vector<unsigned> LiveIns; 8489115Sjake 85107044Sjake /// Alignment - Alignment of the basic block. Zero if the basic block does 86107044Sjake /// not need to be aligned. 87181905Sed /// The alignment is specified as log2(bytes). 8889115Sjake unsigned Alignment; 89120544Sjake 90120544Sjake /// IsLandingPad - Indicate that this basic block is entered via an 91255424Snwhitehorn /// exception handler. 92255424Snwhitehorn bool IsLandingPad; 93255424Snwhitehorn 94255424Snwhitehorn /// AddressTaken - Indicate that this basic block is potentially the 95255424Snwhitehorn /// target of an indirect branch. 96255424Snwhitehorn bool AddressTaken; 97255424Snwhitehorn 98107044Sjake /// \brief since getSymbol is a relatively heavy-weight operation, the symbol 99107044Sjake /// is only computed once and is cached. 100107044Sjake mutable MCSymbol *CachedMCSymbol; 101107044Sjake 102255424Snwhitehorn // Intrusive list support 103255424Snwhitehorn MachineBasicBlock() {} 104107044Sjake 10589115Sjake explicit MachineBasicBlock(MachineFunction &mf, const BasicBlock *bb); 10689115Sjake 107177253Srwatson ~MachineBasicBlock(); 10889115Sjake 109265967Sian // MachineBasicBlocks are allocated and owned by MachineFunction. 110265967Sian friend class MachineFunction; 11178346Sbenno 11278346Sbennopublic: 113181905Sed /// getBasicBlock - Return the LLVM basic block that this instance 11478346Sbenno /// corresponded to originally. Note that this may be NULL if this instance 115181905Sed /// does not correspond directly to an LLVM basic block. 116181905Sed /// 117181905Sed const BasicBlock *getBasicBlock() const { return BB; } 11878346Sbenno 119181905Sed /// getName - Return the name of the corresponding LLVM basic block, or 12078346Sbenno /// "(null)". 121181905Sed StringRef getName() const; 12278346Sbenno 12378346Sbenno /// getFullName - Return a formatted string to identify this block and its 124181905Sed /// parent function. 125181905Sed std::string getFullName() const; 12678346Sbenno 12778346Sbenno /// hasAddressTaken - Test whether this block is potentially the target 128131016Sobrien /// of an indirect branch. 129131016Sobrien bool hasAddressTaken() const { return AddressTaken; } 13078346Sbenno 13178346Sbenno /// setHasAddressTaken - Set this block to reflect that it potentially 13278346Sbenno /// is the target of an indirect branch. 133181905Sed void setHasAddressTaken() { AddressTaken = true; } 13478346Sbenno 135131016Sobrien /// getParent - Return the MachineFunction containing this basic block. 136131016Sobrien /// 13778346Sbenno const MachineFunction *getParent() const { return xParent; } 138181905Sed MachineFunction *getParent() { return xParent; } 139181905Sed 140181905Sed 141181905Sed /// bundle_iterator - MachineBasicBlock iterator that automatically skips over 142181905Sed /// MIs that are inside bundles (i.e. walk top level MIs only). 14378346Sbenno template<typename Ty, typename IterTy> 14478346Sbenno class bundle_iterator 14578346Sbenno : public std::iterator<std::bidirectional_iterator_tag, Ty, ptrdiff_t> { 14678346Sbenno IterTy MII; 14778346Sbenno 14878346Sbenno public: 14978346Sbenno bundle_iterator(IterTy mii) : MII(mii) {} 15078346Sbenno 15178346Sbenno bundle_iterator(Ty &mi) : MII(mi) { 15278346Sbenno assert(!mi.isBundledWithPred() && 15378346Sbenno "It's not legal to initialize bundle_iterator with a bundled MI"); 154181905Sed } 155181905Sed bundle_iterator(Ty *mi) : MII(mi) { 156181905Sed assert((!mi || !mi->isBundledWithPred()) && 157181905Sed "It's not legal to initialize bundle_iterator with a bundled MI"); 158181905Sed } 15978346Sbenno // Template allows conversion from const to nonconst. 16078346Sbenno template<class OtherTy, class OtherIterTy> 16178346Sbenno bundle_iterator(const bundle_iterator<OtherTy, OtherIterTy> &I) 16278346Sbenno : MII(I.getInstrIterator()) {} 16378346Sbenno bundle_iterator() : MII(nullptr) {} 164159065Sphk 16578346Sbenno Ty &operator*() const { return *MII; } 16678346Sbenno Ty *operator->() const { return &operator*(); } 16778346Sbenno 16878346Sbenno operator Ty*() const { return MII; } 16978346Sbenno 17078346Sbenno bool operator==(const bundle_iterator &x) const { 17178346Sbenno return MII == x.MII; 17278346Sbenno } 173265967Sian bool operator!=(const bundle_iterator &x) const { 17478346Sbenno return !operator==(x); 17578346Sbenno } 17678346Sbenno 17778346Sbenno // Increment and decrement operators... 178265967Sian bundle_iterator &operator--() { // predecrement - Back up 17978346Sbenno do --MII; 18078346Sbenno while (MII->isBundledWithPred()); 18178346Sbenno return *this; 18278346Sbenno } 183120542Sjake bundle_iterator &operator++() { // preincrement - Advance 18478346Sbenno while (MII->isBundledWithSucc()) 18578346Sbenno ++MII; 18678346Sbenno ++MII; 187158964Sphk return *this; 18878346Sbenno } 18978346Sbenno bundle_iterator operator--(int) { // postdecrement operators... 190120467Sphk bundle_iterator tmp = *this; 191184329Sed --*this; 19278346Sbenno return tmp; 19378346Sbenno } 194158964Sphk bundle_iterator operator++(int) { // postincrement operators... 195159065Sphk bundle_iterator tmp = *this; 19678346Sbenno ++*this; 19778346Sbenno return tmp; 19878346Sbenno } 199228631Savg 200228631Savg IterTy getInstrIterator() const { 201228631Savg return MII; 202228631Savg } 203228631Savg }; 204228631Savg 205228631Savg typedef Instructions::iterator instr_iterator; 206228631Savg typedef Instructions::const_iterator const_instr_iterator; 207228631Savg typedef std::reverse_iterator<instr_iterator> reverse_instr_iterator; 208228631Savg typedef 20978346Sbenno std::reverse_iterator<const_instr_iterator> const_reverse_instr_iterator; 210158964Sphk 21178346Sbenno typedef 21278346Sbenno bundle_iterator<MachineInstr,instr_iterator> iterator; 21378346Sbenno typedef 21488792Sjake bundle_iterator<const MachineInstr,const_instr_iterator> const_iterator; 215225203Srwatson typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 216225203Srwatson typedef std::reverse_iterator<iterator> reverse_iterator; 217110509Sharti 21878346Sbenno 21978346Sbenno unsigned size() const { return (unsigned)Insts.size(); } 22078346Sbenno bool empty() const { return Insts.empty(); } 22178346Sbenno 22278346Sbenno MachineInstr &instr_front() { return Insts.front(); } 22378346Sbenno MachineInstr &instr_back() { return Insts.back(); } 22478346Sbenno const MachineInstr &instr_front() const { return Insts.front(); } 225158964Sphk const MachineInstr &instr_back() const { return Insts.back(); } 22678346Sbenno 22778346Sbenno MachineInstr &front() { return Insts.front(); } 22878346Sbenno MachineInstr &back() { return *--end(); } 22978346Sbenno const MachineInstr &front() const { return Insts.front(); } 23078346Sbenno const MachineInstr &back() const { return *--end(); } 23178346Sbenno 23278346Sbenno instr_iterator instr_begin() { return Insts.begin(); } 23378346Sbenno const_instr_iterator instr_begin() const { return Insts.begin(); } 23478346Sbenno instr_iterator instr_end() { return Insts.end(); } 23578346Sbenno const_instr_iterator instr_end() const { return Insts.end(); } 23678346Sbenno reverse_instr_iterator instr_rbegin() { return Insts.rbegin(); } 237 const_reverse_instr_iterator instr_rbegin() const { return Insts.rbegin(); } 238 reverse_instr_iterator instr_rend () { return Insts.rend(); } 239 const_reverse_instr_iterator instr_rend () const { return Insts.rend(); } 240 241 iterator begin() { return instr_begin(); } 242 const_iterator begin() const { return instr_begin(); } 243 iterator end () { return instr_end(); } 244 const_iterator end () const { return instr_end(); } 245 reverse_iterator rbegin() { return instr_rbegin(); } 246 const_reverse_iterator rbegin() const { return instr_rbegin(); } 247 reverse_iterator rend () { return instr_rend(); } 248 const_reverse_iterator rend () const { return instr_rend(); } 249 250 inline iterator_range<iterator> terminators() { 251 return iterator_range<iterator>(getFirstTerminator(), end()); 252 } 253 inline iterator_range<const_iterator> terminators() const { 254 return iterator_range<const_iterator>(getFirstTerminator(), end()); 255 } 256 257 // Machine-CFG iterators 258 typedef std::vector<MachineBasicBlock *>::iterator pred_iterator; 259 typedef std::vector<MachineBasicBlock *>::const_iterator const_pred_iterator; 260 typedef std::vector<MachineBasicBlock *>::iterator succ_iterator; 261 typedef std::vector<MachineBasicBlock *>::const_iterator const_succ_iterator; 262 typedef std::vector<MachineBasicBlock *>::reverse_iterator 263 pred_reverse_iterator; 264 typedef std::vector<MachineBasicBlock *>::const_reverse_iterator 265 const_pred_reverse_iterator; 266 typedef std::vector<MachineBasicBlock *>::reverse_iterator 267 succ_reverse_iterator; 268 typedef std::vector<MachineBasicBlock *>::const_reverse_iterator 269 const_succ_reverse_iterator; 270 pred_iterator pred_begin() { return Predecessors.begin(); } 271 const_pred_iterator pred_begin() const { return Predecessors.begin(); } 272 pred_iterator pred_end() { return Predecessors.end(); } 273 const_pred_iterator pred_end() const { return Predecessors.end(); } 274 pred_reverse_iterator pred_rbegin() 275 { return Predecessors.rbegin();} 276 const_pred_reverse_iterator pred_rbegin() const 277 { return Predecessors.rbegin();} 278 pred_reverse_iterator pred_rend() 279 { return Predecessors.rend(); } 280 const_pred_reverse_iterator pred_rend() const 281 { return Predecessors.rend(); } 282 unsigned pred_size() const { 283 return (unsigned)Predecessors.size(); 284 } 285 bool pred_empty() const { return Predecessors.empty(); } 286 succ_iterator succ_begin() { return Successors.begin(); } 287 const_succ_iterator succ_begin() const { return Successors.begin(); } 288 succ_iterator succ_end() { return Successors.end(); } 289 const_succ_iterator succ_end() const { return Successors.end(); } 290 succ_reverse_iterator succ_rbegin() 291 { return Successors.rbegin(); } 292 const_succ_reverse_iterator succ_rbegin() const 293 { return Successors.rbegin(); } 294 succ_reverse_iterator succ_rend() 295 { return Successors.rend(); } 296 const_succ_reverse_iterator succ_rend() const 297 { return Successors.rend(); } 298 unsigned succ_size() const { 299 return (unsigned)Successors.size(); 300 } 301 bool succ_empty() const { return Successors.empty(); } 302 303 inline iterator_range<pred_iterator> predecessors() { 304 return iterator_range<pred_iterator>(pred_begin(), pred_end()); 305 } 306 inline iterator_range<const_pred_iterator> predecessors() const { 307 return iterator_range<const_pred_iterator>(pred_begin(), pred_end()); 308 } 309 inline iterator_range<succ_iterator> successors() { 310 return iterator_range<succ_iterator>(succ_begin(), succ_end()); 311 } 312 inline iterator_range<const_succ_iterator> successors() const { 313 return iterator_range<const_succ_iterator>(succ_begin(), succ_end()); 314 } 315 316 // LiveIn management methods. 317 318 /// Adds the specified register as a live in. Note that it is an error to add 319 /// the same register to the same set more than once unless the intention is 320 /// to call sortUniqueLiveIns after all registers are added. 321 void addLiveIn(unsigned Reg) { LiveIns.push_back(Reg); } 322 323 /// Sorts and uniques the LiveIns vector. It can be significantly faster to do 324 /// this than repeatedly calling isLiveIn before calling addLiveIn for every 325 /// LiveIn insertion. 326 void sortUniqueLiveIns() { 327 std::sort(LiveIns.begin(), LiveIns.end()); 328 LiveIns.erase(std::unique(LiveIns.begin(), LiveIns.end()), LiveIns.end()); 329 } 330 331 /// Add PhysReg as live in to this block, and ensure that there is a copy of 332 /// PhysReg to a virtual register of class RC. Return the virtual register 333 /// that is a copy of the live in PhysReg. 334 unsigned addLiveIn(unsigned PhysReg, const TargetRegisterClass *RC); 335 336 /// removeLiveIn - Remove the specified register from the live in set. 337 /// 338 void removeLiveIn(unsigned Reg); 339 340 /// isLiveIn - Return true if the specified register is in the live in set. 341 /// 342 bool isLiveIn(unsigned Reg) const; 343 344 // Iteration support for live in sets. These sets are kept in sorted 345 // order by their register number. 346 typedef std::vector<unsigned>::const_iterator livein_iterator; 347 livein_iterator livein_begin() const { return LiveIns.begin(); } 348 livein_iterator livein_end() const { return LiveIns.end(); } 349 bool livein_empty() const { return LiveIns.empty(); } 350 351 /// getAlignment - Return alignment of the basic block. 352 /// The alignment is specified as log2(bytes). 353 /// 354 unsigned getAlignment() const { return Alignment; } 355 356 /// setAlignment - Set alignment of the basic block. 357 /// The alignment is specified as log2(bytes). 358 /// 359 void setAlignment(unsigned Align) { Alignment = Align; } 360 361 /// isLandingPad - Returns true if the block is a landing pad. That is 362 /// this basic block is entered via an exception handler. 363 bool isLandingPad() const { return IsLandingPad; } 364 365 /// setIsLandingPad - Indicates the block is a landing pad. That is 366 /// this basic block is entered via an exception handler. 367 void setIsLandingPad(bool V = true) { IsLandingPad = V; } 368 369 /// getLandingPadSuccessor - If this block has a successor that is a landing 370 /// pad, return it. Otherwise return NULL. 371 const MachineBasicBlock *getLandingPadSuccessor() const; 372 373 // Code Layout methods. 374 375 /// moveBefore/moveAfter - move 'this' block before or after the specified 376 /// block. This only moves the block, it does not modify the CFG or adjust 377 /// potential fall-throughs at the end of the block. 378 void moveBefore(MachineBasicBlock *NewAfter); 379 void moveAfter(MachineBasicBlock *NewBefore); 380 381 /// updateTerminator - Update the terminator instructions in block to account 382 /// for changes to the layout. If the block previously used a fallthrough, 383 /// it may now need a branch, and if it previously used branching it may now 384 /// be able to use a fallthrough. 385 void updateTerminator(); 386 387 // Machine-CFG mutators 388 389 /// addSuccessor - Add succ as a successor of this MachineBasicBlock. 390 /// The Predecessors list of succ is automatically updated. WEIGHT 391 /// parameter is stored in Weights list and it may be used by 392 /// MachineBranchProbabilityInfo analysis to calculate branch probability. 393 /// 394 /// Note that duplicate Machine CFG edges are not allowed. 395 /// 396 void addSuccessor(MachineBasicBlock *succ, uint32_t weight = 0); 397 398 /// Set successor weight of a given iterator. 399 void setSuccWeight(succ_iterator I, uint32_t weight); 400 401 /// removeSuccessor - Remove successor from the successors list of this 402 /// MachineBasicBlock. The Predecessors list of succ is automatically updated. 403 /// 404 void removeSuccessor(MachineBasicBlock *succ); 405 406 /// removeSuccessor - Remove specified successor from the successors list of 407 /// this MachineBasicBlock. The Predecessors list of succ is automatically 408 /// updated. Return the iterator to the element after the one removed. 409 /// 410 succ_iterator removeSuccessor(succ_iterator I); 411 412 /// replaceSuccessor - Replace successor OLD with NEW and update weight info. 413 /// 414 void replaceSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New); 415 416 417 /// transferSuccessors - Transfers all the successors from MBB to this 418 /// machine basic block (i.e., copies all the successors fromMBB and 419 /// remove all the successors from fromMBB). 420 void transferSuccessors(MachineBasicBlock *fromMBB); 421 422 /// transferSuccessorsAndUpdatePHIs - Transfers all the successors, as 423 /// in transferSuccessors, and update PHI operands in the successor blocks 424 /// which refer to fromMBB to refer to this. 425 void transferSuccessorsAndUpdatePHIs(MachineBasicBlock *fromMBB); 426 427 /// isPredecessor - Return true if the specified MBB is a predecessor of this 428 /// block. 429 bool isPredecessor(const MachineBasicBlock *MBB) const; 430 431 /// isSuccessor - Return true if the specified MBB is a successor of this 432 /// block. 433 bool isSuccessor(const MachineBasicBlock *MBB) const; 434 435 /// isLayoutSuccessor - Return true if the specified MBB will be emitted 436 /// immediately after this block, such that if this block exits by 437 /// falling through, control will transfer to the specified MBB. Note 438 /// that MBB need not be a successor at all, for example if this block 439 /// ends with an unconditional branch to some other block. 440 bool isLayoutSuccessor(const MachineBasicBlock *MBB) const; 441 442 /// canFallThrough - Return true if the block can implicitly transfer 443 /// control to the block after it by falling off the end of it. This should 444 /// return false if it can reach the block after it, but it uses an explicit 445 /// branch to do so (e.g., a table jump). True is a conservative answer. 446 bool canFallThrough(); 447 448 /// Returns a pointer to the first instruction in this block that is not a 449 /// PHINode instruction. When adding instructions to the beginning of the 450 /// basic block, they should be added before the returned value, not before 451 /// the first instruction, which might be PHI. 452 /// Returns end() is there's no non-PHI instruction. 453 iterator getFirstNonPHI(); 454 455 /// SkipPHIsAndLabels - Return the first instruction in MBB after I that is 456 /// not a PHI or a label. This is the correct point to insert copies at the 457 /// beginning of a basic block. 458 iterator SkipPHIsAndLabels(iterator I); 459 460 /// getFirstTerminator - returns an iterator to the first terminator 461 /// instruction of this basic block. If a terminator does not exist, 462 /// it returns end() 463 iterator getFirstTerminator(); 464 const_iterator getFirstTerminator() const { 465 return const_cast<MachineBasicBlock *>(this)->getFirstTerminator(); 466 } 467 468 /// getFirstInstrTerminator - Same getFirstTerminator but it ignores bundles 469 /// and return an instr_iterator instead. 470 instr_iterator getFirstInstrTerminator(); 471 472 /// getFirstNonDebugInstr - returns an iterator to the first non-debug 473 /// instruction in the basic block, or end() 474 iterator getFirstNonDebugInstr(); 475 const_iterator getFirstNonDebugInstr() const { 476 return const_cast<MachineBasicBlock *>(this)->getFirstNonDebugInstr(); 477 } 478 479 /// getLastNonDebugInstr - returns an iterator to the last non-debug 480 /// instruction in the basic block, or end() 481 iterator getLastNonDebugInstr(); 482 const_iterator getLastNonDebugInstr() const { 483 return const_cast<MachineBasicBlock *>(this)->getLastNonDebugInstr(); 484 } 485 486 /// SplitCriticalEdge - Split the critical edge from this block to the 487 /// given successor block, and return the newly created block, or null 488 /// if splitting is not possible. 489 /// 490 /// This function updates LiveVariables, MachineDominatorTree, and 491 /// MachineLoopInfo, as applicable. 492 MachineBasicBlock *SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P); 493 494 void pop_front() { Insts.pop_front(); } 495 void pop_back() { Insts.pop_back(); } 496 void push_back(MachineInstr *MI) { Insts.push_back(MI); } 497 498 /// Insert MI into the instruction list before I, possibly inside a bundle. 499 /// 500 /// If the insertion point is inside a bundle, MI will be added to the bundle, 501 /// otherwise MI will not be added to any bundle. That means this function 502 /// alone can't be used to prepend or append instructions to bundles. See 503 /// MIBundleBuilder::insert() for a more reliable way of doing that. 504 instr_iterator insert(instr_iterator I, MachineInstr *M); 505 506 /// Insert a range of instructions into the instruction list before I. 507 template<typename IT> 508 void insert(iterator I, IT S, IT E) { 509 assert((I == end() || I->getParent() == this) && 510 "iterator points outside of basic block"); 511 Insts.insert(I.getInstrIterator(), S, E); 512 } 513 514 /// Insert MI into the instruction list before I. 515 iterator insert(iterator I, MachineInstr *MI) { 516 assert((I == end() || I->getParent() == this) && 517 "iterator points outside of basic block"); 518 assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() && 519 "Cannot insert instruction with bundle flags"); 520 return Insts.insert(I.getInstrIterator(), MI); 521 } 522 523 /// Insert MI into the instruction list after I. 524 iterator insertAfter(iterator I, MachineInstr *MI) { 525 assert((I == end() || I->getParent() == this) && 526 "iterator points outside of basic block"); 527 assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() && 528 "Cannot insert instruction with bundle flags"); 529 return Insts.insertAfter(I.getInstrIterator(), MI); 530 } 531 532 /// Remove an instruction from the instruction list and delete it. 533 /// 534 /// If the instruction is part of a bundle, the other instructions in the 535 /// bundle will still be bundled after removing the single instruction. 536 instr_iterator erase(instr_iterator I); 537 538 /// Remove an instruction from the instruction list and delete it. 539 /// 540 /// If the instruction is part of a bundle, the other instructions in the 541 /// bundle will still be bundled after removing the single instruction. 542 instr_iterator erase_instr(MachineInstr *I) { 543 return erase(instr_iterator(I)); 544 } 545 546 /// Remove a range of instructions from the instruction list and delete them. 547 iterator erase(iterator I, iterator E) { 548 return Insts.erase(I.getInstrIterator(), E.getInstrIterator()); 549 } 550 551 /// Remove an instruction or bundle from the instruction list and delete it. 552 /// 553 /// If I points to a bundle of instructions, they are all erased. 554 iterator erase(iterator I) { 555 return erase(I, std::next(I)); 556 } 557 558 /// Remove an instruction from the instruction list and delete it. 559 /// 560 /// If I is the head of a bundle of instructions, the whole bundle will be 561 /// erased. 562 iterator erase(MachineInstr *I) { 563 return erase(iterator(I)); 564 } 565 566 /// Remove the unbundled instruction from the instruction list without 567 /// deleting it. 568 /// 569 /// This function can not be used to remove bundled instructions, use 570 /// remove_instr to remove individual instructions from a bundle. 571 MachineInstr *remove(MachineInstr *I) { 572 assert(!I->isBundled() && "Cannot remove bundled instructions"); 573 return Insts.remove(I); 574 } 575 576 /// Remove the possibly bundled instruction from the instruction list 577 /// without deleting it. 578 /// 579 /// If the instruction is part of a bundle, the other instructions in the 580 /// bundle will still be bundled after removing the single instruction. 581 MachineInstr *remove_instr(MachineInstr *I); 582 583 void clear() { 584 Insts.clear(); 585 } 586 587 /// Take an instruction from MBB 'Other' at the position From, and insert it 588 /// into this MBB right before 'Where'. 589 /// 590 /// If From points to a bundle of instructions, the whole bundle is moved. 591 void splice(iterator Where, MachineBasicBlock *Other, iterator From) { 592 // The range splice() doesn't allow noop moves, but this one does. 593 if (Where != From) 594 splice(Where, Other, From, std::next(From)); 595 } 596 597 /// Take a block of instructions from MBB 'Other' in the range [From, To), 598 /// and insert them into this MBB right before 'Where'. 599 /// 600 /// The instruction at 'Where' must not be included in the range of 601 /// instructions to move. 602 void splice(iterator Where, MachineBasicBlock *Other, 603 iterator From, iterator To) { 604 Insts.splice(Where.getInstrIterator(), Other->Insts, 605 From.getInstrIterator(), To.getInstrIterator()); 606 } 607 608 /// removeFromParent - This method unlinks 'this' from the containing 609 /// function, and returns it, but does not delete it. 610 MachineBasicBlock *removeFromParent(); 611 612 /// eraseFromParent - This method unlinks 'this' from the containing 613 /// function and deletes it. 614 void eraseFromParent(); 615 616 /// ReplaceUsesOfBlockWith - Given a machine basic block that branched to 617 /// 'Old', change the code and CFG so that it branches to 'New' instead. 618 void ReplaceUsesOfBlockWith(MachineBasicBlock *Old, MachineBasicBlock *New); 619 620 /// CorrectExtraCFGEdges - Various pieces of code can cause excess edges in 621 /// the CFG to be inserted. If we have proven that MBB can only branch to 622 /// DestA and DestB, remove any other MBB successors from the CFG. DestA and 623 /// DestB can be null. Besides DestA and DestB, retain other edges leading 624 /// to LandingPads (currently there can be only one; we don't check or require 625 /// that here). Note it is possible that DestA and/or DestB are LandingPads. 626 bool CorrectExtraCFGEdges(MachineBasicBlock *DestA, 627 MachineBasicBlock *DestB, 628 bool isCond); 629 630 /// findDebugLoc - find the next valid DebugLoc starting at MBBI, skipping 631 /// any DBG_VALUE instructions. Return UnknownLoc if there is none. 632 DebugLoc findDebugLoc(instr_iterator MBBI); 633 DebugLoc findDebugLoc(iterator MBBI) { 634 return findDebugLoc(MBBI.getInstrIterator()); 635 } 636 637 /// Possible outcome of a register liveness query to computeRegisterLiveness() 638 enum LivenessQueryResult { 639 LQR_Live, ///< Register is known to be live. 640 LQR_OverlappingLive, ///< Register itself is not live, but some overlapping 641 ///< register is. 642 LQR_Dead, ///< Register is known to be dead. 643 LQR_Unknown ///< Register liveness not decidable from local 644 ///< neighborhood. 645 }; 646 647 /// Return whether (physical) register \p Reg has been <def>ined and not 648 /// <kill>ed as of just before \p Before. 649 /// 650 /// Search is localised to a neighborhood of \p Neighborhood instructions 651 /// before (searching for defs or kills) and \p Neighborhood instructions 652 /// after (searching just for defs) \p Before. 653 /// 654 /// \p Reg must be a physical register. 655 LivenessQueryResult computeRegisterLiveness(const TargetRegisterInfo *TRI, 656 unsigned Reg, 657 const_iterator Before, 658 unsigned Neighborhood=10) const; 659 660 // Debugging methods. 661 void dump() const; 662 void print(raw_ostream &OS, SlotIndexes* = nullptr) const; 663 void print(raw_ostream &OS, ModuleSlotTracker &MST, 664 SlotIndexes * = nullptr) const; 665 666 // Printing method used by LoopInfo. 667 void printAsOperand(raw_ostream &OS, bool PrintType = true) const; 668 669 /// getNumber - MachineBasicBlocks are uniquely numbered at the function 670 /// level, unless they're not in a MachineFunction yet, in which case this 671 /// will return -1. 672 /// 673 int getNumber() const { return Number; } 674 void setNumber(int N) { Number = N; } 675 676 /// getSymbol - Return the MCSymbol for this basic block. 677 /// 678 MCSymbol *getSymbol() const; 679 680 681private: 682 /// getWeightIterator - Return weight iterator corresponding to the I 683 /// successor iterator. 684 weight_iterator getWeightIterator(succ_iterator I); 685 const_weight_iterator getWeightIterator(const_succ_iterator I) const; 686 687 friend class MachineBranchProbabilityInfo; 688 689 /// getSuccWeight - Return weight of the edge from this block to MBB. This 690 /// method should NOT be called directly, but by using getEdgeWeight method 691 /// from MachineBranchProbabilityInfo class. 692 uint32_t getSuccWeight(const_succ_iterator Succ) const; 693 694 695 // Methods used to maintain doubly linked list of blocks... 696 friend struct ilist_traits<MachineBasicBlock>; 697 698 // Machine-CFG mutators 699 700 /// addPredecessor - Remove pred as a predecessor of this MachineBasicBlock. 701 /// Don't do this unless you know what you're doing, because it doesn't 702 /// update pred's successors list. Use pred->addSuccessor instead. 703 /// 704 void addPredecessor(MachineBasicBlock *pred); 705 706 /// removePredecessor - Remove pred as a predecessor of this 707 /// MachineBasicBlock. Don't do this unless you know what you're 708 /// doing, because it doesn't update pred's successors list. Use 709 /// pred->removeSuccessor instead. 710 /// 711 void removePredecessor(MachineBasicBlock *pred); 712}; 713 714raw_ostream& operator<<(raw_ostream &OS, const MachineBasicBlock &MBB); 715 716// This is useful when building IndexedMaps keyed on basic block pointers. 717struct MBB2NumberFunctor : 718 public std::unary_function<const MachineBasicBlock*, unsigned> { 719 unsigned operator()(const MachineBasicBlock *MBB) const { 720 return MBB->getNumber(); 721 } 722}; 723 724//===--------------------------------------------------------------------===// 725// GraphTraits specializations for machine basic block graphs (machine-CFGs) 726//===--------------------------------------------------------------------===// 727 728// Provide specializations of GraphTraits to be able to treat a 729// MachineFunction as a graph of MachineBasicBlocks... 730// 731 732template <> struct GraphTraits<MachineBasicBlock *> { 733 typedef MachineBasicBlock NodeType; 734 typedef MachineBasicBlock::succ_iterator ChildIteratorType; 735 736 static NodeType *getEntryNode(MachineBasicBlock *BB) { return BB; } 737 static inline ChildIteratorType child_begin(NodeType *N) { 738 return N->succ_begin(); 739 } 740 static inline ChildIteratorType child_end(NodeType *N) { 741 return N->succ_end(); 742 } 743}; 744 745template <> struct GraphTraits<const MachineBasicBlock *> { 746 typedef const MachineBasicBlock NodeType; 747 typedef MachineBasicBlock::const_succ_iterator ChildIteratorType; 748 749 static NodeType *getEntryNode(const MachineBasicBlock *BB) { return BB; } 750 static inline ChildIteratorType child_begin(NodeType *N) { 751 return N->succ_begin(); 752 } 753 static inline ChildIteratorType child_end(NodeType *N) { 754 return N->succ_end(); 755 } 756}; 757 758// Provide specializations of GraphTraits to be able to treat a 759// MachineFunction as a graph of MachineBasicBlocks... and to walk it 760// in inverse order. Inverse order for a function is considered 761// to be when traversing the predecessor edges of a MBB 762// instead of the successor edges. 763// 764template <> struct GraphTraits<Inverse<MachineBasicBlock*> > { 765 typedef MachineBasicBlock NodeType; 766 typedef MachineBasicBlock::pred_iterator ChildIteratorType; 767 static NodeType *getEntryNode(Inverse<MachineBasicBlock *> G) { 768 return G.Graph; 769 } 770 static inline ChildIteratorType child_begin(NodeType *N) { 771 return N->pred_begin(); 772 } 773 static inline ChildIteratorType child_end(NodeType *N) { 774 return N->pred_end(); 775 } 776}; 777 778template <> struct GraphTraits<Inverse<const MachineBasicBlock*> > { 779 typedef const MachineBasicBlock NodeType; 780 typedef MachineBasicBlock::const_pred_iterator ChildIteratorType; 781 static NodeType *getEntryNode(Inverse<const MachineBasicBlock*> G) { 782 return G.Graph; 783 } 784 static inline ChildIteratorType child_begin(NodeType *N) { 785 return N->pred_begin(); 786 } 787 static inline ChildIteratorType child_end(NodeType *N) { 788 return N->pred_end(); 789 } 790}; 791 792 793 794/// MachineInstrSpan provides an interface to get an iteration range 795/// containing the instruction it was initialized with, along with all 796/// those instructions inserted prior to or following that instruction 797/// at some point after the MachineInstrSpan is constructed. 798class MachineInstrSpan { 799 MachineBasicBlock &MBB; 800 MachineBasicBlock::iterator I, B, E; 801public: 802 MachineInstrSpan(MachineBasicBlock::iterator I) 803 : MBB(*I->getParent()), 804 I(I), 805 B(I == MBB.begin() ? MBB.end() : std::prev(I)), 806 E(std::next(I)) {} 807 808 MachineBasicBlock::iterator begin() { 809 return B == MBB.end() ? MBB.begin() : std::next(B); 810 } 811 MachineBasicBlock::iterator end() { return E; } 812 bool empty() { return begin() == end(); } 813 814 MachineBasicBlock::iterator getInitial() { return I; } 815}; 816 817} // End llvm namespace 818 819#endif 820