Re: Surprising CFG construction with goto from then to else

[Richard Biener <richard.guenther@gmail.com>]

On Fri, Sep 2, 2022 at 11:50 AM Jørgen Kvalsvik <j@lambda.is> wrote:
>
>
> Hello,
>
> I played some more with odd programs and the effect on control flow
> graph construction (as a part of condition coverage support [1]) and
> came across this:
>
> int fn (int a, int b, int c) {
>      int x = 0;
>      if (a && b) {
>          if (c) {
>              goto a_;
>          } else {
>              x = a;
>          }
>      } else {
> a_:
>          x = (a - b);
>      }
>
>      return x;
> }
>
> Run through gcov --conditions I get:
>
>          4:    5:    if (a && b) {
> condition outcomes covered 2/2
> condition outcomes covered 2/2
>          2:    6:        if (c) {
> condition outcomes covered 2/2
>
> Which is clearly not correct. So I started digging into why and dump the
> CFG as the coverage profiling sees it https://i.imgur.com/d0q72rA.png
> [2]. I apologize for the labeling, but A2 = a, A3 = b, A5 = c and A9 the
> else block. The problem, which is what confuses the algorithm, is that a
> and b don't share A9 as a successor (on false) as I would expect.
>
> If I add some operation before the label the problem disappears and a
> and b share false-destination again https://i.imgur.com/PSrfaLC.png [3].
>
>      } else {
>          x++;
> a_:
>          x = (a - b);
>      }
>
>          4:    5:    if (a && b) {
> condition outcomes covered 4/4
>          2:    6:        if (c) {
> condition outcomes covered 2/2
>
>
> When dumping the cfg in the former case with -fdump-tree-cfg-graph I get
> a CFG without the split destinations in a and b
> https://i.imgur.com/05MCjzp.png [3]. I would assume from this that the
> graph dump happens after _more_ CFG transformations than the branch
> profiling.
>
> So my questions are:
>
> 1. Is the control flow graph expected to be constructed as such where a
> and b don't share outcome, or is it to be considered a bug?
> 2. If yes, would it be problematic to push the branch coverage and
> condition profiling to a later stage where the cfg has been fixed?

I would say you should only see more nodes merged.  It's a bit hard to follow
what you say with the namings - I usually run cc1 in gdb, breaking at
execute_build_cfg where you can do, after build_gimple_cfg finished
(and before cleanup_tree_cfg ()) do a 'dot-fn' in gdb which produces a nice
picture of the CFG and code with graphviz.

It looks like I would have expected, in particular we do not force a
new basic-block to be generated for a_: after the D.1991: artificial
label we have for the else.  That might be premature optimization
for your case (but the cleanup_tree_cfg () would immediately do
that as well).

Richard.

> Thanks,
> Jørgen
>
> [1] https://gcc.gnu.org/pipermail/gcc-patches/2022-July/598165.html
>
> [2] dot file:
>
> digraph {
>      A0 -> A2
>      A2 -> A3
>      A2 -> A8
>      A3 -> A5
>      A3 -> A4
>      A8 -> A9
>      A9 -> A10
>      A10 -> A11
>      A11 -> A1
>      A5 -> A6
>      A5 -> A7
>      A4 -> A9
>      A6 -> A9
>      A7 -> A10
> }
>
> [3] dot file:
>
> digraph {
>      A0 -> A2
>      A2 -> A3
>      A2 -> A7
>      A3 -> A4
>      A3 -> A7
>      A7 -> A8
>      A8 -> A9
>      A9 -> A10
>      A10 -> A1
>      A4 -> A5
>      A4 -> A6
>      A5 -> A8
>      A6 -> A9
> }
>
> [3] dot file:
>
>
> overlap=false;
> subgraph "cluster_fn" {
>          style="dashed";
>          color="black";
>          label="fn ()";
>          fn_0_basic_block_0
> [shape=Mdiamond,style=filled,fillcolor=white,label="ENTRY"];
>
>          fn_0_basic_block_1
> [shape=Mdiamond,style=filled,fillcolor=white,label="EXIT"];
>
>          fn_0_basic_block_2
> [shape=record,style=filled,fillcolor=lightgrey,label="{\<bb\ 2\>:\l\
> |x\ =\ 0;\l\
> |if\ (a\ !=\ 0)\l\
> \ \ goto\ \<bb\ 3\>;\ [INV]\l\
> else\l\
> \ \ goto\ \<bb\ 7\>;\ [INV]\l\
> }"];
>
>          fn_0_basic_block_3
> [shape=record,style=filled,fillcolor=lightgrey,label="{\<bb\ 3\>:\l\
> |if\ (b\ !=\ 0)\l\
> \ \ goto\ \<bb\ 4\>;\ [INV]\l\
> else\l\
> \ \ goto\ \<bb\ 7\>;\ [INV]\l\
> }"];
>
>          fn_0_basic_block_4
> [shape=record,style=filled,fillcolor=lightgrey,label="{\<bb\ 4\>:\l\
> |if\ (c\ !=\ 0)\l\
> \ \ goto\ \<bb\ 5\>;\ [INV]\l\
> else\l\
> \ \ goto\ \<bb\ 6\>;\ [INV]\l\
> }"];
>
>          fn_0_basic_block_5
> [shape=record,style=filled,fillcolor=lightgrey,label="{\<bb\ 5\>:\l\
> |//\ predicted\ unlikely\ by\ goto\ predictor.\l\
> goto\ \<bb\ 7\>;\ [INV]\l\
> }"];
>
>          fn_0_basic_block_6
> [shape=record,style=filled,fillcolor=lightgrey,label="{\<bb\ 6\>:\l\
> |x\ =\ a;\l\
> goto\ \<bb\ 8\>;\ [INV]\l\
> }"];
>
>          fn_0_basic_block_7
> [shape=record,style=filled,fillcolor=lightgrey,label="{\<bb\ 7\>:\l\
> |a_:\l\
> |x\ =\ a\ -\ b;\l\
> }"];
>
>          fn_0_basic_block_8
> [shape=record,style=filled,fillcolor=lightgrey,label="{\<bb\ 8\>:\l\
> |D.2398\ =\ x;\l\
> }"];
>
>          fn_0_basic_block_9
> [shape=record,style=filled,fillcolor=lightgrey,label="{\<bb\ 9\>:\l\
> |\<L7\>:\l\
> |return\ D.2398;\l\
> }"];
>
>          fn_0_basic_block_0:s -> fn_0_basic_block_2:n
> [style="solid,bold",color=black,weight=100,constraint=true];
>          fn_0_basic_block_2:s -> fn_0_basic_block_3:n
> [style="solid,bold",color=forestgreen,weight=10,constraint=true];
>          fn_0_basic_block_2:s -> fn_0_basic_block_7:n
> [style="solid,bold",color=darkorange,weight=10,constraint=true];
>          fn_0_basic_block_3:s -> fn_0_basic_block_4:n
> [style="solid,bold",color=forestgreen,weight=10,constraint=true];
>          fn_0_basic_block_3:s -> fn_0_basic_block_7:n
> [style="solid,bold",color=darkorange,weight=10,constraint=true];
>          fn_0_basic_block_4:s -> fn_0_basic_block_5:n
> [style="solid,bold",color=forestgreen,weight=10,constraint=true];
>          fn_0_basic_block_4:s -> fn_0_basic_block_6:n
> [style="solid,bold",color=darkorange,weight=10,constraint=true];
>          fn_0_basic_block_5:s -> fn_0_basic_block_7:n
> [style="solid,bold",color=black,weight=100,constraint=true];
>          fn_0_basic_block_6:s -> fn_0_basic_block_8:n
> [style="solid,bold",color=black,weight=100,constraint=true];
>          fn_0_basic_block_7:s -> fn_0_basic_block_8:n
> [style="solid,bold",color=black,weight=100,constraint=true];
>          fn_0_basic_block_8:s -> fn_0_basic_block_9:n
> [style="solid,bold",color=black,weight=100,constraint=true];
>          fn_0_basic_block_9:s -> fn_0_basic_block_1:n
> [style="solid,bold",color=black,weight=10,constraint=true];
>          fn_0_basic_block_0:s -> fn_0_basic_block_1:n
> [style="invis",constraint=true];
> }
> }