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