This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[autovect] Fix a symbolic dependence test
- From: Sebastian Pop <sebastian dot pop at cri dot ensmp dot fr>
- To: gcc-patches at gcc dot gnu dot org
- Date: Mon, 31 Jan 2005 17:03:03 +0100
- Subject: [autovect] Fix a symbolic dependence test
Hi,
Without this patch one of the spec dependence tests fails with an ICE.
The patch also updates the statistics of handled/unhandled tests.
Bootstrapped on x86_64 and commited to autovect branch.
Index: ChangeLog.autovect
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/ChangeLog.autovect,v
retrieving revision 1.1.2.27
diff -d -u -p -r1.1.2.27 ChangeLog.autovect
--- ChangeLog.autovect 31 Jan 2005 11:03:25 -0000 1.1.2.27
+++ ChangeLog.autovect 31 Jan 2005 15:56:53 -0000
@@ -1,5 +1,23 @@
2005-01-31 Sebastian Pop <pop@cri.ensmp.fr>
+ * tree-data-ref.c (datadep_stats): Add the following fields:
+ num_dependence_tests, num_dependence_dependent,
+ num_dependence_independent, num_dependence_undetermined,
+ num_subscript_tests, num_subscript_undetermined,
+ num_same_subscript_function.
+ Removed num_tested and num_unimplemented.
+ (can_use_analyze_subscript_affine_affine): Print some text
+ when executed.
+ (analyze_siv_subscript, analyze_miv_subscript):
+ Increment dependence_stats counters apropriately in missing cases.
+ (chrec_steps_divide_constant_p): Deal with undetermined symbols.
+ (analyze_miv_subscript): Adapt for chrec_steps_divide_constant_p.
+ (analyze_overlapping_iterations, subscript_dependence_tester,
+ compute_affine_dependence, compute_data_dependences_for_loop):
+ Use the new counters.
+
+2005-01-31 Sebastian Pop <pop@cri.ensmp.fr>
+
* tree-scalar-evolution.c (unify_peeled_chrec): Use
standard_iv_increment_position for computing the iv update
location.
Index: tree-data-ref.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-data-ref.c,v
retrieving revision 2.15.4.8
diff -d -u -p -r2.15.4.8 tree-data-ref.c
--- tree-data-ref.c 30 Jan 2005 18:10:44 -0000 2.15.4.8
+++ tree-data-ref.c 31 Jan 2005 15:56:54 -0000
@@ -97,20 +97,29 @@ Software Foundation, 59 Temple Place - S
static struct datadep_stats
{
+ int num_dependence_tests;
+ int num_dependence_dependent;
+ int num_dependence_independent;
+ int num_dependence_undetermined;
+
+ int num_subscript_tests;
+ int num_subscript_undetermined;
+ int num_same_subscript_function;
+
int num_ziv;
int num_ziv_independent;
int num_ziv_dependent;
int num_ziv_unimplemented;
+
int num_siv;
int num_siv_independent;
int num_siv_dependent;
int num_siv_unimplemented;
+
int num_miv;
int num_miv_independent;
int num_miv_dependent;
int num_miv_unimplemented;
- int num_tested;
- int num_unimplemented;
} dependence_stats;
@@ -1656,6 +1665,9 @@ can_use_analyze_subscript_affine_affine
if (!evolution_function_is_constant_p (diff))
return false;
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "can_use_subscript_aff_aff_for_symbolic \n");
+
*chrec_a = build_polynomial_chrec (CHREC_VARIABLE (*chrec_a),
diff, CHREC_RIGHT (*chrec_a));
*chrec_b = build_polynomial_chrec (CHREC_VARIABLE (*chrec_b),
@@ -1698,9 +1710,20 @@ analyze_siv_subscript (tree chrec_a,
{
if (!chrec_contains_symbols (chrec_a)
&& !chrec_contains_symbols (chrec_b))
- analyze_subscript_affine_affine (chrec_a, chrec_b,
- overlaps_a, overlaps_b,
- last_conflicts);
+ {
+ analyze_subscript_affine_affine (chrec_a, chrec_b,
+ overlaps_a, overlaps_b,
+ last_conflicts);
+
+ if (*overlaps_a == chrec_dont_know
+ || *overlaps_b == chrec_dont_know)
+ dependence_stats.num_siv_unimplemented++;
+ else if (*overlaps_a == chrec_known
+ || *overlaps_b == chrec_known)
+ dependence_stats.num_siv_independent++;
+ else
+ dependence_stats.num_siv_dependent++;
+ }
else if (can_use_analyze_subscript_affine_affine (&chrec_a,
&chrec_b))
{
@@ -1710,6 +1733,15 @@ analyze_siv_subscript (tree chrec_a,
/* FIXME: The number of iterations is a symbolic expression.
Compute it properly. */
*last_conflicts = chrec_dont_know;
+
+ if (*overlaps_a == chrec_dont_know
+ || *overlaps_b == chrec_dont_know)
+ dependence_stats.num_siv_unimplemented++;
+ else if (*overlaps_a == chrec_known
+ || *overlaps_b == chrec_known)
+ dependence_stats.num_siv_independent++;
+ else
+ dependence_stats.num_siv_dependent++;
}
else
goto siv_subscript_dontknow;
@@ -1730,19 +1762,32 @@ analyze_siv_subscript (tree chrec_a,
fprintf (dump_file, ")\n");
}
-/* Return true when the evolution steps of an affine CHREC divide the
- constant CST. */
+/* Return true when the property can be computed. RES should contain
+ true when calling the first time this function, then it is set to
+ false when one of the evolution steps of an affine CHREC does not
+ divide the constant CST. */
static bool
chrec_steps_divide_constant_p (tree chrec,
- tree cst)
+ tree cst,
+ bool *res)
{
switch (TREE_CODE (chrec))
{
case POLYNOMIAL_CHREC:
- return (tree_fold_divides_p (integer_type_node, CHREC_RIGHT (chrec), cst)
- && chrec_steps_divide_constant_p (CHREC_LEFT (chrec), cst));
-
+ if (evolution_function_is_constant_p (CHREC_RIGHT (chrec)))
+ {
+ if (tree_fold_divides_p (integer_type_node, CHREC_RIGHT (chrec), cst))
+ /* Keep RES to true, and iterate on other dimensions. */
+ return chrec_steps_divide_constant_p (CHREC_LEFT (chrec), cst, res);
+
+ *res = false;
+ return true;
+ }
+ else
+ /* When the step is a parameter the result is undetermined. */
+ return false;
+
default:
/* On the initial condition, return true. */
return true;
@@ -1771,6 +1816,7 @@ analyze_miv_subscript (tree chrec_a,
variables. In the MIV case we have to solve a Diophantine
equation with 2*n variables (if the subscript uses n IVs).
*/
+ bool divide_p = true;
tree difference;
dependence_stats.num_miv++;
if (dump_file && (dump_flags & TDF_DETAILS))
@@ -1791,11 +1837,12 @@ analyze_miv_subscript (tree chrec_a,
else if (evolution_function_is_constant_p (difference)
/* For the moment, the following is verified:
evolution_function_is_affine_multivariate_p (chrec_a) */
- && !chrec_steps_divide_constant_p (chrec_a, difference))
+ && chrec_steps_divide_constant_p (chrec_a, difference, ÷_p)
+ && !divide_p)
{
/* testsuite/.../ssa-chrec-33.c
{{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
-
+
The difference is 1, and the evolution steps are equal to 2,
consequently there are no overlapping elements. */
*overlaps_a = chrec_known;
@@ -1825,6 +1872,15 @@ analyze_miv_subscript (tree chrec_a,
*/
analyze_subscript_affine_affine (chrec_a, chrec_b,
overlaps_a, overlaps_b, last_conflicts);
+
+ if (*overlaps_a == chrec_dont_know
+ || *overlaps_b == chrec_dont_know)
+ dependence_stats.num_miv_unimplemented++;
+ else if (*overlaps_a == chrec_known
+ || *overlaps_b == chrec_known)
+ dependence_stats.num_miv_independent++;
+ else
+ dependence_stats.num_miv_dependent++;
}
else
@@ -1859,7 +1915,7 @@ analyze_overlapping_iterations (tree chr
tree *overlap_iterations_b,
tree *last_conflicts)
{
- dependence_stats.num_tested++;
+ dependence_stats.num_subscript_tests++;
if (dump_file && (dump_flags & TDF_DETAILS))
{
@@ -1876,7 +1932,7 @@ analyze_overlapping_iterations (tree chr
|| chrec_contains_undetermined (chrec_a)
|| chrec_contains_undetermined (chrec_b))
{
- dependence_stats.num_unimplemented++;
+ dependence_stats.num_subscript_undetermined++;
*overlap_iterations_a = chrec_dont_know;
*overlap_iterations_b = chrec_dont_know;
@@ -1887,6 +1943,7 @@ analyze_overlapping_iterations (tree chr
else if (eq_evolutions_p (chrec_a, chrec_b)
&& evolution_function_is_affine_multivariate_p (chrec_a))
{
+ dependence_stats.num_same_subscript_function++;
*overlap_iterations_a = integer_zero_node;
*overlap_iterations_b = integer_zero_node;
*last_conflicts = chrec_dont_know;
@@ -1898,7 +1955,7 @@ analyze_overlapping_iterations (tree chr
&& (!evolution_function_is_affine_multivariate_p (chrec_a)
|| !evolution_function_is_affine_multivariate_p (chrec_b)))
{
- dependence_stats.num_unimplemented++;
+ dependence_stats.num_subscript_undetermined++;
*overlap_iterations_a = chrec_dont_know;
*overlap_iterations_b = chrec_dont_know;
}
@@ -1958,6 +2015,7 @@ subscript_dependence_tester (struct data
|| chrec_contains_undetermined (overlaps_b))
{
finalize_ddr_dependent (ddr, chrec_dont_know);
+ dependence_stats.num_dependence_undetermined++;
break;
}
@@ -1965,6 +2023,7 @@ subscript_dependence_tester (struct data
|| overlaps_b == chrec_known)
{
finalize_ddr_dependent (ddr, chrec_known);
+ dependence_stats.num_dependence_independent++;
break;
}
@@ -1973,6 +2032,7 @@ subscript_dependence_tester (struct data
SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
SUB_LAST_CONFLICT (subscript) = last_conflicts;
+ dependence_stats.num_dependence_dependent++;
}
}
@@ -2379,10 +2439,12 @@ compute_affine_dependence (struct data_d
print_generic_expr (dump_file, DR_STMT (drb), 0);
fprintf (dump_file, ")\n");
}
- dependence_stats.num_tested++;
+
/* Analyze only when the dependence relation is not yet known. */
if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
{
+ dependence_stats.num_dependence_tests++;
+
if (access_functions_are_affine_or_constant_p (dra)
&& access_functions_are_affine_or_constant_p (drb))
subscript_dependence_tester (ddr);
@@ -2392,7 +2454,7 @@ compute_affine_dependence (struct data_d
"don't know". */
else
{
- dependence_stats.num_unimplemented++;
+ dependence_stats.num_dependence_undetermined++;
if (dump_file && (dump_flags & TDF_DETAILS))
{
@@ -2578,10 +2640,22 @@ compute_data_dependences_for_loop (unsig
if (dump_file && (dump_flags & TDF_STATS))
{
fprintf (dump_file, "Dependence tester statistics:\n");
- fprintf (dump_file, "Number of tests: %d\n",
- dependence_stats.num_tested);
- fprintf (dump_file, "Number of completely unimplemented tests: %d\n",
- dependence_stats.num_unimplemented);
+
+ fprintf (dump_file, "Number of dependence tests: %d\n",
+ dependence_stats.num_dependence_tests);
+ fprintf (dump_file, "Number of dependence tests classified dependent: %d\n",
+ dependence_stats.num_dependence_dependent);
+ fprintf (dump_file, "Number of dependence tests classified independent: %d\n",
+ dependence_stats.num_dependence_independent);
+ fprintf (dump_file, "Number of undetermined dependence tests: %d\n",
+ dependence_stats.num_dependence_undetermined);
+
+ fprintf (dump_file, "Number of subscript tests: %d\n",
+ dependence_stats.num_subscript_tests);
+ fprintf (dump_file, "Number of undetermined subscript tests: %d\n",
+ dependence_stats.num_subscript_undetermined);
+ fprintf (dump_file, "Number of same subscript function: %d\n",
+ dependence_stats.num_same_subscript_function);
fprintf (dump_file, "Number of ziv tests: %d\n",
dependence_stats.num_ziv);
@@ -2591,6 +2665,7 @@ compute_data_dependences_for_loop (unsig
dependence_stats.num_ziv_independent);
fprintf (dump_file, "Number of ziv tests unimplemented: %d\n",
dependence_stats.num_ziv_unimplemented);
+
fprintf (dump_file, "Number of siv tests: %d\n",
dependence_stats.num_siv);
fprintf (dump_file, "Number of siv tests returning dependent: %d\n",
@@ -2599,6 +2674,7 @@ compute_data_dependences_for_loop (unsig
dependence_stats.num_siv_independent);
fprintf (dump_file, "Number of siv tests unimplemented: %d\n",
dependence_stats.num_siv_unimplemented);
+
fprintf (dump_file, "Number of miv tests: %d\n",
dependence_stats.num_miv);
fprintf (dump_file, "Number of miv tests returning dependent: %d\n",