LCOV - code coverage report
Current view: top level - lib/Analysis - IteratedDominanceFrontier.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 30 30 100.0 %
Date: 2018-02-23 15:42:53 Functions: 2 2 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- IteratedDominanceFrontier.cpp - Compute IDF ------------------------===//
       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             : // Compute iterated dominance frontiers using a linear time algorithm.
      11             : //
      12             : //===----------------------------------------------------------------------===//
      13             : 
      14             : #include "llvm/Analysis/IteratedDominanceFrontier.h"
      15             : #include "llvm/IR/CFG.h"
      16             : #include "llvm/IR/Dominators.h"
      17             : #include <queue>
      18             : 
      19             : namespace llvm {
      20             : template <class NodeTy, bool IsPostDom>
      21       48375 : void IDFCalculator<NodeTy, IsPostDom>::calculate(
      22             :     SmallVectorImpl<BasicBlock *> &PHIBlocks) {
      23             :   // Use a priority queue keyed on dominator tree level so that inserted nodes
      24             :   // are handled from the bottom of the dominator tree upwards.
      25             :   typedef std::pair<DomTreeNode *, unsigned> DomTreeNodePair;
      26             :   typedef std::priority_queue<DomTreeNodePair, SmallVector<DomTreeNodePair, 32>,
      27             :                               less_second> IDFPriorityQueue;
      28             :   IDFPriorityQueue PQ;
      29             : 
      30       48375 :   for (BasicBlock *BB : *DefBlocks) {
      31      587892 :     if (DomTreeNode *Node = DT.getNode(BB))
      32      586298 :       PQ.push({Node, Node->getLevel()});
      33             :   }
      34             : 
      35             :   SmallVector<DomTreeNode *, 32> Worklist;
      36             :   SmallPtrSet<DomTreeNode *, 32> VisitedPQ;
      37             :   SmallPtrSet<DomTreeNode *, 32> VisitedWorklist;
      38             : 
      39      702667 :   while (!PQ.empty()) {
      40      327146 :     DomTreeNodePair RootPair = PQ.top();
      41             :     PQ.pop();
      42      327146 :     DomTreeNode *Root = RootPair.first;
      43             :     unsigned RootLevel = RootPair.second;
      44             : 
      45             :     // Walk all dominator tree children of Root, inspecting their CFG edges with
      46             :     // targets elsewhere on the dominator tree. Only targets whose level is at
      47             :     // most Root's level are added to the iterated dominance frontier of the
      48             :     // definition set.
      49             : 
      50             :     Worklist.clear();
      51      327146 :     Worklist.push_back(Root);
      52      327146 :     VisitedWorklist.insert(Root);
      53             : 
      54     1204284 :     while (!Worklist.empty()) {
      55             :       DomTreeNode *Node = Worklist.pop_back_val();
      56      438569 :       BasicBlock *BB = Node->getBlock();
      57             :       // Succ is the successor in the direction we are calculating IDF, so it is
      58             :       // successor for IDF, and predecessor for Reverse IDF.
      59      624949 :       for (auto *Succ : children<NodeTy>(BB)) {
      60      529325 :         DomTreeNode *SuccNode = DT.getNode(Succ);
      61             : 
      62             :         // Quickly skip all CFG edges that are also dominator tree edges instead
      63             :         // of catching them below.
      64      529325 :         if (SuccNode->getIDom() == Node)
      65      721577 :           continue;
      66             : 
      67      255531 :         const unsigned SuccLevel = SuccNode->getLevel();
      68      255531 :         if (SuccLevel > RootLevel)
      69       58684 :           continue;
      70             : 
      71      196847 :         if (!VisitedPQ.insert(SuccNode).second)
      72       85502 :           continue;
      73             : 
      74      111345 :         BasicBlock *SuccBB = SuccNode->getBlock();
      75      141148 :         if (useLiveIn && !LiveInBlocks->count(SuccBB))
      76       29803 :           continue;
      77             : 
      78       81542 :         PHIBlocks.emplace_back(SuccBB);
      79       81542 :         if (!DefBlocks->count(SuccBB))
      80       67994 :           PQ.push(std::make_pair(SuccNode, SuccLevel));
      81             :       }
      82             : 
      83      754886 :       for (auto DomChild : *Node) {
      84      316317 :         if (VisitedWorklist.insert(DomChild).second)
      85      111423 :           Worklist.push_back(DomChild);
      86             :       }
      87             :     }
      88             :   }
      89       48375 : }
      90             : 
      91             : template class IDFCalculator<BasicBlock *, false>;
      92             : template class IDFCalculator<Inverse<BasicBlock *>, true>;
      93             : }

Generated by: LCOV version 1.13