From 87da4f2e31d49c241e7380f86b014304846fa08e Mon Sep 17 00:00:00 2001 From: rakdver Date: Fri, 26 Jan 2007 19:33:04 +0000 Subject: [PATCH] * tree-data-ref.c (dump_subscript): Use dump_conflict_function. (compute_subscript_distance, initialize_data_dependence_relation, finalize_ddr_dependent, analyze_ziv_subscript, analyze_siv_subscript_cst_affine, compute_overlap_steps_for_affine_univar, compute_overlap_steps_for_affine_1_2, analyze_subscript_affine_affine, analyze_siv_subscript, analyze_miv_subscript, analyze_overlapping_iterations, subscript_dependence_tester_1, compute_self_dependence, free_dependence_relation): Work with affine_fn instead of chrecs. (dump_affine_function, dump_conflict_function, affine_function_equal_p, common_affine_function, affine_function_base, affine_function_constant_p, affine_fn_op, affine_fn_plus, affine_fn_minus, affine_fn_free, conflict_fn_not_known, conflict_fn_no_dependence, free_conflict_function, free_subscripts, conflict_fn, affine_fn_cst, affine_fn_univar): New functions. (all_chrecs_equal_p): Removed. * tree-data-ref.h (affine_fn, conflict_function): New types. (struct subscript): Change type of conflicting_iterations_in_a and conflicting_iterations_in_b. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@121212 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/ChangeLog | 23 ++ gcc/tree-data-ref.c | 713 ++++++++++++++++++++++++++++++++++------------------ gcc/tree-data-ref.h | 27 +- 3 files changed, 522 insertions(+), 241 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 9248b0c508a..19e183db6f1 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,26 @@ +2007-01-26 Zdenek Dvorak + + * tree-data-ref.c (dump_subscript): Use dump_conflict_function. + (compute_subscript_distance, initialize_data_dependence_relation, + finalize_ddr_dependent, analyze_ziv_subscript, + analyze_siv_subscript_cst_affine, + compute_overlap_steps_for_affine_univar, + compute_overlap_steps_for_affine_1_2, analyze_subscript_affine_affine, + analyze_siv_subscript, analyze_miv_subscript, + analyze_overlapping_iterations, subscript_dependence_tester_1, + compute_self_dependence, free_dependence_relation): Work + with affine_fn instead of chrecs. + (dump_affine_function, dump_conflict_function, affine_function_equal_p, + common_affine_function, affine_function_base, + affine_function_constant_p, affine_fn_op, affine_fn_plus, + affine_fn_minus, affine_fn_free, conflict_fn_not_known, + conflict_fn_no_dependence, free_conflict_function, free_subscripts, + conflict_fn, affine_fn_cst, affine_fn_univar): New functions. + (all_chrecs_equal_p): Removed. + * tree-data-ref.h (affine_fn, conflict_function): New types. + (struct subscript): Change type of conflicting_iterations_in_a + and conflicting_iterations_in_b. + 2007-01-26 Steve Ellcey PR other/30182 diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c index 4d60da027bb..2da59db43ff 100644 --- a/gcc/tree-data-ref.c +++ b/gcc/tree-data-ref.c @@ -626,35 +626,66 @@ dump_data_reference (FILE *outf, fprintf (outf, ")\n"); } +/* Dumps the affine function described by FN to the file OUTF. */ + +static void +dump_affine_function (FILE *outf, affine_fn fn) +{ + unsigned i; + tree coef; + + print_generic_expr (outf, VEC_index (tree, fn, 0), TDF_SLIM); + for (i = 1; VEC_iterate (tree, fn, i, coef); i++) + { + fprintf (outf, " + "); + print_generic_expr (outf, coef, TDF_SLIM); + fprintf (outf, " * x_%u", i); + } +} + +/* Dumps the conflict function CF to the file OUTF. */ + +static void +dump_conflict_function (FILE *outf, conflict_function *cf) +{ + unsigned i; + + if (cf->n == NO_DEPENDENCE) + fprintf (outf, "no dependence\n"); + else if (cf->n == NOT_KNOWN) + fprintf (outf, "not known\n"); + else + { + for (i = 0; i < cf->n; i++) + { + fprintf (outf, "["); + dump_affine_function (outf, cf->fns[i]); + fprintf (outf, "]\n"); + } + } +} + /* Dump function for a SUBSCRIPT structure. */ void dump_subscript (FILE *outf, struct subscript *subscript) { - tree chrec = SUB_CONFLICTS_IN_A (subscript); + conflict_function *cf = SUB_CONFLICTS_IN_A (subscript); fprintf (outf, "\n (subscript \n"); fprintf (outf, " iterations_that_access_an_element_twice_in_A: "); - print_generic_stmt (outf, chrec, 0); - if (chrec == chrec_known) - fprintf (outf, " (no dependence)\n"); - else if (chrec_contains_undetermined (chrec)) - fprintf (outf, " (don't know)\n"); - else + dump_conflict_function (outf, cf); + if (CF_NONTRIVIAL_P (cf)) { tree last_iteration = SUB_LAST_CONFLICT (subscript); fprintf (outf, " last_conflict: "); print_generic_stmt (outf, last_iteration, 0); } - chrec = SUB_CONFLICTS_IN_B (subscript); + cf = SUB_CONFLICTS_IN_B (subscript); fprintf (outf, " iterations_that_access_an_element_twice_in_B: "); - print_generic_stmt (outf, chrec, 0); - if (chrec == chrec_known) - fprintf (outf, " (no dependence)\n"); - else if (chrec_contains_undetermined (chrec)) - fprintf (outf, " (don't know)\n"); - else + dump_conflict_function (outf, cf); + if (CF_NONTRIVIAL_P (cf)) { tree last_iteration = SUB_LAST_CONFLICT (subscript); fprintf (outf, " last_conflict: "); @@ -2003,80 +2034,193 @@ create_data_ref (tree memref, tree stmt, bool is_read) return dr; } +/* Returns true if FNA == FNB. */ + +static bool +affine_function_equal_p (affine_fn fna, affine_fn fnb) +{ + unsigned i, n = VEC_length (tree, fna); -/* Returns true when all the functions of a tree_vec CHREC are the - same. */ + gcc_assert (n == VEC_length (tree, fnb)); -static bool -all_chrecs_equal_p (tree chrec) + for (i = 0; i < n; i++) + if (!operand_equal_p (VEC_index (tree, fna, i), + VEC_index (tree, fnb, i), 0)) + return false; + + return true; +} + +/* If all the functions in CF are the same, returns one of them, + otherwise returns NULL. */ + +static affine_fn +common_affine_function (conflict_function *cf) { - int j; + unsigned i; + affine_fn comm; + + if (!CF_NONTRIVIAL_P (cf)) + return NULL; + + comm = cf->fns[0]; + + for (i = 1; i < cf->n; i++) + if (!affine_function_equal_p (comm, cf->fns[i])) + return NULL; + + return comm; +} - for (j = 0; j < TREE_VEC_LENGTH (chrec) - 1; j++) - if (!eq_evolutions_p (TREE_VEC_ELT (chrec, j), - TREE_VEC_ELT (chrec, j + 1))) +/* Returns the base of the affine function FN. */ + +static tree +affine_function_base (affine_fn fn) +{ + return VEC_index (tree, fn, 0); +} + +/* Returns true if FN is a constant. */ + +static bool +affine_function_constant_p (affine_fn fn) +{ + unsigned i; + tree coef; + + for (i = 1; VEC_iterate (tree, fn, i, coef); i++) + if (!integer_zerop (coef)) return false; return true; } +/* Applies operation OP on affine functions FNA and FNB, and returns the + result. */ + +static affine_fn +affine_fn_op (enum tree_code op, affine_fn fna, affine_fn fnb) +{ + unsigned i, n, m; + affine_fn ret; + tree coef; + + if (VEC_length (tree, fnb) > VEC_length (tree, fna)) + { + n = VEC_length (tree, fna); + m = VEC_length (tree, fnb); + } + else + { + n = VEC_length (tree, fnb); + m = VEC_length (tree, fna); + } + + ret = VEC_alloc (tree, heap, m); + for (i = 0; i < n; i++) + VEC_quick_push (tree, ret, + fold_build2 (op, integer_type_node, + VEC_index (tree, fna, i), + VEC_index (tree, fnb, i))); + + for (; VEC_iterate (tree, fna, i, coef); i++) + VEC_quick_push (tree, ret, + fold_build2 (op, integer_type_node, + coef, integer_zero_node)); + for (; VEC_iterate (tree, fnb, i, coef); i++) + VEC_quick_push (tree, ret, + fold_build2 (op, integer_type_node, + integer_zero_node, coef)); + + return ret; +} + +/* Returns the sum of affine functions FNA and FNB. */ + +static affine_fn +affine_fn_plus (affine_fn fna, affine_fn fnb) +{ + return affine_fn_op (PLUS_EXPR, fna, fnb); +} + +/* Returns the difference of affine functions FNA and FNB. */ + +static affine_fn +affine_fn_minus (affine_fn fna, affine_fn fnb) +{ + return affine_fn_op (MINUS_EXPR, fna, fnb); +} + +/* Frees affine function FN. */ + +static void +affine_fn_free (affine_fn fn) +{ + VEC_free (tree, heap, fn); +} + /* Determine for each subscript in the data dependence relation DDR the distance. */ static void compute_subscript_distance (struct data_dependence_relation *ddr) { + conflict_function *cf_a, *cf_b; + affine_fn fn_a, fn_b, diff; + if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE) { unsigned int i; for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) { - tree conflicts_a, conflicts_b, difference; struct subscript *subscript; subscript = DDR_SUBSCRIPT (ddr, i); - conflicts_a = SUB_CONFLICTS_IN_A (subscript); - conflicts_b = SUB_CONFLICTS_IN_B (subscript); + cf_a = SUB_CONFLICTS_IN_A (subscript); + cf_b = SUB_CONFLICTS_IN_B (subscript); - if (TREE_CODE (conflicts_a) == TREE_VEC) + fn_a = common_affine_function (cf_a); + fn_b = common_affine_function (cf_b); + if (!fn_a || !fn_b) { - if (!all_chrecs_equal_p (conflicts_a)) - { - SUB_DISTANCE (subscript) = chrec_dont_know; - return; - } - else - conflicts_a = TREE_VEC_ELT (conflicts_a, 0); - } - - if (TREE_CODE (conflicts_b) == TREE_VEC) - { - if (!all_chrecs_equal_p (conflicts_b)) - { - SUB_DISTANCE (subscript) = chrec_dont_know; - return; - } - else - conflicts_b = TREE_VEC_ELT (conflicts_b, 0); + SUB_DISTANCE (subscript) = chrec_dont_know; + return; } - - conflicts_b = chrec_convert (integer_type_node, conflicts_b, - NULL_TREE); - conflicts_a = chrec_convert (integer_type_node, conflicts_a, - NULL_TREE); - difference = chrec_fold_minus - (integer_type_node, conflicts_b, conflicts_a); - - if (evolution_function_is_constant_p (difference)) - SUB_DISTANCE (subscript) = difference; + diff = affine_fn_minus (fn_a, fn_b); + if (affine_function_constant_p (diff)) + SUB_DISTANCE (subscript) = affine_function_base (diff); else SUB_DISTANCE (subscript) = chrec_dont_know; + + affine_fn_free (diff); } } } +/* Returns the conflict function for "unknown". */ + +static conflict_function * +conflict_fn_not_known (void) +{ + conflict_function *fn = XCNEW (conflict_function); + fn->n = NOT_KNOWN; + + return fn; +} + +/* Returns the conflict function for "independent". */ + +static conflict_function * +conflict_fn_no_dependence (void) +{ + conflict_function *fn = XCNEW (conflict_function); + fn->n = NO_DEPENDENCE; + + return fn; +} + /* Initialize a data dependence relation between data accesses A and B. NB_LOOPS is the number of loops surrounding the references: the size of the classic distance/direction vectors. */ @@ -2141,8 +2285,8 @@ initialize_data_dependence_relation (struct data_reference *a, struct subscript *subscript; subscript = XNEW (struct subscript); - SUB_CONFLICTS_IN_A (subscript) = chrec_dont_know; - SUB_CONFLICTS_IN_B (subscript) = chrec_dont_know; + SUB_CONFLICTS_IN_A (subscript) = conflict_fn_not_known (); + SUB_CONFLICTS_IN_B (subscript) = conflict_fn_not_known (); SUB_LAST_CONFLICT (subscript) = chrec_dont_know; SUB_DISTANCE (subscript) = chrec_dont_know; VEC_safe_push (subscript_p, heap, DDR_SUBSCRIPTS (res), subscript); @@ -2151,6 +2295,37 @@ initialize_data_dependence_relation (struct data_reference *a, return res; } +/* Frees memory used by the conflict function F. */ + +static void +free_conflict_function (conflict_function *f) +{ + unsigned i; + + if (CF_NONTRIVIAL_P (f)) + { + for (i = 0; i < f->n; i++) + affine_fn_free (f->fns[i]); + } + free (f); +} + +/* Frees memory used by SUBSCRIPTS. */ + +static void +free_subscripts (VEC (subscript_p, heap) *subscripts) +{ + unsigned i; + subscript_p s; + + for (i = 0; VEC_iterate (subscript_p, subscripts, i, s); i++) + { + free_conflict_function (s->conflicting_iterations_in_a); + free_conflict_function (s->conflicting_iterations_in_b); + } + VEC_free (subscript_p, heap, subscripts); +} + /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap description. */ @@ -2166,7 +2341,7 @@ finalize_ddr_dependent (struct data_dependence_relation *ddr, } DDR_ARE_DEPENDENT (ddr) = chrec; - VEC_free (subscript_p, heap, DDR_SUBSCRIPTS (ddr)); + free_subscripts (DDR_SUBSCRIPTS (ddr)); } /* The dependence relation DDR cannot be represented by a distance @@ -2233,6 +2408,52 @@ siv_subscript_p (tree chrec_a, return false; } +/* Creates a conflict function with N dimensions. The affine functions + in each dimension follow. */ + +static conflict_function * +conflict_fn (unsigned n, ...) +{ + unsigned i; + conflict_function *ret = XCNEW (conflict_function); + va_list ap; + + va_start(ap, n); + + ret->n = n; + for (i = 0; i < n; i++) + ret->fns[i] = va_arg (ap, affine_fn); + va_end(ap); + + return ret; +} + +/* Returns constant affine function with value CST. */ + +static affine_fn +affine_fn_cst (tree cst) +{ + affine_fn fn = VEC_alloc (tree, heap, 1); + VEC_quick_push (tree, fn, cst); + return fn; +} + +/* Returns affine function with single variable, CST + COEF * x_DIM. */ + +static affine_fn +affine_fn_univar (tree cst, unsigned dim, tree coef) +{ + affine_fn fn = VEC_alloc (tree, heap, dim + 1); + unsigned i; + + gcc_assert (dim > 0); + VEC_quick_push (tree, fn, cst); + for (i = 1; i < dim; i++) + VEC_quick_push (tree, fn, integer_zero_node); + VEC_quick_push (tree, fn, coef); + return fn; +} + /* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and *OVERLAPS_B are initialized to the functions that describe the relation between the elements accessed twice by CHREC_A and @@ -2243,8 +2464,8 @@ siv_subscript_p (tree chrec_a, static void analyze_ziv_subscript (tree chrec_a, tree chrec_b, - tree *overlaps_a, - tree *overlaps_b, + conflict_function **overlaps_a, + conflict_function **overlaps_b, tree *last_conflicts) { tree difference; @@ -2264,16 +2485,16 @@ analyze_ziv_subscript (tree chrec_a, { /* The difference is equal to zero: the accessed index overlaps for each iteration in the loop. */ - *overlaps_a = integer_zero_node; - *overlaps_b = integer_zero_node; + *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node)); + *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node)); *last_conflicts = chrec_dont_know; dependence_stats.num_ziv_dependent++; } else { /* The accesses do not overlap. */ - *overlaps_a = chrec_known; - *overlaps_b = chrec_known; + *overlaps_a = conflict_fn_no_dependence (); + *overlaps_b = conflict_fn_no_dependence (); *last_conflicts = integer_zero_node; dependence_stats.num_ziv_independent++; } @@ -2285,8 +2506,8 @@ analyze_ziv_subscript (tree chrec_a, if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "ziv test failed: difference is non-integer.\n"); - *overlaps_a = chrec_dont_know; - *overlaps_b = chrec_dont_know; + *overlaps_a = conflict_fn_not_known (); + *overlaps_b = conflict_fn_not_known (); *last_conflicts = chrec_dont_know; dependence_stats.num_ziv_unimplemented++; break; @@ -2330,12 +2551,12 @@ get_number_of_iters_for_loop (int loopnum) static void analyze_siv_subscript_cst_affine (tree chrec_a, tree chrec_b, - tree *overlaps_a, - tree *overlaps_b, + conflict_function **overlaps_a, + conflict_function **overlaps_b, tree *last_conflicts) { bool value0, value1, value2; - tree difference; + tree difference, tmp; chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE); chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE); @@ -2348,8 +2569,8 @@ analyze_siv_subscript_cst_affine (tree chrec_a, fprintf (dump_file, "siv test failed: chrec is not positive.\n"); dependence_stats.num_siv_unimplemented++; - *overlaps_a = chrec_dont_know; - *overlaps_b = chrec_dont_know; + *overlaps_a = conflict_fn_not_known (); + *overlaps_b = conflict_fn_not_known (); *last_conflicts = chrec_dont_know; return; } @@ -2362,8 +2583,8 @@ analyze_siv_subscript_cst_affine (tree chrec_a, if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "siv test failed: chrec not positive.\n"); - *overlaps_a = chrec_dont_know; - *overlaps_b = chrec_dont_know; + *overlaps_a = conflict_fn_not_known (); + *overlaps_b = conflict_fn_not_known (); *last_conflicts = chrec_dont_know; dependence_stats.num_siv_unimplemented++; return; @@ -2382,12 +2603,13 @@ analyze_siv_subscript_cst_affine (tree chrec_a, tree numiter; int loopnum = CHREC_VARIABLE (chrec_b); - *overlaps_a = integer_zero_node; - *overlaps_b = fold_build2 (EXACT_DIV_EXPR, integer_type_node, - fold_build1 (ABS_EXPR, - integer_type_node, - difference), - CHREC_RIGHT (chrec_b)); + *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node)); + tmp = fold_build2 (EXACT_DIV_EXPR, integer_type_node, + fold_build1 (ABS_EXPR, + integer_type_node, + difference), + CHREC_RIGHT (chrec_b)); + *overlaps_b = conflict_fn (1, affine_fn_cst (tmp)); *last_conflicts = integer_one_node; @@ -2396,11 +2618,13 @@ analyze_siv_subscript_cst_affine (tree chrec_a, numiter = get_number_of_iters_for_loop (loopnum); if (numiter != NULL_TREE - && TREE_CODE (*overlaps_b) == INTEGER_CST - && tree_int_cst_lt (numiter, *overlaps_b)) + && TREE_CODE (tmp) == INTEGER_CST + && tree_int_cst_lt (numiter, tmp)) { - *overlaps_a = chrec_known; - *overlaps_b = chrec_known; + free_conflict_function (*overlaps_a); + free_conflict_function (*overlaps_b); + *overlaps_a = conflict_fn_no_dependence (); + *overlaps_b = conflict_fn_no_dependence (); *last_conflicts = integer_zero_node; dependence_stats.num_siv_independent++; return; @@ -2413,8 +2637,8 @@ analyze_siv_subscript_cst_affine (tree chrec_a, no overlaps. */ else { - *overlaps_a = chrec_known; - *overlaps_b = chrec_known; + *overlaps_a = conflict_fn_no_dependence (); + *overlaps_b = conflict_fn_no_dependence (); *last_conflicts = integer_zero_node; dependence_stats.num_siv_independent++; return; @@ -2428,8 +2652,8 @@ analyze_siv_subscript_cst_affine (tree chrec_a, chrec_b = {10, +, -1} In this case, chrec_a will not overlap with chrec_b. */ - *overlaps_a = chrec_known; - *overlaps_b = chrec_known; + *overlaps_a = conflict_fn_no_dependence (); + *overlaps_b = conflict_fn_no_dependence (); *last_conflicts = integer_zero_node; dependence_stats.num_siv_independent++; return; @@ -2443,8 +2667,8 @@ analyze_siv_subscript_cst_affine (tree chrec_a, if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "siv test failed: chrec not positive.\n"); - *overlaps_a = chrec_dont_know; - *overlaps_b = chrec_dont_know; + *overlaps_a = conflict_fn_not_known (); + *overlaps_b = conflict_fn_not_known (); *last_conflicts = chrec_dont_know; dependence_stats.num_siv_unimplemented++; return; @@ -2462,10 +2686,11 @@ analyze_siv_subscript_cst_affine (tree chrec_a, tree numiter; int loopnum = CHREC_VARIABLE (chrec_b); - *overlaps_a = integer_zero_node; - *overlaps_b = fold_build2 (EXACT_DIV_EXPR, - integer_type_node, difference, - CHREC_RIGHT (chrec_b)); + *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node)); + tmp = fold_build2 (EXACT_DIV_EXPR, + integer_type_node, difference, + CHREC_RIGHT (chrec_b)); + *overlaps_b = conflict_fn (1, affine_fn_cst (tmp)); *last_conflicts = integer_one_node; /* Perform weak-zero siv test to see if overlap is @@ -2473,11 +2698,13 @@ analyze_siv_subscript_cst_affine (tree chrec_a, numiter = get_number_of_iters_for_loop (loopnum); if (numiter != NULL_TREE - && TREE_CODE (*overlaps_b) == INTEGER_CST - && tree_int_cst_lt (numiter, *overlaps_b)) + && TREE_CODE (tmp) == INTEGER_CST + && tree_int_cst_lt (numiter, tmp)) { - *overlaps_a = chrec_known; - *overlaps_b = chrec_known; + free_conflict_function (*overlaps_a); + free_conflict_function (*overlaps_b); + *overlaps_a = conflict_fn_no_dependence (); + *overlaps_b = conflict_fn_no_dependence (); *last_conflicts = integer_zero_node; dependence_stats.num_siv_independent++; return; @@ -2490,8 +2717,8 @@ analyze_siv_subscript_cst_affine (tree chrec_a, are no overlaps. */ else { - *overlaps_a = chrec_known; - *overlaps_b = chrec_known; + *overlaps_a = conflict_fn_no_dependence (); + *overlaps_b = conflict_fn_no_dependence (); *last_conflicts = integer_zero_node; dependence_stats.num_siv_independent++; return; @@ -2504,8 +2731,8 @@ analyze_siv_subscript_cst_affine (tree chrec_a, chrec_b = {4, +, 1} In this case, chrec_a will not overlap with chrec_b. */ - *overlaps_a = chrec_known; - *overlaps_b = chrec_known; + *overlaps_a = conflict_fn_no_dependence (); + *overlaps_b = conflict_fn_no_dependence (); *last_conflicts = integer_zero_node; dependence_stats.num_siv_independent++; return; @@ -2541,7 +2768,8 @@ initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult) static void compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b, - tree *overlaps_a, tree *overlaps_b, + affine_fn *overlaps_a, + affine_fn *overlaps_b, tree *last_conflicts, int dim) { if (((step_a > 0 && step_b > 0) @@ -2558,24 +2786,23 @@ compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b, tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b)); last_conflict = tau2; - *overlaps_a = build_polynomial_chrec - (dim, integer_zero_node, - build_int_cst (NULL_TREE, step_overlaps_a)); - *overlaps_b = build_polynomial_chrec - (dim, integer_zero_node, - build_int_cst (NULL_TREE, step_overlaps_b)); + *overlaps_a = affine_fn_univar (integer_zero_node, dim, + build_int_cst (NULL_TREE, + step_overlaps_a)); + *overlaps_b = affine_fn_univar (integer_zero_node, dim, + build_int_cst (NULL_TREE, + step_overlaps_b)); *last_conflicts = build_int_cst (NULL_TREE, last_conflict); } else { - *overlaps_a = integer_zero_node; - *overlaps_b = integer_zero_node; + *overlaps_a = affine_fn_cst (integer_zero_node); + *overlaps_b = affine_fn_cst (integer_zero_node); *last_conflicts = integer_zero_node; } } - /* Solves the special case of a Diophantine equation where CHREC_A is an affine bivariate function, and CHREC_B is an affine univariate function. For example, @@ -2593,16 +2820,19 @@ compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b, static void compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b, - tree *overlaps_a, tree *overlaps_b, + conflict_function **overlaps_a, + conflict_function **overlaps_b, tree *last_conflicts) { bool xz_p, yz_p, xyz_p; int step_x, step_y, step_z; int niter_x, niter_y, niter_z, niter; tree numiter_x, numiter_y, numiter_z; - tree overlaps_a_xz, overlaps_b_xz, last_conflicts_xz; - tree overlaps_a_yz, overlaps_b_yz, last_conflicts_yz; - tree overlaps_a_xyz, overlaps_b_xyz, last_conflicts_xyz; + affine_fn overlaps_a_xz, overlaps_b_xz; + affine_fn overlaps_a_yz, overlaps_b_yz; + affine_fn overlaps_a_xyz, overlaps_b_xyz; + affine_fn ova1, ova2, ovb; + tree last_conflicts_xz, last_conflicts_yz, last_conflicts_xyz; step_x = int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a))); step_y = int_cst_value (CHREC_RIGHT (chrec_a)); @@ -2618,8 +2848,8 @@ compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b, if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "overlap steps test failed: no iteration counts.\n"); - *overlaps_a = chrec_dont_know; - *overlaps_b = chrec_dont_know; + *overlaps_a = conflict_fn_not_known (); + *overlaps_b = conflict_fn_not_known (); *last_conflicts = chrec_dont_know; return; } @@ -2651,67 +2881,61 @@ compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b, if (xz_p || yz_p || xyz_p) { - *overlaps_a = make_tree_vec (2); - TREE_VEC_ELT (*overlaps_a, 0) = integer_zero_node; - TREE_VEC_ELT (*overlaps_a, 1) = integer_zero_node; - *overlaps_b = integer_zero_node; + ova1 = affine_fn_cst (integer_zero_node); + ova2 = affine_fn_cst (integer_zero_node); + ovb = affine_fn_cst (integer_zero_node); if (xz_p) { - tree t0 = chrec_convert (integer_type_node, - TREE_VEC_ELT (*overlaps_a, 0), NULL_TREE); - tree t1 = chrec_convert (integer_type_node, overlaps_a_xz, - NULL_TREE); - tree t2 = chrec_convert (integer_type_node, *overlaps_b, - NULL_TREE); - tree t3 = chrec_convert (integer_type_node, overlaps_b_xz, - NULL_TREE); - - TREE_VEC_ELT (*overlaps_a, 0) = chrec_fold_plus (integer_type_node, - t0, t1); - *overlaps_b = chrec_fold_plus (integer_type_node, t2, t3); + affine_fn t0 = ova1; + affine_fn t2 = ovb; + + ova1 = affine_fn_plus (ova1, overlaps_a_xz); + ovb = affine_fn_plus (ovb, overlaps_b_xz); + affine_fn_free (t0); + affine_fn_free (t2); *last_conflicts = last_conflicts_xz; } if (yz_p) { - tree t0 = chrec_convert (integer_type_node, - TREE_VEC_ELT (*overlaps_a, 1), NULL_TREE); - tree t1 = chrec_convert (integer_type_node, overlaps_a_yz, NULL_TREE); - tree t2 = chrec_convert (integer_type_node, *overlaps_b, NULL_TREE); - tree t3 = chrec_convert (integer_type_node, overlaps_b_yz, NULL_TREE); - - TREE_VEC_ELT (*overlaps_a, 1) = chrec_fold_plus (integer_type_node, - t0, t1); - *overlaps_b = chrec_fold_plus (integer_type_node, t2, t3); + affine_fn t0 = ova2; + affine_fn t2 = ovb; + + ova2 = affine_fn_plus (ova2, overlaps_a_yz); + ovb = affine_fn_plus (ovb, overlaps_b_yz); + affine_fn_free (t0); + affine_fn_free (t2); *last_conflicts = last_conflicts_yz; } if (xyz_p) { - tree t0 = chrec_convert (integer_type_node, - TREE_VEC_ELT (*overlaps_a, 0), NULL_TREE); - tree t1 = chrec_convert (integer_type_node, overlaps_a_xyz, - NULL_TREE); - tree t2 = chrec_convert (integer_type_node, - TREE_VEC_ELT (*overlaps_a, 1), NULL_TREE); - tree t3 = chrec_convert (integer_type_node, overlaps_a_xyz, - NULL_TREE); - tree t4 = chrec_convert (integer_type_node, *overlaps_b, NULL_TREE); - tree t5 = chrec_convert (integer_type_node, overlaps_b_xyz, - NULL_TREE); - - TREE_VEC_ELT (*overlaps_a, 0) = chrec_fold_plus (integer_type_node, - t0, t1); - TREE_VEC_ELT (*overlaps_a, 1) = chrec_fold_plus (integer_type_node, - t2, t3); - *overlaps_b = chrec_fold_plus (integer_type_node, t4, t5); + affine_fn t0 = ova1; + affine_fn t2 = ova2; + affine_fn t4 = ovb; + + ova1 = affine_fn_plus (ova1, overlaps_a_xyz); + ova2 = affine_fn_plus (ova2, overlaps_a_xyz); + ovb = affine_fn_plus (ovb, overlaps_b_xyz); + affine_fn_free (t0); + affine_fn_free (t2); + affine_fn_free (t4); *last_conflicts = last_conflicts_xyz; } + *overlaps_a = conflict_fn (2, ova1, ova2); + *overlaps_b = conflict_fn (1, ovb); } else { - *overlaps_a = integer_zero_node; - *overlaps_b = integer_zero_node; + *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node)); + *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node)); *last_conflicts = integer_zero_node; } + + affine_fn_free (overlaps_a_xz); + affine_fn_free (overlaps_b_xz); + affine_fn_free (overlaps_a_yz); + affine_fn_free (overlaps_b_yz); + affine_fn_free (overlaps_a_xyz); + affine_fn_free (overlaps_b_xyz); } /* Determines the overlapping elements due to accesses CHREC_A and @@ -2722,8 +2946,8 @@ compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b, static void analyze_subscript_affine_affine (tree chrec_a, tree chrec_b, - tree *overlaps_a, - tree *overlaps_b, + conflict_function **overlaps_a, + conflict_function **overlaps_b, tree *last_conflicts) { unsigned nb_vars_a, nb_vars_b, dim; @@ -2735,8 +2959,8 @@ analyze_subscript_affine_affine (tree chrec_a, { /* The accessed index overlaps for each iteration in the loop. */ - *overlaps_a = integer_zero_node; - *overlaps_b = integer_zero_node; + *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node)); + *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node)); *last_conflicts = chrec_dont_know; return; } @@ -2781,6 +3005,7 @@ analyze_subscript_affine_affine (tree chrec_a, int step_a, step_b; int niter, niter_a, niter_b; tree numiter_a, numiter_b; + affine_fn ova, ovb; numiter_a = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a)); numiter_b = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b)); @@ -2788,8 +3013,8 @@ analyze_subscript_affine_affine (tree chrec_a, { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n"); - *overlaps_a = chrec_dont_know; - *overlaps_b = chrec_dont_know; + *overlaps_a = conflict_fn_not_known (); + *overlaps_b = conflict_fn_not_known (); *last_conflicts = chrec_dont_know; goto end_analyze_subs_aa; } @@ -2802,8 +3027,10 @@ analyze_subscript_affine_affine (tree chrec_a, step_b = int_cst_value (CHREC_RIGHT (chrec_b)); compute_overlap_steps_for_affine_univar (niter, step_a, step_b, - overlaps_a, overlaps_b, + &ova, &ovb, last_conflicts, 1); + *overlaps_a = conflict_fn (1, ova); + *overlaps_b = conflict_fn (1, ovb); } else if (nb_vars_a == 2 && nb_vars_b == 1) @@ -2818,8 +3045,8 @@ analyze_subscript_affine_affine (tree chrec_a, { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "affine-affine test failed: too many variables.\n"); - *overlaps_a = chrec_dont_know; - *overlaps_b = chrec_dont_know; + *overlaps_a = conflict_fn_not_known (); + *overlaps_b = conflict_fn_not_known (); *last_conflicts = chrec_dont_know; } goto end_analyze_subs_aa; @@ -2840,8 +3067,8 @@ analyze_subscript_affine_affine (tree chrec_a, don't know. */ if (gcd_alpha_beta == 0) { - *overlaps_a = chrec_dont_know; - *overlaps_b = chrec_dont_know; + *overlaps_a = conflict_fn_not_known (); + *overlaps_b = conflict_fn_not_known (); *last_conflicts = chrec_dont_know; goto end_analyze_subs_aa; } @@ -2851,8 +3078,8 @@ analyze_subscript_affine_affine (tree chrec_a, { /* The "gcd-test" has determined that there is no integer solution, i.e. there is no dependence. */ - *overlaps_a = chrec_known; - *overlaps_b = chrec_known; + *overlaps_a = conflict_fn_no_dependence (); + *overlaps_b = conflict_fn_no_dependence (); *last_conflicts = integer_zero_node; } @@ -2896,8 +3123,8 @@ analyze_subscript_affine_affine (tree chrec_a, { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n"); - *overlaps_a = chrec_dont_know; - *overlaps_b = chrec_dont_know; + *overlaps_a = conflict_fn_not_known (); + *overlaps_b = conflict_fn_not_known (); *last_conflicts = chrec_dont_know; goto end_analyze_subs_aa; } @@ -2918,8 +3145,8 @@ analyze_subscript_affine_affine (tree chrec_a, FIXME: The case "i0 > nb_iterations, j0 > nb_iterations" falls in here, but for the moment we don't look at the upper bound of the iteration domain. */ - *overlaps_a = chrec_known; - *overlaps_b = chrec_known; + *overlaps_a = conflict_fn_no_dependence (); + *overlaps_b = conflict_fn_no_dependence (); *last_conflicts = integer_zero_node; } @@ -2954,20 +3181,22 @@ analyze_subscript_affine_affine (tree chrec_a, loop, there is no dependence. */ if (x0 > niter || y0 > niter) { - *overlaps_a = chrec_known; - *overlaps_b = chrec_known; + *overlaps_a = conflict_fn_no_dependence (); + *overlaps_b = conflict_fn_no_dependence (); *last_conflicts = integer_zero_node; } else { - *overlaps_a = build_polynomial_chrec - (1, - build_int_cst (NULL_TREE, x0), - build_int_cst (NULL_TREE, i1)); - *overlaps_b = build_polynomial_chrec - (1, - build_int_cst (NULL_TREE, y0), - build_int_cst (NULL_TREE, j1)); + *overlaps_a + = conflict_fn (1, + affine_fn_univar (build_int_cst (NULL_TREE, x0), + 1, + build_int_cst (NULL_TREE, i1))); + *overlaps_b + = conflict_fn (1, + affine_fn_univar (build_int_cst (NULL_TREE, y0), + 1, + build_int_cst (NULL_TREE, j1))); *last_conflicts = build_int_cst (NULL_TREE, last_conflict); } } @@ -2977,8 +3206,8 @@ analyze_subscript_affine_affine (tree chrec_a, iteration domain for j is not checked. */ if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "affine-affine test failed: unimplemented.\n"); - *overlaps_a = chrec_dont_know; - *overlaps_b = chrec_dont_know; + *overlaps_a = conflict_fn_not_known (); + *overlaps_b = conflict_fn_not_known (); *last_conflicts = chrec_dont_know; } } @@ -2989,8 +3218,8 @@ analyze_subscript_affine_affine (tree chrec_a, iteration domain for i is not checked. */ if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "affine-affine test failed: unimplemented.\n"); - *overlaps_a = chrec_dont_know; - *overlaps_b = chrec_dont_know; + *overlaps_a = conflict_fn_not_known (); + *overlaps_b = conflict_fn_not_known (); *last_conflicts = chrec_dont_know; } } @@ -2999,8 +3228,8 @@ analyze_subscript_affine_affine (tree chrec_a, { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "affine-affine test failed: unimplemented.\n"); - *overlaps_a = chrec_dont_know; - *overlaps_b = chrec_dont_know; + *overlaps_a = conflict_fn_not_known (); + *overlaps_b = conflict_fn_not_known (); *last_conflicts = chrec_dont_know; } } @@ -3009,8 +3238,8 @@ analyze_subscript_affine_affine (tree chrec_a, { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "affine-affine test failed: unimplemented.\n"); - *overlaps_a = chrec_dont_know; - *overlaps_b = chrec_dont_know; + *overlaps_a = conflict_fn_not_known (); + *overlaps_b = conflict_fn_not_known (); *last_conflicts = chrec_dont_know; } @@ -3018,9 +3247,9 @@ end_analyze_subs_aa: if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, " (overlaps_a = "); - print_generic_expr (dump_file, *overlaps_a, 0); + dump_conflict_function (dump_file, *overlaps_a); fprintf (dump_file, ")\n (overlaps_b = "); - print_generic_expr (dump_file, *overlaps_b, 0); + dump_conflict_function (dump_file, *overlaps_b); fprintf (dump_file, ")\n"); fprintf (dump_file, ")\n"); } @@ -3080,8 +3309,8 @@ can_use_analyze_subscript_affine_affine (tree *chrec_a, tree *chrec_b) static void analyze_siv_subscript (tree chrec_a, tree chrec_b, - tree *overlaps_a, - tree *overlaps_b, + conflict_function **overlaps_a, + conflict_function **overlaps_b, tree *last_conflicts) { dependence_stats.num_siv++; @@ -3109,11 +3338,11 @@ analyze_siv_subscript (tree chrec_a, overlaps_a, overlaps_b, last_conflicts); - if (*overlaps_a == chrec_dont_know - || *overlaps_b == chrec_dont_know) + if (CF_NOT_KNOWN_P (*overlaps_a) + || CF_NOT_KNOWN_P (*overlaps_b)) dependence_stats.num_siv_unimplemented++; - else if (*overlaps_a == chrec_known - || *overlaps_b == chrec_known) + else if (CF_NO_DEPENDENCE_P (*overlaps_a) + || CF_NO_DEPENDENCE_P (*overlaps_b)) dependence_stats.num_siv_independent++; else dependence_stats.num_siv_dependent++; @@ -3128,11 +3357,11 @@ analyze_siv_subscript (tree chrec_a, Compute it properly. */ *last_conflicts = chrec_dont_know; - if (*overlaps_a == chrec_dont_know - || *overlaps_b == chrec_dont_know) + if (CF_NOT_KNOWN_P (*overlaps_a) + || CF_NOT_KNOWN_P (*overlaps_b)) dependence_stats.num_siv_unimplemented++; - else if (*overlaps_a == chrec_known - || *overlaps_b == chrec_known) + else if (CF_NO_DEPENDENCE_P (*overlaps_a) + || CF_NO_DEPENDENCE_P (*overlaps_b)) dependence_stats.num_siv_independent++; else dependence_stats.num_siv_dependent++; @@ -3146,8 +3375,8 @@ analyze_siv_subscript (tree chrec_a, siv_subscript_dontknow:; if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "siv test failed: unimplemented.\n"); - *overlaps_a = chrec_dont_know; - *overlaps_b = chrec_dont_know; + *overlaps_a = conflict_fn_not_known (); + *overlaps_b = conflict_fn_not_known (); *last_conflicts = chrec_dont_know; dependence_stats.num_siv_unimplemented++; } @@ -3198,8 +3427,8 @@ chrec_steps_divide_constant_p (tree chrec, static void analyze_miv_subscript (tree chrec_a, tree chrec_b, - tree *overlaps_a, - tree *overlaps_b, + conflict_function **overlaps_a, + conflict_function **overlaps_b, tree *last_conflicts) { /* FIXME: This is a MIV subscript, not yet handled. @@ -3224,8 +3453,8 @@ analyze_miv_subscript (tree chrec_a, { /* Access functions are the same: all the elements are accessed in the same order. */ - *overlaps_a = integer_zero_node; - *overlaps_b = integer_zero_node; + *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node)); + *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node)); *last_conflicts = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a)); dependence_stats.num_miv_dependent++; } @@ -3241,8 +3470,8 @@ analyze_miv_subscript (tree chrec_a, The difference is 1, and the evolution steps are equal to 2, consequently there are no overlapping elements. */ - *overlaps_a = chrec_known; - *overlaps_b = chrec_known; + *overlaps_a = conflict_fn_no_dependence (); + *overlaps_b = conflict_fn_no_dependence (); *last_conflicts = integer_zero_node; dependence_stats.num_miv_independent++; } @@ -3269,11 +3498,11 @@ analyze_miv_subscript (tree chrec_a, analyze_subscript_affine_affine (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts); - if (*overlaps_a == chrec_dont_know - || *overlaps_b == chrec_dont_know) + if (CF_NOT_KNOWN_P (*overlaps_a) + || CF_NOT_KNOWN_P (*overlaps_b)) dependence_stats.num_miv_unimplemented++; - else if (*overlaps_a == chrec_known - || *overlaps_b == chrec_known) + else if (CF_NO_DEPENDENCE_P (*overlaps_a) + || CF_NO_DEPENDENCE_P (*overlaps_b)) dependence_stats.num_miv_independent++; else dependence_stats.num_miv_dependent++; @@ -3285,8 +3514,8 @@ analyze_miv_subscript (tree chrec_a, if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "analyze_miv_subscript test failed: unimplemented.\n"); - *overlaps_a = chrec_dont_know; - *overlaps_b = chrec_dont_know; + *overlaps_a = conflict_fn_not_known (); + *overlaps_b = conflict_fn_not_known (); *last_conflicts = chrec_dont_know; dependence_stats.num_miv_unimplemented++; } @@ -3308,8 +3537,8 @@ analyze_miv_subscript (tree chrec_a, static void analyze_overlapping_iterations (tree chrec_a, tree chrec_b, - tree *overlap_iterations_a, - tree *overlap_iterations_b, + conflict_function **overlap_iterations_a, + conflict_function **overlap_iterations_b, tree *last_conflicts) { dependence_stats.num_subscript_tests++; @@ -3331,8 +3560,8 @@ analyze_overlapping_iterations (tree chrec_a, { dependence_stats.num_subscript_undetermined++; - *overlap_iterations_a = chrec_dont_know; - *overlap_iterations_b = chrec_dont_know; + *overlap_iterations_a = conflict_fn_not_known (); + *overlap_iterations_b = conflict_fn_not_known (); } /* If they are the same chrec, and are affine, they overlap @@ -3341,8 +3570,8 @@ analyze_overlapping_iterations (tree chrec_a, && evolution_function_is_affine_multivariate_p (chrec_a)) { dependence_stats.num_same_subscript_function++; - *overlap_iterations_a = integer_zero_node; - *overlap_iterations_b = integer_zero_node; + *overlap_iterations_a = conflict_fn (1, affine_fn_cst (integer_zero_node)); + *overlap_iterations_b = conflict_fn (1, affine_fn_cst (integer_zero_node)); *last_conflicts = chrec_dont_know; } @@ -3354,8 +3583,8 @@ analyze_overlapping_iterations (tree chrec_a, || !evolution_function_is_affine_multivariate_p (chrec_b))) { dependence_stats.num_subscript_undetermined++; - *overlap_iterations_a = chrec_dont_know; - *overlap_iterations_b = chrec_dont_know; + *overlap_iterations_a = conflict_fn_not_known (); + *overlap_iterations_b = conflict_fn_not_known (); } else if (ziv_subscript_p (chrec_a, chrec_b)) @@ -3376,9 +3605,9 @@ analyze_overlapping_iterations (tree chrec_a, if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, " (overlap_iterations_a = "); - print_generic_expr (dump_file, *overlap_iterations_a, 0); + dump_conflict_function (dump_file, *overlap_iterations_a); fprintf (dump_file, ")\n (overlap_iterations_b = "); - print_generic_expr (dump_file, *overlap_iterations_b, 0); + dump_conflict_function (dump_file, *overlap_iterations_b); fprintf (dump_file, ")\n"); fprintf (dump_file, ")\n"); } @@ -3808,26 +4037,30 @@ subscript_dependence_tester_1 (struct data_dependence_relation *ddr, for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript); i++) { - tree overlaps_a, overlaps_b; + conflict_function *overlaps_a, *overlaps_b; analyze_overlapping_iterations (DR_ACCESS_FN (dra, i), DR_ACCESS_FN (drb, i), &overlaps_a, &overlaps_b, &last_conflicts); - if (chrec_contains_undetermined (overlaps_a) - || chrec_contains_undetermined (overlaps_b)) + if (CF_NOT_KNOWN_P (overlaps_a) + || CF_NOT_KNOWN_P (overlaps_b)) { finalize_ddr_dependent (ddr, chrec_dont_know); dependence_stats.num_dependence_undetermined++; + free_conflict_function (overlaps_a); + free_conflict_function (overlaps_b); return false; } - else if (overlaps_a == chrec_known - || overlaps_b == chrec_known) + else if (CF_NO_DEPENDENCE_P (overlaps_a) + || CF_NO_DEPENDENCE_P (overlaps_b)) { finalize_ddr_dependent (ddr, chrec_known); dependence_stats.num_dependence_independent++; + free_conflict_function (overlaps_a); + free_conflict_function (overlaps_b); return false; } @@ -3950,8 +4183,10 @@ compute_self_dependence (struct data_dependence_relation *ddr) i++) { /* The accessed index overlaps for each iteration. */ - SUB_CONFLICTS_IN_A (subscript) = integer_zero_node; - SUB_CONFLICTS_IN_B (subscript) = integer_zero_node; + SUB_CONFLICTS_IN_A (subscript) + = conflict_fn (1, affine_fn_cst (integer_zero_node)); + SUB_CONFLICTS_IN_B (subscript) + = conflict_fn (1, affine_fn_cst (integer_zero_node)); SUB_LAST_CONFLICT (subscript) = chrec_dont_know; } @@ -4367,7 +4602,7 @@ free_dependence_relation (struct data_dependence_relation *ddr) return; if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_SUBSCRIPTS (ddr)) - VEC_free (subscript_p, heap, DDR_SUBSCRIPTS (ddr)); + free_subscripts (DDR_SUBSCRIPTS (ddr)); free (ddr); } diff --git a/gcc/tree-data-ref.h b/gcc/tree-data-ref.h index 8c6ee416d32..ba471744767 100644 --- a/gcc/tree-data-ref.h +++ b/gcc/tree-data-ref.h @@ -190,6 +190,29 @@ enum data_dependence_direction { dir_independent }; +/* The description of the grid of iterations that overlap. At most + two loops are considered at the same time just now, hence at most + two functions are needed. For each of the functions, we store + the vector of coefficients, f[0] + x * f[1] + y * f[2] + ..., + where x, y, ... are variables. */ + +#define MAX_DIM 2 + +/* Special values of N. */ +#define NO_DEPENDENCE 0 +#define NOT_KNOWN (MAX_DIM + 1) +#define CF_NONTRIVIAL_P(CF) ((CF)->n != NO_DEPENDENCE && (CF)->n != NOT_KNOWN) +#define CF_NOT_KNOWN_P(CF) ((CF)->n == NOT_KNOWN) +#define CF_NO_DEPENDENCE_P(CF) ((CF)->n == NO_DEPENDENCE) + +typedef VEC (tree, heap) *affine_fn; + +typedef struct +{ + unsigned n; + affine_fn fns[MAX_DIM]; +} conflict_function; + /* What is a subscript? Given two array accesses a subscript is the tuple composed of the access functions for a given dimension. Example: Given A[f1][f2][f3] and B[g1][g2][g3], there are three @@ -201,8 +224,8 @@ struct subscript { /* A description of the iterations for which the elements are accessed twice. */ - tree conflicting_iterations_in_a; - tree conflicting_iterations_in_b; + conflict_function *conflicting_iterations_in_a; + conflict_function *conflicting_iterations_in_b; /* This field stores the information about the iteration domain validity of the dependence relation. */ -- 2.11.4.GIT