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: 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: 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: 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, FromBeginIt: FromBB->begin(), FromEndIt: 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(x: FromIt); |
629 | // Single-element splice is a noop if destination == source. |
630 | if (ToIt == FromIt || ToIt == FromItNext) |
631 | return; |
632 | splice(ToIt, FromBB, FromBeginIt: FromIt, FromEndIt: 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> () 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(dest: &AsBits, src: &ValueData, n: 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(dest: &D, src: &AsBits, n: 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 | |