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 {

//===----------------------------------------------------------------------===//
template <class NodeT>
class DominatorBase {
protected:
  std::vector<NodeT*> Roots;
  const bool IsPostDominators;
  inline explicit DominatorBase(bool isPostDom) :
    Roots(), IsPostDominators(isPostDom) {}
public:

  inline const std::vector<NodeT*> &getRoots() const { return Roots; }

  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)->getBlock();
      if (OtherChildren.count(N) == 0)
        return true;
    }
    return false;
  }

  void setIDom(DomTreeNodeBase<NodeT> *NewIDom) {
    assert(IDom && "No immediate dominator?");
    if (IDom != NewIDom) {
      typename std::vector<DomTreeNodeBase<NodeT>*>::iterator I =
                  std::find(IDom->Children.begin(), IDom->Children.end(), this);
      assert(I != IDom->Children.end() &&
             "Not in immediate dominator children set!");
      // I am no longer your child...
      IDom->Children.erase(I);

      // Switch to new dominator
      IDom = NewIDom;
      IDom->Children.push_back(this);
    }
  }

  unsigned getDFSNumIn() const { return DFSNumIn; }
  unsigned getDFSNumOut() const { return DFSNumOut; }
private:
  // Return true if this node is dominated by other. Use this only if DFS info
  // is valid.
  bool DominatedBy(const DomTreeNodeBase<NodeT> *other) const {
    return this->DFSNumIn >= other->DFSNumIn &&
      this->DFSNumOut <= other->DFSNumOut;
  }
};

EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase<BasicBlock>);
EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase<MachineBasicBlock>);

template<class NodeT>
static raw_ostream &operator<<(raw_ostream &o,
                               const DomTreeNodeBase<NodeT> *Node) {
  if (Node->getBlock())
    WriteAsOperand(o, Node->getBlock(), false);
  else
    o << " <<exit node>>";

  o << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "}";

  return o << "\n";
}

template<class NodeT>
static void PrintDomTree(const DomTreeNodeBase<NodeT> *N, raw_ostream &o,
                         unsigned Lev) {
  o.indent(2*Lev) << "[" << Lev << "] " << N;
  for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(),
       E = N->end(); I != E; ++I)
    PrintDomTree<NodeT>(*I, o, Lev+1);
}

typedef DomTreeNodeBase<BasicBlock> DomTreeNode;

//===----------------------------------------------------------------------===//

template<class FuncT, class N>
void Calculate(DominatorTreeBase<typename GraphTraits<N>::NodeType>& DT,
               FuncT& F);

template<class NodeT>
class DominatorTreeBase : public DominatorBase<NodeT> {
protected:
  typedef DenseMap<NodeT*, DomTreeNodeBase<NodeT>*> DomTreeNodeMapType;
  DomTreeNodeMapType DomTreeNodes;
  DomTreeNodeBase<NodeT> *RootNode;

  bool DFSInfoValid;
  unsigned int SlowQueries;
  // Information record used during immediate dominators computation.
  struct InfoRec {
    unsigned DFSNum;
    unsigned Semi;
    unsigned Size;
    NodeT *Label, *Child;
    unsigned Parent, Ancestor;

    std::vector<NodeT*> Bucket;

    InfoRec() : DFSNum(0), Semi(0), Size(0), Label(0), Child(0), Parent(0),
                Ancestor(0) {}
  };

  DenseMap<NodeT*, NodeT*> IDoms;

  // Vertex - Map the DFS number to the BasicBlock*
  std::vector<NodeT*> Vertex;

  // Info - Collection of information used during the computation of idoms.
  DenseMap<NodeT*, InfoRec> Info;

  void reset() {
    for (typename DomTreeNodeMapType::iterator I = this->DomTreeNodes.begin(),
           E = DomTreeNodes.end(); I != E; ++I)
      delete I->second;
    DomTreeNodes.clear();
    IDoms.clear();
    this->Roots.clear();
    Vertex.clear();
    RootNode = 0;
  }

  // NewBB is split and now it