This is an archive of the discontinued LLVM Phabricator instance.

[Analyzer][Core] Better simplification in SimpleSValBuilder::evalBinOpNN
ClosedPublic

Authored by martong on Nov 12 2021, 4:06 AM.

Details

Summary

Make the SValBuilder capable to simplify existing
SVals based on a newly added constraints when evaluating a BinOp.

Before this patch, we called simplify only in some edge cases.
However, we can and should investigate the constraints in all cases.

Diff Detail

Event Timeline

martong created this revision.Nov 12 2021, 4:06 AM
martong requested review of this revision.Nov 12 2021, 4:06 AM
Herald added a project: Restricted Project. · View Herald TranscriptNov 12 2021, 4:06 AM
Herald added a subscriber: cfe-commits. · View Herald Transcript
steakhal added inline comments.Nov 12 2021, 6:06 AM
clang/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp
378

It seems like you simplify the rhs as well. Could we have a test for that?

clang/test/Analysis/svalbuilder-simplify-in-evalbinop.cpp
14

Please declare x in this statement.

martong marked 2 inline comments as done.Nov 23 2021, 6:26 AM

I'm attaching the coverage of the new test file for the related change:

375             :   // Constraints may have changed since the creation of a bound SVal. Check if
376             :   // the values can be simplified based on those new constraints.
377          12 :   SVal simplifiedLhs = simplifySVal(state, lhs);
378          12 :   SVal simplifiedRhs = simplifySVal(state, rhs);
379          12 :   if (auto simplifiedLhsAsNonLoc = simplifiedLhs.getAs<NonLoc>())
380          12 :     lhs = *simplifiedLhsAsNonLoc;
381          12 :   if (auto simplifiedRhsAsNonLoc = simplifiedRhs.getAs<NonLoc>())
382          12 :     rhs = *simplifiedRhsAsNonLoc;
383             :
clang/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp
378

Ok, I've added a new test case and reworked the existing a bit.

martong updated this revision to Diff 389186.Nov 23 2021, 6:26 AM
martong marked an inline comment as done.
  • Add new test case
steakhal accepted this revision.Nov 23 2021, 7:17 AM

Awesome!

This revision is now accepted and ready to land.Nov 23 2021, 7:17 AM
This revision was landed with ongoing or failed builds.Nov 23 2021, 7:45 AM
This revision was automatically updated to reflect the committed changes.

I'm attaching the coverage of the new test file for the related change:

375             :   // Constraints may have changed since the creation of a bound SVal. Check if
376             :   // the values can be simplified based on those new constraints.
377          12 :   SVal simplifiedLhs = simplifySVal(state, lhs);
378          12 :   SVal simplifiedRhs = simplifySVal(state, rhs);
379          12 :   if (auto simplifiedLhsAsNonLoc = simplifiedLhs.getAs<NonLoc>())
380          12 :     lhs = *simplifiedLhsAsNonLoc;
381          12 :   if (auto simplifiedRhsAsNonLoc = simplifiedRhs.getAs<NonLoc>())
382          12 :     rhs = *simplifiedRhsAsNonLoc;
383             :
bjope added a subscriber: bjope.Nov 26 2021, 10:24 AM

This seem to cause some weird results.

Given this input:

bar(short k) {
  k++;
  for (short f = 0; f < k; f++)
    ;
  (long)k << 16;
}

we get

> clang  --analyze --target=x86_64 'bbi-63538.c'
bbi-63538.c:5:11: warning: The result of the left shift is undefined due to shifting '1' by '16', which is unrepresentable in the unsigned version of the return type 'long' [core.UndefinedBinaryOperatorResult]
  (long)k << 16;
  ~~~~~~~ ^
bbi-63538.c:5:11: warning: The result of the left shift is undefined due to shifting '2' by '16', which is unrepresentable in the unsigned version of the return type 'long' [core.UndefinedBinaryOperatorResult]
  (long)k << 16;
  ~~~~~~~ ^
bbi-63538.c:5:11: warning: The result of the left shift is undefined due to shifting '3' by '16', which is unrepresentable in the unsigned version of the return type 'long' [core.UndefinedBinaryOperatorResult]
  (long)k << 16;
  ~~~~~~~ ^
3 warnings generated.

This seem to cause some weird results.

Given this input:

bar(short k) {
  k++;
  for (short f = 0; f < k; f++)
    ;
  (long)k << 16;
}

we get

> clang  --analyze --target=x86_64 'bbi-63538.c'
bbi-63538.c:5:11: warning: The result of the left shift is undefined due to shifting '1' by '16', which is unrepresentable in the unsigned version of the return type 'long' [core.UndefinedBinaryOperatorResult]
  (long)k << 16;
  ~~~~~~~ ^
bbi-63538.c:5:11: warning: The result of the left shift is undefined due to shifting '2' by '16', which is unrepresentable in the unsigned version of the return type 'long' [core.UndefinedBinaryOperatorResult]
  (long)k << 16;
  ~~~~~~~ ^
bbi-63538.c:5:11: warning: The result of the left shift is undefined due to shifting '3' by '16', which is unrepresentable in the unsigned version of the return type 'long' [core.UndefinedBinaryOperatorResult]
  (long)k << 16;
  ~~~~~~~ ^
3 warnings generated.

Good catch @bjope !
Here is an example without the loop: https://godbolt.org/z/z3rqMz4bs
We'll have a closer look.

dstenb added a subscriber: dstenb.Nov 29 2021, 4:21 AM

Here is a smaller reproducer:

void bar(short k) {
  ++k;             // k1 = k0 + 1
  assert(k == 1);  // k1 == 1 --> k0 == 0
  (long)k << 16;   // k0 + 1 <<  16
}

And the explanation is the following. With this patch, when the analyzer evaluates the (long)k << 16 expression then it can properly deduce the value of k being 1. However, it was not possible in the baseline. Since we do not model neither promotion nor explicit casts we get the false positive report. This issue highlights the importance of the patch stack to implement the modeling of casts (starting with https://reviews.llvm.org/D99797).

steakhal added inline comments.Dec 2 2021, 2:24 PM
clang/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp
372

@martong, you simplified the operands, but you overwrite only the lhs and rhs. Shouldnt you overwite these as well?
What is the purpose of these variables, do you know?

martong added inline comments.Dec 3 2021, 12:41 AM
clang/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp
372

@martong, you simplified the operands, but you overwrite only the lhs and rhs. Shouldnt you overwite these as well?
What is the purpose of these variables, do you know?

They are used exclusively to create SymExprs with makeSymExprValNN when both lhs and rhs are symbols. If we were to simplify the Input variables then it might happen that we end up with a non symbol (i.e. a concrete int) and then makeSymExprValNN would fail miserably (would assert I guess).

steakhal added inline comments.Dec 3 2021, 1:42 AM
clang/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp
372

I see. Although, it still seems suboptimal.