X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Ftree-if-conv.c;h=43b04c1900ef5c8feff607e31ff65c49db11cf10;hb=40e175e78b8bfcaf6afa0f75e705d62f752cc3e9;hp=076eca9828dee964a0bf7a5eac9b5a756c5156b4;hpb=0891994dee8eb49ac15db2cd7b8d8a168b022870;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/tree-if-conv.c b/gcc/tree-if-conv.c index 076eca9828d..43b04c1900e 100644 --- a/gcc/tree-if-conv.c +++ b/gcc/tree-if-conv.c @@ -1,12 +1,13 @@ /* If-conversion for vectorizer. - Copyright (C) 2004 Free Software Foundation, Inc. + Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009 + Free Software Foundation, Inc. Contributed by Devang Patel This file is part of GCC. GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free -Software Foundation; either version 2, or (at your option) any later +Software Foundation; either version 3, or (at your option) any later version. GCC is distributed in the hope that it will be useful, but WITHOUT ANY @@ -15,16 +16,16 @@ FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License -along with GCC; see the file COPYING. If not, write to the Free -Software Foundation, 59 Temple Place - Suite 330, Boston, MA -02111-1307, USA. */ +along with GCC; see the file COPYING3. If not see +. */ -/* This pass implements tree level if-conversion transformation of loops. - Initial goal is to help vectorizer vectorize loops with conditions. +/* This pass implements a tree level if-conversion of loops. Its + initial goal is to help the vectorizer to vectorize loops with + conditions. A short description of if-conversion: - o Decide if a loop is if-convertable or not. + o Decide if a loop is if-convertible or not. o Walk all loop basic blocks in breadth first order (BFS order). o Remove conditional statements (at the end of basic block) and propagate condition into destination basic blocks' @@ -84,9 +85,7 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA #include "system.h" #include "coretypes.h" #include "tm.h" -#include "errors.h" #include "tree.h" -#include "c-common.h" #include "flags.h" #include "timevar.h" #include "varray.h" @@ -102,255 +101,243 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA #include "tree-pass.h" #include "target.h" -/* local function prototypes */ -static void main_tree_if_conversion (void); -static tree tree_if_convert_stmt (struct loop *loop, tree, tree, - block_stmt_iterator *); -static void tree_if_convert_cond_expr (struct loop *, tree, tree, - block_stmt_iterator *); -static bool if_convertable_phi_p (struct loop *, basic_block, tree); -static bool if_convertable_modify_expr_p (struct loop *, basic_block, tree); -static bool if_convertable_stmt_p (struct loop *, basic_block, tree); -static bool if_convertable_bb_p (struct loop *, basic_block, bool); -static bool if_convertable_loop_p (struct loop *, bool); -static void add_to_predicate_list (basic_block, tree); -static tree add_to_dst_predicate_list (struct loop * loop, basic_block, tree, tree, - block_stmt_iterator *); -static void clean_predicate_lists (struct loop *loop); -static basic_block find_phi_replacement_condition (basic_block, tree *, - block_stmt_iterator *); -static void replace_phi_with_cond_modify_expr (tree, tree, basic_block, - block_stmt_iterator *); -static void process_phi_nodes (struct loop *); -static void combine_blocks (struct loop *); -static tree ifc_temp_var (tree, tree); -static bool pred_blocks_visited_p (basic_block, bitmap *); -static basic_block * get_loop_body_in_if_conv_order (const struct loop *loop); -static bool bb_with_exit_edge_p (basic_block); - /* List of basic blocks in if-conversion-suitable order. */ static basic_block *ifc_bbs; -/* 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). */ +/* Create a new temp variable of type TYPE. Add GIMPLE_ASSIGN to assign EXP + to the new variable. */ -static bool -tree_if_conversion (struct loop *loop, bool for_vectorizer) +static gimple +ifc_temp_var (tree type, tree exp) { - basic_block bb; - block_stmt_iterator itr; - tree cond; - unsigned int i; - - ifc_bbs = NULL; - - /* if-conversion is not appropriate for all loops. First, check if loop is - if-convertable or not. */ - if (!if_convertable_loop_p (loop, for_vectorizer)) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file,"-------------------------\n"); - if (ifc_bbs) - { - free (ifc_bbs); - ifc_bbs = NULL; - } - free_dominance_info (CDI_POST_DOMINATORS); - free_df (); - return false; - } + const char *name = "_ifc_"; + tree var, new_name; + gimple stmt; - cond = NULL_TREE; + /* Create new temporary variable. */ + var = create_tmp_var (type, name); + add_referenced_var (var); - /* Do actual work now. */ - for (i = 0; i < loop->num_nodes; i++) - { - bb = ifc_bbs [i]; + /* Build new statement to assign EXP to new variable. */ + stmt = gimple_build_assign (var, exp); - /* Update condition using predicate list. */ - cond = bb->aux; + /* 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); - /* Process all statements in this basic block. - Remove conditional expression, if any, and annotate - destination basic block(s) appropriately. */ - for (itr = bsi_start (bb); !bsi_end_p (itr); /* empty */) - { - tree t = bsi_stmt (itr); - cond = tree_if_convert_stmt (loop, t, cond, &itr); - if (!bsi_end_p (itr)) - bsi_next (&itr); - } + return stmt; +} - /* If current bb has only one successor, then consider it as an - unconditional goto. */ - if (EDGE_COUNT (bb->succs) == 1) - { - basic_block bb_n = EDGE_SUCC (bb, 0)->dest; - if (cond != NULL_TREE) - add_to_predicate_list (bb_n, cond); - cond = NULL_TREE; - } - } +/* Add condition NEW_COND to the predicate list of basic block BB. */ - /* Now, all statements are if-converted and basic blocks are - annotated appropriately. Combine all basic block into one huge - basic block. */ - combine_blocks (loop); +static void +add_to_predicate_list (basic_block bb, tree new_cond) +{ + tree cond = (tree) bb->aux; - /* clean up */ - clean_predicate_lists (loop); - free (ifc_bbs); - ifc_bbs = NULL; - free_df (); + if (cond) + cond = fold_build2_loc (EXPR_LOCATION (cond), + TRUTH_OR_EXPR, boolean_type_node, + unshare_expr (cond), new_cond); + else + cond = new_cond; - return true; + bb->aux = cond; } -/* if-convert stmt T which is part of LOOP. - If T is a MODIFY_EXPR than 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. */ +/* 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 -tree_if_convert_stmt (struct loop * loop, tree t, tree cond, - block_stmt_iterator *bsi) +add_to_dst_predicate_list (struct loop *loop, edge e, + tree prev_cond, tree cond, + gimple_stmt_iterator *gsi) { - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "------if-convert stmt\n"); - print_generic_stmt (dump_file, t, TDF_SLIM); - print_generic_stmt (dump_file, cond, TDF_SLIM); - } + tree new_cond = NULL_TREE; + + if (!flow_bb_inside_loop_p (loop, e->dest)) + return NULL_TREE; - switch (TREE_CODE (t)) + if (prev_cond == boolean_true_node || !prev_cond) + new_cond = unshare_expr (cond); + else { - /* Labels are harmless here. */ - case LABEL_EXPR: - break; + tree tmp; + gimple tmp_stmt = NULL; - case MODIFY_EXPR: - /* This modify_expr is killing previous value of LHS. Appropriate value will - be selected by PHI node based on condition. It is possible that before - this transformation, PHI nodes was selecting default value and now it will - use this new value. This is OK because it does not change validity the - program. */ - break; + prev_cond = force_gimple_operand_gsi (gsi, unshare_expr (prev_cond), + true, NULL, true, GSI_SAME_STMT); - case GOTO_EXPR: - /* Unconditional goto */ - add_to_predicate_list (bb_for_stmt (TREE_OPERAND (t, 1)), cond); - bsi_remove (bsi); - cond = NULL_TREE; - break; + cond = force_gimple_operand_gsi (gsi, unshare_expr (cond), + true, NULL, true, GSI_SAME_STMT); - case COND_EXPR: - /* Update destination blocks' predicate list and remove this - condition expression. */ - tree_if_convert_cond_expr (loop, t, cond, bsi); - cond = NULL_TREE; - break; + /* Add the condition COND to the e->aux field. In case the edge + destination is a PHI node, this condition will be added to + the block predicate to construct a complete condition. */ + e->aux = cond; - default: - gcc_unreachable (); + 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); } - return cond; + + add_to_predicate_list (e->dest, new_cond); + return new_cond; } -/* STMT is COND_EXPR. Update two destination's predicate list. - Remove COND_EXPR, if it is not the loop exit condition. Otherwise - update loop exit condition appropriately. BSI is the iterator - used to traverse statement list. STMT is part of loop LOOP. */ +/* Return true if one of the successor edges of BB exits LOOP. */ -static void -tree_if_convert_cond_expr (struct loop *loop, tree stmt, tree cond, - block_stmt_iterator *bsi) +static bool +bb_with_exit_edge_p (struct loop *loop, basic_block bb) { - tree c, c2, new_cond; - edge true_edge, false_edge; - new_cond = NULL_TREE; + edge e; + edge_iterator ei; + + FOR_EACH_EDGE (e, ei, bb->succs) + if (loop_exit_edge_p (loop, e)) + return true; - gcc_assert (TREE_CODE (stmt) == COND_EXPR); + return false; +} - c = COND_EXPR_COND (stmt); +/* 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. */ - /* Create temp. for condition. */ - if (!is_gimple_condexpr (c)) - { - tree new_stmt; - new_stmt = ifc_temp_var (TREE_TYPE (c), unshare_expr (c)); - bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT); - c = TREE_OPERAND (new_stmt, 0); - } +static void +tree_if_convert_cond_stmt (struct loop *loop, gimple stmt, tree cond, + gimple_stmt_iterator *gsi) +{ + tree c2; + edge true_edge, false_edge; + location_t loc = gimple_location (stmt); + 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 (bb_for_stmt (stmt), + 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. */ - new_cond = add_to_dst_predicate_list (loop, true_edge->dest, cond, - unshare_expr (c), bsi); + /* 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); - if (!is_gimple_reg(c) && is_gimple_condexpr (c)) + /* Now this conditional statement is redundant. Remove it. But, do + not remove the exit condition! Update the exit condition using + the new condition. */ + if (!bb_with_exit_edge_p (loop, gimple_bb (stmt))) { - tree new_stmt; - new_stmt = ifc_temp_var (TREE_TYPE (c), unshare_expr (c)); - bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT); - c = TREE_OPERAND (new_stmt, 0); + gsi_remove (gsi, true); + cond = NULL_TREE; } +} + +/* If-convert stmt T which is part of LOOP. - /* If 'c' is false then FALSE_EDGE is taken. */ - c2 = invert_truthvalue (unshare_expr (c)); - add_to_dst_predicate_list (loop, false_edge->dest, cond, c2, bsi); + 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. */ + +static tree +tree_if_convert_stmt (struct loop *loop, gimple t, tree cond, + gimple_stmt_iterator *gsi) +{ + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "------if-convert stmt\n"); + print_gimple_stmt (dump_file, t, 0, TDF_SLIM); + print_generic_stmt (dump_file, cond, TDF_SLIM); + } - /* 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 (bb_for_stmt (stmt))) + switch (gimple_code (t)) { - bsi_remove (bsi); + /* Labels are harmless here. */ + case GIMPLE_LABEL: + break; + + case GIMPLE_DEBUG: + /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */ + if (gimple_debug_bind_p (gsi_stmt (*gsi))) + { + gimple_debug_bind_reset_value (gsi_stmt (*gsi)); + update_stmt (gsi_stmt (*gsi)); + } + break; + + case GIMPLE_ASSIGN: + /* This GIMPLE_ASSIGN is killing previous value of LHS. Appropriate + value will be selected by PHI node based on condition. It is possible + that before this transformation, PHI nodes was selecting default + value and now it will use this new value. This is OK because it does + not change the validity of the program. */ + break; + + case GIMPLE_COND: + /* Update destination blocks' predicate list and remove this + condition expression. */ + tree_if_convert_cond_stmt (loop, t, cond, gsi); cond = NULL_TREE; + break; + + default: + gcc_unreachable (); } - return; + + return cond; } -/* Return true, iff PHI is if-convertable. PHI is part of loop LOOP +/* Return true when PHI is if-convertible. PHI is part of loop LOOP and it belongs to basic block BB. - PHI is not if-convertable - - if it has more than 2 arguments. - - Virtual PHI is immediately used in another PHI node. */ + + 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. */ static bool -if_convertable_phi_p (struct loop *loop, basic_block bb, tree phi) +if_convertible_phi_p (struct loop *loop, basic_block bb, gimple phi) { if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "-------------------------\n"); - print_generic_stmt (dump_file, phi, TDF_SLIM); + print_gimple_stmt (dump_file, phi, 0, TDF_SLIM); } - if (bb != loop->header && PHI_NUM_ARGS (phi) != 2) + if (bb != loop->header && gimple_phi_num_args (phi) != 2) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "More than two phi node args.\n"); return false; } - if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi)))) + if (!is_gimple_reg (SSA_NAME_VAR (gimple_phi_result (phi)))) { - int j; - dataflow_t df = get_immediate_uses (phi); - int num_uses = num_immediate_uses (df); - for (j = 0; j < num_uses; j++) + imm_use_iterator imm_iter; + use_operand_p use_p; + + if (bb != loop->header) { - tree use = immediate_use (df, j); - if (TREE_CODE (use) == PHI_NODE) + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Virtual phi not on loop header.\n"); + return false; + } + FOR_EACH_IMM_USE_FAST (use_p, imm_iter, gimple_phi_result (phi)) + { + if (gimple_code (USE_STMT (use_p)) == GIMPLE_PHI) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "Difficult to handle this virtual phi.\n"); @@ -362,93 +349,90 @@ if_convertable_phi_p (struct loop *loop, basic_block bb, tree phi) return true; } -/* Return true, if M_EXPR is if-convertable. - MODIFY_EXPR is not if-convertable if, - - It is not movable. - - It could trap. +/* Return true when STMT is if-convertible. + + GIMPLE_ASSIGN statement is not if-convertible if, + - it is not movable, + - it could trap, - LHS is not var decl. - MODIFY_EXPR is part of block BB, which is inside loop LOOP. -*/ + + GIMPLE_ASSIGN is part of block BB, which is inside loop LOOP. */ static bool -if_convertable_modify_expr_p (struct loop *loop, basic_block bb, tree m_expr) +if_convertible_gimple_assign_stmt_p (struct loop *loop, basic_block bb, + gimple stmt) { + tree lhs = gimple_assign_lhs (stmt); + if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "-------------------------\n"); - print_generic_stmt (dump_file, m_expr, TDF_SLIM); + print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); } - /* Be conservative and do not handle immovable expressions. */ - if (movement_possibility (m_expr) == MOVE_IMPOSSIBLE) + /* Some of these constrains might be too conservative. */ + if (stmt_ends_bb_p (stmt) + || gimple_has_volatile_ops (stmt) + || (TREE_CODE (lhs) == SSA_NAME + && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)) + || gimple_has_side_effects (stmt)) { if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "stmt is movable. Don't take risk\n"); + fprintf (dump_file, "stmt not suitable for ifcvt\n"); return false; } /* See if it needs speculative loading or not. */ if (bb != loop->header - && tree_could_trap_p (TREE_OPERAND (m_expr, 1))) + && gimple_assign_rhs_could_trap_p (stmt)) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "tree could trap...\n"); return false; } - if (TREE_CODE (TREE_OPERAND (m_expr, 1)) == CALL_EXPR) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "CALL_EXPR \n"); - return false; - } - - if (TREE_CODE (TREE_OPERAND (m_expr, 0)) != SSA_NAME + if (TREE_CODE (lhs) != SSA_NAME && bb != loop->header - && !bb_with_exit_edge_p (bb)) + && !bb_with_exit_edge_p (loop, bb)) { if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "LHS is not var\n"); - print_generic_stmt (dump_file, m_expr, TDF_SLIM); + print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); } return false; } - return true; } -/* Return true, iff STMT is if-convertable. - Statement is if-convertable if, - - It is if-convertable MODIFY_EXPR - - IT is LABEL_EXPR, GOTO_EXPR or COND_EXPR. - STMT is inside block BB, which is inside loop LOOP. */ +/* 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. */ static bool -if_convertable_stmt_p (struct loop *loop, basic_block bb, tree stmt) +if_convertible_stmt_p (struct loop *loop, basic_block bb, gimple stmt) { - switch (TREE_CODE (stmt)) + switch (gimple_code (stmt)) { - case LABEL_EXPR: - break; - - case MODIFY_EXPR: - - if (!if_convertable_modify_expr_p (loop, bb, stmt)) - return false; - break; + case GIMPLE_LABEL: + case GIMPLE_DEBUG: + case GIMPLE_COND: + return true; - case GOTO_EXPR: - case COND_EXPR: - break; + case GIMPLE_ASSIGN: + return if_convertible_gimple_assign_stmt_p (loop, bb, stmt); default: /* Don't know what to do with 'em so don't do anything. */ if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "don't know what to do\n"); - print_generic_stmt (dump_file, stmt, TDF_SLIM); + print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); } return false; break; @@ -457,17 +441,19 @@ if_convertable_stmt_p (struct loop *loop, basic_block bb, tree stmt) return true; } -/* Return true, iff BB is if-convertable. - Note: This routine does _not_ check basic block statements and phis. - Basic block is not if-convertable 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. */ +/* 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. */ static bool -if_convertable_bb_p (struct loop *loop, basic_block bb, bool exit_bb_seen) +if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb) { edge e; edge_iterator ei; @@ -475,7 +461,7 @@ if_convertable_bb_p (struct loop *loop, basic_block bb, bool exit_bb_seen) if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "----------[%d]-------------\n", bb->index); - if (exit_bb_seen) + if (exit_bb) { if (bb != loop->latch) { @@ -489,6 +475,14 @@ if_convertable_bb_p (struct loop *loop, basic_block bb, bool exit_bb_seen) fprintf (dump_file, "non empty basic block after exit bb\n"); return false; } + else if (bb == loop->latch + && bb != exit_bb + && !dominated_by_p (CDI_DOMINATORS, bb, exit_bb)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "latch is not dominated by exit_block\n"); + return false; + } } /* Be less adventurous and handle only normal edges. */ @@ -497,34 +491,104 @@ if_convertable_bb_p (struct loop *loop, basic_block bb, bool exit_bb_seen) (EDGE_ABNORMAL_CALL | EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP)) { if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file,"Difficult to handle edges\n"); + fprintf (dump_file, "Difficult to handle edges\n"); return false; } return true; } -/* Return true, iff LOOP is if-convertable. - LOOP is if-convertable 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 convertable. See above for - more info. - FOR_VECTORIZER enables vectorizer specific checks. For example, support - for vector conditions, data dependency checks etc.. (Not implemented yet). */ +/* Return true when all predecessor blocks of BB are visited. The + VISITED bitmap keeps track of the visited blocks. */ static bool -if_convertable_loop_p (struct loop *loop, bool for_vectorizer ATTRIBUTE_UNUSED) +pred_blocks_visited_p (basic_block bb, bitmap *visited) { - tree phi; + 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; - block_stmt_iterator itr; + 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); + + blocks_in_bfs_order = get_loop_body_in_bfs_order (loop); + + index = 0; + while (index < loop->num_nodes) + { + bb = blocks_in_bfs_order [index]; + + if (bb->flags & BB_IRREDUCIBLE_LOOP) + { + free (blocks_in_bfs_order); + BITMAP_FREE (visited); + free (blocks); + return NULL; + } + + if (!bitmap_bit_p (visited, bb->index)) + { + if (pred_blocks_visited_p (bb, &visited) + || bb == loop->header) + { + /* This block is now visited. */ + bitmap_set_bit (visited, bb->index); + blocks[visited_count++] = bb; + } + } + + index++; + + if (index == loop->num_nodes + && visited_count != loop->num_nodes) + /* Not done yet. */ + index = 0; + } + free (blocks_in_bfs_order); + BITMAP_FREE (visited); + return blocks; +} + +/* Return true when 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. */ + +static bool +if_convertible_loop_p (struct loop *loop) +{ + basic_block bb; + gimple_stmt_iterator itr; unsigned int i; edge e; edge_iterator ei; - bool exit_bb_seen = false; + basic_block exit_bb = NULL; /* Handle only inner most loop. */ if (!loop || loop->inner) @@ -534,8 +598,6 @@ if_convertable_loop_p (struct loop *loop, bool for_vectorizer ATTRIBUTE_UNUSED) return false; } - flow_loop_scan (loop, LOOP_ALL); - /* If only one block, no need for if-conversion. */ if (loop->num_nodes <= 2) { @@ -545,7 +607,7 @@ if_convertable_loop_p (struct loop *loop, bool for_vectorizer ATTRIBUTE_UNUSED) } /* More than one loop exit is too much to handle. */ - if (loop->num_exits > 1) + if (!single_exit (loop)) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "multiple exits\n"); @@ -557,10 +619,10 @@ if_convertable_loop_p (struct loop *loop, bool for_vectorizer ATTRIBUTE_UNUSED) /* If one of the loop header's edge is exit edge then do not apply if-conversion. */ FOR_EACH_EDGE (e, ei, loop->header->succs) - if ( e->flags & EDGE_LOOP_EXIT) - return false; - - compute_immediate_uses (TDFA_USE_OPS|TDFA_USE_VOPS, NULL); + { + if (loop_exit_edge_p (loop, e)) + return false; + } calculate_dominance_info (CDI_DOMINATORS); calculate_dominance_info (CDI_POST_DOMINATORS); @@ -579,26 +641,27 @@ if_convertable_loop_p (struct loop *loop, bool for_vectorizer ATTRIBUTE_UNUSED) { bb = ifc_bbs[i]; - if (!if_convertable_bb_p (loop, bb, exit_bb_seen)) + if (!if_convertible_bb_p (loop, bb, exit_bb)) return false; - /* Check statements. */ - for (itr = bsi_start (bb); !bsi_end_p (itr); bsi_next (&itr)) - if (!if_convertable_stmt_p (loop, bb, bsi_stmt (itr))) + for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr)) + if (!if_convertible_stmt_p (loop, bb, gsi_stmt (itr))) return false; - /* ??? Check data dependency for vectorizer. */ - /* What about phi nodes ? */ - for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) - if (!if_convertable_phi_p (loop, bb, phi)) + itr = gsi_start_phis (bb); + + if (!gsi_end_p (itr)) + FOR_EACH_EDGE (e, ei, bb->preds) + e->aux = NULL; + + for (; !gsi_end_p (itr); gsi_next (&itr)) + if (!if_convertible_phi_p (loop, bb, gsi_stmt (itr))) return false; - if (bb_with_exit_edge_p (bb)) - exit_bb_seen = true; + if (bb_with_exit_edge_p (loop, bb)) + exit_bb = bb; } - /* OK. Did not find any potential issues so go ahead in if-convert - this loop. Now there is no looking back. */ if (dump_file) fprintf (dump_file,"Applying if-conversion\n"); @@ -606,195 +669,196 @@ if_convertable_loop_p (struct loop *loop, bool for_vectorizer ATTRIBUTE_UNUSED) return true; } -/* Add condition COND into predicate list of basic block BB. */ +/* 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. */ static void -add_to_predicate_list (basic_block bb, tree new_cond) +clean_predicate_lists (struct loop *loop) { - tree cond = bb->aux; - - if (cond) - cond = fold (build (TRUTH_OR_EXPR, boolean_type_node, - unshare_expr (cond), new_cond)); - else - cond = new_cond; + basic_block *bb; + unsigned int i; + edge e; + edge_iterator ei; - bb->aux = cond; + bb = get_loop_body (loop); + for (i = 0; i < loop->num_nodes; i++) + { + bb[i]->aux = NULL; + FOR_EACH_EDGE (e, ei, bb[i]->succs) + e->aux = NULL; + } + free (bb); } -/* Add condition COND into BB's predicate list. PREV_COND is - existing condition. */ +/* 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. */ -static tree -add_to_dst_predicate_list (struct loop * loop, basic_block bb, - tree prev_cond, tree cond, - block_stmt_iterator *bsi) +static basic_block +find_phi_replacement_condition (struct loop *loop, + basic_block bb, tree *cond, + gimple_stmt_iterator *gsi) { - tree new_cond = NULL_TREE; + edge first_edge, second_edge; + tree tmp_cond; - if (!flow_bb_inside_loop_p (loop, bb)) - return NULL_TREE; + gcc_assert (EDGE_COUNT (bb->preds) == 2); + first_edge = EDGE_PRED (bb, 0); + second_edge = EDGE_PRED (bb, 1); - if (prev_cond == boolean_true_node || !prev_cond) - new_cond = unshare_expr (cond); - else - { - tree tmp_stmt; - /* new_cond == prev_cond AND cond */ - tree tmp = build (TRUTH_AND_EXPR, boolean_type_node, - unshare_expr (prev_cond), cond); - tmp_stmt = ifc_temp_var (boolean_type_node, tmp); - bsi_insert_before (bsi, tmp_stmt, BSI_SAME_STMT); - new_cond = TREE_OPERAND (tmp_stmt, 0); - } - add_to_predicate_list (bb, new_cond); - return new_cond; -} + /* Use condition based on following criteria: + 1) + S1: x = !c ? a : b; -/* During if-conversion aux field from basic block is used to hold predicate - list. Clean each basic block's predicate list for the given LOOP. */ + S2: x = c ? b : a; -static void -clean_predicate_lists (struct loop *loop) -{ -#ifdef ENABLE_CHECKING - gcc_assert (loop->num_nodes == 2 || loop->num_nodes == 1); -#endif - loop->header->aux = NULL; - loop->latch->aux = NULL; -} + S2 is preferred over S1. Make 'b' first_bb and use its condition. -/* 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. */ + 2) Do not make loop header first_bb. -static basic_block -find_phi_replacement_condition (basic_block bb, tree *cond, - block_stmt_iterator *bsi) -{ - edge e; - basic_block p1 = NULL; - basic_block p2 = NULL; - basic_block true_bb = NULL; - tree tmp_cond; - edge_iterator ei; + 3) + S1: x = !(c == d)? a : b; - FOR_EACH_EDGE (e, ei, bb->preds) + S21: t1 = c == d; + S22: x = t1 ? b : a; + + S3: x = (c == d) ? b : a; + + S3 is preferred over S1 and S2*, Make 'b' first_bb and use + its condition. + + 4) If pred B is dominated by pred A then use pred B's condition. + See PR23115. */ + + /* Select condition that is not TRUTH_NOT_EXPR. */ + tmp_cond = (tree) (first_edge->src)->aux; + gcc_assert (tmp_cond); + + if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR) { - if (p1 == NULL) - p1 = e->src; - else - { - gcc_assert (!p2); - p2 = e->src; - } + edge tmp_edge; + + tmp_edge = first_edge; + first_edge = second_edge; + second_edge = tmp_edge; } - /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr. */ - tmp_cond = p1->aux; - if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR) + /* Check if FIRST_BB is loop header or not and make sure that + FIRST_BB does not dominate SECOND_BB. */ + if (first_edge->src == loop->header + || dominated_by_p (CDI_DOMINATORS, + second_edge->src, first_edge->src)) { - *cond = p2->aux; - true_bb = p2; + *cond = (tree) (second_edge->src)->aux; + + /* If there is a condition on an incoming edge, add it to the + incoming bb predicate. */ + if (second_edge->aux) + *cond = build2 (TRUTH_AND_EXPR, boolean_type_node, + *cond, (tree) second_edge->aux); + + if (TREE_CODE (*cond) == TRUTH_NOT_EXPR) + *cond = invert_truthvalue (*cond); + else + /* Select non loop header bb. */ + first_edge = second_edge; } else { - *cond = p1->aux; - true_bb = p1; + *cond = (tree) (first_edge->src)->aux; + + /* If there is a condition on an incoming edge, add it to the + incoming bb predicate. */ + if (first_edge->aux) + *cond = build2 (TRUTH_AND_EXPR, boolean_type_node, + *cond, (tree) first_edge->aux); } - /* Create temp. for the condition. Vectorizer prefers to have gimple - value as condition. Various targets use different means to communicate - condition in vector compare operation. Using gimple value allows compiler - to emit vector compare and select RTL without exposing compare's result. */ + /* Gimplify the condition: the vectorizer prefers to have gimple + values as conditions. Various targets use different means to + communicate conditions in vector compare operations. Using a + gimple value allows the compiler to emit vector compare and + select RTL without exposing compare's result. */ + *cond = force_gimple_operand_gsi (gsi, unshare_expr (*cond), + false, NULL_TREE, + true, GSI_SAME_STMT); if (!is_gimple_reg (*cond) && !is_gimple_condexpr (*cond)) { - tree new_stmt; + gimple new_stmt; new_stmt = ifc_temp_var (TREE_TYPE (*cond), unshare_expr (*cond)); - bsi_insert_after (bsi, new_stmt, BSI_SAME_STMT); - bsi_next (bsi); - *cond = TREE_OPERAND (new_stmt, 0); + gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT); + *cond = gimple_assign_lhs (new_stmt); } gcc_assert (*cond); - return true_bb; + return first_edge->src; } +/* Replace PHI node with conditional modify expr using COND. This + routine does not handle PHI nodes with more than two arguments. -/* Replace PHI node with conditional modify expr using COND. - This routine does not handle PHI nodes with more than two arguments. For example, S1: A = PHI src == true_bb) + if (EDGE_PRED (bb, 1)->src == true_bb) { - arg_0 = PHI_ARG_DEF (phi, 1); - arg_1 = PHI_ARG_DEF (phi, 0); + arg_0 = gimple_phi_arg_def (phi, 1); + arg_1 = gimple_phi_arg_def (phi, 0); } else { - arg_0 = PHI_ARG_DEF (phi, 0); - arg_1 = PHI_ARG_DEF (phi, 1); + arg_0 = gimple_phi_arg_def (phi, 0); + arg_1 = gimple_phi_arg_def (phi, 1); } /* Build new RHS using selected condition and arguments. */ - rhs = build (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)), - unshare_expr (cond), unshare_expr (arg_0), - unshare_expr (arg_1)); - - /* Create new MODIFY expression using RHS. */ - new_stmt = build (MODIFY_EXPR, TREE_TYPE (PHI_RESULT (phi)), - unshare_expr (PHI_RESULT (phi)), rhs); - - /* Make new statement definition of the original phi result. */ - SSA_NAME_DEF_STMT (PHI_RESULT (phi)) = new_stmt; + rhs = build3 (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)), + unshare_expr (cond), unshare_expr (arg_0), + unshare_expr (arg_1)); - /* Set basic block and insert using iterator. */ - set_bb_for_stmt (new_stmt, bb); - - bsi_insert_after (bsi, new_stmt, BSI_SAME_STMT); - bsi_next (bsi); - - modify_stmt (new_stmt); + new_stmt = gimple_build_assign (unshare_expr (PHI_RESULT (phi)), rhs); + SSA_NAME_DEF_STMT (gimple_phi_result (phi)) = new_stmt; + gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT); + update_stmt (new_stmt); if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "new phi replacement stmt\n"); - print_generic_stmt (dump_file, new_stmt, TDF_SLIM); + print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM); } } -/* Process phi nodes for the given LOOP. Replace phi nodes with cond - modify expr. */ +/* Process phi nodes for the given LOOP. Replace phi nodes with + conditional modify expressions. */ static void process_phi_nodes (struct loop *loop) @@ -803,39 +867,38 @@ process_phi_nodes (struct loop *loop) unsigned int orig_loop_num_nodes = loop->num_nodes; unsigned int i; - /* Replace phi nodes with cond. modify expr. */ for (i = 1; i < orig_loop_num_nodes; i++) { - tree phi, cond; - block_stmt_iterator bsi; + gimple phi; + tree cond = NULL_TREE; + gimple_stmt_iterator gsi, phi_gsi; basic_block true_bb = NULL; bb = ifc_bbs[i]; if (bb == loop->header) continue; - phi = phi_nodes (bb); - bsi = bsi_start (bb); + phi_gsi = gsi_start_phis (bb); + gsi = gsi_after_labels (bb); - /* BB has two predecessors. Using predecessor's aux field, set + /* BB has two predecessors. Using predecessor's aux field, set appropriate condition for the PHI node replacement. */ - if (phi) - true_bb = find_phi_replacement_condition (bb, &cond, &bsi); + if (!gsi_end_p (phi_gsi)) + true_bb = find_phi_replacement_condition (loop, bb, &cond, &gsi); - while (phi) + while (!gsi_end_p (phi_gsi)) { - tree next = PHI_CHAIN (phi); - replace_phi_with_cond_modify_expr (phi, cond, true_bb, &bsi); + phi = gsi_stmt (phi_gsi); + replace_phi_with_cond_gimple_assign_stmt (phi, cond, true_bb, &gsi); release_phi_node (phi); - phi = next; + gsi_next (&phi_gsi); } - bb_ann (bb)->phi_nodes = NULL; + set_phi_nodes (bb, NULL); } - return; } -/* Combine all basic block from the given LOOP into one or two super - basic block. Replace PHI nodes with conditional modify expression. */ +/* Combine all the basic blocks from LOOP into one or two super basic + blocks. Replace PHI nodes with conditional modify expressions. */ static void combine_blocks (struct loop *loop) @@ -843,244 +906,191 @@ combine_blocks (struct loop *loop) basic_block bb, exit_bb, merge_target_bb; unsigned int orig_loop_num_nodes = loop->num_nodes; unsigned int i; + edge e; + edge_iterator ei; /* Process phi nodes to prepare blocks for merge. */ process_phi_nodes (loop); + /* Merge basic blocks: first remove all the edges in the loop, + except for those from the exit block. */ exit_bb = NULL; + for (i = 0; i < orig_loop_num_nodes; i++) + { + bb = ifc_bbs[i]; + if (bb_with_exit_edge_p (loop, bb)) + { + exit_bb = bb; + break; + } + } + gcc_assert (exit_bb != loop->latch); - /* Merge basic blocks */ - merge_target_bb = loop->header; for (i = 1; i < orig_loop_num_nodes; i++) { - edge e; - block_stmt_iterator bsi; - tree_stmt_iterator last; - bb = ifc_bbs[i]; - if (!exit_bb && bb_with_exit_edge_p (bb)) - exit_bb = bb; - - if (bb == exit_bb) + for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));) { - edge new_e; - edge_iterator ei; + if (e->src == exit_bb) + ei_next (&ei); + else + remove_edge (e); + } + } - /* Connect this node with loop header. */ - new_e = make_edge (ifc_bbs[0], bb, EDGE_FALLTHRU); - set_immediate_dominator (CDI_DOMINATORS, bb, ifc_bbs[0]); + if (exit_bb != NULL) + { + if (exit_bb != loop->header) + { + /* Connect this node to loop header. */ + make_edge (loop->header, exit_bb, EDGE_FALLTHRU); + set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header); + } - if (exit_bb != loop->latch) - { - /* Redirect non-exit edge to loop->latch. */ - FOR_EACH_EDGE (e, ei, bb->succs) - if (!(e->flags & EDGE_LOOP_EXIT)) - { - redirect_edge_and_branch (e, loop->latch); - set_immediate_dominator (CDI_DOMINATORS, loop->latch, bb); - } - } - continue; + /* Redirect non-exit edges to loop->latch. */ + FOR_EACH_EDGE (e, ei, exit_bb->succs) + { + if (!loop_exit_edge_p (loop, e)) + redirect_edge_and_branch (e, loop->latch); } + set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb); + } + else + { + /* If the loop does not have an exit, reconnect header and latch. */ + make_edge (loop->header, loop->latch, EDGE_FALLTHRU); + set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header); + } - if (bb == loop->latch && empty_block_p (bb)) - continue; + merge_target_bb = loop->header; + for (i = 1; i < orig_loop_num_nodes; i++) + { + gimple_stmt_iterator gsi; + gimple_stmt_iterator last; - /* It is time to remove this basic block. First remove edges. */ - while (EDGE_COUNT (bb->succs) > 0) - remove_edge (EDGE_SUCC (bb, 0)); - while (EDGE_COUNT (bb->preds) > 0) - remove_edge (EDGE_PRED (bb, 0)); + bb = ifc_bbs[i]; + + if (bb == exit_bb || bb == loop->latch) + continue; /* Remove labels and make stmts member of loop->header. */ - for (bsi = bsi_start (bb); !bsi_end_p (bsi); ) + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); ) { - if (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR) - bsi_remove (&bsi); + if (gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL) + gsi_remove (&gsi, true); else { - set_bb_for_stmt (bsi_stmt (bsi), merge_target_bb); - bsi_next (&bsi); + gimple_set_bb (gsi_stmt (gsi), merge_target_bb); + gsi_next (&gsi); } } /* Update stmt list. */ - last = tsi_last (merge_target_bb->stmt_list); - tsi_link_after (&last, bb->stmt_list, TSI_NEW_STMT); - bb->stmt_list = NULL; - - /* Update dominator info. */ - if (dom_computed[CDI_DOMINATORS]) - delete_from_dominance_info (CDI_DOMINATORS, bb); - if (dom_computed[CDI_POST_DOMINATORS]) - delete_from_dominance_info (CDI_POST_DOMINATORS, bb); - - /* Remove basic block. */ - if (bb == loop->latch) - loop->latch = merge_target_bb; - remove_bb_from_loops (bb); - expunge_block (bb); - } + last = gsi_last_bb (merge_target_bb); + gsi_insert_seq_after (&last, bb_seq (bb), GSI_NEW_STMT); + set_bb_seq (bb, NULL); - /* 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 - && loop->header != loop->latch - && exit_bb != loop->latch - && empty_block_p (loop->latch)) - { - if (can_merge_blocks_p (loop->header, exit_bb)) - { - remove_bb_from_loops (exit_bb); - merge_blocks (loop->header, exit_bb); - } + delete_basic_block (bb); } -} -/* Make new temp variable of type TYPE. Add MODIFY_EXPR to assign EXP - to the new variable. */ + /* 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. -static tree -ifc_temp_var (tree type, tree exp) -{ - const char *name = "_ifc_"; - tree var, stmt, new_name; - - if (is_gimple_reg (exp)) - return exp; - - /* Create new temporary variable. */ - var = create_tmp_var (type, name); - add_referenced_tmp_var (var); - - /* Build new statement to assign EXP to new variable. */ - stmt = build (MODIFY_EXPR, type, var, exp); - - /* Get SSA name for the new variable and set make new statement - its definition statment. */ - new_name = make_ssa_name (var, stmt); - TREE_OPERAND (stmt, 0) = new_name; - SSA_NAME_DEF_STMT (new_name) = stmt; - - return stmt; + FIXME: Call cleanup_tree_cfg. */ + if (exit_bb + && exit_bb != loop->header + && can_merge_blocks_p (loop->header, exit_bb)) + merge_blocks (loop->header, exit_bb); } - -/* Return TRUE iff, all pred blocks of BB are visited. - Bitmap VISITED keeps history of visited blocks. */ +/* Main entry point: return true when LOOP is if-converted, otherwise + the loop remains unchanged. */ static bool -pred_blocks_visited_p (basic_block bb, bitmap *visited) -{ - 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, BFS order with one - additional constraint. Select block in BFS block, if all - pred are already selected. */ - -static basic_block * -get_loop_body_in_if_conv_order (const struct loop *loop) +tree_if_conversion (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 = xcalloc (loop->num_nodes, sizeof (basic_block)); - visited = BITMAP_XMALLOC (); + gimple_stmt_iterator itr; + unsigned int i; - blocks_in_bfs_order = get_loop_body_in_bfs_order (loop); + ifc_bbs = NULL; - index = 0; - while (index < loop->num_nodes) + /* If-conversion is not appropriate for all loops. First, check if + the loop is if-convertible. */ + if (!if_convertible_loop_p (loop)) { - bb = blocks_in_bfs_order [index]; - - if (bb->flags & BB_IRREDUCIBLE_LOOP) + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file,"-------------------------\n"); + if (ifc_bbs) { - free (blocks_in_bfs_order); - BITMAP_XFREE (visited); - free (blocks); - return NULL; + free (ifc_bbs); + ifc_bbs = NULL; } - if (!bitmap_bit_p (visited, bb->index)) + 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 (pred_blocks_visited_p (bb, &visited) - || bb == loop->header) - { - /* This block is now visited. */ - bitmap_set_bit (visited, bb->index); - blocks[visited_count++] = bb; - } + gimple t = gsi_stmt (itr); + cond = tree_if_convert_stmt (loop, t, cond, &itr); + if (!gsi_end_p (itr)) + gsi_next (&itr); } - index++; - if (index == loop->num_nodes - && visited_count != loop->num_nodes) + + /* If current bb has only one successor, then consider it as an + unconditional goto. */ + if (single_succ_p (bb)) { - /* Not done yet. */ - index = 0; + 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; + + add_to_predicate_list (bb_n, cond); } } - free (blocks_in_bfs_order); - BITMAP_XFREE (visited); - return blocks; -} -/* Return true if one of the basic block BB edge is loop exit. */ - -static bool -bb_with_exit_edge_p (basic_block bb) -{ - edge e; - edge_iterator ei; - bool exit_edge_found = false; + /* Now, all statements are if-converted and basic blocks are + annotated appropriately. Combine all the basic blocks into one + huge basic block. */ + combine_blocks (loop); - FOR_EACH_EDGE (e, ei, bb->succs) - if (e->flags & EDGE_LOOP_EXIT) - { - exit_edge_found = true; - break; - } + /* clean up */ + clean_predicate_lists (loop); + free (ifc_bbs); + ifc_bbs = NULL; - return exit_edge_found; + return true; } /* Tree if-conversion pass management. */ -static void +static unsigned int main_tree_if_conversion (void) { - unsigned i, loop_num; + loop_iterator li; struct loop *loop; - if (!current_loops) - return; + if (number_of_loops () <= 1) + return 0; - loop_num = current_loops->num; - for (i = 0; i < loop_num; i++) - { - loop = current_loops->parray[i]; - if (!loop) - continue; - - tree_if_conversion (loop, true); - } + FOR_EACH_LOOP (li, loop, 0) + tree_if_conversion (loop); + return 0; } static bool @@ -1089,22 +1099,22 @@ gate_tree_if_conversion (void) return flag_tree_vectorize != 0; } -struct tree_opt_pass pass_if_conversion = +struct gimple_opt_pass pass_if_conversion = { - "ifcvt", /* name */ - gate_tree_if_conversion, /* gate */ - main_tree_if_conversion, /* execute */ - NULL, /* sub */ - NULL, /* next */ - 0, /* static_pass_number */ - 0, /* tv_id */ - PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ - 0, /* properties_provided */ - 0, /* properties_destroyed */ - TODO_dump_func, /* todo_flags_start */ - TODO_dump_func - | TODO_verify_ssa - | TODO_verify_stmts - | TODO_verify_flow, /* todo_flags_finish */ - 0 /* letter */ + { + GIMPLE_PASS, + "ifcvt", /* name */ + gate_tree_if_conversion, /* gate */ + main_tree_if_conversion, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + TV_NONE, /* tv_id */ + PROP_cfg | PROP_ssa, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_dump_func | TODO_verify_stmts | TODO_verify_flow + /* todo_flags_finish */ + } };