X-Git-Url: http://git.sourceforge.jp/view?p=pf3gnuchains%2Fgcc-fork.git;a=blobdiff_plain;f=gcc%2Ftree-data-ref.c;h=1b5e92b5af344283b80f9590544b2c7164f1be84;hp=8ef5c51a66060e761a80861ee6e8c5d0af7a0a90;hb=d010953eebc456ca7654214131f6e4b9da8b1487;hpb=b66731e8c2683e73ff3e734e22cd16fe42dd367d diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c index 8ef5c51a660..1b5e92b5af3 100644 --- a/gcc/tree-data-ref.c +++ b/gcc/tree-data-ref.c @@ -1,12 +1,12 @@ /* Data references and dependences detectors. - Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc. - Contributed by Sebastian Pop + Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc. + Contributed by Sebastian Pop This file is part of GCC. GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free -Software Foundation; either version 2, or (at your option) any later +Software Foundation; either version 3, or (at your option) any later version. GCC is distributed in the hope that it will be useful, but WITHOUT ANY @@ -15,9 +15,8 @@ FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License -along with GCC; see the file COPYING. If not, write to the Free -Software Foundation, 59 Temple Place - Suite 330, Boston, MA -02111-1307, USA. */ +along with GCC; see the file COPYING3. If not see +. */ /* This pass walks a given loop structure searching for array references. The information about the array accesses is recorded @@ -78,7 +77,6 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA #include "system.h" #include "coretypes.h" #include "tm.h" -#include "errors.h" #include "ggc.h" #include "tree.h" @@ -90,130 +88,50 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA #include "tree-dump.h" #include "timevar.h" #include "cfgloop.h" -#include "tree-chrec.h" #include "tree-data-ref.h" #include "tree-scalar-evolution.h" #include "tree-pass.h" +#include "langhooks.h" -/* This is the simplest data dependence test: determines whether the - data references A and B access the same array/region. Returns - false when the property is not computable at compile time. - Otherwise return true, and DIFFER_P will record the result. This - utility will not be necessary when alias_sets_conflict_p will be - less conservative. */ - -bool -array_base_name_differ_p (struct data_reference *a, - struct data_reference *b, - bool *differ_p) +static struct datadep_stats { - tree base_a = DR_BASE_NAME (a); - tree base_b = DR_BASE_NAME (b); - - if (!base_a || !base_b) - return false; - - /* Determine if same base. Example: for the array accesses - a[i], b[i] or pointer accesses *a, *b, bases are a, b. */ - if (base_a == base_b) - { - *differ_p = false; - return true; - } - - /* For pointer based accesses, (*p)[i], (*q)[j], the bases are (*p) - and (*q) */ - if (TREE_CODE (base_a) == INDIRECT_REF && TREE_CODE (base_b) == INDIRECT_REF - && TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0)) - { - *differ_p = false; - return true; - } - - /* Record/union based accesses - s.a[i], t.b[j]. bases are s.a,t.b. */ - if (TREE_CODE (base_a) == COMPONENT_REF && TREE_CODE (base_b) == COMPONENT_REF - && TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0) - && TREE_OPERAND (base_a, 1) == TREE_OPERAND (base_b, 1)) - { - *differ_p = false; - return true; - } - - - /* Determine if different bases. */ - - /* At this point we know that base_a != base_b. However, pointer - accesses of the form x=(*p) and y=(*q), whose bases are p and q, - may still be pointing to the same base. In SSAed GIMPLE p and q will - be SSA_NAMES in this case. Therefore, here we check if they are - really two different declarations. */ - if (TREE_CODE (base_a) == VAR_DECL && TREE_CODE (base_b) == VAR_DECL) - { - *differ_p = true; - return true; - } - - /* Compare two record/union bases s.a and t.b: s != t or (a != b and - s and t are not unions). */ - if (TREE_CODE (base_a) == COMPONENT_REF && TREE_CODE (base_b) == COMPONENT_REF - && ((TREE_CODE (TREE_OPERAND (base_a, 0)) == VAR_DECL - && TREE_CODE (TREE_OPERAND (base_b, 0)) == VAR_DECL - && TREE_OPERAND (base_a, 0) != TREE_OPERAND (base_b, 0)) - || (TREE_CODE (TREE_TYPE (TREE_OPERAND (base_a, 0))) == RECORD_TYPE - && TREE_CODE (TREE_TYPE (TREE_OPERAND (base_b, 0))) == RECORD_TYPE - && TREE_OPERAND (base_a, 1) != TREE_OPERAND (base_b, 1)))) - { - *differ_p = true; - return true; - } - - /* Compare a record/union access and an array access. */ - if ((TREE_CODE (base_a) == VAR_DECL - && (TREE_CODE (base_b) == COMPONENT_REF - && TREE_CODE (TREE_OPERAND (base_b, 0)) == VAR_DECL)) - || (TREE_CODE (base_b) == VAR_DECL - && (TREE_CODE (base_a) == COMPONENT_REF - && TREE_CODE (TREE_OPERAND (base_a, 0)) == VAR_DECL))) - { - *differ_p = true; - return true; - } - - return false; -} - + int num_dependence_tests; + int num_dependence_dependent; + int num_dependence_independent; + int num_dependence_undetermined; + + int num_subscript_tests; + int num_subscript_undetermined; + int num_same_subscript_function; + + int num_ziv; + int num_ziv_independent; + int num_ziv_dependent; + int num_ziv_unimplemented; + + int num_siv; + int num_siv_independent; + int num_siv_dependent; + int num_siv_unimplemented; + + int num_miv; + int num_miv_independent; + int num_miv_dependent; + int num_miv_unimplemented; +} dependence_stats; + +static bool subscript_dependence_tester_1 (struct data_dependence_relation *, + struct data_reference *, + struct data_reference *, + struct loop *); /* Returns true iff A divides B. */ static inline bool -tree_fold_divides_p (tree type, - tree a, - tree b) -{ - /* Determines whether (A == gcd (A, B)). */ - return integer_zerop - (fold (build (MINUS_EXPR, type, a, tree_fold_gcd (a, b)))); -} - -/* Compute the greatest common denominator of two numbers using - Euclid's algorithm. */ - -static int -gcd (int a, int b) +tree_fold_divides_p (const_tree a, const_tree b) { - - int x, y, z; - - x = abs (a); - y = abs (b); - - while (x>0) - { - z = y % x; - y = x; - x = z; - } - - return (y); + gcc_assert (TREE_CODE (a) == INTEGER_CST); + gcc_assert (TREE_CODE (b) == INTEGER_CST); + return integer_zerop (int_const_binop (TRUNC_MOD_EXPR, b, a, 0)); } /* Returns true iff A divides B. */ @@ -229,25 +147,34 @@ int_divides_p (int a, int b) /* Dump into FILE all the data references from DATAREFS. */ void -dump_data_references (FILE *file, - varray_type datarefs) +dump_data_references (FILE *file, VEC (data_reference_p, heap) *datarefs) { unsigned int i; - - for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++) - dump_data_reference (file, VARRAY_GENERIC_PTR (datarefs, i)); + struct data_reference *dr; + + for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++) + dump_data_reference (file, dr); +} + +/* Dump to STDERR all the dependence relations from DDRS. */ + +void +debug_data_dependence_relations (VEC (ddr_p, heap) *ddrs) +{ + dump_data_dependence_relations (stderr, ddrs); } -/* Dump into FILE all the dependence relations from DDR. */ +/* Dump into FILE all the dependence relations from DDRS. */ void dump_data_dependence_relations (FILE *file, - varray_type ddr) + VEC (ddr_p, heap) *ddrs) { unsigned int i; - - for (i = 0; i < VARRAY_ACTIVE_SIZE (ddr); i++) - dump_data_dependence_relation (file, VARRAY_GENERIC_PTR (ddr, i)); + struct data_dependence_relation *ddr; + + for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++) + dump_data_dependence_relation (file, ddr); } /* Dump function for a DATA_REFERENCE structure. */ @@ -259,11 +186,11 @@ dump_data_reference (FILE *outf, unsigned int i; fprintf (outf, "(Data Ref: \n stmt: "); - print_generic_stmt (outf, DR_STMT (dr), 0); + print_gimple_stmt (outf, DR_STMT (dr), 0, 0); fprintf (outf, " ref: "); print_generic_stmt (outf, DR_REF (dr), 0); - fprintf (outf, " base_name: "); - print_generic_stmt (outf, DR_BASE_NAME (dr), 0); + fprintf (outf, " base_object: "); + print_generic_stmt (outf, DR_BASE_OBJECT (dr), 0); for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++) { @@ -273,35 +200,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: "); @@ -314,6 +272,84 @@ dump_subscript (FILE *outf, struct subscript *subscript) fprintf (outf, " )\n"); } +/* Print the classic direction vector DIRV to OUTF. */ + +void +print_direction_vector (FILE *outf, + lambda_vector dirv, + int length) +{ + int eq; + + for (eq = 0; eq < length; eq++) + { + enum data_dependence_direction dir = dirv[eq]; + + switch (dir) + { + case dir_positive: + fprintf (outf, " +"); + break; + case dir_negative: + fprintf (outf, " -"); + break; + case dir_equal: + fprintf (outf, " ="); + break; + case dir_positive_or_equal: + fprintf (outf, " +="); + break; + case dir_positive_or_negative: + fprintf (outf, " +-"); + break; + case dir_negative_or_equal: + fprintf (outf, " -="); + break; + case dir_star: + fprintf (outf, " *"); + break; + default: + fprintf (outf, "indep"); + break; + } + } + fprintf (outf, "\n"); +} + +/* Print a vector of direction vectors. */ + +void +print_dir_vectors (FILE *outf, VEC (lambda_vector, heap) *dir_vects, + int length) +{ + unsigned j; + lambda_vector v; + + for (j = 0; VEC_iterate (lambda_vector, dir_vects, j, v); j++) + print_direction_vector (outf, v, length); +} + +/* Print a vector of distance vectors. */ + +void +print_dist_vectors (FILE *outf, VEC (lambda_vector, heap) *dist_vects, + int length) +{ + unsigned j; + lambda_vector v; + + for (j = 0; VEC_iterate (lambda_vector, dist_vects, j, v); j++) + print_lambda_vector (outf, v, length); +} + +/* Debug version. */ + +void +debug_data_dependence_relation (struct data_dependence_relation *ddr) +{ + dump_data_dependence_relation (stderr, ddr); +} + /* Dump function for a DATA_DEPENDENCE_RELATION structure. */ void @@ -322,18 +358,27 @@ dump_data_dependence_relation (FILE *outf, { struct data_reference *dra, *drb; + fprintf (outf, "(Data Dep: \n"); + + if (!ddr || DDR_ARE_DEPENDENT (ddr) == chrec_dont_know) + { + fprintf (outf, " (don't know)\n)\n"); + return; + } + dra = DDR_A (ddr); drb = DDR_B (ddr); - fprintf (outf, "(Data Dep: \n"); - if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know) - fprintf (outf, " (don't know)\n"); - - else if (DDR_ARE_DEPENDENT (ddr) == chrec_known) + dump_data_reference (outf, dra); + dump_data_reference (outf, drb); + + if (DDR_ARE_DEPENDENT (ddr) == chrec_known) fprintf (outf, " (no dependence)\n"); else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE) { unsigned int i; + struct loop *loopi; + for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) { fprintf (outf, " access_fn_A: "); @@ -342,23 +387,31 @@ dump_data_dependence_relation (FILE *outf, print_generic_stmt (outf, DR_ACCESS_FN (drb, i), 0); dump_subscript (outf, DDR_SUBSCRIPT (ddr, i)); } - if (DDR_DIST_VECT (ddr)) + + fprintf (outf, " inner loop index: %d\n", DDR_INNER_LOOP (ddr)); + fprintf (outf, " loop nest: ("); + for (i = 0; VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++) + fprintf (outf, "%d ", loopi->num); + fprintf (outf, ")\n"); + + for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++) { - fprintf (outf, " distance_vect: "); - print_lambda_vector (outf, DDR_DIST_VECT (ddr), DDR_SIZE_VECT (ddr)); + fprintf (outf, " distance_vector: "); + print_lambda_vector (outf, DDR_DIST_VECT (ddr, i), + DDR_NB_LOOPS (ddr)); } - if (DDR_DIR_VECT (ddr)) + + for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++) { - fprintf (outf, " direction_vect: "); - print_lambda_vector (outf, DDR_DIR_VECT (ddr), DDR_SIZE_VECT (ddr)); + fprintf (outf, " direction_vector: "); + print_direction_vector (outf, DDR_DIR_VECT (ddr, i), + DDR_NB_LOOPS (ddr)); } } fprintf (outf, ")\n"); } - - /* Dump function for a DATA_DEPENDENCE_DIRECTION structure. */ void @@ -406,2062 +459,4616 @@ dump_data_dependence_direction (FILE *file, considered nest. */ void -dump_dist_dir_vectors (FILE *file, varray_type ddrs) +dump_dist_dir_vectors (FILE *file, VEC (ddr_p, heap) *ddrs) { - unsigned int i; + unsigned int i, j; + struct data_dependence_relation *ddr; + lambda_vector v; + + for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++) + if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_AFFINE_P (ddr)) + { + for (j = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), j, v); j++) + { + fprintf (file, "DISTANCE_V ("); + print_lambda_vector (file, v, DDR_NB_LOOPS (ddr)); + fprintf (file, ")\n"); + } + + for (j = 0; VEC_iterate (lambda_vector, DDR_DIR_VECTS (ddr), j, v); j++) + { + fprintf (file, "DIRECTION_V ("); + print_direction_vector (file, v, DDR_NB_LOOPS (ddr)); + fprintf (file, ")\n"); + } + } - for (i = 0; i < VARRAY_ACTIVE_SIZE (ddrs); i++) - { - struct data_dependence_relation *ddr = - (struct data_dependence_relation *) - VARRAY_GENERIC_PTR (ddrs, i); - if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE - && DDR_AFFINE_P (ddr)) - { - fprintf (file, "DISTANCE_V ("); - print_lambda_vector (file, DDR_DIST_VECT (ddr), DDR_SIZE_VECT (ddr)); - fprintf (file, ")\n"); - fprintf (file, "DIRECTION_V ("); - print_lambda_vector (file, DDR_DIR_VECT (ddr), DDR_SIZE_VECT (ddr)); - fprintf (file, ")\n"); - } - } fprintf (file, "\n\n"); } /* Dumps the data dependence relations DDRS in FILE. */ void -dump_ddrs (FILE *file, varray_type ddrs) +dump_ddrs (FILE *file, VEC (ddr_p, heap) *ddrs) { unsigned int i; + struct data_dependence_relation *ddr; + + for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++) + dump_data_dependence_relation (file, ddr); - for (i = 0; i < VARRAY_ACTIVE_SIZE (ddrs); i++) - { - struct data_dependence_relation *ddr = - (struct data_dependence_relation *) - VARRAY_GENERIC_PTR (ddrs, i); - dump_data_dependence_relation (file, ddr); - } fprintf (file, "\n\n"); } - - -/* Compute the lowest iteration bound for LOOP. It is an - INTEGER_CST. */ +/* Helper function for split_constant_offset. Expresses OP0 CODE OP1 + (the type of the result is TYPE) as VAR + OFF, where OFF is a nonzero + constant of type ssizetype, and returns true. If we cannot do this + with OFF nonzero, OFF and VAR are set to NULL_TREE instead and false + is returned. */ -static void -compute_estimated_nb_iterations (struct loop *loop) +static bool +split_constant_offset_1 (tree type, tree op0, enum tree_code code, tree op1, + tree *var, tree *off) { - tree estimation; - struct nb_iter_bound *bound, *next; - - for (bound = loop->bounds; bound; bound = next) + tree var0, var1; + tree off0, off1; + enum tree_code ocode = code; + + *var = NULL_TREE; + *off = NULL_TREE; + + switch (code) { - next = bound->next; - estimation = bound->bound; + case INTEGER_CST: + *var = build_int_cst (type, 0); + *off = fold_convert (ssizetype, op0); + return true; - if (TREE_CODE (estimation) != INTEGER_CST) - continue; + case POINTER_PLUS_EXPR: + ocode = PLUS_EXPR; + /* FALLTHROUGH */ + case PLUS_EXPR: + case MINUS_EXPR: + split_constant_offset (op0, &var0, &off0); + split_constant_offset (op1, &var1, &off1); + *var = fold_build2 (code, type, var0, var1); + *off = size_binop (ocode, off0, off1); + return true; - if (loop->estimated_nb_iterations) - { - /* Update only if estimation is smaller. */ - if (tree_int_cst_lt (estimation, loop->estimated_nb_iterations)) - loop->estimated_nb_iterations = estimation; - } - else - loop->estimated_nb_iterations = estimation; + case MULT_EXPR: + if (TREE_CODE (op1) != INTEGER_CST) + return false; + + split_constant_offset (op0, &var0, &off0); + *var = fold_build2 (MULT_EXPR, type, var0, op1); + *off = size_binop (MULT_EXPR, off0, fold_convert (ssizetype, op1)); + return true; + + case ADDR_EXPR: + { + tree base, poffset; + HOST_WIDE_INT pbitsize, pbitpos; + enum machine_mode pmode; + int punsignedp, pvolatilep; + + if (!handled_component_p (op0)) + return false; + + base = get_inner_reference (op0, &pbitsize, &pbitpos, &poffset, + &pmode, &punsignedp, &pvolatilep, false); + + if (pbitpos % BITS_PER_UNIT != 0) + return false; + base = build_fold_addr_expr (base); + off0 = ssize_int (pbitpos / BITS_PER_UNIT); + + if (poffset) + { + split_constant_offset (poffset, &poffset, &off1); + off0 = size_binop (PLUS_EXPR, off0, off1); + if (POINTER_TYPE_P (TREE_TYPE (base))) + base = fold_build2 (POINTER_PLUS_EXPR, TREE_TYPE (base), + base, fold_convert (sizetype, poffset)); + else + base = fold_build2 (PLUS_EXPR, TREE_TYPE (base), base, + fold_convert (TREE_TYPE (base), poffset)); + } + + var0 = fold_convert (type, base); + + /* If variable length types are involved, punt, otherwise casts + might be converted into ARRAY_REFs in gimplify_conversion. + To compute that ARRAY_REF's element size TYPE_SIZE_UNIT, which + possibly no longer appears in current GIMPLE, might resurface. + This perhaps could run + if (TREE_CODE (var0) == NOP_EXPR + || TREE_CODE (var0) == CONVERT_EXPR) + { + gimplify_conversion (&var0); + // Attempt to fill in any within var0 found ARRAY_REF's + // element size from corresponding op embedded ARRAY_REF, + // if unsuccessful, just punt. + } */ + while (POINTER_TYPE_P (type)) + type = TREE_TYPE (type); + if (int_size_in_bytes (type) < 0) + return false; + + *var = var0; + *off = off0; + return true; + } + + case SSA_NAME: + { + gimple def_stmt = SSA_NAME_DEF_STMT (op0); + enum tree_code subcode; + + if (gimple_code (def_stmt) != GIMPLE_ASSIGN) + return false; + + var0 = gimple_assign_rhs1 (def_stmt); + subcode = gimple_assign_rhs_code (def_stmt); + var1 = gimple_assign_rhs2 (def_stmt); + + return split_constant_offset_1 (type, var0, subcode, var1, var, off); + } + + default: + return false; } } -/* Estimate the number of iterations from the size of the data and the - access functions. */ +/* Expresses EXP as VAR + OFF, where off is a constant. The type of OFF + will be ssizetype. */ -static void -estimate_niter_from_size_of_data (struct loop *loop, - tree opnd0, - tree access_fn, - tree stmt) -{ - tree estimation; - tree array_size, data_size, element_size; - tree init, step; - - init = initial_condition (access_fn); - step = evolution_part_in_loop_num (access_fn, loop->num); - - array_size = TYPE_SIZE (TREE_TYPE (opnd0)); - element_size = TYPE_SIZE (TREE_TYPE (TREE_TYPE (opnd0))); - if (array_size == NULL_TREE - || TREE_CODE (array_size) != INTEGER_CST - || TREE_CODE (element_size) != INTEGER_CST) - return; +void +split_constant_offset (tree exp, tree *var, tree *off) +{ + tree type = TREE_TYPE (exp), otype, op0, op1, e, o; + enum tree_code code; - data_size = fold (build2 (EXACT_DIV_EXPR, integer_type_node, - array_size, element_size)); + *var = exp; + *off = ssize_int (0); + STRIP_NOPS (exp); - if (init != NULL_TREE - && step != NULL_TREE - && TREE_CODE (init) == INTEGER_CST - && TREE_CODE (step) == INTEGER_CST) - { - estimation = fold (build2 (CEIL_DIV_EXPR, integer_type_node, - fold (build2 (MINUS_EXPR, integer_type_node, - data_size, init)), step)); + if (automatically_generated_chrec_p (exp)) + return; - record_estimate (loop, estimation, boolean_true_node, stmt); + otype = TREE_TYPE (exp); + code = TREE_CODE (exp); + extract_ops_from_tree (exp, &code, &op0, &op1); + if (split_constant_offset_1 (otype, op0, code, op1, &e, &o)) + { + *var = fold_convert (type, e); + *off = o; } } -/* Given an ARRAY_REF node REF, records its access functions. - Example: given A[i][3], record in ACCESS_FNS the opnd1 function, - i.e. the constant "3", then recursively call the function on opnd0, - i.e. the ARRAY_REF "A[i]". The function returns the base name: - "A". */ +/* Returns the address ADDR of an object in a canonical shape (without nop + casts, and with type of pointer to the object). */ static tree -analyze_array_indexes (struct loop *loop, - varray_type *access_fns, - tree ref, tree stmt) +canonicalize_base_object_address (tree addr) { - tree opnd0, opnd1; - tree access_fn; - - opnd0 = TREE_OPERAND (ref, 0); - opnd1 = TREE_OPERAND (ref, 1); - - /* The detection of the evolution function for this data access is - postponed until the dependence test. This lazy strategy avoids - the computation of access functions that are of no interest for - the optimizers. */ - access_fn = instantiate_parameters - (loop, analyze_scalar_evolution (loop, opnd1)); - - if (loop->estimated_nb_iterations == NULL_TREE) - estimate_niter_from_size_of_data (loop, opnd0, access_fn, stmt); - - VARRAY_PUSH_TREE (*access_fns, access_fn); - - /* Recursively record other array access functions. */ - if (TREE_CODE (opnd0) == ARRAY_REF) - return analyze_array_indexes (loop, access_fns, opnd0, stmt); - - /* Return the base name of the data access. */ - else - return opnd0; -} + tree orig = addr; -/* For a data reference REF contained in the statement STMT, initialize - a DATA_REFERENCE structure, and return it. IS_READ flag has to be - set to true when REF is in the right hand side of an - assignment. */ + STRIP_NOPS (addr); -struct data_reference * -analyze_array (tree stmt, tree ref, bool is_read) -{ - struct data_reference *res; + /* The base address may be obtained by casting from integer, in that case + keep the cast. */ + if (!POINTER_TYPE_P (TREE_TYPE (addr))) + return orig; - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "(analyze_array \n"); - fprintf (dump_file, " (ref = "); - print_generic_stmt (dump_file, ref, 0); - fprintf (dump_file, ")\n"); - } - - res = xmalloc (sizeof (struct data_reference)); - - DR_STMT (res) = stmt; - DR_REF (res) = ref; - VARRAY_TREE_INIT (DR_ACCESS_FNS (res), 3, "access_fns"); - DR_BASE_NAME (res) = analyze_array_indexes - (loop_containing_stmt (stmt), &(DR_ACCESS_FNS (res)), ref, stmt); - DR_IS_READ (res) = is_read; - - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, ")\n"); - - return res; + if (TREE_CODE (addr) != ADDR_EXPR) + return addr; + + return build_fold_addr_expr (TREE_OPERAND (addr, 0)); } -/* For a data reference REF contained in the statement STMT, initialize - a DATA_REFERENCE structure, and return it. */ +/* Analyzes the behavior of the memory reference DR in the innermost loop that + contains it. */ -struct data_reference * -init_data_ref (tree stmt, - tree ref, - tree base, - tree access_fn, - bool is_read) +void +dr_analyze_innermost (struct data_reference *dr) { - struct data_reference *res; + gimple stmt = DR_STMT (dr); + struct loop *loop = loop_containing_stmt (stmt); + tree ref = DR_REF (dr); + HOST_WIDE_INT pbitsize, pbitpos; + tree base, poffset; + enum machine_mode pmode; + int punsignedp, pvolatilep; + affine_iv base_iv, offset_iv; + tree init, dinit, step; if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "analyze_innermost: "); + + base = get_inner_reference (ref, &pbitsize, &pbitpos, &poffset, + &pmode, &punsignedp, &pvolatilep, false); + gcc_assert (base != NULL_TREE); + + if (pbitpos % BITS_PER_UNIT != 0) { - fprintf (dump_file, "(init_data_ref \n"); - fprintf (dump_file, " (ref = "); - print_generic_stmt (dump_file, ref, 0); - fprintf (dump_file, ")\n"); + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "failed: bit offset alignment.\n"); + return; } - - res = xmalloc (sizeof (struct data_reference)); - - DR_STMT (res) = stmt; - DR_REF (res) = ref; - VARRAY_TREE_INIT (DR_ACCESS_FNS (res), 5, "access_fns"); - DR_BASE_NAME (res) = base; - VARRAY_PUSH_TREE (DR_ACCESS_FNS (res), access_fn); - DR_IS_READ (res) = is_read; - + + base = build_fold_addr_expr (base); + if (!simple_iv (loop, stmt, base, &base_iv, false)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "failed: evolution of base is not affine.\n"); + return; + } + if (!poffset) + { + offset_iv.base = ssize_int (0); + offset_iv.step = ssize_int (0); + } + else if (!simple_iv (loop, stmt, poffset, &offset_iv, false)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "failed: evolution of offset is not affine.\n"); + return; + } + + init = ssize_int (pbitpos / BITS_PER_UNIT); + split_constant_offset (base_iv.base, &base_iv.base, &dinit); + init = size_binop (PLUS_EXPR, init, dinit); + split_constant_offset (offset_iv.base, &offset_iv.base, &dinit); + init = size_binop (PLUS_EXPR, init, dinit); + + step = size_binop (PLUS_EXPR, + fold_convert (ssizetype, base_iv.step), + fold_convert (ssizetype, offset_iv.step)); + + DR_BASE_ADDRESS (dr) = canonicalize_base_object_address (base_iv.base); + + DR_OFFSET (dr) = fold_convert (ssizetype, offset_iv.base); + DR_INIT (dr) = init; + DR_STEP (dr) = step; + + DR_ALIGNED_TO (dr) = size_int (highest_pow2_factor (offset_iv.base)); + if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, ")\n"); - - return res; + fprintf (dump_file, "success.\n"); } - - -/* Returns true when all the functions of a tree_vec CHREC are the - same. */ +/* Determines the base object and the list of indices of memory reference + DR, analyzed in loop nest NEST. */ -static bool -all_chrecs_equal_p (tree chrec) +static void +dr_analyze_indices (struct data_reference *dr, struct loop *nest) { - int j; + gimple stmt = DR_STMT (dr); + struct loop *loop = loop_containing_stmt (stmt); + VEC (tree, heap) *access_fns = NULL; + tree ref = unshare_expr (DR_REF (dr)), aref = ref, op; + tree base, off, access_fn; - for (j = 0; j < TREE_VEC_LENGTH (chrec) - 1; j++) + while (handled_component_p (aref)) { - tree chrec_j = TREE_VEC_ELT (chrec, j); - tree chrec_j_1 = TREE_VEC_ELT (chrec, j + 1); - if (!integer_zerop - (chrec_fold_minus - (integer_type_node, chrec_j, chrec_j_1))) - return false; + if (TREE_CODE (aref) == ARRAY_REF) + { + op = TREE_OPERAND (aref, 1); + access_fn = analyze_scalar_evolution (loop, op); + access_fn = instantiate_scev (nest, loop, access_fn); + VEC_safe_push (tree, heap, access_fns, access_fn); + + TREE_OPERAND (aref, 1) = build_int_cst (TREE_TYPE (op), 0); + } + + aref = TREE_OPERAND (aref, 0); } - return true; -} -/* Determine for each subscript in the data dependence relation DDR - the distance. */ + if (INDIRECT_REF_P (aref)) + { + op = TREE_OPERAND (aref, 0); + access_fn = analyze_scalar_evolution (loop, op); + access_fn = instantiate_scev (nest, loop, access_fn); + base = initial_condition (access_fn); + split_constant_offset (base, &base, &off); + access_fn = chrec_replace_initial_condition (access_fn, + fold_convert (TREE_TYPE (base), off)); + + TREE_OPERAND (aref, 0) = base; + VEC_safe_push (tree, heap, access_fns, access_fn); + } -void -compute_subscript_distance (struct data_dependence_relation *ddr) + DR_BASE_OBJECT (dr) = ref; + DR_ACCESS_FNS (dr) = access_fns; +} + +/* Extracts the alias analysis information from the memory reference DR. */ + +static void +dr_analyze_alias (struct data_reference *dr) { - if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE) + gimple stmt = DR_STMT (dr); + tree ref = DR_REF (dr); + tree base = get_base_address (ref), addr, smt = NULL_TREE; + ssa_op_iter it; + tree op; + bitmap vops; + + if (DECL_P (base)) + smt = base; + else if (INDIRECT_REF_P (base)) { - 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); - - if (TREE_CODE (conflicts_a) == TREE_VEC) - { - if (!all_chrecs_equal_p (conflicts_a)) - { - SUB_DISTANCE (subscript) = chrec_dont_know; - return; - } - else - conflicts_a = TREE_VEC_ELT (conflicts_a, 0); - } + addr = TREE_OPERAND (base, 0); + if (TREE_CODE (addr) == SSA_NAME) + { + smt = symbol_mem_tag (SSA_NAME_VAR (addr)); + DR_PTR_INFO (dr) = SSA_NAME_PTR_INFO (addr); + } + } - 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); - } + DR_SYMBOL_TAG (dr) = smt; - difference = chrec_fold_minus - (integer_type_node, conflicts_b, conflicts_a); - - if (evolution_function_is_constant_p (difference)) - SUB_DISTANCE (subscript) = difference; - - else - SUB_DISTANCE (subscript) = chrec_dont_know; - } + vops = BITMAP_ALLOC (NULL); + FOR_EACH_SSA_TREE_OPERAND (op, stmt, it, SSA_OP_VIRTUAL_USES) + { + bitmap_set_bit (vops, DECL_UID (SSA_NAME_VAR (op))); } + + DR_VOPS (dr) = vops; } -/* Initialize a ddr. */ +/* Returns true if the address of DR is invariant. */ -struct data_dependence_relation * -initialize_data_dependence_relation (struct data_reference *a, - struct data_reference *b) +static bool +dr_address_invariant_p (struct data_reference *dr) { - struct data_dependence_relation *res; - bool differ_p; - - res = xmalloc (sizeof (struct data_dependence_relation)); - DDR_A (res) = a; - DDR_B (res) = b; + unsigned i; + tree idx; - if (a == NULL || b == NULL - || DR_BASE_NAME (a) == NULL_TREE - || DR_BASE_NAME (b) == NULL_TREE) - DDR_ARE_DEPENDENT (res) = chrec_dont_know; + for (i = 0; VEC_iterate (tree, DR_ACCESS_FNS (dr), i, idx); i++) + if (tree_contains_chrecs (idx, NULL)) + return false; - /* When the dimensions of A and B differ, we directly initialize - the relation to "there is no dependence": chrec_known. */ - else if (DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b) - || (array_base_name_differ_p (a, b, &differ_p) && differ_p)) - DDR_ARE_DEPENDENT (res) = chrec_known; - - else - { - unsigned int i; - DDR_AFFINE_P (res) = true; - DDR_ARE_DEPENDENT (res) = NULL_TREE; - DDR_SUBSCRIPTS_VECTOR_INIT (res, DR_NUM_DIMENSIONS (a)); - DDR_SIZE_VECT (res) = 0; - DDR_DIST_VECT (res) = NULL; - DDR_DIR_VECT (res) = NULL; - - for (i = 0; i < DR_NUM_DIMENSIONS (a); i++) - { - struct subscript *subscript; - - subscript = xmalloc (sizeof (struct subscript)); - SUB_CONFLICTS_IN_A (subscript) = chrec_dont_know; - SUB_CONFLICTS_IN_B (subscript) = chrec_dont_know; - SUB_LAST_CONFLICT (subscript) = chrec_dont_know; - SUB_DISTANCE (subscript) = chrec_dont_know; - VARRAY_PUSH_GENERIC_PTR (DDR_SUBSCRIPTS (res), subscript); - } - } - - return res; + return true; } -/* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap - description. */ +/* Frees data reference DR. */ -static inline void -finalize_ddr_dependent (struct data_dependence_relation *ddr, - tree chrec) +void +free_data_ref (data_reference_p dr) +{ + BITMAP_FREE (DR_VOPS (dr)); + VEC_free (tree, heap, DR_ACCESS_FNS (dr)); + free (dr); +} + +/* Analyzes memory reference MEMREF accessed in STMT. The reference + is read if IS_READ is true, write otherwise. Returns the + data_reference description of MEMREF. NEST is the outermost loop of the + loop nest in that the reference should be analyzed. */ + +struct data_reference * +create_data_ref (struct loop *nest, tree memref, gimple stmt, bool is_read) { + struct data_reference *dr; + if (dump_file && (dump_flags & TDF_DETAILS)) { - fprintf (dump_file, "(dependence classified: "); - print_generic_expr (dump_file, chrec, 0); - fprintf (dump_file, ")\n"); + fprintf (dump_file, "Creating dr for "); + print_generic_expr (dump_file, memref, TDF_SLIM); + fprintf (dump_file, "\n"); } - DDR_ARE_DEPENDENT (ddr) = chrec; - varray_clear (DDR_SUBSCRIPTS (ddr)); + dr = XCNEW (struct data_reference); + DR_STMT (dr) = stmt; + DR_REF (dr) = memref; + DR_IS_READ (dr) = is_read; + + dr_analyze_innermost (dr); + dr_analyze_indices (dr, nest); + dr_analyze_alias (dr); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "\tbase_address: "); + print_generic_expr (dump_file, DR_BASE_ADDRESS (dr), TDF_SLIM); + fprintf (dump_file, "\n\toffset from base address: "); + print_generic_expr (dump_file, DR_OFFSET (dr), TDF_SLIM); + fprintf (dump_file, "\n\tconstant offset from base address: "); + print_generic_expr (dump_file, DR_INIT (dr), TDF_SLIM); + fprintf (dump_file, "\n\tstep: "); + print_generic_expr (dump_file, DR_STEP (dr), TDF_SLIM); + fprintf (dump_file, "\n\taligned to: "); + print_generic_expr (dump_file, DR_ALIGNED_TO (dr), TDF_SLIM); + fprintf (dump_file, "\n\tbase_object: "); + print_generic_expr (dump_file, DR_BASE_OBJECT (dr), TDF_SLIM); + fprintf (dump_file, "\n\tsymbol tag: "); + print_generic_expr (dump_file, DR_SYMBOL_TAG (dr), TDF_SLIM); + fprintf (dump_file, "\n"); + } + + return dr; } -/* The dependence relation DDR cannot be represented by a distance - vector. */ +/* Returns true if FNA == FNB. */ -static inline void -non_affine_dependence_relation (struct data_dependence_relation *ddr) +static bool +affine_function_equal_p (affine_fn fna, affine_fn fnb) { - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "(Dependence relation cannot be represented by distance vector.) \n"); + unsigned i, n = VEC_length (tree, fna); - DDR_AFFINE_P (ddr) = false; + if (n != VEC_length (tree, fnb)) + return false; + + 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. */ -/* This section contains the classic Banerjee tests. */ +static affine_fn +common_affine_function (conflict_function *cf) +{ + unsigned i; + affine_fn comm; -/* Returns true iff CHREC_A and CHREC_B are not dependent on any index - variables, i.e., if the ZIV (Zero Index Variable) test is true. */ + if (!CF_NONTRIVIAL_P (cf)) + return NULL; -static inline bool -ziv_subscript_p (tree chrec_a, - tree chrec_b) + comm = cf->fns[0]; + + for (i = 1; i < cf->n; i++) + if (!affine_function_equal_p (comm, cf->fns[i])) + return NULL; + + return comm; +} + +/* Returns the base of the affine function FN. */ + +static tree +affine_function_base (affine_fn fn) { - return (evolution_function_is_constant_p (chrec_a) - && evolution_function_is_constant_p (chrec_b)); + return VEC_index (tree, fn, 0); } -/* Returns true iff CHREC_A and CHREC_B are dependent on an index - variable, i.e., if the SIV (Single Index Variable) test is true. */ +/* Returns true if FN is a constant. */ static bool -siv_subscript_p (tree chrec_a, - tree chrec_b) +affine_function_constant_p (affine_fn fn) { - if ((evolution_function_is_constant_p (chrec_a) - && evolution_function_is_univariate_p (chrec_b)) - || (evolution_function_is_constant_p (chrec_b) - && evolution_function_is_univariate_p (chrec_a))) - return true; - - if (evolution_function_is_univariate_p (chrec_a) - && evolution_function_is_univariate_p (chrec_b)) - { - switch (TREE_CODE (chrec_a)) - { - case POLYNOMIAL_CHREC: - switch (TREE_CODE (chrec_b)) - { - case POLYNOMIAL_CHREC: - if (CHREC_VARIABLE (chrec_a) != CHREC_VARIABLE (chrec_b)) - return false; - - default: - return true; - } - - default: - return true; - } - } - - return false; + unsigned i; + tree coef; + + for (i = 1; VEC_iterate (tree, fn, i, coef); i++) + if (!integer_zerop (coef)) + return false; + + return true; } -/* 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 - CHREC_B. For k >= 0, the following property is verified: +/* Returns true if FN is the zero constant function. */ - CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */ +static bool +affine_function_zero_p (affine_fn fn) +{ + return (integer_zerop (affine_function_base (fn)) + && affine_function_constant_p (fn)); +} -static void -analyze_ziv_subscript (tree chrec_a, - tree chrec_b, - tree *overlaps_a, - tree *overlaps_b, - tree *last_conflicts) +/* Returns a signed integer type with the largest precision from TA + and TB. */ + +static tree +signed_type_for_types (tree ta, tree tb) { - tree difference; - - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "(analyze_ziv_subscript \n"); - - difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b); - - switch (TREE_CODE (difference)) + if (TYPE_PRECISION (ta) > TYPE_PRECISION (tb)) + return signed_type_for (ta); + else + return signed_type_for (tb); +} + +/* 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)) { - case INTEGER_CST: - if (integer_zerop (difference)) - { - /* 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; - *last_conflicts = chrec_dont_know; - } - else - { - /* The accesses do not overlap. */ - *overlaps_a = chrec_known; - *overlaps_b = chrec_known; - *last_conflicts = integer_zero_node; - } - break; - - default: - /* We're not sure whether the indexes overlap. For the moment, - conservatively answer "don't know". */ - *overlaps_a = chrec_dont_know; - *overlaps_b = chrec_dont_know; - *last_conflicts = chrec_dont_know; - break; + n = VEC_length (tree, fna); + m = VEC_length (tree, fnb); } - - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, ")\n"); + else + { + n = VEC_length (tree, fnb); + m = VEC_length (tree, fna); + } + + ret = VEC_alloc (tree, heap, m); + for (i = 0; i < n; i++) + { + tree type = signed_type_for_types (TREE_TYPE (VEC_index (tree, fna, i)), + TREE_TYPE (VEC_index (tree, fnb, i))); + + VEC_quick_push (tree, ret, + fold_build2 (op, type, + 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, signed_type_for (TREE_TYPE (coef)), + coef, integer_zero_node)); + for (; VEC_iterate (tree, fnb, i, coef); i++) + VEC_quick_push (tree, ret, + fold_build2 (op, signed_type_for (TREE_TYPE (coef)), + integer_zero_node, coef)); + + return ret; } -/* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a - constant, and CHREC_B is an affine function. *OVERLAPS_A and - *OVERLAPS_B are initialized to the functions that describe the - relation between the elements accessed twice by CHREC_A and - CHREC_B. For k >= 0, the following property is verified: +/* Returns the sum of affine functions FNA and FNB. */ - CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */ +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 -analyze_siv_subscript_cst_affine (tree chrec_a, - tree chrec_b, - tree *overlaps_a, - tree *overlaps_b, - tree *last_conflicts) +affine_fn_free (affine_fn fn) { - bool value0, value1, value2; - tree difference = chrec_fold_minus - (integer_type_node, CHREC_LEFT (chrec_b), chrec_a); - - if (!chrec_is_positive (initial_condition (difference), &value0)) - { - *overlaps_a = chrec_dont_know; - *overlaps_b = chrec_dont_know; - *last_conflicts = chrec_dont_know; - return; - } - else + 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) { - if (value0 == false) - { - if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1)) + unsigned int i; + + for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) + { + struct subscript *subscript; + + subscript = DDR_SUBSCRIPT (ddr, i); + cf_a = SUB_CONFLICTS_IN_A (subscript); + cf_b = SUB_CONFLICTS_IN_B (subscript); + + fn_a = common_affine_function (cf_a); + fn_b = common_affine_function (cf_b); + if (!fn_a || !fn_b) { - *overlaps_a = chrec_dont_know; - *overlaps_b = chrec_dont_know; - *last_conflicts = chrec_dont_know; + SUB_DISTANCE (subscript) = chrec_dont_know; return; } - else - { - if (value1 == true) - { - /* Example: - chrec_a = 12 - chrec_b = {10, +, 1} - */ - - if (tree_fold_divides_p - (integer_type_node, CHREC_RIGHT (chrec_b), difference)) - { - *overlaps_a = integer_zero_node; - *overlaps_b = fold - (build (EXACT_DIV_EXPR, integer_type_node, - fold (build1 (ABS_EXPR, integer_type_node, difference)), - CHREC_RIGHT (chrec_b))); - *last_conflicts = integer_one_node; - return; - } - - /* When the step does not divides the difference, there are - no overlaps. */ - else - { - *overlaps_a = chrec_known; - *overlaps_b = chrec_known; - *last_conflicts = integer_zero_node; - return; - } - } - - else - { - /* Example: - chrec_a = 12 - chrec_b = {10, +, -1} - - In this case, chrec_a will not overlap with chrec_b. */ - *overlaps_a = chrec_known; - *overlaps_b = chrec_known; - *last_conflicts = integer_zero_node; - return; - } - } - } - else - { - if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2)) - { - *overlaps_a = chrec_dont_know; - *overlaps_b = chrec_dont_know; - *last_conflicts = chrec_dont_know; - return; - } - else - { - if (value2 == false) - { - /* Example: - chrec_a = 3 - chrec_b = {10, +, -1} - */ - if (tree_fold_divides_p - (integer_type_node, CHREC_RIGHT (chrec_b), difference)) - { - *overlaps_a = integer_zero_node; - *overlaps_b = fold - (build (EXACT_DIV_EXPR, integer_type_node, difference, - CHREC_RIGHT (chrec_b))); - *last_conflicts = integer_one_node; - return; - } - - /* When the step does not divides the difference, there - are no overlaps. */ - else - { - *overlaps_a = chrec_known; - *overlaps_b = chrec_known; - *last_conflicts = integer_zero_node; - return; - } - } - else - { - /* Example: - chrec_a = 3 - chrec_b = {4, +, 1} - - In this case, chrec_a will not overlap with chrec_b. */ - *overlaps_a = chrec_known; - *overlaps_b = chrec_known; - *last_conflicts = integer_zero_node; - return; - } - } - } + 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); + } } } -/* Helper recursive function for initializing the matrix A. Returns - the initial value of CHREC. */ +/* Returns the conflict function for "unknown". */ -static int -initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult) +static conflict_function * +conflict_fn_not_known (void) { - gcc_assert (chrec); + conflict_function *fn = XCNEW (conflict_function); + fn->n = NOT_KNOWN; - if (TREE_CODE (chrec) != POLYNOMIAL_CHREC) - return int_cst_value (chrec); - - A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec)); - return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult); + return fn; } -#define FLOOR_DIV(x,y) ((x) / (y)) +/* Returns the conflict function for "independent". */ -/* Solves the special case of the Diophantine equation: - | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B) +static conflict_function * +conflict_fn_no_dependence (void) +{ + conflict_function *fn = XCNEW (conflict_function); + fn->n = NO_DEPENDENCE; - Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the - number of iterations that loops X and Y run. The overlaps will be - constructed as evolutions in dimension DIM. */ + return fn; +} -static void -compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b, - tree *overlaps_a, tree *overlaps_b, - tree *last_conflicts, int dim) +/* Returns true if the address of OBJ is invariant in LOOP. */ + +static bool +object_address_invariant_in_loop_p (const struct loop *loop, const_tree obj) { - if (((step_a > 0 && step_b > 0) - || (step_a < 0 && step_b < 0))) + while (handled_component_p (obj)) { - int step_overlaps_a, step_overlaps_b; - int gcd_steps_a_b, last_conflict, tau2; + if (TREE_CODE (obj) == ARRAY_REF) + { + /* Index of the ARRAY_REF was zeroed in analyze_indices, thus we only + need to check the stride and the lower bound of the reference. */ + if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 2), + loop->num) + || chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 3), + loop->num)) + return false; + } + else if (TREE_CODE (obj) == COMPONENT_REF) + { + if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 2), + loop->num)) + return false; + } + obj = TREE_OPERAND (obj, 0); + } - gcd_steps_a_b = gcd (step_a, step_b); - step_overlaps_a = step_b / gcd_steps_a_b; - step_overlaps_b = step_a / gcd_steps_a_b; + if (!INDIRECT_REF_P (obj)) + return true; + + return !chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 0), + loop->num); +} + +/* Returns true if A and B are accesses to different objects, or to different + fields of the same object. */ + +static bool +disjoint_objects_p (tree a, tree b) +{ + tree base_a, base_b; + VEC (tree, heap) *comp_a = NULL, *comp_b = NULL; + bool ret; + + base_a = get_base_address (a); + base_b = get_base_address (b); + + if (DECL_P (base_a) + && DECL_P (base_b) + && base_a != base_b) + return true; - tau2 = FLOOR_DIV (niter, step_overlaps_a); - tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b)); - last_conflict = tau2; + if (!operand_equal_p (base_a, base_b, 0)) + return false; - *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)); - *last_conflicts = build_int_cst (NULL_TREE, last_conflict); + /* Compare the component references of A and B. We must start from the inner + ones, so record them to the vector first. */ + while (handled_component_p (a)) + { + VEC_safe_push (tree, heap, comp_a, a); + a = TREE_OPERAND (a, 0); + } + while (handled_component_p (b)) + { + VEC_safe_push (tree, heap, comp_b, b); + b = TREE_OPERAND (b, 0); } - else + ret = false; + while (1) { - *overlaps_a = integer_zero_node; - *overlaps_b = integer_zero_node; - *last_conflicts = integer_zero_node; + if (VEC_length (tree, comp_a) == 0 + || VEC_length (tree, comp_b) == 0) + break; + + a = VEC_pop (tree, comp_a); + b = VEC_pop (tree, comp_b); + + /* Real and imaginary part of a variable do not alias. */ + if ((TREE_CODE (a) == REALPART_EXPR + && TREE_CODE (b) == IMAGPART_EXPR) + || (TREE_CODE (a) == IMAGPART_EXPR + && TREE_CODE (b) == REALPART_EXPR)) + { + ret = true; + break; + } + + if (TREE_CODE (a) != TREE_CODE (b)) + break; + + /* Nothing to do for ARRAY_REFs, as the indices of array_refs in + DR_BASE_OBJECT are always zero. */ + if (TREE_CODE (a) == ARRAY_REF) + continue; + else if (TREE_CODE (a) == COMPONENT_REF) + { + if (operand_equal_p (TREE_OPERAND (a, 1), TREE_OPERAND (b, 1), 0)) + continue; + + /* Different fields of unions may overlap. */ + base_a = TREE_OPERAND (a, 0); + if (TREE_CODE (TREE_TYPE (base_a)) == UNION_TYPE) + break; + + /* Different fields of structures cannot. */ + ret = true; + break; + } + else + break; } + + VEC_free (tree, heap, comp_a); + VEC_free (tree, heap, comp_b); + + return ret; } +/* Returns false if we can prove that data references A and B do not alias, + true otherwise. */ -/* 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, +static bool +dr_may_alias_p (const struct data_reference *a, const struct data_reference *b) +{ + const_tree addr_a = DR_BASE_ADDRESS (a); + const_tree addr_b = DR_BASE_ADDRESS (b); + const_tree type_a, type_b; + const_tree decl_a = NULL_TREE, decl_b = NULL_TREE; + + /* If the sets of virtual operands are disjoint, the memory references do not + alias. */ + if (!bitmap_intersect_p (DR_VOPS (a), DR_VOPS (b))) + return false; - | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z - - has the following overlapping functions: + /* If the accessed objects are disjoint, the memory references do not + alias. */ + if (disjoint_objects_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b))) + return false; - | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v - | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v - | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v + if (!addr_a || !addr_b) + return true; - FORNOW: This is a specialized implementation for a case occurring in - a common benchmark. Implement the general algorithm. */ + /* If the references are based on different static objects, they cannot alias + (PTA should be able to disambiguate such accesses, but often it fails to, + since currently we cannot distinguish between pointer and offset in pointer + arithmetics). */ + if (TREE_CODE (addr_a) == ADDR_EXPR + && TREE_CODE (addr_b) == ADDR_EXPR) + return TREE_OPERAND (addr_a, 0) == TREE_OPERAND (addr_b, 0); + + /* An instruction writing through a restricted pointer is "independent" of any + instruction reading or writing through a different restricted pointer, + in the same block/scope. */ + + type_a = TREE_TYPE (addr_a); + type_b = TREE_TYPE (addr_b); + gcc_assert (POINTER_TYPE_P (type_a) && POINTER_TYPE_P (type_b)); + + if (TREE_CODE (addr_a) == SSA_NAME) + decl_a = SSA_NAME_VAR (addr_a); + if (TREE_CODE (addr_b) == SSA_NAME) + decl_b = SSA_NAME_VAR (addr_b); + + if (TYPE_RESTRICT (type_a) && TYPE_RESTRICT (type_b) + && (!DR_IS_READ (a) || !DR_IS_READ (b)) + && decl_a && DECL_P (decl_a) + && decl_b && DECL_P (decl_b) + && decl_a != decl_b + && TREE_CODE (DECL_CONTEXT (decl_a)) == FUNCTION_DECL + && DECL_CONTEXT (decl_a) == DECL_CONTEXT (decl_b)) + return false; -static void -compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b, - tree *overlaps_a, tree *overlaps_b, - tree *last_conflicts) + return true; +} + +static void compute_self_dependence (struct data_dependence_relation *); + +/* 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. */ + +static struct data_dependence_relation * +initialize_data_dependence_relation (struct data_reference *a, + struct data_reference *b, + VEC (loop_p, heap) *loop_nest) { - 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; + struct data_dependence_relation *res; + unsigned int i; + + res = XNEW (struct data_dependence_relation); + DDR_A (res) = a; + DDR_B (res) = b; + DDR_LOOP_NEST (res) = NULL; + DDR_REVERSED_P (res) = false; + DDR_SUBSCRIPTS (res) = NULL; + DDR_DIR_VECTS (res) = NULL; + DDR_DIST_VECTS (res) = NULL; - step_x = int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a))); - step_y = int_cst_value (CHREC_RIGHT (chrec_a)); - step_z = int_cst_value (CHREC_RIGHT (chrec_b)); + if (a == NULL || b == NULL) + { + DDR_ARE_DEPENDENT (res) = chrec_dont_know; + return res; + } - numiter_x = number_of_iterations_in_loop - (current_loops->parray[CHREC_VARIABLE (CHREC_LEFT (chrec_a))]); - numiter_y = number_of_iterations_in_loop - (current_loops->parray[CHREC_VARIABLE (chrec_a)]); - numiter_z = number_of_iterations_in_loop - (current_loops->parray[CHREC_VARIABLE (chrec_b)]); - - if (TREE_CODE (numiter_x) != INTEGER_CST) - numiter_x = current_loops->parray[CHREC_VARIABLE (CHREC_LEFT (chrec_a))] - ->estimated_nb_iterations; - if (TREE_CODE (numiter_y) != INTEGER_CST) - numiter_y = current_loops->parray[CHREC_VARIABLE (chrec_a)] - ->estimated_nb_iterations; - if (TREE_CODE (numiter_z) != INTEGER_CST) - numiter_z = current_loops->parray[CHREC_VARIABLE (chrec_b)] - ->estimated_nb_iterations; - - if (numiter_x == NULL_TREE || numiter_y == NULL_TREE - || numiter_z == NULL_TREE) - { - *overlaps_a = chrec_dont_know; - *overlaps_b = chrec_dont_know; - *last_conflicts = chrec_dont_know; - return; + /* If the data references do not alias, then they are independent. */ + if (!dr_may_alias_p (a, b)) + { + DDR_ARE_DEPENDENT (res) = chrec_known; + return res; } - niter_x = int_cst_value (numiter_x); - niter_y = int_cst_value (numiter_y); - niter_z = int_cst_value (numiter_z); - - niter = MIN (niter_x, niter_z); - compute_overlap_steps_for_affine_univar (niter, step_x, step_z, - &overlaps_a_xz, - &overlaps_b_xz, - &last_conflicts_xz, 1); - niter = MIN (niter_y, niter_z); - compute_overlap_steps_for_affine_univar (niter, step_y, step_z, - &overlaps_a_yz, - &overlaps_b_yz, - &last_conflicts_yz, 2); - niter = MIN (niter_x, niter_z); - niter = MIN (niter_y, niter); - compute_overlap_steps_for_affine_univar (niter, step_x + step_y, step_z, - &overlaps_a_xyz, - &overlaps_b_xyz, - &last_conflicts_xyz, 3); + /* When the references are exactly the same, don't spend time doing + the data dependence tests, just initialize the ddr and return. */ + if (operand_equal_p (DR_REF (a), DR_REF (b), 0)) + { + DDR_AFFINE_P (res) = true; + DDR_ARE_DEPENDENT (res) = NULL_TREE; + DDR_SUBSCRIPTS (res) = VEC_alloc (subscript_p, heap, DR_NUM_DIMENSIONS (a)); + DDR_LOOP_NEST (res) = loop_nest; + DDR_INNER_LOOP (res) = 0; + DDR_SELF_REFERENCE (res) = true; + compute_self_dependence (res); + return res; + } - xz_p = !integer_zerop (last_conflicts_xz); - yz_p = !integer_zerop (last_conflicts_yz); - xyz_p = !integer_zerop (last_conflicts_xyz); + /* If the references do not access the same object, we do not know + whether they alias or not. */ + if (!operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), 0)) + { + DDR_ARE_DEPENDENT (res) = chrec_dont_know; + return res; + } - if (xz_p || yz_p || xyz_p) + /* If the base of the object is not invariant in the loop nest, we cannot + analyze it. TODO -- in fact, it would suffice to record that there may + be arbitrary dependences in the loops where the base object varies. */ + if (!object_address_invariant_in_loop_p (VEC_index (loop_p, loop_nest, 0), + DR_BASE_OBJECT (a))) { - *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; - if (xz_p) - { - TREE_VEC_ELT (*overlaps_a, 0) = - chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 0), - overlaps_a_xz); - *overlaps_b = - chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_xz); - *last_conflicts = last_conflicts_xz; - } - if (yz_p) - { - TREE_VEC_ELT (*overlaps_a, 1) = - chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 1), - overlaps_a_yz); - *overlaps_b = - chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_yz); - *last_conflicts = last_conflicts_yz; - } - if (xyz_p) - { - TREE_VEC_ELT (*overlaps_a, 0) = - chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 0), - overlaps_a_xyz); - TREE_VEC_ELT (*overlaps_a, 1) = - chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 1), - overlaps_a_xyz); - *overlaps_b = - chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_xyz); - *last_conflicts = last_conflicts_xyz; - } + DDR_ARE_DEPENDENT (res) = chrec_dont_know; + return res; } - else + + gcc_assert (DR_NUM_DIMENSIONS (a) == DR_NUM_DIMENSIONS (b)); + + DDR_AFFINE_P (res) = true; + DDR_ARE_DEPENDENT (res) = NULL_TREE; + DDR_SUBSCRIPTS (res) = VEC_alloc (subscript_p, heap, DR_NUM_DIMENSIONS (a)); + DDR_LOOP_NEST (res) = loop_nest; + DDR_INNER_LOOP (res) = 0; + DDR_SELF_REFERENCE (res) = false; + + for (i = 0; i < DR_NUM_DIMENSIONS (a); i++) { - *overlaps_a = integer_zero_node; - *overlaps_b = integer_zero_node; - *last_conflicts = integer_zero_node; + struct subscript *subscript; + + subscript = XNEW (struct subscript); + 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); } + + return res; } -/* Determines the overlapping elements due to accesses CHREC_A and - CHREC_B, that are affine functions. This is a part of the - subscript analyzer. */ +/* Frees memory used by the conflict function F. */ static void -analyze_subscript_affine_affine (tree chrec_a, - tree chrec_b, - tree *overlaps_a, - tree *overlaps_b, - tree *last_conflicts) +free_conflict_function (conflict_function *f) { - unsigned nb_vars_a, nb_vars_b, dim; - int init_a, init_b, gamma, gcd_alpha_beta; - int tau1, tau2; - lambda_matrix A, U, S; - - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "(analyze_subscript_affine_affine \n"); - - /* For determining the initial intersection, we have to solve a - Diophantine equation. This is the most time consuming part. - - For answering to the question: "Is there a dependence?" we have - to prove that there exists a solution to the Diophantine - equation, and that the solution is in the iteration domain, - i.e. the solution is positive or zero, and that the solution - happens before the upper bound loop.nb_iterations. Otherwise - there is no dependence. This function outputs a description of - the iterations that hold the intersections. */ + unsigned i; - - nb_vars_a = nb_vars_in_chrec (chrec_a); - nb_vars_b = nb_vars_in_chrec (chrec_b); + if (CF_NONTRIVIAL_P (f)) + { + for (i = 0; i < f->n; i++) + affine_fn_free (f->fns[i]); + } + free (f); +} - dim = nb_vars_a + nb_vars_b; - U = lambda_matrix_new (dim, dim); - A = lambda_matrix_new (dim, 1); - S = lambda_matrix_new (dim, 1); +/* Frees memory used by SUBSCRIPTS. */ - init_a = initialize_matrix_A (A, chrec_a, 0, 1); - init_b = initialize_matrix_A (A, chrec_b, nb_vars_a, -1); - gamma = init_b - init_a; +static void +free_subscripts (VEC (subscript_p, heap) *subscripts) +{ + unsigned i; + subscript_p s; - /* Don't do all the hard work of solving the Diophantine equation - when we already know the solution: for example, - | {3, +, 1}_1 - | {3, +, 4}_2 - | gamma = 3 - 3 = 0. - Then the first overlap occurs during the first iterations: - | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x) - */ - if (gamma == 0) + for (i = 0; VEC_iterate (subscript_p, subscripts, i, s); i++) { - if (nb_vars_a == 1 && nb_vars_b == 1) - { - int step_a, step_b; - int niter, niter_a, niter_b; - tree numiter_a, numiter_b; - - numiter_a = number_of_iterations_in_loop - (current_loops->parray[CHREC_VARIABLE (chrec_a)]); - numiter_b = number_of_iterations_in_loop - (current_loops->parray[CHREC_VARIABLE (chrec_b)]); - - if (TREE_CODE (numiter_a) != INTEGER_CST) - numiter_a = current_loops->parray[CHREC_VARIABLE (chrec_a)] - ->estimated_nb_iterations; - if (TREE_CODE (numiter_b) != INTEGER_CST) - numiter_b = current_loops->parray[CHREC_VARIABLE (chrec_b)] - ->estimated_nb_iterations; - if (numiter_a == NULL_TREE || numiter_b == NULL_TREE) - { - *overlaps_a = chrec_dont_know; - *overlaps_b = chrec_dont_know; - *last_conflicts = chrec_dont_know; - return; - } + free_conflict_function (s->conflicting_iterations_in_a); + free_conflict_function (s->conflicting_iterations_in_b); + } + VEC_free (subscript_p, heap, subscripts); +} - niter_a = int_cst_value (numiter_a); - niter_b = int_cst_value (numiter_b); - niter = MIN (niter_a, niter_b); +/* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap + description. */ - step_a = int_cst_value (CHREC_RIGHT (chrec_a)); - step_b = int_cst_value (CHREC_RIGHT (chrec_b)); +static inline void +finalize_ddr_dependent (struct data_dependence_relation *ddr, + tree chrec) +{ + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "(dependence classified: "); + print_generic_expr (dump_file, chrec, 0); + fprintf (dump_file, ")\n"); + } - compute_overlap_steps_for_affine_univar (niter, step_a, step_b, - overlaps_a, overlaps_b, - last_conflicts, 1); - } + DDR_ARE_DEPENDENT (ddr) = chrec; + free_subscripts (DDR_SUBSCRIPTS (ddr)); + DDR_SUBSCRIPTS (ddr) = NULL; +} - else if (nb_vars_a == 2 && nb_vars_b == 1) - compute_overlap_steps_for_affine_1_2 - (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts); +/* The dependence relation DDR cannot be represented by a distance + vector. */ - else if (nb_vars_a == 1 && nb_vars_b == 2) - compute_overlap_steps_for_affine_1_2 - (chrec_b, chrec_a, overlaps_b, overlaps_a, last_conflicts); +static inline void +non_affine_dependence_relation (struct data_dependence_relation *ddr) +{ + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "(Dependence relation cannot be represented by distance vector.) \n"); - else - { - *overlaps_a = chrec_dont_know; - *overlaps_b = chrec_dont_know; - *last_conflicts = chrec_dont_know; - } - return; - } + DDR_AFFINE_P (ddr) = false; +} - /* U.A = S */ - lambda_matrix_right_hermite (A, dim, 1, S, U); + - if (S[0][0] < 0) - { - S[0][0] *= -1; - lambda_matrix_row_negate (U, dim, 0); - } - gcd_alpha_beta = S[0][0]; +/* This section contains the classic Banerjee tests. */ - /* The classic "gcd-test". */ - if (!int_divides_p (gcd_alpha_beta, gamma)) - { - /* 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; - *last_conflicts = integer_zero_node; - } +/* Returns true iff CHREC_A and CHREC_B are not dependent on any index + variables, i.e., if the ZIV (Zero Index Variable) test is true. */ - /* Both access functions are univariate. This includes SIV and MIV cases. */ - else if (nb_vars_a == 1 && nb_vars_b == 1) +static inline bool +ziv_subscript_p (const_tree chrec_a, const_tree chrec_b) +{ + return (evolution_function_is_constant_p (chrec_a) + && evolution_function_is_constant_p (chrec_b)); +} + +/* Returns true iff CHREC_A and CHREC_B are dependent on an index + variable, i.e., if the SIV (Single Index Variable) test is true. */ + +static bool +siv_subscript_p (const_tree chrec_a, const_tree chrec_b) +{ + if ((evolution_function_is_constant_p (chrec_a) + && evolution_function_is_univariate_p (chrec_b)) + || (evolution_function_is_constant_p (chrec_b) + && evolution_function_is_univariate_p (chrec_a))) + return true; + + if (evolution_function_is_univariate_p (chrec_a) + && evolution_function_is_univariate_p (chrec_b)) { - /* Both functions should have the same evolution sign. */ - if (((A[0][0] > 0 && -A[1][0] > 0) - || (A[0][0] < 0 && -A[1][0] < 0))) + switch (TREE_CODE (chrec_a)) { - /* The solutions are given by: - | - | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0] - | [u21 u22] [y0] - - For a given integer t. Using the following variables, - - | i0 = u11 * gamma / gcd_alpha_beta - | j0 = u12 * gamma / gcd_alpha_beta - | i1 = u21 - | j1 = u22 - - the solutions are: - - | x0 = i0 + i1 * t, - | y0 = j0 + j1 * t. */ - - int i0, j0, i1, j1; - - /* X0 and Y0 are the first iterations for which there is a - dependence. X0, Y0 are two solutions of the Diophantine - equation: chrec_a (X0) = chrec_b (Y0). */ - int x0, y0; - int niter, niter_a, niter_b; - tree numiter_a, numiter_b; - - numiter_a = number_of_iterations_in_loop - (current_loops->parray[CHREC_VARIABLE (chrec_a)]); - numiter_b = number_of_iterations_in_loop - (current_loops->parray[CHREC_VARIABLE (chrec_b)]); - - if (TREE_CODE (numiter_a) != INTEGER_CST) - numiter_a = current_loops->parray[CHREC_VARIABLE (chrec_a)] - ->estimated_nb_iterations; - if (TREE_CODE (numiter_b) != INTEGER_CST) - numiter_b = current_loops->parray[CHREC_VARIABLE (chrec_b)] - ->estimated_nb_iterations; - if (numiter_a == NULL_TREE || numiter_b == NULL_TREE) + case POLYNOMIAL_CHREC: + switch (TREE_CODE (chrec_b)) { - *overlaps_a = chrec_dont_know; - *overlaps_b = chrec_dont_know; - *last_conflicts = chrec_dont_know; - return; + case POLYNOMIAL_CHREC: + if (CHREC_VARIABLE (chrec_a) != CHREC_VARIABLE (chrec_b)) + return false; + + default: + return true; } + + default: + return true; + } + } + + return false; +} - niter_a = int_cst_value (numiter_a); - niter_b = int_cst_value (numiter_b); - niter = MIN (niter_a, niter_b); - - i0 = U[0][0] * gamma / gcd_alpha_beta; - j0 = U[0][1] * gamma / gcd_alpha_beta; - i1 = U[1][0]; - j1 = U[1][1]; +/* Creates a conflict function with N dimensions. The affine functions + in each dimension follow. */ - if ((i1 == 0 && i0 < 0) - || (j1 == 0 && j0 < 0)) - { - /* There is no solution. - 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; - *last_conflicts = integer_zero_node; - } +static conflict_function * +conflict_fn (unsigned n, ...) +{ + unsigned i; + conflict_function *ret = XCNEW (conflict_function); + va_list ap; + + gcc_assert (0 < n && n <= MAX_DIM); + 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; +} - else - { - if (i1 > 0) - { - tau1 = CEIL (-i0, i1); - tau2 = FLOOR_DIV (niter - i0, i1); +/* Returns constant affine function with value CST. */ - if (j1 > 0) - { - int last_conflict, min_multiple; - tau1 = MAX (tau1, CEIL (-j0, j1)); - tau2 = MIN (tau2, FLOOR_DIV (niter - j0, j1)); - - x0 = i1 * tau1 + i0; - y0 = j1 * tau1 + j0; - - /* At this point (x0, y0) is one of the - solutions to the Diophantine equation. The - next step has to compute the smallest - positive solution: the first conflicts. */ - min_multiple = MIN (x0 / i1, y0 / j1); - x0 -= i1 * min_multiple; - y0 -= j1 * min_multiple; - - tau1 = (x0 - i0)/i1; - last_conflict = tau2 - tau1; - - *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)); - *last_conflicts = build_int_cst (NULL_TREE, last_conflict); - } - else - { - /* FIXME: For the moment, the upper bound of the - iteration domain for j is not checked. */ - *overlaps_a = chrec_dont_know; - *overlaps_b = chrec_dont_know; - *last_conflicts = chrec_dont_know; - } - } - - else - { - /* FIXME: For the moment, the upper bound of the - iteration domain for i is not checked. */ - *overlaps_a = chrec_dont_know; - *overlaps_b = chrec_dont_know; - *last_conflicts = chrec_dont_know; - } - } - } - else - { - *overlaps_a = chrec_dont_know; - *overlaps_b = chrec_dont_know; - *last_conflicts = chrec_dont_know; - } - } +static affine_fn +affine_fn_cst (tree cst) +{ + affine_fn fn = VEC_alloc (tree, heap, 1); + VEC_quick_push (tree, fn, cst); + return fn; +} - else - { - *overlaps_a = chrec_dont_know; - *overlaps_b = chrec_dont_know; - *last_conflicts = chrec_dont_know; - } +/* 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; - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, " (overlaps_a = "); - print_generic_expr (dump_file, *overlaps_a, 0); - fprintf (dump_file, ")\n (overlaps_b = "); - print_generic_expr (dump_file, *overlaps_b, 0); - fprintf (dump_file, ")\n"); - } - - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, ")\n"); + 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 SIV (Single Index Variable) subscript. *OVERLAPS_A and +/* 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 CHREC_B. For k >= 0, the following property is verified: CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */ -static void -analyze_siv_subscript (tree chrec_a, - tree chrec_b, - tree *overlaps_a, - tree *overlaps_b, +static void +analyze_ziv_subscript (tree chrec_a, + tree chrec_b, + conflict_function **overlaps_a, + conflict_function **overlaps_b, tree *last_conflicts) { - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "(analyze_siv_subscript \n"); + tree type, difference; + dependence_stats.num_ziv++; - if (evolution_function_is_constant_p (chrec_a) - && evolution_function_is_affine_p (chrec_b)) - analyze_siv_subscript_cst_affine (chrec_a, chrec_b, - overlaps_a, overlaps_b, last_conflicts); - - else if (evolution_function_is_affine_p (chrec_a) - && evolution_function_is_constant_p (chrec_b)) - analyze_siv_subscript_cst_affine (chrec_b, chrec_a, - overlaps_b, overlaps_a, last_conflicts); + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "(analyze_ziv_subscript \n"); + + type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b)); + chrec_a = chrec_convert (type, chrec_a, NULL); + chrec_b = chrec_convert (type, chrec_b, NULL); + difference = chrec_fold_minus (type, chrec_a, chrec_b); - else if (evolution_function_is_affine_p (chrec_a) - && evolution_function_is_affine_p (chrec_b)) - analyze_subscript_affine_affine (chrec_a, chrec_b, - overlaps_a, overlaps_b, last_conflicts); - else + switch (TREE_CODE (difference)) { - *overlaps_a = chrec_dont_know; - *overlaps_b = chrec_dont_know; + case INTEGER_CST: + if (integer_zerop (difference)) + { + /* The difference is equal to zero: the accessed index + overlaps for each iteration in the loop. */ + *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 = conflict_fn_no_dependence (); + *overlaps_b = conflict_fn_no_dependence (); + *last_conflicts = integer_zero_node; + dependence_stats.num_ziv_independent++; + } + break; + + default: + /* We're not sure whether the indexes overlap. For the moment, + conservatively answer "don't know". */ + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "ziv test failed: difference is non-integer.\n"); + + *overlaps_a = conflict_fn_not_known (); + *overlaps_b = conflict_fn_not_known (); *last_conflicts = chrec_dont_know; + dependence_stats.num_ziv_unimplemented++; + break; } if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, ")\n"); } -/* Return true when the evolution steps of an affine CHREC divide the - constant CST. */ +/* Sets NIT to the estimated number of executions of the statements in + LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as + large as the number of iterations. If we have no reliable estimate, + the function returns false, otherwise returns true. */ -static bool -chrec_steps_divide_constant_p (tree chrec, - tree cst) +bool +estimated_loop_iterations (struct loop *loop, bool conservative, + double_int *nit) { - switch (TREE_CODE (chrec)) + estimate_numbers_of_iterations_loop (loop); + if (conservative) { - case POLYNOMIAL_CHREC: - return (tree_fold_divides_p (integer_type_node, CHREC_RIGHT (chrec), cst) - && chrec_steps_divide_constant_p (CHREC_LEFT (chrec), cst)); - - default: - /* On the initial condition, return true. */ - return true; + if (!loop->any_upper_bound) + return false; + + *nit = loop->nb_iterations_upper_bound; } -} + else + { + if (!loop->any_estimate) + return false; -/* Analyze a MIV (Multiple 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 - CHREC_B. For k >= 0, the following property is verified: + *nit = loop->nb_iterations_estimate; + } - CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */ + return true; +} -static void -analyze_miv_subscript (tree chrec_a, - tree chrec_b, - tree *overlaps_a, - tree *overlaps_b, - tree *last_conflicts) +/* Similar to estimated_loop_iterations, but returns the estimate only + if it fits to HOST_WIDE_INT. If this is not the case, or the estimate + on the number of iterations of LOOP could not be derived, returns -1. */ + +HOST_WIDE_INT +estimated_loop_iterations_int (struct loop *loop, bool conservative) +{ + double_int nit; + HOST_WIDE_INT hwi_nit; + + if (!estimated_loop_iterations (loop, conservative, &nit)) + return -1; + + if (!double_int_fits_in_shwi_p (nit)) + return -1; + hwi_nit = double_int_to_shwi (nit); + + return hwi_nit < 0 ? -1 : hwi_nit; +} + +/* Similar to estimated_loop_iterations, but returns the estimate as a tree, + and only if it fits to the int type. If this is not the case, or the + estimate on the number of iterations of LOOP could not be derived, returns + chrec_dont_know. */ + +static tree +estimated_loop_iterations_tree (struct loop *loop, bool conservative) +{ + double_int nit; + tree type; + + if (!estimated_loop_iterations (loop, conservative, &nit)) + return chrec_dont_know; + + type = lang_hooks.types.type_for_size (INT_TYPE_SIZE, true); + if (!double_int_fits_to_tree_p (type, nit)) + return chrec_dont_know; + + return double_int_to_tree (type, nit); +} + +/* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a + constant, and CHREC_B is an affine function. *OVERLAPS_A and + *OVERLAPS_B are initialized to the functions that describe the + relation between the elements accessed twice by CHREC_A and + CHREC_B. For k >= 0, the following property is verified: + + CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */ + +static void +analyze_siv_subscript_cst_affine (tree chrec_a, + tree chrec_b, + conflict_function **overlaps_a, + conflict_function **overlaps_b, + tree *last_conflicts) +{ + bool value0, value1, value2; + tree type, difference, tmp; + + type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b)); + chrec_a = chrec_convert (type, chrec_a, NULL); + chrec_b = chrec_convert (type, chrec_b, NULL); + difference = chrec_fold_minus (type, initial_condition (chrec_b), chrec_a); + + if (!chrec_is_positive (initial_condition (difference), &value0)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "siv test failed: chrec is not positive.\n"); + + dependence_stats.num_siv_unimplemented++; + *overlaps_a = conflict_fn_not_known (); + *overlaps_b = conflict_fn_not_known (); + *last_conflicts = chrec_dont_know; + return; + } + else + { + if (value0 == false) + { + if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "siv test failed: chrec not positive.\n"); + + *overlaps_a = conflict_fn_not_known (); + *overlaps_b = conflict_fn_not_known (); + *last_conflicts = chrec_dont_know; + dependence_stats.num_siv_unimplemented++; + return; + } + else + { + if (value1 == true) + { + /* Example: + chrec_a = 12 + chrec_b = {10, +, 1} + */ + + if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference)) + { + HOST_WIDE_INT numiter; + struct loop *loop = get_chrec_loop (chrec_b); + + *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node)); + tmp = fold_build2 (EXACT_DIV_EXPR, type, + fold_build1 (ABS_EXPR, type, 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 + outside the loop bounds. */ + numiter = estimated_loop_iterations_int (loop, false); + + if (numiter >= 0 + && compare_tree_int (tmp, numiter) > 0) + { + 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; + } + dependence_stats.num_siv_dependent++; + return; + } + + /* When the step does not divide the difference, there are + no overlaps. */ + else + { + *overlaps_a = conflict_fn_no_dependence (); + *overlaps_b = conflict_fn_no_dependence (); + *last_conflicts = integer_zero_node; + dependence_stats.num_siv_independent++; + return; + } + } + + else + { + /* Example: + chrec_a = 12 + chrec_b = {10, +, -1} + + In this case, chrec_a will not overlap with chrec_b. */ + *overlaps_a = conflict_fn_no_dependence (); + *overlaps_b = conflict_fn_no_dependence (); + *last_conflicts = integer_zero_node; + dependence_stats.num_siv_independent++; + return; + } + } + } + else + { + if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "siv test failed: chrec not positive.\n"); + + *overlaps_a = conflict_fn_not_known (); + *overlaps_b = conflict_fn_not_known (); + *last_conflicts = chrec_dont_know; + dependence_stats.num_siv_unimplemented++; + return; + } + else + { + if (value2 == false) + { + /* Example: + chrec_a = 3 + chrec_b = {10, +, -1} + */ + if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference)) + { + HOST_WIDE_INT numiter; + struct loop *loop = get_chrec_loop (chrec_b); + + *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node)); + tmp = fold_build2 (EXACT_DIV_EXPR, type, 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 + outside the loop bounds. */ + numiter = estimated_loop_iterations_int (loop, false); + + if (numiter >= 0 + && compare_tree_int (tmp, numiter) > 0) + { + 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; + } + dependence_stats.num_siv_dependent++; + return; + } + + /* When the step does not divide the difference, there + are no overlaps. */ + else + { + *overlaps_a = conflict_fn_no_dependence (); + *overlaps_b = conflict_fn_no_dependence (); + *last_conflicts = integer_zero_node; + dependence_stats.num_siv_independent++; + return; + } + } + else + { + /* Example: + chrec_a = 3 + chrec_b = {4, +, 1} + + In this case, chrec_a will not overlap with chrec_b. */ + *overlaps_a = conflict_fn_no_dependence (); + *overlaps_b = conflict_fn_no_dependence (); + *last_conflicts = integer_zero_node; + dependence_stats.num_siv_independent++; + return; + } + } + } + } +} + +/* Helper recursive function for initializing the matrix A. Returns + the initial value of CHREC. */ + +static tree +initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult) +{ + gcc_assert (chrec); + + switch (TREE_CODE (chrec)) + { + case POLYNOMIAL_CHREC: + gcc_assert (TREE_CODE (CHREC_RIGHT (chrec)) == INTEGER_CST); + + A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec)); + return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult); + + case PLUS_EXPR: + case MULT_EXPR: + case MINUS_EXPR: + { + tree op0 = initialize_matrix_A (A, TREE_OPERAND (chrec, 0), index, mult); + tree op1 = initialize_matrix_A (A, TREE_OPERAND (chrec, 1), index, mult); + + return chrec_fold_op (TREE_CODE (chrec), chrec_type (chrec), op0, op1); + } + + case NOP_EXPR: + { + tree op = initialize_matrix_A (A, TREE_OPERAND (chrec, 0), index, mult); + return chrec_convert (chrec_type (chrec), op, NULL); + } + + case INTEGER_CST: + return chrec; + + default: + gcc_unreachable (); + return NULL_TREE; + } +} + +#define FLOOR_DIV(x,y) ((x) / (y)) + +/* Solves the special case of the Diophantine equation: + | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B) + + Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the + number of iterations that loops X and Y run. The overlaps will be + constructed as evolutions in dimension DIM. */ + +static void +compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b, + affine_fn *overlaps_a, + affine_fn *overlaps_b, + tree *last_conflicts, int dim) +{ + if (((step_a > 0 && step_b > 0) + || (step_a < 0 && step_b < 0))) + { + int step_overlaps_a, step_overlaps_b; + int gcd_steps_a_b, last_conflict, tau2; + + gcd_steps_a_b = gcd (step_a, step_b); + step_overlaps_a = step_b / gcd_steps_a_b; + step_overlaps_b = step_a / gcd_steps_a_b; + + if (niter > 0) + { + tau2 = FLOOR_DIV (niter, step_overlaps_a); + tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b)); + last_conflict = tau2; + *last_conflicts = build_int_cst (NULL_TREE, last_conflict); + } + else + *last_conflicts = chrec_dont_know; + + *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)); + } + + else + { + *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, + + | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z + + has the following overlapping functions: + + | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v + | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v + | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v + + FORNOW: This is a specialized implementation for a case occurring in + a common benchmark. Implement the general algorithm. */ + +static void +compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_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; + HOST_WIDE_INT niter_x, niter_y, niter_z, niter; + 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)); + step_z = int_cst_value (CHREC_RIGHT (chrec_b)); + + niter_x = + estimated_loop_iterations_int (get_chrec_loop (CHREC_LEFT (chrec_a)), + false); + niter_y = estimated_loop_iterations_int (get_chrec_loop (chrec_a), false); + niter_z = estimated_loop_iterations_int (get_chrec_loop (chrec_b), false); + + if (niter_x < 0 || niter_y < 0 || niter_z < 0) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "overlap steps test failed: no iteration counts.\n"); + + *overlaps_a = conflict_fn_not_known (); + *overlaps_b = conflict_fn_not_known (); + *last_conflicts = chrec_dont_know; + return; + } + + niter = MIN (niter_x, niter_z); + compute_overlap_steps_for_affine_univar (niter, step_x, step_z, + &overlaps_a_xz, + &overlaps_b_xz, + &last_conflicts_xz, 1); + niter = MIN (niter_y, niter_z); + compute_overlap_steps_for_affine_univar (niter, step_y, step_z, + &overlaps_a_yz, + &overlaps_b_yz, + &last_conflicts_yz, 2); + niter = MIN (niter_x, niter_z); + niter = MIN (niter_y, niter); + compute_overlap_steps_for_affine_univar (niter, step_x + step_y, step_z, + &overlaps_a_xyz, + &overlaps_b_xyz, + &last_conflicts_xyz, 3); + + xz_p = !integer_zerop (last_conflicts_xz); + yz_p = !integer_zerop (last_conflicts_yz); + xyz_p = !integer_zerop (last_conflicts_xyz); + + if (xz_p || yz_p || xyz_p) + { + ova1 = affine_fn_cst (integer_zero_node); + ova2 = affine_fn_cst (integer_zero_node); + ovb = affine_fn_cst (integer_zero_node); + if (xz_p) + { + 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) + { + 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) + { + 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 = 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 + CHREC_B, that are affine functions. This function cannot handle + symbolic evolution functions, ie. when initial conditions are + parameters, because it uses lambda matrices of integers. */ + +static void +analyze_subscript_affine_affine (tree chrec_a, + tree chrec_b, + conflict_function **overlaps_a, + conflict_function **overlaps_b, + tree *last_conflicts) +{ + unsigned nb_vars_a, nb_vars_b, dim; + HOST_WIDE_INT init_a, init_b, gamma, gcd_alpha_beta; + lambda_matrix A, U, S; + + if (eq_evolutions_p (chrec_a, chrec_b)) + { + /* The accessed index overlaps for each iteration in the + loop. */ + *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; + } + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "(analyze_subscript_affine_affine \n"); + + /* For determining the initial intersection, we have to solve a + Diophantine equation. This is the most time consuming part. + + For answering to the question: "Is there a dependence?" we have + to prove that there exists a solution to the Diophantine + equation, and that the solution is in the iteration domain, + i.e. the solution is positive or zero, and that the solution + happens before the upper bound loop.nb_iterations. Otherwise + there is no dependence. This function outputs a description of + the iterations that hold the intersections. */ + + nb_vars_a = nb_vars_in_chrec (chrec_a); + nb_vars_b = nb_vars_in_chrec (chrec_b); + + dim = nb_vars_a + nb_vars_b; + U = lambda_matrix_new (dim, dim); + A = lambda_matrix_new (dim, 1); + S = lambda_matrix_new (dim, 1); + + init_a = int_cst_value (initialize_matrix_A (A, chrec_a, 0, 1)); + init_b = int_cst_value (initialize_matrix_A (A, chrec_b, nb_vars_a, -1)); + gamma = init_b - init_a; + + /* Don't do all the hard work of solving the Diophantine equation + when we already know the solution: for example, + | {3, +, 1}_1 + | {3, +, 4}_2 + | gamma = 3 - 3 = 0. + Then the first overlap occurs during the first iterations: + | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x) + */ + if (gamma == 0) + { + if (nb_vars_a == 1 && nb_vars_b == 1) + { + HOST_WIDE_INT step_a, step_b; + HOST_WIDE_INT niter, niter_a, niter_b; + affine_fn ova, ovb; + + niter_a = estimated_loop_iterations_int (get_chrec_loop (chrec_a), + false); + niter_b = estimated_loop_iterations_int (get_chrec_loop (chrec_b), + false); + niter = MIN (niter_a, niter_b); + step_a = int_cst_value (CHREC_RIGHT (chrec_a)); + step_b = int_cst_value (CHREC_RIGHT (chrec_b)); + + compute_overlap_steps_for_affine_univar (niter, step_a, step_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) + compute_overlap_steps_for_affine_1_2 + (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts); + + else if (nb_vars_a == 1 && nb_vars_b == 2) + compute_overlap_steps_for_affine_1_2 + (chrec_b, chrec_a, overlaps_b, overlaps_a, last_conflicts); + + else + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "affine-affine test failed: too many variables.\n"); + *overlaps_a = conflict_fn_not_known (); + *overlaps_b = conflict_fn_not_known (); + *last_conflicts = chrec_dont_know; + } + goto end_analyze_subs_aa; + } + + /* U.A = S */ + lambda_matrix_right_hermite (A, dim, 1, S, U); + + if (S[0][0] < 0) + { + S[0][0] *= -1; + lambda_matrix_row_negate (U, dim, 0); + } + gcd_alpha_beta = S[0][0]; + + /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5, + but that is a quite strange case. Instead of ICEing, answer + don't know. */ + if (gcd_alpha_beta == 0) + { + *overlaps_a = conflict_fn_not_known (); + *overlaps_b = conflict_fn_not_known (); + *last_conflicts = chrec_dont_know; + goto end_analyze_subs_aa; + } + + /* The classic "gcd-test". */ + if (!int_divides_p (gcd_alpha_beta, gamma)) + { + /* The "gcd-test" has determined that there is no integer + solution, i.e. there is no dependence. */ + *overlaps_a = conflict_fn_no_dependence (); + *overlaps_b = conflict_fn_no_dependence (); + *last_conflicts = integer_zero_node; + } + + /* Both access functions are univariate. This includes SIV and MIV cases. */ + else if (nb_vars_a == 1 && nb_vars_b == 1) + { + /* Both functions should have the same evolution sign. */ + if (((A[0][0] > 0 && -A[1][0] > 0) + || (A[0][0] < 0 && -A[1][0] < 0))) + { + /* The solutions are given by: + | + | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0] + | [u21 u22] [y0] + + For a given integer t. Using the following variables, + + | i0 = u11 * gamma / gcd_alpha_beta + | j0 = u12 * gamma / gcd_alpha_beta + | i1 = u21 + | j1 = u22 + + the solutions are: + + | x0 = i0 + i1 * t, + | y0 = j0 + j1 * t. */ + HOST_WIDE_INT i0, j0, i1, j1; + + i0 = U[0][0] * gamma / gcd_alpha_beta; + j0 = U[0][1] * gamma / gcd_alpha_beta; + i1 = U[1][0]; + j1 = U[1][1]; + + if ((i1 == 0 && i0 < 0) + || (j1 == 0 && j0 < 0)) + { + /* There is no solution. + 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 = conflict_fn_no_dependence (); + *overlaps_b = conflict_fn_no_dependence (); + *last_conflicts = integer_zero_node; + goto end_analyze_subs_aa; + } + + if (i1 > 0 && j1 > 0) + { + HOST_WIDE_INT niter_a = estimated_loop_iterations_int + (get_chrec_loop (chrec_a), false); + HOST_WIDE_INT niter_b = estimated_loop_iterations_int + (get_chrec_loop (chrec_b), false); + HOST_WIDE_INT niter = MIN (niter_a, niter_b); + + /* (X0, Y0) is a solution of the Diophantine equation: + "chrec_a (X0) = chrec_b (Y0)". */ + HOST_WIDE_INT tau1 = MAX (CEIL (-i0, i1), + CEIL (-j0, j1)); + HOST_WIDE_INT x0 = i1 * tau1 + i0; + HOST_WIDE_INT y0 = j1 * tau1 + j0; + + /* (X1, Y1) is the smallest positive solution of the eq + "chrec_a (X1) = chrec_b (Y1)", i.e. this is where the + first conflict occurs. */ + HOST_WIDE_INT min_multiple = MIN (x0 / i1, y0 / j1); + HOST_WIDE_INT x1 = x0 - i1 * min_multiple; + HOST_WIDE_INT y1 = y0 - j1 * min_multiple; + + if (niter > 0) + { + HOST_WIDE_INT tau2 = MIN (FLOOR_DIV (niter - i0, i1), + FLOOR_DIV (niter - j0, j1)); + HOST_WIDE_INT last_conflict = tau2 - (x1 - i0)/i1; + + /* If the overlap occurs outside of the bounds of the + loop, there is no dependence. */ + if (x1 > niter || y1 > niter) + { + *overlaps_a = conflict_fn_no_dependence (); + *overlaps_b = conflict_fn_no_dependence (); + *last_conflicts = integer_zero_node; + goto end_analyze_subs_aa; + } + else + *last_conflicts = build_int_cst (NULL_TREE, last_conflict); + } + else + *last_conflicts = chrec_dont_know; + + *overlaps_a + = conflict_fn (1, + affine_fn_univar (build_int_cst (NULL_TREE, x1), + 1, + build_int_cst (NULL_TREE, i1))); + *overlaps_b + = conflict_fn (1, + affine_fn_univar (build_int_cst (NULL_TREE, y1), + 1, + build_int_cst (NULL_TREE, j1))); + } + else + { + /* FIXME: For the moment, the upper bound of the + iteration domain for i and j is not checked. */ + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "affine-affine test failed: unimplemented.\n"); + *overlaps_a = conflict_fn_not_known (); + *overlaps_b = conflict_fn_not_known (); + *last_conflicts = chrec_dont_know; + } + } + else + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "affine-affine test failed: unimplemented.\n"); + *overlaps_a = conflict_fn_not_known (); + *overlaps_b = conflict_fn_not_known (); + *last_conflicts = chrec_dont_know; + } + } + else + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "affine-affine test failed: unimplemented.\n"); + *overlaps_a = conflict_fn_not_known (); + *overlaps_b = conflict_fn_not_known (); + *last_conflicts = chrec_dont_know; + } + +end_analyze_subs_aa: + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, " (overlaps_a = "); + dump_conflict_function (dump_file, *overlaps_a); + fprintf (dump_file, ")\n (overlaps_b = "); + dump_conflict_function (dump_file, *overlaps_b); + fprintf (dump_file, ")\n"); + fprintf (dump_file, ")\n"); + } +} + +/* Returns true when analyze_subscript_affine_affine can be used for + determining the dependence relation between chrec_a and chrec_b, + that contain symbols. This function modifies chrec_a and chrec_b + such that the analysis result is the same, and such that they don't + contain symbols, and then can safely be passed to the analyzer. + + Example: The analysis of the following tuples of evolutions produce + the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1 + vs. {0, +, 1}_1 + + {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1) + {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1) +*/ + +static bool +can_use_analyze_subscript_affine_affine (tree *chrec_a, tree *chrec_b) +{ + tree diff, type, left_a, left_b, right_b; + + if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a)) + || chrec_contains_symbols (CHREC_RIGHT (*chrec_b))) + /* FIXME: For the moment not handled. Might be refined later. */ + return false; + + type = chrec_type (*chrec_a); + left_a = CHREC_LEFT (*chrec_a); + left_b = chrec_convert (type, CHREC_LEFT (*chrec_b), NULL); + diff = chrec_fold_minus (type, left_a, left_b); + + if (!evolution_function_is_constant_p (diff)) + return false; + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "can_use_subscript_aff_aff_for_symbolic \n"); + + *chrec_a = build_polynomial_chrec (CHREC_VARIABLE (*chrec_a), + diff, CHREC_RIGHT (*chrec_a)); + right_b = chrec_convert (type, CHREC_RIGHT (*chrec_b), NULL); + *chrec_b = build_polynomial_chrec (CHREC_VARIABLE (*chrec_b), + build_int_cst (type, 0), + right_b); + return true; +} + +/* Analyze a SIV (Single 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 + CHREC_B. For k >= 0, the following property is verified: + + CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */ + +static void +analyze_siv_subscript (tree chrec_a, + tree chrec_b, + conflict_function **overlaps_a, + conflict_function **overlaps_b, + tree *last_conflicts, + int loop_nest_num) +{ + dependence_stats.num_siv++; + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "(analyze_siv_subscript \n"); + + if (evolution_function_is_constant_p (chrec_a) + && evolution_function_is_affine_in_loop (chrec_b, loop_nest_num)) + analyze_siv_subscript_cst_affine (chrec_a, chrec_b, + overlaps_a, overlaps_b, last_conflicts); + + else if (evolution_function_is_affine_in_loop (chrec_a, loop_nest_num) + && evolution_function_is_constant_p (chrec_b)) + analyze_siv_subscript_cst_affine (chrec_b, chrec_a, + overlaps_b, overlaps_a, last_conflicts); + + else if (evolution_function_is_affine_in_loop (chrec_a, loop_nest_num) + && evolution_function_is_affine_in_loop (chrec_b, loop_nest_num)) + { + if (!chrec_contains_symbols (chrec_a) + && !chrec_contains_symbols (chrec_b)) + { + analyze_subscript_affine_affine (chrec_a, chrec_b, + overlaps_a, overlaps_b, + last_conflicts); + + if (CF_NOT_KNOWN_P (*overlaps_a) + || CF_NOT_KNOWN_P (*overlaps_b)) + dependence_stats.num_siv_unimplemented++; + 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++; + } + else if (can_use_analyze_subscript_affine_affine (&chrec_a, + &chrec_b)) + { + analyze_subscript_affine_affine (chrec_a, chrec_b, + overlaps_a, overlaps_b, + last_conflicts); + + if (CF_NOT_KNOWN_P (*overlaps_a) + || CF_NOT_KNOWN_P (*overlaps_b)) + dependence_stats.num_siv_unimplemented++; + 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++; + } + else + goto siv_subscript_dontknow; + } + + else + { + siv_subscript_dontknow:; + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "siv test failed: unimplemented.\n"); + *overlaps_a = conflict_fn_not_known (); + *overlaps_b = conflict_fn_not_known (); + *last_conflicts = chrec_dont_know; + dependence_stats.num_siv_unimplemented++; + } + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, ")\n"); +} + +/* Returns false if we can prove that the greatest common divisor of the steps + of CHREC does not divide CST, false otherwise. */ + +static bool +gcd_of_steps_may_divide_p (const_tree chrec, const_tree cst) +{ + HOST_WIDE_INT cd = 0, val; + tree step; + + if (!host_integerp (cst, 0)) + return true; + val = tree_low_cst (cst, 0); + + while (TREE_CODE (chrec) == POLYNOMIAL_CHREC) + { + step = CHREC_RIGHT (chrec); + if (!host_integerp (step, 0)) + return true; + cd = gcd (cd, tree_low_cst (step, 0)); + chrec = CHREC_LEFT (chrec); + } + + return val % cd == 0; +} + +/* Analyze a MIV (Multiple Index Variable) subscript with respect to + LOOP_NEST. *OVERLAPS_A and *OVERLAPS_B are initialized to the + functions that describe the relation between the elements accessed + twice by CHREC_A and CHREC_B. For k >= 0, the following property + is verified: + + CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */ + +static void +analyze_miv_subscript (tree chrec_a, + tree chrec_b, + conflict_function **overlaps_a, + conflict_function **overlaps_b, + tree *last_conflicts, + struct loop *loop_nest) { /* FIXME: This is a MIV subscript, not yet handled. Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from (A[i] vs. A[j]). - In the SIV test we had to solve a Diophantine equation with two - variables. In the MIV case we have to solve a Diophantine - equation with 2*n variables (if the subscript uses n IVs). - */ - tree difference; + In the SIV test we had to solve a Diophantine equation with two + variables. In the MIV case we have to solve a Diophantine + equation with 2*n variables (if the subscript uses n IVs). + */ + tree type, difference; + + dependence_stats.num_miv++; + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "(analyze_miv_subscript \n"); + + type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b)); + chrec_a = chrec_convert (type, chrec_a, NULL); + chrec_b = chrec_convert (type, chrec_b, NULL); + difference = chrec_fold_minus (type, chrec_a, chrec_b); + + if (eq_evolutions_p (chrec_a, chrec_b)) + { + /* Access functions are the same: all the elements are accessed + in the same order. */ + *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node)); + *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node)); + *last_conflicts = estimated_loop_iterations_tree + (get_chrec_loop (chrec_a), true); + dependence_stats.num_miv_dependent++; + } + + else if (evolution_function_is_constant_p (difference) + /* For the moment, the following is verified: + evolution_function_is_affine_multivariate_p (chrec_a, + loop_nest->num) */ + && !gcd_of_steps_may_divide_p (chrec_a, difference)) + { + /* testsuite/.../ssa-chrec-33.c + {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2 + + The difference is 1, and all the evolution steps are multiples + of 2, consequently there are no overlapping elements. */ + *overlaps_a = conflict_fn_no_dependence (); + *overlaps_b = conflict_fn_no_dependence (); + *last_conflicts = integer_zero_node; + dependence_stats.num_miv_independent++; + } + + else if (evolution_function_is_affine_multivariate_p (chrec_a, loop_nest->num) + && !chrec_contains_symbols (chrec_a) + && evolution_function_is_affine_multivariate_p (chrec_b, loop_nest->num) + && !chrec_contains_symbols (chrec_b)) + { + /* testsuite/.../ssa-chrec-35.c + {0, +, 1}_2 vs. {0, +, 1}_3 + the overlapping elements are respectively located at iterations: + {0, +, 1}_x and {0, +, 1}_x, + in other words, we have the equality: + {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x) + + Other examples: + {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) = + {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y) + + {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) = + {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) + */ + analyze_subscript_affine_affine (chrec_a, chrec_b, + overlaps_a, overlaps_b, last_conflicts); + + if (CF_NOT_KNOWN_P (*overlaps_a) + || CF_NOT_KNOWN_P (*overlaps_b)) + dependence_stats.num_miv_unimplemented++; + 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++; + } + + else + { + /* When the analysis is too difficult, answer "don't know". */ + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "analyze_miv_subscript test failed: unimplemented.\n"); + + *overlaps_a = conflict_fn_not_known (); + *overlaps_b = conflict_fn_not_known (); + *last_conflicts = chrec_dont_know; + dependence_stats.num_miv_unimplemented++; + } + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, ")\n"); +} + +/* Determines the iterations for which CHREC_A is equal to CHREC_B in + with respect to LOOP_NEST. OVERLAP_ITERATIONS_A and + OVERLAP_ITERATIONS_B are initialized with two functions that + describe the iterations that contain conflicting elements. + + Remark: For an integer k >= 0, the following equality is true: + + CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)). +*/ + +static void +analyze_overlapping_iterations (tree chrec_a, + tree chrec_b, + conflict_function **overlap_iterations_a, + conflict_function **overlap_iterations_b, + tree *last_conflicts, struct loop *loop_nest) +{ + unsigned int lnn = loop_nest->num; + + dependence_stats.num_subscript_tests++; + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "(analyze_overlapping_iterations \n"); + fprintf (dump_file, " (chrec_a = "); + print_generic_expr (dump_file, chrec_a, 0); + fprintf (dump_file, ")\n (chrec_b = "); + print_generic_expr (dump_file, chrec_b, 0); + fprintf (dump_file, ")\n"); + } + + if (chrec_a == NULL_TREE + || chrec_b == NULL_TREE + || chrec_contains_undetermined (chrec_a) + || chrec_contains_undetermined (chrec_b)) + { + dependence_stats.num_subscript_undetermined++; + + *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 + on every iteration. */ + else if (eq_evolutions_p (chrec_a, chrec_b) + && evolution_function_is_affine_multivariate_p (chrec_a, lnn)) + { + dependence_stats.num_same_subscript_function++; + *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; + } + + /* If they aren't the same, and aren't affine, we can't do anything + yet. */ + else if ((chrec_contains_symbols (chrec_a) + || chrec_contains_symbols (chrec_b)) + && (!evolution_function_is_affine_multivariate_p (chrec_a, lnn) + || !evolution_function_is_affine_multivariate_p (chrec_b, lnn))) + { + dependence_stats.num_subscript_undetermined++; + *overlap_iterations_a = conflict_fn_not_known (); + *overlap_iterations_b = conflict_fn_not_known (); + } + + else if (ziv_subscript_p (chrec_a, chrec_b)) + analyze_ziv_subscript (chrec_a, chrec_b, + overlap_iterations_a, overlap_iterations_b, + last_conflicts); + + else if (siv_subscript_p (chrec_a, chrec_b)) + analyze_siv_subscript (chrec_a, chrec_b, + overlap_iterations_a, overlap_iterations_b, + last_conflicts, lnn); + + else + analyze_miv_subscript (chrec_a, chrec_b, + overlap_iterations_a, overlap_iterations_b, + last_conflicts, loop_nest); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, " (overlap_iterations_a = "); + dump_conflict_function (dump_file, *overlap_iterations_a); + fprintf (dump_file, ")\n (overlap_iterations_b = "); + dump_conflict_function (dump_file, *overlap_iterations_b); + fprintf (dump_file, ")\n"); + fprintf (dump_file, ")\n"); + } +} + +/* Helper function for uniquely inserting distance vectors. */ + +static void +save_dist_v (struct data_dependence_relation *ddr, lambda_vector dist_v) +{ + unsigned i; + lambda_vector v; + + for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, v); i++) + if (lambda_vector_equal (v, dist_v, DDR_NB_LOOPS (ddr))) + return; + + VEC_safe_push (lambda_vector, heap, DDR_DIST_VECTS (ddr), dist_v); +} + +/* Helper function for uniquely inserting direction vectors. */ + +static void +save_dir_v (struct data_dependence_relation *ddr, lambda_vector dir_v) +{ + unsigned i; + lambda_vector v; + + for (i = 0; VEC_iterate (lambda_vector, DDR_DIR_VECTS (ddr), i, v); i++) + if (lambda_vector_equal (v, dir_v, DDR_NB_LOOPS (ddr))) + return; + + VEC_safe_push (lambda_vector, heap, DDR_DIR_VECTS (ddr), dir_v); +} + +/* Add a distance of 1 on all the loops outer than INDEX. If we + haven't yet determined a distance for this outer loop, push a new + distance vector composed of the previous distance, and a distance + of 1 for this outer loop. Example: + + | loop_1 + | loop_2 + | A[10] + | endloop_2 + | endloop_1 + + Saved vectors are of the form (dist_in_1, dist_in_2). First, we + save (0, 1), then we have to save (1, 0). */ + +static void +add_outer_distances (struct data_dependence_relation *ddr, + lambda_vector dist_v, int index) +{ + /* For each outer loop where init_v is not set, the accesses are + in dependence of distance 1 in the loop. */ + while (--index >= 0) + { + lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr)); + lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr)); + save_v[index] = 1; + save_dist_v (ddr, save_v); + } +} + +/* Return false when fail to represent the data dependence as a + distance vector. INIT_B is set to true when a component has been + added to the distance vector DIST_V. INDEX_CARRY is then set to + the index in DIST_V that carries the dependence. */ + +static bool +build_classic_dist_vector_1 (struct data_dependence_relation *ddr, + struct data_reference *ddr_a, + struct data_reference *ddr_b, + lambda_vector dist_v, bool *init_b, + int *index_carry) +{ + unsigned i; + lambda_vector init_v = lambda_vector_new (DDR_NB_LOOPS (ddr)); + + for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) + { + tree access_fn_a, access_fn_b; + struct subscript *subscript = DDR_SUBSCRIPT (ddr, i); + + if (chrec_contains_undetermined (SUB_DISTANCE (subscript))) + { + non_affine_dependence_relation (ddr); + return false; + } + + access_fn_a = DR_ACCESS_FN (ddr_a, i); + access_fn_b = DR_ACCESS_FN (ddr_b, i); + + if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC + && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC) + { + int dist, index; + int index_a = index_in_loop_nest (CHREC_VARIABLE (access_fn_a), + DDR_LOOP_NEST (ddr)); + int index_b = index_in_loop_nest (CHREC_VARIABLE (access_fn_b), + DDR_LOOP_NEST (ddr)); + + /* The dependence is carried by the outermost loop. Example: + | loop_1 + | A[{4, +, 1}_1] + | loop_2 + | A[{5, +, 1}_2] + | endloop_2 + | endloop_1 + In this case, the dependence is carried by loop_1. */ + index = index_a < index_b ? index_a : index_b; + *index_carry = MIN (index, *index_carry); + + if (chrec_contains_undetermined (SUB_DISTANCE (subscript))) + { + non_affine_dependence_relation (ddr); + return false; + } + + dist = int_cst_value (SUB_DISTANCE (subscript)); + + /* This is the subscript coupling test. If we have already + recorded a distance for this loop (a distance coming from + another subscript), it should be the same. For example, + in the following code, there is no dependence: + + | loop i = 0, N, 1 + | T[i+1][i] = ... + | ... = T[i][i] + | endloop + */ + if (init_v[index] != 0 && dist_v[index] != dist) + { + finalize_ddr_dependent (ddr, chrec_known); + return false; + } + + dist_v[index] = dist; + init_v[index] = 1; + *init_b = true; + } + else if (!operand_equal_p (access_fn_a, access_fn_b, 0)) + { + /* This can be for example an affine vs. constant dependence + (T[i] vs. T[3]) that is not an affine dependence and is + not representable as a distance vector. */ + non_affine_dependence_relation (ddr); + return false; + } + } + + return true; +} + +/* Return true when the DDR contains only constant access functions. */ + +static bool +constant_access_functions (const struct data_dependence_relation *ddr) +{ + unsigned i; + + for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) + if (!evolution_function_is_constant_p (DR_ACCESS_FN (DDR_A (ddr), i)) + || !evolution_function_is_constant_p (DR_ACCESS_FN (DDR_B (ddr), i))) + return false; + + return true; +} + +/* Helper function for the case where DDR_A and DDR_B are the same + multivariate access function with a constant step. For an example + see pr34635-1.c. */ + +static void +add_multivariate_self_dist (struct data_dependence_relation *ddr, tree c_2) +{ + int x_1, x_2; + tree c_1 = CHREC_LEFT (c_2); + tree c_0 = CHREC_LEFT (c_1); + lambda_vector dist_v; + int v1, v2, cd; + + /* Polynomials with more than 2 variables are not handled yet. When + the evolution steps are parameters, it is not possible to + represent the dependence using classical distance vectors. */ + if (TREE_CODE (c_0) != INTEGER_CST + || TREE_CODE (CHREC_RIGHT (c_1)) != INTEGER_CST + || TREE_CODE (CHREC_RIGHT (c_2)) != INTEGER_CST) + { + DDR_AFFINE_P (ddr) = false; + return; + } + + x_2 = index_in_loop_nest (CHREC_VARIABLE (c_2), DDR_LOOP_NEST (ddr)); + x_1 = index_in_loop_nest (CHREC_VARIABLE (c_1), DDR_LOOP_NEST (ddr)); + + /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2). */ + dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr)); + v1 = int_cst_value (CHREC_RIGHT (c_1)); + v2 = int_cst_value (CHREC_RIGHT (c_2)); + cd = gcd (v1, v2); + v1 /= cd; + v2 /= cd; + + if (v2 < 0) + { + v2 = -v2; + v1 = -v1; + } + + dist_v[x_1] = v2; + dist_v[x_2] = -v1; + save_dist_v (ddr, dist_v); + + add_outer_distances (ddr, dist_v, x_1); +} + +/* Helper function for the case where DDR_A and DDR_B are the same + access functions. */ + +static void +add_other_self_distances (struct data_dependence_relation *ddr) +{ + lambda_vector dist_v; + unsigned i; + int index_carry = DDR_NB_LOOPS (ddr); + + for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) + { + tree access_fun = DR_ACCESS_FN (DDR_A (ddr), i); + + if (TREE_CODE (access_fun) == POLYNOMIAL_CHREC) + { + if (!evolution_function_is_univariate_p (access_fun)) + { + if (DDR_NUM_SUBSCRIPTS (ddr) != 1) + { + DDR_ARE_DEPENDENT (ddr) = chrec_dont_know; + return; + } + + access_fun = DR_ACCESS_FN (DDR_A (ddr), 0); + + if (TREE_CODE (CHREC_LEFT (access_fun)) == POLYNOMIAL_CHREC) + add_multivariate_self_dist (ddr, access_fun); + else + /* The evolution step is not constant: it varies in + the outer loop, so this cannot be represented by a + distance vector. For example in pr34635.c the + evolution is {0, +, {0, +, 4}_1}_2. */ + DDR_AFFINE_P (ddr) = false; + + return; + } + + index_carry = MIN (index_carry, + index_in_loop_nest (CHREC_VARIABLE (access_fun), + DDR_LOOP_NEST (ddr))); + } + } + + dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr)); + add_outer_distances (ddr, dist_v, index_carry); +} + +static void +insert_innermost_unit_dist_vector (struct data_dependence_relation *ddr) +{ + lambda_vector dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr)); + + dist_v[DDR_INNER_LOOP (ddr)] = 1; + save_dist_v (ddr, dist_v); +} + +/* Adds a unit distance vector to DDR when there is a 0 overlap. This + is the case for example when access functions are the same and + equal to a constant, as in: + + | loop_1 + | A[3] = ... + | ... = A[3] + | endloop_1 + + in which case the distance vectors are (0) and (1). */ + +static void +add_distance_for_zero_overlaps (struct data_dependence_relation *ddr) +{ + unsigned i, j; + + for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) + { + subscript_p sub = DDR_SUBSCRIPT (ddr, i); + conflict_function *ca = SUB_CONFLICTS_IN_A (sub); + conflict_function *cb = SUB_CONFLICTS_IN_B (sub); + + for (j = 0; j < ca->n; j++) + if (affine_function_zero_p (ca->fns[j])) + { + insert_innermost_unit_dist_vector (ddr); + return; + } + + for (j = 0; j < cb->n; j++) + if (affine_function_zero_p (cb->fns[j])) + { + insert_innermost_unit_dist_vector (ddr); + return; + } + } +} + +/* Compute the classic per loop distance vector. DDR is the data + dependence relation to build a vector from. Return false when fail + to represent the data dependence as a distance vector. */ + +static bool +build_classic_dist_vector (struct data_dependence_relation *ddr, + struct loop *loop_nest) +{ + bool init_b = false; + int index_carry = DDR_NB_LOOPS (ddr); + lambda_vector dist_v; + + if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE) + return false; + + if (same_access_functions (ddr)) + { + /* Save the 0 vector. */ + dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr)); + save_dist_v (ddr, dist_v); + + if (constant_access_functions (ddr)) + add_distance_for_zero_overlaps (ddr); + + if (DDR_NB_LOOPS (ddr) > 1) + add_other_self_distances (ddr); + + return true; + } + + dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr)); + if (!build_classic_dist_vector_1 (ddr, DDR_A (ddr), DDR_B (ddr), + dist_v, &init_b, &index_carry)) + return false; + + /* Save the distance vector if we initialized one. */ + if (init_b) + { + /* Verify a basic constraint: classic distance vectors should + always be lexicographically positive. + + Data references are collected in the order of execution of + the program, thus for the following loop + + | for (i = 1; i < 100; i++) + | for (j = 1; j < 100; j++) + | { + | t = T[j+1][i-1]; // A + | T[j][i] = t + 2; // B + | } + + references are collected following the direction of the wind: + A then B. The data dependence tests are performed also + following this order, such that we're looking at the distance + separating the elements accessed by A from the elements later + accessed by B. But in this example, the distance returned by + test_dep (A, B) is lexicographically negative (-1, 1), that + means that the access A occurs later than B with respect to + the outer loop, ie. we're actually looking upwind. In this + case we solve test_dep (B, A) looking downwind to the + lexicographically positive solution, that returns the + distance vector (1, -1). */ + if (!lambda_vector_lexico_pos (dist_v, DDR_NB_LOOPS (ddr))) + { + lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr)); + if (!subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr), + loop_nest)) + return false; + compute_subscript_distance (ddr); + if (!build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr), + save_v, &init_b, &index_carry)) + return false; + save_dist_v (ddr, save_v); + DDR_REVERSED_P (ddr) = true; + + /* In this case there is a dependence forward for all the + outer loops: + + | for (k = 1; k < 100; k++) + | for (i = 1; i < 100; i++) + | for (j = 1; j < 100; j++) + | { + | t = T[j+1][i-1]; // A + | T[j][i] = t + 2; // B + | } + + the vectors are: + (0, 1, -1) + (1, 1, -1) + (1, -1, 1) + */ + if (DDR_NB_LOOPS (ddr) > 1) + { + add_outer_distances (ddr, save_v, index_carry); + add_outer_distances (ddr, dist_v, index_carry); + } + } + else + { + lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr)); + lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr)); + + if (DDR_NB_LOOPS (ddr) > 1) + { + lambda_vector opposite_v = lambda_vector_new (DDR_NB_LOOPS (ddr)); + + if (!subscript_dependence_tester_1 (ddr, DDR_B (ddr), + DDR_A (ddr), loop_nest)) + return false; + compute_subscript_distance (ddr); + if (!build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr), + opposite_v, &init_b, + &index_carry)) + return false; + + save_dist_v (ddr, save_v); + add_outer_distances (ddr, dist_v, index_carry); + add_outer_distances (ddr, opposite_v, index_carry); + } + else + save_dist_v (ddr, save_v); + } + } + else + { + /* There is a distance of 1 on all the outer loops: Example: + there is a dependence of distance 1 on loop_1 for the array A. + + | loop_1 + | A[5] = ... + | endloop + */ + add_outer_distances (ddr, dist_v, + lambda_vector_first_nz (dist_v, + DDR_NB_LOOPS (ddr), 0)); + } + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + unsigned i; + + fprintf (dump_file, "(build_classic_dist_vector\n"); + for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++) + { + fprintf (dump_file, " dist_vector = ("); + print_lambda_vector (dump_file, DDR_DIST_VECT (ddr, i), + DDR_NB_LOOPS (ddr)); + fprintf (dump_file, " )\n"); + } + fprintf (dump_file, ")\n"); + } + + return true; +} + +/* Return the direction for a given distance. + FIXME: Computing dir this way is suboptimal, since dir can catch + cases that dist is unable to represent. */ + +static inline enum data_dependence_direction +dir_from_dist (int dist) +{ + if (dist > 0) + return dir_positive; + else if (dist < 0) + return dir_negative; + else + return dir_equal; +} + +/* Compute the classic per loop direction vector. DDR is the data + dependence relation to build a vector from. */ + +static void +build_classic_dir_vector (struct data_dependence_relation *ddr) +{ + unsigned i, j; + lambda_vector dist_v; + + for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, dist_v); i++) + { + lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr)); + + for (j = 0; j < DDR_NB_LOOPS (ddr); j++) + dir_v[j] = dir_from_dist (dist_v[j]); + + save_dir_v (ddr, dir_v); + } +} + +/* Helper function. Returns true when there is a dependence between + data references DRA and DRB. */ + +static bool +subscript_dependence_tester_1 (struct data_dependence_relation *ddr, + struct data_reference *dra, + struct data_reference *drb, + struct loop *loop_nest) +{ + unsigned int i; + tree last_conflicts; + struct subscript *subscript; + + for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript); + i++) + { + 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, loop_nest); + + 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 (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; + } + + else + { + if (SUB_CONFLICTS_IN_A (subscript)) + free_conflict_function (SUB_CONFLICTS_IN_A (subscript)); + if (SUB_CONFLICTS_IN_B (subscript)) + free_conflict_function (SUB_CONFLICTS_IN_B (subscript)); + + SUB_CONFLICTS_IN_A (subscript) = overlaps_a; + SUB_CONFLICTS_IN_B (subscript) = overlaps_b; + SUB_LAST_CONFLICT (subscript) = last_conflicts; + } + } + + return true; +} + +/* Computes the conflicting iterations in LOOP_NEST, and initialize DDR. */ + +static void +subscript_dependence_tester (struct data_dependence_relation *ddr, + struct loop *loop_nest) +{ + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "(subscript_dependence_tester \n"); + + if (subscript_dependence_tester_1 (ddr, DDR_A (ddr), DDR_B (ddr), loop_nest)) + dependence_stats.num_dependence_dependent++; + + compute_subscript_distance (ddr); + if (build_classic_dist_vector (ddr, loop_nest)) + build_classic_dir_vector (ddr); + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, ")\n"); +} + +/* Returns true when all the access functions of A are affine or + constant with respect to LOOP_NEST. */ + +static bool +access_functions_are_affine_or_constant_p (const struct data_reference *a, + const struct loop *loop_nest) +{ + unsigned int i; + VEC(tree,heap) *fns = DR_ACCESS_FNS (a); + tree t; + + for (i = 0; VEC_iterate (tree, fns, i, t); i++) + if (!evolution_function_is_invariant_p (t, loop_nest->num) + && !evolution_function_is_affine_multivariate_p (t, loop_nest->num)) + return false; + + return true; +} + +/* Initializes an equation for an OMEGA problem using the information + contained in the ACCESS_FUN. Returns true when the operation + succeeded. + + PB is the omega constraint system. + EQ is the number of the equation to be initialized. + OFFSET is used for shifting the variables names in the constraints: + a constrain is composed of 2 * the number of variables surrounding + dependence accesses. OFFSET is set either to 0 for the first n variables, + then it is set to n. + ACCESS_FUN is expected to be an affine chrec. */ + +static bool +init_omega_eq_with_af (omega_pb pb, unsigned eq, + unsigned int offset, tree access_fun, + struct data_dependence_relation *ddr) +{ + switch (TREE_CODE (access_fun)) + { + case POLYNOMIAL_CHREC: + { + tree left = CHREC_LEFT (access_fun); + tree right = CHREC_RIGHT (access_fun); + int var = CHREC_VARIABLE (access_fun); + unsigned var_idx; + + if (TREE_CODE (right) != INTEGER_CST) + return false; + + var_idx = index_in_loop_nest (var, DDR_LOOP_NEST (ddr)); + pb->eqs[eq].coef[offset + var_idx + 1] = int_cst_value (right); + + /* Compute the innermost loop index. */ + DDR_INNER_LOOP (ddr) = MAX (DDR_INNER_LOOP (ddr), var_idx); + + if (offset == 0) + pb->eqs[eq].coef[var_idx + DDR_NB_LOOPS (ddr) + 1] + += int_cst_value (right); + + switch (TREE_CODE (left)) + { + case POLYNOMIAL_CHREC: + return init_omega_eq_with_af (pb, eq, offset, left, ddr); + + case INTEGER_CST: + pb->eqs[eq].coef[0] += int_cst_value (left); + return true; + + default: + return false; + } + } + + case INTEGER_CST: + pb->eqs[eq].coef[0] += int_cst_value (access_fun); + return true; + + default: + return false; + } +} + +/* As explained in the comments preceding init_omega_for_ddr, we have + to set up a system for each loop level, setting outer loops + variation to zero, and current loop variation to positive or zero. + Save each lexico positive distance vector. */ + +static void +omega_extract_distance_vectors (omega_pb pb, + struct data_dependence_relation *ddr) +{ + int eq, geq; + unsigned i, j; + struct loop *loopi, *loopj; + enum omega_result res; + + /* Set a new problem for each loop in the nest. The basis is the + problem that we have initialized until now. On top of this we + add new constraints. */ + for (i = 0; i <= DDR_INNER_LOOP (ddr) + && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++) + { + int dist = 0; + omega_pb copy = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), + DDR_NB_LOOPS (ddr)); + + omega_copy_problem (copy, pb); + + /* For all the outer loops "loop_j", add "dj = 0". */ + for (j = 0; + j < i && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), j, loopj); j++) + { + eq = omega_add_zero_eq (copy, omega_black); + copy->eqs[eq].coef[j + 1] = 1; + } + + /* For "loop_i", add "0 <= di". */ + geq = omega_add_zero_geq (copy, omega_black); + copy->geqs[geq].coef[i + 1] = 1; + + /* Reduce the constraint system, and test that the current + problem is feasible. */ + res = omega_simplify_problem (copy); + if (res == omega_false + || res == omega_unknown + || copy->num_geqs > (int) DDR_NB_LOOPS (ddr)) + goto next_problem; + + for (eq = 0; eq < copy->num_subs; eq++) + if (copy->subs[eq].key == (int) i + 1) + { + dist = copy->subs[eq].coef[0]; + goto found_dist; + } + + if (dist == 0) + { + /* Reinitialize problem... */ + omega_copy_problem (copy, pb); + for (j = 0; + j < i && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), j, loopj); j++) + { + eq = omega_add_zero_eq (copy, omega_black); + copy->eqs[eq].coef[j + 1] = 1; + } + + /* ..., but this time "di = 1". */ + eq = omega_add_zero_eq (copy, omega_black); + copy->eqs[eq].coef[i + 1] = 1; + copy->eqs[eq].coef[0] = -1; + + res = omega_simplify_problem (copy); + if (res == omega_false + || res == omega_unknown + || copy->num_geqs > (int) DDR_NB_LOOPS (ddr)) + goto next_problem; + + for (eq = 0; eq < copy->num_subs; eq++) + if (copy->subs[eq].key == (int) i + 1) + { + dist = copy->subs[eq].coef[0]; + goto found_dist; + } + } + + found_dist:; + /* Save the lexicographically positive distance vector. */ + if (dist >= 0) + { + lambda_vector dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr)); + lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr)); + + dist_v[i] = dist; + + for (eq = 0; eq < copy->num_subs; eq++) + if (copy->subs[eq].key > 0) + { + dist = copy->subs[eq].coef[0]; + dist_v[copy->subs[eq].key - 1] = dist; + } + + for (j = 0; j < DDR_NB_LOOPS (ddr); j++) + dir_v[j] = dir_from_dist (dist_v[j]); + + save_dist_v (ddr, dist_v); + save_dir_v (ddr, dir_v); + } + + next_problem:; + omega_free_problem (copy); + } +} + +/* This is called for each subscript of a tuple of data references: + insert an equality for representing the conflicts. */ + +static bool +omega_setup_subscript (tree access_fun_a, tree access_fun_b, + struct data_dependence_relation *ddr, + omega_pb pb, bool *maybe_dependent) +{ + int eq; + tree type = signed_type_for_types (TREE_TYPE (access_fun_a), + TREE_TYPE (access_fun_b)); + tree fun_a = chrec_convert (type, access_fun_a, NULL); + tree fun_b = chrec_convert (type, access_fun_b, NULL); + tree difference = chrec_fold_minus (type, fun_a, fun_b); + + /* When the fun_a - fun_b is not constant, the dependence is not + captured by the classic distance vector representation. */ + if (TREE_CODE (difference) != INTEGER_CST) + return false; + + /* ZIV test. */ + if (ziv_subscript_p (fun_a, fun_b) && !integer_zerop (difference)) + { + /* There is no dependence. */ + *maybe_dependent = false; + return true; + } + + fun_b = chrec_fold_multiply (type, fun_b, integer_minus_one_node); + + eq = omega_add_zero_eq (pb, omega_black); + if (!init_omega_eq_with_af (pb, eq, DDR_NB_LOOPS (ddr), fun_a, ddr) + || !init_omega_eq_with_af (pb, eq, 0, fun_b, ddr)) + /* There is probably a dependence, but the system of + constraints cannot be built: answer "don't know". */ + return false; + + /* GCD test. */ + if (DDR_NB_LOOPS (ddr) != 0 && pb->eqs[eq].coef[0] + && !int_divides_p (lambda_vector_gcd + ((lambda_vector) &(pb->eqs[eq].coef[1]), + 2 * DDR_NB_LOOPS (ddr)), + pb->eqs[eq].coef[0])) + { + /* There is no dependence. */ + *maybe_dependent = false; + return true; + } + + return true; +} + +/* Helper function, same as init_omega_for_ddr but specialized for + data references A and B. */ + +static bool +init_omega_for_ddr_1 (struct data_reference *dra, struct data_reference *drb, + struct data_dependence_relation *ddr, + omega_pb pb, bool *maybe_dependent) +{ + unsigned i; + int ineq; + struct loop *loopi; + unsigned nb_loops = DDR_NB_LOOPS (ddr); + + /* Insert an equality per subscript. */ + for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) + { + if (!omega_setup_subscript (DR_ACCESS_FN (dra, i), DR_ACCESS_FN (drb, i), + ddr, pb, maybe_dependent)) + return false; + else if (*maybe_dependent == false) + { + /* There is no dependence. */ + DDR_ARE_DEPENDENT (ddr) = chrec_known; + return true; + } + } + + /* Insert inequalities: constraints corresponding to the iteration + domain, i.e. the loops surrounding the references "loop_x" and + the distance variables "dx". The layout of the OMEGA + representation is as follows: + - coef[0] is the constant + - coef[1..nb_loops] are the protected variables that will not be + removed by the solver: the "dx" + - coef[nb_loops + 1, 2*nb_loops] are the loop variables: "loop_x". + */ + for (i = 0; i <= DDR_INNER_LOOP (ddr) + && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++) + { + HOST_WIDE_INT nbi = estimated_loop_iterations_int (loopi, false); + + /* 0 <= loop_x */ + ineq = omega_add_zero_geq (pb, omega_black); + pb->geqs[ineq].coef[i + nb_loops + 1] = 1; + + /* 0 <= loop_x + dx */ + ineq = omega_add_zero_geq (pb, omega_black); + pb->geqs[ineq].coef[i + nb_loops + 1] = 1; + pb->geqs[ineq].coef[i + 1] = 1; + + if (nbi != -1) + { + /* loop_x <= nb_iters */ + ineq = omega_add_zero_geq (pb, omega_black); + pb->geqs[ineq].coef[i + nb_loops + 1] = -1; + pb->geqs[ineq].coef[0] = nbi; + + /* loop_x + dx <= nb_iters */ + ineq = omega_add_zero_geq (pb, omega_black); + pb->geqs[ineq].coef[i + nb_loops + 1] = -1; + pb->geqs[ineq].coef[i + 1] = -1; + pb->geqs[ineq].coef[0] = nbi; + + /* A step "dx" bigger than nb_iters is not feasible, so + add "0 <= nb_iters + dx", */ + ineq = omega_add_zero_geq (pb, omega_black); + pb->geqs[ineq].coef[i + 1] = 1; + pb->geqs[ineq].coef[0] = nbi; + /* and "dx <= nb_iters". */ + ineq = omega_add_zero_geq (pb, omega_black); + pb->geqs[ineq].coef[i + 1] = -1; + pb->geqs[ineq].coef[0] = nbi; + } + } + + omega_extract_distance_vectors (pb, ddr); + + return true; +} + +/* Sets up the Omega dependence problem for the data dependence + relation DDR. Returns false when the constraint system cannot be + built, ie. when the test answers "don't know". Returns true + otherwise, and when independence has been proved (using one of the + trivial dependence test), set MAYBE_DEPENDENT to false, otherwise + set MAYBE_DEPENDENT to true. + + Example: for setting up the dependence system corresponding to the + conflicting accesses + + | loop_i + | loop_j + | A[i, i+1] = ... + | ... A[2*j, 2*(i + j)] + | endloop_j + | endloop_i + + the following constraints come from the iteration domain: + + 0 <= i <= Ni + 0 <= i + di <= Ni + 0 <= j <= Nj + 0 <= j + dj <= Nj + + where di, dj are the distance variables. The constraints + representing the conflicting elements are: + + i = 2 * (j + dj) + i + 1 = 2 * (i + di + j + dj) + + For asking that the resulting distance vector (di, dj) be + lexicographically positive, we insert the constraint "di >= 0". If + "di = 0" in the solution, we fix that component to zero, and we + look at the inner loops: we set a new problem where all the outer + loop distances are zero, and fix this inner component to be + positive. When one of the components is positive, we save that + distance, and set a new problem where the distance on this loop is + zero, searching for other distances in the inner loops. Here is + the classic example that illustrates that we have to set for each + inner loop a new problem: + + | loop_1 + | loop_2 + | A[10] + | endloop_2 + | endloop_1 + + we have to save two distances (1, 0) and (0, 1). + + Given two array references, refA and refB, we have to set the + dependence problem twice, refA vs. refB and refB vs. refA, and we + cannot do a single test, as refB might occur before refA in the + inner loops, and the contrary when considering outer loops: ex. + + | loop_0 + | loop_1 + | loop_2 + | T[{1,+,1}_2][{1,+,1}_1] // refA + | T[{2,+,1}_2][{0,+,1}_1] // refB + | endloop_2 + | endloop_1 + | endloop_0 + + refB touches the elements in T before refA, and thus for the same + loop_0 refB precedes refA: ie. the distance vector (0, 1, -1) + but for successive loop_0 iterations, we have (1, -1, 1) + + The Omega solver expects the distance variables ("di" in the + previous example) to come first in the constraint system (as + variables to be protected, or "safe" variables), the constraint + system is built using the following layout: + + "cst | distance vars | index vars". +*/ + +static bool +init_omega_for_ddr (struct data_dependence_relation *ddr, + bool *maybe_dependent) +{ + omega_pb pb; + bool res = false; + + *maybe_dependent = true; + + if (same_access_functions (ddr)) + { + unsigned j; + lambda_vector dir_v; + + /* Save the 0 vector. */ + save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr))); + dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr)); + for (j = 0; j < DDR_NB_LOOPS (ddr); j++) + dir_v[j] = dir_equal; + save_dir_v (ddr, dir_v); + + /* Save the dependences carried by outer loops. */ + pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr)); + res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb, + maybe_dependent); + omega_free_problem (pb); + return res; + } + + /* Omega expects the protected variables (those that have to be kept + after elimination) to appear first in the constraint system. + These variables are the distance variables. In the following + initialization we declare NB_LOOPS safe variables, and the total + number of variables for the constraint system is 2*NB_LOOPS. */ + pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr)); + res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb, + maybe_dependent); + omega_free_problem (pb); + + /* Stop computation if not decidable, or no dependence. */ + if (res == false || *maybe_dependent == false) + return res; + + pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr)); + res = init_omega_for_ddr_1 (DDR_B (ddr), DDR_A (ddr), ddr, pb, + maybe_dependent); + omega_free_problem (pb); + + return res; +} + +/* Return true when DDR contains the same information as that stored + in DIR_VECTS and in DIST_VECTS, return false otherwise. */ + +static bool +ddr_consistent_p (FILE *file, + struct data_dependence_relation *ddr, + VEC (lambda_vector, heap) *dist_vects, + VEC (lambda_vector, heap) *dir_vects) +{ + unsigned int i, j; + + /* If dump_file is set, output there. */ + if (dump_file && (dump_flags & TDF_DETAILS)) + file = dump_file; + + if (VEC_length (lambda_vector, dist_vects) != DDR_NUM_DIST_VECTS (ddr)) + { + lambda_vector b_dist_v; + fprintf (file, "\n(Number of distance vectors differ: Banerjee has %d, Omega has %d.\n", + VEC_length (lambda_vector, dist_vects), + DDR_NUM_DIST_VECTS (ddr)); + + fprintf (file, "Banerjee dist vectors:\n"); + for (i = 0; VEC_iterate (lambda_vector, dist_vects, i, b_dist_v); i++) + print_lambda_vector (file, b_dist_v, DDR_NB_LOOPS (ddr)); + + fprintf (file, "Omega dist vectors:\n"); + for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++) + print_lambda_vector (file, DDR_DIST_VECT (ddr, i), DDR_NB_LOOPS (ddr)); + + fprintf (file, "data dependence relation:\n"); + dump_data_dependence_relation (file, ddr); + + fprintf (file, ")\n"); + return false; + } + + if (VEC_length (lambda_vector, dir_vects) != DDR_NUM_DIR_VECTS (ddr)) + { + fprintf (file, "\n(Number of direction vectors differ: Banerjee has %d, Omega has %d.)\n", + VEC_length (lambda_vector, dir_vects), + DDR_NUM_DIR_VECTS (ddr)); + return false; + } + + for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++) + { + lambda_vector a_dist_v; + lambda_vector b_dist_v = DDR_DIST_VECT (ddr, i); + + /* Distance vectors are not ordered in the same way in the DDR + and in the DIST_VECTS: search for a matching vector. */ + for (j = 0; VEC_iterate (lambda_vector, dist_vects, j, a_dist_v); j++) + if (lambda_vector_equal (a_dist_v, b_dist_v, DDR_NB_LOOPS (ddr))) + break; + + if (j == VEC_length (lambda_vector, dist_vects)) + { + fprintf (file, "\n(Dist vectors from the first dependence analyzer:\n"); + print_dist_vectors (file, dist_vects, DDR_NB_LOOPS (ddr)); + fprintf (file, "not found in Omega dist vectors:\n"); + print_dist_vectors (file, DDR_DIST_VECTS (ddr), DDR_NB_LOOPS (ddr)); + fprintf (file, "data dependence relation:\n"); + dump_data_dependence_relation (file, ddr); + fprintf (file, ")\n"); + } + } + + for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++) + { + lambda_vector a_dir_v; + lambda_vector b_dir_v = DDR_DIR_VECT (ddr, i); + + /* Direction vectors are not ordered in the same way in the DDR + and in the DIR_VECTS: search for a matching vector. */ + for (j = 0; VEC_iterate (lambda_vector, dir_vects, j, a_dir_v); j++) + if (lambda_vector_equal (a_dir_v, b_dir_v, DDR_NB_LOOPS (ddr))) + break; + + if (j == VEC_length (lambda_vector, dist_vects)) + { + fprintf (file, "\n(Dir vectors from the first dependence analyzer:\n"); + print_dir_vectors (file, dir_vects, DDR_NB_LOOPS (ddr)); + fprintf (file, "not found in Omega dir vectors:\n"); + print_dir_vectors (file, DDR_DIR_VECTS (ddr), DDR_NB_LOOPS (ddr)); + fprintf (file, "data dependence relation:\n"); + dump_data_dependence_relation (file, ddr); + fprintf (file, ")\n"); + } + } + + return true; +} + +/* This computes the affine dependence relation between A and B with + respect to LOOP_NEST. CHREC_KNOWN is used for representing the + independence between two accesses, while CHREC_DONT_KNOW is used + for representing the unknown relation. + + Note that it is possible to stop the computation of the dependence + relation the first time we detect a CHREC_KNOWN element for a given + subscript. */ + +static void +compute_affine_dependence (struct data_dependence_relation *ddr, + struct loop *loop_nest) +{ + struct data_reference *dra = DDR_A (ddr); + struct data_reference *drb = DDR_B (ddr); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "(compute_affine_dependence\n"); + fprintf (dump_file, " (stmt_a = \n"); + print_gimple_stmt (dump_file, DR_STMT (dra), 0, 0); + fprintf (dump_file, ")\n (stmt_b = \n"); + print_gimple_stmt (dump_file, DR_STMT (drb), 0, 0); + fprintf (dump_file, ")\n"); + } + + /* Analyze only when the dependence relation is not yet known. */ + if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE + && !DDR_SELF_REFERENCE (ddr)) + { + dependence_stats.num_dependence_tests++; + + if (access_functions_are_affine_or_constant_p (dra, loop_nest) + && access_functions_are_affine_or_constant_p (drb, loop_nest)) + { + if (flag_check_data_deps) + { + /* Compute the dependences using the first algorithm. */ + subscript_dependence_tester (ddr, loop_nest); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "\n\nBanerjee Analyzer\n"); + dump_data_dependence_relation (dump_file, ddr); + } + + if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE) + { + bool maybe_dependent; + VEC (lambda_vector, heap) *dir_vects, *dist_vects; + + /* Save the result of the first DD analyzer. */ + dist_vects = DDR_DIST_VECTS (ddr); + dir_vects = DDR_DIR_VECTS (ddr); + + /* Reset the information. */ + DDR_DIST_VECTS (ddr) = NULL; + DDR_DIR_VECTS (ddr) = NULL; + + /* Compute the same information using Omega. */ + if (!init_omega_for_ddr (ddr, &maybe_dependent)) + goto csys_dont_know; + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Omega Analyzer\n"); + dump_data_dependence_relation (dump_file, ddr); + } + + /* Check that we get the same information. */ + if (maybe_dependent) + gcc_assert (ddr_consistent_p (stderr, ddr, dist_vects, + dir_vects)); + } + } + else + subscript_dependence_tester (ddr, loop_nest); + } + + /* As a last case, if the dependence cannot be determined, or if + the dependence is considered too difficult to determine, answer + "don't know". */ + else + { + csys_dont_know:; + dependence_stats.num_dependence_undetermined++; + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Data ref a:\n"); + dump_data_reference (dump_file, dra); + fprintf (dump_file, "Data ref b:\n"); + dump_data_reference (dump_file, drb); + fprintf (dump_file, "affine dependence test not usable: access function not affine or constant.\n"); + } + finalize_ddr_dependent (ddr, chrec_dont_know); + } + } if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "(analyze_miv_subscript \n"); - - difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b); - - if (chrec_zerop (difference)) + fprintf (dump_file, ")\n"); +} + +/* This computes the dependence relation for the same data + reference into DDR. */ + +static void +compute_self_dependence (struct data_dependence_relation *ddr) +{ + unsigned int i; + struct subscript *subscript; + + if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE) + return; + + for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript); + i++) { - /* Access functions are the same: all the elements are accessed - in the same order. */ - *overlaps_a = integer_zero_node; - *overlaps_b = integer_zero_node; - *last_conflicts = number_of_iterations_in_loop - (current_loops->parray[CHREC_VARIABLE (chrec_a)]); + if (SUB_CONFLICTS_IN_A (subscript)) + free_conflict_function (SUB_CONFLICTS_IN_A (subscript)); + if (SUB_CONFLICTS_IN_B (subscript)) + free_conflict_function (SUB_CONFLICTS_IN_B (subscript)); + + /* The accessed index overlaps for each iteration. */ + 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; } - - else if (evolution_function_is_constant_p (difference) - /* For the moment, the following is verified: - evolution_function_is_affine_multivariate_p (chrec_a) */ - && !chrec_steps_divide_constant_p (chrec_a, difference)) + + /* The distance vector is the zero vector. */ + save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr))); + save_dir_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr))); +} + +/* Compute in DEPENDENCE_RELATIONS the data dependence graph for all + the data references in DATAREFS, in the LOOP_NEST. When + COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self + relations. */ + +void +compute_all_dependences (VEC (data_reference_p, heap) *datarefs, + VEC (ddr_p, heap) **dependence_relations, + VEC (loop_p, heap) *loop_nest, + bool compute_self_and_rr) +{ + struct data_dependence_relation *ddr; + struct data_reference *a, *b; + unsigned int i, j; + + for (i = 0; VEC_iterate (data_reference_p, datarefs, i, a); i++) + for (j = i + 1; VEC_iterate (data_reference_p, datarefs, j, b); j++) + if (!DR_IS_READ (a) || !DR_IS_READ (b) || compute_self_and_rr) + { + ddr = initialize_data_dependence_relation (a, b, loop_nest); + VEC_safe_push (ddr_p, heap, *dependence_relations, ddr); + compute_affine_dependence (ddr, VEC_index (loop_p, loop_nest, 0)); + } + + if (compute_self_and_rr) + for (i = 0; VEC_iterate (data_reference_p, datarefs, i, a); i++) + { + ddr = initialize_data_dependence_relation (a, a, loop_nest); + VEC_safe_push (ddr_p, heap, *dependence_relations, ddr); + compute_self_dependence (ddr); + } +} + +/* Stores the locations of memory references in STMT to REFERENCES. Returns + true if STMT clobbers memory, false otherwise. */ + +bool +get_references_in_stmt (gimple stmt, VEC (data_ref_loc, heap) **references) +{ + bool clobbers_memory = false; + data_ref_loc *ref; + tree *op0, *op1; + enum gimple_code stmt_code = gimple_code (stmt); + + *references = NULL; + + /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects. + Calls have side-effects, except those to const or pure + functions. */ + if ((stmt_code == GIMPLE_CALL + && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE))) + || (stmt_code == GIMPLE_ASM + && gimple_asm_volatile_p (stmt))) + clobbers_memory = true; + + if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)) + return clobbers_memory; + + if (stmt_code == GIMPLE_ASSIGN) { - /* testsuite/.../ssa-chrec-33.c - {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2 - - 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; - *last_conflicts = integer_zero_node; + tree base; + op0 = gimple_assign_lhs_ptr (stmt); + op1 = gimple_assign_rhs1_ptr (stmt); + + if (DECL_P (*op1) + || (REFERENCE_CLASS_P (*op1) + && (base = get_base_address (*op1)) + && TREE_CODE (base) != SSA_NAME)) + { + ref = VEC_safe_push (data_ref_loc, heap, *references, NULL); + ref->pos = op1; + ref->is_read = true; + } + + if (DECL_P (*op0) + || (REFERENCE_CLASS_P (*op0) && get_base_address (*op0))) + { + ref = VEC_safe_push (data_ref_loc, heap, *references, NULL); + ref->pos = op0; + ref->is_read = false; + } } - - else if (evolution_function_is_affine_multivariate_p (chrec_a) - && evolution_function_is_affine_multivariate_p (chrec_b)) + else if (stmt_code == GIMPLE_CALL) { - /* testsuite/.../ssa-chrec-35.c - {0, +, 1}_2 vs. {0, +, 1}_3 - the overlapping elements are respectively located at iterations: - {0, +, 1}_x and {0, +, 1}_x, - in other words, we have the equality: - {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x) - - Other examples: - {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) = - {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y) + unsigned i, n = gimple_call_num_args (stmt); - {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) = - {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) - */ - analyze_subscript_affine_affine (chrec_a, chrec_b, - overlaps_a, overlaps_b, last_conflicts); + for (i = 0; i < n; i++) + { + op0 = gimple_call_arg_ptr (stmt, i); + + if (DECL_P (*op0) + || (REFERENCE_CLASS_P (*op0) && get_base_address (*op0))) + { + ref = VEC_safe_push (data_ref_loc, heap, *references, NULL); + ref->pos = op0; + ref->is_read = true; + } + } + } + + return clobbers_memory; +} + +/* Stores the data references in STMT to DATAREFS. If there is an unanalyzable + reference, returns false, otherwise returns true. NEST is the outermost + loop of the loop nest in that the references should be analyzed. */ + +static bool +find_data_references_in_stmt (struct loop *nest, gimple stmt, + VEC (data_reference_p, heap) **datarefs) +{ + unsigned i; + VEC (data_ref_loc, heap) *references; + data_ref_loc *ref; + bool ret = true; + data_reference_p dr; + + if (get_references_in_stmt (stmt, &references)) + { + VEC_free (data_ref_loc, heap, references); + return false; } + + for (i = 0; VEC_iterate (data_ref_loc, references, i, ref); i++) + { + dr = create_data_ref (nest, *ref->pos, stmt, ref->is_read); + gcc_assert (dr != NULL); + /* FIXME -- data dependence analysis does not work correctly for objects with + invariant addresses. Let us fail here until the problem is fixed. */ + if (dr_address_invariant_p (dr)) + { + free_data_ref (dr); + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "\tFAILED as dr address is invariant\n"); + ret = false; + break; + } + + VEC_safe_push (data_reference_p, heap, *datarefs, dr); + } + VEC_free (data_ref_loc, heap, references); + return ret; +} + +/* Search the data references in LOOP, and record the information into + DATAREFS. Returns chrec_dont_know when failing to analyze a + difficult case, returns NULL_TREE otherwise. + + TODO: This function should be made smarter so that it can handle address + arithmetic as if they were array accesses, etc. */ + +static tree +find_data_references_in_loop (struct loop *loop, + VEC (data_reference_p, heap) **datarefs) +{ + basic_block bb, *bbs; + unsigned int i; + gimple_stmt_iterator bsi; + + bbs = get_loop_body_in_dom_order (loop); + + for (i = 0; i < loop->num_nodes; i++) + { + bb = bbs[i]; + + for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) + { + gimple stmt = gsi_stmt (bsi); + + if (!find_data_references_in_stmt (loop, stmt, datarefs)) + { + struct data_reference *res; + res = XCNEW (struct data_reference); + VEC_safe_push (data_reference_p, heap, *datarefs, res); + + free (bbs); + return chrec_dont_know; + } + } + } + free (bbs); + + return NULL_TREE; +} + +/* Recursive helper function. */ + +static bool +find_loop_nest_1 (struct loop *loop, VEC (loop_p, heap) **loop_nest) +{ + /* Inner loops of the nest should not contain siblings. Example: + when there are two consecutive loops, + + | loop_0 + | loop_1 + | A[{0, +, 1}_1] + | endloop_1 + | loop_2 + | A[{0, +, 1}_2] + | endloop_2 + | endloop_0 + + the dependence relation cannot be captured by the distance + abstraction. */ + if (loop->next) + return false; + + VEC_safe_push (loop_p, heap, *loop_nest, loop); + if (loop->inner) + return find_loop_nest_1 (loop->inner, loop_nest); + return true; +} + +/* Return false when the LOOP is not well nested. Otherwise return + true and insert in LOOP_NEST the loops of the nest. LOOP_NEST will + contain the loops from the outermost to the innermost, as they will + appear in the classic distance vector. */ + +bool +find_loop_nest (struct loop *loop, VEC (loop_p, heap) **loop_nest) +{ + VEC_safe_push (loop_p, heap, *loop_nest, loop); + if (loop->inner) + return find_loop_nest_1 (loop->inner, loop_nest); + return true; +} + +/* Returns true when the data dependences have been computed, false otherwise. + Given a loop nest LOOP, the following vectors are returned: + DATAREFS is initialized to all the array elements contained in this loop, + DEPENDENCE_RELATIONS contains the relations between the data references. + Compute read-read and self relations if + COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */ + +bool +compute_data_dependences_for_loop (struct loop *loop, + bool compute_self_and_read_read_dependences, + VEC (data_reference_p, heap) **datarefs, + VEC (ddr_p, heap) **dependence_relations) +{ + bool res = true; + VEC (loop_p, heap) *vloops = VEC_alloc (loop_p, heap, 3); + + memset (&dependence_stats, 0, sizeof (dependence_stats)); + + /* If the loop nest is not well formed, or one of the data references + is not computable, give up without spending time to compute other + dependences. */ + if (!loop + || !find_loop_nest (loop, &vloops) + || find_data_references_in_loop (loop, datarefs) == chrec_dont_know) + { + struct data_dependence_relation *ddr; + + /* Insert a single relation into dependence_relations: + chrec_dont_know. */ + ddr = initialize_data_dependence_relation (NULL, NULL, vloops); + VEC_safe_push (ddr_p, heap, *dependence_relations, ddr); + res = false; + } else + compute_all_dependences (*datarefs, dependence_relations, vloops, + compute_self_and_read_read_dependences); + + if (dump_file && (dump_flags & TDF_STATS)) + { + fprintf (dump_file, "Dependence tester statistics:\n"); + + fprintf (dump_file, "Number of dependence tests: %d\n", + dependence_stats.num_dependence_tests); + fprintf (dump_file, "Number of dependence tests classified dependent: %d\n", + dependence_stats.num_dependence_dependent); + fprintf (dump_file, "Number of dependence tests classified independent: %d\n", + dependence_stats.num_dependence_independent); + fprintf (dump_file, "Number of undetermined dependence tests: %d\n", + dependence_stats.num_dependence_undetermined); + + fprintf (dump_file, "Number of subscript tests: %d\n", + dependence_stats.num_subscript_tests); + fprintf (dump_file, "Number of undetermined subscript tests: %d\n", + dependence_stats.num_subscript_undetermined); + fprintf (dump_file, "Number of same subscript function: %d\n", + dependence_stats.num_same_subscript_function); + + fprintf (dump_file, "Number of ziv tests: %d\n", + dependence_stats.num_ziv); + fprintf (dump_file, "Number of ziv tests returning dependent: %d\n", + dependence_stats.num_ziv_dependent); + fprintf (dump_file, "Number of ziv tests returning independent: %d\n", + dependence_stats.num_ziv_independent); + fprintf (dump_file, "Number of ziv tests unimplemented: %d\n", + dependence_stats.num_ziv_unimplemented); + + fprintf (dump_file, "Number of siv tests: %d\n", + dependence_stats.num_siv); + fprintf (dump_file, "Number of siv tests returning dependent: %d\n", + dependence_stats.num_siv_dependent); + fprintf (dump_file, "Number of siv tests returning independent: %d\n", + dependence_stats.num_siv_independent); + fprintf (dump_file, "Number of siv tests unimplemented: %d\n", + dependence_stats.num_siv_unimplemented); + + fprintf (dump_file, "Number of miv tests: %d\n", + dependence_stats.num_miv); + fprintf (dump_file, "Number of miv tests returning dependent: %d\n", + dependence_stats.num_miv_dependent); + fprintf (dump_file, "Number of miv tests returning independent: %d\n", + dependence_stats.num_miv_independent); + fprintf (dump_file, "Number of miv tests unimplemented: %d\n", + dependence_stats.num_miv_unimplemented); + } + + return res; +} + +/* Entry point (for testing only). Analyze all the data references + and the dependence relations in LOOP. + + The data references are computed first. + + A relation on these nodes is represented by a complete graph. Some + of the relations could be of no interest, thus the relations can be + computed on demand. + + In the following function we compute all the relations. This is + just a first implementation that is here for: + - for showing how to ask for the dependence relations, + - for the debugging the whole dependence graph, + - for the dejagnu testcases and maintenance. + + It is possible to ask only for a part of the graph, avoiding to + compute the whole dependence graph. The computed dependences are + stored in a knowledge base (KB) such that later queries don't + recompute the same information. The implementation of this KB is + transparent to the optimizer, and thus the KB can be changed with a + more efficient implementation, or the KB could be disabled. */ +static void +analyze_all_data_dependences (struct loop *loop) +{ + unsigned int i; + int nb_data_refs = 10; + VEC (data_reference_p, heap) *datarefs = + VEC_alloc (data_reference_p, heap, nb_data_refs); + VEC (ddr_p, heap) *dependence_relations = + VEC_alloc (ddr_p, heap, nb_data_refs * nb_data_refs); + + /* Compute DDs on the whole function. */ + compute_data_dependences_for_loop (loop, false, &datarefs, + &dependence_relations); + + if (dump_file) + { + dump_data_dependence_relations (dump_file, dependence_relations); + fprintf (dump_file, "\n\n"); + + if (dump_flags & TDF_DETAILS) + dump_dist_dir_vectors (dump_file, dependence_relations); + + if (dump_flags & TDF_STATS) + { + unsigned nb_top_relations = 0; + unsigned nb_bot_relations = 0; + unsigned nb_basename_differ = 0; + unsigned nb_chrec_relations = 0; + struct data_dependence_relation *ddr; + + for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++) + { + if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr))) + nb_top_relations++; + + else if (DDR_ARE_DEPENDENT (ddr) == chrec_known) + { + struct data_reference *a = DDR_A (ddr); + struct data_reference *b = DDR_B (ddr); + + if (!bitmap_intersect_p (DR_VOPS (a), DR_VOPS (b))) + nb_basename_differ++; + else + nb_bot_relations++; + } + + else + nb_chrec_relations++; + } + + gather_stats_on_scev_database (); + } + } + + free_dependence_relations (dependence_relations); + free_data_refs (datarefs); +} + +/* Computes all the data dependences and check that the results of + several analyzers are the same. */ + +void +tree_check_data_deps (void) +{ + loop_iterator li; + struct loop *loop_nest; + + FOR_EACH_LOOP (li, loop_nest, 0) + analyze_all_data_dependences (loop_nest); +} + +/* Free the memory used by a data dependence relation DDR. */ + +void +free_dependence_relation (struct data_dependence_relation *ddr) +{ + if (ddr == NULL) + return; + + if (DDR_SUBSCRIPTS (ddr)) + free_subscripts (DDR_SUBSCRIPTS (ddr)); + if (DDR_DIST_VECTS (ddr)) + VEC_free (lambda_vector, heap, DDR_DIST_VECTS (ddr)); + if (DDR_DIR_VECTS (ddr)) + VEC_free (lambda_vector, heap, DDR_DIR_VECTS (ddr)); + + free (ddr); +} + +/* Free the memory used by the data dependence relations from + DEPENDENCE_RELATIONS. */ + +void +free_dependence_relations (VEC (ddr_p, heap) *dependence_relations) +{ + unsigned int i; + struct data_dependence_relation *ddr; + VEC (loop_p, heap) *loop_nest = NULL; + + for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++) { - /* When the analysis is too difficult, answer "don't know". */ - *overlaps_a = chrec_dont_know; - *overlaps_b = chrec_dont_know; - *last_conflicts = chrec_dont_know; + if (ddr == NULL) + continue; + if (loop_nest == NULL) + loop_nest = DDR_LOOP_NEST (ddr); + else + gcc_assert (DDR_LOOP_NEST (ddr) == NULL + || DDR_LOOP_NEST (ddr) == loop_nest); + free_dependence_relation (ddr); } - - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, ")\n"); + + if (loop_nest) + VEC_free (loop_p, heap, loop_nest); + VEC_free (ddr_p, heap, dependence_relations); } -/* Determines the iterations for which CHREC_A is equal to CHREC_B. - OVERLAP_ITERATIONS_A and OVERLAP_ITERATIONS_B are initialized with - two functions that describe the iterations that contain conflicting - elements. - - Remark: For an integer k >= 0, the following equality is true: - - CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)). -*/ +/* Free the memory used by the data references from DATAREFS. */ -static void -analyze_overlapping_iterations (tree chrec_a, - tree chrec_b, - tree *overlap_iterations_a, - tree *overlap_iterations_b, - tree *last_conflicts) +void +free_data_refs (VEC (data_reference_p, heap) *datarefs) { - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "(analyze_overlapping_iterations \n"); - fprintf (dump_file, " (chrec_a = "); - print_generic_expr (dump_file, chrec_a, 0); - fprintf (dump_file, ")\n chrec_b = "); - print_generic_expr (dump_file, chrec_b, 0); - fprintf (dump_file, ")\n"); - } - - if (chrec_a == NULL_TREE - || chrec_b == NULL_TREE - || chrec_contains_undetermined (chrec_a) - || chrec_contains_undetermined (chrec_b) - || chrec_contains_symbols (chrec_a) - || chrec_contains_symbols (chrec_b)) - { - *overlap_iterations_a = chrec_dont_know; - *overlap_iterations_b = chrec_dont_know; - } - - else if (ziv_subscript_p (chrec_a, chrec_b)) - analyze_ziv_subscript (chrec_a, chrec_b, - overlap_iterations_a, overlap_iterations_b, - last_conflicts); - - else if (siv_subscript_p (chrec_a, chrec_b)) - analyze_siv_subscript (chrec_a, chrec_b, - overlap_iterations_a, overlap_iterations_b, - last_conflicts); - - else - analyze_miv_subscript (chrec_a, chrec_b, - overlap_iterations_a, overlap_iterations_b, - last_conflicts); - - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, " (overlap_iterations_a = "); - print_generic_expr (dump_file, *overlap_iterations_a, 0); - fprintf (dump_file, ")\n (overlap_iterations_b = "); - print_generic_expr (dump_file, *overlap_iterations_b, 0); - fprintf (dump_file, ")\n"); - } + unsigned int i; + struct data_reference *dr; + + for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++) + free_data_ref (dr); + VEC_free (data_reference_p, heap, datarefs); } -/* This section contains the affine functions dependences detector. */ +/* Dump vertex I in RDG to FILE. */ + +void +dump_rdg_vertex (FILE *file, struct graph *rdg, int i) +{ + struct vertex *v = &(rdg->vertices[i]); + struct graph_edge *e; + + fprintf (file, "(vertex %d: (%s%s) (in:", i, + RDG_MEM_WRITE_STMT (rdg, i) ? "w" : "", + RDG_MEM_READS_STMT (rdg, i) ? "r" : ""); + + if (v->pred) + for (e = v->pred; e; e = e->pred_next) + fprintf (file, " %d", e->src); + + fprintf (file, ") (out:"); + + if (v->succ) + for (e = v->succ; e; e = e->succ_next) + fprintf (file, " %d", e->dest); -/* Computes the conflicting iterations, and initialize DDR. */ + fprintf (file, ") \n"); + print_gimple_stmt (file, RDGV_STMT (v), 0, TDF_VOPS|TDF_MEMSYMS); + fprintf (file, ")\n"); +} + +/* Call dump_rdg_vertex on stderr. */ + +void +debug_rdg_vertex (struct graph *rdg, int i) +{ + dump_rdg_vertex (stderr, rdg, i); +} + +/* Dump component C of RDG to FILE. If DUMPED is non-null, set the + dumped vertices to that bitmap. */ + +void dump_rdg_component (FILE *file, struct graph *rdg, int c, bitmap dumped) +{ + int i; + + fprintf (file, "(%d\n", c); + + for (i = 0; i < rdg->n_vertices; i++) + if (rdg->vertices[i].component == c) + { + if (dumped) + bitmap_set_bit (dumped, i); + + dump_rdg_vertex (file, rdg, i); + } + + fprintf (file, ")\n"); +} + +/* Call dump_rdg_vertex on stderr. */ + +void +debug_rdg_component (struct graph *rdg, int c) +{ + dump_rdg_component (stderr, rdg, c, NULL); +} + +/* Dump the reduced dependence graph RDG to FILE. */ + +void +dump_rdg (FILE *file, struct graph *rdg) +{ + int i; + bitmap dumped = BITMAP_ALLOC (NULL); + + fprintf (file, "(rdg\n"); + + for (i = 0; i < rdg->n_vertices; i++) + if (!bitmap_bit_p (dumped, i)) + dump_rdg_component (file, rdg, rdg->vertices[i].component, dumped); + + fprintf (file, ")\n"); + BITMAP_FREE (dumped); +} + +/* Call dump_rdg on stderr. */ + +void +debug_rdg (struct graph *rdg) +{ + dump_rdg (stderr, rdg); +} static void -subscript_dependence_tester (struct data_dependence_relation *ddr) +dot_rdg_1 (FILE *file, struct graph *rdg) { - unsigned int i; - struct data_reference *dra = DDR_A (ddr); - struct data_reference *drb = DDR_B (ddr); - tree last_conflicts; - - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "(subscript_dependence_tester \n"); - - for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) + int i; + + fprintf (file, "digraph RDG {\n"); + + for (i = 0; i < rdg->n_vertices; i++) { - tree overlaps_a, overlaps_b; - struct subscript *subscript = DDR_SUBSCRIPT (ddr, i); - - 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)) - { - finalize_ddr_dependent (ddr, chrec_dont_know); - break; - } - - else if (overlaps_a == chrec_known - || overlaps_b == chrec_known) - { - finalize_ddr_dependent (ddr, chrec_known); - break; - } - - else - { - SUB_CONFLICTS_IN_A (subscript) = overlaps_a; - SUB_CONFLICTS_IN_B (subscript) = overlaps_b; - SUB_LAST_CONFLICT (subscript) = last_conflicts; - } + struct vertex *v = &(rdg->vertices[i]); + struct graph_edge *e; + + /* Highlight reads from memory. */ + if (RDG_MEM_READS_STMT (rdg, i)) + fprintf (file, "%d [style=filled, fillcolor=green]\n", i); + + /* Highlight stores to memory. */ + if (RDG_MEM_WRITE_STMT (rdg, i)) + fprintf (file, "%d [style=filled, fillcolor=red]\n", i); + + if (v->succ) + for (e = v->succ; e; e = e->succ_next) + switch (RDGE_TYPE (e)) + { + case input_dd: + fprintf (file, "%d -> %d [label=input] \n", i, e->dest); + break; + + case output_dd: + fprintf (file, "%d -> %d [label=output] \n", i, e->dest); + break; + + case flow_dd: + /* These are the most common dependences: don't print these. */ + fprintf (file, "%d -> %d \n", i, e->dest); + break; + + case anti_dd: + fprintf (file, "%d -> %d [label=anti] \n", i, e->dest); + break; + + default: + gcc_unreachable (); + } } - - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, ")\n"); + + fprintf (file, "}\n\n"); } -/* Compute the classic per loop distance vector. +/* Display SCOP using dotty. */ - DDR is the data dependence relation to build a vector from. - NB_LOOPS is the total number of loops we are considering. - FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed - loop nest. - Return FALSE if the dependence relation is outside of the loop nest - starting at FIRST_LOOP_DEPTH. - Return TRUE otherwise. */ +void +dot_rdg (struct graph *rdg) +{ + FILE *file = fopen ("/tmp/rdg.dot", "w"); + gcc_assert (file != NULL); -bool -build_classic_dist_vector (struct data_dependence_relation *ddr, - int nb_loops, int first_loop_depth) + dot_rdg_1 (file, rdg); + fclose (file); + + system ("dotty /tmp/rdg.dot"); +} + + +/* This structure is used for recording the mapping statement index in + the RDG. */ + +struct rdg_vertex_info GTY(()) { - unsigned i; - lambda_vector dist_v, init_v; - - dist_v = lambda_vector_new (nb_loops); - init_v = lambda_vector_new (nb_loops); - lambda_vector_clear (dist_v, nb_loops); - lambda_vector_clear (init_v, nb_loops); - - if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE) - return true; - - for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) + gimple stmt; + int index; +}; + +/* Returns the index of STMT in RDG. */ + +int +rdg_vertex_for_stmt (struct graph *rdg, gimple stmt) +{ + struct rdg_vertex_info rvi, *slot; + + rvi.stmt = stmt; + slot = (struct rdg_vertex_info *) htab_find (rdg->indices, &rvi); + + if (!slot) + return -1; + + return slot->index; +} + +/* Creates an edge in RDG for each distance vector from DDR. The + order that we keep track of in the RDG is the order in which + statements have to be executed. */ + +static void +create_rdg_edge_for_ddr (struct graph *rdg, ddr_p ddr) +{ + struct graph_edge *e; + int va, vb; + data_reference_p dra = DDR_A (ddr); + data_reference_p drb = DDR_B (ddr); + unsigned level = ddr_dependence_level (ddr); + + /* For non scalar dependences, when the dependence is REVERSED, + statement B has to be executed before statement A. */ + if (level > 0 + && !DDR_REVERSED_P (ddr)) { - tree access_fn_a, access_fn_b; - struct subscript *subscript = DDR_SUBSCRIPT (ddr, i); + data_reference_p tmp = dra; + dra = drb; + drb = tmp; + } - if (chrec_contains_undetermined (SUB_DISTANCE (subscript))) - { - non_affine_dependence_relation (ddr); - return true; - } + va = rdg_vertex_for_stmt (rdg, DR_STMT (dra)); + vb = rdg_vertex_for_stmt (rdg, DR_STMT (drb)); - access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i); - access_fn_b = DR_ACCESS_FN (DDR_B (ddr), i); + if (va < 0 || vb < 0) + return; - if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC - && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC) - { - int dist, loop_nb, loop_depth; - int loop_nb_a = CHREC_VARIABLE (access_fn_a); - int loop_nb_b = CHREC_VARIABLE (access_fn_b); - struct loop *loop_a = current_loops->parray[loop_nb_a]; - struct loop *loop_b = current_loops->parray[loop_nb_b]; - - /* If the loop for either variable is at a lower depth than - the first_loop's depth, then we can't possibly have a - dependency at this level of the loop. */ - - if (loop_a->depth < first_loop_depth - || loop_b->depth < first_loop_depth) - return false; + e = add_edge (rdg, va, vb); + e->data = XNEW (struct rdg_edge); - if (loop_nb_a != loop_nb_b - && !flow_loop_nested_p (loop_a, loop_b) - && !flow_loop_nested_p (loop_b, loop_a)) - { - /* Example: when there are two consecutive loops, + RDGE_LEVEL (e) = level; - | loop_1 - | A[{0, +, 1}_1] - | endloop_1 - | loop_2 - | A[{0, +, 1}_2] - | endloop_2 + /* Determines the type of the data dependence. */ + if (DR_IS_READ (dra) && DR_IS_READ (drb)) + RDGE_TYPE (e) = input_dd; + else if (!DR_IS_READ (dra) && !DR_IS_READ (drb)) + RDGE_TYPE (e) = output_dd; + else if (!DR_IS_READ (dra) && DR_IS_READ (drb)) + RDGE_TYPE (e) = flow_dd; + else if (DR_IS_READ (dra) && !DR_IS_READ (drb)) + RDGE_TYPE (e) = anti_dd; +} - the dependence relation cannot be captured by the - distance abstraction. */ - non_affine_dependence_relation (ddr); - return true; - } +/* Creates dependence edges in RDG for all the uses of DEF. IDEF is + the index of DEF in RDG. */ - /* The dependence is carried by the outermost loop. Example: - | loop_1 - | A[{4, +, 1}_1] - | loop_2 - | A[{5, +, 1}_2] - | endloop_2 - | endloop_1 - In this case, the dependence is carried by loop_1. */ - loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b; - loop_depth = current_loops->parray[loop_nb]->depth - first_loop_depth; - - /* If the loop number is still greater than the number of - loops we've been asked to analyze, or negative, - something is borked. */ - gcc_assert (loop_depth >= 0); - gcc_assert (loop_depth < nb_loops); - if (chrec_contains_undetermined (SUB_DISTANCE (subscript))) - { - non_affine_dependence_relation (ddr); - return true; - } - - dist = int_cst_value (SUB_DISTANCE (subscript)); +static void +create_rdg_edges_for_scalar (struct graph *rdg, tree def, int idef) +{ + use_operand_p imm_use_p; + imm_use_iterator iterator; + + FOR_EACH_IMM_USE_FAST (imm_use_p, iterator, def) + { + struct graph_edge *e; + int use = rdg_vertex_for_stmt (rdg, USE_STMT (imm_use_p)); - /* This is the subscript coupling test. - | loop i = 0, N, 1 - | T[i+1][i] = ... - | ... = T[i][i] - | endloop - There is no dependence. */ - if (init_v[loop_depth] != 0 - && dist_v[loop_depth] != dist) - { - finalize_ddr_dependent (ddr, chrec_known); - return true; - } + if (use < 0) + continue; - dist_v[loop_depth] = dist; - init_v[loop_depth] = 1; - } + e = add_edge (rdg, idef, use); + e->data = XNEW (struct rdg_edge); + RDGE_TYPE (e) = flow_dd; } - - /* There is a distance of 1 on all the outer loops: - - Example: there is a dependence of distance 1 on loop_1 for the array A. - | loop_1 - | A[5] = ... - | endloop - */ - { - struct loop *lca, *loop_a, *loop_b; - struct data_reference *a = DDR_A (ddr); - struct data_reference *b = DDR_B (ddr); - int lca_depth; - loop_a = loop_containing_stmt (DR_STMT (a)); - loop_b = loop_containing_stmt (DR_STMT (b)); - - /* Get the common ancestor loop. */ - lca = find_common_loop (loop_a, loop_b); - - lca_depth = lca->depth; - lca_depth -= first_loop_depth; - gcc_assert (lca_depth >= 0); - gcc_assert (lca_depth < nb_loops); - - /* For each outer loop where init_v is not set, the accesses are - in dependence of distance 1 in the loop. */ - if (lca != loop_a - && lca != loop_b - && init_v[lca_depth] == 0) - dist_v[lca_depth] = 1; - - lca = lca->outer; - - if (lca) - { - lca_depth = lca->depth - first_loop_depth; - while (lca->depth != 0) - { - /* If we're considering just a sub-nest, then don't record - any information on the outer loops. */ - if (lca_depth < 0) - break; +} - gcc_assert (lca_depth < nb_loops); +/* Creates the edges of the reduced dependence graph RDG. */ - if (init_v[lca_depth] == 0) - dist_v[lca_depth] = 1; - lca = lca->outer; - lca_depth = lca->depth - first_loop_depth; - - } - } - } - - DDR_DIST_VECT (ddr) = dist_v; - DDR_SIZE_VECT (ddr) = nb_loops; - return true; +static void +create_rdg_edges (struct graph *rdg, VEC (ddr_p, heap) *ddrs) +{ + int i; + struct data_dependence_relation *ddr; + def_operand_p def_p; + ssa_op_iter iter; + + for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++) + if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE) + create_rdg_edge_for_ddr (rdg, ddr); + + for (i = 0; i < rdg->n_vertices; i++) + FOR_EACH_PHI_OR_STMT_DEF (def_p, RDG_STMT (rdg, i), + iter, SSA_OP_DEF) + create_rdg_edges_for_scalar (rdg, DEF_FROM_PTR (def_p), i); } -/* Compute the classic per loop direction vector. +/* Build the vertices of the reduced dependence graph RDG. */ - DDR is the data dependence relation to build a vector from. - NB_LOOPS is the total number of loops we are considering. - FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed - loop nest. - Return FALSE if the dependence relation is outside of the loop nest - at FIRST_LOOP_DEPTH. - Return TRUE otherwise. */ - -static bool -build_classic_dir_vector (struct data_dependence_relation *ddr, - int nb_loops, int first_loop_depth) +static void +create_rdg_vertices (struct graph *rdg, VEC (gimple, heap) *stmts) { - unsigned i; - lambda_vector dir_v, init_v; - - dir_v = lambda_vector_new (nb_loops); - init_v = lambda_vector_new (nb_loops); - lambda_vector_clear (dir_v, nb_loops); - lambda_vector_clear (init_v, nb_loops); - - if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE) - return true; - - for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) - { - tree access_fn_a, access_fn_b; - struct subscript *subscript = DDR_SUBSCRIPT (ddr, i); + int i, j; + gimple stmt; - if (chrec_contains_undetermined (SUB_DISTANCE (subscript))) - { - non_affine_dependence_relation (ddr); - return true; - } + for (i = 0; VEC_iterate (gimple, stmts, i, stmt); i++) + { + VEC (data_ref_loc, heap) *references; + data_ref_loc *ref; + struct vertex *v = &(rdg->vertices[i]); + struct rdg_vertex_info *rvi = XNEW (struct rdg_vertex_info); + struct rdg_vertex_info **slot; + + rvi->stmt = stmt; + rvi->index = i; + slot = (struct rdg_vertex_info **) htab_find_slot (rdg->indices, rvi, INSERT); + + if (!*slot) + *slot = rvi; + else + free (rvi); - access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i); - access_fn_b = DR_ACCESS_FN (DDR_B (ddr), i); - if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC - && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC) - { - int dist, loop_nb, loop_depth; - enum data_dependence_direction dir = dir_star; - int loop_nb_a = CHREC_VARIABLE (access_fn_a); - int loop_nb_b = CHREC_VARIABLE (access_fn_b); - struct loop *loop_a = current_loops->parray[loop_nb_a]; - struct loop *loop_b = current_loops->parray[loop_nb_b]; - - /* If the loop for either variable is at a lower depth than - the first_loop's depth, then we can't possibly have a - dependency at this level of the loop. */ - - if (loop_a->depth < first_loop_depth - || loop_b->depth < first_loop_depth) - return false; + v->data = XNEW (struct rdg_vertex); + RDG_STMT (rdg, i) = stmt; - if (loop_nb_a != loop_nb_b - && !flow_loop_nested_p (loop_a, loop_b) - && !flow_loop_nested_p (loop_b, loop_a)) - { - /* Example: when there are two consecutive loops, + RDG_MEM_WRITE_STMT (rdg, i) = false; + RDG_MEM_READS_STMT (rdg, i) = false; + if (gimple_code (stmt) == GIMPLE_PHI) + continue; - | loop_1 - | A[{0, +, 1}_1] - | endloop_1 - | loop_2 - | A[{0, +, 1}_2] - | endloop_2 + get_references_in_stmt (stmt, &references); + for (j = 0; VEC_iterate (data_ref_loc, references, j, ref); j++) + if (!ref->is_read) + RDG_MEM_WRITE_STMT (rdg, i) = true; + else + RDG_MEM_READS_STMT (rdg, i) = true; - the dependence relation cannot be captured by the - distance abstraction. */ - non_affine_dependence_relation (ddr); - return true; - } + VEC_free (data_ref_loc, heap, references); + } +} - /* The dependence is carried by the outermost loop. Example: - | loop_1 - | A[{4, +, 1}_1] - | loop_2 - | A[{5, +, 1}_2] - | endloop_2 - | endloop_1 - In this case, the dependence is carried by loop_1. */ - loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b; - loop_depth = current_loops->parray[loop_nb]->depth - first_loop_depth; +/* Initialize STMTS with all the statements of LOOP. When + INCLUDE_PHIS is true, include also the PHI nodes. The order in + which we discover statements is important as + generate_loops_for_partition is using the same traversal for + identifying statements. */ - /* If the loop number is still greater than the number of - loops we've been asked to analyze, or negative, - something is borked. */ - gcc_assert (loop_depth >= 0); - gcc_assert (loop_depth < nb_loops); +static void +stmts_from_loop (struct loop *loop, VEC (gimple, heap) **stmts) +{ + unsigned int i; + basic_block *bbs = get_loop_body_in_dom_order (loop); - if (chrec_contains_undetermined (SUB_DISTANCE (subscript))) - { - non_affine_dependence_relation (ddr); - return true; - } + for (i = 0; i < loop->num_nodes; i++) + { + basic_block bb = bbs[i]; + gimple_stmt_iterator bsi; + gimple stmt; - dist = int_cst_value (SUB_DISTANCE (subscript)); + for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi)) + VEC_safe_push (gimple, heap, *stmts, gsi_stmt (bsi)); - if (dist == 0) - dir = dir_equal; - else if (dist > 0) - dir = dir_positive; - else if (dist < 0) - dir = dir_negative; - - /* This is the subscript coupling test. - | loop i = 0, N, 1 - | T[i+1][i] = ... - | ... = T[i][i] - | endloop - There is no dependence. */ - if (init_v[loop_depth] != 0 - && dir != dir_star - && (enum data_dependence_direction) dir_v[loop_depth] != dir - && (enum data_dependence_direction) dir_v[loop_depth] != dir_star) - { - finalize_ddr_dependent (ddr, chrec_known); - return true; - } - - dir_v[loop_depth] = dir; - init_v[loop_depth] = 1; + for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) + { + stmt = gsi_stmt (bsi); + if (gimple_code (stmt) != GIMPLE_LABEL) + VEC_safe_push (gimple, heap, *stmts, stmt); } } - - /* There is a distance of 1 on all the outer loops: - - Example: there is a dependence of distance 1 on loop_1 for the array A. - | loop_1 - | A[5] = ... - | endloop - */ - { - struct loop *lca, *loop_a, *loop_b; - struct data_reference *a = DDR_A (ddr); - struct data_reference *b = DDR_B (ddr); - int lca_depth; - loop_a = loop_containing_stmt (DR_STMT (a)); - loop_b = loop_containing_stmt (DR_STMT (b)); - - /* Get the common ancestor loop. */ - lca = find_common_loop (loop_a, loop_b); - lca_depth = lca->depth - first_loop_depth; - - gcc_assert (lca_depth >= 0); - gcc_assert (lca_depth < nb_loops); - - /* For each outer loop where init_v is not set, the accesses are - in dependence of distance 1 in the loop. */ - if (lca != loop_a - && lca != loop_b - && init_v[lca_depth] == 0) - dir_v[lca_depth] = dir_positive; - - lca = lca->outer; - if (lca) - { - lca_depth = lca->depth - first_loop_depth; - while (lca->depth != 0) - { - /* If we're considering just a sub-nest, then don't record - any information on the outer loops. */ - if (lca_depth < 0) - break; - - gcc_assert (lca_depth < nb_loops); - if (init_v[lca_depth] == 0) - dir_v[lca_depth] = dir_positive; - lca = lca->outer; - lca_depth = lca->depth - first_loop_depth; - - } - } - } - - DDR_DIR_VECT (ddr) = dir_v; - DDR_SIZE_VECT (ddr) = nb_loops; - return true; + free (bbs); } -/* Returns true when all the access functions of A are affine or - constant. */ +/* Returns true when all the dependences are computable. */ -static bool -access_functions_are_affine_or_constant_p (struct data_reference *a) +static bool +known_dependences_p (VEC (ddr_p, heap) *dependence_relations) { + ddr_p ddr; unsigned int i; - varray_type fns = DR_ACCESS_FNS (a); - - for (i = 0; i < VARRAY_ACTIVE_SIZE (fns); i++) - if (!evolution_function_is_constant_p (VARRAY_TREE (fns, i)) - && !evolution_function_is_affine_multivariate_p (VARRAY_TREE (fns, i))) + + for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++) + if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know) return false; - + return true; } -/* This computes the affine dependence relation between A and B. - CHREC_KNOWN is used for representing the independence between two - accesses, while CHREC_DONT_KNOW is used for representing the unknown - relation. - - Note that it is possible to stop the computation of the dependence - relation the first time we detect a CHREC_KNOWN element for a given - subscript. */ +/* Computes a hash function for element ELT. */ -void -compute_affine_dependence (struct data_dependence_relation *ddr) +static hashval_t +hash_stmt_vertex_info (const void *elt) { - struct data_reference *dra = DDR_A (ddr); - struct data_reference *drb = DDR_B (ddr); - - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "(compute_affine_dependence\n"); - fprintf (dump_file, " (stmt_a = \n"); - print_generic_expr (dump_file, DR_STMT (dra), 0); - fprintf (dump_file, ")\n (stmt_b = \n"); - print_generic_expr (dump_file, DR_STMT (drb), 0); - fprintf (dump_file, ")\n"); - } - - /* Analyze only when the dependence relation is not yet known. */ - if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE) - { - if (access_functions_are_affine_or_constant_p (dra) - && access_functions_are_affine_or_constant_p (drb)) - subscript_dependence_tester (ddr); - - /* As a last case, if the dependence cannot be determined, or if - the dependence is considered too difficult to determine, answer - "don't know". */ - else - finalize_ddr_dependent (ddr, chrec_dont_know); - } - - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, ")\n"); + const struct rdg_vertex_info *const rvi = + (const struct rdg_vertex_info *) elt; + gimple stmt = rvi->stmt; + + return htab_hash_pointer (stmt); } -/* Compute a subset of the data dependence relation graph. Don't - compute read-read relations, and avoid the computation of the - opposite relation, i.e. when AB has been computed, don't compute BA. - DATAREFS contains a list of data references, and the result is set - in DEPENDENCE_RELATIONS. */ +/* Compares database elements E1 and E2. */ -static void -compute_all_dependences (varray_type datarefs, - varray_type *dependence_relations) +static int +eq_stmt_vertex_info (const void *e1, const void *e2) { - unsigned int i, j, N; + const struct rdg_vertex_info *elt1 = (const struct rdg_vertex_info *) e1; + const struct rdg_vertex_info *elt2 = (const struct rdg_vertex_info *) e2; - N = VARRAY_ACTIVE_SIZE (datarefs); - - for (i = 0; i < N; i++) - for (j = i; j < N; j++) - { - struct data_reference *a, *b; - struct data_dependence_relation *ddr; + return elt1->stmt == elt2->stmt; +} - a = VARRAY_GENERIC_PTR (datarefs, i); - b = VARRAY_GENERIC_PTR (datarefs, j); - ddr = initialize_data_dependence_relation (a, b); +/* Free the element E. */ - VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr); - compute_affine_dependence (ddr); - compute_subscript_distance (ddr); - } +static void +hash_stmt_vertex_del (void *e) +{ + free (e); } -/* Search the data references in LOOP, and record the information into - DATAREFS. Returns chrec_dont_know when failing to analyze a - difficult case, returns NULL_TREE otherwise. - - TODO: This function should be made smarter so that it can handle address - arithmetic as if they were array accesses, etc. */ +/* Build the Reduced Dependence Graph (RDG) with one vertex per + statement of the loop nest, and one edge per data dependence or + scalar dependence. */ -tree -find_data_references_in_loop (struct loop *loop, varray_type *datarefs) +struct graph * +build_rdg (struct loop *loop) { - bool dont_know_node_not_inserted = true; - basic_block bb, *bbs; - unsigned int i; - block_stmt_iterator bsi; + int nb_data_refs = 10; + struct graph *rdg = NULL; + VEC (ddr_p, heap) *dependence_relations; + VEC (data_reference_p, heap) *datarefs; + VEC (gimple, heap) *stmts = VEC_alloc (gimple, heap, nb_data_refs); + + dependence_relations = VEC_alloc (ddr_p, heap, nb_data_refs * nb_data_refs) ; + datarefs = VEC_alloc (data_reference_p, heap, nb_data_refs); + compute_data_dependences_for_loop (loop, + false, + &datarefs, + &dependence_relations); - bbs = get_loop_body (loop); + if (!known_dependences_p (dependence_relations)) + goto end_rdg; - for (i = 0; i < loop->num_nodes; i++) - { - bb = bbs[i]; + stmts_from_loop (loop, &stmts); + rdg = new_graph (VEC_length (gimple, stmts)); - for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) - { - tree stmt = bsi_stmt (bsi); + rdg->indices = htab_create (nb_data_refs, hash_stmt_vertex_info, + eq_stmt_vertex_info, hash_stmt_vertex_del); + create_rdg_vertices (rdg, stmts); + create_rdg_edges (rdg, dependence_relations); - if (TREE_CODE (stmt) != MODIFY_EXPR) - continue; + end_rdg: + free_dependence_relations (dependence_relations); + free_data_refs (datarefs); + VEC_free (gimple, heap, stmts); - if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)) - continue; - - /* In the GIMPLE representation, a modify expression - contains a single load or store to memory. */ - if (TREE_CODE (TREE_OPERAND (stmt, 0)) == ARRAY_REF) - VARRAY_PUSH_GENERIC_PTR - (*datarefs, analyze_array (stmt, TREE_OPERAND (stmt, 0), - false)); - - else if (TREE_CODE (TREE_OPERAND (stmt, 1)) == ARRAY_REF) - VARRAY_PUSH_GENERIC_PTR - (*datarefs, analyze_array (stmt, TREE_OPERAND (stmt, 1), - true)); - else - { - if (dont_know_node_not_inserted) - { - struct data_reference *res; - res = xmalloc (sizeof (struct data_reference)); - DR_STMT (res) = NULL_TREE; - DR_REF (res) = NULL_TREE; - DR_ACCESS_FNS (res) = NULL; - DR_BASE_NAME (res) = NULL; - DR_IS_READ (res) = false; - VARRAY_PUSH_GENERIC_PTR (*datarefs, res); - dont_know_node_not_inserted = false; - } - } + return rdg; +} - /* When there are no defs in the loop, the loop is parallel. */ - if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS)) - bb->loop_father->parallel_p = false; - } +/* Free the reduced dependence graph RDG. */ - if (bb->loop_father->estimated_nb_iterations == NULL_TREE) - compute_estimated_nb_iterations (bb->loop_father); - } +void +free_rdg (struct graph *rdg) +{ + int i; - free (bbs); + for (i = 0; i < rdg->n_vertices; i++) + free (rdg->vertices[i].data); - return dont_know_node_not_inserted ? NULL_TREE : chrec_dont_know; + htab_delete (rdg->indices); + free_graph (rdg); } - - -/* This section contains all the entry points. */ - -/* Given a loop nest LOOP, the following vectors are returned: - *DATAREFS is initialized to all the array elements contained in this loop, - *DEPENDENCE_RELATIONS contains the relations between the data references. */ +/* Initialize STMTS with all the statements of LOOP that contain a + store to memory. */ void -compute_data_dependences_for_loop (unsigned nb_loops, - struct loop *loop, - varray_type *datarefs, - varray_type *dependence_relations) +stores_from_loop (struct loop *loop, VEC (gimple, heap) **stmts) { unsigned int i; - varray_type allrelations; + basic_block *bbs = get_loop_body_in_dom_order (loop); - /* If one of the data references is not computable, give up without - spending time to compute other dependences. */ - if (find_data_references_in_loop (loop, datarefs) == chrec_dont_know) + for (i = 0; i < loop->num_nodes; i++) { - struct data_dependence_relation *ddr; + basic_block bb = bbs[i]; + gimple_stmt_iterator bsi; - /* Insert a single relation into dependence_relations: - chrec_dont_know. */ - ddr = initialize_data_dependence_relation (NULL, NULL); - VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr); - build_classic_dist_vector (ddr, nb_loops, loop->depth); - build_classic_dir_vector (ddr, nb_loops, loop->depth); - return; + for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) + if (!ZERO_SSA_OPERANDS (gsi_stmt (bsi), SSA_OP_VDEF)) + VEC_safe_push (gimple, heap, *stmts, gsi_stmt (bsi)); } - VARRAY_GENERIC_PTR_INIT (allrelations, 1, "Data dependence relations"); - compute_all_dependences (*datarefs, &allrelations); + free (bbs); +} + +/* For a data reference REF, return the declaration of its base + address or NULL_TREE if the base is not determined. */ + +static inline tree +ref_base_address (gimple stmt, data_ref_loc *ref) +{ + tree base = NULL_TREE; + tree base_address; + struct data_reference *dr = XCNEW (struct data_reference); + + DR_STMT (dr) = stmt; + DR_REF (dr) = *ref->pos; + dr_analyze_innermost (dr); + base_address = DR_BASE_ADDRESS (dr); - for (i = 0; i < VARRAY_ACTIVE_SIZE (allrelations); i++) + if (!base_address) + goto end; + + switch (TREE_CODE (base_address)) { - struct data_dependence_relation *ddr; - ddr = VARRAY_GENERIC_PTR (allrelations, i); - if (build_classic_dist_vector (ddr, nb_loops, loop->depth)) - { - VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr); - build_classic_dir_vector (ddr, nb_loops, loop->depth); - } + case ADDR_EXPR: + base = TREE_OPERAND (base_address, 0); + break; + + default: + base = base_address; + break; } -} -/* Entry point (for testing only). Analyze all the data references - and the dependence relations. + end: + free_data_ref (dr); + return base; +} - The data references are computed first. - - A relation on these nodes is represented by a complete graph. Some - of the relations could be of no interest, thus the relations can be - computed on demand. - - In the following function we compute all the relations. This is - just a first implementation that is here for: - - for showing how to ask for the dependence relations, - - for the debugging the whole dependence graph, - - for the dejagnu testcases and maintenance. - - It is possible to ask only for a part of the graph, avoiding to - compute the whole dependence graph. The computed dependences are - stored in a knowledge base (KB) such that later queries don't - recompute the same information. The implementation of this KB is - transparent to the optimizer, and thus the KB can be changed with a - more efficient implementation, or the KB could be disabled. */ +/* Determines whether the statement from vertex V of the RDG has a + definition used outside the loop that contains this statement. */ -void -analyze_all_data_dependences (struct loops *loops) +bool +rdg_defs_used_in_other_loops_p (struct graph *rdg, int v) { - unsigned int i; - varray_type datarefs; - varray_type dependence_relations; - int nb_data_refs = 10; + gimple stmt = RDG_STMT (rdg, v); + struct loop *loop = loop_containing_stmt (stmt); + use_operand_p imm_use_p; + imm_use_iterator iterator; + ssa_op_iter it; + def_operand_p def_p; + + if (!loop) + return true; - VARRAY_GENERIC_PTR_INIT (datarefs, nb_data_refs, "datarefs"); - VARRAY_GENERIC_PTR_INIT (dependence_relations, - nb_data_refs * nb_data_refs, - "dependence_relations"); + FOR_EACH_PHI_OR_STMT_DEF (def_p, stmt, it, SSA_OP_DEF) + { + FOR_EACH_IMM_USE_FAST (imm_use_p, iterator, DEF_FROM_PTR (def_p)) + { + if (loop_containing_stmt (USE_STMT (imm_use_p)) != loop) + return true; + } + } - /* Compute DDs on the whole function. */ - compute_data_dependences_for_loop (loops->num, loops->parray[0], - &datarefs, &dependence_relations); + return false; +} - if (dump_file) - { - dump_data_dependence_relations (dump_file, dependence_relations); - fprintf (dump_file, "\n\n"); +/* Determines whether statements S1 and S2 access to similar memory + locations. Two memory accesses are considered similar when they + have the same base address declaration, i.e. when their + ref_base_address is the same. */ - if (dump_flags & TDF_DETAILS) - dump_dist_dir_vectors (dump_file, dependence_relations); +bool +have_similar_memory_accesses (gimple s1, gimple s2) +{ + bool res = false; + unsigned i, j; + VEC (data_ref_loc, heap) *refs1, *refs2; + data_ref_loc *ref1, *ref2; - if (dump_flags & TDF_STATS) - { - unsigned nb_top_relations = 0; - unsigned nb_bot_relations = 0; - unsigned nb_basename_differ = 0; - unsigned nb_chrec_relations = 0; + get_references_in_stmt (s1, &refs1); + get_references_in_stmt (s2, &refs2); + + for (i = 0; VEC_iterate (data_ref_loc, refs1, i, ref1); i++) + { + tree base1 = ref_base_address (s1, ref1); - for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++) + if (base1) + for (j = 0; VEC_iterate (data_ref_loc, refs2, j, ref2); j++) + if (base1 == ref_base_address (s2, ref2)) { - struct data_dependence_relation *ddr; - ddr = VARRAY_GENERIC_PTR (dependence_relations, i); - - if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr))) - nb_top_relations++; - - else if (DDR_ARE_DEPENDENT (ddr) == chrec_known) - { - struct data_reference *a = DDR_A (ddr); - struct data_reference *b = DDR_B (ddr); - bool differ_p; - - if (DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b) - || (array_base_name_differ_p (a, b, &differ_p) && differ_p)) - nb_basename_differ++; - else - nb_bot_relations++; - } - - else - nb_chrec_relations++; + res = true; + goto end; } - - gather_stats_on_scev_database (); - } } - free_dependence_relations (dependence_relations); - free_data_refs (datarefs); + end: + VEC_free (data_ref_loc, heap, refs1); + VEC_free (data_ref_loc, heap, refs2); + return res; } -/* Free the memory used by a data dependence relation DDR. */ +/* Helper function for the hashtab. */ -void -free_dependence_relation (struct data_dependence_relation *ddr) +static int +have_similar_memory_accesses_1 (const void *s1, const void *s2) { - if (ddr == NULL) - return; - - if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_SUBSCRIPTS (ddr)) - varray_clear (DDR_SUBSCRIPTS (ddr)); - free (ddr); + return have_similar_memory_accesses (CONST_CAST_GIMPLE ((const_gimple) s1), + CONST_CAST_GIMPLE ((const_gimple) s2)); } -/* Free the memory used by the data dependence relations from - DEPENDENCE_RELATIONS. */ +/* Helper function for the hashtab. */ -void -free_dependence_relations (varray_type dependence_relations) +static hashval_t +ref_base_address_1 (const void *s) { - unsigned int i; - if (dependence_relations == NULL) - return; + gimple stmt = CONST_CAST_GIMPLE ((const_gimple) s); + unsigned i; + VEC (data_ref_loc, heap) *refs; + data_ref_loc *ref; + hashval_t res = 0; + + get_references_in_stmt (stmt, &refs); + + for (i = 0; VEC_iterate (data_ref_loc, refs, i, ref); i++) + if (!ref->is_read) + { + res = htab_hash_pointer (ref_base_address (stmt, ref)); + break; + } - for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++) - free_dependence_relation (VARRAY_GENERIC_PTR (dependence_relations, i)); - varray_clear (dependence_relations); + VEC_free (data_ref_loc, heap, refs); + return res; } -/* Free the memory used by the data references from DATAREFS. */ +/* Try to remove duplicated write data references from STMTS. */ void -free_data_refs (varray_type datarefs) +remove_similar_memory_refs (VEC (gimple, heap) **stmts) { - unsigned int i; - - if (datarefs == NULL) - return; + unsigned i; + gimple stmt; + htab_t seen = htab_create (VEC_length (gimple, *stmts), ref_base_address_1, + have_similar_memory_accesses_1, NULL); - for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++) + for (i = 0; VEC_iterate (gimple, *stmts, i, stmt); ) { - struct data_reference *dr = (struct data_reference *) - VARRAY_GENERIC_PTR (datarefs, i); - if (dr) + void **slot; + + slot = htab_find_slot (seen, stmt, INSERT); + + if (*slot) + VEC_ordered_remove (gimple, *stmts, i); + else { - if (DR_ACCESS_FNS (dr)) - varray_clear (DR_ACCESS_FNS (dr)); - free (dr); + *slot = (void *) stmt; + i++; } } - varray_clear (datarefs); + + htab_delete (seen); } +/* Returns the index of PARAMETER in the parameters vector of the + ACCESS_MATRIX. If PARAMETER does not exist return -1. */ + +int +access_matrix_get_index_for_parameter (tree parameter, + struct access_matrix *access_matrix) +{ + int i; + VEC (tree,heap) *lambda_parameters = AM_PARAMETERS (access_matrix); + tree lambda_parameter; + + for (i = 0; VEC_iterate (tree, lambda_parameters, i, lambda_parameter); i++) + if (lambda_parameter == parameter) + return i + AM_NB_INDUCTION_VARS (access_matrix); + + return -1; +}