sgatev updated this revision to Diff 389773. sgatev added a comment. Put typed and type-erased interfaces in separate files.
Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D114234/new/ https://reviews.llvm.org/D114234 Files: clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisDynamic.h clang/include/clang/Analysis/FlowSensitive/DataflowLattice.h clang/include/clang/Analysis/FlowSensitive/Environment.h clang/lib/Analysis/CMakeLists.txt clang/lib/Analysis/FlowSensitive/CMakeLists.txt clang/lib/Analysis/FlowSensitive/DataflowAnalysisDynamic.cpp
Index: clang/lib/Analysis/FlowSensitive/DataflowAnalysisDynamic.cpp =================================================================== --- /dev/null +++ clang/lib/Analysis/FlowSensitive/DataflowAnalysisDynamic.cpp @@ -0,0 +1,34 @@ +//===- DataflowAnalysisDynamic.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 type-erased base types and functions for building dataflow +// analyses that run over Control-Flow Graphs (CFGs). +// +//===----------------------------------------------------------------------===// + +#include <vector> + +#include "clang/Analysis/CFG.h" +#include "clang/Analysis/FlowSensitive/DataflowAnalysisDynamic.h" +#include "clang/Analysis/FlowSensitive/Environment.h" +#include "llvm/ADT/Optional.h" + +using namespace clang; +using namespace dataflow; + +std::vector<llvm::Optional<DataflowAnalysisStateDynamic>> +runDataflowAnalysisDynamic(const CFG &Cfg, DataflowAnalysisDynamic &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. + + // FIXME: Implement work list-based algorithm to compute the fixed + // point of `Analysis::transform` for every basic block in `Cfg`. + return {}; +} Index: clang/lib/Analysis/FlowSensitive/CMakeLists.txt =================================================================== --- /dev/null +++ clang/lib/Analysis/FlowSensitive/CMakeLists.txt @@ -0,0 +1,7 @@ +add_clang_library(clangAnalysisFlowSensitive + DataflowAnalysisDynamic.cpp + + LINK_LIBS + clangAnalysis + clangAST + ) Index: clang/lib/Analysis/CMakeLists.txt =================================================================== --- clang/lib/Analysis/CMakeLists.txt +++ clang/lib/Analysis/CMakeLists.txt @@ -44,3 +44,4 @@ ) add_subdirectory(plugins) +add_subdirectory(FlowSensitive) Index: clang/include/clang/Analysis/FlowSensitive/Environment.h =================================================================== --- /dev/null +++ clang/include/clang/Analysis/FlowSensitive/Environment.h @@ -0,0 +1,27 @@ +//===-- Environment.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 an Environment class that is used by dataflow analyses +// that run over Control-Flow Graphs (CFGs) to keep track of the state of the +// program at given program points. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_ENVIRONMENT_H +#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_ENVIRONMENT_H + +namespace clang { +namespace dataflow { + +/// Holds the state of the program (store and heap) at a given program point. +class Environment {}; + +} // namespace dataflow +} // namespace clang + +#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_ENVIRONMENT_H Index: clang/include/clang/Analysis/FlowSensitive/DataflowLattice.h =================================================================== --- /dev/null +++ clang/include/clang/Analysis/FlowSensitive/DataflowLattice.h @@ -0,0 +1,29 @@ +//===- DataflowLattice.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 base types for building lattices to be used in dataflow +// analyses that run over Control-Flow Graphs (CFGs). +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWLATTICE_H +#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWLATTICE_H + +namespace clang { +namespace dataflow { + +/// Effect indicating whether a lattice join operation resulted in a new value. +enum class LatticeJoinEffect { + Unchanged, + Changed, +}; + +} // namespace dataflow +} // namespace clang + +#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWLATTICE_H Index: clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisDynamic.h =================================================================== --- /dev/null +++ clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisDynamic.h @@ -0,0 +1,95 @@ +//===- DataflowAnalysisDynamic.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 type-erased base types and functions for building dataflow +// analyses that run over Control-Flow Graphs (CFGs). +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSISDYNAMIC_H +#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSISDYNAMIC_H + +#include <vector> + +#include "clang/AST/ASTContext.h" +#include "clang/AST/Stmt.h" +#include "clang/Analysis/CFG.h" +#include "clang/Analysis/FlowSensitive/DataflowLattice.h" +#include "clang/Analysis/FlowSensitive/Environment.h" +#include "llvm/ADT/Any.h" +#include "llvm/ADT/Optional.h" + +namespace clang { +namespace dataflow { + +/// Type-erased lattice element container. +/// +/// Requirements: +/// +/// The type of the object stored in the container must be a bounded +/// join-semilattice. +struct AnyLatticeElement { + llvm::Any Value; +}; + +/// Type-erased base class for dataflow analyses built on a single lattice type. +/// +/// The "Dynamic" suffix in the names of this class and its members emphasizes +/// their type-erased nature and differentiates them from the typed counterparts +/// in `DataflowAnalysis`. +class DataflowAnalysisDynamic { +public: + /// Returns the `ASTContext` that is used by the analysis. + virtual ASTContext &getASTContext() = 0; + + /// Returns a lattice element that models the initial state of a basic block. + virtual AnyLatticeElement initialElementDynamic() = 0; + + /// Joins two lattice elements by computing their least upper bound. Places + /// the join result in the left element and returns an effect indicating + /// whether any changes were made to it. + virtual LatticeJoinEffect joinDynamic(AnyLatticeElement &, + const AnyLatticeElement &) = 0; + + /// Returns true if and only if the two given lattice elements are equal. + virtual bool isEqualDynamic(const AnyLatticeElement &, + const AnyLatticeElement &) = 0; + + /// Applies the analysis transfer function for a given statement and lattice + /// element. + virtual AnyLatticeElement + transferDynamic(const Stmt *, const AnyLatticeElement &, Environment &) = 0; +}; + +/// Type-erased model of the program at a given program point. +/// +/// The "Dynamic" suffix in the name of this class emphasizes its type-erased +/// nature and differentiates it from the typed `DataflowAnalysisState`. +struct DataflowAnalysisStateDynamic { + /// Type-erased model of a program property. + AnyLatticeElement Lattice; + + /// Model of the state of the program (store and heap). + Environment Env; +}; + +/// Performs dataflow analysis and returns a mapping from basic block IDs to +/// type-erased dataflow analysis states that model the respective basic blocks. +/// +/// The "Dynamic" suffix in the name of this function emphasizes its type-erased +/// nature and differentiates it from the typed `runDataflowAnalysis`. +/// +/// Requirements are the same as those for `runDataflowAnalysis`. +std::vector<llvm::Optional<DataflowAnalysisStateDynamic>> +runDataflowAnalysisDynamic(const CFG &Cfg, DataflowAnalysisDynamic &Analysis, + const Environment &InitEnv); + +} // namespace dataflow +} // namespace clang + +#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSISDYNAMIC_H Index: clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h =================================================================== --- /dev/null +++ clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h @@ -0,0 +1,133 @@ +//===- DataflowAnalysis.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 base types and functions for building dataflow analyses +// that run over Control-Flow Graphs (CFGs). +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSIS_H +#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSIS_H + +#include <iterator> +#include <utility> +#include <vector> + +#include "clang/AST/ASTContext.h" +#include "clang/AST/Stmt.h" +#include "clang/Analysis/CFG.h" +#include "clang/Analysis/FlowSensitive/DataflowAnalysisDynamic.h" +#include "clang/Analysis/FlowSensitive/Environment.h" +#include "llvm/ADT/Any.h" +#include "llvm/ADT/Optional.h" +#include "llvm/ADT/STLExtras.h" + +namespace clang { +namespace dataflow { + +/// Base class template for dataflow analyses built on a single lattice type. +/// +/// Requirements: +/// +/// `Derived` must be derived from a specialization of this class template and +/// must provide the following public members: +/// * `LatticeT initialElement()` - returns a lattice element that models the +/// initial state of a basic block; +/// * `LatticeT transfer(const Stmt*, const LatticeT&, Environment&)` - +/// applies +/// the analysis transfer function for a given statement and lattice +/// element. +/// +/// `LatticeT` is a bounded join-semilattice that is used by `Derived` and must +/// provide the following public members: +/// * `LatticeJoinEffect join(const LatticeT&)` - joins the object and the +/// argument by computing their least upper bound, modifies the object if +/// necessary, and returns an effect indicating whether any changes were +/// made to it; +/// * `bool operator==(const LatticeT&) const` - returns true if and only if +/// the object is equal to the argument. +template <typename Derived, typename LatticeT> +class DataflowAnalysis : public DataflowAnalysisDynamic { +public: + /// Bounded join-semilattice that is used in the analysis. + using Lattice = LatticeT; + + explicit DataflowAnalysis(ASTContext &Context) : Context(Context) {} + + ASTContext &getASTContext() final { return Context; } + + AnyLatticeElement initialElementDynamic() final { + return {static_cast<Derived *>(this)->initialElement()}; + } + + LatticeJoinEffect joinDynamic(AnyLatticeElement &E1, + const AnyLatticeElement &E2) final { + Lattice &L1 = llvm::any_cast<Lattice &>(E1.Value); + const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value); + return L1.join(L2); + } + + bool isEqualDynamic(const AnyLatticeElement &E1, + const AnyLatticeElement &E2) final { + const Lattice &L1 = llvm::any_cast<const Lattice &>(E1.Value); + const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value); + return L1 == L2; + } + + AnyLatticeElement transferDynamic(const Stmt *Stmt, + const AnyLatticeElement &E, + Environment &Environment) final { + const Lattice &L = llvm::any_cast<const Lattice &>(E.Value); + return {static_cast<Derived *>(this)->transfer(Stmt, L, Environment)}; + } + +private: + ASTContext &Context; +}; + +// Model of the program at a given program point. +template <typename LatticeT> struct DataflowAnalysisState { + // Model of a program property. + LatticeT Lattice; + + // Model of the state of the program (store and heap). + Environment Env; +}; + +/// Performs dataflow analysis and returns a mapping from basic block IDs to +/// dataflow analysis states that model the respective basic blocks. +/// +/// Requirements: +/// +/// `Cfg` must have been built with `CFG::BuildOptions::setAllAlwaysAdd()` to +/// ensure that all sub-expressions in a basic block are evaluated. +template <typename AnalysisT> +std::vector<llvm::Optional<DataflowAnalysisState<typename AnalysisT::Lattice>>> +runDataflowAnalysis(const CFG &Cfg, AnalysisT &Analysis, + const Environment &InitEnv) { + auto DynamicBlockStates = runDataflowAnalysisDynamic(Cfg, Analysis, InitEnv); + std::vector< + llvm::Optional<DataflowAnalysisState<typename AnalysisT::Lattice>>> + BlockStates; + BlockStates.reserve(DynamicBlockStates.size()); + llvm::transform(std::move(DynamicBlockStates), + std::back_inserter(BlockStates), [](auto &OptState) { + return std::move(OptState).map([](auto &&State) { + return DataflowAnalysisState<typename AnalysisT::Lattice>{ + llvm::any_cast<typename AnalysisT::Lattice>( + std::move(State.Lattice.Value)), + std::move(State.Env)}; + }); + }); + return BlockStates; +} + +} // namespace dataflow +} // namespace clang + +#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSIS_H
_______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
