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 using namespace llvm;
     20 
     21 void IDFCalculator::calculate(SmallVectorImpl<BasicBlock *> &PHIBlocks) {
     22   // If we haven't computed dominator tree levels, do so now.
     23   if (DomLevels.empty()) {
     24     for (auto DFI = df_begin(DT.getRootNode()), DFE = df_end(DT.getRootNode());
     25          DFI != DFE; ++DFI) {
     26       DomLevels[*DFI] = DFI.getPathLength() - 1;
     27     }
     28   }
     29 
     30   // Use a priority queue keyed on dominator tree level so that inserted nodes
     31   // are handled from the bottom of the dominator tree upwards.
     32   typedef std::pair<DomTreeNode *, unsigned> DomTreeNodePair;
     33   typedef std::priority_queue<DomTreeNodePair, SmallVector<DomTreeNodePair, 32>,
     34                               less_second> IDFPriorityQueue;
     35   IDFPriorityQueue PQ;
     36 
     37   for (BasicBlock *BB : *DefBlocks) {
     38     if (DomTreeNode *Node = DT.getNode(BB))
     39       PQ.push(std::make_pair(Node, DomLevels.lookup(Node)));
     40   }
     41 
     42   SmallVector<DomTreeNode *, 32> Worklist;
     43   SmallPtrSet<DomTreeNode *, 32> VisitedPQ;
     44   SmallPtrSet<DomTreeNode *, 32> VisitedWorklist;
     45 
     46   while (!PQ.empty()) {
     47     DomTreeNodePair RootPair = PQ.top();
     48     PQ.pop();
     49     DomTreeNode *Root = RootPair.first;
     50     unsigned RootLevel = RootPair.second;
     51 
     52     // Walk all dominator tree children of Root, inspecting their CFG edges with
     53     // targets elsewhere on the dominator tree. Only targets whose level is at
     54     // most Root's level are added to the iterated dominance frontier of the
     55     // definition set.
     56 
     57     Worklist.clear();
     58     Worklist.push_back(Root);
     59     VisitedWorklist.insert(Root);
     60 
     61     while (!Worklist.empty()) {
     62       DomTreeNode *Node = Worklist.pop_back_val();
     63       BasicBlock *BB = Node->getBlock();
     64 
     65       for (auto Succ : successors(BB)) {
     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           continue;
     72 
     73         unsigned SuccLevel = DomLevels.lookup(SuccNode);
     74         if (SuccLevel > RootLevel)
     75           continue;
     76 
     77         if (!VisitedPQ.insert(SuccNode).second)
     78           continue;
     79 
     80         BasicBlock *SuccBB = SuccNode->getBlock();
     81         if (useLiveIn && !LiveInBlocks->count(SuccBB))
     82           continue;
     83 
     84         PHIBlocks.emplace_back(SuccBB);
     85         if (!DefBlocks->count(SuccBB))
     86           PQ.push(std::make_pair(SuccNode, SuccLevel));
     87       }
     88 
     89       for (auto DomChild : *Node) {
     90         if (VisitedWorklist.insert(DomChild).second)
     91           Worklist.push_back(DomChild);
     92       }
     93     }
     94   }
     95 }
     96