X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Ftree-predcom.c;h=bef5252923ec51fb2a5b95c6fd7b4a7ffb3f2a78;hb=0df4975170851fc68246dc1dd79c3156229dde4a;hp=78d45b88364cf906d583c58ba14d090a443b619a;hpb=48e1416a24d50cacbb2a5e06a9ee61dd8cbee313;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/tree-predcom.c b/gcc/tree-predcom.c index 78d45b88364..bef5252923e 100644 --- a/gcc/tree-predcom.c +++ b/gcc/tree-predcom.c @@ -1,5 +1,6 @@ /* Predictive commoning. - Copyright (C) 2005, 2007, 2008, 2009 Free Software Foundation, Inc. + Copyright (C) 2005, 2007, 2008, 2009, 2010, 2011, 2012 + Free Software Foundation, Inc. This file is part of GCC. @@ -197,7 +198,8 @@ along with GCC; see the file COPYING3. If not see #include "tree-scalar-evolution.h" #include "tree-chrec.h" #include "params.h" -#include "diagnostic.h" +#include "tree-pretty-print.h" +#include "gimple-pretty-print.h" #include "tree-pass.h" #include "tree-affine.h" #include "tree-inline.h" @@ -418,7 +420,7 @@ dump_chain (FILE *file, chain_p chain) if (chain->vars) { fprintf (file, " vars"); - for (i = 0; VEC_iterate (tree, chain->vars, i, var); i++) + FOR_EACH_VEC_ELT (tree, chain->vars, i, var) { fprintf (file, " "); print_generic_expr (file, var, TDF_SLIM); @@ -429,7 +431,7 @@ dump_chain (FILE *file, chain_p chain) if (chain->inits) { fprintf (file, " inits"); - for (i = 0; VEC_iterate (tree, chain->inits, i, var); i++) + FOR_EACH_VEC_ELT (tree, chain->inits, i, var) { fprintf (file, " "); print_generic_expr (file, var, TDF_SLIM); @@ -438,7 +440,7 @@ dump_chain (FILE *file, chain_p chain) } fprintf (file, " references:\n"); - for (i = 0; VEC_iterate (dref, chain->refs, i, a); i++) + FOR_EACH_VEC_ELT (dref, chain->refs, i, a) dump_dref (file, a); fprintf (file, "\n"); @@ -453,7 +455,7 @@ dump_chains (FILE *file, VEC (chain_p, heap) *chains) chain_p chain; unsigned i; - for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++) + FOR_EACH_VEC_ELT (chain_p, chains, i, chain) dump_chain (file, chain); } @@ -468,7 +470,7 @@ dump_component (FILE *file, struct component *comp) fprintf (file, "Component%s:\n", comp->comp_step == RS_INVARIANT ? " (invariant)" : ""); - for (i = 0; VEC_iterate (dref, comp->refs, i, a); i++) + FOR_EACH_VEC_ELT (dref, comp->refs, i, a) dump_dref (file, a); fprintf (file, "\n"); } @@ -496,7 +498,7 @@ release_chain (chain_p chain) if (chain == NULL) return; - for (i = 0; VEC_iterate (dref, chain->refs, i, ref); i++) + FOR_EACH_VEC_ELT (dref, chain->refs, i, ref) free (ref); VEC_free (dref, heap, chain->refs); @@ -514,7 +516,7 @@ release_chains (VEC (chain_p, heap) *chains) unsigned i; chain_p chain; - for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++) + FOR_EACH_VEC_ELT (chain_p, chains, i, chain) release_chain (chain); VEC_free (chain_p, heap, chains); } @@ -596,6 +598,7 @@ suitable_reference_p (struct data_reference *a, enum ref_step_type *ref_step) tree ref = DR_REF (a), step = DR_STEP (a); if (!step + || TREE_THIS_VOLATILE (ref) || !is_gimple_reg_type (TREE_TYPE (ref)) || tree_could_throw_p (ref)) return false; @@ -615,11 +618,12 @@ suitable_reference_p (struct data_reference *a, enum ref_step_type *ref_step) static void aff_combination_dr_offset (struct data_reference *dr, aff_tree *offset) { + tree type = TREE_TYPE (DR_OFFSET (dr)); aff_tree delta; - tree_to_aff_combination_expand (DR_OFFSET (dr), sizetype, offset, + tree_to_aff_combination_expand (DR_OFFSET (dr), type, offset, &name_expansions); - aff_combination_const (&delta, sizetype, tree_to_double_int (DR_INIT (dr))); + aff_combination_const (&delta, type, tree_to_double_int (DR_INIT (dr))); aff_combination_add (offset, &delta); } @@ -664,7 +668,7 @@ determine_offset (struct data_reference *a, struct data_reference *b, aff_combination_scale (&baseb, double_int_minus_one); aff_combination_add (&diff, &baseb); - tree_to_aff_combination_expand (DR_STEP (a), sizetype, + tree_to_aff_combination_expand (DR_STEP (a), TREE_TYPE (DR_STEP (a)), &step, &name_expansions); return aff_combination_constant_multiple_p (&diff, &step, off); } @@ -680,7 +684,7 @@ last_always_executed_block (struct loop *loop) edge ex; basic_block last = loop->latch; - for (i = 0; VEC_iterate (edge, exits, i, ex); i++) + FOR_EACH_VEC_ELT (edge, exits, i, ex) last = nearest_common_dominator (CDI_DOMINATORS, last, ex->src); VEC_free (edge, heap, exits); @@ -705,7 +709,7 @@ split_data_refs_to_components (struct loop *loop, dref dataref; basic_block last_always_executed = last_always_executed_block (loop); - for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++) + FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, dr) { if (!DR_REF (dr)) { @@ -722,7 +726,7 @@ split_data_refs_to_components (struct loop *loop, comp_father[n] = n; comp_size[n] = 1; - for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++) + FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, dr) { enum ref_step_type dummy; @@ -733,7 +737,7 @@ split_data_refs_to_components (struct loop *loop, } } - for (i = 0; VEC_iterate (ddr_p, depends, i, ddr); i++) + FOR_EACH_VEC_ELT (ddr_p, depends, i, ddr) { double_int dummy_off; @@ -760,7 +764,7 @@ split_data_refs_to_components (struct loop *loop, comps = XCNEWVEC (struct component *, n); bad = component_of (comp_father, n); - for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++) + FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, dr) { ia = (unsigned) (size_t) dr->aux; ca = component_of (comp_father, ia); @@ -817,7 +821,7 @@ suitable_component_p (struct loop *loop, struct component *comp) basic_block ba, bp = loop->header; bool ok, has_write = false; - for (i = 0; VEC_iterate (dref, comp->refs, i, a); i++) + FOR_EACH_VEC_ELT (dref, comp->refs, i, a) { ba = gimple_bb (a->stmt); @@ -827,7 +831,7 @@ suitable_component_p (struct loop *loop, struct component *comp) gcc_assert (dominated_by_p (CDI_DOMINATORS, ba, bp)); bp = ba; - if (!DR_IS_READ (a->ref)) + if (DR_IS_WRITE (a->ref)) has_write = true; } @@ -881,7 +885,7 @@ filter_suitable_components (struct loop *loop, struct component *comps) unsigned i; *comp = act->next; - for (i = 0; VEC_iterate (dref, act->refs, i, ref); i++) + FOR_EACH_VEC_ELT (dref, act->refs, i, ref) free (ref); release_component (act); } @@ -923,7 +927,7 @@ add_ref_to_chain (chain_p chain, dref ref) double_int dist; gcc_assert (double_int_scmp (root->offset, ref->offset) <= 0); - dist = double_int_add (ref->offset, double_int_neg (root->offset)); + dist = double_int_sub (ref->offset, root->offset); if (double_int_ucmp (uhwi_to_double_int (MAX_DISTANCE), dist) <= 0) { free (ref); @@ -961,7 +965,7 @@ make_invariant_chain (struct component *comp) chain->all_always_accessed = true; - for (i = 0; VEC_iterate (dref, comp->refs, i, ref); i++) + FOR_EACH_VEC_ELT (dref, comp->refs, i, ref) { VEC_safe_push (dref, heap, chain->refs, ref); chain->all_always_accessed &= ref->always_accessed; @@ -1047,8 +1051,8 @@ valid_initializer_p (struct data_reference *ref, aff_combination_scale (&base, double_int_minus_one); aff_combination_add (&diff, &base); - tree_to_aff_combination_expand (DR_STEP (root), sizetype, &step, - &name_expansions); + tree_to_aff_combination_expand (DR_STEP (root), TREE_TYPE (DR_STEP (root)), + &step, &name_expansions); if (!aff_combination_constant_multiple_p (&diff, &step, &off)) return false; @@ -1112,7 +1116,7 @@ find_looparound_phi (struct loop *loop, dref ref, dref root) memset (&init_dr, 0, sizeof (struct data_reference)); DR_REF (&init_dr) = init_ref; DR_STMT (&init_dr) = phi; - if (!dr_analyze_innermost (&init_dr)) + if (!dr_analyze_innermost (&init_dr, loop)) return NULL; if (!valid_initializer_p (&init_dr, ref->distance + 1, root->ref)) @@ -1133,7 +1137,7 @@ insert_looparound_copy (chain_p chain, dref ref, gimple phi) nw->distance = ref->distance + 1; nw->always_accessed = 1; - for (i = 0; VEC_iterate (dref, chain->refs, i, aref); i++) + FOR_EACH_VEC_ELT (dref, chain->refs, i, aref) if (aref->distance >= nw->distance) break; VEC_safe_insert (dref, heap, chain->refs, i, nw); @@ -1157,7 +1161,7 @@ add_looparound_copies (struct loop *loop, chain_p chain) dref ref, root = get_chain_root (chain); gimple phi; - for (i = 0; VEC_iterate (dref, chain->refs, i, ref); i++) + FOR_EACH_VEC_ELT (dref, chain->refs, i, ref) { phi = find_looparound_phi (loop, ref, root); if (!phi) @@ -1180,6 +1184,7 @@ determine_roots_comp (struct loop *loop, unsigned i; dref a; chain_p chain = NULL; + double_int last_ofs = double_int_zero; /* Invariants are handled specially. */ if (comp->comp_step == RS_INVARIANT) @@ -1189,18 +1194,23 @@ determine_roots_comp (struct loop *loop, return; } - qsort (VEC_address (dref, comp->refs), VEC_length (dref, comp->refs), - sizeof (dref), order_drefs); + VEC_qsort (dref, comp->refs, order_drefs); - for (i = 0; VEC_iterate (dref, comp->refs, i, a); i++) + FOR_EACH_VEC_ELT (dref, comp->refs, i, a) { - if (!chain || !DR_IS_READ (a->ref)) + if (!chain || DR_IS_WRITE (a->ref) + || double_int_ucmp (uhwi_to_double_int (MAX_DISTANCE), + double_int_sub (a->offset, last_ofs)) <= 0) { if (nontrivial_chain_p (chain)) - VEC_safe_push (chain_p, heap, *chains, chain); + { + add_looparound_copies (loop, chain); + VEC_safe_push (chain_p, heap, *chains, chain); + } else release_chain (chain); chain = make_rooted_chain (a); + last_ofs = a->offset; continue; } @@ -1296,8 +1306,20 @@ replace_ref_with (gimple stmt, tree new_tree, bool set, bool in_lhs) val = gimple_assign_lhs (stmt); if (TREE_CODE (val) != SSA_NAME) { - gcc_assert (gimple_assign_copy_p (stmt)); val = gimple_assign_rhs1 (stmt); + gcc_assert (gimple_assign_single_p (stmt)); + if (TREE_CLOBBER_P (val)) + { + val = gimple_default_def (cfun, SSA_NAME_VAR (new_tree)); + if (val == NULL_TREE) + { + val = make_ssa_name (SSA_NAME_VAR (new_tree), + gimple_build_nop ()); + set_default_def (SSA_NAME_VAR (new_tree), val); + } + } + else + gcc_assert (gimple_assign_copy_p (stmt)); } } else @@ -1335,12 +1357,13 @@ ref_at_iteration (struct loop *loop, tree ref, int iter) if (!op0) return NULL_TREE; } - else if (!INDIRECT_REF_P (ref)) + else if (!INDIRECT_REF_P (ref) + && TREE_CODE (ref) != MEM_REF) return unshare_expr (ref); - if (TREE_CODE (ref) == INDIRECT_REF) + if (TREE_CODE (ref) == MEM_REF) { - ret = build1 (INDIRECT_REF, TREE_TYPE (ref), NULL_TREE); + ret = unshare_expr (ref); idx = TREE_OPERAND (ref, 0); idx_p = &TREE_OPERAND (ret, 0); } @@ -1387,7 +1410,7 @@ ref_at_iteration (struct loop *loop, tree ref, int iter) { val = fold_build2 (MULT_EXPR, sizetype, iv.step, size_int (iter)); - val = fold_build2 (POINTER_PLUS_EXPR, type, iv.base, val); + val = fold_build_pointer_plus (iv.base, val); } else { @@ -1449,13 +1472,9 @@ static tree predcom_tmp_var (tree ref, unsigned i, bitmap tmp_vars) { tree type = TREE_TYPE (ref); - tree var = create_tmp_var (type, get_lsm_tmp_name (ref, i)); - /* We never access the components of the temporary variable in predictive commoning. */ - if (TREE_CODE (type) == COMPLEX_TYPE - || TREE_CODE (type) == VECTOR_TYPE) - DECL_GIMPLE_REG_P (var) = 1; + tree var = create_tmp_reg (type, get_lsm_tmp_name (ref, i)); add_referenced_var (var); bitmap_set_bit (tmp_vars, DECL_UID (var)); @@ -1497,7 +1516,7 @@ initialize_root_vars (struct loop *loop, chain_p chain, bitmap tmp_vars) if (reuse_first) VEC_quick_push (tree, chain->vars, VEC_index (tree, chain->vars, 0)); - for (i = 0; VEC_iterate (tree, chain->vars, i, var); i++) + FOR_EACH_VEC_ELT (tree, chain->vars, i, var) VEC_replace (tree, chain->vars, i, make_ssa_name (var, NULL)); for (i = 0; i < n; i++) @@ -1562,7 +1581,7 @@ initialize_root_vars_lm (struct loop *loop, dref root, bool written, if (written) VEC_quick_push (tree, *vars, VEC_index (tree, *vars, 0)); - for (i = 0; VEC_iterate (tree, *vars, i, var); i++) + FOR_EACH_VEC_ELT (tree, *vars, i, var) VEC_replace (tree, *vars, i, make_ssa_name (var, NULL)); var = VEC_index (tree, *vars, 0); @@ -1601,8 +1620,8 @@ execute_load_motion (struct loop *loop, chain_p chain, bitmap tmp_vars) gcc_assert (chain->type == CT_INVARIANT); gcc_assert (!chain->combined); - for (i = 0; VEC_iterate (dref, chain->refs, i, a); i++) - if (!DR_IS_READ (a->ref)) + FOR_EACH_VEC_ELT (dref, chain->refs, i, a) + if (DR_IS_WRITE (a->ref)) n_writes++; /* If there are no reads in the loop, there is nothing to do. */ @@ -1613,12 +1632,12 @@ execute_load_motion (struct loop *loop, chain_p chain, bitmap tmp_vars) &vars, chain->inits, tmp_vars); ridx = 0; - for (i = 0; VEC_iterate (dref, chain->refs, i, a); i++) + FOR_EACH_VEC_ELT (dref, chain->refs, i, a) { bool is_read = DR_IS_READ (a->ref); mark_virtual_ops_for_renaming (a->stmt); - if (!DR_IS_READ (a->ref)) + if (DR_IS_WRITE (a->ref)) { n_writes--; if (n_writes) @@ -1663,6 +1682,8 @@ single_nonlooparound_use (tree name) return NULL; } + else if (is_gimple_debug (stmt)) + continue; else if (ret != NULL) return NULL; else @@ -1768,7 +1789,7 @@ determine_unroll_factor (VEC (chain_p, heap) *chains) unsigned factor = 1, af, nfactor, i; unsigned max = PARAM_VALUE (PARAM_MAX_UNROLL_TIMES); - for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++) + FOR_EACH_VEC_ELT (chain_p, chains, i, chain) { if (chain->type == CT_INVARIANT || chain->combined) continue; @@ -1797,7 +1818,7 @@ execute_pred_commoning (struct loop *loop, VEC (chain_p, heap) *chains, chain_p chain; unsigned i; - for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++) + FOR_EACH_VEC_ELT (chain_p, chains, i, chain) { if (chain->type == CT_INVARIANT) execute_load_motion (loop, chain, tmp_vars); @@ -1818,8 +1839,8 @@ replace_phis_by_defined_names (VEC (chain_p, heap) *chains) dref a; unsigned i, j; - for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++) - for (j = 0; VEC_iterate (dref, chain->refs, j, a); j++) + FOR_EACH_VEC_ELT (chain_p, chains, i, chain) + FOR_EACH_VEC_ELT (dref, chain->refs, j, a) { if (gimple_code (a->stmt) == GIMPLE_PHI) { @@ -1839,8 +1860,8 @@ replace_names_by_phis (VEC (chain_p, heap) *chains) dref a; unsigned i, j; - for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++) - for (j = 0; VEC_iterate (dref, chain->refs, j, a); j++) + FOR_EACH_VEC_ELT (chain_p, chains, i, chain) + FOR_EACH_VEC_ELT (dref, chain->refs, j, a) if (a->stmt == NULL) { a->stmt = SSA_NAME_DEF_STMT (a->name_defined_by_phi); @@ -1879,7 +1900,6 @@ base_names_in_chain_on (struct loop *loop, tree name, tree var) { gimple stmt, phi; imm_use_iterator iter; - edge e; SSA_NAME_VAR (name) = var; @@ -1898,11 +1918,6 @@ base_names_in_chain_on (struct loop *loop, tree name, tree var) if (!phi) return; - if (gimple_bb (phi) == loop->header) - e = loop_latch_edge (loop); - else - e = single_pred_edge (gimple_bb (stmt)); - name = PHI_RESULT (phi); SSA_NAME_VAR (name) = var; } @@ -2204,12 +2219,12 @@ reassociate_to_the_same_stmt (tree name1, tree name2) /* Insert the new statement combining NAME1 and NAME2 before S1, and combine it with the rhs of S1. */ - var = create_tmp_var (type, "predreastmp"); + var = create_tmp_reg (type, "predreastmp"); add_referenced_var (var); new_name = make_ssa_name (var, NULL); new_stmt = gimple_build_assign_with_ops (code, new_name, name1, name2); - var = create_tmp_var (type, "predreastmp"); + var = create_tmp_reg (type, "predreastmp"); add_referenced_var (var); tmp_name = make_ssa_name (var, NULL); @@ -2267,7 +2282,7 @@ combine_chains (chain_p ch1, chain_p ch2) tree rslt_type = NULL_TREE; if (ch1 == ch2) - return false; + return NULL; if (ch1->length != ch2->length) return NULL; @@ -2335,7 +2350,7 @@ try_combine_chains (VEC (chain_p, heap) **chains) chain_p ch1, ch2, cch; VEC (chain_p, heap) *worklist = NULL; - for (i = 0; VEC_iterate (chain_p, *chains, i, ch1); i++) + FOR_EACH_VEC_ELT (chain_p, *chains, i, ch1) if (chain_can_be_combined_p (ch1)) VEC_safe_push (chain_p, heap, worklist, ch1); @@ -2345,7 +2360,7 @@ try_combine_chains (VEC (chain_p, heap) **chains) if (!chain_can_be_combined_p (ch1)) continue; - for (j = 0; VEC_iterate (chain_p, *chains, j, ch2); j++) + FOR_EACH_VEC_ELT (chain_p, *chains, j, ch2) { if (!chain_can_be_combined_p (ch2)) continue; @@ -2382,7 +2397,7 @@ prepare_initializers_chain (struct loop *loop, chain_p chain) /* If we have replaced some looparound phi nodes, use their initializers instead of creating our own. */ - for (i = 0; VEC_iterate (dref, chain->refs, i, laref); i++) + FOR_EACH_VEC_ELT (dref, chain->refs, i, laref) { if (gimple_code (laref->stmt) != GIMPLE_PHI) continue; @@ -2442,6 +2457,7 @@ prepare_initializers (struct loop *loop, VEC (chain_p, heap) *chains) static bool tree_predictive_commoning_loop (struct loop *loop) { + VEC (loop_p, heap) *loop_nest; VEC (data_reference_p, heap) *datarefs; VEC (ddr_p, heap) *dependences; struct component *components; @@ -2459,11 +2475,23 @@ tree_predictive_commoning_loop (struct loop *loop) dependence relations. */ datarefs = VEC_alloc (data_reference_p, heap, 10); dependences = VEC_alloc (ddr_p, heap, 10); - compute_data_dependences_for_loop (loop, true, &datarefs, &dependences); + loop_nest = VEC_alloc (loop_p, heap, 3); + if (! compute_data_dependences_for_loop (loop, true, &loop_nest, &datarefs, + &dependences)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Cannot analyze data dependencies\n"); + VEC_free (loop_p, heap, loop_nest); + free_data_refs (datarefs); + free_dependence_relations (dependences); + return false; + } + if (dump_file && (dump_flags & TDF_DETAILS)) dump_data_dependence_relations (dump_file, dependences); components = split_data_refs_to_components (loop, datarefs, dependences); + VEC_free (loop_p, heap, loop_nest); free_dependence_relations (dependences); if (!components) {