[clang][dataflow] Add base types for building dataflow analyses

[sgatev]

Summary

This is part of the implementation of the dataflow analysis framework.
See "[RFC] A dataflow analysis framework for Clang AST" on cfe-dev.

[sgatev]

Fix ifndefs.

[sgatev]

Use triple slash at the start of declaration comments.

[ymandel]

clang/lib/Analysis/FlowSensitive/DataflowAnalysis.cpp

21–22 ↗

(On Diff #388469)

It's more common in .cpp files to use using declarations instead:

using clang;
using dataflow;

[sgatev]

Add using namespace declarations in the cpp file.

[xazax.hun]

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

49

Does the Dynamic in the suffix refer to the fact this is using type erasure as opposed to templates?

I have multiple questions at this point:

• Why do we prefer type erasure over generic programming?
• Do you plan to have non-dynamic counterparts?

Nit: having Dynamic both in the class name and in the method names sounds overly verbose to me.
Nit: please add a comment what dynamic refers to in the name,

141

Do we need a ctor? Or is this a workaround for aggregate initialization not working well with certain library facilities?

clang/lib/Analysis/FlowSensitive/DataflowAnalysis.cpp

26 ↗

(On Diff #388490)

Is there a way to query how the CFG was built? Adding an assert to see if setAlwaysAdd was set might be useful.

[sgatev]

Remove unnecessary constructor.

[sgatev]

Add a note about asserting the requirements of the CFG object.

[sgatev]

Document the role of the "Dynamic" suffix in the name of DataflowAnalysisDynamic and its members.

[sgatev]

Put typed and type-erased interfaces in separate files.

[sgatev]

Rename Environment.h to DataflowEnvironment.h.

[sgatev]

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

49

Right. The "Dynamic" suffix emphasizes the type-erased nature of the class and its members and is used to differentiate them from their typed counterparts in DataflowAnalysis. I added this to the documentation of the type. I also split the typed and type-erased interfaces in separate files. Users of the framework shouldn't need to interact with types and functions from DataflowAnalysisDynamic.h.

The names are verbose, but should be used in relatively few internal places in the framework. Currently, we have one call site for each of the methods of DataflowAnalysisDynamic. Nevertheless, if you have ideas for better names I'd be happy to change them.

The reason we went with a type-erased layer is to avoid pulling a lot of code in the templates. Over time the implementation got cleaner and as I'm preparing these patches I see some opportunities to simplify it further. However, it's still non-trivial amount of code. I think we should revisit this decision at some point and consider having entirely template-based implementation of the algorithm. I personally don't see clear benefits of one approach over the other at this point. If you have strong preference for using templates, we can consider going down that route now.

141

We don't really need it at this point. Removed.

clang/lib/Analysis/FlowSensitive/DataflowAnalysis.cpp

26 ↗

(On Diff #388490)

Good point. I believe there isn't a way to do that currently, but this is something we should consider implementing. I added a FIXME.

[xazax.hun]

Thanks, it looks good to me. Most of my comments are just brainstorming, exploring alternative ideas. Feel free to ignore some/all of them.

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

49

Thanks for the explanation! I don't have a strong preference, we could stick with the type-erased version unless we see some reason to change in the future. However, I don't see much value in the "Dynamic" suffix for the method names. What do you think about simply dropping them?

95

If I understand this correctly, this could derive from DataflowAnalysisStateDynamic, it could just provide a getter function that casts the type erased lattice element to LatticeT, returning a reference to the contents of the any object. As a result, you would no longer need to do move/copy in runDataflowAnalysis. On the other hand, the user would need to call a getter to get out the lattice element. I guess we expect lattice elements to be relatively cheap to move. Feel free to leave this unchanged, it is more of an observation.

103

While it is probably obvious to most of us, I wonder if it is obvious to all future readers that the block IDs are the indices of the vector. Depending on how beginner-friendly do we want these comments to be we could make that more explicit.

clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisDynamic.h

45 ↗

(On Diff #389774)

Alternatively, we could replace Dynamic with TypeErased in the class name making the comment redundant.

[sgatev]

Replace "Dynamic" with "TypeErased" in the names of types and their members.

[sgatev]

Minor tweaks to documentation.

[sgatev]

Thanks Gábor and Dmitri!

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

49

Well, the only reason I see to have the suffix is to differentiate the type-erased methods from the methods of the concrete dataflow analysis class that will derive from DataflowAnalysis. For example, we could have

class ConstantPropagationAnalysis : public DataflowAnalysis<
  ConstantPropagationAnalysis, ConstantPropagationLattice> {
public:
  ConstantPropagationLattice initialElement();

  ConstantPropagationLattice transfer(
    const Stmt *, const ConstantPropagationLattice &, Environment &);
};

In this setup ConstantPropagationAnalysis has two methods that return the initial element and two methods that perform the transfer function - one pair in the definition and one pair inherited from TypeErasedDataflowAnalysis. For the initial element we need to use different names as the two methods differ only in their return types. For the transfer function we could use the same name and rely on overload resolution, however it seems that's not recommended - https://clang.llvm.org/docs/DiagnosticsReference.html#woverloaded-virtual. The names of the remaining methods (joinTypeErased and isEqualTypeErased) have the suffix for consistency.

95

Acknowledged. I'll keep this option in mind. For now I suggest we keep the typed and type-erased structs separate if possible and if the cost isn't too high.

103

Let's make it clear. I added a note on that.

clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisDynamic.h

45 ↗

(On Diff #389774)

That would be appropriate indeed. I updated the names.

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

+//===- 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/DataflowEnvironment.h"
+#include "clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.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 TypeErasedDataflowAnalysis {
+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 typeErasedInitialElement() final {
+    return {static_cast<Derived *>(this)->initialElement()};
+  }
+
+  LatticeJoinEffect joinTypeErased(TypeErasedLattice &E1,
+                                   const TypeErasedLattice &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 isEqualTypeErased(const TypeErasedLattice &E1,
+                         const TypeErasedLattice &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 transferTypeErased(const Stmt *Stmt,
+                                       const AnyLatticeElement &E,
+                                       Environment &Env) final {
+    const Lattice &L = llvm::any_cast<const Lattice &>(E.Value);
+    return {static_cast<Derived *>(this)->transfer(Stmt, L, Env)};
+  }
+
+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. Indices
+/// of the returned vector correspond to basic block IDs.
+///
+/// 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 TypeErasedBlockStates =
+      runTypeErasedDataflowAnalysis(Cfg, Analysis, InitEnv);
+  std::vector<
+      llvm::Optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>
+      BlockStates;
+  BlockStates.reserve(TypeErasedBlockStates.size());
+  llvm::transform(std::move(TypeErasedBlockStates),
+                  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

clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h

+//===-- DataflowEnvironment.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_DATAFLOWENVIRONMENT_H
+#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_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_DATAFLOWENVIRONMENT_H

clang/include/clang/Analysis/FlowSensitive/DataflowLattice.h

+//===- 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

clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h

+//===- 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 <vector>
+
+#include "clang/AST/ASTContext.h"
+#include "clang/AST/Stmt.h"
+#include "clang/Analysis/CFG.h"
+#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
+#include "clang/Analysis/FlowSensitive/DataflowLattice.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 TypeErasedLattice {
+  llvm::Any Value;
+};
+
+/// Type-erased base class for dataflow analyses built on a single lattice type.
+class TypeErasedDataflowAnalysis {
+public:
+  /// 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;
+
+  /// 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 statement and
+  /// type-erased lattice element.
+  virtual TypeErasedLattice transferTypeErased(const Stmt *,
+                                               const TypeErasedLattice &,
+                                               Environment &) = 0;
+};
+
+/// 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;
+};
+
+/// 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.
+///
+/// Requirements:
+///
+///  `Cfg` must have been built with `CFG::BuildOptions::setAllAlwaysAdd()` to
+///  ensure that all sub-expressions in a basic block are evaluated.
+std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>>
+runTypeErasedDataflowAnalysis(const CFG &Cfg,
+                              TypeErasedDataflowAnalysis &Analysis,
+                              const Environment &InitEnv);
+
+} // namespace dataflow
+} // namespace clang
+
+#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TYPEERASEDDATAFLOWANALYSIS_H

clang/lib/Analysis/CMakeLists.txt

add_clang_library(clangAnalysis
   clangBasic
   clangLex
 
   DEPENDS
   omp_gen
   )
 
 add_subdirectory(plugins)
+add_subdirectory(FlowSensitive)

clang/lib/Analysis/FlowSensitive/CMakeLists.txt

+add_clang_library(clangAnalysisFlowSensitive
+  TypeErasedDataflowAnalysis.cpp
+
+  LINK_LIBS
+  clangAnalysis
+  clangAST
+  )

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

+//===- TypeErasedDataflowAnalysis.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/DataflowEnvironment.h"
+#include "clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h"
+#include "llvm/ADT/Optional.h"
+
+using namespace clang;
+using namespace dataflow;
+
+std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>>
+runTypeErasedDataflowAnalysis(const CFG &Cfg,
+                              TypeErasedDataflowAnalysis &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 {};
+}