LCOV - code coverage report
Current view: top level - include/llvm/IR - CFG.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 69 94 73.4 %
Date: 2018-10-16 05:50:02 Functions: 7 21 33.3 %
Legend: Lines: hit not hit

          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    77103346 :   inline void advancePastNonTerminators() {
      51             :     // Loop to ignore non-terminator uses (for example BlockAddresses).
      52    77107318 :     while (!It.atEnd()) {
      53             :       if (auto *Inst = dyn_cast<Instruction>(*It))
      54    47904224 :         if (Inst->isTerminator())
      55             :           break;
      56             : 
      57             :       ++It;
      58             :     }
      59    77103346 :   }
      60    11572655 : 
      61             : public:
      62    11572945 :   using pointer = typename super::pointer;
      63             :   using reference = typename super::reference;
      64     7559980 : 
      65             :   PredIterator() = default;
      66    26480964 :   explicit inline PredIterator(Ptr *bb) : It(bb->user_begin()) {
      67    26480964 :     advancePastNonTerminators();
      68             :   }
      69    11572655 :   inline PredIterator(Ptr *bb, bool) : It(bb->user_end()) {}
      70    27545334 : 
      71             :   inline bool operator==(const Self& x) const { return It == x.It; }
      72    27556532 :   inline bool operator!=(const Self& x) const { return !operator==(x); }
      73             : 
      74    16299139 :   inline reference operator*() const {
      75             :     assert(!It.atEnd() && "pred_iterator out of range!");
      76    28368734 :     return cast<TerminatorInst>(*It)->getParent();
      77             :   }
      78             :   inline pointer *operator->() const { return &operator*(); }
      79    27545334 : 
      80             :   inline Self& operator++() {   // Preincrement
      81             :     assert(!It.atEnd() && "pred_iterator out of range!");
      82    28124169 :     ++It; advancePastNonTerminators();
      83             :     return *this;
      84             :   }
      85             : 
      86     9167295 :   inline Self operator++(int) { // Postincrement
      87    11682926 :     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     4438718 :   /// 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     8465829 : 
     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     9776692 : inline pred_iterator pred_begin(BasicBlock *BB) { return pred_iterator(BB); }
     110             : inline const_pred_iterator pred_begin(const BasicBlock *BB) {
     111    16704103 :   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     4181186 : 
     130             : //===----------------------------------------------------------------------===//
     131     7501739 : // 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     2515643 :   using difference_type = int;
     141     2515643 :   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    30044110 :     if (Inst)
     183    53181114 :       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     1444202 :   inline bool operator==(const Self &x) const { return Idx == x.Idx; }
     199             : 
     200    27819734 :   inline BlockT *operator*() const { return Inst->getSuccessor(Idx); }
     201             : 
     202    41555377 :   // We use the basic block pointer directly for operator->.
     203    41579916 :   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     2244003 :     return Idx - RHS.Idx;
     213             :   }
     214             : 
     215             :   inline Self &operator+=(int RHS) {
     216    22708652 :     int NewIdx = Idx + RHS;
     217             :     assert(index_is_valid(NewIdx) && "Iterator index out of bound");
     218    17940189 :     Idx = NewIdx;
     219             :     return *this;
     220    24171070 :   }
     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    16607176 :   /// 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     6915284 :   }
     237             : };
     238    23571412 : 
     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    16857354 :   return succ_const_iterator(BB->getTerminator());
     274             : }
     275    16004497 : inline succ_iterator succ_end(BasicBlock *BB) {
     276    16004499 :   return succ_iterator(BB->getTerminator(), true);
     277             : }
     278    33173758 : inline succ_const_iterator succ_end(const BasicBlock *BB) {
     279    33173758 :   return succ_const_iterator(BB->getTerminator(), true);
     280             : }
     281             : inline bool succ_empty(const BasicBlock *BB) {
     282      405876 :   return succ_begin(BB) == succ_end(BB);
     283             : }
     284             : inline unsigned succ_size(const BasicBlock *BB) {
     285      787776 :   return std::distance(succ_begin(BB), succ_end(BB));
     286             : }
     287     1115878 : inline succ_range successors(BasicBlock *BB) {
     288     1115878 :   return succ_range(succ_begin(BB), succ_end(BB));
     289             : }
     290     2482011 : inline succ_const_range successors(const BasicBlock *BB) {
     291     2482011 :   return succ_const_range(succ_begin(BB), succ_end(BB));
     292             : }
     293       23168 : 
     294             : //===--------------------------------------------------------------------===//
     295    38637420 : // GraphTraits specializations for basic block graphs (CFGs)
     296    38637420 : //===--------------------------------------------------------------------===//
     297             : 
     298       23168 : // Provide specializations of GraphTraits to be able to treat a function as a
     299       23168 : // 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    14959374 :   static ChildIteratorType child_end(NodeRef N) { return succ_end(N); }
     308     3772492 : };
     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    20996954 :   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    34207530 :   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       23164 : 
     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

Generated by: LCOV version 1.13