llvm.org GIT mirror llvm / release_35 include / llvm / IR / Dominators.h
release_35

Tree @release_35 (Download .tar.gz)

Dominators.h @release_35

56e1394
9769ab2
6fbcc26
 
7ed47a1
 
9769ab2
6fbcc26
70b6337
9fc5cdf
 
9769ab2
70b6337
 
56e1394
 
70b6337
49b653a
f0d24f1
78daec9
49b653a
 
2073b0a
03e36d7
0b8c9a8
255f89f
49b653a
1decd56
791102f
1aad74c
7a73b80
d0fde30
 
49b653a
2073b0a
49b653a
d4762e8
fa4ff8a
a666f9d
 
 
 
 
 
d4762e8
 
1aad74c
 
0513059
 
 
 
 
 
 
 
 
 
 
 
 
 
702bcce
bb4954d
 
7f2eff7
b62ff3f
7f2eff7
0aeed04
7f2eff7
0aeed04
bb4954d
 
7f2eff7
 
 
0aeed04
5b57e72
 
0aeed04
7f2eff7
5b57e72
 
 
 
 
7f2eff7
 
0aeed04
7f2eff7
 
 
 
558ece2
c9ae8cc
 
702bcce
 
b5c26ef
7f2eff7
 
0aeed04
7f2eff7
558ece2
 
7f2eff7
 
 
 
 
b62ff3f
 
 
bb4954d
 
 
f0d24f1
2604242
b62ff3f
0aeed04
b62ff3f
 
 
f0d24f1
b62ff3f
 
f0d24f1
b62ff3f
 
f0d24f1
 
 
 
 
 
 
 
 
 
b62ff3f
 
 
f0d24f1
b62ff3f
 
 
f0d24f1
 
 
 
 
 
 
 
b62ff3f
 
7f2eff7
 
 
 
 
 
 
 
 
 
 
 
 
 
98f54c0
7f2eff7
98f54c0
7f2eff7
98f54c0
7f2eff7
 
 
98f54c0
7f2eff7
ec0f0bc
7f2eff7
 
d0fde30
 
70b6337
//===- 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 DominatorTree class, which provides fast and efficient
// dominance queries.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_IR_DOMINATORS_H
#define LLVM_IR_DOMINATORS_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/IR/BasicBlock.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Function.h"
#include "llvm/Pass.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/GenericDomTree.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>

namespace llvm {

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

#define LLVM_COMMA ,
EXTERN_TEMPLATE_INSTANTIATION(void Calculate<Function LLVM_COMMA BasicBlock *>(
    DominatorTreeBase<GraphTraits<BasicBlock *>::NodeType> &DT LLVM_COMMA
        Function &F));
EXTERN_TEMPLATE_INSTANTIATION(
    void Calculate<Function LLVM_COMMA Inverse<BasicBlock *> >(
        DominatorTreeBase<GraphTraits<Inverse<BasicBlock *> >::NodeType> &DT
            LLVM_COMMA Function &F));
#undef LLVM_COMMA

typedef DomTreeNodeBase<BasicBlock> DomTreeNode;

class BasicBlockEdge {
  const BasicBlock *Start;
  const BasicBlock *End;
public:
  BasicBlockEdge(const BasicBlock *Start_, const BasicBlock *End_) :
    Start(Start_), End(End_) { }
  const BasicBlock *getStart() const {
    return Start;
  }
  const BasicBlock *getEnd() const {
    return End;
  }
  bool isSingleEdge() const;
};

/// \brief Concrete subclass of DominatorTreeBase that is used to compute a
/// normal dominator tree.
class DominatorTree : public DominatorTreeBase<BasicBlock> {
public:
  typedef DominatorTreeBase<BasicBlock> Base;

  DominatorTree() : DominatorTreeBase<BasicBlock>(false) {}

  /// \brief Returns *false* if the other dominator tree matches this dominator
  /// tree.
  inline bool compare(const DominatorTree &Other) const {
    const DomTreeNode *R = getRootNode();
    const DomTreeNode *OtherR = Other.getRootNode();

    if (!R || !OtherR || R->getBlock() != OtherR->getBlock())
      return true;

    if (Base::compare(Other))
      return true;

    return false;
  }

  // Ensure base-class overloads are visible.
  using Base::dominates;

  /// \brief Return true if Def dominates a use in User.
  ///
  /// This performs the special checks necessary if Def and User are in the same
  /// basic block. Note that Def doesn't dominate a use in Def itself!
  bool dominates(const Instruction *Def, const Use &U) const;
  bool dominates(const Instruction *Def, const Instruction *User) const;
  bool dominates(const Instruction *Def, const BasicBlock *BB) const;
  bool dominates(const BasicBlockEdge &BBE, const Use &U) const;
  bool dominates(const BasicBlockEdge &BBE, const BasicBlock *BB) const;

  // Ensure base class overloads are visible.
  using Base::isReachableFromEntry;

  /// \brief Provide an overload for a Use.
  bool isReachableFromEntry(const Use &U) const;

  /// \brief Verify the correctness of the domtree by re-computing it.
  ///
  /// This should only be used for debugging as it aborts the program if the
  /// verification fails.
  void verifyDomTree() const;
};

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

template <> struct GraphTraits<DomTreeNode*> {
  typedef DomTreeNode 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();
  }

  typedef df_iterator<DomTreeNode*> nodes_iterator;

  static nodes_iterator nodes_begin(DomTreeNode *N) {
    return df_begin(getEntryNode(N));
  }

  static nodes_iterator nodes_end(DomTreeNode *N) {
    return df_end(getEntryNode(N));
  }
};

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

  static nodes_iterator nodes_begin(DominatorTree *N) {
    return df_begin(getEntryNode(N));
  }

  static nodes_iterator nodes_end(DominatorTree *N) {
    return df_end(getEntryNode(N));
  }
};

/// \brief Analysis pass which computes a \c DominatorTree.
class DominatorTreeWrapperPass : public FunctionPass {
  DominatorTree DT;

public:
  static char ID;

  DominatorTreeWrapperPass() : FunctionPass(ID) {
    initializeDominatorTreeWrapperPassPass(*PassRegistry::getPassRegistry());
  }

  DominatorTree &getDomTree() { return DT; }
  const DominatorTree &getDomTree() const { return DT; }

  bool runOnFunction(Function &F) override;

  void verifyAnalysis() const override;

  void getAnalysisUsage(AnalysisUsage &AU) const override {
    AU.setPreservesAll();
  }

  void releaseMemory() override { DT.releaseMemory(); }

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

} // End llvm namespace

#endif