[clang][dataflow] Add an API for dataflow "models" -- reusable analysis components.

[ymandel]

Summary

This patch introduces DataflowModel, an abstract base class for dataflow
"models": reusable analysis components that model a particular aspect of program
semantics.

[sgatev]

clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h

148–149

Do we want to compose models that have different lattice types? Do we want to have models with no lattices that only use Environment? If we don't know this yet, I suggest replacing this with a FIXME to explore model composability at a later point when we have answers to these questions.

153

LatticeT for consistency with the code above.

[gribozavr2]

clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h

139

DYM "Abstract base class"?

[ymandel]

Address comments.

[ymandel]

clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h

139

Indeed.

[xazax.hun]

clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h

150–151

I think supporting different lattice types is a must for a good composability model. E.g., in an ideal world when we have a lattice for constant propagation of integers and we have a model for std::optional, it would be great if we could do constant propagation to/from non-empty optionals of integers.

152

The Clang Static Analyzer is full of modeling that has no dedicated state, it will just update the equivalent of an environment (e.g., adding a range to the returned values): https://github.com/llvm/llvm-project/blob/main/clang/lib/StaticAnalyzer/Checkers/StdLibraryFunctionsChecker.cpp#L1208

Once we have a framework that can reason about integers, I think having something similar (or even better, somehow being able to reuse these summaries across CSA and dataflow) would be awesome.

159

In the Clang Static Analyzer the process of modelling is more conversational between the "modeling checks" and the framework. There, a return value indicates whether a particular function call was modeled and the first time someone wants to model a function call it will short circuit the whole process. This ensures that only one model will be applied.

I'm not 100% sure whether this would be the best model here. But I'd strongly suggest to add a bool return value here, because it might be useful for the framework to know in the future if some modeling was done at all (potentially skipping some default modeling based ont he return value).

[ymandel]

adjust API in response to comments.

[ymandel]

clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h

150–151

Agreed. And, fwiw, my stacked patch with a very small model does not involve the lattice. For the optional checker, we plan to split it into a model and a separate analysis which handles the lattice.

152

I removed the lattice dependency and reworded the description to focus on the environment.

[xazax.hun]

Thanks!

clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h

llvm::transform(std::move(*TypeErasedBlockStates),
                           llvm::any_cast<typename AnalysisT::Lattice>(
                               std::move(State.Lattice.Value)),
                           std::move(State.Env)};
                     });
                   });
   return BlockStates;
 }
 
+/// Abstract base class for dataflow "models": reusable analysis components that
+/// model a particular aspect of program semantics, with respect to a specific
+/// lattice. Models are very similar to analyses, except:
+///
+/// a) Models implement a typed dynamic (that is, virtual) interface (with
+///    respect to the lattice type), while analyses implement an untyped dynamic
+///    interface.
+///
+/// b) Models should focus on a _particular_ aspect of program semantics -- for
+///    example, a type and its related functions. FIXME: determine how models
+///    should relate to each other -- that is, how they should compose. Open
+///    questions include: Do we want to enable composition of models that have
+///    different lattice types? Do we want to support models with no lattices
+///    that only use the Environment?
+///
+/// c) Models do not provide an initial element -- that is the responsibility of
+///    the analysis.
+template <typename LatticeT>
+class DataflowModel : public Environment::ValueModel {
+public:
+  virtual void transfer(const Stmt *Stmt, LatticeT &L, Environment &Env) = 0;
+};
+
 } // namespace dataflow
 } // namespace clang
 
 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSIS_H