From 520af9ec9a673351b046e06e91d8f66fa70341d2 Mon Sep 17 00:00:00 2001 From: Jeff Law Date: Mon, 28 Mar 2011 12:33:42 -0600 Subject: [PATCH] tree-ssa-threadupdate.c (redirect_edges): Call create_edge_and_update_destination_phis as needed. * tree-ssa-threadupdate.c (redirect_edges): Call create_edge_and_update_destination_phis as needed. (create_edge_and_update_destination_phis): Accept new BB argument. All callers updated. (thread_block): Do not update the profile when threading around intermediate blocks. (thread_single_edge): Likewise. (determine_bb_domination_status): If BB is not a successor of the loop header, return NONDOMINATING. (register_jump_thread): Note when we register a jump thread around an intermediate block. * tree-ssa-threadedge.c (thread_around_empty_block): New function. (thread_across_edge): Use it. * gcc.dg/tree-ssa/ssa-dom-thread-3.c: New test. From-SVN: r171622 --- gcc/ChangeLog | 16 +++ gcc/testsuite/ChangeLog | 4 + .../gcc.dg/tree-ssa/ssa-dom-thread-3.c | 47 ++++++++ gcc/tree-ssa-threadedge.c | 100 +++++++++++++++++- gcc/tree-ssa-threadupdate.c | 38 +++++-- 5 files changed, 193 insertions(+), 12 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-3.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 70b6506cf95..15500e48df8 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,19 @@ +2011-03-28 Jeff Law + + * tree-ssa-threadupdate.c (redirect_edges): Call + create_edge_and_update_destination_phis as needed. + (create_edge_and_update_destination_phis): Accept new BB argument. + All callers updated. + (thread_block): Do not update the profile when threading around + intermediate blocks. + (thread_single_edge): Likewise. + (determine_bb_domination_status): If BB is not a successor of the + loop header, return NONDOMINATING. + (register_jump_thread): Note when we register a jump thread around + an intermediate block. + * tree-ssa-threadedge.c (thread_around_empty_block): New function. + (thread_across_edge): Use it. + 2011-03-28 Tristan Gingold * config/ia64/ia64.c (ia64_promote_function_mode): Fix promotion diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index a6214b1adbf..dec92efca7c 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,7 @@ +2011-03-28 Jeff Law + + * gcc.dg/tree-ssa/ssa-dom-thread-3.c: New test. + 2011-03-28 Peter Bergner * gcc.dg/stack-usage-1.c (SIZE): Provide proper values for __PPC64__ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-3.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-3.c new file mode 100644 index 00000000000..d851bf23fe8 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-3.c @@ -0,0 +1,47 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-dom1-details" } */ +extern void abort (void) __attribute__ ((__noreturn__)); +union tree_node; +typedef union tree_node *tree; +enum tree_code +{ + VAR_DECL, + SSA_NAME, + MAX_TREE_CODES +}; +extern unsigned char tree_contains_struct[MAX_TREE_CODES][64]; +struct tree_base +{ + enum tree_code code:16; +}; +enum tree_node_structure_enum +{ + TS_DECL_COMMON +}; +struct tree_ssa_name +{ + tree var; +}; +union tree_node +{ + struct tree_base base; + struct tree_ssa_name ssa_name; +}; +long +expand_one_var (tree var, unsigned char toplevel, unsigned char really_expand) +{ + tree origvar = var; + var = var->ssa_name.var; + if (((enum tree_code) (origvar)->base.code) == SSA_NAME + && !((var->base.code != VAR_DECL))) + abort (); + if ((var->base.code) != VAR_DECL && ((origvar)->base.code) != SSA_NAME) + ; + else if (tree_contains_struct[(var->base.code)][(TS_DECL_COMMON)] != 1) + abort (); +} +/* We should thread the jump, through an intermediate block. */ +/* { dg-final { scan-tree-dump-times "Threaded" 1 "dom1"} } */ +/* { dg-final { scan-tree-dump-times "one or more intermediate" 1 "dom1"} } */ +/* { dg-final { cleanup-tree-dump "dom1" } } */ + diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c index 020f6e7fdb8..1fee9bf84c3 100644 --- a/gcc/tree-ssa-threadedge.c +++ b/gcc/tree-ssa-threadedge.c @@ -583,6 +583,76 @@ simplify_control_stmt_condition (edge e, return cached_lhs; } +/* TAKEN_EDGE represents the an edge taken as a result of jump threading. + See if we can thread around TAKEN_EDGE->dest as well. If so, return + the edge out of TAKEN_EDGE->dest that we can statically compute will be + traversed. + + We are much more restrictive as to the contents of TAKEN_EDGE->dest + as the path isolation code in tree-ssa-threadupdate.c isn't prepared + to handle copying intermediate blocks on a threaded path. + + Long term a more consistent and structured approach to path isolation + would be a huge help. */ +static edge +thread_around_empty_block (edge taken_edge, + gimple dummy_cond, + bool handle_dominating_asserts, + tree (*simplify) (gimple, gimple), + bitmap visited) +{ + basic_block bb = taken_edge->dest; + gimple_stmt_iterator gsi; + gimple stmt; + tree cond; + + /* This block must have a single predecessor (E->dest). */ + if (!single_pred_p (bb)) + return NULL; + + /* This block must have more than one successor. */ + if (single_succ_p (bb)) + return NULL; + + /* This block can have no PHI nodes. This is overly conservative. */ + if (!gsi_end_p (gsi_start_phis (bb))) + return NULL; + + /* Skip over DEBUG statements at the start of the block. */ + gsi = gsi_start_nondebug_bb (bb); + + if (gsi_end_p (gsi)) + return NULL; + + /* This block can have no statements other than its control altering + statement. This is overly conservative. */ + stmt = gsi_stmt (gsi); + if (gimple_code (stmt) != GIMPLE_COND + && gimple_code (stmt) != GIMPLE_GOTO + && gimple_code (stmt) != GIMPLE_SWITCH) + return NULL; + + /* Extract and simplify the condition. */ + cond = simplify_control_stmt_condition (taken_edge, stmt, dummy_cond, + simplify, handle_dominating_asserts); + + /* If the condition can be statically computed and we have not already + visited the destination edge, then add the taken edge to our thread + path. */ + if (cond && is_gimple_min_invariant (cond)) + { + edge taken_edge = find_taken_edge (bb, cond); + + if (bitmap_bit_p (visited, taken_edge->dest->index)) + return NULL; + bitmap_set_bit (visited, taken_edge->dest->index); + return taken_edge; + } + + return NULL; +} + + /* We are exiting E->src, see if E->dest ends with a conditional jump which has a known value when reached via E. @@ -661,16 +731,44 @@ thread_across_edge (gimple dummy_cond, tree cond; /* Extract and simplify the condition. */ - cond = simplify_control_stmt_condition (e, stmt, dummy_cond, simplify, handle_dominating_asserts); + cond = simplify_control_stmt_condition (e, stmt, dummy_cond, simplify, + handle_dominating_asserts); if (cond && is_gimple_min_invariant (cond)) { edge taken_edge = find_taken_edge (e->dest, cond); basic_block dest = (taken_edge ? taken_edge->dest : NULL); + bitmap visited; + edge e2; if (dest == e->dest) goto fail; + /* DEST could be null for a computed jump to an absolute + address. If DEST is not null, then see if we can thread + through it as well, this helps capture secondary effects + of threading without having to re-run DOM or VRP. */ + if (dest) + { + /* We don't want to thread back to a block we have already + visited. This may be overly conservative. */ + visited = BITMAP_ALLOC (NULL); + bitmap_set_bit (visited, dest->index); + bitmap_set_bit (visited, e->dest->index); + do + { + e2 = thread_around_empty_block (taken_edge, + dummy_cond, + handle_dominating_asserts, + simplify, + visited); + if (e2) + taken_edge = e2; + } + while (e2); + BITMAP_FREE (visited); + } + remove_temporary_equivalences (stack); register_jump_thread (e, taken_edge); } diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c index 951f47e0be0..efbc5ec28e5 100644 --- a/gcc/tree-ssa-threadupdate.c +++ b/gcc/tree-ssa-threadupdate.c @@ -304,14 +304,15 @@ lookup_redirection_data (edge e, edge incoming_edge, enum insert_option insert) destination. */ static void -create_edge_and_update_destination_phis (struct redirection_data *rd) +create_edge_and_update_destination_phis (struct redirection_data *rd, + basic_block bb) { - edge e = make_edge (rd->dup_block, rd->outgoing_edge->dest, EDGE_FALLTHRU); + edge e = make_edge (bb, rd->outgoing_edge->dest, EDGE_FALLTHRU); gimple_stmt_iterator gsi; rescan_loop_exit (e, true, false); e->probability = REG_BR_PROB_BASE; - e->count = rd->dup_block->count; + e->count = bb->count; e->aux = rd->outgoing_edge->aux; /* If there are any PHI nodes at the destination of the outgoing edge @@ -359,7 +360,7 @@ create_duplicates (void **slot, void *data) /* Go ahead and wire up outgoing edges and update PHIs for the duplicate block. */ - create_edge_and_update_destination_phis (rd); + create_edge_and_update_destination_phis (rd, rd->dup_block); } /* Keep walking the hash table. */ @@ -380,7 +381,7 @@ fixup_template_block (void **slot, void *data) and halt the hash table traversal. */ if (rd->dup_block && rd->dup_block == local_info->template_block) { - create_edge_and_update_destination_phis (rd); + create_edge_and_update_destination_phis (rd, rd->dup_block); return 0; } @@ -443,6 +444,11 @@ redirect_edges (void **slot, void *data) remove_ctrl_stmt_and_useless_edges (local_info->bb, rd->outgoing_edge->dest); + /* If we are threading beyond the immediate successors of + the duplicate, then BB will have no edges, create one. */ + if (EDGE_COUNT (local_info->bb->succs) == 0) + create_edge_and_update_destination_phis (rd, local_info->bb); + /* Fixup the flags on the single remaining edge. */ single_succ_edge (local_info->bb)->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE | EDGE_ABNORMAL); @@ -565,8 +571,9 @@ thread_block (basic_block bb, bool noloop_only) continue; } - update_bb_profile_for_threading (e->dest, EDGE_FREQUENCY (e), - e->count, (edge) e->aux); + if (e->dest == e2->src) + update_bb_profile_for_threading (e->dest, EDGE_FREQUENCY (e), + e->count, (edge) e->aux); /* Insert the outgoing edge into the hash table if it is not already in the hash table. */ @@ -650,12 +657,13 @@ thread_single_edge (edge e) } /* Otherwise, we need to create a copy. */ - update_bb_profile_for_threading (bb, EDGE_FREQUENCY (e), e->count, eto); + if (e->dest == eto->src) + update_bb_profile_for_threading (bb, EDGE_FREQUENCY (e), e->count, eto); rd.outgoing_edge = eto; create_block_for_threading (bb, &rd); - create_edge_and_update_destination_phis (&rd); + create_edge_and_update_destination_phis (&rd, rd.dup_block); if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, " Threaded jump %d --> %d to %d\n", @@ -704,7 +712,9 @@ determine_bb_domination_status (struct loop *loop, basic_block bb) edge e; #ifdef ENABLE_CHECKING - /* This function assumes BB is a successor of LOOP->header. */ + /* This function assumes BB is a successor of LOOP->header. + If that is not the case return DOMST_NONDOMINATING which + is always safe. */ { bool ok = false; @@ -717,7 +727,8 @@ determine_bb_domination_status (struct loop *loop, basic_block bb) } } - gcc_assert (ok); + if (!ok) + return DOMST_NONDOMINATING; } #endif @@ -1099,6 +1110,11 @@ register_jump_thread (edge e, edge e2) if (threaded_edges == NULL) threaded_edges = VEC_alloc (edge, heap, 10); + if (dump_file && (dump_flags & TDF_DETAILS) + && e->dest != e2->src) + fprintf (dump_file, + " Registering jump thread around one or more intermediate blocks\n"); + VEC_safe_push (edge, heap, threaded_edges, e); VEC_safe_push (edge, heap, threaded_edges, e2); } -- 2.30.2