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/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