[clang][dataflow] Perform structural comparison of indirection values in `join`.

[ymandel]

Summary

This patch changes Environment::join, in the case that two values at the same
location are not (pointer) equal, to structurally compare indirection values
(pointers and references) for equivalence (that is, equivalent pointees) before
resorting to merging.

This change makes join consistent with equivalence, which also performs
structural comparison. It also fixes a bug where the values are ReferenceValue
but the merge creates a non-reference value. This case arises when the
ReferenceValues were created to represent an lvalue, so the "reference-ness"
is not reflected in the type. In this case, the pointees will always be
equivalent, because lvalues at the same code location point to the location of a
fixed declaration, whose location is itself stable across blocks.

We were unable to reproduce a unit test for this latter bug, but have verified
the fix in the context of a larger piece of code that triggers the bug.

[sgatev]

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

366–374

Let's add merging of distinct indirection values to mergeDistinctValues where we already have code for merging distinct boolean values.

[ymandel]

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

366–374

Good idea, done. That's nicer, thanks.

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

 #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/StorageLocation.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>
 
 namespace clang {
 namespace dataflow {
 
if (auto *Expr1 = dyn_cast<BoolValue>(Val1)) {
     }
     auto *Expr2 = cast<BoolValue>(Val2);
     for (BoolValue *Constraint : Env2.getFlowConditionConstraints()) {
       Expr2 = &MergedEnv.makeAnd(*Expr2, *Constraint);
     }
     return &MergedEnv.makeOr(*Expr1, *Expr2);
   }
 
+  // FIXME: add unit tests that cover this statement.
+  if (auto *IndVal1 = dyn_cast<IndirectionValue>(Val1)) {
+    auto *IndVal2 = cast<IndirectionValue>(Val2);
+    assert(IndVal1->getKind() == IndVal2->getKind());
+    if (&IndVal1->getPointeeLoc() == &IndVal2->getPointeeLoc()) {
+      return Val1;
+    }
+  }
+
   // FIXME: Consider destroying `MergedValue` immediately if `ValueModel::merge`
   // returns false to avoid storing unneeded values in `DACtx`.
   if (Value *MergedVal = MergedEnv.createValue(Type))
     if (Model.merge(Type, *Val1, Env1, *Val2, Env2, *MergedVal, MergedEnv))
       return MergedVal;
 
   return nullptr;
 }
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) {
   assert(!Type.isNull());
   if (Type->isStructureOrClassType() || Type->isUnionType()) {
     // FIXME: Explore options to avoid eager initialization of fields as some of
     // them might not be needed for a particular analysis.