X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=gcc%2Ftree-loop-linear.c;h=f0dfa7ac49029cdb50df508f958cf0ddfd8fa622;hb=9ba025a2c1ba2d4c6529d16b26218a1c52866b72;hp=c93765a2eac17ef22642d0ee5fcdb7cba84156d1;hpb=366ccddb2bc50711bd3a11c1dee97b50e8ef1677;p=platform%2Fupstream%2Fgcc.git diff --git a/gcc/tree-loop-linear.c b/gcc/tree-loop-linear.c index c93765a..f0dfa7a 100644 --- a/gcc/tree-loop-linear.c +++ b/gcc/tree-loop-linear.c @@ -41,7 +41,6 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA #include "tree-data-ref.h" #include "tree-scalar-evolution.h" #include "tree-pass.h" -#include "varray.h" #include "lambda.h" /* Linear loop transforms include any composition of interchange, @@ -90,70 +89,77 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA */ static void -gather_interchange_stats (varray_type dependence_relations, - varray_type datarefs, +gather_interchange_stats (VEC (ddr_p, heap) *dependence_relations, + VEC (data_reference_p, heap) *datarefs, struct loop *loop, struct loop *first_loop, unsigned int *dependence_steps, unsigned int *nb_deps_not_carried_by_loop, - unsigned int *access_strides) + double_int *access_strides) { - unsigned int i; + unsigned int i, j; + struct data_dependence_relation *ddr; + struct data_reference *dr; *dependence_steps = 0; *nb_deps_not_carried_by_loop = 0; - *access_strides = 0; + *access_strides = double_int_zero; - for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++) + for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++) { - int dist; - struct data_dependence_relation *ddr = - (struct data_dependence_relation *) - VARRAY_GENERIC_PTR (dependence_relations, i); - /* If we don't know anything about this dependence, or the distance vector is NULL, or there is no dependence, then there is no reuse of data. */ - - if (DDR_DIST_VECT (ddr) == NULL - || DDR_ARE_DEPENDENT (ddr) == chrec_dont_know - || DDR_ARE_DEPENDENT (ddr) == chrec_known) + if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know + || DDR_ARE_DEPENDENT (ddr) == chrec_known + || DDR_NUM_DIST_VECTS (ddr) == 0) continue; - - - - dist = DDR_DIST_VECT (ddr)[loop->depth - first_loop->depth]; - if (dist == 0) - (*nb_deps_not_carried_by_loop) += 1; - else if (dist < 0) - (*dependence_steps) += -dist; - else - (*dependence_steps) += dist; + + for (j = 0; j < DDR_NUM_DIST_VECTS (ddr); j++) + { + int dist = DDR_DIST_VECT (ddr, j)[loop_depth (loop) - loop_depth (first_loop)]; + + if (dist == 0) + (*nb_deps_not_carried_by_loop) += 1; + + else if (dist < 0) + (*dependence_steps) += -dist; + + else + (*dependence_steps) += dist; + } } /* Compute the access strides. */ - for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++) + for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++) { unsigned int it; - struct data_reference *dr = VARRAY_GENERIC_PTR (datarefs, i); + tree ref = DR_REF (dr); tree stmt = DR_STMT (dr); struct loop *stmt_loop = loop_containing_stmt (stmt); struct loop *inner_loop = first_loop->inner; - + if (inner_loop != stmt_loop && !flow_loop_nested_p (inner_loop, stmt_loop)) continue; - for (it = 0; it < DR_NUM_DIMENSIONS (dr); it++) + + for (it = 0; it < DR_NUM_DIMENSIONS (dr); + it++, ref = TREE_OPERAND (ref, 0)) { tree chrec = DR_ACCESS_FN (dr, it); - tree tstride = evolution_part_in_loop_num - (chrec, loop->num); - + tree tstride = evolution_part_in_loop_num (chrec, loop->num); + tree array_size = TYPE_SIZE (TREE_TYPE (ref)); + double_int dstride; + if (tstride == NULL_TREE - || TREE_CODE (tstride) != INTEGER_CST) + || array_size == NULL_TREE + || TREE_CODE (tstride) != INTEGER_CST + || TREE_CODE (array_size) != INTEGER_CST) continue; - - (*access_strides) += int_cst_value (tstride); + + dstride = double_int_mul (tree_to_double_int (array_size), + tree_to_double_int (tstride)); + (*access_strides) = double_int_add (*access_strides, dstride); } } } @@ -169,21 +175,23 @@ gather_interchange_stats (varray_type dependence_relations, static lambda_trans_matrix try_interchange_loops (lambda_trans_matrix trans, unsigned int depth, - varray_type dependence_relations, - varray_type datarefs, + VEC (ddr_p, heap) *dependence_relations, + VEC (data_reference_p, heap) *datarefs, struct loop *first_loop) { struct loop *loop_i; struct loop *loop_j; unsigned int dependence_steps_i, dependence_steps_j; - unsigned int access_strides_i, access_strides_j; + double_int access_strides_i, access_strides_j; unsigned int nb_deps_not_carried_by_i, nb_deps_not_carried_by_j; struct data_dependence_relation *ddr; + if (VEC_length (ddr_p, dependence_relations) == 0) + return trans; + /* When there is an unknown relation in the dependence_relations, we know that it is no worth looking at this loop nest: give up. */ - ddr = (struct data_dependence_relation *) - VARRAY_GENERIC_PTR (dependence_relations, 0); + ddr = VEC_index (ddr_p, dependence_relations, 0); if (ddr == NULL || DDR_ARE_DEPENDENT (ddr) == chrec_dont_know) return trans; @@ -192,7 +200,7 @@ try_interchange_loops (lambda_trans_matrix trans, loop_j; loop_j = loop_j->inner) for (loop_i = first_loop; - loop_i->depth < loop_j->depth; + loop_depth (loop_i) < loop_depth (loop_j); loop_i = loop_i->inner) { gather_interchange_stats (dependence_relations, datarefs, @@ -219,43 +227,43 @@ try_interchange_loops (lambda_trans_matrix trans, */ if (dependence_steps_i < dependence_steps_j || nb_deps_not_carried_by_i > nb_deps_not_carried_by_j - || access_strides_i < access_strides_j) + || double_int_ucmp (access_strides_i, access_strides_j) < 0) { lambda_matrix_row_exchange (LTM_MATRIX (trans), - loop_i->depth - first_loop->depth, - loop_j->depth - first_loop->depth); + loop_depth (loop_i) - loop_depth (first_loop), + loop_depth (loop_j) - loop_depth (first_loop)); /* Validate the resulting matrix. When the transformation is not valid, reverse to the previous transformation. */ if (!lambda_transform_legal_p (trans, depth, dependence_relations)) lambda_matrix_row_exchange (LTM_MATRIX (trans), - loop_i->depth - first_loop->depth, - loop_j->depth - first_loop->depth); + loop_depth (loop_i) - loop_depth (first_loop), + loop_depth (loop_j) - loop_depth (first_loop)); } } return trans; } -/* Perform a set of linear transforms on LOOPS. */ +/* Perform a set of linear transforms on loops. */ void -linear_transform_loops (struct loops *loops) +linear_transform_loops (void) { - unsigned int i; + bool modified = false; + loop_iterator li; VEC(tree,heap) *oldivs = NULL; VEC(tree,heap) *invariants = NULL; + struct loop *loop_nest; - for (i = 1; i < loops->num; i++) + FOR_EACH_LOOP (li, loop_nest, 0) { unsigned int depth = 0; - varray_type datarefs; - varray_type dependence_relations; - struct loop *loop_nest = loops->parray[i]; + VEC (ddr_p, heap) *dependence_relations; + VEC (data_reference_p, heap) *datarefs; struct loop *temp; lambda_loopnest before, after; lambda_trans_matrix trans; bool problem = false; - bool need_perfect_nest = false; /* If it's not a loop nest, we don't want it. We also don't handle sibling loops properly, which are loops of the following form: @@ -265,12 +273,12 @@ linear_transform_loops (struct loops *loops) { ... } - for (j = 0; j < 50; j++) + for (j = 0; j < 50; j++) { ... } } */ - if (!loop_nest || !loop_nest->inner) + if (!loop_nest->inner || !single_exit (loop_nest)) continue; VEC_truncate (tree, oldivs, 0); VEC_truncate (tree, invariants, 0); @@ -278,7 +286,7 @@ linear_transform_loops (struct loops *loops) for (temp = loop_nest->inner; temp; temp = temp->inner) { /* If we have a sibling loop or multiple exit edges, jump ship. */ - if (temp->next || !temp->single_exit) + if (temp->next || !single_exit (temp)) { problem = true; break; @@ -290,40 +298,17 @@ linear_transform_loops (struct loops *loops) /* Analyze data references and dependence relations using scev. */ - VARRAY_GENERIC_PTR_INIT (datarefs, 10, "datarefs"); - VARRAY_GENERIC_PTR_INIT (dependence_relations, 10, - "dependence_relations"); - - - compute_data_dependences_for_loop (depth, loop_nest, - &datarefs, &dependence_relations); + datarefs = VEC_alloc (data_reference_p, heap, 10); + dependence_relations = VEC_alloc (ddr_p, heap, 10 * 10); + compute_data_dependences_for_loop (loop_nest, true, &datarefs, + &dependence_relations); + if (dump_file && (dump_flags & TDF_DETAILS)) - { - unsigned int j; - for (j = 0; j < VARRAY_ACTIVE_SIZE (dependence_relations); j++) - { - struct data_dependence_relation *ddr = - (struct data_dependence_relation *) - VARRAY_GENERIC_PTR (dependence_relations, j); - - if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE) - { - fprintf (dump_file, "DISTANCE_V ("); - print_lambda_vector (dump_file, DDR_DIST_VECT (ddr), - DDR_SIZE_VECT (ddr)); - fprintf (dump_file, ")\n"); - fprintf (dump_file, "DIRECTION_V ("); - print_lambda_vector (dump_file, DDR_DIR_VECT (ddr), - DDR_SIZE_VECT (ddr)); - fprintf (dump_file, ")\n"); - } - } - fprintf (dump_file, "\n\n"); - } + dump_ddrs (dump_file, dependence_relations); + /* Build the transformation matrix. */ trans = lambda_trans_matrix_new (depth, depth); lambda_matrix_id (LTM_MATRIX (trans), depth); - trans = try_interchange_loops (trans, depth, dependence_relations, datarefs, loop_nest); @@ -331,7 +316,7 @@ linear_transform_loops (struct loops *loops) { if (dump_file) fprintf (dump_file, "Won't transform loop. Optimal transform is the identity transform\n"); - continue; + goto free_and_continue; } /* Check whether the transformation is legal. */ @@ -339,17 +324,15 @@ linear_transform_loops (struct loops *loops) { if (dump_file) fprintf (dump_file, "Can't transform loop, transform is illegal:\n"); - continue; + goto free_and_continue; } - if (!perfect_nest_p (loop_nest)) - need_perfect_nest = true; - before = gcc_loopnest_to_lambda_loopnest (loops, - loop_nest, &oldivs, - &invariants, - need_perfect_nest); + + before = gcc_loopnest_to_lambda_loopnest (loop_nest, &oldivs, + &invariants); + if (!before) - continue; - + goto free_and_continue; + if (dump_file) { fprintf (dump_file, "Before:\n"); @@ -357,20 +340,29 @@ linear_transform_loops (struct loops *loops) } after = lambda_loopnest_transform (before, trans); + if (dump_file) { fprintf (dump_file, "After:\n"); print_lambda_loopnest (dump_file, after, 'u'); } + lambda_loopnest_to_gcc_loopnest (loop_nest, oldivs, invariants, after, trans); + modified = true; + if (dump_file) fprintf (dump_file, "Successfully transformed loop.\n"); + + free_and_continue: free_dependence_relations (dependence_relations); free_data_refs (datarefs); } + VEC_free (tree, heap, oldivs); VEC_free (tree, heap, invariants); scev_reset (); - rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa_full_phi); + + if (modified) + rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa_full_phi); }