X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Ftree-data-ref.c;h=89d123d65e9742bc91d9dc8a5bdf59b953711a9e;hb=17b9476e1ecf66ab2cab1e4174c1a610a8e4a6c2;hp=5aecbff7fcb8271651c4320792226a8e842920e2;hpb=221a697ef63c250228039a936197faa57569d586;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c index 5aecbff7fcb..89d123d65e9 100644 --- a/gcc/tree-data-ref.c +++ b/gcc/tree-data-ref.c @@ -1,5 +1,5 @@ /* Data references and dependences detectors. - Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 + Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011 Free Software Foundation, Inc. Contributed by Sebastian Pop @@ -84,6 +84,7 @@ along with GCC; see the file COPYING3. If not see #include "tree-scalar-evolution.h" #include "tree-pass.h" #include "langhooks.h" +#include "tree-affine.h" static struct datadep_stats { @@ -123,7 +124,7 @@ tree_fold_divides_p (const_tree a, const_tree b) { gcc_assert (TREE_CODE (a) == INTEGER_CST); gcc_assert (TREE_CODE (b) == INTEGER_CST); - return integer_zerop (int_const_binop (TRUNC_MOD_EXPR, b, a, 0)); + return integer_zerop (int_const_binop (TRUNC_MOD_EXPR, b, a)); } /* Returns true iff A divides B. */ @@ -340,6 +341,18 @@ print_dir_vectors (FILE *outf, VEC (lambda_vector, heap) *dir_vects, print_direction_vector (outf, v, length); } +/* Print out a vector VEC of length N to OUTFILE. */ + +static inline void +print_lambda_vector (FILE * outfile, lambda_vector vector, int n) +{ + int i; + + for (i = 0; i < n; i++) + fprintf (outfile, "%3d ", vector[i]); + fprintf (outfile, "\n"); +} + /* Print a vector of distance vectors. */ void @@ -576,9 +589,6 @@ split_constant_offset_1 (tree type, tree op0, enum tree_code code, tree op1, int punsignedp, pvolatilep; op0 = TREE_OPERAND (op0, 0); - if (!handled_component_p (op0)) - return false; - base = get_inner_reference (op0, &pbitsize, &pbitpos, &poffset, &pmode, &punsignedp, &pvolatilep, false); @@ -592,8 +602,7 @@ split_constant_offset_1 (tree type, tree op0, enum tree_code code, tree op1, split_constant_offset (poffset, &poffset, &off1); off0 = size_binop (PLUS_EXPR, off0, off1); if (POINTER_TYPE_P (TREE_TYPE (base))) - base = fold_build2 (POINTER_PLUS_EXPR, TREE_TYPE (base), - base, fold_convert (sizetype, poffset)); + base = fold_build_pointer_plus (base, poffset); else base = fold_build2 (PLUS_EXPR, TREE_TYPE (base), base, fold_convert (TREE_TYPE (base), poffset)); @@ -674,7 +683,8 @@ split_constant_offset (tree exp, tree *var, tree *off) *off = ssize_int (0); STRIP_NOPS (exp); - if (automatically_generated_chrec_p (exp)) + if (tree_is_chrec (exp) + || get_gimple_rhs_class (TREE_CODE (exp)) == GIMPLE_TERNARY_RHS) return; otype = TREE_TYPE (exp); @@ -709,11 +719,11 @@ canonicalize_base_object_address (tree addr) } /* 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 + basic block that contains it. Returns true if analysis succeed or false otherwise. */ bool -dr_analyze_innermost (struct data_reference *dr) +dr_analyze_innermost (struct data_reference *dr, struct loop *nest) { gimple stmt = DR_STMT (dr); struct loop *loop = loop_containing_stmt (stmt); @@ -756,14 +766,25 @@ dr_analyze_innermost (struct data_reference *dr) } else base = build_fold_addr_expr (base); + if (in_loop) { 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; + if (nest) + { + 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; + } } } else @@ -788,10 +809,18 @@ dr_analyze_innermost (struct data_reference *dr) 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; + if (nest) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "failed: evolution of offset is not" + " affine.\n"); + return false; + } + else + { + offset_iv.base = poffset; + offset_iv.step = ssize_int (0); + } } } @@ -826,66 +855,93 @@ static void dr_analyze_indices (struct data_reference *dr, loop_p nest, loop_p loop) { VEC (tree, heap) *access_fns = NULL; - tree ref = unshare_expr (DR_REF (dr)), aref = ref, op; - tree base, off, access_fn = NULL_TREE; - basic_block before_loop = NULL; + tree ref, *aref, op; + tree base, off, access_fn; + basic_block before_loop; + + /* If analyzing a basic-block there are no indices to analyze + and thus no access functions. */ + if (!nest) + { + DR_BASE_OBJECT (dr) = DR_REF (dr); + DR_ACCESS_FNS (dr) = NULL; + return; + } - if (nest) - before_loop = block_before_loop (nest); + ref = unshare_expr (DR_REF (dr)); + before_loop = block_before_loop (nest); + + /* REALPART_EXPR and IMAGPART_EXPR can be handled like accesses + into a two element array with a constant index. The base is + then just the immediate underlying object. */ + if (TREE_CODE (ref) == REALPART_EXPR) + { + ref = TREE_OPERAND (ref, 0); + VEC_safe_push (tree, heap, access_fns, integer_zero_node); + } + else if (TREE_CODE (ref) == IMAGPART_EXPR) + { + ref = TREE_OPERAND (ref, 0); + VEC_safe_push (tree, heap, access_fns, integer_one_node); + } - while (handled_component_p (aref)) + /* Analyze access functions of dimensions we know to be independent. */ + aref = &ref; + while (handled_component_p (*aref)) { - if (TREE_CODE (aref) == ARRAY_REF) + if (TREE_CODE (*aref) == ARRAY_REF) { - op = TREE_OPERAND (aref, 1); - if (nest) + op = TREE_OPERAND (*aref, 1); + 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); + /* For ARRAY_REFs the base is the reference with the index replaced + by zero if we can not strip it as the outermost component. */ + if (*aref == ref) { - 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); + *aref = TREE_OPERAND (*aref, 0); + continue; } - - TREE_OPERAND (aref, 1) = build_int_cst (TREE_TYPE (op), 0); + else + TREE_OPERAND (*aref, 1) = build_int_cst (TREE_TYPE (op), 0); } - aref = TREE_OPERAND (aref, 0); + aref = &TREE_OPERAND (*aref, 0); } - if (nest - && (INDIRECT_REF_P (aref) - || TREE_CODE (aref) == MEM_REF)) + /* If the address operand of a MEM_REF base has an evolution in the + analyzed nest, add it as an additional independent access-function. */ + if (TREE_CODE (*aref) == MEM_REF) { - op = TREE_OPERAND (aref, 0); + op = TREE_OPERAND (*aref, 0); access_fn = analyze_scalar_evolution (loop, op); access_fn = instantiate_scev (before_loop, loop, access_fn); - base = initial_condition (access_fn); - split_constant_offset (base, &base, &off); - if (TREE_CODE (aref) == MEM_REF) - off = size_binop (PLUS_EXPR, off, - fold_convert (ssizetype, TREE_OPERAND (aref, 1))); - access_fn = chrec_replace_initial_condition (access_fn, - fold_convert (TREE_TYPE (base), off)); - - TREE_OPERAND (aref, 0) = base; - VEC_safe_push (tree, heap, access_fns, access_fn); + if (TREE_CODE (access_fn) == POLYNOMIAL_CHREC) + { + tree orig_type; + base = initial_condition (access_fn); + orig_type = TREE_TYPE (base); + STRIP_USELESS_TYPE_CONVERSION (base); + split_constant_offset (base, &base, &off); + /* Fold the MEM_REF offset into the evolutions initial + value to make more bases comparable. */ + if (!integer_zerop (TREE_OPERAND (*aref, 1))) + { + off = size_binop (PLUS_EXPR, off, + fold_convert (ssizetype, + TREE_OPERAND (*aref, 1))); + TREE_OPERAND (*aref, 1) + = build_int_cst (TREE_TYPE (TREE_OPERAND (*aref, 1)), 0); + } + access_fn = chrec_replace_initial_condition + (access_fn, fold_convert (orig_type, off)); + *aref = fold_build2_loc (EXPR_LOCATION (*aref), + MEM_REF, TREE_TYPE (*aref), + base, TREE_OPERAND (*aref, 1)); + VEC_safe_push (tree, heap, access_fns, access_fn); + } } - if (TREE_CODE (aref) == MEM_REF) - TREE_OPERAND (aref, 1) - = build_int_cst (TREE_TYPE (TREE_OPERAND (aref, 1)), 0); - - if (TREE_CODE (ref) == MEM_REF - && TREE_CODE (TREE_OPERAND (ref, 0)) == ADDR_EXPR - && integer_zerop (TREE_OPERAND (ref, 1))) - ref = TREE_OPERAND (TREE_OPERAND (ref, 0), 0); - - /* For canonicalization purposes we'd like to strip all outermost - zero-offset component-refs. - ??? For now simply handle zero-index array-refs. */ - while (TREE_CODE (ref) == ARRAY_REF - && integer_zerop (TREE_OPERAND (ref, 1))) - ref = TREE_OPERAND (ref, 0); - DR_BASE_OBJECT (dr) = ref; DR_ACCESS_FNS (dr) = access_fns; } @@ -907,21 +963,6 @@ dr_analyze_alias (struct data_reference *dr) } } -/* Returns true if the address of DR is invariant. */ - -static bool -dr_address_invariant_p (struct data_reference *dr) -{ - unsigned i; - tree idx; - - FOR_EACH_VEC_ELT (tree, DR_ACCESS_FNS (dr), i, idx) - if (tree_contains_chrecs (idx, NULL)) - return false; - - return true; -} - /* Frees data reference DR. */ void @@ -955,12 +996,13 @@ create_data_ref (loop_p nest, loop_p loop, tree memref, gimple stmt, DR_REF (dr) = memref; DR_IS_READ (dr) = is_read; - dr_analyze_innermost (dr); + dr_analyze_innermost (dr, nest); dr_analyze_indices (dr, nest, loop); dr_analyze_alias (dr); if (dump_file && (dump_flags & TDF_DETAILS)) { + unsigned i; fprintf (dump_file, "\tbase_address: "); print_generic_expr (dump_file, DR_BASE_ADDRESS (dr), TDF_SLIM); fprintf (dump_file, "\n\toffset from base address: "); @@ -974,11 +1016,58 @@ create_data_ref (loop_p nest, loop_p loop, tree memref, gimple stmt, fprintf (dump_file, "\n\tbase_object: "); print_generic_expr (dump_file, DR_BASE_OBJECT (dr), TDF_SLIM); fprintf (dump_file, "\n"); + for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++) + { + fprintf (dump_file, "\tAccess function %d: ", i); + print_generic_stmt (dump_file, DR_ACCESS_FN (dr, i), TDF_SLIM); + } } return dr; } +/* Check if OFFSET1 and OFFSET2 (DR_OFFSETs of some data-refs) are identical + expressions. */ +static bool +dr_equal_offsets_p1 (tree offset1, tree offset2) +{ + bool res; + + STRIP_NOPS (offset1); + STRIP_NOPS (offset2); + + if (offset1 == offset2) + return true; + + if (TREE_CODE (offset1) != TREE_CODE (offset2) + || (!BINARY_CLASS_P (offset1) && !UNARY_CLASS_P (offset1))) + return false; + + res = dr_equal_offsets_p1 (TREE_OPERAND (offset1, 0), + TREE_OPERAND (offset2, 0)); + + if (!res || !BINARY_CLASS_P (offset1)) + return res; + + res = dr_equal_offsets_p1 (TREE_OPERAND (offset1, 1), + TREE_OPERAND (offset2, 1)); + + return res; +} + +/* Check if DRA and DRB have equal offsets. */ +bool +dr_equal_offsets_p (struct data_reference *dra, + struct data_reference *drb) +{ + tree offset1, offset2; + + offset1 = DR_OFFSET (dra); + offset2 = DR_OFFSET (drb); + + return dr_equal_offsets_p1 (offset1, offset2); +} + /* Returns true if FNA == FNB. */ static bool @@ -1228,14 +1317,33 @@ object_address_invariant_in_loop_p (const struct loop *loop, const_tree obj) } /* Returns false if we can prove that data references A and B do not alias, - true otherwise. */ + true otherwise. If LOOP_NEST is false no cross-iteration aliases are + considered. */ bool -dr_may_alias_p (const struct data_reference *a, const struct data_reference *b) +dr_may_alias_p (const struct data_reference *a, const struct data_reference *b, + bool loop_nest) { tree addr_a = DR_BASE_OBJECT (a); tree addr_b = DR_BASE_OBJECT (b); + /* If we are not processing a loop nest but scalar code we + do not need to care about possible cross-iteration dependences + and thus can process the full original reference. Do so, + similar to how loop invariant motion applies extra offset-based + disambiguation. */ + if (!loop_nest) + { + aff_tree off1, off2; + double_int size1, size2; + get_inner_reference_aff (DR_REF (a), &off1, &size1); + get_inner_reference_aff (DR_REF (b), &off2, &size2); + aff_combination_scale (&off1, double_int_minus_one); + aff_combination_add (&off2, &off1); + if (aff_comb_cannot_overlap_p (&off2, size1, size2)) + return false; + } + if (DR_IS_WRITE (a) && DR_IS_WRITE (b)) return refs_output_dependent_p (addr_a, addr_b); else if (DR_IS_READ (a) && DR_IS_WRITE (b)) @@ -1243,13 +1351,11 @@ dr_may_alias_p (const struct data_reference *a, const struct data_reference *b) return refs_may_alias_p (addr_a, addr_b); } -static void compute_self_dependence (struct data_dependence_relation *); - /* Initialize a data dependence relation between data accesses A and B. NB_LOOPS is the number of loops surrounding the references: the size of the classic distance/direction vectors. */ -static struct data_dependence_relation * +struct data_dependence_relation * initialize_data_dependence_relation (struct data_reference *a, struct data_reference *b, VEC (loop_p, heap) *loop_nest) @@ -1273,7 +1379,7 @@ initialize_data_dependence_relation (struct data_reference *a, } /* If the data references do not alias, then they are independent. */ - if (!dr_may_alias_p (a, b)) + if (!dr_may_alias_p (a, b, loop_nest != NULL)) { DDR_ARE_DEPENDENT (res) = chrec_known; return res; @@ -1567,73 +1673,23 @@ analyze_ziv_subscript (tree chrec_a, fprintf (dump_file, ")\n"); } -/* Sets NIT to the estimated number of executions of the statements in - LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as - large as the number of iterations. If we have no reliable estimate, - the function returns false, otherwise returns true. */ - -bool -estimated_loop_iterations (struct loop *loop, bool conservative, - double_int *nit) -{ - estimate_numbers_of_iterations_loop (loop, true); - if (conservative) - { - if (!loop->any_upper_bound) - return false; - - *nit = loop->nb_iterations_upper_bound; - } - else - { - if (!loop->any_estimate) - return false; - - *nit = loop->nb_iterations_estimate; - } - - return true; -} - -/* Similar to estimated_loop_iterations, but returns the estimate only - if it fits to HOST_WIDE_INT. If this is not the case, or the estimate - on the number of iterations of LOOP could not be derived, returns -1. */ - -HOST_WIDE_INT -estimated_loop_iterations_int (struct loop *loop, bool conservative) -{ - double_int nit; - HOST_WIDE_INT hwi_nit; - - if (!estimated_loop_iterations (loop, conservative, &nit)) - return -1; - - if (!double_int_fits_in_shwi_p (nit)) - return -1; - hwi_nit = double_int_to_shwi (nit); - - return hwi_nit < 0 ? -1 : hwi_nit; -} - -/* Similar to estimated_loop_iterations, but returns the estimate as a tree, +/* Similar to max_stmt_executions_int, but returns the bound 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 + bound on the number of iterations of LOOP could not be derived, returns chrec_dont_know. */ static tree -estimated_loop_iterations_tree (struct loop *loop, bool conservative) +max_stmt_executions_tree (struct loop *loop) { double_int nit; - tree type; - if (!estimated_loop_iterations (loop, conservative, &nit)) + if (!max_stmt_executions (loop, true, &nit)) return chrec_dont_know; - type = lang_hooks.types.type_for_size (INT_TYPE_SIZE, true); - if (!double_int_fits_to_tree_p (type, nit)) + if (!double_int_fits_to_tree_p (unsigned_type_node, nit)) return chrec_dont_know; - return double_int_to_tree (type, nit); + return double_int_to_tree (unsigned_type_node, nit); } /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a @@ -1709,7 +1765,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, false); + numiter = max_stmt_executions_int (loop, true); if (numiter >= 0 && compare_tree_int (tmp, numiter) > 0) @@ -1787,7 +1843,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, false); + numiter = max_stmt_executions_int (loop, true); if (numiter >= 0 && compare_tree_int (tmp, numiter) > 0) @@ -1968,10 +2024,9 @@ compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b, step_z = int_cst_value (CHREC_RIGHT (chrec_b)); niter_x = - estimated_loop_iterations_int (get_chrec_loop (CHREC_LEFT (chrec_a)), - false); - niter_y = estimated_loop_iterations_int (get_chrec_loop (chrec_a), false); - niter_z = estimated_loop_iterations_int (get_chrec_loop (chrec_b), false); + max_stmt_executions_int (get_chrec_loop (CHREC_LEFT (chrec_a)), true); + niter_y = max_stmt_executions_int (get_chrec_loop (chrec_a), true); + niter_z = max_stmt_executions_int (get_chrec_loop (chrec_b), true); if (niter_x < 0 || niter_y < 0 || niter_z < 0) { @@ -2064,6 +2119,168 @@ compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b, affine_fn_free (overlaps_b_xyz); } +/* Copy the elements of vector VEC1 with length SIZE to VEC2. */ + +static void +lambda_vector_copy (lambda_vector vec1, lambda_vector vec2, + int size) +{ + memcpy (vec2, vec1, size * sizeof (*vec1)); +} + +/* Copy the elements of M x N matrix MAT1 to MAT2. */ + +static void +lambda_matrix_copy (lambda_matrix mat1, lambda_matrix mat2, + int m, int n) +{ + int i; + + for (i = 0; i < m; i++) + lambda_vector_copy (mat1[i], mat2[i], n); +} + +/* Store the N x N identity matrix in MAT. */ + +static void +lambda_matrix_id (lambda_matrix mat, int size) +{ + int i, j; + + for (i = 0; i < size; i++) + for (j = 0; j < size; j++) + mat[i][j] = (i == j) ? 1 : 0; +} + +/* Return the first nonzero element of vector VEC1 between START and N. + We must have START <= N. Returns N if VEC1 is the zero vector. */ + +static int +lambda_vector_first_nz (lambda_vector vec1, int n, int start) +{ + int j = start; + while (j < n && vec1[j] == 0) + j++; + return j; +} + +/* Add a multiple of row R1 of matrix MAT with N columns to row R2: + R2 = R2 + CONST1 * R1. */ + +static void +lambda_matrix_row_add (lambda_matrix mat, int n, int r1, int r2, int const1) +{ + int i; + + if (const1 == 0) + return; + + for (i = 0; i < n; i++) + mat[r2][i] += const1 * mat[r1][i]; +} + +/* Swap rows R1 and R2 in matrix MAT. */ + +static void +lambda_matrix_row_exchange (lambda_matrix mat, int r1, int r2) +{ + lambda_vector row; + + row = mat[r1]; + mat[r1] = mat[r2]; + mat[r2] = row; +} + +/* Multiply vector VEC1 of length SIZE by a constant CONST1, + and store the result in VEC2. */ + +static void +lambda_vector_mult_const (lambda_vector vec1, lambda_vector vec2, + int size, int const1) +{ + int i; + + if (const1 == 0) + lambda_vector_clear (vec2, size); + else + for (i = 0; i < size; i++) + vec2[i] = const1 * vec1[i]; +} + +/* Negate vector VEC1 with length SIZE and store it in VEC2. */ + +static void +lambda_vector_negate (lambda_vector vec1, lambda_vector vec2, + int size) +{ + lambda_vector_mult_const (vec1, vec2, size, -1); +} + +/* Negate row R1 of matrix MAT which has N columns. */ + +static void +lambda_matrix_row_negate (lambda_matrix mat, int n, int r1) +{ + lambda_vector_negate (mat[r1], mat[r1], n); +} + +/* Return true if two vectors are equal. */ + +static bool +lambda_vector_equal (lambda_vector vec1, lambda_vector vec2, int size) +{ + int i; + for (i = 0; i < size; i++) + if (vec1[i] != vec2[i]) + return false; + return true; +} + +/* Given an M x N integer matrix A, this function determines an M x + M unimodular matrix U, and an M x N echelon matrix S such that + "U.A = S". This decomposition is also known as "right Hermite". + + Ref: Algorithm 2.1 page 33 in "Loop Transformations for + Restructuring Compilers" Utpal Banerjee. */ + +static void +lambda_matrix_right_hermite (lambda_matrix A, int m, int n, + lambda_matrix S, lambda_matrix U) +{ + int i, j, i0 = 0; + + lambda_matrix_copy (A, S, m, n); + lambda_matrix_id (U, m); + + for (j = 0; j < n; j++) + { + if (lambda_vector_first_nz (S[j], m, i0) < m) + { + ++i0; + for (i = m - 1; i >= i0; i--) + { + while (S[i][j] != 0) + { + int sigma, factor, a, b; + + a = S[i-1][j]; + b = S[i][j]; + sigma = (a * b < 0) ? -1: 1; + a = abs (a); + b = abs (b); + factor = sigma * (a / b); + + lambda_matrix_row_add (S, n, i, i-1, -factor); + lambda_matrix_row_exchange (S, i, i-1); + + lambda_matrix_row_add (U, m, i, i-1, -factor); + lambda_matrix_row_exchange (U, i, i-1); + } + } + } + } +} + /* Determines the overlapping elements due to accesses CHREC_A and CHREC_B, that are affine functions. This function cannot handle symbolic evolution functions, ie. when initial conditions are @@ -2134,10 +2351,8 @@ analyze_subscript_affine_affine (tree chrec_a, HOST_WIDE_INT niter, niter_a, niter_b; affine_fn ova, ovb; - niter_a = estimated_loop_iterations_int (get_chrec_loop (chrec_a), - false); - niter_b = estimated_loop_iterations_int (get_chrec_loop (chrec_b), - false); + niter_a = max_stmt_executions_int (get_chrec_loop (chrec_a), true); + niter_b = max_stmt_executions_int (get_chrec_loop (chrec_b), true); niter = MIN (niter_a, niter_b); step_a = int_cst_value (CHREC_RIGHT (chrec_a)); step_b = int_cst_value (CHREC_RIGHT (chrec_b)); @@ -2244,10 +2459,10 @@ analyze_subscript_affine_affine (tree chrec_a, if (i1 > 0 && j1 > 0) { - HOST_WIDE_INT niter_a = estimated_loop_iterations_int - (get_chrec_loop (chrec_a), false); - HOST_WIDE_INT niter_b = estimated_loop_iterations_int - (get_chrec_loop (chrec_b), false); + HOST_WIDE_INT niter_a = max_stmt_executions_int + (get_chrec_loop (chrec_a), true); + HOST_WIDE_INT niter_b = max_stmt_executions_int + (get_chrec_loop (chrec_b), true); HOST_WIDE_INT niter = MIN (niter_a, niter_b); /* (X0, Y0) is a solution of the Diophantine equation: @@ -2507,14 +2722,6 @@ analyze_miv_subscript (tree chrec_a, tree *last_conflicts, struct loop *loop_nest) { - /* FIXME: This is a MIV subscript, not yet handled. - Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from - (A[i] vs. A[j]). - - In the SIV test we had to solve a Diophantine equation with two - variables. In the MIV case we have to solve a Diophantine - equation with 2*n variables (if the subscript uses n IVs). - */ tree type, difference; dependence_stats.num_miv++; @@ -2532,8 +2739,7 @@ analyze_miv_subscript (tree chrec_a, in the same order. */ *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node)); *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node)); - *last_conflicts = estimated_loop_iterations_tree - (get_chrec_loop (chrec_a), true); + *last_conflicts = max_stmt_executions_tree (get_chrec_loop (chrec_a)); dependence_stats.num_miv_dependent++; } @@ -2786,29 +2992,19 @@ build_classic_dist_vector_1 (struct data_dependence_relation *ddr, && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC) { int dist, index; - int index_a = index_in_loop_nest (CHREC_VARIABLE (access_fn_a), - DDR_LOOP_NEST (ddr)); - int index_b = index_in_loop_nest (CHREC_VARIABLE (access_fn_b), - DDR_LOOP_NEST (ddr)); - - /* The dependence is carried by the outermost loop. Example: - | loop_1 - | A[{4, +, 1}_1] - | loop_2 - | A[{5, +, 1}_2] - | endloop_2 - | endloop_1 - In this case, the dependence is carried by loop_1. */ - index = index_a < index_b ? index_a : index_b; - *index_carry = MIN (index, *index_carry); + int var_a = CHREC_VARIABLE (access_fn_a); + int var_b = CHREC_VARIABLE (access_fn_b); - if (chrec_contains_undetermined (SUB_DISTANCE (subscript))) + if (var_a != var_b + || chrec_contains_undetermined (SUB_DISTANCE (subscript))) { non_affine_dependence_relation (ddr); return false; } dist = int_cst_value (SUB_DISTANCE (subscript)); + index = index_in_loop_nest (var_a, DDR_LOOP_NEST (ddr)); + *index_carry = MIN (index, *index_carry); /* This is the subscript coupling test. If we have already recorded a distance for this loop (a distance coming from @@ -3556,7 +3752,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, false); + HOST_WIDE_INT nbi = max_stmt_executions_int (loopi, true); /* 0 <= loop_x */ ineq = omega_add_zero_geq (pb, omega_black); @@ -3923,7 +4119,7 @@ compute_affine_dependence (struct data_dependence_relation *ddr, /* This computes the dependence relation for the same data reference into DDR. */ -static void +void compute_self_dependence (struct data_dependence_relation *ddr) { unsigned int i; @@ -4027,33 +4223,37 @@ get_references_in_stmt (gimple stmt, VEC (data_ref_loc, heap) **references) ref->pos = op1; ref->is_read = true; } - - if (DECL_P (*op0) - || (REFERENCE_CLASS_P (*op0) && get_base_address (*op0))) - { - ref = VEC_safe_push (data_ref_loc, heap, *references, NULL); - ref->pos = op0; - ref->is_read = false; - } } else if (stmt_code == GIMPLE_CALL) { - unsigned i, n = gimple_call_num_args (stmt); + unsigned i, n; + op0 = gimple_call_lhs_ptr (stmt); + n = gimple_call_num_args (stmt); for (i = 0; i < n; i++) { - op0 = gimple_call_arg_ptr (stmt, i); + op1 = gimple_call_arg_ptr (stmt, i); - if (DECL_P (*op0) - || (REFERENCE_CLASS_P (*op0) && get_base_address (*op0))) + if (DECL_P (*op1) + || (REFERENCE_CLASS_P (*op1) && get_base_address (*op1))) { ref = VEC_safe_push (data_ref_loc, heap, *references, NULL); - ref->pos = op0; + ref->pos = op1; ref->is_read = true; } } } + else + return clobbers_memory; + if (*op0 + && (DECL_P (*op0) + || (REFERENCE_CLASS_P (*op0) && get_base_address (*op0)))) + { + ref = VEC_safe_push (data_ref_loc, heap, *references, NULL); + ref->pos = op0; + ref->is_read = false; + } return clobbers_memory; } @@ -4082,19 +4282,6 @@ find_data_references_in_stmt (struct loop *nest, gimple stmt, dr = create_data_ref (nest, loop_containing_stmt (stmt), *ref->pos, stmt, ref->is_read); gcc_assert (dr != NULL); - - /* 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)) - fprintf (dump_file, "\tFAILED as dr address is invariant\n"); - ret = false; - break; - } - VEC_safe_push (data_reference_p, heap, *datarefs, dr); } VEC_free (data_ref_loc, heap, references); @@ -4138,7 +4325,7 @@ graphite_find_data_references_in_stmt (loop_p nest, loop_p loop, gimple stmt, DATAREFS. Returns chrec_dont_know when failing to analyze a difficult case, returns NULL_TREE otherwise. */ -static tree +tree find_data_references_in_bb (struct loop *loop, basic_block bb, VEC (data_reference_p, heap) **datarefs) { @@ -4819,7 +5006,7 @@ stmts_from_loop (struct loop *loop, VEC (gimple, heap) **stmts) for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) { stmt = gsi_stmt (bsi); - if (gimple_code (stmt) != GIMPLE_LABEL) + if (gimple_code (stmt) != GIMPLE_LABEL && !is_gimple_debug (stmt)) VEC_safe_push (gimple, heap, *stmts, stmt); } } @@ -4929,11 +5116,9 @@ free_rdg (struct graph *rdg) struct graph_edge *e; for (e = v->succ; e; e = e->succ_next) - if (e->data) - free (e->data); + free (e->data); - if (v->data) - free (v->data); + free (v->data); } htab_delete (rdg->indices); @@ -4987,7 +5172,7 @@ stmt_with_adjacent_zero_store_dr_p (gimple stmt) DR_STMT (dr) = stmt; DR_REF (dr) = op0; - res = dr_analyze_innermost (dr) + res = dr_analyze_innermost (dr, loop_containing_stmt (stmt)) && stride_of_unit_type_p (DR_STEP (dr), TREE_TYPE (op0)); free_data_ref (dr); @@ -5027,7 +5212,7 @@ ref_base_address (gimple stmt, data_ref_loc *ref) DR_STMT (dr) = stmt; DR_REF (dr) = *ref->pos; - dr_analyze_innermost (dr); + dr_analyze_innermost (dr, loop_containing_stmt (stmt)); base_address = DR_BASE_ADDRESS (dr); if (!base_address)