llvm.org GIT mirror llvm / 9f998de include / llvm / CodeGen / MachineDominators.h
9f998de

Tree @9f998de (Download .tar.gz)

MachineDominators.h @9f998de

08895f8
 
 
 
7ed47a1
 
08895f8
 
 
 
 
 
 
 
 
 
 
abd9855
 
08895f8
2073b0a
1decd56
08895f8
 
 
5d32ec4
 
 
 
 
 
 
 
 
08895f8
 
 
 
 
 
 
 
 
7209987
d68a076
7209987
d68a076
7209987
af9ac8f
7209987
9f998de
7209987
08895f8
 
 
 
 
 
 
7209987
08895f8
 
 
7209987
08895f8
 
 
7209987
9f998de
7209987
55ba691
 
08895f8
 
7209987
55ba691
 
08895f8
 
7209987
08895f8
 
a293782
 
08895f8
 
 
a293782
c50b433
 
08895f8
 
 
 
 
 
 
 
 
7209987
08895f8
55ba691
08895f8
 
7209987
55ba691
 
08895f8
 
7209987
08895f8
 
 
 
 
 
7209987
08895f8
 
 
7209987
08895f8
 
 
 
 
 
7209987
08895f8
7209987
08895f8
 
 
 
 
7209987
08895f8
 
 
 
 
 
 
7209987
08895f8
 
 
 
7209987
08895f8
e2d5004
08895f8
 
 
 
7209987
08895f8
 
 
 
 
54ab2e9
 
 
55ba691
54ab2e9
 
 
9f998de
7209987
9f998de
08895f8
 
96fa396
 
 
 
99d562d
 
 
96fa396
 
 
7209987
96fa396
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
08895f8
 
1bd3271
//=- llvm/CodeGen/MachineDominators.h - Machine Dom 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 classes mirroring those in llvm/Analysis/Dominators.h,
// but for target-specific code rather than target-independent IR.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_CODEGEN_MACHINEDOMINATORS_H
#define LLVM_CODEGEN_MACHINEDOMINATORS_H

#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/Support/GenericDomTree.h"
#include "llvm/Support/GenericDomTreeConstruction.h"

namespace llvm {

template<>
inline void DominatorTreeBase<MachineBasicBlock>::addRoot(MachineBasicBlock* MBB) {
  this->Roots.push_back(MBB);
}

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

typedef DomTreeNodeBase<MachineBasicBlock> MachineDomTreeNode;

//===-------------------------------------
/// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
/// compute a normal dominator tree.
///
class MachineDominatorTree : public MachineFunctionPass {
public:
  static char ID; // Pass ID, replacement for typeid
  DominatorTreeBase<MachineBasicBlock>* DT;

  MachineDominatorTree();

  ~MachineDominatorTree();

  DominatorTreeBase<MachineBasicBlock>& getBase() { return *DT; }

  void getAnalysisUsage(AnalysisUsage &AU) const override;

  /// 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<MachineBasicBlock*> &getRoots() const {
    return DT->getRoots();
  }

  inline MachineBasicBlock *getRoot() const {
    return DT->getRoot();
  }

  inline MachineDomTreeNode *getRootNode() const {
    return DT->getRootNode();
  }

  bool runOnMachineFunction(MachineFunction &F) override;

  inline bool dominates(const MachineDomTreeNode* A,
                        const MachineDomTreeNode* B) const {
    return DT->dominates(A, B);
  }

  inline bool dominates(const MachineBasicBlock* A,
                        const MachineBasicBlock* B) const {
    return DT->dominates(A, B);
  }

  // dominates - Return true if A dominates B. This performs the
  // special checks necessary if A and B are in the same basic block.
  bool dominates(const MachineInstr *A, const MachineInstr *B) const {
    const MachineBasicBlock *BBA = A->getParent(), *BBB = B->getParent();
    if (BBA != BBB) return DT->dominates(BBA, BBB);

    // Loop through the basic block until we find A or B.
    MachineBasicBlock::const_iterator I = BBA->begin();
    for (; &*I != A && &*I != B; ++I)
      /*empty*/ ;

    //if(!DT.IsPostDominators) {
      // A dominates B if it is found first in the basic block.
      return &*I == A;
    //} else {
    //  // A post-dominates B if B is found first in the basic block.
    //  return &*I == B;
    //}
  }

  inline bool properlyDominates(const MachineDomTreeNode* A,
                                const MachineDomTreeNode* B) const {
    return DT->properlyDominates(A, B);
  }

  inline bool properlyDominates(const MachineBasicBlock* A,
                                const MachineBasicBlock* B) const {
    return DT->properlyDominates(A, B);
  }

  /// findNearestCommonDominator - Find nearest common dominator basic block
  /// for basic block A and B. If there is no such block then return NULL.
  inline MachineBasicBlock *findNearestCommonDominator(MachineBasicBlock *A,
                                                       MachineBasicBlock *B) {
    return DT->findNearestCommonDominator(A, B);
  }

  inline MachineDomTreeNode *operator[](MachineBasicBlock *BB) const {
    return DT->getNode(BB);
  }

  /// getNode - return the (Post)DominatorTree node for the specified basic
  /// block.  This is the same as using operator[] on this class.
  ///
  inline MachineDomTreeNode *getNode(MachineBasicBlock *BB) const {
    return DT->getNode(BB);
  }

  /// addNewBlock - Add a new node to the dominator tree information.  This
  /// creates a new node as a child of DomBB dominator node,linking it into
  /// the children list of the immediate dominator.
  inline MachineDomTreeNode *addNewBlock(MachineBasicBlock *BB,
                                         MachineBasicBlock *DomBB) {
    return DT->addNewBlock(BB, DomBB);
  }

  /// changeImmediateDominator - This method is used to update the dominator
  /// tree information when a node's immediate dominator changes.
  ///
  inline void changeImmediateDominator(MachineBasicBlock *N,
                                       MachineBasicBlock* NewIDom) {
    DT->changeImmediateDominator(N, NewIDom);
  }

  inline void changeImmediateDominator(MachineDomTreeNode *N,
                                       MachineDomTreeNode* NewIDom) {
    DT->changeImmediateDominator(N, NewIDom);
  }

  /// eraseNode - Removes a node from  the dominator tree. Block must not
  /// dominate any other blocks. Removes node from its immediate dominator's
  /// children list. Deletes dominator node associated with basic block BB.
  inline void eraseNode(MachineBasicBlock *BB) {
    DT->eraseNode(BB);
  }

  /// splitBlock - BB is split and now it has one successor. Update dominator
  /// tree to reflect this change.
  inline void splitBlock(MachineBasicBlock* NewBB) {
    DT->splitBlock(NewBB);
  }

  /// isReachableFromEntry - Return true if A is dominated by the entry
  /// block of the function containing it.
  bool isReachableFromEntry(const MachineBasicBlock *A) {
    return DT->isReachableFromEntry(A);
  }

  void releaseMemory() override;

  void print(raw_ostream &OS, const Module*) const override;
};

//===-------------------------------------
/// DominatorTree GraphTraits specialization so the DominatorTree can be
/// iterable by generic graph iterators.
///

template<class T> struct GraphTraits;

template <> struct GraphTraits<MachineDomTreeNode *> {
  typedef MachineDomTreeNode NodeType;
  typedef NodeType::iterator  ChildIteratorType;

  static NodeType *getEntryNode(NodeType *N) {
    return N;
  }
  static inline ChildIteratorType child_begin(NodeType* N) {
    return N->begin();
  }
  static inline ChildIteratorType child_end(NodeType* N) {
    return N->end();
  }
};

template <> struct GraphTraits<MachineDominatorTree*>
  : public GraphTraits<MachineDomTreeNode *> {
  static NodeType *getEntryNode(MachineDominatorTree *DT) {
    return DT->getRootNode();
  }
};

}

#endif