This is an archive of the discontinued LLVM Phabricator instance.

[analyzer][Bugfix/improvement] Fix for PR16833
ClosedPublic

Authored by a.sidorin on Aug 28 2014, 7:58 AM.

Diff Detail

Repository
rL LLVM

Event Timeline

a.sidorin updated this revision to Diff 13036.Aug 28 2014, 7:58 AM
a.sidorin retitled this revision from to [analyzer][Bugfix/improvement] Fix for PR16833.
a.sidorin updated this object.
a.sidorin edited the test plan for this revision. (Show Details)
a.sidorin added a subscriber: Unknown Object (MLST).
a.sidorin updated this revision to Diff 14102.Sep 26 2014, 4:40 AM

Remove debug output; fix handling of Unknown values.

jordan_rose edited edge metadata.Oct 7 2014, 3:16 PM

Sorry it's taken a while to get back to this. I still have a few concerns here (see inline comments), but overall I think this approach is all right. Please add several more tests, though, showing that we're actually modeling this correctly, and including cases where we take the case and cases where we don't.

lib/StaticAnalyzer/Core/ExprEngine.cpp
1675 ↗(On Diff #14102)
1681 ↗(On Diff #14102)

This comment is no longer quite correct; the "assume" part has already been done in assumeBoundDual.

1691 ↗(On Diff #14102)

I don't think this break is correct. Cases are not guaranteed to be in order.

lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
84–85 ↗(On Diff #14102)

Nitpick: please include periods ('.') in your doc comments.

88–89 ↗(On Diff #14102)

You might as well use a C++11 for-each loop here.

324–327 ↗(On Diff #14102)

Please follow the LLVM naming conventions (capital letters, here and elsewhere) and put the & next to the variable name.

604–605 ↗(On Diff #14102)

These are expensive operations. Is it possible to do this at a lower level? Or are there good reasons to do this extra work?

One reason I'm not so happy with this is that some day we could have constraints on one symbol affect another symbol, but this doesn't preserve that. Then again, neither would a lower-level solution.

Thank you Jordan. I have fixed some issues (will post later) but I left some questions in replies.

a.sidorin added inline comments.Oct 8 2014, 6:49 AM
lib/StaticAnalyzer/Core/ExprEngine.cpp
1691 ↗(On Diff #14102)

Does the order really affect this code? The fact that DefaultSt is null means that all possible cases for switch were already covered (range-by-range), there is nothing left to consider and we can break out of loop. Or am I missed something?

lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
604–605 ↗(On Diff #14102)

Jordan, could you explain what do you mean here?
If you mean removing of creation of new states (creating ranges only), that could be done easily.
But it seems that you mean something else that I cannot understand correctly.
BTW, does the code in previous function need correction too?

a.sidorin updated this revision to Diff 14575.Oct 8 2014, 7:16 AM
a.sidorin edited edge metadata.

Some review issues were fixed.

jordan_rose added inline comments.Oct 8 2014, 9:30 AM
lib/StaticAnalyzer/Core/ExprEngine.cpp
1691 ↗(On Diff #14102)

Hm, that's true—that means a case matched definitively. Okay, I stand corrected.

lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
604–605 ↗(On Diff #14102)

The creation of new states is the expensive part. I'm kind of okay with the previous function doing it because it keeps things simple, it does exactly what it's specified to do, and it only has one intermediate state. (But yes, avoiding that would be nice if it can still be done tidily.)

For the second, I guess I was concerned about a hypothetical constraint manager that can handle things like this:

Given: ($x * 2) < 20 - we do handle this today, opaquely
Assume: $x outside of (0, 10)
Then: ($x * 2) < 0

Exactly what $x is is still not known because the analyzer operates under -fwrapv semantics. But we could make the above assumption about ($x * 2).

That said, we don't do anything like that today, and this is within RangeConstraintManager, not a general-purpose implementation in ConstraintManager or SimpleConstraintManager. So maybe this is all right, though I still think it would be a good idea to do it at the RangeSet level rather than the ProgramState level.

a.sidorin updated this revision to Diff 14641.Oct 9 2014, 2:58 AM

Remove creation of new states; add two more tests.

Oh, that's a nice way to refactor RangeConstraintManager::assumeSymLT. Now I'm wondering if it makes sense to do the same for RangeConstraintManager::assumeSymInBound. What do you think?

I discussed this offline with Anna and Ted and one other thing that came up was that this is very specifically operating on inclusive bounds. Now, the feature is motivated by the GNU switch extension, so it makes sense to do that, but then it also makes sense to make sure that's very clear for anyone who might want to use the same interface for something else in the future. How about naming it as such?

ProgramState::assumeWithinInclusiveRange
SimpleConstraintManager::assumeSymbolWithinInclusiveRange
RangeConstraintManager::assumeSymbolOutOfInclusiveRange

etc.

a.sidorin updated this revision to Diff 15026.Oct 16 2014, 10:22 AM

Thank you Jordan. I have refactored assumeSymInBound. Does it look better?

a.sidorin updated this revision to Diff 15030.Oct 16 2014, 11:13 AM

Give new functions more informative names; add entry in ProgramState.

jordan_rose added inline comments.Oct 16 2014, 12:57 PM
lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
610–614 ↗(On Diff #15030)

Unfortunately this logic isn't correct—assumeSymGE does a lot more than this to account for From and To being the min or max values of the symbol type, or completely outside the range of the symbol. I'd be more comfortable with factoring out assumeSymGE into getSymGERange, like you did with assumeSymGT. Or just going back to the simple form from before.

lib/StaticAnalyzer/Core/SimpleConstraintManager.cpp
215–220 ↗(On Diff #15030)

I believe this ignores the case where the bounds have a different type, and APSInt will assert. I don't know if this can happen in the analyzer, but if you don't want to worry about it for now it at least deserves a comment and possibly an explicit assertion.

a.sidorin updated this revision to Diff 15075.Oct 17 2014, 7:28 AM

Add an assertion; an another attempt to refactor RangeConstraintManager::assumeSymbolWithinInclusiveRange.

a.sidorin updated this revision to Diff 15076.Oct 17 2014, 7:37 AM

Constantify a function parameter.

I guess the regular pings didn't work, so it was worth trying the gentle one? Sorry!

This seems mostly ready to me, but I still have a few comments.

lib/StaticAnalyzer/Core/ExprEngine.cpp
1646–1650 ↗(On Diff #15076)

What's the purpose of this? As I understand it, a switch condition value will never be reused in later states, so there's no point in adding constraints to it unless it's already symbolic.

(And not bothering to do this would remove the need to pass the NodeBuilderContext through.)

lib/StaticAnalyzer/Core/SimpleConstraintManager.cpp
199–200 ↗(On Diff #15076)

Will this ever return a null symbol? Maybe add an assertion?

215–220 ↗(On Diff #15076)

This is still relevant.

test/Analysis/switch-case.c
1 ↗(On Diff #15076)

All tests should include the "core" checkers. At some point we'll probably make that implicit, but for now please add that to the -analyzer-checker list.

24–25 ↗(On Diff #15076)

Can you include at least one more check here: clang_analyzer_eval(t > 2)? (Which should be unknown.)

122 ↗(On Diff #15076)

Typo: "Brach"

Thank you for reply, Jordan.

I guess the regular pings didn't work, so it was worth trying the gentle one? Sorry!

And it worked :)

I'll fix the issues you pointed.

a.sidorin added inline comments.Aug 16 2015, 3:35 AM
lib/StaticAnalyzer/Core/SimpleConstraintManager.cpp
215–220 ↗(On Diff #15076)

Both types are equal for CaseStmt. But I'll check this code anyway because I found an interesting issue in CFG for SwitchStmt and I'm still investigating it.

a.sidorin updated this revision to Diff 32293.Aug 17 2015, 6:25 AM
  • Fix review notes
  • Add some more tests
  • Add a fix and a test for incorrect pruning of trivially unreachable case statements in CFG for SwitchStmt (accidentially found while writing a test).
a.sidorin updated this revision to Diff 32664.Aug 20 2015, 1:05 AM
a.sidorin marked an inline comment as done.

Remove duplicating assertion.

a.sidorin marked 8 inline comments as done.Aug 20 2015, 1:09 AM
jordan_rose accepted this revision.Sep 15 2015, 9:39 AM
jordan_rose edited edge metadata.

Thanks for all the changes. This looks good to me! (And good catch for the constant expression case.)

This revision is now accepted and ready to land.Sep 15 2015, 9:39 AM

Folks, could someone commit this for us?

I will commit. Thanks!

This revision was automatically updated to reflect the committed changes.