1//===- DominanceFrontier.cpp - Dominance Frontier 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#include "llvm/Analysis/DominanceFrontier.h"
11#include "llvm/Support/Debug.h"
12#include "llvm/ADT/SmallPtrSet.h"
13#include "llvm/Assembly/Writer.h"
14#include "llvm/Support/raw_ostream.h"
15using namespace llvm;
16
17char DominanceFrontier::ID = 0;
18INITIALIZE_PASS_BEGIN(DominanceFrontier, "domfrontier",
19                "Dominance Frontier Construction", true, true)
20INITIALIZE_PASS_DEPENDENCY(DominatorTree)
21INITIALIZE_PASS_END(DominanceFrontier, "domfrontier",
22                "Dominance Frontier Construction", true, true)
23
24namespace {
25  class DFCalculateWorkObject {
26  public:
27    DFCalculateWorkObject(BasicBlock *B, BasicBlock *P,
28                          const DomTreeNode *N,
29                          const DomTreeNode *PN)
30    : currentBB(B), parentBB(P), Node(N), parentNode(PN) {}
31    BasicBlock *currentBB;
32    BasicBlock *parentBB;
33    const DomTreeNode *Node;
34    const DomTreeNode *parentNode;
35  };
36}
37
38const DominanceFrontier::DomSetType &
39DominanceFrontier::calculate(const DominatorTree &DT,
40                             const DomTreeNode *Node) {
41  BasicBlock *BB = Node->getBlock();
42  DomSetType *Result = NULL;
43
44  std::vector<DFCalculateWorkObject> workList;
45  SmallPtrSet<BasicBlock *, 32> visited;
46
47  workList.push_back(DFCalculateWorkObject(BB, NULL, Node, NULL));
48  do {
49    DFCalculateWorkObject *currentW = &workList.back();
50    assert (currentW && "Missing work object.");
51
52    BasicBlock *currentBB = currentW->currentBB;
53    BasicBlock *parentBB = currentW->parentBB;
54    const DomTreeNode *currentNode = currentW->Node;
55    const DomTreeNode *parentNode = currentW->parentNode;
56    assert (currentBB && "Invalid work object. Missing current Basic Block");
57    assert (currentNode && "Invalid work object. Missing current Node");
58    DomSetType &S = Frontiers[currentBB];
59
60    // Visit each block only once.
61    if (visited.count(currentBB) == 0) {
62      visited.insert(currentBB);
63
64      // Loop over CFG successors to calculate DFlocal[currentNode]
65      for (succ_iterator SI = succ_begin(currentBB), SE = succ_end(currentBB);
66           SI != SE; ++SI) {
67        // Does Node immediately dominate this successor?
68        if (DT[*SI]->getIDom() != currentNode)
69          S.insert(*SI);
70      }
71    }
72
73    // At this point, S is DFlocal.  Now we union in DFup's of our children...
74    // Loop through and visit the nodes that Node immediately dominates (Node's
75    // children in the IDomTree)
76    bool visitChild = false;
77    for (DomTreeNode::const_iterator NI = currentNode->begin(),
78           NE = currentNode->end(); NI != NE; ++NI) {
79      DomTreeNode *IDominee = *NI;
80      BasicBlock *childBB = IDominee->getBlock();
81      if (visited.count(childBB) == 0) {
82        workList.push_back(DFCalculateWorkObject(childBB, currentBB,
83                                                 IDominee, currentNode));
84        visitChild = true;
85      }
86    }
87
88    // If all children are visited or there is any child then pop this block
89    // from the workList.
90    if (!visitChild) {
91
92      if (!parentBB) {
93        Result = &S;
94        break;
95      }
96
97      DomSetType::const_iterator CDFI = S.begin(), CDFE = S.end();
98      DomSetType &parentSet = Frontiers[parentBB];
99      for (; CDFI != CDFE; ++CDFI) {
100        if (!DT.properlyDominates(parentNode, DT[*CDFI]))
101          parentSet.insert(*CDFI);
102      }
103      workList.pop_back();
104    }
105
106  } while (!workList.empty());
107
108  return *Result;
109}
110
111void DominanceFrontierBase::print(raw_ostream &OS, const Module* ) const {
112  for (const_iterator I = begin(), E = end(); I != E; ++I) {
113    OS << "  DomFrontier for BB ";
114    if (I->first)
115      WriteAsOperand(OS, I->first, false);
116    else
117      OS << " <<exit node>>";
118    OS << " is:\t";
119
120    const std::set<BasicBlock*> &BBs = I->second;
121
122    for (std::set<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end();
123         I != E; ++I) {
124      OS << ' ';
125      if (*I)
126        WriteAsOperand(OS, *I, false);
127      else
128        OS << "<<exit node>>";
129    }
130    OS << "\n";
131  }
132}
133
134void DominanceFrontierBase::dump() const {
135  print(dbgs());
136}
137
138