MachineBasicBlock.h revision 25101bb2a799a36be9f077ee2fc2dcf0df2b6efb
1//===-- llvm/CodeGen/MachineBasicBlock.h ------------------------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// Collect the sequence of machine instructions for a basic block. 11// 12//===----------------------------------------------------------------------===// 13 14#ifndef LLVM_CODEGEN_MACHINEBASICBLOCK_H 15#define LLVM_CODEGEN_MACHINEBASICBLOCK_H 16 17#include "llvm/CodeGen/MachineInstr.h" 18#include "llvm/ADT/GraphTraits.h" 19#include "llvm/Support/DataTypes.h" 20#include <functional> 21 22namespace llvm { 23 24class Pass; 25class BasicBlock; 26class MachineFunction; 27class MCSymbol; 28class SlotIndexes; 29class StringRef; 30class raw_ostream; 31class MachineBranchProbabilityInfo; 32 33template <> 34struct ilist_traits<MachineInstr> : public ilist_default_traits<MachineInstr> { 35private: 36 mutable ilist_half_node<MachineInstr> Sentinel; 37 38 // this is only set by the MachineBasicBlock owning the LiveList 39 friend class MachineBasicBlock; 40 MachineBasicBlock* Parent; 41 42public: 43 MachineInstr *createSentinel() const { 44 return static_cast<MachineInstr*>(&Sentinel); 45 } 46 void destroySentinel(MachineInstr *) const {} 47 48 MachineInstr *provideInitialHead() const { return createSentinel(); } 49 MachineInstr *ensureHead(MachineInstr*) const { return createSentinel(); } 50 static void noteHead(MachineInstr*, MachineInstr*) {} 51 52 void addNodeToList(MachineInstr* N); 53 void removeNodeFromList(MachineInstr* N); 54 void transferNodesFromList(ilist_traits &SrcTraits, 55 ilist_iterator<MachineInstr> first, 56 ilist_iterator<MachineInstr> last); 57 void deleteNode(MachineInstr *N); 58private: 59 void createNode(const MachineInstr &); 60}; 61 62class MachineBasicBlock : public ilist_node<MachineBasicBlock> { 63 typedef ilist<MachineInstr> Instructions; 64 Instructions Insts; 65 const BasicBlock *BB; 66 int Number; 67 MachineFunction *xParent; 68 69 /// Predecessors/Successors - Keep track of the predecessor / successor 70 /// basicblocks. 71 std::vector<MachineBasicBlock *> Predecessors; 72 std::vector<MachineBasicBlock *> Successors; 73 74 75 /// Weights - Keep track of the weights to the successors. This vector 76 /// has the same order as Successors, or it is empty if we don't use it 77 /// (disable optimization). 78 std::vector<uint32_t> Weights; 79 typedef std::vector<uint32_t>::iterator weight_iterator; 80 typedef std::vector<uint32_t>::const_iterator const_weight_iterator; 81 82 /// LiveIns - Keep track of the physical registers that are livein of 83 /// the basicblock. 84 std::vector<unsigned> LiveIns; 85 86 /// Alignment - Alignment of the basic block. Zero if the basic block does 87 /// not need to be aligned. 88 /// The alignment is specified as log2(bytes). 89 unsigned Alignment; 90 91 /// IsLandingPad - Indicate that this basic block is entered via an 92 /// exception handler. 93 bool IsLandingPad; 94 95 /// AddressTaken - Indicate that this basic block is potentially the 96 /// target of an indirect branch. 97 bool AddressTaken; 98 99 // Intrusive list support 100 MachineBasicBlock() {} 101 102 explicit MachineBasicBlock(MachineFunction &mf, const BasicBlock *bb); 103 104 ~MachineBasicBlock(); 105 106 // MachineBasicBlocks are allocated and owned by MachineFunction. 107 friend class MachineFunction; 108 109public: 110 /// getBasicBlock - Return the LLVM basic block that this instance 111 /// corresponded to originally. Note that this may be NULL if this instance 112 /// does not correspond directly to an LLVM basic block. 113 /// 114 const BasicBlock *getBasicBlock() const { return BB; } 115 116 /// getName - Return the name of the corresponding LLVM basic block, or 117 /// "(null)". 118 StringRef getName() const; 119 120 /// hasAddressTaken - Test whether this block is potentially the target 121 /// of an indirect branch. 122 bool hasAddressTaken() const { return AddressTaken; } 123 124 /// setHasAddressTaken - Set this block to reflect that it potentially 125 /// is the target of an indirect branch. 126 void setHasAddressTaken() { AddressTaken = true; } 127 128 /// getParent - Return the MachineFunction containing this basic block. 129 /// 130 const MachineFunction *getParent() const { return xParent; } 131 MachineFunction *getParent() { return xParent; } 132 133 134 /// bundle_iterator - MachineBasicBlock iterator that automatically skips over 135 /// MIs that are inside bundles (i.e. walk top level MIs only). 136 template<typename Ty, typename IterTy> 137 class bundle_iterator 138 : public std::iterator<std::bidirectional_iterator_tag, Ty, ptrdiff_t> { 139 IterTy MII; 140 141 public: 142 bundle_iterator(IterTy mii) : MII(mii) { 143 assert(!MII->isInsideBundle() && 144 "It's not legal to initialize bundle_iterator with a bundled MI"); 145 } 146 147 bundle_iterator(Ty &mi) : MII(mi) { 148 assert(!mi.isInsideBundle() && 149 "It's not legal to initialize bundle_iterator with a bundled MI"); 150 } 151 bundle_iterator(Ty *mi) : MII(mi) { 152 assert((!mi || !mi->isInsideBundle()) && 153 "It's not legal to initialize bundle_iterator with a bundled MI"); 154 } 155 bundle_iterator(const bundle_iterator &I) : MII(I.MII) {} 156 bundle_iterator() : MII(0) {} 157 158 Ty &operator*() const { return *MII; } 159 Ty *operator->() const { return &operator*(); } 160 161 operator Ty*() const { return MII; } 162 163 bool operator==(const bundle_iterator &x) const { 164 return MII == x.MII; 165 } 166 bool operator!=(const bundle_iterator &x) const { 167 return !operator==(x); 168 } 169 170 // Increment and decrement operators... 171 bundle_iterator &operator--() { // predecrement - Back up 172 do { 173 --MII; 174 } while (MII->isInsideBundle()); 175 return *this; 176 } 177 bundle_iterator &operator++() { // preincrement - Advance 178 do { 179 ++MII; 180 } while (MII->isInsideBundle()); 181 return *this; 182 } 183 bundle_iterator operator--(int) { // postdecrement operators... 184 bundle_iterator tmp = *this; 185 do { 186 --MII; 187 } while (MII->isInsideBundle()); 188 return tmp; 189 } 190 bundle_iterator operator++(int) { // postincrement operators... 191 bundle_iterator tmp = *this; 192 do { 193 ++MII; 194 } while (MII->isInsideBundle()); 195 return tmp; 196 } 197 198 IterTy getInstrIterator() const { 199 return MII; 200 } 201 }; 202 203 typedef Instructions::iterator instr_iterator; 204 typedef Instructions::const_iterator const_instr_iterator; 205 typedef std::reverse_iterator<instr_iterator> reverse_instr_iterator; 206 typedef 207 std::reverse_iterator<const_instr_iterator> const_reverse_instr_iterator; 208 209 typedef 210 bundle_iterator<MachineInstr,instr_iterator> iterator; 211 typedef 212 bundle_iterator<const MachineInstr,const_instr_iterator> const_iterator; 213 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 214 typedef std::reverse_iterator<iterator> reverse_iterator; 215 216 217 unsigned size() const { return (unsigned)Insts.size(); } 218 bool empty() const { return Insts.empty(); } 219 220 MachineInstr& front() { return Insts.front(); } 221 MachineInstr& back() { return Insts.back(); } 222 const MachineInstr& front() const { return Insts.front(); } 223 const MachineInstr& back() const { return Insts.back(); } 224 225 instr_iterator instr_begin() { return Insts.begin(); } 226 const_instr_iterator instr_begin() const { return Insts.begin(); } 227 instr_iterator instr_end() { return Insts.end(); } 228 const_instr_iterator instr_end() const { return Insts.end(); } 229 reverse_instr_iterator instr_rbegin() { return Insts.rbegin(); } 230 const_reverse_instr_iterator instr_rbegin() const { return Insts.rbegin(); } 231 reverse_instr_iterator instr_rend () { return Insts.rend(); } 232 const_reverse_instr_iterator instr_rend () const { return Insts.rend(); } 233 234 iterator begin() { return Insts.begin(); } 235 const_iterator begin() const { return Insts.begin(); } 236 iterator end() { 237 instr_iterator II = instr_end(); 238 if (II != instr_begin()) { 239 while (II->isInsideBundle()) 240 --II; 241 } 242 return II; 243 } 244 const_iterator end() const { 245 const_instr_iterator II = instr_end(); 246 if (II != instr_begin()) { 247 while (II->isInsideBundle()) 248 --II; 249 } 250 return II; 251 } 252 reverse_iterator rbegin() { 253 reverse_instr_iterator II = instr_rbegin(); 254 if (II != instr_rend()) { 255 while (II->isInsideBundle()) 256 ++II; 257 } 258 return II; 259 } 260 const_reverse_iterator rbegin() const { 261 const_reverse_instr_iterator II = instr_rbegin(); 262 if (II != instr_rend()) { 263 while (II->isInsideBundle()) 264 ++II; 265 } 266 return II; 267 } 268 reverse_iterator rend () { return Insts.rend(); } 269 const_reverse_iterator rend () const { return Insts.rend(); } 270 271 272 // Machine-CFG iterators 273 typedef std::vector<MachineBasicBlock *>::iterator pred_iterator; 274 typedef std::vector<MachineBasicBlock *>::const_iterator const_pred_iterator; 275 typedef std::vector<MachineBasicBlock *>::iterator succ_iterator; 276 typedef std::vector<MachineBasicBlock *>::const_iterator const_succ_iterator; 277 typedef std::vector<MachineBasicBlock *>::reverse_iterator 278 pred_reverse_iterator; 279 typedef std::vector<MachineBasicBlock *>::const_reverse_iterator 280 const_pred_reverse_iterator; 281 typedef std::vector<MachineBasicBlock *>::reverse_iterator 282 succ_reverse_iterator; 283 typedef std::vector<MachineBasicBlock *>::const_reverse_iterator 284 const_succ_reverse_iterator; 285 286 pred_iterator pred_begin() { return Predecessors.begin(); } 287 const_pred_iterator pred_begin() const { return Predecessors.begin(); } 288 pred_iterator pred_end() { return Predecessors.end(); } 289 const_pred_iterator pred_end() const { return Predecessors.end(); } 290 pred_reverse_iterator pred_rbegin() 291 { return Predecessors.rbegin();} 292 const_pred_reverse_iterator pred_rbegin() const 293 { return Predecessors.rbegin();} 294 pred_reverse_iterator pred_rend() 295 { return Predecessors.rend(); } 296 const_pred_reverse_iterator pred_rend() const 297 { return Predecessors.rend(); } 298 unsigned pred_size() const { 299 return (unsigned)Predecessors.size(); 300 } 301 bool pred_empty() const { return Predecessors.empty(); } 302 succ_iterator succ_begin() { return Successors.begin(); } 303 const_succ_iterator succ_begin() const { return Successors.begin(); } 304 succ_iterator succ_end() { return Successors.end(); } 305 const_succ_iterator succ_end() const { return Successors.end(); } 306 succ_reverse_iterator succ_rbegin() 307 { return Successors.rbegin(); } 308 const_succ_reverse_iterator succ_rbegin() const 309 { return Successors.rbegin(); } 310 succ_reverse_iterator succ_rend() 311 { return Successors.rend(); } 312 const_succ_reverse_iterator succ_rend() const 313 { return Successors.rend(); } 314 unsigned succ_size() const { 315 return (unsigned)Successors.size(); 316 } 317 bool succ_empty() const { return Successors.empty(); } 318 319 // LiveIn management methods. 320 321 /// addLiveIn - Add the specified register as a live in. Note that it 322 /// is an error to add the same register to the same set more than once. 323 void addLiveIn(unsigned Reg) { LiveIns.push_back(Reg); } 324 325 /// removeLiveIn - Remove the specified register from the live in set. 326 /// 327 void removeLiveIn(unsigned Reg); 328 329 /// isLiveIn - Return true if the specified register is in the live in set. 330 /// 331 bool isLiveIn(unsigned Reg) const; 332 333 // Iteration support for live in sets. These sets are kept in sorted 334 // order by their register number. 335 typedef std::vector<unsigned>::const_iterator livein_iterator; 336 livein_iterator livein_begin() const { return LiveIns.begin(); } 337 livein_iterator livein_end() const { return LiveIns.end(); } 338 bool livein_empty() const { return LiveIns.empty(); } 339 340 /// getAlignment - Return alignment of the basic block. 341 /// The alignment is specified as log2(bytes). 342 /// 343 unsigned getAlignment() const { return Alignment; } 344 345 /// setAlignment - Set alignment of the basic block. 346 /// The alignment is specified as log2(bytes). 347 /// 348 void setAlignment(unsigned Align) { Alignment = Align; } 349 350 /// isLandingPad - Returns true if the block is a landing pad. That is 351 /// this basic block is entered via an exception handler. 352 bool isLandingPad() const { return IsLandingPad; } 353 354 /// setIsLandingPad - Indicates the block is a landing pad. That is 355 /// this basic block is entered via an exception handler. 356 void setIsLandingPad(bool V = true) { IsLandingPad = V; } 357 358 /// getLandingPadSuccessor - If this block has a successor that is a landing 359 /// pad, return it. Otherwise return NULL. 360 const MachineBasicBlock *getLandingPadSuccessor() const; 361 362 // Code Layout methods. 363 364 /// moveBefore/moveAfter - move 'this' block before or after the specified 365 /// block. This only moves the block, it does not modify the CFG or adjust 366 /// potential fall-throughs at the end of the block. 367 void moveBefore(MachineBasicBlock *NewAfter); 368 void moveAfter(MachineBasicBlock *NewBefore); 369 370 /// updateTerminator - Update the terminator instructions in block to account 371 /// for changes to the layout. If the block previously used a fallthrough, 372 /// it may now need a branch, and if it previously used branching it may now 373 /// be able to use a fallthrough. 374 void updateTerminator(); 375 376 // Machine-CFG mutators 377 378 /// addSuccessor - Add succ as a successor of this MachineBasicBlock. 379 /// The Predecessors list of succ is automatically updated. WEIGHT 380 /// parameter is stored in Weights list and it may be used by 381 /// MachineBranchProbabilityInfo analysis to calculate branch probability. 382 /// 383 void addSuccessor(MachineBasicBlock *succ, uint32_t weight = 0); 384 385 /// removeSuccessor - Remove successor from the successors list of this 386 /// MachineBasicBlock. The Predecessors list of succ is automatically updated. 387 /// 388 void removeSuccessor(MachineBasicBlock *succ); 389 390 /// removeSuccessor - Remove specified successor from the successors list of 391 /// this MachineBasicBlock. The Predecessors list of succ is automatically 392 /// updated. Return the iterator to the element after the one removed. 393 /// 394 succ_iterator removeSuccessor(succ_iterator I); 395 396 /// replaceSuccessor - Replace successor OLD with NEW and update weight info. 397 /// 398 void replaceSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New); 399 400 401 /// transferSuccessors - Transfers all the successors from MBB to this 402 /// machine basic block (i.e., copies all the successors fromMBB and 403 /// remove all the successors from fromMBB). 404 void transferSuccessors(MachineBasicBlock *fromMBB); 405 406 /// transferSuccessorsAndUpdatePHIs - Transfers all the successors, as 407 /// in transferSuccessors, and update PHI operands in the successor blocks 408 /// which refer to fromMBB to refer to this. 409 void transferSuccessorsAndUpdatePHIs(MachineBasicBlock *fromMBB); 410 411 /// isSuccessor - Return true if the specified MBB is a successor of this 412 /// block. 413 bool isSuccessor(const MachineBasicBlock *MBB) const; 414 415 /// isLayoutSuccessor - Return true if the specified MBB will be emitted 416 /// immediately after this block, such that if this block exits by 417 /// falling through, control will transfer to the specified MBB. Note 418 /// that MBB need not be a successor at all, for example if this block 419 /// ends with an unconditional branch to some other block. 420 bool isLayoutSuccessor(const MachineBasicBlock *MBB) const; 421 422 /// canFallThrough - Return true if the block can implicitly transfer 423 /// control to the block after it by falling off the end of it. This should 424 /// return false if it can reach the block after it, but it uses an explicit 425 /// branch to do so (e.g., a table jump). True is a conservative answer. 426 bool canFallThrough(); 427 428 /// Returns a pointer to the first instructon in this block that is not a 429 /// PHINode instruction. When adding instruction to the beginning of the 430 /// basic block, they should be added before the returned value, not before 431 /// the first instruction, which might be PHI. 432 /// Returns end() is there's no non-PHI instruction. 433 iterator getFirstNonPHI(); 434 435 /// SkipPHIsAndLabels - Return the first instruction in MBB after I that is 436 /// not a PHI or a label. This is the correct point to insert copies at the 437 /// beginning of a basic block. 438 iterator SkipPHIsAndLabels(iterator I); 439 440 /// getFirstTerminator - returns an iterator to the first terminator 441 /// instruction of this basic block. If a terminator does not exist, 442 /// it returns end() 443 iterator getFirstTerminator(); 444 const_iterator getFirstTerminator() const; 445 446 /// getFirstInstrTerminator - Same getFirstTerminator but it ignores bundles 447 /// and return an instr_iterator instead. 448 instr_iterator getFirstInstrTerminator(); 449 450 /// getLastNonDebugInstr - returns an iterator to the last non-debug 451 /// instruction in the basic block, or end() 452 iterator getLastNonDebugInstr(); 453 const_iterator getLastNonDebugInstr() const; 454 455 /// SplitCriticalEdge - Split the critical edge from this block to the 456 /// given successor block, and return the newly created block, or null 457 /// if splitting is not possible. 458 /// 459 /// This function updates LiveVariables, MachineDominatorTree, and 460 /// MachineLoopInfo, as applicable. 461 MachineBasicBlock *SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P); 462 463 void pop_front() { Insts.pop_front(); } 464 void pop_back() { Insts.pop_back(); } 465 void push_back(MachineInstr *MI) { Insts.push_back(MI); } 466 467 template<typename IT> 468 void insert(instr_iterator I, IT S, IT E) { 469 Insts.insert(I, S, E); 470 } 471 instr_iterator insert(instr_iterator I, MachineInstr *M) { 472 return Insts.insert(I, M); 473 } 474 instr_iterator insertAfter(instr_iterator I, MachineInstr *M) { 475 return Insts.insertAfter(I, M); 476 } 477 478 template<typename IT> 479 void insert(iterator I, IT S, IT E) { 480 Insts.insert(I.getInstrIterator(), S, E); 481 } 482 iterator insert(iterator I, MachineInstr *M) { 483 return Insts.insert(I.getInstrIterator(), M); 484 } 485 iterator insertAfter(iterator I, MachineInstr *M) { 486 return Insts.insertAfter(I.getInstrIterator(), M); 487 } 488 489 /// erase - Remove the specified element or range from the instruction list. 490 /// These functions delete any instructions removed. 491 /// 492 instr_iterator erase(instr_iterator I) { 493 return Insts.erase(I); 494 } 495 instr_iterator erase(instr_iterator I, instr_iterator E) { 496 return Insts.erase(I, E); 497 } 498 instr_iterator erase_instr(MachineInstr *I) { 499 instr_iterator MII(I); 500 return erase(MII); 501 } 502 503 iterator erase(iterator I); 504 iterator erase(iterator I, iterator E) { 505 return Insts.erase(I.getInstrIterator(), E.getInstrIterator()); 506 } 507 iterator erase(MachineInstr *I) { 508 iterator MII(I); 509 return erase(MII); 510 } 511 512 /// remove - Remove the instruction from the instruction list. This function 513 /// does not delete the instruction. WARNING: Note, if the specified 514 /// instruction is a bundle this function will remove all the bundled 515 /// instructions as well. It is up to the caller to keep a list of the 516 /// bundled instructions and re-insert them if desired. This function is 517 /// *not recommended* for manipulating instructions with bundles. Use 518 /// splice instead. 519 MachineInstr *remove(MachineInstr *I); 520 void clear() { 521 Insts.clear(); 522 } 523 524 /// splice - Take an instruction from MBB 'Other' at the position From, 525 /// and insert it into this MBB right before 'where'. 526 void splice(instr_iterator where, MachineBasicBlock *Other, 527 instr_iterator From) { 528 Insts.splice(where, Other->Insts, From); 529 } 530 void splice(iterator where, MachineBasicBlock *Other, iterator From); 531 532 /// splice - Take a block of instructions from MBB 'Other' in the range [From, 533 /// To), and insert them into this MBB right before 'where'. 534 void splice(instr_iterator where, MachineBasicBlock *Other, instr_iterator From, 535 instr_iterator To) { 536 Insts.splice(where, Other->Insts, From, To); 537 } 538 void splice(iterator where, MachineBasicBlock *Other, iterator From, 539 iterator To) { 540 Insts.splice(where.getInstrIterator(), Other->Insts, 541 From.getInstrIterator(), To.getInstrIterator()); 542 } 543 544 /// removeFromParent - This method unlinks 'this' from the containing 545 /// function, and returns it, but does not delete it. 546 MachineBasicBlock *removeFromParent(); 547 548 /// eraseFromParent - This method unlinks 'this' from the containing 549 /// function and deletes it. 550 void eraseFromParent(); 551 552 /// ReplaceUsesOfBlockWith - Given a machine basic block that branched to 553 /// 'Old', change the code and CFG so that it branches to 'New' instead. 554 void ReplaceUsesOfBlockWith(MachineBasicBlock *Old, MachineBasicBlock *New); 555 556 /// CorrectExtraCFGEdges - Various pieces of code can cause excess edges in 557 /// the CFG to be inserted. If we have proven that MBB can only branch to 558 /// DestA and DestB, remove any other MBB successors from the CFG. DestA and 559 /// DestB can be null. Besides DestA and DestB, retain other edges leading 560 /// to LandingPads (currently there can be only one; we don't check or require 561 /// that here). Note it is possible that DestA and/or DestB are LandingPads. 562 bool CorrectExtraCFGEdges(MachineBasicBlock *DestA, 563 MachineBasicBlock *DestB, 564 bool isCond); 565 566 /// findDebugLoc - find the next valid DebugLoc starting at MBBI, skipping 567 /// any DBG_VALUE instructions. Return UnknownLoc if there is none. 568 DebugLoc findDebugLoc(instr_iterator MBBI); 569 DebugLoc findDebugLoc(iterator MBBI) { 570 return findDebugLoc(MBBI.getInstrIterator()); 571 } 572 573 // Debugging methods. 574 void dump() const; 575 void print(raw_ostream &OS, SlotIndexes* = 0) const; 576 577 /// getNumber - MachineBasicBlocks are uniquely numbered at the function 578 /// level, unless they're not in a MachineFunction yet, in which case this 579 /// will return -1. 580 /// 581 int getNumber() const { return Number; } 582 void setNumber(int N) { Number = N; } 583 584 /// getSymbol - Return the MCSymbol for this basic block. 585 /// 586 MCSymbol *getSymbol() const; 587 588 589private: 590 /// getWeightIterator - Return weight iterator corresponding to the I 591 /// successor iterator. 592 weight_iterator getWeightIterator(succ_iterator I); 593 const_weight_iterator getWeightIterator(const_succ_iterator I) const; 594 595 friend class MachineBranchProbabilityInfo; 596 597 /// getSuccWeight - Return weight of the edge from this block to MBB. This 598 /// method should NOT be called directly, but by using getEdgeWeight method 599 /// from MachineBranchProbabilityInfo class. 600 uint32_t getSuccWeight(const MachineBasicBlock *succ) const; 601 602 603 // Methods used to maintain doubly linked list of blocks... 604 friend struct ilist_traits<MachineBasicBlock>; 605 606 // Machine-CFG mutators 607 608 /// addPredecessor - Remove pred as a predecessor of this MachineBasicBlock. 609 /// Don't do this unless you know what you're doing, because it doesn't 610 /// update pred's successors list. Use pred->addSuccessor instead. 611 /// 612 void addPredecessor(MachineBasicBlock *pred); 613 614 /// removePredecessor - Remove pred as a predecessor of this 615 /// MachineBasicBlock. Don't do this unless you know what you're 616 /// doing, because it doesn't update pred's successors list. Use 617 /// pred->removeSuccessor instead. 618 /// 619 void removePredecessor(MachineBasicBlock *pred); 620}; 621 622raw_ostream& operator<<(raw_ostream &OS, const MachineBasicBlock &MBB); 623 624void WriteAsOperand(raw_ostream &, const MachineBasicBlock*, bool t); 625 626// This is useful when building IndexedMaps keyed on basic block pointers. 627struct MBB2NumberFunctor : 628 public std::unary_function<const MachineBasicBlock*, unsigned> { 629 unsigned operator()(const MachineBasicBlock *MBB) const { 630 return MBB->getNumber(); 631 } 632}; 633 634//===--------------------------------------------------------------------===// 635// GraphTraits specializations for machine basic block graphs (machine-CFGs) 636//===--------------------------------------------------------------------===// 637 638// Provide specializations of GraphTraits to be able to treat a 639// MachineFunction as a graph of MachineBasicBlocks... 640// 641 642template <> struct GraphTraits<MachineBasicBlock *> { 643 typedef MachineBasicBlock NodeType; 644 typedef MachineBasicBlock::succ_iterator ChildIteratorType; 645 646 static NodeType *getEntryNode(MachineBasicBlock *BB) { return BB; } 647 static inline ChildIteratorType child_begin(NodeType *N) { 648 return N->succ_begin(); 649 } 650 static inline ChildIteratorType child_end(NodeType *N) { 651 return N->succ_end(); 652 } 653}; 654 655template <> struct GraphTraits<const MachineBasicBlock *> { 656 typedef const MachineBasicBlock NodeType; 657 typedef MachineBasicBlock::const_succ_iterator ChildIteratorType; 658 659 static NodeType *getEntryNode(const MachineBasicBlock *BB) { return BB; } 660 static inline ChildIteratorType child_begin(NodeType *N) { 661 return N->succ_begin(); 662 } 663 static inline ChildIteratorType child_end(NodeType *N) { 664 return N->succ_end(); 665 } 666}; 667 668// Provide specializations of GraphTraits to be able to treat a 669// MachineFunction as a graph of MachineBasicBlocks... and to walk it 670// in inverse order. Inverse order for a function is considered 671// to be when traversing the predecessor edges of a MBB 672// instead of the successor edges. 673// 674template <> struct GraphTraits<Inverse<MachineBasicBlock*> > { 675 typedef MachineBasicBlock NodeType; 676 typedef MachineBasicBlock::pred_iterator ChildIteratorType; 677 static NodeType *getEntryNode(Inverse<MachineBasicBlock *> G) { 678 return G.Graph; 679 } 680 static inline ChildIteratorType child_begin(NodeType *N) { 681 return N->pred_begin(); 682 } 683 static inline ChildIteratorType child_end(NodeType *N) { 684 return N->pred_end(); 685 } 686}; 687 688template <> struct GraphTraits<Inverse<const MachineBasicBlock*> > { 689 typedef const MachineBasicBlock NodeType; 690 typedef MachineBasicBlock::const_pred_iterator ChildIteratorType; 691 static NodeType *getEntryNode(Inverse<const MachineBasicBlock*> G) { 692 return G.Graph; 693 } 694 static inline ChildIteratorType child_begin(NodeType *N) { 695 return N->pred_begin(); 696 } 697 static inline ChildIteratorType child_end(NodeType *N) { 698 return N->pred_end(); 699 } 700}; 701 702} // End llvm namespace 703 704#endif 705