#include "llvm/Analysis/Dominators.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Analysis/DominatorInternals.h"
#include "llvm/Assembly/Writer.h"
#include "llvm/Instructions.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Support/CommandLine.h"
#include <algorithm>
using namespace llvm;
#ifdef XDEBUG
static bool VerifyDomInfo = true;
#else
static bool VerifyDomInfo = false;
#endif
static cl::opt<bool,true>
VerifyDomInfoX("verify-dom-info", cl::location(VerifyDomInfo),
cl::desc("Verify dominator info (time consuming)"));
TEMPLATE_INSTANTIATION(class llvm::DomTreeNodeBase<BasicBlock>);
TEMPLATE_INSTANTIATION(class llvm::DominatorTreeBase<BasicBlock>);
char DominatorTree::ID = 0;
INITIALIZE_PASS(DominatorTree, "domtree",
"Dominator Tree Construction", true, true)
bool DominatorTree::runOnFunction(Function &F) {
DT->recalculate(F);
return false;
}
void DominatorTree::verifyAnalysis() const {
if (!VerifyDomInfo) return;
Function &F = *getRoot()->getParent();
DominatorTree OtherDT;
OtherDT.getBase().recalculate(F);
if (compare(OtherDT)) {
errs() << "DominatorTree is not up to date!\nComputed:\n";
print(errs());
errs() << "\nActual:\n";
OtherDT.print(errs());
abort();
}
}
void DominatorTree::print(raw_ostream &OS, const Module *) const {
DT->print(OS);
}
bool DominatorTree::dominates(const Instruction *Def,
const Instruction *User) const {
const BasicBlock *UseBB = User->getParent();
const BasicBlock *DefBB = Def->getParent();
assert(isReachableFromEntry(DefBB) && isReachableFromEntry(UseBB) &&
"We only handle reachable blocks");
if (Def == User)
return false;
if (isa<InvokeInst>(Def) || isa<PHINode>(User))
return dominates(Def, UseBB);
if (DefBB != UseBB)
return dominates(DefBB, UseBB);
BasicBlock::const_iterator I = DefBB->begin();
for (; &*I != Def && &*I != User; ++I)
;
return &*I == Def;
}
bool DominatorTree::dominates(const Instruction *Def,
const BasicBlock *UseBB) const {
const BasicBlock *DefBB = Def->getParent();
assert(isReachableFromEntry(DefBB) && isReachableFromEntry(UseBB) &&
"We only handle reachable blocks");
if (DefBB == UseBB)
return false;
const InvokeInst *II = dyn_cast<InvokeInst>(Def);
if (!II)
return dominates(DefBB, UseBB);
BasicBlock *NormalDest = II->getNormalDest();
if (!dominates(NormalDest, UseBB))
return false;
if (NormalDest->getSinglePredecessor())
return true;
for (pred_iterator PI = pred_begin(NormalDest),
E = pred_end(NormalDest); PI != E; ++PI) {
const BasicBlock *BB = *PI;
if (BB == DefBB)
continue;
if (!DT->isReachableFromEntry(BB))
continue;
if (!dominates(NormalDest, BB))
return false;
}
return true;
}