FlameGraph of astutils.cpp using cppcheck version 2.6

[john borland]

I have attched the flamegraph as a svg file and I normally use firefox to view them. Normally I just start looking at large plateaus in the flamegraph. I will put my instructions at the bottom for how I made the flame graph. A Flame Graph https://www.brendangregg.com/flamegraphs.html is mainly just using perf to ask the cpu over and over what it is doing and counting up how many times a stack trace was found. So the wider the bar the more times it was found on the CPU. Looking at this flame graph two function stood out to me ValueFlow::setValues and ForwardTransversal::updateRange. Starting with ValueFlow::setValue I had a couple of questions.
1. Where does the number 4 come from as the loop index?
2. Why are some functions called more than once? I did notice that the first arguments was different.
valueFlowCondition(SymbolicConditionHandler{}, tokenlist, symboldatabase, errorLogger, settings);
valueFlowCondition(SimpleConditionHandler{}, tokenlist, symboldatabase, errorLogger, settings);
valueFlowCondition(IteratorConditionHandler{}, tokenlist, symboldatabase, errorLogger, settings);
valueFlowCondition(ContainerConditionHandler{}, tokenlist, symboldatabase, errorLogger, settings);
3. Does the order of those functions matter?

Here are my instructions for creating the Flamegraph

git clone https://github.com/brendangregg/FlameGraph.git
git clone https://github.com/danmar/cppcheck.git
cd cppcheck/
git checkout tags/2.6 -b 2.6
mkdir Build
cd Build
export CXXFLAGS="-g -fno-omit-frame-pointer"
cmake3 MATCHCOMPILER=YES -DCMAKE_BUILD_TYPE=Release ..
make -j 6 >& build.out.out
perf record -F 99 --output=2.6.out.perf.data -g ./bin/cppcheck check=all ../lib/astutils.cpp &> 2.6.out.out
perf script --input=2.6.out.perf.data > ./2.6.out.perf
../../FlameGraph/stackcollapse-perf.pl ./2.6.out.perf > ./2.6.out.folded
../../FlameGraph/flamegraph.pl ./2.6.out.folded > ./2.6.svg

[Daniel Marjamäki]

I have attched the flamegraph as a svg file and I normally use firefox to view them.

it was very interesting. does this graph say that most of the time in Tokenizer::simplifyTokens1 is spent in ValueFlow::setValues?
I have thought that Tokenizer::simplifyTokenList1 would take quite a lot time also.

[john borland]

So in total there were 8001 stack traces collected
5198 (64.97%) Tokenizer::simplifyTokens1
4987 (62.33%) ValueFlow::setValues
So the difference between those two would be all the other stack traces going through Tokenizer::simplifyTokens1 that didn't contain ValueFlow::setValues which would be 211. So going through ValueFlow::setValues is the dominant path by a lot.

So flamegraphs are really good at showing you the path that takes the most time in your code. I find it gives me alot more context to attack the problem with.

[Daniel Marjamäki]

Ok thanks. I get the feeling that ValueFlow::setValues has increased much in last couple of years. It's good that it has improved and is more capable today. But at the same time we can't use as much cpu as we want. Would it be good to disable some analysis that costs a lot and does not generate enough bang. I think a configuration would be nice so people can have a quick run for general use and somehow a more verbose slow run.

[Daniel Marjamäki]

So flamegraphs are really good at showing you the path that takes the most time in your code

It is pretty intuitive. 👍

The "inclusive" time is very important value however that is not always shown in all measurements. However if it's shown graphically or textually does not matter a lot for me.

[john borland]

I made a few more flame graphs. I went a head and put them in a tgz to save space.
One I wanted to show you what the output from the diff tool looks like. At work I normally have the CI system compair head to the flame graph of the last tagged release. ./FlameGraph/difffolded.pl 2.5.out.folded 2.6.out.folded | ./FlameGraph/flamegraph.pl > diff01.svg

I also included a flame graph of cppcheck v2.5 cppcheck v1.90 I also made one of 2.6 That I called 2.6.c.svg where I put a wrapper function around each version of the valueFlowCondition so I could see how the call stacks where distributed.

6.91 % wrap01 valueFlowCondition(SymbolicConditionHandler{},
23.43% wrap02 valueFlowCondition(SimpleConditionHandler{},
0.29% wrap03 valueFlowCondition(IteratorConditionHandler{},
1.15% wrap04 valueFlowCondition(ContainerConditionHandler{},

So it looks like to me SimpleConditionHandler isn't so simple.

Also made a FlameGraph on my raspberry pi 4 so you could see how well the flame graph matched my intel box.

[Daniel Marjamäki]

1. Where does the number 4 come from as the loop index?

as far as I know we wrote 4 to limit cpu. It might be interesting to have a some more dynamic and configurable behavior here.

Why are some functions called more than once?

Because in each loop the valueflow is extended.. and that provides more opportunities to perform further data flow analysis.

Here is 1 example:

void foo(int a) {
    int x = a; // 2
    if (a == 0) {} // 1
    return 1000 / x; // 3
}

1: cppcheck will see that a might be 0 and performs dataflow for a forwards and backwards.
2: cppcheck will see that assigned value might be 0 and performs forward dataflow analysis for x
3: it is seen that division rhs is 0.

the valueflow functions that are executed only once perform simple analysis that we do not need to repeat. For instance determining the value for hard coded values.

1. Does the order of those functions matter?

Yes it does. Unfortunately the optimal order is different for different functions.
As far as I know we more or less call the functions in some arbitrary order.

[john borland]

You ever think about making a --deep-check that changes that number from 4 to 24? It would be interesting if there was a way to see at which level a an issue was found. It might make for an interesting opinion in the python donate cpu script. Which would probably be useful feedback for someone to look into how to make it more dynamic.

[john borland]

I would say I have a very naive understanding of the inner workings of cppcheck. While looking at ForwardTransversal::updateRange it makes me wonder if any one has ever looked into an encoding scheme to see if it would speed up cppcheck. Strings are still strings. While I'm sure they can make debugging output more intuitive. Lets say if you replaced the following

if = \ti
for = \tf
while = \tw
break = \tb
case = \tc
try = \tt
else = \te
do = \td
assert = \ta
ASSERT = \ta
switch = \ts

If you new the first character was not a \t (The Tab Charterer) it could rule out a lot of the else if cases much faster. While I think the string operations are not this functions bottleneck. I'm just wondering if this has ever been looked at or is it the kind of optimization that cppcheck would prefer to say away from?

Bellow is some code snippets from forwardanalyzer.cpp updateRange function .

Progress updateRange(Token* start, const Token* end, int depth = 20) {

for (Token* tok = start; precedes(tok, end); tok = tok->next()) {
                        //Code was removed
          if (tok->link()) {
                if (tok->str() == "(" && !tok->astOperand2() && tok->isCast()) {
                        //Code was removed
                    continue;
                }
                if (tok->str() == "<") {
                      //Code was removed
                    continue;
                }
            }
            // Evaluate RHS of assignment before LHS
            if (Token* assignTok = assignExpr(tok)) {
                if (updateRecursive(assignTok) == Progress::Break)
                    return Break();
                tok = nextAfterAstRightmostLeaf(assignTok);
                if (!tok)
                    return Break();
            } else if (tok->str() ==  "break") { 
                         //Code was removed
            } else if (Token::Match(tok, "%name% :") || tok->str() == "case") {
                        //Code was removed
            } else if (tok->link() && tok->str() == "}") {
                       //Code was removed
            } else if (tok->isControlFlowKeyword() && Token::Match(tok, "if|while|for (") && Token::simpleMatch(tok->next()->link(), ") {")) {
                     //Code was removed
            } else if (Token::simpleMatch(tok, "try {")) {
                     //Code was removed
            } else if (Token::simpleMatch(tok, "do {")) {
                     //Code was removed
            } else if (Token::Match(tok, "assert|ASSERT (")) {
                    //Code was removed
            } else if (Token::simpleMatch(tok, "switch (")) {
                    //Code was removed
            } else {
                if (updateTok(tok, &next) == Progress::Break)
                    return Break();
                if (next) {
                    if (precedes(next, end))
                        tok = next->previous();
                    else
                        return Break();
                }
            }
            // Prevent infinite recursion
            if (tok->next() == start)
                break;
        }
        return Progress::Continue;
  }

Just wondering?

[john borland]

Looking at while loop condition in ValueFlow::setValues

I was wondering about three approaches in regards to getTotalValues(tokenlist)

1. If it would be better to keep track of the size as things are added to the token``list.
2. Add a flag to the tokenlist that get's marked when something is added and a function to reset the flag at the top of the loop.
3. Change getTotalValues to take a second argument called lastValue;

static std::size_t getTotalValues(TokenList *tokenlist, std::size_t & lastValues)
{
    std::size_t n = 1;
    for (Token *tok = tokenlist->front(); tok; tok = tok->next())
        n += tok->values().size();
     lastValues=n;
    return n;
}

    while (n > 0 && values < getTotalValues(tokenlist,lastValues)) {
        values = lastValues;

Just to see if this has any performances differences.

I like the approach number one the best as it keeps the size information there as that is probably a better thing to uses should the loop need a more dynamic condition to use for termination. To me it would at least stop the walking of the tokenlist twice for every iteration of the loop.

    while (n > 0 && values < getTotalValues(tokenlist)) {
        values = getTotalValues(tokenlist);

I'm mainly wondering if any of these ideas have been explored in the passed and have already been ruled out for one reason or another?

[Paul Fultz]

I dont think we can add a flag to the tokenlist since we dont have a reference to the tokenlist when we add a value. We could instead add an integer to Settings and then setTokenValue can increment this integer when addValue return true. This can then be reset when entering the loop.

[john borland]

I have another naive question. Looking at all the valueFlow functions being called in the while loop in setValues https://github.com/danmar/cppcheck/blob/b9be38aaecaf39f2c9fc7ae6786c6b1eaa40f4e5/lib/valueflow.cpp#L7326

if the call to the valueFlow function doesn't change the size of the token list after it's first call. Is it possible for it to change it on any of the later calls?

[Paul Fultz]

if the call to the valueFlow function doesn't change the size of the token list after it's first call. Is it possible for it to change it on any of the later calls?

Yes, thats the whole point of the loop because other functions may introduce values that a previous function can utilize.

[john borland]

In exploring the code some more I printed out the change in size of the values after every valueflow function call in the while loop. One thing kind of stuck out to me as interesting . I saw this happen with a few files. You can see on the first pass when n = 4 a bunch of values change. Then on the next pass when n =3 the only one to change was valueFlowSubFunction. Then on the next pass when n =2 valueFlowSubFunction changes the size again. While that might be the desired behavior it might make since to try and understand the case better. There maybe away to reduce the number of times the loop is running.

NameOfFile. ,n, change in values after each call.
lib/build/mc_analyzerinfo.cpp:,4,134,0,14,0,0,0,1,27,0,0,0,5,0,0,0,0,0,0,0,0,0,0,1,3,
lib/build/mc_analyzerinfo.cpp:,3,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,
lib/build/mc_analyzerinfo.cpp:,2,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,

The 3 valueflow functions that a appeared the most on the last line showing changes were
42 /69 valueFlowCondition(SimpleConditionHandler
51 /69 valueFlowAfterAssign
62 /69 valueFlowSubFunction
it might be interesting to move valueFlowSubFunction and valueFlowAfterAssign to further down in the list to see if it reduces the number of times the while loop has to run.

[john borland]

I made some pretty printing to hopefully show the two little interesting things I have found. To speed things up I used the compilation database file that was there.
./bin/cppcheck --enable=all --project=./compile_commands.json

I have also attached the output from my pretty printing to hopefully make it easier to look at. Each column after the funtion name is the about that the function changed getTotalValues(tokenlist) by at each iteration of the while loop. I also increased the size of the while loop to 18 just because I wanted to see if anything would need that many tries. Nothing went passed 4 all though one of them should but that is explained more why it didn't by the 2nd interesting thing that I found.

The first one is the valueFlowSubFunction thing.

Checking ./CPPCheck/cppcheck/cli/cppcheckexecutor.cpp ...
Checking ./CPPCheck/cppcheck/cli/cppcheckexecutor.cpp: FILESDIR="/usr/local/share/Cppcheck";NDEBUG=1;__cplusplus=201103L...
01 | ImpossibleValues    |    314 |      0 |      0 |      0 |
02 | SymbolicAbs         |      0 |      0 |      0 |      0 |
03 | Condition_Symbolic  |     43 |      0 |      0 |      0 |
04 | SymbolicInfer       |      0 |      0 |      0 |      0 |
05 | ArrayBool           |      0 |      0 |      0 |      0 |
06 | RightShift          |      0 |      0 |      0 |      0 |
07 | AfterAssign         |      4 |      0 |      0 |      0 |
08 | Condition_Simple    |     62 |      0 |      0 |      0 |
09 | InferCondition      |      0 |      0 |      0 |      0 |
10 | SwitchVariable      |      0 |      0 |      0 |      0 |
11 | ForLoop             |      0 |      0 |      0 |      0 |
12 | SubFunction         |      9 |      1 |      1 |      0 |
13 | FunctionReturn      |      0 |      0 |      0 |      0 |
14 | Lifetime            |      0 |      0 |      0 |      0 |
15 | FunctionDefaultPar  |      2 |      0 |      0 |      0 |
16 | Uninit              |      0 |      0 |      0 |      0 |
17 | UninitPointerAlias  |      0 |      0 |      0 |      0 |
18 | AfterMove           |      0 |      0 |      0 |      0 |
19 | SmartPointer        |      0 |      0 |      0 |      0 |
20 | Iterators           |     39 |      0 |      0 |      0 |
21 | Condition_Iterator  |     12 |      0 |      0 |      0 |
22 | IteratorInfer       |      0 |      0 |      0 |      0 |
23 | ContainerSize       |      9 |      0 |      0 |      0 |
24 | Condition_Container |     41 |      0 |      0 |      0 |
25 | SafeFunctions       |      0 |      0 |      0 |      0 |
VFDepth | 1135 | 1672 |

VFDepth | getTotalValues(tokenlist) before the while loop | getTotalVaules after valueFlowDynamicBufferSize |

List of files that it is doing that on.
./lib/build/mc_analyzerinfo.cpp
./lib/build/mc_pathmatch.cpp
./lib/build/mc_platform.cpp
./lib/build/mc_preprocessor.cpp
./lib/build/mc_settings.cpp
./lib/build/mc_suppressions.cpp
./lib/build/mc_utils.cpp
./CPPCheck/cppcheck/cli/cppcheckexecutor.cpp
./CPPCheck/cppcheck/cli/threadexecutor.cpp
./lib/build/mc_pathmatch.cpp
./CPPCheck/cppcheck/lib/utils.cpp

The second one might be more interesting. I have found a small amount of cases that one valueFlow function reduces the size and another function adds back to the size the same amount so the while loop thinks nothing has been changed.

Checking lib/build/mc_programmemory.cpp ...
Checking lib/build/mc_programmemory.cpp: FILESDIR="/usr/local/share/Cppcheck";NDEBUG=1;__cplusplus=201103L...
01 | ImpossibleValues    |    277 |      0 |      0 | 
02 | SymbolicAbs         |      0 |      0 |      0 | 
03 | Condition_Symbolic  |     46 |      0 |      0 | 
04 | SymbolicInfer       |      0 |      0 |      0 | 
05 | ArrayBool           |      0 |      0 |      0 | 
06 | RightShift          |      0 |      0 |      0 | 
07 | AfterAssign         |     27 |     14 |     -1 | 
08 | Condition_Simple    |    374 |      2 |      1 | 
09 | InferCondition      |      0 |      0 |      0 | 
10 | SwitchVariable      |      0 |      0 |      0 | 
11 | ForLoop             |      0 |      0 |      0 | 
12 | SubFunction         |    175 |      5 |      0 | 
13 | FunctionReturn      |      0 |      0 |      0 | 
14 | Lifetime            |      0 |      0 |      0 | 
15 | FunctionDefaultPar  |      5 |      0 |      0 | 
16 | Uninit              |      4 |      0 |      0 | 
17 | UninitPointerAlias  |      0 |      0 |      0 | 
18 | AfterMove           |      0 |      0 |      0 | 
19 | SmartPointer        |      0 |      0 |      0 | 
20 | Iterators           |     31 |      0 |      0 | 
21 | Condition_Iterator  |     12 |      0 |      0 | 
22 | IteratorInfer       |      0 |      0 |      0 | 
23 | ContainerSize       |      0 |      0 |      0 | 
24 | Condition_Container |     15 |      0 |      0 | 
25 | SafeFunctions       |      0 |      0 |      0 | 
VFDepth | 2596 | 3583 |

The files that it did that on are as followed.
lib/build/mc_programmemory.cpp
lib/build/mc_mathlib.cpp
lib/build/mc_symboldatabase.cpp

[john borland]

In this case I actually commented out all the calls in the while loop except for the one to valueFlowSubFunction. So that you can see that no other function is adding to the work it has to do. So techly the while loop should run only 2 times. Once when it finds some work to do in valueFlowSubFunction and the next time it should one would think be zero.

Checking lib/build/mc_pathmatch.cpp ...
Checking lib/build/mc_pathmatch.cpp: FILESDIR="/usr/local/share/Cppcheck";NDEBUG=1;__cplusplus=201103L...
01 | ImpossibleValues    |      0 |      0 |      0 |      0 | 
02 | SymbolicAbs         |      0 |      0 |      0 |      0 | 
03 | Condition_Symbolic  |      0 |      0 |      0 |      0 | 
04 | SymbolicInfer       |      0 |      0 |      0 |      0 | 
05 | ArrayBool           |      0 |      0 |      0 |      0 | 
06 | RightShift          |      0 |      0 |      0 |      0 | 
07 | AfterAssign         |      0 |      0 |      0 |      0 | 
08 | Condition_Simple    |      0 |      0 |      0 |      0 | 
09 | InferCondition      |      0 |      0 |      0 |      0 | 
10 | SwitchVariable      |      0 |      0 |      0 |      0 | 
11 | ForLoop             |      0 |      0 |      0 |      0 | 
12 | SubFunction         |      5 |      1 |      1 |      0 | 
13 | FunctionReturn      |      0 |      0 |      0 |      0 | 
14 | Lifetime            |      0 |      0 |      0 |      0 | 
15 | FunctionDefaultPar  |      0 |      0 |      0 |      0 | 
16 | Uninit              |      0 |      0 |      0 |      0 | 
17 | UninitPointerAlias  |      0 |      0 |      0 |      0 | 
18 | AfterMove           |      0 |      0 |      0 |      0 | 
19 | SmartPointer        |      0 |      0 |      0 |      0 | 
20 | Iterators           |      0 |      0 |      0 |      0 | 
21 | Condition_Iterator  |      0 |      0 |      0 |      0 | 
22 | IteratorInfer       |      0 |      0 |      0 |      0 | 
23 | ContainerSize       |      0 |      0 |      0 |      0 | 
24 | Condition_Container |      0 |      0 |      0 |      0 | 
25 | SafeFunctions       |      0 |      0 |      0 |      0 | 
VFDepth | 65 | 72 |

I have attached my full output for

./bin/cppcheck --enable=all --project=./compile_commands.json 

And I have also attached an output of pathmatch.cpp with the --debug-normal flag.

./bin/cppcheck --enable=all --debug-normal ../lib/pathmatch.cpp 

I'm trying to better understand what valueFlowSubFunction is doing. So I can try to understand why it can't solve the input on the first pass. Any advice would be helpful.

Thanks.

[Paul Fultz]

So techly the while loop should run only 2 times.

Setting n to 2 will not pass our unit tests.

[john borland]

I guess I'm wondering more about what valueFlowSubFunction is really doing and what case is being generated that it can't solve in the first pass. Looking at my output. It is rare for it to solve it's work in one pass. In the case of ./cppcheck/tools/dmake.cpp it seems to be able to do that. So not in every cases it has work to do. I'm just really trying to better understand what's going on. Are there any other flags that would be useful to turn on or variables I should print out that would given me more information?

Checking ./CPPCheck/cppcheck/tools/dmake.cpp ...
Checking ./CPPCheck/cppcheck/tools/dmake.cpp: FILESDIR="/usr/local/share/Cppcheck";NDEBUG=1;__cplusplus=201103L...
01 | ImpossibleValues    |      0 |      0 | 
02 | SymbolicAbs         |      0 |      0 | 
03 | Condition_Symbolic  |      0 |      0 | 
04 | SymbolicInfer       |      0 |      0 | 
05 | ArrayBool           |      0 |      0 | 
06 | RightShift          |      0 |      0 | 
07 | AfterAssign         |      0 |      0 | 
08 | Condition_Simple    |      0 |      0 | 
09 | InferCondition      |      0 |      0 | 
10 | SwitchVariable      |      0 |      0 | 
11 | ForLoop             |      0 |      0 | 
12 | SubFunction         |     39 |      0 | 
13 | FunctionReturn      |      0 |      0 | 
14 | Lifetime            |      0 |      0 | 
15 | FunctionDefaultPar  |      0 |      0 | 
16 | Uninit              |      0 |      0 | 
17 | UninitPointerAlias  |      0 |      0 | 
18 | AfterMove           |      0 |      0 | 
19 | SmartPointer        |      0 |      0 | 
20 | Iterators           |      0 |      0 | 
21 | Condition_Iterator  |      0 |      0 | 
22 | IteratorInfer       |      0 |      0 | 
23 | ContainerSize       |      0 |      0 | 
24 | Condition_Container |      0 |      0 | 
25 | SafeFunctions       |      0 |      0 | 
VFDepth | 378 | 417 |

After I have a better understanding of what is going on I was going to run it on some much large code bases and see what is the average number of times that the while loop needs to execute for the valueFlow analyses. From there try and see if calling the functions is a different order changes that. In my short amount of sampling it looked like to me valueFlowSubFunction and valueFlowCondition_Simple took a lot of time. Maybe it would be as simple as calling a few of the cheap valueFlow calls before the loop. Personally I'm having fun just learning more about the inner works of cppcheck. I hope my posting aren't becoming too bothersome.

[Paul Fultz]

So the valueFlowSubfunction propagate values across function calls. We most likely should do this backwards as functions are usually called after they are defined. For example something like this:

void f1(int x) {}
void f2(int x) {
    f1(x); //  Set on the second passes
}
void f3(int x) {
    f2(x); // Set on first pass
}
void g() {
    f3(1);
}

Requires two passes to get the values to f2, but if we go backwards then the values would all be set in the first pass. Since its more common(but not always) that function are called after they are defined.

[john borland]

I had made a hacked version of the setValues function in valueflow.cpp so that I could better see which valueflow function was contributing to the while loop execution. I also had to run single threaded because of my uses of cout.

#include <iostream>
#include <iomanip>

static void myPrettyPrint(int len, int loc, std::size_t valuesList[18][28])
{
    int index;
    for (index = 0; index < len; ++index) {
       int before = valuesList[index][loc-1];
       int after  = valuesList[index][loc];

       std::cout<<std::setw(6)<<after-before<<" | ";
    }
    std::cout<<'\n';
}

void ValueFlow::setValues(TokenList *tokenlist, SymbolDatabase* symboldatabase, ErrorLogger *errorLogger, const Settings *settings)
{
    for (Token *tok = tokenlist->front(); tok; tok = tok->next())
        tok->clearValueFlow();

    valueFlowEnumValue(symboldatabase, settings);
    valueFlowNumber(tokenlist);
    valueFlowString(tokenlist);
    valueFlowArray(tokenlist);
    valueFlowUnknownFunctionReturn(tokenlist, settings);
    valueFlowGlobalConstVar(tokenlist, settings);
    valueFlowEnumValue(symboldatabase, settings);
    valueFlowNumber(tokenlist);
    valueFlowGlobalStaticVar(tokenlist, settings);
    valueFlowPointerAlias(tokenlist);
    valueFlowLifetime(tokenlist, symboldatabase, errorLogger, settings);
    valueFlowSymbolic(tokenlist, symboldatabase);
    valueFlowBitAnd(tokenlist);
    valueFlowSameExpressions(tokenlist);
    valueFlowConditionExpressions(tokenlist, symboldatabase, errorLogger, settings);

    std::size_t values = 0;
    std::size_t valuesList[18][28];
    int index,ind;
    std::size_t n = 18;
    std::size_t otherVal[3];

    otherVal[0]=getTotalValues(tokenlist);
    ind=0;
    while (n > 0 && values < getTotalValues(tokenlist)) {
        values = getTotalValues(tokenlist);

        index = 0;
        valuesList[ind][index]= values;
        valueFlowImpossibleValues(tokenlist, settings);
        valuesList[ind][++index] = getTotalValues(tokenlist);
        valueFlowSymbolicAbs(tokenlist, symboldatabase);
        valuesList[ind][++index] = getTotalValues(tokenlist);
        valueFlowCondition(SymbolicConditionHandler{}, tokenlist, symboldatabase, errorLogger, settings);
        valuesList[ind][++index] = getTotalValues(tokenlist);
        valueFlowSymbolicInfer(tokenlist, symboldatabase);
        valuesList[ind][++index] = getTotalValues(tokenlist);
        valueFlowArrayBool(tokenlist);
        valuesList[ind][++index] = getTotalValues(tokenlist);
        valueFlowRightShift(tokenlist, settings);
        valuesList[ind][++index] = getTotalValues(tokenlist);
        valueFlowAfterAssign(tokenlist, symboldatabase, errorLogger, settings);
        valuesList[ind][++index] = getTotalValues(tokenlist);
        valueFlowCondition(SimpleConditionHandler{}, tokenlist, symboldatabase, errorLogger, settings);
        valuesList[ind][++index] = getTotalValues(tokenlist);
        valueFlowInferCondition(tokenlist, settings);
        valuesList[ind][++index] = getTotalValues(tokenlist);
        valueFlowSwitchVariable(tokenlist, symboldatabase, errorLogger, settings);
        valuesList[ind][++index] = getTotalValues(tokenlist);
        valueFlowForLoop(tokenlist, symboldatabase, errorLogger, settings);
        valuesList[ind][++index] = getTotalValues(tokenlist);
        valueFlowSubFunction(tokenlist, symboldatabase, errorLogger, settings);
        valuesList[ind][++index] = getTotalValues(tokenlist);
        valueFlowFunctionReturn(tokenlist, errorLogger);
        valuesList[ind][++index] = getTotalValues(tokenlist);
        valueFlowLifetime(tokenlist, symboldatabase, errorLogger, settings);
        valuesList[ind][++index] = getTotalValues(tokenlist);
        valueFlowFunctionDefaultParameter(tokenlist, symboldatabase, settings);
        valuesList[ind][++index] = getTotalValues(tokenlist);
        valueFlowUninit(tokenlist, symboldatabase, settings);
        valuesList[ind][++index] = getTotalValues(tokenlist);
        valueFlowUninitPointerAliasDeref(tokenlist);
        valuesList[ind][++index] = getTotalValues(tokenlist);
        if (tokenlist->isCPP()) {
            valueFlowAfterMove(tokenlist, symboldatabase, settings);
            valuesList[ind][++index] = getTotalValues(tokenlist);
            valueFlowSmartPointer(tokenlist, errorLogger, settings);
            valuesList[ind][++index] = getTotalValues(tokenlist);
            valueFlowIterators(tokenlist, settings);
            valuesList[ind][++index] = getTotalValues(tokenlist);
            valueFlowCondition(IteratorConditionHandler{}, tokenlist, symboldatabase, errorLogger, settings);
            valuesList[ind][++index] = getTotalValues(tokenlist);
            valueFlowIteratorInfer(tokenlist, settings);
            valuesList[ind][++index] = getTotalValues(tokenlist);
            valueFlowContainerSize(tokenlist, symboldatabase, errorLogger, settings);
            valuesList[ind][++index] = getTotalValues(tokenlist);
            valueFlowCondition(ContainerConditionHandler{}, tokenlist, symboldatabase, errorLogger, settings);
            valuesList[ind][++index] = getTotalValues(tokenlist);
        }


        valueFlowSafeFunctions(tokenlist, symboldatabase, settings);
        valuesList[ind][++index] = getTotalValues(tokenlist);
        ++ind;
         n--;
    }

    otherVal[1]=getTotalValues(tokenlist);
    valueFlowDynamicBufferSize(tokenlist, symboldatabase, settings);
    otherVal[2]=getTotalValues(tokenlist);
    int nInd=0;
       std::cout<<"01 | ImpossibleValues    | ";  myPrettyPrint(ind, ++nInd, valuesList); 
       std::cout<<"02 | SymbolicAbs         | ";  myPrettyPrint(ind, ++nInd, valuesList); 
       std::cout<<"03 | Condition_Symbolic  | ";  myPrettyPrint(ind, ++nInd, valuesList); 
       std::cout<<"04 | SymbolicInfer       | ";  myPrettyPrint(ind, ++nInd, valuesList); 
       std::cout<<"05 | ArrayBool           | ";  myPrettyPrint(ind, ++nInd, valuesList); 
       std::cout<<"06 | RightShift          | ";  myPrettyPrint(ind, ++nInd, valuesList); 
       std::cout<<"07 | AfterAssign         | ";  myPrettyPrint(ind, ++nInd, valuesList); 
       std::cout<<"08 | Condition_Simple    | ";  myPrettyPrint(ind, ++nInd, valuesList); 
       std::cout<<"09 | InferCondition      | ";  myPrettyPrint(ind, ++nInd, valuesList); 
       std::cout<<"10 | SwitchVariable      | ";  myPrettyPrint(ind, ++nInd, valuesList); 
       std::cout<<"11 | ForLoop             | ";  myPrettyPrint(ind, ++nInd, valuesList); 
       std::cout<<"12 | SubFunction         | ";  myPrettyPrint(ind, ++nInd, valuesList); 
       std::cout<<"13 | FunctionReturn      | ";  myPrettyPrint(ind, ++nInd, valuesList); 
       std::cout<<"14 | Lifetime            | ";  myPrettyPrint(ind, ++nInd, valuesList); 
       std::cout<<"15 | FunctionDefaultPar  | ";  myPrettyPrint(ind, ++nInd, valuesList); 
       std::cout<<"16 | Uninit              | ";  myPrettyPrint(ind, ++nInd, valuesList); 
       std::cout<<"17 | UninitPointerAlias  | ";  myPrettyPrint(ind, ++nInd, valuesList); 
        if (tokenlist->isCPP()) {
       std::cout<<"18 | AfterMove           | ";  myPrettyPrint(ind, ++nInd, valuesList); 
       std::cout<<"19 | SmartPointer        | ";  myPrettyPrint(ind, ++nInd, valuesList); 
       std::cout<<"20 | Iterators           | ";  myPrettyPrint(ind, ++nInd, valuesList); 
       std::cout<<"21 | Condition_Iterator  | ";  myPrettyPrint(ind, ++nInd, valuesList); 
       std::cout<<"22 | IteratorInfer       | ";  myPrettyPrint(ind, ++nInd, valuesList); 
       std::cout<<"23 | ContainerSize       | ";  myPrettyPrint(ind, ++nInd, valuesList); 
       std::cout<<"24 | Condition_Container | ";  myPrettyPrint(ind, ++nInd, valuesList); 
        }

       std::cout<<"25 | SafeFunctions       | ";  myPrettyPrint(ind, ++nInd, valuesList); 

    std::cout<<"VFDepth | "<<otherVal[0]<<" | " <<otherVal[2]<<" |\n";

}

After finish my little minor performance improvement. I would like to look into a cheaper way to get the information than calling getTotalValues. I know you had told me before we might be able to pass it back through the settings structure. My goal would be to set up some debug flag to get this info and then talk to you all about turning it on in the donate cpu script. That way we can maybe see over all the projects that it run on if there are any cases where one valueflow function is driving the iteration more unfairly. I could easily see possibly calling one or two valueflow functions a head of the while loop and also placing them at the bottom of the loop if it cause the loop to run on average one less iteration. The other thing I think it might be useful for is to see if in this debug mode if the loop iteration max was raised higher to let say 8 to see if there are projects out there that are leaving things on the table by ending too early. Just like the --force option for defines people might want to a --valueflow-long option that increases the size or even a --valueflow-quick that sets it to 2 if you want quicker feedback at a risk of FP or less things found.

[Paul Fultz]

I think we need to create a PassManager to handle these cases, so each ValueFlowPass has a method to check if there will be changes. This should probably be done on a per-function basis if possible(most ValueFlow passes run over functions), but the pass manager can keep inventory of which passes are applicable.

struct ValueFlowPass {
    // Check if token matches
    virtual bool matches(const Token* tok) const;
    // Run the pass
    virtual void run(ValueFlowPassManager* pm) const;
};

Although, from your reports, I think if we modify ValueFlowSubFunction to run backwards then we could see a big improvement as may only need to run twice at most.

[john borland]

One of my many shortcomings is I tend to see things in a very C like way first. I have just been a C programmer for a very long time.

I'm trying to better under stand your ValueFlowPass example. I was envisioning a single loop over token list.

for (Token *tok = tokenlist->front(); tok;) {
        valueFlowSymbolicIdentityCheck(tok,pm[SymbolicIdentity]);
        valueFlowSymbolicAbsCheck(tok,pm[SymbolicAbs]);
        valueFlowRightShif(tok,pm[SymbolicIdentity]);
        And so on....
}
    std::size_t values = 0;
    std::size_t n = 4;
    while (n > 0 && values < getTotalValues(tokenlist)) {
       And so on....
    }

In the case of SymbolicIdentityCheck I would be looking for

if( Token::Match(tok, "*|/|<<|>>|^|+|-|%or%"){
    if( pm->first == nullptr ){
         pm->frist=tok;
         pm->staus=run;
    } else{
        pm->last=tok;
    }    
}

That way at the top of SymbolicIdentity this would be added.

static void valueFlowSymbolicIdentity(TokenList*tokenlist, ValueFlowPassManager* pm)
{
     if( pm->status == skip ){
          return;
    }
    Token* start;
    if( pm->status == run && pm->first != nullptr ) {
           start = pm->first;
          if( pm->last != nullptr ){
                stop=pm->last; 
          }
    } else {
         start = tokenlist->front();
         stop  = tokenlist->back();
    }

    for (Token* tok = start; tok!=stop->next(); tok = tok->next()) {
        if (tok->hasKnownIntValue())
            continue;
        if (!Token::Match(tok, "*|/|<<|>>|^|+|-|%or%"))
        And so on....

I saw it as things that iterated over the token list I would have the opportunity to change the start and stop of the for loop over token list to be slightly more optimal. In cases where we are looping over functions like in the valueFlowForLoop case. It would only be able to say there are no ForLoops so it can skip it or not, but there isn't a good way for me to change the start at stop like in the value flow case that iterate over the token list.

I'm trying to better understand how your suggested method would look in setValues?

struct ValueFlowPass {
    // Check if token matches
    virtual bool matches(const Token* tok) const;
    // Run the pass
    virtual void run(ValueFlowPassManager* pm) const;
};

I'm have trouble visualizing how that would look. Any more help or insight would be greatly appreciated.