[Bug tree-optimization/107114] New: [13 Regression] Failure to discover range results in bogus warning

[Bug tree-optimization/107114] New: [13 Regression] Failure to discover range results in bogus warning

[jeffreyalaw at gmail dot com]

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

            Bug ID: 107114
           Summary: [13 Regression] Failure to discover range results in
                    bogus warning
           Product: gcc
           Version: 13.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: jeffreyalaw at gmail dot com
                CC: aldyh at redhat dot com, amacleod at redhat dot com
  Target Milestone: ---
            Target: arc-elf

After this change (from me):

aa360fbf68b11e54017e8fa5b1bdb87ce7c19188

I'm seeing a case on arc-elf where VRP/Ranger is no longer identifying the
range of one object as not including zero.  As a result a test later in the CFG
isn't simplified and we get a bogus warning.

What's really interesting here is my change simplifies the CFG by eliminating a
handful of blocks in the affected loop (including a sub-loop).

Here's the testcase:
/* { dg-do compile } */

short a;
long b;
void fn1()
{
  int c = a = 1;
  for (; a; a++)
    {
      for (; 9 <= 8;)
        for (;;) {
            a = 20;
            for (; a <= 35; a++)
              ;
line:;
        }
      if ((c += 264487869) == 9)
        {
          unsigned *d = 0;
          for (; b;)
            d = (unsigned *)&c;
          if (d)
            for (;;)
              ;
        }
    }
  goto line;
}



Compiled on arc-elf with -Os -Wall:
[jlaw@X10DRH-iT gcc]$ ./cc1 -Os -Wall k.c -quiet
k.c: In function ‘fn1’:
k.c:17:14: warning: iteration 8 invokes undefined behavior
[-Waggressive-loop-optimizations]
   17 |       if ((c += 264487869) == 9)
      |              ^~
k.c:8:10: note: within this loop
    8 |   for (; a; a++)
      |          ^

If we look at the .vrp2 dump before my change we have this:

Global Exported: a_lsm.14_26 = [irange] short int [1, 9] NONZERO 0xf

This is key because we have this in the CFG:

;;   basic block 7, loop depth 1, count 21262216 (estimated locally), maybe hot
;;    prev block 6, next block 1, flags: (NEW, REACHABLE, VISITED)
;;    pred:       2 [always]  count:1346238 (estimated locally)
(FALLTHRU,EXECUTABLE) k.c:8:3
;;                6 [always]  count:20092794 (estimated locally)
(FALLTHRU,DFS_BACK,EXECUTABLE)
  # a_lsm.14_26 = PHI <1(2), _11(6)>
  # a_lsm_flag.15_28 = PHI <0(2), 1(6)>
  # c_lsm.16_29 = PHI <1(2), _6(6)>
  if (a_lsm.14_26 != 0) 
    goto <bb 6>; [94.50%]
  else 
    goto <bb 3>; [5.50%]


We really want to simplify that condition to a compile-time constant.  That
avoids the incorrect warning.

After my change we do not discover the range for a_lsm.14_26 in vfp2 and
naturally conditional above isn't simplified and the warning gets triggered.



Maybe I'm missing something subtle, but it looks like the simplifications done
in dom3 are resulting in vrp2 missing discovery of the key range.  It's not
clear to me why that's that's happening though.

Thoughts?

[Bug tree-optimization/107114] [13 Regression] Failure to discover range results in bogus warning

[law at gcc dot gnu.org]

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

Jeffrey A. Law <law at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P4
                 CC|                            |law at gcc dot gnu.org

[Bug tree-optimization/107114] [13 Regression] Failure to discover range results in bogus warning

[amacleod at redhat dot com]

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

--- Comment #1 from Andrew Macleod <amacleod at redhat dot com> ---
Looks like something in the change is causing the loop analysis to not be able
to count the iterations.


> Analyzing # of iterations of loop 1
>   exit condition [1, + , 1] != 0
>   bounds on difference of bases: -1 ... -1
>   result:
>     # of iterations 65535, bounded by 65535
109,110d68
<    Loops range found for a_lsm.14_26: [irange] short int [1, 9] NONZERO 0xf
and calculated range :[irange] short int VARYING
< Global Exported: a_lsm.14_26 = [irange] short int [1, 9] NONZERO 0xf
112,114c70,72
<    Loops range found for c_lsm.16_29: [irange] int [1, 2115902953] NONZERO
0x7fffffff and calculated range :[irange] int [-1618507910, +INF]
< Global Exported: c_lsm.16_29 = [irange] int [1, 2115902953] NONZERO
0x7fffffff
< Folding PHI node: a_lsm.14_26 = PHI <1(2), _11(12)>

before this change, loop analysis decided the range of _26 as
a_lsm.14_26: [irange] short int [1, 9] NONZERO 0xf a

afterwards, it doesn't even seem to see the loop.  IN fact, before LCSSA
creates a whole bunch of new blocks too.

< ;; Created LCSSA PHI: a_lsm.14_15 = PHI <a_lsm.14_26(8)>
< ;; Created LCSSA PHI: a_lsm_flag.15_16 = PHI <a_lsm_flag.15_28(8)>
< ;; Created LCSSA PHI: d_47 = PHI <d_13(7)>
< 
< Updating SSA:
< Registering new PHI nodes in block #13
< Updating SSA information for statement if (a_lsm.14_26 != 0)
< Registering new PHI nodes in block #6
< Registering new PHI nodes in block #12
< Updating SSA information for statement a.9_9 = (unsigned short) a_lsm.14_26;
< Registering new PHI nodes in block #16
< Registering new PHI nodes in block #7
< Registering new PHI nodes in block #8
< Updating SSA information for statement if (d_13 != 0B)
< Registering new PHI nodes in block #9
< Updating SSA information for statement if (a_lsm_flag.15_28 != 0)
< Registering new PHI nodes in block #10
< Updating SSA information for statement a = a_lsm.14_26;
< Registering new PHI nodes in block #11
< Registering new PHI nodes in block #19
< Registering new PHI nodes in block #15

[Bug tree-optimization/107114] [13 Regression] Failure to discover range results in bogus warning

[law at gcc dot gnu.org]

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

--- Comment #2 from Jeffrey A. Law <law at gcc dot gnu.org> ---
Which is just uber-weird.  The change in question removes a little subloop
which becomes unreachable.  Why that would cause us to be unable to analyze the
remaining key loop for the IV's range is a complete mystery.  Though I guess
I'll have to sit down and debug that a bit.  VRP is just calling into the loop
optimizer to to the IV analysis, right?


WRT the new blocks -- I strongly suspect they're part of normalization of the
loop and putting it into LCSSA form.  I'm not terribly worried about them. 
Typically they're just going to be creating empty loop latches.

[Bug tree-optimization/107114] [13 Regression] Failure to discover range results in bogus warning

[amacleod at redhat dot com]

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

--- Comment #3 from Andrew Macleod <amacleod at redhat dot com> ---
yeah, we just invoke the loop analyzer and pick up what it tells us. From VRP2
point of view, it is just not getting the info supplied from the loop
optimizer.

I see dom3 removes some code and I see 

 < fix_loop_structure: removing loop 5

any chance it doesn't fix it up right somehow?

[Bug tree-optimization/107114] [13 Regression] Failure to discover range results in bogus warning

[law at gcc dot gnu.org]

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

--- Comment #4 from Jeffrey A. Law <law at gcc dot gnu.org> ---
I'll double check, but IIRC we throw away the loop structures at the end of DOM
and they're supposed to be rebuilt (which appears to be happening as we
re-construct LCSSA).

[Bug tree-optimization/107114] [13 Regression] Failure to discover range results in bogus warning

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P4                          |P3
           Keywords|                            |missed-optimization
   Target Milestone|---                         |13.0

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Jeffrey A. Law from comment #4)
> I'll double check, but IIRC we throw away the loop structures at the end of
> DOM and they're supposed to be rebuilt (which appears to be happening as we
> re-construct LCSSA).

If you elide a loop it gets removed by fixup but we never fully re-build
loops.  Eliding a loop might have removed a stmt based on which undefined
behavior on overflow we could have derived an upper bound for the outer loop.
But you really have to sit down and see why we are no longer deriving
number of iterations [upper bound].

[Bug tree-optimization/107114] [13 Regression] Failure to discover range results in bogus warning

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |diagnostic
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2022-12-22

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
Confirmed for the diagnostics.  But note the loop in question is basically

 for (a = 1; a != 0; a++)

so it iterates until we wrap to zero (a is 'short', the increment is in
'int' due to promotion so short wrap doesn't invoke undefined overflow).

That means the loop iterates >65000 times which means the repeated add
of 264487869 overflows.

At the point we emit this diagnostic this will always happen so the
diagnostic is correct?

We do fail to optimize if ((c += 264487869) == 9) though, but likely
because VRP no longer iterates.  c starts from 1 and we only add positive
numbers the range for it should be [1, +INF].  The entry to the line:
tail loop has this optimized and the add removed as dead code.  That's
what possibly happened before - we optimized this branch and thus DCEd
the add?

Anyhow, on x86_64 we mangle the whole thing a bit more than on arc-elf.

Huh, it looks like arc-elf disables GIMPLE loop optimizers.  I can reproduce
the diagnostic on x86_64 with -fno-tree-loop-optimize.
gcc/common/config/arc/arc-common.cc has

    { OPT_LEVELS_SIZE, OPT_ftree_loop_optimize, NULL, 0},

for whatever reason.  -ftree-loop-optimize "fixes" the diagnostic.

But as said, I think the diagnostic is correct.

[Bug tree-optimization/107114] [13 Regression] Failure to discover range results in bogus warning

[rguenth at gcc dot gnu.org]

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

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

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

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
Based on that, closing as invalid.