[clang][dataflow] Merge distinct pointer values in Environment::join

[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.

[xazax.hun]

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

114

Shouldn't we ensure that operator== return true when we have two PointerValues with the same pointee above? That would make this piece of code redundant.

[xazax.hun]

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

114

Never mind, just realized the above is comparing pointers. But I still think we might want to have a separate operator== for Values as we might want to compare values in many separate places.

[xazax.hun]

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

114

Or alternatively, Values could be internalized, and all PointerValues with the same pointee could have the same address.

[sgatev]

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

114

Right. Currently, all tests that assign values in loops (including the test introduced in this patch) are hitting the maximum iterations limit because we don't have a way to tell the framework how to compare distinct values (e.g. there's no need to continue iterating if the has_value properties of distinct optional values are the same). This will be the focus of my next patch.

[xazax.hun]

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

114

Oh, I see. In this case let's merge this and looking forward to the next one :)

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

LatticeJoinEffect Environment::join(const Environment &Other,
   if (DeclToLocSizeBefore != DeclToLoc.size())
     Effect = LatticeJoinEffect::Changed;
 
   const unsigned ExprToLocSizeBefore = ExprToLoc.size();
   ExprToLoc = intersectDenseMaps(ExprToLoc, Other.ExprToLoc);
   if (ExprToLocSizeBefore != ExprToLoc.size())
     Effect = LatticeJoinEffect::Changed;
 
-  llvm::DenseMap<const StorageLocation *, Value *> MergedLocToVal;
-  for (auto &Entry : LocToVal) {
+  // Move `LocToVal` so that `Environment::Merger::merge` can safely assign
+  // values to storage locations while this code iterates over the current
+  // assignments.
+  llvm::DenseMap<const StorageLocation *, Value *> OldLocToVal =
+      std::move(LocToVal);
+  for (auto &Entry : OldLocToVal) {
     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 (It->second == Val) {
-      MergedLocToVal.insert({Loc, Val});
+      LocToVal.insert({Loc, Val});
       continue;
     }
 
+    if (auto *FirstVal = dyn_cast<PointerValue>(Val)) {
+      auto *SecondVal = cast<PointerValue>(It->second);
+      if (&FirstVal->getPointeeLoc() == &SecondVal->getPointeeLoc()) {
+        LocToVal.insert({Loc, FirstVal});
+        continue;
+      }
+    }
+
     // FIXME: Consider destroying `MergedValue` immediately if `Merger::merge`
     // returns false to avoid storing unneeded values in `DACtx`.
     if (Value *MergedVal = createValue(Loc->getType()))
       if (Merger.merge(Loc->getType(), *Val, *It->second, *MergedVal, *this))
-        MergedLocToVal.insert({Loc, MergedVal});
+        LocToVal.insert({Loc, MergedVal});
   }
-  const unsigned LocToValSizeBefore = LocToVal.size();
-  LocToVal = std::move(MergedLocToVal);
-  if (LocToValSizeBefore != LocToVal.size())
+  if (OldLocToVal.size() != LocToVal.size())
     Effect = LatticeJoinEffect::Changed;
 
   return Effect;
 }
 
 StorageLocation &Environment::createStorageLocation(QualType Type) {
   assert(!Type.isNull());
   if (Type->isStructureOrClassType() || Type->isUnionType()) {

clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp

runDataflow(
                   &Env2.getBoolLiteralValue(true));
         EXPECT_EQ(GetFooValue(Env3)->getProperty("has_value"),
                   &Env3.getBoolLiteralValue(true));
         EXPECT_EQ(GetFooValue(Env4)->getProperty("has_value"),
                   &Env4.getBoolLiteralValue(true));
       });
 }
 
+TEST_F(WideningTest, DistinctPointersToTheSameLocation) {
+  std::string Code = R"(
+    void target(int Foo, bool Cond) {
+      int *Bar = &Foo;
+      while (Cond) {
+        Bar = &Foo;
+      }
+      (void)0;
+      // [[p]]
+    }
+  )";
+  runDataflow(Code,
+              [](llvm::ArrayRef<
+                     std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
+                     Results,
+                 ASTContext &ASTCtx) {
+                ASSERT_THAT(Results, ElementsAre(Pair("p", _)));
+                const Environment &Env = Results[0].second.Env;
+
+                const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
+                ASSERT_THAT(FooDecl, NotNull());
+
+                const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
+                ASSERT_THAT(BarDecl, NotNull());
+
+                const auto *FooLoc = cast<ScalarStorageLocation>(
+                    Env.getStorageLocation(*FooDecl, SkipPast::None));
+                const auto *BarVal =
+                    cast<PointerValue>(Env.getValue(*BarDecl, SkipPast::None));
+                EXPECT_EQ(&BarVal->getPointeeLoc(), FooLoc);
+              });
+}
+
 } // namespace