slow static analyzer performance with if-else chains

[firewave]

#include <string>

std::string replaceEscapeSequences(const std::string &source)
{
    std::string result;
    for (std::size_t i = 0; i < source.size(); ++i) {
        if (source[i] != '\\' || i + 1 >= source.size()) {
            result += source[i];
        }
        else {
            ++i;
            if (source[i] == 't') {
                result += '\t';
            } else if (source[i] == 'x')
            {
                std::string value = "0";
                if (i + 1 < source.size() && std::isxdigit(source[i+1])) {
                    value += source[i++ + 1];
                }
                if (i + 1 < source.size() && std::isxdigit(source[i+1])) {
                    value += source[i++ + 1];
                }
                result += static_cast<char>(std::stoi(value, nullptr, 16));
            }
        }
    }
    return result;
}

$ time clang-tidy-20 -checks='-*,clang-analyzer-*' utils.cpp
1 warning generated.
Suppressed 1 warnings (1 with check filters).

real    0m4.272s
user    0m3.984s
sys     0m0.266s

This has been reduced from https://github.com/danmar/cppcheck/blob/main/lib/utils.cpp. The total time of the whole file is about 10 seconds and the code above accounts for about half of that.

Any further reduction cuts the analysis time by a third or in half.

[llvmbot]

@llvm/issue-subscribers-clang-static-analyzer

Author: Oliver Stöneberg (firewave)

```cpp #include <string>

std::string replaceEscapeSequences(const std::string &source)
{
std::string result;
for (std::size_t i = 0; i < source.size(); ++i) {
if (source[i] != '\' || i + 1 >= source.size()) {
result += source[i];
}
else {
++i;
if (source[i] == 't') {
result += '\t';
} else if (source[i] == 'x')
{
std::string value = "0";
if (i + 1 < source.size() && std::isxdigit(source[i+1])) {
value += source[i++ + 1];
}
if (i + 1 < source.size() && std::isxdigit(source[i+1])) {
value += source[i++ + 1];
}
result += static_cast<char>(std::stoi(value, nullptr, 16));
}
}
}
return result;
}

$ time clang-tidy-20 -checks='-,clang-analyzer-' utils.cpp
1 warning generated.
Suppressed 1 warnings (1 with check filters).

real 0m4.272s
user 0m3.984s
sys 0m0.266s

This has been reduced from https://github.com/danmar/cppcheck/blob/main/lib/utils.cpp. The total time of the whole file is about 10 seconds and the code above accounts for about half of that.

Any further reduction cuts the analysis time by a third or in half.
</details>

[haoNoQ]

Yes, that's just the nature of our analysis algorithm. We actually explore every combination of if-statements on every iteration of the loop, up to a certain limit. We emit different bugs we find on each execution path we explore this way, independently of each other.

This allows us to find bugs on execution paths that were never covered by runtime tests, which is one of the major reasons why static analysis is a useful addition to your software quality toolkit.

Our deterministic budget limit makes sure that we don't hang for too long. We're also clever about the order in which we explore the branches to get the most out of the limited budget. But generally, yes, the static analyzer can be slower than the compiler because of that, and this is expected.

[firewave]

I do understand how data/value flow works (in Cppcheck if-else chains are about the biggest performance issue we are have to deal with at the moment).

But in this case it seems a bit excessive and possible some hot spots could be identified.

Example (sorry for not providing it initially):
If I replace static_cast<char>(std::stoi(value, nullptr, 16)) with value the analysis time drops to just a third:

real    0m1.453s
user    0m1.281s
sys     0m0.141s

[steakhal]

I had a look at the flamegraphs, and nothing sticks out.
Here is when we use value, (the quick variant):

Here is when we use static_cast<char>(std::stoi(value, nullptr, 16)) (the slow variant):

While highlighting frames called VisitCast, to demonstrate that we have more time spent in casts when we have a static_cast there - which makes sense.

One would need to look at the exploded graph to find what blows up and when - which I can't tell from only looking at the flamegraphs.