1 //===- llvm/BasicBlock.h - Represent a basic block in the VM ----*- 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 // This file contains the declaration of the BasicBlock class. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #ifndef LLVM_IR_BASICBLOCK_H 14 #define LLVM_IR_BASICBLOCK_H 15 16 #include "llvm-c/Types.h" 17 #include "llvm/ADT/Twine.h" 18 #include "llvm/ADT/ilist.h" 19 #include "llvm/ADT/ilist_node.h" 20 #include "llvm/ADT/iterator.h" 21 #include "llvm/ADT/iterator_range.h" 22 #include "llvm/IR/DebugProgramInstruction.h" 23 #include "llvm/IR/Instruction.h" 24 #include "llvm/IR/DebugProgramInstruction.h" 25 #include "llvm/IR/SymbolTableListTraits.h" 26 #include "llvm/IR/Value.h" 27 #include <cassert> 28 #include <cstddef> 29 #include <iterator> 30 31 namespace llvm { 32 33 class AssemblyAnnotationWriter; 34 class CallInst; 35 class Function; 36 class LandingPadInst; 37 class LLVMContext; 38 class Module; 39 class PHINode; 40 class ValueSymbolTable; 41 class DPValue; 42 class DPMarker; 43 44 /// LLVM Basic Block Representation 45 /// 46 /// This represents a single basic block in LLVM. A basic block is simply a 47 /// container of instructions that execute sequentially. Basic blocks are Values 48 /// because they are referenced by instructions such as branches and switch 49 /// tables. The type of a BasicBlock is "Type::LabelTy" because the basic block 50 /// represents a label to which a branch can jump. 51 /// 52 /// A well formed basic block is formed of a list of non-terminating 53 /// instructions followed by a single terminator instruction. Terminator 54 /// instructions may not occur in the middle of basic blocks, and must terminate 55 /// the blocks. The BasicBlock class allows malformed basic blocks to occur 56 /// because it may be useful in the intermediate stage of constructing or 57 /// modifying a program. However, the verifier will ensure that basic blocks are 58 /// "well formed". 59 class BasicBlock final : public Value, // Basic blocks are data objects also 60 public ilist_node_with_parent<BasicBlock, Function> { 61 public: 62 using InstListType = SymbolTableList<Instruction, ilist_iterator_bits<true>>; 63 /// Flag recording whether or not this block stores debug-info in the form 64 /// of intrinsic instructions (false) or non-instruction records (true). 65 bool IsNewDbgInfoFormat; 66 67 private: 68 friend class BlockAddress; 69 friend class SymbolTableListTraits<BasicBlock>; 70 71 InstListType InstList; 72 Function *Parent; 73 74 public: 75 /// Attach a DPMarker to the given instruction. Enables the storage of any 76 /// debug-info at this position in the program. 77 DPMarker *createMarker(Instruction *I); 78 DPMarker *createMarker(InstListType::iterator It); 79 80 /// Convert variable location debugging information stored in dbg.value 81 /// intrinsics into DPMarker / DPValue records. Deletes all dbg.values in 82 /// the process and sets IsNewDbgInfoFormat = true. Only takes effect if 83 /// the UseNewDbgInfoFormat LLVM command line option is given. 84 void convertToNewDbgValues(); 85 86 /// Convert variable location debugging information stored in DPMarkers and 87 /// DPValues into the dbg.value intrinsic representation. Sets 88 /// IsNewDbgInfoFormat = false. 89 void convertFromNewDbgValues(); 90 91 /// Ensure the block is in "old" dbg.value format (\p NewFlag == false) or 92 /// in the new format (\p NewFlag == true), converting to the desired format 93 /// if necessary. 94 void setIsNewDbgInfoFormat(bool NewFlag); 95 96 /// Validate any DPMarkers / DPValues attached to instructions in this block, 97 /// and block-level stored data too (TrailingDPValues). 98 /// \p Assert Should this method fire an assertion if a problem is found? 99 /// \p Msg Should this method print a message to errs() if a problem is found? 100 /// \p OS Output stream to write errors to. 101 /// \returns True if a problem is found. 102 bool validateDbgValues(bool Assert = true, bool Msg = false, 103 raw_ostream *OS = nullptr); 104 105 /// Record that the collection of DPValues in \p M "trails" after the last 106 /// instruction of this block. These are equivalent to dbg.value intrinsics 107 /// that exist at the end of a basic block with no terminator (a transient 108 /// state that occurs regularly). 109 void setTrailingDPValues(DPMarker *M); 110 111 /// Fetch the collection of DPValues that "trail" after the last instruction 112 /// of this block, see \ref setTrailingDPValues. If there are none, returns 113 /// nullptr. 114 DPMarker *getTrailingDPValues(); 115 116 /// Delete any trailing DPValues at the end of this block, see 117 /// \ref setTrailingDPValues. 118 void deleteTrailingDPValues(); 119 120 void dumpDbgValues() const; 121 122 /// Return the DPMarker for the position given by \p It, so that DPValues can 123 /// be inserted there. This will either be nullptr if not present, a DPMarker, 124 /// or TrailingDPValues if It is end(). 125 DPMarker *getMarker(InstListType::iterator It); 126 127 /// Return the DPMarker for the position that comes after \p I. \see 128 /// BasicBlock::getMarker, this can be nullptr, a DPMarker, or 129 /// TrailingDPValues if there is no next instruction. 130 DPMarker *getNextMarker(Instruction *I); 131 132 /// Insert a DPValue into a block at the position given by \p I. 133 void insertDPValueAfter(DPValue *DPV, Instruction *I); 134 135 /// Insert a DPValue into a block at the position given by \p Here. 136 void insertDPValueBefore(DPValue *DPV, InstListType::iterator Here); 137 138 /// Eject any debug-info trailing at the end of a block. DPValues can 139 /// transiently be located "off the end" of a block if the blocks terminator 140 /// is temporarily removed. Once a terminator is re-inserted this method will 141 /// move such DPValues back to the right place (ahead of the terminator). 142 void flushTerminatorDbgValues(); 143 144 /// In rare circumstances instructions can be speculatively removed from 145 /// blocks, and then be re-inserted back into that position later. When this 146 /// happens in RemoveDIs debug-info mode, some special patching-up needs to 147 /// occur: inserting into the middle of a sequence of dbg.value intrinsics 148 /// does not have an equivalent with DPValues. 149 void reinsertInstInDPValues(Instruction *I, 150 std::optional<DPValue::self_iterator> Pos); 151 152 private: 153 void setParent(Function *parent); 154 155 /// Constructor. 156 /// 157 /// If the function parameter is specified, the basic block is automatically 158 /// inserted at either the end of the function (if InsertBefore is null), or 159 /// before the specified basic block. 160 explicit BasicBlock(LLVMContext &C, const Twine &Name = "", 161 Function *Parent = nullptr, 162 BasicBlock *InsertBefore = nullptr); 163 164 public: 165 BasicBlock(const BasicBlock &) = delete; 166 BasicBlock &operator=(const BasicBlock &) = delete; 167 ~BasicBlock(); 168 169 /// Get the context in which this basic block lives. 170 LLVMContext &getContext() const; 171 172 /// Instruction iterators... 173 using iterator = InstListType::iterator; 174 using const_iterator = InstListType::const_iterator; 175 using reverse_iterator = InstListType::reverse_iterator; 176 using const_reverse_iterator = InstListType::const_reverse_iterator; 177 178 // These functions and classes need access to the instruction list. 179 friend void Instruction::removeFromParent(); 180 friend BasicBlock::iterator Instruction::eraseFromParent(); 181 friend BasicBlock::iterator Instruction::insertInto(BasicBlock *BB, 182 BasicBlock::iterator It); 183 friend class llvm::SymbolTableListTraits<llvm::Instruction, 184 ilist_iterator_bits<true>>; 185 friend class llvm::ilist_node_with_parent<llvm::Instruction, llvm::BasicBlock, 186 ilist_iterator_bits<true>>; 187 188 // Friendly methods that need to access us for the maintenence of 189 // debug-info attachments. 190 friend void Instruction::insertBefore(BasicBlock::iterator InsertPos); 191 friend void Instruction::insertAfter(Instruction *InsertPos); 192 friend void Instruction::insertBefore(BasicBlock &BB, 193 InstListType::iterator InsertPos); 194 friend void Instruction::moveBeforeImpl(BasicBlock &BB, 195 InstListType::iterator I, 196 bool Preserve); 197 friend iterator_range<DPValue::self_iterator> Instruction::cloneDebugInfoFrom( 198 const Instruction *From, std::optional<DPValue::self_iterator> FromHere, 199 bool InsertAtHead); 200 201 /// Creates a new BasicBlock. 202 /// 203 /// If the Parent parameter is specified, the basic block is automatically 204 /// inserted at either the end of the function (if InsertBefore is 0), or 205 /// before the specified basic block. 206 static BasicBlock *Create(LLVMContext &Context, const Twine &Name = "", 207 Function *Parent = nullptr, 208 BasicBlock *InsertBefore = nullptr) { 209 return new BasicBlock(Context, Name, Parent, InsertBefore); 210 } 211 212 /// Return the enclosing method, or null if none. 213 const Function *getParent() const { return Parent; } 214 Function *getParent() { return Parent; } 215 216 /// Return the module owning the function this basic block belongs to, or 217 /// nullptr if the function does not have a module. 218 /// 219 /// Note: this is undefined behavior if the block does not have a parent. 220 const Module *getModule() const; 221 Module *getModule() { 222 return const_cast<Module *>( 223 static_cast<const BasicBlock *>(this)->getModule()); 224 } 225 226 /// Returns the terminator instruction if the block is well formed or null 227 /// if the block is not well formed. 228 const Instruction *getTerminator() const LLVM_READONLY { 229 if (InstList.empty() || !InstList.back().isTerminator()) 230 return nullptr; 231 return &InstList.back(); 232 } 233 Instruction *getTerminator() { 234 return const_cast<Instruction *>( 235 static_cast<const BasicBlock *>(this)->getTerminator()); 236 } 237 238 /// Returns the call instruction calling \@llvm.experimental.deoptimize 239 /// prior to the terminating return instruction of this basic block, if such 240 /// a call is present. Otherwise, returns null. 241 const CallInst *getTerminatingDeoptimizeCall() const; 242 CallInst *getTerminatingDeoptimizeCall() { 243 return const_cast<CallInst *>( 244 static_cast<const BasicBlock *>(this)->getTerminatingDeoptimizeCall()); 245 } 246 247 /// Returns the call instruction calling \@llvm.experimental.deoptimize 248 /// that is present either in current basic block or in block that is a unique 249 /// successor to current block, if such call is present. Otherwise, returns null. 250 const CallInst *getPostdominatingDeoptimizeCall() const; 251 CallInst *getPostdominatingDeoptimizeCall() { 252 return const_cast<CallInst *>( 253 static_cast<const BasicBlock *>(this)->getPostdominatingDeoptimizeCall()); 254 } 255 256 /// Returns the call instruction marked 'musttail' prior to the terminating 257 /// return instruction of this basic block, if such a call is present. 258 /// Otherwise, returns null. 259 const CallInst *getTerminatingMustTailCall() const; 260 CallInst *getTerminatingMustTailCall() { 261 return const_cast<CallInst *>( 262 static_cast<const BasicBlock *>(this)->getTerminatingMustTailCall()); 263 } 264 265 /// Returns a pointer to the first instruction in this block that is not a 266 /// PHINode instruction. 267 /// 268 /// When adding instructions to the beginning of the basic block, they should 269 /// be added before the returned value, not before the first instruction, 270 /// which might be PHI. Returns 0 is there's no non-PHI instruction. 271 const Instruction* getFirstNonPHI() const; 272 Instruction* getFirstNonPHI() { 273 return const_cast<Instruction *>( 274 static_cast<const BasicBlock *>(this)->getFirstNonPHI()); 275 } 276 277 /// Iterator returning form of getFirstNonPHI. Installed as a placeholder for 278 /// the RemoveDIs project that will eventually remove debug intrinsics. 279 InstListType::const_iterator getFirstNonPHIIt() const; 280 InstListType::iterator getFirstNonPHIIt() { 281 BasicBlock::iterator It = 282 static_cast<const BasicBlock *>(this)->getFirstNonPHIIt().getNonConst(); 283 It.setHeadBit(true); 284 return It; 285 } 286 287 /// Returns a pointer to the first instruction in this block that is not a 288 /// PHINode or a debug intrinsic, or any pseudo operation if \c SkipPseudoOp 289 /// is true. 290 const Instruction *getFirstNonPHIOrDbg(bool SkipPseudoOp = true) const; 291 Instruction *getFirstNonPHIOrDbg(bool SkipPseudoOp = true) { 292 return const_cast<Instruction *>( 293 static_cast<const BasicBlock *>(this)->getFirstNonPHIOrDbg( 294 SkipPseudoOp)); 295 } 296 297 /// Returns a pointer to the first instruction in this block that is not a 298 /// PHINode, a debug intrinsic, or a lifetime intrinsic, or any pseudo 299 /// operation if \c SkipPseudoOp is true. 300 const Instruction * 301 getFirstNonPHIOrDbgOrLifetime(bool SkipPseudoOp = true) const; 302 Instruction *getFirstNonPHIOrDbgOrLifetime(bool SkipPseudoOp = true) { 303 return const_cast<Instruction *>( 304 static_cast<const BasicBlock *>(this)->getFirstNonPHIOrDbgOrLifetime( 305 SkipPseudoOp)); 306 } 307 308 /// Returns an iterator to the first instruction in this block that is 309 /// suitable for inserting a non-PHI instruction. 310 /// 311 /// In particular, it skips all PHIs and LandingPad instructions. 312 const_iterator getFirstInsertionPt() const; 313 iterator getFirstInsertionPt() { 314 return static_cast<const BasicBlock *>(this) 315 ->getFirstInsertionPt().getNonConst(); 316 } 317 318 /// Returns an iterator to the first instruction in this block that is 319 /// not a PHINode, a debug intrinsic, a static alloca or any pseudo operation. 320 const_iterator getFirstNonPHIOrDbgOrAlloca() const; 321 iterator getFirstNonPHIOrDbgOrAlloca() { 322 return static_cast<const BasicBlock *>(this) 323 ->getFirstNonPHIOrDbgOrAlloca() 324 .getNonConst(); 325 } 326 327 /// Returns the first potential AsynchEH faulty instruction 328 /// currently it checks for loads/stores (which may dereference a null 329 /// pointer) and calls/invokes (which may propagate exceptions) 330 const Instruction* getFirstMayFaultInst() const; 331 Instruction* getFirstMayFaultInst() { 332 return const_cast<Instruction*>( 333 static_cast<const BasicBlock*>(this)->getFirstMayFaultInst()); 334 } 335 336 /// Return a const iterator range over the instructions in the block, skipping 337 /// any debug instructions. Skip any pseudo operations as well if \c 338 /// SkipPseudoOp is true. 339 iterator_range<filter_iterator<BasicBlock::const_iterator, 340 std::function<bool(const Instruction &)>>> 341 instructionsWithoutDebug(bool SkipPseudoOp = true) const; 342 343 /// Return an iterator range over the instructions in the block, skipping any 344 /// debug instructions. Skip and any pseudo operations as well if \c 345 /// SkipPseudoOp is true. 346 iterator_range< 347 filter_iterator<BasicBlock::iterator, std::function<bool(Instruction &)>>> 348 instructionsWithoutDebug(bool SkipPseudoOp = true); 349 350 /// Return the size of the basic block ignoring debug instructions 351 filter_iterator<BasicBlock::const_iterator, 352 std::function<bool(const Instruction &)>>::difference_type 353 sizeWithoutDebug() const; 354 355 /// Unlink 'this' from the containing function, but do not delete it. 356 void removeFromParent(); 357 358 /// Unlink 'this' from the containing function and delete it. 359 /// 360 // \returns an iterator pointing to the element after the erased one. 361 SymbolTableList<BasicBlock>::iterator eraseFromParent(); 362 363 /// Unlink this basic block from its current function and insert it into 364 /// the function that \p MovePos lives in, right before \p MovePos. 365 inline void moveBefore(BasicBlock *MovePos) { 366 moveBefore(MovePos->getIterator()); 367 } 368 void moveBefore(SymbolTableList<BasicBlock>::iterator MovePos); 369 370 /// Unlink this basic block from its current function and insert it 371 /// right after \p MovePos in the function \p MovePos lives in. 372 void moveAfter(BasicBlock *MovePos); 373 374 /// Insert unlinked basic block into a function. 375 /// 376 /// Inserts an unlinked basic block into \c Parent. If \c InsertBefore is 377 /// provided, inserts before that basic block, otherwise inserts at the end. 378 /// 379 /// \pre \a getParent() is \c nullptr. 380 void insertInto(Function *Parent, BasicBlock *InsertBefore = nullptr); 381 382 /// Return the predecessor of this block if it has a single predecessor 383 /// block. Otherwise return a null pointer. 384 const BasicBlock *getSinglePredecessor() const; 385 BasicBlock *getSinglePredecessor() { 386 return const_cast<BasicBlock *>( 387 static_cast<const BasicBlock *>(this)->getSinglePredecessor()); 388 } 389 390 /// Return the predecessor of this block if it has a unique predecessor 391 /// block. Otherwise return a null pointer. 392 /// 393 /// Note that unique predecessor doesn't mean single edge, there can be 394 /// multiple edges from the unique predecessor to this block (for example a 395 /// switch statement with multiple cases having the same destination). 396 const BasicBlock *getUniquePredecessor() const; 397 BasicBlock *getUniquePredecessor() { 398 return const_cast<BasicBlock *>( 399 static_cast<const BasicBlock *>(this)->getUniquePredecessor()); 400 } 401 402 /// Return true if this block has exactly N predecessors. 403 bool hasNPredecessors(unsigned N) const; 404 405 /// Return true if this block has N predecessors or more. 406 bool hasNPredecessorsOrMore(unsigned N) const; 407 408 /// Return the successor of this block if it has a single successor. 409 /// Otherwise return a null pointer. 410 /// 411 /// This method is analogous to getSinglePredecessor above. 412 const BasicBlock *getSingleSuccessor() const; 413 BasicBlock *getSingleSuccessor() { 414 return const_cast<BasicBlock *>( 415 static_cast<const BasicBlock *>(this)->getSingleSuccessor()); 416 } 417 418 /// Return the successor of this block if it has a unique successor. 419 /// Otherwise return a null pointer. 420 /// 421 /// This method is analogous to getUniquePredecessor above. 422 const BasicBlock *getUniqueSuccessor() const; 423 BasicBlock *getUniqueSuccessor() { 424 return const_cast<BasicBlock *>( 425 static_cast<const BasicBlock *>(this)->getUniqueSuccessor()); 426 } 427 428 /// Print the basic block to an output stream with an optional 429 /// AssemblyAnnotationWriter. 430 void print(raw_ostream &OS, AssemblyAnnotationWriter *AAW = nullptr, 431 bool ShouldPreserveUseListOrder = false, 432 bool IsForDebug = false) const; 433 434 //===--------------------------------------------------------------------===// 435 /// Instruction iterator methods 436 /// 437 inline iterator begin() { 438 iterator It = InstList.begin(); 439 // Set the head-inclusive bit to indicate that this iterator includes 440 // any debug-info at the start of the block. This is a no-op unless the 441 // appropriate CMake flag is set. 442 It.setHeadBit(true); 443 return It; 444 } 445 inline const_iterator begin() const { 446 const_iterator It = InstList.begin(); 447 It.setHeadBit(true); 448 return It; 449 } 450 inline iterator end () { return InstList.end(); } 451 inline const_iterator end () const { return InstList.end(); } 452 453 inline reverse_iterator rbegin() { return InstList.rbegin(); } 454 inline const_reverse_iterator rbegin() const { return InstList.rbegin(); } 455 inline reverse_iterator rend () { return InstList.rend(); } 456 inline const_reverse_iterator rend () const { return InstList.rend(); } 457 458 inline size_t size() const { return InstList.size(); } 459 inline bool empty() const { return InstList.empty(); } 460 inline const Instruction &front() const { return InstList.front(); } 461 inline Instruction &front() { return InstList.front(); } 462 inline const Instruction &back() const { return InstList.back(); } 463 inline Instruction &back() { return InstList.back(); } 464 465 /// Iterator to walk just the phi nodes in the basic block. 466 template <typename PHINodeT = PHINode, typename BBIteratorT = iterator> 467 class phi_iterator_impl 468 : public iterator_facade_base<phi_iterator_impl<PHINodeT, BBIteratorT>, 469 std::forward_iterator_tag, PHINodeT> { 470 friend BasicBlock; 471 472 PHINodeT *PN; 473 474 phi_iterator_impl(PHINodeT *PN) : PN(PN) {} 475 476 public: 477 // Allow default construction to build variables, but this doesn't build 478 // a useful iterator. 479 phi_iterator_impl() = default; 480 481 // Allow conversion between instantiations where valid. 482 template <typename PHINodeU, typename BBIteratorU, 483 typename = std::enable_if_t< 484 std::is_convertible<PHINodeU *, PHINodeT *>::value>> 485 phi_iterator_impl(const phi_iterator_impl<PHINodeU, BBIteratorU> &Arg) 486 : PN(Arg.PN) {} 487 488 bool operator==(const phi_iterator_impl &Arg) const { return PN == Arg.PN; } 489 490 PHINodeT &operator*() const { return *PN; } 491 492 using phi_iterator_impl::iterator_facade_base::operator++; 493 phi_iterator_impl &operator++() { 494 assert(PN && "Cannot increment the end iterator!"); 495 PN = dyn_cast<PHINodeT>(std::next(BBIteratorT(PN))); 496 return *this; 497 } 498 }; 499 using phi_iterator = phi_iterator_impl<>; 500 using const_phi_iterator = 501 phi_iterator_impl<const PHINode, BasicBlock::const_iterator>; 502 503 /// Returns a range that iterates over the phis in the basic block. 504 /// 505 /// Note that this cannot be used with basic blocks that have no terminator. 506 iterator_range<const_phi_iterator> phis() const { 507 return const_cast<BasicBlock *>(this)->phis(); 508 } 509 iterator_range<phi_iterator> phis(); 510 511 private: 512 /// Return the underlying instruction list container. 513 /// This is deliberately private because we have implemented an adequate set 514 /// of functions to modify the list, including BasicBlock::splice(), 515 /// BasicBlock::erase(), Instruction::insertInto() etc. 516 const InstListType &getInstList() const { return InstList; } 517 InstListType &getInstList() { return InstList; } 518 519 /// Returns a pointer to a member of the instruction list. 520 /// This is private on purpose, just like `getInstList()`. 521 static InstListType BasicBlock::*getSublistAccess(Instruction *) { 522 return &BasicBlock::InstList; 523 } 524 525 /// Dedicated function for splicing debug-info: when we have an empty 526 /// splice (i.e. zero instructions), the caller may still intend any 527 /// debug-info in between the two "positions" to be spliced. 528 void spliceDebugInfoEmptyBlock(BasicBlock::iterator ToIt, BasicBlock *FromBB, 529 BasicBlock::iterator FromBeginIt, 530 BasicBlock::iterator FromEndIt); 531 532 /// Perform any debug-info specific maintenence for the given splice 533 /// activity. In the DPValue debug-info representation, debug-info is not 534 /// in instructions, and so it does not automatically move from one block 535 /// to another. 536 void spliceDebugInfo(BasicBlock::iterator ToIt, BasicBlock *FromBB, 537 BasicBlock::iterator FromBeginIt, 538 BasicBlock::iterator FromEndIt); 539 void spliceDebugInfoImpl(BasicBlock::iterator ToIt, BasicBlock *FromBB, 540 BasicBlock::iterator FromBeginIt, 541 BasicBlock::iterator FromEndIt); 542 543 public: 544 /// Returns a pointer to the symbol table if one exists. 545 ValueSymbolTable *getValueSymbolTable(); 546 547 /// Methods for support type inquiry through isa, cast, and dyn_cast. 548 static bool classof(const Value *V) { 549 return V->getValueID() == Value::BasicBlockVal; 550 } 551 552 /// Cause all subinstructions to "let go" of all the references that said 553 /// subinstructions are maintaining. 554 /// 555 /// This allows one to 'delete' a whole class at a time, even though there may 556 /// be circular references... first all references are dropped, and all use 557 /// counts go to zero. Then everything is delete'd for real. Note that no 558 /// operations are valid on an object that has "dropped all references", 559 /// except operator delete. 560 void dropAllReferences(); 561 562 /// Update PHI nodes in this BasicBlock before removal of predecessor \p Pred. 563 /// Note that this function does not actually remove the predecessor. 564 /// 565 /// If \p KeepOneInputPHIs is true then don't remove PHIs that are left with 566 /// zero or one incoming values, and don't simplify PHIs with all incoming 567 /// values the same. 568 void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs = false); 569 570 bool canSplitPredecessors() const; 571 572 /// Split the basic block into two basic blocks at the specified instruction. 573 /// 574 /// If \p Before is true, splitBasicBlockBefore handles the 575 /// block splitting. Otherwise, execution proceeds as described below. 576 /// 577 /// Note that all instructions BEFORE the specified iterator 578 /// stay as part of the original basic block, an unconditional branch is added 579 /// to the original BB, and the rest of the instructions in the BB are moved 580 /// to the new BB, including the old terminator. The newly formed basic block 581 /// is returned. This function invalidates the specified iterator. 582 /// 583 /// Note that this only works on well formed basic blocks (must have a 584 /// terminator), and \p 'I' must not be the end of instruction list (which 585 /// would cause a degenerate basic block to be formed, having a terminator 586 /// inside of the basic block). 587 /// 588 /// Also note that this doesn't preserve any passes. To split blocks while 589 /// keeping loop information consistent, use the SplitBlock utility function. 590 BasicBlock *splitBasicBlock(iterator I, const Twine &BBName = "", 591 bool Before = false); 592 BasicBlock *splitBasicBlock(Instruction *I, const Twine &BBName = "", 593 bool Before = false) { 594 return splitBasicBlock(I->getIterator(), BBName, Before); 595 } 596 597 /// Split the basic block into two basic blocks at the specified instruction 598 /// and insert the new basic blocks as the predecessor of the current block. 599 /// 600 /// This function ensures all instructions AFTER and including the specified 601 /// iterator \p I are part of the original basic block. All Instructions 602 /// BEFORE the iterator \p I are moved to the new BB and an unconditional 603 /// branch is added to the new BB. The new basic block is returned. 604 /// 605 /// Note that this only works on well formed basic blocks (must have a 606 /// terminator), and \p 'I' must not be the end of instruction list (which 607 /// would cause a degenerate basic block to be formed, having a terminator 608 /// inside of the basic block). \p 'I' cannot be a iterator for a PHINode 609 /// with multiple incoming blocks. 610 /// 611 /// Also note that this doesn't preserve any passes. To split blocks while 612 /// keeping loop information consistent, use the SplitBlockBefore utility 613 /// function. 614 BasicBlock *splitBasicBlockBefore(iterator I, const Twine &BBName = ""); 615 BasicBlock *splitBasicBlockBefore(Instruction *I, const Twine &BBName = "") { 616 return splitBasicBlockBefore(I->getIterator(), BBName); 617 } 618 619 /// Transfer all instructions from \p FromBB to this basic block at \p ToIt. 620 void splice(BasicBlock::iterator ToIt, BasicBlock *FromBB) { 621 splice(ToIt, FromBB, FromBB->begin(), FromBB->end()); 622 } 623 624 /// Transfer one instruction from \p FromBB at \p FromIt to this basic block 625 /// at \p ToIt. 626 void splice(BasicBlock::iterator ToIt, BasicBlock *FromBB, 627 BasicBlock::iterator FromIt) { 628 auto FromItNext = std::next(FromIt); 629 // Single-element splice is a noop if destination == source. 630 if (ToIt == FromIt || ToIt == FromItNext) 631 return; 632 splice(ToIt, FromBB, FromIt, FromItNext); 633 } 634 635 /// Transfer a range of instructions that belong to \p FromBB from \p 636 /// FromBeginIt to \p FromEndIt, to this basic block at \p ToIt. 637 void splice(BasicBlock::iterator ToIt, BasicBlock *FromBB, 638 BasicBlock::iterator FromBeginIt, 639 BasicBlock::iterator FromEndIt); 640 641 /// Erases a range of instructions from \p FromIt to (not including) \p ToIt. 642 /// \Returns \p ToIt. 643 BasicBlock::iterator erase(BasicBlock::iterator FromIt, BasicBlock::iterator ToIt); 644 645 /// Returns true if there are any uses of this basic block other than 646 /// direct branches, switches, etc. to it. 647 bool hasAddressTaken() const { 648 return getBasicBlockBits().BlockAddressRefCount != 0; 649 } 650 651 /// Update all phi nodes in this basic block to refer to basic block \p New 652 /// instead of basic block \p Old. 653 void replacePhiUsesWith(BasicBlock *Old, BasicBlock *New); 654 655 /// Update all phi nodes in this basic block's successors to refer to basic 656 /// block \p New instead of basic block \p Old. 657 void replaceSuccessorsPhiUsesWith(BasicBlock *Old, BasicBlock *New); 658 659 /// Update all phi nodes in this basic block's successors to refer to basic 660 /// block \p New instead of to it. 661 void replaceSuccessorsPhiUsesWith(BasicBlock *New); 662 663 /// Return true if this basic block is an exception handling block. 664 bool isEHPad() const { return getFirstNonPHI()->isEHPad(); } 665 666 /// Return true if this basic block is a landing pad. 667 /// 668 /// Being a ``landing pad'' means that the basic block is the destination of 669 /// the 'unwind' edge of an invoke instruction. 670 bool isLandingPad() const; 671 672 /// Return the landingpad instruction associated with the landing pad. 673 const LandingPadInst *getLandingPadInst() const; 674 LandingPadInst *getLandingPadInst() { 675 return const_cast<LandingPadInst *>( 676 static_cast<const BasicBlock *>(this)->getLandingPadInst()); 677 } 678 679 /// Return true if it is legal to hoist instructions into this block. 680 bool isLegalToHoistInto() const; 681 682 /// Return true if this is the entry block of the containing function. 683 /// This method can only be used on blocks that have a parent function. 684 bool isEntryBlock() const; 685 686 std::optional<uint64_t> getIrrLoopHeaderWeight() const; 687 688 /// Returns true if the Order field of child Instructions is valid. 689 bool isInstrOrderValid() const { 690 return getBasicBlockBits().InstrOrderValid; 691 } 692 693 /// Mark instruction ordering invalid. Done on every instruction insert. 694 void invalidateOrders() { 695 validateInstrOrdering(); 696 BasicBlockBits Bits = getBasicBlockBits(); 697 Bits.InstrOrderValid = false; 698 setBasicBlockBits(Bits); 699 } 700 701 /// Renumber instructions and mark the ordering as valid. 702 void renumberInstructions(); 703 704 /// Asserts that instruction order numbers are marked invalid, or that they 705 /// are in ascending order. This is constant time if the ordering is invalid, 706 /// and linear in the number of instructions if the ordering is valid. Callers 707 /// should be careful not to call this in ways that make common operations 708 /// O(n^2). For example, it takes O(n) time to assign order numbers to 709 /// instructions, so the order should be validated no more than once after 710 /// each ordering to ensure that transforms have the same algorithmic 711 /// complexity when asserts are enabled as when they are disabled. 712 void validateInstrOrdering() const; 713 714 private: 715 #if defined(_AIX) && (!defined(__GNUC__) || defined(__clang__)) 716 // Except for GCC; by default, AIX compilers store bit-fields in 4-byte words 717 // and give the `pack` pragma push semantics. 718 #define BEGIN_TWO_BYTE_PACK() _Pragma("pack(2)") 719 #define END_TWO_BYTE_PACK() _Pragma("pack(pop)") 720 #else 721 #define BEGIN_TWO_BYTE_PACK() 722 #define END_TWO_BYTE_PACK() 723 #endif 724 725 BEGIN_TWO_BYTE_PACK() 726 /// Bitfield to help interpret the bits in Value::SubclassData. 727 struct BasicBlockBits { 728 unsigned short BlockAddressRefCount : 15; 729 unsigned short InstrOrderValid : 1; 730 }; 731 END_TWO_BYTE_PACK() 732 733 #undef BEGIN_TWO_BYTE_PACK 734 #undef END_TWO_BYTE_PACK 735 736 /// Safely reinterpret the subclass data bits to a more useful form. 737 BasicBlockBits getBasicBlockBits() const { 738 static_assert(sizeof(BasicBlockBits) == sizeof(unsigned short), 739 "too many bits for Value::SubclassData"); 740 unsigned short ValueData = getSubclassDataFromValue(); 741 BasicBlockBits AsBits; 742 memcpy(&AsBits, &ValueData, sizeof(AsBits)); 743 return AsBits; 744 } 745 746 /// Reinterpret our subclass bits and store them back into Value. 747 void setBasicBlockBits(BasicBlockBits AsBits) { 748 unsigned short D; 749 memcpy(&D, &AsBits, sizeof(D)); 750 Value::setValueSubclassData(D); 751 } 752 753 /// Increment the internal refcount of the number of BlockAddresses 754 /// referencing this BasicBlock by \p Amt. 755 /// 756 /// This is almost always 0, sometimes one possibly, but almost never 2, and 757 /// inconceivably 3 or more. 758 void AdjustBlockAddressRefCount(int Amt) { 759 BasicBlockBits Bits = getBasicBlockBits(); 760 Bits.BlockAddressRefCount += Amt; 761 setBasicBlockBits(Bits); 762 assert(Bits.BlockAddressRefCount < 255 && "Refcount wrap-around"); 763 } 764 765 /// Shadow Value::setValueSubclassData with a private forwarding method so 766 /// that any future subclasses cannot accidentally use it. 767 void setValueSubclassData(unsigned short D) { 768 Value::setValueSubclassData(D); 769 } 770 }; 771 772 // Create wrappers for C Binding types (see CBindingWrapping.h). 773 DEFINE_SIMPLE_CONVERSION_FUNCTIONS(BasicBlock, LLVMBasicBlockRef) 774 775 /// Advance \p It while it points to a debug instruction and return the result. 776 /// This assumes that \p It is not at the end of a block. 777 BasicBlock::iterator skipDebugIntrinsics(BasicBlock::iterator It); 778 779 #ifdef NDEBUG 780 /// In release builds, this is a no-op. For !NDEBUG builds, the checks are 781 /// implemented in the .cpp file to avoid circular header deps. 782 inline void BasicBlock::validateInstrOrdering() const {} 783 #endif 784 785 } // end namespace llvm 786 787 #endif // LLVM_IR_BASICBLOCK_H 788