77 lines
2.6 KiB
C++
77 lines
2.6 KiB
C++
|
//===- CFGReachabilityAnalysis.cpp - Basic reachability analysis ----------===//
|
||
|
|
//
|
||
|
|
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
|
||
|
|
// See https://llvm.org/LICENSE.txt for license information.
|
||
|
|
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
|
||
|
|
//
|
||
|
|
//===----------------------------------------------------------------------===//
|
||
|
|
//
|
||
|
|
// This file defines a flow-sensitive, (mostly) path-insensitive reachability
|
||
|
|
// analysis based on Clang's CFGs. Clients can query if a given basic block
|
||
|
|
// is reachable within the CFG.
|
||
|
|
//
|
||
|
|
//===----------------------------------------------------------------------===//
|
||
|
|
|
||
|
|
#include "clang/Analysis/Analyses/CFGReachabilityAnalysis.h"
|
||
|
|
#include "clang/Analysis/CFG.h"
|
||
|
|
#include "llvm/ADT/BitVector.h"
|
||
|
|
#include "llvm/ADT/SmallVector.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 we haven't analyzed the destination node, run the analysis now
|
||
|
|
if (!analyzed[DstBlockID]) {
|
||
|
|
mapReachability(Dst);
|
||
|
|
analyzed[DstBlockID] = true;
|
||
|
|
}
|
||
|
|
|
||
|
|
// Return the cached result
|
||
|
|
return reachable[DstBlockID][Src->getBlockID()];
|
||
|
|
}
|
||
|
|
|
||
|
|
// Maps reachability to a common node by walking the predecessors of the
|
||
|
|
// destination node.
|
||
|
|
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);
|
||
|
|
|
||
|
|
// Start searching from the destination node, since we commonly will perform
|
||
|
|
// multiple queries relating to a destination node.
|
||
|
|
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;
|
||
|
|
|
||
|
|
// Update reachability information for this node -> Dst
|
||
|
|
if (!firstRun) {
|
||
|
|
// Don't insert Dst -> Dst unless it was a predecessor of itself
|
||
|
|
DstReachability[block->getBlockID()] = true;
|
||
|
|
}
|
||
|
|
else
|
||
|
|
firstRun = false;
|
||
|
|
|
||
|
|
// Add the predecessors to the worklist.
|
||
|
|
for (CFGBlock::const_pred_iterator i = block->pred_begin(),
|
||
|
|
e = block->pred_end(); i != e; ++i) {
|
||
|
|
if (*i)
|
||
|
|
worklist.push_back(*i);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|