martong updated this revision to Diff 469625. martong marked 8 inline comments as done. martong added a comment.
- Add comments - Assumption -> ConditionValue - Use CRTP - branchTransfer -> transferBranch - Make just one simple test case for transferBranch Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D133698/new/ https://reviews.llvm.org/D133698 Files: clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp clang/unittests/Analysis/FlowSensitive/CMakeLists.txt clang/unittests/Analysis/FlowSensitive/TestingSupport.h clang/unittests/Analysis/FlowSensitive/TransferBranchTest.cpp
Index: clang/unittests/Analysis/FlowSensitive/TransferBranchTest.cpp =================================================================== --- /dev/null +++ clang/unittests/Analysis/FlowSensitive/TransferBranchTest.cpp @@ -0,0 +1,129 @@ +//===- 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 simplistic version of Sign Analysis as an example +// of a forward, monotonic dataflow analysis. The analysis tracks all +// variables in the scope, but lacks escape analysis. +// +//===----------------------------------------------------------------------===// + +#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 { +namespace dataflow { +namespace { +using namespace ast_matchers; +using namespace test; + +struct TestLattice { + enum class Branch : int { True, False }; + llvm::Optional<Branch> TheBranch; + 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.TheBranch == Rhs.TheBranch; + } +}; + +class TestPropagationAnalysis + : public DataflowAnalysis<TestPropagationAnalysis, TestLattice> { +public: + explicit TestPropagationAnalysis(ASTContext &Context) + : DataflowAnalysis<TestPropagationAnalysis, TestLattice>(Context) {} + static TestLattice initialElement() { return TestLattice::bottom(); } + void transferBranch(bool Branch, const Stmt *S, TestLattice &L, + Environment &Env) { + L.TheBranch = + Branch ? TestLattice::Branch::True : TestLattice::Branch::False; + } +}; + +using ::testing::UnorderedElementsAre; + +MATCHER_P(Var, name, + (llvm::Twine(negation ? "isn't" : "is") + " a variable named `" + + name + "`") + .str()) { + assert(isa<VarDecl>(arg)); + return arg->getName() == name; +} + +template <typename Matcher> +void runDataflow(llvm::StringRef Code, Matcher Match, + LangStandard::Kind Std = LangStandard::lang_cxx17, + llvm::StringRef TargetFun = "fun") { + using ast_matchers::hasName; + ASSERT_THAT_ERROR( + checkDataflow<TestPropagationAnalysis>( + AnalysisInputs<TestPropagationAnalysis>( + Code, hasName(TargetFun), + [](ASTContext &C, Environment &) { + return TestPropagationAnalysis(C); + }) + .withASTBuildArgs( + {"-fsyntax-only", "-fno-delayed-template-parsing", + "-std=" + + std::string(LangStandard::getLangStandardForKind(Std) + .getName())}), + /*VerifyResults=*/ + [&Match](const llvm::StringMap<DataflowAnalysisState<TestLattice>> + &Results, + const AnalysisOutputs &AO) { Match(Results, AO.ASTCtx); }), + llvm::Succeeded()); +} + +template <typename LatticeT> +const LatticeT &getLatticeAtAnnotation( + const llvm::StringMap<DataflowAnalysisState<LatticeT>> &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<DataflowAnalysisState<TestLattice>> &Results, + ASTContext &ASTCtx) { + ASSERT_THAT(Results.keys(), UnorderedElementsAre("p", "q")); + + const TestLattice &LP = getLatticeAtAnnotation(Results, "p"); + EXPECT_TRUE(LP.TheBranch == TestLattice::Branch::True); + + const TestLattice &LQ = getLatticeAtAnnotation(Results, "q"); + EXPECT_TRUE(LQ.TheBranch == TestLattice::Branch::False); + }, + LangStandard::lang_cxx17); +} + +} // namespace +} // namespace dataflow +} // namespace clang Index: clang/unittests/Analysis/FlowSensitive/TestingSupport.h =================================================================== --- clang/unittests/Analysis/FlowSensitive/TestingSupport.h +++ clang/unittests/Analysis/FlowSensitive/TestingSupport.h @@ -344,6 +344,7 @@ llvm::any_cast<typename AnalysisT::Lattice>(&State.Lattice.Value); auto [_, InsertSuccess] = AnnotationStates.insert({It->second, StateT{*Lattice, State.Env}}); + (void)_; (void)InsertSuccess; assert(InsertSuccess); }; Index: clang/unittests/Analysis/FlowSensitive/CMakeLists.txt =================================================================== --- clang/unittests/Analysis/FlowSensitive/CMakeLists.txt +++ clang/unittests/Analysis/FlowSensitive/CMakeLists.txt @@ -12,12 +12,13 @@ MapLatticeTest.cpp MatchSwitchTest.cpp MultiVarConstantPropagationTest.cpp + TransferBranchTest.cpp SingleVarConstantPropagationTest.cpp + SolverTest.cpp TestingSupport.cpp TestingSupportTest.cpp TransferTest.cpp TypeErasedDataflowAnalysisTest.cpp - SolverTest.cpp UncheckedOptionalAccessModelTest.cpp ) Index: clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp =================================================================== --- clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp +++ clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp @@ -71,52 +71,58 @@ /// Extends the flow condition of an environment based on a terminator /// statement. -class TerminatorVisitor : public ConstStmtVisitor<TerminatorVisitor> { +class TerminatorVisitor + : public ConstStmtVisitor<TerminatorVisitor, + std::pair<const Expr *, bool>> { public: - TerminatorVisitor(const StmtToEnvMap &StmtToEnv, Environment &Env, + // The return type of the visit functions. + using RetTy = std::pair<const Expr *, bool>; + 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) { + RetTy VisitIfStmt(const IfStmt *S) { auto *Cond = S->getCond(); assert(Cond != nullptr); - extendFlowCondition(*Cond); + return extendFlowCondition(*Cond); } - void VisitWhileStmt(const WhileStmt *S) { + RetTy VisitWhileStmt(const WhileStmt *S) { auto *Cond = S->getCond(); assert(Cond != nullptr); - extendFlowCondition(*Cond); + return extendFlowCondition(*Cond); } - void VisitDoStmt(const DoStmt *S) { + RetTy VisitDoStmt(const DoStmt *S) { auto *Cond = S->getCond(); assert(Cond != nullptr); - extendFlowCondition(*Cond); + return extendFlowCondition(*Cond); } - void VisitForStmt(const ForStmt *S) { + RetTy VisitForStmt(const ForStmt *S) { auto *Cond = S->getCond(); if (Cond != nullptr) - extendFlowCondition(*Cond); + return extendFlowCondition(*Cond); + return {nullptr, false}; } - void VisitBinaryOperator(const BinaryOperator *S) { + RetTy 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) { + RetTy VisitConditionalOperator(const ConditionalOperator *S) { auto *Cond = S->getCond(); assert(Cond != nullptr); - extendFlowCondition(*Cond); + return extendFlowCondition(*Cond); } private: - void extendFlowCondition(const Expr &Cond) { + RetTy 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 +146,19 @@ 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 +250,16 @@ 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) + // TODO Call transferBranchTypeErased even if BuiltinTransferOpts are + // not set. + Analysis.transferBranchTypeErased(CondValue, Cond, PredState.Lattice, + PredState.Env); } } Index: clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h =================================================================== --- clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h +++ clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h @@ -84,6 +84,14 @@ 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. Index: clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h =================================================================== --- clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h +++ clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h @@ -44,6 +44,17 @@ std::declval<const InputT *>(), std::declval<LatticeT &>(), std::declval<Environment &>()))>> : std::true_type {}; +template <typename AnalysisT, typename LatticeT, typename = std::void_t<>> +struct HasTransferBranchFor : std::false_type {}; + +template <typename AnalysisT, typename LatticeT> +struct HasTransferBranchFor< + AnalysisT, LatticeT, + std::void_t<decltype(std::declval<AnalysisT>().transferBranch( + std::declval<bool>(), std::declval<const Stmt *>(), + std::declval<LatticeT &>(), std::declval<Environment &>()))>> + : std::true_type {}; + /// Base class template for dataflow analyses built on a single lattice type. /// /// Requirements: @@ -123,6 +134,17 @@ } } + void transferBranchTypeErased(bool Branch, const Stmt *Stmt, + TypeErasedLattice &E, Environment &Env) final { + if constexpr (HasTransferBranchFor<Derived, LatticeT>::value) { + Lattice &L = llvm::any_cast<Lattice &>(E.Value); + static_cast<Derived *>(this)->transferBranch(Branch, Stmt, L, Env); + } + // Silence unused parameter warnings. + (void)Branch; + (void)Stmt; + } + private: ASTContext &Context; };
_______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
