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

Generated by: LCOV version 1.13