[clang][dataflow] Unsoundly treat "Unknown" as "Equivalent" in widening.

[ymandel]

Summary

This change makes widening act the same as equivalence checking. When the
analysis does not provide an answer regarding the equivalence of two distinct
values, the framework treats them as equivalent. This is an unsound choice that
enables convergence.

[mboehme]

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

53

Did you mean "hack"?

If you did indeed mean "hook" -- I think it's not strictly speaking a hook, as there's no way to change the behavior here (i.e. install a different handler). Maybe just "this function enables unsoundness..."?

[ymandel]

fix typo

[ymandel]

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

53

yes, "hack". Good catch. :)

[ymandel]

Gabor -- do you want a chance to review (given that it's a non-trivial change to the infrastructure)?

[xazax.hun]

Sorry for the late review. This looks good to me, but I hope we will be able to undo it soon :)

[ymandel]

In D159355#4640054, @xazax.hun wrote:

Sorry for the late review. This looks good to me, but I hope we will be able to undo it soon :)

Thanks! Np, and agreed. I think we have a clear path towards dropping the unsoundness altogether. Up next. :)

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

 #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 {
 namespace dataflow {
 
 // FIXME: convert these to parameters of the analysis or environment. Current
 // settings have been experimentaly validated, but only for a particular
 // analysis.
 static constexpr int MaxCompositeValueDepth = 3;
 static constexpr int MaxCompositeValueSize = 1000;
 
 /// Returns a map consisting of key-value entries that are present in both maps.
 template <typename K, typename V>
 llvm::DenseMap<K, V> intersectDenseMaps(const llvm::DenseMap<K, V> &Map1,
                                         const llvm::DenseMap<K, V> &Map2) {
   llvm::DenseMap<K, V> Result;
   for (auto &Entry : Map1) {
     auto It = Map2.find(Entry.first);
     if (It != Map2.end() && Entry.second == It->second)
       Result.insert({Entry.first, Entry.second});
   }
   return Result;
 }
 
+// Whether to consider equivalent two values with an unknown relation.
+//
+// FIXME: this function is a hack enabling unsoundness to support
+// convergence. Once we have widening support for the reference/pointer and
+// struct built-in models, this should be unconditionally `false` (and inlined
+// as such at its call sites).
+static bool equateUnknownValues(Value::Kind K) {
+  switch (K) {
+  case Value::Kind::Integer:
+  case Value::Kind::Pointer:
+  case Value::Kind::Record:
+    return true;
+  default:
+    return false;
+  }
+}
+
 static bool compareDistinctValues(QualType Type, Value &Val1,
                                   const Environment &Env1, Value &Val2,
                                   const Environment &Env2,
                                   Environment::ValueModel &Model) {
   // Note: Potentially costly, but, for booleans, we could check whether both
   // can be proven equivalent in their respective environments.
 
   // FIXME: move the reference/pointers logic from `areEquivalentValues` to here
   // and implement separate, join/widen specific handling for
   // reference/pointers.
   switch (Model.compare(Type, Val1, Env1, Val2, Env2)) {
   case ComparisonResult::Same:
     return true;
   case ComparisonResult::Different:
     return false;
   case ComparisonResult::Unknown:
-    switch (Val1.getKind()) {
-    case Value::Kind::Integer:
-    case Value::Kind::Pointer:
-    case Value::Kind::Record:
-      // FIXME: this choice intentionally introduces unsoundness to allow
-      // for convergence. Once we have widening support for the
-      // reference/pointer and struct built-in models, this should be
-      // `false`.
-      return true;
-    default:
-      return false;
-    }
+    return equateUnknownValues(Val1.getKind());
   }
   llvm_unreachable("All cases covered in switch");
 }
 
 /// Attempts to merge distinct values `Val1` and `Val2` in `Env1` and `Env2`,
 /// respectively, of the same type `Type`. Merging generally produces a single
 /// value that (soundly) approximates the two inputs, although the actual
 /// meaning depends on `Model`.
static Value &widenDistinctValues(QualType Type, Value &Prev,
   }
 
   // FIXME: Add other built-in model widening.
 
   // Custom-model widening.
   if (auto *W = Model.widen(Type, Prev, PrevEnv, Current, CurrentEnv))
     return *W;
 
-  // Default of widening is a no-op: leave the current value unchanged.
-  return Current;
+  return equateUnknownValues(Prev.getKind()) ? Prev : Current;
 }
 
 // Returns whether the values in `Map1` and `Map2` compare equal for those
 // keys that `Map1` and `Map2` have in common.
 template <typename Key>
 bool compareKeyToValueMaps(const llvm::MapVector<Key, Value *> &Map1,
                            const llvm::MapVector<Key, Value *> &Map2,
                            const Environment &Env1, const Environment &Env2,

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

void target(int i1, int i2) {
         (void)*p;
         if (some_condition())
           p = &i1;
         else
           p = &i2;
       }
     }
   )cc";
-  // FIXME: Implement pointer value widening to make analysis converge.
-  ASSERT_THAT_ERROR(
-      checkDataflowWithNoopAnalysis(Code),
-      llvm::FailedWithMessage("maximum number of iterations reached"));
+  ASSERT_THAT_ERROR(checkDataflowWithNoopAnalysis(Code), llvm::Succeeded());
 }
 
 TEST(TransferTest, LoopDereferencingChangingRecordPointerConverges) {
   std::string Code = R"cc(
     struct Lookup {
       int x;
     };
 
     bool some_condition();
 
     void target(Lookup l1, Lookup l2) {
       Lookup *l = &l1;
       while (true) {
         (void)l->x;
         if (some_condition())
           l = &l1;
         else
           l = &l2;
       }
     }
   )cc";
-  // FIXME: Implement pointer value widening to make analysis converge.
-  ASSERT_THAT_ERROR(
-      checkDataflowWithNoopAnalysis(Code),
-      llvm::FailedWithMessage("maximum number of iterations reached"));
+  ASSERT_THAT_ERROR(checkDataflowWithNoopAnalysis(Code), llvm::Succeeded());
 }
 
 TEST(TransferTest, DoesNotCrashOnUnionThisExpr) {
   std::string Code = R"(
     union Union {
       int A;
       float B;
     };