[Bug tree-optimization/106234] New: [13 Regression] stack overflow from range_from_dom

[Bug tree-optimization/106234] New: [13 Regression] stack overflow from range_from_dom

[rguenth at gcc dot gnu.org]

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

            Bug ID: 106234
           Summary: [13 Regression] stack overflow from range_from_dom
           Product: gcc
           Version: 13.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: rguenth at gcc dot gnu.org
  Target Milestone: ---

Some recent commit on the testcase below with -O2 -funswitch-loops
-fno-thread-jumps blows the stack due to deep recursion

#0  0x0000000000f33a1b in range_query::get_tree_range (this=0x5bc6d78, r=..., 
    expr=0x7ffff68e10f0, stmt=0x7fffe99fafa0)
    at /space/rguenther/src/gcc/gcc/value-query.cc:214
#1  0x0000000001892bfc in ranger_cache::range_of_expr (this=<optimized out>, 
    r=..., name=<optimized out>, stmt=<optimized out>)
    at /space/rguenther/src/gcc/gcc/gimple-range-cache.cc:978
...
(gdb) up 10000
#7950 0x00000000007103eb in main (argc=8, argv=0x7fffffffdd48)
    at /space/rguenther/src/gcc/gcc/main.cc:39
39        int r = toplev.main (argc, argv);

with range_from_dom appearing a lot of times.  -fno-tree-dominator-opts
-fno-tree-vrp "fixes" this.

extern int foo (int);

int bar(int flag)
{
  int res = 0;
#define A \
  for (int i = 0; i < 1024; ++i) if (flag) res ^= foo(i);
#define B A A A A A A A A A A
#define C B B B B B B B B B B
#define D C C C C C C C C C C
#define E D D D D D D D D D D
  E
  return res;
}


it looks like range_from_dom walks up immediate dominators but in that loop
recurses to itself!?  isn't that quadratic?  shouldn't the recursion stop
at the next immediate dominator of the recursion invoker?

[Bug tree-optimization/106234] [13 Regression] stack overflow from range_from_dom

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |aldyh at gcc dot gnu.org,
                   |                            |amacleod at redhat dot com
   Target Milestone|---                         |13.0

[Bug tree-optimization/106234] [13 Regression] stack overflow from range_from_dom

[amacleod at redhat dot com]

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

--- Comment #1 from Andrew Macleod <amacleod at redhat dot com> ---

> it looks like range_from_dom walks up immediate dominators but in that loop
> recurses to itself!?  isn't that quadratic?  shouldn't the recursion stop
> at the next immediate dominator of the recursion invoker?

it walks immediate dominators, and when it finds a block with multiple incoming
edges, the recursion call is to calculate the immediate dominators range. When
that recursive call finishes, the walk stops because the immediate dominator
has now been resolved.

So it should be linear.. a mix of walking immediate dominators and resolving
immediate dominators.  but its still a march up the immediate dominator chain.

I suspect its just such a deep list of unresolved dominators to walk that the
recursion is problematic.  I will investigate to verify and see if I can
integrate the recursion with the existing walk stack

[Bug tree-optimization/106234] [13 Regression] stack overflow from range_from_dom

[amacleod at redhat dot com]

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

--- Comment #2 from Andrew Macleod <amacleod at redhat dot com> ---
Created attachment 53281
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=53281&action=edit
proposed patch

we're having some connection issues, but I am in the process of trying to test
the  attached patch.

basically, when we were ensuring the range was set in the immediate dominator,
I was *suppose* to first check to see if it was already set and not make the
call... like the other call sites... Doh!

Without that, it was possible for this to be quadratic when the correct
circumstances were presented.. as in this case.  It walks the dominator chain
all the way to the top, not utilizing the cache.

this should make it linear again.   speedup in your testcase for VRP was
noticable.

Let me know if it resolves your problem..   and I wil continue the test cycle

[Bug tree-optimization/106234] [13 Regression] stack overflow from range_from_dom

[rguenth at gcc dot gnu.org]

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

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Andrew Macleod from comment #2)
> Created attachment 53281 [details]
> proposed patch
> 
> we're having some connection issues, but I am in the process of trying to
> test the  attached patch.
> 
> basically, when we were ensuring the range was set in the immediate
> dominator, I was *suppose* to first check to see if it was already set and
> not make the call... like the other call sites... Doh!
> 
> Without that, it was possible for this to be quadratic when the correct
> circumstances were presented.. as in this case.  It walks the dominator
> chain all the way to the top, not utilizing the cache.
> 
> this should make it linear again.   speedup in your testcase for VRP was
> noticable.
> 
> Let me know if it resolves your problem..   and I wil continue the test cycle

Yes, that resolves my problem with the deep recursion.

Thanks!

[Bug tree-optimization/106234] [13 Regression] stack overflow from range_from_dom

[cvs-commit at gcc dot gnu.org]

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

--- Comment #4 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:12a9b98ac574bc8092a75849b5c462135d35c31d

commit r13-1608-g12a9b98ac574bc8092a75849b5c462135d35c31d
Author: Andrew MacLeod <amacleod@redhat.com>
Date:   Fri Jul 8 13:30:49 2022 -0400

    Avoid calling range_from_dom when dominator is already resolved.

    range_from_dom makes a recursive call to resolve the immediate dominator
    when there are multiple incoming edges to a block.  This is not necessary
    when the dominator already has an on-entry cache value.

            PR tree-optimization/106234
            * gimple-range-cache.cc (ranger_cache::range_from_dom): Check
dominator
            cache value before recursively resolving it.

[Bug tree-optimization/106234] [13 Regression] stack overflow from range_from_dom

[amacleod at redhat dot com]

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

Andrew Macleod <amacleod at redhat dot com> changed:

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

--- Comment #5 from Andrew Macleod <amacleod at redhat dot com> ---
fixed.