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