contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h

   1 //===- TypeErasedDataflowAnalysis.h -----------------------------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 //  This file defines type-erased base types and functions for building dataflow
  10 //  analyses that run over Control-Flow Graphs (CFGs).
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TYPEERASEDDATAFLOWANALYSIS_H
  15 #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TYPEERASEDDATAFLOWANALYSIS_H
  16
  17 #include <utility>
  18 #include <vector>
  19
  20 #include "clang/AST/ASTContext.h"
  21 #include "clang/AST/Stmt.h"
  22 #include "clang/Analysis/CFG.h"
  23 #include "clang/Analysis/FlowSensitive/ControlFlowContext.h"
  24 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
  25 #include "clang/Analysis/FlowSensitive/DataflowLattice.h"
  26 #include "llvm/ADT/Any.h"
  27 #include "llvm/ADT/Optional.h"
  28 #include "llvm/Support/Error.h"
  29
  30 namespace clang {
  31 namespace dataflow {
  32
  33 /// Type-erased lattice element container.
  34 ///
  35 /// Requirements:
  36 ///
  37 ///  The type of the object stored in the container must be a bounded
  38 ///  join-semilattice.
  39 struct TypeErasedLattice {
  40   llvm::Any Value;
  41 };
  42
  43 /// Type-erased base class for dataflow analyses built on a single lattice type.
  44 class TypeErasedDataflowAnalysis : public Environment::ValueModel {
  45   /// Determines whether to apply the built-in transfer functions.
  46   // FIXME: Remove this option once the framework supports composing analyses
  47   // (at which point the built-in transfer functions can be simply a standalone
  48   // analysis).
  49   bool ApplyBuiltinTransfer;
  50
  51 public:
  52   TypeErasedDataflowAnalysis() : ApplyBuiltinTransfer(true) {}
  53   TypeErasedDataflowAnalysis(bool ApplyBuiltinTransfer)
  54       : ApplyBuiltinTransfer(ApplyBuiltinTransfer) {}
  55
  56   virtual ~TypeErasedDataflowAnalysis() {}
  57
  58   /// Returns the `ASTContext` that is used by the analysis.
  59   virtual ASTContext &getASTContext() = 0;
  60
  61   /// Returns a type-erased lattice element that models the initial state of a
  62   /// basic block.
  63   virtual TypeErasedLattice typeErasedInitialElement() = 0;
  64
  65   /// Joins two type-erased lattice elements by computing their least upper
  66   /// bound. Places the join result in the left element and returns an effect
  67   /// indicating whether any changes were made to it.
  68   virtual LatticeJoinEffect joinTypeErased(TypeErasedLattice &,
  69                                            const TypeErasedLattice &) = 0;
  70
  71   /// Returns true if and only if the two given type-erased lattice elements are
  72   /// equal.
  73   virtual bool isEqualTypeErased(const TypeErasedLattice &,
  74                                  const TypeErasedLattice &) = 0;
  75
  76   /// Applies the analysis transfer function for a given statement and
  77   /// type-erased lattice element.
  78   virtual void transferTypeErased(const Stmt *, TypeErasedLattice &,
  79                                   Environment &) = 0;
  80
  81   /// Determines whether to apply the built-in transfer functions, which model
  82   /// the heap and stack in the `Environment`.
  83   bool applyBuiltinTransfer() const { return ApplyBuiltinTransfer; }
  84 };
  85
  86 /// Type-erased model of the program at a given program point.
  87 struct TypeErasedDataflowAnalysisState {
  88   /// Type-erased model of a program property.
  89   TypeErasedLattice Lattice;
  90
  91   /// Model of the state of the program (store and heap).
  92   Environment Env;
  93
  94   TypeErasedDataflowAnalysisState(TypeErasedLattice Lattice, Environment Env)
  95       : Lattice(std::move(Lattice)), Env(std::move(Env)) {}
  96 };
  97
  98 /// Transfers the state of a basic block by evaluating each of its statements in
  99 /// the context of `Analysis` and the states of its predecessors that are
 100 /// available in `BlockStates`. `HandleTransferredStmt` (if provided) will be
 101 /// applied to each statement in the block, after it is evaluated.
 102 ///
 103 /// Requirements:
 104 ///
 105 ///   All predecessors of `Block` except those with loop back edges must have
 106 ///   already been transferred. States in `BlockStates` that are set to
 107 ///   `llvm::None` represent basic blocks that are not evaluated yet.
 108 TypeErasedDataflowAnalysisState transferBlock(
 109     const ControlFlowContext &CFCtx,
 110     std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>> &BlockStates,
 111     const CFGBlock &Block, const Environment &InitEnv,
 112     TypeErasedDataflowAnalysis &Analysis,
 113     std::function<void(const CFGStmt &,
 114                        const TypeErasedDataflowAnalysisState &)>
 115         HandleTransferredStmt = nullptr);
 116
 117 /// Performs dataflow analysis and returns a mapping from basic block IDs to
 118 /// dataflow analysis states that model the respective basic blocks. Indices
 119 /// of the returned vector correspond to basic block IDs. Returns an error if
 120 /// the dataflow analysis cannot be performed successfully.
 121 llvm::Expected<std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>>>
 122 runTypeErasedDataflowAnalysis(const ControlFlowContext &CFCtx,
 123                               TypeErasedDataflowAnalysis &Analysis,
 124                               const Environment &InitEnv);
 125
 126 } // namespace dataflow
 127 } // namespace clang
 128
 129 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TYPEERASEDDATAFLOWANALYSIS_H