This is an archive of the discontinued LLVM Phabricator instance.

[analyzer] Treat functions without runtime branches as "small".
ClosedPublic

Authored by NoQ on Apr 23 2019, 6:56 PM.

Details

Summary

Currently we always inline functions that have no branches, i.e. have exactly three CFG blocks: ENTRY, some code, EXIT. This makes sense because when there are no branches, it means that there's no exponential complexity introduced by inlining such function. Such functions also don't trigger various fundamental problems with our inlining mechanism, such as the problem of inlined defensive checks.

Sometimes the CFG may contain more blocks, but in practice it still has linear structure because all directions (except, at most, one) of all branches turned out to be unreachable. When this happens, still treat the function as "small".

This is useful, in particular, for dealing with C++17 if constexpr.

Diff Detail

Event Timeline

NoQ created this revision.Apr 23 2019, 6:56 PM
Herald added a project: Restricted Project. · View Herald TranscriptApr 23 2019, 6:56 PM
NoQ edited the summary of this revision. (Show Details)Apr 23 2019, 6:56 PM
NoQ edited the summary of this revision. (Show Details)

Nice! I have no objections (other than the nits) to this! Ill take a second look later, because I really need to play around with CFG a bit to give a definitive LGTM.

clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h
723

Your explanation of state splitting, and early returns and the like could be added here as well :)

clang/lib/Analysis/CFG.cpp
4684

What are the cases for the size being 2 or 1? Empty function? Is a size of 1 even possible? Can we enforce something here with asserts?

4686

Break TODO to new line.

clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp
890

Nice.

clang/test/Analysis/inline-if-constexpr.cpp
16

Aha, we wouldve seen UNKNOWN because the analyzer wouldn't inline these many functions, right? Neat!

clang/unittests/Analysis/CFGTest.cpp
117

What do you mean?

NoQ marked 4 inline comments as done.Apr 24 2019, 2:43 PM
NoQ added inline comments.
clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h
723

This function can be controlled through -analyzer-config, which breaks the explanation. I guess i'll put it inside the body.

clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp
890

Whoops, that was actually accidental.

clang/test/Analysis/inline-if-constexpr.cpp
16

Aha, yup.

NoQ updated this revision to Diff 196733.Apr 25 2019, 3:07 PM
NoQ marked 4 inline comments as done.

Fxd.

clang/lib/Analysis/CFG.cpp
4684

An empty function, i.e. void foo() {}, has two CFG blocks. Every CFG has (by construction) at least an ENTRY and an EXIT, but i don't think this is the right place to introduce such sanity check.

clang/test/Analysis/inline-if-constexpr.cpp
16

Hardcoded the max stack depth count to make this more apparent and prevent the test from not testing anything if it's bumped.

Charusso accepted this revision.Apr 28 2019, 10:54 PM

Great patch! There is only a design problem:
You have negated every isSmall() condition looks like you could write isLarge() instead but there is no connection between these functions.
Could you rename or redesign them? The following would be cool: isLarge() iff !isSmalll and isSmall() iff !isLarge().

This revision is now accepted and ready to land.Apr 28 2019, 10:54 PM
NoQ added a comment.Apr 29 2019, 12:07 PM

Great patch! There is only a design problem:
You have negated every isSmall() condition looks like you could write isLarge() instead but there is no connection between these functions.
Could you rename or redesign them? The following would be cool: isLarge() iff !isSmalll and isSmall() iff !isLarge().

We essentially classify functions into small/medium/large/huge. In this sense !isSmall() may mean medium or large or huge, while isLarge() may mean large or huge.
I guess i'll comment this up.

NoQ updated this revision to Diff 197248.Apr 29 2019, 7:33 PM

Crystallize the isHuge() function and document more stuff.

This revision was automatically updated to reflect the committed changes.

I mean, better late then never, but LGTM :^)