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