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       64250 : 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       64250 :   DT.updateDFSNumbers();
      35             : 
      36      456821 :   for (BasicBlock *BB : *DefBlocks) {
      37      783353 :     if (DomTreeNode *Node = DT.getNode(BB))
      38      781564 :       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      503885 :   while (!PQ.empty()) {
      46      439635 :     DomTreeNodePair RootPair = PQ.top();
      47      439635 :     PQ.pop();
      48      439635 :     DomTreeNode *Root = RootPair.first;
      49      439635 :     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      439635 :     Worklist.push_back(Root);
      58      439635 :     VisitedWorklist.insert(Root);
      59             : 
      60     1061610 :     while (!Worklist.empty()) {
      61      621975 :       DomTreeNode *Node = Worklist.pop_back_val();
      62      621975 :       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      621975 :       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      621975 :       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     1913359 :         for (auto *Succ : children<NodeTy>(BB))
      97      765608 :           DoWork(Succ);
      98             :       }
      99             : 
     100     1094935 :       for (auto DomChild : *Node) {
     101      472960 :         if (VisitedWorklist.insert(DomChild).second)
     102      182340 :           Worklist.push_back(DomChild);
     103             :       }
     104             :     }
     105             :   }
     106       64250 : }
     107        7685 : 
     108             : template class IDFCalculator<BasicBlock *, false>;
     109             : template class IDFCalculator<Inverse<BasicBlock *>, true>;
     110             : }