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 | |
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 DbgVariableRecord; |
42 | class 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". |
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 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 | |
144 | private: |
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 | |
156 | public: |
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 | |
504 | private: |
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 | |
536 | public: |
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> () 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 | |
707 | private: |
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). |
766 | DEFINE_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. |
770 | BasicBlock::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. |
775 | inline 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. |
781 | template <> 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 | |