LCOV - code coverage report
Current view: top level - lib/Analysis - IteratedDominanceFrontier.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 33 33 100.0 %
Date: 2018-07-13 00:08:38 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       51205 : 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. We also augment
      25             :   // the level with a DFS number to ensure that the blocks are ordered in a
      26             :   // deterministic way.
      27             :   typedef std::pair<DomTreeNode *, std::pair<unsigned, unsigned>>
      28             :       DomTreeNodePair;
      29             :   typedef std::priority_queue<DomTreeNodePair, SmallVector<DomTreeNodePair, 32>,
      30             :                               less_second> IDFPriorityQueue;
      31             :   IDFPriorityQueue PQ;
      32             : 
      33       51205 :   DT.updateDFSNumbers();
      34             : 
      35       51205 :   for (BasicBlock *BB : *DefBlocks) {
      36      609638 :     if (DomTreeNode *Node = DT.getNode(BB))
      37      607988 :       PQ.push({Node, std::make_pair(Node->getLevel(), Node->getDFSNumIn())});
      38             :   }
      39             : 
      40             :   SmallVector<DomTreeNode *, 32> Worklist;
      41             :   SmallPtrSet<DomTreeNode *, 32> VisitedPQ;
      42             :   SmallPtrSet<DomTreeNode *, 32> VisitedWorklist;
      43             : 
      44      729773 :   while (!PQ.empty()) {
      45      339284 :     DomTreeNodePair RootPair = PQ.top();
      46      339284 :     PQ.pop();
      47      339284 :     DomTreeNode *Root = RootPair.first;
      48             :     unsigned RootLevel = RootPair.second.first;
      49             : 
      50             :     // Walk all dominator tree children of Root, inspecting their CFG edges with
      51             :     // targets elsewhere on the dominator tree. Only targets whose level is at
      52             :     // most Root's level are added to the iterated dominance frontier of the
      53             :     // definition set.
      54             : 
      55             :     Worklist.clear();
      56      339284 :     Worklist.push_back(Root);
      57      339284 :     VisitedWorklist.insert(Root);
      58             : 
      59     1245158 :     while (!Worklist.empty()) {
      60             :       DomTreeNode *Node = Worklist.pop_back_val();
      61      452937 :       BasicBlock *BB = Node->getBlock();
      62             :       // Succ is the successor in the direction we are calculating IDF, so it is
      63             :       // successor for IDF, and predecessor for Reverse IDF.
      64      644771 :       for (auto *Succ : children<NodeTy>(BB)) {
      65      544760 :         DomTreeNode *SuccNode = DT.getNode(Succ);
      66             : 
      67             :         // Quickly skip all CFG edges that are also dominator tree edges instead
      68             :         // of catching them below.
      69      544760 :         if (SuccNode->getIDom() == Node)
      70      742595 :           continue;
      71             : 
      72      262270 :         const unsigned SuccLevel = SuccNode->getLevel();
      73      262270 :         if (SuccLevel > RootLevel)
      74       59473 :           continue;
      75             : 
      76      202797 :         if (!VisitedPQ.insert(SuccNode).second)
      77       87870 :           continue;
      78             : 
      79      114927 :         BasicBlock *SuccBB = SuccNode->getBlock();
      80      145199 :         if (useLiveIn && !LiveInBlocks->count(SuccBB))
      81       30272 :           continue;
      82             : 
      83       84655 :         PHIBlocks.emplace_back(SuccBB);
      84       84655 :         if (!DefBlocks->count(SuccBB))
      85       35290 :           PQ.push(std::make_pair(
      86       35290 :               SuccNode, std::make_pair(SuccLevel, SuccNode->getDFSNumIn())));
      87             :       }
      88             : 
      89      778883 :       for (auto DomChild : *Node) {
      90      325946 :         if (VisitedWorklist.insert(DomChild).second)
      91      113653 :           Worklist.push_back(DomChild);
      92             :       }
      93             :     }
      94             :   }
      95       51205 : }
      96             : 
      97             : template class IDFCalculator<BasicBlock *, false>;
      98             : template class IDFCalculator<Inverse<BasicBlock *>, true>;
      99             : }

Generated by: LCOV version 1.13