Dominators.h revision efd4a5144b03f61ebfd53d0245176f95e1170fb8 
1//===- llvm/Analysis/Dominators.h - Dominator Info Calculation --*- C++ -*-===//
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 defines the following classes:
11//  1. DominatorTree: Represent dominators as an explicit tree structure.
12//  2. DominanceFrontier: Calculate and hold the dominance frontier for a
13//     function.
14//
15//  These data structures are listed in increasing order of complexity.  It
16//  takes longer to calculate the dominator frontier, for example, than the
17//  DominatorTree mapping.
18//
19//===----------------------------------------------------------------------===//
20
21#ifndef LLVM_ANALYSIS_DOMINATORS_H
22#define LLVM_ANALYSIS_DOMINATORS_H
23
24#include "llvm/Pass.h"
25#include "llvm/Instruction.h"
26#include "llvm/Instructions.h"
27#include "llvm/ADT/DenseMap.h"
28#include "llvm/ADT/SmallPtrSet.h"
29#include "llvm/ADT/SmallVector.h"
30#include "llvm/Assembly/Writer.h"
31#include "llvm/Support/Compiler.h"
32#include <algorithm>
33#include <set>
34
35namespace llvm {
36
37template <typename GraphType> struct GraphTraits;
38
39//===----------------------------------------------------------------------===//
40/// DominatorBase - Base class that other, more interesting dominator analyses
41/// inherit from.
42///
43template <class NodeT>
44class DominatorBase : public FunctionPass {
45protected:
46  std::vector<NodeT*> Roots;
47  const bool IsPostDominators;
48  inline DominatorBase(intptr_t ID, bool isPostDom) :
49    FunctionPass(ID), Roots(), IsPostDominators(isPostDom) {}
50public:
51
52  /// getRoots -  Return the root blocks of the current CFG.  This may include
53  /// multiple blocks if we are computing post dominators.  For forward
54  /// dominators, this will always be a single block (the entry node).
55  ///
56  inline const std::vector<NodeT*> &getRoots() const { return Roots; }
57
58  /// isPostDominator - Returns true if analysis based of postdoms
59  ///
60  bool isPostDominator() const { return IsPostDominators; }
61};
62
63
64//===----------------------------------------------------------------------===//
65// DomTreeNode - Dominator Tree Node
66template<class NodeT> class DominatorTreeBase;
67struct PostDominatorTree;
68class MachineBasicBlock;
69
70template <class NodeT>
71class DomTreeNodeBase {
72  NodeT *TheBB;
73  DomTreeNodeBase<NodeT> *IDom;
74  std::vector<DomTreeNodeBase<NodeT> *> Children;
75  int DFSNumIn, DFSNumOut;
76
77  template<class N> friend class DominatorTreeBase;
78  friend struct PostDominatorTree;
79public:
80  typedef typename std::vector<DomTreeNodeBase<NodeT> *>::iterator iterator;
81  typedef typename std::vector<DomTreeNodeBase<NodeT> *>::const_iterator
82                   const_iterator;
83
84  iterator begin()             { return Children.begin(); }
85  iterator end()               { return Children.end(); }
86  const_iterator begin() const { return Children.begin(); }
87  const_iterator end()   const { return Children.end(); }
88
89  NodeT *getBlock() const { return TheBB; }
90  DomTreeNodeBase<NodeT> *getIDom() const { return IDom; }
91  const std::vector<DomTreeNodeBase<NodeT>*> &getChildren() const {
92    return Children;
93  }
94
95  DomTreeNodeBase(NodeT *BB, DomTreeNodeBase<NodeT> *iDom)
96    : TheBB(BB), IDom(iDom), DFSNumIn(-1), DFSNumOut(-1) { }
97
98  DomTreeNodeBase<NodeT> *addChild(DomTreeNodeBase<NodeT> *C) {
99    Children.push_back(C);
100    return C;
101  }
102
103  void setIDom(DomTreeNodeBase<NodeT> *NewIDom) {
104    assert(IDom && "No immediate dominator?");
105    if (IDom != NewIDom) {
106      std::vector<DomTreeNodeBase<BasicBlock>*>::iterator I =
107                  std::find(IDom->Children.begin(), IDom->Children.end(), this);
108      assert(I != IDom->Children.end() &&
109             "Not in immediate dominator children set!");
110      // I am no longer your child...
111      IDom->Children.erase(I);
112
113      // Switch to new dominator
114      IDom = NewIDom;
115      IDom->Children.push_back(this);
116    }
117  }
118
119  /// getDFSNumIn/getDFSNumOut - These are an internal implementation detail, do
120  /// not call them.
121  unsigned getDFSNumIn() const { return DFSNumIn; }
122  unsigned getDFSNumOut() const { return DFSNumOut; }
123private:
124  // Return true if this node is dominated by other. Use this only if DFS info
125  // is valid.
126  bool DominatedBy(const DomTreeNodeBase<NodeT> *other) const {
127    return this->DFSNumIn >= other->DFSNumIn &&
128      this->DFSNumOut <= other->DFSNumOut;
129  }
130};
131
132EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase<BasicBlock>);
133
134template<class NodeT>
135static std::ostream &operator<<(std::ostream &o,
136                                const DomTreeNodeBase<NodeT> *Node) {
137  if (Node->getBlock())
138    WriteAsOperand(o, Node->getBlock(), false);
139  else
140    o << " <<exit node>>";
141
142  o << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "}";
143
144  return o << "\n";
145}
146
147template<class NodeT>
148static void PrintDomTree(const DomTreeNodeBase<NodeT> *N, std::ostream &o,
149                         unsigned Lev) {
150  o << std::string(2*Lev, ' ') << "[" << Lev << "] " << N;
151  for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(),
152       E = N->end(); I != E; ++I)
153    PrintDomTree<NodeT>(*I, o, Lev+1);
154}
155
156typedef DomTreeNodeBase<BasicBlock> DomTreeNode;
157typedef DomTreeNodeBase<MachineBasicBlock> MachineDomTreeNode;
158
159//===----------------------------------------------------------------------===//
160/// DominatorTree - Calculate the immediate dominator tree for a function.
161///
162
163template<class N, class GraphT>
164void Split(DominatorTreeBase<typename GraphT::NodeType>& DT,
165           typename GraphT::NodeType* NewBB);
166
167template<class NodeT>
168class DominatorTreeBase : public DominatorBase<NodeT> {
169protected:
170  typedef DenseMap<NodeT*, DomTreeNodeBase<NodeT>*> DomTreeNodeMapType;
171  DomTreeNodeMapType DomTreeNodes;
172  DomTreeNodeBase<NodeT> *RootNode;
173
174  bool DFSInfoValid;
175  unsigned int SlowQueries;
176  // Information record used during immediate dominators computation.
177  struct InfoRec {
178    unsigned Semi;
179    unsigned Size;
180    NodeT *Label, *Parent, *Child, *Ancestor;
181
182    std::vector<NodeT*> Bucket;
183
184    InfoRec() : Semi(0), Size(0), Label(0), Parent(0), Child(0), Ancestor(0) {}
185  };
186
187  DenseMap<NodeT*, NodeT*> IDoms;
188
189  // Vertex - Map the DFS number to the BasicBlock*
190  std::vector<NodeT*> Vertex;
191
192  // Info - Collection of information used during the computation of idoms.
193  DenseMap<NodeT*, InfoRec> Info;
194
195  void reset() {
196    for (typename DomTreeNodeMapType::iterator I = this->DomTreeNodes.begin(),
197           E = DomTreeNodes.end(); I != E; ++I)
198      delete I->second;
199    DomTreeNodes.clear();
200    IDoms.clear();
201    this->Roots.clear();
202    Vertex.clear();
203    RootNode = 0;
204  }
205
206public:
207  DominatorTreeBase(intptr_t ID, bool isPostDom)
208    : DominatorBase<NodeT>(ID, isPostDom), DFSInfoValid(false), SlowQueries(0) {}
209  ~DominatorTreeBase() { reset(); }
210
211  virtual void releaseMemory() { reset(); }
212
213  /// getNode - return the (Post)DominatorTree node for the specified basic
214  /// block.  This is the same as using operator[] on this class.
215  ///
216  inline DomTreeNodeBase<NodeT> *getNode(NodeT *BB) const {
217    typename DomTreeNodeMapType::const_iterator I = DomTreeNodes.find(BB);
218    return I != DomTreeNodes.end() ? I->second : 0;
219  }
220
221  inline DomTreeNodeBase<NodeT> *operator[](NodeT *BB) const {
222    return getNode(BB);
223  }
224
225  /// getRootNode - This returns the entry node for the CFG of the function.  If
226  /// this tree represents the post-dominance relations for a function, however,
227  /// this root may be a node with the block == NULL.  This is the case when
228  /// there are multiple exit nodes from a particular function.  Consumers of
229  /// post-dominance information must be capable of dealing with this
230  /// possibility.
231  ///
232  DomTreeNodeBase<NodeT> *getRootNode() { return RootNode; }
233  const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; }
234
235  /// properlyDominates - Returns true iff this dominates N and this != N.
236  /// Note that this is not a constant time operation!
237  ///
238  bool properlyDominates(const DomTreeNodeBase<NodeT> *A,
239                         DomTreeNodeBase<NodeT> *B) const {
240    if (A == 0 || B == 0) return false;
241    return dominatedBySlowTreeWalk(A, B);
242  }
243
244  inline bool properlyDominates(NodeT *A, NodeT *B) {
245    return properlyDominates(getNode(A), getNode(B));
246  }
247
248  bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A,
249                               const DomTreeNodeBase<NodeT> *B) const {
250    const DomTreeNodeBase<NodeT> *IDom;
251    if (A == 0 || B == 0) return false;
252    while ((IDom = B->getIDom()) != 0 && IDom != A && IDom != B)
253      B = IDom;   // Walk up the tree
254    return IDom != 0;
255  }
256
257
258  /// isReachableFromEntry - Return true if A is dominated by the entry
259  /// block of the function containing it.
260  const bool isReachableFromEntry(NodeT* A) {
261    assert (!this->isPostDominator()
262            && "This is not implemented for post dominators");
263    return dominates(&A->getParent()->getEntryBlock(), A);
264  }
265
266  /// dominates - Returns true iff A dominates B.  Note that this is not a
267  /// constant time operation!
268  ///
269  inline bool dominates(const DomTreeNodeBase<NodeT> *A,
270                        DomTreeNodeBase<NodeT> *B) {
271    if (B == A)
272      return true;  // A node trivially dominates itself.
273
274    if (A == 0 || B == 0)
275      return false;
276
277    if (DFSInfoValid)
278      return B->DominatedBy(A);
279
280    // If we end up with too many slow queries, just update the
281    // DFS numbers on the theory that we are going to keep querying.
282    SlowQueries++;
283    if (SlowQueries > 32) {
284      updateDFSNumbers();
285      return B->DominatedBy(A);
286    }
287
288    return dominatedBySlowTreeWalk(A, B);
289  }
290
291  inline bool dominates(NodeT *A, NodeT *B) {
292    if (A == B)
293      return true;
294
295    return dominates(getNode(A), getNode(B));
296  }
297
298  /// findNearestCommonDominator - Find nearest common dominator basic block
299  /// for basic block A and B. If there is no such block then return NULL.
300  NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) {
301
302    assert (!this->isPostDominator()
303            && "This is not implemented for post dominators");
304    assert (A->getParent() == B->getParent()
305            && "Two blocks are not in same function");
306
307    // If either A or B is a entry block then it is nearest common dominator.
308    NodeT &Entry  = A->getParent()->getEntryBlock();
309    if (A == &Entry || B == &Entry)
310      return &Entry;
311
312    // If B dominates A then B is nearest common dominator.
313    if (dominates(B, A))
314      return B;
315
316    // If A dominates B then A is nearest common dominator.
317    if (dominates(A, B))
318      return A;
319
320    DomTreeNodeBase<NodeT> *NodeA = getNode(A);
321    DomTreeNodeBase<NodeT> *NodeB = getNode(B);
322
323    // Collect NodeA dominators set.
324    SmallPtrSet<DomTreeNodeBase<NodeT>*, 16> NodeADoms;
325    NodeADoms.insert(NodeA);
326    DomTreeNodeBase<NodeT> *IDomA = NodeA->getIDom();
327    while (IDomA) {
328      NodeADoms.insert(IDomA);
329      IDomA = IDomA->getIDom();
330    }
331
332    // Walk NodeB immediate dominators chain and find common dominator node.
333    DomTreeNodeBase<NodeT> *IDomB = NodeB->getIDom();
334    while(IDomB) {
335      if (NodeADoms.count(IDomB) != 0)
336        return IDomB->getBlock();
337
338      IDomB = IDomB->getIDom();
339    }
340
341    return NULL;
342  }
343
344  // dominates - Return true if A dominates B. This performs the
345  // special checks necessary if A and B are in the same basic block.
346  bool dominates(Instruction *A, Instruction *B) {
347    NodeT *BBA = A->getParent(), *BBB = B->getParent();
348    if (BBA != BBB) return this->dominates(BBA, BBB);
349
350    // It is not possible to determine dominance between two PHI nodes
351    // based on their ordering.
352    if (isa<PHINode>(A) && isa<PHINode>(B))
353      return false;
354
355    // Loop through the basic block until we find A or B.
356    typename NodeT::iterator I = BBA->begin();
357    for (; &*I != A && &*I != B; ++I) /*empty*/;
358
359    if(!this->IsPostDominators) {
360      // A dominates B if it is found first in the basic block.
361      return &*I == A;
362    } else {
363      // A post-dominates B if B is found first in the basic block.
364      return &*I == B;
365    }
366  }
367
368  //===--------------------------------------------------------------------===//
369  // API to update (Post)DominatorTree information based on modifications to
370  // the CFG...
371
372  /// addNewBlock - Add a new node to the dominator tree information.  This
373  /// creates a new node as a child of DomBB dominator node,linking it into
374  /// the children list of the immediate dominator.
375  DomTreeNodeBase<NodeT> *addNewBlock(NodeT *BB, NodeT *DomBB) {
376    assert(getNode(BB) == 0 && "Block already in dominator tree!");
377    DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB);
378    assert(IDomNode && "Not immediate dominator specified for block!");
379    DFSInfoValid = false;
380    return DomTreeNodes[BB] =
381      IDomNode->addChild(new DomTreeNode(BB, IDomNode));
382  }
383
384  /// changeImmediateDominator - This method is used to update the dominator
385  /// tree information when a node's immediate dominator changes.
386  ///
387  void changeImmediateDominator(DomTreeNodeBase<NodeT> *N,
388                                DomTreeNodeBase<NodeT> *NewIDom) {
389    assert(N && NewIDom && "Cannot change null node pointers!");
390    DFSInfoValid = false;
391    N->setIDom(NewIDom);
392  }
393
394  void changeImmediateDominator(NodeT *BB, NodeT *NewBB) {
395    changeImmediateDominator(getNode(BB), getNode(NewBB));
396  }
397
398  /// eraseNode - Removes a node from  the dominator tree. Block must not
399  /// domiante any other blocks. Removes node from its immediate dominator's
400  /// children list. Deletes dominator node associated with basic block BB.
401  void eraseNode(NodeT *BB) {
402    DomTreeNodeBase<NodeT> *Node = getNode(BB);
403    assert (Node && "Removing node that isn't in dominator tree.");
404    assert (Node->getChildren().empty() && "Node is not a leaf node.");
405
406      // Remove node from immediate dominator's children list.
407    DomTreeNodeBase<NodeT> *IDom = Node->getIDom();
408    if (IDom) {
409      typename std::vector<DomTreeNodeBase<NodeT>*>::iterator I =
410        std::find(IDom->Children.begin(), IDom->Children.end(), Node);
411      assert(I != IDom->Children.end() &&
412             "Not in immediate dominator children set!");
413      // I am no longer your child...
414      IDom->Children.erase(I);
415    }
416
417    DomTreeNodes.erase(BB);
418    delete Node;
419  }
420
421  /// removeNode - Removes a node from the dominator tree.  Block must not
422  /// dominate any other blocks.  Invalidates any node pointing to removed
423  /// block.
424  void removeNode(NodeT *BB) {
425    assert(getNode(BB) && "Removing node that isn't in dominator tree.");
426    DomTreeNodes.erase(BB);
427  }
428
429  /// print - Convert to human readable form
430  ///
431  virtual void print(std::ostream &o, const Module* ) const {
432    o << "=============================--------------------------------\n";
433    o << "Inorder Dominator Tree: ";
434    if (this->DFSInfoValid)
435      o << "DFSNumbers invalid: " << SlowQueries << " slow queries.";
436    o << "\n";
437
438    PrintDomTree<NodeT>(getRootNode(), o, 1);
439  }
440
441  void print(std::ostream *OS, const Module* M = 0) const {
442    if (OS) print(*OS, M);
443  }
444
445  virtual void dump() {
446    print(llvm::cerr);
447  }
448
449protected:
450  template<class GraphT>
451  friend void Compress(DominatorTreeBase<typename GraphT::NodeType>& DT,
452                       typename GraphT::NodeType* VIn);
453
454  template<class GraphT>
455  friend typename GraphT::NodeType* Eval(
456                               DominatorTreeBase<typename GraphT::NodeType>& DT,
457                                         typename GraphT::NodeType* V);
458
459  template<class GraphT>
460  friend void Link(DominatorTreeBase<typename GraphT::NodeType>& DT,
461                   typename GraphT::NodeType* V,
462                   typename GraphT::NodeType* W,
463         typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &WInfo);
464
465  template<class GraphT>
466  friend unsigned DFSPass(DominatorTreeBase<typename GraphT::NodeType>& DT,
467                          typename GraphT::NodeType* V,
468                          unsigned N);
469
470  template<class N, class GraphT>
471  friend void Calculate(DominatorTreeBase<typename GraphT::NodeType>& DT,
472                        Function& F);
473
474  template<class N, class GraphT>
475  friend void Split(DominatorTreeBase<typename GraphT::NodeType>& DT,
476                    typename GraphT::NodeType* NewBB);
477
478public:
479  /// splitBlock - BB is split and now it has one successor. Update dominator
480  /// tree to reflect this change.
481  void splitBlock(NodeT* NewBB) {
482    if (this->IsPostDominators)
483      Split<Inverse<NodeT*>, GraphTraits<Inverse<NodeT*> > >(*this, NewBB);
484    else
485      Split<NodeT*, GraphTraits<NodeT*> >(*this, NewBB);
486  }
487
488protected:
489  /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking
490  /// dominator tree in dfs order.
491  void updateDFSNumbers() {
492    unsigned DFSNum = 0;
493
494    SmallVector<std::pair<DomTreeNodeBase<NodeT>*,
495                typename DomTreeNodeBase<NodeT>::iterator>, 32> WorkStack;
496
497    for (unsigned i = 0, e = this->Roots.size(); i != e; ++i) {
498      DomTreeNodeBase<NodeT> *ThisRoot = getNode(this->Roots[i]);
499      WorkStack.push_back(std::make_pair(ThisRoot, ThisRoot->begin()));
500      ThisRoot->DFSNumIn = DFSNum++;
501
502      while (!WorkStack.empty()) {
503        DomTreeNodeBase<NodeT> *Node = WorkStack.back().first;
504        typename DomTreeNodeBase<NodeT>::iterator ChildIt =
505                                                        WorkStack.back().second;
506
507        // If we visited all of the children of this node, "recurse" back up the
508        // stack setting the DFOutNum.
509        if (ChildIt == Node->end()) {
510          Node->DFSNumOut = DFSNum++;
511          WorkStack.pop_back();
512        } else {
513          // Otherwise, recursively visit this child.
514          DomTreeNodeBase<NodeT> *Child = *ChildIt;
515          ++WorkStack.back().second;
516
517          WorkStack.push_back(std::make_pair(Child, Child->begin()));
518          Child->DFSNumIn = DFSNum++;
519        }
520      }
521    }
522
523    SlowQueries = 0;
524    DFSInfoValid = true;
525  }
526
527  DomTreeNodeBase<NodeT> *getNodeForBlock(NodeT *BB) {
528    if (DomTreeNodeBase<NodeT> *BBNode = this->DomTreeNodes[BB])
529      return BBNode;
530
531    // Haven't calculated this node yet?  Get or calculate the node for the
532    // immediate dominator.
533    NodeT *IDom = getIDom(BB);
534    DomTreeNodeBase<NodeT> *IDomNode = getNodeForBlock(IDom);
535
536    // Add a new tree node for this BasicBlock, and link it as a child of
537    // IDomNode
538    DomTreeNodeBase<NodeT> *C = new DomTreeNodeBase<NodeT>(BB, IDomNode);
539    return this->DomTreeNodes[BB] = IDomNode->addChild(C);
540  }
541
542  inline NodeT *getIDom(NodeT *BB) const {
543    typename DenseMap<NodeT*, NodeT*>::const_iterator I = IDoms.find(BB);
544    return I != IDoms.end() ? I->second : 0;
545  }
546};
547
548EXTERN_TEMPLATE_INSTANTIATION(class DominatorTreeBase<BasicBlock>);
549
550//===-------------------------------------
551/// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
552/// compute a normal dominator tree.
553///
554class DominatorTree : public DominatorTreeBase<BasicBlock> {
555public:
556  static char ID; // Pass ID, replacement for typeid
557  DominatorTree() : DominatorTreeBase<BasicBlock>(intptr_t(&ID), false) {}
558
559  BasicBlock *getRoot() const {
560    assert(Roots.size() == 1 && "Should always have entry node!");
561    return Roots[0];
562  }
563
564  virtual bool runOnFunction(Function &F);
565
566  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
567    AU.setPreservesAll();
568  }
569};
570
571//===-------------------------------------
572/// DominatorTree GraphTraits specialization so the DominatorTree can be
573/// iterable by generic graph iterators.
574///
575template <> struct GraphTraits<DomTreeNode *> {
576  typedef DomTreeNode NodeType;
577  typedef NodeType::iterator  ChildIteratorType;
578
579  static NodeType *getEntryNode(NodeType *N) {
580    return N;
581  }
582  static inline ChildIteratorType child_begin(NodeType* N) {
583    return N->begin();
584  }
585  static inline ChildIteratorType child_end(NodeType* N) {
586    return N->end();
587  }
588};
589
590template <> struct GraphTraits<DominatorTree*>
591  : public GraphTraits<DomTreeNode *> {
592  static NodeType *getEntryNode(DominatorTree *DT) {
593    return DT->getRootNode();
594  }
595};
596
597
598//===----------------------------------------------------------------------===//
599/// DominanceFrontierBase - Common base class for computing forward and inverse
600/// dominance frontiers for a function.
601///
602class DominanceFrontierBase : public DominatorBase<BasicBlock> {
603public:
604  typedef std::set<BasicBlock*>             DomSetType;    // Dom set for a bb
605  typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map
606protected:
607  DomSetMapType Frontiers;
608public:
609  DominanceFrontierBase(intptr_t ID, bool isPostDom)
610    : DominatorBase<BasicBlock>(ID, isPostDom) {}
611
612  virtual void releaseMemory() { Frontiers.clear(); }
613
614  // Accessor interface:
615  typedef DomSetMapType::iterator iterator;
616  typedef DomSetMapType::const_iterator const_iterator;
617  iterator       begin()       { return Frontiers.begin(); }
618  const_iterator begin() const { return Frontiers.begin(); }
619  iterator       end()         { return Frontiers.end(); }
620  const_iterator end()   const { return Frontiers.end(); }
621  iterator       find(BasicBlock *B)       { return Frontiers.find(B); }
622  const_iterator find(BasicBlock *B) const { return Frontiers.find(B); }
623
624  void addBasicBlock(BasicBlock *BB, const DomSetType &frontier) {
625    assert(find(BB) == end() && "Block already in DominanceFrontier!");
626    Frontiers.insert(std::make_pair(BB, frontier));
627  }
628
629  /// removeBlock - Remove basic block BB's frontier.
630  void removeBlock(BasicBlock *BB) {
631    assert(find(BB) != end() && "Block is not in DominanceFrontier!");
632    for (iterator I = begin(), E = end(); I != E; ++I)
633      I->second.erase(BB);
634    Frontiers.erase(BB);
635  }
636
637  void addToFrontier(iterator I, BasicBlock *Node) {
638    assert(I != end() && "BB is not in DominanceFrontier!");
639    I->second.insert(Node);
640  }
641
642  void removeFromFrontier(iterator I, BasicBlock *Node) {
643    assert(I != end() && "BB is not in DominanceFrontier!");
644    assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB");
645    I->second.erase(Node);
646  }
647
648  /// print - Convert to human readable form
649  ///
650  virtual void print(std::ostream &OS, const Module* = 0) const;
651  void print(std::ostream *OS, const Module* M = 0) const {
652    if (OS) print(*OS, M);
653  }
654  virtual void dump();
655};
656
657
658//===-------------------------------------
659/// DominanceFrontier Class - Concrete subclass of DominanceFrontierBase that is
660/// used to compute a forward dominator frontiers.
661///
662class DominanceFrontier : public DominanceFrontierBase {
663public:
664  static char ID; // Pass ID, replacement for typeid
665  DominanceFrontier() :
666    DominanceFrontierBase(intptr_t(&ID), false) {}
667
668  BasicBlock *getRoot() const {
669    assert(Roots.size() == 1 && "Should always have entry node!");
670    return Roots[0];
671  }
672
673  virtual bool runOnFunction(Function &) {
674    Frontiers.clear();
675    DominatorTree &DT = getAnalysis<DominatorTree>();
676    Roots = DT.getRoots();
677    assert(Roots.size() == 1 && "Only one entry block for forward domfronts!");
678    calculate(DT, DT[Roots[0]]);
679    return false;
680  }
681
682  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
683    AU.setPreservesAll();
684    AU.addRequired<DominatorTree>();
685  }
686
687  /// splitBlock - BB is split and now it has one successor. Update dominance
688  /// frontier to reflect this change.
689  void splitBlock(BasicBlock *BB);
690
691  /// BasicBlock BB's new dominator is NewBB. Update BB's dominance frontier
692  /// to reflect this change.
693  void changeImmediateDominator(BasicBlock *BB, BasicBlock *NewBB,
694                                DominatorTree *DT) {
695    // NewBB is now  dominating BB. Which means BB's dominance
696    // frontier is now part of NewBB's dominance frontier. However, BB
697    // itself is not member of NewBB's dominance frontier.
698    DominanceFrontier::iterator NewDFI = find(NewBB);
699    DominanceFrontier::iterator DFI = find(BB);
700    DominanceFrontier::DomSetType BBSet = DFI->second;
701    for (DominanceFrontier::DomSetType::iterator BBSetI = BBSet.begin(),
702           BBSetE = BBSet.end(); BBSetI != BBSetE; ++BBSetI) {
703      BasicBlock *DFMember = *BBSetI;
704      // Insert only if NewBB dominates DFMember.
705      if (!DT->dominates(NewBB, DFMember))
706        NewDFI->second.insert(DFMember);
707    }
708    NewDFI->second.erase(BB);
709  }
710
711private:
712  const DomSetType &calculate(const DominatorTree &DT,
713                              const DomTreeNode *Node);
714};
715
716
717} // End llvm namespace
718
719#endif
720