From aa620173eb5c350ab316602f970010b450786b35 Mon Sep 17 00:00:00 2001 From: revitale Date: Sun, 6 Jan 2008 15:24:10 +0000 Subject: [PATCH] Fix PR34263: Cleaning up latch blocks git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@131352 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/ChangeLog | 11 +++ gcc/testsuite/ChangeLog | 5 ++ gcc/testsuite/gcc.dg/pr34263.c | 59 +++++++++++++++ gcc/tree-outof-ssa.c | 159 ++++++++++++++++++++++++++++++++++++++++- 4 files changed, 233 insertions(+), 1 deletion(-) create mode 100644 gcc/testsuite/gcc.dg/pr34263.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 85cdaca..87bc032 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,14 @@ +2008-01-06 Andrew Pinski + Mircea Namolaru + Vladimir Yanovsky + Revital Eres + + PR tree-optimization/34263 + * tree-outof-ssa.c (process_single_block_loop_latch, + contains_tree_r): New functions. + (analyze_edges_for_bb): Call process_single_block_loop_latch + function to empty single-basic-block latch block if possible. + 2008-01-05 Uros Bizjak * config/i386/i386.c (ix86_builtin_reciprocal): Remove check diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index b456bba..2b08e57 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,8 @@ +2008-01-06 Revital Eres + + PR tree-optimization/34263 + * gcc.dg/pr34263.c: New testcase. + 2008-01-06 Tobias Burnus PR fortran/34654 diff --git a/gcc/testsuite/gcc.dg/pr34263.c b/gcc/testsuite/gcc.dg/pr34263.c new file mode 100644 index 0000000..10df9d8 --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr34263.c @@ -0,0 +1,59 @@ +/* { dg-do run } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ +/* Same test as 990128-1.c. */ + +extern int printf (const char *,...); +extern void abort (void); + +struct s { struct s *n; } *p; +struct s ss; +#define MAX 10 +struct s sss[MAX]; +int count = 0; + +void sub( struct s *p, struct s **pp ); +int look( struct s *p, struct s **pp ); + +main() +{ + struct s *pp; + struct s *next; + int i; + + p = &ss; + next = p; + for ( i = 0; i < MAX; i++ ) { + next->n = &sss[i]; + next = next->n; + } + next->n = 0; + + sub( p, &pp ); + if (count != MAX+2) + abort (); + + return( 0 ); +} + +void sub( struct s *p, struct s **pp ) +{ + for ( ; look( p, pp ); ) { + if ( p ) + p = p->n; + else + break; + } +} + +int look( struct s *p, struct s **pp ) +{ + for ( ; p; p = p->n ) + ; + *pp = p; + count++; + return( 1 ); +} + +/* { dg-final { scan-tree-dump "Cleaned-up latch block of loop with single BB" "optimized" } } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ + diff --git a/gcc/tree-outof-ssa.c b/gcc/tree-outof-ssa.c index b2816a0..be8a459 100644 --- a/gcc/tree-outof-ssa.c +++ b/gcc/tree-outof-ssa.c @@ -872,6 +872,158 @@ fini_analyze_edges_for_bb (void) BITMAP_FREE (leader_has_match); } +/* A helper function to be called via walk_tree. Return DATA if it is + contained in subtree TP. */ + +static tree +contains_tree_r (tree * tp, int *walk_subtrees, void *data) +{ + if (*tp == data) + { + *walk_subtrees = 0; + return data; + } + else + return NULL_TREE; +} + +/* A threshold for the number of insns contained in the latch block. + It is used to prevent blowing the loop with too many copies from + the latch. */ +#define MAX_STMTS_IN_LATCH 2 + +/* Return TRUE if the stmts on SINGLE-EDGE can be moved to the + body of the loop. This should be permitted only if SINGLE-EDGE is a + single-basic-block latch edge and thus cleaning the latch will help + to create a single-basic-block loop. Otherwise return FALSE. */ + +static bool +process_single_block_loop_latch (edge single_edge) +{ + tree stmts; + basic_block b_exit, b_pheader, b_loop = single_edge->src; + edge_iterator ei; + edge e; + block_stmt_iterator bsi, bsi_exit; + tree_stmt_iterator tsi; + tree expr, stmt; + unsigned int count = 0; + + if (single_edge == NULL || (single_edge->dest != single_edge->src) + || (EDGE_COUNT (b_loop->succs) != 2) + || (EDGE_COUNT (b_loop->preds) != 2)) + return false; + + /* Get the stmts on the latch edge. */ + stmts = PENDING_STMT (single_edge); + + /* Find the successor edge which is not the latch edge. */ + FOR_EACH_EDGE (e, ei, b_loop->succs) + if (e->dest != b_loop) + break; + + b_exit = e->dest; + + /* Check that the exit block has only the loop as a predecessor, + and that there are no pending stmts on that edge as well. */ + if (EDGE_COUNT (b_exit->preds) != 1 || PENDING_STMT (e)) + return false; + + /* Find the predecessor edge which is not the latch edge. */ + FOR_EACH_EDGE (e, ei, b_loop->preds) + if (e->src != b_loop) + break; + + b_pheader = e->src; + + if (b_exit == b_pheader || b_exit == b_loop || b_pheader == b_loop) + return false; + + bsi_exit = bsi_after_labels (b_exit); + + /* Get the last stmt in the loop body. */ + bsi = bsi_last (single_edge->src); + stmt = bsi_stmt (bsi); + + if (TREE_CODE (stmt) != COND_EXPR) + return false; + + expr = COND_EXPR_COND (stmt); + /* Iterate over the insns on the latch and count them. */ + for (tsi = tsi_start (stmts); !tsi_end_p (tsi); tsi_next (&tsi)) + { + tree stmt1 = tsi_stmt (tsi); + tree var; + + count++; + /* Check that the condition does not contain any new definition + created in the latch as the stmts from the latch intended + to precede it. */ + if (TREE_CODE (stmt1) != GIMPLE_MODIFY_STMT) + return false; + var = GIMPLE_STMT_OPERAND (stmt1, 0); + if (TREE_THIS_VOLATILE (var) + || TYPE_VOLATILE (TREE_TYPE (var)) + || walk_tree (&expr, contains_tree_r, var, NULL)) + return false; + } + /* Check that the latch does not contain more than MAX_STMTS_IN_LATCH + insns. The purpose of this restriction is to prevent blowing the + loop with too many copies from the latch. */ + if (count > MAX_STMTS_IN_LATCH) + return false; + + /* Apply the transformation - clean up the latch block: + + var = something; + L1: + x1 = expr; + if (cond) goto L2 else goto L3; + L2: + var = x1; + goto L1 + L3: + ... + + ==> + + var = something; + L1: + x1 = expr; + tmp_var = var; + var = x1; + if (cond) goto L1 else goto L2; + L2: + var = tmp_var; + ... + */ + for (tsi = tsi_start (stmts); !tsi_end_p (tsi); tsi_next (&tsi)) + { + tree stmt1 = tsi_stmt (tsi); + tree var, tmp_var, copy; + + /* Create a new variable to load back the value of var in case + we exit the loop. */ + var = GIMPLE_STMT_OPERAND (stmt1, 0); + tmp_var = create_temp (var); + copy = build2 (GIMPLE_MODIFY_STMT, TREE_TYPE (tmp_var), tmp_var, var); + set_is_used (tmp_var); + bsi_insert_before (&bsi, copy, BSI_SAME_STMT); + copy = build2 (GIMPLE_MODIFY_STMT, TREE_TYPE (tmp_var), var, tmp_var); + bsi_insert_before (&bsi_exit, copy, BSI_SAME_STMT); + } + + PENDING_STMT (single_edge) = 0; + /* Insert the new stmts to the loop body. */ + bsi_insert_before (&bsi, stmts, BSI_NEW_STMT); + + if (dump_file) + fprintf (dump_file, + "\nCleaned-up latch block of loop with single BB: %d\n\n", + single_edge->dest->index); + + return true; +} /* Look at all the incoming edges to block BB, and decide where the best place to insert the stmts on each edge are, and perform those insertions. */ @@ -945,7 +1097,12 @@ analyze_edges_for_bb (basic_block bb) if (count < 2) { if (single_edge) - bsi_commit_one_edge_insert (single_edge, NULL); + { + /* Add stmts to the edge unless processed specially as a + single-block loop latch edge. */ + if (!process_single_block_loop_latch (single_edge)) + bsi_commit_one_edge_insert (single_edge, NULL); + } return; } -- 2.7.4