Line data Source code
1 : //===- CFG.h ----------------------------------------------------*- 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 : /// \file
10 : ///
11 : /// This file provides various utilities for inspecting and working with the
12 : /// control flow graph in LLVM IR. This includes generic facilities for
13 : /// iterating successors and predecessors of basic blocks, the successors of
14 : /// specific terminator instructions, etc. It also defines specializations of
15 : /// GraphTraits that allow Function and BasicBlock graphs to be treated as
16 : /// proper graphs for generic algorithms.
17 : ///
18 : //===----------------------------------------------------------------------===//
19 :
20 : #ifndef LLVM_IR_CFG_H
21 : #define LLVM_IR_CFG_H
22 :
23 : #include "llvm/ADT/GraphTraits.h"
24 : #include "llvm/ADT/iterator.h"
25 : #include "llvm/ADT/iterator_range.h"
26 : #include "llvm/IR/BasicBlock.h"
27 : #include "llvm/IR/Function.h"
28 : #include "llvm/IR/InstrTypes.h"
29 : #include "llvm/IR/Value.h"
30 : #include "llvm/Support/Casting.h"
31 : #include "llvm/Support/type_traits.h"
32 : #include <cassert>
33 : #include <cstddef>
34 : #include <iterator>
35 :
36 : namespace llvm {
37 :
38 : //===----------------------------------------------------------------------===//
39 : // BasicBlock pred_iterator definition
40 : //===----------------------------------------------------------------------===//
41 :
42 : template <class Ptr, class USE_iterator> // Predecessor Iterator
43 : class PredIterator : public std::iterator<std::forward_iterator_tag,
44 : Ptr, ptrdiff_t, Ptr*, Ptr*> {
45 : using super =
46 : std::iterator<std::forward_iterator_tag, Ptr, ptrdiff_t, Ptr*, Ptr*>;
47 : using Self = PredIterator<Ptr, USE_iterator>;
48 : USE_iterator It;
49 :
50 77139327 : inline void advancePastNonTerminators() {
51 : // Loop to ignore non-terminator uses (for example BlockAddresses).
52 77143299 : while (!It.atEnd()) {
53 : if (auto *Inst = dyn_cast<Instruction>(*It))
54 47930524 : if (Inst->isTerminator())
55 : break;
56 :
57 : ++It;
58 : }
59 77139327 : }
60 11579732 :
61 : public:
62 11580022 : using pointer = typename super::pointer;
63 : using reference = typename super::reference;
64 7564624 :
65 : PredIterator() = default;
66 26488550 : explicit inline PredIterator(Ptr *bb) : It(bb->user_begin()) {
67 26488550 : advancePastNonTerminators();
68 : }
69 11579732 : inline PredIterator(Ptr *bb, bool) : It(bb->user_end()) {}
70 27572093 :
71 : inline bool operator==(const Self& x) const { return It == x.It; }
72 27583305 : inline bool operator!=(const Self& x) const { return !operator==(x); }
73 :
74 16314557 : inline reference operator*() const {
75 : assert(!It.atEnd() && "pred_iterator out of range!");
76 28379133 : return cast<Instruction>(*It)->getParent();
77 : }
78 : inline pointer *operator->() const { return &operator*(); }
79 27572093 :
80 : inline Self& operator++() { // Preincrement
81 : assert(!It.atEnd() && "pred_iterator out of range!");
82 28132019 : ++It; advancePastNonTerminators();
83 : return *this;
84 : }
85 :
86 9175974 : inline Self operator++(int) { // Postincrement
87 11692580 : Self tmp = *this; ++*this; return tmp;
88 : }
89 :
90 : /// getOperandNo - Return the operand number in the predecessor's
91 : /// terminator of the successor.
92 : unsigned getOperandNo() const {
93 : return It.getOperandNo();
94 : }
95 :
96 4444856 : /// getUse - Return the operand Use in the predecessor's terminator
97 : /// of the successor.
98 : Use &getUse() const {
99 : return It.getUse();
100 : }
101 : };
102 8474141 :
103 : using pred_iterator = PredIterator<BasicBlock, Value::user_iterator>;
104 : using const_pred_iterator =
105 : PredIterator<const BasicBlock, Value::const_user_iterator>;
106 0 : using pred_range = iterator_range<pred_iterator>;
107 0 : using pred_const_range = iterator_range<const_pred_iterator>;
108 :
109 9773743 : inline pred_iterator pred_begin(BasicBlock *BB) { return pred_iterator(BB); }
110 : inline const_pred_iterator pred_begin(const BasicBlock *BB) {
111 16714625 : return const_pred_iterator(BB);
112 : }
113 0 : inline pred_iterator pred_end(BasicBlock *BB) { return pred_iterator(BB, true);}
114 0 : inline const_pred_iterator pred_end(const BasicBlock *BB) {
115 0 : return const_pred_iterator(BB, true);
116 : }
117 : inline bool pred_empty(const BasicBlock *BB) {
118 : return pred_begin(BB) == pred_end(BB);
119 : }
120 : inline unsigned pred_size(const BasicBlock *BB) {
121 : return std::distance(pred_begin(BB), pred_end(BB));
122 : }
123 : inline pred_range predecessors(BasicBlock *BB) {
124 : return pred_range(pred_begin(BB), pred_end(BB));
125 : }
126 : inline pred_const_range predecessors(const BasicBlock *BB) {
127 : return pred_const_range(pred_begin(BB), pred_end(BB));
128 : }
129 4185582 :
130 : //===----------------------------------------------------------------------===//
131 7506998 : // Instruction and BasicBlock succ_iterator helpers
132 : //===----------------------------------------------------------------------===//
133 0 :
134 0 : template <class InstructionT, class BlockT>
135 0 : class SuccIterator
136 : : public iterator_facade_base<SuccIterator<InstructionT, BlockT>,
137 : std::random_access_iterator_tag, BlockT, int,
138 : BlockT *, BlockT *> {
139 : public:
140 2516618 : using difference_type = int;
141 2516618 : using pointer = BlockT *;
142 : using reference = BlockT *;
143 :
144 : private:
145 : InstructionT *Inst;
146 : int Idx;
147 : using Self = SuccIterator<InstructionT, BlockT>;
148 :
149 : inline bool index_is_valid(int Idx) {
150 : // Note that we specially support the index of zero being valid even in the
151 : // face of a null instruction.
152 : return Idx >= 0 && (Idx == 0 || Idx <= (int)Inst->getNumSuccessors());
153 : }
154 :
155 : /// Proxy object to allow write access in operator[]
156 : class SuccessorProxy {
157 : Self It;
158 :
159 : public:
160 : explicit SuccessorProxy(const Self &It) : It(It) {}
161 :
162 : SuccessorProxy(const SuccessorProxy &) = default;
163 :
164 0 : SuccessorProxy &operator=(SuccessorProxy RHS) {
165 : *this = reference(RHS);
166 0 : return *this;
167 : }
168 :
169 : SuccessorProxy &operator=(reference RHS) {
170 1 : It.Inst->setSuccessor(It.Idx, RHS);
171 : return *this;
172 : }
173 :
174 0 : operator reference() const { return *It; }
175 : };
176 :
177 : public:
178 : // begin iterator
179 0 : explicit inline SuccIterator(InstructionT *Inst) : Inst(Inst), Idx(0) {}
180 : // end iterator
181 0 : inline SuccIterator(InstructionT *Inst, bool) : Inst(Inst) {
182 30005044 : if (Inst)
183 53226625 : Idx = Inst->getNumSuccessors();
184 : else
185 : // Inst == NULL happens, if a basic block is not fully constructed and
186 : // consequently getTerminator() returns NULL. In this case we construct
187 : // a SuccIterator which describes a basic block that has zero
188 : // successors.
189 : // Defining SuccIterator for incomplete and malformed CFGs is especially
190 : // useful for debugging.
191 : Idx = 0;
192 : }
193 :
194 : /// This is used to interface between code that wants to
195 : /// operate on terminator instructions directly.
196 0 : int getSuccessorIndex() const { return Idx; }
197 :
198 1444783 : inline bool operator==(const Self &x) const { return Idx == x.Idx; }
199 :
200 27821927 : inline BlockT *operator*() const { return Inst->getSuccessor(Idx); }
201 :
202 41209679 : // We use the basic block pointer directly for operator->.
203 41234233 : inline BlockT *operator->() const { return operator*(); }
204 :
205 : inline bool operator<(const Self &RHS) const {
206 : assert(Inst == RHS.Inst && "Cannot compare iterators of different blocks!");
207 : return Idx < RHS.Idx;
208 : }
209 :
210 0 : int operator-(const Self &RHS) const {
211 : assert(Inst == RHS.Inst && "Cannot compare iterators of different blocks!");
212 2204494 : return Idx - RHS.Idx;
213 : }
214 :
215 : inline Self &operator+=(int RHS) {
216 22699045 : int NewIdx = Idx + RHS;
217 : assert(index_is_valid(NewIdx) && "Iterator index out of bound");
218 17953946 : Idx = NewIdx;
219 : return *this;
220 24129679 : }
221 :
222 : inline Self &operator-=(int RHS) { return operator+=(-RHS); }
223 :
224 : // Specially implement the [] operation using a proxy object to support
225 : // assignment.
226 : inline SuccessorProxy operator[](int Offset) {
227 : Self TmpIt = *this;
228 : TmpIt += Offset;
229 : return SuccessorProxy(TmpIt);
230 0 : }
231 :
232 16245832 : /// Get the source BlockT of this iterator.
233 : inline BlockT *getSource() {
234 0 : assert(Inst && "Source not available, if basic block was malformed");
235 : return Inst->getParent();
236 6917358 : }
237 : };
238 23531912 :
239 : template <typename T, typename U> struct isPodLike<SuccIterator<T, U>> {
240 0 : static const bool value = isPodLike<T>::value;
241 : };
242 :
243 : using succ_iterator = SuccIterator<Instruction, BasicBlock>;
244 0 : using succ_const_iterator = SuccIterator<const Instruction, const BasicBlock>;
245 : using succ_range = iterator_range<succ_iterator>;
246 54 : using succ_const_range = iterator_range<succ_const_iterator>;
247 :
248 : inline succ_iterator succ_begin(Instruction *I) { return succ_iterator(I); }
249 : inline succ_const_iterator succ_begin(const Instruction *I) {
250 : return succ_const_iterator(I);
251 : }
252 : inline succ_iterator succ_end(Instruction *I) { return succ_iterator(I, true); }
253 : inline succ_const_iterator succ_end(const Instruction *I) {
254 : return succ_const_iterator(I, true);
255 : }
256 : inline bool succ_empty(const Instruction *I) {
257 : return succ_begin(I) == succ_end(I);
258 : }
259 : inline unsigned succ_size(const Instruction *I) {
260 : return std::distance(succ_begin(I), succ_end(I));
261 : }
262 : inline succ_range successors(Instruction *I) {
263 : return succ_range(succ_begin(I), succ_end(I));
264 : }
265 : inline succ_const_range successors(const Instruction *I) {
266 : return succ_const_range(succ_begin(I), succ_end(I));
267 : }
268 :
269 : inline succ_iterator succ_begin(BasicBlock *BB) {
270 : return succ_iterator(BB->getTerminator());
271 : }
272 : inline succ_const_iterator succ_begin(const BasicBlock *BB) {
273 16870770 : return succ_const_iterator(BB->getTerminator());
274 : }
275 15959076 : inline succ_iterator succ_end(BasicBlock *BB) {
276 15959076 : return succ_iterator(BB->getTerminator(), true);
277 : }
278 33197244 : inline succ_const_iterator succ_end(const BasicBlock *BB) {
279 33197244 : return succ_const_iterator(BB->getTerminator(), true);
280 : }
281 : inline bool succ_empty(const BasicBlock *BB) {
282 406052 : return succ_begin(BB) == succ_end(BB);
283 : }
284 : inline unsigned succ_size(const BasicBlock *BB) {
285 788211 : return std::distance(succ_begin(BB), succ_end(BB));
286 : }
287 1116991 : inline succ_range successors(BasicBlock *BB) {
288 1116991 : return succ_range(succ_begin(BB), succ_end(BB));
289 : }
290 2482910 : inline succ_const_range successors(const BasicBlock *BB) {
291 2482910 : return succ_const_range(succ_begin(BB), succ_end(BB));
292 : }
293 23183 :
294 : //===--------------------------------------------------------------------===//
295 38290369 : // GraphTraits specializations for basic block graphs (CFGs)
296 38290369 : //===--------------------------------------------------------------------===//
297 :
298 23183 : // Provide specializations of GraphTraits to be able to treat a function as a
299 23183 : // graph of basic blocks...
300 :
301 : template <> struct GraphTraits<BasicBlock*> {
302 : using NodeRef = BasicBlock *;
303 249 : using ChildIteratorType = succ_iterator;
304 249 :
305 : static NodeRef getEntryNode(BasicBlock *BB) { return BB; }
306 191 : static ChildIteratorType child_begin(NodeRef N) { return succ_begin(N); }
307 14973602 : static ChildIteratorType child_end(NodeRef N) { return succ_end(N); }
308 3773455 : };
309 :
310 4 : template <> struct GraphTraits<const BasicBlock*> {
311 4 : using NodeRef = const BasicBlock *;
312 : using ChildIteratorType = succ_const_iterator;
313 0 :
314 : static NodeRef getEntryNode(const BasicBlock *BB) { return BB; }
315 128 :
316 128 : static ChildIteratorType child_begin(NodeRef N) { return succ_begin(N); }
317 21015386 : static ChildIteratorType child_end(NodeRef N) { return succ_end(N); }
318 : };
319 :
320 : // Provide specializations of GraphTraits to be able to treat a function as a
321 : // graph of basic blocks... and to walk it in inverse order. Inverse order for
322 : // a function is considered to be when traversing the predecessor edges of a BB
323 : // instead of the successor edges.
324 : //
325 : template <> struct GraphTraits<Inverse<BasicBlock*>> {
326 : using NodeRef = BasicBlock *;
327 33859136 : using ChildIteratorType = pred_iterator;
328 :
329 0 : static NodeRef getEntryNode(Inverse<BasicBlock *> G) { return G.Graph; }
330 : static ChildIteratorType child_begin(NodeRef N) { return pred_begin(N); }
331 0 : static ChildIteratorType child_end(NodeRef N) { return pred_end(N); }
332 : };
333 :
334 : template <> struct GraphTraits<Inverse<const BasicBlock*>> {
335 : using NodeRef = const BasicBlock *;
336 : using ChildIteratorType = const_pred_iterator;
337 23179 :
338 : static NodeRef getEntryNode(Inverse<const BasicBlock *> G) { return G.Graph; }
339 : static ChildIteratorType child_begin(NodeRef N) { return pred_begin(N); }
340 : static ChildIteratorType child_end(NodeRef N) { return pred_end(N); }
341 : };
342 :
343 : //===--------------------------------------------------------------------===//
344 : // GraphTraits specializations for function basic block graphs (CFGs)
345 : //===--------------------------------------------------------------------===//
346 :
347 : // Provide specializations of GraphTraits to be able to treat a function as a
348 : // graph of basic blocks... these are the same as the basic block iterators,
349 : // except that the root node is implicitly the first node of the function.
350 : //
351 0 : template <> struct GraphTraits<Function*> : public GraphTraits<BasicBlock*> {
352 : static NodeRef getEntryNode(Function *F) { return &F->getEntryBlock(); }
353 :
354 : // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
355 : using nodes_iterator = pointer_iterator<Function::iterator>;
356 :
357 : static nodes_iterator nodes_begin(Function *F) {
358 0 : return nodes_iterator(F->begin());
359 : }
360 0 :
361 : static nodes_iterator nodes_end(Function *F) {
362 : return nodes_iterator(F->end());
363 : }
364 :
365 : static size_t size(Function *F) { return F->size(); }
366 : };
367 : template <> struct GraphTraits<const Function*> :
368 : public GraphTraits<const BasicBlock*> {
369 : static NodeRef getEntryNode(const Function *F) { return &F->getEntryBlock(); }
370 :
371 : // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
372 : using nodes_iterator = pointer_iterator<Function::const_iterator>;
373 :
374 : static nodes_iterator nodes_begin(const Function *F) {
375 : return nodes_iterator(F->begin());
376 : }
377 :
378 : static nodes_iterator nodes_end(const Function *F) {
379 : return nodes_iterator(F->end());
380 : }
381 :
382 : static size_t size(const Function *F) { return F->size(); }
383 : };
384 :
385 : // Provide specializations of GraphTraits to be able to treat a function as a
386 : // graph of basic blocks... and to walk it in inverse order. Inverse order for
387 : // a function is considered to be when traversing the predecessor edges of a BB
388 : // instead of the successor edges.
389 : //
390 : template <> struct GraphTraits<Inverse<Function*>> :
391 : public GraphTraits<Inverse<BasicBlock*>> {
392 : static NodeRef getEntryNode(Inverse<Function *> G) {
393 : return &G.Graph->getEntryBlock();
394 : }
395 : };
396 : template <> struct GraphTraits<Inverse<const Function*>> :
397 : public GraphTraits<Inverse<const BasicBlock*>> {
398 : static NodeRef getEntryNode(Inverse<const Function *> G) {
399 : return &G.Graph->getEntryBlock();
400 : }
401 : };
402 :
403 : } // end namespace llvm
404 :
405 : #endif // LLVM_IR_CFG_H
|
