[COMMITTED 2/5] Fix ranger when called from SCEV.

[COMMITTED 2/5] Fix ranger when called from SCEV.

[Andrew MacLeod]

[-- Attachment #1: Type: text/plain, Size: 705 bytes --]

Also during stage 3/4, we discovered that it is unsafe to call ranger 
from within SCEV.  This is because ranger uses SCEV to resolve PHIS, and 
we can end up in a bad loop under the right conditions.

The fix is for ranger's cache to NOT try to pre-evaluate PHIs (which is 
kind of waste anyway since they rarely resolve based on known incoming 
ranges to anything interesting).

Combined with this, it is now safe to make filling the block cache 
re-entrant (which can also happen if called from SCEV).

Turns out not wasting time pre-evaluating PHIs was also a time win.. so 
this patch also provides some modest speedups.

Bootstrapped on x86_64-pc-linux-gnu with no regressions.  pushed.

Andrew



[-- Attachment #2: 0002-Fix-ranger-when-called-from-SCEV.patch --]
[-- Type: text/x-patch, Size: 2431 bytes --]

From 83e95c10ed822270e39cb8da8c09f607ad65abbd Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacleod@redhat.com>
Date: Wed, 13 Mar 2024 14:10:41 -0400
Subject: [PATCH 2/9] Fix ranger when called from SCEV.

Do not pre-evaluate PHIs in the cache, and allow fill_block_cache to
be re-entrant.  This allows SCEV to call into ranger with a context
and not produce cycles or loops.

	* gimple-range-cache.cc (ranger_cache::get_global_range): Do not
	pre-evaluate PHI nodes from the cache.
	(ranger_cache::fill_block_cache): Make re-entrant.
---
 gcc/gimple-range-cache.cc | 10 ++++++----
 1 file changed, 6 insertions(+), 4 deletions(-)

diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc
index a33b7a73872..72ac2552311 100644
--- a/gcc/gimple-range-cache.cc
+++ b/gcc/gimple-range-cache.cc
@@ -1047,7 +1047,9 @@ ranger_cache::get_global_range (vrange &r, tree name, bool &current_p)
       if (r.varying_p () && !cfun->after_inlining)
 	{
 	  gimple *s = SSA_NAME_DEF_STMT (name);
-	  if (gimple_get_lhs (s) == name)
+	  // Do not process PHIs as SCEV may be in use and it can
+	  // spawn cyclic lookups.
+	  if (gimple_get_lhs (s) == name && !is_a<gphi *> (s))
 	    {
 	      if (!fold_range (r, s, get_global_range_query ()))
 		gimple_range_global (r, name);
@@ -1413,7 +1415,7 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb)
 
   // At this point we shouldn't be looking at the def, entry block.
   gcc_checking_assert (bb != def_bb && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun));
-  gcc_checking_assert (m_workback.length () == 0);
+  unsigned start_length = m_workback.length ();
 
   // If the block cache is set, then we've already visited this block.
   if (m_on_entry.bb_range_p (name, bb))
@@ -1500,7 +1502,7 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb)
 	}
 
       m_on_entry.set_bb_range (name, bb, block_result);
-      gcc_checking_assert (m_workback.length () == 0);
+      gcc_checking_assert (m_workback.length () == start_length);
       return;
     }
 
@@ -1512,7 +1514,7 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb)
   m_on_entry.set_bb_range (name, bb, undefined);
   gcc_checking_assert (m_update->empty_p ());
 
-  while (m_workback.length () > 0)
+  while (m_workback.length () > start_length)
     {
       basic_block node = m_workback.pop ();
       if (DEBUG_RANGE_CACHE)
-- 
2.41.0

Re: [COMMITTED 2/5] Fix ranger when called from SCEV.

[Jan-Benedict Glaw]

[-- Attachment #1: Type: text/plain, Size: 3198 bytes --]

On Tue, 2024-04-30 17:24:15 -0400, Andrew MacLeod <amacleod@redhat.com> wrote:
> Bootstrapped on x86_64-pc-linux-gnu with no regressions.  pushed.

Starting with this patch (upstream as
e8ae56a7dc46e39a48017bb5159e4dc672ec7fad, can still be reproduced with
0c585c8d0dd85601a8d116ada99126a48c8ce9fd as of May 13th), my CI builds fail for
csky-elf in all-target-libgcc by falling into a loop infinite loop:

../gcc/configure '--with-pkgversion=basepoints/gcc-15-432-g0c585c8d0dd, built at 1715608899'	\
	--prefix=/tmp/gcc-csky-elf --enable-werror-always --enable-languages=all		\
	--disable-gcov --disable-shared --disable-threads --target=csky-elf --without-headers
make V=1 all-gcc
make V=1 install-strip-gcc
make V=1 all-target-libgcc

(gdb) bt
#0  0x000000000098f1df in bitmap_list_find_element (head=0x38f2e18, indx=5001) at ../../gcc/gcc/bitmap.cc:375
#1  bitmap_set_bit (head=0x38f2e18, bit=640244) at ../../gcc/gcc/bitmap.cc:962
#2  0x0000000000d39cd1 in process_bb_lives (bb=<optimized out>, curr_point=@0x7ffe062c1b2c: 3039473, dead_insn_p=<optimized out>) at ../../gcc/gcc/lra-lives.cc:889
#3  lra_create_live_ranges_1 (all_p=all_p@entry=true, dead_insn_p=<optimized out>) at ../../gcc/gcc/lra-lives.cc:1416
#4  0x0000000000d3b810 in lra_create_live_ranges (all_p=all_p@entry=true, dead_insn_p=<optimized out>) at ../../gcc/gcc/lra-lives.cc:1486
#5  0x0000000000d1a8bd in lra (f=<optimized out>, verbose=<optimized out>) at ../../gcc/gcc/lra.cc:2482
#6  0x0000000000cd0e18 in do_reload () at ../../gcc/gcc/ira.cc:5973
#7  (anonymous namespace)::pass_reload::execute (this=<optimized out>) at ../../gcc/gcc/ira.cc:6161
#8  0x0000000000de6368 in execute_one_pass (pass=pass@entry=0x367c490) at ../../gcc/gcc/passes.cc:2647
#9  0x0000000000de6c00 in execute_pass_list_1 (pass=0x367c490) at ../../gcc/gcc/passes.cc:2756
#10 0x0000000000de6c12 in execute_pass_list_1 (pass=0x367b2f0) at ../../gcc/gcc/passes.cc:2757
#11 0x0000000000de6c39 in execute_pass_list (fn=0x7f24a1c06240, pass=<optimized out>) at ../../gcc/gcc/passes.cc:2767
#12 0x0000000000a188c6 in cgraph_node::expand (this=0x7f24a1bfaaa0) at ../../gcc/gcc/context.h:48
#13 cgraph_node::expand (this=0x7f24a1bfaaa0) at ../../gcc/gcc/cgraphunit.cc:1798
#14 0x0000000000a1a69b in expand_all_functions () at ../../gcc/gcc/cgraphunit.cc:2028
#15 symbol_table::compile (this=0x7f24a205b000) at ../../gcc/gcc/cgraphunit.cc:2404
#16 0x0000000000a1ccb8 in symbol_table::compile (this=0x7f24a205b000) at ../../gcc/gcc/cgraphunit.cc:2315
#17 symbol_table::finalize_compilation_unit (this=0x7f24a205b000) at ../../gcc/gcc/cgraphunit.cc:2589
#18 0x0000000000f0932d in compile_file () at ../../gcc/gcc/toplev.cc:476
#19 0x0000000000839648 in do_compile () at ../../gcc/gcc/toplev.cc:2158
#20 toplev::main (this=this@entry=0x7ffe062c1f2e, argc=<optimized out>, argc@entry=78, argv=<optimized out>, argv@entry=0x7ffe062c2058) at ../../gcc/gcc/toplev.cc:2314
#21 0x000000000083ad9e in main (argc=78, argv=0x7ffe062c2058) at ../../gcc/gcc/main.cc:39

(Loop is based in process_bb_lives(), looping in the
FOR_BB_INSNS_REVERSE_SAFE (bb, curr_insn, next) block starting at
about line 696.)

MfG, JBG

-- 

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 195 bytes --]

Re: [COMMITTED 2/5] Fix ranger when called from SCEV.

[Jan-Benedict Glaw]

[-- Attachment #1: Type: text/plain, Size: 4603 bytes --]

On Mon, 2024-05-13 20:19:42 +0200, Jan-Benedict Glaw <jbglaw@lug-owl.de> wrote:
> On Tue, 2024-04-30 17:24:15 -0400, Andrew MacLeod <amacleod@redhat.com> wrote:
> > Bootstrapped on x86_64-pc-linux-gnu with no regressions.  pushed.
> 
> Starting with this patch (upstream as
> e8ae56a7dc46e39a48017bb5159e4dc672ec7fad, can still be reproduced with
> 0c585c8d0dd85601a8d116ada99126a48c8ce9fd as of May 13th), my CI builds fail for
> csky-elf in all-target-libgcc by falling into a loop infinite loop:
> 
> ../gcc/configure '--with-pkgversion=basepoints/gcc-15-432-g0c585c8d0dd, built at 1715608899'	\
> 	--prefix=/tmp/gcc-csky-elf --enable-werror-always --enable-languages=all		\
> 	--disable-gcov --disable-shared --disable-threads --target=csky-elf --without-headers
> make V=1 all-gcc
> make V=1 install-strip-gcc
> make V=1 all-target-libgcc

Just to add:

/var/lib/laminar/run/gcc-csky-elf/65/toolchain-build/./gcc/cc1 -quiet				\
	-I . -I . -I ../../.././gcc -I ../../../../gcc/libgcc					\
	-I ../../../../gcc/libgcc/. -I ../../../../gcc/libgcc/../gcc				\
	-I ../../../../gcc/libgcc/../include -imultilib ck801					\
	-iprefix /var/lib/laminar/run/gcc-csky-elf/65/toolchain-build/gcc/../lib/gcc/csky-elf/15.0.0/	\
	-isystem /var/lib/laminar/run/gcc-csky-elf/65/toolchain-build/./gcc/include		\
	-isystem /var/lib/laminar/run/gcc-csky-elf/65/toolchain-build/./gcc/include-fixed	\
	-MD unwind-dw2-fde.d -MF unwind-dw2-fde.dep -MP -MT unwind-dw2-fde.o			\
	-D IN_GCC -D CROSS_DIRECTORY_STRUCTURE -D IN_LIBGCC2 -D inhibit_libc			\
	-D HAVE_CC_TLS -D USE_EMUTLS -D HIDE_EXPORTS						\
	-isystem /tmp/gcc-csky-elf/csky-elf/include						\
	-isystem /tmp/gcc-csky-elf/csky-elf/sys-include						\
	-isystem ./include ../../../../gcc/libgcc/unwind-dw2-fde.c -quiet			\
	-dumpbase unwind-dw2-fde.c -dumpbase-ext .c -mcpu=ck801 -g -g -g -O2 -O2 -O2		\
	-Wextra -Wall -Wno-narrowing -Wwrite-strings -Wcast-qual -Wstrict-prototypes		\
	-Wmissing-prototypes -Wold-style-definition -fbuilding-libgcc -fno-stack-protector	\
	-fexceptions -fvisibility=hidden -o /tmp/cc3SHedS.s

> (gdb) bt
> #0  0x000000000098f1df in bitmap_list_find_element (head=0x38f2e18, indx=5001) at ../../gcc/gcc/bitmap.cc:375
> #1  bitmap_set_bit (head=0x38f2e18, bit=640244) at ../../gcc/gcc/bitmap.cc:962
> #2  0x0000000000d39cd1 in process_bb_lives (bb=<optimized out>, curr_point=@0x7ffe062c1b2c: 3039473, dead_insn_p=<optimized out>) at ../../gcc/gcc/lra-lives.cc:889
> #3  lra_create_live_ranges_1 (all_p=all_p@entry=true, dead_insn_p=<optimized out>) at ../../gcc/gcc/lra-lives.cc:1416
> #4  0x0000000000d3b810 in lra_create_live_ranges (all_p=all_p@entry=true, dead_insn_p=<optimized out>) at ../../gcc/gcc/lra-lives.cc:1486
> #5  0x0000000000d1a8bd in lra (f=<optimized out>, verbose=<optimized out>) at ../../gcc/gcc/lra.cc:2482
> #6  0x0000000000cd0e18 in do_reload () at ../../gcc/gcc/ira.cc:5973
> #7  (anonymous namespace)::pass_reload::execute (this=<optimized out>) at ../../gcc/gcc/ira.cc:6161
> #8  0x0000000000de6368 in execute_one_pass (pass=pass@entry=0x367c490) at ../../gcc/gcc/passes.cc:2647
> #9  0x0000000000de6c00 in execute_pass_list_1 (pass=0x367c490) at ../../gcc/gcc/passes.cc:2756
> #10 0x0000000000de6c12 in execute_pass_list_1 (pass=0x367b2f0) at ../../gcc/gcc/passes.cc:2757
> #11 0x0000000000de6c39 in execute_pass_list (fn=0x7f24a1c06240, pass=<optimized out>) at ../../gcc/gcc/passes.cc:2767
> #12 0x0000000000a188c6 in cgraph_node::expand (this=0x7f24a1bfaaa0) at ../../gcc/gcc/context.h:48
> #13 cgraph_node::expand (this=0x7f24a1bfaaa0) at ../../gcc/gcc/cgraphunit.cc:1798
> #14 0x0000000000a1a69b in expand_all_functions () at ../../gcc/gcc/cgraphunit.cc:2028
> #15 symbol_table::compile (this=0x7f24a205b000) at ../../gcc/gcc/cgraphunit.cc:2404
> #16 0x0000000000a1ccb8 in symbol_table::compile (this=0x7f24a205b000) at ../../gcc/gcc/cgraphunit.cc:2315
> #17 symbol_table::finalize_compilation_unit (this=0x7f24a205b000) at ../../gcc/gcc/cgraphunit.cc:2589
> #18 0x0000000000f0932d in compile_file () at ../../gcc/gcc/toplev.cc:476
> #19 0x0000000000839648 in do_compile () at ../../gcc/gcc/toplev.cc:2158
> #20 toplev::main (this=this@entry=0x7ffe062c1f2e, argc=<optimized out>, argc@entry=78, argv=<optimized out>, argv@entry=0x7ffe062c2058) at ../../gcc/gcc/toplev.cc:2314
> #21 0x000000000083ad9e in main (argc=78, argv=0x7ffe062c2058) at ../../gcc/gcc/main.cc:39
> 
> (Loop is based in process_bb_lives(), looping in the
> FOR_BB_INSNS_REVERSE_SAFE (bb, curr_insn, next) block starting at
> about line 696.)

MfG, JBG

-- 

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 195 bytes --]

Re: [COMMITTED 2/5] Fix ranger when called from SCEV.

[Richard Biener]

On Mon, May 13, 2024 at 8:28 PM Jan-Benedict Glaw <jbglaw@lug-owl.de> wrote:
>
> On Mon, 2024-05-13 20:19:42 +0200, Jan-Benedict Glaw <jbglaw@lug-owl.de> wrote:
> > On Tue, 2024-04-30 17:24:15 -0400, Andrew MacLeod <amacleod@redhat.com> wrote:
> > > Bootstrapped on x86_64-pc-linux-gnu with no regressions.  pushed.
> >
> > Starting with this patch (upstream as
> > e8ae56a7dc46e39a48017bb5159e4dc672ec7fad, can still be reproduced with
> > 0c585c8d0dd85601a8d116ada99126a48c8ce9fd as of May 13th), my CI builds fail for
> > csky-elf in all-target-libgcc by falling into a loop infinite loop:

Does the CI build GCC for the host and then use that compiler to build
the csky cross?  That said,
I can't see how the ref (or wasn't this a bisect?) can cause an issue
in LRA when building a cross-compiler.

Richard.

> > ../gcc/configure '--with-pkgversion=basepoints/gcc-15-432-g0c585c8d0dd, built at 1715608899'  \
> >       --prefix=/tmp/gcc-csky-elf --enable-werror-always --enable-languages=all                \
> >       --disable-gcov --disable-shared --disable-threads --target=csky-elf --without-headers
> > make V=1 all-gcc
> > make V=1 install-strip-gcc
> > make V=1 all-target-libgcc
>
> Just to add:
>
> /var/lib/laminar/run/gcc-csky-elf/65/toolchain-build/./gcc/cc1 -quiet                           \
>         -I . -I . -I ../../.././gcc -I ../../../../gcc/libgcc                                   \
>         -I ../../../../gcc/libgcc/. -I ../../../../gcc/libgcc/../gcc                            \
>         -I ../../../../gcc/libgcc/../include -imultilib ck801                                   \
>         -iprefix /var/lib/laminar/run/gcc-csky-elf/65/toolchain-build/gcc/../lib/gcc/csky-elf/15.0.0/   \
>         -isystem /var/lib/laminar/run/gcc-csky-elf/65/toolchain-build/./gcc/include             \
>         -isystem /var/lib/laminar/run/gcc-csky-elf/65/toolchain-build/./gcc/include-fixed       \
>         -MD unwind-dw2-fde.d -MF unwind-dw2-fde.dep -MP -MT unwind-dw2-fde.o                    \
>         -D IN_GCC -D CROSS_DIRECTORY_STRUCTURE -D IN_LIBGCC2 -D inhibit_libc                    \
>         -D HAVE_CC_TLS -D USE_EMUTLS -D HIDE_EXPORTS                                            \
>         -isystem /tmp/gcc-csky-elf/csky-elf/include                                             \
>         -isystem /tmp/gcc-csky-elf/csky-elf/sys-include                                         \
>         -isystem ./include ../../../../gcc/libgcc/unwind-dw2-fde.c -quiet                       \
>         -dumpbase unwind-dw2-fde.c -dumpbase-ext .c -mcpu=ck801 -g -g -g -O2 -O2 -O2            \
>         -Wextra -Wall -Wno-narrowing -Wwrite-strings -Wcast-qual -Wstrict-prototypes            \
>         -Wmissing-prototypes -Wold-style-definition -fbuilding-libgcc -fno-stack-protector      \
>         -fexceptions -fvisibility=hidden -o /tmp/cc3SHedS.s
>
> > (gdb) bt
> > #0  0x000000000098f1df in bitmap_list_find_element (head=0x38f2e18, indx=5001) at ../../gcc/gcc/bitmap.cc:375
> > #1  bitmap_set_bit (head=0x38f2e18, bit=640244) at ../../gcc/gcc/bitmap.cc:962
> > #2  0x0000000000d39cd1 in process_bb_lives (bb=<optimized out>, curr_point=@0x7ffe062c1b2c: 3039473, dead_insn_p=<optimized out>) at ../../gcc/gcc/lra-lives.cc:889
> > #3  lra_create_live_ranges_1 (all_p=all_p@entry=true, dead_insn_p=<optimized out>) at ../../gcc/gcc/lra-lives.cc:1416
> > #4  0x0000000000d3b810 in lra_create_live_ranges (all_p=all_p@entry=true, dead_insn_p=<optimized out>) at ../../gcc/gcc/lra-lives.cc:1486
> > #5  0x0000000000d1a8bd in lra (f=<optimized out>, verbose=<optimized out>) at ../../gcc/gcc/lra.cc:2482
> > #6  0x0000000000cd0e18 in do_reload () at ../../gcc/gcc/ira.cc:5973
> > #7  (anonymous namespace)::pass_reload::execute (this=<optimized out>) at ../../gcc/gcc/ira.cc:6161
> > #8  0x0000000000de6368 in execute_one_pass (pass=pass@entry=0x367c490) at ../../gcc/gcc/passes.cc:2647
> > #9  0x0000000000de6c00 in execute_pass_list_1 (pass=0x367c490) at ../../gcc/gcc/passes.cc:2756
> > #10 0x0000000000de6c12 in execute_pass_list_1 (pass=0x367b2f0) at ../../gcc/gcc/passes.cc:2757
> > #11 0x0000000000de6c39 in execute_pass_list (fn=0x7f24a1c06240, pass=<optimized out>) at ../../gcc/gcc/passes.cc:2767
> > #12 0x0000000000a188c6 in cgraph_node::expand (this=0x7f24a1bfaaa0) at ../../gcc/gcc/context.h:48
> > #13 cgraph_node::expand (this=0x7f24a1bfaaa0) at ../../gcc/gcc/cgraphunit.cc:1798
> > #14 0x0000000000a1a69b in expand_all_functions () at ../../gcc/gcc/cgraphunit.cc:2028
> > #15 symbol_table::compile (this=0x7f24a205b000) at ../../gcc/gcc/cgraphunit.cc:2404
> > #16 0x0000000000a1ccb8 in symbol_table::compile (this=0x7f24a205b000) at ../../gcc/gcc/cgraphunit.cc:2315
> > #17 symbol_table::finalize_compilation_unit (this=0x7f24a205b000) at ../../gcc/gcc/cgraphunit.cc:2589
> > #18 0x0000000000f0932d in compile_file () at ../../gcc/gcc/toplev.cc:476
> > #19 0x0000000000839648 in do_compile () at ../../gcc/gcc/toplev.cc:2158
> > #20 toplev::main (this=this@entry=0x7ffe062c1f2e, argc=<optimized out>, argc@entry=78, argv=<optimized out>, argv@entry=0x7ffe062c2058) at ../../gcc/gcc/toplev.cc:2314
> > #21 0x000000000083ad9e in main (argc=78, argv=0x7ffe062c2058) at ../../gcc/gcc/main.cc:39
> >
> > (Loop is based in process_bb_lives(), looping in the
> > FOR_BB_INSNS_REVERSE_SAFE (bb, curr_insn, next) block starting at
> > about line 696.)
>
> MfG, JBG
>
> --