/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/include/llvm/IR/BasicBlock.h
Line | Count | Source (jump to first uncovered line) |
1 | | //===- llvm/BasicBlock.h - Represent a basic block in the VM ----*- C++ -*-===// |
2 | | // |
3 | | // The LLVM Compiler Infrastructure |
4 | | // |
5 | | // This file is distributed under the University of Illinois Open Source |
6 | | // License. See LICENSE.TXT for details. |
7 | | // |
8 | | //===----------------------------------------------------------------------===// |
9 | | // |
10 | | // This file contains the declaration of the BasicBlock class. |
11 | | // |
12 | | //===----------------------------------------------------------------------===// |
13 | | |
14 | | #ifndef LLVM_IR_BASICBLOCK_H |
15 | | #define LLVM_IR_BASICBLOCK_H |
16 | | |
17 | | #include "llvm-c/Types.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/Instruction.h" |
24 | | #include "llvm/IR/SymbolTableListTraits.h" |
25 | | #include "llvm/IR/Value.h" |
26 | | #include "llvm/Support/CBindingWrapping.h" |
27 | | #include "llvm/Support/Casting.h" |
28 | | #include "llvm/Support/Compiler.h" |
29 | | #include <cassert> |
30 | | #include <cstddef> |
31 | | #include <iterator> |
32 | | |
33 | | namespace llvm { |
34 | | |
35 | | class CallInst; |
36 | | class Function; |
37 | | class LandingPadInst; |
38 | | class LLVMContext; |
39 | | class Module; |
40 | | class PHINode; |
41 | | class TerminatorInst; |
42 | | class ValueSymbolTable; |
43 | | |
44 | | /// \brief 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 TerminatorInst instruction. |
54 | | /// TerminatorInst's may not occur in the middle of basic blocks, and must |
55 | | /// terminate the blocks. The BasicBlock class allows malformed basic blocks to |
56 | | /// occur because it may be useful in the intermediate stage of constructing or |
57 | | /// modifying a program. However, the verifier will ensure that basic blocks |
58 | | /// are "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>; |
63 | | |
64 | | private: |
65 | | friend class BlockAddress; |
66 | | friend class SymbolTableListTraits<BasicBlock>; |
67 | | |
68 | | InstListType InstList; |
69 | | Function *Parent; |
70 | | |
71 | | void setParent(Function *parent); |
72 | | |
73 | | /// \brief Constructor. |
74 | | /// |
75 | | /// If the function parameter is specified, the basic block is automatically |
76 | | /// inserted at either the end of the function (if InsertBefore is null), or |
77 | | /// before the specified basic block. |
78 | | explicit BasicBlock(LLVMContext &C, const Twine &Name = "", |
79 | | Function *Parent = nullptr, |
80 | | BasicBlock *InsertBefore = nullptr); |
81 | | |
82 | | public: |
83 | | BasicBlock(const BasicBlock &) = delete; |
84 | | BasicBlock &operator=(const BasicBlock &) = delete; |
85 | | ~BasicBlock(); |
86 | | |
87 | | /// \brief Get the context in which this basic block lives. |
88 | | LLVMContext &getContext() const; |
89 | | |
90 | | /// Instruction iterators... |
91 | | using iterator = InstListType::iterator; |
92 | | using const_iterator = InstListType::const_iterator; |
93 | | using reverse_iterator = InstListType::reverse_iterator; |
94 | | using const_reverse_iterator = InstListType::const_reverse_iterator; |
95 | | |
96 | | /// \brief Creates a new BasicBlock. |
97 | | /// |
98 | | /// If the Parent parameter is specified, the basic block is automatically |
99 | | /// inserted at either the end of the function (if InsertBefore is 0), or |
100 | | /// before the specified basic block. |
101 | | static BasicBlock *Create(LLVMContext &Context, const Twine &Name = "", |
102 | | Function *Parent = nullptr, |
103 | 8.30M | BasicBlock *InsertBefore = nullptr) { |
104 | 8.30M | return new BasicBlock(Context, Name, Parent, InsertBefore); |
105 | 8.30M | } |
106 | | |
107 | | /// \brief Return the enclosing method, or null if none. |
108 | 455M | const Function *getParent() const { return Parent; } |
109 | 183M | Function *getParent() { return Parent; } |
110 | | |
111 | | /// \brief Return the module owning the function this basic block belongs to, |
112 | | /// or nullptr it the function does not have a module. |
113 | | /// |
114 | | /// Note: this is undefined behavior if the block does not have a parent. |
115 | | const Module *getModule() const; |
116 | 145M | Module *getModule() { |
117 | 145M | return const_cast<Module *>( |
118 | 145M | static_cast<const BasicBlock *>(this)->getModule()); |
119 | 145M | } |
120 | | |
121 | | /// \brief Returns the terminator instruction if the block is well formed or |
122 | | /// null if the block is not well formed. |
123 | | const TerminatorInst *getTerminator() const LLVM_READONLY; |
124 | 2.20G | TerminatorInst *getTerminator() { |
125 | 2.20G | return const_cast<TerminatorInst *>( |
126 | 2.20G | static_cast<const BasicBlock *>(this)->getTerminator()); |
127 | 2.20G | } |
128 | | |
129 | | /// \brief Returns the call instruction calling @llvm.experimental.deoptimize |
130 | | /// prior to the terminating return instruction of this basic block, if such a |
131 | | /// call is present. Otherwise, returns null. |
132 | | const CallInst *getTerminatingDeoptimizeCall() const; |
133 | 190 | CallInst *getTerminatingDeoptimizeCall() { |
134 | 190 | return const_cast<CallInst *>( |
135 | 190 | static_cast<const BasicBlock *>(this)->getTerminatingDeoptimizeCall()); |
136 | 190 | } |
137 | | |
138 | | /// \brief Returns the call instruction marked 'musttail' prior to the |
139 | | /// terminating return instruction of this basic block, if such a call is |
140 | | /// present. Otherwise, returns null. |
141 | | const CallInst *getTerminatingMustTailCall() const; |
142 | 26 | CallInst *getTerminatingMustTailCall() { |
143 | 26 | return const_cast<CallInst *>( |
144 | 26 | static_cast<const BasicBlock *>(this)->getTerminatingMustTailCall()); |
145 | 26 | } |
146 | | |
147 | | /// \brief Returns a pointer to the first instruction in this block that is |
148 | | /// not a PHINode instruction. |
149 | | /// |
150 | | /// When adding instructions to the beginning of the basic block, they should |
151 | | /// be added before the returned value, not before the first instruction, |
152 | | /// which might be PHI. Returns 0 is there's no non-PHI instruction. |
153 | | const Instruction* getFirstNonPHI() const; |
154 | 3.79M | Instruction* getFirstNonPHI() { |
155 | 3.79M | return const_cast<Instruction *>( |
156 | 3.79M | static_cast<const BasicBlock *>(this)->getFirstNonPHI()); |
157 | 3.79M | } |
158 | | |
159 | | /// \brief Returns a pointer to the first instruction in this block that is not |
160 | | /// a PHINode or a debug intrinsic. |
161 | | const Instruction* getFirstNonPHIOrDbg() const; |
162 | 34.4M | Instruction* getFirstNonPHIOrDbg() { |
163 | 34.4M | return const_cast<Instruction *>( |
164 | 34.4M | static_cast<const BasicBlock *>(this)->getFirstNonPHIOrDbg()); |
165 | 34.4M | } |
166 | | |
167 | | /// \brief Returns a pointer to the first instruction in this block that is not |
168 | | /// a PHINode, a debug intrinsic, or a lifetime intrinsic. |
169 | | const Instruction* getFirstNonPHIOrDbgOrLifetime() const; |
170 | 81 | Instruction* getFirstNonPHIOrDbgOrLifetime() { |
171 | 81 | return const_cast<Instruction *>( |
172 | 81 | static_cast<const BasicBlock *>(this)->getFirstNonPHIOrDbgOrLifetime()); |
173 | 81 | } |
174 | | |
175 | | /// \brief Returns an iterator to the first instruction in this block that is |
176 | | /// suitable for inserting a non-PHI instruction. |
177 | | /// |
178 | | /// In particular, it skips all PHIs and LandingPad instructions. |
179 | | const_iterator getFirstInsertionPt() const; |
180 | 2.95M | iterator getFirstInsertionPt() { |
181 | 2.95M | return static_cast<const BasicBlock *>(this) |
182 | 2.95M | ->getFirstInsertionPt().getNonConst(); |
183 | 2.95M | } |
184 | | |
185 | | /// \brief Unlink 'this' from the containing function, but do not delete it. |
186 | | void removeFromParent(); |
187 | | |
188 | | /// \brief Unlink 'this' from the containing function and delete it. |
189 | | /// |
190 | | // \returns an iterator pointing to the element after the erased one. |
191 | | SymbolTableList<BasicBlock>::iterator eraseFromParent(); |
192 | | |
193 | | /// \brief Unlink this basic block from its current function and insert it |
194 | | /// into the function that \p MovePos lives in, right before \p MovePos. |
195 | | void moveBefore(BasicBlock *MovePos); |
196 | | |
197 | | /// \brief Unlink this basic block from its current function and insert it |
198 | | /// right after \p MovePos in the function \p MovePos lives in. |
199 | | void moveAfter(BasicBlock *MovePos); |
200 | | |
201 | | /// \brief Insert unlinked basic block into a function. |
202 | | /// |
203 | | /// Inserts an unlinked basic block into \c Parent. If \c InsertBefore is |
204 | | /// provided, inserts before that basic block, otherwise inserts at the end. |
205 | | /// |
206 | | /// \pre \a getParent() is \c nullptr. |
207 | | void insertInto(Function *Parent, BasicBlock *InsertBefore = nullptr); |
208 | | |
209 | | /// \brief Return the predecessor of this block if it has a single predecessor |
210 | | /// block. Otherwise return a null pointer. |
211 | | const BasicBlock *getSinglePredecessor() const; |
212 | 270M | BasicBlock *getSinglePredecessor() { |
213 | 270M | return const_cast<BasicBlock *>( |
214 | 270M | static_cast<const BasicBlock *>(this)->getSinglePredecessor()); |
215 | 270M | } |
216 | | |
217 | | /// \brief Return the predecessor of this block if it has a unique predecessor |
218 | | /// block. Otherwise return a null pointer. |
219 | | /// |
220 | | /// Note that unique predecessor doesn't mean single edge, there can be |
221 | | /// multiple edges from the unique predecessor to this block (for example a |
222 | | /// switch statement with multiple cases having the same destination). |
223 | | const BasicBlock *getUniquePredecessor() const; |
224 | 54.7M | BasicBlock *getUniquePredecessor() { |
225 | 54.7M | return const_cast<BasicBlock *>( |
226 | 54.7M | static_cast<const BasicBlock *>(this)->getUniquePredecessor()); |
227 | 54.7M | } |
228 | | |
229 | | /// \brief Return the successor of this block if it has a single successor. |
230 | | /// Otherwise return a null pointer. |
231 | | /// |
232 | | /// This method is analogous to getSinglePredecessor above. |
233 | | const BasicBlock *getSingleSuccessor() const; |
234 | 64.7M | BasicBlock *getSingleSuccessor() { |
235 | 64.7M | return const_cast<BasicBlock *>( |
236 | 64.7M | static_cast<const BasicBlock *>(this)->getSingleSuccessor()); |
237 | 64.7M | } |
238 | | |
239 | | /// \brief Return the successor of this block if it has a unique successor. |
240 | | /// Otherwise return a null pointer. |
241 | | /// |
242 | | /// This method is analogous to getUniquePredecessor above. |
243 | | const BasicBlock *getUniqueSuccessor() const; |
244 | 34.8k | BasicBlock *getUniqueSuccessor() { |
245 | 34.8k | return const_cast<BasicBlock *>( |
246 | 34.8k | static_cast<const BasicBlock *>(this)->getUniqueSuccessor()); |
247 | 34.8k | } |
248 | | |
249 | | //===--------------------------------------------------------------------===// |
250 | | /// Instruction iterator methods |
251 | | /// |
252 | 945M | inline iterator begin() { return InstList.begin(); } |
253 | 159M | inline const_iterator begin() const { return InstList.begin(); } |
254 | 792M | inline iterator end () { return InstList.end(); } |
255 | 200M | inline const_iterator end () const { return InstList.end(); } |
256 | | |
257 | 14.6M | inline reverse_iterator rbegin() { return InstList.rbegin(); } |
258 | 0 | inline const_reverse_iterator rbegin() const { return InstList.rbegin(); } |
259 | 35.2M | inline reverse_iterator rend () { return InstList.rend(); } |
260 | 0 | inline const_reverse_iterator rend () const { return InstList.rend(); } |
261 | | |
262 | 4.39M | inline size_t size() const { return InstList.size(); } |
263 | 6.89M | inline bool empty() const { return InstList.empty(); } |
264 | 737k | inline const Instruction &front() const { return InstList.front(); } |
265 | 14.3M | inline Instruction &front() { return InstList.front(); } |
266 | 801k | inline const Instruction &back() const { return InstList.back(); } |
267 | 156k | inline Instruction &back() { return InstList.back(); } |
268 | | |
269 | | /// Iterator to walk just the phi nodes in the basic block. |
270 | | template <typename PHINodeT = PHINode, typename BBIteratorT = iterator> |
271 | | class phi_iterator_impl |
272 | | : public iterator_facade_base<phi_iterator_impl<PHINodeT, BBIteratorT>, |
273 | | std::forward_iterator_tag, PHINodeT> { |
274 | | friend BasicBlock; |
275 | | |
276 | | PHINodeT *PN; |
277 | | |
278 | 726k | phi_iterator_impl(PHINodeT *PN) : PN(PN) {} |
279 | | |
280 | | public: |
281 | | // Allow default construction to build variables, but this doesn't build |
282 | | // a useful iterator. |
283 | | phi_iterator_impl() = default; |
284 | | |
285 | | // Allow conversion between instantiations where valid. |
286 | | template <typename PHINodeU, typename BBIteratorU> |
287 | | phi_iterator_impl(const phi_iterator_impl<PHINodeU, BBIteratorU> &Arg) |
288 | | : PN(Arg.PN) {} |
289 | | |
290 | 589k | bool operator==(const phi_iterator_impl &Arg) const { return PN == Arg.PN; } |
291 | | |
292 | 226k | PHINodeT &operator*() const { return *PN; } |
293 | | |
294 | | using phi_iterator_impl::iterator_facade_base::operator++; |
295 | 226k | phi_iterator_impl &operator++() { |
296 | 226k | assert(PN && "Cannot increment the end iterator!"); |
297 | 226k | PN = dyn_cast<PHINodeT>(std::next(BBIteratorT(PN))); |
298 | 226k | return *this; |
299 | 226k | } |
300 | | }; |
301 | | using phi_iterator = phi_iterator_impl<>; |
302 | | using const_phi_iterator = |
303 | | phi_iterator_impl<const PHINode, BasicBlock::const_iterator>; |
304 | | |
305 | | /// Returns a range that iterates over the phis in the basic block. |
306 | | /// |
307 | | /// Note that this cannot be used with basic blocks that have no terminator. |
308 | 0 | iterator_range<const_phi_iterator> phis() const { |
309 | 0 | return const_cast<BasicBlock *>(this)->phis(); |
310 | 0 | } |
311 | | iterator_range<phi_iterator> phis(); |
312 | | |
313 | | /// \brief Return the underlying instruction list container. |
314 | | /// |
315 | | /// Currently you need to access the underlying instruction list container |
316 | | /// directly if you want to modify it. |
317 | 289 | const InstListType &getInstList() const { return InstList; } |
318 | 90.3M | InstListType &getInstList() { return InstList; } |
319 | | |
320 | | /// \brief Returns a pointer to a member of the instruction list. |
321 | 179M | static InstListType BasicBlock::*getSublistAccess(Instruction*) { |
322 | 179M | return &BasicBlock::InstList; |
323 | 179M | } |
324 | | |
325 | | /// \brief Returns a pointer to the symbol table if one exists. |
326 | | ValueSymbolTable *getValueSymbolTable(); |
327 | | |
328 | | /// \brief Methods for support type inquiry through isa, cast, and dyn_cast. |
329 | 0 | static bool classof(const Value *V) { |
330 | 0 | return V->getValueID() == Value::BasicBlockVal; |
331 | 0 | } |
332 | | |
333 | | /// \brief Cause all subinstructions to "let go" of all the references that |
334 | | /// said subinstructions are maintaining. |
335 | | /// |
336 | | /// This allows one to 'delete' a whole class at a time, even though there may |
337 | | /// be circular references... first all references are dropped, and all use |
338 | | /// counts go to zero. Then everything is delete'd for real. Note that no |
339 | | /// operations are valid on an object that has "dropped all references", |
340 | | /// except operator delete. |
341 | | void dropAllReferences(); |
342 | | |
343 | | /// \brief Notify the BasicBlock that the predecessor \p Pred is no longer |
344 | | /// able to reach it. |
345 | | /// |
346 | | /// This is actually not used to update the Predecessor list, but is actually |
347 | | /// used to update the PHI nodes that reside in the block. Note that this |
348 | | /// should be called while the predecessor still refers to this block. |
349 | | void removePredecessor(BasicBlock *Pred, bool DontDeleteUselessPHIs = false); |
350 | | |
351 | | bool canSplitPredecessors() const; |
352 | | |
353 | | /// \brief Split the basic block into two basic blocks at the specified |
354 | | /// instruction. |
355 | | /// |
356 | | /// Note that all instructions BEFORE the specified iterator stay as part of |
357 | | /// the original basic block, an unconditional branch is added to the original |
358 | | /// BB, and the rest of the instructions in the BB are moved to the new BB, |
359 | | /// including the old terminator. The newly formed BasicBlock is returned. |
360 | | /// This function invalidates the specified iterator. |
361 | | /// |
362 | | /// Note that this only works on well formed basic blocks (must have a |
363 | | /// terminator), and 'I' must not be the end of instruction list (which would |
364 | | /// cause a degenerate basic block to be formed, having a terminator inside of |
365 | | /// the basic block). |
366 | | /// |
367 | | /// Also note that this doesn't preserve any passes. To split blocks while |
368 | | /// keeping loop information consistent, use the SplitBlock utility function. |
369 | | BasicBlock *splitBasicBlock(iterator I, const Twine &BBName = ""); |
370 | 103k | BasicBlock *splitBasicBlock(Instruction *I, const Twine &BBName = "") { |
371 | 103k | return splitBasicBlock(I->getIterator(), BBName); |
372 | 103k | } |
373 | | |
374 | | /// \brief Returns true if there are any uses of this basic block other than |
375 | | /// direct branches, switches, etc. to it. |
376 | 76.0M | bool hasAddressTaken() const { return getSubclassDataFromValue() != 0; } |
377 | | |
378 | | /// \brief Update all phi nodes in this basic block's successors to refer to |
379 | | /// basic block \p New instead of to it. |
380 | | void replaceSuccessorsPhiUsesWith(BasicBlock *New); |
381 | | |
382 | | /// \brief Return true if this basic block is an exception handling block. |
383 | 18.6M | bool isEHPad() const { return getFirstNonPHI()->isEHPad(); } |
384 | | |
385 | | /// \brief Return true if this basic block is a landing pad. |
386 | | /// |
387 | | /// Being a ``landing pad'' means that the basic block is the destination of |
388 | | /// the 'unwind' edge of an invoke instruction. |
389 | | bool isLandingPad() const; |
390 | | |
391 | | /// \brief Return the landingpad instruction associated with the landing pad. |
392 | | const LandingPadInst *getLandingPadInst() const; |
393 | 3.73M | LandingPadInst *getLandingPadInst() { |
394 | 3.73M | return const_cast<LandingPadInst *>( |
395 | 3.73M | static_cast<const BasicBlock *>(this)->getLandingPadInst()); |
396 | 3.73M | } |
397 | | |
398 | | /// \brief Return true if it is legal to hoist instructions into this block. |
399 | | bool isLegalToHoistInto() const; |
400 | | |
401 | | private: |
402 | | /// \brief Increment the internal refcount of the number of BlockAddresses |
403 | | /// referencing this BasicBlock by \p Amt. |
404 | | /// |
405 | | /// This is almost always 0, sometimes one possibly, but almost never 2, and |
406 | | /// inconceivably 3 or more. |
407 | 1.53k | void AdjustBlockAddressRefCount(int Amt) { |
408 | 1.53k | setValueSubclassData(getSubclassDataFromValue()+Amt); |
409 | 1.53k | assert((int)(signed char)getSubclassDataFromValue() >= 0 && |
410 | 1.53k | "Refcount wrap-around"); |
411 | 1.53k | } |
412 | | |
413 | | /// \brief Shadow Value::setValueSubclassData with a private forwarding method |
414 | | /// so that any future subclasses cannot accidentally use it. |
415 | 1.53k | void setValueSubclassData(unsigned short D) { |
416 | 1.53k | Value::setValueSubclassData(D); |
417 | 1.53k | } |
418 | | }; |
419 | | |
420 | | // Create wrappers for C Binding types (see CBindingWrapping.h). |
421 | | DEFINE_SIMPLE_CONVERSION_FUNCTIONS(BasicBlock, LLVMBasicBlockRef) |
422 | | |
423 | | } // end namespace llvm |
424 | | |
425 | | #endif // LLVM_IR_BASICBLOCK_H |