[clang][dataflow][NFC] Remove LatticeJoinEffect from framework interfaces

[li.zhe.hua]

Summary

Though we request users implementing join to return a meaningful
LatticeJoinEffect, we never use the returned value. Requiring users
(and the framework) to continue calculating an unused value adds
unnecessary complexity.

[xazax.hun]

Returning whether the lattice was changed can be a nice optimization when comparing lattice elements is expensive. On the other hand, it can be one more source of errors. I am fine with either approach, both can make sense depending on whether the goal is to make the interface easier to use or to have superb performance.

[ymandel]

In D131688#3716467, @xazax.hun wrote:

Returning whether the lattice was changed can be a nice optimization when comparing lattice elements is expensive. On the other hand, it can be one more source of errors. I am fine with either approach, both can make sense depending on whether the goal is to make the interface easier to use or to have superb performance.

Agreed and the performance consideration was the original motivation. But, then we never used it! Indeed, we'd have to rework the worklist algorithm to make use of return value so that, for each block, it saved the state immediately before the block (that is, after the join from incoming branches). Currently, we only save the state *after* the block.

That's why I suggested to Eric that we should remove it. We can revisit in the future: if it seems a valuable source of performance improvement, we can consider how best to modify the system at that point.

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

 ///
 ///  `Derived` can optionally override the following members:
 ///   * `bool merge(QualType, const Value &, const Value &, Value &,
 ///     Environment &)` -  joins distinct values. This could be a strict
 ///     lattice join or a more general widening operation.
 ///
 ///  `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;
+///   * `void join(const LatticeT &)` - joins the object and the argument by
+///     computing their least upper bound and modifies the object if necessary;
 ///   * `bool operator==(const LatticeT &) const` - returns true if and only if
 ///     the object is equal to the argument.
 ///
 ///  `LatticeT` may also optionally provide the following members:
 ///   * `void widen(const LatticeT &)` - relaxes the object to subsume the
 ///     argument, computing an upper bound. Widen is called during loops, where
 ///     a join operation may prevent convergence for a lattice of infinite
 ///     height. If `widen` is not provided, `join` is used by default.
explicit DataflowAnalysis(ASTContext &Context,
       : TypeErasedDataflowAnalysis(Options), Context(Context) {}
 
   ASTContext &getASTContext() final { return Context; }
 
   TypeErasedLattice typeErasedInitialElement() final {
     return {static_cast<Derived *>(this)->initialElement()};
   }
 
-  LatticeJoinEffect joinTypeErased(TypeErasedLattice &E1,
-                                   const TypeErasedLattice &E2) final {
+  void joinTypeErased(TypeErasedLattice &E1,
     Lattice &L1 = llvm::any_cast<Lattice &>(E1.Value);
     const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value);
-    return L1.join(L2);
+    L1.join(L2);
   }
 
   void widenTypeErased(TypeErasedLattice &E1,
                        const TypeErasedLattice &E2) final {
     Lattice &L1 = llvm::any_cast<Lattice &>(E1.Value);
     const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value);
     widenInternal(Rank0{}, L1, L2);
   }

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

 #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H
 
 #include "clang/AST/Decl.h"
 #include "clang/AST/DeclBase.h"
 #include "clang/AST/Expr.h"
 #include "clang/AST/Type.h"
 #include "clang/Analysis/FlowSensitive/ControlFlowContext.h"
 #include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h"
-#include "clang/Analysis/FlowSensitive/DataflowLattice.h"
 #include "clang/Analysis/FlowSensitive/StorageLocation.h"
 #include "clang/Analysis/FlowSensitive/Value.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include <memory>
 #include <type_traits>
 #include <utility>
 
public:
   /// Joins the environment with `Other` by taking the intersection of storage
   /// locations and values that are stored in them. Distinct values that are
   /// assigned to the same storage locations in the environment and `Other` are
   /// merged using `Model`.
   ///
   /// Requirements:
   ///
   ///  `Other` and `this` must use the same `DataflowAnalysisContext`.
-  LatticeJoinEffect join(const Environment &Other,
-                         Environment::ValueModel &Model);
+  void join(const Environment &Other, Environment::ValueModel &Model);
 
   // FIXME: Rename `createOrGetStorageLocation` to `getOrCreateStorageLocation`,
   // `getStableStorageLocation`, or something more appropriate.
 
   /// Creates a storage location appropriate for `Type`. Does not assign a value
   /// to the returned storage location in the environment.
   ///
   /// Requirements:

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

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWLATTICE_H
 #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWLATTICE_H
 
 namespace clang {
 namespace dataflow {
 
+/// DEPRECATED: Not meaningfully used.
+///
 /// Effect indicating whether a lattice join operation resulted in a new value.
+///
+/// FIXME: Delete this file once all references are removed.
 enum class LatticeJoinEffect {
   Unchanged,
   Changed,
 };
 
 } // namespace dataflow
 } // namespace clang
 
 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWLATTICE_H

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

 #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/DataflowEnvironment.h"
-#include "clang/Analysis/FlowSensitive/DataflowLattice.h"
 #include "clang/Analysis/FlowSensitive/Transfer.h"
 #include "llvm/ADT/Any.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/Support/Error.h"
 
 namespace clang {
 namespace dataflow {
 
public:
 
   /// 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;
+  virtual void joinTypeErased(TypeErasedLattice &,
 
   /// Relaxes the constraints in `A` to subsume the state in `B`.
   virtual void widenTypeErased(TypeErasedLattice &A,
                                const TypeErasedLattice &B) = 0;
 
   /// Returns true if and only if the two given type-erased lattice elements are
   /// equal.
   virtual bool isEqualTypeErased(const TypeErasedLattice &,

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

 //  program at given program points.
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
 #include "clang/AST/Decl.h"
 #include "clang/AST/DeclCXX.h"
 #include "clang/AST/Type.h"
-#include "clang/Analysis/FlowSensitive/DataflowLattice.h"
 #include "clang/Analysis/FlowSensitive/Value.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/ErrorHandling.h"
 #include <cassert>
 #include <memory>
 #include <utility>
for (auto &Entry : LocToVal) {
 
     if (!equivalentValues(Loc->getType(), Val, *this, It->second, Other, Model))
       return false;
   }
 
   return true;
 }
 
-LatticeJoinEffect Environment::join(const Environment &Other,
-                                    Environment::ValueModel &Model) {
+void Environment::join(const Environment &Other,
   assert(DACtx == Other.DACtx);
   assert(ReturnLoc == Other.ReturnLoc);
   assert(ThisPointeeLoc == Other.ThisPointeeLoc);
 
-  auto Effect = LatticeJoinEffect::Unchanged;
-
   Environment JoinedEnv(*DACtx);
 
   JoinedEnv.ReturnLoc = ReturnLoc;
   JoinedEnv.ThisPointeeLoc = ThisPointeeLoc;
 
   JoinedEnv.DeclToLoc = intersectDenseMaps(DeclToLoc, Other.DeclToLoc);
-  if (DeclToLoc.size() != JoinedEnv.DeclToLoc.size())
-    Effect = LatticeJoinEffect::Changed;
-
   JoinedEnv.ExprToLoc = intersectDenseMaps(ExprToLoc, Other.ExprToLoc);
-  if (ExprToLoc.size() != JoinedEnv.ExprToLoc.size())
-    Effect = LatticeJoinEffect::Changed;
-
   JoinedEnv.MemberLocToStruct =
       intersectDenseMaps(MemberLocToStruct, Other.MemberLocToStruct);
-  if (MemberLocToStruct.size() != JoinedEnv.MemberLocToStruct.size())
-    Effect = LatticeJoinEffect::Changed;
-
-  // FIXME: set `Effect` as needed.
   JoinedEnv.FlowConditionToken = &DACtx->joinFlowConditions(
       *FlowConditionToken, *Other.FlowConditionToken);
 
   for (auto &Entry : LocToVal) {
     const StorageLocation *Loc = Entry.first;
     assert(Loc != nullptr);
 
     Value *Val = Entry.second;
     assert(Val != nullptr);
 
     auto It = Other.LocToVal.find(Loc);
     if (It == Other.LocToVal.end())
       continue;
     assert(It->second != nullptr);
 
     if (Val == It->second) {
       JoinedEnv.LocToVal.insert({Loc, Val});
       continue;
     }
 
     if (Value *MergedVal = mergeDistinctValues(
             Loc->getType(), Val, *this, It->second, Other, JoinedEnv, Model))
       JoinedEnv.LocToVal.insert({Loc, MergedVal});
   }
-  if (LocToVal.size() != JoinedEnv.LocToVal.size())
-    Effect = LatticeJoinEffect::Changed;
 
   *this = std::move(JoinedEnv);
-
-  return Effect;
 }
 
 StorageLocation &Environment::createStorageLocation(QualType Type) {
   return DACtx->createStorageLocation(Type);
 }
 
 StorageLocation &Environment::createStorageLocation(const VarDecl &D) {
   // Evaluated declarations are always assigned the same storage locations to