Re: [PATCH 2/2] Backwards jump threader rewrite with ranger.

[Jeff Law <jeffreyalaw@gmail.com>]

On 7/15/2021 8:57 AM, Aldy Hernandez wrote:
> As mentioned in my previous email, these are some minor changes to the
> previous revision.  All I'm changing here is the call into the solver
> to use range_of_expr and range_of_stmt.  Everything else remains the
> same.
>
> Tested on x86-64 Linux.
>
> On Mon, Jul 5, 2021 at 5:39 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>> PING.
>>
>> Aldy
>>
>> 0003-Backwards-jump-threader-rewrite-with-ranger.patch
>>
>>  From 1774338ddd1f4718884e766aae2fc48b97110c5d Mon Sep 17 00:00:00 2001
>> From: Aldy Hernandez <aldyh@redhat.com>
>> Date: Tue, 15 Jun 2021 12:32:51 +0200
>> Subject: [PATCH 3/5] Backwards jump threader rewrite with ranger.
>>
>> This is a rewrite of the backwards threader with a ranger based solver.
>>
>> The code is divided into two parts: the path solver in
>> gimple-range-path.*, and the path discovery bits in
>> tree-ssa-threadbackward.c.
>>
>> The legacy code is still available with --param=threader-mode=legacy,
>> but will be removed shortly after.
>>
>> gcc/ChangeLog:
>>
>> 	* Makefile.in (tree-ssa-loop-im.o-warn): New.
>> 	* flag-types.h (enum threader_mode): New.
>> 	* params.opt: Add entry for --param=threader-mode.
>> 	* tree-ssa-threadbackward.c (THREADER_ITERATIVE_MODE): New.
>> 	(class back_threader): New.
>> 	(back_threader::back_threader): New.
>> 	(back_threader::~back_threader): New.
>> 	(back_threader::maybe_register_path): New.
>> 	(back_threader::find_taken_edge): New.
>> 	(back_threader::find_taken_edge_switch): New.
>> 	(back_threader::find_taken_edge_cond): New.
>> 	(back_threader::resolve_def): New.
>> 	(back_threader::resolve_phi): New.
>> 	(back_threader::find_paths_to_names): New.
>> 	(back_threader::find_paths): New.
>> 	(dump_path): New.
>> 	(debug): New.
>> 	(thread_jumps::find_jump_threads_backwards): Call ranger threader.
>> 	(thread_jumps::find_jump_threads_backwards_with_ranger): New.
>> 	(pass_thread_jumps::execute): Abstract out code...
>> 	(try_thread_blocks): ...here.
>> 	* tree-ssa-threadedge.c (jump_threader::thread_outgoing_edges):
>> 	Abstract out threading candidate code to...
>> 	(single_succ_to_potentially_threadable_block): ...here.
>> 	* tree-ssa-threadedge.h (single_succ_to_potentially_threadable_block):
>> 	New.
>> 	* tree-ssa-threadupdate.c (register_jump_thread): Return boolean.
>> 	* tree-ssa-threadupdate.h (class jump_thread_path_registry):
>> 	Return bool from register_jump_thread.
>>
>> libgomp/ChangeLog:
>>
>> 	* testsuite/libgomp.graphite/force-parallel-4.c: Adjust for
>> 	threader.
>> 	* testsuite/libgomp.graphite/force-parallel-8.c: Same.
>>
>> gcc/testsuite/ChangeLog:
>>
>> 	* g++.dg/debug/dwarf2/deallocator.C: Adjust for threader.
>> 	* gcc.c-torture/compile/pr83510.c: Same.
>> 	* gcc.dg/loop-unswitch-2.c: Same.
>> 	* gcc.dg/old-style-asm-1.c: Same.
>> 	* gcc.dg/pr68317.c: Same.
>> 	* gcc.dg/pr97567-2.c: Same.
>> 	* gcc.dg/predict-9.c: Same.
>> 	* gcc.dg/shrink-wrap-loop.c: Same.
>> 	* gcc.dg/sibcall-1.c: Same.
>> 	* gcc.dg/tree-ssa/builtin-sprintf-3.c: Same.
>> 	* gcc.dg/tree-ssa/pr21001.c: Same.
>> 	* gcc.dg/tree-ssa/pr21294.c: Same.
>> 	* gcc.dg/tree-ssa/pr21417.c: Same.
>> 	* gcc.dg/tree-ssa/pr21458-2.c: Same.
>> 	* gcc.dg/tree-ssa/pr21563.c: Same.
>> 	* gcc.dg/tree-ssa/pr49039.c: Same.
>> 	* gcc.dg/tree-ssa/pr61839_1.c: Same.
>> 	* gcc.dg/tree-ssa/pr61839_3.c: Same.
>> 	* gcc.dg/tree-ssa/pr77445-2.c: Same.
>> 	* gcc.dg/tree-ssa/split-path-4.c: Same.
>> 	* gcc.dg/tree-ssa/ssa-dom-thread-11.c: Same.
>> 	* gcc.dg/tree-ssa/ssa-dom-thread-12.c: Same.
>> 	* gcc.dg/tree-ssa/ssa-dom-thread-14.c: Same.
>> 	* gcc.dg/tree-ssa/ssa-dom-thread-18.c: Same.
>> 	* gcc.dg/tree-ssa/ssa-dom-thread-6.c: Same.
>> 	* gcc.dg/tree-ssa/ssa-dom-thread-7.c: Same.
>> 	* gcc.dg/tree-ssa/ssa-fre-48.c: Same.
>> 	* gcc.dg/tree-ssa/ssa-thread-11.c: Same.
>> 	* gcc.dg/tree-ssa/ssa-thread-12.c: Same.
>> 	* gcc.dg/tree-ssa/ssa-thread-14.c: Same.
>> 	* gcc.dg/tree-ssa/vrp02.c: Same.
>> 	* gcc.dg/tree-ssa/vrp03.c: Same.
>> 	* gcc.dg/tree-ssa/vrp05.c: Same.
>> 	* gcc.dg/tree-ssa/vrp06.c: Same.
>> 	* gcc.dg/tree-ssa/vrp07.c: Same.
>> 	* gcc.dg/tree-ssa/vrp09.c: Same.
>> 	* gcc.dg/tree-ssa/vrp19.c: Same.
>> 	* gcc.dg/tree-ssa/vrp20.c: Same.
>> 	* gcc.dg/tree-ssa/vrp33.c: Same.
>> 	* gcc.dg/uninit-pred-9_b.c: Same.
>> 	* gcc.dg/vect/bb-slp-16.c: Same.
>> 	* gcc.target/i386/avx2-vect-aggressive.c: Same.
>> 	* gcc.dg/tree-ssa/ranger-threader-1.c: New test.
>> 	* gcc.dg/tree-ssa/ranger-threader-2.c: New test.
>> 	* gcc.dg/tree-ssa/ranger-threader-3.c: New test.
>> 	* gcc.dg/tree-ssa/ranger-threader-4.c: New test.
>> 	* gcc.dg/tree-ssa/ranger-threader-5.c: New test.
>> ---
>>   gcc/Makefile.in                               |   5 +
>>   gcc/flag-types.h                              |   7 +
>>   gcc/params.opt                                |  17 +
>>   .../g++.dg/debug/dwarf2/deallocator.C         |   3 +-
>>   gcc/testsuite/gcc.c-torture/compile/pr83510.c |  33 ++
>>   gcc/testsuite/gcc.dg/loop-unswitch-2.c        |   2 +-
>>   gcc/testsuite/gcc.dg/old-style-asm-1.c        |   5 +-
>>   gcc/testsuite/gcc.dg/pr68317.c                |   4 +-
>>   gcc/testsuite/gcc.dg/pr97567-2.c              |   2 +-
>>   gcc/testsuite/gcc.dg/predict-9.c              |   4 +-
>>   gcc/testsuite/gcc.dg/shrink-wrap-loop.c       |  53 ++
>>   gcc/testsuite/gcc.dg/sibcall-1.c              |  10 +
>>   .../gcc.dg/tree-ssa/builtin-sprintf-3.c       |  25 +-
>>   gcc/testsuite/gcc.dg/tree-ssa/pr21001.c       |   1 +
>>   gcc/testsuite/gcc.dg/tree-ssa/pr21294.c       |   1 +
>>   gcc/testsuite/gcc.dg/tree-ssa/pr21417.c       |   2 +-
>>   gcc/testsuite/gcc.dg/tree-ssa/pr21458-2.c     |   2 +-
>>   gcc/testsuite/gcc.dg/tree-ssa/pr21563.c       |   2 +-
>>   gcc/testsuite/gcc.dg/tree-ssa/pr49039.c       |   2 +-
>>   gcc/testsuite/gcc.dg/tree-ssa/pr61839_1.c     |   2 +-
>>   gcc/testsuite/gcc.dg/tree-ssa/pr61839_3.c     |   2 +-
>>   gcc/testsuite/gcc.dg/tree-ssa/pr77445-2.c     |   2 +-
>>   .../gcc.dg/tree-ssa/ranger-threader-1.c       |  20 +
>>   .../gcc.dg/tree-ssa/ranger-threader-2.c       |  39 ++
>>   .../gcc.dg/tree-ssa/ranger-threader-3.c       |  41 ++
>>   .../gcc.dg/tree-ssa/ranger-threader-4.c       |  83 +++
>>   .../gcc.dg/tree-ssa/ranger-threader-5.c       |  80 +++
>>   gcc/testsuite/gcc.dg/tree-ssa/split-path-4.c  |   4 +-
>>   .../gcc.dg/tree-ssa/ssa-dom-thread-11.c       |   2 +-
>>   .../gcc.dg/tree-ssa/ssa-dom-thread-12.c       |   2 +-
>>   .../gcc.dg/tree-ssa/ssa-dom-thread-14.c       |   1 +
>>   .../gcc.dg/tree-ssa/ssa-dom-thread-18.c       |   5 +-
>>   .../gcc.dg/tree-ssa/ssa-dom-thread-6.c        |   4 +-
>>   .../gcc.dg/tree-ssa/ssa-dom-thread-7.c        |   1 +
>>   gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-48.c    |   2 +-
>>   gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-11.c |   1 +
>>   gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-12.c |   2 +-
>>   gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-14.c |   1 +
>>   gcc/testsuite/gcc.dg/tree-ssa/vrp02.c         |   2 +-
>>   gcc/testsuite/gcc.dg/tree-ssa/vrp03.c         |   2 +-
>>   gcc/testsuite/gcc.dg/tree-ssa/vrp05.c         |   2 +-
>>   gcc/testsuite/gcc.dg/tree-ssa/vrp06.c         |   2 +-
>>   gcc/testsuite/gcc.dg/tree-ssa/vrp07.c         |   2 +-
>>   gcc/testsuite/gcc.dg/tree-ssa/vrp09.c         |   2 +-
>>   gcc/testsuite/gcc.dg/tree-ssa/vrp19.c         |   2 +-
>>   gcc/testsuite/gcc.dg/tree-ssa/vrp20.c         |   2 +-
>>   gcc/testsuite/gcc.dg/tree-ssa/vrp33.c         |   2 +-
>>   gcc/testsuite/gcc.dg/uninit-pred-9_b.c        |   1 +
>>   gcc/testsuite/gcc.dg/vect/bb-slp-16.c         |   7 +
>>   .../gcc.target/i386/avx2-vect-aggressive.c    |   2 +-
>>   gcc/tree-ssa-threadbackward.c                 | 475 +++++++++++++++++-
>>   gcc/tree-ssa-threadedge.c                     |  20 +-
>>   gcc/tree-ssa-threadedge.h                     |   3 +-
>>   gcc/tree-ssa-threadupdate.c                   |  12 +-
>>   gcc/tree-ssa-threadupdate.h                   |   2 +-
>>   .../libgomp.graphite/force-parallel-4.c       |   1 +
>>   .../libgomp.graphite/force-parallel-8.c       |   2 +
>>   57 files changed, 963 insertions(+), 54 deletions(-)
>>   create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ranger-threader-1.c
>>   create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ranger-threader-2.c
>>   create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ranger-threader-3.c
>>   create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ranger-threader-4.c
>>   create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ranger-threader-5.c
>>
>> diff --git a/gcc/Makefile.in b/gcc/Makefile.in
>> index 863f1256811..0e205a41ac3 100644
>> --- a/gcc/Makefile.in
>> +++ b/gcc/Makefile.in
>> @@ -223,6 +223,11 @@ gimple-match.o-warn = -Wno-unused
>>   generic-match.o-warn = -Wno-unused
>>   dfp.o-warn = -Wno-strict-aliasing
>>   
>> +# maybe_emit_free_warning() is picking up the inlined location for the
>> +# warning, not the source of the original va_heap::release() function
>> +# which has a pragma disabling this warning.
>> +tree-ssa-loop-im.o-warn = -Wno-free-nonheap-object
I think some of Martin's work may help here, but I'm not sure if it's 
all gone in yet.  It might be worth syncing with him on the state of the 
improvements to how inlining and warnings interact.  If his work does 
fix the problem here, this hunk can be removed as a distinct follow-up.

>> diff --git a/gcc/params.opt b/gcc/params.opt
>> index 92b003e38cb..f1f47b44215 100644
>> --- a/gcc/params.opt
>> +++ b/gcc/params.opt
>> @@ -1010,6 +1010,23 @@ Maximum depth of DFS walk used by modref escape analysis.
>>   Common Joined UInteger Var(param_modref_max_escape_points) Init(256) Param Optimization
>>   Maximum number of escape points tracked by modref per SSA-name.
>>   
>> +-param=threader-iterative=
>> +Common Joined UInteger Var(param_threader_iterative) Init(0) Param Optimization
>> +Run backwards threader in iterative mode.
Presumably this is going away?  I thought the iterative mode was just 
for debugging/evaluation purposes.

I only glossed over the testsuite changes.

God I love how much you've refactored here.  Lots of small, easy to 
understand functions.

>> +
>> +// If any of the incoming edges for a PHI resolves the current path,
>> +// register the path(s), and return TRUE.
>> +
>> +bool
>> +back_threader::resolve_phi (gphi *phi, bitmap interesting)
[ ... ]
It might be useful to indicate somewhere what "resolving the current 
path" means.  I kind of figured it out as I was walking through the 
patch, but my first thought had it reversed.


diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c
>> index 6ce32644aa5..ea5c37a2c65 100644
>> --- a/gcc/tree-ssa-threadedge.c
>> +++ b/gcc/tree-ssa-threadedge.c
>> @@ -1335,6 +1335,18 @@ jump_threader::thread_across_edge (edge e)
>>     m_avail_exprs_stack->pop_to_marker ();
>>   }
>>   
>> +/* Return TRUE if BB has a single successor to a block with multiple
>> +   incoming and outgoing edges.  */
>> +
>> +bool
>> +single_succ_to_potentially_threadable_block (basic_block bb)
>> +{
>> +  int flags = (EDGE_IGNORE | EDGE_COMPLEX | EDGE_ABNORMAL);
>> +  return (single_succ_p (bb)
>> +	  && (single_succ_edge (bb)->flags & flags) == 0
>> +	  && potentially_threadable_block (single_succ (bb)));
>> +}
Note on many occasions I've pondered killing these checks.  The forward 
jump threader in particular uses them to narrow its search space.  But 
I've regularly found that they're suppressing useful paths.  The worry, 
of course, is the compile-time cost.


I don't see anything in here that is worrisome.  I'd like to see the 
iterating bits disappear, but I'd also understand if you want to keep 
them for debugging/evaluation purposes in the immediate term.

OK for the trunk.

jeff