LCOV - code coverage report
Current view: top level - include/llvm/Analysis - DominanceFrontierImpl.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 51 93 54.8 %
Date: 2017-09-14 15:23:50 Functions: 3 26 11.5 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- llvm/Analysis/DominanceFrontier.h - Dominator Frontiers --*- 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 is the generic implementation of the DominanceFrontier class, which
      11             : // calculate and holds the dominance frontier for a function for.
      12             : //
      13             : // This should be considered deprecated, don't add any more uses of this data
      14             : // structure.
      15             : //
      16             : //===----------------------------------------------------------------------===//
      17             : 
      18             : #ifndef LLVM_ANALYSIS_DOMINANCEFRONTIERIMPL_H
      19             : #define LLVM_ANALYSIS_DOMINANCEFRONTIERIMPL_H
      20             : 
      21             : #include "llvm/ADT/GraphTraits.h"
      22             : #include "llvm/ADT/SmallPtrSet.h"
      23             : #include "llvm/Analysis/DominanceFrontier.h"
      24             : #include "llvm/Support/Debug.h"
      25             : #include "llvm/Support/GenericDomTree.h"
      26             : #include "llvm/Support/raw_ostream.h"
      27             : #include <cassert>
      28             : #include <set>
      29             : #include <utility>
      30             : #include <vector>
      31             : 
      32             : namespace llvm {
      33             : 
      34             : template <class BlockT>
      35             : class DFCalculateWorkObject {
      36             : public:
      37             :   using DomTreeNodeT = DomTreeNodeBase<BlockT>;
      38             : 
      39       43493 :   DFCalculateWorkObject(BlockT *B, BlockT *P, const DomTreeNodeT *N,
      40             :                         const DomTreeNodeT *PN)
      41       43493 :       : currentBB(B), parentBB(P), Node(N), parentNode(PN) {}
      42             : 
      43             :   BlockT *currentBB;
      44             :   BlockT *parentBB;
      45             :   const DomTreeNodeT *Node;
      46             :   const DomTreeNodeT *parentNode;
      47             : };
      48             : 
      49             : template <class BlockT, bool IsPostDom>
      50           0 : void DominanceFrontierBase<BlockT, IsPostDom>::removeBlock(BlockT *BB) {
      51             :   assert(find(BB) != end() && "Block is not in DominanceFrontier!");
      52           0 :   for (iterator I = begin(), E = end(); I != E; ++I)
      53           0 :     I->second.erase(BB);
      54           0 :   Frontiers.erase(BB);
      55           0 : }
      56             : 
      57             : template <class BlockT, bool IsPostDom>
      58           0 : void DominanceFrontierBase<BlockT, IsPostDom>::addToFrontier(iterator I,
      59             :                                                              BlockT *Node) {
      60             :   assert(I != end() && "BB is not in DominanceFrontier!");
      61             :   assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB");
      62           0 :   I->second.erase(Node);
      63           0 : }
      64             : 
      65             : template <class BlockT, bool IsPostDom>
      66           0 : void DominanceFrontierBase<BlockT, IsPostDom>::removeFromFrontier(
      67             :     iterator I, BlockT *Node) {
      68             :   assert(I != end() && "BB is not in DominanceFrontier!");
      69             :   assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB");
      70           0 :   I->second.erase(Node);
      71           0 : }
      72             : 
      73             : template <class BlockT, bool IsPostDom>
      74           0 : bool DominanceFrontierBase<BlockT, IsPostDom>::compareDomSet(
      75             :     DomSetType &DS1, const DomSetType &DS2) const {
      76           0 :   std::set<BlockT *> tmpSet;
      77           0 :   for (BlockT *BB : DS2)
      78           0 :     tmpSet.insert(BB);
      79             : 
      80           0 :   for (typename DomSetType::const_iterator I = DS1.begin(), E = DS1.end();
      81           0 :        I != E;) {
      82           0 :     BlockT *Node = *I++;
      83             : 
      84           0 :     if (tmpSet.erase(Node) == 0)
      85             :       // Node is in DS1 but tnot in DS2.
      86           0 :       return true;
      87             :   }
      88             : 
      89           0 :   if (!tmpSet.empty()) {
      90             :     // There are nodes that are in DS2 but not in DS1.
      91             :     return true;
      92             :   }
      93             : 
      94             :   // DS1 and DS2 matches.
      95           0 :   return false;
      96             : }
      97             : 
      98             : template <class BlockT, bool IsPostDom>
      99           0 : bool DominanceFrontierBase<BlockT, IsPostDom>::compare(
     100             :     DominanceFrontierBase<BlockT, IsPostDom> &Other) const {
     101           0 :   DomSetMapType tmpFrontiers;
     102           0 :   for (typename DomSetMapType::const_iterator I = Other.begin(),
     103           0 :                                               E = Other.end();
     104           0 :        I != E; ++I)
     105           0 :     tmpFrontiers.insert(std::make_pair(I->first, I->second));
     106             : 
     107           0 :   for (typename DomSetMapType::iterator I = tmpFrontiers.begin(),
     108           0 :                                         E = tmpFrontiers.end();
     109           0 :        I != E;) {
     110           0 :     BlockT *Node = I->first;
     111           0 :     const_iterator DFI = find(Node);
     112           0 :     if (DFI == end())
     113           0 :       return true;
     114             : 
     115           0 :     if (compareDomSet(I->second, DFI->second))
     116             :       return true;
     117             : 
     118           0 :     ++I;
     119           0 :     tmpFrontiers.erase(Node);
     120             :   }
     121             : 
     122           0 :   if (!tmpFrontiers.empty())
     123             :     return true;
     124             : 
     125           0 :   return false;
     126             : }
     127             : 
     128             : template <class BlockT, bool IsPostDom>
     129           2 : void DominanceFrontierBase<BlockT, IsPostDom>::print(raw_ostream &OS) const {
     130           4 :   for (const_iterator I = begin(), E = end(); I != E; ++I) {
     131          10 :     OS << "  DomFrontier for BB ";
     132          10 :     if (I->first)
     133          10 :       I->first->printAsOperand(OS, false);
     134             :     else
     135           0 :       OS << " <<exit node>>";
     136          10 :     OS << " is:\t";
     137             : 
     138          10 :     const std::set<BlockT *> &BBs = I->second;
     139             : 
     140          36 :     for (const BlockT *BB : BBs) {
     141           6 :       OS << ' ';
     142           6 :       if (BB)
     143           6 :         BB->printAsOperand(OS, false);
     144             :       else
     145           0 :         OS << "<<exit node>>";
     146             :     }
     147          10 :     OS << '\n';
     148             :   }
     149           2 : }
     150             : 
     151             : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
     152             : template <class BlockT, bool IsPostDom>
     153             : void DominanceFrontierBase<BlockT, IsPostDom>::dump() const {
     154             :   print(dbgs());
     155             : }
     156             : #endif
     157             : 
     158             : template <class BlockT>
     159             : const typename ForwardDominanceFrontierBase<BlockT>::DomSetType &
     160       21208 : ForwardDominanceFrontierBase<BlockT>::calculate(const DomTreeT &DT,
     161             :                                                 const DomTreeNodeT *Node) {
     162       21208 :   BlockT *BB = Node->getBlock();
     163       21208 :   DomSetType *Result = nullptr;
     164             : 
     165       42416 :   std::vector<DFCalculateWorkObject<BlockT>> workList;
     166       42416 :   SmallPtrSet<BlockT *, 32> visited;
     167             : 
     168       42416 :   workList.push_back(DFCalculateWorkObject<BlockT>(BB, nullptr, Node, nullptr));
     169             :   do {
     170       59710 :     DFCalculateWorkObject<BlockT> *currentW = &workList.back();
     171             :     assert(currentW && "Missing work object.");
     172             : 
     173       59710 :     BlockT *currentBB = currentW->currentBB;
     174       59710 :     BlockT *parentBB = currentW->parentBB;
     175       59710 :     const DomTreeNodeT *currentNode = currentW->Node;
     176       59710 :     const DomTreeNodeT *parentNode = currentW->parentNode;
     177             :     assert(currentBB && "Invalid work object. Missing current Basic Block");
     178             :     assert(currentNode && "Invalid work object. Missing current Node");
     179       59710 :     DomSetType &S = this->Frontiers[currentBB];
     180             : 
     181             :     // Visit each block only once.
     182       59710 :     if (visited.insert(currentBB).second) {
     183             :       // Loop over CFG successors to calculate DFlocal[currentNode]
     184      148504 :       for (const auto Succ : children<BlockT *>(currentBB)) {
     185             :         // Does Node immediately dominate this successor?
     186       60848 :         if (DT[Succ]->getIDom() != currentNode)
     187             :           S.insert(Succ);
     188             :       }
     189             :     }
     190             : 
     191             :     // At this point, S is DFlocal.  Now we union in DFup's of our children...
     192             :     // Loop through and visit the nodes that Node immediately dominates (Node's
     193             :     // children in the IDomTree)
     194       59710 :     bool visitChild = false;
     195       59710 :     for (typename DomTreeNodeT::const_iterator NI = currentNode->begin(),
     196       59710 :                                                NE = currentNode->end();
     197      104280 :          NI != NE; ++NI) {
     198       44570 :       DomTreeNodeT *IDominee = *NI;
     199       44570 :       BlockT *childBB = IDominee->getBlock();
     200       44570 :       if (visited.count(childBB) == 0) {
     201       66855 :         workList.push_back(DFCalculateWorkObject<BlockT>(
     202             :             childBB, currentBB, IDominee, currentNode));
     203       22285 :         visitChild = true;
     204             :       }
     205             :     }
     206             : 
     207             :     // If all children are visited or there is any child then pop this block
     208             :     // from the workList.
     209       59710 :     if (!visitChild) {
     210       43493 :       if (!parentBB) {
     211       21208 :         Result = &S;
     212       21208 :         break;
     213             :       }
     214             : 
     215       44570 :       typename DomSetType::const_iterator CDFI = S.begin(), CDFE = S.end();
     216       22285 :       DomSetType &parentSet = this->Frontiers[parentBB];
     217       41398 :       for (; CDFI != CDFE; ++CDFI) {
     218       54157 :         if (!DT.properlyDominates(parentNode, DT[*CDFI]))
     219       10828 :           parentSet.insert(*CDFI);
     220             :       }
     221       22285 :       workList.pop_back();
     222             :     }
     223             : 
     224       38502 :   } while (!workList.empty());
     225             : 
     226       42416 :   return *Result;
     227             : }
     228             : 
     229             : } // end namespace llvm
     230             : 
     231             : #endif // LLVM_ANALYSIS_DOMINANCEFRONTIERIMPL_H

Generated by: LCOV version 1.13