This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH]: Fix some simple dependence cases
- From: Daniel Berlin <dberlin at dberlin dot org>
- To: GCC Patches <gcc-patches at gcc dot gnu dot org>, Richard Henderson <rth at redhat dot com>
- Date: Sun, 18 Sep 2005 19:10:57 -0400
- Subject: [PATCH]: Fix some simple dependence cases
This adds the tests we had on autovect, which include the simple "do
they always overlap" test, which was biting RTH's case.
I included the cleanup i had done to the get_number_of_iterations
related code.
I had originally planned on adding this code in 4.2, but i'm happy to
add it now if it's actually blocking vectorization cases.
It's been pretty well tested on autovect.
I'll commit it monday afternoon if nobody says otherwise.
--Dan
2005-09-18 Daniel Berlin <dberlin@dberlin.org>
* tree-data-ref.c (get_number_of_iters_for_loop): New function.
(analyze_siv_subscript_cst_affine): Add weak SIV test.
(compute_overlap_steps_for_affine_1_2): Use
get_number_of_iters_for_loop.
(analyze_subscript_affine_affine): Check whether difference is
zero first.
Use get_number_of_iters_for_loop.
Check whether overlap occurs outside of bounds.
(analyze_miv_subscript): Use get_number_of_iters_for_loop.
Index: tree-data-ref.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-data-ref.c,v
retrieving revision 2.42
diff -u -p -r2.42 tree-data-ref.c
--- tree-data-ref.c 15 Sep 2005 17:21:48 -0000 2.42
+++ tree-data-ref.c 18 Sep 2005 22:59:45 -0000
@@ -2152,6 +2152,20 @@ analyze_ziv_subscript (tree chrec_a,
fprintf (dump_file, ")\n");
}
+/* Get the real or estimated number of iterations for LOOPNUM, whichever is
+ available. Return the number of iterations as a tree, or NULL_TREE if
+ we don't know. */
+
+static tree
+get_number_of_iters_for_loop (int loopnum)
+{
+ tree numiter = number_of_iterations_in_loop (current_loops->parray[loopnum]);
+
+ if (TREE_CODE (numiter) != INTEGER_CST)
+ numiter = current_loops->parray[loopnum]->estimated_nb_iterations;
+ return numiter;
+}
+
/* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
constant, and CHREC_B is an affine function. *OVERLAPS_A and
*OVERLAPS_B are initialized to the functions that describe the
@@ -2200,6 +2214,9 @@ analyze_siv_subscript_cst_affine (tree c
if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
{
+ tree numiter;
+ int loopnum = CHREC_VARIABLE (chrec_b);
+
*overlaps_a = integer_zero_node;
*overlaps_b = fold_build2 (EXACT_DIV_EXPR, integer_type_node,
fold_build1 (ABS_EXPR,
@@ -2207,6 +2224,21 @@ analyze_siv_subscript_cst_affine (tree c
difference),
CHREC_RIGHT (chrec_b));
*last_conflicts = integer_one_node;
+
+
+ /* Perform weak-zero siv test to see if overlap is
+ outside the loop bounds. */
+ numiter = get_number_of_iters_for_loop (loopnum);
+
+ if (numiter != NULL_TREE
+ && TREE_CODE (*overlaps_b) == INTEGER_CST
+ && tree_int_cst_lt (numiter, *overlaps_b))
+ {
+ *overlaps_a = chrec_known;
+ *overlaps_b = chrec_known;
+ *last_conflicts = integer_zero_node;
+ return;
+ }
return;
}
@@ -2254,11 +2286,28 @@ analyze_siv_subscript_cst_affine (tree c
*/
if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
{
+ tree numiter;
+ int loopnum = CHREC_VARIABLE (chrec_b);
+
*overlaps_a = integer_zero_node;
*overlaps_b = fold_build2 (EXACT_DIV_EXPR,
integer_type_node, difference,
CHREC_RIGHT (chrec_b));
*last_conflicts = integer_one_node;
+
+ /* Perform weak-zero siv test to see if overlap is
+ outside the loop bounds. */
+ numiter = get_number_of_iters_for_loop (loopnum);
+
+ if (numiter != NULL_TREE
+ && TREE_CODE (*overlaps_b) == INTEGER_CST
+ && tree_int_cst_lt (numiter, *overlaps_b))
+ {
+ *overlaps_a = chrec_known;
+ *overlaps_b = chrec_known;
+ *last_conflicts = integer_zero_node;
+ return;
+ }
return;
}
@@ -2382,29 +2431,12 @@ compute_overlap_steps_for_affine_1_2 (tr
step_y = int_cst_value (CHREC_RIGHT (chrec_a));
step_z = int_cst_value (CHREC_RIGHT (chrec_b));
- numiter_x = number_of_iterations_in_loop
- (current_loops->parray[CHREC_VARIABLE (CHREC_LEFT (chrec_a))]);
- numiter_y = number_of_iterations_in_loop
- (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
- numiter_z = number_of_iterations_in_loop
- (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
-
- if (TREE_CODE (numiter_x) != INTEGER_CST)
- numiter_x = current_loops->parray[CHREC_VARIABLE (CHREC_LEFT (chrec_a))]
- ->estimated_nb_iterations;
- if (TREE_CODE (numiter_y) != INTEGER_CST)
- numiter_y = current_loops->parray[CHREC_VARIABLE (chrec_a)]
- ->estimated_nb_iterations;
- if (TREE_CODE (numiter_z) != INTEGER_CST)
- numiter_z = current_loops->parray[CHREC_VARIABLE (chrec_b)]
- ->estimated_nb_iterations;
-
- if (chrec_contains_undetermined (numiter_x)
- || chrec_contains_undetermined (numiter_y)
- || chrec_contains_undetermined (numiter_z)
- || TREE_CODE (numiter_x) != INTEGER_CST
- || TREE_CODE (numiter_y) != INTEGER_CST
- || TREE_CODE (numiter_z) != INTEGER_CST)
+ numiter_x = get_number_of_iters_for_loop (CHREC_VARIABLE (CHREC_LEFT (chrec_a)));
+ numiter_y = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a));
+ numiter_z = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b));
+
+ if (numiter_x == NULL_TREE || numiter_y == NULL_TREE
+ || numiter_z == NULL_TREE)
{
*overlaps_a = chrec_dont_know;
*overlaps_b = chrec_dont_know;
@@ -2497,7 +2529,17 @@ analyze_subscript_affine_affine (tree ch
int init_a, init_b, gamma, gcd_alpha_beta;
int tau1, tau2;
lambda_matrix A, U, S;
+ tree difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
+ if (integer_zerop (difference))
+ {
+ /* The difference is equal to zero: the accessed index
+ overlaps for each iteration in the loop. */
+ *overlaps_a = integer_zero_node;
+ *overlaps_b = integer_zero_node;
+ *last_conflicts = chrec_dont_know;
+ return;
+ }
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "(analyze_subscript_affine_affine \n");
@@ -2541,21 +2583,9 @@ analyze_subscript_affine_affine (tree ch
int niter, niter_a, niter_b;
tree numiter_a, numiter_b;
- numiter_a = number_of_iterations_in_loop
- (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
- numiter_b = number_of_iterations_in_loop
- (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
-
- if (TREE_CODE (numiter_a) != INTEGER_CST)
- numiter_a = current_loops->parray[CHREC_VARIABLE (chrec_a)]
- ->estimated_nb_iterations;
- if (TREE_CODE (numiter_b) != INTEGER_CST)
- numiter_b = current_loops->parray[CHREC_VARIABLE (chrec_b)]
- ->estimated_nb_iterations;
- if (chrec_contains_undetermined (numiter_a)
- || chrec_contains_undetermined (numiter_b)
- || TREE_CODE (numiter_a) != INTEGER_CST
- || TREE_CODE (numiter_b) != INTEGER_CST)
+ numiter_a = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a));
+ numiter_b = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b));
+ if (numiter_a == NULL_TREE || numiter_b == NULL_TREE)
{
*overlaps_a = chrec_dont_know;
*overlaps_b = chrec_dont_know;
@@ -2645,21 +2675,10 @@ analyze_subscript_affine_affine (tree ch
int niter, niter_a, niter_b;
tree numiter_a, numiter_b;
- numiter_a = number_of_iterations_in_loop
- (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
- numiter_b = number_of_iterations_in_loop
- (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
-
- if (TREE_CODE (numiter_a) != INTEGER_CST)
- numiter_a = current_loops->parray[CHREC_VARIABLE (chrec_a)]
- ->estimated_nb_iterations;
- if (TREE_CODE (numiter_b) != INTEGER_CST)
- numiter_b = current_loops->parray[CHREC_VARIABLE (chrec_b)]
- ->estimated_nb_iterations;
- if (chrec_contains_undetermined (numiter_a)
- || chrec_contains_undetermined (numiter_b)
- || TREE_CODE (numiter_a) != INTEGER_CST
- || TREE_CODE (numiter_b) != INTEGER_CST)
+ numiter_a = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a));
+ numiter_b = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b));
+
+ if (numiter_a == NULL_TREE || numiter_b == NULL_TREE)
{
*overlaps_a = chrec_dont_know;
*overlaps_b = chrec_dont_know;
@@ -2715,15 +2734,26 @@ analyze_subscript_affine_affine (tree ch
tau1 = (x0 - i0)/i1;
last_conflict = tau2 - tau1;
- *overlaps_a = build_polynomial_chrec
- (1,
- build_int_cst (NULL_TREE, x0),
- build_int_cst (NULL_TREE, i1));
- *overlaps_b = build_polynomial_chrec
- (1,
- build_int_cst (NULL_TREE, y0),
- build_int_cst (NULL_TREE, j1));
- *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
+ /* If the overlap occurs outside of the bounds of the
+ loop, there is no dependence. */
+ if (x0 > niter || y0 > niter)
+ {
+ *overlaps_a = chrec_known;
+ *overlaps_b = chrec_known;
+ *last_conflicts = integer_zero_node;
+ }
+ else
+ {
+ *overlaps_a = build_polynomial_chrec
+ (1,
+ build_int_cst (NULL_TREE, x0),
+ build_int_cst (NULL_TREE, i1));
+ *overlaps_b = build_polynomial_chrec
+ (1,
+ build_int_cst (NULL_TREE, y0),
+ build_int_cst (NULL_TREE, j1));
+ *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
+ }
}
else
{
@@ -2870,8 +2900,8 @@ analyze_miv_subscript (tree chrec_a,
in the same order. */
*overlaps_a = integer_zero_node;
*overlaps_b = integer_zero_node;
- *last_conflicts = number_of_iterations_in_loop
- (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
+ *last_conflicts = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a));
+
}
else if (evolution_function_is_constant_p (difference)