From patchwork Thu Jun 10 22:52:58 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sebastian Pop X-Patchwork-Id: 55276 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id D4B0CB7D90 for ; Fri, 11 Jun 2010 08:53:30 +1000 (EST) Received: (qmail 26688 invoked by alias); 10 Jun 2010 22:53:28 -0000 Received: (qmail 26677 invoked by uid 22791); 10 Jun 2010 22:53:26 -0000 X-SWARE-Spam-Status: No, hits=-1.7 required=5.0 tests=AWL, BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, RCVD_IN_DNSWL_NONE, TW_TM X-Spam-Check-By: sourceware.org Received: from mail-vw0-f47.google.com (HELO mail-vw0-f47.google.com) (209.85.212.47) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Thu, 10 Jun 2010 22:53:22 +0000 Received: by vws11 with SMTP id 11so445591vws.20 for ; Thu, 10 Jun 2010 15:53:20 -0700 (PDT) Received: by 10.224.80.11 with SMTP id r11mr95901qak.148.1276210399810; Thu, 10 Jun 2010 15:53:19 -0700 (PDT) MIME-Version: 1.0 Received: by 10.224.74.18 with HTTP; Thu, 10 Jun 2010 15:52:58 -0700 (PDT) From: Sebastian Pop Date: Thu, 10 Jun 2010 17:52:58 -0500 Message-ID: Subject: [patch] Fix PR44483: incrementally gimplify BB predicates to avoid redundant computations. To: GCC Patches , Richard Guenther X-IsSubscribed: yes Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Hi, The attached patch fixes PR44483 by early gimplifying the expressions that are used in the predicates of basic blocks: in the testcase, these expressions are redundant and if not gimplified in time, they end up to form an exponential tree of conditions. With this patch we gimplify the predicates, and collect the gimple sequences during the analysis phase. Because we now force the predicate of a BB to be an SSA_NAME, this is what is used further on for the next basic block, avoiding the full expression to be recomputed. When the if-conversion analysis fails, the SSA_NAMEs used in the gimple sequences are released using free_stmt_operands. Otherwise the gimple sequences are inserted in the end of each basic block that is predicated by these computations. These computations are then used in the if-conversion of the PHI nodes following the BB. The patch passed make -k check RUNTESTFLAGS=tree-ssa.exp and vect.exp and is right now under regstrap on amd64-linux. Ok for trunk after regstrap? Thanks, Sebastian Pop --- AMD / Open Source Compiler Engineering / GNU Tools From d9521b43a607e5b194935ff66a7677118bbe814f Mon Sep 17 00:00:00 2001 From: Sebastian Pop Date: Thu, 10 Jun 2010 17:22:40 -0500 Subject: [PATCH] Fix PR44483: incrementally gimplify BB predicates to avoid redundant computations. PR middle-end/44483 * tree-if-conv.c (bb_predicate_s): New struct. (bb_predicate_p): New. (bb_has_predicate): New. (bb_predicate): New. (set_bb_predicate): New. (bb_predicate_gimplified_stmts): New. (set_bb_predicate_gimplified_stmts): New. (add_bb_predicate_gimplified_stmts): New. (init_bb_predicate): New. (free_bb_predicate): New. (is_predicated): Use bb_predicate. (add_to_predicate_list): Use bb_predicate and set_bb_predicate. (predicate_bbs): Same. Gimplify the condition of the basic blocks before processing their successors. (clean_predicate_lists): Removed. (find_phi_replacement_condition): Use bb_predicate. (process_phi_nodes): Renamed ifconvert_phi_nodes. Avoid useless computations. (insert_gimplified_predicates): New. (combine_blocks): Call insert_gimplified_predicates. (tree_if_conversion): Call free_bb_predicate instead of clean_predicate_lists. * gcc.dg/tree-ssa/pr44483.c: New. --- gcc/testsuite/gcc.dg/tree-ssa/pr44483.c | 20 +++ gcc/tree-if-conv.c | 235 ++++++++++++++++++++++++------- 2 files changed, 207 insertions(+), 48 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr44483.c diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr44483.c b/gcc/testsuite/gcc.dg/tree-ssa/pr44483.c new file mode 100644 index 0000000..cdae91a --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr44483.c @@ -0,0 +1,20 @@ +/* { dg-do compile } */ +/* { dg-options "-c -O3" { target *-*-* } } */ + +int ffesum (void) { + int ch[4], ii, jj, kk; + char asc[32]; + + for (ii = 0; ii < 4; ii++) + { + for (jj = 0; jj < 4; jj++) + ch[jj] = ii; + for (kk = 0; kk < 13; kk++) + for (jj = 0; jj < 4; jj += 2) + if ((unsigned char) ch[jj] || (unsigned char) ch[jj + 1]) + ch[jj]++; + for (jj = 0; jj < 4; jj++) + asc[4 * jj + ii] = ch[jj]; + } + return asc[0]; +} diff --git a/gcc/tree-if-conv.c b/gcc/tree-if-conv.c index 25cb918..1686473 100644 --- a/gcc/tree-if-conv.c +++ b/gcc/tree-if-conv.c @@ -102,6 +102,106 @@ along with GCC; see the file COPYING3. If not see /* List of basic blocks in if-conversion-suitable order. */ static basic_block *ifc_bbs; +/* Structure used to predicate basic blocks. This is attached to the + ->aux field of the BBs in the loop to be if-converted. */ +typedef struct bb_predicate_s { + + /* The condition under which this basic block is executed. */ + tree predicate; + + /* PREDICATE is gimplified, and the sequence of statements is + recorded here, in order to avoid the duplication of computations + that occur in previous conditions. See PR44483. */ + gimple_seq predicate_gimplified_stmts; +} *bb_predicate_p; + +/* Returns true when the basic block BB has a predicate. */ + +static inline bool +bb_has_predicate (basic_block bb) +{ + return bb->aux != NULL; +} + +/* Returns the gimplified predicate for basic block BB. */ + +static inline tree +bb_predicate (basic_block bb) +{ + return ((bb_predicate_p) bb->aux)->predicate; +} + +/* Sets the gimplified predicate COND for basic block BB. */ + +static inline void +set_bb_predicate (basic_block bb, tree cond) +{ + ((bb_predicate_p) bb->aux)->predicate = cond; +} + +/* Returns the sequence of statements of the gimplification of the + predicate for basic block BB. */ + +static inline gimple_seq +bb_predicate_gimplified_stmts (basic_block bb) +{ + return ((bb_predicate_p) bb->aux)->predicate_gimplified_stmts; +} + +/* Sets the sequence of statements STMTS of the gimplification of the + predicate for basic block BB. */ + +static inline void +set_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts) +{ + ((bb_predicate_p) bb->aux)->predicate_gimplified_stmts = stmts; +} + +/* Adds the sequence of statements STMTS to the sequence of statements + of the predicate for basic block BB. */ + +static inline void +add_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts) +{ + gimple_seq_add_seq + (&(((bb_predicate_p) bb->aux)->predicate_gimplified_stmts), stmts); +} + +/* Initializes to TRUE the predicate of basic block BB. */ + +static inline void +init_bb_predicate (basic_block bb) +{ + bb->aux = XNEW (struct bb_predicate_s); + set_bb_predicate_gimplified_stmts (bb, NULL); + set_bb_predicate (bb, NULL_TREE); +} + +/* Free the predicate of basic block BB. */ + +static inline void +free_bb_predicate (basic_block bb) +{ + gimple_seq stmts; + + if (!bb_has_predicate (bb)) + return; + + /* Release the SSA_NAMEs created for the gimplification of the + predicate. */ + stmts = bb_predicate_gimplified_stmts (bb); + if (stmts) + { + gimple_stmt_iterator i; + + for (i = gsi_start (stmts); !gsi_end_p (i); gsi_next (&i)) + free_stmt_operands (gsi_stmt (i)); + } + + free (bb->aux); + bb->aux = NULL; +} + /* Create a new temp variable of type TYPE. Add GIMPLE_ASSIGN to assign EXP to the new variable. */ @@ -145,7 +245,7 @@ is_true_predicate (tree cond) static inline bool is_predicated (basic_block bb) { - return !is_true_predicate ((tree) bb->aux); + return !is_true_predicate (bb_predicate (bb)); } /* Add condition NEW_COND to the predicate list of basic block BB. */ @@ -153,12 +253,12 @@ is_predicated (basic_block bb) static inline void add_to_predicate_list (basic_block bb, tree new_cond) { - tree cond = (tree) bb->aux; + tree cond = bb_predicate (bb); - bb->aux = is_true_predicate (cond) ? new_cond : - fold_build2_loc (EXPR_LOCATION (cond), - TRUTH_OR_EXPR, boolean_type_node, - cond, new_cond); + set_bb_predicate (bb, is_true_predicate (cond) ? new_cond : + fold_build2_loc (EXPR_LOCATION (cond), + TRUTH_OR_EXPR, boolean_type_node, + cond, new_cond)); } /* Add the condition COND to the previous condition PREV_COND, and add @@ -471,7 +571,7 @@ get_loop_body_in_if_conv_order (const struct loop *loop) /* Returns true when the analysis of the predicates for all the basic blocks in LOOP succeeded. - predicate_bbs first clears the ->aux fields of the basic blocks. + predicate_bbs first allocates the predicates of the basic blocks. These fields are then initialized with the tree expressions representing the predicates under which a basic block is executed in the LOOP. As the loop->header is executed at each iteration, it @@ -492,14 +592,33 @@ predicate_bbs (loop_p loop) unsigned int i; for (i = 0; i < loop->num_nodes; i++) - ifc_bbs[i]->aux = NULL; + init_bb_predicate (ifc_bbs[i]); for (i = 0; i < loop->num_nodes; i++) { - basic_block bb = ifc_bbs [i]; - tree cond = (tree) bb->aux; + basic_block bb = ifc_bbs[i]; + tree cond; gimple_stmt_iterator itr; + /* The loop latch is always executed and has no extra conditions + to be processed: skip it. */ + if (bb == loop->latch) + { + set_bb_predicate (loop->latch, boolean_true_node); + set_bb_predicate_gimplified_stmts (loop->latch, NULL); + continue; + } + + cond = bb_predicate (bb); + if (cond + && bb != loop->header) + { + gimple_seq stmts; + + cond = force_gimple_operand (cond, &stmts, true, NULL_TREE); + add_bb_predicate_gimplified_stmts (bb, stmts); + } + for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr)) { gimple stmt = gsi_stmt (itr); @@ -522,11 +641,10 @@ predicate_bbs (loop_p loop) gimple_cond_lhs (stmt), gimple_cond_rhs (stmt)); + /* Add new condition into destination's predicate list. */ extract_true_false_edges_from_block (gimple_bb (stmt), &true_edge, &false_edge); - /* Add new condition into destination's predicate list. */ - /* If C is true, then TRUE_EDGE is taken. */ add_to_dst_predicate_list (loop, true_edge, cond, c); @@ -561,7 +679,9 @@ predicate_bbs (loop_p loop) } /* The loop header is always executed. */ - loop->header->aux = boolean_true_node; + set_bb_predicate (loop->header, boolean_true_node); + gcc_assert (bb_predicate_gimplified_stmts (loop->header) == NULL + && bb_predicate_gimplified_stmts (loop->latch) == NULL); return true; } @@ -679,27 +799,12 @@ if_convertible_loop_p (struct loop *loop) return true; } -/* During if-conversion, the bb->aux field is used to hold a predicate - list. This function cleans for all the basic blocks in the given - LOOP their predicate list. */ - -static void -clean_predicate_lists (struct loop *loop) -{ - unsigned int i; - basic_block *bbs = get_loop_body (loop); - - for (i = 0; i < loop->num_nodes; i++) - bbs[i]->aux = NULL; - - free (bbs); -} - -/* Basic block BB has two predecessors. Using predecessor's bb->aux - field, set appropriate condition COND for the PHI node replacement. - Return true block whose phi arguments are selected when cond is - true. LOOP is the loop containing the if-converted region, GSI is - the place to insert the code for the if-conversion. */ +/* Basic block BB has two predecessors. Using predecessor's bb + predicate, set an appropriate condition COND for the PHI node + replacement. Return the true block whose phi arguments are + selected when cond is true. LOOP is the loop containing the + if-converted region, GSI is the place to insert the code for the + if-conversion. */ static basic_block find_phi_replacement_condition (struct loop *loop, @@ -738,7 +843,7 @@ find_phi_replacement_condition (struct loop *loop, See PR23115. */ /* Select condition that is not TRUTH_NOT_EXPR. */ - tmp_cond = (tree) (first_edge->src)->aux; + tmp_cond = bb_predicate (first_edge->src); gcc_assert (tmp_cond); if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR) @@ -756,7 +861,7 @@ find_phi_replacement_condition (struct loop *loop, || dominated_by_p (CDI_DOMINATORS, second_edge->src, first_edge->src)) { - *cond = (tree) (second_edge->src)->aux; + *cond = bb_predicate (second_edge->src); if (TREE_CODE (*cond) == TRUTH_NOT_EXPR) *cond = invert_truthvalue (*cond); @@ -765,7 +870,7 @@ find_phi_replacement_condition (struct loop *loop, first_edge = second_edge; } else - *cond = (tree) (first_edge->src)->aux; + *cond = bb_predicate (first_edge->src); /* Gimplify the condition: the vectorizer prefers to have gimple values as conditions. Various targets use different means to @@ -851,11 +956,11 @@ replace_phi_with_cond_gimple_assign_stmt (gimple phi, tree cond, } } -/* Process phi nodes for the given LOOP. Replace phi nodes with - conditional modify expressions. */ +/* Replaces in LOOP all the phi nodes other than those in the + LOOP->header block with conditional modify expressions. */ static void -process_phi_nodes (struct loop *loop) +ifconvert_phi_nodes (struct loop *loop) { basic_block bb; unsigned int orig_loop_num_nodes = loop->num_nodes; @@ -873,12 +978,13 @@ process_phi_nodes (struct loop *loop) continue; phi_gsi = gsi_start_phis (bb); - gsi = gsi_after_labels (bb); + if (gsi_end_p (phi_gsi)) + continue; /* BB has two predecessors. Using predecessor's aux field, set appropriate condition for the PHI node replacement. */ - if (!gsi_end_p (phi_gsi)) - true_bb = find_phi_replacement_condition (loop, bb, &cond, &gsi); + gsi = gsi_after_labels (bb); + true_bb = find_phi_replacement_condition (loop, bb, &cond, &gsi); while (!gsi_end_p (phi_gsi)) { @@ -887,10 +993,40 @@ process_phi_nodes (struct loop *loop) release_phi_node (phi); gsi_next (&phi_gsi); } + set_phi_nodes (bb, NULL); } } +/* Insert in each basic block of LOOP the statements produced by the + gimplification of the predicates. */ + +static void +insert_gimplified_predicates (loop_p loop) +{ + unsigned int i; + + for (i = 0; i < loop->num_nodes; i++) + { + basic_block bb = ifc_bbs[i]; + gimple_seq stmts = bb_predicate_gimplified_stmts (bb); + + if (stmts) + { + gimple_stmt_iterator gsi = gsi_last_bb (bb); + + if (gsi_end_p (gsi) + || gimple_code (gsi_stmt (gsi)) == GIMPLE_COND) + gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT); + else + gsi_insert_seq_after (&gsi, stmts, GSI_SAME_STMT); + + /* Once the sequence is code generated, set it to NULL. */ + set_bb_predicate_gimplified_stmts (bb, NULL); + } + } +} + /* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks other than the exit and latch of the LOOP. Also resets the GIMPLE_DEBUG information. */ @@ -903,7 +1039,7 @@ remove_conditions_and_labels (loop_p loop) for (i = 0; i < loop->num_nodes; i++) { - basic_block bb = ifc_bbs [i]; + basic_block bb = ifc_bbs[i]; if (bb_with_exit_edge_p (loop, bb) || bb == loop->latch) @@ -946,9 +1082,8 @@ combine_blocks (struct loop *loop) edge_iterator ei; remove_conditions_and_labels (loop); - - /* Process phi nodes to prepare blocks for merge. */ - process_phi_nodes (loop); + insert_gimplified_predicates (loop); + ifconvert_phi_nodes (loop); /* Merge basic blocks: first remove all the edges in the loop, except for those from the exit block. */ @@ -1052,9 +1187,13 @@ tree_if_conversion (struct loop *loop) combine_blocks (loop); cleanup: - clean_predicate_lists (loop); if (ifc_bbs) { + unsigned int i; + + for (i = 0; i < loop->num_nodes; i++) + free_bb_predicate (ifc_bbs[i]); + free (ifc_bbs); ifc_bbs = NULL; } -- 1.7.0.4