LCOV - code coverage report
Current view: top level - include/llvm/IR - CFG.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 27 27 100.0 %
Date: 2018-05-20 00:06:23 Functions: 7 7 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- CFG.h - Process LLVM structures as graphs ----------------*- 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 defines specializations of GraphTraits that allow Function and
      11             : // BasicBlock graphs to be treated as proper graphs for generic algorithms.
      12             : //
      13             : //===----------------------------------------------------------------------===//
      14             : 
      15             : #ifndef LLVM_IR_CFG_H
      16             : #define LLVM_IR_CFG_H
      17             : 
      18             : #include "llvm/ADT/GraphTraits.h"
      19             : #include "llvm/ADT/iterator.h"
      20             : #include "llvm/ADT/iterator_range.h"
      21             : #include "llvm/IR/BasicBlock.h"
      22             : #include "llvm/IR/Function.h"
      23             : #include "llvm/IR/InstrTypes.h"
      24             : #include "llvm/IR/Value.h"
      25             : #include "llvm/Support/Casting.h"
      26             : #include "llvm/Support/type_traits.h"
      27             : #include <cassert>
      28             : #include <cstddef>
      29             : #include <iterator>
      30             : 
      31             : namespace llvm {
      32             : 
      33             : //===----------------------------------------------------------------------===//
      34             : // BasicBlock pred_iterator definition
      35             : //===----------------------------------------------------------------------===//
      36             : 
      37             : template <class Ptr, class USE_iterator> // Predecessor Iterator
      38             : class PredIterator : public std::iterator<std::forward_iterator_tag,
      39             :                                           Ptr, ptrdiff_t, Ptr*, Ptr*> {
      40             :   using super =
      41             :       std::iterator<std::forward_iterator_tag, Ptr, ptrdiff_t, Ptr*, Ptr*>;
      42             :   using Self = PredIterator<Ptr, USE_iterator>;
      43             :   USE_iterator It;
      44             : 
      45    42654764 :   inline void advancePastNonTerminators() {
      46             :     // Loop to ignore non-terminator uses (for example BlockAddresses).
      47    42658078 :     while (!It.atEnd() && !isa<TerminatorInst>(*It))
      48             :       ++It;
      49    42654764 :   }
      50             : 
      51             : public:
      52             :   using pointer = typename super::pointer;
      53             :   using reference = typename super::reference;
      54             : 
      55             :   PredIterator() = default;
      56    45203320 :   explicit inline PredIterator(Ptr *bb) : It(bb->user_begin()) {
      57    22601660 :     advancePastNonTerminators();
      58             :   }
      59             :   inline PredIterator(Ptr *bb, bool) : It(bb->user_end()) {}
      60             : 
      61             :   inline bool operator==(const Self& x) const { return It == x.It; }
      62        7778 :   inline bool operator!=(const Self& x) const { return !operator==(x); }
      63             : 
      64             :   inline reference operator*() const {
      65             :     assert(!It.atEnd() && "pred_iterator out of range!");
      66    19213964 :     return cast<TerminatorInst>(*It)->getParent();
      67             :   }
      68             :   inline pointer *operator->() const { return &operator*(); }
      69             : 
      70             :   inline Self& operator++() {   // Preincrement
      71             :     assert(!It.atEnd() && "pred_iterator out of range!");
      72    19982780 :     ++It; advancePastNonTerminators();
      73             :     return *this;
      74             :   }
      75             : 
      76             :   inline Self operator++(int) { // Postincrement
      77             :     Self tmp = *this; ++*this; return tmp;
      78             :   }
      79             : 
      80             :   /// getOperandNo - Return the operand number in the predecessor's
      81             :   /// terminator of the successor.
      82             :   unsigned getOperandNo() const {
      83             :     return It.getOperandNo();
      84             :   }
      85             : 
      86             :   /// getUse - Return the operand Use in the predecessor's terminator
      87             :   /// of the successor.
      88             :   Use &getUse() const {
      89             :     return It.getUse();
      90             :   }
      91             : };
      92             : 
      93             : using pred_iterator = PredIterator<BasicBlock, Value::user_iterator>;
      94             : using const_pred_iterator =
      95             :     PredIterator<const BasicBlock, Value::const_user_iterator>;
      96             : using pred_range = iterator_range<pred_iterator>;
      97             : using pred_const_range = iterator_range<const_pred_iterator>;
      98             : 
      99     9205071 : inline pred_iterator pred_begin(BasicBlock *BB) { return pred_iterator(BB); }
     100             : inline const_pred_iterator pred_begin(const BasicBlock *BB) {
     101    13396563 :   return const_pred_iterator(BB);
     102             : }
     103             : inline pred_iterator pred_end(BasicBlock *BB) { return pred_iterator(BB, true);}
     104             : inline const_pred_iterator pred_end(const BasicBlock *BB) {
     105             :   return const_pred_iterator(BB, true);
     106             : }
     107             : inline bool pred_empty(const BasicBlock *BB) {
     108             :   return pred_begin(BB) == pred_end(BB);
     109             : }
     110      615085 : inline unsigned pred_size(const BasicBlock *BB) {
     111      615085 :   return std::distance(pred_begin(BB), pred_end(BB));
     112             : }
     113             : inline pred_range predecessors(BasicBlock *BB) {
     114             :   return pred_range(pred_begin(BB), pred_end(BB));
     115             : }
     116             : inline pred_const_range predecessors(const BasicBlock *BB) {
     117             :   return pred_const_range(pred_begin(BB), pred_end(BB));
     118             : }
     119             : 
     120             : //===----------------------------------------------------------------------===//
     121             : // BasicBlock succ_iterator helpers
     122             : //===----------------------------------------------------------------------===//
     123             : 
     124             : using succ_iterator =
     125             :     TerminatorInst::SuccIterator<TerminatorInst *, BasicBlock>;
     126             : using succ_const_iterator =
     127             :     TerminatorInst::SuccIterator<const TerminatorInst *, const BasicBlock>;
     128             : using succ_range = iterator_range<succ_iterator>;
     129             : using succ_const_range = iterator_range<succ_const_iterator>;
     130             : 
     131             : inline succ_iterator succ_begin(BasicBlock *BB) {
     132             :   return succ_iterator(BB->getTerminator());
     133             : }
     134             : inline succ_const_iterator succ_begin(const BasicBlock *BB) {
     135    10496183 :   return succ_const_iterator(BB->getTerminator());
     136             : }
     137    32281119 : inline succ_iterator succ_end(BasicBlock *BB) {
     138    32281119 :   return succ_iterator(BB->getTerminator(), true);
     139             : }
     140    17540979 : inline succ_const_iterator succ_end(const BasicBlock *BB) {
     141    35081958 :   return succ_const_iterator(BB->getTerminator(), true);
     142             : }
     143             : inline bool succ_empty(const BasicBlock *BB) {
     144      316877 :   return succ_begin(BB) == succ_end(BB);
     145             : }
     146             : inline unsigned succ_size(const BasicBlock *BB) {
     147      563845 :   return std::distance(succ_begin(BB), succ_end(BB));
     148             : }
     149     3481653 : inline succ_range successors(BasicBlock *BB) {
     150     6963306 :   return succ_range(succ_begin(BB), succ_end(BB));
     151             : }
     152     1577767 : inline succ_const_range successors(const BasicBlock *BB) {
     153     3155534 :   return succ_const_range(succ_begin(BB), succ_end(BB));
     154             : }
     155             : 
     156             : template <typename T, typename U>
     157             : struct isPodLike<TerminatorInst::SuccIterator<T, U>> {
     158             :   static const bool value = isPodLike<T>::value;
     159             : };
     160             : 
     161             : //===--------------------------------------------------------------------===//
     162             : // GraphTraits specializations for basic block graphs (CFGs)
     163             : //===--------------------------------------------------------------------===//
     164             : 
     165             : // Provide specializations of GraphTraits to be able to treat a function as a
     166             : // graph of basic blocks...
     167             : 
     168             : template <> struct GraphTraits<BasicBlock*> {
     169             :   using NodeRef = BasicBlock *;
     170             :   using ChildIteratorType = succ_iterator;
     171             : 
     172             :   static NodeRef getEntryNode(BasicBlock *BB) { return BB; }
     173             :   static ChildIteratorType child_begin(NodeRef N) { return succ_begin(N); }
     174    25196885 :   static ChildIteratorType child_end(NodeRef N) { return succ_end(N); }
     175             : };
     176             : 
     177             : template <> struct GraphTraits<const BasicBlock*> {
     178             :   using NodeRef = const BasicBlock *;
     179             :   using ChildIteratorType = succ_const_iterator;
     180             : 
     181             :   static NodeRef getEntryNode(const BasicBlock *BB) { return BB; }
     182             : 
     183             :   static ChildIteratorType child_begin(NodeRef N) { return succ_begin(N); }
     184    10275208 :   static ChildIteratorType child_end(NodeRef N) { return succ_end(N); }
     185             : };
     186             : 
     187             : // Provide specializations of GraphTraits to be able to treat a function as a
     188             : // graph of basic blocks... and to walk it in inverse order.  Inverse order for
     189             : // a function is considered to be when traversing the predecessor edges of a BB
     190             : // instead of the successor edges.
     191             : //
     192             : template <> struct GraphTraits<Inverse<BasicBlock*>> {
     193             :   using NodeRef = BasicBlock *;
     194             :   using ChildIteratorType = pred_iterator;
     195             : 
     196         313 :   static NodeRef getEntryNode(Inverse<BasicBlock *> G) { return G.Graph; }
     197             :   static ChildIteratorType child_begin(NodeRef N) { return pred_begin(N); }
     198             :   static ChildIteratorType child_end(NodeRef N) { return pred_end(N); }
     199             : };
     200             : 
     201             : template <> struct GraphTraits<Inverse<const BasicBlock*>> {
     202             :   using NodeRef = const BasicBlock *;
     203             :   using ChildIteratorType = const_pred_iterator;
     204             : 
     205         306 :   static NodeRef getEntryNode(Inverse<const BasicBlock *> G) { return G.Graph; }
     206             :   static ChildIteratorType child_begin(NodeRef N) { return pred_begin(N); }
     207             :   static ChildIteratorType child_end(NodeRef N) { return pred_end(N); }
     208             : };
     209             : 
     210             : //===--------------------------------------------------------------------===//
     211             : // GraphTraits specializations for function basic block graphs (CFGs)
     212             : //===--------------------------------------------------------------------===//
     213             : 
     214             : // Provide specializations of GraphTraits to be able to treat a function as a
     215             : // graph of basic blocks... these are the same as the basic block iterators,
     216             : // except that the root node is implicitly the first node of the function.
     217             : //
     218             : template <> struct GraphTraits<Function*> : public GraphTraits<BasicBlock*> {
     219             :   static NodeRef getEntryNode(Function *F) { return &F->getEntryBlock(); }
     220             : 
     221             :   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
     222             :   using nodes_iterator = pointer_iterator<Function::iterator>;
     223             : 
     224             :   static nodes_iterator nodes_begin(Function *F) {
     225             :     return nodes_iterator(F->begin());
     226             :   }
     227             : 
     228             :   static nodes_iterator nodes_end(Function *F) {
     229             :     return nodes_iterator(F->end());
     230             :   }
     231             : 
     232             :   static size_t size(Function *F) { return F->size(); }
     233             : };
     234             : template <> struct GraphTraits<const Function*> :
     235             :   public GraphTraits<const BasicBlock*> {
     236             :   static NodeRef getEntryNode(const Function *F) { return &F->getEntryBlock(); }
     237             : 
     238             :   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
     239             :   using nodes_iterator = pointer_iterator<Function::const_iterator>;
     240             : 
     241             :   static nodes_iterator nodes_begin(const Function *F) {
     242             :     return nodes_iterator(F->begin());
     243             :   }
     244             : 
     245             :   static nodes_iterator nodes_end(const Function *F) {
     246             :     return nodes_iterator(F->end());
     247             :   }
     248             : 
     249             :   static size_t size(const Function *F) { return F->size(); }
     250             : };
     251             : 
     252             : // Provide specializations of GraphTraits to be able to treat a function as a
     253             : // graph of basic blocks... and to walk it in inverse order.  Inverse order for
     254             : // a function is considered to be when traversing the predecessor edges of a BB
     255             : // instead of the successor edges.
     256             : //
     257             : template <> struct GraphTraits<Inverse<Function*>> :
     258             :   public GraphTraits<Inverse<BasicBlock*>> {
     259             :   static NodeRef getEntryNode(Inverse<Function *> G) {
     260             :     return &G.Graph->getEntryBlock();
     261             :   }
     262             : };
     263             : template <> struct GraphTraits<Inverse<const Function*>> :
     264             :   public GraphTraits<Inverse<const BasicBlock*>> {
     265             :   static NodeRef getEntryNode(Inverse<const Function *> G) {
     266             :     return &G.Graph->getEntryBlock();
     267             :   }
     268             : };
     269             : 
     270             : } // end namespace llvm
     271             : 
     272             : #endif // LLVM_IR_CFG_H

Generated by: LCOV version 1.13