Author: Yitzhak Mandelbaum Date: 2022-08-03T15:17:49Z New Revision: 692e03039d1ee57c06c0cfae68b91bc5bfd99f6e
URL: https://github.com/llvm/llvm-project/commit/692e03039d1ee57c06c0cfae68b91bc5bfd99f6e DIFF: https://github.com/llvm/llvm-project/commit/692e03039d1ee57c06c0cfae68b91bc5bfd99f6e.diff LOG: [clang][dataflow] Add cache of `ControlFlowContext`s for function decls. This patch modifies context-sensitive analysis of functions to use a cache, rather than recreate the `ControlFlowContext` from a function decl on each encounter. However, this is just step 1 (of N) in adding support for a configurable map of "modeled" function decls (see issue #56879). The map will go from the actual function decl to the `ControlFlowContext` used to model it. Only functions pre-configured in the map will be modeled in a context-sensitive way. We start with a cache because it introduces the desired map, while retaining the current behavior. Here, functions are mapped to their actual implementations (when available). Differential Revision: https://reviews.llvm.org/D131039 Added: Modified: clang/include/clang/Analysis/FlowSensitive/ControlFlowContext.h clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h clang/lib/Analysis/FlowSensitive/ControlFlowContext.cpp clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp clang/lib/Analysis/FlowSensitive/Transfer.cpp Removed: ################################################################################ diff --git a/clang/include/clang/Analysis/FlowSensitive/ControlFlowContext.h b/clang/include/clang/Analysis/FlowSensitive/ControlFlowContext.h index e6ceb3a89131..58e901fac004 100644 --- a/clang/include/clang/Analysis/FlowSensitive/ControlFlowContext.h +++ b/clang/include/clang/Analysis/FlowSensitive/ControlFlowContext.h @@ -30,10 +30,19 @@ namespace dataflow { /// analysis. class ControlFlowContext { public: - /// Builds a ControlFlowContext from an AST node. + /// Builds a ControlFlowContext from an AST node. `D` is the function in which + /// `S` resides and must not be null. + static llvm::Expected<ControlFlowContext> build(const Decl *D, Stmt &S, + ASTContext &C); + + // DEPRECATED. Use overload above. static llvm::Expected<ControlFlowContext> build(const Decl *D, Stmt *S, ASTContext *C); + /// Returns the `Decl` containing the statement used to construct the CFG, if + /// available. + const Decl *getDecl() const { return ContainingDecl; } + /// Returns the CFG that is stored in this context. const CFG &getCFG() const { return *Cfg; } @@ -43,10 +52,15 @@ class ControlFlowContext { } private: - ControlFlowContext(std::unique_ptr<CFG> Cfg, + // FIXME: Once the deprecated `build` method is removed, mark `D` as "must not + // be null" and add an assertion. + ControlFlowContext(const Decl *D, std::unique_ptr<CFG> Cfg, llvm::DenseMap<const Stmt *, const CFGBlock *> StmtToBlock) - : Cfg(std::move(Cfg)), StmtToBlock(std::move(StmtToBlock)) {} + : ContainingDecl(D), Cfg(std::move(Cfg)), + StmtToBlock(std::move(StmtToBlock)) {} + /// The `Decl` containing the statement used to construct the CFG. + const Decl *ContainingDecl; std::unique_ptr<CFG> Cfg; llvm::DenseMap<const Stmt *, const CFGBlock *> StmtToBlock; }; diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h b/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h index c7903fd7ee89..99e16f825544 100644 --- a/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h +++ b/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h @@ -20,7 +20,6 @@ #include "clang/AST/ASTContext.h" #include "clang/AST/Stmt.h" -#include "clang/Analysis/CFG.h" #include "clang/Analysis/FlowSensitive/ControlFlowContext.h" #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h" #include "clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h" diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h b/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h index 6a9a35ac0baf..a31e08fd16c4 100644 --- a/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h +++ b/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h @@ -18,6 +18,7 @@ #include "clang/AST/Decl.h" #include "clang/AST/Expr.h" #include "clang/AST/TypeOrdering.h" +#include "clang/Analysis/FlowSensitive/ControlFlowContext.h" #include "clang/Analysis/FlowSensitive/Solver.h" #include "clang/Analysis/FlowSensitive/StorageLocation.h" #include "clang/Analysis/FlowSensitive/Value.h" @@ -254,6 +255,10 @@ class DataflowAnalysisContext { LLVM_DUMP_METHOD void dumpFlowCondition(AtomicBoolValue &Token); + /// Returns the `ControlFlowContext` registered for `F`, if any. Otherwise, + /// returns null. + const ControlFlowContext *getControlFlowContext(const FunctionDecl *F); + private: struct NullableQualTypeDenseMapInfo : private llvm::DenseMapInfo<QualType> { static QualType getEmptyKey() { @@ -360,6 +365,8 @@ class DataflowAnalysisContext { llvm::DenseMap<AtomicBoolValue *, llvm::DenseSet<AtomicBoolValue *>> FlowConditionDeps; llvm::DenseMap<AtomicBoolValue *, BoolValue *> FlowConditionConstraints; + + llvm::DenseMap<const FunctionDecl *, ControlFlowContext> FunctionContexts; }; } // namespace dataflow diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h index 9ba73d9224a6..1ecac86125a7 100644 --- a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h +++ b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h @@ -19,6 +19,7 @@ #include "clang/AST/DeclBase.h" #include "clang/AST/Expr.h" #include "clang/AST/Type.h" +#include "clang/Analysis/FlowSensitive/ControlFlowContext.h" #include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h" #include "clang/Analysis/FlowSensitive/DataflowLattice.h" #include "clang/Analysis/FlowSensitive/StorageLocation.h" @@ -343,6 +344,12 @@ class Environment { /// imply that `Val` is true. bool flowConditionImplies(BoolValue &Val) const; + /// Returns the `ControlFlowContext` registered for `F`, if any. Otherwise, + /// returns null. + const ControlFlowContext *getControlFlowContext(const FunctionDecl *F) { + return DACtx->getControlFlowContext(F); + } + LLVM_DUMP_METHOD void dump() const; private: diff --git a/clang/lib/Analysis/FlowSensitive/ControlFlowContext.cpp b/clang/lib/Analysis/FlowSensitive/ControlFlowContext.cpp index 58708b5b5efb..b112059693e8 100644 --- a/clang/lib/Analysis/FlowSensitive/ControlFlowContext.cpp +++ b/clang/lib/Analysis/FlowSensitive/ControlFlowContext.cpp @@ -45,7 +45,7 @@ buildStmtToBasicBlockMap(const CFG &Cfg) { } llvm::Expected<ControlFlowContext> -ControlFlowContext::build(const Decl *D, Stmt *S, ASTContext *C) { +ControlFlowContext::build(const Decl *D, Stmt &S, ASTContext &C) { CFG::BuildOptions Options; Options.PruneTriviallyFalseEdges = false; Options.AddImplicitDtors = true; @@ -56,7 +56,7 @@ ControlFlowContext::build(const Decl *D, Stmt *S, ASTContext *C) { // Ensure that all sub-expressions in basic blocks are evaluated. Options.setAllAlwaysAdd(); - auto Cfg = CFG::buildCFG(D, S, C, Options); + auto Cfg = CFG::buildCFG(D, &S, &C, Options); if (Cfg == nullptr) return llvm::createStringError( std::make_error_code(std::errc::invalid_argument), @@ -64,7 +64,14 @@ ControlFlowContext::build(const Decl *D, Stmt *S, ASTContext *C) { llvm::DenseMap<const Stmt *, const CFGBlock *> StmtToBlock = buildStmtToBasicBlockMap(*Cfg); - return ControlFlowContext(std::move(Cfg), std::move(StmtToBlock)); + return ControlFlowContext(D, std::move(Cfg), std::move(StmtToBlock)); +} + +llvm::Expected<ControlFlowContext> +ControlFlowContext::build(const Decl *D, Stmt *S, ASTContext *C) { + assert(S != nullptr); + assert(C != nullptr); + return build(D, *S, *C); } } // namespace dataflow diff --git a/clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp b/clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp index fa70e5fd9f9a..af2f1fcbe24e 100644 --- a/clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp +++ b/clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp @@ -334,6 +334,27 @@ void DataflowAnalysisContext::dumpFlowCondition(AtomicBoolValue &Token) { llvm::dbgs() << debugString(Constraints, AtomNames); } +const ControlFlowContext * +DataflowAnalysisContext::getControlFlowContext(const FunctionDecl *F) { + // Canonicalize the key: + F = F->getDefinition(); + if (F == nullptr) + return nullptr; + auto It = FunctionContexts.find(F); + if (It != FunctionContexts.end()) + return &It->second; + + if (Stmt *Body = F->getBody()) { + auto CFCtx = ControlFlowContext::build(F, *Body, F->getASTContext()); + // FIXME: Handle errors. + assert(CFCtx); + auto Result = FunctionContexts.insert({F, std::move(*CFCtx)}); + return &Result.first->second; + } + + return nullptr; +} + } // namespace dataflow } // namespace clang diff --git a/clang/lib/Analysis/FlowSensitive/Transfer.cpp b/clang/lib/Analysis/FlowSensitive/Transfer.cpp index 06053e50c7ae..8b2e79826e81 100644 --- a/clang/lib/Analysis/FlowSensitive/Transfer.cpp +++ b/clang/lib/Analysis/FlowSensitive/Transfer.cpp @@ -507,28 +507,30 @@ class TransferVisitor : public ConstStmtVisitor<TransferVisitor> { return; Env.setStorageLocation(*S, *ArgLoc); } else if (const FunctionDecl *F = S->getDirectCallee()) { - // This case is for context-sensitive analysis, which we only do if we - // have the callee body available in the translation unit. - if (!Options.ContextSensitive || F->getBody() == nullptr) + // This case is for context-sensitive analysis. + if (!Options.ContextSensitive) + return; + + const ControlFlowContext *CFCtx = Env.getControlFlowContext(F); + if (!CFCtx) return; // FIXME: We don't support context-sensitive analysis of recursion, so // we should return early here if `F` is the same as the `FunctionDecl` // holding `S` itself. - auto &ASTCtx = F->getASTContext(); - - // FIXME: Cache these CFGs. - auto CFCtx = ControlFlowContext::build(F, F->getBody(), &ASTCtx); - // FIXME: Handle errors here and below. - assert(CFCtx); auto ExitBlock = CFCtx->getCFG().getExit().getBlockID(); auto CalleeEnv = Env.pushCall(S); - // FIXME: Use the same analysis as the caller for the callee. - DataflowAnalysisOptions Options; - auto Analysis = NoopAnalysis(ASTCtx, Options); + // FIXME: Use the same analysis as the caller for the callee. Note, + // though, that doing so would require support for changing the analysis's + // ASTContext. + assert( + CFCtx->getDecl() != nullptr && + "ControlFlowContexts in the environment should always carry a decl"); + auto Analysis = NoopAnalysis(CFCtx->getDecl()->getASTContext(), + DataflowAnalysisOptions()); auto BlockToOutputState = dataflow::runDataflowAnalysis(*CFCtx, Analysis, CalleeEnv); _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
