[clang][dataflow] Change `transfer` function to update lattice element in place.

[ymandel]

Summary

Currently, the transfer function returns a new lattice element, which forces an
unnecessary copy on processing each CFG statement.

[sgatev]

clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp

167

nit: let's call this E for consistency.

[ymandel]

address comments

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

 /// 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.
+///   * `void transfer(const Stmt *, 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
public:
 
   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;
   }
 
-  TypeErasedLattice transferTypeErased(const Stmt *Stmt,
-                                       const TypeErasedLattice &E,
-                                       Environment &Env) final {
-    const Lattice &L = llvm::any_cast<const Lattice &>(E.Value);
-    return {static_cast<Derived *>(this)->transfer(Stmt, L, Env)};
+  void transferTypeErased(const Stmt *Stmt, TypeErasedLattice &E,
+    Lattice &L = llvm::any_cast<Lattice &>(E.Value);
+    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 {

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

public:
 
   /// 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;
+  virtual void transferTypeErased(const Stmt *, TypeErasedLattice &,
 };
 
 /// 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).

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

for (const CFGElement &Element : Block) {
     const llvm::Optional<CFGStmt> CfgStmt = Element.getAs<CFGStmt>();
     if (!CfgStmt.hasValue())
       continue;
 
     const Stmt *S = CfgStmt.getValue().getStmt();
     assert(S != nullptr);
 
     transfer(*S, State.Env);
-    State.Lattice = Analysis.transferTypeErased(S, State.Lattice, State.Env);
+    Analysis.transferTypeErased(S, State.Lattice, State.Env);
 
     if (HandleTransferredStmt != nullptr)
       HandleTransferredStmt(CfgStmt.getValue(), State);
   }
   return State;
 }
 
 std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>>

clang/unittests/Analysis/FlowSensitive/MultiVarConstantPropagationTest.cpp

public:
   explicit ConstantPropagationAnalysis(ASTContext &Context)
       : DataflowAnalysis<ConstantPropagationAnalysis,
                          ConstantPropagationLattice>(Context) {}
 
   static ConstantPropagationLattice initialElement() {
     return ConstantPropagationLattice::bottom();
   }
 
-  ConstantPropagationLattice
-  transfer(const Stmt *S, ConstantPropagationLattice Vars, Environment &Env) {
+  void transfer(const Stmt *S, ConstantPropagationLattice &Vars,
+                Environment &Env) {
     auto matcher =
         stmt(anyOf(declStmt(hasSingleDecl(
                        varDecl(decl().bind(kVar), hasType(isInteger()),
                                optionally(hasInitializer(expr().bind(kInit))))
                            .bind(kDecl))),
                    binaryOperator(hasOperatorName("="), hasLHS(refToVar()),
                                   hasRHS(expr().bind(kRHS)))
                        .bind(kJustAssignment),
                    binaryOperator(isAssignmentOperator(), hasLHS(refToVar()))
                        .bind(kAssignment)));
 
     ASTContext &Context = getASTContext();
     auto Results = match(matcher, *S, Context);
     if (Results.empty())
-      return Vars;
+      return;
     const BoundNodes &Nodes = Results[0];
 
     const auto *Var = Nodes.getNodeAs<clang::VarDecl>(kVar);
     assert(Var != nullptr);
 
     if (Nodes.getNodeAs<clang::VarDecl>(kDecl) != nullptr) {
       if (const auto *E = Nodes.getNodeAs<clang::Expr>(kInit)) {
         Expr::EvalResult R;
         Vars[Var] = (E->EvaluateAsInt(R, Context) && R.Val.isInt())
                         ? ValueLattice(R.Val.getInt().getExtValue())
                         : ValueLattice::top();
       } else {
         // An unitialized variable holds *some* value, but we don't know what it
         // is (it is implementation defined), so we set it to top.
         Vars[Var] = ValueLattice::top();
       }
-      return Vars;
-    }
-
-    if (Nodes.getNodeAs<clang::Expr>(kJustAssignment)) {
+    } else if (Nodes.getNodeAs<clang::Expr>(kJustAssignment)) {
       const auto *E = Nodes.getNodeAs<clang::Expr>(kRHS);
       assert(E != nullptr);
 
       Expr::EvalResult R;
       Vars[Var] = (E->EvaluateAsInt(R, Context) && R.Val.isInt())
                       ? ValueLattice(R.Val.getInt().getExtValue())
                       : ValueLattice::top();
-      return Vars;
-    }
-
+    } else if (Nodes.getNodeAs<clang::Expr>(kAssignment)) {
       // Any assignment involving the expression itself resets the variable to
       // "unknown". A more advanced analysis could try to evaluate the compound
       // assignment. For example, `x += 0` need not invalidate `x`.
-    if (Nodes.getNodeAs<clang::Expr>(kAssignment)) {
       Vars[Var] = ValueLattice::top();
-      return Vars;
     }
-
-    llvm_unreachable("expected at least one bound identifier");
   }
 };
 
 using ::testing::IsEmpty;
 using ::testing::Pair;
 using ::testing::UnorderedElementsAre;
 
 MATCHER_P(Var, name,

clang/unittests/Analysis/FlowSensitive/NoopAnalysis.h

 
 class NoopAnalysis : public DataflowAnalysis<NoopAnalysis, NoopLattice> {
 public:
   NoopAnalysis(ASTContext &Context)
       : DataflowAnalysis<NoopAnalysis, NoopLattice>(Context) {}
 
   static NoopLattice initialElement() { return {}; }
 
-  NoopLattice transfer(const Stmt *S, const NoopLattice &E, Environment &Env) {
-    return {};
-  }
+  void transfer(const Stmt *S, NoopLattice &E, Environment &Env) {}
 };
 
 } // namespace dataflow
 } // namespace clang
 
 #endif // LLVM_CLANG_UNITTESTS_ANALYSIS_FLOWSENSITIVE_NOOPANALYSIS_H

clang/unittests/Analysis/FlowSensitive/SingleVarConstantPropagationTest.cpp

public:
   explicit ConstantPropagationAnalysis(ASTContext &Context)
       : DataflowAnalysis<ConstantPropagationAnalysis,
                          ConstantPropagationLattice>(Context) {}
 
   static ConstantPropagationLattice initialElement() {
     return ConstantPropagationLattice::bottom();
   }
 
-  ConstantPropagationLattice transfer(const Stmt *S,
-                                      const ConstantPropagationLattice &Element,
-                                      Environment &Env) {
+  void transfer(const Stmt *S, ConstantPropagationLattice &Element,
     auto matcher = stmt(
         anyOf(declStmt(hasSingleDecl(varDecl(hasType(isInteger()),
                                              hasInitializer(expr().bind(kInit)))
                                          .bind(kVar))),
               binaryOperator(hasOperatorName("="), hasLHS(refToVar()),
                              hasRHS(expr().bind(kRHS)))
                   .bind(kJustAssignment),
               binaryOperator(isAssignmentOperator(), hasLHS(refToVar()))
                   .bind(kAssignment)));
 
     ASTContext &Context = getASTContext();
     auto Results = match(matcher, *S, Context);
     if (Results.empty())
-      return Element;
+      return;
     const BoundNodes &Nodes = Results[0];
 
     const auto *Var = Nodes.getNodeAs<clang::VarDecl>(kVar);
     assert(Var != nullptr);
 
     if (const auto *E = Nodes.getNodeAs<clang::Expr>(kInit)) {
       Expr::EvalResult R;
-      if (E->EvaluateAsInt(R, Context) && R.Val.isInt())
-        return ConstantPropagationLattice{
-            {{Var, R.Val.getInt().getExtValue()}}};
-      return ConstantPropagationLattice::top();
-    }
-
-    if (Nodes.getNodeAs<clang::Expr>(kJustAssignment)) {
+      Element =
+          (E->EvaluateAsInt(R, Context) && R.Val.isInt())
+              ? ConstantPropagationLattice{{{Var,
+                                             R.Val.getInt().getExtValue()}}}
+              : ConstantPropagationLattice::top();
+    } else if (Nodes.getNodeAs<clang::Expr>(kJustAssignment)) {
       const auto *RHS = Nodes.getNodeAs<clang::Expr>(kRHS);
       assert(RHS != nullptr);
 
       Expr::EvalResult R;
-      if (RHS->EvaluateAsInt(R, Context) && R.Val.isInt())
-        return ConstantPropagationLattice{
-            {{Var, R.Val.getInt().getExtValue()}}};
-      return ConstantPropagationLattice::top();
-    }
-
+      Element =
+          (RHS->EvaluateAsInt(R, Context) && R.Val.isInt())
+              ? ConstantPropagationLattice{{{Var,
+                                             R.Val.getInt().getExtValue()}}}
+              : ConstantPropagationLattice::top();
+    } else if (Nodes.getNodeAs<clang::Expr>(kAssignment))
       // Any assignment involving the expression itself resets the variable to
       // "unknown". A more advanced analysis could try to evaluate the compound
       // assignment. For example, `x += 0` need not invalidate `x`.
-    if (Nodes.getNodeAs<clang::Expr>(kAssignment))
-      return ConstantPropagationLattice::top();
-
-    llvm_unreachable("expected at least one bound identifier");
+      Element = ConstantPropagationLattice::top();
   }
 };
 
 using ::testing::Pair;
 using ::testing::UnorderedElementsAre;
 
 MATCHER_P(HasConstantVal, v, "") {
   return arg.Data.hasValue() && arg.Data->Value == v;

clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp

class NonConvergingAnalysis
     : public DataflowAnalysis<NonConvergingAnalysis, NonConvergingLattice> {
 public:
   explicit NonConvergingAnalysis(ASTContext &Context)
       : DataflowAnalysis<NonConvergingAnalysis, NonConvergingLattice>(Context) {
   }
 
   static NonConvergingLattice initialElement() { return {0}; }
 
-  NonConvergingLattice transfer(const Stmt *S, const NonConvergingLattice &E,
-                                Environment &Env) {
-    return {E.State + 1};
+  void transfer(const Stmt *S, NonConvergingLattice &E, Environment &Env) {
+    ++E.State;
   }
 };
 
 TEST(DataflowAnalysisTest, NonConvergingAnalysis) {
   auto BlockStates = runAnalysis<NonConvergingAnalysis>(R"(
     void target() {
       while(true) {}
     }

 class FunctionCallAnalysis
     : public DataflowAnalysis<FunctionCallAnalysis, FunctionCallLattice> {
 public:
   explicit FunctionCallAnalysis(ASTContext &Context)
       : DataflowAnalysis<FunctionCallAnalysis, FunctionCallLattice>(Context) {}
 
   static FunctionCallLattice initialElement() { return {}; }
 
-  FunctionCallLattice transfer(const Stmt *S, const FunctionCallLattice &E,
-                               Environment &Env) {
-    FunctionCallLattice R = E;
+  void transfer(const Stmt *S, FunctionCallLattice &E, Environment &Env) {
     if (auto *C = dyn_cast<CallExpr>(S)) {
       if (auto *F = dyn_cast<FunctionDecl>(C->getCalleeDecl())) {
-        R.CalledFunctions.insert(F->getNameInfo().getAsString());
+        E.CalledFunctions.insert(F->getNameInfo().getAsString());
       }
     }
-    return R;
   }
 };
 
 class NoreturnDestructorTest : public ::testing::Test {
 protected:
   template <typename Matcher>
   void runDataflow(llvm::StringRef Code, Matcher Expectations) {
     tooling::FileContentMappings FilesContents;