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 <al...@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 <al...@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
