136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines//===- Dominators.h - Dominator Info Calculation ----------------*- C++ -*-===// 236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// 336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// The LLVM Compiler Infrastructure 436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// 536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// This file is distributed under the University of Illinois Open Source 636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// License. See LICENSE.TXT for details. 736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// 836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines//===----------------------------------------------------------------------===// 936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// 1036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// This file defines the DominatorTree class, which provides fast and efficient 1136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// dominance queries. 1236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// 1336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines//===----------------------------------------------------------------------===// 1436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 1536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#ifndef LLVM_IR_DOMINATORS_H 1636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#define LLVM_IR_DOMINATORS_H 1736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 1836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/ADT/DenseMap.h" 1936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/ADT/DepthFirstIterator.h" 2036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/ADT/GraphTraits.h" 2136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/ADT/SmallPtrSet.h" 2236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/ADT/SmallVector.h" 2336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/BasicBlock.h" 2436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/CFG.h" 2536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/Function.h" 2636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/Pass.h" 2736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/Support/Compiler.h" 2836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/Support/GenericDomTree.h" 2936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/Support/raw_ostream.h" 3036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include <algorithm> 3136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 3236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesnamespace llvm { 3336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 3436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesEXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase<BasicBlock>); 3536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesEXTERN_TEMPLATE_INSTANTIATION(class DominatorTreeBase<BasicBlock>); 3636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 3736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#define LLVM_COMMA , 3836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesEXTERN_TEMPLATE_INSTANTIATION(void Calculate<Function LLVM_COMMA BasicBlock *>( 3936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DominatorTreeBase<GraphTraits<BasicBlock *>::NodeType> &DT LLVM_COMMA 4036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Function &F)); 4136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesEXTERN_TEMPLATE_INSTANTIATION( 4236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void Calculate<Function LLVM_COMMA Inverse<BasicBlock *> >( 4336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DominatorTreeBase<GraphTraits<Inverse<BasicBlock *> >::NodeType> &DT 4436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines LLVM_COMMA Function &F)); 4536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#undef LLVM_COMMA 4636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 4736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinestypedef DomTreeNodeBase<BasicBlock> DomTreeNode; 4836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 4936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesclass BasicBlockEdge { 5036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const BasicBlock *Start; 5136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const BasicBlock *End; 5236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinespublic: 5336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BasicBlockEdge(const BasicBlock *Start_, const BasicBlock *End_) : 5436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Start(Start_), End(End_) { } 5536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const BasicBlock *getStart() const { 5636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return Start; 5736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 5836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const BasicBlock *getEnd() const { 5936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return End; 6036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 6136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool isSingleEdge() const; 6236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines}; 6336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 6436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \brief Concrete subclass of DominatorTreeBase that is used to compute a 6536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// normal dominator tree. 6636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesclass DominatorTree : public DominatorTreeBase<BasicBlock> { 6736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinespublic: 6836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines typedef DominatorTreeBase<BasicBlock> Base; 6936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 7036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DominatorTree() : DominatorTreeBase<BasicBlock>(false) {} 7136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 7236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \brief Returns *false* if the other dominator tree matches this dominator 7336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// tree. 7436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines inline bool compare(const DominatorTree &Other) const { 7536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const DomTreeNode *R = getRootNode(); 7636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const DomTreeNode *OtherR = Other.getRootNode(); 7736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 7836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!R || !OtherR || R->getBlock() != OtherR->getBlock()) 7936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return true; 8036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 8136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Base::compare(Other)) 8236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return true; 8336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 8436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 8536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 8636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 8736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Ensure base-class overloads are visible. 8836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines using Base::dominates; 8936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 9036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \brief Return true if Def dominates a use in User. 9136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// 9236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// This performs the special checks necessary if Def and User are in the same 9336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// basic block. Note that Def doesn't dominate a use in Def itself! 9436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool dominates(const Instruction *Def, const Use &U) const; 9536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool dominates(const Instruction *Def, const Instruction *User) const; 9636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool dominates(const Instruction *Def, const BasicBlock *BB) const; 9736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool dominates(const BasicBlockEdge &BBE, const Use &U) const; 9836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool dominates(const BasicBlockEdge &BBE, const BasicBlock *BB) const; 9936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 10036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Ensure base class overloads are visible. 10136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines using Base::isReachableFromEntry; 10236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 10336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \brief Provide an overload for a Use. 10436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool isReachableFromEntry(const Use &U) const; 10536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 10636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \brief Verify the correctness of the domtree by re-computing it. 10736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// 10836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// This should only be used for debugging as it aborts the program if the 10936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// verification fails. 11036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void verifyDomTree() const; 11136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines}; 11236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 11336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines//===------------------------------------- 11436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// DominatorTree GraphTraits specializations so the DominatorTree can be 11536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// iterable by generic graph iterators. 11636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 11736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinestemplate <> struct GraphTraits<DomTreeNode*> { 11836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines typedef DomTreeNode NodeType; 11936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines typedef NodeType::iterator ChildIteratorType; 12036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 12136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines static NodeType *getEntryNode(NodeType *N) { 12236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return N; 12336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 12436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines static inline ChildIteratorType child_begin(NodeType *N) { 12536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return N->begin(); 12636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 12736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines static inline ChildIteratorType child_end(NodeType *N) { 12836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return N->end(); 12936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 13036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 13136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines typedef df_iterator<DomTreeNode*> nodes_iterator; 13236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 13336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines static nodes_iterator nodes_begin(DomTreeNode *N) { 13436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return df_begin(getEntryNode(N)); 13536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 13636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 13736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines static nodes_iterator nodes_end(DomTreeNode *N) { 13836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return df_end(getEntryNode(N)); 13936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 14036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines}; 14136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 14236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinestemplate <> struct GraphTraits<DominatorTree*> 14336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines : public GraphTraits<DomTreeNode*> { 14436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines static NodeType *getEntryNode(DominatorTree *DT) { 14536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return DT->getRootNode(); 14636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 14736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 14836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines static nodes_iterator nodes_begin(DominatorTree *N) { 14936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return df_begin(getEntryNode(N)); 15036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 15136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 15236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines static nodes_iterator nodes_end(DominatorTree *N) { 15336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return df_end(getEntryNode(N)); 15436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 15536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines}; 15636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 15736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \brief Analysis pass which computes a \c DominatorTree. 15836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesclass DominatorTreeWrapperPass : public FunctionPass { 15936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DominatorTree DT; 16036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 16136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinespublic: 16236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines static char ID; 16336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 16436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DominatorTreeWrapperPass() : FunctionPass(ID) { 16536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines initializeDominatorTreeWrapperPassPass(*PassRegistry::getPassRegistry()); 16636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 16736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 16836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DominatorTree &getDomTree() { return DT; } 16936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const DominatorTree &getDomTree() const { return DT; } 17036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 17136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool runOnFunction(Function &F) override; 17236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 17336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void verifyAnalysis() const override; 17436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 17536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override { 17636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AU.setPreservesAll(); 17736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 17836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 17936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void releaseMemory() override { DT.releaseMemory(); } 18036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 181dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines void print(raw_ostream &OS, const Module *M = nullptr) const override; 18236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines}; 18336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 18436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} // End llvm namespace 18536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 18636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#endif 187