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