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/ADT/GraphTraits.h" 18 #include "llvm/ADT/iterator_range.h" 19 #include "llvm/CodeGen/MachineInstrBundleIterator.h" 20 #include "llvm/CodeGen/MachineInstr.h" 21 #include "llvm/Support/BranchProbability.h" 22 #include "llvm/MC/MCRegisterInfo.h" 23 #include "llvm/Support/DataTypes.h" 24 #include <functional> 25 26 namespace llvm { 27 28 class Pass; 29 class BasicBlock; 30 class MachineFunction; 31 class MCSymbol; 32 class MIPrinter; 33 class SlotIndexes; 34 class StringRef; 35 class raw_ostream; 36 class MachineBranchProbabilityInfo; 37 38 // Forward declaration to avoid circular include problem with TargetRegisterInfo 39 typedef unsigned LaneBitmask; 40 41 template <> 42 struct ilist_traits<MachineInstr> : public ilist_default_traits<MachineInstr> { 43 private: 44 mutable ilist_half_node<MachineInstr> Sentinel; 45 46 // this is only set by the MachineBasicBlock owning the LiveList 47 friend class MachineBasicBlock; 48 MachineBasicBlock* Parent; 49 50 public: 51 MachineInstr *createSentinel() const { 52 return static_cast<MachineInstr*>(&Sentinel); 53 } 54 void destroySentinel(MachineInstr *) const {} 55 56 MachineInstr *provideInitialHead() const { return createSentinel(); } 57 MachineInstr *ensureHead(MachineInstr*) const { return createSentinel(); } 58 static void noteHead(MachineInstr*, MachineInstr*) {} 59 60 void addNodeToList(MachineInstr* N); 61 void removeNodeFromList(MachineInstr* N); 62 void transferNodesFromList(ilist_traits &SrcTraits, 63 ilist_iterator<MachineInstr> First, 64 ilist_iterator<MachineInstr> Last); 65 void deleteNode(MachineInstr *N); 66 private: 67 void createNode(const MachineInstr &); 68 }; 69 70 class MachineBasicBlock 71 : public ilist_node_with_parent<MachineBasicBlock, MachineFunction> { 72 public: 73 /// Pair of physical register and lane mask. 74 /// This is not simply a std::pair typedef because the members should be named 75 /// clearly as they both have an integer type. 76 struct RegisterMaskPair { 77 public: 78 MCPhysReg PhysReg; 79 LaneBitmask LaneMask; 80 81 RegisterMaskPair(MCPhysReg PhysReg, LaneBitmask LaneMask) 82 : PhysReg(PhysReg), LaneMask(LaneMask) {} 83 }; 84 85 private: 86 typedef ilist<MachineInstr> Instructions; 87 Instructions Insts; 88 const BasicBlock *BB; 89 int Number; 90 MachineFunction *xParent; 91 92 /// Keep track of the predecessor / successor basic blocks. 93 std::vector<MachineBasicBlock *> Predecessors; 94 std::vector<MachineBasicBlock *> Successors; 95 96 /// Keep track of the probabilities to the successors. This vector has the 97 /// same order as Successors, or it is empty if we don't use it (disable 98 /// optimization). 99 std::vector<BranchProbability> Probs; 100 typedef std::vector<BranchProbability>::iterator probability_iterator; 101 typedef std::vector<BranchProbability>::const_iterator 102 const_probability_iterator; 103 104 /// Keep track of the physical registers that are livein of the basicblock. 105 typedef std::vector<RegisterMaskPair> LiveInVector; 106 LiveInVector LiveIns; 107 108 /// Alignment of the basic block. Zero if the basic block does not need to be 109 /// aligned. The alignment is specified as log2(bytes). 110 unsigned Alignment = 0; 111 112 /// Indicate that this basic block is entered via an exception handler. 113 bool IsEHPad = false; 114 115 /// Indicate that this basic block is potentially the target of an indirect 116 /// branch. 117 bool AddressTaken = false; 118 119 /// Indicate that this basic block is the entry block of an EH funclet. 120 bool IsEHFuncletEntry = false; 121 122 /// Indicate that this basic block is the entry block of a cleanup funclet. 123 bool IsCleanupFuncletEntry = false; 124 125 /// \brief since getSymbol is a relatively heavy-weight operation, the symbol 126 /// is only computed once and is cached. 127 mutable MCSymbol *CachedMCSymbol = nullptr; 128 129 // Intrusive list support 130 MachineBasicBlock() {} 131 132 explicit MachineBasicBlock(MachineFunction &MF, const BasicBlock *BB); 133 134 ~MachineBasicBlock(); 135 136 // MachineBasicBlocks are allocated and owned by MachineFunction. 137 friend class MachineFunction; 138 139 public: 140 /// Return the LLVM basic block that this instance corresponded to originally. 141 /// Note that this may be NULL if this instance does not correspond directly 142 /// to an LLVM basic block. 143 const BasicBlock *getBasicBlock() const { return BB; } 144 145 /// Return the name of the corresponding LLVM basic block, or "(null)". 146 StringRef getName() const; 147 148 /// Return a formatted string to identify this block and its parent function. 149 std::string getFullName() const; 150 151 /// Test whether this block is potentially the target of an indirect branch. 152 bool hasAddressTaken() const { return AddressTaken; } 153 154 /// Set this block to reflect that it potentially is the target of an indirect 155 /// branch. 156 void setHasAddressTaken() { AddressTaken = true; } 157 158 /// Return the MachineFunction containing this basic block. 159 const MachineFunction *getParent() const { return xParent; } 160 MachineFunction *getParent() { return xParent; } 161 162 typedef Instructions::iterator instr_iterator; 163 typedef Instructions::const_iterator const_instr_iterator; 164 typedef std::reverse_iterator<instr_iterator> reverse_instr_iterator; 165 typedef 166 std::reverse_iterator<const_instr_iterator> const_reverse_instr_iterator; 167 168 typedef MachineInstrBundleIterator<MachineInstr> iterator; 169 typedef MachineInstrBundleIterator<const MachineInstr> const_iterator; 170 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 171 typedef std::reverse_iterator<iterator> reverse_iterator; 172 173 174 unsigned size() const { return (unsigned)Insts.size(); } 175 bool empty() const { return Insts.empty(); } 176 177 MachineInstr &instr_front() { return Insts.front(); } 178 MachineInstr &instr_back() { return Insts.back(); } 179 const MachineInstr &instr_front() const { return Insts.front(); } 180 const MachineInstr &instr_back() const { return Insts.back(); } 181 182 MachineInstr &front() { return Insts.front(); } 183 MachineInstr &back() { return *--end(); } 184 const MachineInstr &front() const { return Insts.front(); } 185 const MachineInstr &back() const { return *--end(); } 186 187 instr_iterator instr_begin() { return Insts.begin(); } 188 const_instr_iterator instr_begin() const { return Insts.begin(); } 189 instr_iterator instr_end() { return Insts.end(); } 190 const_instr_iterator instr_end() const { return Insts.end(); } 191 reverse_instr_iterator instr_rbegin() { return Insts.rbegin(); } 192 const_reverse_instr_iterator instr_rbegin() const { return Insts.rbegin(); } 193 reverse_instr_iterator instr_rend () { return Insts.rend(); } 194 const_reverse_instr_iterator instr_rend () const { return Insts.rend(); } 195 196 typedef iterator_range<instr_iterator> instr_range; 197 typedef iterator_range<const_instr_iterator> const_instr_range; 198 instr_range instrs() { return instr_range(instr_begin(), instr_end()); } 199 const_instr_range instrs() const { 200 return const_instr_range(instr_begin(), instr_end()); 201 } 202 203 iterator begin() { return instr_begin(); } 204 const_iterator begin() const { return instr_begin(); } 205 iterator end () { return instr_end(); } 206 const_iterator end () const { return instr_end(); } 207 reverse_iterator rbegin() { return instr_rbegin(); } 208 const_reverse_iterator rbegin() const { return instr_rbegin(); } 209 reverse_iterator rend () { return instr_rend(); } 210 const_reverse_iterator rend () const { return instr_rend(); } 211 212 /// Support for MachineInstr::getNextNode(). 213 static Instructions MachineBasicBlock::*getSublistAccess(MachineInstr *) { 214 return &MachineBasicBlock::Insts; 215 } 216 217 inline iterator_range<iterator> terminators() { 218 return make_range(getFirstTerminator(), end()); 219 } 220 inline iterator_range<const_iterator> terminators() const { 221 return make_range(getFirstTerminator(), end()); 222 } 223 224 // Machine-CFG iterators 225 typedef std::vector<MachineBasicBlock *>::iterator pred_iterator; 226 typedef std::vector<MachineBasicBlock *>::const_iterator const_pred_iterator; 227 typedef std::vector<MachineBasicBlock *>::iterator succ_iterator; 228 typedef std::vector<MachineBasicBlock *>::const_iterator const_succ_iterator; 229 typedef std::vector<MachineBasicBlock *>::reverse_iterator 230 pred_reverse_iterator; 231 typedef std::vector<MachineBasicBlock *>::const_reverse_iterator 232 const_pred_reverse_iterator; 233 typedef std::vector<MachineBasicBlock *>::reverse_iterator 234 succ_reverse_iterator; 235 typedef std::vector<MachineBasicBlock *>::const_reverse_iterator 236 const_succ_reverse_iterator; 237 pred_iterator pred_begin() { return Predecessors.begin(); } 238 const_pred_iterator pred_begin() const { return Predecessors.begin(); } 239 pred_iterator pred_end() { return Predecessors.end(); } 240 const_pred_iterator pred_end() const { return Predecessors.end(); } 241 pred_reverse_iterator pred_rbegin() 242 { return Predecessors.rbegin();} 243 const_pred_reverse_iterator pred_rbegin() const 244 { return Predecessors.rbegin();} 245 pred_reverse_iterator pred_rend() 246 { return Predecessors.rend(); } 247 const_pred_reverse_iterator pred_rend() const 248 { return Predecessors.rend(); } 249 unsigned pred_size() const { 250 return (unsigned)Predecessors.size(); 251 } 252 bool pred_empty() const { return Predecessors.empty(); } 253 succ_iterator succ_begin() { return Successors.begin(); } 254 const_succ_iterator succ_begin() const { return Successors.begin(); } 255 succ_iterator succ_end() { return Successors.end(); } 256 const_succ_iterator succ_end() const { return Successors.end(); } 257 succ_reverse_iterator succ_rbegin() 258 { return Successors.rbegin(); } 259 const_succ_reverse_iterator succ_rbegin() const 260 { return Successors.rbegin(); } 261 succ_reverse_iterator succ_rend() 262 { return Successors.rend(); } 263 const_succ_reverse_iterator succ_rend() const 264 { return Successors.rend(); } 265 unsigned succ_size() const { 266 return (unsigned)Successors.size(); 267 } 268 bool succ_empty() const { return Successors.empty(); } 269 270 inline iterator_range<pred_iterator> predecessors() { 271 return make_range(pred_begin(), pred_end()); 272 } 273 inline iterator_range<const_pred_iterator> predecessors() const { 274 return make_range(pred_begin(), pred_end()); 275 } 276 inline iterator_range<succ_iterator> successors() { 277 return make_range(succ_begin(), succ_end()); 278 } 279 inline iterator_range<const_succ_iterator> successors() const { 280 return make_range(succ_begin(), succ_end()); 281 } 282 283 // LiveIn management methods. 284 285 /// Adds the specified register as a live in. Note that it is an error to add 286 /// the same register to the same set more than once unless the intention is 287 /// to call sortUniqueLiveIns after all registers are added. 288 void addLiveIn(MCPhysReg PhysReg, LaneBitmask LaneMask = ~0u) { 289 LiveIns.push_back(RegisterMaskPair(PhysReg, LaneMask)); 290 } 291 void addLiveIn(const RegisterMaskPair &RegMaskPair) { 292 LiveIns.push_back(RegMaskPair); 293 } 294 295 /// Sorts and uniques the LiveIns vector. It can be significantly faster to do 296 /// this than repeatedly calling isLiveIn before calling addLiveIn for every 297 /// LiveIn insertion. 298 void sortUniqueLiveIns(); 299 300 /// Add PhysReg as live in to this block, and ensure that there is a copy of 301 /// PhysReg to a virtual register of class RC. Return the virtual register 302 /// that is a copy of the live in PhysReg. 303 unsigned addLiveIn(MCPhysReg PhysReg, const TargetRegisterClass *RC); 304 305 /// Remove the specified register from the live in set. 306 void removeLiveIn(MCPhysReg Reg, LaneBitmask LaneMask = ~0u); 307 308 /// Return true if the specified register is in the live in set. 309 bool isLiveIn(MCPhysReg Reg, LaneBitmask LaneMask = ~0u) const; 310 311 // Iteration support for live in sets. These sets are kept in sorted 312 // order by their register number. 313 typedef LiveInVector::const_iterator livein_iterator; 314 livein_iterator livein_begin() const { return LiveIns.begin(); } 315 livein_iterator livein_end() const { return LiveIns.end(); } 316 bool livein_empty() const { return LiveIns.empty(); } 317 iterator_range<livein_iterator> liveins() const { 318 return make_range(livein_begin(), livein_end()); 319 } 320 321 /// Get the clobber mask for the start of this basic block. Funclets use this 322 /// to prevent register allocation across funclet transitions. 323 const uint32_t *getBeginClobberMask(const TargetRegisterInfo *TRI) const; 324 325 /// Get the clobber mask for the end of the basic block. 326 /// \see getBeginClobberMask() 327 const uint32_t *getEndClobberMask(const TargetRegisterInfo *TRI) const; 328 329 /// Return alignment of the basic block. The alignment is specified as 330 /// log2(bytes). 331 unsigned getAlignment() const { return Alignment; } 332 333 /// Set alignment of the basic block. The alignment is specified as 334 /// log2(bytes). 335 void setAlignment(unsigned Align) { Alignment = Align; } 336 337 /// Returns true if the block is a landing pad. That is this basic block is 338 /// entered via an exception handler. 339 bool isEHPad() const { return IsEHPad; } 340 341 /// Indicates the block is a landing pad. That is this basic block is entered 342 /// via an exception handler. 343 void setIsEHPad(bool V = true) { IsEHPad = V; } 344 345 bool hasEHPadSuccessor() const; 346 347 /// Returns true if this is the entry block of an EH funclet. 348 bool isEHFuncletEntry() const { return IsEHFuncletEntry; } 349 350 /// Indicates if this is the entry block of an EH funclet. 351 void setIsEHFuncletEntry(bool V = true) { IsEHFuncletEntry = V; } 352 353 /// Returns true if this is the entry block of a cleanup funclet. 354 bool isCleanupFuncletEntry() const { return IsCleanupFuncletEntry; } 355 356 /// Indicates if this is the entry block of a cleanup funclet. 357 void setIsCleanupFuncletEntry(bool V = true) { IsCleanupFuncletEntry = V; } 358 359 // Code Layout methods. 360 361 /// Move 'this' block before or after the specified block. This only moves 362 /// the block, it does not modify the CFG or adjust potential fall-throughs at 363 /// the end of the block. 364 void moveBefore(MachineBasicBlock *NewAfter); 365 void moveAfter(MachineBasicBlock *NewBefore); 366 367 /// Update the terminator instructions in block to account for changes to the 368 /// layout. If the block previously used a fallthrough, it may now need a 369 /// branch, and if it previously used branching it may now be able to use a 370 /// fallthrough. 371 void updateTerminator(); 372 373 // Machine-CFG mutators 374 375 /// Add Succ as a successor of this MachineBasicBlock. The Predecessors list 376 /// of Succ is automatically updated. PROB parameter is stored in 377 /// Probabilities list. The default probability is set as unknown. Mixing 378 /// known and unknown probabilities in successor list is not allowed. When all 379 /// successors have unknown probabilities, 1 / N is returned as the 380 /// probability for each successor, where N is the number of successors. 381 /// 382 /// Note that duplicate Machine CFG edges are not allowed. 383 void addSuccessor(MachineBasicBlock *Succ, 384 BranchProbability Prob = BranchProbability::getUnknown()); 385 386 /// Add Succ as a successor of this MachineBasicBlock. The Predecessors list 387 /// of Succ is automatically updated. The probability is not provided because 388 /// BPI is not available (e.g. -O0 is used), in which case edge probabilities 389 /// won't be used. Using this interface can save some space. 390 void addSuccessorWithoutProb(MachineBasicBlock *Succ); 391 392 /// Set successor probability of a given iterator. 393 void setSuccProbability(succ_iterator I, BranchProbability Prob); 394 395 /// Normalize probabilities of all successors so that the sum of them becomes 396 /// one. This is usually done when the current update on this MBB is done, and 397 /// the sum of its successors' probabilities is not guaranteed to be one. The 398 /// user is responsible for the correct use of this function. 399 /// MBB::removeSuccessor() has an option to do this automatically. 400 void normalizeSuccProbs() { 401 BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end()); 402 } 403 404 /// Validate successors' probabilities and check if the sum of them is 405 /// approximate one. This only works in DEBUG mode. 406 void validateSuccProbs() const; 407 408 /// Remove successor from the successors list of this MachineBasicBlock. The 409 /// Predecessors list of Succ is automatically updated. 410 /// If NormalizeSuccProbs is true, then normalize successors' probabilities 411 /// after the successor is removed. 412 void removeSuccessor(MachineBasicBlock *Succ, 413 bool NormalizeSuccProbs = false); 414 415 /// Remove specified successor from the successors list of this 416 /// MachineBasicBlock. The Predecessors list of Succ is automatically updated. 417 /// If NormalizeSuccProbs is true, then normalize successors' probabilities 418 /// after the successor is removed. 419 /// Return the iterator to the element after the one removed. 420 succ_iterator removeSuccessor(succ_iterator I, 421 bool NormalizeSuccProbs = false); 422 423 /// Replace successor OLD with NEW and update probability info. 424 void replaceSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New); 425 426 /// Transfers all the successors from MBB to this machine basic block (i.e., 427 /// copies all the successors FromMBB and remove all the successors from 428 /// FromMBB). 429 void transferSuccessors(MachineBasicBlock *FromMBB); 430 431 /// Transfers all the successors, as in transferSuccessors, and update PHI 432 /// operands in the successor blocks which refer to FromMBB to refer to this. 433 void transferSuccessorsAndUpdatePHIs(MachineBasicBlock *FromMBB); 434 435 /// Return true if any of the successors have probabilities attached to them. 436 bool hasSuccessorProbabilities() const { return !Probs.empty(); } 437 438 /// Return true if the specified MBB is a predecessor of this block. 439 bool isPredecessor(const MachineBasicBlock *MBB) const; 440 441 /// Return true if the specified MBB is a successor of this block. 442 bool isSuccessor(const MachineBasicBlock *MBB) const; 443 444 /// Return true if the specified MBB will be emitted immediately after this 445 /// block, such that if this block exits by falling through, control will 446 /// transfer to the specified MBB. Note that MBB need not be a successor at 447 /// all, for example if this block ends with an unconditional branch to some 448 /// other block. 449 bool isLayoutSuccessor(const MachineBasicBlock *MBB) const; 450 451 /// Return true if the block can implicitly transfer control to the block 452 /// after it by falling off the end of it. This should return false if it can 453 /// reach the block after it, but it uses an explicit branch to do so (e.g., a 454 /// table jump). True is a conservative answer. 455 bool canFallThrough(); 456 457 /// Returns a pointer to the first instruction in this block that is not a 458 /// PHINode instruction. When adding instructions to the beginning of the 459 /// basic block, they should be added before the returned value, not before 460 /// the first instruction, which might be PHI. 461 /// Returns end() is there's no non-PHI instruction. 462 iterator getFirstNonPHI(); 463 464 /// Return the first instruction in MBB after I that is not a PHI or a label. 465 /// This is the correct point to insert copies at the beginning of a basic 466 /// block. 467 iterator SkipPHIsAndLabels(iterator I); 468 469 /// Returns an iterator to the first terminator instruction of this basic 470 /// block. If a terminator does not exist, it returns end(). 471 iterator getFirstTerminator(); 472 const_iterator getFirstTerminator() const { 473 return const_cast<MachineBasicBlock *>(this)->getFirstTerminator(); 474 } 475 476 /// Same getFirstTerminator but it ignores bundles and return an 477 /// instr_iterator instead. 478 instr_iterator getFirstInstrTerminator(); 479 480 /// Returns an iterator to the first non-debug instruction in the basic block, 481 /// or end(). 482 iterator getFirstNonDebugInstr(); 483 const_iterator getFirstNonDebugInstr() const { 484 return const_cast<MachineBasicBlock *>(this)->getFirstNonDebugInstr(); 485 } 486 487 /// Returns an iterator to the last non-debug instruction in the basic block, 488 /// or end(). 489 iterator getLastNonDebugInstr(); 490 const_iterator getLastNonDebugInstr() const { 491 return const_cast<MachineBasicBlock *>(this)->getLastNonDebugInstr(); 492 } 493 494 /// Convenience function that returns true if the block ends in a return 495 /// instruction. 496 bool isReturnBlock() const { 497 return !empty() && back().isReturn(); 498 } 499 500 /// Split the critical edge from this block to the given successor block, and 501 /// return the newly created block, or null if splitting is not possible. 502 /// 503 /// This function updates LiveVariables, MachineDominatorTree, and 504 /// MachineLoopInfo, as applicable. 505 MachineBasicBlock *SplitCriticalEdge(MachineBasicBlock *Succ, Pass &P); 506 507 /// Check if the edge between this block and the given successor \p 508 /// Succ, can be split. If this returns true a subsequent call to 509 /// SplitCriticalEdge is guaranteed to return a valid basic block if 510 /// no changes occured in the meantime. 511 bool canSplitCriticalEdge(const MachineBasicBlock *Succ) const; 512 513 void pop_front() { Insts.pop_front(); } 514 void pop_back() { Insts.pop_back(); } 515 void push_back(MachineInstr *MI) { Insts.push_back(MI); } 516 517 /// Insert MI into the instruction list before I, possibly inside a bundle. 518 /// 519 /// If the insertion point is inside a bundle, MI will be added to the bundle, 520 /// otherwise MI will not be added to any bundle. That means this function 521 /// alone can't be used to prepend or append instructions to bundles. See 522 /// MIBundleBuilder::insert() for a more reliable way of doing that. 523 instr_iterator insert(instr_iterator I, MachineInstr *M); 524 525 /// Insert a range of instructions into the instruction list before I. 526 template<typename IT> 527 void insert(iterator I, IT S, IT E) { 528 assert((I == end() || I->getParent() == this) && 529 "iterator points outside of basic block"); 530 Insts.insert(I.getInstrIterator(), S, E); 531 } 532 533 /// Insert MI into the instruction list before I. 534 iterator insert(iterator I, MachineInstr *MI) { 535 assert((I == end() || I->getParent() == this) && 536 "iterator points outside of basic block"); 537 assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() && 538 "Cannot insert instruction with bundle flags"); 539 return Insts.insert(I.getInstrIterator(), MI); 540 } 541 542 /// Insert MI into the instruction list after I. 543 iterator insertAfter(iterator I, MachineInstr *MI) { 544 assert((I == end() || I->getParent() == this) && 545 "iterator points outside of basic block"); 546 assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() && 547 "Cannot insert instruction with bundle flags"); 548 return Insts.insertAfter(I.getInstrIterator(), MI); 549 } 550 551 /// Remove an instruction from the instruction list and delete it. 552 /// 553 /// If the instruction is part of a bundle, the other instructions in the 554 /// bundle will still be bundled after removing the single instruction. 555 instr_iterator erase(instr_iterator I); 556 557 /// Remove an instruction from the instruction list and delete it. 558 /// 559 /// If the instruction is part of a bundle, the other instructions in the 560 /// bundle will still be bundled after removing the single instruction. 561 instr_iterator erase_instr(MachineInstr *I) { 562 return erase(instr_iterator(I)); 563 } 564 565 /// Remove a range of instructions from the instruction list and delete them. 566 iterator erase(iterator I, iterator E) { 567 return Insts.erase(I.getInstrIterator(), E.getInstrIterator()); 568 } 569 570 /// Remove an instruction or bundle from the instruction list and delete it. 571 /// 572 /// If I points to a bundle of instructions, they are all erased. 573 iterator erase(iterator I) { 574 return erase(I, std::next(I)); 575 } 576 577 /// Remove an instruction from the instruction list and delete it. 578 /// 579 /// If I is the head of a bundle of instructions, the whole bundle will be 580 /// erased. 581 iterator erase(MachineInstr *I) { 582 return erase(iterator(I)); 583 } 584 585 /// Remove the unbundled instruction from the instruction list without 586 /// deleting it. 587 /// 588 /// This function can not be used to remove bundled instructions, use 589 /// remove_instr to remove individual instructions from a bundle. 590 MachineInstr *remove(MachineInstr *I) { 591 assert(!I->isBundled() && "Cannot remove bundled instructions"); 592 return Insts.remove(instr_iterator(I)); 593 } 594 595 /// Remove the possibly bundled instruction from the instruction list 596 /// without deleting it. 597 /// 598 /// If the instruction is part of a bundle, the other instructions in the 599 /// bundle will still be bundled after removing the single instruction. 600 MachineInstr *remove_instr(MachineInstr *I); 601 602 void clear() { 603 Insts.clear(); 604 } 605 606 /// Take an instruction from MBB 'Other' at the position From, and insert it 607 /// into this MBB right before 'Where'. 608 /// 609 /// If From points to a bundle of instructions, the whole bundle is moved. 610 void splice(iterator Where, MachineBasicBlock *Other, iterator From) { 611 // The range splice() doesn't allow noop moves, but this one does. 612 if (Where != From) 613 splice(Where, Other, From, std::next(From)); 614 } 615 616 /// Take a block of instructions from MBB 'Other' in the range [From, To), 617 /// and insert them into this MBB right before 'Where'. 618 /// 619 /// The instruction at 'Where' must not be included in the range of 620 /// instructions to move. 621 void splice(iterator Where, MachineBasicBlock *Other, 622 iterator From, iterator To) { 623 Insts.splice(Where.getInstrIterator(), Other->Insts, 624 From.getInstrIterator(), To.getInstrIterator()); 625 } 626 627 /// This method unlinks 'this' from the containing function, and returns it, 628 /// but does not delete it. 629 MachineBasicBlock *removeFromParent(); 630 631 /// This method unlinks 'this' from the containing function and deletes it. 632 void eraseFromParent(); 633 634 /// Given a machine basic block that branched to 'Old', change the code and 635 /// CFG so that it branches to 'New' instead. 636 void ReplaceUsesOfBlockWith(MachineBasicBlock *Old, MachineBasicBlock *New); 637 638 /// Various pieces of code can cause excess edges in the CFG to be inserted. 639 /// If we have proven that MBB can only branch to DestA and DestB, remove any 640 /// other MBB successors from the CFG. DestA and DestB can be null. Besides 641 /// DestA and DestB, retain other edges leading to LandingPads (currently 642 /// there can be only one; we don't check or require that here). Note it is 643 /// possible that DestA and/or DestB are LandingPads. 644 bool CorrectExtraCFGEdges(MachineBasicBlock *DestA, 645 MachineBasicBlock *DestB, 646 bool IsCond); 647 648 /// Find the next valid DebugLoc starting at MBBI, skipping any DBG_VALUE 649 /// instructions. Return UnknownLoc if there is none. 650 DebugLoc findDebugLoc(instr_iterator MBBI); 651 DebugLoc findDebugLoc(iterator MBBI) { 652 return findDebugLoc(MBBI.getInstrIterator()); 653 } 654 655 /// Possible outcome of a register liveness query to computeRegisterLiveness() 656 enum LivenessQueryResult { 657 LQR_Live, ///< Register is known to be (at least partially) live. 658 LQR_Dead, ///< Register is known to be fully dead. 659 LQR_Unknown ///< Register liveness not decidable from local neighborhood. 660 }; 661 662 /// Return whether (physical) register \p Reg has been <def>ined and not 663 /// <kill>ed as of just before \p Before. 664 /// 665 /// Search is localised to a neighborhood of \p Neighborhood instructions 666 /// before (searching for defs or kills) and \p Neighborhood instructions 667 /// after (searching just for defs) \p Before. 668 /// 669 /// \p Reg must be a physical register. 670 LivenessQueryResult computeRegisterLiveness(const TargetRegisterInfo *TRI, 671 unsigned Reg, 672 const_iterator Before, 673 unsigned Neighborhood=10) const; 674 675 // Debugging methods. 676 void dump() const; 677 void print(raw_ostream &OS, const SlotIndexes* = nullptr) const; 678 void print(raw_ostream &OS, ModuleSlotTracker &MST, 679 const SlotIndexes* = nullptr) const; 680 681 // Printing method used by LoopInfo. 682 void printAsOperand(raw_ostream &OS, bool PrintType = true) const; 683 684 /// MachineBasicBlocks are uniquely numbered at the function level, unless 685 /// they're not in a MachineFunction yet, in which case this will return -1. 686 int getNumber() const { return Number; } 687 void setNumber(int N) { Number = N; } 688 689 /// Return the MCSymbol for this basic block. 690 MCSymbol *getSymbol() const; 691 692 693 private: 694 /// Return probability iterator corresponding to the I successor iterator. 695 probability_iterator getProbabilityIterator(succ_iterator I); 696 const_probability_iterator 697 getProbabilityIterator(const_succ_iterator I) const; 698 699 friend class MachineBranchProbabilityInfo; 700 friend class MIPrinter; 701 702 /// Return probability of the edge from this block to MBB. This method should 703 /// NOT be called directly, but by using getEdgeProbability method from 704 /// MachineBranchProbabilityInfo class. 705 BranchProbability getSuccProbability(const_succ_iterator Succ) const; 706 707 // Methods used to maintain doubly linked list of blocks... 708 friend struct ilist_traits<MachineBasicBlock>; 709 710 // Machine-CFG mutators 711 712 /// Remove Pred as a predecessor of this MachineBasicBlock. Don't do this 713 /// unless you know what you're doing, because it doesn't update Pred's 714 /// successors list. Use Pred->addSuccessor instead. 715 void addPredecessor(MachineBasicBlock *Pred); 716 717 /// Remove Pred as a predecessor of this MachineBasicBlock. Don't do this 718 /// unless you know what you're doing, because it doesn't update Pred's 719 /// successors list. Use Pred->removeSuccessor instead. 720 void removePredecessor(MachineBasicBlock *Pred); 721 }; 722 723 raw_ostream& operator<<(raw_ostream &OS, const MachineBasicBlock &MBB); 724 725 // This is useful when building IndexedMaps keyed on basic block pointers. 726 struct MBB2NumberFunctor : 727 public std::unary_function<const MachineBasicBlock*, unsigned> { 728 unsigned operator()(const MachineBasicBlock *MBB) const { 729 return MBB->getNumber(); 730 } 731 }; 732 733 //===--------------------------------------------------------------------===// 734 // GraphTraits specializations for machine basic block graphs (machine-CFGs) 735 //===--------------------------------------------------------------------===// 736 737 // Provide specializations of GraphTraits to be able to treat a 738 // MachineFunction as a graph of MachineBasicBlocks. 739 // 740 741 template <> struct GraphTraits<MachineBasicBlock *> { 742 typedef MachineBasicBlock NodeType; 743 typedef MachineBasicBlock::succ_iterator ChildIteratorType; 744 745 static NodeType *getEntryNode(MachineBasicBlock *BB) { return BB; } 746 static inline ChildIteratorType child_begin(NodeType *N) { 747 return N->succ_begin(); 748 } 749 static inline ChildIteratorType child_end(NodeType *N) { 750 return N->succ_end(); 751 } 752 }; 753 754 template <> struct GraphTraits<const MachineBasicBlock *> { 755 typedef const MachineBasicBlock NodeType; 756 typedef MachineBasicBlock::const_succ_iterator ChildIteratorType; 757 758 static NodeType *getEntryNode(const MachineBasicBlock *BB) { return BB; } 759 static inline ChildIteratorType child_begin(NodeType *N) { 760 return N->succ_begin(); 761 } 762 static inline ChildIteratorType child_end(NodeType *N) { 763 return N->succ_end(); 764 } 765 }; 766 767 // Provide specializations of GraphTraits to be able to treat a 768 // MachineFunction as a graph of MachineBasicBlocks and to walk it 769 // in inverse order. Inverse order for a function is considered 770 // to be when traversing the predecessor edges of a MBB 771 // instead of the successor edges. 772 // 773 template <> struct GraphTraits<Inverse<MachineBasicBlock*> > { 774 typedef MachineBasicBlock NodeType; 775 typedef MachineBasicBlock::pred_iterator ChildIteratorType; 776 static NodeType *getEntryNode(Inverse<MachineBasicBlock *> G) { 777 return G.Graph; 778 } 779 static inline ChildIteratorType child_begin(NodeType *N) { 780 return N->pred_begin(); 781 } 782 static inline ChildIteratorType child_end(NodeType *N) { 783 return N->pred_end(); 784 } 785 }; 786 787 template <> struct GraphTraits<Inverse<const MachineBasicBlock*> > { 788 typedef const MachineBasicBlock NodeType; 789 typedef MachineBasicBlock::const_pred_iterator ChildIteratorType; 790 static NodeType *getEntryNode(Inverse<const MachineBasicBlock*> G) { 791 return G.Graph; 792 } 793 static inline ChildIteratorType child_begin(NodeType *N) { 794 return N->pred_begin(); 795 } 796 static inline ChildIteratorType child_end(NodeType *N) { 797 return N->pred_end(); 798 } 799 }; 800 801 802 803 /// MachineInstrSpan provides an interface to get an iteration range 804 /// containing the instruction it was initialized with, along with all 805 /// those instructions inserted prior to or following that instruction 806 /// at some point after the MachineInstrSpan is constructed. 807 class MachineInstrSpan { 808 MachineBasicBlock &MBB; 809 MachineBasicBlock::iterator I, B, E; 810 public: 811 MachineInstrSpan(MachineBasicBlock::iterator I) 812 : MBB(*I->getParent()), 813 I(I), 814 B(I == MBB.begin() ? MBB.end() : std::prev(I)), 815 E(std::next(I)) {} 816 817 MachineBasicBlock::iterator begin() { 818 return B == MBB.end() ? MBB.begin() : std::next(B); 819 } 820 MachineBasicBlock::iterator end() { return E; } 821 bool empty() { return begin() == end(); } 822 823 MachineBasicBlock::iterator getInitial() { return I; } 824 }; 825 826 } // End llvm namespace 827 828 #endif 829