X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Ftree-data-ref.c;h=9f5a623b2fa9e161b85f7c0c6acfe9a0abe014d4;hb=9d33046c199ad03cc0ba1210be7bcfbbcb136254;hp=1b5e92b5af344283b80f9590544b2c7164f1be84;hpb=75a70cf95f65fe9204b15ad9aba31c571381d224;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c index 1b5e92b5af3..9f5a623b2fa 100644 --- a/gcc/tree-data-ref.c +++ b/gcc/tree-data-ref.c @@ -1,5 +1,6 @@ /* Data references and dependences detectors. - Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc. + Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009 + Free Software Foundation, Inc. Contributed by Sebastian Pop This file is part of GCC. @@ -20,57 +21,57 @@ 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 - in DATA_REFERENCE structures. - - The basic test for determining the dependences is: - given two access functions chrec1 and chrec2 to a same array, and - x and y two vectors from the iteration domain, the same element of + in DATA_REFERENCE structures. + + The basic test for determining the dependences is: + given two access functions chrec1 and chrec2 to a same array, and + x and y two vectors from the iteration domain, the same element of the array is accessed twice at iterations x and y if and only if: | chrec1 (x) == chrec2 (y). - + The goals of this analysis are: - + - to determine the independence: the relation between two independent accesses is qualified with the chrec_known (this information allows a loop parallelization), - + - when two data references access the same data, to qualify the dependence relation with classic dependence representations: - + - distance vectors - direction vectors - loop carried level dependence - polyhedron dependence or with the chains of recurrences based representation, - - - to define a knowledge base for storing the data dependence + + - to define a knowledge base for storing the data dependence information, - + - to define an interface to access this data. - - + + Definitions: - + - subscript: given two array accesses a subscript is the tuple composed of the access functions for a given dimension. Example: Given A[f1][f2][f3] and B[g1][g2][g3], there are three subscripts: (f1, g1), (f2, g2), (f3, g3). - Diophantine equation: an equation whose coefficients and - solutions are integer constants, for example the equation + solutions are integer constants, for example the equation | 3*x + 2*y = 1 has an integer solution x = 1 and y = -1. - + References: - + - "Advanced Compilation for High Performance Computing" by Randy Allen and Ken Kennedy. - http://citeseer.ist.psu.edu/goff91practical.html - - - "Loop Transformations for Restructuring Compilers - The Foundations" + http://citeseer.ist.psu.edu/goff91practical.html + + - "Loop Transformations for Restructuring Compilers - The Foundations" by Utpal Banerjee. - + */ #include "config.h" @@ -78,6 +79,7 @@ along with GCC; see the file COPYING3. If not see #include "coretypes.h" #include "tm.h" #include "ggc.h" +#include "flags.h" #include "tree.h" /* These RTL headers are needed for basic-block.h. */ @@ -126,7 +128,7 @@ static bool subscript_dependence_tester_1 (struct data_dependence_relation *, struct loop *); /* Returns true iff A divides B. */ -static inline bool +static inline bool tree_fold_divides_p (const_tree a, const_tree b) { gcc_assert (TREE_CODE (a) == INTEGER_CST); @@ -136,7 +138,7 @@ tree_fold_divides_p (const_tree a, const_tree b) /* Returns true iff A divides B. */ -static inline bool +static inline bool int_divides_p (int a, int b) { return ((b % a) == 0); @@ -144,9 +146,9 @@ int_divides_p (int a, int b) -/* Dump into FILE all the data references from DATAREFS. */ +/* Dump into FILE all the data references from DATAREFS. */ -void +void dump_data_references (FILE *file, VEC (data_reference_p, heap) *datarefs) { unsigned int i; @@ -156,18 +158,26 @@ 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. */ +/* Dump into STDERR all the data references from DATAREFS. */ -void +void +debug_data_references (VEC (data_reference_p, heap) *datarefs) +{ + dump_data_references (stderr, datarefs); +} + +/* 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. */ +/* Dump into FILE all the dependence relations from DDRS. */ -void -dump_data_dependence_relations (FILE *file, +void +dump_data_dependence_relations (FILE *file, VEC (ddr_p, heap) *ddrs) { unsigned int i; @@ -177,21 +187,29 @@ dump_data_dependence_relations (FILE *file, dump_data_dependence_relation (file, ddr); } +/* Print to STDERR the data_reference DR. */ + +void +debug_data_reference (struct data_reference *dr) +{ + dump_data_reference (stderr, dr); +} + /* Dump function for a DATA_REFERENCE structure. */ -void -dump_data_reference (FILE *outf, +void +dump_data_reference (FILE *outf, struct data_reference *dr) { unsigned int i; - + fprintf (outf, "(Data Ref: \n stmt: "); print_gimple_stmt (outf, DR_STMT (dr), 0, 0); fprintf (outf, " ref: "); print_generic_stmt (outf, DR_REF (dr), 0); fprintf (outf, " base_object: "); print_generic_stmt (outf, DR_BASE_OBJECT (dr), 0); - + for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++) { fprintf (outf, " Access function %d: ", i); @@ -241,7 +259,7 @@ dump_conflict_function (FILE *outf, conflict_function *cf) /* Dump function for a SUBSCRIPT structure. */ -void +void dump_subscript (FILE *outf, struct subscript *subscript) { conflict_function *cf = SUB_CONFLICTS_IN_A (subscript); @@ -255,7 +273,7 @@ dump_subscript (FILE *outf, struct subscript *subscript) fprintf (outf, " last_conflict: "); print_generic_stmt (outf, last_iteration, 0); } - + cf = SUB_CONFLICTS_IN_B (subscript); fprintf (outf, " iterations_that_access_an_element_twice_in_B: "); dump_conflict_function (outf, cf); @@ -283,7 +301,8 @@ print_direction_vector (FILE *outf, for (eq = 0; eq < length; eq++) { - enum data_dependence_direction dir = dirv[eq]; + enum data_dependence_direction dir = ((enum data_dependence_direction) + dirv[eq]); switch (dir) { @@ -344,7 +363,7 @@ print_dist_vectors (FILE *outf, VEC (lambda_vector, heap) *dist_vects, /* Debug version. */ -void +void debug_data_dependence_relation (struct data_dependence_relation *ddr) { dump_data_dependence_relation (stderr, ddr); @@ -352,8 +371,8 @@ debug_data_dependence_relation (struct data_dependence_relation *ddr) /* Dump function for a DATA_DEPENDENCE_RELATION structure. */ -void -dump_data_dependence_relation (FILE *outf, +void +dump_data_dependence_relation (FILE *outf, struct data_dependence_relation *ddr) { struct data_reference *dra, *drb; @@ -362,6 +381,19 @@ dump_data_dependence_relation (FILE *outf, if (!ddr || DDR_ARE_DEPENDENT (ddr) == chrec_dont_know) { + if (ddr) + { + dra = DDR_A (ddr); + drb = DDR_B (ddr); + if (dra) + dump_data_reference (outf, dra); + else + fprintf (outf, " (nil)\n"); + if (drb) + dump_data_reference (outf, drb); + else + fprintf (outf, " (nil)\n"); + } fprintf (outf, " (don't know)\n)\n"); return; } @@ -373,7 +405,7 @@ dump_data_dependence_relation (FILE *outf, if (DDR_ARE_DEPENDENT (ddr) == chrec_known) fprintf (outf, " (no dependence)\n"); - + else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE) { unsigned int i; @@ -415,40 +447,40 @@ dump_data_dependence_relation (FILE *outf, /* Dump function for a DATA_DEPENDENCE_DIRECTION structure. */ void -dump_data_dependence_direction (FILE *file, +dump_data_dependence_direction (FILE *file, enum data_dependence_direction dir) { switch (dir) { - case dir_positive: + case dir_positive: fprintf (file, "+"); break; - + case dir_negative: fprintf (file, "-"); break; - + case dir_equal: fprintf (file, "="); break; - + case dir_positive_or_negative: fprintf (file, "+-"); break; - - case dir_positive_or_equal: + + case dir_positive_or_equal: fprintf (file, "+="); break; - - case dir_negative_or_equal: + + case dir_negative_or_equal: fprintf (file, "-="); break; - - case dir_star: - fprintf (file, "*"); + + case dir_star: + fprintf (file, "*"); break; - - default: + + default: break; } } @@ -458,7 +490,7 @@ dump_data_dependence_direction (FILE *file, dependence vectors, or in other words the number of loops in the considered nest. */ -void +void dump_dist_dir_vectors (FILE *file, VEC (ddr_p, heap) *ddrs) { unsigned int i, j; @@ -488,7 +520,7 @@ dump_dist_dir_vectors (FILE *file, VEC (ddr_p, heap) *ddrs) /* Dumps the data dependence relations DDRS in FILE. */ -void +void dump_ddrs (FILE *file, VEC (ddr_p, heap) *ddrs) { unsigned int i; @@ -551,6 +583,7 @@ split_constant_offset_1 (tree type, tree op0, enum tree_code code, tree op1, enum machine_mode pmode; int punsignedp, pvolatilep; + op0 = TREE_OPERAND (op0, 0); if (!handled_component_p (op0)) return false; @@ -581,8 +614,7 @@ split_constant_offset_1 (tree type, tree op0, enum tree_code code, tree op1, 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) + if (CONVERT_EXPR_P (var0)) { gimplify_conversion (&var0); // Attempt to fill in any within var0 found ARRAY_REF's @@ -613,6 +645,24 @@ split_constant_offset_1 (tree type, tree op0, enum tree_code code, tree op1, return split_constant_offset_1 (type, var0, subcode, var1, var, off); } + CASE_CONVERT: + { + /* We must not introduce undefined overflow, and we must not change the value. + Hence we're okay if the inner type doesn't overflow to start with + (pointer or signed), the outer type also is an integer or pointer + and the outer precision is at least as large as the inner. */ + tree itype = TREE_TYPE (op0); + if ((POINTER_TYPE_P (itype) + || (INTEGRAL_TYPE_P (itype) && TYPE_OVERFLOW_UNDEFINED (itype))) + && TYPE_PRECISION (type) >= TYPE_PRECISION (itype) + && (POINTER_TYPE_P (type) || INTEGRAL_TYPE_P (type))) + { + split_constant_offset (op0, &var0, off); + *var = fold_convert (type, var0); + return true; + } + return false; + } default: return false; @@ -666,10 +716,11 @@ canonicalize_base_object_address (tree addr) return build_fold_addr_expr (TREE_OPERAND (addr, 0)); } -/* Analyzes the behavior of the memory reference DR in the innermost loop that - contains it. */ +/* Analyzes the behavior of the memory reference DR in the innermost loop or + basic block that contains it. Returns true if analysis succeed or false + otherwise. */ -void +bool dr_analyze_innermost (struct data_reference *dr) { gimple stmt = DR_STMT (dr); @@ -681,6 +732,7 @@ dr_analyze_innermost (struct data_reference *dr) int punsignedp, pvolatilep; affine_iv base_iv, offset_iv; tree init, dinit, step; + bool in_loop = (loop && loop->num); if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "analyze_innermost: "); @@ -693,26 +745,47 @@ dr_analyze_innermost (struct data_reference *dr) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "failed: bit offset alignment.\n"); - return; + return false; } base = build_fold_addr_expr (base); - if (!simple_iv (loop, stmt, base, &base_iv, false)) + if (in_loop) { - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "failed: evolution of base is not affine.\n"); - return; + if (!simple_iv (loop, loop_containing_stmt (stmt), base, &base_iv, + false)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "failed: evolution of base is not affine.\n"); + return false; + } + } + else + { + base_iv.base = base; + base_iv.step = ssize_int (0); + base_iv.no_overflow = true; } + if (!poffset) { offset_iv.base = ssize_int (0); offset_iv.step = ssize_int (0); } - else if (!simple_iv (loop, stmt, poffset, &offset_iv, false)) + else { - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "failed: evolution of offset is not affine.\n"); - return; + if (!in_loop) + { + offset_iv.base = poffset; + offset_iv.step = ssize_int (0); + } + else if (!simple_iv (loop, loop_containing_stmt (stmt), + poffset, &offset_iv, false)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "failed: evolution of offset is not" + " affine.\n"); + return false; + } } init = ssize_int (pbitpos / BITS_PER_UNIT); @@ -735,6 +808,8 @@ dr_analyze_innermost (struct data_reference *dr) if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "success.\n"); + + return true; } /* Determines the base object and the list of indices of memory reference @@ -747,28 +822,35 @@ dr_analyze_indices (struct data_reference *dr, struct loop *nest) 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; + tree base, off, access_fn = NULL_TREE; + basic_block before_loop = NULL; + + if (nest) + before_loop = block_before_loop (nest); while (handled_component_p (aref)) { 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); + if (nest) + { + access_fn = analyze_scalar_evolution (loop, op); + 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); } - + aref = TREE_OPERAND (aref, 0); } - if (INDIRECT_REF_P (aref)) + if (nest && INDIRECT_REF_P (aref)) { op = TREE_OPERAND (aref, 0); access_fn = analyze_scalar_evolution (loop, op); - access_fn = instantiate_scev (nest, loop, 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, @@ -787,34 +869,15 @@ dr_analyze_indices (struct data_reference *dr, struct loop *nest) static void dr_analyze_alias (struct data_reference *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; - tree op; - bitmap vops; + tree base = get_base_address (ref), addr; - if (DECL_P (base)) - smt = base; - else if (INDIRECT_REF_P (base)) + if (INDIRECT_REF_P (base)) { 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); - } - } - - DR_SYMBOL_TAG (dr) = smt; - - 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_PTR_INFO (dr) = SSA_NAME_PTR_INFO (addr); } - - DR_VOPS (dr) = vops; } /* Returns true if the address of DR is invariant. */ @@ -837,7 +900,6 @@ dr_address_invariant_p (struct data_reference *dr) void free_data_ref (data_reference_p dr) { - BITMAP_FREE (DR_VOPS (dr)); VEC_free (tree, heap, DR_ACCESS_FNS (dr)); free (dr); } @@ -882,12 +944,10 @@ create_data_ref (struct loop *nest, tree memref, gimple stmt, bool is_read) 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; + return dr; } /* Returns true if FNA == FNB. */ @@ -1002,7 +1062,7 @@ affine_fn_op (enum tree_code op, affine_fn fna, affine_fn fnb) VEC_quick_push (tree, ret, fold_build2 (op, type, - VEC_index (tree, fna, i), + VEC_index (tree, fna, i), VEC_index (tree, fnb, i))); } @@ -1054,11 +1114,11 @@ compute_subscript_distance (struct data_dependence_relation *ddr) if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE) { 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); @@ -1071,7 +1131,7 @@ compute_subscript_distance (struct data_dependence_relation *ddr) return; } diff = affine_fn_minus (fn_a, fn_b); - + if (affine_function_constant_p (diff)) SUB_DISTANCE (subscript) = affine_function_base (diff); else @@ -1225,7 +1285,7 @@ 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 +bool dr_may_alias_p (const struct data_reference *a, const struct data_reference *b) { const_tree addr_a = DR_BASE_ADDRESS (a); @@ -1233,29 +1293,37 @@ dr_may_alias_p (const struct data_reference *a, const struct data_reference *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; - /* 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; + /* Query the alias oracle. */ + if (!DR_IS_READ (a) && !DR_IS_READ (b)) + { + if (!refs_output_dependent_p (DR_REF (a), DR_REF (b))) + return false; + } + else if (DR_IS_READ (a) && !DR_IS_READ (b)) + { + if (!refs_anti_dependent_p (DR_REF (a), DR_REF (b))) + return false; + } + else if (!refs_may_alias_p (DR_REF (a), DR_REF (b))) + return false; + if (!addr_a || !addr_b) return true; - /* 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 the references are based on different static objects, they cannot + alias (PTA should be able to disambiguate such accesses, but often + it fails to). */ 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, + /* 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); @@ -1267,7 +1335,7 @@ dr_may_alias_p (const struct data_reference *a, const struct data_reference *b) if (TREE_CODE (addr_b) == SSA_NAME) decl_b = SSA_NAME_VAR (addr_b); - if (TYPE_RESTRICT (type_a) && TYPE_RESTRICT (type_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) @@ -1286,13 +1354,13 @@ static void compute_self_dependence (struct data_dependence_relation *); size of the classic distance/direction vectors. */ static struct data_dependence_relation * -initialize_data_dependence_relation (struct data_reference *a, +initialize_data_dependence_relation (struct data_reference *a, struct data_reference *b, VEC (loop_p, heap) *loop_nest) { struct data_dependence_relation *res; unsigned int i; - + res = XNEW (struct data_dependence_relation); DDR_A (res) = a; DDR_B (res) = b; @@ -1304,14 +1372,14 @@ initialize_data_dependence_relation (struct data_reference *a, if (a == NULL || b == NULL) { - DDR_ARE_DEPENDENT (res) = chrec_dont_know; + DDR_ARE_DEPENDENT (res) = chrec_dont_know; return res; - } + } /* If the data references do not alias, then they are independent. */ if (!dr_may_alias_p (a, b)) { - DDR_ARE_DEPENDENT (res) = chrec_known; + DDR_ARE_DEPENDENT (res) = chrec_known; return res; } @@ -1333,17 +1401,18 @@ initialize_data_dependence_relation (struct data_reference *a, 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; + DDR_ARE_DEPENDENT (res) = chrec_dont_know; return res; } /* 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))) + if (loop_nest + && !object_address_invariant_in_loop_p (VEC_index (loop_p, loop_nest, 0), + DR_BASE_OBJECT (a))) { - DDR_ARE_DEPENDENT (res) = chrec_dont_know; + DDR_ARE_DEPENDENT (res) = chrec_dont_know; return res; } @@ -1359,7 +1428,7 @@ initialize_data_dependence_relation (struct data_reference *a, for (i = 0; i < DR_NUM_DIMENSIONS (a); i++) { 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 (); @@ -1398,6 +1467,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); } @@ -1406,7 +1476,7 @@ free_subscripts (VEC (subscript_p, heap) *subscripts) description. */ static inline void -finalize_ddr_dependent (struct data_dependence_relation *ddr, +finalize_ddr_dependent (struct data_dependence_relation *ddr, tree chrec) { if (dump_file && (dump_flags & TDF_DETAILS)) @@ -1416,7 +1486,7 @@ finalize_ddr_dependent (struct data_dependence_relation *ddr, fprintf (dump_file, ")\n"); } - DDR_ARE_DEPENDENT (ddr) = chrec; + DDR_ARE_DEPENDENT (ddr) = chrec; free_subscripts (DDR_SUBSCRIPTS (ddr)); DDR_SUBSCRIPTS (ddr) = NULL; } @@ -1458,7 +1528,7 @@ siv_subscript_p (const_tree chrec_a, const_tree 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)) { @@ -1470,16 +1540,16 @@ siv_subscript_p (const_tree chrec_a, const_tree chrec_b) case POLYNOMIAL_CHREC: if (CHREC_VARIABLE (chrec_a) != CHREC_VARIABLE (chrec_b)) return false; - + default: return true; } - + default: return true; } } - + return false; } @@ -1495,7 +1565,7 @@ conflict_fn (unsigned n, ...) 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); @@ -1537,16 +1607,16 @@ affine_fn_univar (tree cst, unsigned dim, tree coef) CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */ -static void -analyze_ziv_subscript (tree chrec_a, - tree chrec_b, +static void +analyze_ziv_subscript (tree chrec_a, + tree chrec_b, conflict_function **overlaps_a, - conflict_function **overlaps_b, + conflict_function **overlaps_b, tree *last_conflicts) { tree type, difference; dependence_stats.num_ziv++; - + if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "(analyze_ziv_subscript \n"); @@ -1554,7 +1624,7 @@ analyze_ziv_subscript (tree chrec_a, 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)) { case INTEGER_CST: @@ -1576,9 +1646,9 @@ analyze_ziv_subscript (tree chrec_a, dependence_stats.num_ziv_independent++; } break; - + default: - /* We're not sure whether the indexes overlap. For the moment, + /* 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"); @@ -1589,7 +1659,7 @@ analyze_ziv_subscript (tree chrec_a, dependence_stats.num_ziv_unimplemented++; break; } - + if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, ")\n"); } @@ -1641,7 +1711,7 @@ estimated_loop_iterations_int (struct loop *loop, bool conservative) 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 @@ -1672,10 +1742,10 @@ estimated_loop_iterations_tree (struct loop *loop, bool conservative) CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */ static void -analyze_siv_subscript_cst_affine (tree chrec_a, +analyze_siv_subscript_cst_affine (tree chrec_a, tree chrec_b, - conflict_function **overlaps_a, - conflict_function **overlaps_b, + conflict_function **overlaps_a, + conflict_function **overlaps_b, tree *last_conflicts) { bool value0, value1, value2; @@ -1685,11 +1755,11 @@ analyze_siv_subscript_cst_affine (tree chrec_a, 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"); + fprintf (dump_file, "siv test failed: chrec is not positive.\n"); dependence_stats.num_siv_unimplemented++; *overlaps_a = conflict_fn_not_known (); @@ -1707,7 +1777,7 @@ analyze_siv_subscript_cst_affine (tree chrec_a, fprintf (dump_file, "siv test failed: chrec not positive.\n"); *overlaps_a = conflict_fn_not_known (); - *overlaps_b = conflict_fn_not_known (); + *overlaps_b = conflict_fn_not_known (); *last_conflicts = chrec_dont_know; dependence_stats.num_siv_unimplemented++; return; @@ -1716,11 +1786,11 @@ analyze_siv_subscript_cst_affine (tree chrec_a, { if (value1 == true) { - /* Example: + /* Example: chrec_a = 12 chrec_b = {10, +, 1} */ - + if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference)) { HOST_WIDE_INT numiter; @@ -1732,7 +1802,7 @@ analyze_siv_subscript_cst_affine (tree chrec_a, 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. */ @@ -1748,29 +1818,29 @@ analyze_siv_subscript_cst_affine (tree chrec_a, *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 (); + *overlaps_b = conflict_fn_no_dependence (); *last_conflicts = integer_zero_node; dependence_stats.num_siv_independent++; return; } } - + else { - /* Example: + /* 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 (); @@ -1780,7 +1850,7 @@ analyze_siv_subscript_cst_affine (tree chrec_a, } } } - else + else { if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2)) { @@ -1788,7 +1858,7 @@ analyze_siv_subscript_cst_affine (tree chrec_a, fprintf (dump_file, "siv test failed: chrec not positive.\n"); *overlaps_a = conflict_fn_not_known (); - *overlaps_b = conflict_fn_not_known (); + *overlaps_b = conflict_fn_not_known (); *last_conflicts = chrec_dont_know; dependence_stats.num_siv_unimplemented++; return; @@ -1797,7 +1867,7 @@ analyze_siv_subscript_cst_affine (tree chrec_a, { if (value2 == false) { - /* Example: + /* Example: chrec_a = 3 chrec_b = {10, +, -1} */ @@ -1826,17 +1896,17 @@ analyze_siv_subscript_cst_affine (tree chrec_a, *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 (); + *overlaps_b = conflict_fn_no_dependence (); *last_conflicts = integer_zero_node; dependence_stats.num_siv_independent++; return; @@ -1844,10 +1914,10 @@ analyze_siv_subscript_cst_affine (tree chrec_a, } else { - /* Example: - chrec_a = 3 + /* 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 (); @@ -1892,6 +1962,14 @@ initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult) return chrec_convert (chrec_type (chrec), op, NULL); } + case BIT_NOT_EXPR: + { + /* Handle ~X as -1 - X. */ + tree op = initialize_matrix_A (A, TREE_OPERAND (chrec, 0), index, mult); + return chrec_fold_op (MINUS_EXPR, chrec_type (chrec), + build_int_cst (TREE_TYPE (chrec), -1), op); + } + case INTEGER_CST: return chrec; @@ -1903,7 +1981,7 @@ initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult) #define FLOOR_DIV(x,y) ((x) / (y)) -/* Solves the special case of the Diophantine equation: +/* 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 @@ -1911,9 +1989,9 @@ initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult) constructed as evolutions in dimension DIM. */ static void -compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b, +compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b, affine_fn *overlaps_a, - affine_fn *overlaps_b, + affine_fn *overlaps_b, tree *last_conflicts, int dim) { if (((step_a > 0 && step_b > 0) @@ -1936,11 +2014,11 @@ compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b, else *last_conflicts = chrec_dont_know; - *overlaps_a = affine_fn_univar (integer_zero_node, dim, + *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, + *overlaps_b = affine_fn_univar (integer_zero_node, dim, + build_int_cst (NULL_TREE, step_overlaps_b)); } @@ -1954,11 +2032,11 @@ compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b, /* 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, + function. For example, | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z - - has the following overlapping functions: + + has the following overlapping functions: | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v @@ -1968,9 +2046,9 @@ compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b, a common benchmark. Implement the general algorithm. */ static void -compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b, +compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b, conflict_function **overlaps_a, - conflict_function **overlaps_b, + conflict_function **overlaps_b, tree *last_conflicts) { bool xz_p, yz_p, xyz_p; @@ -1986,17 +2064,17 @@ 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 = + 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; @@ -2089,10 +2167,10 @@ compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b, parameters, because it uses lambda matrices of integers. */ static void -analyze_subscript_affine_affine (tree chrec_a, +analyze_subscript_affine_affine (tree chrec_a, tree chrec_b, - conflict_function **overlaps_a, - conflict_function **overlaps_b, + conflict_function **overlaps_a, + conflict_function **overlaps_b, tree *last_conflicts) { unsigned nb_vars_a, nb_vars_b, dim; @@ -2110,10 +2188,10 @@ analyze_subscript_affine_affine (tree chrec_a, } 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, @@ -2135,11 +2213,11 @@ analyze_subscript_affine_affine (tree chrec_a, 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, + 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: + Then the first overlap occurs during the first iterations: | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x) */ if (gamma == 0) @@ -2158,8 +2236,8 @@ analyze_subscript_affine_affine (tree chrec_a, 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, + 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); @@ -2223,20 +2301,20 @@ analyze_subscript_affine_affine (tree chrec_a, || (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, + + | x0 = i0 + i1 * t, | y0 = j0 + j1 * t. */ HOST_WIDE_INT i0, j0, i1, j1; @@ -2248,9 +2326,9 @@ analyze_subscript_affine_affine (tree chrec_a, 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 + /* 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 (); @@ -2288,7 +2366,7 @@ analyze_subscript_affine_affine (tree chrec_a, /* If the overlap occurs outside of the bounds of the loop, there is no dependence. */ - if (x1 > niter || y1 > niter) + if (x1 >= niter || y1 >= niter) { *overlaps_a = conflict_fn_no_dependence (); *overlaps_b = conflict_fn_no_dependence (); @@ -2341,7 +2419,7 @@ analyze_subscript_affine_affine (tree chrec_a, *last_conflicts = chrec_dont_know; } -end_analyze_subs_aa: +end_analyze_subs_aa: if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, " (overlaps_a = "); @@ -2357,12 +2435,12 @@ end_analyze_subs_aa: 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. + 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) */ @@ -2388,7 +2466,7 @@ can_use_analyze_subscript_affine_affine (tree *chrec_a, tree *chrec_b) 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), + *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), @@ -2405,36 +2483,36 @@ can_use_analyze_subscript_affine_affine (tree *chrec_a, tree *chrec_b) CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */ static void -analyze_siv_subscript (tree chrec_a, +analyze_siv_subscript (tree chrec_a, tree chrec_b, - conflict_function **overlaps_a, - conflict_function **overlaps_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, + 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, + 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, + analyze_subscript_affine_affine (chrec_a, chrec_b, + overlaps_a, overlaps_b, last_conflicts); if (CF_NOT_KNOWN_P (*overlaps_a) @@ -2446,11 +2524,11 @@ analyze_siv_subscript (tree chrec_a, else dependence_stats.num_siv_dependent++; } - else if (can_use_analyze_subscript_affine_affine (&chrec_a, + else if (can_use_analyze_subscript_affine_affine (&chrec_a, &chrec_b)) { - analyze_subscript_affine_affine (chrec_a, chrec_b, - overlaps_a, overlaps_b, + analyze_subscript_affine_affine (chrec_a, chrec_b, + overlaps_a, overlaps_b, last_conflicts); if (CF_NOT_KNOWN_P (*overlaps_a) @@ -2476,7 +2554,7 @@ analyze_siv_subscript (tree chrec_a, *last_conflicts = chrec_dont_know; dependence_stats.num_siv_unimplemented++; } - + if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, ")\n"); } @@ -2515,17 +2593,17 @@ gcd_of_steps_may_divide_p (const_tree chrec, const_tree cst) 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, +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]). - + 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). @@ -2540,7 +2618,7 @@ analyze_miv_subscript (tree chrec_a, 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 @@ -2551,7 +2629,7 @@ analyze_miv_subscript (tree chrec_a, (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, @@ -2559,8 +2637,8 @@ analyze_miv_subscript (tree chrec_a, && !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 - + {{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 (); @@ -2568,7 +2646,7 @@ analyze_miv_subscript (tree chrec_a, *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) @@ -2577,18 +2655,18 @@ analyze_miv_subscript (tree chrec_a, /* 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}_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) = + + 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, +, 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, + analyze_subscript_affine_affine (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts); if (CF_NOT_KNOWN_P (*overlaps_a) @@ -2600,7 +2678,7 @@ analyze_miv_subscript (tree chrec_a, else dependence_stats.num_miv_dependent++; } - + else { /* When the analysis is too difficult, answer "don't know". */ @@ -2612,7 +2690,7 @@ analyze_miv_subscript (tree chrec_a, *last_conflicts = chrec_dont_know; dependence_stats.num_miv_unimplemented++; } - + if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, ")\n"); } @@ -2621,23 +2699,23 @@ analyze_miv_subscript (tree chrec_a, 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, +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"); @@ -2654,12 +2732,12 @@ analyze_overlapping_iterations (tree 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 + /* 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)) @@ -2672,7 +2750,7 @@ analyze_overlapping_iterations (tree chrec_a, /* If they aren't the same, and aren't affine, we can't do anything yet. */ - else if ((chrec_contains_symbols (chrec_a) + 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))) @@ -2683,20 +2761,20 @@ analyze_overlapping_iterations (tree chrec_a, } else if (ziv_subscript_p (chrec_a, chrec_b)) - analyze_ziv_subscript (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, + analyze_siv_subscript (chrec_a, chrec_b, + overlap_iterations_a, overlap_iterations_b, last_conflicts, lnn); - + else - analyze_miv_subscript (chrec_a, chrec_b, + 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 = "); @@ -2796,7 +2874,7 @@ build_classic_dist_vector_1 (struct data_dependence_relation *ddr, 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 + if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC) { int dist, index; @@ -2821,7 +2899,7 @@ build_classic_dist_vector_1 (struct data_dependence_relation *ddr, non_affine_dependence_relation (ddr); return false; } - + dist = int_cst_value (SUB_DISTANCE (subscript)); /* This is the subscript coupling test. If we have already @@ -3101,7 +3179,7 @@ build_classic_dist_vector (struct data_dependence_relation *ddr, | T[j][i] = t + 2; // B | } - the vectors are: + the vectors are: (0, 1, -1) (1, 1, -1) (1, -1, 1) @@ -3223,9 +3301,9 @@ subscript_dependence_tester_1 (struct data_dependence_relation *ddr, { conflict_function *overlaps_a, *overlaps_b; - analyze_overlapping_iterations (DR_ACCESS_FN (dra, i), + analyze_overlapping_iterations (DR_ACCESS_FN (dra, i), DR_ACCESS_FN (drb, i), - &overlaps_a, &overlaps_b, + &overlaps_a, &overlaps_b, &last_conflicts, loop_nest); if (CF_NOT_KNOWN_P (overlaps_a) @@ -3270,10 +3348,10 @@ 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++; @@ -3288,7 +3366,7 @@ subscript_dependence_tester (struct data_dependence_relation *ddr, /* Returns true when all the access functions of A are affine or constant with respect to LOOP_NEST. */ -static bool +static bool access_functions_are_affine_or_constant_p (const struct data_reference *a, const struct loop *loop_nest) { @@ -3300,7 +3378,7 @@ access_functions_are_affine_or_constant_p (const struct data_reference *a, if (!evolution_function_is_invariant_p (t, loop_nest->num) && !evolution_function_is_affine_multivariate_p (t, loop_nest->num)) return false; - + return true; } @@ -3317,8 +3395,8 @@ access_functions_are_affine_or_constant_p (const struct data_reference *a, 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, +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)) @@ -3340,7 +3418,7 @@ init_omega_eq_with_af (omega_pb pb, unsigned eq, 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] + pb->eqs[eq].coef[var_idx + DDR_NB_LOOPS (ddr) + 1] += int_cst_value (right); switch (TREE_CODE (left)) @@ -3383,7 +3461,7 @@ omega_extract_distance_vectors (omega_pb pb, /* 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) + for (i = 0; i <= DDR_INNER_LOOP (ddr) && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++) { int dist = 0; @@ -3407,7 +3485,7 @@ omega_extract_distance_vectors (omega_pb pb, /* Reduce the constraint system, and test that the current problem is feasible. */ res = omega_simplify_problem (copy); - if (res == omega_false + if (res == omega_false || res == omega_unknown || copy->num_geqs > (int) DDR_NB_LOOPS (ddr)) goto next_problem; @@ -3436,7 +3514,7 @@ omega_extract_distance_vectors (omega_pb pb, copy->eqs[eq].coef[0] = -1; res = omega_simplify_problem (copy); - if (res == omega_false + if (res == omega_false || res == omega_unknown || copy->num_geqs > (int) DDR_NB_LOOPS (ddr)) goto next_problem; @@ -3516,7 +3594,7 @@ omega_setup_subscript (tree access_fun_a, tree access_fun_b, /* GCD test. */ if (DDR_NB_LOOPS (ddr) != 0 && pb->eqs[eq].coef[0] - && !int_divides_p (lambda_vector_gcd + && !int_divides_p (lambda_vector_gcd ((lambda_vector) &(pb->eqs[eq].coef[1]), 2 * DDR_NB_LOOPS (ddr)), pb->eqs[eq].coef[0])) @@ -3565,7 +3643,7 @@ init_omega_for_ddr_1 (struct data_reference *dra, struct data_reference *drb, 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) + 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); @@ -3617,7 +3695,7 @@ init_omega_for_ddr_1 (struct data_reference *dra, struct data_reference *drb, set MAYBE_DEPENDENT to true. Example: for setting up the dependence system corresponding to the - conflicting accesses + conflicting accesses | loop_i | loop_j @@ -3625,7 +3703,7 @@ init_omega_for_ddr_1 (struct data_reference *dra, struct data_reference *drb, | ... A[2*j, 2*(i + j)] | endloop_j | endloop_i - + the following constraints come from the iteration domain: 0 <= i <= Ni @@ -3826,14 +3904,14 @@ ddr_consistent_p (FILE *file, } } - return true; + 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. */ @@ -3844,7 +3922,7 @@ compute_affine_dependence (struct data_dependence_relation *ddr, { 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"); @@ -3907,7 +3985,7 @@ compute_affine_dependence (struct data_dependence_relation *ddr, 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". */ @@ -3927,7 +4005,7 @@ compute_affine_dependence (struct data_dependence_relation *ddr, finalize_ddr_dependent (ddr, chrec_dont_know); } } - + if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, ")\n"); } @@ -3970,7 +4048,7 @@ compute_self_dependence (struct data_dependence_relation *ddr) COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self relations. */ -void +void compute_all_dependences (VEC (data_reference_p, heap) *datarefs, VEC (ddr_p, heap) **dependence_relations, VEC (loop_p, heap) *loop_nest, @@ -3986,7 +4064,8 @@ 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, VEC_index (loop_p, loop_nest, 0)); + if (loop_nest) + compute_affine_dependence (ddr, VEC_index (loop_p, loop_nest, 0)); } if (compute_self_and_rr) @@ -4020,7 +4099,7 @@ get_references_in_stmt (gimple stmt, VEC (data_ref_loc, heap) **references) && gimple_asm_volatile_p (stmt))) clobbers_memory = true; - if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)) + if (!gimple_vuse (stmt)) return clobbers_memory; if (stmt_code == GIMPLE_ASSIGN) @@ -4028,7 +4107,7 @@ get_references_in_stmt (gimple stmt, VEC (data_ref_loc, heap) **references) 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)) @@ -4070,9 +4149,9 @@ get_references_in_stmt (gimple 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 analyzed. */ + loop of the loop nest in which the references should be analyzed. */ -static bool +bool find_data_references_in_stmt (struct loop *nest, gimple stmt, VEC (data_reference_p, heap) **datarefs) { @@ -4092,10 +4171,11 @@ find_data_references_in_stmt (struct loop *nest, gimple stmt, { 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)) + + /* FIXME -- data dependence analysis does not work correctly for objects + with invariant addresses in loop nests. Let us fail here until the + problem is fixed. */ + if (dr_address_invariant_p (dr) && nest) { free_data_ref (dr); if (dump_file && (dump_flags & TDF_DETAILS)) @@ -4110,6 +4190,64 @@ find_data_references_in_stmt (struct loop *nest, gimple stmt, return ret; } +/* 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 which the references should be analyzed. */ + +bool +graphite_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); + 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. */ + +static tree +find_data_references_in_bb (struct loop *loop, basic_block bb, + VEC (data_reference_p, heap) **datarefs) +{ + gimple_stmt_iterator bsi; + + 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); + + return chrec_dont_know; + } + } + + return NULL_TREE; +} + /* 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. @@ -4117,13 +4255,12 @@ find_data_references_in_stmt (struct loop *nest, gimple 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; - gimple_stmt_iterator bsi; bbs = get_loop_body_in_dom_order (loop); @@ -4131,20 +4268,11 @@ find_data_references_in_loop (struct loop *loop, { 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; - } - } + if (find_data_references_in_bb (loop, bb, datarefs) == chrec_dont_know) + { + free (bbs); + return chrec_dont_know; + } } free (bbs); @@ -4195,13 +4323,13 @@ find_loop_nest (struct loop *loop, VEC (loop_p, heap) **loop_nest) /* 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 + 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, +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) @@ -4211,7 +4339,7 @@ compute_data_dependences_for_loop (struct loop *loop, memset (&dependence_stats, 0, sizeof (dependence_stats)); - /* If the loop nest is not well formed, or one of the data references + /* 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 @@ -4234,20 +4362,20 @@ compute_data_dependences_for_loop (struct loop *loop, { fprintf (dump_file, "Dependence tester statistics:\n"); - fprintf (dump_file, "Number of dependence tests: %d\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", + 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", + 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", + fprintf (dump_file, "Number of undetermined dependence tests: %d\n", dependence_stats.num_dependence_undetermined); - fprintf (dump_file, "Number of subscript tests: %d\n", + fprintf (dump_file, "Number of subscript tests: %d\n", dependence_stats.num_subscript_tests); - fprintf (dump_file, "Number of undetermined subscript tests: %d\n", + 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", + 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", @@ -4257,9 +4385,9 @@ compute_data_dependences_for_loop (struct loop *loop, 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); + dependence_stats.num_ziv_unimplemented); - fprintf (dump_file, "Number of siv tests: %d\n", + 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); @@ -4268,7 +4396,7 @@ compute_data_dependences_for_loop (struct loop *loop, fprintf (dump_file, "Number of siv tests unimplemented: %d\n", dependence_stats.num_siv_unimplemented); - fprintf (dump_file, "Number of miv tests: %d\n", + 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); @@ -4281,35 +4409,55 @@ compute_data_dependences_for_loop (struct loop *loop, return res; } +/* Returns true when the data dependences for the basic block BB have been + computed, false otherwise. + DATAREFS is initialized to all the array elements contained in this basic + block, 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_bb (basic_block bb, + bool compute_self_and_read_read_dependences, + VEC (data_reference_p, heap) **datarefs, + VEC (ddr_p, heap) **dependence_relations) +{ + if (find_data_references_in_bb (NULL, bb, datarefs) == chrec_dont_know) + return false; + + compute_all_dependences (*datarefs, dependence_relations, NULL, + compute_self_and_read_read_dependences); + return true; +} + /* Entry point (for testing only). Analyze all the data references and the dependence relations in LOOP. - The data references are computed first. - + 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 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 +static void analyze_all_data_dependences (struct loop *loop) { unsigned int i; int nb_data_refs = 10; - VEC (data_reference_p, heap) *datarefs = + VEC (data_reference_p, heap) *datarefs = VEC_alloc (data_reference_p, heap, nb_data_refs); - VEC (ddr_p, heap) *dependence_relations = + VEC (ddr_p, heap) *dependence_relations = VEC_alloc (ddr_p, heap, nb_data_refs * nb_data_refs); /* Compute DDs on the whole function. */ @@ -4328,7 +4476,6 @@ analyze_all_data_dependences (struct loop *loop) { 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; @@ -4336,22 +4483,14 @@ analyze_all_data_dependences (struct loop *loop) { 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); + nb_bot_relations++; - if (!bitmap_intersect_p (DR_VOPS (a), DR_VOPS (b))) - nb_basename_differ++; - else - nb_bot_relations++; - } - - else + else nb_chrec_relations++; } - + gather_stats_on_scev_database (); } } @@ -4394,7 +4533,7 @@ free_dependence_relation (struct data_dependence_relation *ddr) /* Free the memory used by the data dependence relations from DEPENDENCE_RELATIONS. */ -void +void free_dependence_relations (VEC (ddr_p, heap) *dependence_relations) { unsigned int i; @@ -4441,7 +4580,7 @@ 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, + fprintf (file, "(vertex %d: (%s%s) (in:", i, RDG_MEM_WRITE_STMT (rdg, i) ? "w" : "", RDG_MEM_READS_STMT (rdg, i) ? "r" : ""); @@ -4523,74 +4662,10 @@ 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(()) +struct GTY(()) rdg_vertex_info { gimple stmt; int index; @@ -4645,6 +4720,7 @@ create_rdg_edge_for_ddr (struct graph *rdg, ddr_p ddr) 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)) @@ -4665,7 +4741,7 @@ 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; @@ -4677,6 +4753,7 @@ create_rdg_edges_for_scalar (struct graph *rdg, tree def, int idef) e = add_edge (rdg, idef, use); e->data = XNEW (struct rdg_edge); RDGE_TYPE (e) = flow_dd; + RDGE_RELATION (e) = NULL; } } @@ -4702,7 +4779,7 @@ create_rdg_edges (struct graph *rdg, VEC (ddr_p, heap) *ddrs) /* Build the vertices of the reduced dependence graph RDG. */ -static void +void create_rdg_vertices (struct graph *rdg, VEC (gimple, heap) *stmts) { int i, j; @@ -4787,7 +4864,7 @@ known_dependences_p (VEC (ddr_p, heap) *dependence_relations) for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++) if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know) return false; - + return true; } @@ -4827,6 +4904,21 @@ hash_stmt_vertex_del (void *e) 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; @@ -4834,30 +4926,32 @@ build_rdg (struct loop *loop) 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, + compute_data_dependences_for_loop (loop, false, &datarefs, &dependence_relations); if (!known_dependences_p (dependence_relations)) - goto end_rdg; + { + free_dependence_relations (dependence_relations); + free_data_refs (datarefs); + VEC_free (gimple, heap, stmts); + + return rdg; + } stmts_from_loop (loop, &stmts); - rdg = new_graph (VEC_length (gimple, 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); - end_rdg: - free_dependence_relations (dependence_relations); - free_data_refs (datarefs); VEC_free (gimple, heap, stmts); - return rdg; } @@ -4890,7 +4984,7 @@ stores_from_loop (struct loop *loop, VEC (gimple, heap) **stmts) 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)) + if (gimple_vdef (gsi_stmt (bsi))) VEC_safe_push (gimple, heap, *stmts, gsi_stmt (bsi)); } @@ -5058,8 +5152,8 @@ remove_similar_memory_refs (VEC (gimple, heap) **stmts) /* 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, +int +access_matrix_get_index_for_parameter (tree parameter, struct access_matrix *access_matrix) { int i;