lib/Analysis/DominanceFrontier.cpp

   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(DominatorTree)
  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 = NULL;
  44
  45   std::vector<DFCalculateWorkObject> workList;
  46   SmallPtrSet<BasicBlock *, 32> visited;
  47
  48   workList.push_back(DFCalculateWorkObject(BB, NULL, Node, NULL));
  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