diff options
| -rw-r--r-- | gcc/testsuite/gcc.dg/old-style-asm-1.c | 2 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/predict-9.c | 2 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/builtin-sprintf-3.c | 2 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/pr21001.c | 2 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/pr21563.c | 2 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-11.c | 6 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-14.c | 2 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-48.c | 2 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-20.c | 30 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-21.c | 42 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-22.c | 41 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-23.c | 25 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-24.c | 52 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/vrp06.c | 2 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/vrp20.c | 2 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/vrp33.c | 2 | ||||
| -rw-r--r-- | gcc/tree-cfg.c | 12 | ||||
| -rw-r--r-- | gcc/tree-ssa-threadbackward.c | 543 | ||||
| -rw-r--r-- | gcc/tree-ssa-threadupdate.c | 209 |
19 files changed, 906 insertions, 74 deletions
diff --git a/gcc/testsuite/gcc.dg/old-style-asm-1.c b/gcc/testsuite/gcc.dg/old-style-asm-1.c index 8af007795a7..ac981228738 100644 --- a/gcc/testsuite/gcc.dg/old-style-asm-1.c +++ b/gcc/testsuite/gcc.dg/old-style-asm-1.c @@ -1,6 +1,6 @@ /* PR inline-asm/8832 */ /* { dg-do compile } */ -/* { dg-options "-O2 -dP" } */ +/* { dg-options "-O2 -dP -fdisable-tree-ethread -fdisable-tree-thread1 -fdisable-tree-thread2 -fdisable-tree-thread3 -fdisable-tree-thread4" } */ /* Verify that GCC doesn't optimize old style asm instructions. */ diff --git a/gcc/testsuite/gcc.dg/predict-9.c b/gcc/testsuite/gcc.dg/predict-9.c index ec467519504..29b366a01b3 100644 --- a/gcc/testsuite/gcc.dg/predict-9.c +++ b/gcc/testsuite/gcc.dg/predict-9.c @@ -1,5 +1,5 @@ /* { dg-do compile } */ -/* { dg-options "-O2 -fdisable-tree-evrp -fdump-tree-profile_estimate" } */ +/* { dg-options "-O2 -fdisable-tree-ethread -fdisable-tree-evrp -fdump-tree-profile_estimate" } */ extern int global; extern int global2; diff --git a/gcc/testsuite/gcc.dg/tree-ssa/builtin-sprintf-3.c b/gcc/testsuite/gcc.dg/tree-ssa/builtin-sprintf-3.c index fae2a1b73ea..e47317cc644 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/builtin-sprintf-3.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/builtin-sprintf-3.c @@ -3,7 +3,7 @@ that the sprintf return value (or value range) optimization is not performed for an unknown string. */ /* { dg-do compile } */ -/* { dg-options "-O2 -Wall -Werror -fdump-tree-optimized -fprintf-return-value" } */ +/* { dg-options "-O2 -Wall -Werror -fdump-tree-optimized -fprintf-return-value -fdisable-tree-thread1 -fdisable-tree-thread2 -fdisable-tree-thread3 -fdisable-tree-thread4" } */ #define INT_MAX __INT_MAX__ #define INT_MIN (-INT_MAX - 1) diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr21001.c b/gcc/testsuite/gcc.dg/tree-ssa/pr21001.c index 719360a015f..785a4790817 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/pr21001.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr21001.c @@ -5,7 +5,7 @@ range information out of the conditional. */ /* { dg-do compile } */ -/* { dg-options "-O2 -fno-tree-dominator-opts -fno-tree-fre -fdisable-tree-evrp -fdump-tree-vrp1-details" } */ +/* { dg-options "-O2 -fno-tree-dominator-opts -fno-tree-fre -fdisable-tree-ethread -fdisable-tree-thread1 -fdisable-tree-evrp -fdump-tree-vrp1-details" } */ int foo (int a) diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr21563.c b/gcc/testsuite/gcc.dg/tree-ssa/pr21563.c index 9c67a3acb46..c7ff3774e9e 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/pr21563.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr21563.c @@ -2,7 +2,7 @@ Make sure VRP folds the second "if" statement. */ /* { dg-do compile } */ -/* { dg-options "-O2 -fno-tree-dominator-opts -fdisable-tree-evrp -fdump-tree-vrp1-details" } */ +/* { dg-options "-O2 -fno-tree-dominator-opts -fdisable-tree-ethread -fdisable-tree-thread1 -fdisable-tree-evrp -fdump-tree-vrp1-details" } */ int foo (int a) diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-11.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-11.c index f42d64bed71..0a657606a0f 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-11.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-11.c @@ -1,5 +1,9 @@ /* { dg-do compile { target { ! logical_op_short_circuit } } } */ -/* { dg-options "-O2 -fdump-tree-dom2-details" } */ +/* { dg-options "-O2 -fdisable-tree-thread1 -fdisable-tree-thread2 -fdump-tree-dom2-details" } */ + +/* NOTE: This looks like a test that VRP could not thread, but we can + now thread as early as thread1. We should make a separate test out + of this for the backwards threader. */ static int *bb_ticks; extern void frob (void); diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-14.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-14.c index 2d97f86fa28..2bb5e7681d3 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-14.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-14.c @@ -1,5 +1,5 @@ /* { dg-do compile { target { ! logical_op_short_circuit } } } */ -/* { dg-options "-O2 -fdump-tree-dom2-details -w" } */ +/* { dg-options "-O2 -fdump-tree-dom2-details -w -fdisable-tree-thread1 -fdisable-tree-ethread " } */ enum optab_methods { diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-48.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-48.c index b3d610204da..78eba61ae3e 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-48.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-48.c @@ -1,5 +1,5 @@ /* { dg-do compile } */ -/* { dg-options "-O -fdump-tree-fre1-details" } */ +/* { dg-options "-O -fdisable-tree-ethread -fdump-tree-fre1-details" } */ int foo (int i) { diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-20.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-20.c new file mode 100644 index 00000000000..713c9b298cd --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-20.c @@ -0,0 +1,30 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fgimple -fdump-tree-ethread-stats" } */ + +/* Test that we thread 2 -> 3 -> 5 in the early threader. */ + +int no; +int yes; + +void __GIMPLE (startwith ("ethread")) foo (int x) +{ + bb_2: + if (x == 222) + goto bb_3; + else + goto bb_5; + + bb_3: + if (x == 444) + goto bb_4; + else + goto bb_5; + + bb_4: + no = 123; + + bb_5: + yes = 456; +} + +/* { dg-final { scan-tree-dump-times "Jumps threaded: 1" 1 "ethread" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-21.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-21.c new file mode 100644 index 00000000000..30ef492ec39 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-21.c @@ -0,0 +1,42 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fgimple -fdump-tree-thread1-details" } */ + +/* Test that we can thread multiple paths that start from the same BB. */ + +int never_exec; +int stuff; + +void __GIMPLE (startwith ("thread1")) foo (int x, int fork) +{ + /* There should be two paths reaching bb_5 from here that must be threaded: + 2->3->5 + 2->3->4->5. */ + bb_2: + if (x == 24) + goto bb_3; + else + goto bb_7; + + bb_3: + if (fork) + goto bb_5; + else + goto bb_4; + + bb_4: + stuff = 1; + + bb_5: + if (x == 42) + goto bb_6; + else + goto bb_7; + + bb_6: + never_exec = 1; + + bb_7: + return; +} + +/* { dg-final { scan-tree-dump-times "Registering FSM jump thread: \\(2, 3\\)" 2 "thread1" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-22.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-22.c new file mode 100644 index 00000000000..85ea401e29d --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-22.c @@ -0,0 +1,41 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fgimple -fdump-tree-thread1-details" } */ + +/* Test that we thread multiple range-based paths out of bb2. */ + +int greather_than_10; +int less_than_12; +int equals_11; + +void __GIMPLE (startwith ("thread1")) foo (int v) +{ + bb_2: + if (v > 10) + goto bb_3; + else + goto bb_4; + + bb_3: + greather_than_10 = 1; + + bb_4: + if (v <= 11) + goto bb_5; + else + goto bb_7; + + bb_5: + less_than_12 = 1; + if (v == 11) + goto bb_6; + else + goto bb_7; + + bb_6: + equals_11 = 1; + + bb_7: + return; +} + +/* { dg-final { scan-tree-dump-times "Registering FSM jump thread: \\(2, " 3 "thread1" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-23.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-23.c new file mode 100644 index 00000000000..5dbbe4af0d8 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-23.c @@ -0,0 +1,25 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-ethread-stats" } */ + +/* Test that we can thread a switch for which we have a known range. */ + +extern void there(); +int stuff10, stuff20; +void foo(int x) +{ + if (x == 50 || x == 80) goto doit; + there(); +doit: + switch (x) { + case 10: + stuff10 = 1; + break; + case 20: + stuff20 = 2; + break; + default: + break; + } +} + +/* { dg-final { scan-tree-dump-times "Jumps threaded: 1" 1 "ethread" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-24.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-24.c new file mode 100644 index 00000000000..425ba363d20 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-24.c @@ -0,0 +1,52 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fgimple" } */ + +/* FIXME: This test currently does nothing. It is a placeholder for + when the ranger handles PHIs and the threader can determine that + bb4 -> bb5 -> bb7 can be threaded. + + We should test that 4->5->7 has been threaded. */ + +int result; +int shouldnt_happen_from_bb4; + +void __GIMPLE (startwith ("thread1")) foo (int arg1, int arg2) +{ + int v1; + int _14; + unsigned int _15; + unsigned int _16; + + bb_2: + if (arg1 == arg2) + goto bb_3; + else + goto bb_4; + + bb_3: + result = 1; + goto bb_5; + + bb_4: + result = 2; + + bb_5: + v1_595 = __PHI (bb_3: arg1, bb_4: 0); + _14 = v1_595 * 3600; + _15 = (unsigned int) _14; + _16 = _15 / 60U; + if (_16 > 389U) + goto bb_6; + else + goto bb_7; + + bb_6: + shouldnt_happen_from_bb4 = 0; + goto bb_8; + + bb_7: + result = 3; + + bb_8: + return; +} diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp06.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp06.c index a872bc43731..39c6fc549cb 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/vrp06.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp06.c @@ -1,5 +1,5 @@ /* { dg-do compile } */ -/* { dg-options "-O2 -fdisable-tree-evrp -fdump-tree-vrp1" } */ +/* { dg-options "-O2 -fdisable-tree-ethread -fdisable-tree-thread1 -fdisable-tree-evrp -fdump-tree-vrp1" } */ int baz (void); diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp20.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp20.c index 4a3b0d73648..9da5a006c44 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/vrp20.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp20.c @@ -1,5 +1,5 @@ /* { dg-do compile } */ -/* { dg-options "-fwrapv -O1 -fno-tree-fre -fdisable-tree-evrp -ftree-vrp -fdump-tree-vrp1" } */ +/* { dg-options "-fwrapv -O1 -fdisable-tree-ethread -fno-tree-fre -fdisable-tree-evrp -ftree-vrp -fdump-tree-vrp1" } */ extern void abort (); extern void exit (int); diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp33.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp33.c index 75fefa49925..2ec18ebaa0f 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/vrp33.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp33.c @@ -1,5 +1,5 @@ /* { dg-do compile } */ -/* { dg-options "-O2 -fdump-tree-vrp1 -fno-tree-fre" } */ +/* { dg-options "-O2 -fdisable-tree-ethread -fdisable-tree-thread1 -fdump-tree-vrp1 -fno-tree-fre" } */ /* This is from PR14052. */ diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c index 99d1f1e1af8..b7848e852fe 100644 --- a/gcc/tree-cfg.c +++ b/gcc/tree-cfg.c @@ -2314,7 +2314,11 @@ find_taken_edge_cond_expr (basic_block bb, tree val) /* Given an INTEGER_CST VAL and the entry block BB to a SWITCH_EXPR statement, determine which edge will be taken out of the block. Return - NULL if any edge may be taken. */ + NULL if any edge may be taken. + + Note: As a special case, an empty VAL means the taken edge should + be the default case. It doesn't look like we ever get an empty VAL + for anything else, so it *SHOULD* be safe to use (??). */ static edge find_taken_edge_switch_expr (gswitch *switch_stmt, basic_block bb, @@ -2324,9 +2328,11 @@ find_taken_edge_switch_expr (gswitch *switch_stmt, basic_block bb, edge e; tree taken_case; - if (gimple_switch_num_labels (switch_stmt) == 1) + if (gimple_switch_num_labels (switch_stmt) == 1 + /* An empty VAL means take the default case. */ + || !val) taken_case = gimple_switch_default_label (switch_stmt); - else if (! val || TREE_CODE (val) != INTEGER_CST) + else if (TREE_CODE (val) != INTEGER_CST) return NULL; else taken_case = find_case_label_for_value (switch_stmt, val); diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c index 12bc80350f5..e50a0f1f8b7 100644 --- a/gcc/tree-ssa-threadbackward.c +++ b/gcc/tree-ssa-threadbackward.c @@ -37,9 +37,322 @@ along with GCC; see the file COPYING3. If not see #include "tree-phinodes.h" #include "tree-inline.h" #include "tree-vectorizer.h" +#include "stringpool.h" +#include "tree-vrp.h" +#include "tree-ssanames.h" +#include "ssa-range-gen.h" +#include "domwalk.h" + +#include "graph.h" +#include "tree-pretty-print.h" +#include "gimple-pretty-print.h" static int max_threaded_paths; +DEBUG_FUNCTION +void graphme() +{ + system("rm -f /tmp/base.dot"); + print_graph_cfg("/tmp/base", cfun); + system("~/bin/dotview"); +} + +/* Class to generate all paths from an SSA name to a use of NAME. + Note: we discard any paths greater than PARAM_MAX_FSM_THREAD_LENGTH. + + Use it like this: + + bb_paths p; + p.calculate (x_99, some_bb); + for (unsigned i = 0; i < p.length (); i++) + { + vec<basic_block> path = p[i]; + do_funky_things (path); + } + */ + +class bb_paths +{ + /* All paths from DEF_BB to USE_BB. */ + vec< vec<basic_block> > all_paths; + /* The SSA name we are interested in. */ + tree name; + /* The BB defining NAME. */ + basic_block def_bb; + /* The BB using NAME. */ + basic_block use_bb; + /* One ranger for everything so ranges get cached. */ + path_ranger ranger; + + void calculate_1 (vec<basic_block> &path, basic_block bb, + hash_set<basic_block> &visited); + void prune_duplicate_paths (void); + void prune_irrelevant_range_blocks (vec <basic_block> &path); + void dump_one_path (FILE *out, const vec<basic_block> &path); + + public: + bb_paths (); + ~bb_paths (); + void calculate (tree ssa, basic_block use); + /* Calculate the range for path number I and store it in R. + Return TRUE if R is non empty. */ + bool range_of_path (irange &r, unsigned i) + { + return ranger.path_range (r, name, all_paths[i], path_ranger::REVERSE); + } + /* Attempt to fold STMT given VAR and its known range VAR_RANGE. + Store the resulting range in R and return TRUE if R is non + empty. */ + bool range_of_stmt (irange &r, gimple *stmt, tree var, + const irange var_range) + { + return ranger.range_of_def (r, stmt, var, var_range); + } + const vec<basic_block> &operator[] (unsigned i) const { return all_paths[i]; } + vec<basic_block> &operator[] (unsigned i) { return all_paths[i]; } + unsigned length () const { return all_paths.length (); } + void dump (); +}; + +bb_paths::bb_paths () +{ + all_paths = vNULL; +} + +bb_paths::~bb_paths () +{ + for (unsigned i = 0; i < all_paths.length (); ++i) + all_paths[i].release (); + all_paths.release (); +} + +/* Generate all paths from the definition of SSA to its USE. + Accumulate the paths in ALL_PATHS. */ + +void +bb_paths::calculate (tree ssa, basic_block use) +{ + all_paths = vNULL; + name = ssa; + use_bb = use; + if (SSA_NAME_IS_DEFAULT_DEF (name)) + def_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun); + else + def_bb = gimple_bb (SSA_NAME_DEF_STMT (name)); + + /* A path where the use and the definition are in the same block, is + a path of one block, and can be handled specially. */ + if (use_bb == def_bb) + { + vec<basic_block> v; + v.create (1); + v.quick_push (use_bb); + all_paths.safe_push (v); + return; + } + + hash_set<basic_block> visited; + auto_vec<basic_block> path; + calculate_1 (path, use_bb, visited); + prune_duplicate_paths (); +} + +/* Helper function for calculate(). Calculate all paths from DEF_BB + to BB and store them into ALL_PATHS. + + PATH is the current path being accumulated. VISITED is a hash of + visited blocks. */ + +void +bb_paths::calculate_1 (vec<basic_block> &path, basic_block bb, + hash_set<basic_block> &visited) +{ + if (!def_bb) + return; + /* Discard loops. */ + if (visited.add (bb)) + return; + if ((int)path.length () + 1 > PARAM_VALUE (PARAM_MAX_FSM_THREAD_LENGTH)) + return; + + /* As an optimization, we disregard paths that cross loops. Since + profitable_jump_thread_path() will ignore them, we can avoid + putting them in the queue altogether. */ + if (!path.is_empty () && path[0]->loop_father != bb->loop_father) + return; + + path.safe_push (bb); + + edge e; + edge_iterator ei; + FOR_EACH_EDGE (e, ei, bb->preds) + { + /* If we reached the defining block, we're at the top, and have a + complete path. */ + if (e->src == def_bb) + { + /* If we've already seen DEF_BB, we have a complete loop + back to DEF_BB. We discard loops, so... */ + if (visited.contains (def_bb)) + return; + + /* As mentioned in profitable_jump_thread_path(), the last + entry in a path (DEF_BB in our case) represents the block + with an outgoing edge that will redirect to the jump + threading path. Thus, we don't care if DEF_BB lives in a + loop different than the rest of the path we are + accumulating. This is why we don't perform the + loop_father optimization at the beginning of this + function. */ + + /* Push the DEF_BB for completeness sake. */ + path.safe_push (def_bb); + vec<basic_block> t = path.copy (); + all_paths.safe_push (t); + path.pop (); + } + else + calculate_1 (path, e->src, visited); + } + path.pop (); + visited.remove (bb); +} + +/* If we have a path that generates range information for SSA, any + blocks until the first block that contains range information is + irrelevant for the range. Prune such blocks. */ + +void +bb_paths::prune_irrelevant_range_blocks (vec <basic_block> &path) +{ + /* If the path is just one block, we have a path where the + definition and the use are in the same BB. In this case, there + is nothing to do. */ + if (path.length () == 1) + return; + + for (int i = path.length () - 1; i > 0; --i) + { + irange r; + edge e; + + gcc_assert (e = find_edge (path[i], path[i - 1])); + /* ?? When the path ranger can understand copies, we should look + into using it instead of gori. For instance, we may not have + a range here, but the path ranger may realize that earlier + than E we have a range because of a copy??. */ + if (ranger.range_on_edge (r, name, e)) + { + /* Remove anything that came before here. */ + path.truncate (i + 1); + return; + } + } + path.truncate (0); +} + +/* Clean-up paths by removing any irrelevant blocks in the paths + themselves and then removing any duplicate paths. */ + +void +bb_paths::prune_duplicate_paths (void) +{ + if (all_paths.is_empty ()) + return; + + vec<basic_block> prev_path = vNULL; + vec< vec<basic_block> > new_all_paths; + /* If we prune any duplicates, new_all_paths will have some extra + memory allocated. We dont' care, as this won't live long. */ + new_all_paths.create (all_paths.length ()); + + /* Get rid of useless blocks per path, and then accumulate all + non-duplicate paths into new_all_paths. Removing duplicates is + easy because all_paths is already sorted. */ + for (unsigned i = 0; i < all_paths.length (); ++i) + { + vec<basic_block> path = all_paths[i]; + + prune_irrelevant_range_blocks (path); + if (path.is_empty ()) + { + path.release (); + continue; + } + + /* Is this a duplicate of the last known path? */ + bool duplicate = false; + if (prev_path.length () == path.length ()) + { + duplicate = true; + for (unsigned i = 0; i < path.length (); ++i) + if (path[i] != prev_path[i]) + { + duplicate = false; + break; + } + } + if (duplicate) + path.release (); + else + { + prev_path = path; + new_all_paths.safe_push (path); + } + } + all_paths.release (); + all_paths = new_all_paths; +} + +/* Helper function for bb_paths::dump to dump one PATH to OUT. */ + +void +bb_paths::dump_one_path (FILE *out, const vec<basic_block> &path) +{ + fprintf (out, "\tpath: "); + if (path.is_empty ()) + { + fprintf (out, "<empty>\n"); + return; + } + for (int i = path.length () - 1; i > 0; --i) + { + fprintf (out, "bb%d", path[i]->index); + edge e = find_edge (path[i], path[i - 1]); + gcc_assert (e); + fprintf (out, " => "); + } + fprintf (out, "bb%d\n", path[0]->index); +} + +/* Dump all available paths. */ + +void +bb_paths::dump () +{ + if (all_paths.is_empty ()) + return; + + fprintf (stderr, "range path to BB%d for SSA = ", use_bb->index); + print_generic_stmt (stderr, name, 0); + + for (unsigned i = 0; i < length (); ++i) + { + irange r; + vec<basic_block> path = all_paths[i]; + + dump_one_path (stderr, path); + if (range_of_path (r, i)) + { + fprintf (stderr, "\t "); + r.dump (); + } + else + fprintf (stderr, "\n"); + } + fprintf (stderr, "-----------------------------\n"); +} + /* Simple helper to get the last statement from BB, which is assumed to be a control statement. Return NULL if the last statement is not a control statement. */ @@ -94,13 +407,94 @@ fsm_find_thread_path (basic_block start_bb, basic_block end_bb, return false; } +/* Try to evaluate the control statement and see if we can fold to a + constant. If we do, set RESULT to it and return TRUE. + Otherwise, return FALSE. + + For GIMPLE_COND we evaluate the control statement and set the + substituted true/false value in RESULT. For GIMPLE_SWITCH we set + RESULT to NULL if evaluating the switch will yield the default + case. */ +static bool +resolve_control_statement (gimple *stmt, tree name, + const irange &range_for_name, tree &result, + bb_paths &paths) +{ + wide_int singleton; + switch (gimple_code (stmt)) + { + case GIMPLE_COND: + { + /* It looks like NAME is not necessarily the same SSA name as + the LHS conditional here. Look at the LHS to make sure + the ranger gets the right range. */ + tree var = gimple_cond_lhs (stmt); + irange r; + if (!paths.range_of_stmt (r, stmt, var, range_for_name) + || !r.singleton_p (singleton)) + return false; + result = wide_int_to_tree (TREE_TYPE (name), singleton); + return true; + } + case GIMPLE_SWITCH: + { + /* Handle the simple case fast. */ + if (range_for_name.singleton_p (singleton)) + { + result = wide_int_to_tree (TREE_TYPE (name), singleton); + return true; + } + gswitch *gs = as_a <gswitch *> (stmt); + for (unsigned i = 1; i < gimple_switch_num_labels (gs); ++i) + { + tree label = gimple_switch_label (gs, i); + tree case_low = CASE_LOW (label); + tree case_high = CASE_HIGH (label); + if (!case_high) + case_high = case_low; + irange label_range (TREE_TYPE (name), case_low, case_high); + /* If NAME can fall into one of the switch cases, we can't + be sure where the switch will land. */ + if (!irange_intersect (range_for_name, label_range).empty_p ()) + return false; + /* If we have an exact match, for example, a case of 3..10 + with a known range of [3,10], then we know we will + always select this case. Set RESULT to any number + within the range so find_taken_edge() can find the + right case. + + ?? Is this even worth the effort? */ + if (range_for_name == label_range) + { + wide_int any_number_in_range = range_for_name.lower_bound (); + result = wide_int_to_tree (TREE_TYPE (name), + any_number_in_range); + return true; + } + } + /* If we couldn't find anything, the only alternative is that + we will always select the default case. */ + result = NULL; + return true; + } + case GIMPLE_GOTO: + if (!range_for_name.singleton_p (singleton)) + return false; + result = wide_int_to_tree (TREE_TYPE (name), singleton); + return true; + default: + gcc_unreachable (); + return false; + } +} + /* Examine jump threading path PATH to which we want to add BBI. If the resulting path is profitable to thread, then return the final taken edge from the path, NULL otherwise. NAME is the SSA_NAME of the variable we found to have a constant - value on PATH. ARG is the constant value of NAME on that path. + value on PATH. RANGE_FOR_NAME is the range of NAME on that path. BBI will be appended to PATH when we have a profitable jump threading path. Callers are responsible for removing BBI from PATH in that case. @@ -110,8 +504,10 @@ fsm_find_thread_path (basic_block start_bb, basic_block end_bb, static edge profitable_jump_thread_path (vec<basic_block> &path, - basic_block bbi, tree name, tree arg, - bool speed_p, bool *creates_irreducible_loop) + basic_block bbi, + tree name, const irange &range_for_name, + bool speed_p, bool *creates_irreducible_loop, + bb_paths &paths) { /* Note BBI is not in the path yet, hence the +1 in the test below to make sure BBI is accounted for in the path length test. */ @@ -146,6 +542,14 @@ profitable_jump_thread_path (vec<basic_block> &path, return NULL; } + if (range_for_name.empty_p ()) + return NULL; + + gimple *stmt = get_gimple_control_stmt (path[0]); + tree arg; + if (!resolve_control_statement (stmt, name, range_for_name, arg, paths)) + return NULL; + /* Add BBI to the path. From this point onward, if we decide we the path is not profitable to thread, we must remove BBI from the path. */ @@ -267,9 +671,6 @@ profitable_jump_thread_path (vec<basic_block> &path, threaded_through_latch = true; } - gimple *stmt = get_gimple_control_stmt (path[0]); - gcc_assert (stmt); - /* We are going to remove the control statement at the end of the last block in the threading path. So don't count it against our statement count. */ @@ -282,19 +683,6 @@ profitable_jump_thread_path (vec<basic_block> &path, " Overall: %i insns\n", stmt_insns, n_insns); - /* We have found a constant value for ARG. For GIMPLE_SWITCH - and GIMPLE_GOTO, we use it as-is. However, for a GIMPLE_COND - we need to substitute, fold and simplify so we can determine - the edge taken out of the last block. */ - if (gimple_code (stmt) == GIMPLE_COND) - { - enum tree_code cond_code = gimple_cond_code (stmt); - - /* We know the underyling format of the condition. */ - arg = fold_binary (cond_code, boolean_type_node, - arg, gimple_cond_rhs (stmt)); - } - /* If this path threaded through the loop latch back into the same loop and the destination does not dominate the loop latch, then this thread would create an irreducible loop. @@ -444,9 +832,8 @@ convert_and_register_jump_thread_path (vec<basic_block> &path, edge taken_edge) --max_threaded_paths; } -/* While following a chain of SSA_NAME definitions, we jumped from a - definition in LAST_BB to a definition in NEW_BB (walking - backwards). +/* While following a chain of SSA_NAME definitions, we jumped from a definition + in LAST_BB to a definition in NEW_BB (walking backwards). Verify there is a single path between the blocks and none of the blocks in the path is already in VISITED_BBS. If so, then update @@ -505,7 +892,7 @@ check_subpath_and_update_thread_path (basic_block last_bb, basic_block new_bb, /* If this is a profitable jump thread path, register it. - NAME is an SSA NAME with a possible constant value of ARG on PATH. + NAME is an SSA NAME with a possible RANGE on PATH. DEF_BB is the basic block that ultimately defines the constant. @@ -516,16 +903,18 @@ check_subpath_and_update_thread_path (basic_block last_bb, basic_block new_bb, static void register_jump_thread_path_if_profitable (vec<basic_block> &path, tree name, - tree arg, + const irange &range, basic_block def_bb, - bool speed_p) + bool speed_p, + bb_paths &paths) { - if (TREE_CODE_CLASS (TREE_CODE (arg)) != tcc_constant) + if (range.empty_p ()) return; bool irreducible = false; - edge taken_edge = profitable_jump_thread_path (path, def_bb, name, arg, - speed_p, &irreducible); + edge taken_edge = profitable_jump_thread_path (path, def_bb, name, range, + speed_p, &irreducible, + paths); if (taken_edge) { convert_and_register_jump_thread_path (path, taken_edge); @@ -539,7 +928,7 @@ register_jump_thread_path_if_profitable (vec<basic_block> &path, static void fsm_find_control_statement_thread_paths (tree, hash_set<basic_block> &, vec<basic_block> &, - bool, bool); + bool, bool, bb_paths &); /* Given PHI which defines NAME in block DEF_BB, recurse through the PHI's arguments searching for paths where NAME will ultimately have @@ -558,7 +947,7 @@ static void handle_phi (gphi *phi, tree name, basic_block def_bb, hash_set<basic_block> &visited_bbs, vec<basic_block> &path, - bool seen_loop_phi, bool speed_p) + bool seen_loop_phi, bool speed_p, bb_paths &paths) { /* Iterate over the arguments of PHI. */ for (unsigned int i = 0; i < gimple_phi_num_args (phi); i++) @@ -576,13 +965,19 @@ handle_phi (gphi *phi, tree name, basic_block def_bb, /* Recursively follow SSA_NAMEs looking for a constant definition. */ fsm_find_control_statement_thread_paths (arg, visited_bbs, path, - seen_loop_phi, speed_p); + seen_loop_phi, speed_p, + paths); path.pop (); continue; } - register_jump_thread_path_if_profitable (path, name, arg, bbi, speed_p); + if (TREE_CODE_CLASS (TREE_CODE (arg)) == tcc_constant) + { + irange range (TREE_TYPE (name), arg, arg); + register_jump_thread_path_if_profitable (path, name, range, + bbi, speed_p, paths); + } } } @@ -633,13 +1028,14 @@ static void handle_assignment (gimple *stmt, tree name, basic_block def_bb, hash_set<basic_block> &visited_bbs, vec<basic_block> &path, - bool seen_loop_phi, bool speed_p) + bool seen_loop_phi, bool speed_p, bb_paths &paths) { tree arg = gimple_assign_rhs1 (stmt); if (TREE_CODE (arg) == SSA_NAME) fsm_find_control_statement_thread_paths (arg, visited_bbs, - path, seen_loop_phi, speed_p); + path, seen_loop_phi, speed_p, + paths); else { @@ -648,8 +1044,12 @@ handle_assignment (gimple *stmt, tree name, basic_block def_bb, block at this point. So we can just pop it. */ path.pop (); - register_jump_thread_path_if_profitable (path, name, arg, def_bb, - speed_p); + if (TREE_CODE_CLASS (TREE_CODE (arg)) == tcc_constant) + { + irange range (TREE_TYPE (name), arg, arg); + register_jump_thread_path_if_profitable (path, name, range, def_bb, + speed_p, paths); + } /* And put the current block back onto the path so that the state of the stack is unchanged when we leave. */ @@ -668,7 +1068,8 @@ static void fsm_find_control_statement_thread_paths (tree name, hash_set<basic_block> &visited_bbs, vec<basic_block> &path, - bool seen_loop_phi, bool speed_p) + bool seen_loop_phi, bool speed_p, + bb_paths &paths) { /* If NAME appears in an abnormal PHI, then don't try to trace its value back through PHI nodes. */ @@ -731,16 +1132,57 @@ fsm_find_control_statement_thread_paths (tree name, if (gimple_code (def_stmt) == GIMPLE_PHI) handle_phi (as_a <gphi *> (def_stmt), name, def_bb, - visited_bbs, path, seen_loop_phi, speed_p); + visited_bbs, path, seen_loop_phi, speed_p, paths); else if (gimple_code (def_stmt) == GIMPLE_ASSIGN) handle_assignment (def_stmt, name, def_bb, - visited_bbs, path, seen_loop_phi, speed_p); + visited_bbs, path, seen_loop_phi, speed_p, paths); /* Remove all the nodes that we added from NEXT_PATH. */ if (next_path_length) path.truncate (path.length () - next_path_length); } +/* Record jump threads based on range information. + + It is assumed that BB ends with a control statement and that by + finding a path where NAME is a constant, we can thread the path. + SPEED_P indicate that we could increase code size to improve the + code path. */ + +static void +find_range_based_jump_threads (tree name, basic_block bb, bool speed_p, + bb_paths &paths) +{ + if (!INTEGRAL_TYPE_P (TREE_TYPE (name))) + return; + + paths.calculate (name, bb); + + for (unsigned i = 0; i < paths.length (); ++i) + { + irange r; + if (paths.range_of_path (r, i)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, + "Considering range-based path for jump threading: " + "SSA = "); + print_generic_stmt (dump_file, name, 0); + fprintf (dump_file, "\tRange is: "); + r.dump (dump_file); + } + /* register_jump_thread_path_if_profitable will push + the current block onto the path. But the path + will always have the current block at this point. + So we can just pop it. */ + basic_block def_bb = paths[i].pop (); + register_jump_thread_path_if_profitable + (paths[i], name, r, def_bb, speed_p, paths); + } + } +} + /* Search backwards from BB looking for paths where NAME (an SSA_NAME) is a constant. Record such paths for jump threading. @@ -749,8 +1191,8 @@ fsm_find_control_statement_thread_paths (tree name, SPEED_P indicate that we could increase code size to improve the code path. */ -void -find_jump_threads_backwards (basic_block bb, bool speed_p) +static void +find_jump_threads_backwards (basic_block bb, bool speed_p, bb_paths &paths) { gimple *stmt = get_gimple_control_stmt (bb); if (!stmt) @@ -774,13 +1216,18 @@ find_jump_threads_backwards (basic_block bb, bool speed_p) if (!name || TREE_CODE (name) != SSA_NAME) return; - auto_vec<basic_block> bb_path; - bb_path.safe_push (bb); + auto_vec<basic_block> path; + path.safe_push (bb); hash_set<basic_block> visited_bbs; max_threaded_paths = PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATHS); - fsm_find_control_statement_thread_paths (name, visited_bbs, bb_path, false, - speed_p); + fsm_find_control_statement_thread_paths (name, visited_bbs, path, false, + speed_p, paths); + + /* If we didn't thread any paths above, try threading by making use + of available range information. */ + if (max_threaded_paths == PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATHS)) + find_range_based_jump_threads (name, bb, speed_p, paths); } namespace { @@ -824,10 +1271,11 @@ pass_thread_jumps::execute (function *fun) /* Try to thread each block with more than one successor. */ basic_block bb; + bb_paths paths; FOR_EACH_BB_FN (bb, fun) { if (EDGE_COUNT (bb->succs) > 1) - find_jump_threads_backwards (bb, true); + find_jump_threads_backwards (bb, true, paths); } bool changed = thread_through_all_blocks (true); @@ -884,10 +1332,11 @@ pass_early_thread_jumps::execute (function *fun) /* Try to thread each block with more than one successor. */ basic_block bb; + bb_paths paths; FOR_EACH_BB_FN (bb, fun) { if (EDGE_COUNT (bb->succs) > 1) - find_jump_threads_backwards (bb, false); + find_jump_threads_backwards (bb, false, paths); } thread_through_all_blocks (true); diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c index 28c81a6ec57..6345ea82eed 100644 --- a/gcc/tree-ssa-threadupdate.c +++ b/gcc/tree-ssa-threadupdate.c @@ -1983,7 +1983,8 @@ mark_threaded_blocks (bitmap threaded_blocks) { vec<jump_thread_edge *> *path = paths[i]; - if ((*path)[1]->type != EDGE_COPY_SRC_JOINER_BLOCK) + if (path->length () > 1 + && (*path)[1]->type != EDGE_COPY_SRC_JOINER_BLOCK) { edge e = (*path)[0]->e; e->aux = (void *)path; @@ -2003,7 +2004,8 @@ mark_threaded_blocks (bitmap threaded_blocks) { vec<jump_thread_edge *> *path = paths[i]; - if ((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK) + if (path->length () > 1 + && (*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK) { /* Attach the path to the starting edge if none is yet recorded. */ if ((*path)[0]->e->aux == NULL) @@ -2032,7 +2034,8 @@ mark_threaded_blocks (bitmap threaded_blocks) vec<jump_thread_edge *> *path = paths[i]; edge e = (*path)[0]->e; - if ((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK && e->aux == path) + if (path->length () > 1 + && (*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK && e->aux == path) { unsigned int j; for (j = 1; j < path->length (); j++) @@ -2198,6 +2201,169 @@ bb_in_bbs (basic_block bb, basic_block *bbs, int n) return false; } +DEBUG_FUNCTION void +debug_path (FILE *dump_file, int pathno) +{ + vec<jump_thread_edge *> *p = paths[pathno]; + fprintf (dump_file, "path: "); + for (unsigned i = 0; i < p->length (); ++i) + fprintf (dump_file, "%d -> %d, ", + (*p)[i]->e->src->index, (*p)[i]->e->dest->index); + fprintf (dump_file, "\n"); +} + +DEBUG_FUNCTION void +debug_all_paths () +{ + for (unsigned i = 0; i < paths.length (); ++i) + debug_path (stderr, i); +} + +/* Rewire a jump_thread_edge so that the source block is now a + threaded source block. + + PATH_NUM is an index into the global path table PATHS. + EDGE_NUM is the jump thread edge number into said path. + + Returns TRUE if we were able to successfully rewire the edge. */ + +static bool +rewire_first_differing_edge (unsigned path_num, unsigned edge_num) +{ + vec<jump_thread_edge *> *path = paths[path_num]; + edge &e = (*path)[edge_num]->e; + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "rewiring edge candidate: %d -> %d\n", + e->src->index, e->dest->index); + basic_block src_copy = get_bb_copy (e->src); + if (src_copy == NULL) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "ignoring candidate: there is no src COPY\n"); + return false; + } + edge new_edge = find_edge (src_copy, e->dest); + /* If the previously threaded paths created a flow graph where we + can no longer figure out where to go, give up. */ + if (new_edge == NULL) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "ignoring candidate: we lost our way\n"); + return false; + } + e = new_edge; + return true; +} + +/* After an FSM path has been jump threaded, adjust the remaining FSM + paths that are subsets of this path, so these paths can be safely + threaded within the context of the new threaded path. + + For example, suppose we have just threaded: + + 5 -> 6 -> 7 -> 8 -> 12 => 5 -> 6' -> 7' -> 8' -> 12' + + And we have an upcoming threading candidate: + 5 -> 6 -> 7 -> 8 -> 15 -> 20 + + This function adjusts the upcoming path into: + 8' -> 15 -> 20 + + CURR_PATH_NUM is an index into the global paths table. It + specifies the path that was just threaded. */ + +static void +adjust_paths_after_duplication (unsigned curr_path_num) +{ + vec<jump_thread_edge *> *curr_path = paths[curr_path_num]; + gcc_assert ((*curr_path)[0]->type == EDGE_FSM_THREAD); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "just threaded: "); + debug_path (dump_file, curr_path_num); + } + + /* Iterate through all the other paths and adjust them. */ + for (unsigned cand_path_num = 0; cand_path_num < paths.length (); ) + { + if (cand_path_num == curr_path_num) + { + ++cand_path_num; + continue; + } + /* Make sure the candidate to adjust starts with the same path + as the recently threaded path and is an FSM thread. */ + vec<jump_thread_edge *> *cand_path = paths[cand_path_num]; + if ((*cand_path)[0]->type != EDGE_FSM_THREAD + || (*cand_path)[0]->e != (*curr_path)[0]->e) + { + ++cand_path_num; + continue; + } + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "adjusting candidate: "); + debug_path (dump_file, cand_path_num); + } + + /* Chop off from the candidate path any prefix it shares with + the recently threaded path. */ + unsigned minlength = MIN (curr_path->length (), cand_path->length ()); + unsigned j; + for (j = 0; j < minlength; ++j) + { + edge cand_edge = (*cand_path)[j]->e; + edge curr_edge = (*curr_path)[j]->e; + + /* Once the prefix no longer matches, adjust the first + non-matching edge to point from an adjusted edge to + wherever it was going. */ + if (cand_edge != curr_edge) + { + gcc_assert (cand_edge->src == curr_edge->src); + if (!rewire_first_differing_edge (cand_path_num, j)) + goto remove_candidate_from_list; + break; + } + } + if (j == minlength) + { + /* If we consumed the max subgraph we could look at, and + still didn't find any different edges, it's the + last edge after MINLENGTH. */ + if (cand_path->length () > minlength) + { + if (!rewire_first_differing_edge (cand_path_num, j)) + goto remove_candidate_from_list; + } + else if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "adjusting first edge after MINLENGTH.\n"); + } + if (j > 0) + { + /* If we are removing everything, delete the entire candidate. */ + if (j == cand_path->length ()) + { + remove_candidate_from_list: + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "adjusted candidate: [EMPTY]\n"); + delete_jump_thread_path (cand_path); + paths.unordered_remove (cand_path_num); + continue; + } + /* Otherwise, just remove the redundant sub-path. */ + cand_path->block_remove (0, j); + } + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "adjusted candidate: "); + debug_path (dump_file, cand_path_num); + } + ++cand_path_num; + } +} + /* Duplicates a jump-thread path of N_REGION basic blocks. The ENTRY edge is redirected to the duplicate of the region. @@ -2205,11 +2371,14 @@ bb_in_bbs (basic_block bb, basic_block *bbs, int n) and create a single fallthru edge pointing to the same destination as the EXIT edge. + CURRENT_PATH_NO is an index into the global paths[] table + specifying the jump-thread path. + Returns false if it is unable to copy the region, true otherwise. */ static bool duplicate_thread_path (edge entry, edge exit, basic_block *region, - unsigned n_region) + unsigned n_region, unsigned current_path_no) { unsigned i; struct loop *loop = entry->dest->loop_father; @@ -2221,6 +2390,12 @@ duplicate_thread_path (edge entry, edge exit, basic_block *region, if (!can_copy_bbs_p (region, n_region)) return false; + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "\nabout to thread: "); + debug_path (dump_file, current_path_no); + } + /* Some sanity checking. Note that we do not check for all possible missuses of the functions. I.e. if you ask to copy something weird, it will work, but the state of structures probably will not be @@ -2368,6 +2543,8 @@ duplicate_thread_path (edge entry, edge exit, basic_block *region, free (region_copy); + adjust_paths_after_duplication (current_path_no); + free_original_copy_tables (); return true; } @@ -2427,6 +2604,7 @@ thread_through_all_blocks (bool may_peel_loop_headers) bitmap_iterator bi; struct loop *loop; auto_bitmap threaded_blocks; + hash_set<edge> visited_starting_edges; if (!paths.exists ()) { @@ -2472,10 +2650,17 @@ thread_through_all_blocks (bool may_peel_loop_headers) continue; } - /* Do not jump-thread twice from the same block. */ - if (bitmap_bit_p (threaded_blocks, entry->src->index) - /* We may not want to realize this jump thread path - for various reasons. So check it first. */ + /* Do not jump-thread twice the same starting edge. + + Previously we only checked that we weren't threading twice + from the same BB, but that was too restrictive. Imagine a + path that starts from GIMPLE_COND(x_123 == 0,...), where both + edges out of this conditional yield paths that can be + threaded (for example, both lead to an x_123==0 or x_123!=0 + conditional further down the line. */ + if (visited_starting_edges.contains (entry) + /* We may not want to realize this jump thread path for + various reasons. So check it first. */ || !valid_jump_thread_path (path)) { /* Remove invalid FSM jump-thread paths. */ @@ -2491,11 +2676,11 @@ thread_through_all_blocks (bool may_peel_loop_headers) for (unsigned int j = 0; j < len - 1; j++) region[j] = (*path)[j]->e->dest; - if (duplicate_thread_path (entry, exit, region, len - 1)) + if (duplicate_thread_path (entry, exit, region, len - 1, i)) { /* We do not update dominance info. */ free_dominance_info (CDI_DOMINATORS); - bitmap_set_bit (threaded_blocks, entry->src->index); + visited_starting_edges.add (entry); retval = true; thread_stats.num_threaded_edges++; } @@ -2513,7 +2698,7 @@ thread_through_all_blocks (bool may_peel_loop_headers) edge entry = (*path)[0]->e; /* Do not jump-thread twice from the same block. */ - if (bitmap_bit_p (threaded_blocks, entry->src->index)) + if (visited_starting_edges.contains (entry)) { delete_jump_thread_path (path); paths.unordered_remove (i); @@ -2522,8 +2707,6 @@ thread_through_all_blocks (bool may_peel_loop_headers) i++; } - bitmap_clear (threaded_blocks); - mark_threaded_blocks (threaded_blocks); initialize_original_copy_tables (); |