Recently some users reported that they observed large increases of
runtime (up to +600% on some translation units) when they upgraded to a
more recent (slightly patched, internal) clang version. Bisection
revealed that the bulk of this increase was probably caused by my
earlier commit bb27d5e5c6b194a1440b8ac4e5ace68d0ee2a849 ("Don't assume
third iteration in loops").
As I evaluated that earlier commit on several open source project, it
turns out that on average it's runtime-neutral (or slightly helpful: it
reduced the total analysis time by 1.5%) but it can cause runtime spikes
on some code: in particular it more than doubled the time to analyze
`tmux` (one of the smaller test projects).
Further profiling and investigation proved that these spikes were caused
by an _increase of analysis scope_ because there was an heuristic that
placed functions on a "don't inline this" blacklist if they reached the
`-analyzer-max-loop` limit (anywhere, on any one execution path) --
which became significantly rarer when my commit ensured the analyzer no
longer "just assumes" four iterations. (With more inlining significantly
more entry points use up their allocated budgets, which leads to the
increased runtime.)
I feel that this heuristic for the "don't inline" blacklist is
unjustified and arbitrary, because reaching the "retry without inlining"
limit on one path does not imply that inlining the function won't be
valuable on other paths -- so I hope that we can eventually replace it
with more "natural" limits of the analysis scope.
However, the runtime increases are annoying for the users whose project
is affected, so I created this quick workaround commit that approximates
the "don't inline" blacklist effects of ambiguous loops (where the
analyzer doesn't understand the loop condition) without fully reverting
the "Don't assume third iteration" commit (to avoid reintroducing the
false positives that were eliminated by it).
Investigating this issue was a team effort: I'm grateful to Endre Fülöp
(gamesh411) who did the bisection and shared his time measurement setup,
and Gábor Tóthvári (tigbr) who helped me in profiling.
This commit ensures that if the loop condition is opaque (the analyzer
cannot determine whether it's true or false) and there were at least two
iterations, then the analyzer doesn't make the unjustified assumption
that it can enter yet another iteration.
Note that the presence of a loop suggests that the developer thought
that two iterations can happen (otherwise an `if` would've been
sufficient), but it does not imply that the developer expected three or
four iterations -- and in fact there are many false positives where a
loop iterates over a two-element (or three-element) data structure, but
the analyzer cannot understand the loop condition and blindly assumes
that there may be three or more iterations. (In particular, analyzing
the FFMPEG project produces 100+ such false positives.)
Moreover, this provides some performance improvements in the sense that
the analyzer won't waste time on traversing the execution paths with 3
or 4 iterations in a loop (which are very similar to the paths with 2
iterations) and therefore will be able to traverse more branches
elsewhere on the `ExplodedGraph`.
This logic is disabled if the user enables the widen-loops analyzer
option (which is disabled by default), because the "simulate one final
iteration after the invalidation" execution path would be suppressed by
the "exit the loop if the loop condition is opaque and there were at
least two iterations" logic. If we want to support loop widening, we
would need to create a follow-up commit which ensures that it "plays
nicely" with this logic.
StaticAnalyzer didn't check if the variable is declared in
`CompoundStmt` under `SwitchStmt`, which make static analyzer reach root
without finding the declaration.
Fixes#68819
---------
Co-authored-by: Balazs Benics <benicsbalazs@gmail.com>
When loop counter is a function parameter "isPossiblyEscaped" will not find
the variable declaration which lead to hitting "llvm_unreachable".
Parameters of reference type should be escaped like global variables;
otherwise treat them as unescaped.
Patch by Abbas Sabra!
Differential Revision: https://reviews.llvm.org/D80171
Summary:
It allows discriminating between stack frames of the same call that is
called multiple times in a loop.
Thanks to Artem Dergachev for the great idea!
Reviewed By: NoQ
Tags: #clang
Differential Revision: https://reviews.llvm.org/D65587
llvm-svn: 367608
Summary:
Since Z3 tests have been not been running [1] some tests needed to be
updated. I also added a regression test for [1].
[1] https://reviews.llvm.org/D47722
Reviewers: george.karpenkov, NoQ, ddcc
Reviewed By: george.karpenkov
Subscribers: mikhail.ramalho, dcoughlin, xazax.hun, szepet, zzheng, a.sidorin, cfe-commits
Differential Revision: https://reviews.llvm.org/D47726
llvm-svn: 334067
Summary:
The original implementation in the `LoopUnrolling.cpp` didn't consider the case where the counter is unsigned. This case is only handled in `simpleCondition()`, but this is not enough, we also need to deal with the unsinged counter with the counter initialization.
Since `IntegerLiteral` is `signed`, there is a `ImplicitCastExpr<IntegralCast>` in `unsigned counter = IntergerLiteral`. This patch add the `ignoringParenImpCasts()` in the `IntegerLiteral` matcher.
Reviewers: szepet, a.sidorin, NoQ, george.karpenkov
Reviewed By: szepet, george.karpenkov
Subscribers: xazax.hun, rnkovacs, cfe-commits, MTC
Differential Revision: https://reviews.llvm.org/D45086
llvm-svn: 328919
Extended the matched assignment operators when checking for bound changes in a body of the loop by using the freshly added isAssignmentOperator matcher.
This covers all the (current) possible assignments, tests added as well.
Differential Revision: https://reviews.llvm.org/D38921
llvm-svn: 328619
The loop unrolling feature aims to track the maximum possible steps a loop can
make. In order to implement this, it investigates the initial value of the
counter variable and the bound number. (It has to be known.)
These numbers are used as llvm::APInts, however, it was not checked if their
bitwidths are the same which lead to some crashes.
This revision solves this problem by extending the "shorter" one (to the length
of the "longer" one).
For the detailed bug report, see: https://bugs.llvm.org/show_bug.cgi?id=34943
Differential Revision: https://reviews.llvm.org/D38922
llvm-svn: 316830
This way the unrolling can be restricted for loops which will take at most a
given number of steps. It is defined as 128 in this patch and it seems to have
a good number for that purpose.
Differential Revision: https://reviews.llvm.org/D37181
llvm-svn: 311883
Added check if the execution of the last step of the given unrolled loop has
generated more branches. If yes, than treat it as a normal (non-unrolled) loop
in the remaining part of the analysis.
Differential Revision: https://reviews.llvm.org/D36962
llvm-svn: 311881
1. The LoopUnrolling feature needs the LoopExit included in the CFG so added this
dependency via the config options
2. The LoopExit element can be encountered even if we haven't encountered the
block of the corresponding LoopStmt. So the asserts were not right.
3. If we are caching out the Node then we get a nullptr from generateNode which
case was not handled.
Differential Revision: https://reviews.llvm.org/D37103
llvm-svn: 311880
The LoopExit CFG information provides the opportunity to not mark the loops but
having a stack which tracks if a loop is unrolled or not. So in case of
simulating a loop we just add it and the information if it meets the
requirements to be unrolled to the top of the stack.
Differential Revision: https://reviews.llvm.org/D35684
llvm-svn: 311346
Adding escape check for the counter variable of the loop.
It is achieved by jumping back on the ExplodedGraph to its declStmt.
Differential Revision: https://reviews.llvm.org/D35657
llvm-svn: 311234
This feature allows the analyzer to consider loops to completely unroll.
New requirements/rules (for unrolling) can be added easily via ASTMatchers.
Right now it is hidden behind a flag, the aim is to find the correct heuristic
and create a solution which results higher coverage % and more precise
analysis, thus can be enabled by default.
Right now the blocks which belong to an unrolled loop are marked by the
LoopVisitor which adds them to the ProgramState.
Then whenever we encounter a CFGBlock in the processCFGBlockEntrance which is
marked then we skip its investigating. That means, it won't be considered to
be visited more than the maximal bound for visiting since it won't be checked.
llvm-svn: 309006
