summaryrefslogtreecommitdiffstats
path: root/lib/Analysis
diff options
context:
space:
mode:
Diffstat (limited to 'lib/Analysis')
-rw-r--r--lib/Analysis/AnalysisContext.cpp28
-rw-r--r--lib/Analysis/CFG.cpp53
-rw-r--r--lib/Analysis/CFGReachabilityAnalysis.cpp76
-rw-r--r--lib/Analysis/CMakeLists.txt1
4 files changed, 138 insertions, 20 deletions
diff --git a/lib/Analysis/AnalysisContext.cpp b/lib/Analysis/AnalysisContext.cpp
index 5233d3b..62097ef 100644
--- a/lib/Analysis/AnalysisContext.cpp
+++ b/lib/Analysis/AnalysisContext.cpp
@@ -19,8 +19,10 @@
#include "clang/AST/StmtVisitor.h"
#include "clang/Analysis/Analyses/LiveVariables.h"
#include "clang/Analysis/Analyses/PseudoConstantAnalysis.h"
+#include "clang/Analysis/Analyses/CFGReachabilityAnalysis.h"
#include "clang/Analysis/AnalysisContext.h"
#include "clang/Analysis/CFG.h"
+#include "clang/Analysis/CFGStmtMap.h"
#include "clang/Analysis/Support/BumpVector.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/Support/ErrorHandling.h"
@@ -86,6 +88,30 @@ CFG *AnalysisContext::getUnoptimizedCFG() {
return completeCFG;
}
+CFGStmtMap *AnalysisContext::getCFGStmtMap() {
+ if (cfgStmtMap)
+ return cfgStmtMap;
+
+ if (CFG *c = getCFG()) {
+ cfgStmtMap = CFGStmtMap::Build(c, &getParentMap());
+ return cfgStmtMap;
+ }
+
+ return 0;
+}
+
+CFGReachabilityAnalysis *AnalysisContext::getCFGReachablityAnalysis() {
+ if (CFA)
+ return CFA;
+
+ if (CFG *c = getCFG()) {
+ CFA = new CFGReachabilityAnalysis(*c);
+ return CFA;
+ }
+
+ return 0;
+}
+
void AnalysisContext::dumpCFG() {
getCFG()->dump(getASTContext().getLangOptions());
}
@@ -346,10 +372,12 @@ AnalysisContext::getReferencedBlockVars(const BlockDecl *BD) {
AnalysisContext::~AnalysisContext() {
delete cfg;
delete completeCFG;
+ delete cfgStmtMap;
delete liveness;
delete relaxedLiveness;
delete PM;
delete PCA;
+ delete CFA;
delete ReferencedBlockVars;
}
diff --git a/lib/Analysis/CFG.cpp b/lib/Analysis/CFG.cpp
index a0ec5fe..cc6e9c5 100644
--- a/lib/Analysis/CFG.cpp
+++ b/lib/Analysis/CFG.cpp
@@ -17,6 +17,7 @@
#include "clang/AST/DeclCXX.h"
#include "clang/AST/StmtVisitor.h"
#include "clang/AST/PrettyPrinter.h"
+#include "clang/AST/CharUnits.h"
#include "llvm/Support/GraphWriter.h"
#include "llvm/Support/Allocator.h"
#include "llvm/Support/Format.h"
@@ -413,9 +414,16 @@ private:
Expr::EvalResult Result;
if (!S->isTypeDependent() && !S->isValueDependent() &&
- S->Evaluate(Result, *Context) && Result.Val.isInt())
- return Result.Val.getInt().getBoolValue();
-
+ S->Evaluate(Result, *Context)) {
+ if (Result.Val.isInt())
+ return Result.Val.getInt().getBoolValue();
+ if (Result.Val.isLValue()) {
+ Expr *e = Result.Val.getLValueBase();
+ const CharUnits &c = Result.Val.getLValueOffset();
+ if (!e && c.isZero())
+ return false;
+ }
+ }
return TryResult();
}
};
@@ -928,11 +936,13 @@ CFGBlock *CFGBuilder::VisitStmt(Stmt *S, AddStmtChoice asc) {
/// VisitChildren - Visit the children of a Stmt.
CFGBlock *CFGBuilder::VisitChildren(Stmt* Terminator) {
- CFGBlock *B = Block;
- for (Stmt::child_range I = Terminator->children(); I; ++I) {
- if (*I) B = Visit(*I);
- }
- return B;
+ CFGBlock *lastBlock = Block;
+ for (Stmt::child_range I = Terminator->children(); I; ++I)
+ if (Stmt *child = *I)
+ if (CFGBlock *b = Visit(child))
+ lastBlock = b;
+
+ return lastBlock;
}
CFGBlock *CFGBuilder::VisitAddrLabelExpr(AddrLabelExpr *A,
@@ -1207,6 +1217,8 @@ CFGBlock *CFGBuilder::VisitConditionalOperator(AbstractConditionalOperator *C,
return 0;
Block = NULL;
}
+ else
+ LHSBlock = ConfluenceBlock;
// Create the block for the RHS expression.
Succ = ConfluenceBlock;
@@ -1219,23 +1231,23 @@ CFGBlock *CFGBuilder::VisitConditionalOperator(AbstractConditionalOperator *C,
// See if this is a known constant.
const TryResult& KnownVal = tryEvaluateBool(C->getCond());
- if (LHSBlock)
- addSuccessor(Block, KnownVal.isFalse() ? NULL : LHSBlock);
+ addSuccessor(Block, KnownVal.isFalse() ? NULL : LHSBlock);
addSuccessor(Block, KnownVal.isTrue() ? NULL : RHSBlock);
Block->setTerminator(C);
Expr *condExpr = C->getCond();
- CFGBlock *result = 0;
-
- // Run the condition expression if it's not trivially expressed in
- // terms of the opaque value (or if there is no opaque value).
- if (condExpr != opaqueValue) result = addStmt(condExpr);
-
- // Before that, run the common subexpression if there was one.
- // At least one of this or the above will be run.
- if (opaqueValue) result = addStmt(BCO->getCommon());
+ if (opaqueValue) {
+ // Run the condition expression if it's not trivially expressed in
+ // terms of the opaque value (or if there is no opaque value).
+ if (condExpr != opaqueValue)
+ addStmt(condExpr);
- return result;
+ // Before that, run the common subexpression if there was one.
+ // At least one of this or the above will be run.
+ return addStmt(BCO->getCommon());
+ }
+
+ return addStmt(condExpr);
}
CFGBlock *CFGBuilder::VisitDeclStmt(DeclStmt *DS) {
@@ -1819,6 +1831,7 @@ CFGBlock* CFGBuilder::VisitWhileStmt(WhileStmt* W) {
if (badCFG)
return 0;
LoopSuccessor = Block;
+ Block = 0;
} else
LoopSuccessor = Succ;
diff --git a/lib/Analysis/CFGReachabilityAnalysis.cpp b/lib/Analysis/CFGReachabilityAnalysis.cpp
new file mode 100644
index 0000000..7786584
--- /dev/null
+++ b/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);
+ }
+ }
+}
diff --git a/lib/Analysis/CMakeLists.txt b/lib/Analysis/CMakeLists.txt
index 0912f3c..84b211f 100644
--- a/lib/Analysis/CMakeLists.txt
+++ b/lib/Analysis/CMakeLists.txt
@@ -3,6 +3,7 @@ set(LLVM_USED_LIBS clangBasic clangAST clangIndex)
add_clang_library(clangAnalysis
AnalysisContext.cpp
CFG.cpp
+ CFGReachabilityAnalysis.cpp
CFGStmtMap.cpp
CocoaConventions.cpp
FormatString.cpp
OpenPOWER on IntegriCloud