[clang][dataflow] Create `Value`s for integer literals.

[mboehme]

Summary

This patch includes a test that fails without the fix.

I discovered that we weren't creating Values for integer literals when, in a
different patch, I tried to overwrite the value of a struct field with a literal
for the purposes of a test and was surprised to find that the struct compared
the same before and after the assignment.

This functionality therefore seems useful at least for tests, but is probably
also useful for actual analysis of code.

[mboehme]

Pre-merge check failures are in a test for the unchecked-optional-access check clang-tidy. The test that's failing is the following from unchecked-optional-access.cpp:

void multiple_unchecked_accesses(absl::optional<int> opt1,
                                 absl::optional<int> opt2) {
  for (int i = 0; i < 10; i++) {
    opt1.value();
    // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: unchecked access to optional
  }
  opt2.value();
  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: unchecked access to optional value
}

Both of the expected diagnostics are not output.

It looks to me as if the values we're now newly producing for integer literals are causing non-convergence of the analysis on the for-loop.

This looks like a pretty serious issue. We would certainly want analysis of a simple loop like this to converge, especially with a small bounded trip count, but even with an unbounded trip count. It looks as if, currently, the analysis is converging merely because we don't generate values for integer literals.

Next step will be to repro this issue with a test in TransferTest.cpp so that I can take a closer look at why we're failing to converge.

[gribozavr2]

In D152813#4420399, @mboehme wrote:

It looks to me as if the values we're now newly producing for integer literals are causing non-convergence of the analysis on the for-loop.

For integer literals specifically, we should be returning the same value for the same literal over multiple loop iterations. And also, ideally, for multiple equal literals, too, so that an integer literal "42", no matter how many times spelled in the program, creates the same symbolic value.

[mboehme]

In D152813#4420445, @gribozavr2 wrote:

In D152813#4420399, @mboehme wrote:

It looks to me as if the values we're now newly producing for integer literals are causing non-convergence of the analysis on the for-loop.

For integer literals specifically, we should be returning the same value for the same literal over multiple loop iterations. And also, ideally, for multiple equal literals, too, so that an integer literal "42", no matter how many times spelled in the program, creates the same symbolic value.

That's true, and I'll modify the patch so that we do this. (I should probably also include a test that checks that 42 == 42 is equivalent to true.)

But even without this, wouldn't we expect the analysis to converge? The way I'm treating integer literals right now, the analysis is in effect "seeing" the example I quoted above like this:

int return_some_random_int();
void multiple_unchecked_accesses(absl::optional<int> opt1,
                                 absl::optional<int> opt2) {
  for (int i = return_some_random_int(); i < return_some_random_int(); i++) {
    opt1.value();
    // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: unchecked access to optional
  }
  opt2.value();
  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: unchecked access to optional value
}

We would expect analysis of this code to converge too -- right? So I think the problem we're seeing here is independent of how we treat integer literals specifically (though I agree the same integer literal should always be represented by the same Value).

[gribozavr2]

In D152813#4420448, @mboehme wrote:

We would expect analysis of this code to converge too -- right?

Yes - but we might need universal top values for that? maybe?

[mboehme]

In D152813#4420471, @gribozavr2 wrote:

In D152813#4420448, @mboehme wrote:

We would expect analysis of this code to converge too -- right?

Yes - but we might need universal top values for that? maybe?

Ah, I see what you mean.

Anyway, I'll look at producing "reproducible" Values for the same integer.

[mboehme]

Always return the same Value for the same integer.

[mboehme]

PTAL

[gribozavr2]

clang/include/clang/Analysis/FlowSensitive/Arena.h

89

Should we be taking the type into account? If not, why not? Please add the type or document why the type isn't tracked.

[xazax.hun]

clang/include/clang/Analysis/FlowSensitive/Arena.h

89

What would happen if we try to create the same value (like 5) but with different bit widths? (E.g., 64 bit integer vs 32 bit integer). I suspect we might end up having the same value twice in our constant pool, which might be fine. Just wanted to double check what is the desired behavior.

[mboehme]

Clarify that integer literals aren't typed.

[mboehme]

clang/include/clang/Analysis/FlowSensitive/Arena.h

89

Should we be taking the type into account? If not, why not? Please add the type or document why the type isn't tracked.

I've clarified that the type isn't tracked but is instead determined by the Expr that the integer literal is associated with. (This is consistent with our treatment of IntegerValues more generally.)

If we want to do constant propagation through integral conversions, this should be done when processing the IntegerCast node. This would, if necessary, produce an integer literal with a different value.

89

What would happen if we try to create the same value (like 5) but with different bit widths? (E.g., 64 bit integer vs 32 bit integer). I suspect we might end up having the same value twice in our constant pool, which might be fine. Just wanted to double check what is the desired behavior.

This isn't a consideration, as integer literals aren't typed (see reply to comment above).

clang/include/clang/Analysis/FlowSensitive/Arena.h

public:
   BoolValue &makeImplies(BoolValue &LHS, BoolValue &RHS);
 
   /// Returns a boolean value that represents `LHS <=> RHS`. Subsequent calls
   /// with the same arguments, regardless of their order, will return the same
   /// result. If the given boolean values represent the same value, the result
   /// will be a value that represents the true boolean literal.
   BoolValue &makeEquals(BoolValue &LHS, BoolValue &RHS);
 
+  /// Returns a symbolic integer value that models an integer literal equal to
+  /// `Value`. These literals are the same every time.
+  /// Integer literals are not typed; the type is determined by the `Expr` that
+  /// an integer literal is associated with.
+  IntegerValue &makeIntLiteral(llvm::APInt Value);
+
   /// Returns a symbolic boolean value that models a boolean literal equal to
   /// `Value`. These literals are the same every time.
   AtomicBoolValue &makeLiteral(bool Value) const {
     return Value ? TrueVal : FalseVal;
   }
 
   /// Creates a fresh flow condition and returns a token that identifies it. The
   /// token can be used to perform various operations on the flow condition such
   /// as adding constraints to it, forking it, joining it with another flow
   /// condition, or checking implications.
   AtomicBoolValue &makeFlowConditionToken() {
     return create<AtomicBoolValue>();
   }
 
 private:
   // Storage for the state of a program.
   std::vector<std::unique_ptr<StorageLocation>> Locs;
   std::vector<std::unique_ptr<Value>> Vals;
 
-  // Indices that are used to avoid recreating the same composite boolean
-  // values.
+  // Indices that are used to avoid recreating the same integer literals and
+  // composite boolean values.
+  llvm::DenseMap<llvm::APInt, IntegerValue *> IntegerLiterals;
   llvm::DenseMap<std::pair<BoolValue *, BoolValue *>, ConjunctionValue *>
       ConjunctionVals;
   llvm::DenseMap<std::pair<BoolValue *, BoolValue *>, DisjunctionValue *>
       DisjunctionVals;
   llvm::DenseMap<BoolValue *, NegationValue *> NegationVals;
   llvm::DenseMap<std::pair<BoolValue *, BoolValue *>, ImplicationValue *>
       ImplicationVals;
   llvm::DenseMap<std::pair<BoolValue *, BoolValue *>, BiconditionalValue *>

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

public:
   /// The analysis context takes ownership of the created object. The object
   /// will be destroyed when the analysis context is destroyed.
   template <typename T, typename... Args>
   std::enable_if_t<std::is_base_of<Value, T>::value, T &>
   create(Args &&...args) {
     return DACtx->arena().create<T>(std::forward<Args>(args)...);
   }
 
+  /// Returns a symbolic integer value that models an integer literal equal to
+  /// `Value`
+  IntegerValue &getIntLiteralValue(llvm::APInt Value) const {
+    return DACtx->arena().makeIntLiteral(Value);
+  }
+
   /// Returns a symbolic boolean value that models a boolean literal equal to
   /// `Value`
   AtomicBoolValue &getBoolLiteralValue(bool Value) const {
     return DACtx->arena().makeLiteral(Value);
   }
 
   /// Returns an atomic boolean value.
   BoolValue &makeAtomicBoolValue() const {

clang/lib/Analysis/FlowSensitive/Arena.cpp

BoolValue &Arena::makeEquals(BoolValue &LHS, BoolValue &RHS) {
 
   auto Res = BiconditionalVals.try_emplace(makeCanonicalBoolValuePair(LHS, RHS),
                                            nullptr);
   if (Res.second)
     Res.first->second = &create<BiconditionalValue>(LHS, RHS);
   return *Res.first->second;
 }
 
+IntegerValue &Arena::makeIntLiteral(llvm::APInt Value) {
+  auto [It, Inserted] = IntegerLiterals.try_emplace(Value, nullptr);
+
+  if (Inserted)
+    It->second = &create<IntegerValue>();
+  return *It->second;
+}
+
 } // namespace clang::dataflow

clang/lib/Analysis/FlowSensitive/Transfer.cpp

if (!CFCtx.isBlockReachable(*BlockIt->getSecond()))
     return nullptr;
   const auto &State = BlockToState[BlockIt->getSecond()->getBlockID()];
   assert(State);
   return &State->Env;
 }
 
 static BoolValue &evaluateBooleanEquality(const Expr &LHS, const Expr &RHS,
                                           Environment &Env) {
-  if (auto *LHSValue = dyn_cast_or_null<BoolValue>(Env.getValueStrict(LHS)))
-    if (auto *RHSValue = dyn_cast_or_null<BoolValue>(Env.getValueStrict(RHS)))
-      return Env.makeIff(*LHSValue, *RHSValue);
+  Value *LHSValue = Env.getValueStrict(LHS);
+  Value *RHSValue = Env.getValueStrict(RHS);
+
+  if (LHSValue == RHSValue)
+    return Env.getBoolLiteralValue(true);
+
+  if (auto *LHSBool = dyn_cast_or_null<BoolValue>(LHSValue))
+    if (auto *RHSBool = dyn_cast_or_null<BoolValue>(RHSValue))
+      return Env.makeIff(*LHSBool, *RHSBool);
 
   return Env.makeAtomicBoolValue();
 }
 
 // Functionally updates `V` such that any instances of `TopBool` are replaced
 // with fresh atomic bools. Note: This implementation assumes that `B` is a
 // tree; if `B` is a DAG, it will lose any sharing between subvalues that was
 // present in the original .
void VisitInitListExpr(const InitListExpr *S) {
     }
     // FIXME: Implement array initialization.
   }
 
   void VisitCXXBoolLiteralExpr(const CXXBoolLiteralExpr *S) {
     Env.setValueStrict(*S, Env.getBoolLiteralValue(S->getValue()));
   }
 
+  void VisitIntegerLiteral(const IntegerLiteral *S) {
+    Env.setValueStrict(*S, Env.getIntLiteralValue(S->getValue()));
+  }
+
   void VisitParenExpr(const ParenExpr *S) {
     // The CFG does not contain `ParenExpr` as top-level statements in basic
     // blocks, however manual traversal to sub-expressions may encounter them.
     // Redirect to the sub-expression.
     auto *SubExpr = S->getSubExpr();
     assert(SubExpr != nullptr);
     Visit(SubExpr);
   }

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

runDataflow(
 
         const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
         ASSERT_THAT(BarDecl, NotNull());
 
         EXPECT_EQ(Env.getValue(*BarDecl), FooVal);
       });
 }
 
+TEST(TransferTest, BinaryOperatorAssignIntegerLiteral) {
+  std::string Code = R"(
+    void target() {
+      int Foo = 1;
+      // [[before]]
+      Foo = 2;
+      // [[after]]
+    }
+  )";
+  runDataflow(
+      Code,
+      [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
+         ASTContext &ASTCtx) {
+        const Environment &Before =
+            getEnvironmentAtAnnotation(Results, "before");
+        const Environment &After = getEnvironmentAtAnnotation(Results, "after");
+
+        const auto &ValBefore =
+            getValueForDecl<IntegerValue>(ASTCtx, Before, "Foo");
+        const auto &ValAfter =
+            getValueForDecl<IntegerValue>(ASTCtx, After, "Foo");
+        EXPECT_NE(&ValBefore, &ValAfter);
+      });
+}
+
 TEST(TransferTest, VarDeclInitAssign) {
   std::string Code = R"(
     void target() {
       int Foo;
       int Bar = Foo;
       // [[p]]
     }
   )";
runDataflow(
         auto &BarValThen = *cast<BoolValue>(EnvThen.getValue(*BarDecl));
         EXPECT_FALSE(EnvThen.flowConditionImplies(BarValThen));
 
         auto &BarValElse = *cast<BoolValue>(EnvElse.getValue(*BarDecl));
         EXPECT_TRUE(EnvElse.flowConditionImplies(BarValElse));
       });
 }
 
+TEST(TransferTest, IntegerLiteralEquality) {
+  std::string Code = R"(
+    void target() {
+      bool equal = (42 == 42);
+      // [[p]]
+    }
+  )";
+  runDataflow(
+      Code,
+      [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
+         ASTContext &ASTCtx) {
+        const Environment &Env = getEnvironmentAtAnnotation(Results, "p");
+
+        auto &Equal = getValueForDecl<BoolValue>(ASTCtx, Env, "equal");
+        EXPECT_TRUE(Env.flowConditionImplies(Equal));
+      });
+}
+
 TEST(TransferTest, CorrelatedBranches) {
   std::string Code = R"(
     void target(bool B, bool C) {
       if (B) {
         return;
       }
       (void)0;
       /*[[p0]]*/