LCOV - code coverage report
Current view: top level - include/llvm/IR - CFG.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 46 46 100.0 %
Date: 2017-09-14 15:23:50 Functions: 6 6 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    39340479 :   inline void advancePastNonTerminators() {
      46             :     // Loop to ignore non-terminator uses (for example BlockAddresses).
      47   102223798 :     while (!It.atEnd() && !isa<TerminatorInst>(*It))
      48        2566 :       ++It;
      49    39340479 :   }
      50             : 
      51             : public:
      52             :   using pointer = typename super::pointer;
      53             :   using reference = typename super::reference;
      54             : 
      55             :   PredIterator() = default;
      56    41088154 :   explicit inline PredIterator(Ptr *bb) : It(bb->user_begin()) {
      57    20544077 :     advancePastNonTerminators();
      58             :   }
      59    20600672 :   inline PredIterator(Ptr *bb, bool) : It(bb->user_end()) {}
      60             : 
      61    81220746 :   inline bool operator==(const Self& x) const { return It == x.It; }
      62    23109324 :   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    56107758 :     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    37459126 :     ++It; advancePastNonTerminators();
      73             :     return *this;
      74             :   }
      75             : 
      76             :   inline Self operator++(int) { // Postincrement
      77       14654 :     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     8658478 : inline pred_iterator pred_begin(BasicBlock *BB) { return pred_iterator(BB); }
     100             : inline const_pred_iterator pred_begin(const BasicBlock *BB) {
     101    11885578 :   return const_pred_iterator(BB);
     102             : }
     103     8714735 : inline pred_iterator pred_end(BasicBlock *BB) { return pred_iterator(BB, true);}
     104             : inline const_pred_iterator pred_end(const BasicBlock *BB) {
     105    11885895 :   return const_pred_iterator(BB, true);
     106             : }
     107             : inline bool pred_empty(const BasicBlock *BB) {
     108    12842620 :   return pred_begin(BB) == pred_end(BB);
     109             : }
     110             : inline pred_range predecessors(BasicBlock *BB) {
     111     7477411 :   return pred_range(pred_begin(BB), pred_end(BB));
     112             : }
     113             : inline pred_const_range predecessors(const BasicBlock *BB) {
     114        8428 :   return pred_const_range(pred_begin(BB), pred_end(BB));
     115             : }
     116             : 
     117             : //===----------------------------------------------------------------------===//
     118             : // BasicBlock succ_iterator helpers
     119             : //===----------------------------------------------------------------------===//
     120             : 
     121             : using succ_iterator =
     122             :     TerminatorInst::SuccIterator<TerminatorInst *, BasicBlock>;
     123             : using succ_const_iterator =
     124             :     TerminatorInst::SuccIterator<const TerminatorInst *, const BasicBlock>;
     125             : using succ_range = iterator_range<succ_iterator>;
     126             : using succ_const_range = iterator_range<succ_const_iterator>;
     127             : 
     128             : inline succ_iterator succ_begin(BasicBlock *BB) {
     129    21060194 :   return succ_iterator(BB->getTerminator());
     130             : }
     131             : inline succ_const_iterator succ_begin(const BasicBlock *BB) {
     132     7460650 :   return succ_const_iterator(BB->getTerminator());
     133             : }
     134    26522032 : inline succ_iterator succ_end(BasicBlock *BB) {
     135    53044064 :   return succ_iterator(BB->getTerminator(), true);
     136             : }
     137    12848716 : inline succ_const_iterator succ_end(const BasicBlock *BB) {
     138    25697432 :   return succ_const_iterator(BB->getTerminator(), true);
     139             : }
     140             : inline bool succ_empty(const BasicBlock *BB) {
     141      621284 :   return succ_begin(BB) == succ_end(BB);
     142             : }
     143     3094589 : inline succ_range successors(BasicBlock *BB) {
     144     9283767 :   return succ_range(succ_begin(BB), succ_end(BB));
     145             : }
     146     1215435 : inline succ_const_range successors(const BasicBlock *BB) {
     147     3646305 :   return succ_const_range(succ_begin(BB), succ_end(BB));
     148             : }
     149             : 
     150             : template <typename T, typename U>
     151             : struct isPodLike<TerminatorInst::SuccIterator<T, U>> {
     152             :   static const bool value = isPodLike<T>::value;
     153             : };
     154             : 
     155             : //===--------------------------------------------------------------------===//
     156             : // GraphTraits specializations for basic block graphs (CFGs)
     157             : //===--------------------------------------------------------------------===//
     158             : 
     159             : // Provide specializations of GraphTraits to be able to treat a function as a
     160             : // graph of basic blocks...
     161             : 
     162             : template <> struct GraphTraits<BasicBlock*> {
     163             :   using NodeRef = BasicBlock *;
     164             :   using ChildIteratorType = succ_iterator;
     165             : 
     166             :   static NodeRef getEntryNode(BasicBlock *BB) { return BB; }
     167    14631668 :   static ChildIteratorType child_begin(NodeRef N) { return succ_begin(N); }
     168    20090279 :   static ChildIteratorType child_end(NodeRef N) { return succ_end(N); }
     169             : };
     170             : 
     171             : template <> struct GraphTraits<const BasicBlock*> {
     172             :   using NodeRef = const BasicBlock *;
     173             :   using ChildIteratorType = succ_const_iterator;
     174             : 
     175             :   static NodeRef getEntryNode(const BasicBlock *BB) { return BB; }
     176             : 
     177     3065198 :   static ChildIteratorType child_begin(NodeRef N) { return succ_begin(N); }
     178     5183046 :   static ChildIteratorType child_end(NodeRef N) { return succ_end(N); }
     179             : };
     180             : 
     181             : // Provide specializations of GraphTraits to be able to treat a function as a
     182             : // graph of basic blocks... and to walk it in inverse order.  Inverse order for
     183             : // a function is considered to be when traversing the predecessor edges of a BB
     184             : // instead of the successor edges.
     185             : //
     186             : template <> struct GraphTraits<Inverse<BasicBlock*>> {
     187             :   using NodeRef = BasicBlock *;
     188             :   using ChildIteratorType = pred_iterator;
     189             : 
     190         308 :   static NodeRef getEntryNode(Inverse<BasicBlock *> G) { return G.Graph; }
     191     4656267 :   static ChildIteratorType child_begin(NodeRef N) { return pred_begin(N); }
     192     4660044 :   static ChildIteratorType child_end(NodeRef N) { return pred_end(N); }
     193             : };
     194             : 
     195             : template <> struct GraphTraits<Inverse<const BasicBlock*>> {
     196             :   using NodeRef = const BasicBlock *;
     197             :   using ChildIteratorType = const_pred_iterator;
     198             : 
     199         318 :   static NodeRef getEntryNode(Inverse<const BasicBlock *> G) { return G.Graph; }
     200         303 :   static ChildIteratorType child_begin(NodeRef N) { return pred_begin(N); }
     201         620 :   static ChildIteratorType child_end(NodeRef N) { return pred_end(N); }
     202             : };
     203             : 
     204             : //===--------------------------------------------------------------------===//
     205             : // GraphTraits specializations for function basic block graphs (CFGs)
     206             : //===--------------------------------------------------------------------===//
     207             : 
     208             : // Provide specializations of GraphTraits to be able to treat a function as a
     209             : // graph of basic blocks... these are the same as the basic block iterators,
     210             : // except that the root node is implicitly the first node of the function.
     211             : //
     212             : template <> struct GraphTraits<Function*> : public GraphTraits<BasicBlock*> {
     213     2165892 :   static NodeRef getEntryNode(Function *F) { return &F->getEntryBlock(); }
     214             : 
     215             :   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
     216             :   using nodes_iterator = pointer_iterator<Function::iterator>;
     217             : 
     218             :   static nodes_iterator nodes_begin(Function *F) {
     219      200582 :     return nodes_iterator(F->begin());
     220             :   }
     221             : 
     222             :   static nodes_iterator nodes_end(Function *F) {
     223      200582 :     return nodes_iterator(F->end());
     224             :   }
     225             : 
     226             :   static size_t size(Function *F) { return F->size(); }
     227             : };
     228             : template <> struct GraphTraits<const Function*> :
     229             :   public GraphTraits<const BasicBlock*> {
     230      142329 :   static NodeRef getEntryNode(const Function *F) { return &F->getEntryBlock(); }
     231             : 
     232             :   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
     233             :   using nodes_iterator = pointer_iterator<Function::const_iterator>;
     234             : 
     235             :   static nodes_iterator nodes_begin(const Function *F) {
     236           4 :     return nodes_iterator(F->begin());
     237             :   }
     238             : 
     239             :   static nodes_iterator nodes_end(const Function *F) {
     240           4 :     return nodes_iterator(F->end());
     241             :   }
     242             : 
     243             :   static size_t size(const Function *F) { return F->size(); }
     244             : };
     245             : 
     246             : // Provide specializations of GraphTraits to be able to treat a function as a
     247             : // graph of basic blocks... and to walk it in inverse order.  Inverse order for
     248             : // a function is considered to be when traversing the predecessor edges of a BB
     249             : // instead of the successor edges.
     250             : //
     251             : template <> struct GraphTraits<Inverse<Function*>> :
     252             :   public GraphTraits<Inverse<BasicBlock*>> {
     253             :   static NodeRef getEntryNode(Inverse<Function *> G) {
     254             :     return &G.Graph->getEntryBlock();
     255             :   }
     256             : };
     257             : template <> struct GraphTraits<Inverse<const Function*>> :
     258             :   public GraphTraits<Inverse<const BasicBlock*>> {
     259             :   static NodeRef getEntryNode(Inverse<const Function *> G) {
     260             :     return &G.Graph->getEntryBlock();
     261             :   }
     262             : };
     263             : 
     264             : } // end namespace llvm
     265             : 
     266             : #endif // LLVM_IR_CFG_H

Generated by: LCOV version 1.13