DominanceFrontier.h [plain text]
#ifndef LLVM_ANALYSIS_DOMINANCEFRONTIER_H
#define LLVM_ANALYSIS_DOMINANCEFRONTIER_H
#include "llvm/IR/Dominators.h"
#include <map>
#include <set>
namespace llvm {
template <class BlockT>
class DominanceFrontierBase {
public:
typedef std::set<BlockT *> DomSetType; typedef std::map<BlockT *, DomSetType> DomSetMapType;
protected:
typedef GraphTraits<BlockT *> BlockTraits;
DomSetMapType Frontiers;
std::vector<BlockT *> Roots;
const bool IsPostDominators;
public:
DominanceFrontierBase(bool isPostDom) : IsPostDominators(isPostDom) {}
inline const std::vector<BlockT *> &getRoots() const {
return Roots;
}
BlockT *getRoot() const {
assert(Roots.size() == 1 && "Should always have entry node!");
return Roots[0];
}
bool isPostDominator() const {
return IsPostDominators;
}
void releaseMemory() {
Frontiers.clear();
}
typedef typename DomSetMapType::iterator iterator;
typedef typename DomSetMapType::const_iterator const_iterator;
iterator begin() { return Frontiers.begin(); }
const_iterator begin() const { return Frontiers.begin(); }
iterator end() { return Frontiers.end(); }
const_iterator end() const { return Frontiers.end(); }
iterator find(BlockT *B) { return Frontiers.find(B); }
const_iterator find(BlockT *B) const { return Frontiers.find(B); }
iterator addBasicBlock(BlockT *BB, const DomSetType &frontier) {
assert(find(BB) == end() && "Block already in DominanceFrontier!");
return Frontiers.insert(std::make_pair(BB, frontier)).first;
}
void removeBlock(BlockT *BB);
void addToFrontier(iterator I, BlockT *Node);
void removeFromFrontier(iterator I, BlockT *Node);
bool compareDomSet(DomSetType &DS1, const DomSetType &DS2) const;
bool compare(DominanceFrontierBase<BlockT> &Other) const;
void print(raw_ostream &OS) const;
void dump() const;
};
template <class BlockT>
class ForwardDominanceFrontierBase : public DominanceFrontierBase<BlockT> {
private:
typedef GraphTraits<BlockT *> BlockTraits;
public:
typedef DominatorTreeBase<BlockT> DomTreeT;
typedef DomTreeNodeBase<BlockT> DomTreeNodeT;
typedef typename DominanceFrontierBase<BlockT>::DomSetType DomSetType;
ForwardDominanceFrontierBase() : DominanceFrontierBase<BlockT>(false) {}
void analyze(DomTreeT &DT) {
this->Roots = DT.getRoots();
assert(this->Roots.size() == 1 &&
"Only one entry block for forward domfronts!");
calculate(DT, DT[this->Roots[0]]);
}
const DomSetType &calculate(const DomTreeT &DT, const DomTreeNodeT *Node);
};
class DominanceFrontier : public FunctionPass {
ForwardDominanceFrontierBase<BasicBlock> Base;
public:
typedef DominatorTreeBase<BasicBlock> DomTreeT;
typedef DomTreeNodeBase<BasicBlock> DomTreeNodeT;
typedef DominanceFrontierBase<BasicBlock>::DomSetType DomSetType;
typedef DominanceFrontierBase<BasicBlock>::iterator iterator;
typedef DominanceFrontierBase<BasicBlock>::const_iterator const_iterator;
static char ID;
DominanceFrontier();
ForwardDominanceFrontierBase<BasicBlock> &getBase() { return Base; }
inline const std::vector<BasicBlock *> &getRoots() const {
return Base.getRoots();
}
BasicBlock *getRoot() const { return Base.getRoot(); }
bool isPostDominator() const { return Base.isPostDominator(); }
iterator begin() { return Base.begin(); }
const_iterator begin() const { return Base.begin(); }
iterator end() { return Base.end(); }
const_iterator end() const { return Base.end(); }
iterator find(BasicBlock *B) { return Base.find(B); }
const_iterator find(BasicBlock *B) const { return Base.find(B); }
iterator addBasicBlock(BasicBlock *BB, const DomSetType &frontier) {
return Base.addBasicBlock(BB, frontier);
}
void removeBlock(BasicBlock *BB) { return Base.removeBlock(BB); }
void addToFrontier(iterator I, BasicBlock *Node) {
return Base.addToFrontier(I, Node);
}
void removeFromFrontier(iterator I, BasicBlock *Node) {
return Base.removeFromFrontier(I, Node);
}
bool compareDomSet(DomSetType &DS1, const DomSetType &DS2) const {
return Base.compareDomSet(DS1, DS2);
}
bool compare(DominanceFrontierBase<BasicBlock> &Other) const {
return Base.compare(Other);
}
void releaseMemory() override;
bool runOnFunction(Function &) override;
void getAnalysisUsage(AnalysisUsage &AU) const override;
void print(raw_ostream &OS, const Module * = nullptr) const override;
void dump() const;
};
EXTERN_TEMPLATE_INSTANTIATION(class DominanceFrontierBase<BasicBlock>);
EXTERN_TEMPLATE_INSTANTIATION(class ForwardDominanceFrontierBase<BasicBlock>);
}
#endif