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