lib/Analysis/PostDominators.cpp

   1 //===- PostDominators.cpp - Post-Dominator Calculation --------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the post-dominator construction algorithms.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/Analysis/PostDominators.h"
  15 #include "llvm/Instructions.h"
  16 #include "llvm/Support/CFG.h"
  17 #include "llvm/ADT/DepthFirstIterator.h"
  18 #include "llvm/ADT/SetOperations.h"
  19 #include "PostDominatorCalculation.h"
  20 using namespace llvm;
  21
  22 //===----------------------------------------------------------------------===//
  23 //  PostDominatorTree Implementation
  24 //===----------------------------------------------------------------------===//
  25
  26 char PostDominatorTree::ID = 0;
  27 char PostDominanceFrontier::ID = 0;
  28 static RegisterPass<PostDominatorTree>
  29 F("postdomtree", "Post-Dominator Tree Construction", true);
  30
  31 unsigned PostDominatorTree::DFSPass(BasicBlock *V, unsigned N) {
  32   std::vector<BasicBlock *> workStack;
  33   SmallPtrSet<BasicBlock *, 32> Visited;
  34   workStack.push_back(V);
  35
  36   do {
  37     BasicBlock *currentBB = workStack.back();
  38     InfoRec &CurVInfo = Info[currentBB];
  39
  40     // Visit each block only once.
  41     if (Visited.insert(currentBB)) {
  42       CurVInfo.Semi = ++N;
  43       CurVInfo.Label = currentBB;
  44
  45       Vertex.push_back(currentBB);  // Vertex[n] = current;
  46       // Info[currentBB].Ancestor = 0;
  47       // Ancestor[n] = 0
  48       // Child[currentBB] = 0;
  49       CurVInfo.Size = 1;       // Size[currentBB] = 1
  50     }
  51
  52     // Visit children
  53     bool visitChild = false;
  54     for (pred_iterator PI = pred_begin(currentBB), PE = pred_end(currentBB);
  55          PI != PE && !visitChild; ++PI) {
  56       InfoRec &SuccVInfo = Info[*PI];
  57       if (SuccVInfo.Semi == 0) {
  58         SuccVInfo.Parent = currentBB;
  59         if (!Visited.count(*PI)) {
  60           workStack.push_back(*PI);
  61           visitChild = true;
  62         }
  63       }
  64     }
  65
  66     // If all children are visited or if this block has no child then pop this
  67     // block out of workStack.
  68     if (!visitChild)
  69       workStack.pop_back();
  70
  71   } while (!workStack.empty());
  72
  73   return N;
  74 }
  75
  76 //===----------------------------------------------------------------------===//
  77 //  PostDominanceFrontier Implementation
  78 //===----------------------------------------------------------------------===//
  79
  80 static RegisterPass<PostDominanceFrontier>
  81 H("postdomfrontier", "Post-Dominance Frontier Construction", true);
  82
  83 const DominanceFrontier::DomSetType &
  84 PostDominanceFrontier::calculate(const PostDominatorTree &DT,
  85                                  const DomTreeNode *Node) {
  86   // Loop over CFG successors to calculate DFlocal[Node]
  87   BasicBlock *BB = Node->getBlock();
  88   DomSetType &S = Frontiers[BB];       // The new set to fill in...
  89   if (getRoots().empty()) return S;
  90
  91   if (BB)
  92     for (pred_iterator SI = pred_begin(BB), SE = pred_end(BB);
  93          SI != SE; ++SI) {
  94       // Does Node immediately dominate this predecessor?
  95       DomTreeNode *SINode = DT[*SI];
  96       if (SINode && SINode->getIDom() != Node)
  97         S.insert(*SI);
  98     }
  99
 100   // At this point, S is DFlocal.  Now we union in DFup's of our children...
 101   // Loop through and visit the nodes that Node immediately dominates (Node's
 102   // children in the IDomTree)
 103   //
 104   for (DomTreeNode::const_iterator
 105          NI = Node->begin(), NE = Node->end(); NI != NE; ++NI) {
 106     DomTreeNode *IDominee = *NI;
 107     const DomSetType &ChildDF = calculate(DT, IDominee);
 108
 109     DomSetType::const_iterator CDFI = ChildDF.begin(), CDFE = ChildDF.end();
 110     for (; CDFI != CDFE; ++CDFI) {
 111       if (!DT.properlyDominates(Node, DT[*CDFI]))
 112         S.insert(*CDFI);
 113     }
 114   }
 115
 116   return S;
 117 }
 118
 119 // Ensure that this .cpp file gets linked when PostDominators.h is used.
 120 DEFINING_FILE_FOR(PostDominanceFrontier)