LCOV - code coverage report
Current view: top level - lib/Analysis - IteratedDominanceFrontier.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 69 75 92.0 %
Date: 2018-10-17 09:37:48 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             : 
      21             : template <class NodeTy, bool IsPostDom>
      22       64240 : void IDFCalculator<NodeTy, IsPostDom>::calculate(
      23             :     SmallVectorImpl<BasicBlock *> &PHIBlocks) {
      24             :   // Use a priority queue keyed on dominator tree level so that inserted nodes
      25             :   // are handled from the bottom of the dominator tree upwards. We also augment
      26             :   // the level with a DFS number to ensure that the blocks are ordered in a
      27             :   // deterministic way.
      28             :   typedef std::pair<DomTreeNode *, std::pair<unsigned, unsigned>>
      29             :       DomTreeNodePair;
      30             :   typedef std::priority_queue<DomTreeNodePair, SmallVector<DomTreeNodePair, 32>,
      31             :                               less_second> IDFPriorityQueue;
      32             :   IDFPriorityQueue PQ;
      33             : 
      34       64240 :   DT.updateDFSNumbers();
      35             : 
      36      456780 :   for (BasicBlock *BB : *DefBlocks) {
      37      783291 :     if (DomTreeNode *Node = DT.getNode(BB))
      38      781502 :       PQ.push({Node, std::make_pair(Node->getLevel(), Node->getDFSNumIn())});
      39             :   }
      40             : 
      41             :   SmallVector<DomTreeNode *, 32> Worklist;
      42             :   SmallPtrSet<DomTreeNode *, 32> VisitedPQ;
      43             :   SmallPtrSet<DomTreeNode *, 32> VisitedWorklist;
      44             : 
      45      503844 :   while (!PQ.empty()) {
      46      439604 :     DomTreeNodePair RootPair = PQ.top();
      47      439604 :     PQ.pop();
      48      439604 :     DomTreeNode *Root = RootPair.first;
      49      439604 :     unsigned RootLevel = RootPair.second.first;
      50             : 
      51             :     // Walk all dominator tree children of Root, inspecting their CFG edges with
      52             :     // targets elsewhere on the dominator tree. Only targets whose level is at
      53             :     // most Root's level are added to the iterated dominance frontier of the
      54             :     // definition set.
      55             : 
      56             :     Worklist.clear();
      57      439604 :     Worklist.push_back(Root);
      58      439604 :     VisitedWorklist.insert(Root);
      59             : 
      60     1061546 :     while (!Worklist.empty()) {
      61      621942 :       DomTreeNode *Node = Worklist.pop_back_val();
      62      621942 :       BasicBlock *BB = Node->getBlock();
      63             :       // Succ is the successor in the direction we are calculating IDF, so it is
      64             :       // successor for IDF, and predecessor for Reverse IDF.
      65      621942 :       auto DoWork = [&](BasicBlock *Succ) {
      66             :         DomTreeNode *SuccNode = DT.getNode(Succ);
      67             : 
      68             :         // Quickly skip all CFG edges that are also dominator tree edges instead
      69             :         // of catching them below.
      70             :         if (SuccNode->getIDom() == Node)
      71             :           return;
      72             : 
      73             :         const unsigned SuccLevel = SuccNode->getLevel();
      74             :         if (SuccLevel > RootLevel)
      75             :           return;
      76             : 
      77             :         if (!VisitedPQ.insert(SuccNode).second)
      78             :           return;
      79             : 
      80             :         BasicBlock *SuccBB = SuccNode->getBlock();
      81             :         if (useLiveIn && !LiveInBlocks->count(SuccBB))
      82             :           return;
      83             : 
      84             :         PHIBlocks.emplace_back(SuccBB);
      85             :         if (!DefBlocks->count(SuccBB))
      86             :           PQ.push(std::make_pair(
      87             :               SuccNode, std::make_pair(SuccLevel, SuccNode->getDFSNumIn())));
      88             :       };
      89             : 
      90      621942 :       if (GD) {
      91           0 :         for (auto Pair : children<
      92             :                  std::pair<const GraphDiff<BasicBlock *, IsPostDom> *, NodeTy>>(
      93             :                  {GD, BB}))
      94           0 :           DoWork(Pair.second);
      95             :       } else {
      96     1913275 :         for (auto *Succ : children<NodeTy>(BB))
      97      765576 :           DoWork(Succ);
      98             :       }
      99             : 
     100     1094882 :       for (auto DomChild : *Node) {
     101      472940 :         if (VisitedWorklist.insert(DomChild).second)
     102      182338 :           Worklist.push_back(DomChild);
     103             :       }
     104             :     }
     105             :   }
     106       64240 : }
     107        7683 : 
     108             : template class IDFCalculator<BasicBlock *, false>;
     109             : template class IDFCalculator<Inverse<BasicBlock *>, true>;
     110             : }

Generated by: LCOV version 1.13