From 2b252fdbe15075984b766120464ea987c2e484c3 Mon Sep 17 00:00:00 2001 From: spop Date: Wed, 7 Apr 2010 06:33:35 +0000 Subject: [PATCH] Fix comments in ifconvert. 2010-04-07 Sebastian Pop * tree-if-conv.c: Fix indentation and comments. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@158039 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/ChangeLog | 4 + gcc/tree-if-conv.c | 346 ++++++++++++++++++++++++++++++++++------------------- 2 files changed, 229 insertions(+), 121 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index d6eb9523b7d..68e82846e0d 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,7 @@ +2010-04-07 Sebastian Pop + + * tree-if-conv.c: Fix indentation and comments. + 2010-04-06 Sebastian Pop PR middle-end/43519 diff --git a/gcc/tree-if-conv.c b/gcc/tree-if-conv.c index fbdaa0df36c..e7af4aa5103 100644 --- a/gcc/tree-if-conv.c +++ b/gcc/tree-if-conv.c @@ -103,8 +103,12 @@ along with GCC; see the file COPYING3. If not see /* List of basic blocks in if-conversion-suitable order. */ static basic_block *ifc_bbs; -/* Create a new temp variable of type TYPE. Add GIMPLE_ASSIGN to assign EXP - to the new variable. */ +/* Main entry point. Apply if-conversion to the LOOP. Return true if + successful otherwise return false. If false is returned then loop + remains unchanged. FOR_VECTORIZER is a boolean flag. It indicates + whether if-conversion is used for vectorizer or not. If it is used + for vectorizer, additional checks are used. (Vectorization checks + are not yet implemented). */ static gimple ifc_temp_var (tree type, tree exp) @@ -127,44 +131,9 @@ ifc_temp_var (tree type, tree exp) SSA_NAME_DEF_STMT (new_name) = stmt; update_stmt (stmt); - return stmt; -} - -/* Add condition NEW_COND to the predicate list of basic block BB. */ - -static void -add_to_predicate_list (basic_block bb, tree new_cond) -{ - tree cond = (tree) bb->aux; - - if (cond) - cond = fold_build2_loc (EXPR_LOCATION (cond), - TRUTH_OR_EXPR, boolean_type_node, - unshare_expr (cond), new_cond); - else - cond = new_cond; - - bb->aux = cond; -} - -/* Add the condition COND to the previous condition PREV_COND, and add this - to the predicate list of the destination of edge E. GSI is the - place where the gimplification of the resulting condition should - output code. LOOP is the loop to be if-converted. */ - -static tree -add_to_dst_predicate_list (struct loop *loop, edge e, - tree prev_cond, tree cond, - gimple_stmt_iterator *gsi) -{ - tree new_cond = NULL_TREE; - - if (!flow_bb_inside_loop_p (loop, e->dest)) - return NULL_TREE; - - if (prev_cond == boolean_true_node || !prev_cond) - new_cond = unshare_expr (cond); - else + /* If-conversion is not appropriate for all loops. First, check if + loop is if-convertible or not. */ + if (!if_convertible_loop_p (loop, for_vectorizer)) { tree tmp; gimple tmp_stmt = NULL; @@ -206,10 +175,11 @@ bb_with_exit_edge_p (struct loop *loop, basic_block bb) return false; } -/* STMT is a GIMPLE_COND. Update two destination's predicate list. - Remove COND_EXPR, if it is not the exit condition of LOOP. - Otherwise update the exit condition of LOOP appropriately. GSI - points to the statement STMT. */ + /* Successor bb inherits predicate of its predecessor. If there + is no predicate in predecessor bb, then consider successor bb + as always executed. */ + if (cond == NULL_TREE) + cond = boolean_true_node; static void tree_if_convert_cond_stmt (struct loop *loop, gimple stmt, tree cond, @@ -221,8 +191,10 @@ tree_if_convert_cond_stmt (struct loop *loop, gimple stmt, tree cond, tree c = fold_build2_loc (loc, gimple_cond_code (stmt), boolean_type_node, gimple_cond_lhs (stmt), gimple_cond_rhs (stmt)); - extract_true_false_edges_from_block (gimple_bb (stmt), - &true_edge, &false_edge); + /* Now, all statements are if-converted and basic blocks are + annotated appropriately. Combine all basic block into one huge + basic block. */ + combine_blocks (loop); /* Add new condition into destination's predicate list. */ @@ -244,12 +216,11 @@ tree_if_convert_cond_stmt (struct loop *loop, gimple stmt, tree cond, } /* If-convert stmt T which is part of LOOP. - - If T is a GIMPLE_ASSIGN then it is converted into a conditional - modify expression using COND. For conditional expressions, add - a condition in the destination basic block's predicate list and - remove the conditional expression itself. GSI points to the - statement T. */ + If T is a GIMPLE_ASSIGN then it is converted into conditional modify + expression using COND. For conditional expressions, add condition in the + destination basic block's predicate list and remove conditional + expression itself. BSI is the iterator used to traverse statements of + loop. It is used here when it is required to delete current statement. */ static tree tree_if_convert_stmt (struct loop *loop, gimple t, tree cond, @@ -295,15 +266,54 @@ tree_if_convert_stmt (struct loop *loop, gimple t, tree cond, default: gcc_unreachable (); } - return cond; } -/* Return true when PHI is if-convertible. PHI is part of loop LOOP - and it belongs to basic block BB. +/* STMT is a GIMPLE_COND. Update two destination's predicate list. + Remove COND_EXPR, if it is not the loop exit condition. Otherwise + update loop exit condition appropriately. GSI is the iterator + used to traverse statement list. STMT is part of loop LOOP. */ + +static void +tree_if_convert_cond_stmt (struct loop *loop, gimple stmt, tree cond, + gimple_stmt_iterator *gsi) +{ + tree c, c2; + edge true_edge, false_edge; + location_t loc = gimple_location (stmt); + + gcc_assert (gimple_code (stmt) == GIMPLE_COND); + + c = fold_build2_loc (loc, gimple_cond_code (stmt), boolean_type_node, + gimple_cond_lhs (stmt), gimple_cond_rhs (stmt)); - PHI is not if-convertible if: - - it has more than 2 arguments, + 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, gsi); + + /* If C is false, then FALSE_EDGE is taken. */ + c2 = invert_truthvalue_loc (loc, unshare_expr (c)); + add_to_dst_predicate_list (loop, false_edge, cond, c2, gsi); + + /* Now this conditional statement is redundant. Remove it. + But, do not remove exit condition! Update exit condition + using new condition. */ + if (!bb_with_exit_edge_p (loop, gimple_bb (stmt))) + { + gsi_remove (gsi, true); + cond = NULL_TREE; + } + return; +} + +/* Return true, iff PHI is if-convertible. PHI is part of loop LOOP + and it belongs to basic block BB. + PHI is not if-convertible + - if it has more than 2 arguments, - virtual PHI is immediately used in another PHI node, - virtual PHI on BB other than header. */ @@ -354,7 +364,6 @@ if_convertible_phi_p (struct loop *loop, basic_block bb, gimple phi) - it is not movable, - it could trap, - LHS is not var decl. - GIMPLE_ASSIGN is part of block BB, which is inside loop LOOP. */ static bool @@ -405,13 +414,11 @@ if_convertible_gimple_assign_stmt_p (struct loop *loop, basic_block bb, return true; } -/* Return true when STMT is if-convertible. - - A statement is if-convertible if: - - it is an if-convertible GIMPLE_ASSGIN, - - it is a GIMPLE_LABEL or a GIMPLE_COND. - - STMT is inside BB, which is inside loop LOOP. */ +/* Return true, iff STMT is if-convertible. + Statement is if-convertible if, + - it is if-convertible GIMPLE_ASSGIN, + - it is GIMPLE_LABEL or GIMPLE_COND. + STMT is inside block BB, which is inside loop LOOP. */ static bool if_convertible_stmt_p (struct loop *loop, basic_block bb, gimple stmt) @@ -440,16 +447,14 @@ if_convertible_stmt_p (struct loop *loop, basic_block bb, gimple stmt) return true; } -/* Return true when BB is if-convertible. This routine does not check - basic block's statements and phis. - - A basic block is not if-convertible if: - - it is non-empty and it is after the exit block (in BFS order), - - it is after the exit block but before the latch, - - its edges are not normal. - - EXIT_BB is the basic block containing the exit of the LOOP. BB is - inside LOOP. */ +/* Return true, iff BB is if-convertible. + Note: This routine does _not_ check basic block statements and phis. + Basic block is not if-convertible if: + - basic block is non-empty and it is after exit block (in BFS order), + - basic block is after exit block but before latch, + - basic block edge(s) is not normal. + EXIT_BB_SEEN is true if basic block with exit edge is already seen. + BB is inside loop LOOP. */ static bool if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb) @@ -497,8 +502,17 @@ if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb) return true; } -/* Return true when all predecessor blocks of BB are visited. The - VISITED bitmap keeps track of the visited blocks. */ +/* Return true, iff LOOP is if-convertible. + LOOP is if-convertible if: + - it is innermost, + - it has two or more basic blocks, + - it has only one exit, + - loop header is not the exit edge, + - if its basic blocks and phi nodes are if convertible. See above for + more info. + FOR_VECTORIZER enables vectorizer specific checks, for example, support + for vector conditions, data dependency checks, etc. + (Not implemented yet). */ static bool pred_blocks_visited_p (basic_block bb, bitmap *visited) @@ -668,11 +682,69 @@ 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. It also cleans up the e->aux field of - all the successor edges: e->aux is used to hold the true and false - conditions for conditional expressions. */ +/* Add condition COND into predicate list of basic block BB. */ + +static void +add_to_predicate_list (basic_block bb, tree new_cond) +{ + tree cond = (tree) bb->aux; + + if (cond) + cond = fold_build2_loc (EXPR_LOCATION (cond), + TRUTH_OR_EXPR, boolean_type_node, + unshare_expr (cond), new_cond); + else + cond = new_cond; + + bb->aux = cond; +} + +/* Add condition COND into BB's predicate list. PREV_COND is + existing condition. */ + +static tree +add_to_dst_predicate_list (struct loop * loop, edge e, + tree prev_cond, tree cond, + gimple_stmt_iterator *gsi) +{ + tree new_cond = NULL_TREE; + + if (!flow_bb_inside_loop_p (loop, e->dest)) + return NULL_TREE; + + if (prev_cond == boolean_true_node || !prev_cond) + new_cond = unshare_expr (cond); + else + { + tree tmp; + gimple tmp_stmt = NULL; + + prev_cond = force_gimple_operand_gsi (gsi, unshare_expr (prev_cond), + true, NULL, true, GSI_SAME_STMT); + + cond = force_gimple_operand_gsi (gsi, unshare_expr (cond), + true, NULL, true, GSI_SAME_STMT); + + /* Add the condition to aux field of the edge. In case edge + destination is a PHI node, this condition will be ANDed with + block predicate to construct complete condition. */ + e->aux = cond; + + /* new_cond == prev_cond AND cond */ + tmp = build2 (TRUTH_AND_EXPR, boolean_type_node, + unshare_expr (prev_cond), cond); + tmp_stmt = ifc_temp_var (boolean_type_node, tmp); + gsi_insert_before (gsi, tmp_stmt, GSI_SAME_STMT); + new_cond = gimple_assign_lhs (tmp_stmt); + } + add_to_predicate_list (e->dest, new_cond); + return new_cond; +} + +/* During if-conversion aux field from basic block structure is used to hold + predicate list. Clean each basic block's predicate list for the given LOOP. + Also clean aux field of successor edges, used to hold true and false + condition from conditional expression. */ static void clean_predicate_lists (struct loop *loop) @@ -692,11 +764,9 @@ clean_predicate_lists (struct loop *loop) free (bb); } -/* 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 aux field, set + appropriate condition COND for the PHI node replacement. Return true block + whose phi arguments are selected when cond is true. */ static basic_block find_phi_replacement_condition (struct loop *loop, @@ -993,25 +1063,78 @@ combine_blocks (struct loop *loop) delete_basic_block (bb); } - /* If possible, merge loop header to the block with the exit edge. - This reduces the number of basic blocks to two, to please the - vectorizer that handles only loops with two nodes. - - FIXME: Call cleanup_tree_cfg. */ + /* Now if possible, merge loop header and block with exit edge. + This reduces number of basic blocks to 2. Auto vectorizer addresses + loops with two nodes only. FIXME: Use cleanup_tree_cfg(). */ if (exit_bb && exit_bb != loop->header && can_merge_blocks_p (loop->header, exit_bb)) merge_blocks (loop->header, exit_bb); } -/* Main entry point: return true when LOOP is if-converted, otherwise - the loop remains unchanged. */ +/* Make a new temp variable of type TYPE. Add GIMPLE_ASSIGN to assign EXP + to the new variable. */ + +static gimple +ifc_temp_var (tree type, tree exp) +{ + const char *name = "_ifc_"; + tree var, new_name; + gimple stmt; + + /* Create new temporary variable. */ + var = create_tmp_var (type, name); + add_referenced_var (var); + + /* Build new statement to assign EXP to new variable. */ + stmt = gimple_build_assign (var, exp); + + /* Get SSA name for the new variable and set make new statement + its definition statement. */ + new_name = make_ssa_name (var, stmt); + gimple_assign_set_lhs (stmt, new_name); + SSA_NAME_DEF_STMT (new_name) = stmt; + update_stmt (stmt); + + return stmt; +} + + +/* Return TRUE iff, all pred blocks of BB are visited. + Bitmap VISITED keeps history of visited blocks. */ static bool tree_if_conversion (struct loop *loop) { - gimple_stmt_iterator itr; - unsigned int i; + edge e; + edge_iterator ei; + FOR_EACH_EDGE (e, ei, bb->preds) + if (!bitmap_bit_p (*visited, e->src->index)) + return false; + + return true; +} + +/* Get body of a LOOP in suitable order for if-conversion. It is + caller's responsibility to deallocate basic block list. + If-conversion suitable order is, breadth first sort (BFS) order + with an additional constraint: select a block only if all its + predecessors are already selected. */ + +static basic_block * +get_loop_body_in_if_conv_order (const struct loop *loop) +{ + basic_block *blocks, *blocks_in_bfs_order; + basic_block bb; + bitmap visited; + unsigned int index = 0; + unsigned int visited_count = 0; + + gcc_assert (loop->num_nodes); + gcc_assert (loop->latch != EXIT_BLOCK_PTR); + + blocks = XCNEWVEC (basic_block, loop->num_nodes); + visited = BITMAP_ALLOC (NULL); ifc_bbs = NULL; @@ -1026,19 +1149,8 @@ tree_if_conversion (struct loop *loop) free (ifc_bbs); ifc_bbs = NULL; } - free_dominance_info (CDI_POST_DOMINATORS); - return false; - } - - for (i = 0; i < loop->num_nodes; i++) - { - basic_block bb = ifc_bbs [i]; - tree cond = (tree) bb->aux; - /* Process all the statements in this basic block. - Remove conditional expression, if any, and annotate - destination basic block(s) appropriately. */ - for (itr = gsi_start_bb (bb); !gsi_end_p (itr); /* empty */) + if (!bitmap_bit_p (visited, bb->index)) { gimple t = gsi_stmt (itr); cond = tree_if_convert_stmt (loop, t, cond, &itr); @@ -1046,20 +1158,12 @@ tree_if_conversion (struct loop *loop) gsi_next (&itr); } - /* If current bb has only one successor, then consider it as an - unconditional goto. */ - if (single_succ_p (bb)) - { - basic_block bb_n = single_succ (bb); - - /* The successor bb inherits the predicate of its - predecessor. If there is no predicate in the predecessor - bb, then consider the successor bb as always executed. */ - if (cond == NULL_TREE) - cond = boolean_true_node; + index++; - add_to_predicate_list (bb_n, cond); - } + if (index == loop->num_nodes + && visited_count != loop->num_nodes) + /* Not done yet. */ + index = 0; } /* Now, all statements are if-converted and basic blocks are -- 2.11.0