From bb72d0dde29edc2f240ab3d3650544251795ef9f Mon Sep 17 00:00:00 2001 From: Gabor Marton Date: Mon, 12 Sep 2022 15:44:53 +0200 Subject: [PATCH] [clang][dataflow] Implement transferBranch This patch introduces `transferBranch`, which Applies the analysis transfer function for a given edge from a CFG block of a conditional statement. RFC: https://discourse.llvm.org/t/rfc-clang-dataflow-signanalysis-edgetransfer-branchtransfer/65220 Differential Revision: https://reviews.llvm.org/D133698 --- .../Analysis/FlowSensitive/DataflowAnalysis.h | 21 ++++ .../FlowSensitive/TypeErasedDataflowAnalysis.h | 8 ++ .../FlowSensitive/TypeErasedDataflowAnalysis.cpp | 65 ++++++++---- .../Analysis/FlowSensitive/CMakeLists.txt | 1 + .../Analysis/FlowSensitive/TestingSupport.h | 1 + .../Analysis/FlowSensitive/TransferBranchTest.cpp | 114 +++++++++++++++++++++ 6 files changed, 188 insertions(+), 22 deletions(-) create mode 100644 clang/unittests/Analysis/FlowSensitive/TransferBranchTest.cpp diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h b/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h index 6184f22..5284430 100644 --- a/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h +++ b/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h @@ -32,6 +32,16 @@ namespace clang { namespace dataflow { +template > +struct HasTransferBranchFor : std::false_type {}; + +template +struct HasTransferBranchFor< + AnalysisT, LatticeT, + std::void_t().transferBranch( + std::declval(), std::declval(), + std::declval(), std::declval()))>> + : std::true_type {}; /// Base class template for dataflow analyses built on a single lattice type. /// /// Requirements: @@ -101,6 +111,17 @@ public: static_cast(this)->transfer(Element, L, Env); } + void transferBranchTypeErased(bool Branch, const Stmt *Stmt, + TypeErasedLattice &E, Environment &Env) final { + if constexpr (HasTransferBranchFor::value) { + Lattice &L = llvm::any_cast(E.Value); + static_cast(this)->transferBranch(Branch, Stmt, L, Env); + } + // Silence unused parameter warnings. + (void)Branch; + (void)Stmt; + } + private: ASTContext &Context; }; diff --git a/clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h b/clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h index c7dccc3..fe8b431 100644 --- a/clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h +++ b/clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h @@ -84,6 +84,14 @@ public: virtual void transferTypeErased(const CFGElement *, TypeErasedLattice &, Environment &) = 0; + /// Applies the analysis transfer function for a given edge from a CFG block + /// of a conditional statement. + /// @param Stmt The condition which is responsible for the split in the CFG. + /// @param Branch True if the edge goes to the basic block where the + /// condition is true. + virtual void transferBranchTypeErased(bool Branch, const Stmt *, + TypeErasedLattice &, Environment &) = 0; + /// If the built-in transfer functions (which model the heap and stack in the /// `Environment`) are to be applied, returns the options to be passed to /// them. Otherwise returns empty. diff --git a/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp b/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp index b85a72a..ec6a8a3 100644 --- a/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp +++ b/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp @@ -69,54 +69,64 @@ static int blockIndexInPredecessor(const CFGBlock &Pred, return BlockPos - Pred.succ_begin(); } +// The return type of the visit functions in TerminatorVisitor. The first +// element represents the terminator expression (that is the conditional +// expression in case of a path split in the CFG). The second element +// represents whether the condition was true or false. +using TerminatorVisitorRetTy = std::pair; + /// Extends the flow condition of an environment based on a terminator /// statement. -class TerminatorVisitor : public ConstStmtVisitor { +class TerminatorVisitor + : public ConstStmtVisitor { public: - TerminatorVisitor(const StmtToEnvMap &StmtToEnv, Environment &Env, + TerminatorVisitor(TypeErasedDataflowAnalysis &Analysis, + const StmtToEnvMap &StmtToEnv, Environment &Env, int BlockSuccIdx, TransferOptions TransferOpts) - : StmtToEnv(StmtToEnv), Env(Env), BlockSuccIdx(BlockSuccIdx), - TransferOpts(TransferOpts) {} + : Analysis(Analysis), StmtToEnv(StmtToEnv), Env(Env), + BlockSuccIdx(BlockSuccIdx), TransferOpts(TransferOpts) {} - void VisitIfStmt(const IfStmt *S) { + TerminatorVisitorRetTy VisitIfStmt(const IfStmt *S) { auto *Cond = S->getCond(); assert(Cond != nullptr); - extendFlowCondition(*Cond); + return extendFlowCondition(*Cond); } - void VisitWhileStmt(const WhileStmt *S) { + TerminatorVisitorRetTy VisitWhileStmt(const WhileStmt *S) { auto *Cond = S->getCond(); assert(Cond != nullptr); - extendFlowCondition(*Cond); + return extendFlowCondition(*Cond); } - void VisitDoStmt(const DoStmt *S) { + TerminatorVisitorRetTy VisitDoStmt(const DoStmt *S) { auto *Cond = S->getCond(); assert(Cond != nullptr); - extendFlowCondition(*Cond); + return extendFlowCondition(*Cond); } - void VisitForStmt(const ForStmt *S) { + TerminatorVisitorRetTy VisitForStmt(const ForStmt *S) { auto *Cond = S->getCond(); if (Cond != nullptr) - extendFlowCondition(*Cond); + return extendFlowCondition(*Cond); + return {nullptr, false}; } - void VisitBinaryOperator(const BinaryOperator *S) { + TerminatorVisitorRetTy VisitBinaryOperator(const BinaryOperator *S) { assert(S->getOpcode() == BO_LAnd || S->getOpcode() == BO_LOr); auto *LHS = S->getLHS(); assert(LHS != nullptr); - extendFlowCondition(*LHS); + return extendFlowCondition(*LHS); } - void VisitConditionalOperator(const ConditionalOperator *S) { + TerminatorVisitorRetTy + VisitConditionalOperator(const ConditionalOperator *S) { auto *Cond = S->getCond(); assert(Cond != nullptr); - extendFlowCondition(*Cond); + return extendFlowCondition(*Cond); } private: - void extendFlowCondition(const Expr &Cond) { + TerminatorVisitorRetTy extendFlowCondition(const Expr &Cond) { // The terminator sub-expression might not be evaluated. if (Env.getStorageLocation(Cond, SkipPast::None) == nullptr) transfer(StmtToEnv, Cond, Env, TransferOpts); @@ -140,14 +150,19 @@ private: Env.setValue(*Loc, *Val); } + bool ConditionValue = true; // The condition must be inverted for the successor that encompasses the // "else" branch, if such exists. - if (BlockSuccIdx == 1) + if (BlockSuccIdx == 1) { Val = &Env.makeNot(*Val); + ConditionValue = false; + } Env.addToFlowCondition(*Val); + return {&Cond, ConditionValue}; } + TypeErasedDataflowAnalysis &Analysis; const StmtToEnvMap &StmtToEnv; Environment &Env; int BlockSuccIdx; @@ -239,10 +254,16 @@ computeBlockInputState(const CFGBlock &Block, AnalysisContext &AC) { if (BuiltinTransferOpts) { if (const Stmt *PredTerminatorStmt = Pred->getTerminatorStmt()) { const StmtToEnvMapImpl StmtToEnv(AC.CFCtx, AC.BlockStates); - TerminatorVisitor(StmtToEnv, PredState.Env, - blockIndexInPredecessor(*Pred, Block), - *BuiltinTransferOpts) - .Visit(PredTerminatorStmt); + auto [Cond, CondValue] = + TerminatorVisitor(Analysis, StmtToEnv, PredState.Env, + blockIndexInPredecessor(*Pred, Block), + *BuiltinTransferOpts) + .Visit(PredTerminatorStmt); + if (Cond != nullptr) + // FIXME: Call transferBranchTypeErased even if BuiltinTransferOpts + // are not set. + Analysis.transferBranchTypeErased(CondValue, Cond, PredState.Lattice, + PredState.Env); } } diff --git a/clang/unittests/Analysis/FlowSensitive/CMakeLists.txt b/clang/unittests/Analysis/FlowSensitive/CMakeLists.txt index 434d71c..a5ad105 100644 --- a/clang/unittests/Analysis/FlowSensitive/CMakeLists.txt +++ b/clang/unittests/Analysis/FlowSensitive/CMakeLists.txt @@ -17,6 +17,7 @@ add_clang_unittest(ClangAnalysisFlowSensitiveTests SolverTest.cpp TestingSupport.cpp TestingSupportTest.cpp + TransferBranchTest.cpp TransferTest.cpp TypeErasedDataflowAnalysisTest.cpp UncheckedOptionalAccessModelTest.cpp diff --git a/clang/unittests/Analysis/FlowSensitive/TestingSupport.h b/clang/unittests/Analysis/FlowSensitive/TestingSupport.h index bc5a2bf..511ff71 100644 --- a/clang/unittests/Analysis/FlowSensitive/TestingSupport.h +++ b/clang/unittests/Analysis/FlowSensitive/TestingSupport.h @@ -344,6 +344,7 @@ checkDataflow(AnalysisInputs AI, llvm::any_cast(&State.Lattice.Value); auto [_, InsertSuccess] = AnnotationStates.insert({It->second, StateT{*Lattice, State.Env}}); + (void)_; (void)InsertSuccess; assert(InsertSuccess); }; diff --git a/clang/unittests/Analysis/FlowSensitive/TransferBranchTest.cpp b/clang/unittests/Analysis/FlowSensitive/TransferBranchTest.cpp new file mode 100644 index 0000000..df179dd --- /dev/null +++ b/clang/unittests/Analysis/FlowSensitive/TransferBranchTest.cpp @@ -0,0 +1,114 @@ +//===- unittests/Analysis/FlowSensitive/SignAnalysisTest.cpp --===// +// +// 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 test for the transferBranch function of the +// TypeErasedDataflowAnalysis. +// +//===----------------------------------------------------------------------===// + +#include "TestingSupport.h" +#include "clang/Analysis/FlowSensitive/DataflowAnalysis.h" +#include "clang/Tooling/Tooling.h" +#include "llvm/ADT/Optional.h" +#include "llvm/Support/Error.h" +#include "llvm/Testing/Support/Annotations.h" +#include "llvm/Testing/Support/Error.h" +#include "gtest/gtest.h" + +namespace clang::dataflow::test { +namespace { + +using namespace ast_matchers; + +struct TestLattice { + llvm::Optional Branch; + static TestLattice bottom() { return {}; } + + // Does not matter for this test, but we must provide some definition of join. + LatticeJoinEffect join(const TestLattice &Other) { + return LatticeJoinEffect::Unchanged; + } + friend bool operator==(const TestLattice &Lhs, const TestLattice &Rhs) { + return Lhs.Branch == Rhs.Branch; + } +}; + +class TestPropagationAnalysis + : public DataflowAnalysis { +public: + explicit TestPropagationAnalysis(ASTContext &Context) + : DataflowAnalysis(Context) {} + static TestLattice initialElement() { return TestLattice::bottom(); } + void transfer(const CFGElement *, TestLattice &, Environment &) {} + void transferBranch(bool Branch, const Stmt *S, TestLattice &L, + Environment &Env) { + L.Branch = Branch; + } +}; + +using ::testing::UnorderedElementsAre; + +template +void runDataflow(llvm::StringRef Code, Matcher VerifyResults, + LangStandard::Kind Std = LangStandard::lang_cxx17, + llvm::StringRef TargetFun = "fun") { + using ast_matchers::hasName; + ASSERT_THAT_ERROR( + checkDataflow( + AnalysisInputs( + Code, hasName(TargetFun), + [](ASTContext &C, Environment &) { + return TestPropagationAnalysis(C); + }) + .withASTBuildArgs( + {"-fsyntax-only", "-fno-delayed-template-parsing", + "-std=" + + std::string(LangStandard::getLangStandardForKind(Std) + .getName())}), + VerifyResults), + llvm::Succeeded()); +} + +template +const LatticeT &getLatticeAtAnnotation( + const llvm::StringMap> &AnnotationStates, + llvm::StringRef Annotation) { + auto It = AnnotationStates.find(Annotation); + assert(It != AnnotationStates.end()); + return It->getValue().Lattice; +} + +TEST(TransferBranchTest, IfElse) { + std::string Code = R"( + void fun(int a) { + if (a > 0) { + (void)1; + // [[p]] + } else { + (void)0; + // [[q]] + } + } + )"; + runDataflow( + Code, + [](const llvm::StringMap> &Results, + const AnalysisOutputs &) { + ASSERT_THAT(Results.keys(), UnorderedElementsAre("p", "q")); + + const TestLattice &LP = getLatticeAtAnnotation(Results, "p"); + EXPECT_THAT(LP.Branch, Optional(true)); + + const TestLattice &LQ = getLatticeAtAnnotation(Results, "q"); + EXPECT_THAT(LQ.Branch, Optional(false)); + }, + LangStandard::lang_cxx17); +} + +} // namespace +} // namespace clang::dataflow::test -- 2.7.4