From 00852255e4a0d3b67ed853aacbc4aa4f4dfe724a Mon Sep 17 00:00:00 2001 From: Jeff Law Date: Tue, 6 Oct 2015 20:25:57 -0600 Subject: [PATCH] [PATCH][PR tree-optimization/67816] Fix jump threading when DOM removes conditionals in jump threading path PR tree-optimization/67816 * tree-ssa-threadupdate.h (remove_jump_threads_including): Renamed from remove_jump_threads_starting_at. Accept an edge rather than a basic block. * tree-ssa-threadupdate.c (removed_edges): New hash table. (remove_jump_threads_including): Note edges that get removed from the CFG for later pruning of jump threading paths including them. (thread_through_all_blocks): Remove paths which include edges that have been removed. * tree-ssa-dom.c (optimize_stmt): Call remove_jump_threads_including on each outgoing edges when optimizing away a control statement. * gcc.c-torture/compile/pr67816.c: New test. From-SVN: r228559 --- gcc/ChangeLog | 14 +++++ gcc/testsuite/ChangeLog | 4 ++ gcc/testsuite/gcc.c-torture/compile/pr67816.c | 19 +++++++ gcc/tree-ssa-dom.c | 9 +++- gcc/tree-ssa-threadupdate.c | 75 +++++++++++++++++++-------- gcc/tree-ssa-threadupdate.h | 2 +- 6 files changed, 97 insertions(+), 26 deletions(-) create mode 100644 gcc/testsuite/gcc.c-torture/compile/pr67816.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 732b3d1..db6f1b6 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,17 @@ +2015-10-06 Jeff Law + + PR tree-optimization/67816 + * tree-ssa-threadupdate.h (remove_jump_threads_including): Renamed + from remove_jump_threads_starting_at. Accept an edge rather than + a basic block. + * tree-ssa-threadupdate.c (removed_edges): New hash table. + (remove_jump_threads_including): Note edges that get removed from + the CFG for later pruning of jump threading paths including them. + (thread_through_all_blocks): Remove paths which include edges that + have been removed. + * tree-ssa-dom.c (optimize_stmt): Call remove_jump_threads_including + on each outgoing edges when optimizing away a control statement. + 2015-10-06 Trevor Saunders * reorg.c (emit_delay_sequence): Store list of delay slot insns diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 4ec4743..1882fbd 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,7 @@ +2015-10-06 Jeff Law + + * gcc.c-torture/compile/pr67816.c: New test. + 2015-10-07 Kugan Vivekanandarajah * gcc.target/aarch64/get_lane_f16_1.c: New test. diff --git a/gcc/testsuite/gcc.c-torture/compile/pr67816.c b/gcc/testsuite/gcc.c-torture/compile/pr67816.c new file mode 100644 index 0000000..c3db3a3 --- /dev/null +++ b/gcc/testsuite/gcc.c-torture/compile/pr67816.c @@ -0,0 +1,19 @@ +int a, c, d, e; +int b[10]; +void fn1() { + int i, f = 0; + for (;;) { + i = 0; + for (; i < a; i++) + if (c) { + if (b[i]) + f = 1; + } else if (b[i]) + f = 0; + if (f) + d++; + while (e) + ; + } +} + diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c index c226da5..941087d 100644 --- a/gcc/tree-ssa-dom.c +++ b/gcc/tree-ssa-dom.c @@ -1840,8 +1840,13 @@ optimize_stmt (basic_block bb, gimple_stmt_iterator si, edge taken_edge = find_taken_edge (bb, val); if (taken_edge) { - /* Delete threads that start at BB. */ - remove_jump_threads_starting_at (bb); + + /* We need to remove any queued jump threads that + reference outgoing edges from this block. */ + edge_iterator ei; + edge e; + FOR_EACH_EDGE (e, ei, bb->succs) + remove_jump_threads_including (e); /* If BB is in a loop, then removing an outgoing edge from BB may cause BB to move outside the loop, changes in the diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c index 4a147bb..26b199b 100644 --- a/gcc/tree-ssa-threadupdate.c +++ b/gcc/tree-ssa-threadupdate.c @@ -215,6 +215,18 @@ redirection_data::equal (const redirection_data *p1, const redirection_data *p2) return true; } +/* Rather than search all the edges in jump thread paths each time + DOM is able to simply if control statement, we build a hash table + with the deleted edges. We only care about the address of the edge, + not its contents. */ +struct removed_edges : nofree_ptr_hash +{ + static hashval_t hash (edge e) { return htab_hash_pointer (e); } + static bool equal (edge e1, edge e2) { return e1 == e2; } +}; + +static hash_table *removed_edges; + /* Data structure of information to pass to hash table traversal routines. */ struct ssa_local_info_t { @@ -2539,35 +2551,23 @@ valid_jump_thread_path (vec *path) return true; } -/* Remove any queued jump threads that start at BB. */ +/* Remove any queued jump threads that include edge E. + + We don't actually remove them here, just record the edges into ax + hash table. That way we can do the search once per iteration of + DOM/VRP rather than for every case where DOM optimizes away a COND_EXPR. */ void -remove_jump_threads_starting_at (basic_block bb) +remove_jump_threads_including (edge_def *e) { if (!paths.exists ()) return; - for (unsigned i = 0; i < paths.length ();) - { - vec *path = paths[i]; + if (!removed_edges) + removed_edges = new hash_table (17); - /* Sadly, FSM jump threads have a slightly different - representation than the rest of the jump threads. */ - if ((*path)[0]->type == EDGE_FSM_THREAD - && (*path)[0]->e->src == bb) - { - delete_jump_thread_path (path); - paths.unordered_remove (i); - } - else if ((*path)[0]->type != EDGE_FSM_THREAD - && (*path)[0]->e->dest == bb) - { - delete_jump_thread_path (path); - paths.unordered_remove (i); - } - else - i++; - } + edge *slot = removed_edges->find_slot (e, INSERT); + *slot = e; } /* Walk through all blocks and thread incoming edges to the appropriate @@ -2591,11 +2591,37 @@ thread_through_all_blocks (bool may_peel_loop_headers) struct loop *loop; if (!paths.exists ()) - return false; + { + retval = false; + goto out; + } threaded_blocks = BITMAP_ALLOC (NULL); memset (&thread_stats, 0, sizeof (thread_stats)); + /* Remove any paths that referenced removed edges. */ + if (removed_edges) + for (i = 0; i < paths.length (); ) + { + unsigned int j; + vec *path = paths[i]; + + for (j = 0; j < path->length (); j++) + { + edge e = (*path)[j]->e; + if (removed_edges->find_slot (e, NO_INSERT)) + break; + } + + if (j != path->length ()) + { + delete_jump_thread_path (path); + paths.unordered_remove (i); + continue; + } + i++; + } + /* Jump-thread all FSM threads before other jump-threads. */ for (i = 0; i < paths.length ();) { @@ -2778,6 +2804,9 @@ thread_through_all_blocks (bool may_peel_loop_headers) if (retval) loops_state_set (LOOPS_NEED_FIXUP); + out: + delete removed_edges; + removed_edges = NULL; return retval; } diff --git a/gcc/tree-ssa-threadupdate.h b/gcc/tree-ssa-threadupdate.h index 30428e8..984b6c4 100644 --- a/gcc/tree-ssa-threadupdate.h +++ b/gcc/tree-ssa-threadupdate.h @@ -43,7 +43,7 @@ public: }; extern void register_jump_thread (vec *); -extern void remove_jump_threads_starting_at (basic_block); +extern void remove_jump_threads_including (edge); extern void delete_jump_thread_path (vec *); extern void remove_ctrl_stmt_and_useless_edges (basic_block, basic_block); #endif -- 2.7.4