Home | History | Annotate | Download | only in Analysis 
      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 /// \brief 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>
     21 void IDFCalculator<NodeTy>::calculate(
     22     SmallVectorImpl<BasicBlock *> &PHIBlocks) {
     23   // If we haven't computed dominator tree levels, do so now.
     24   if (DomLevels.empty()) {
     25     for (auto DFI = df_begin(DT.getRootNode()), DFE = df_end(DT.getRootNode());
     26          DFI != DFE; ++DFI) {
     27       DomLevels[*DFI] = DFI.getPathLength() - 1;
     28     }
     29   }
     30 
     31   // Use a priority queue keyed on dominator tree level so that inserted nodes
     32   // are handled from the bottom of the dominator tree upwards.
     33   typedef std::pair<DomTreeNode *, unsigned> DomTreeNodePair;
     34   typedef std::priority_queue<DomTreeNodePair, SmallVector<DomTreeNodePair, 32>,
     35                               less_second> IDFPriorityQueue;
     36   IDFPriorityQueue PQ;
     37 
     38   for (BasicBlock *BB : *DefBlocks) {
     39     if (DomTreeNode *Node = DT.getNode(BB))
     40       PQ.push(std::make_pair(Node, DomLevels.lookup(Node)));
     41   }
     42 
     43   SmallVector<DomTreeNode *, 32> Worklist;
     44   SmallPtrSet<DomTreeNode *, 32> VisitedPQ;
     45   SmallPtrSet<DomTreeNode *, 32> VisitedWorklist;
     46 
     47   while (!PQ.empty()) {
     48     DomTreeNodePair RootPair = PQ.top();
     49     PQ.pop();
     50     DomTreeNode *Root = RootPair.first;
     51     unsigned RootLevel = RootPair.second;
     52 
     53     // Walk all dominator tree children of Root, inspecting their CFG edges with
     54     // targets elsewhere on the dominator tree. Only targets whose level is at
     55     // most Root's level are added to the iterated dominance frontier of the
     56     // definition set.
     57 
     58     Worklist.clear();
     59     Worklist.push_back(Root);
     60     VisitedWorklist.insert(Root);
     61 
     62     while (!Worklist.empty()) {
     63       DomTreeNode *Node = Worklist.pop_back_val();
     64       BasicBlock *BB = Node->getBlock();
     65       // Succ is the successor in the direction we are calculating IDF, so it is
     66       // successor for IDF, and predecessor for Reverse IDF.
     67       for (auto SuccIter = GraphTraits<NodeTy>::child_begin(BB),
     68                 End = GraphTraits<NodeTy>::child_end(BB);
     69            SuccIter != End; ++SuccIter) {
     70         BasicBlock *Succ = *SuccIter;
     71         DomTreeNode *SuccNode = DT.getNode(Succ);
     72 
     73         // Quickly skip all CFG edges that are also dominator tree edges instead
     74         // of catching them below.
     75         if (SuccNode->getIDom() == Node)
     76           continue;
     77 
     78         unsigned SuccLevel = DomLevels.lookup(SuccNode);
     79         if (SuccLevel > RootLevel)
     80           continue;
     81 
     82         if (!VisitedPQ.insert(SuccNode).second)
     83           continue;
     84 
     85         BasicBlock *SuccBB = SuccNode->getBlock();
     86         if (useLiveIn && !LiveInBlocks->count(SuccBB))
     87           continue;
     88 
     89         PHIBlocks.emplace_back(SuccBB);
     90         if (!DefBlocks->count(SuccBB))
     91           PQ.push(std::make_pair(SuccNode, SuccLevel));
     92       }
     93 
     94       for (auto DomChild : *Node) {
     95         if (VisitedWorklist.insert(DomChild).second)
     96           Worklist.push_back(DomChild);
     97       }
     98     }
     99   }
    100 }
    101 
    102 template class IDFCalculator<BasicBlock *>;
    103 template class IDFCalculator<Inverse<BasicBlock *>>;
    104 }
    105