LCOV - code coverage report
Current view: top level - include/llvm/Analysis - IntervalIterator.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 0 70 0.0 %
Date: 2017-09-14 15:23:50 Functions: 0 11 0.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- IntervalIterator.h - Interval Iterator Declaration -------*- 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 an iterator that enumerates the intervals in a control flow
      11             : // graph of some sort.  This iterator is parametric, allowing iterator over the
      12             : // following types of graphs:
      13             : //
      14             : //  1. A Function* object, composed of BasicBlock nodes.
      15             : //  2. An IntervalPartition& object, composed of Interval nodes.
      16             : //
      17             : // This iterator is defined to walk the control flow graph, returning intervals
      18             : // in depth first order.  These intervals are completely filled in except for
      19             : // the predecessor fields (the successor information is filled in however).
      20             : //
      21             : // By default, the intervals created by this iterator are deleted after they
      22             : // are no longer any use to the iterator.  This behavior can be changed by
      23             : // passing a false value into the intervals_begin() function. This causes the
      24             : // IOwnMem member to be set, and the intervals to not be deleted.
      25             : //
      26             : // It is only safe to use this if all of the intervals are deleted by the caller
      27             : // and all of the intervals are processed.  However, the user of the iterator is
      28             : // not allowed to modify or delete the intervals until after the iterator has
      29             : // been used completely.  The IntervalPartition class uses this functionality.
      30             : //
      31             : //===----------------------------------------------------------------------===//
      32             : 
      33             : #ifndef LLVM_ANALYSIS_INTERVALITERATOR_H
      34             : #define LLVM_ANALYSIS_INTERVALITERATOR_H
      35             : 
      36             : #include "llvm/ADT/GraphTraits.h"
      37             : #include "llvm/Analysis/Interval.h"
      38             : #include "llvm/Analysis/IntervalPartition.h"
      39             : #include "llvm/IR/CFG.h"
      40             : #include "llvm/IR/Function.h"
      41             : #include "llvm/Support/ErrorHandling.h"
      42             : #include <algorithm>
      43             : #include <cassert>
      44             : #include <iterator>
      45             : #include <set>
      46             : #include <utility>
      47             : #include <vector>
      48             : 
      49             : namespace llvm {
      50             : 
      51             : class BasicBlock;
      52             : 
      53             : // getNodeHeader - Given a source graph node and the source graph, return the
      54             : // BasicBlock that is the header node.  This is the opposite of
      55             : // getSourceGraphNode.
      56             : inline BasicBlock *getNodeHeader(BasicBlock *BB) { return BB; }
      57           0 : inline BasicBlock *getNodeHeader(Interval *I) { return I->getHeaderNode(); }
      58             : 
      59             : // getSourceGraphNode - Given a BasicBlock and the source graph, return the
      60             : // source graph node that corresponds to the BasicBlock.  This is the opposite
      61             : // of getNodeHeader.
      62             : inline BasicBlock *getSourceGraphNode(Function *, BasicBlock *BB) {
      63             :   return BB;
      64             : }
      65             : inline Interval *getSourceGraphNode(IntervalPartition *IP, BasicBlock *BB) {
      66           0 :   return IP->getBlockInterval(BB);
      67             : }
      68             : 
      69             : // addNodeToInterval - This method exists to assist the generic ProcessNode
      70             : // with the task of adding a node to the new interval, depending on the
      71             : // type of the source node.  In the case of a CFG source graph (BasicBlock
      72             : // case), the BasicBlock itself is added to the interval.
      73             : inline void addNodeToInterval(Interval *Int, BasicBlock *BB) {
      74           0 :   Int->Nodes.push_back(BB);
      75             : }
      76             : 
      77             : // addNodeToInterval - This method exists to assist the generic ProcessNode
      78             : // with the task of adding a node to the new interval, depending on the
      79             : // type of the source node.  In the case of a CFG source graph (BasicBlock
      80             : // case), the BasicBlock itself is added to the interval.  In the case of
      81             : // an IntervalPartition source graph (Interval case), all of the member
      82             : // BasicBlocks are added to the interval.
      83           0 : inline void addNodeToInterval(Interval *Int, Interval *I) {
      84             :   // Add all of the nodes in I as new nodes in Int.
      85           0 :   Int->Nodes.insert(Int->Nodes.end(), I->Nodes.begin(), I->Nodes.end());
      86           0 : }
      87             : 
      88             : template<class NodeTy, class OrigContainer_t, class GT = GraphTraits<NodeTy *>,
      89             :          class IGT = GraphTraits<Inverse<NodeTy *>>>
      90             : class IntervalIterator {
      91             :   std::vector<std::pair<Interval *, typename Interval::succ_iterator>> IntStack;
      92             :   std::set<BasicBlock *> Visited;
      93             :   OrigContainer_t *OrigContainer;
      94             :   bool IOwnMem;     // If True, delete intervals when done with them
      95             :                     // See file header for conditions of use
      96             : 
      97             : public:
      98             :   using iterator_category = std::forward_iterator_tag;
      99             : 
     100           0 :   IntervalIterator() = default; // End iterator, empty stack
     101             : 
     102           0 :   IntervalIterator(Function *M, bool OwnMemory) : IOwnMem(OwnMemory) {
     103           0 :     OrigContainer = M;
     104           0 :     if (!ProcessInterval(&M->front())) {
     105           0 :       llvm_unreachable("ProcessInterval should never fail for first interval!");
     106             :     }
     107           0 :   }
     108             : 
     109             :   IntervalIterator(IntervalIterator &&x)
     110             :       : IntStack(std::move(x.IntStack)), Visited(std::move(x.Visited)),
     111             :         OrigContainer(x.OrigContainer), IOwnMem(x.IOwnMem) {
     112             :     x.IOwnMem = false;
     113             :   }
     114             : 
     115           0 :   IntervalIterator(IntervalPartition &IP, bool OwnMemory) : IOwnMem(OwnMemory) {
     116           0 :     OrigContainer = &IP;
     117           0 :     if (!ProcessInterval(IP.getRootInterval())) {
     118           0 :       llvm_unreachable("ProcessInterval should never fail for first interval!");
     119             :     }
     120           0 :   }
     121             : 
     122           0 :   ~IntervalIterator() {
     123           0 :     if (IOwnMem)
     124           0 :       while (!IntStack.empty()) {
     125           0 :         delete operator*();
     126           0 :         IntStack.pop_back();
     127             :       }
     128           0 :   }
     129             : 
     130             :   bool operator==(const IntervalIterator &x) const {
     131           0 :     return IntStack == x.IntStack;
     132             :   }
     133           0 :   bool operator!=(const IntervalIterator &x) const { return !(*this == x); }
     134             : 
     135             :   const Interval *operator*() const { return IntStack.back().first; }
     136           0 :   Interval *operator*() { return IntStack.back().first; }
     137             :   const Interval *operator->() const { return operator*(); }
     138             :   Interval *operator->() { return operator*(); }
     139             : 
     140           0 :   IntervalIterator &operator++() { // Preincrement
     141             :     assert(!IntStack.empty() && "Attempting to use interval iterator at end!");
     142             :     do {
     143             :       // All of the intervals on the stack have been visited.  Try visiting
     144             :       // their successors now.
     145           0 :       Interval::succ_iterator &SuccIt = IntStack.back().second,
     146           0 :                                 EndIt = succ_end(IntStack.back().first);
     147           0 :       while (SuccIt != EndIt) {                 // Loop over all interval succs
     148           0 :         bool Done = ProcessInterval(getSourceGraphNode(OrigContainer, *SuccIt));
     149           0 :         ++SuccIt;                               // Increment iterator
     150           0 :         if (Done) return *this;                 // Found a new interval! Use it!
     151             :       }
     152             : 
     153             :       // Free interval memory... if necessary
     154           0 :       if (IOwnMem) delete IntStack.back().first;
     155             : 
     156             :       // We ran out of successors for this interval... pop off the stack
     157           0 :       IntStack.pop_back();
     158           0 :     } while (!IntStack.empty());
     159             : 
     160             :     return *this;
     161             :   }
     162             : 
     163             :   IntervalIterator operator++(int) { // Postincrement
     164             :     IntervalIterator tmp = *this;
     165             :     ++*this;
     166             :     return tmp;
     167             :   }
     168             : 
     169             : private:
     170             :   // ProcessInterval - This method is used during the construction of the
     171             :   // interval graph.  It walks through the source graph, recursively creating
     172             :   // an interval per invocation until the entire graph is covered.  This uses
     173             :   // the ProcessNode method to add all of the nodes to the interval.
     174             :   //
     175             :   // This method is templated because it may operate on two different source
     176             :   // graphs: a basic block graph, or a preexisting interval graph.
     177           0 :   bool ProcessInterval(NodeTy *Node) {
     178           0 :     BasicBlock *Header = getNodeHeader(Node);
     179           0 :     if (!Visited.insert(Header).second)
     180             :       return false;
     181             : 
     182           0 :     Interval *Int = new Interval(Header);
     183             : 
     184             :     // Check all of our successors to see if they are in the interval...
     185           0 :     for (typename GT::ChildIteratorType I = GT::child_begin(Node),
     186           0 :            E = GT::child_end(Node); I != E; ++I)
     187           0 :       ProcessNode(Int, getSourceGraphNode(OrigContainer, *I));
     188             : 
     189           0 :     IntStack.push_back(std::make_pair(Int, succ_begin(Int)));
     190           0 :     return true;
     191             :   }
     192             : 
     193             :   // ProcessNode - This method is called by ProcessInterval to add nodes to the
     194             :   // interval being constructed, and it is also called recursively as it walks
     195             :   // the source graph.  A node is added to the current interval only if all of
     196             :   // its predecessors are already in the graph.  This also takes care of keeping
     197             :   // the successor set of an interval up to date.
     198             :   //
     199             :   // This method is templated because it may operate on two different source
     200             :   // graphs: a basic block graph, or a preexisting interval graph.
     201           0 :   void ProcessNode(Interval *Int, NodeTy *Node) {
     202             :     assert(Int && "Null interval == bad!");
     203             :     assert(Node && "Null Node == bad!");
     204             : 
     205           0 :     BasicBlock *NodeHeader = getNodeHeader(Node);
     206             : 
     207           0 :     if (Visited.count(NodeHeader)) {     // Node already been visited?
     208           0 :       if (Int->contains(NodeHeader)) {   // Already in this interval...
     209           0 :         return;
     210             :       } else {                           // In other interval, add as successor
     211           0 :         if (!Int->isSuccessor(NodeHeader)) // Add only if not already in set
     212           0 :           Int->Successors.push_back(NodeHeader);
     213             :       }
     214             :     } else {                             // Otherwise, not in interval yet
     215           0 :       for (typename IGT::ChildIteratorType I = IGT::child_begin(Node),
     216           0 :              E = IGT::child_end(Node); I != E; ++I) {
     217           0 :         if (!Int->contains(*I)) {        // If pred not in interval, we can't be
     218           0 :           if (!Int->isSuccessor(NodeHeader)) // Add only if not already in set
     219           0 :             Int->Successors.push_back(NodeHeader);
     220           0 :           return;                        // See you later
     221             :         }
     222             :       }
     223             : 
     224             :       // If we get here, then all of the predecessors of BB are in the interval
     225             :       // already.  In this case, we must add BB to the interval!
     226           0 :       addNodeToInterval(Int, Node);
     227           0 :       Visited.insert(NodeHeader);     // The node has now been visited!
     228             : 
     229           0 :       if (Int->isSuccessor(NodeHeader)) {
     230             :         // If we were in the successor list from before... remove from succ list
     231           0 :         Int->Successors.erase(std::remove(Int->Successors.begin(),
     232             :                                           Int->Successors.end(), NodeHeader),
     233           0 :                               Int->Successors.end());
     234             :       }
     235             : 
     236             :       // Now that we have discovered that Node is in the interval, perhaps some
     237             :       // of its successors are as well?
     238           0 :       for (typename GT::ChildIteratorType It = GT::child_begin(Node),
     239           0 :              End = GT::child_end(Node); It != End; ++It)
     240           0 :         ProcessNode(Int, getSourceGraphNode(OrigContainer, *It));
     241             :     }
     242             :   }
     243             : };
     244             : 
     245             : using function_interval_iterator = IntervalIterator<BasicBlock, Function>;
     246             : using interval_part_interval_iterator =
     247             :     IntervalIterator<Interval, IntervalPartition>;
     248             : 
     249             : inline function_interval_iterator intervals_begin(Function *F,
     250             :                                                   bool DeleteInts = true) {
     251           0 :   return function_interval_iterator(F, DeleteInts);
     252             : }
     253             : inline function_interval_iterator intervals_end(Function *) {
     254           0 :   return function_interval_iterator();
     255             : }
     256             : 
     257             : inline interval_part_interval_iterator
     258             :    intervals_begin(IntervalPartition &IP, bool DeleteIntervals = true) {
     259           0 :   return interval_part_interval_iterator(IP, DeleteIntervals);
     260             : }
     261             : 
     262             : inline interval_part_interval_iterator intervals_end(IntervalPartition &IP) {
     263           0 :   return interval_part_interval_iterator();
     264             : }
     265             : 
     266             : } // end namespace llvm
     267             : 
     268             : #endif // LLVM_ANALYSIS_INTERVALITERATOR_H

Generated by: LCOV version 1.13