X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Ftree-if-conv.c;h=cdbbe5bd353860ba4de636148ff81cf333ef4a92;hb=6620d7d7c5f2fe5df0df2b85e143746f76fdd4cf;hp=c1b05328fa61e33840469248a4c99827025a5eec;hpb=2f8eb9091b18ca1a7b6868980a41678f6d93b9ed;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/tree-if-conv.c b/gcc/tree-if-conv.c index c1b05328fa6..cdbbe5bd353 100644 --- a/gcc/tree-if-conv.c +++ b/gcc/tree-if-conv.c @@ -1,5 +1,5 @@ /* If-conversion for vectorizer. - Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009 + Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011 Free Software Foundation, Inc. Contributed by Devang Patel @@ -19,8 +19,9 @@ You should have received a copy of the GNU General Public License 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: @@ -87,10 +88,9 @@ along with GCC; see the file COPYING3. If not see #include "tree.h" #include "flags.h" #include "timevar.h" -#include "varray.h" -#include "rtl.h" #include "basic-block.h" -#include "diagnostic.h" +#include "tree-pretty-print.h" +#include "gimple-pretty-print.h" #include "tree-flow.h" #include "tree-dump.h" #include "cfgloop.h" @@ -98,214 +98,314 @@ along with GCC; see the file COPYING3. If not see #include "tree-data-ref.h" #include "tree-scalar-evolution.h" #include "tree-pass.h" -#include "target.h" - - -/* local function prototypes */ -static unsigned int main_tree_if_conversion (void); -static tree tree_if_convert_stmt (struct loop *loop, gimple, tree, - gimple_stmt_iterator *); -static void tree_if_convert_cond_stmt (struct loop *, gimple, tree, - gimple_stmt_iterator *); -static bool if_convertible_phi_p (struct loop *, basic_block, gimple); -static bool if_convertible_gimple_assign_stmt_p (struct loop *, basic_block, - gimple); -static bool if_convertible_stmt_p (struct loop *, basic_block, gimple); -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, edge, - tree, tree, - gimple_stmt_iterator *); -static void clean_predicate_lists (struct loop *loop); -static basic_block find_phi_replacement_condition (struct loop *loop, - basic_block, tree *, - gimple_stmt_iterator *); -static void replace_phi_with_cond_gimple_assign_stmt (gimple, tree, - basic_block, - gimple_stmt_iterator *); -static void process_phi_nodes (struct loop *); -static void combine_blocks (struct loop *); -static gimple 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 (struct loop *, basic_block); +#include "dbgcnt.h" /* 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). */ +/* 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 { -static bool -tree_if_conversion (struct loop *loop, bool for_vectorizer) + /* 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) { - basic_block bb; - gimple_stmt_iterator itr; - unsigned int i; + return bb->aux != NULL; +} - ifc_bbs = NULL; +/* Returns the gimplified predicate for basic block BB. */ + +static inline tree +bb_predicate (basic_block bb) +{ + return ((bb_predicate_p) bb->aux)->predicate; +} - /* 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)) +/* Sets the gimplified predicate COND for basic block BB. */ + +static inline void +set_bb_predicate (basic_block bb, tree cond) +{ + gcc_assert ((TREE_CODE (cond) == TRUTH_NOT_EXPR + && is_gimple_condexpr (TREE_OPERAND (cond, 0))) + || is_gimple_condexpr (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, boolean_true_node); +} + +/* 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) { - 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); - return false; + gimple_stmt_iterator i; + + for (i = gsi_start (stmts); !gsi_end_p (i); gsi_next (&i)) + free_stmt_operands (gsi_stmt (i)); } - /* Do actual work now. */ - for (i = 0; i < loop->num_nodes; i++) - { - tree cond; + free (bb->aux); + bb->aux = NULL; +} + +/* Free the predicate of BB and reinitialize it with the true + predicate. */ + +static inline void +reset_bb_predicate (basic_block bb) +{ + free_bb_predicate (bb); + init_bb_predicate (bb); +} + +/* Returns a new SSA_NAME of type TYPE that is assigned the value of + the expression EXPR. Inserts the statement created for this + computation before GSI and leaves the iterator GSI at the same + statement. */ + +static tree +ifc_temp_var (tree type, tree expr, gimple_stmt_iterator *gsi) +{ + const char *name = "_ifc_"; + tree var, new_name; + gimple stmt; + + /* Create new temporary variable. */ + var = create_tmp_var (type, name); + add_referenced_var (var); - bb = ifc_bbs [i]; + /* Build new statement to assign EXPR to new variable. */ + stmt = gimple_build_assign (var, expr); - /* Update condition using predicate list. */ - cond = (tree) 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 = gsi_start_bb (bb); !gsi_end_p (itr); /* empty */) + gsi_insert_before (gsi, stmt, GSI_SAME_STMT); + return gimple_assign_lhs (stmt); +} + +/* Return true when COND is a true predicate. */ + +static inline bool +is_true_predicate (tree cond) +{ + return (cond == NULL_TREE + || cond == boolean_true_node + || integer_onep (cond)); +} + +/* Returns true when BB has a predicate that is not trivial: true or + NULL_TREE. */ + +static inline bool +is_predicated (basic_block bb) +{ + return !is_true_predicate (bb_predicate (bb)); +} + +/* Parses the predicate COND and returns its comparison code and + operands OP0 and OP1. */ + +static enum tree_code +parse_predicate (tree cond, tree *op0, tree *op1) +{ + gimple s; + + if (TREE_CODE (cond) == SSA_NAME + && is_gimple_assign (s = SSA_NAME_DEF_STMT (cond))) + { + if (TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison) { - gimple t = gsi_stmt (itr); - cond = tree_if_convert_stmt (loop, t, cond, &itr); - if (!gsi_end_p (itr)) - gsi_next (&itr); + *op0 = gimple_assign_rhs1 (s); + *op1 = gimple_assign_rhs2 (s); + return gimple_assign_rhs_code (s); } - /* If current bb has only one successor, then consider it as an - unconditional goto. */ - if (single_succ_p (bb)) + else if (gimple_assign_rhs_code (s) == TRUTH_NOT_EXPR) { - basic_block bb_n = single_succ (bb); - - /* 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; + tree op = gimple_assign_rhs1 (s); + tree type = TREE_TYPE (op); + enum tree_code code = parse_predicate (op, op0, op1); - add_to_predicate_list (bb_n, cond); + return code == ERROR_MARK ? ERROR_MARK + : invert_tree_comparison (code, HONOR_NANS (TYPE_MODE (type))); } - } - /* Now, all statements are if-converted and basic blocks are - annotated appropriately. Combine all basic block into one huge - basic block. */ - combine_blocks (loop); + return ERROR_MARK; + } - /* clean up */ - clean_predicate_lists (loop); - free (ifc_bbs); - ifc_bbs = NULL; + if (TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison) + { + *op0 = TREE_OPERAND (cond, 0); + *op1 = TREE_OPERAND (cond, 1); + return TREE_CODE (cond); + } - return true; + return ERROR_MARK; } -/* if-convert stmt T which is part of LOOP. - 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. */ +/* Returns the fold of predicate C1 OR C2 at location LOC. */ static tree -tree_if_convert_stmt (struct loop * loop, gimple t, tree cond, - gimple_stmt_iterator *gsi) +fold_or_predicates (location_t loc, tree c1, tree c2) { - if (dump_file && (dump_flags & TDF_DETAILS)) + tree op1a, op1b, op2a, op2b; + enum tree_code code1 = parse_predicate (c1, &op1a, &op1b); + enum tree_code code2 = parse_predicate (c2, &op2a, &op2b); + + if (code1 != ERROR_MARK && code2 != ERROR_MARK) { - fprintf (dump_file, "------if-convert stmt\n"); - print_gimple_stmt (dump_file, t, 0, TDF_SLIM); - print_generic_stmt (dump_file, cond, TDF_SLIM); + tree t = maybe_fold_or_comparisons (code1, op1a, op1b, + code2, op2a, op2b); + if (t) + return t; } - switch (gimple_code (t)) - { - /* Labels are harmless here. */ - case GIMPLE_LABEL: - break; + return fold_build2_loc (loc, TRUTH_OR_EXPR, boolean_type_node, c1, c2); +} - 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 validity the program. */ - break; +/* Add condition NC to the predicate list of basic block BB. */ - 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; +static inline void +add_to_predicate_list (basic_block bb, tree nc) +{ + tree bc, *tp; - default: - gcc_unreachable (); + if (is_true_predicate (nc)) + return; + + if (!is_predicated (bb)) + bc = nc; + else + { + bc = bb_predicate (bb); + bc = fold_or_predicates (EXPR_LOCATION (bc), nc, bc); + if (is_true_predicate (bc)) + { + reset_bb_predicate (bb); + return; + } } - return cond; + + /* Allow a TRUTH_NOT_EXPR around the main predicate. */ + if (TREE_CODE (bc) == TRUTH_NOT_EXPR) + tp = &TREE_OPERAND (bc, 0); + else + tp = &bc; + if (!is_gimple_condexpr (*tp)) + { + gimple_seq stmts; + *tp = force_gimple_operand_1 (*tp, &stmts, is_gimple_condexpr, NULL_TREE); + add_bb_predicate_gimplified_stmts (bb, stmts); + } + set_bb_predicate (bb, bc); } -/* 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. */ +/* Add the condition COND to the previous condition PREV_COND, and add + this to the predicate list of the destination of edge E. LOOP is + the loop to be if-converted. */ static void -tree_if_convert_cond_stmt (struct loop *loop, gimple stmt, tree cond, - gimple_stmt_iterator *gsi) +add_to_dst_predicate_list (struct loop *loop, edge e, + tree prev_cond, tree cond) { - tree c, c2; - edge true_edge, false_edge; - - gcc_assert (gimple_code (stmt) == GIMPLE_COND); + if (!flow_bb_inside_loop_p (loop, e->dest)) + return; - c = fold_build2 (gimple_cond_code (stmt), boolean_type_node, - gimple_cond_lhs (stmt), gimple_cond_rhs (stmt)); + if (!is_true_predicate (prev_cond)) + cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, + prev_cond, cond); - extract_true_false_edges_from_block (gimple_bb (stmt), - &true_edge, &false_edge); + add_to_predicate_list (e->dest, cond); +} - /* Add new condition into destination's predicate list. */ +/* Return true if one of the successor edges of BB exits LOOP. */ - /* If C is true then TRUE_EDGE is taken. */ - add_to_dst_predicate_list (loop, true_edge, cond, c, gsi); +static bool +bb_with_exit_edge_p (struct loop *loop, basic_block bb) +{ + edge e; + edge_iterator ei; - /* If 'c' is false then FALSE_EDGE is taken. */ - c2 = invert_truthvalue (unshare_expr (c)); - add_to_dst_predicate_list (loop, false_edge, cond, c2, gsi); + FOR_EACH_EDGE (e, ei, bb->succs) + if (loop_exit_edge_p (loop, e)) + return true; - /* 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 false; } -/* Return true, iff PHI is if-convertible. 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-convertible - - if it has more than 2 arguments. - - Virtual PHI is immediately used in another PHI node. - - Virtual PHI on BB other than header. */ + + PHI is not if-convertible if: + - it has more than 2 arguments. + + When the flag_tree_loop_if_convert_stores is not set, PHI is not + if-convertible if: + - a virtual PHI is immediately used in another PHI node, + - there is a virtual PHI in a BB other than the loop->header. */ static bool if_convertible_phi_p (struct loop *loop, basic_block bb, gimple phi) @@ -323,6 +423,12 @@ if_convertible_phi_p (struct loop *loop, basic_block bb, gimple phi) return false; } + if (flag_tree_loop_if_convert_stores) + return true; + + /* When the flag_tree_loop_if_convert_stores is not set, check + that there are no memory writes in the branches of the loop to be + if-converted. */ if (!is_gimple_reg (SSA_NAME_VAR (gimple_phi_result (phi)))) { imm_use_iterator imm_iter; @@ -331,9 +437,10 @@ if_convertible_phi_p (struct loop *loop, basic_block bb, gimple phi) if (bb != loop->header) { if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "Virtual phi not on loop header.\n"); + 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) @@ -348,29 +455,212 @@ if_convertible_phi_p (struct loop *loop, basic_block bb, gimple phi) return true; } -/* Return true, if STMT is if-convertible. - GIMPLE_ASSIGN statement is not if-convertible if, - - It is not movable. - - It could trap. - - LHS is not var decl. - GIMPLE_ASSIGN is part of block BB, which is inside loop LOOP. */ +/* Records the status of a data reference. This struct is attached to + each DR->aux field. */ + +struct ifc_dr { + /* -1 when not initialized, 0 when false, 1 when true. */ + int written_at_least_once; + + /* -1 when not initialized, 0 when false, 1 when true. */ + int rw_unconditionally; +}; + +#define IFC_DR(DR) ((struct ifc_dr *) (DR)->aux) +#define DR_WRITTEN_AT_LEAST_ONCE(DR) (IFC_DR (DR)->written_at_least_once) +#define DR_RW_UNCONDITIONALLY(DR) (IFC_DR (DR)->rw_unconditionally) + +/* Returns true when the memory references of STMT are read or written + unconditionally. In other words, this function returns true when + for every data reference A in STMT there exist other accesses to + a data reference with the same base with predicates that add up (OR-up) to + the true predicate: this ensures that the data reference A is touched + (read or written) on every iteration of the if-converted loop. */ + +static bool +memrefs_read_or_written_unconditionally (gimple stmt, + VEC (data_reference_p, heap) *drs) +{ + int i, j; + data_reference_p a, b; + tree ca = bb_predicate (gimple_bb (stmt)); + + for (i = 0; VEC_iterate (data_reference_p, drs, i, a); i++) + if (DR_STMT (a) == stmt) + { + bool found = false; + int x = DR_RW_UNCONDITIONALLY (a); + + if (x == 0) + return false; + + if (x == 1) + continue; + + for (j = 0; VEC_iterate (data_reference_p, drs, j, b); j++) + { + tree ref_base_a = DR_REF (a); + tree ref_base_b = DR_REF (b); + + if (DR_STMT (b) == stmt) + continue; + + while (TREE_CODE (ref_base_a) == COMPONENT_REF + || TREE_CODE (ref_base_a) == IMAGPART_EXPR + || TREE_CODE (ref_base_a) == REALPART_EXPR) + ref_base_a = TREE_OPERAND (ref_base_a, 0); + + while (TREE_CODE (ref_base_b) == COMPONENT_REF + || TREE_CODE (ref_base_b) == IMAGPART_EXPR + || TREE_CODE (ref_base_b) == REALPART_EXPR) + ref_base_b = TREE_OPERAND (ref_base_b, 0); + + if (!operand_equal_p (ref_base_a, ref_base_b, 0)) + { + tree cb = bb_predicate (gimple_bb (DR_STMT (b))); + + if (DR_RW_UNCONDITIONALLY (b) == 1 + || is_true_predicate (cb) + || is_true_predicate (ca + = fold_or_predicates (EXPR_LOCATION (cb), ca, cb))) + { + DR_RW_UNCONDITIONALLY (a) = 1; + DR_RW_UNCONDITIONALLY (b) = 1; + found = true; + break; + } + } + } + + if (!found) + { + DR_RW_UNCONDITIONALLY (a) = 0; + return false; + } + } + + return true; +} + +/* Returns true when the memory references of STMT are unconditionally + written. In other words, this function returns true when for every + data reference A written in STMT, there exist other writes to the + same data reference with predicates that add up (OR-up) to the true + predicate: this ensures that the data reference A is written on + every iteration of the if-converted loop. */ + +static bool +write_memrefs_written_at_least_once (gimple stmt, + VEC (data_reference_p, heap) *drs) +{ + int i, j; + data_reference_p a, b; + tree ca = bb_predicate (gimple_bb (stmt)); + + for (i = 0; VEC_iterate (data_reference_p, drs, i, a); i++) + if (DR_STMT (a) == stmt + && DR_IS_WRITE (a)) + { + bool found = false; + int x = DR_WRITTEN_AT_LEAST_ONCE (a); + + if (x == 0) + return false; + + if (x == 1) + continue; + + for (j = 0; VEC_iterate (data_reference_p, drs, j, b); j++) + if (DR_STMT (b) != stmt + && DR_IS_WRITE (b) + && same_data_refs_base_objects (a, b)) + { + tree cb = bb_predicate (gimple_bb (DR_STMT (b))); + + if (DR_WRITTEN_AT_LEAST_ONCE (b) == 1 + || is_true_predicate (cb) + || is_true_predicate (ca = fold_or_predicates (EXPR_LOCATION (cb), + ca, cb))) + { + DR_WRITTEN_AT_LEAST_ONCE (a) = 1; + DR_WRITTEN_AT_LEAST_ONCE (b) = 1; + found = true; + break; + } + } + + if (!found) + { + DR_WRITTEN_AT_LEAST_ONCE (a) = 0; + return false; + } + } + + return true; +} + +/* Return true when the memory references of STMT won't trap in the + if-converted code. There are two things that we have to check for: + + - writes to memory occur to writable memory: if-conversion of + memory writes transforms the conditional memory writes into + unconditional writes, i.e. "if (cond) A[i] = foo" is transformed + into "A[i] = cond ? foo : A[i]", and as the write to memory may not + be executed at all in the original code, it may be a readonly + memory. To check that A is not const-qualified, we check that + there exists at least an unconditional write to A in the current + function. + + - reads or writes to memory are valid memory accesses for every + iteration. To check that the memory accesses are correctly formed + and that we are allowed to read and write in these locations, we + check that the memory accesses to be if-converted occur at every + iteration unconditionally. */ static bool -if_convertible_gimple_assign_stmt_p (struct loop *loop, basic_block bb, - gimple stmt) +ifcvt_memrefs_wont_trap (gimple stmt, VEC (data_reference_p, heap) *refs) { - tree lhs; + return write_memrefs_written_at_least_once (stmt, refs) + && memrefs_read_or_written_unconditionally (stmt, refs); +} - if (!is_gimple_assign (stmt)) +/* Wrapper around gimple_could_trap_p refined for the needs of the + if-conversion. Try to prove that the memory accesses of STMT could + not trap in the innermost loop containing STMT. */ + +static bool +ifcvt_could_trap_p (gimple stmt, VEC (data_reference_p, heap) *refs) +{ + if (gimple_vuse (stmt) + && !gimple_could_trap_p_1 (stmt, false, false) + && ifcvt_memrefs_wont_trap (stmt, refs)) return false; + return gimple_could_trap_p (stmt); +} + +/* 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. */ + +static bool +if_convertible_gimple_assign_stmt_p (gimple stmt, + VEC (data_reference_p, heap) *refs) +{ + tree lhs = gimple_assign_lhs (stmt); + basic_block bb; + if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "-------------------------\n"); print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); } - lhs = gimple_assign_lhs (stmt); + if (!is_gimple_reg_type (TREE_TYPE (lhs))) + return false; /* Some of these constrains might be too conservative. */ if (stmt_ends_bb_p (stmt) @@ -384,18 +674,29 @@ if_convertible_gimple_assign_stmt_p (struct loop *loop, basic_block bb, return false; } - /* See if it needs speculative loading or not. */ - if (bb != loop->header - && gimple_assign_rhs_could_trap_p (stmt)) + if (flag_tree_loop_if_convert_stores) + { + if (ifcvt_could_trap_p (stmt, refs)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "tree could trap...\n"); + return false; + } + return true; + } + + if (gimple_assign_rhs_could_trap_p (stmt)) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "tree could trap...\n"); return false; } + bb = gimple_bb (stmt); + if (TREE_CODE (lhs) != SSA_NAME - && bb != loop->header - && !bb_with_exit_edge_p (loop, bb)) + && bb != bb->loop_father->header + && !bb_with_exit_edge_p (bb->loop_father, bb)) { if (dump_file && (dump_flags & TDF_DETAILS)) { @@ -408,28 +709,40 @@ if_convertible_gimple_assign_stmt_p (struct loop *loop, basic_block bb, return true; } -/* 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. */ +/* 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. */ static bool -if_convertible_stmt_p (struct loop *loop, basic_block bb, gimple stmt) +if_convertible_stmt_p (gimple stmt, VEC (data_reference_p, heap) *refs) { switch (gimple_code (stmt)) { case GIMPLE_LABEL: - break; + case GIMPLE_DEBUG: + case GIMPLE_COND: + return true; case GIMPLE_ASSIGN: + return if_convertible_gimple_assign_stmt_p (stmt, refs); - if (!if_convertible_gimple_assign_stmt_p (loop, bb, stmt)) + case GIMPLE_CALL: + { + tree fndecl = gimple_call_fndecl (stmt); + if (fndecl) + { + int flags = gimple_call_flags (stmt); + if ((flags & ECF_CONST) + && !(flags & ECF_LOOPING_CONST_OR_PURE) + /* We can only vectorize some builtins at the moment, + so restrict if-conversion to those. */ + && DECL_BUILT_IN (fndecl)) + return true; + } return false; - break; - - case GIMPLE_COND: - break; + } default: /* Don't know what to do with 'em so don't do anything. */ @@ -445,14 +758,30 @@ if_convertible_stmt_p (struct loop *loop, basic_block bb, gimple stmt) return true; } -/* 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. */ +/* Return true when BB post-dominates all its predecessors. */ + +static bool +bb_postdominates_preds (basic_block bb) +{ + unsigned i; + + for (i = 0; i < EDGE_COUNT (bb->preds); i++) + if (!dominated_by_p (CDI_POST_DOMINATORS, EDGE_PRED (bb, i)->src, bb)) + return false; + + 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. */ static bool if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb) @@ -463,6 +792,10 @@ if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb) if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "----------[%d]-------------\n", bb->index); + if (EDGE_COUNT (bb->preds) > 2 + || EDGE_COUNT (bb->succs) > 2) + return false; + if (exit_bb) { if (bb != loop->latch) @@ -477,7 +810,7 @@ if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb) fprintf (dump_file, "non empty basic block after exit bb\n"); return false; } - else if (bb == loop->latch + else if (bb == loop->latch && bb != exit_bb && !dominated_by_p (CDI_DOMINATORS, bb, exit_bb)) { @@ -493,67 +826,226 @@ if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb) (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; } + if (EDGE_COUNT (bb->preds) == 2 + && bb != loop->header + && !bb_postdominates_preds (bb)) + return false; + return true; } -/* 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). */ +/* Return true when all predecessor blocks of BB are visited. The + VISITED bitmap keeps track of the visited blocks. */ static bool -if_convertible_loop_p (struct loop *loop, bool for_vectorizer ATTRIBUTE_UNUSED) +pred_blocks_visited_p (basic_block bb, bitmap *visited) { - basic_block bb; - gimple_stmt_iterator itr; - unsigned int i; edge e; edge_iterator ei; - basic_block exit_bb = NULL; - - /* Handle only inner most loop. */ - if (!loop || loop->inner) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "not inner most loop\n"); + FOR_EACH_EDGE (e, ei, bb->preds) + if (!bitmap_bit_p (*visited, e->src->index)) return false; - } - /* If only one block, no need for if-conversion. */ - if (loop->num_nodes <= 2) + 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); + + blocks_in_bfs_order = get_loop_body_in_bfs_order (loop); + + index = 0; + while (index < loop->num_nodes) { - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "less than 2 basic blocks\n"); - return false; + 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; +} - /* More than one loop exit is too much to handle. */ - if (!single_exit (loop)) +/* Returns true when the analysis of the predicates for all the basic + blocks in LOOP succeeded. + + 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 + has the "true" predicate. Other statements executed under a + condition are predicated with that condition, for example + + | if (x) + | S1; + | else + | S2; + + S1 will be predicated with "x", and + S2 will be predicated with "!x". */ + +static bool +predicate_bbs (loop_p loop) +{ + unsigned int i; + + for (i = 0; i < loop->num_nodes; i++) + init_bb_predicate (ifc_bbs[i]); + + for (i = 0; i < loop->num_nodes; i++) { - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "multiple exits\n"); - return false; + 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) + { + reset_bb_predicate (loop->latch); + continue; + } + + cond = bb_predicate (bb); + + for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr)) + { + gimple stmt = gsi_stmt (itr); + + switch (gimple_code (stmt)) + { + case GIMPLE_LABEL: + case GIMPLE_ASSIGN: + case GIMPLE_CALL: + case GIMPLE_DEBUG: + break; + + case GIMPLE_COND: + { + tree c2, tem; + 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)); + + /* Add new condition into destination's predicate list. */ + extract_true_false_edges_from_block (gimple_bb (stmt), + &true_edge, &false_edge); + + /* If C is true, then TRUE_EDGE is taken. */ + add_to_dst_predicate_list (loop, true_edge, + unshare_expr (cond), + unshare_expr (c)); + + /* If C is false, then FALSE_EDGE is taken. */ + c2 = invert_truthvalue_loc (loc, unshare_expr (c)); + tem = canonicalize_cond_expr_cond (c2); + if (tem) + c2 = tem; + add_to_dst_predicate_list (loop, false_edge, + unshare_expr (cond), c2); + + cond = NULL_TREE; + break; + } + + default: + /* Not handled yet in if-conversion. */ + return false; + } + } + + /* 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; + + add_to_predicate_list (bb_n, cond); + } } - /* ??? Check target's vector conditional operation support for vectorizer. */ + /* The loop header is always executed. */ + reset_bb_predicate (loop->header); + gcc_assert (bb_predicate_gimplified_stmts (loop->header) == NULL + && bb_predicate_gimplified_stmts (loop->latch) == NULL); + + return true; +} + +/* Return true when LOOP is if-convertible. This is a helper function + for if_convertible_loop_p. REFS and DDRS are initialized and freed + in if_convertible_loop_p. */ - /* 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 (loop_exit_edge_p (loop, e)) - return false; - } +static bool +if_convertible_loop_p_1 (struct loop *loop, + VEC (loop_p, heap) **loop_nest, + VEC (data_reference_p, heap) **refs, + VEC (ddr_p, heap) **ddrs) +{ + bool res; + unsigned int i; + basic_block exit_bb = NULL; + + /* Don't if-convert the loop when the data dependences cannot be + computed: the loop won't be vectorized in that case. */ + res = compute_data_dependences_for_loop (loop, true, loop_nest, refs, ddrs); + if (!res) + return false; calculate_dominance_info (CDI_DOMINATORS); calculate_dominance_info (CDI_POST_DOMINATORS); @@ -563,139 +1055,138 @@ if_convertible_loop_p (struct loop *loop, bool for_vectorizer ATTRIBUTE_UNUSED) if (!ifc_bbs) { if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file,"Irreducible loop\n"); - free_dominance_info (CDI_POST_DOMINATORS); + fprintf (dump_file, "Irreducible loop\n"); return false; } for (i = 0; i < loop->num_nodes; i++) { - bb = ifc_bbs[i]; + basic_block bb = ifc_bbs[i]; if (!if_convertible_bb_p (loop, bb, exit_bb)) return false; - /* Check statements. */ - 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. */ + if (bb_with_exit_edge_p (loop, bb)) + exit_bb = bb; + } - /* What about phi nodes ? */ - itr = gsi_start_phis (bb); + res = predicate_bbs (loop); + if (!res) + return false; + + if (flag_tree_loop_if_convert_stores) + { + data_reference_p dr; + + for (i = 0; VEC_iterate (data_reference_p, *refs, i, dr); i++) + { + dr->aux = XNEW (struct ifc_dr); + DR_WRITTEN_AT_LEAST_ONCE (dr) = -1; + DR_RW_UNCONDITIONALLY (dr) = -1; + } + } - /* Clear aux field of incoming edges to a bb with a phi node. */ - if (!gsi_end_p (itr)) - FOR_EACH_EDGE (e, ei, bb->preds) - e->aux = NULL; + for (i = 0; i < loop->num_nodes; i++) + { + basic_block bb = ifc_bbs[i]; + gimple_stmt_iterator itr; - /* Check statements. */ - for (; !gsi_end_p (itr); gsi_next (&itr)) + for (itr = gsi_start_phis (bb); !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 (loop, bb)) - exit_bb = bb; + /* Check the if-convertibility of statements in predicated BBs. */ + if (is_predicated (bb)) + for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr)) + if (!if_convertible_stmt_p (gsi_stmt (itr), *refs)) + return false; } - /* 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"); + fprintf (dump_file, "Applying if-conversion\n"); - free_dominance_info (CDI_POST_DOMINATORS); return true; } -/* Add condition COND into predicate list of basic block BB. */ +/* 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 void -add_to_predicate_list (basic_block bb, tree new_cond) +static bool +if_convertible_loop_p (struct loop *loop) { - tree cond = (tree) bb->aux; - - if (cond) - cond = fold_build2 (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. */ + edge e; + edge_iterator ei; + bool res = false; + VEC (data_reference_p, heap) *refs; + VEC (ddr_p, heap) *ddrs; + VEC (loop_p, heap) *loop_nest; -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; + /* Handle only innermost loop. */ + if (!loop || loop->inner) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "not innermost loop\n"); + return false; + } - if (!flow_bb_inside_loop_p (loop, e->dest)) - return NULL_TREE; + /* If only one block, no need for if-conversion. */ + if (loop->num_nodes <= 2) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "less than 2 basic blocks\n"); + return false; + } - if (prev_cond == boolean_true_node || !prev_cond) - new_cond = unshare_expr (cond); - else + /* More than one loop exit is too much to handle. */ + if (!single_exit (loop)) { - 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); + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "multiple exits\n"); + return false; } - 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. */ + /* If one of the loop header's edge is an exit edge then do not + apply if-conversion. */ + FOR_EACH_EDGE (e, ei, loop->header->succs) + if (loop_exit_edge_p (loop, e)) + return false; -static void -clean_predicate_lists (struct loop *loop) -{ - basic_block *bb; - unsigned int i; - edge e; - edge_iterator ei; + refs = VEC_alloc (data_reference_p, heap, 5); + ddrs = VEC_alloc (ddr_p, heap, 25); + loop_nest = VEC_alloc (loop_p, heap, 3); + res = if_convertible_loop_p_1 (loop, &loop_nest, &refs, &ddrs); - bb = get_loop_body (loop); - for (i = 0; i < loop->num_nodes; i++) + if (flag_tree_loop_if_convert_stores) { - bb[i]->aux = NULL; - FOR_EACH_EDGE (e, ei, bb[i]->succs) - e->aux = NULL; + data_reference_p dr; + unsigned int i; + + for (i = 0; VEC_iterate (data_reference_p, refs, i, dr); i++) + free (dr->aux); } - free (bb); + + VEC_free (loop_p, heap, loop_nest); + free_data_refs (refs); + free_dependence_relations (ddrs); + return res; } -/* 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. */ +/* 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, +find_phi_replacement_condition (struct loop *loop, basic_block bb, tree *cond, - gimple_stmt_iterator *gsi) + gimple_stmt_iterator *gsi) { edge first_edge, second_edge; tree tmp_cond; @@ -711,7 +1202,7 @@ find_phi_replacement_condition (struct loop *loop, 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) @@ -722,14 +1213,14 @@ find_phi_replacement_condition (struct loop *loop, S3: x = (c == d) ? b : a; - S3 is preferred over S1 and S2*, Make 'b' first_bb and use + 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; + tmp_cond = bb_predicate (first_edge->src); gcc_assert (tmp_cond); if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR) @@ -747,109 +1238,89 @@ find_phi_replacement_condition (struct loop *loop, || dominated_by_p (CDI_DOMINATORS, second_edge->src, first_edge->src)) { - *cond = (tree) (second_edge->src)->aux; - - /* If there is a condition on an incoming edge, - AND it with the incoming bb predicate. */ - if (second_edge->aux) - *cond = build2 (TRUTH_AND_EXPR, boolean_type_node, - *cond, (tree) second_edge->aux); + *cond = bb_predicate (second_edge->src); if (TREE_CODE (*cond) == TRUTH_NOT_EXPR) - /* We can be smart here and choose inverted - condition without switching bbs. */ - *cond = invert_truthvalue (*cond); + *cond = TREE_OPERAND (*cond, 0); else /* Select non loop header bb. */ first_edge = second_edge; } else - { - /* FIRST_BB is not loop header */ - *cond = (tree) (first_edge->src)->aux; - - /* If there is a condition on an incoming edge, - AND it with 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. */ - *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)) - { - gimple new_stmt; - - new_stmt = ifc_temp_var (TREE_TYPE (*cond), unshare_expr (*cond)); - gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT); - *cond = gimple_assign_lhs (new_stmt); - } + *cond = bb_predicate (first_edge->src); - gcc_assert (*cond); + /* Gimplify the condition to a valid cond-expr conditonal operand. */ + *cond = force_gimple_operand_gsi_1 (gsi, unshare_expr (*cond), + is_gimple_condexpr, NULL_TREE, + true, GSI_SAME_STMT); return first_edge->src; } +/* Replace a scalar PHI node with a COND_EXPR using COND as condition. + 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) - { - arg_0 = gimple_phi_arg_def (phi, 1); - arg_1 = gimple_phi_arg_def (phi, 0); - } + if ((arg = degenerate_phi_result (phi)) + || ((scev = analyze_scalar_evolution (gimple_bb (phi)->loop_father, + res)) + && !chrec_contains_undetermined (scev) + && scev != res + && (arg = gimple_phi_arg_def (phi, 0)))) + rhs = arg; else { - arg_0 = gimple_phi_arg_def (phi, 0); - arg_1 = gimple_phi_arg_def (phi, 1); - } + tree arg_0, arg_1; + /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr. */ + if (EDGE_PRED (bb, 1)->src == true_bb) + { + arg_0 = gimple_phi_arg_def (phi, 1); + arg_1 = gimple_phi_arg_def (phi, 0); + } + else + { + 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 = build3 (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)), - unshare_expr (cond), unshare_expr (arg_0), - unshare_expr (arg_1)); + gcc_checking_assert (bb == bb->loop_father->header + || bb_postdominates_preds (bb)); - /* Create new GIMPLE_ASSIGN statement using RHS. */ - new_stmt = gimple_build_assign (unshare_expr (PHI_RESULT (phi)), rhs); + /* Build new RHS using selected condition and arguments. */ + rhs = build3 (COND_EXPR, TREE_TYPE (res), + unshare_expr (cond), arg_0, arg_1); + } - /* Make new statement definition of the original phi result. */ + new_stmt = gimple_build_assign (res, rhs); SSA_NAME_DEF_STMT (gimple_phi_result (phi)) = new_stmt; - - /* Insert using iterator. */ gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT); update_stmt (new_stmt); @@ -860,17 +1331,16 @@ replace_phi_with_cond_gimple_assign_stmt (gimple phi, tree cond, } } -/* Process phi nodes for the given LOOP. Replace phi nodes with cond - modify expr. */ +/* Replaces in LOOP all the scalar phi nodes other than those in the + LOOP->header block with conditional modify expressions. */ static void -process_phi_nodes (struct loop *loop) +predicate_all_scalar_phis (struct loop *loop) { basic_block bb; 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++) { gimple phi; @@ -883,27 +1353,263 @@ 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 + /* 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)) { phi = gsi_stmt (phi_gsi); - replace_phi_with_cond_gimple_assign_stmt (phi, cond, true_bb, &gsi); + predicate_scalar_phi (phi, cond, true_bb, &gsi); release_phi_node (phi); gsi_next (&phi_gsi); } + 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. */ +/* 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; + + if (!is_predicated (bb)) + { + /* Do not insert statements for a basic block that is not + predicated. Also make sure that the predicate of the + basic block is set to true. */ + reset_bb_predicate (bb); + continue; + } + + stmts = bb_predicate_gimplified_stmts (bb); + if (stmts) + { + if (flag_tree_loop_if_convert_stores) + { + /* Insert the predicate of the BB just after the label, + as the if-conversion of memory writes will use this + predicate. */ + gimple_stmt_iterator gsi = gsi_after_labels (bb); + gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT); + } + else + { + /* Insert the predicate of the BB at the end of the BB + as this would reduce the register pressure: the only + use of this predicate will be in successor BBs. */ + gimple_stmt_iterator gsi = gsi_last_bb (bb); + + if (gsi_end_p (gsi) + || stmt_ends_bb_p (gsi_stmt (gsi))) + 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); + } + } +} + +/* Predicate each write to memory in LOOP. + + This function transforms control flow constructs containing memory + writes of the form: + + | for (i = 0; i < N; i++) + | if (cond) + | A[i] = expr; + + into the following form that does not contain control flow: + + | for (i = 0; i < N; i++) + | A[i] = cond ? expr : A[i]; + + The original CFG looks like this: + + | bb_0 + | i = 0 + | end_bb_0 + | + | bb_1 + | if (i < N) goto bb_5 else goto bb_2 + | end_bb_1 + | + | bb_2 + | cond = some_computation; + | if (cond) goto bb_3 else goto bb_4 + | end_bb_2 + | + | bb_3 + | A[i] = expr; + | goto bb_4 + | end_bb_3 + | + | bb_4 + | goto bb_1 + | end_bb_4 + + insert_gimplified_predicates inserts the computation of the COND + expression at the beginning of the destination basic block: + + | bb_0 + | i = 0 + | end_bb_0 + | + | bb_1 + | if (i < N) goto bb_5 else goto bb_2 + | end_bb_1 + | + | bb_2 + | cond = some_computation; + | if (cond) goto bb_3 else goto bb_4 + | end_bb_2 + | + | bb_3 + | cond = some_computation; + | A[i] = expr; + | goto bb_4 + | end_bb_3 + | + | bb_4 + | goto bb_1 + | end_bb_4 + + predicate_mem_writes is then predicating the memory write as follows: + + | bb_0 + | i = 0 + | end_bb_0 + | + | bb_1 + | if (i < N) goto bb_5 else goto bb_2 + | end_bb_1 + | + | bb_2 + | if (cond) goto bb_3 else goto bb_4 + | end_bb_2 + | + | bb_3 + | cond = some_computation; + | A[i] = cond ? expr : A[i]; + | goto bb_4 + | end_bb_3 + | + | bb_4 + | goto bb_1 + | end_bb_4 + + and finally combine_blocks removes the basic block boundaries making + the loop vectorizable: + + | bb_0 + | i = 0 + | if (i < N) goto bb_5 else goto bb_1 + | end_bb_0 + | + | bb_1 + | cond = some_computation; + | A[i] = cond ? expr : A[i]; + | if (i < N) goto bb_5 else goto bb_4 + | end_bb_1 + | + | bb_4 + | goto bb_1 + | end_bb_4 +*/ + +static void +predicate_mem_writes (loop_p loop) +{ + unsigned int i, orig_loop_num_nodes = loop->num_nodes; + + for (i = 1; i < orig_loop_num_nodes; i++) + { + gimple_stmt_iterator gsi; + basic_block bb = ifc_bbs[i]; + tree cond = bb_predicate (bb); + gimple stmt; + + if (is_true_predicate (cond)) + continue; + + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + if ((stmt = gsi_stmt (gsi)) + && gimple_assign_single_p (stmt) + && gimple_vdef (stmt)) + { + tree lhs = gimple_assign_lhs (stmt); + tree rhs = gimple_assign_rhs1 (stmt); + tree type = TREE_TYPE (lhs); + + lhs = ifc_temp_var (type, unshare_expr (lhs), &gsi); + rhs = ifc_temp_var (type, unshare_expr (rhs), &gsi); + rhs = build3 (COND_EXPR, type, unshare_expr (cond), rhs, lhs); + gimple_assign_set_rhs1 (stmt, ifc_temp_var (type, rhs, &gsi)); + update_stmt (stmt); + } + } +} + +/* 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. */ + +static void +remove_conditions_and_labels (loop_p loop) +{ + gimple_stmt_iterator gsi; + unsigned int i; + + for (i = 0; i < loop->num_nodes; i++) + { + basic_block bb = ifc_bbs[i]; + + if (bb_with_exit_edge_p (loop, bb) + || bb == loop->latch) + continue; + + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); ) + switch (gimple_code (gsi_stmt (gsi))) + { + case GIMPLE_COND: + case GIMPLE_LABEL: + gsi_remove (&gsi, true); + 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)); + } + gsi_next (&gsi); + break; + + default: + gsi_next (&gsi); + } + } +} + +/* 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) @@ -914,15 +1620,20 @@ combine_blocks (struct loop *loop) edge e; edge_iterator ei; - /* Process phi nodes to prepare blocks for merge. */ - process_phi_nodes (loop); + remove_conditions_and_labels (loop); + insert_gimplified_predicates (loop); + predicate_all_scalar_phis (loop); + + if (flag_tree_loop_if_convert_stores) + predicate_mem_writes (loop); - /* Merge basic blocks. First remove all the edges in the loop, except - for those from the exit block. */ + /* 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]; + free_bb_predicate (bb); if (bb_with_exit_edge_p (loop, bb)) { exit_bb = bb; @@ -948,7 +1659,7 @@ combine_blocks (struct loop *loop) { if (exit_bb != loop->header) { - /* Connect this node with 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); } @@ -963,7 +1674,7 @@ combine_blocks (struct loop *loop) } else { - /* If the loop does not have exit then reconnect header and latch. */ + /* 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); } @@ -979,17 +1690,9 @@ combine_blocks (struct loop *loop) if (bb == exit_bb || bb == loop->latch) continue; - /* Remove labels and make stmts member of loop->header. */ - for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); ) - { - if (gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL) - gsi_remove (&gsi, true); - else - { - gimple_set_bb (gsi_stmt (gsi), merge_target_bb); - gsi_next (&gsi); - } - } + /* Make stmts member of loop->header. */ + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + gimple_set_bb (gsi_stmt (gsi), merge_target_bb); /* Update stmt list. */ last = gsi_last_bb (merge_target_bb); @@ -999,133 +1702,54 @@ combine_blocks (struct loop *loop) delete_basic_block (bb); } - /* 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 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. */ if (exit_bb && exit_bb != loop->header && can_merge_blocks_p (loop->header, exit_bb)) merge_blocks (loop->header, exit_bb); -} -/* 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; + free (ifc_bbs); + ifc_bbs = NULL; } - -/* Return TRUE iff, all pred blocks of BB are visited. - Bitmap VISITED keeps history of visited blocks. */ +/* If-convert LOOP when it is legal. For the moment this pass has no + profitability analysis. Returns true when something changed. */ static bool -pred_blocks_visited_p (basic_block bb, bitmap *visited) +tree_if_conversion (struct loop *loop) { - 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. */ + bool changed = false; + ifc_bbs = NULL; -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; + if (!if_convertible_loop_p (loop) + || !dbg_cnt (if_conversion_tree)) + goto cleanup; - gcc_assert (loop->num_nodes); - gcc_assert (loop->latch != EXIT_BLOCK_PTR); + /* Now all statements are if-convertible. Combine all the basic + blocks into one huge basic block doing the if-conversion + on-the-fly. */ + combine_blocks (loop); - blocks = XCNEWVEC (basic_block, loop->num_nodes); - visited = BITMAP_ALLOC (NULL); + if (flag_tree_loop_if_convert_stores) + mark_sym_for_renaming (gimple_vop (cfun)); - blocks_in_bfs_order = get_loop_body_in_bfs_order (loop); + changed = true; - index = 0; - while (index < loop->num_nodes) + cleanup: + if (ifc_bbs) { - 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 if one of the basic block BB edge is exit of LOOP. */ + unsigned int i; -static bool -bb_with_exit_edge_p (struct loop *loop, basic_block bb) -{ - edge e; - edge_iterator ei; - bool exit_edge_found = false; + for (i = 0; i < loop->num_nodes; i++) + free_bb_predicate (ifc_bbs[i]); - FOR_EACH_EDGE (e, ei, bb->succs) - if (loop_exit_edge_p (loop, e)) - { - exit_edge_found = true; - break; - } + free (ifc_bbs); + ifc_bbs = NULL; + } - return exit_edge_found; + return changed; } /* Tree if-conversion pass management. */ @@ -1135,21 +1759,34 @@ main_tree_if_conversion (void) { loop_iterator li; struct loop *loop; + bool changed = false; + unsigned todo = 0; if (number_of_loops () <= 1) return 0; FOR_EACH_LOOP (li, loop, 0) - { - tree_if_conversion (loop, true); - } - return 0; + changed |= tree_if_conversion (loop); + + if (changed) + todo |= TODO_cleanup_cfg; + + if (changed && flag_tree_loop_if_convert_stores) + todo |= TODO_update_ssa_only_virtuals; + + free_dominance_info (CDI_POST_DOMINATORS); + + return todo; } +/* Returns true when the if-conversion pass is enabled. */ + static bool gate_tree_if_conversion (void) { - return flag_tree_vectorize != 0; + return ((flag_tree_vectorize && flag_tree_loop_if_convert != 0) + || flag_tree_loop_if_convert == 1 + || flag_tree_loop_if_convert_stores == 1); } struct gimple_opt_pass pass_if_conversion = @@ -1167,7 +1804,7 @@ struct gimple_opt_pass pass_if_conversion = 0, /* properties_provided */ 0, /* properties_destroyed */ 0, /* todo_flags_start */ - TODO_dump_func | TODO_verify_loops | TODO_verify_stmts | TODO_verify_flow + TODO_verify_stmts | TODO_verify_flow /* todo_flags_finish */ } };