How stable is the CFG and basic block IDs?

How stable is the CFG and basic block IDs?

[Jørgen Kvalsvik]

Hi,

I am working on adding path coverage support to gcc/gcov and need to 
develop a good testing strategy.

So far I can reasonably well report on the uncovered path as such:

paths covered 6 of 17
path not covered: 2 8 3 4
path not covered: 2 8 3 5 6
path not covered: 2 8 3 5 7 10
...

where the numbers are the basic blocks of the CFG, which can be seen in 
the source listing with gcov -a, e.g.:

     #####:    6:    while (low <= high)
     %%%%%:    6-block 2
     %%%%%:    6-block 8

Some natural test would be to by hand determine the paths taken and 
compare with the gcov output, like lines/branches/conditions are tested 
today. Unlike the other coverages in gcov, paths work more like function 
summaries and cannot be reasonably shown in the source listing, but the 
basic block listing actually works quite alright.

The problem is testing. If gcc would re-number the basic blocks then 
tests comparing hard-coded test paths would break, even though the path 
coverage itself would be just fine (and presumably the change to the 
basic block indices), which would add an unreasonable maintenance 
burden. If anything, it feels very fragile to write tests against the 
basic block indices.

On the other hand, if it can be expected that the same code should 
always yield the same CFG, the same BBs, and the same BB indices then I 
would happily test against them. I suppose this makes the basic blocks 
basically a public interface, which granted feels odd.

If you have any good idea on how to test paths in a robust way please 
let me know.

Thanks,
Jørgen

Re: How stable is the CFG and basic block IDs?

[Richard Biener]

On Tue, Apr 30, 2024 at 11:45 AM Jørgen Kvalsvik <j@lambda.is> wrote:
>
> Hi,
>
> I am working on adding path coverage support to gcc/gcov and need to
> develop a good testing strategy.
>
> So far I can reasonably well report on the uncovered path as such:
>
> paths covered 6 of 17
> path not covered: 2 8 3 4
> path not covered: 2 8 3 5 6
> path not covered: 2 8 3 5 7 10
> ...
>
> where the numbers are the basic blocks of the CFG, which can be seen in
> the source listing with gcov -a, e.g.:
>
>      #####:    6:    while (low <= high)
>      %%%%%:    6-block 2
>      %%%%%:    6-block 8
>
> Some natural test would be to by hand determine the paths taken and
> compare with the gcov output, like lines/branches/conditions are tested
> today. Unlike the other coverages in gcov, paths work more like function
> summaries and cannot be reasonably shown in the source listing, but the
> basic block listing actually works quite alright.
>
> The problem is testing. If gcc would re-number the basic blocks then
> tests comparing hard-coded test paths would break, even though the path
> coverage itself would be just fine (and presumably the change to the
> basic block indices), which would add an unreasonable maintenance
> burden. If anything, it feels very fragile to write tests against the
> basic block indices.

Problematic is usually when early canonicalization changes the
direction of a branch which affects the block IDs of the true/false
destinations (and their downstream blocks).

> On the other hand, if it can be expected that the same code should
> always yield the same CFG, the same BBs, and the same BB indices then I
> would happily test against them. I suppose this makes the basic blocks
> basically a public interface, which granted feels odd.
>
> If you have any good idea on how to test paths in a robust way please
> let me know.

Is there enough info to print a path like the following?

path not covered: t.c:2(true) t.c:4(false) t.c:11(true) ...

instead of printing (condition destination?) block IDs?

Richard.

>
> Thanks,
> Jørgen

Re: How stable is the CFG and basic block IDs?

[Jørgen Kvalsvik]

On 30/04/2024 12:45, Richard Biener wrote:
> On Tue, Apr 30, 2024 at 11:45 AM Jørgen Kvalsvik <j@lambda.is> wrote:
>>
>> Hi,
>>
>> I am working on adding path coverage support to gcc/gcov and need to
>> develop a good testing strategy.
>>
>> So far I can reasonably well report on the uncovered path as such:
>>
>> paths covered 6 of 17
>> path not covered: 2 8 3 4
>> path not covered: 2 8 3 5 6
>> path not covered: 2 8 3 5 7 10
>> ...
>>
>> where the numbers are the basic blocks of the CFG, which can be seen in
>> the source listing with gcov -a, e.g.:
>>
>>       #####:    6:    while (low <= high)
>>       %%%%%:    6-block 2
>>       %%%%%:    6-block 8
>>
>> Some natural test would be to by hand determine the paths taken and
>> compare with the gcov output, like lines/branches/conditions are tested
>> today. Unlike the other coverages in gcov, paths work more like function
>> summaries and cannot be reasonably shown in the source listing, but the
>> basic block listing actually works quite alright.
>>
>> The problem is testing. If gcc would re-number the basic blocks then
>> tests comparing hard-coded test paths would break, even though the path
>> coverage itself would be just fine (and presumably the change to the
>> basic block indices), which would add an unreasonable maintenance
>> burden. If anything, it feels very fragile to write tests against the
>> basic block indices.
> 
> Problematic is usually when early canonicalization changes the
> direction of a branch which affects the block IDs of the true/false
> destinations (and their downstream blocks).

I figured. Ok, that means I must figure out another strategy.

> 
>> On the other hand, if it can be expected that the same code should
>> always yield the same CFG, the same BBs, and the same BB indices then I
>> would happily test against them. I suppose this makes the basic blocks
>> basically a public interface, which granted feels odd.
>>
>> If you have any good idea on how to test paths in a robust way please
>> let me know.
> 
> Is there enough info to print a path like the following?
> 
> path not covered: t.c:2(true) t.c:4(false) t.c:11(true) ...
> 
> instead of printing (condition destination?) block IDs?

Yes! This is all pulled from the CFG and BB -> line mapping. I plan to 
implement this under different verbosity flags. We can even do one 
better - I have implemented this in my POC:

path not covered: 6 8 3 5 6
BB 6: 14:       high = mid - 1;
BB 8:  6:    while (low <= high)
BB 3:  8:    int mid = (low + high) >> 1;
BB 3:  9:    long midVal = a[mid];
BB 3: 11:   if (midVal < key)
BB 5: 13:   else if (midVal > key)
BB 6: 14:       high = mid - 1;

That is, gcov will print the statements in the order they need to be 
executed in order to achieve coverage.

Thanks,
Jørgen

> 
> Richard.
> 
>>
>> Thanks,
>> Jørgen

Re: How stable is the CFG and basic block IDs?

[Jan Hubicka]

> > The problem is testing. If gcc would re-number the basic blocks then
> > tests comparing hard-coded test paths would break, even though the path
> > coverage itself would be just fine (and presumably the change to the
> > basic block indices), which would add an unreasonable maintenance
> > burden. If anything, it feels very fragile to write tests against the
> > basic block indices.
> 
> Problematic is usually when early canonicalization changes the
> direction of a branch which affects the block IDs of the true/false
> destinations (and their downstream blocks).

I think we can renumber Bbs sequentially before profile generation (or
maybe we do already).  But indeed the CfG may change with time.
> 
> > On the other hand, if it can be expected that the same code should
> > always yield the same CFG, the same BBs, and the same BB indices then I
> > would happily test against them. I suppose this makes the basic blocks
> > basically a public interface, which granted feels odd.
> >
> > If you have any good idea on how to test paths in a robust way please
> > let me know.
> 
> Is there enough info to print a path like the following?
> 
> path not covered: t.c:2(true) t.c:4(false) t.c:11(true) ...
> 
> instead of printing (condition destination?) block IDs?

This was my first idea too.  Thre can be multiple BBs per line but you
can print both BB ID and source file nameand ignore the BB ID for
testsuite pruposes.

Honza
> 
> Richard.
> 
> >
> > Thanks,
> > Jørgen

Re: How stable is the CFG and basic block IDs?

[Jørgen Kvalsvik]

On 30/04/2024 13:43, Jan Hubicka wrote:
>>> The problem is testing. If gcc would re-number the basic blocks then
>>> tests comparing hard-coded test paths would break, even though the path
>>> coverage itself would be just fine (and presumably the change to the
>>> basic block indices), which would add an unreasonable maintenance
>>> burden. If anything, it feels very fragile to write tests against the
>>> basic block indices.
>>
>> Problematic is usually when early canonicalization changes the
>> direction of a branch which affects the block IDs of the true/false
>> destinations (and their downstream blocks).
> 
> I think we can renumber Bbs sequentially before profile generation (or
> maybe we do already).  But indeed the CfG may change with time.
>>
>>> On the other hand, if it can be expected that the same code should
>>> always yield the same CFG, the same BBs, and the same BB indices then I
>>> would happily test against them. I suppose this makes the basic blocks
>>> basically a public interface, which granted feels odd.
>>>
>>> If you have any good idea on how to test paths in a robust way please
>>> let me know.
>>
>> Is there enough info to print a path like the following?
>>
>> path not covered: t.c:2(true) t.c:4(false) t.c:11(true) ...
>>
>> instead of printing (condition destination?) block IDs?
> 
> This was my first idea too.  Thre can be multiple BBs per line but you
> can print both BB ID and source file nameand ignore the BB ID for
> testsuite pruposes.
> 

That's a brilliant idea, simply testing against the source line mapping. 
I'll try it right away, fantastic!

Thanks,
Jørgen

> Honza
>>
>> Richard.
>>
>>>
>>> Thanks,
>>> Jørgen

Re: How stable is the CFG and basic block IDs?

[Jørgen Kvalsvik]

On 30/04/2024 13:43, Jan Hubicka wrote:
>>> The problem is testing. If gcc would re-number the basic blocks then
>>> tests comparing hard-coded test paths would break, even though the path
>>> coverage itself would be just fine (and presumably the change to the
>>> basic block indices), which would add an unreasonable maintenance
>>> burden. If anything, it feels very fragile to write tests against the
>>> basic block indices.
>>
>> Problematic is usually when early canonicalization changes the
>> direction of a branch which affects the block IDs of the true/false
>> destinations (and their downstream blocks).
> 
> I think we can renumber Bbs sequentially before profile generation (or
> maybe we do already).  But indeed the CfG may change with time.
>>
>>> On the other hand, if it can be expected that the same code should
>>> always yield the same CFG, the same BBs, and the same BB indices then I
>>> would happily test against them. I suppose this makes the basic blocks
>>> basically a public interface, which granted feels odd.
>>>
>>> If you have any good idea on how to test paths in a robust way please
>>> let me know.
>>
>> Is there enough info to print a path like the following?
>>
>> path not covered: t.c:2(true) t.c:4(false) t.c:11(true) ...
>>
>> instead of printing (condition destination?) block IDs?
> 
> This was my first idea too.  Thre can be multiple BBs per line but you
> can print both BB ID and source file nameand ignore the BB ID for
> testsuite pruposes.
> 

Actually, we don't have the true/false, but maybe the CFG recording can 
be extended to include it, along with unconditional, is_fake, is_throw 
etc., looks like there's room in the bitset. Finding the right edge is 
easy because we have both the source and destination.

I'll check out if storing the true/false flag is simple and submit a patch.

> Honza
>>
>> Richard.
>>
>>>
>>> Thanks,
>>> Jørgen