lib/VMCore/Dominators.cpp

   1 //===- Dominators.cpp - Dominator 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 // This file implements simple dominator construction algorithms for finding
  11 // forward dominators.  Postdominators are available in libanalysis, but are not
  12 // included in libvmcore, because it's not needed.  Forward dominators are
  13 // needed to support the Verifier pass.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #include "llvm/Analysis/Dominators.h"
  18 #include "llvm/Support/CFG.h"
  19 #include "llvm/Support/Compiler.h"
  20 #include "llvm/ADT/DepthFirstIterator.h"
  21 #include "llvm/ADT/SetOperations.h"
  22 #include "llvm/ADT/SmallPtrSet.h"
  23 #include "llvm/ADT/SmallVector.h"
  24 #include "llvm/Analysis/DominatorInternals.h"
  25 #include "llvm/Instructions.h"
  26 #include "llvm/Support/raw_ostream.h"
  27 #include <algorithm>
  28 using namespace llvm;
  29
  30 //===----------------------------------------------------------------------===//
  31 //  DominatorTree Implementation
  32 //===----------------------------------------------------------------------===//
  33 //
  34 // Provide public access to DominatorTree information.  Implementation details
  35 // can be found in DominatorCalculation.h.
  36 //
  37 //===----------------------------------------------------------------------===//
  38
  39 TEMPLATE_INSTANTIATION(class DomTreeNodeBase<BasicBlock>);
  40 TEMPLATE_INSTANTIATION(class DominatorTreeBase<BasicBlock>);
  41
  42 char DominatorTree::ID = 0;
  43 static RegisterPass<DominatorTree>
  44 E("domtree", "Dominator Tree Construction", true, true);
  45
  46 bool DominatorTree::runOnFunction(Function &F) {
  47   DT->recalculate(F);
  48   return false;
  49 }
  50
  51 void DominatorTree::print(std::ostream &OS, const Module *) const {
  52   raw_os_ostream OSS(OS);
  53   DT->print(OSS);
  54 }
  55
  56
  57
  58 //===----------------------------------------------------------------------===//
  59 //  DominanceFrontier Implementation
  60 //===----------------------------------------------------------------------===//
  61
  62 char DominanceFrontier::ID = 0;
  63 static RegisterPass<DominanceFrontier>
  64 G("domfrontier", "Dominance Frontier Construction", true, true);
  65
  66 // NewBB is split and now it has one successor. Update dominace frontier to
  67 // reflect this change.
  68 void DominanceFrontier::splitBlock(BasicBlock *NewBB) {
  69   assert(NewBB->getTerminator()->getNumSuccessors() == 1
  70          && "NewBB should have a single successor!");
  71   BasicBlock *NewBBSucc = NewBB->getTerminator()->getSuccessor(0);
  72
  73   SmallVector<BasicBlock*, 8> PredBlocks;
  74   for (pred_iterator PI = pred_begin(NewBB), PE = pred_end(NewBB);
  75        PI != PE; ++PI)
  76       PredBlocks.push_back(*PI);
  77
  78   if (PredBlocks.empty())
  79     // If NewBB does not have any predecessors then it is a entry block.
  80     // In this case, NewBB and its successor NewBBSucc dominates all
  81     // other blocks.
  82     return;
  83
  84   // NewBBSucc inherits original NewBB frontier.
  85   DominanceFrontier::iterator NewBBI = find(NewBB);
  86   if (NewBBI != end()) {
  87     DominanceFrontier::DomSetType NewBBSet = NewBBI->second;
  88     DominanceFrontier::DomSetType NewBBSuccSet;
  89     NewBBSuccSet.insert(NewBBSet.begin(), NewBBSet.end());
  90     addBasicBlock(NewBBSucc, NewBBSuccSet);
  91   }
  92
  93   // If NewBB dominates NewBBSucc, then DF(NewBB) is now going to be the
  94   // DF(PredBlocks[0]) without the stuff that the new block does not dominate
  95   // a predecessor of.
  96   DominatorTree &DT = getAnalysis<DominatorTree>();
  97   if (DT.dominates(NewBB, NewBBSucc)) {
  98     DominanceFrontier::iterator DFI = find(PredBlocks[0]);
  99     if (DFI != end()) {
 100       DominanceFrontier::DomSetType Set = DFI->second;
 101       // Filter out stuff in Set that we do not dominate a predecessor of.
 102       for (DominanceFrontier::DomSetType::iterator SetI = Set.begin(),
 103              E = Set.end(); SetI != E;) {
 104         bool DominatesPred = false;
 105         for (pred_iterator PI = pred_begin(*SetI), E = pred_end(*SetI);
 106              PI != E; ++PI)
 107           if (DT.dominates(NewBB, *PI))
 108             DominatesPred = true;
 109         if (!DominatesPred)
 110           Set.erase(SetI++);
 111         else
 112           ++SetI;
 113       }
 114
 115       if (NewBBI != end()) {
 116         for (DominanceFrontier::DomSetType::iterator SetI = Set.begin(),
 117                E = Set.end(); SetI != E; ++SetI) {
 118           BasicBlock *SB = *SetI;
 119           addToFrontier(NewBBI, SB);
 120         }
 121       } else
 122         addBasicBlock(NewBB, Set);
 123     }
 124
 125   } else {
 126     // DF(NewBB) is {NewBBSucc} because NewBB does not strictly dominate
 127     // NewBBSucc, but it does dominate itself (and there is an edge (NewBB ->
 128     // NewBBSucc)).  NewBBSucc is the single successor of NewBB.
 129     DominanceFrontier::DomSetType NewDFSet;
 130     NewDFSet.insert(NewBBSucc);
 131     addBasicBlock(NewBB, NewDFSet);
 132   }
 133
 134   // Now we must loop over all of the dominance frontiers in the function,
 135   // replacing occurrences of NewBBSucc with NewBB in some cases.  All
 136   // blocks that dominate a block in PredBlocks and contained NewBBSucc in
 137   // their dominance frontier must be updated to contain NewBB instead.
 138   //
 139   for (Function::iterator FI = NewBB->getParent()->begin(),
 140          FE = NewBB->getParent()->end(); FI != FE; ++FI) {
 141     DominanceFrontier::iterator DFI = find(FI);
 142     if (DFI == end()) continue;  // unreachable block.
 143
 144     // Only consider nodes that have NewBBSucc in their dominator frontier.
 145     if (!DFI->second.count(NewBBSucc)) continue;
 146
 147     // Verify whether this block dominates a block in predblocks.  If not, do
 148     // not update it.
 149     bool BlockDominatesAny = false;
 150     for (SmallVectorImpl<BasicBlock*>::const_iterator BI = PredBlocks.begin(),
 151            BE = PredBlocks.end(); BI != BE; ++BI) {
 152       if (DT.dominates(FI, *BI)) {
 153         BlockDominatesAny = true;
 154         break;
 155       }
 156     }
 157
 158     // If NewBBSucc should not stay in our dominator frontier, remove it.
 159     // We remove it unless there is a predecessor of NewBBSucc that we
 160     // dominate, but we don't strictly dominate NewBBSucc.
 161     bool ShouldRemove = true;
 162     if ((BasicBlock*)FI == NewBBSucc || !DT.dominates(FI, NewBBSucc)) {
 163       // Okay, we know that PredDom does not strictly dominate NewBBSucc.
 164       // Check to see if it dominates any predecessors of NewBBSucc.
 165       for (pred_iterator PI = pred_begin(NewBBSucc),
 166            E = pred_end(NewBBSucc); PI != E; ++PI)
 167         if (DT.dominates(FI, *PI)) {
 168           ShouldRemove = false;
 169           break;
 170         }
 171     }
 172
 173     if (ShouldRemove)
 174       removeFromFrontier(DFI, NewBBSucc);
 175     if (BlockDominatesAny && (&*FI == NewBB || !DT.dominates(FI, NewBB)))
 176       addToFrontier(DFI, NewBB);
 177   }
 178 }
 179
 180 namespace {
 181   class DFCalculateWorkObject {
 182   public:
 183     DFCalculateWorkObject(BasicBlock *B, BasicBlock *P,
 184                           const DomTreeNode *N,
 185                           const DomTreeNode *PN)
 186     : currentBB(B), parentBB(P), Node(N), parentNode(PN) {}
 187     BasicBlock *currentBB;
 188     BasicBlock *parentBB;
 189     const DomTreeNode *Node;
 190     const DomTreeNode *parentNode;
 191   };
 192 }
 193
 194 const DominanceFrontier::DomSetType &
 195 DominanceFrontier::calculate(const DominatorTree &DT,
 196                              const DomTreeNode *Node) {
 197   BasicBlock *BB = Node->getBlock();
 198   DomSetType *Result = NULL;
 199
 200   std::vector<DFCalculateWorkObject> workList;
 201   SmallPtrSet<BasicBlock *, 32> visited;
 202
 203   workList.push_back(DFCalculateWorkObject(BB, NULL, Node, NULL));
 204   do {
 205     DFCalculateWorkObject *currentW = &workList.back();
 206     assert (currentW && "Missing work object.");
 207
 208     BasicBlock *currentBB = currentW->currentBB;
 209     BasicBlock *parentBB = currentW->parentBB;
 210     const DomTreeNode *currentNode = currentW->Node;
 211     const DomTreeNode *parentNode = currentW->parentNode;
 212     assert (currentBB && "Invalid work object. Missing current Basic Block");
 213     assert (currentNode && "Invalid work object. Missing current Node");
 214     DomSetType &S = Frontiers[currentBB];
 215
 216     // Visit each block only once.
 217     if (visited.count(currentBB) == 0) {
 218       visited.insert(currentBB);
 219
 220       // Loop over CFG successors to calculate DFlocal[currentNode]
 221       for (succ_iterator SI = succ_begin(currentBB), SE = succ_end(currentBB);
 222            SI != SE; ++SI) {
 223         // Does Node immediately dominate this successor?
 224         if (DT[*SI]->getIDom() != currentNode)
 225           S.insert(*SI);
 226       }
 227     }
 228
 229     // At this point, S is DFlocal.  Now we union in DFup's of our children...
 230     // Loop through and visit the nodes that Node immediately dominates (Node's
 231     // children in the IDomTree)
 232     bool visitChild = false;
 233     for (DomTreeNode::const_iterator NI = currentNode->begin(),
 234            NE = currentNode->end(); NI != NE; ++NI) {
 235       DomTreeNode *IDominee = *NI;
 236       BasicBlock *childBB = IDominee->getBlock();
 237       if (visited.count(childBB) == 0) {
 238         workList.push_back(DFCalculateWorkObject(childBB, currentBB,
 239                                                  IDominee, currentNode));
 240         visitChild = true;
 241       }
 242     }
 243
 244     // If all children are visited or there is any child then pop this block
 245     // from the workList.
 246     if (!visitChild) {
 247
 248       if (!parentBB) {
 249         Result = &S;
 250         break;
 251       }
 252
 253       DomSetType::const_iterator CDFI = S.begin(), CDFE = S.end();
 254       DomSetType &parentSet = Frontiers[parentBB];
 255       for (; CDFI != CDFE; ++CDFI) {
 256         if (!DT.properlyDominates(parentNode, DT[*CDFI]))
 257           parentSet.insert(*CDFI);
 258       }
 259       workList.pop_back();
 260     }
 261
 262   } while (!workList.empty());
 263
 264   return *Result;
 265 }
 266
 267 void DominanceFrontierBase::print(std::ostream &O, const Module* ) const {
 268   raw_os_ostream OS(O);
 269   for (const_iterator I = begin(), E = end(); I != E; ++I) {
 270     OS << "  DomFrontier for BB";
 271     if (I->first)
 272       WriteAsOperand(OS, I->first, false);
 273     else
 274       OS << " <<exit node>>";
 275     OS << " is:\t";
 276
 277     const std::set<BasicBlock*> &BBs = I->second;
 278
 279     for (std::set<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end();
 280          I != E; ++I)
 281       if (*I)
 282         WriteAsOperand(OS, *I, false);
 283       else
 284         OS << " <<exit node>>";
 285     OS << "\n";
 286   }
 287 }
 288