[dataflow] improve determinism of generated SAT system

[sammccall]

Summary

Fixes two places where we relied on map iteration order when processing
values, which leaked nondeterminism into the generated SAT formulas.
Adds a couple of tests that directly assert that the SAT system is
equivalent on each run.

It's desirable that the formulas are deterministic based on the input:

• our SAT solver is naive and perfermance is sensitive to even simple semantics-preserving transformations like A|B to B|A. (e.g. it's likely to choose a different variable to split on). Timeout failures are bad, but *flaky* ones are terrible to debug.
• similarly when debugging, it's important to have a consistent understanding of what e.g. "V23" means across runs.

---

Both changes in this patch were isolated from a nullability analysis of
real-world code which was extremely slow, spending ages in the SAT
solver at "random" points that varied on each run.
I've included a reduced version of the code as a regression test.

One of the changes shows up directly as flow-condition nondeterminism
with a no-op analysis, the other relied on bits of the nullability
analysis but I found a synthetic example to show the problem.

[gribozavr2]

clang/unittests/Analysis/FlowSensitive/DeterminismTest.cpp

63

[ymandel]

Thank you, Sam!

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

 #include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h"
 #include "clang/Analysis/FlowSensitive/DataflowLattice.h"
 #include "clang/Analysis/FlowSensitive/Formula.h"
 #include "clang/Analysis/FlowSensitive/Logger.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/ADT/MapVector.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/ErrorHandling.h"
 #include <memory>
 #include <type_traits>
 #include <utility>
 
 namespace clang {
 namespace dataflow {
private:
   AggregateStorageLocation *ThisPointeeLoc = nullptr;
 
   // Maps from program declarations and statements to storage locations that are
   // assigned to them. Unlike the maps in `DataflowAnalysisContext`, these
   // include only storage locations that are in scope for a particular basic
   // block.
   llvm::DenseMap<const ValueDecl *, StorageLocation *> DeclToLoc;
   llvm::DenseMap<const Expr *, StorageLocation *> ExprToLoc;
-
-  llvm::DenseMap<const StorageLocation *, Value *> LocToVal;
+  // We preserve insertion order so that join/widen process values in
+  // deterministic sequence. This in turn produces deterministic SAT formulas.
+  llvm::MapVector<const StorageLocation *, Value *> LocToVal;
 
   // Maps locations of struct members to symbolic values of the structs that own
   // them and the decls of the struct members.
   llvm::DenseMap<const StorageLocation *,
                  std::pair<StructValue *, const ValueDecl *>>
       MemberLocToStruct;
 
   Atom FlowConditionToken;

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

 #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/ADT/MapVector.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/ErrorHandling.h"
 #include <cassert>
 #include <memory>
 #include <utility>
 
 namespace clang {
LatticeJoinEffect Environment::widen(const Environment &PrevEnv,
   // `join` can cause the map size to increase (when we add fresh data in places
   // of conflict). Once this issue with join is resolved, re-enable the
   // assertion below or replace with something that captures the desired
   // invariant.
   assert(DeclToLoc.size() <= PrevEnv.DeclToLoc.size());
   assert(ExprToLoc.size() <= PrevEnv.ExprToLoc.size());
   // assert(MemberLocToStruct.size() <= PrevEnv.MemberLocToStruct.size());
 
-  llvm::DenseMap<const StorageLocation *, Value *> WidenedLocToVal;
+  llvm::MapVector<const StorageLocation *, Value *> WidenedLocToVal;
   for (auto &Entry : LocToVal) {
     const StorageLocation *Loc = Entry.first;
     assert(Loc != nullptr);
 
     Value *Val = Entry.second;
     assert(Val != nullptr);
 
     auto PrevIt = PrevEnv.LocToVal.find(Loc);

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

 ///
 /// Requirements:
 ///
 ///   All predecessors of `Block` except those with loop back edges must have
 ///   already been transferred. States in `AC.BlockStates` that are set to
 ///   `std::nullopt` represent basic blocks that are not evaluated yet.
 static TypeErasedDataflowAnalysisState
 computeBlockInputState(const CFGBlock &Block, AnalysisContext &AC) {
-  llvm::DenseSet<const CFGBlock *> Preds;
-  Preds.insert(Block.pred_begin(), Block.pred_end());
+  std::vector<const CFGBlock *> Preds(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
     // B3 (contains code that calls a noreturn destructor) - succs: B4
if (Block.getTerminator().isTemporaryDtorsBranch()) {
     // operator includes a branch that contains a noreturn destructor call.
     //
     // See `NoreturnDestructorTest` for concrete examples.
     if (Block.succ_begin()->getReachableBlock() != nullptr &&
         Block.succ_begin()->getReachableBlock()->hasNoReturnElement()) {
       auto &StmtToBlock = AC.CFCtx.getStmtToBlock();
       auto StmtBlock = StmtToBlock.find(Block.getTerminatorStmt());
       assert(StmtBlock != StmtToBlock.end());
-      Preds.erase(StmtBlock->getSecond());
+      llvm::erase_value(Preds, StmtBlock->getSecond());
     }
   }
 
   JoinedStateBuilder Builder(AC);
   for (const CFGBlock *Pred : Preds) {
     // Skip if the `Block` is unreachable or control flow cannot get past it.
     if (!Pred || Pred->hasNoReturnElement())
       continue;

clang/unittests/Analysis/FlowSensitive/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   FrontendOpenMP
   Support
   )
 
 add_clang_unittest(ClangAnalysisFlowSensitiveTests
   ArenaTest.cpp
   CFGMatchSwitchTest.cpp
   ChromiumCheckModelTest.cpp
   DataflowAnalysisContextTest.cpp
   DataflowEnvironmentTest.cpp
   DebugSupportTest.cpp
+  DeterminismTest.cpp
   LoggerTest.cpp
   MapLatticeTest.cpp
   MatchSwitchTest.cpp
   MultiVarConstantPropagationTest.cpp
   RecordOpsTest.cpp
   SignAnalysisTest.cpp
   SingleVarConstantPropagationTest.cpp
   SolverTest.cpp

clang/unittests/Analysis/FlowSensitive/DeterminismTest.cpp

+//===- unittests/Analysis/FlowSensitive/DeterminismTest.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
+//
+//===----------------------------------------------------------------------===//
+
+#include "TestingSupport.h"
+#include "clang/AST/Decl.h"
+#include "clang/Analysis/FlowSensitive/ControlFlowContext.h"
+#include "clang/Analysis/FlowSensitive/DataflowAnalysis.h"
+#include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h"
+#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
+#include "clang/Analysis/FlowSensitive/Formula.h"
+#include "clang/Analysis/FlowSensitive/NoopAnalysis.h"
+#include "clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h"
+#include "clang/Analysis/FlowSensitive/WatchedLiteralsSolver.h"
+#include "clang/Basic/LLVM.h"
+#include "clang/Testing/TestAST.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Support/raw_ostream.h"
+#include "gtest/gtest.h"
+#include <memory>
+#include <string>
+
+namespace clang::dataflow {
+
+// Run a no-op analysis, and return a textual representation of the
+// flow-condition at function exit.
+std::string analyzeAndPrintExitCondition(llvm::StringRef Code) {
+  DataflowAnalysisContext DACtx(std::make_unique<WatchedLiteralsSolver>());
+  clang::TestAST AST(Code);
+  const auto *Target =
+      cast<FunctionDecl>(test::findValueDecl(AST.context(), "target"));
+  Environment InitEnv(DACtx, *Target);
+  auto CFCtx = cantFail(ControlFlowContext::build(*Target));
+
+  NoopAnalysis Analysis(AST.context(), DataflowAnalysisOptions{});
+
+  auto Result = runDataflowAnalysis(CFCtx, Analysis, InitEnv);
+  EXPECT_FALSE(!Result) << Result.takeError();
+
+  Atom FinalFC = (*Result)[CFCtx.getCFG().getExit().getBlockID()]
+                     ->Env.getFlowConditionToken();
+  std::string Textual;
+  llvm::raw_string_ostream OS(Textual);
+  DACtx.dumpFlowCondition(FinalFC, OS);
+  return Textual;
+}
+
+TEST(DeterminismTest, NestedSwitch) {
+  // Example extracted from real-world code that had wildly nondeterministic
+  // analysis times.
+  // Its flow condition depends on the order we join predecessor blocks.
+  const char *Code = R"cpp(
+    struct Tree;
+    struct Rep {
+      Tree *tree();
+      int length;
+    };
+    struct Tree {
+      int height();
+      Rep *edge(int);
+      int length;
+    };
+    struct RetVal {};
+    int getInt();
+    bool maybe();
+
+    RetVal make(int size);
+    inline RetVal target(int size, Tree& self) {
+      Tree* tree = &self;
+      const int height = self.height();
+      Tree* n1 = tree;
+      Tree* n2 = tree;
+      switch (height) {
+        case 3:
+          tree = tree->edge(0)->tree();
+          if (maybe()) return {};
+          n2 = tree;
+        case 2:
+          tree = tree->edge(0)->tree();
+          n1 = tree;
+          if (maybe()) return {};
+        case 1:
+          tree = tree->edge(0)->tree();
+          if (maybe()) return {};
+        case 0:
+          Rep* edge = tree->edge(0);
+          if (maybe()) return {};
+          int avail = getInt();
+          if (avail == 0) return {};
+          int delta = getInt();
+          RetVal span = {};
+          edge->length += delta;
+          switch (height) {
+            case 3:
+              n1->length += delta;
+            case 2:
+              n1->length += delta;
+            case 1:
+              n1->length += delta;
+            case 0:
+              n1->length += delta;
+              return span;
+          }
+          break;
+      }
+      return make(size);
+    }
+  )cpp";
+
+  std::string Cond = analyzeAndPrintExitCondition(Code);
+  for (unsigned I = 0; I < 10; ++I)
+    EXPECT_EQ(Cond, analyzeAndPrintExitCondition(Code));
+}
+
+TEST(DeterminismTest, ValueMergeOrder) {
+  // Artificial example whose final flow condition variable numbering depends
+  // on the order in which we merge a, b, and c.
+  const char *Code = R"cpp(
+    bool target(bool a, bool b, bool c) {
+      if (a)
+        b = c;
+      else
+        c = b;
+      return a && b && c;
+    }
+  )cpp";
+
+  std::string Cond = analyzeAndPrintExitCondition(Code);
+  for (unsigned I = 0; I < 10; ++I)
+    EXPECT_EQ(Cond, analyzeAndPrintExitCondition(Code));
+}
+
+} // namespace clang::dataflow