diff --git a/clang/include/clang/Analysis/FlowSensitive/ControlFlowContext.h b/clang/include/clang/Analysis/FlowSensitive/ControlFlowContext.h new file mode 100644 --- /dev/null +++ b/clang/include/clang/Analysis/FlowSensitive/ControlFlowContext.h @@ -0,0 +1,57 @@ +//===-- ControlFlowContext.h ------------------------------------*- C++ -*-===// +// +// 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 ControlFlowContext class that is used by dataflow +// analyses that run over Control-Flow Graphs (CFGs). +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_CONTROLFLOWCONTEXT_H +#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_CONTROLFLOWCONTEXT_H + +#include "clang/AST/ASTContext.h" +#include "clang/AST/Decl.h" +#include "clang/AST/Stmt.h" +#include "clang/Analysis/CFG.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/Support/Error.h" +#include + +namespace clang { +namespace dataflow { + +/// Holds CFG and other derived context that is needed to perform dataflow +/// analysis. +class ControlFlowContext { +public: + /// Builds a ControlFlowContext from an AST node. + static llvm::Expected build(const Decl *D, Stmt *S, + ASTContext *C); + + /// Returns the CFG that is stored in this context. + const CFG &getCFG() const { return *Cfg; } + + /// Returns the mapping from statements to basic blocks that is stored in this + /// context. + const llvm::DenseMap &getStmtToBlock() const { + return StmtToBlock; + } + +private: + ControlFlowContext(std::unique_ptr Cfg, + llvm::DenseMap StmtToBlock) + : Cfg(std::move(Cfg)), StmtToBlock(std::move(StmtToBlock)) {} + + std::unique_ptr Cfg; + llvm::DenseMap StmtToBlock; +}; + +} // namespace dataflow +} // namespace clang + +#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_CONTROLFLOWCONTEXT_H diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h b/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h --- a/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h +++ b/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h @@ -21,6 +21,7 @@ #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" #include "llvm/ADT/Any.h" @@ -101,17 +102,12 @@ /// Performs dataflow analysis and returns a mapping from basic block IDs to /// dataflow analysis states that model the respective basic blocks. Indices /// of the returned vector correspond to basic block IDs. -/// -/// Requirements: -/// -/// `Cfg` must have been built with `CFG::BuildOptions::setAllAlwaysAdd()` to -/// ensure that all sub-expressions in a basic block are evaluated. template std::vector>> -runDataflowAnalysis(const CFG &Cfg, AnalysisT &Analysis, +runDataflowAnalysis(const ControlFlowContext &Ctx, AnalysisT &Analysis, const Environment &InitEnv) { auto TypeErasedBlockStates = - runTypeErasedDataflowAnalysis(Cfg, Analysis, InitEnv); + runTypeErasedDataflowAnalysis(Ctx, Analysis, InitEnv); std::vector< llvm::Optional>> BlockStates; diff --git a/clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h b/clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h --- a/clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h +++ b/clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h @@ -19,6 +19,7 @@ #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/DataflowLattice.h" #include "llvm/ADT/Any.h" @@ -87,6 +88,7 @@ /// already been transferred. States in `BlockStates` that are set to /// `llvm::None` represent basic blocks that are not evaluated yet. TypeErasedDataflowAnalysisState transferBlock( + const ControlFlowContext &Ctx, std::vector> &BlockStates, const CFGBlock &Block, const Environment &InitEnv, TypeErasedDataflowAnalysis &Analysis, @@ -97,13 +99,8 @@ /// Performs dataflow analysis and returns a mapping from basic block IDs to /// dataflow analysis states that model the respective basic blocks. Indices /// of the returned vector correspond to basic block IDs. -/// -/// Requirements: -/// -/// `Cfg` must have been built with `CFG::BuildOptions::setAllAlwaysAdd()` to -/// ensure that all sub-expressions in a basic block are evaluated. std::vector> -runTypeErasedDataflowAnalysis(const CFG &Cfg, +runTypeErasedDataflowAnalysis(const ControlFlowContext &Ctx, TypeErasedDataflowAnalysis &Analysis, const Environment &InitEnv); diff --git a/clang/lib/Analysis/FlowSensitive/CMakeLists.txt b/clang/lib/Analysis/FlowSensitive/CMakeLists.txt --- a/clang/lib/Analysis/FlowSensitive/CMakeLists.txt +++ b/clang/lib/Analysis/FlowSensitive/CMakeLists.txt @@ -1,4 +1,5 @@ add_clang_library(clangAnalysisFlowSensitive + ControlFlowContext.cpp TypeErasedDataflowAnalysis.cpp LINK_LIBS diff --git a/clang/lib/Analysis/FlowSensitive/ControlFlowContext.cpp b/clang/lib/Analysis/FlowSensitive/ControlFlowContext.cpp new file mode 100644 --- /dev/null +++ b/clang/lib/Analysis/FlowSensitive/ControlFlowContext.cpp @@ -0,0 +1,59 @@ +#include "clang/Analysis/FlowSensitive/ControlFlowContext.h" +#include "clang/AST/ASTContext.h" +#include "clang/AST/Decl.h" +#include "clang/AST/Stmt.h" +#include "clang/Analysis/CFG.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/Support/Error.h" +#include + +namespace clang { +namespace dataflow { +namespace { + +/// Returns a map from statements to basic blocks that contain them. +llvm::DenseMap +buildStmtToBasicBlockMap(const CFG &Cfg) { + llvm::DenseMap StmtToBlock; + for (const CFGBlock *Block : Cfg) { + if (Block == nullptr) + continue; + + for (const CFGElement &Element : *Block) { + auto Stmt = Element.getAs(); + if (!Stmt.hasValue()) + continue; + + StmtToBlock[Stmt.getValue().getStmt()] = Block; + } + } + return StmtToBlock; +} + +} // namespace + +llvm::Expected +ControlFlowContext::build(const Decl *D, Stmt *S, ASTContext *C) { + CFG::BuildOptions Options; + Options.PruneTriviallyFalseEdges = false; + Options.AddImplicitDtors = true; + Options.AddTemporaryDtors = true; + Options.AddInitializers = true; + + // `Cfg` must be built with `CFG::BuildOptions::setAllAlwaysAdd()` to + // ensure that all sub-expressions in a basic block are evaluated. + Options.setAllAlwaysAdd(); + + auto Cfg = CFG::buildCFG(D, S, C, Options); + if (Cfg == nullptr) + return llvm::createStringError( + std::make_error_code(std::errc::invalid_argument), + "CFG::buildCFG failed"); + + llvm::DenseMap StmtToBlock = + buildStmtToBasicBlockMap(*Cfg); + return ControlFlowContext(std::move(Cfg), std::move(StmtToBlock)); +} + +} // namespace dataflow +} // namespace clang diff --git a/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp b/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp --- a/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp +++ b/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp @@ -35,6 +35,7 @@ /// already been transferred. States in `BlockStates` that are set to /// `llvm::None` represent basic blocks that are not evaluated yet. static TypeErasedDataflowAnalysisState computeBlockInputState( + const ControlFlowContext &Ctx, std::vector> &BlockStates, const CFGBlock &Block, const Environment &InitEnv, TypeErasedDataflowAnalysis &Analysis) { @@ -43,7 +44,23 @@ // the state of each basic block differently. TypeErasedDataflowAnalysisState State = {Analysis.typeErasedInitialElement(), InitEnv}; - for (const CFGBlock *Pred : Block.preds()) { + + llvm::DenseSet Preds; + Preds.insert(Block.pred_begin(), Block.pred_end()); + if (Block.getTerminator().isTemporaryDtorsBranch()) { + // The first successor of a block with a temporary destructor terminator is + // the block that evaluates the destructor. If that block has a noreturn + // element then the predecessor block that constructed the temporary object + // is effectively a noreturn block and its state should not be used as + // input. + if (Block.succ_begin()->getReachableBlock()->hasNoReturnElement()) { + auto StmtBlock = Ctx.getStmtToBlock().find(Block.getTerminatorStmt()); + assert(StmtBlock != Ctx.getStmtToBlock().end()); + Preds.erase(StmtBlock->getSecond()); + } + } + + for (const CFGBlock *Pred : Preds) { // Skip if the `Block` is unreachable or control flow cannot get past it. if (!Pred || Pred->hasNoReturnElement()) continue; @@ -64,6 +81,7 @@ } TypeErasedDataflowAnalysisState transferBlock( + const ControlFlowContext &Ctx, std::vector> &BlockStates, const CFGBlock &Block, const Environment &InitEnv, TypeErasedDataflowAnalysis &Analysis, @@ -71,7 +89,7 @@ const TypeErasedDataflowAnalysisState &)> HandleTransferredStmt) { TypeErasedDataflowAnalysisState State = - computeBlockInputState(BlockStates, Block, InitEnv, Analysis); + computeBlockInputState(Ctx, BlockStates, Block, InitEnv, Analysis); for (const CFGElement &Element : Block) { // FIXME: Evaluate other kinds of `CFGElement`. const llvm::Optional Stmt = Element.getAs(); @@ -89,21 +107,21 @@ } std::vector> -runTypeErasedDataflowAnalysis(const CFG &Cfg, +runTypeErasedDataflowAnalysis(const ControlFlowContext &Ctx, TypeErasedDataflowAnalysis &Analysis, const Environment &InitEnv) { // FIXME: Consider enforcing that `Cfg` meets the requirements that // are specified in the header. This could be done by remembering // what options were used to build `Cfg` and asserting on them here. - PostOrderCFGView POV(&Cfg); - ForwardDataflowWorklist Worklist(Cfg, &POV); + PostOrderCFGView POV(&Ctx.getCFG()); + ForwardDataflowWorklist Worklist(Ctx.getCFG(), &POV); std::vector> BlockStates; - BlockStates.resize(Cfg.size(), llvm::None); + BlockStates.resize(Ctx.getCFG().size(), llvm::None); // The entry basic block doesn't contain statements so it can be skipped. - const CFGBlock &Entry = Cfg.getEntry(); + const CFGBlock &Entry = Ctx.getCFG().getEntry(); BlockStates[Entry.getBlockID()] = {Analysis.typeErasedInitialElement(), InitEnv}; Worklist.enqueueSuccessors(&Entry); @@ -125,7 +143,7 @@ const llvm::Optional &OldBlockState = BlockStates[Block->getBlockID()]; TypeErasedDataflowAnalysisState NewBlockState = - transferBlock(BlockStates, *Block, InitEnv, Analysis); + transferBlock(Ctx, BlockStates, *Block, InitEnv, Analysis); if (OldBlockState.hasValue() && Analysis.isEqualTypeErased(OldBlockState.getValue().Lattice, diff --git a/clang/unittests/Analysis/FlowSensitive/TestingSupport.h b/clang/unittests/Analysis/FlowSensitive/TestingSupport.h --- a/clang/unittests/Analysis/FlowSensitive/TestingSupport.h +++ b/clang/unittests/Analysis/FlowSensitive/TestingSupport.h @@ -20,6 +20,7 @@ #include "clang/ASTMatchers/ASTMatchers.h" #include "clang/ASTMatchers/ASTMatchersInternal.h" #include "clang/Analysis/CFG.h" +#include "clang/Analysis/FlowSensitive/ControlFlowContext.h" #include "clang/Analysis/FlowSensitive/DataflowAnalysis.h" #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h" #include "clang/Basic/LLVM.h" @@ -56,12 +57,6 @@ buildStatementToAnnotationMapping(const FunctionDecl *Func, llvm::Annotations AnnotatedCode); -// Creates a CFG from the body of the function that matches `func_matcher`, -// suitable to testing a dataflow analysis. -std::pair> -buildCFG(ASTContext &Context, - ast_matchers::internal::Matcher FuncMatcher); - // Runs dataflow on the body of the function that matches `func_matcher` in code // snippet `code`. Requires: `Analysis` contains a type `Lattice`. template @@ -87,12 +82,16 @@ "the test log"; } - std::pair> CFGResult = - buildCFG(Context, FuncMatcher); - const auto *F = CFGResult.first; - auto Cfg = std::move(CFGResult.second); - ASSERT_TRUE(F != nullptr) << "Could not find target function"; - ASSERT_TRUE(Cfg != nullptr) << "Could not build control flow graph."; + const FunctionDecl *F = ast_matchers::selectFirst( + "target", + ast_matchers::match( + ast_matchers::functionDecl(ast_matchers::isDefinition(), FuncMatcher) + .bind("target"), + Context)); + ASSERT_TRUE(F != nullptr) << "Could not find target function."; + + auto Ctx = ControlFlowContext::build(F, F->getBody(), &F->getASTContext()); + ASSERT_TRUE((bool)Ctx) << "Could not build ControlFlowContext."; Environment Env; auto Analysis = MakeAnalysis(Context, Env); @@ -107,7 +106,7 @@ auto &Annotations = *StmtToAnnotations; std::vector> BlockStates = - runTypeErasedDataflowAnalysis(*Cfg, Analysis, Env); + runTypeErasedDataflowAnalysis(*Ctx, Analysis, Env); if (BlockStates.empty()) { Expectations({}, Context); @@ -117,13 +116,13 @@ // Compute a map from statement annotations to the state computed for // the program point immediately after the annotated statement. std::vector> Results; - for (const CFGBlock *Block : *Cfg) { + for (const CFGBlock *Block : Ctx->getCFG()) { // Skip blocks that were not evaluated. if (!BlockStates[Block->getBlockID()].hasValue()) continue; transferBlock( - BlockStates, *Block, Env, Analysis, + *Ctx, BlockStates, *Block, Env, Analysis, [&Results, &Annotations](const clang::CFGStmt &Stmt, const TypeErasedDataflowAnalysisState &State) { auto It = Annotations.find(Stmt.getStmt()); diff --git a/clang/unittests/Analysis/FlowSensitive/TestingSupport.cpp b/clang/unittests/Analysis/FlowSensitive/TestingSupport.cpp --- a/clang/unittests/Analysis/FlowSensitive/TestingSupport.cpp +++ b/clang/unittests/Analysis/FlowSensitive/TestingSupport.cpp @@ -144,26 +144,3 @@ return Result; } - -std::pair> -test::buildCFG(ASTContext &Context, - ast_matchers::internal::Matcher FuncMatcher) { - CFG::BuildOptions Options; - Options.PruneTriviallyFalseEdges = false; - Options.AddInitializers = true; - Options.AddImplicitDtors = true; - Options.AddTemporaryDtors = true; - Options.setAllAlwaysAdd(); - - const FunctionDecl *F = ast_matchers::selectFirst( - "target", - ast_matchers::match( - ast_matchers::functionDecl(ast_matchers::isDefinition(), FuncMatcher) - .bind("target"), - Context)); - if (F == nullptr) - return std::make_pair(nullptr, nullptr); - - return std::make_pair( - F, clang::CFG::buildCFG(F, F->getBody(), &Context, Options)); -} diff --git a/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp b/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp --- a/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp +++ b/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp @@ -6,6 +6,7 @@ // //===----------------------------------------------------------------------===// +#include "TestingSupport.h" #include "clang/AST/Decl.h" #include "clang/ASTMatchers/ASTMatchFinder.h" #include "clang/ASTMatchers/ASTMatchers.h" @@ -14,15 +15,21 @@ #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h" #include "clang/Analysis/FlowSensitive/DataflowLattice.h" #include "clang/Tooling/Tooling.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SmallSet.h" #include "llvm/ADT/StringRef.h" #include "gmock/gmock.h" #include "gtest/gtest.h" #include #include +#include +#include #include using namespace clang; using namespace dataflow; +using ::testing::Pair; +using ::testing::UnorderedElementsAre; template class AnalysisCallback : public ast_matchers::MatchFinder::MatchCallback { @@ -36,21 +43,12 @@ Stmt *Body = Func->getBody(); assert(Body != nullptr); - // FIXME: Consider providing a utility that returns a `CFG::BuildOptions` - // which is a good default for most clients or a utility that directly - // builds the `CFG` using default `CFG::BuildOptions`. - CFG::BuildOptions Options; - Options.AddImplicitDtors = true; - Options.AddTemporaryDtors = true; - Options.setAllAlwaysAdd(); - - std::unique_ptr Cfg = - CFG::buildCFG(nullptr, Body, Result.Context, Options); - assert(Cfg != nullptr); + auto Ctx = ControlFlowContext::build(nullptr, Body, Result.Context); + assert(Ctx); AnalysisT Analysis(*Result.Context); Environment Env; - BlockStates = runDataflowAnalysis(*Cfg, Analysis, Env); + BlockStates = runDataflowAnalysis(*Ctx, Analysis, Env); } std::vector< @@ -141,8 +139,123 @@ } )"); EXPECT_EQ(BlockStates.size(), 4u); - EXPECT_FALSE(BlockStates[0].hasValue()); + EXPECT_TRUE(BlockStates[0].hasValue()); EXPECT_TRUE(BlockStates[1].hasValue()); EXPECT_TRUE(BlockStates[2].hasValue()); EXPECT_TRUE(BlockStates[3].hasValue()); } + +struct FunctionCallLattice { + llvm::SmallSet CalledFunctions; + + bool operator==(const FunctionCallLattice &Other) const { + return CalledFunctions == Other.CalledFunctions; + } + + LatticeJoinEffect join(const FunctionCallLattice &Other) { + if (Other.CalledFunctions.empty()) + return LatticeJoinEffect::Unchanged; + const size_t size_before = CalledFunctions.size(); + CalledFunctions.insert(Other.CalledFunctions.begin(), + Other.CalledFunctions.end()); + return CalledFunctions.size() == size_before ? LatticeJoinEffect::Unchanged + : LatticeJoinEffect::Changed; + } +}; + +std::ostream &operator<<(std::ostream &OS, const FunctionCallLattice &L) { + std::string result; + llvm::raw_string_ostream ROS(result); + llvm::interleaveComma(L.CalledFunctions, ROS); + return OS << "{" << result << "}"; +} + +class FunctionCallAnalysis + : public DataflowAnalysis { +public: + explicit FunctionCallAnalysis(ASTContext &Context) + : DataflowAnalysis(Context) {} + + static FunctionCallLattice initialElement() { return {}; } + + FunctionCallLattice transfer(const Stmt *S, const FunctionCallLattice &E, + Environment &Env) { + FunctionCallLattice R = E; + if (auto *C = dyn_cast(S)) { + if (auto *F = dyn_cast(C->getCalleeDecl())) { + R.CalledFunctions.insert(F->getNameInfo().getAsString()); + } + } + return R; + } +}; + +class FunctionCallTest : public ::testing::Test { +protected: + template + void RunDataflow(llvm::StringRef Code, Matcher Expectations) { + test::checkDataflow( + Code, "target", + [](ASTContext &C, Environment &) { return FunctionCallAnalysis(C); }, + [&Expectations]( + llvm::ArrayRef>> + Results, + ASTContext &) { EXPECT_THAT(Results, Expectations); }, + {"-fsyntax-only", "-std=c++17"}); + } +}; + +MATCHER_P(HoldsFunctionCallLattice, m, + ((negation ? "doesn't hold" : "holds") + + llvm::StringRef(" a lattice element that ") + + ::testing::DescribeMatcher(m, negation)) + .str()) { + return ExplainMatchResult(m, arg.Lattice, result_listener); +} + +MATCHER_P(HasCalledFunctions, m, "") { + return ExplainMatchResult(m, arg.CalledFunctions, result_listener); +} + +TEST_F(FunctionCallTest, VirtualDestructor) { + std::string Code = R"( + int foo(); + + class NonFatal { + public: + ~NonFatal(); + int bar(); + }; + + void target(bool b) { + int value = b ? foo() : NonFatal().bar(); + (void)0; + // [[p]] + } + )"; + RunDataflow(Code, UnorderedElementsAre( + Pair("p", HoldsFunctionCallLattice(HasCalledFunctions( + UnorderedElementsAre("foo", "bar")))))); +} + +TEST_F(FunctionCallTest, VirtualDestructorNoReturn) { + std::string Code = R"( + int foo(); + + class Fatal { + public: + ~Fatal() __attribute__((noreturn)); + int bar(); + }; + + void target(bool b) { + int value = b ? foo() : Fatal().bar(); + (void)0; + // [[p]] + } + )"; + RunDataflow(Code, UnorderedElementsAre( + Pair("p", HoldsFunctionCallLattice(HasCalledFunctions( + UnorderedElementsAre("foo")))))); +}