//===- Dominators.cpp - Dominator Calculation -----------------------------===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements simple dominator construction algorithms for finding
// forward dominators. Postdominators are available in libanalysis, but are not
// included in libvmcore, because it's not needed. Forward dominators are
// needed to support the Verifier pass.
//
//===----------------------------------------------------------------------===//
#include "llvm/IR/Dominators.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Instructions.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/GenericDomTreeConstruction.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
using namespace llvm;
// Always verify dominfo if expensive checking is enabled.
#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)"));
bool BasicBlockEdge::isSingleEdge() const {
const TerminatorInst *TI = Start->getTerminator();
unsigned NumEdgesToEnd = 0;
for (unsigned int i = 0, n = TI->getNumSuccessors(); i < n; ++i) {
if (TI->getSuccessor(i) == End)
++NumEdgesToEnd;
if (NumEdgesToEnd >= 2)
return false;
}
assert(NumEdgesToEnd == 1);
return true;
}
//===----------------------------------------------------------------------===//
// DominatorTree Implementation
//===----------------------------------------------------------------------===//
//
// Provide public access to DominatorTree information. Implementation details
// can be found in Dominators.h, GenericDomTree.h, and
// GenericDomTreeConstruction.h.
//
//===----------------------------------------------------------------------===//
TEMPLATE_INSTANTIATION(class llvm::DomTreeNodeBase<BasicBlock>);
TEMPLATE_INSTANTIATION(class llvm::DominatorTreeBase<BasicBlock>);
#define LLVM_COMMA ,
TEMPLATE_INSTANTIATION(void llvm::Calculate<Function LLVM_COMMA BasicBlock *>(
DominatorTreeBase<GraphTraits<BasicBlock *>::NodeType> &DT LLVM_COMMA
Function &F));
TEMPLATE_INSTANTIATION(
void llvm::Calculate<Function LLVM_COMMA Inverse<BasicBlock *> >(
DominatorTreeBase<GraphTraits<Inverse<BasicBlock *> >::NodeType> &DT
LLVM_COMMA Function &F));
#undef LLVM_COMMA
// 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 DominatorTree::dominates(const Instruction *Def,
const Instruction *User) const {
const BasicBlock *UseBB = User->getParent();
const BasicBlock *DefBB = Def->getParent();
// Any unreachable use is dominated, even if Def == User.
if (!isReachableFromEntry(UseBB))
return true;
// Unreachable definitions don't dominate anything.
if (!isReachableFromEntry(DefBB))
return false;
// An instruction doesn't dominate a use in itself.
if (Def == User)
return false;
// The value defined by an invoke dominates an instruction only if
// it dominates every instruction in UseBB.
// A PHI is dominated only if the instruction dominates every possible use
// in the UseBB.
if (isa<InvokeInst>(Def) || isa<PHINode>(User))
return dominates(Def, UseBB);
if (DefBB != UseBB)
return dominates(DefBB, UseBB);
// Loop through the basic block until we find Def or User.
BasicBlock::const_iterator I = DefBB->begin();
for (; &*I != Def && &*I != User; ++I)
/*empty*/;
return &*I == Def;
}
// true if Def would dominate a use in any instruction in UseBB.
// note that dominates(Def, Def->getParent()) is false.
bool DominatorTree::dominates(const Instruction *Def,
const BasicBlock *UseBB) const {
const BasicBlock *DefBB = Def->getParent();
// Any unreachable use is dominated, even if DefBB == UseBB.
if (!isReachableFromEntry(UseBB))
return true;
// Unreachable definitions don't dominate anything.
if (!isReachableFromEntry(DefBB))
return false;
if (DefBB == UseBB)
return false;
const InvokeInst *II = dyn_cast<InvokeInst>(Def);
if (!II)
return dominates(DefBB, UseBB);
// Invoke results are only usable in the normal destination, not in the
// exceptional destination.
BasicBlock *NormalDest = II->getNormalDest();
BasicBlockEdge E(DefBB, NormalDest);
return dominates(E, UseBB);
}
bool DominatorTree::dominates(const BasicBlockEdge &BBE,
const BasicBlock *UseBB) const {
// Assert that we have a single edge. We could handle them by simply
// returning false, but since isSingleEdge is linear on the number of
// edges, the callers can normally handle them more efficiently.
assert(BBE.isSingleEdge());
// If the BB the edge ends in doesn't dominate the use BB, then the
// edge also doesn't.
const BasicBlock *Start = BBE.getStart();
const BasicBlock *End = BBE.getEnd();
if (!dominates(End, UseBB))
return false;
// Simple case: if the end BB has a single predecessor, the fact that it
// dominates the use block implies that the edge also does.
if (End->getSinglePredecessor())
return true;
// The normal edge from the invoke is critical. Conceptually, what we would
// like to do is split it and check if the new block dominates the use.
// With X being the new block, the graph would look like:
//
// DefBB
// /\ . .
// / \ . .
// / \ . .
// / \ | |
// A X B C
// | \ | /
// . \|/
// . NormalDest
// .
//
// Given the definition of dominance, NormalDest is dominated by X iff X
// dominates all of NormalDest's predecessors (X, B, C in the example). X
// trivially dominates itself, so we only have to find if it dominates the
// other predecessors. Since the only way out of X is via NormalDest, X can
// only properly dominate a node if NormalDest dominates that node too.
for (const_pred_iterator PI = pred_begin(End), E = pred_end(End);
PI != E; ++PI) {
const BasicBlock *BB = *PI;
if (BB == Start)
continue;
if (!dominates(End, BB))
return false;
}
return true;
}
bool DominatorTree::dominates(const BasicBlockEdge &BBE, const Use &U) const {
// Assert that we have a single edge. We could handle them by simply
// returning false, but since isSingleEdge is linear on the number of
// edges, the callers can normally handle them more efficiently.
assert(BBE.isSingleEdge());
Instruction *UserInst = cast<Instruction>(U.getUser());
// A PHI in the end of the edge is dominated by it.
PHINode *PN = dyn_cast<PHINode>(UserInst);
if (PN && PN->getParent() == BBE.getEnd() &&
PN->getIncomingBlock(U) == BBE.getStart())
return true;
// Otherwise use the edge-dominates-block query, which
// handles the crazy critical edge cases properly.
const BasicBlock *UseBB;
if (PN)
UseBB = PN->getIncomingBlock(U);
else
UseBB = UserInst->getParent();
return dominates(BBE, UseBB);
}
bool DominatorTree::dominates(const Instruction *Def, const Use &U) const {
Instruction *UserInst = cast<Instruction>(U.getUser());
const BasicBlock *DefBB = Def->getParent();
// Determine the block in which the use happens. PHI nodes use
// their operands on edges; simulate this by thinking of the use
// hap
