X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Ftree-if-conv.c;h=2a6102026efd5bd3f0d9834c2a839893fb8d25cd;hb=a39ac8645754aaee468aa8add01b601723955ca0;hp=ce66e2a7bbce2956f45db26a446847c9d1136a40;hpb=46d1d560e93eb52b85884a6c478d08933b2b010e;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/tree-if-conv.c b/gcc/tree-if-conv.c index ce66e2a7bbc..2a6102026ef 100644 --- a/gcc/tree-if-conv.c +++ b/gcc/tree-if-conv.c @@ -16,8 +16,8 @@ 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. */ +Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA +02110-1301, USA. */ /* This pass implements tree level if-conversion transformation of loops. Initial goal is to help vectorizer vectorize loops with conditions. @@ -84,7 +84,6 @@ 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" @@ -103,7 +102,7 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA #include "target.h" /* local function prototypes */ -static void main_tree_if_conversion (void); +static unsigned int 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, @@ -111,13 +110,14 @@ static void tree_if_convert_cond_expr (struct loop *, tree, tree, static bool if_convertible_phi_p (struct loop *, basic_block, tree); static bool if_convertible_modify_expr_p (struct loop *, basic_block, tree); static bool if_convertible_stmt_p (struct loop *, basic_block, tree); -static bool if_convertible_bb_p (struct loop *, basic_block, bool); +static bool if_convertible_bb_p (struct loop *, basic_block, basic_block); static bool if_convertible_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 *, +static basic_block find_phi_replacement_condition (struct loop *loop, + basic_block, tree *, block_stmt_iterator *); static void replace_phi_with_cond_modify_expr (tree, tree, basic_block, block_stmt_iterator *); @@ -160,7 +160,6 @@ tree_if_conversion (struct loop *loop, bool for_vectorizer) ifc_bbs = NULL; } free_dominance_info (CDI_POST_DOMINATORS); - free_df (); return false; } @@ -187,9 +186,9 @@ tree_if_conversion (struct loop *loop, bool for_vectorizer) /* If current bb has only one successor, then consider it as an unconditional goto. */ - if (EDGE_COUNT (bb->succs) == 1) + if (single_succ_p (bb)) { - basic_block bb_n = EDGE_SUCC (bb, 0)->dest; + basic_block bb_n = single_succ (bb); if (cond != NULL_TREE) add_to_predicate_list (bb_n, cond); cond = NULL_TREE; @@ -205,7 +204,6 @@ tree_if_conversion (struct loop *loop, bool for_vectorizer) clean_predicate_lists (loop); free (ifc_bbs); ifc_bbs = NULL; - free_df (); return true; } @@ -242,13 +240,6 @@ tree_if_convert_stmt (struct loop * loop, tree t, tree cond, program. */ break; - case GOTO_EXPR: - /* Unconditional goto */ - add_to_predicate_list (bb_for_stmt (TREE_OPERAND (t, 1)), cond); - bsi_remove (bsi); - cond = NULL_TREE; - break; - case COND_EXPR: /* Update destination blocks' predicate list and remove this condition expression. */ @@ -271,39 +262,21 @@ static void tree_if_convert_cond_expr (struct loop *loop, tree stmt, tree cond, block_stmt_iterator *bsi) { - tree c, c2, new_cond; + tree c, c2; edge true_edge, false_edge; - new_cond = NULL_TREE; gcc_assert (TREE_CODE (stmt) == COND_EXPR); c = COND_EXPR_COND (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); - } - extract_true_false_edges_from_block (bb_for_stmt (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 (!is_gimple_reg(c) && 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); - } + add_to_dst_predicate_list (loop, true_edge->dest, cond, + unshare_expr (c), bsi); /* If 'c' is false then FALSE_EDGE is taken. */ c2 = invert_truthvalue (unshare_expr (c)); @@ -314,7 +287,7 @@ tree_if_convert_cond_expr (struct loop *loop, tree stmt, tree cond, using new condition. */ if (!bb_with_exit_edge_p (loop, bb_for_stmt (stmt))) { - bsi_remove (bsi); + bsi_remove (bsi, true); cond = NULL_TREE; } return; @@ -344,13 +317,11 @@ if_convertible_phi_p (struct loop *loop, basic_block bb, tree phi) if (!is_gimple_reg (SSA_NAME_VAR (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; + FOR_EACH_IMM_USE_FAST (use_p, imm_iter, PHI_RESULT (phi)) { - tree use = immediate_use (df, j); - if (TREE_CODE (use) == PHI_NODE) + if (TREE_CODE (USE_STMT (use_p)) == PHI_NODE) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "Difficult to handle this virtual phi.\n"); @@ -422,7 +393,7 @@ if_convertible_modify_expr_p (struct loop *loop, basic_block bb, tree m_expr) /* Return true, iff STMT is if-convertible. Statement is if-convertible if, - It is if-convertible MODIFY_EXPR - - IT is LABEL_EXPR, GOTO_EXPR or COND_EXPR. + - IT is LABEL_EXPR or COND_EXPR. STMT is inside block BB, which is inside loop LOOP. */ static bool @@ -439,7 +410,6 @@ if_convertible_stmt_p (struct loop *loop, basic_block bb, tree stmt) return false; break; - case GOTO_EXPR: case COND_EXPR: break; @@ -467,7 +437,7 @@ if_convertible_stmt_p (struct loop *loop, basic_block bb, tree stmt) BB is inside loop LOOP. */ static bool -if_convertible_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 +445,7 @@ if_convertible_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 +459,14 @@ if_convertible_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. */ @@ -524,7 +502,7 @@ if_convertible_loop_p (struct loop *loop, bool for_vectorizer ATTRIBUTE_UNUSED) 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) @@ -560,8 +538,6 @@ if_convertible_loop_p (struct loop *loop, bool for_vectorizer ATTRIBUTE_UNUSED) return false; } - compute_immediate_uses (TDFA_USE_OPS|TDFA_USE_VOPS, NULL); - calculate_dominance_info (CDI_DOMINATORS); calculate_dominance_info (CDI_POST_DOMINATORS); @@ -579,7 +555,7 @@ if_convertible_loop_p (struct loop *loop, bool for_vectorizer ATTRIBUTE_UNUSED) { bb = ifc_bbs[i]; - if (!if_convertible_bb_p (loop, bb, exit_bb_seen)) + if (!if_convertible_bb_p (loop, bb, exit_bb)) return false; /* Check statements. */ @@ -594,7 +570,7 @@ if_convertible_loop_p (struct loop *loop, bool for_vectorizer ATTRIBUTE_UNUSED) return false; if (bb_with_exit_edge_p (loop, bb)) - exit_bb_seen = true; + exit_bb = bb; } /* OK. Did not find any potential issues so go ahead in if-convert @@ -614,8 +590,8 @@ add_to_predicate_list (basic_block bb, tree new_cond) tree cond = bb->aux; if (cond) - cond = fold (build (TRUTH_OR_EXPR, boolean_type_node, - unshare_expr (cond), new_cond)); + cond = fold_build2 (TRUTH_OR_EXPR, boolean_type_node, + unshare_expr (cond), new_cond); else cond = new_cond; @@ -654,8 +630,8 @@ add_to_dst_predicate_list (struct loop * loop, basic_block bb, bsi_insert_before (bsi, tmp_stmts2, BSI_SAME_STMT); /* new_cond == prev_cond AND cond */ - tmp = build (TRUTH_AND_EXPR, boolean_type_node, - unshare_expr (prev_cond), cond); + tmp = build2 (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); @@ -684,39 +660,73 @@ clean_predicate_lists (struct loop *loop) whose phi arguments are selected when cond is true. */ static basic_block -find_phi_replacement_condition (basic_block bb, tree *cond, +find_phi_replacement_condition (struct loop *loop, + basic_block bb, tree *cond, block_stmt_iterator *bsi) { - edge e; - basic_block p1 = NULL; - basic_block p2 = NULL; - basic_block true_bb = NULL; + basic_block first_bb = NULL; + basic_block second_bb = NULL; tree tmp_cond; - edge_iterator ei; - FOR_EACH_EDGE (e, ei, bb->preds) - { - if (p1 == NULL) - p1 = e->src; - else - { - gcc_assert (!p2); - p2 = e->src; - } - } + gcc_assert (EDGE_COUNT (bb->preds) == 2); + first_bb = (EDGE_PRED (bb, 0))->src; + second_bb = (EDGE_PRED (bb, 1))->src; - /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr. */ - tmp_cond = p1->aux; + /* Use condition based on following criteria: + 1) + S1: x = !c ? a : b; + + S2: x = c ? b : a; + + S2 is preferred over S1. Make 'b' first_bb and use its condition. + + 2) Do not make loop header first_bb. + + 3) + S1: x = !(c == d)? a : b; + + 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 = first_bb->aux; if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR) { - *cond = p2->aux; - true_bb = p2; + basic_block tmp_bb; + tmp_bb = first_bb; + first_bb = second_bb; + second_bb = tmp_bb; } - else + + /* Check if FIRST_BB is loop header or not and make sure that + FIRST_BB does not dominate SECOND_BB. */ + if (first_bb == loop->header + || dominated_by_p (CDI_DOMINATORS, second_bb, first_bb)) { - *cond = p1->aux; - true_bb = p1; + tmp_cond = second_bb->aux; + if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR) + { + /* Select non loop header condition but do not switch basic blocks. */ + *cond = invert_truthvalue (unshare_expr (tmp_cond)); + } + else + { + /* Select non loop header condition. */ + first_bb = second_bb; + *cond = first_bb->aux; + } } + else + /* FIRST_BB is not loop header */ + *cond = first_bb->aux; /* Create temp. for the condition. Vectorizer prefers to have gimple value as condition. Various targets use different means to communicate @@ -727,14 +737,13 @@ find_phi_replacement_condition (basic_block bb, tree *cond, tree 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); + bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT); *cond = TREE_OPERAND (new_stmt, 0); } gcc_assert (*cond); - return true_bb; + return first_bb; } @@ -782,24 +791,20 @@ replace_phi_with_cond_modify_expr (tree phi, tree cond, basic_block true_bb, } /* 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)); + rhs = build3 (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); + new_stmt = build2 (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; - /* 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); + /* Insert using iterator. */ + bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT); + update_stmt (new_stmt); if (dump_file && (dump_flags & TDF_DETAILS)) { @@ -835,7 +840,7 @@ process_phi_nodes (struct loop *loop) /* 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); + true_bb = find_phi_replacement_condition (loop, bb, &cond, &bsi); while (phi) { @@ -844,7 +849,7 @@ process_phi_nodes (struct loop *loop) release_phi_node (phi); phi = next; } - bb_ann (bb)->phi_nodes = NULL; + bb->phi_nodes = NULL; } return; } @@ -858,7 +863,11 @@ 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; + unsigned int n_exits; + edge *exits; + exits = get_loop_exit_edges (loop, &n_exits); + free (exits); /* Process phi nodes to prepare blocks for merge. */ process_phi_nodes (loop); @@ -879,11 +888,10 @@ combine_blocks (struct loop *loop) if (bb == exit_bb) { - edge new_e; edge_iterator ei; /* Connect this node with loop header. */ - new_e = make_edge (ifc_bbs[0], bb, EDGE_FALLTHRU); + make_edge (ifc_bbs[0], bb, EDGE_FALLTHRU); set_immediate_dominator (CDI_DOMINATORS, bb, ifc_bbs[0]); if (exit_bb != loop->latch) @@ -909,14 +917,14 @@ combine_blocks (struct loop *loop) remove_edge (EDGE_PRED (bb, 0)); /* This is loop latch and loop does not have exit then do not - delete this basic block. Just remove its PREDS and reconnect - loop->header and loop->latch blocks. */ - if (bb == loop->latch && loop->num_exits == 0) - { - make_edge (loop->header, loop->latch, EDGE_FALLTHRU); - set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header); + delete this basic block. Just remove its PREDS and reconnect + loop->header and loop->latch blocks. */ + if (bb == loop->latch && n_exits == 0) + { + make_edge (loop->header, loop->latch, EDGE_FALLTHRU); + set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header); continue; - } + } while (EDGE_COUNT (bb->succs) > 0) remove_edge (EDGE_SUCC (bb, 0)); @@ -925,7 +933,7 @@ combine_blocks (struct loop *loop) for (bsi = bsi_start (bb); !bsi_end_p (bsi); ) { if (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR) - bsi_remove (&bsi); + bsi_remove (&bsi, true); else { set_bb_for_stmt (bsi_stmt (bsi), merge_target_bb); @@ -984,7 +992,7 @@ ifc_temp_var (tree type, tree exp) add_referenced_tmp_var (var); /* Build new statement to assign EXP to new variable. */ - stmt = build (MODIFY_EXPR, type, var, exp); + stmt = build2 (MODIFY_EXPR, type, var, exp); /* Get SSA name for the new variable and set make new statement its definition statement. */ @@ -1029,7 +1037,7 @@ get_loop_body_in_if_conv_order (const struct loop *loop) gcc_assert (loop->num_nodes); gcc_assert (loop->latch != EXIT_BLOCK_PTR); - blocks = xcalloc (loop->num_nodes, sizeof (basic_block)); + blocks = XCNEWVEC (basic_block, loop->num_nodes); visited = BITMAP_ALLOC (NULL); blocks_in_bfs_order = get_loop_body_in_bfs_order (loop); @@ -1090,14 +1098,14 @@ bb_with_exit_edge_p (struct loop *loop, basic_block bb) /* Tree if-conversion pass management. */ -static void +static unsigned int main_tree_if_conversion (void) { unsigned i, loop_num; struct loop *loop; if (!current_loops) - return; + return 0; loop_num = current_loops->num; for (i = 0; i < loop_num; i++) @@ -1108,7 +1116,7 @@ main_tree_if_conversion (void) tree_if_conversion (loop, true); } - + return 0; } static bool @@ -1119,20 +1127,18 @@ gate_tree_if_conversion (void) struct tree_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 */ + "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 */ + 0, /* todo_flags_start */ + TODO_dump_func | TODO_verify_loops | TODO_verify_stmts | TODO_verify_flow, + /* todo_flags_finish */ + 0 /* letter */ };