LCOV - code coverage report
Current view: top level - lib/Analysis - IteratedDominanceFrontier.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 38 38 100.0 %
Date: 2017-09-14 15:23:50 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       47540 : 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       95080 :   IDFPriorityQueue PQ;
      29             : 
      30      331253 :   for (BasicBlock *BB : *DefBlocks) {
      31      567426 :     if (DomTreeNode *Node = DT.getNode(BB))
      32      846987 :       PQ.push({Node, Node->getLevel()});
      33             :   }
      34             : 
      35       95080 :   SmallVector<DomTreeNode *, 32> Worklist;
      36       95080 :   SmallPtrSet<DomTreeNode *, 32> VisitedPQ;
      37       47540 :   SmallPtrSet<DomTreeNode *, 32> VisitedWorklist;
      38             : 
      39      678054 :   while (!PQ.empty()) {
      40      315257 :     DomTreeNodePair RootPair = PQ.top();
      41      315257 :     PQ.pop();
      42      315257 :     DomTreeNode *Root = RootPair.first;
      43      315257 :     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      315257 :     Worklist.clear();
      51      315257 :     Worklist.push_back(Root);
      52      315257 :     VisitedWorklist.insert(Root);
      53             : 
      54     1149571 :     while (!Worklist.empty()) {
      55      417157 :       DomTreeNode *Node = Worklist.pop_back_val();
      56      417157 :       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     1917698 :       for (auto *Succ : children<NodeTy>(BB)) {
      60     1005592 :         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      502796 :         if (SuccNode->getIDom() == Node)
      65      683601 :           continue;
      66             : 
      67      243196 :         const unsigned SuccLevel = SuccNode->getLevel();
      68      243196 :         if (SuccLevel > RootLevel)
      69       53518 :           continue;
      70             : 
      71      189678 :         if (!VisitedPQ.insert(SuccNode).second)
      72       82249 :           continue;
      73             : 
      74      107429 :         BasicBlock *SuccBB = SuccNode->getBlock();
      75      136063 :         if (useLiveIn && !LiveInBlocks->count(SuccBB))
      76       28634 :           continue;
      77             : 
      78       78795 :         PHIBlocks.emplace_back(SuccBB);
      79       78795 :         if (!DefBlocks->count(SuccBB))
      80       98784 :           PQ.push(std::make_pair(SuccNode, SuccLevel));
      81             :       }
      82             : 
      83     1968033 :       for (auto DomChild : *Node) {
      84      299405 :         if (VisitedWorklist.insert(DomChild).second)
      85      101900 :           Worklist.push_back(DomChild);
      86             :       }
      87             :     }
      88             :   }
      89       47540 : }
      90             : 
      91             : template class IDFCalculator<BasicBlock *, false>;
      92             : template class IDFCalculator<Inverse<BasicBlock *>, true>;
      93             : }

Generated by: LCOV version 1.13