[Bug c/106474] New: DCE depends on how if expressions are nested

[Bug c/106474] New: DCE depends on how if expressions are nested

[tmayerl at student dot ethz.ch]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106474

            Bug ID: 106474
           Summary: DCE depends on how if expressions are nested
           Product: gcc
           Version: 12.1.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
          Assignee: unassigned at gcc dot gnu.org
          Reporter: tmayerl at student dot ethz.ch
  Target Milestone: ---

In some cases, the compiler's ability to eliminate dead code depends on how if
expressions are nested.

GCC detects that the if expressions in the following code snippet evaluate to
false and thus removes the dead code:

#include <stdio.h>
#include <stdbool.h>

static void __attribute__ ((noinline)) DCEMarker0_() {printf("DCE2.0");}

void f(bool s, bool c) {
    if (!c == !s) {
        if (!c && s) {
            DCEMarker0_();
        }
    }
}

In the following snippet the !c term is moved into the outer if expression.
However, GCC cannot eliminate the dead code anymore:

#include <stdio.h>
#include <stdbool.h>

static void __attribute__ ((noinline)) DCEMarker0_() {printf("DCE2.0");}

void f(bool s, bool c) {
    if ((!c == !s) && !c) {
        if (s) {
            DCEMarker0_();
        }
    }
}

In the following snippet, only the outer if statement is kept and all terms are
moved there. GCC is now able to eliminate the code again:

#include <stdio.h>
#include <stdbool.h>

static void __attribute__ ((noinline)) DCEMarker0_() {printf("DCE2.0");}

void f(bool s, bool c) {
    if (((!c == !s) && !c) && s) {
        DCEMarker0_();
    }
}

This can also be seen via the following Compiler Explorer link:
https://godbolt.org/z/9WPn5cG1W

[Bug tree-optimization/106474] DCE depends on how if expressions are nested

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106474

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization
                 CC|                            |amacleod at redhat dot com
     Ever confirmed|0                           |1
          Component|c                           |tree-optimization
   Last reconfirmed|                            |2022-07-29
             Status|UNCONFIRMED                 |NEW

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
For the failing case we see

  <bb 2> :
  if (c_5(D) == s_6(D))
    goto <bb 3>; [INV]
  else
    goto <bb 6>; [INV]

  <bb 3> :
  if (c_5(D) != 0)
    goto <bb 6>; [INV]
  else
    goto <bb 4>; [INV]

  <bb 4> :
  if (s_6(D) != 0)
    goto <bb 5>; [INV]
  else
    goto <bb 6>; [INV]

and we basically fail to thread 2->3->4->6, eliminating the if (s_6(D) != 0)
branch when c_5(D) == s_6(D) and c_5(D) == 0.

It looks like relations / equivalences related, but maybe not exactly.  Andrew?

[Bug tree-optimization/106474] DCE depends on how if expressions are nested

[amacleod at redhat dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106474

--- Comment #2 from Andrew Macleod <amacleod at redhat dot com> ---
(In reply to Richard Biener from comment #1)
> For the failing case we see
> 
>   <bb 2> :
>   if (c_5(D) == s_6(D))
>     goto <bb 3>; [INV]
>   else
>     goto <bb 6>; [INV]
> 
>   <bb 3> :
>   if (c_5(D) != 0)
>     goto <bb 6>; [INV]
>   else
>     goto <bb 4>; [INV]
> 
>   <bb 4> :
>   if (s_6(D) != 0)
>     goto <bb 5>; [INV]
>   else
>     goto <bb 6>; [INV]
> 
> and we basically fail to thread 2->3->4->6, eliminating the if (s_6(D) != 0)
> branch when c_5(D) == s_6(D) and c_5(D) == 0.
> 
> It looks like relations / equivalences related, but maybe not exactly. 
> Andrew?

it is related.  Due to the expense, we don't evaluate every equivalence at
every use point.  In this case, there was no obvious "trigger" when we see s_6
!= 0 to go query all of the equivalences to see if they have ranges.

However range_from_dom ()  is now quite efficient and has a "read-only" mode
where it will make a DOM query without filling the cache. I am experimenting
with having the on-entry cache fill also invoke range_from_dom on equivalences
in read-only mode to see if any existing equivalence value can improve the
range.

The initial protoype reduces that test case in EVRP from
 <bb 2> :
  _1 = ~c_7(D);
  _2 = (int) _1;
  _3 = ~s_8(D);
  _4 = (int) _3;
  if (c_7(D) == s_8(D))
    goto <bb 3>; [INV]
  else
    goto <bb 6>; [INV]

  <bb 3> :
  if (c_7(D) != 0)
    goto <bb 6>; [INV]
  else
    goto <bb 4>; [INV]

  <bb 4> :
  if (s_8(D) != 0)
    goto <bb 5>; [INV]
  else
    goto <bb 6>; [INV]

  <bb 5> :
  DCEMarker0_ ();

  <bb 6> :
  return;

 to

   <bb 2> :
  _1 = ~c_7(D);
  _2 = (int) _1;
  _3 = ~s_8(D);
  _4 = (int) _3;
  return;


Let me run some performance numbers and see what the result is to see if there
is any throtteling needed or not.

[Bug tree-optimization/106474] DCE depends on how if expressions are nested

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106474

--- Comment #3 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Andrew Macleod <amacleod@gcc.gnu.org>:

https://gcc.gnu.org/g:87dd4c8c83768aafad92588853fd84a6070553d6

commit r13-1938-g87dd4c8c83768aafad92588853fd84a6070553d6
Author: Andrew MacLeod <amacleod@redhat.com>
Date:   Fri Jul 29 12:05:38 2022 -0400

    Check equivalencies when calculating range on entry.

    When propagating on-entry values in the cache, checking if any equivalence
    has a known value can improve results.  No new calculations are made.
    Only queries via dominators which do not populate the cache are checked.

            PR tree-optimization/106474
            gcc/
            * gimple-range-cache.cc (ranger_cache::fill_block_cache): Query
            range of equivalences that may contribute to the range.

            gcc/testsuite/
            * g++.dg/pr106474.C: New.

[Bug tree-optimization/106474] DCE depends on how if expressions are nested

[amacleod at redhat dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106474

Andrew Macleod <amacleod at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |FIXED
             Status|NEW                         |RESOLVED

--- Comment #4 from Andrew Macleod <amacleod at redhat dot com> ---
Presumably this is about functionality rather than the actual DCE pass.
The committed patch fixes this in any of the VRP passes.