PostDominators.cpp revision d20cc14dbf6d54d896e67b9920cd9bccdc14c41a 
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 "llvm/Analysis/DominatorInternals.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
31bool PostDominatorTree::runOnFunction(Function &F) {
32  DT->recalculate(F);
33  return false;
34}
35
36//===----------------------------------------------------------------------===//
37//  PostDominanceFrontier Implementation
38//===----------------------------------------------------------------------===//
39
40static RegisterPass<PostDominanceFrontier>
41H("postdomfrontier", "Post-Dominance Frontier Construction", true);
42
43const DominanceFrontier::DomSetType &
44PostDominanceFrontier::calculate(const PostDominatorTree &DT,
45                                 const DomTreeNode *Node) {
46  // Loop over CFG successors to calculate DFlocal[Node]
47  BasicBlock *BB = Node->getBlock();
48  DomSetType &S = Frontiers[BB];       // The new set to fill in...
49  if (getRoots().empty()) return S;
50
51  if (BB)
52    for (pred_iterator SI = pred_begin(BB), SE = pred_end(BB);
53         SI != SE; ++SI) {
54      // Does Node immediately dominate this predecessor?
55      DomTreeNode *SINode = DT[*SI];
56      if (SINode && SINode->getIDom() != Node)
57        S.insert(*SI);
58    }
59
60  // At this point, S is DFlocal.  Now we union in DFup's of our children...
61  // Loop through and visit the nodes that Node immediately dominates (Node's
62  // children in the IDomTree)
63  //
64  for (DomTreeNode::const_iterator
65         NI = Node->begin(), NE = Node->end(); NI != NE; ++NI) {
66    DomTreeNode *IDominee = *NI;
67    const DomSetType &ChildDF = calculate(DT, IDominee);
68
69    DomSetType::const_iterator CDFI = ChildDF.begin(), CDFE = ChildDF.end();
70    for (; CDFI != CDFE; ++CDFI) {
71      if (!DT.properlyDominates(Node, DT[*CDFI]))
72        S.insert(*CDFI);
73    }
74  }
75
76  return S;
77}
78
79// Ensure that this .cpp file gets linked when PostDominators.h is used.
80DEFINING_FILE_FOR(PostDominanceFrontier)
81