PostDominators.cpp revision 04fa56932052f416ea911fe65615ebecbf154f6d 
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"
20using namespace llvm;
21
22//===----------------------------------------------------------------------===//
23//  PostDominatorTree Implementation
24//===----------------------------------------------------------------------===//
25
26char PostDominatorTree::ID = 0;
27char PostDominanceFrontier::ID = 0;
28static RegisterPass<PostDominatorTree>
29F("postdomtree", "Post-Dominator Tree Construction", true);
30
31unsigned 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
80static RegisterPass<PostDominanceFrontier>
81H("postdomfrontier", "Post-Dominance Frontier Construction", true);
82
83const DominanceFrontier::DomSetType &
84PostDominanceFrontier::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.
120DEFINING_FILE_FOR(PostDominanceFrontier)
121