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