[clang][dataflow] Intersect ExprToLoc when joining environments

[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/TypeErasedDataflowAnalysis.cpp

59

Are we sure that the memory addresses of CFGBlocks are stable enough for a deterministic order? Alternatively, we could use the block ids for the ordering.

[xazax.hun]

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

59

Also, could you describe where the flakiness is originated from? Naively, I'd expect that the order in which we process the predecessors should not change the results of the analysis.

[sgatev]

Address reviewers' comments.

[sgatev]

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

59

You're right, using block ids for ordering is better. I updated the code.

Also, could you describe where the flakiness is originated from?

Say we have a block B1 with predecessors B2 and B3. Let the environment of B2 after evaluating all of its statements is B2Env = { Expr1 -> Loc1 } and the environment of B3 after evaluating all of its statement is B3Env = { Expr2 -> Loc2 } where ExprX -> LocX refers to a particular mapping of storage locations to expressions.

What we want for the input environment of B1 is {} because B2Env and B3Env do not contain common assignments of storage locations to expressions. What we got before this patch is either B2Env.join(B3Env) = { Expr1 -> Loc1 } or B3Env.join(B2Env) = { Expr2 -> Loc2 }.

Without deterministic ordering of predecessors the test that I'm introducing in this patch is flaky.

[xazax.hun]

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

59

What we got before this patch is either B2Env.join(B3Env) = { Expr1 -> Loc1 } or B3Env.join(B2Env) = { Expr2 -> Loc2 }.

I think I'm still missing something. With this patch, wouldn't both B2Env.join(B3Env) and B3Env.join(B2Env) produce the empty environment? If that is the case, do we still care about a deterministic order?

[sgatev]

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

59

That's right. With the patch in DataflowEnvironment.cpp the particular order of predecessors doesn't affect the result. However, one of the properties that I'm looking for in tests is being able to remove functionality from the code and have the tests that exercise this functionality fail. This won't necessarily be the case here if the order wasn't deterministic. I don't have a strong preference so please let me know if you have concerns about it. I should also note that we expect all of this to be removed once temporary destructors are handled better in the CFG.

[xazax.hun]

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

59

Strictly speaking, making this deterministic is not a requirement, it should not have any observable effect for the end user. On the other hand, we could think of this non-determinism as a feature. A well behaved analysis should produce the same answer regardless of the order in which we process the nodes. (This requirement follows from the algebraic properties of the join operation.) So in the future I would even anticipate a feature that deliberately randomize the order to ensure that the clients are well behaved.

I think eliminating this non-determinism could potentially mask bugs in the future and also it requires extra code. I think I prefer the original version until we see some evidence that determinism is desired.

[sgatev]

Address reviewers' comments.

[sgatev]

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

59

Sure. Reverted that part.

[xazax.hun]

Thanks, this looks good to me!

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

LatticeJoinEffect Environment::join(const Environment &Other) {
 
   auto Effect = LatticeJoinEffect::Unchanged;
 
   const unsigned DeclToLocSizeBefore = DeclToLoc.size();
   DeclToLoc = intersectDenseMaps(DeclToLoc, Other.DeclToLoc);
   if (DeclToLocSizeBefore != DeclToLoc.size())
     Effect = LatticeJoinEffect::Changed;
 
+  const unsigned ExprToLocSizeBefore = ExprToLoc.size();
+  ExprToLoc = intersectDenseMaps(ExprToLoc, Other.ExprToLoc);
+  if (ExprToLocSizeBefore != ExprToLoc.size())
+    Effect = LatticeJoinEffect::Changed;
+
   // FIXME: Add support for joining distinct values that are assigned to the
   // same storage locations in `LocToVal` and `Other.LocToVal`.
   const unsigned LocToValSizeBefore = LocToVal.size();
   LocToVal = intersectDenseMaps(LocToVal, Other.LocToVal);
   if (LocToValSizeBefore != LocToVal.size())
     Effect = LatticeJoinEffect::Changed;
 
   return Effect;

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 <memory>
+#include <set>
 #include <utility>
 #include <vector>
 
 #include "clang/AST/DeclCXX.h"
 #include "clang/Analysis/Analyses/PostOrderCFGView.h"
 #include "clang/Analysis/CFG.h"
 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
 #include "clang/Analysis/FlowSensitive/DataflowWorklist.h"
 #include "clang/Analysis/FlowSensitive/Transfer.h"
 #include "clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h"
 #include "clang/Analysis/FlowSensitive/Value.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/Support/raw_ostream.h"
 
 namespace clang {
 namespace dataflow {
 
+struct CFGBlockPtrCompare {
+  bool operator()(const CFGBlock *LHS, const CFGBlock *RHS) const {
+    if (LHS == nullptr)
+      return true;
+    if (RHS == nullptr)
+      return false;
+    return LHS->getBlockID() < RHS->getBlockID();
+  }
+};
+
 /// Computes the input state for a given basic block by joining the output
 /// states of its predecessors.
 ///
 /// Requirements:
 ///
 ///   All predecessors of `Block` except those with loop back edges must have
 ///   already been transferred. States in `BlockStates` that are set to
 ///   `llvm::None` represent basic blocks that are not evaluated yet.
 static TypeErasedDataflowAnalysisState computeBlockInputState(
     const ControlFlowContext &CFCtx,
     std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>> &BlockStates,
     const CFGBlock &Block, const Environment &InitEnv,
     TypeErasedDataflowAnalysis &Analysis) {
-  llvm::DenseSet<const CFGBlock *> Preds;
+  // Ensure the order of predecessor blocks is deterministic to avoid flakiness
+  // in tests.
+  std::set<const CFGBlock *, CFGBlockPtrCompare> Preds;
   Preds.insert(Block.pred_begin(), Block.pred_end());
   if (Block.getTerminator().isTemporaryDtorsBranch()) {
     // This handles a special case where the code that produced the CFG includes
     // a conditional operator with a branch that constructs a temporary and
     // calls a destructor annotated as noreturn. The CFG models this as follows:
     //
     // B1 (contains the condition of the conditional operator) - succs: B2, B3
     // B2 (contains code that does not call a noreturn destructor) - succs: B4

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

runDataflow(
             dyn_cast<StructValue>(Env.getValue(*BazDecl, SkipPast::None));
         ASSERT_THAT(BazVal, NotNull());
 
         EXPECT_NE(BazVal, FooVal);
         EXPECT_NE(BazVal, BarVal);
       });
 }
 
+TEST_F(TransferTest, VarDeclInDoWhile) {
+  std::string Code = R"(
+    void target(int *Foo) {
+      do {
+        int Bar = *Foo;
+      } while (true);
+      (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 *FooVal =
+                    cast<PointerValue>(Env.getValue(*FooDecl, SkipPast::None));
+                const auto *FooPointeeVal =
+                    cast<IntegerValue>(Env.getValue(FooVal->getPointeeLoc()));
+
+                const auto *BarVal = dyn_cast_or_null<IntegerValue>(
+                    Env.getValue(*BarDecl, SkipPast::None));
+                ASSERT_THAT(BarVal, NotNull());
+
+                EXPECT_EQ(BarVal, FooPointeeVal);
+              });
+}
+
 } // namespace