Home | History | Annotate | Download | only in Analysis 
      1 //===- DominanceFrontier.cpp - Dominance Frontier Calculation -------------===//
      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 #include "llvm/Analysis/DominanceFrontier.h"
     11 #include "llvm/Support/Debug.h"
     12 #include "llvm/ADT/SmallPtrSet.h"
     13 #include "llvm/Assembly/Writer.h"
     14 #include "llvm/Support/raw_ostream.h"
     15 using namespace llvm;
     16 
     17 char DominanceFrontier::ID = 0;
     18 INITIALIZE_PASS_BEGIN(DominanceFrontier, "domfrontier",
     19                 "Dominance Frontier Construction", true, true)
     20 INITIALIZE_PASS_DEPENDENCY(DominatorTree)
     21 INITIALIZE_PASS_END(DominanceFrontier, "domfrontier",
     22                 "Dominance Frontier Construction", true, true)
     23 
     24 namespace {
     25   class DFCalculateWorkObject {
     26   public:
     27     DFCalculateWorkObject(BasicBlock *B, BasicBlock *P,
     28                           const DomTreeNode *N,
     29                           const DomTreeNode *PN)
     30     : currentBB(B), parentBB(P), Node(N), parentNode(PN) {}
     31     BasicBlock *currentBB;
     32     BasicBlock *parentBB;
     33     const DomTreeNode *Node;
     34     const DomTreeNode *parentNode;
     35   };
     36 }
     37 
     38 const DominanceFrontier::DomSetType &
     39 DominanceFrontier::calculate(const DominatorTree &DT,
     40                              const DomTreeNode *Node) {
     41   BasicBlock *BB = Node->getBlock();
     42   DomSetType *Result = NULL;
     43 
     44   std::vector<DFCalculateWorkObject> workList;
     45   SmallPtrSet<BasicBlock *, 32> visited;
     46 
     47   workList.push_back(DFCalculateWorkObject(BB, NULL, Node, NULL));
     48   do {
     49     DFCalculateWorkObject *currentW = &workList.back();
     50     assert (currentW && "Missing work object.");
     51 
     52     BasicBlock *currentBB = currentW->currentBB;
     53     BasicBlock *parentBB = currentW->parentBB;
     54     const DomTreeNode *currentNode = currentW->Node;
     55     const DomTreeNode *parentNode = currentW->parentNode;
     56     assert (currentBB && "Invalid work object. Missing current Basic Block");
     57     assert (currentNode && "Invalid work object. Missing current Node");
     58     DomSetType &S = Frontiers[currentBB];
     59 
     60     // Visit each block only once.
     61     if (visited.count(currentBB) == 0) {
     62       visited.insert(currentBB);
     63 
     64       // Loop over CFG successors to calculate DFlocal[currentNode]
     65       for (succ_iterator SI = succ_begin(currentBB), SE = succ_end(currentBB);
     66            SI != SE; ++SI) {
     67         // Does Node immediately dominate this successor?
     68         if (DT[*SI]->getIDom() != currentNode)
     69           S.insert(*SI);
     70       }
     71     }
     72 
     73     // At this point, S is DFlocal.  Now we union in DFup's of our children...
     74     // Loop through and visit the nodes that Node immediately dominates (Node's
     75     // children in the IDomTree)
     76     bool visitChild = false;
     77     for (DomTreeNode::const_iterator NI = currentNode->begin(),
     78            NE = currentNode->end(); NI != NE; ++NI) {
     79       DomTreeNode *IDominee = *NI;
     80       BasicBlock *childBB = IDominee->getBlock();
     81       if (visited.count(childBB) == 0) {
     82         workList.push_back(DFCalculateWorkObject(childBB, currentBB,
     83                                                  IDominee, currentNode));
     84         visitChild = true;
     85       }
     86     }
     87 
     88     // If all children are visited or there is any child then pop this block
     89     // from the workList.
     90     if (!visitChild) {
     91 
     92       if (!parentBB) {
     93         Result = &S;
     94         break;
     95       }
     96 
     97       DomSetType::const_iterator CDFI = S.begin(), CDFE = S.end();
     98       DomSetType &parentSet = Frontiers[parentBB];
     99       for (; CDFI != CDFE; ++CDFI) {
    100         if (!DT.properlyDominates(parentNode, DT[*CDFI]))
    101           parentSet.insert(*CDFI);
    102       }
    103       workList.pop_back();
    104     }
    105 
    106   } while (!workList.empty());
    107 
    108   return *Result;
    109 }
    110 
    111 void DominanceFrontierBase::print(raw_ostream &OS, const Module* ) const {
    112   for (const_iterator I = begin(), E = end(); I != E; ++I) {
    113     OS << "  DomFrontier for BB ";
    114     if (I->first)
    115       WriteAsOperand(OS, I->first, false);
    116     else
    117       OS << " <<exit node>>";
    118     OS << " is:\t";
    119 
    120     const std::set<BasicBlock*> &BBs = I->second;
    121 
    122     for (std::set<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end();
    123          I != E; ++I) {
    124       OS << ' ';
    125       if (*I)
    126         WriteAsOperand(OS, *I, false);
    127       else
    128         OS << "<<exit node>>";
    129     }
    130     OS << "\n";
    131   }
    132 }
    133 
    134 void DominanceFrontierBase::dump() const {
    135   print(dbgs());
    136 }
    137 
    138