diff options
| author | dim <dim@FreeBSD.org> | 2011-02-27 01:32:10 +0000 |
|---|---|---|
| committer | dim <dim@FreeBSD.org> | 2011-02-27 01:32:10 +0000 |
| commit | b951d621be1d00a520871c689c1cd687b6aa3ae6 (patch) | |
| tree | 5c342f2374324ffec4626f558d9aa49f323f90b4 /contrib/llvm/tools/clang/lib/Analysis/CFGReachabilityAnalysis.cpp | |
| parent | 4004d6a3076e94bd23e681411c43682267a202fe (diff) | |
| parent | a0fb00f9837bd0d2e5948f16f6a6b82a7a628f51 (diff) | |
| download | FreeBSD-src-b951d621be1d00a520871c689c1cd687b6aa3ae6.zip FreeBSD-src-b951d621be1d00a520871c689c1cd687b6aa3ae6.tar.gz | |
Update llvm/clang to trunk r126547.
There are several bugfixes in this update, but the most important one is
to ensure __start_ and __stop_ symbols for linker sets and kernel module
metadata are always emitted in object files:
http://llvm.org/bugs/show_bug.cgi?id=9292
Before this fix, if you compiled kernel modules with clang, they would
not be properly processed by kldxref, and if they had any dependencies,
the kernel would fail to load those. Another problem occurred when
attempting to mount a tmpfs filesystem, which would result in 'operation
not supported by device'.
Diffstat (limited to 'contrib/llvm/tools/clang/lib/Analysis/CFGReachabilityAnalysis.cpp')
| -rw-r--r-- | contrib/llvm/tools/clang/lib/Analysis/CFGReachabilityAnalysis.cpp | 76 |
1 files changed, 76 insertions, 0 deletions
diff --git a/contrib/llvm/tools/clang/lib/Analysis/CFGReachabilityAnalysis.cpp b/contrib/llvm/tools/clang/lib/Analysis/CFGReachabilityAnalysis.cpp new file mode 100644 index 0000000..7786584 --- /dev/null +++ b/contrib/llvm/tools/clang/lib/Analysis/CFGReachabilityAnalysis.cpp @@ -0,0 +1,76 @@ +//==- CFGReachabilityAnalysis.cpp - Basic reachability analysis --*- C++ -*-==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// 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 "llvm/ADT/SmallVector.h" +#include "clang/Analysis/Analyses/CFGReachabilityAnalysis.h" +#include "clang/Analysis/CFG.h" + +using namespace clang; + +CFGReachabilityAnalysis::CFGReachabilityAnalysis(const CFG &cfg) + : analyzed(cfg.getNumBlockIDs(), false) {} + +bool CFGReachabilityAnalysis::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 CFGReachabilityAnalysis::mapReachability(const CFGBlock *Dst) { + llvm::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.back(); + worklist.pop_back(); + + 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) { + worklist.push_back(*i); + } + } +} |
