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