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.
	* dg.dg/analyzer/pr94851-2.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/uninit-pr61112.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.

1 files changed, 33 insertions, 0 deletions

diff --git a/gcc/testsuite/gcc.c-torture/compile/pr83510.c b/gcc/testsuite/gcc.c-torture/compile/pr83510.c
index 907dd80..fc932e5 100644
--- a/gcc/testsuite/gcc.c-torture/compile/pr83510.c
+++ b/gcc/testsuite/gcc.c-torture/compile/pr83510.c
@@ -3,6 +3,39 @@
    (PR tree-optimization/83510).  */
 
 /* { dg-options "-Warray-bounds" } */
+/* { dg-xfail-if "" { "*-*-*" } { "-Os" } } */
+
+
+/*  This test is XFAILed because thread1 threads a switch statement
+    such that the various cases have been split into different
+    independent blocks.  One of these blocks exposes an arr[i_27]
+    which is later propagated by VRP to be arr[10].  This is an
+    invalid access, but the array bounds code doesn't know it is an
+    unreachable path.
+
+    However, it is not until dom2 that we "know" that the value of the
+    switch index is such that the path to arr[10] is unreachable.  For
+    that matter, it is not until dom3 that we remove the unreachable
+    path.
+
+
+    See:
+    https://gcc.gnu.org/bugzilla/show_bug.cgi?id=83510
+    https://gcc.gnu.org/bugzilla/show_bug.cgi?id=83312
+
+    It's not until here that ranger "knows" that the path is
+    unreachable:
+
+    thread1
+    vrp1		<-- array bounds checking
+    dce2
+    stdarg
+    cdce
+    cselim
+    copyprop
+    ifcombine
+    mergephi3		<-- too late
+*/
 
 extern int get_flag (void);