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