| //===- TypeErasedDataflowAnalysis.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_TYPEERASEDDATAFLOWANALYSIS_H |
| #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TYPEERASEDDATAFLOWANALYSIS_H |
| |
| #include <optional> |
| #include <utility> |
| #include <vector> |
| |
| #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/DataflowAnalysisContext.h" |
| #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h" |
| #include "clang/Analysis/FlowSensitive/DataflowLattice.h" |
| #include "llvm/ADT/Any.h" |
| #include "llvm/Support/Error.h" |
| |
| namespace clang { |
| namespace dataflow { |
| |
| struct DataflowAnalysisOptions { |
| /// Options for the built-in model, or empty to not apply them. |
| // FIXME: Remove this option once the framework supports composing analyses |
| // (at which point the built-in transfer functions can be simply a standalone |
| // analysis). |
| std::optional<DataflowAnalysisContext::Options> BuiltinOpts = |
| DataflowAnalysisContext::Options{}; |
| }; |
| |
| /// Type-erased lattice element container. |
| /// |
| /// Requirements: |
| /// |
| /// The type of the object stored in the container must be a bounded |
| /// join-semilattice. |
| struct TypeErasedLattice { |
| llvm::Any Value; |
| }; |
| |
| /// Type-erased base class for dataflow analyses built on a single lattice type. |
| class TypeErasedDataflowAnalysis : public Environment::ValueModel { |
| DataflowAnalysisOptions Options; |
| |
| public: |
| TypeErasedDataflowAnalysis() : Options({}) {} |
| |
| TypeErasedDataflowAnalysis(DataflowAnalysisOptions Options) |
| : Options(Options) {} |
| |
| virtual ~TypeErasedDataflowAnalysis() {} |
| |
| /// Returns the `ASTContext` that is used by the analysis. |
| virtual ASTContext &getASTContext() = 0; |
| |
| /// Returns a type-erased lattice element that models the initial state of a |
| /// basic block. |
| virtual TypeErasedLattice typeErasedInitialElement() = 0; |
| |
| /// Joins two type-erased 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 joinTypeErased(TypeErasedLattice &, |
| const TypeErasedLattice &) = 0; |
| |
| /// Chooses a lattice element that approximates the current element at a |
| /// program point, given the previous element at that point. Places the |
| /// widened result in the current element (`Current`). Widening is optional -- |
| /// it is only needed to either accelerate convergence (for lattices with |
| /// non-trivial height) or guarantee convergence (for lattices with infinite |
| /// height). |
| /// |
| /// Returns an indication of whether any changes were made to `Current` in |
| /// order to widen. This saves a separate call to `isEqualTypeErased` after |
| /// the widening. |
| virtual LatticeJoinEffect |
| widenTypeErased(TypeErasedLattice &Current, |
| const TypeErasedLattice &Previous) = 0; |
| |
| /// Returns true if and only if the two given type-erased lattice elements are |
| /// equal. |
| virtual bool isEqualTypeErased(const TypeErasedLattice &, |
| const TypeErasedLattice &) = 0; |
| |
| /// Applies the analysis transfer function for a given control flow graph |
| /// element and type-erased lattice element. |
| 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. |
| // FIXME: Change `Stmt` argument to a reference. |
| virtual void transferBranchTypeErased(bool Branch, const Stmt *, |
| TypeErasedLattice &, Environment &) = 0; |
| |
| /// If the built-in model is enabled, returns the options to be passed to |
| /// them. Otherwise returns empty. |
| const std::optional<DataflowAnalysisContext::Options> & |
| builtinOptions() const { |
| return Options.BuiltinOpts; |
| } |
| }; |
| |
| /// Type-erased model of the program at a given program point. |
| struct TypeErasedDataflowAnalysisState { |
| /// Type-erased model of a program property. |
| TypeErasedLattice Lattice; |
| |
| /// Model of the state of the program (store and heap). |
| Environment Env; |
| |
| TypeErasedDataflowAnalysisState(TypeErasedLattice Lattice, Environment Env) |
| : Lattice(std::move(Lattice)), Env(std::move(Env)) {} |
| }; |
| |
| /// Transfers the state of a basic block by evaluating each of its elements in |
| /// the context of `Analysis` and the states of its predecessors that are |
| /// available in `BlockStates`. `PostVisitCFG` (if provided) will be applied to |
| /// each element in the block, after it is evaluated. |
| /// |
| /// Requirements: |
| /// |
| /// All predecessors of `Block` except those with loop back edges must have |
| /// already been transferred. States in `BlockStates` that are set to |
| /// `std::nullopt` represent basic blocks that are not evaluated yet. |
| TypeErasedDataflowAnalysisState transferBlock( |
| const ControlFlowContext &CFCtx, |
| llvm::ArrayRef<std::optional<TypeErasedDataflowAnalysisState>> BlockStates, |
| const CFGBlock &Block, const Environment &InitEnv, |
| TypeErasedDataflowAnalysis &Analysis, |
| std::function<void(const CFGElement &, |
| const TypeErasedDataflowAnalysisState &)> |
| PostVisitCFG = nullptr); |
| |
| /// 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. Returns an error if the |
| /// dataflow analysis cannot be performed successfully. Otherwise, calls |
| /// `PostVisitCFG` on each CFG element with the final analysis results at that |
| /// program point. |
| llvm::Expected<std::vector<std::optional<TypeErasedDataflowAnalysisState>>> |
| runTypeErasedDataflowAnalysis( |
| const ControlFlowContext &CFCtx, TypeErasedDataflowAnalysis &Analysis, |
| const Environment &InitEnv, |
| std::function<void(const CFGElement &, |
| const TypeErasedDataflowAnalysisState &)> |
| PostVisitCFG = nullptr); |
| |
| } // namespace dataflow |
| } // namespace clang |
| |
| #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TYPEERASEDDATAFLOWANALYSIS_H |