X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Ftree-data-ref.c;h=4f1a9fddb43c5e663dd9484c86a730ef9e969bbf;hb=f2b9a606fa39bd21567289e3ad29e7f1744e1e87;hp=e0223c326f7805634183ae3a3af4c34683415452;hpb=5b5037b32317ffd475a733d701c4ad7f90592d7b;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c index e0223c326f7..4f1a9fddb43 100644 --- a/gcc/tree-data-ref.c +++ b/gcc/tree-data-ref.c @@ -6,7 +6,7 @@ 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, 51 Franklin Street, Fifth Floor, Boston, MA -02110-1301, 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 @@ -89,7 +88,6 @@ Software Foundation, 51 Franklin Street, Fifth Floor, 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" @@ -124,11 +122,12 @@ static struct datadep_stats static bool subscript_dependence_tester_1 (struct data_dependence_relation *, struct data_reference *, - struct data_reference *); + struct data_reference *, + struct loop *); /* Returns true iff A divides B. */ static inline bool -tree_fold_divides_p (tree a, tree b) +tree_fold_divides_p (const_tree a, const_tree b) { gcc_assert (TREE_CODE (a) == INTEGER_CST); gcc_assert (TREE_CODE (b) == INTEGER_CST); @@ -157,6 +156,14 @@ dump_data_references (FILE *file, VEC (data_reference_p, heap) *datarefs) 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 DDRS. */ void @@ -179,7 +186,7 @@ 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_object: "); @@ -351,13 +358,20 @@ 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) @@ -486,63 +500,66 @@ dump_ddrs (FILE *file, VEC (ddr_p, heap) *ddrs) fprintf (file, "\n\n"); } -/* Expresses EXP as VAR + OFF, where off is a constant. The type of OFF - will be ssizetype. */ +/* 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 -split_constant_offset (tree exp, tree *var, tree *off) +static bool +split_constant_offset_1 (tree type, tree op0, enum tree_code code, tree op1, + tree *var, tree *off) { - tree type = TREE_TYPE (exp), otype; tree var0, var1; tree off0, off1; + enum tree_code ocode = code; - *var = exp; - STRIP_NOPS (exp); - otype = TREE_TYPE (exp); + *var = NULL_TREE; + *off = NULL_TREE; - switch (TREE_CODE (exp)) + switch (code) { case INTEGER_CST: *var = build_int_cst (type, 0); - *off = fold_convert (ssizetype, exp); - return; + *off = fold_convert (ssizetype, op0); + return true; + case POINTER_PLUS_EXPR: + ocode = PLUS_EXPR; + /* FALLTHROUGH */ case PLUS_EXPR: case MINUS_EXPR: - split_constant_offset (TREE_OPERAND (exp, 0), &var0, &off0); - split_constant_offset (TREE_OPERAND (exp, 1), &var1, &off1); - *var = fold_convert (type, fold_build2 (TREE_CODE (exp), otype, - var0, var1)); - *off = size_binop (TREE_CODE (exp), off0, off1); - return; + 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; case MULT_EXPR: - off1 = TREE_OPERAND (exp, 1); - if (TREE_CODE (off1) != INTEGER_CST) - break; + if (TREE_CODE (op1) != INTEGER_CST) + return false; - split_constant_offset (TREE_OPERAND (exp, 0), &var0, &off0); - *var = fold_convert (type, fold_build2 (MULT_EXPR, otype, - var0, off1)); - *off = size_binop (MULT_EXPR, off0, fold_convert (ssizetype, off1)); - return; + 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 op, base, poffset; + tree base, poffset; HOST_WIDE_INT pbitsize, pbitpos; enum machine_mode pmode; int punsignedp, pvolatilep; - op = TREE_OPERAND (exp, 0); - if (!handled_component_p (op)) - break; + op0 = TREE_OPERAND (op0, 0); + if (!handled_component_p (op0)) + return false; - base = get_inner_reference (op, &pbitsize, &pbitpos, &poffset, + base = get_inner_reference (op0, &pbitsize, &pbitpos, &poffset, &pmode, &punsignedp, &pvolatilep, false); if (pbitpos % BITS_PER_UNIT != 0) - break; + return false; base = build_fold_addr_expr (base); off0 = ssize_int (pbitpos / BITS_PER_UNIT); @@ -550,21 +567,82 @@ split_constant_offset (tree exp, tree *var, tree *off) { split_constant_offset (poffset, &poffset, &off1); off0 = size_binop (PLUS_EXPR, off0, off1); - base = fold_build2 (PLUS_EXPR, TREE_TYPE (base), - base, - fold_convert (TREE_TYPE (base), poffset)); + 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)); } - *var = fold_convert (type, base); + 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 (CONVERT_EXPR_P (var0)) + { + 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; + 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: - break; + return false; } +} +/* Expresses EXP as VAR + OFF, where off is a constant. The type of OFF + will be ssizetype. */ + +void +split_constant_offset (tree exp, tree *var, tree *off) +{ + tree type = TREE_TYPE (exp), otype, op0, op1, e, o; + enum tree_code code; + + *var = exp; *off = ssize_int (0); + STRIP_NOPS (exp); + + if (automatically_generated_chrec_p (exp)) + return; + + 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; + } } /* Returns the address ADDR of an object in a canonical shape (without nop @@ -594,7 +672,7 @@ canonicalize_base_object_address (tree addr) void dr_analyze_innermost (struct data_reference *dr) { - tree stmt = DR_STMT (dr); + gimple stmt = DR_STMT (dr); struct loop *loop = loop_containing_stmt (stmt); tree ref = DR_REF (dr); HOST_WIDE_INT pbitsize, pbitpos; @@ -665,11 +743,12 @@ dr_analyze_innermost (struct data_reference *dr) static void dr_analyze_indices (struct data_reference *dr, struct loop *nest) { - tree stmt = DR_STMT (dr); + 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; + basic_block before_loop = block_before_loop (nest); while (handled_component_p (aref)) { @@ -677,7 +756,7 @@ dr_analyze_indices (struct data_reference *dr, struct loop *nest) { op = TREE_OPERAND (aref, 1); access_fn = analyze_scalar_evolution (loop, op); - access_fn = resolve_mixers (nest, access_fn); + access_fn = instantiate_scev (before_loop, loop, access_fn); VEC_safe_push (tree, heap, access_fns, access_fn); TREE_OPERAND (aref, 1) = build_int_cst (TREE_TYPE (op), 0); @@ -690,7 +769,7 @@ dr_analyze_indices (struct data_reference *dr, struct loop *nest) { op = TREE_OPERAND (aref, 0); access_fn = analyze_scalar_evolution (loop, op); - access_fn = resolve_mixers (nest, access_fn); + access_fn = instantiate_scev (before_loop, loop, access_fn); base = initial_condition (access_fn); split_constant_offset (base, &base, &off); access_fn = chrec_replace_initial_condition (access_fn, @@ -709,7 +788,7 @@ dr_analyze_indices (struct data_reference *dr, struct loop *nest) static void dr_analyze_alias (struct data_reference *dr) { - tree stmt = DR_STMT (dr); + gimple stmt = DR_STMT (dr); tree ref = DR_REF (dr); tree base = get_base_address (ref), addr, smt = NULL_TREE; ssa_op_iter it; @@ -729,8 +808,6 @@ dr_analyze_alias (struct data_reference *dr) } DR_SYMBOL_TAG (dr) = smt; - if (smt && var_can_have_subvars (smt)) - DR_SUBVARS (dr) = get_subvars_for_var (smt); vops = BITMAP_ALLOC (NULL); FOR_EACH_SSA_TREE_OPERAND (op, stmt, it, SSA_OP_VIRTUAL_USES) @@ -758,7 +835,7 @@ dr_address_invariant_p (struct data_reference *dr) /* Frees data reference DR. */ -static void +void free_data_ref (data_reference_p dr) { BITMAP_FREE (DR_VOPS (dr)); @@ -769,10 +846,10 @@ free_data_ref (data_reference_p 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 analysed. */ + loop nest in that the reference should be analyzed. */ struct data_reference * -create_data_ref (struct loop *nest, tree memref, tree stmt, bool is_read) +create_data_ref (struct loop *nest, tree memref, gimple stmt, bool is_read) { struct data_reference *dr; @@ -885,6 +962,18 @@ affine_function_zero_p (affine_fn fn) && affine_function_constant_p (fn)); } +/* Returns a signed integer type with the largest precision from TA + and TB. */ + +static tree +signed_type_for_types (tree ta, tree tb) +{ + 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. */ @@ -908,18 +997,23 @@ affine_fn_op (enum tree_code op, affine_fn fna, affine_fn fnb) ret = VEC_alloc (tree, heap, m); for (i = 0; i < n; i++) - VEC_quick_push (tree, ret, - fold_build2 (op, integer_type_node, - VEC_index (tree, fna, i), - VEC_index (tree, fnb, i))); + { + 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, integer_type_node, + 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, integer_type_node, + fold_build2 (op, signed_type_for (TREE_TYPE (coef)), integer_zero_node, coef)); return ret; @@ -1014,7 +1108,7 @@ conflict_fn_no_dependence (void) /* Returns true if the address of OBJ is invariant in LOOP. */ static bool -object_address_invariant_in_loop_p (struct loop *loop, tree obj) +object_address_invariant_in_loop_p (const struct loop *loop, const_tree obj) { while (handled_component_p (obj)) { @@ -1132,13 +1226,13 @@ disjoint_objects_p (tree a, tree b) /* Returns false if we can prove that data references A and B do not alias, true otherwise. */ -static bool -dr_may_alias_p (struct data_reference *a, struct data_reference *b) +bool +dr_may_alias_p (const struct data_reference *a, const struct data_reference *b) { - tree addr_a = DR_BASE_ADDRESS (a); - tree addr_b = DR_BASE_ADDRESS (b); - tree type_a, type_b; - tree decl_a = NULL_TREE, decl_b = NULL_TREE; + 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. */ @@ -1186,6 +1280,8 @@ dr_may_alias_p (struct data_reference *a, struct data_reference *b) 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. */ @@ -1202,6 +1298,10 @@ initialize_data_dependence_relation (struct data_reference *a, 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; if (a == NULL || b == NULL) { @@ -1216,6 +1316,20 @@ initialize_data_dependence_relation (struct data_reference *a, return res; } + /* 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; + } + /* 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)) @@ -1225,7 +1339,7 @@ initialize_data_dependence_relation (struct data_reference *a, } /* If the base of the object is not invariant in the loop nest, we cannot - analyse it. TODO -- in fact, it would suffice to record that there may + 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))) @@ -1241,8 +1355,7 @@ initialize_data_dependence_relation (struct data_reference *a, DDR_SUBSCRIPTS (res) = VEC_alloc (subscript_p, heap, DR_NUM_DIMENSIONS (a)); DDR_LOOP_NEST (res) = loop_nest; DDR_INNER_LOOP (res) = 0; - DDR_DIR_VECTS (res) = NULL; - DDR_DIST_VECTS (res) = NULL; + DDR_SELF_REFERENCE (res) = false; for (i = 0; i < DR_NUM_DIMENSIONS (a); i++) { @@ -1286,6 +1399,7 @@ free_subscripts (VEC (subscript_p, heap) *subscripts) { free_conflict_function (s->conflicting_iterations_in_a); free_conflict_function (s->conflicting_iterations_in_b); + free (s); } VEC_free (subscript_p, heap, subscripts); } @@ -1306,6 +1420,7 @@ finalize_ddr_dependent (struct data_dependence_relation *ddr, DDR_ARE_DEPENDENT (ddr) = chrec; free_subscripts (DDR_SUBSCRIPTS (ddr)); + DDR_SUBSCRIPTS (ddr) = NULL; } /* The dependence relation DDR cannot be represented by a distance @@ -1328,8 +1443,7 @@ non_affine_dependence_relation (struct data_dependence_relation *ddr) variables, i.e., if the ZIV (Zero Index Variable) test is true. */ static inline bool -ziv_subscript_p (tree chrec_a, - tree chrec_b) +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)); @@ -1339,8 +1453,7 @@ ziv_subscript_p (tree chrec_a, variable, i.e., if the SIV (Single Index Variable) test is true. */ static bool -siv_subscript_p (tree chrec_a, - tree chrec_b) +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)) @@ -1433,15 +1546,16 @@ analyze_ziv_subscript (tree chrec_a, conflict_function **overlaps_b, tree *last_conflicts) { - tree difference; + tree type, difference; dependence_stats.num_ziv++; if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "(analyze_ziv_subscript \n"); - - chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE); - chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE); - difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b); + + 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); switch (TREE_CODE (difference)) { @@ -1567,12 +1681,12 @@ analyze_siv_subscript_cst_affine (tree chrec_a, tree *last_conflicts) { bool value0, value1, value2; - tree difference, tmp; + tree type, difference, tmp; - chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE); - chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE); - difference = chrec_fold_minus - (integer_type_node, initial_condition (chrec_b), chrec_a); + 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)) { @@ -1615,10 +1729,8 @@ analyze_siv_subscript_cst_affine (tree chrec_a, 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, integer_type_node, - fold_build1 (ABS_EXPR, - integer_type_node, - difference), + 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; @@ -1626,7 +1738,7 @@ analyze_siv_subscript_cst_affine (tree chrec_a, /* Perform weak-zero siv test to see if overlap is outside the loop bounds. */ - numiter = estimated_loop_iterations_int (loop, true); + numiter = estimated_loop_iterations_int (loop, false); if (numiter >= 0 && compare_tree_int (tmp, numiter) > 0) @@ -1697,15 +1809,14 @@ analyze_siv_subscript_cst_affine (tree chrec_a, 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, - integer_type_node, difference, + 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, true); + numiter = estimated_loop_iterations_int (loop, false); if (numiter >= 0 && compare_tree_int (tmp, numiter) > 0) @@ -1754,16 +1865,42 @@ analyze_siv_subscript_cst_affine (tree chrec_a, /* Helper recursive function for initializing the matrix A. Returns the initial value of CHREC. */ -static int +static tree initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult) { gcc_assert (chrec); - if (TREE_CODE (chrec) != POLYNOMIAL_CHREC) - return int_cst_value (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); - 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)) @@ -1791,9 +1928,15 @@ compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b, step_overlaps_a = step_b / gcd_steps_a_b; step_overlaps_b = step_a / gcd_steps_a_b; - tau2 = FLOOR_DIV (niter, step_overlaps_a); - tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b)); - last_conflict = tau2; + 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, @@ -1801,7 +1944,6 @@ compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b, *overlaps_b = affine_fn_univar (integer_zero_node, dim, build_int_cst (NULL_TREE, step_overlaps_b)); - *last_conflicts = build_int_cst (NULL_TREE, last_conflict); } else @@ -1846,10 +1988,11 @@ compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b, 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)), true); - niter_y = estimated_loop_iterations_int (get_chrec_loop (chrec_a), true); - niter_z = estimated_loop_iterations_int (get_chrec_loop (chrec_b), true); + 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) { @@ -1955,8 +2098,7 @@ analyze_subscript_affine_affine (tree chrec_a, tree *last_conflicts) { unsigned nb_vars_a, nb_vars_b, dim; - int init_a, init_b, gamma, gcd_alpha_beta; - int tau1, tau2; + HOST_WIDE_INT init_a, init_b, gamma, gcd_alpha_beta; lambda_matrix A, U, S; if (eq_evolutions_p (chrec_a, chrec_b)) @@ -1990,8 +2132,8 @@ analyze_subscript_affine_affine (tree chrec_a, A = lambda_matrix_new (dim, 1); S = lambda_matrix_new (dim, 1); - init_a = initialize_matrix_A (A, chrec_a, 0, 1); - init_b = initialize_matrix_A (A, chrec_b, nb_vars_a, -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 @@ -2006,26 +2148,15 @@ analyze_subscript_affine_affine (tree chrec_a, { if (nb_vars_a == 1 && nb_vars_b == 1) { - int step_a, step_b; + 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), true); - niter_b = estimated_loop_iterations_int - (get_chrec_loop (chrec_b), true); - if (niter_a < 0 || niter_b < 0) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n"); - *overlaps_a = conflict_fn_not_known (); - *overlaps_b = conflict_fn_not_known (); - *last_conflicts = chrec_dont_know; - goto end_analyze_subs_aa; - } - + 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)); @@ -2109,31 +2240,7 @@ analyze_subscript_affine_affine (tree chrec_a, | 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; - - niter_a = estimated_loop_iterations_int - (get_chrec_loop (chrec_a), true); - niter_b = estimated_loop_iterations_int - (get_chrec_loop (chrec_b), true); - - if (niter_a < 0 || niter_b < 0) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n"); - *overlaps_a = conflict_fn_not_known (); - *overlaps_b = conflict_fn_not_known (); - *last_conflicts = chrec_dont_know; - goto end_analyze_subs_aa; - } - - niter = MIN (niter_a, niter_b); + HOST_WIDE_INT i0, j0, i1, j1; i0 = U[0][0] * gamma / gcd_alpha_beta; j0 = U[0][1] * gamma / gcd_alpha_beta; @@ -2150,80 +2257,72 @@ analyze_subscript_affine_affine (tree chrec_a, *overlaps_a = conflict_fn_no_dependence (); *overlaps_b = conflict_fn_no_dependence (); *last_conflicts = integer_zero_node; + goto end_analyze_subs_aa; } - else + if (i1 > 0 && j1 > 0) { - if (i1 > 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) { - tau1 = CEIL (-i0, i1); - tau2 = FLOOR_DIV (niter - i0, i1); + 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 (j1 > 0) + /* If the overlap occurs outside of the bounds of the + loop, there is no dependence. */ + if (x1 > niter || y1 > niter) { - 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; - - /* If the overlap occurs outside of the bounds of the - loop, there is no dependence. */ - if (x0 > niter || y0 > niter) - { - *overlaps_a = conflict_fn_no_dependence (); - *overlaps_b = conflict_fn_no_dependence (); - *last_conflicts = integer_zero_node; - } - else - { - *overlaps_a - = conflict_fn (1, - affine_fn_univar (build_int_cst (NULL_TREE, x0), - 1, - build_int_cst (NULL_TREE, i1))); - *overlaps_b - = conflict_fn (1, - affine_fn_univar (build_int_cst (NULL_TREE, y0), - 1, - build_int_cst (NULL_TREE, j1))); - *last_conflicts = build_int_cst (NULL_TREE, last_conflict); - } + *overlaps_a = conflict_fn_no_dependence (); + *overlaps_b = conflict_fn_no_dependence (); + *last_conflicts = integer_zero_node; + goto end_analyze_subs_aa; } else - { - /* FIXME: For the moment, the upper bound of the - iteration domain for j is not checked. */ - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "affine-affine test failed: unimplemented.\n"); - *overlaps_a = conflict_fn_not_known (); - *overlaps_b = conflict_fn_not_known (); - *last_conflicts = chrec_dont_know; - } + *last_conflicts = build_int_cst (NULL_TREE, last_conflict); } - else - { - /* FIXME: For the moment, the upper bound of the - iteration domain for i is not checked. */ - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "affine-affine test failed: unimplemented.\n"); - *overlaps_a = conflict_fn_not_known (); - *overlaps_b = conflict_fn_not_known (); - *last_conflicts = chrec_dont_know; - } + *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 @@ -2235,7 +2334,6 @@ analyze_subscript_affine_affine (tree chrec_a, *last_conflicts = chrec_dont_know; } } - else { if (dump_file && (dump_flags & TDF_DETAILS)) @@ -2283,7 +2381,7 @@ can_use_analyze_subscript_affine_affine (tree *chrec_a, tree *chrec_b) type = chrec_type (*chrec_a); left_a = CHREC_LEFT (*chrec_a); - left_b = chrec_convert (type, CHREC_LEFT (*chrec_b), NULL_TREE); + 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)) @@ -2294,7 +2392,7 @@ can_use_analyze_subscript_affine_affine (tree *chrec_a, tree *chrec_b) *chrec_a = build_polynomial_chrec (CHREC_VARIABLE (*chrec_a), diff, CHREC_RIGHT (*chrec_a)); - right_b = chrec_convert (type, CHREC_RIGHT (*chrec_b), NULL_TREE); + 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); @@ -2313,7 +2411,8 @@ analyze_siv_subscript (tree chrec_a, tree chrec_b, conflict_function **overlaps_a, conflict_function **overlaps_b, - tree *last_conflicts) + tree *last_conflicts, + int loop_nest_num) { dependence_stats.num_siv++; @@ -2321,17 +2420,17 @@ analyze_siv_subscript (tree chrec_a, fprintf (dump_file, "(analyze_siv_subscript \n"); if (evolution_function_is_constant_p (chrec_a) - && evolution_function_is_affine_p (chrec_b)) + && 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_p (chrec_a) + 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_p (chrec_a) - && evolution_function_is_affine_p (chrec_b)) + 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)) @@ -2355,9 +2454,6 @@ analyze_siv_subscript (tree chrec_a, analyze_subscript_affine_affine (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts); - /* FIXME: The number of iterations is a symbolic expression. - Compute it properly. */ - *last_conflicts = chrec_dont_know; if (CF_NOT_KNOWN_P (*overlaps_a) || CF_NOT_KNOWN_P (*overlaps_b)) @@ -2391,7 +2487,7 @@ analyze_siv_subscript (tree chrec_a, of CHREC does not divide CST, false otherwise. */ static bool -gcd_of_steps_may_divide_p (tree chrec, tree cst) +gcd_of_steps_may_divide_p (const_tree chrec, const_tree cst) { HOST_WIDE_INT cd = 0, val; tree step; @@ -2412,10 +2508,11 @@ gcd_of_steps_may_divide_p (tree chrec, tree cst) return val % cd == 0; } -/* 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: +/* 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)). */ @@ -2424,7 +2521,8 @@ analyze_miv_subscript (tree chrec_a, tree chrec_b, conflict_function **overlaps_a, conflict_function **overlaps_b, - tree *last_conflicts) + 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 @@ -2434,14 +2532,16 @@ analyze_miv_subscript (tree chrec_a, variables. In the MIV case we have to solve a Diophantine equation with 2*n variables (if the subscript uses n IVs). */ - tree difference; + tree type, difference; + dependence_stats.num_miv++; if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "(analyze_miv_subscript \n"); - chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE); - chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE); - difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b); + 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)) { @@ -2456,7 +2556,8 @@ analyze_miv_subscript (tree chrec_a, else if (evolution_function_is_constant_p (difference) /* For the moment, the following is verified: - evolution_function_is_affine_multivariate_p (chrec_a, 0) */ + 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 @@ -2470,9 +2571,9 @@ analyze_miv_subscript (tree chrec_a, dependence_stats.num_miv_independent++; } - else if (evolution_function_is_affine_multivariate_p (chrec_a, 0) + 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, 0) + && evolution_function_is_affine_multivariate_p (chrec_b, loop_nest->num) && !chrec_contains_symbols (chrec_b)) { /* testsuite/.../ssa-chrec-35.c @@ -2518,10 +2619,10 @@ analyze_miv_subscript (tree chrec_a, fprintf (dump_file, ")\n"); } -/* 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. +/* 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: @@ -2533,8 +2634,10 @@ analyze_overlapping_iterations (tree chrec_a, tree chrec_b, conflict_function **overlap_iterations_a, conflict_function **overlap_iterations_b, - tree *last_conflicts) + 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)) @@ -2561,7 +2664,7 @@ analyze_overlapping_iterations (tree chrec_a, /* 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, 0)) + && 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)); @@ -2573,8 +2676,8 @@ analyze_overlapping_iterations (tree chrec_a, yet. */ else if ((chrec_contains_symbols (chrec_a) || chrec_contains_symbols (chrec_b)) - && (!evolution_function_is_affine_multivariate_p (chrec_a, 0) - || !evolution_function_is_affine_multivariate_p (chrec_b, 0))) + && (!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 (); @@ -2589,12 +2692,12 @@ analyze_overlapping_iterations (tree chrec_a, else if (siv_subscript_p (chrec_a, chrec_b)) analyze_siv_subscript (chrec_a, chrec_b, overlap_iterations_a, overlap_iterations_b, - last_conflicts); + last_conflicts, lnn); else analyze_miv_subscript (chrec_a, chrec_b, overlap_iterations_a, overlap_iterations_b, - last_conflicts); + last_conflicts, loop_nest); if (dump_file && (dump_flags & TDF_DETAILS)) { @@ -2756,26 +2859,10 @@ build_classic_dist_vector_1 (struct data_dependence_relation *ddr, return true; } -/* Return true when the DDR contains two data references that have the - same access functions. */ - -static bool -same_access_functions (struct data_dependence_relation *ddr) -{ - unsigned i; - - for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) - if (!eq_evolutions_p (DR_ACCESS_FN (DDR_A (ddr), i), - DR_ACCESS_FN (DDR_B (ddr), i))) - return false; - - return true; -} - /* Return true when the DDR contains only constant access functions. */ static bool -constant_access_functions (struct data_dependence_relation *ddr) +constant_access_functions (const struct data_dependence_relation *ddr) { unsigned i; @@ -2787,9 +2874,9 @@ constant_access_functions (struct data_dependence_relation *ddr) return true; } - /* Helper function for the case where DDR_A and DDR_B are the same - multivariate access function. */ + 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) @@ -2800,10 +2887,14 @@ add_multivariate_self_dist (struct data_dependence_relation *ddr, tree c_2) lambda_vector dist_v; int v1, v2, cd; - /* Polynomials with more than 2 variables are not handled yet. */ - if (TREE_CODE (c_0) != INTEGER_CST) + /* 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_ARE_DEPENDENT (ddr) = chrec_dont_know; + DDR_AFFINE_P (ddr) = false; return; } @@ -2855,7 +2946,17 @@ add_other_self_distances (struct data_dependence_relation *ddr) return; } - add_multivariate_self_dist (ddr, DR_ACCESS_FN (DDR_A (ddr), 0)); + 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; } @@ -2921,14 +3022,15 @@ add_distance_for_zero_overlaps (struct data_dependence_relation *ddr) to represent the data dependence as a distance vector. */ static bool -build_classic_dist_vector (struct data_dependence_relation *ddr) +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 true; + return false; if (same_access_functions (ddr)) { @@ -2980,11 +3082,15 @@ build_classic_dist_vector (struct data_dependence_relation *ddr) if (!lambda_vector_lexico_pos (dist_v, DDR_NB_LOOPS (ddr))) { lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr)); - subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr)); + if (!subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr), + loop_nest)) + return false; compute_subscript_distance (ddr); - build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr), - save_v, &init_b, &index_carry); + 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: @@ -3012,20 +3118,26 @@ build_classic_dist_vector (struct data_dependence_relation *ddr) { lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr)); lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr)); - save_dist_v (ddr, save_v); if (DDR_NB_LOOPS (ddr) > 1) { lambda_vector opposite_v = lambda_vector_new (DDR_NB_LOOPS (ddr)); - subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr)); + if (!subscript_dependence_tester_1 (ddr, DDR_B (ddr), + DDR_A (ddr), loop_nest)) + return false; compute_subscript_distance (ddr); - build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr), - opposite_v, &init_b, &index_carry); + 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 @@ -3101,7 +3213,8 @@ build_classic_dir_vector (struct data_dependence_relation *ddr) static bool subscript_dependence_tester_1 (struct data_dependence_relation *ddr, struct data_reference *dra, - struct data_reference *drb) + struct data_reference *drb, + struct loop *loop_nest) { unsigned int i; tree last_conflicts; @@ -3115,7 +3228,7 @@ subscript_dependence_tester_1 (struct data_dependence_relation *ddr, analyze_overlapping_iterations (DR_ACCESS_FN (dra, i), DR_ACCESS_FN (drb, i), &overlaps_a, &overlaps_b, - &last_conflicts); + &last_conflicts, loop_nest); if (CF_NOT_KNOWN_P (overlaps_a) || CF_NOT_KNOWN_P (overlaps_b)) @@ -3139,6 +3252,11 @@ subscript_dependence_tester_1 (struct data_dependence_relation *ddr, 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; @@ -3148,20 +3266,21 @@ subscript_dependence_tester_1 (struct data_dependence_relation *ddr, return true; } -/* Computes the conflicting iterations, and initialize DDR. */ +/* Computes the conflicting iterations in LOOP_NEST, and initialize DDR. */ static void -subscript_dependence_tester (struct data_dependence_relation *ddr) +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))) + 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)) + if (build_classic_dist_vector (ddr, loop_nest)) build_classic_dir_vector (ddr); if (dump_file && (dump_flags & TDF_DETAILS)) @@ -3169,23 +3288,40 @@ subscript_dependence_tester (struct data_dependence_relation *ddr) } /* Returns true when all the access functions of A are affine or - constant. */ + constant with respect to LOOP_NEST. */ static bool -access_functions_are_affine_or_constant_p (struct data_reference *a) +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_constant_p (t) - && !evolution_function_is_affine_multivariate_p (t, 0)) + if (!evolution_function_is_invariant_p (t, loop_nest->num) + && !evolution_function_is_affine_multivariate_p (t, loop_nest->num)) return false; return true; } +/* Return true if we can create an affine data-ref for OP in STMT. */ + +bool +stmt_simple_memref_p (struct loop *loop, gimple stmt, tree op) +{ + data_reference_p dr; + bool res = true; + + dr = create_data_ref (loop, op, stmt, true); + if (!access_functions_are_affine_or_constant_p (dr, loop)) + res = false; + + free_data_ref (dr); + return res; +} + /* Initializes an equation for an OMEGA problem using the information contained in the ACCESS_FUN. Returns true when the operation succeeded. @@ -3368,9 +3504,11 @@ omega_setup_subscript (tree access_fun_a, tree access_fun_b, omega_pb pb, bool *maybe_dependent) { int eq; - tree fun_a = chrec_convert (integer_type_node, access_fun_a, NULL_TREE); - tree fun_b = chrec_convert (integer_type_node, access_fun_b, NULL_TREE); - tree difference = chrec_fold_minus (integer_type_node, fun_a, fun_b); + 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. */ @@ -3385,8 +3523,7 @@ omega_setup_subscript (tree access_fun_a, tree access_fun_b, return true; } - fun_b = chrec_fold_multiply (integer_type_node, fun_b, - integer_minus_one_node); + 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) @@ -3449,7 +3586,7 @@ init_omega_for_ddr_1 (struct data_reference *dra, struct data_reference *drb, 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, true); + HOST_WIDE_INT nbi = estimated_loop_iterations_int (loopi, false); /* 0 <= loop_x */ ineq = omega_add_zero_geq (pb, omega_black); @@ -3710,17 +3847,18 @@ ddr_consistent_p (FILE *file, 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. +/* 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) +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); @@ -3729,24 +3867,25 @@ compute_affine_dependence (struct data_dependence_relation *ddr) { fprintf (dump_file, "(compute_affine_dependence\n"); fprintf (dump_file, " (stmt_a = \n"); - print_generic_expr (dump_file, DR_STMT (dra), 0); + print_gimple_stmt (dump_file, DR_STMT (dra), 0, 0); fprintf (dump_file, ")\n (stmt_b = \n"); - print_generic_expr (dump_file, DR_STMT (drb), 0); + 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) + 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) - && access_functions_are_affine_or_constant_p (drb)) + 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); + subscript_dependence_tester (ddr, loop_nest); if (dump_file && (dump_flags & TDF_DETAILS)) { @@ -3784,7 +3923,7 @@ compute_affine_dependence (struct data_dependence_relation *ddr) } } else - subscript_dependence_tester (ddr); + subscript_dependence_tester (ddr, loop_nest); } /* As a last case, if the dependence cannot be determined, or if @@ -3826,11 +3965,16 @@ compute_self_dependence (struct data_dependence_relation *ddr) for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript); i++) { + 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)); + = conflict_fn (1, affine_fn_cst (integer_zero_node)); SUB_CONFLICTS_IN_B (subscript) - = conflict_fn (1, affine_fn_cst (integer_zero_node)); + = conflict_fn (1, affine_fn_cst (integer_zero_node)); SUB_LAST_CONFLICT (subscript) = chrec_dont_know; } @@ -3860,7 +4004,7 @@ compute_all_dependences (VEC (data_reference_p, heap) *datarefs, { ddr = initialize_data_dependence_relation (a, b, loop_nest); VEC_safe_push (ddr_p, heap, *dependence_relations, ddr); - compute_affine_dependence (ddr); + compute_affine_dependence (ddr, VEC_index (loop_p, loop_nest, 0)); } if (compute_self_and_rr) @@ -3876,34 +4020,37 @@ compute_all_dependences (VEC (data_reference_p, heap) *datarefs, true if STMT clobbers memory, false otherwise. */ bool -get_references_in_stmt (tree stmt, VEC (data_ref_loc, heap) **references) +get_references_in_stmt (gimple stmt, VEC (data_ref_loc, heap) **references) { bool clobbers_memory = false; data_ref_loc *ref; - tree *op0, *op1, call; + 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. */ - call = get_call_expr_in (stmt); - if ((call - && !(call_expr_flags (call) & (ECF_CONST | ECF_PURE))) - || (TREE_CODE (stmt) == ASM_EXPR - && ASM_VOLATILE_P (stmt))) + 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 (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT) + if (stmt_code == GIMPLE_ASSIGN) { - op0 = &GIMPLE_STMT_OPERAND (stmt, 0); - op1 = &GIMPLE_STMT_OPERAND (stmt, 1); + tree base; + op0 = gimple_assign_lhs_ptr (stmt); + op1 = gimple_assign_rhs1_ptr (stmt); if (DECL_P (*op1) - || REFERENCE_CLASS_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; @@ -3911,24 +4058,23 @@ get_references_in_stmt (tree stmt, VEC (data_ref_loc, heap) **references) } if (DECL_P (*op0) - || REFERENCE_CLASS_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; } } - - if (call) + else if (stmt_code == GIMPLE_CALL) { - unsigned i, n = call_expr_nargs (call); + unsigned i, n = gimple_call_num_args (stmt); for (i = 0; i < n; i++) { - op0 = &CALL_EXPR_ARG (call, i); + op0 = gimple_call_arg_ptr (stmt, i); if (DECL_P (*op0) - || REFERENCE_CLASS_P (*op0)) + || (REFERENCE_CLASS_P (*op0) && get_base_address (*op0))) { ref = VEC_safe_push (data_ref_loc, heap, *references, NULL); ref->pos = op0; @@ -3942,10 +4088,10 @@ get_references_in_stmt (tree stmt, VEC (data_ref_loc, heap) **references) /* 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 analysed. */ + loop of the loop nest in which the references should be analyzed. */ -static bool -find_data_references_in_stmt (struct loop *nest, tree stmt, +bool +find_data_references_in_stmt (struct loop *nest, gimple stmt, VEC (data_reference_p, heap) **datarefs) { unsigned i; @@ -3989,13 +4135,13 @@ find_data_references_in_stmt (struct loop *nest, tree stmt, TODO: This function should be made smarter so that it can handle address arithmetic as if they were array accesses, etc. */ -static tree +tree find_data_references_in_loop (struct loop *loop, VEC (data_reference_p, heap) **datarefs) { basic_block bb, *bbs; unsigned int i; - block_stmt_iterator bsi; + gimple_stmt_iterator bsi; bbs = get_loop_body_in_dom_order (loop); @@ -4003,9 +4149,9 @@ find_data_references_in_loop (struct loop *loop, { bb = bbs[i]; - for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) + for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) { - tree stmt = bsi_stmt (bsi); + gimple stmt = gsi_stmt (bsi); if (!find_data_references_in_stmt (loop, stmt, datarefs)) { @@ -4065,18 +4211,20 @@ find_loop_nest (struct loop *loop, VEC (loop_p, heap) **loop_nest) return true; } -/* Given a loop nest LOOP, the following vectors are returned: +/* 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. */ -void +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)); @@ -4094,6 +4242,7 @@ compute_data_dependences_for_loop (struct loop *loop, 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, @@ -4145,7 +4294,9 @@ compute_data_dependences_for_loop (struct loop *loop, 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 @@ -4248,8 +4399,12 @@ free_dependence_relation (struct data_dependence_relation *ddr) if (ddr == NULL) return; - if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_SUBSCRIPTS (ddr)) + 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); } @@ -4294,3 +4449,663 @@ free_data_refs (VEC (data_reference_p, heap) *datarefs) VEC_free (data_reference_p, heap, datarefs); } + + +/* 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); + + 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 +dot_rdg_1 (FILE *file, struct graph *rdg) +{ + int i; + + fprintf (file, "digraph RDG {\n"); + + for (i = 0; i < rdg->n_vertices; i++) + { + 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 (); + } + } + + fprintf (file, "}\n\n"); +} + +/* Display SCOP using dotty. */ + +void +dot_rdg (struct graph *rdg) +{ + FILE *file = fopen ("/tmp/rdg.dot", "w"); + gcc_assert (file != NULL); + + 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(()) +{ + 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)) + { + data_reference_p tmp = dra; + dra = drb; + drb = tmp; + } + + va = rdg_vertex_for_stmt (rdg, DR_STMT (dra)); + vb = rdg_vertex_for_stmt (rdg, DR_STMT (drb)); + + if (va < 0 || vb < 0) + return; + + e = add_edge (rdg, va, vb); + e->data = XNEW (struct rdg_edge); + + RDGE_LEVEL (e) = level; + RDGE_RELATION (e) = ddr; + + /* 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; +} + +/* Creates dependence edges in RDG for all the uses of DEF. IDEF is + the index of DEF in RDG. */ + +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)); + + if (use < 0) + continue; + + e = add_edge (rdg, idef, use); + e->data = XNEW (struct rdg_edge); + RDGE_TYPE (e) = flow_dd; + RDGE_RELATION (e) = NULL; + } +} + +/* Creates the edges of the reduced dependence graph RDG. */ + +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); +} + +/* Build the vertices of the reduced dependence graph RDG. */ + +void +create_rdg_vertices (struct graph *rdg, VEC (gimple, heap) *stmts) +{ + int i, j; + gimple stmt; + + 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); + + v->data = XNEW (struct rdg_vertex); + RDG_STMT (rdg, i) = stmt; + + RDG_MEM_WRITE_STMT (rdg, i) = false; + RDG_MEM_READS_STMT (rdg, i) = false; + if (gimple_code (stmt) == GIMPLE_PHI) + continue; + + 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; + + VEC_free (data_ref_loc, heap, references); + } +} + +/* 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. */ + +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); + + for (i = 0; i < loop->num_nodes; i++) + { + basic_block bb = bbs[i]; + gimple_stmt_iterator bsi; + gimple stmt; + + for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi)) + VEC_safe_push (gimple, heap, *stmts, gsi_stmt (bsi)); + + 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); + } + } + + free (bbs); +} + +/* Returns true when all the dependences are computable. */ + +static bool +known_dependences_p (VEC (ddr_p, heap) *dependence_relations) +{ + ddr_p ddr; + unsigned int 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; +} + +/* Computes a hash function for element ELT. */ + +static hashval_t +hash_stmt_vertex_info (const void *elt) +{ + const struct rdg_vertex_info *const rvi = + (const struct rdg_vertex_info *) elt; + gimple stmt = rvi->stmt; + + return htab_hash_pointer (stmt); +} + +/* Compares database elements E1 and E2. */ + +static int +eq_stmt_vertex_info (const void *e1, const void *e2) +{ + const struct rdg_vertex_info *elt1 = (const struct rdg_vertex_info *) e1; + const struct rdg_vertex_info *elt2 = (const struct rdg_vertex_info *) e2; + + return elt1->stmt == elt2->stmt; +} + +/* Free the element E. */ + +static void +hash_stmt_vertex_del (void *e) +{ + free (e); +} + +/* Build the Reduced Dependence Graph (RDG) with one vertex per + statement of the loop nest, and one edge per data dependence or + scalar dependence. */ + +struct graph * +build_empty_rdg (int n_stmts) +{ + int nb_data_refs = 10; + struct graph *rdg = new_graph (n_stmts); + + rdg->indices = htab_create (nb_data_refs, hash_stmt_vertex_info, + eq_stmt_vertex_info, hash_stmt_vertex_del); + return rdg; +} + +/* Build the Reduced Dependence Graph (RDG) with one vertex per + statement of the loop nest, and one edge per data dependence or + scalar dependence. */ + +struct graph * +build_rdg (struct loop *loop) +{ + 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); + + if (!known_dependences_p (dependence_relations)) + { + free_dependence_relations (dependence_relations); + free_data_refs (datarefs); + VEC_free (gimple, heap, stmts); + + return rdg; + } + + stmts_from_loop (loop, &stmts); + rdg = build_empty_rdg (VEC_length (gimple, stmts)); + + 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); + + VEC_free (gimple, heap, stmts); + return rdg; +} + +/* Free the reduced dependence graph RDG. */ + +void +free_rdg (struct graph *rdg) +{ + int i; + + for (i = 0; i < rdg->n_vertices; i++) + free (rdg->vertices[i].data); + + htab_delete (rdg->indices); + free_graph (rdg); +} + +/* Initialize STMTS with all the statements of LOOP that contain a + store to memory. */ + +void +stores_from_loop (struct loop *loop, VEC (gimple, heap) **stmts) +{ + unsigned int i; + basic_block *bbs = get_loop_body_in_dom_order (loop); + + for (i = 0; i < loop->num_nodes; i++) + { + basic_block bb = bbs[i]; + gimple_stmt_iterator bsi; + + 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)); + } + + 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); + + if (!base_address) + goto end; + + switch (TREE_CODE (base_address)) + { + case ADDR_EXPR: + base = TREE_OPERAND (base_address, 0); + break; + + default: + base = base_address; + break; + } + + end: + free_data_ref (dr); + return base; +} + +/* Determines whether the statement from vertex V of the RDG has a + definition used outside the loop that contains this statement. */ + +bool +rdg_defs_used_in_other_loops_p (struct graph *rdg, int v) +{ + 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; + + 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; + } + } + + return false; +} + +/* 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. */ + +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; + + 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); + + if (base1) + for (j = 0; VEC_iterate (data_ref_loc, refs2, j, ref2); j++) + if (base1 == ref_base_address (s2, ref2)) + { + res = true; + goto end; + } + } + + end: + VEC_free (data_ref_loc, heap, refs1); + VEC_free (data_ref_loc, heap, refs2); + return res; +} + +/* Helper function for the hashtab. */ + +static int +have_similar_memory_accesses_1 (const void *s1, const void *s2) +{ + return have_similar_memory_accesses (CONST_CAST_GIMPLE ((const_gimple) s1), + CONST_CAST_GIMPLE ((const_gimple) s2)); +} + +/* Helper function for the hashtab. */ + +static hashval_t +ref_base_address_1 (const void *s) +{ + 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; + } + + VEC_free (data_ref_loc, heap, refs); + return res; +} + +/* Try to remove duplicated write data references from STMTS. */ + +void +remove_similar_memory_refs (VEC (gimple, heap) **stmts) +{ + 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; VEC_iterate (gimple, *stmts, i, stmt); ) + { + void **slot; + + slot = htab_find_slot (seen, stmt, INSERT); + + if (*slot) + VEC_ordered_remove (gimple, *stmts, i); + else + { + *slot = (void *) stmt; + i++; + } + } + + 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; +}