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