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