From 78cf0a232ee4314a9d668aab9b4b54f86b308111 Mon Sep 17 00:00:00 2001 From: Sebastian Pop Date: Thu, 27 Aug 2015 17:11:21 -0500 Subject: port revision 219584 from linaro/gcc-4_9-branch gcc/ 2015-01-14 Yvan Roux Backport from trunk r218451. 2014-12-06 James Greenhalgh Sebastian Pop Brian Rzycki PR tree-optimization/54742 * params.def (max-fsm-thread-path-insns, max-fsm-thread-length, max-fsm-thread-paths): New. * doc/invoke.texi (max-fsm-thread-path-insns, max-fsm-thread-length, max-fsm-thread-paths): Documented. * tree-cfg.c (split_edge_bb_loc): Export. * tree-cfg.h (split_edge_bb_loc): Declared extern. * tree-ssa-threadedge.c (simplify_control_stmt_condition): Restore the original value of cond when simplification fails. (fsm_find_thread_path): New. (fsm_find_control_statement_thread_paths): New. (thread_through_normal_block): Call find_control_statement_thread_paths. * tree-ssa-threadupdate.c (dump_jump_thread_path): Pretty print EDGE_FSM_THREAD. (verify_seme): New. (duplicate_seme_region): New. (thread_through_all_blocks): Generate code for EDGE_FSM_THREAD edges calling duplicate_seme_region. * tree-ssa-threadupdate.h (jump_thread_edge_type): Add EDGE_FSM_THREAD. gcc/testsuite/ 2015-01-14 Yvan Roux Backport from trunk r218451. 2014-12-06 James Greenhalgh Sebastian Pop Brian Rzycki PR tree-optimization/54742 * gcc.dg/tree-ssa/ssa-dom-thread-6.c: New test. * gcc.dg/tree-ssa/ssa-dom-thread-7.c: New test. --- gcc-4.9/gcc/tree-ssa-threadupdate.c | 203 +++++++++++++++++++++++++++++++++++- 1 file changed, 202 insertions(+), 1 deletion(-) (limited to 'gcc-4.9/gcc/tree-ssa-threadupdate.c') diff --git a/gcc-4.9/gcc/tree-ssa-threadupdate.c b/gcc-4.9/gcc/tree-ssa-threadupdate.c index f458d6a99..d1b289ffa 100644 --- a/gcc-4.9/gcc/tree-ssa-threadupdate.c +++ b/gcc-4.9/gcc/tree-ssa-threadupdate.c @@ -156,8 +156,9 @@ dump_jump_thread_path (FILE *dump_file, vec path, bool registering) { fprintf (dump_file, - " %s jump thread: (%d, %d) incoming edge; ", + " %s%s jump thread: (%d, %d) incoming edge; ", (registering ? "Registering" : "Cancelling"), + (path[0]->type == EDGE_FSM_THREAD ? " FSM": ""), path[0]->e->src->index, path[0]->e->dest->index); for (unsigned int i = 1; i < path.length (); i++) @@ -1622,6 +1623,155 @@ bb_ends_with_multiway_branch (basic_block bb ATTRIBUTE_UNUSED) return false; } +/* Verify that the REGION is a Single Entry Multiple Exits region: make sure no + edge other than ENTRY is entering the REGION. */ + +DEBUG_FUNCTION void +verify_seme (edge entry, basic_block *region, unsigned n_region) +{ + bitmap bbs = BITMAP_ALLOC (NULL); + + for (unsigned i = 0; i < n_region; i++) + bitmap_set_bit (bbs, region[i]->index); + + for (unsigned i = 0; i < n_region; i++) + { + edge e; + edge_iterator ei; + basic_block bb = region[i]; + + /* All predecessors other than ENTRY->src should be in the region. */ + for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); ei_next (&ei)) + if (e != entry) + gcc_assert (bitmap_bit_p (bbs, e->src->index)); + } + + BITMAP_FREE (bbs); +} + +/* Duplicates a Single Entry Multiple Exit REGION (set of N_REGION basic + blocks). The ENTRY edge is redirected to the duplicate of the region. If + REGION is not a Single Entry region, ignore any incoming edges other than + ENTRY: this makes the copied region a Single Entry region. + + Remove the last conditional statement in the last basic block in the REGION, + and create a single fallthru edge pointing to the same destination as the + EXIT edge. + + The new basic blocks are stored to REGION_COPY in the same order as they had + in REGION, provided that REGION_COPY is not NULL. + + Returns false if it is unable to copy the region, true otherwise. */ + +static bool +duplicate_seme_region (edge entry, edge exit, + basic_block *region, unsigned n_region, + basic_block *region_copy) +{ + unsigned i; + bool free_region_copy = false, copying_header = false; + struct loop *loop = entry->dest->loop_father; + edge exit_copy; + edge redirected; + int total_freq = 0, entry_freq = 0; + gcov_type total_count = 0, entry_count = 0; + + if (!can_copy_bbs_p (region, n_region)) + return false; + + /* 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 + correct. */ + for (i = 0; i < n_region; i++) + { + /* We do not handle subloops, i.e. all the blocks must belong to the + same loop. */ + if (region[i]->loop_father != loop) + return false; + } + + initialize_original_copy_tables (); + + if (copying_header) + set_loop_copy (loop, loop_outer (loop)); + else + set_loop_copy (loop, loop); + + if (!region_copy) + { + region_copy = XNEWVEC (basic_block, n_region); + free_region_copy = true; + } + + if (entry->dest->count) + { + total_count = entry->dest->count; + entry_count = entry->count; + /* Fix up corner cases, to avoid division by zero or creation of negative + frequencies. */ + if (entry_count > total_count) + entry_count = total_count; + } + else + { + total_freq = entry->dest->frequency; + entry_freq = EDGE_FREQUENCY (entry); + /* Fix up corner cases, to avoid division by zero or creation of negative + frequencies. */ + if (total_freq == 0) + total_freq = 1; + else if (entry_freq > total_freq) + entry_freq = total_freq; + } + + copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop, + split_edge_bb_loc (entry), 0); + if (total_count) + { + scale_bbs_frequencies_gcov_type (region, n_region, + total_count - entry_count, + total_count); + scale_bbs_frequencies_gcov_type (region_copy, n_region, entry_count, + total_count); + } + else + { + scale_bbs_frequencies_int (region, n_region, total_freq - entry_freq, + total_freq); + scale_bbs_frequencies_int (region_copy, n_region, entry_freq, total_freq); + } + +#ifdef ENABLE_CHECKING + /* Make sure no edge other than ENTRY is entering the copied region. */ + verify_seme (entry, region_copy, n_region); +#endif + + /* Remove the last branch in the jump thread path. */ + remove_ctrl_stmt_and_useless_edges (region_copy[n_region - 1], exit->dest); + edge e = make_edge (region_copy[n_region - 1], exit->dest, EDGE_FALLTHRU); + + if (e) { + rescan_loop_exit (e, true, false); + e->probability = REG_BR_PROB_BASE; + e->count = region_copy[n_region - 1]->count; + } + + /* Redirect the entry and add the phi node arguments. */ + redirected = redirect_edge_and_branch (entry, get_bb_copy (entry->dest)); + gcc_assert (redirected != NULL); + flush_pending_stmts (entry); + + /* Add the other PHI node arguments. */ + add_phi_args_after_copy (region_copy, n_region, NULL); + + if (free_region_copy) + free (region_copy); + + free_original_copy_tables (); + return true; +} + /* Walk through all blocks and thread incoming edges to the appropriate outgoing edge for each edge pair recorded in THREADED_EDGES. @@ -1651,6 +1801,57 @@ thread_through_all_blocks (bool may_peel_loop_headers) threaded_blocks = BITMAP_ALLOC (NULL); memset (&thread_stats, 0, sizeof (thread_stats)); + /* Jump-thread all FSM threads before other jump-threads. */ + for (i = 0; i < paths.length ();) + { + vec *path = paths[i]; + edge entry = (*path)[0]->e; + + if ((*path)[0]->type != EDGE_FSM_THREAD + /* Do not jump-thread twice from the same block. */ + || bitmap_bit_p (threaded_blocks, entry->src->index)) { + i++; + continue; + } + + unsigned len = path->length (); + edge exit = (*path)[len - 1]->e; + basic_block *region = XNEWVEC (basic_block, len - 1); + + for (unsigned int j = 0; j < len - 1; j++) + region[j] = (*path)[j]->e->dest; + + if (duplicate_seme_region (entry, exit, region, len - 1, NULL)) + { + /* We do not update dominance info. */ + free_dominance_info (CDI_DOMINATORS); + bitmap_set_bit (threaded_blocks, entry->src->index); + retval = true; + } + + delete_jump_thread_path (path); + paths.unordered_remove (i); + } + + /* Remove from PATHS all the jump-threads starting with an edge already + jump-threaded. */ + for (i = 0; i < paths.length ();) + { + vec *path = paths[i]; + edge entry = (*path)[0]->e; + + /* Do not jump-thread twice from the same block. */ + if (bitmap_bit_p (threaded_blocks, entry->src->index)) + { + delete_jump_thread_path (path); + paths.unordered_remove (i); + } + else + i++; + } + + bitmap_clear (threaded_blocks); + mark_threaded_blocks (threaded_blocks); initialize_original_copy_tables (); -- cgit v1.2.3 From fa0139c9969e54f37f0add025af87cc21b46ffcb Mon Sep 17 00:00:00 2001 From: Sebastian Pop Date: Fri, 28 Aug 2015 15:36:58 -0500 Subject: backport patch to fix PR65048 PR tree-optimization/65048 * tree-ssa-threadupdate.c (valid_jump_thread_path): New. (thread_through_all_blocks): Call valid_jump_thread_path. Remove invalid FSM jump-thread paths. PR tree-optimization/65048 * gcc.dg/tree-ssa/ssa-dom-thread-9.c: New. --- gcc-4.9/gcc/tree-ssa-threadupdate.c | 40 +++++++++++++++++++++++++++++++------ 1 file changed, 34 insertions(+), 6 deletions(-) (limited to 'gcc-4.9/gcc/tree-ssa-threadupdate.c') diff --git a/gcc-4.9/gcc/tree-ssa-threadupdate.c b/gcc-4.9/gcc/tree-ssa-threadupdate.c index d1b289ffa..3c7df9add 100644 --- a/gcc-4.9/gcc/tree-ssa-threadupdate.c +++ b/gcc-4.9/gcc/tree-ssa-threadupdate.c @@ -1772,6 +1772,21 @@ duplicate_seme_region (edge entry, edge exit, return true; } +/* Return true when PATH is a valid jump-thread path. */ + +static bool +valid_jump_thread_path (vec *path) +{ + unsigned len = path->length (); + + /* Check that the path is connected. */ + for (unsigned int j = 0; j < len - 1; j++) + if ((*path)[j]->e->dest != (*path)[j+1]->e->src) + return false; + + return true; +} + /* Walk through all blocks and thread incoming edges to the appropriate outgoing edge for each edge pair recorded in THREADED_EDGES. @@ -1807,12 +1822,25 @@ thread_through_all_blocks (bool may_peel_loop_headers) vec *path = paths[i]; edge entry = (*path)[0]->e; - if ((*path)[0]->type != EDGE_FSM_THREAD - /* Do not jump-thread twice from the same block. */ - || bitmap_bit_p (threaded_blocks, entry->src->index)) { - i++; - continue; - } + /* Only code-generate FSM jump-threads in this loop. */ + if ((*path)[0]->type != EDGE_FSM_THREAD) + { + i++; + continue; + } + + /* Do not jump-thread twice from the same block. */ + if (bitmap_bit_p (threaded_blocks, entry->src->index) + /* Verify that the jump thread path is still valid: a + previous jump-thread may have changed the CFG, and + invalidated the current path. */ + || !valid_jump_thread_path (path)) + { + /* Remove invalid FSM jump-thread paths. */ + delete_jump_thread_path (path); + paths.unordered_remove (i); + continue; + } unsigned len = path->length (); edge exit = (*path)[len - 1]->e; -- cgit v1.2.3 From aa65e2d1e40e4dd0d936a275683c4aadfe8aa20f Mon Sep 17 00:00:00 2001 From: Sebastian Pop Date: Fri, 28 Aug 2015 15:43:11 -0500 Subject: backport patch to fix PR65177 PR tree-optimization/65177 * tree-ssa-threadupdate.c (verify_seme): Renamed verify_jump_thread. (bb_in_bbs): New. (duplicate_seme_region): Renamed duplicate_thread_path. Redirect all edges not adjacent on the path to the original code. * gcc.dg/tree-ssa/ssa-dom-thread-10.c: New. --- gcc-4.9/gcc/tree-ssa-threadupdate.c | 93 ++++++++++++++++++++++++++----------- 1 file changed, 67 insertions(+), 26 deletions(-) (limited to 'gcc-4.9/gcc/tree-ssa-threadupdate.c') diff --git a/gcc-4.9/gcc/tree-ssa-threadupdate.c b/gcc-4.9/gcc/tree-ssa-threadupdate.c index 3c7df9add..c2f02a6ab 100644 --- a/gcc-4.9/gcc/tree-ssa-threadupdate.c +++ b/gcc-4.9/gcc/tree-ssa-threadupdate.c @@ -1623,36 +1623,32 @@ bb_ends_with_multiway_branch (basic_block bb ATTRIBUTE_UNUSED) return false; } -/* Verify that the REGION is a Single Entry Multiple Exits region: make sure no - edge other than ENTRY is entering the REGION. */ +/* Verify that the REGION is a valid jump thread. A jump thread is a special + case of SEME Single Entry Multiple Exits region in which all nodes in the + REGION have exactly one incoming edge. The only exception is the first block + that may not have been connected to the rest of the cfg yet. */ DEBUG_FUNCTION void -verify_seme (edge entry, basic_block *region, unsigned n_region) +verify_jump_thread (basic_block *region, unsigned n_region) { - bitmap bbs = BITMAP_ALLOC (NULL); - for (unsigned i = 0; i < n_region; i++) - bitmap_set_bit (bbs, region[i]->index); + gcc_assert (EDGE_COUNT (region[i]->preds) <= 1); +} - for (unsigned i = 0; i < n_region; i++) - { - edge e; - edge_iterator ei; - basic_block bb = region[i]; +/* Return true when BB is one of the first N items in BBS. */ - /* All predecessors other than ENTRY->src should be in the region. */ - for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); ei_next (&ei)) - if (e != entry) - gcc_assert (bitmap_bit_p (bbs, e->src->index)); - } +static inline bool +bb_in_bbs (basic_block bb, basic_block *bbs, int n) +{ + for (int i = 0; i < n; i++) + if (bb == bbs[i]) + return true; - BITMAP_FREE (bbs); + return false; } -/* Duplicates a Single Entry Multiple Exit REGION (set of N_REGION basic - blocks). The ENTRY edge is redirected to the duplicate of the region. If - REGION is not a Single Entry region, ignore any incoming edges other than - ENTRY: this makes the copied region a Single Entry region. +/* Duplicates a jump-thread path of N_REGION basic blocks. + The ENTRY edge is redirected to the duplicate of the region. Remove the last conditional statement in the last basic block in the REGION, and create a single fallthru edge pointing to the same destination as the @@ -1664,7 +1660,7 @@ verify_seme (edge entry, basic_block *region, unsigned n_region) Returns false if it is unable to copy the region, true otherwise. */ static bool -duplicate_seme_region (edge entry, edge exit, +duplicate_thread_path (edge entry, edge exit, basic_block *region, unsigned n_region, basic_block *region_copy) { @@ -1726,7 +1722,53 @@ duplicate_seme_region (edge entry, edge exit, } copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop, - split_edge_bb_loc (entry), 0); + split_edge_bb_loc (entry), false); + + /* Fix up: copy_bbs redirects all edges pointing to copied blocks. The + following code ensures that all the edges exiting the jump-thread path are + redirected back to the original code: these edges are exceptions + invalidating the property that is propagated by executing all the blocks of + the jump-thread path in order. */ + + for (i = 0; i < n_region; i++) + { + edge e; + edge_iterator ei; + basic_block bb = region_copy[i]; + + if (single_succ_p (bb)) + { + /* Make sure the successor is the next node in the path. */ + gcc_assert (i + 1 == n_region + || region_copy[i + 1] == single_succ_edge (bb)->dest); + continue; + } + + /* Special case the last block on the path: make sure that it does not + jump back on the copied path. */ + if (i + 1 == n_region) + { + FOR_EACH_EDGE (e, ei, bb->succs) + if (bb_in_bbs (e->dest, region_copy, n_region - 1)) + { + basic_block orig = get_bb_original (e->dest); + if (orig) + redirect_edge_and_branch_force (e, orig); + } + continue; + } + + /* Redirect all other edges jumping to non-adjacent blocks back to the + original code. */ + FOR_EACH_EDGE (e, ei, bb->succs) + if (region_copy[i + 1] != e->dest) + { + basic_block orig = get_bb_original (e->dest); + if (orig) + redirect_edge_and_branch_force (e, orig); + } + } + if (total_count) { scale_bbs_frequencies_gcov_type (region, n_region, @@ -1743,8 +1785,7 @@ duplicate_seme_region (edge entry, edge exit, } #ifdef ENABLE_CHECKING - /* Make sure no edge other than ENTRY is entering the copied region. */ - verify_seme (entry, region_copy, n_region); + verify_jump_thread (region_copy, n_region); #endif /* Remove the last branch in the jump thread path. */ @@ -1849,7 +1890,7 @@ 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_seme_region (entry, exit, region, len - 1, NULL)) + if (duplicate_thread_path (entry, exit, region, len - 1, NULL)) { /* We do not update dominance info. */ free_dominance_info (CDI_DOMINATORS); -- cgit v1.2.3