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