CFGReachabilityAnalysis.cpp [plain text]
#include "llvm/ADT/SmallVector.h"
#include "clang/Analysis/Analyses/CFGReachabilityAnalysis.h"
#include "clang/Analysis/CFG.h"
using namespace clang;
CFGReverseBlockReachabilityAnalysis::CFGReverseBlockReachabilityAnalysis(const CFG &cfg)
: analyzed(cfg.getNumBlockIDs(), false) {}
bool CFGReverseBlockReachabilityAnalysis::isReachable(const CFGBlock *Src,
const CFGBlock *Dst) {
const unsigned DstBlockID = Dst->getBlockID();
if (!analyzed[DstBlockID]) {
mapReachability(Dst);
analyzed[DstBlockID] = true;
}
return reachable[DstBlockID][Src->getBlockID()];
}
void CFGReverseBlockReachabilityAnalysis::mapReachability(const CFGBlock *Dst) {
SmallVector<const CFGBlock *, 11> worklist;
llvm::BitVector visited(analyzed.size());
ReachableSet &DstReachability = reachable[Dst->getBlockID()];
DstReachability.resize(analyzed.size(), false);
worklist.push_back(Dst);
bool firstRun = true;
while (!worklist.empty()) {
const CFGBlock *block = worklist.pop_back_val();
if (visited[block->getBlockID()])
continue;
visited[block->getBlockID()] = true;
if (!firstRun) {
DstReachability[block->getBlockID()] = true;
}
else
firstRun = false;
for (CFGBlock::const_pred_iterator i = block->pred_begin(),
e = block->pred_end(); i != e; ++i) {
if (*i)
worklist.push_back(*i);
}
}
}