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

source code of llvm/include/llvm/IR/BasicBlock.h