path: root/include/llvm/Analysis/Dominators.h

//===- llvm/Analysis/Dominators.h - Dominator Info Calculation --*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file defines the following classes:
//  1. DominatorTree: Represent dominators as an explicit tree structure.
//  2. DominanceFrontier: Calculate and hold the dominance frontier for a
//     function.
//
//  These data structures are listed in increasing order of complexity.  It
//  takes longer to calculate the dominator frontier, for example, than the
//  DominatorTree mapping.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_ANALYSIS_DOMINATORS_H
#define LLVM_ANALYSIS_DOMINATORS_H

#include "llvm/Pass.h"
#include "llvm/Function.h"
#include "llvm/Instructions.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/GraphTraits.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Assembly/Writer.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <map>
#include <set>

namespace llvm {

//===----------------------------------------------------------------------===//
/// DominatorBase - Base class that other, more interesting dominator analyses
/// inherit from.
///
template <class NodeT>
class DominatorBase {
protected:
  std::vector<NodeT*> Roots;
  const bool IsPostDominators;
  inline explicit DominatorBase(bool isPostDom) :
    Roots(), IsPostDominators(isPostDom) {}
public:

  /// getRoots - Return the root blocks of the current CFG.  This may include
  /// multiple blocks if we are computing post dominators.  For forward
  /// dominators, this will always be a single block (the entry node).
  ///
  inline const std::vector<NodeT*> &getRoots() const { return Roots; }

  /// isPostDominator - Returns true if analysis based of postdoms
  ///
  bool isPostDominator() const { return IsPostDominators; }
};


//===----------------------------------------------------------------------===//
// DomTreeNode - Dominator Tree Node
template<class NodeT> class DominatorTreeBase;
struct PostDominatorTree;
class MachineBasicBlock;

template <class NodeT>
class DomTreeNodeBase {
  NodeT *TheBB;
  DomTreeNodeBase<NodeT> *IDom;
  std::vector<DomTreeNodeBase<NodeT> *> Children;
  int DFSNumIn, DFSNumOut;

  template<class N> friend class DominatorTreeBase;
  friend struct PostDominatorTree;
public:
  typedef typename std::vector<DomTreeNodeBase<NodeT> *>::iterator iterator;
  typedef typename std::vector<DomTreeNodeBase<NodeT> *>::const_iterator
                   const_iterator;

  iterator begin()             { return Children.begin(); }
  iterator end()               { return Children.end(); }
  const_iterator begin() const { return Children.begin(); }
  const_iterator end()   const { return Children.end(); }

  NodeT *getBlock() const { return TheBB; }
  DomTreeNodeBase<NodeT> *getIDom() const { return IDom; }
  const std::vector<DomTreeNodeBase<NodeT>*> &getChildren() const {
    return Children;
  }

  DomTreeNodeBase(NodeT *BB, DomTreeNodeBase<NodeT> *iDom)
    : TheBB(BB), IDom(iDom), DFSNumIn(-1), DFSNumOut(-1) { }

  DomTreeNodeBase<NodeT> *addChild(DomTreeNodeBase<NodeT> *C) {
    Children.push_back(C);
    return C;
  }

  size_t getNumChildren() const {
    return Children.size();
  }

  void clearAllChildren() {
    Children.clear();
  }

  bool compare(DomTreeNodeBase<NodeT> *Other) {
    if (getNumChildren() != Other->getNumChildren())
      return true;

    SmallPtrSet<NodeT *, 4> OtherChildren;
    for (iterator I = Other->begin(), E = Other->end(); I != E; ++I) {
      NodeT *Nd = (*I)->getBlock();
      OtherChildren.insert(Nd);
    }

    for (iterator I = begin(), E = end(); I != E; ++I) {
      NodeT *N = (*I