This is an archive of the discontinued LLVM Phabricator instance.

[analyzer] Improve SVal cast from integer to bool using known RangeSet
AbandonedPublic

Authored by ASDenysPetrov on Mar 3 2021, 10:08 AM.

Details

Summary

Improve SValBuilder::evalCast function in a part of integer to bool cast. Сonvert known SymbolVal RangeSet to ConcreteInt if possible.

Diff Detail

Event Timeline

ASDenysPetrov created this revision.Mar 3 2021, 10:08 AM
ASDenysPetrov requested review of this revision.Mar 3 2021, 10:08 AM
NoQ added inline comments.Mar 3 2021, 3:46 PM
clang/lib/StaticAnalyzer/Core/SValBuilder.cpp
877–879

What was wrong with State->assume(V)? Why make a new function? Is this for optimization only?

Rebased on main.

@NoQ Thanks for your comment.

clang/lib/StaticAnalyzer/Core/SValBuilder.cpp
877–879

Yes, it's created just for avoiding unnecessary work. You are right. I found an appropriate function ProgramState::isNull. I'll replace by it.

Updated due to discussion.

NoQ accepted this revision.Mar 9 2021, 1:34 PM

Great, thanks!

I still have concerns about these functions - isNull, isNonNull etc. They do indeed provide a quick test for nullness that doesn't involve constructing a new program state. This test, however, will never be as precise as constructing a new state. It used to be when RangeConstraintManager boiled down to simple range operations but now that it grew much larger (eg., the newly added support for symbolic == and != that involves tracking equivalence classes), there's really no way to tell whether a state is going to be feasible without running the whole machine and observing its emergent behavior, which is what assume() does. On the other hand i still don't see any indication that assume() is noticeably expensive. So i'm really worried that this is a premature optimization that sacrifices correctness for nothing. So i'm in favor of phasing out these functions entirely and converting all code to always use assume(). This may occasionally involve untangling unwanted recursions but i hope that all recursive-ish operations can be isolated within the constraint manager itself (and possibly in checker's evalAssume() which we can hopefully guard against with runtime assertions).

This revision is now accepted and ready to land.Mar 9 2021, 1:34 PM

I would suggest not merging this patch.

Circumventing the assume machinery could cause potential crashes.
By tracking equivalence classes and whatnot, our solver is becoming more and more capable.

Doing a bifurcation, then realizing that the current path is infeasible had caused some trouble in the past (D88019), and
it still can cause crashes RangeConstraintManager infeasible execution path due to EquivalenceClasses.
Reproducing and debugging these is a real headache. And I think there are more bugs like these lurking inside.

If we want to have a chance to tackle all of these for once and all, we need a common entrypoint for querying assumptions.
Thus, I would suggest not providing an extra API.

@NoQ @vsavchenko What's your take on this?

You could probably put these changes into the assume handler, but that would need really careful evaluation.
If you think it's worth the effort, consider taking a few measurements on several projects.

@steakhal I personally don't see any fundamental problems with this patch

clang/lib/StaticAnalyzer/Core/SValBuilder.cpp
879

nit: LLVM coding standards call for variable names starting with upper-case letters.

@steakhal I personally don't see any fundamental problems with this patch

Then, I guess, it should be fine :)

@ASDenysPetrov I think the dependent patch https://reviews.llvm.org/D97296 is too much and contains unnecessary things for this change.

If you could you please incorporate the minimum needed changes from that patch to here then this patch could land.
If I am not mistaken then we need only the below changes:

SVal evalCastKind(ProgramStateRef State, UndefinedVal V, QualType CastTy,
SVal evalCastSubKind(ProgramStateRef State, nonloc::SymbolVal V,
ASDenysPetrov abandoned this revision.Oct 4 2021, 8:17 AM

@ASDenysPetrov I think the dependent patch https://reviews.llvm.org/D97296 is too much and contains unnecessary things for this change.

If you could you please incorporate the minimum needed changes from that patch to here then this patch could land.
If I am not mistaken then we need only the below changes:

SVal evalCastKind(ProgramStateRef State, UndefinedVal V, QualType CastTy,
SVal evalCastSubKind(ProgramStateRef State, nonloc::SymbolVal V,

This patch is an old one. I believe it is already irrelevant and has to be reviewed once again by me as an author, since it were a lot of improvements made for ConstraintManager. Indeed it has a big parent revision, which also need a revision. There was my idea about adding a ProgramState inside evalCast to make symbolic values more transparent for casts. Let me mark it as Abandoned for now. I'll return back to it ASAP. Thank you for attention to this.