#ifndef LLVM_ANALYSIS_DOMINATORS_H
#define LLVM_ANALYSIS_DOMINATORS_H
-#include "llvm/Pass.h"
-#include "llvm/Function.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/Function.h"
+#include "llvm/Pass.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/raw_ostream.h"
Children.clear();
}
- bool compare(DomTreeNodeBase<NodeT> *Other) {
+ bool compare(const DomTreeNodeBase<NodeT> *Other) const {
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();
+ SmallPtrSet<const NodeT *, 4> OtherChildren;
+ for (const_iterator I = Other->begin(), E = Other->end(); I != E; ++I) {
+ const NodeT *Nd = (*I)->getBlock();
OtherChildren.insert(Nd);
}
- for (iterator I = begin(), E = end(); I != E; ++I) {
- NodeT *N = (*I)->getBlock();
+ for (const_iterator I = begin(), E = end(); I != E; ++I) {
+ const NodeT *N = (*I)->getBlock();
if (OtherChildren.count(N) == 0)
return true;
}
EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase<MachineBasicBlock>);
template<class NodeT>
-static raw_ostream &operator<<(raw_ostream &o,
+inline raw_ostream &operator<<(raw_ostream &o,
const DomTreeNodeBase<NodeT> *Node) {
if (Node->getBlock())
WriteAsOperand(o, Node->getBlock(), false);
}
template<class NodeT>
-static void PrintDomTree(const DomTreeNodeBase<NodeT> *N, raw_ostream &o,
+inline 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(),
template<class NodeT>
class DominatorTreeBase : public DominatorBase<NodeT> {
+ bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A,
+ const DomTreeNodeBase<NodeT> *B) const {
+ assert(A != B);
+ assert(isReachableFromEntry(B));
+ assert(isReachableFromEntry(A));
+
+ const DomTreeNodeBase<NodeT> *IDom;
+ while ((IDom = B->getIDom()) != 0 && IDom != A && IDom != B)
+ B = IDom; // Walk up the tree
+ return IDom != 0;
+ }
+
protected:
typedef DenseMap<NodeT*, DomTreeNodeBase<NodeT>*> DomTreeNodeMapType;
DomTreeNodeMapType DomTreeNodes;
DomTreeNodeBase<NodeT> *getRootNode() { return RootNode; }
const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; }
- /// properlyDominates - Returns true iff this dominates N and this != N.
+ /// properlyDominates - Returns true iff A dominates B and A != B.
/// Note that this is not a constant time operation!
///
bool properlyDominates(const DomTreeNodeBase<NodeT> *A,
bool properlyDominates(const NodeT *A, const NodeT *B);
- bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A,
- const DomTreeNodeBase<NodeT> *B) const {
- // A node trivially dominates itself.
- if (B == A)
- return true;
-
- // An unreachable node is dominated by anything.
- if (!isReachableFromEntry(B))
- return true;
-
- // And dominates nothing.
- if (!isReachableFromEntry(A))
- return false;
-
- const DomTreeNodeBase<NodeT> *IDom;
- while ((IDom = B->getIDom()) != 0 && IDom != A && IDom != B)
- B = IDom; // Walk up the tree
- return IDom != 0;
- }
-
-
/// isReachableFromEntry - Return true if A is dominated by the entry
/// block of the function containing it.
bool isReachableFromEntry(const NodeT* A) const {
// Initialize the roots list
for (typename TraitsTy::nodes_iterator I = TraitsTy::nodes_begin(&F),
E = TraitsTy::nodes_end(&F); I != E; ++I) {
- if (std::distance(TraitsTy::child_begin(I),
- TraitsTy::child_end(I)) == 0)
+ if (TraitsTy::child_begin(I) == TraitsTy::child_end(I))
addRoot(I);
// Prepopulate maps so that we don't get iterator invalidation issues later.
EXTERN_TEMPLATE_INSTANTIATION(class DominatorTreeBase<BasicBlock>);
+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;
+};
+
//===-------------------------------------
/// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
/// compute a normal dominator tree.
// dominates - 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;
bool properlyDominates(const DomTreeNode *A, const DomTreeNode *B) const {
return DT->properlyDominates(A, B);
return DT->isReachableFromEntry(A);
}
+ bool isReachableFromEntry(const Use &U) const;
+
virtual void releaseMemory() {
DT->releaseMemory();