This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[lno] some cleanups for scev
- From: Sebastian Pop <sebastian dot pop at cri dot ensmp dot fr>
- To: gcc-patches at gcc dot gnu dot org
- Date: Thu, 15 Apr 2004 16:54:18 +0200
- Subject: [lno] some cleanups for scev
Hi,
This patch
- cleans up a bit the gathering of stats for the scev algorithm,
- moves the Banerjee test from tree-chrec.c to tree-data-ref.c,
- removes some unused functions.
- fixes the number of iterations when it depends on outer loops.
Bootstrapped on i686-pc-linux-gnu.
* tree-fold-const.h (chrec_merge_types): Move it...
* tree-chrec.c (multiply_int, divide_int, add_int, substract_int,
integer_divides_p, lcm, gcd, update_initial_condition_to_origin,
remove_initial_condition, ): Removed.
(evolution_function_in_loop_num): Renamed into
hide_evolution_in_other_loops_than_loop.
(hide_evolution_in_loop, hide_evolution_in_other_loops_than_loop): New.
(chrec_merge_types): ... here.
(chrec_merge): Answer chrec_top on EXPONENTIAL_CHREC.
(ziv_subscript_p, siv_subscript_p, analyze_ziv_subscript,
analyze_siv_subscript, analyze_siv_subscript_cst_affine,
analyze_siv_subscript_affine_cst, analyze_siv_subscript_affine_affine,
chrec_steps_divide_constant_p, analyze_miv_subscript,
analyze_overlapping_iterations): Moved from here...
* tree-chrec.h (evolution_function_in_loop_num): Rename declaration.
(hide_evolution_in_other_loops_than_loop, hide_evolution_in_loop): New.
(analyze_overlapping_iterations): No longer extern.
* tree-data-ref.c (ziv_subscript_p, siv_subscript_p,
analyze_ziv_subscript,
analyze_siv_subscript, analyze_siv_subscript_cst_affine,
analyze_siv_subscript_affine_cst, analyze_siv_subscript_affine_affine,
chrec_steps_divide_constant_p, analyze_miv_subscript,
analyze_overlapping_iterations): ... there.
(initialize_data_dependence_relation,
access_functions_are_affine_or_constant_p): Moved down.
(compute_all_dependences): Moved down. Now is static.
(build_classic_dir_vector): New.
(build_classic_dist_vector):
(find_data_references): Renamed find_data_references_in_loop.
Now is static.
(compute_data_dependences_for_loop): New.
(analyze_all_data_dependences): Use compute_data_dependences_for_loop.
* tree-data-ref.h (dd_info_available): Don't declare it extern.
* tree-scalar-evolution.c (dd_info_available): Declare static.
(select_outer_and_current_evolutions): Removed.
(stats_*): Move the static variables in the chrec_stats structure.
(chrec_stats): New structure.
(first_iteration_non_satisfying_1): In the multivariate case,
don't forget that the outer loops can change the number of iterations.
(cannot_analyze_loop_nb_iterations_yet): Removed.
(follow_ssa_edge_inner_loop_phi): Refine the case where the
evolution of the inner loop is symbolic.
(number_of_iterations_in_loop): Factor the end of the cases.
Index: tree-chrec.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-chrec.c,v
retrieving revision 1.1.2.13
diff -d -u -p -r1.1.2.13 tree-chrec.c
--- tree-chrec.c 15 Apr 2004 01:01:47 -0000 1.1.2.13
+++ tree-chrec.c 15 Apr 2004 14:47:29 -0000
@@ -37,131 +37,6 @@ Software Foundation, 59 Temple Place - S
#include "tree-chrec.h"
#include "tree-pass.h"
-/* Operations. */
-static tree chrec_merge_intervals (tree, tree);
-static tree remove_initial_condition (tree);
-
-/* Observers. */
-static bool is_multivariate_chrec_rec (tree, unsigned int);
-static inline bool is_not_constant_evolution (tree);
-
-/* Analyzers. */
-static inline bool ziv_subscript_p (tree, tree);
-static bool siv_subscript_p (tree, tree);
-static void analyze_ziv_subscript (tree, tree, tree*, tree*);
-static void analyze_siv_subscript (tree, tree, tree*, tree*);
-static void analyze_siv_subscript_cst_affine (tree, tree, tree*, tree*);
-static void analyze_siv_subscript_affine_cst (tree, tree, tree*, tree*);
-static void analyze_siv_subscript_affine_affine (tree, tree, tree*, tree*);
-static bool chrec_steps_divide_constant_p (tree, tree);
-static void analyze_miv_subscript (tree, tree, tree*, tree*);
-
-/* Basic arithmetics. */
-static int lcm (int, int);
-static int gcd (int, int);
-static inline int multiply_int (int, int);
-static inline int divide_int (int, int);
-static inline int add_int (int, int);
-static inline int substract_int (int, int);
-static inline bool integer_divides_p (int, int);
-
-
-
-/* Multiply integers. */
-
-static inline int
-multiply_int (int a, int b)
-{
- return a * b;
-}
-
-/* Divide integers. */
-
-static inline int
-divide_int (int a, int b)
-{
- return a / b;
-}
-
-/* Add integers. */
-
-static inline int
-add_int (int a, int b)
-{
- return a + b;
-}
-
-/* Substract integers. */
-
-static inline int
-substract_int (int a, int b)
-{
- return a - b;
-}
-
-/* Determines whether a divides b. */
-
-static inline bool
-integer_divides_p (int a, int b)
-{
- return (a == gcd (a, b));
-}
-
-/* Least common multiple. */
-
-static int
-lcm (int a,
- int b)
-{
- int pgcd;
-
- if (a == 1)
- return b;
-
- if (b == 1)
- return a;
-
- if (a == 0 || b == 0)
- return 0;
-
- pgcd = gcd (a, b);
-
- if (pgcd == 1)
- return multiply_int (a, b);
-
- return pgcd * lcm (divide_int (a, pgcd),
- divide_int (b, pgcd));
-}
-
-/* Greatest common divisor. */
-
-static int
-gcd (int a,
- int b)
-{
- if (a == 0)
- return b;
-
- if (b == 0)
- return a;
-
- if (a < 0)
- a = multiply_int (a, -1);
-
- if (b < 0)
- b = multiply_int (b, -1);
-
- if (a == b)
- return a;
-
- if (a > b)
- return gcd (substract_int (a, b), b);
-
- /* if (b > a) */
- return gcd (substract_int (b, a), a);
-}
-
-
/* Extended folder for chrecs. */
@@ -1235,6 +1110,7 @@ chrec_fold_multiply (tree type,
}
}
}
+
/* Operations. */
@@ -1341,7 +1217,7 @@ chrec_apply (unsigned var,
if (dump_file && (dump_flags & TDF_DETAILS))
{
- fprintf (dump_file, " (var = %d\n", var);
+ fprintf (dump_file, " (varying_loop = %d\n", var);
fprintf (dump_file, ")\n (chrec = ");
print_generic_expr (dump_file, chrec, 0);
fprintf (dump_file, ")\n (x = ");
@@ -1385,11 +1261,26 @@ chrec_replace_initial_condition (tree ch
}
}
-/* Updates the initial condition to the origin, ie. zero for a
- polynomial function, and one for an exponential function. */
+/* Returns the initial condition of a given CHREC. */
tree
-update_initial_condition_to_origin (tree chrec)
+initial_condition (tree chrec)
+{
+ if (automatically_generated_chrec_p (chrec))
+ return chrec;
+
+ if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
+ || TREE_CODE (chrec) == EXPONENTIAL_CHREC)
+ return initial_condition (CHREC_LEFT (chrec));
+ else
+ return chrec;
+}
+
+/* Returns a multivariate function that has no evolution in LOOP_NUM.
+ Mask the evolution LOOP_NUM. */
+
+tree
+hide_evolution_in_loop (tree chrec, unsigned loop_num)
{
if (automatically_generated_chrec_p (chrec))
return chrec;
@@ -1397,57 +1288,36 @@ update_initial_condition_to_origin (tree
switch (TREE_CODE (chrec))
{
case POLYNOMIAL_CHREC:
- if (TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
- || TREE_CODE (CHREC_LEFT (chrec)) == EXPONENTIAL_CHREC)
- return build_polynomial_chrec
- (CHREC_VARIABLE (chrec),
- update_initial_condition_to_origin (CHREC_LEFT (chrec)),
- CHREC_RIGHT (chrec));
+ if (CHREC_VARIABLE (chrec) >= loop_num)
+ return hide_evolution_in_loop (CHREC_LEFT (chrec), loop_num);
+
else
- return build_polynomial_chrec
- (CHREC_VARIABLE (chrec),
- integer_zero_node,
+ return build_polynomial_chrec
+ (CHREC_VARIABLE (chrec),
+ hide_evolution_in_loop (CHREC_LEFT (chrec), loop_num),
CHREC_RIGHT (chrec));
-
+
case EXPONENTIAL_CHREC:
- if (TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
- || TREE_CODE (CHREC_LEFT (chrec)) == EXPONENTIAL_CHREC)
- return build_exponential_chrec
- (CHREC_VARIABLE (chrec),
- integer_one_node,
- CHREC_RIGHT (chrec));
+ if (CHREC_VARIABLE (chrec) >= loop_num)
+ return hide_evolution_in_loop (CHREC_LEFT (chrec), loop_num);
+
else
- return build_polynomial_chrec
+ return build_exponential_chrec
(CHREC_VARIABLE (chrec),
- integer_zero_node,
+ hide_evolution_in_loop (CHREC_LEFT (chrec), loop_num),
CHREC_RIGHT (chrec));
-
+
default:
- return chrec_top;
+ return chrec;
}
}
-/* Returns the initial condition of a given CHREC. */
-
-tree
-initial_condition (tree chrec)
-{
- if (automatically_generated_chrec_p (chrec))
- return chrec;
-
- if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
- || TREE_CODE (chrec) == EXPONENTIAL_CHREC)
- return initial_condition (CHREC_LEFT (chrec));
- else
- return chrec;
-}
-
/* Returns a univariate function that represents the evolution in
- LOOP_NUM. */
+ LOOP_NUM. Mask the evolution of any other loop. */
tree
-evolution_function_in_loop_num (tree chrec,
- unsigned loop_num)
+hide_evolution_in_other_loops_than_loop (tree chrec,
+ unsigned loop_num)
{
if (automatically_generated_chrec_p (chrec))
return chrec;
@@ -1458,7 +1328,8 @@ evolution_function_in_loop_num (tree chr
if (CHREC_VARIABLE (chrec) == loop_num)
return build_polynomial_chrec
(loop_num,
- evolution_function_in_loop_num (CHREC_LEFT (chrec), loop_num),
+ hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
+ loop_num),
CHREC_RIGHT (chrec));
else if (CHREC_VARIABLE (chrec) < loop_num)
@@ -1466,13 +1337,15 @@ evolution_function_in_loop_num (tree chr
return initial_condition (chrec);
else
- return evolution_function_in_loop_num (CHREC_LEFT (chrec), loop_num);
+ return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
+ loop_num);
case EXPONENTIAL_CHREC:
if (CHREC_VARIABLE (chrec) == loop_num)
return build_exponential_chrec
(loop_num,
- evolution_function_in_loop_num (CHREC_LEFT (chrec), loop_num),
+ hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
+ loop_num),
CHREC_RIGHT (chrec));
else if (CHREC_VARIABLE (chrec) < loop_num)
@@ -1480,7 +1353,8 @@ evolution_function_in_loop_num (tree chr
return initial_condition (chrec);
else
- return evolution_function_in_loop_num (CHREC_LEFT (chrec), loop_num);
+ return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
+ loop_num);
default:
return chrec;
@@ -1620,32 +1494,37 @@ chrec_eval_next_init_cond (unsigned loop
return init_cond;
}
-/* Merge the information contained in two intervals.
+/* Determine the type of the result after the merge of types TYPE0 and
+ TYPE1. */
+
+static inline tree
+chrec_merge_types (tree type0,
+ tree type1)
+{
+ if (type0 == type1)
+ return type0;
+
+ else
+ /* FIXME. */
+ return NULL_TREE;
+}
+
+/* Merge the information contained in intervals or scalar constants.
merge ([a, b], [c, d]) -> [min (a, c), max (b, d)],
merge ([a, b], c) -> [min (a, c), max (b, c)],
merge (a, [b, c]) -> [min (a, b), max (a, c)],
merge (a, b) -> [min (a, b), max (a, b)]. */
-static tree
+static inline tree
chrec_merge_intervals (tree chrec1,
tree chrec2)
{
- tree type;
+ tree type1 = chrec_type (chrec1);
+ tree type2 = chrec_type (chrec2);
+ tree type = chrec_merge_types (type1, type2);
- /* Don't modify abstract values. */
- if (chrec1 == chrec_top
- || chrec2 == chrec_top)
+ if (type == NULL_TREE)
return chrec_top;
- if (chrec1 == chrec_bot
- || chrec2 == chrec_bot)
- return chrec_bot;
- if (chrec1 == chrec_not_analyzed_yet)
- return chrec2;
- if (chrec2 == chrec_not_analyzed_yet)
- return chrec1;
-
- type = chrec_merge_types
- (chrec_type (chrec1), chrec_type (chrec2));
if (TREE_CODE (chrec1) == INTERVAL_CHREC)
{
@@ -1675,11 +1554,19 @@ tree
chrec_merge (tree chrec1,
tree chrec2)
{
+ if (chrec1 == chrec_top
+ || chrec2 == chrec_top)
+ return chrec_top;
+
+ if (chrec1 == chrec_bot
+ || chrec2 == chrec_bot)
+ return chrec_bot;
+
if (chrec1 == chrec_not_analyzed_yet)
return chrec2;
if (chrec2 == chrec_not_analyzed_yet)
return chrec1;
-
+
if (operand_equal_p (chrec1, chrec2, 0))
return chrec1;
@@ -1704,10 +1591,7 @@ chrec_merge (tree chrec1,
(CHREC_VARIABLE (chrec2),
chrec_merge (chrec1, CHREC_LEFT (chrec2)),
chrec_merge (integer_one_node, CHREC_RIGHT (chrec2)));
-
- return chrec_merge_intervals
- (chrec1, build_interval_chrec (chrec2, chrec2));
-
+
default:
return chrec_top;
}
@@ -1740,90 +1624,20 @@ chrec_merge (tree chrec1,
chrec_merge (CHREC_RIGHT (chrec1), integer_zero_node));
case EXPONENTIAL_CHREC:
- if (CHREC_VARIABLE (chrec1) == CHREC_VARIABLE (chrec2))
- return chrec_top;
- else if (CHREC_VARIABLE (chrec1) < CHREC_VARIABLE (chrec2))
- return build_exponential_chrec
- (CHREC_VARIABLE (chrec2),
- chrec_merge (chrec1, CHREC_LEFT (chrec2)),
- chrec_merge (integer_one_node, CHREC_RIGHT (chrec2)));
- else
- return build_polynomial_chrec
- (CHREC_VARIABLE (chrec1),
- chrec_merge (CHREC_LEFT (chrec1), chrec2),
- chrec_merge (CHREC_RIGHT (chrec1), integer_zero_node));
-
- default:
return chrec_top;
- }
-
- case EXPONENTIAL_CHREC:
- switch (TREE_CODE (chrec2))
- {
- case INTEGER_CST:
- case INTERVAL_CHREC:
- return build_exponential_chrec
- (CHREC_VARIABLE (chrec1),
- chrec_merge (CHREC_LEFT (chrec1), chrec2),
- chrec_merge (CHREC_RIGHT (chrec1), integer_one_node));
-
- case POLYNOMIAL_CHREC:
- if (CHREC_VARIABLE (chrec1) == CHREC_VARIABLE (chrec2))
- return chrec_top;
- else if (CHREC_VARIABLE (chrec1) < CHREC_VARIABLE (chrec2))
- return build_polynomial_chrec
- (CHREC_VARIABLE (chrec2),
- chrec_merge (chrec1, CHREC_LEFT (chrec2)),
- chrec_merge (integer_zero_node, CHREC_RIGHT (chrec2)));
- else
- return build_exponential_chrec
- (CHREC_VARIABLE (chrec1),
- chrec_merge (CHREC_LEFT (chrec1), chrec2),
- chrec_merge (CHREC_RIGHT (chrec1), integer_one_node));
-
- case EXPONENTIAL_CHREC:
- return build_exponential_chrec
- (CHREC_VARIABLE (chrec1),
- chrec_merge (CHREC_LEFT (chrec1), CHREC_LEFT (chrec2)),
- chrec_merge (CHREC_RIGHT (chrec1), CHREC_RIGHT (chrec2)));
default:
return chrec_top;
}
+ case EXPONENTIAL_CHREC:
+ return chrec_top;
+
default:
return chrec_top;
}
}
-/* Returns a chrec for which the initial condition has been removed.
- Example: {{1, +, 2}, +, 3} returns {2, +, 3}. */
-
-static tree
-remove_initial_condition (tree chrec)
-{
- tree left;
-
- if (chrec == NULL_TREE)
- return NULL_TREE;
-
- if (TREE_CODE (chrec) != POLYNOMIAL_CHREC
- && TREE_CODE (chrec) != EXPONENTIAL_CHREC)
- return NULL_TREE;
-
- left = remove_initial_condition (CHREC_LEFT (chrec));
- if (left == NULL_TREE)
- return CHREC_RIGHT (chrec);
-
- if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
- return build_polynomial_chrec
- (CHREC_VARIABLE (chrec), left, CHREC_RIGHT (chrec));
-
- else
- return build_exponential_chrec
- (CHREC_VARIABLE (chrec), left, CHREC_RIGHT (chrec));
-}
-
/* Observers. */
@@ -1898,7 +1712,7 @@ no_evolution_in_loop_p (tree chrec,
if (chrec == chrec_top)
return false;
- scev = evolution_function_in_loop_num (chrec, loop_num);
+ scev = hide_evolution_in_other_loops_than_loop (chrec, loop_num);
return (TREE_CODE (scev) != POLYNOMIAL_CHREC
&& TREE_CODE (scev) != EXPONENTIAL_CHREC);
}
@@ -2118,710 +1932,6 @@ evolution_function_is_univariate_p (tree
default:
return true;
- }
-}
-
-
-
-/* Analyzers. */
-
-/* This is the ZIV test. ZIV = Zero Index Variable, ie. both
- functions do not depend on the iterations of a loop. */
-
-static inline bool
-ziv_subscript_p (tree chrec_a,
- tree chrec_b)
-{
- return (evolution_function_is_constant_p (chrec_a)
- && evolution_function_is_constant_p (chrec_b));
-}
-
-/* Determines whether the subscript depends on the evolution of a
- single loop or not. SIV = Single Index Variable. */
-
-static bool
-siv_subscript_p (tree chrec_a,
- tree chrec_b)
-{
- if ((evolution_function_is_constant_p (chrec_a)
- && evolution_function_is_univariate_p (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))
- {
- switch (TREE_CODE (chrec_a))
- {
- case POLYNOMIAL_CHREC:
- case EXPONENTIAL_CHREC:
- switch (TREE_CODE (chrec_b))
- {
- case POLYNOMIAL_CHREC:
- case EXPONENTIAL_CHREC:
- if (CHREC_VARIABLE (chrec_a) != CHREC_VARIABLE (chrec_b))
- return false;
-
- default:
- return true;
- }
-
- default:
- return true;
- }
- }
-
- return false;
-}
-
-/* Analyze a ZIV (Zero Index Variable) subscript. */
-
-static void
-analyze_ziv_subscript (tree chrec_a,
- tree chrec_b,
- tree *overlaps_a,
- tree *overlaps_b)
-{
- tree difference;
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "(analyze_ziv_subscript \n");
-
- difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
-
- switch (TREE_CODE (difference))
- {
- case INTEGER_CST:
- 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;
- }
- else
- {
- /* The accesses do not overlap. */
- *overlaps_a = chrec_bot;
- *overlaps_b = chrec_bot;
- }
- break;
-
- case INTERVAL_CHREC:
- if (integer_zerop (CHREC_LOW (difference))
- && integer_zerop (CHREC_UP (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;
- }
- else
- {
- /* There could be an overlap, conservative answer:
- "don't know". */
- *overlaps_a = chrec_top;
- *overlaps_b = chrec_top;
- }
- break;
-
- default:
- /* We're not sure whether the indexes overlap. For the moment,
- conservatively answer "don't know". */
- *overlaps_a = chrec_top;
- *overlaps_b = chrec_top;
- break;
- }
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, ")\n");
-}
-
-/* Analyze single index variable subscript. Note that the dependence
- testing is not commutative, and that's why both versions of
- analyze_siv_subscript_x_y and analyze_siv_subscript_y_x are
- implemented. */
-
-static void
-analyze_siv_subscript (tree chrec_a,
- tree chrec_b,
- tree *overlaps_a,
- tree *overlaps_b)
-{
- 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_p (chrec_b))
- analyze_siv_subscript_cst_affine (chrec_a, chrec_b,
- overlaps_a, overlaps_b);
-
- else if (evolution_function_is_affine_p (chrec_a)
- && evolution_function_is_constant_p (chrec_b))
- analyze_siv_subscript_affine_cst (chrec_a, chrec_b,
- overlaps_a, overlaps_b);
-
- else if (evolution_function_is_affine_p (chrec_a)
- && evolution_function_is_affine_p (chrec_b)
- && (CHREC_VARIABLE (chrec_a) == CHREC_VARIABLE (chrec_b)))
- analyze_siv_subscript_affine_affine (chrec_a, chrec_b,
- overlaps_a, overlaps_b);
- else
- {
- *overlaps_a = chrec_top;
- *overlaps_b = chrec_top;
- }
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, ")\n");
-}
-
-/* This is a part of the SIV subscript analyzer (Single Index
- Variable). */
-
-static void
-analyze_siv_subscript_cst_affine (tree chrec_a,
- tree chrec_b,
- tree *overlaps_a,
- tree *overlaps_b)
-{
- bool value0, value1, value2;
- tree difference = chrec_fold_minus
- (integer_type_node, CHREC_LEFT (chrec_b), chrec_a);
-
- if (!chrec_is_positive (initial_condition (difference), &value0))
- {
- /* Static analysis failed. */
- *overlaps_a = chrec_top;
- *overlaps_b = chrec_top;
- return;
- }
- else
- {
- if (value0 == false)
- {
- if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1))
- {
- /* The static analysis failed. */
- *overlaps_a = chrec_top;
- *overlaps_b = chrec_top;
- return;
- }
- else
- {
- if (value1 == true)
- {
- /* Example:
- chrec_a = 12
- chrec_b = {10, +, 1}
- */
-
- if (tree_fold_divides_p
- (integer_type_node, CHREC_RIGHT (chrec_b), difference))
- {
- *overlaps_a = integer_zero_node;
- *overlaps_b = tree_fold_exact_div
- (integer_type_node,
- tree_fold_abs (integer_type_node, difference),
- CHREC_RIGHT (chrec_b));
- return;
- }
-
- /* When the step does not divides the difference, there are
- no overlaps. */
- else
- {
- *overlaps_a = chrec_bot;
- *overlaps_b = chrec_bot;
- return;
- }
- }
-
- else
- {
- /* Example:
- chrec_a = 12
- chrec_b = {10, +, -1}
-
- In this case, chrec_a will not overlap with chrec_b. */
- *overlaps_a = chrec_bot;
- *overlaps_b = chrec_bot;
- return;
- }
- }
- }
- else
- {
- if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2))
- {
- /* Static analysis failed. */
- *overlaps_a = chrec_top;
- *overlaps_b = chrec_top;
- return;
- }
- else
- {
- if (value2 == false)
- {
- /* Example:
- chrec_a = 3
- chrec_b = {10, +, -1}
- */
- if (tree_fold_divides_p
- (integer_type_node, CHREC_RIGHT (chrec_b), difference))
- {
- *overlaps_a = integer_zero_node;
- *overlaps_b = tree_fold_exact_div
- (integer_type_node, difference, CHREC_RIGHT (chrec_b));
- return;
- }
-
- /* When the step does not divides the difference, there
- are no overlaps. */
- else
- {
- *overlaps_a = chrec_bot;
- *overlaps_b = chrec_bot;
- return;
- }
- }
- else
- {
- /* Example:
- chrec_a = 3
- chrec_b = {4, +, 1}
-
- In this case, chrec_a will not overlap with chrec_b. */
- *overlaps_a = chrec_bot;
- *overlaps_b = chrec_bot;
- return;
- }
- }
- }
- }
-}
-
-/* This is a part of the SIV subscript analyzer (Single Index
- Variable). */
-
-static void
-analyze_siv_subscript_affine_cst (tree chrec_a,
- tree chrec_b,
- tree *overlaps_a,
- tree *overlaps_b)
-{
- analyze_siv_subscript_cst_affine (chrec_b, chrec_a, overlaps_b, overlaps_a);
-}
-
-/* This is a part of the SIV subscript analyzer (Single Index
- Variable). */
-
-static void
-analyze_siv_subscript_affine_affine (tree chrec_a,
- tree chrec_b,
- tree *overlaps_a,
- tree *overlaps_b)
-{
- tree left_a, left_b, right_a, right_b;
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "(analyze_siv_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,
- ie. the solution is positive or zero, and that the solution
- happens before the upper bound loop.nb_iterations. Otherwise
- there is no dependence. This function outputs a description of
- the iterations that hold the intersections. */
-
- left_a = CHREC_LEFT (chrec_a);
- left_b = CHREC_LEFT (chrec_b);
- right_a = CHREC_RIGHT (chrec_a);
- right_b = CHREC_RIGHT (chrec_b);
-
- if (chrec_zerop (chrec_fold_minus (integer_type_node, left_a, left_b)))
- {
- /* The first element accessed twice is on the first
- iteration. */
- *overlaps_a = build_polynomial_chrec
- (CHREC_VARIABLE (chrec_a),
- integer_zero_node, integer_one_node);
- *overlaps_b = build_polynomial_chrec
- (CHREC_VARIABLE (chrec_b),
- integer_zero_node, integer_one_node);
- }
-
- else if (TREE_CODE (left_a) == INTEGER_CST
- && TREE_CODE (left_b) == INTEGER_CST
- && TREE_CODE (right_a) == INTEGER_CST
- && TREE_CODE (right_b) == INTEGER_CST
-
- /* Both functions should have the same evolution sign. */
- && ((tree_int_cst_sgn (right_a) > 0
- && tree_int_cst_sgn (right_b) > 0)
- || (tree_int_cst_sgn (right_a) < 0
- && tree_int_cst_sgn (right_b) < 0)))
- {
- /* Here we have to solve the Diophantine equation. Reference
- book: "Loop Transformations for Restructuring Compilers - The
- Foundations" by Utpal Banerjee, pages 59-80.
-
- ALPHA * X0 = BETA * Y0 + GAMMA.
-
- with:
- ALPHA = RIGHT_A
- BETA = RIGHT_B
- GAMMA = LEFT_B - LEFT_A
- CHREC_A = {LEFT_A, +, RIGHT_A}
- CHREC_B = {LEFT_B, +, RIGHT_B}
-
- The Diophantine equation has a solution if and only if gcd
- (ALPHA, BETA) divides GAMMA. This is commonly known under
- the name of the "gcd-test".
- */
- tree alpha, beta, gamma;
- tree la, lb;
- tree gcd_alpha_beta;
- tree u11, u12, u21, u22;
-
- /* Both alpha and beta have to be integer_type_node. The gcd
- function does not work correctly otherwise. */
- alpha = copy_node (right_a);
- beta = copy_node (right_b);
- la = copy_node (left_a);
- lb = copy_node (left_b);
- TREE_TYPE (alpha) = integer_type_node;
- TREE_TYPE (beta) = integer_type_node;
- TREE_TYPE (la) = integer_type_node;
- TREE_TYPE (lb) = integer_type_node;
-
- gamma = tree_fold_minus (integer_type_node, lb, la);
-
- /* FIXME: Use lambda_*_Hermite for implementing Bezout. */
- gcd_alpha_beta = tree_fold_bezout
- (alpha,
- tree_fold_multiply (integer_type_node, beta, integer_minus_one_node),
- &u11, &u12,
- &u21, &u22);
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, " (alpha = ");
- print_generic_expr (dump_file, alpha, 0);
- fprintf (dump_file, ")\n (beta = ");
- print_generic_expr (dump_file, beta, 0);
- fprintf (dump_file, ")\n (gamma = ");
- print_generic_expr (dump_file, gamma, 0);
- fprintf (dump_file, ")\n (gcd_alpha_beta = ");
- print_generic_expr (dump_file, gcd_alpha_beta, 0);
- fprintf (dump_file, ")\n");
- }
-
- /* The classic "gcd-test". */
- if (!tree_fold_divides_p (integer_type_node, gcd_alpha_beta, gamma))
- {
- /* The "gcd-test" has determined that there is no integer
- solution, ie. there is no dependence. */
- *overlaps_a = chrec_bot;
- *overlaps_b = chrec_bot;
- }
-
- else
- {
- /* The solutions are given by:
- |
- | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [X]
- | [u21 u22] [Y]
-
- 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:
-
- | x = i0 + i1 * t,
- | y = j0 + j1 * t. */
-
- tree i0, j0, i1, j1, t;
- tree gamma_gcd;
-
- /* X0 and Y0 are the first iterations for which there is a
- dependence. X0, Y0 are two solutions of the Diophantine
- equation: chrec_a (X0) = chrec_b (Y0). */
- tree x0, y0;
-
- /* Exact div because in this case gcd_alpha_beta divides
- gamma. */
- gamma_gcd = tree_fold_exact_div
- (integer_type_node, gamma, gcd_alpha_beta);
- i0 = tree_fold_multiply (integer_type_node, u11, gamma_gcd);
- j0 = tree_fold_multiply (integer_type_node, u12, gamma_gcd);
- i1 = u21;
- j1 = u22;
-
- if ((tree_int_cst_sgn (i1) == 0
- && tree_int_cst_sgn (i0) < 0)
- || (tree_int_cst_sgn (j1) == 0
- && tree_int_cst_sgn (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
- upper bound of the iteration domain. */
- *overlaps_a = chrec_bot;
- *overlaps_b = chrec_bot;
- }
-
- else
- {
- if (tree_int_cst_sgn (i1) > 0)
- {
- t = tree_fold_ceil_div
- (integer_type_node,
- tree_fold_multiply (integer_type_node, i0,
- integer_minus_one_node),
- i1);
-
- if (tree_int_cst_sgn (j1) > 0)
- {
- t = tree_fold_max
- (integer_type_node, t,
- tree_fold_ceil_div (integer_type_node,
- tree_fold_multiply
- (integer_type_node, j0,
- integer_minus_one_node),
- j1));
-
- x0 = tree_fold_plus
- (integer_type_node, i0,
- tree_fold_multiply (integer_type_node, i1, t));
- y0 = tree_fold_plus
- (integer_type_node, j0,
- tree_fold_multiply (integer_type_node, j1, t));
-
- *overlaps_a = build_polynomial_chrec
- (CHREC_VARIABLE (chrec_a), x0, u21);
- *overlaps_b = build_polynomial_chrec
- (CHREC_VARIABLE (chrec_b), y0, u22);
- }
- else
- {
- /* FIXME: For the moment, the upper bound of the
- iteration domain for j is not checked. */
- *overlaps_a = chrec_top;
- *overlaps_b = chrec_top;
- }
- }
-
- else
- {
- /* FIXME: For the moment, the upper bound of the
- iteration domain for i is not checked. */
- *overlaps_a = chrec_top;
- *overlaps_b = chrec_top;
- }
- }
- }
- }
-
- else
- {
- /* For the moment, "don't know". */
- *overlaps_a = chrec_top;
- *overlaps_b = chrec_top;
- }
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, " (overlaps_a = ");
- print_generic_expr (dump_file, *overlaps_a, 0);
- fprintf (dump_file, ")\n (overlaps_b = ");
- print_generic_expr (dump_file, *overlaps_b, 0);
- fprintf (dump_file, ")\n");
- }
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, ")\n");
-}
-
-/* Helper for determining whether the evolution steps of an affine
- CHREC divide the constant CST. */
-
-static bool
-chrec_steps_divide_constant_p (tree chrec,
- tree cst)
-{
- 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));
-
- default:
- /* On the initial condition, return true. */
- return true;
- }
-}
-
-/* This is the MIV subscript analyzer (Multiple Index Variable). */
-
-static void
-analyze_miv_subscript (tree chrec_a,
- tree chrec_b,
- tree *overlaps_a,
- tree *overlaps_b)
-{
- /* 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 difference;
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "(analyze_miv_subscript \n");
-
- difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
-
- if (chrec_zerop (difference))
- {
- /* Access functions are the same: all the elements are accessed
- in the same order. */
- *overlaps_a = integer_zero_node;
- *overlaps_b = integer_zero_node;
- }
-
- 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))
- {
- /* 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_bot;
- *overlaps_b = chrec_bot;
- }
-
- else if (evolution_function_is_univariate_p (chrec_a)
- && evolution_function_is_univariate_p (chrec_b))
- {
- /* testsuite/.../ssa-chrec-35.c
- {0, +, 1}_2 vs. {0, +, 1}_3
- the overlapping elements are respectively located at iterations:
- {0, +, 1}_3 and {0, +, 1}_2.
-
- The overlaps are computed by the classic siv tester, then the
- evolution loops are exchanged.
- */
-
- tree fake_b, fake_overlaps_a;
- fake_b = build_polynomial_chrec
- (CHREC_VARIABLE (chrec_a),
- CHREC_LEFT (chrec_b), CHREC_RIGHT (chrec_b));
- /* Analyze the siv. */
- analyze_siv_subscript (chrec_a, fake_b,
- &fake_overlaps_a, overlaps_b);
-
- /* Exchange the variables. */
- if (evolution_function_is_constant_p (*overlaps_b))
- *overlaps_b = build_polynomial_chrec
- (CHREC_VARIABLE (chrec_a), *overlaps_b,
- integer_one_node);
-
- if (evolution_function_is_constant_p (fake_overlaps_a))
- *overlaps_a = build_polynomial_chrec
- (CHREC_VARIABLE (chrec_b), fake_overlaps_a,
- integer_one_node);
-
- else
- *overlaps_a = build_polynomial_chrec
- (CHREC_VARIABLE (chrec_b),
- CHREC_LEFT (fake_overlaps_a),
- CHREC_RIGHT (fake_overlaps_a));
- }
-
- else
- {
- /* When the analysis is too difficult, answer "don't know". */
- *overlaps_a = chrec_top;
- *overlaps_b = chrec_top;
- }
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, ")\n");
-}
-
-/* Determines the iterations for which CHREC_A is equal to CHREC_B.
- OVERLAP_ITERATIONS_A and OVERLAP_ITERATIONS_B are 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)).
-*/
-
-void
-analyze_overlapping_iterations (tree chrec_a,
- tree chrec_b,
- tree *overlap_iterations_a,
- tree *overlap_iterations_b)
-{
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "(analyze_overlapping_iterations \n");
- fprintf (dump_file, " (chrec_a = ");
- print_generic_expr (dump_file, chrec_a, 0);
- fprintf (dump_file, ")\n chrec_b = ");
- print_generic_expr (dump_file, chrec_b, 0);
- fprintf (dump_file, ")\n");
- }
-
- if (chrec_a == NULL_TREE
- || chrec_b == NULL_TREE
- || chrec_contains_undetermined (chrec_a)
- || chrec_contains_undetermined (chrec_b)
- || chrec_contains_symbols (chrec_a)
- || chrec_contains_symbols (chrec_b)
- || chrec_contains_intervals (chrec_a)
- || chrec_contains_intervals (chrec_b))
- {
- *overlap_iterations_a = chrec_top;
- *overlap_iterations_b = chrec_top;
- }
-
- else if (ziv_subscript_p (chrec_a, chrec_b))
- analyze_ziv_subscript (chrec_a, chrec_b,
- overlap_iterations_a, overlap_iterations_b);
-
- else if (siv_subscript_p (chrec_a, chrec_b))
- analyze_siv_subscript (chrec_a, chrec_b,
- overlap_iterations_a, overlap_iterations_b);
-
- else
- analyze_miv_subscript (chrec_a, chrec_b,
- overlap_iterations_a, overlap_iterations_b);
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, " (overlap_iterations_a = ");
- print_generic_expr (dump_file, *overlap_iterations_a, 0);
- fprintf (dump_file, ")\n (overlap_iterations_b = ");
- print_generic_expr (dump_file, *overlap_iterations_b, 0);
- fprintf (dump_file, ")\n");
}
}
Index: tree-chrec.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-chrec.h,v
retrieving revision 1.1.2.9
diff -d -u -p -r1.1.2.9 tree-chrec.h
--- tree-chrec.h 30 Mar 2004 21:06:44 -0000 1.1.2.9
+++ tree-chrec.h 15 Apr 2004 14:47:29 -0000
@@ -90,7 +90,8 @@ extern tree chrec_replace_initial_condit
extern tree update_initial_condition_to_origin (tree);
extern tree initial_condition (tree);
extern tree evolution_part_in_loop_num (tree, unsigned);
-extern tree evolution_function_in_loop_num (tree, unsigned);
+extern tree hide_evolution_in_other_loops_than_loop (tree, unsigned);
+extern tree hide_evolution_in_loop (tree, unsigned);
extern tree reset_evolution_in_loop (unsigned, tree, tree);
extern tree chrec_eval_next_init_cond (unsigned, tree);
extern tree chrec_merge (tree, tree);
@@ -113,9 +114,6 @@ static inline bool symbolic_parameter_ex
static inline bool evolution_function_is_constant_p (tree);
static inline bool evolution_function_is_affine_p (tree);
static inline bool chrec_should_remain_symbolic (tree);
-
-/* Analyzers. */
-extern void analyze_overlapping_iterations (tree, tree, tree *, tree *);
Index: tree-data-ref.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-data-ref.c,v
retrieving revision 1.1.2.14
diff -d -u -p -r1.1.2.14 tree-data-ref.c
--- tree-data-ref.c 30 Mar 2004 21:06:44 -0000 1.1.2.14
+++ tree-data-ref.c 15 Apr 2004 14:47:29 -0000
@@ -72,6 +72,9 @@ Software Foundation, 59 Temple Place - S
- "Advanced Compilation for High Performance Computing" by Randy Allen
and Ken Kennedy.
+ - "Loop Transformations for Restructuring Compilers - The Foundations"
+ by Utpal Banerjee.
+
*/
#include "config.h"
@@ -97,48 +100,12 @@ Software Foundation, 59 Temple Place - S
#include "tree-pass.h"
#include "lambda.h"
-static tree analyze_array_indexes (struct loop *, varray_type, tree);
-static bool access_functions_are_affine_or_constant_p (struct data_reference *);
-
-static struct data_dependence_relation *
-initialize_data_dependence_relation (struct data_reference *,
- struct data_reference *);
-
static void subscript_dependence_tester (struct data_dependence_relation *);
static unsigned int data_ref_id = 0;
-static struct loops *current_loops;
-/* Debugging functions. */
-
-/* Debugging function for a DATA_REFERENCE structure. */
-
-void
-debug_data_reference (struct data_reference *dr)
-{
- dump_data_reference (stderr, dr);
-}
-
-void
-debug_data_references (varray_type dr)
-{
- dump_data_references (stderr, dr);
-}
-
-void
-debug_data_dependence_relation (struct data_dependence_relation *ddr)
-{
- dump_data_dependence_relation (stderr, ddr);
-}
-
-void
-debug_data_dependence_relations (varray_type ddr)
-{
- dump_data_dependence_relations (stderr, ddr);
-}
-
/* Dump into FILE all the data references from DATAREFS. */
void
@@ -321,23 +288,6 @@ dump_data_dependence_direction (FILE *fi
-/* Determine whether the access functions are affine functions, in
- which case the dependence tester can be runned. */
-
-static bool
-access_functions_are_affine_or_constant_p (struct data_reference *a)
-{
- unsigned int i;
- varray_type fns = DR_ACCESS_FNS (a);
-
- for (i = 0; i < VARRAY_ACTIVE_SIZE (fns); i++)
- if (!evolution_function_is_constant_p (VARRAY_TREE (fns, i))
- && !evolution_function_is_affine_multivariate_p (VARRAY_TREE (fns, i)))
- return false;
-
- return true;
-}
-
/* Given an ARRAY_REF node REF, records its access functions.
Example: given A[i][3], record the opnd1 function, ie. the constant
"3", then recursively call the function on opnd0, ie. the ARRAY_REF
@@ -406,52 +356,10 @@ analyze_array (tree stmt,
-/* Initialize a ddr. */
-
-static struct data_dependence_relation *
-initialize_data_dependence_relation (struct data_reference *a,
- struct data_reference *b)
-{
- struct data_dependence_relation *res;
-
- res = ggc_alloc (sizeof (struct data_dependence_relation));
- DDR_A (res) = a;
- DDR_B (res) = b;
-
- /* When the dimensions of A and B differ, we directly initialize
- the relation to "there is no dependence": chrec_bot. */
- if (DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b)
- || array_base_name_differ_p (a, b))
- DDR_ARE_DEPENDENT (res) = chrec_bot;
-
- else
- {
- unsigned int i;
- DDR_ARE_DEPENDENT (res) = NULL_TREE;
- DDR_SUBSCRIPTS_VECTOR_INIT (res, DR_NUM_DIMENSIONS (a));
-
- for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
- {
- struct subscript *subscript;
-
- subscript = ggc_alloc (sizeof (struct subscript));
- SUB_CONFLICTS_IN_A (subscript) = chrec_top;
- SUB_CONFLICTS_IN_B (subscript) = chrec_top;
- SUB_LAST_CONFLICT_IN_A (subscript) = chrec_top;
- SUB_LAST_CONFLICT_IN_B (subscript) = chrec_top;
- SUB_DISTANCE (subscript) = chrec_top;
- SUB_DIRECTION (subscript) = dir_star;
- VARRAY_PUSH_GENERIC_PTR (DDR_SUBSCRIPTS (res), subscript);
- }
- }
-
- return res;
-}
-
/* When there exists a dependence relation, determine its distance
vector. */
-void
+static void
compute_distance_vector (struct data_dependence_relation *ddr)
{
if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
@@ -481,7 +389,7 @@ compute_distance_vector (struct data_dep
/* When there exists a dependence relation, determine its direction
vector. */
-void
+static void
compute_direction_vector (struct data_dependence_relation *ddr)
{
if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
@@ -515,29 +423,748 @@ compute_direction_vector (struct data_de
}
}
-/* Compute all the data dependence relations. */
+/* Initialize a ddr. */
-void
-compute_all_dependences (varray_type datarefs,
- varray_type *dependence_relations)
+static struct data_dependence_relation *
+initialize_data_dependence_relation (struct data_reference *a,
+ struct data_reference *b)
{
- unsigned int i, j;
+ struct data_dependence_relation *res;
- for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
- for (j = 0; j < VARRAY_ACTIVE_SIZE (datarefs); j++)
- {
- struct data_reference *a, *b;
- struct data_dependence_relation *ddr;
+ res = ggc_alloc (sizeof (struct data_dependence_relation));
+ DDR_A (res) = a;
+ DDR_B (res) = b;
+
+ /* When the dimensions of A and B differ, we directly initialize
+ the relation to "there is no dependence": chrec_bot. */
+ if (DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b)
+ || array_base_name_differ_p (a, b))
+ DDR_ARE_DEPENDENT (res) = chrec_bot;
+
+ else
+ {
+ unsigned int i;
+ DDR_ARE_DEPENDENT (res) = NULL_TREE;
+ DDR_SUBSCRIPTS_VECTOR_INIT (res, DR_NUM_DIMENSIONS (a));
+
+ for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
+ {
+ struct subscript *subscript;
+
+ subscript = ggc_alloc (sizeof (struct subscript));
+ SUB_CONFLICTS_IN_A (subscript) = chrec_top;
+ SUB_CONFLICTS_IN_B (subscript) = chrec_top;
+ SUB_LAST_CONFLICT_IN_A (subscript) = chrec_top;
+ SUB_LAST_CONFLICT_IN_B (subscript) = chrec_top;
+ SUB_DISTANCE (subscript) = chrec_top;
+ SUB_DIRECTION (subscript) = dir_star;
+ VARRAY_PUSH_GENERIC_PTR (DDR_SUBSCRIPTS (res), subscript);
+ }
+ }
+
+ return res;
+}
- a = VARRAY_GENERIC_PTR (datarefs, i);
- b = VARRAY_GENERIC_PTR (datarefs, j);
- ddr = initialize_data_dependence_relation (a, b);
-
- VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
- compute_affine_dependence (ddr);
- compute_distance_vector (ddr);
- compute_direction_vector (ddr);
- }
+
+
+/* This section contains the classic Banerjee. The functions are
+ represented by chains of recurrences. */
+
+/* This is the ZIV test. ZIV = Zero Index Variable, ie. both
+ functions do not depend on the iterations of a loop. */
+
+static inline bool
+ziv_subscript_p (tree chrec_a,
+ tree chrec_b)
+{
+ return (evolution_function_is_constant_p (chrec_a)
+ && evolution_function_is_constant_p (chrec_b));
+}
+
+/* Determines whether the subscript depends on the evolution of a
+ single loop or not. SIV = Single Index Variable. */
+
+static bool
+siv_subscript_p (tree chrec_a,
+ tree chrec_b)
+{
+ if ((evolution_function_is_constant_p (chrec_a)
+ && evolution_function_is_univariate_p (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))
+ {
+ switch (TREE_CODE (chrec_a))
+ {
+ case POLYNOMIAL_CHREC:
+ case EXPONENTIAL_CHREC:
+ switch (TREE_CODE (chrec_b))
+ {
+ case POLYNOMIAL_CHREC:
+ case EXPONENTIAL_CHREC:
+ if (CHREC_VARIABLE (chrec_a) != CHREC_VARIABLE (chrec_b))
+ return false;
+
+ default:
+ return true;
+ }
+
+ default:
+ return true;
+ }
+ }
+
+ return false;
+}
+
+/* Analyze a ZIV (Zero Index Variable) subscript. */
+
+static void
+analyze_ziv_subscript (tree chrec_a,
+ tree chrec_b,
+ tree *overlaps_a,
+ tree *overlaps_b)
+{
+ tree difference;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "(analyze_ziv_subscript \n");
+
+ difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
+
+ switch (TREE_CODE (difference))
+ {
+ case INTEGER_CST:
+ 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;
+ }
+ else
+ {
+ /* The accesses do not overlap. */
+ *overlaps_a = chrec_bot;
+ *overlaps_b = chrec_bot;
+ }
+ break;
+
+ case INTERVAL_CHREC:
+ if (integer_zerop (CHREC_LOW (difference))
+ && integer_zerop (CHREC_UP (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;
+ }
+ else
+ {
+ /* There could be an overlap, conservative answer:
+ "don't know". */
+ *overlaps_a = chrec_top;
+ *overlaps_b = chrec_top;
+ }
+ break;
+
+ default:
+ /* We're not sure whether the indexes overlap. For the moment,
+ conservatively answer "don't know". */
+ *overlaps_a = chrec_top;
+ *overlaps_b = chrec_top;
+ break;
+ }
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, ")\n");
+}
+
+/* This is a part of the SIV subscript analyzer (Single Index
+ Variable). */
+
+static void
+analyze_siv_subscript_cst_affine (tree chrec_a,
+ tree chrec_b,
+ tree *overlaps_a,
+ tree *overlaps_b)
+{
+ bool value0, value1, value2;
+ tree difference = chrec_fold_minus
+ (integer_type_node, CHREC_LEFT (chrec_b), chrec_a);
+
+ if (!chrec_is_positive (initial_condition (difference), &value0))
+ {
+ *overlaps_a = chrec_top;
+ *overlaps_b = chrec_top;
+ return;
+ }
+ else
+ {
+ if (value0 == false)
+ {
+ if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1))
+ {
+ *overlaps_a = chrec_top;
+ *overlaps_b = chrec_top;
+ return;
+ }
+ else
+ {
+ if (value1 == true)
+ {
+ /* Example:
+ chrec_a = 12
+ chrec_b = {10, +, 1}
+ */
+
+ if (tree_fold_divides_p
+ (integer_type_node, CHREC_RIGHT (chrec_b), difference))
+ {
+ *overlaps_a = integer_zero_node;
+ *overlaps_b = tree_fold_exact_div
+ (integer_type_node,
+ tree_fold_abs (integer_type_node, difference),
+ CHREC_RIGHT (chrec_b));
+ return;
+ }
+
+ /* When the step does not divides the difference, there are
+ no overlaps. */
+ else
+ {
+ *overlaps_a = chrec_bot;
+ *overlaps_b = chrec_bot;
+ return;
+ }
+ }
+
+ else
+ {
+ /* Example:
+ chrec_a = 12
+ chrec_b = {10, +, -1}
+
+ In this case, chrec_a will not overlap with chrec_b. */
+ *overlaps_a = chrec_bot;
+ *overlaps_b = chrec_bot;
+ return;
+ }
+ }
+ }
+ else
+ {
+ if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2))
+ {
+ *overlaps_a = chrec_top;
+ *overlaps_b = chrec_top;
+ return;
+ }
+ else
+ {
+ if (value2 == false)
+ {
+ /* Example:
+ chrec_a = 3
+ chrec_b = {10, +, -1}
+ */
+ if (tree_fold_divides_p
+ (integer_type_node, CHREC_RIGHT (chrec_b), difference))
+ {
+ *overlaps_a = integer_zero_node;
+ *overlaps_b = tree_fold_exact_div
+ (integer_type_node, difference, CHREC_RIGHT (chrec_b));
+ return;
+ }
+
+ /* When the step does not divides the difference, there
+ are no overlaps. */
+ else
+ {
+ *overlaps_a = chrec_bot;
+ *overlaps_b = chrec_bot;
+ return;
+ }
+ }
+ else
+ {
+ /* Example:
+ chrec_a = 3
+ chrec_b = {4, +, 1}
+
+ In this case, chrec_a will not overlap with chrec_b. */
+ *overlaps_a = chrec_bot;
+ *overlaps_b = chrec_bot;
+ return;
+ }
+ }
+ }
+ }
+}
+
+/* This is a part of the SIV subscript analyzer (Single Index
+ Variable). */
+
+static void
+analyze_siv_subscript_affine_cst (tree chrec_a,
+ tree chrec_b,
+ tree *overlaps_a,
+ tree *overlaps_b)
+{
+ analyze_siv_subscript_cst_affine (chrec_b, chrec_a, overlaps_b, overlaps_a);
+}
+
+/* This is a part of the SIV subscript analyzer (Single Index
+ Variable). */
+
+static void
+analyze_siv_subscript_affine_affine (tree chrec_a,
+ tree chrec_b,
+ tree *overlaps_a,
+ tree *overlaps_b)
+{
+ tree left_a, left_b, right_a, right_b;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "(analyze_siv_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,
+ ie. the solution is positive or zero, and that the solution
+ happens before the upper bound loop.nb_iterations. Otherwise
+ there is no dependence. This function outputs a description of
+ the iterations that hold the intersections. */
+
+ left_a = CHREC_LEFT (chrec_a);
+ left_b = CHREC_LEFT (chrec_b);
+ right_a = CHREC_RIGHT (chrec_a);
+ right_b = CHREC_RIGHT (chrec_b);
+
+ if (chrec_zerop (chrec_fold_minus (integer_type_node, left_a, left_b)))
+ {
+ /* The first element accessed twice is on the first
+ iteration. */
+ *overlaps_a = build_polynomial_chrec
+ (CHREC_VARIABLE (chrec_a),
+ integer_zero_node, integer_one_node);
+ *overlaps_b = build_polynomial_chrec
+ (CHREC_VARIABLE (chrec_b),
+ integer_zero_node, integer_one_node);
+ }
+
+ else if (TREE_CODE (left_a) == INTEGER_CST
+ && TREE_CODE (left_b) == INTEGER_CST
+ && TREE_CODE (right_a) == INTEGER_CST
+ && TREE_CODE (right_b) == INTEGER_CST
+
+ /* Both functions should have the same evolution sign. */
+ && ((tree_int_cst_sgn (right_a) > 0
+ && tree_int_cst_sgn (right_b) > 0)
+ || (tree_int_cst_sgn (right_a) < 0
+ && tree_int_cst_sgn (right_b) < 0)))
+ {
+ /* Here we have to solve the Diophantine equation. Reference
+ book: "Loop Transformations for Restructuring Compilers - The
+ Foundations" by Utpal Banerjee, pages 59-80.
+
+ ALPHA * X0 = BETA * Y0 + GAMMA.
+
+ with:
+ ALPHA = RIGHT_A
+ BETA = RIGHT_B
+ GAMMA = LEFT_B - LEFT_A
+ CHREC_A = {LEFT_A, +, RIGHT_A}
+ CHREC_B = {LEFT_B, +, RIGHT_B}
+
+ The Diophantine equation has a solution if and only if gcd
+ (ALPHA, BETA) divides GAMMA. This is commonly known under
+ the name of the "gcd-test".
+ */
+ tree alpha, beta, gamma;
+ tree la, lb;
+ tree gcd_alpha_beta;
+ tree u11, u12, u21, u22;
+
+ /* Both alpha and beta have to be integer_type_node. The gcd
+ function does not work correctly otherwise. */
+ alpha = copy_node (right_a);
+ beta = copy_node (right_b);
+ la = copy_node (left_a);
+ lb = copy_node (left_b);
+ TREE_TYPE (alpha) = integer_type_node;
+ TREE_TYPE (beta) = integer_type_node;
+ TREE_TYPE (la) = integer_type_node;
+ TREE_TYPE (lb) = integer_type_node;
+
+ gamma = tree_fold_minus (integer_type_node, lb, la);
+
+ /* FIXME: Use lambda_*_Hermite for implementing Bezout. */
+ gcd_alpha_beta = tree_fold_bezout
+ (alpha,
+ tree_fold_multiply (integer_type_node, beta, integer_minus_one_node),
+ &u11, &u12,
+ &u21, &u22);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, " (alpha = ");
+ print_generic_expr (dump_file, alpha, 0);
+ fprintf (dump_file, ")\n (beta = ");
+ print_generic_expr (dump_file, beta, 0);
+ fprintf (dump_file, ")\n (gamma = ");
+ print_generic_expr (dump_file, gamma, 0);
+ fprintf (dump_file, ")\n (gcd_alpha_beta = ");
+ print_generic_expr (dump_file, gcd_alpha_beta, 0);
+ fprintf (dump_file, ")\n");
+ }
+
+ /* The classic "gcd-test". */
+ if (!tree_fold_divides_p (integer_type_node, gcd_alpha_beta, gamma))
+ {
+ /* The "gcd-test" has determined that there is no integer
+ solution, ie. there is no dependence. */
+ *overlaps_a = chrec_bot;
+ *overlaps_b = chrec_bot;
+ }
+
+ else
+ {
+ /* The solutions are given by:
+ |
+ | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [X]
+ | [u21 u22] [Y]
+
+ 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:
+
+ | x = i0 + i1 * t,
+ | y = j0 + j1 * t. */
+
+ tree i0, j0, i1, j1, t;
+ tree gamma_gcd;
+
+ /* X0 and Y0 are the first iterations for which there is a
+ dependence. X0, Y0 are two solutions of the Diophantine
+ equation: chrec_a (X0) = chrec_b (Y0). */
+ tree x0, y0;
+
+ /* Exact div because in this case gcd_alpha_beta divides
+ gamma. */
+ gamma_gcd = tree_fold_exact_div
+ (integer_type_node, gamma, gcd_alpha_beta);
+ i0 = tree_fold_multiply (integer_type_node, u11, gamma_gcd);
+ j0 = tree_fold_multiply (integer_type_node, u12, gamma_gcd);
+ i1 = u21;
+ j1 = u22;
+
+ if ((tree_int_cst_sgn (i1) == 0
+ && tree_int_cst_sgn (i0) < 0)
+ || (tree_int_cst_sgn (j1) == 0
+ && tree_int_cst_sgn (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
+ upper bound of the iteration domain. */
+ *overlaps_a = chrec_bot;
+ *overlaps_b = chrec_bot;
+ }
+
+ else
+ {
+ if (tree_int_cst_sgn (i1) > 0)
+ {
+ t = tree_fold_ceil_div
+ (integer_type_node,
+ tree_fold_multiply (integer_type_node, i0,
+ integer_minus_one_node),
+ i1);
+
+ if (tree_int_cst_sgn (j1) > 0)
+ {
+ t = tree_fold_max
+ (integer_type_node, t,
+ tree_fold_ceil_div (integer_type_node,
+ tree_fold_multiply
+ (integer_type_node, j0,
+ integer_minus_one_node),
+ j1));
+
+ x0 = tree_fold_plus
+ (integer_type_node, i0,
+ tree_fold_multiply (integer_type_node, i1, t));
+ y0 = tree_fold_plus
+ (integer_type_node, j0,
+ tree_fold_multiply (integer_type_node, j1, t));
+
+ *overlaps_a = build_polynomial_chrec
+ (CHREC_VARIABLE (chrec_a), x0, u21);
+ *overlaps_b = build_polynomial_chrec
+ (CHREC_VARIABLE (chrec_b), y0, u22);
+ }
+ else
+ {
+ /* FIXME: For the moment, the upper bound of the
+ iteration domain for j is not checked. */
+ *overlaps_a = chrec_top;
+ *overlaps_b = chrec_top;
+ }
+ }
+
+ else
+ {
+ /* FIXME: For the moment, the upper bound of the
+ iteration domain for i is not checked. */
+ *overlaps_a = chrec_top;
+ *overlaps_b = chrec_top;
+ }
+ }
+ }
+ }
+
+ else
+ {
+ /* For the moment, "don't know". */
+ *overlaps_a = chrec_top;
+ *overlaps_b = chrec_top;
+ }
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, " (overlaps_a = ");
+ print_generic_expr (dump_file, *overlaps_a, 0);
+ fprintf (dump_file, ")\n (overlaps_b = ");
+ print_generic_expr (dump_file, *overlaps_b, 0);
+ fprintf (dump_file, ")\n");
+ }
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, ")\n");
+}
+
+/* Analyze single index variable subscript. Note that the dependence
+ testing is not commutative, and that's why both versions of
+ analyze_siv_subscript_x_y and analyze_siv_subscript_y_x are
+ implemented. */
+
+static void
+analyze_siv_subscript (tree chrec_a,
+ tree chrec_b,
+ tree *overlaps_a,
+ tree *overlaps_b)
+{
+ 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_p (chrec_b))
+ analyze_siv_subscript_cst_affine (chrec_a, chrec_b,
+ overlaps_a, overlaps_b);
+
+ else if (evolution_function_is_affine_p (chrec_a)
+ && evolution_function_is_constant_p (chrec_b))
+ analyze_siv_subscript_affine_cst (chrec_a, chrec_b,
+ overlaps_a, overlaps_b);
+
+ else if (evolution_function_is_affine_p (chrec_a)
+ && evolution_function_is_affine_p (chrec_b)
+ && (CHREC_VARIABLE (chrec_a) == CHREC_VARIABLE (chrec_b)))
+ analyze_siv_subscript_affine_affine (chrec_a, chrec_b,
+ overlaps_a, overlaps_b);
+ else
+ {
+ *overlaps_a = chrec_top;
+ *overlaps_b = chrec_top;
+ }
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, ")\n");
+}
+
+/* Helper for determining whether the evolution steps of an affine
+ CHREC divide the constant CST. */
+
+static bool
+chrec_steps_divide_constant_p (tree chrec,
+ tree cst)
+{
+ 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));
+
+ default:
+ /* On the initial condition, return true. */
+ return true;
+ }
+}
+
+/* This is the MIV subscript analyzer (Multiple Index Variable). */
+
+static void
+analyze_miv_subscript (tree chrec_a,
+ tree chrec_b,
+ tree *overlaps_a,
+ tree *overlaps_b)
+{
+ /* 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 difference;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "(analyze_miv_subscript \n");
+
+ difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
+
+ if (chrec_zerop (difference))
+ {
+ /* Access functions are the same: all the elements are accessed
+ in the same order. */
+ *overlaps_a = integer_zero_node;
+ *overlaps_b = integer_zero_node;
+ }
+
+ 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))
+ {
+ /* 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_bot;
+ *overlaps_b = chrec_bot;
+ }
+
+ else if (evolution_function_is_univariate_p (chrec_a)
+ && evolution_function_is_univariate_p (chrec_b))
+ {
+ /* testsuite/.../ssa-chrec-35.c
+ {0, +, 1}_2 vs. {0, +, 1}_3
+ the overlapping elements are respectively located at iterations:
+ {0, +, 1}_3 and {0, +, 1}_2.
+
+ The overlaps are computed by the classic siv tester, then the
+ evolution loops are exchanged.
+ */
+
+ tree fake_b, fake_overlaps_a;
+ fake_b = build_polynomial_chrec
+ (CHREC_VARIABLE (chrec_a),
+ CHREC_LEFT (chrec_b), CHREC_RIGHT (chrec_b));
+ /* Analyze the siv. */
+ analyze_siv_subscript (chrec_a, fake_b,
+ &fake_overlaps_a, overlaps_b);
+
+ /* Exchange the variables. */
+ if (evolution_function_is_constant_p (*overlaps_b))
+ *overlaps_b = build_polynomial_chrec
+ (CHREC_VARIABLE (chrec_a), *overlaps_b,
+ integer_one_node);
+
+ if (evolution_function_is_constant_p (fake_overlaps_a))
+ *overlaps_a = build_polynomial_chrec
+ (CHREC_VARIABLE (chrec_b), fake_overlaps_a,
+ integer_one_node);
+
+ else
+ *overlaps_a = build_polynomial_chrec
+ (CHREC_VARIABLE (chrec_b),
+ CHREC_LEFT (fake_overlaps_a),
+ CHREC_RIGHT (fake_overlaps_a));
+ }
+
+ else
+ {
+ /* When the analysis is too difficult, answer "don't know". */
+ *overlaps_a = chrec_top;
+ *overlaps_b = chrec_top;
+ }
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, ")\n");
+}
+
+/* Determines the iterations for which CHREC_A is equal to CHREC_B.
+ OVERLAP_ITERATIONS_A and OVERLAP_ITERATIONS_B are 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,
+ tree *overlap_iterations_a,
+ tree *overlap_iterations_b)
+{
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "(analyze_overlapping_iterations \n");
+ fprintf (dump_file, " (chrec_a = ");
+ print_generic_expr (dump_file, chrec_a, 0);
+ fprintf (dump_file, ")\n chrec_b = ");
+ print_generic_expr (dump_file, chrec_b, 0);
+ fprintf (dump_file, ")\n");
+ }
+
+ if (chrec_a == NULL_TREE
+ || chrec_b == NULL_TREE
+ || chrec_contains_undetermined (chrec_a)
+ || chrec_contains_undetermined (chrec_b)
+ || chrec_contains_symbols (chrec_a)
+ || chrec_contains_symbols (chrec_b)
+ || chrec_contains_intervals (chrec_a)
+ || chrec_contains_intervals (chrec_b))
+ {
+ *overlap_iterations_a = chrec_top;
+ *overlap_iterations_b = chrec_top;
+ }
+
+ else if (ziv_subscript_p (chrec_a, chrec_b))
+ analyze_ziv_subscript (chrec_a, chrec_b,
+ overlap_iterations_a, overlap_iterations_b);
+
+ else if (siv_subscript_p (chrec_a, chrec_b))
+ analyze_siv_subscript (chrec_a, chrec_b,
+ overlap_iterations_a, overlap_iterations_b);
+
+ else
+ analyze_miv_subscript (chrec_a, chrec_b,
+ overlap_iterations_a, overlap_iterations_b);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, " (overlap_iterations_a = ");
+ print_generic_expr (dump_file, *overlap_iterations_a, 0);
+ fprintf (dump_file, ")\n (overlap_iterations_b = ");
+ print_generic_expr (dump_file, *overlap_iterations_b, 0);
+ fprintf (dump_file, ")\n");
+ }
}
@@ -616,11 +1243,11 @@ int_cst_value (tree x)
static void
build_classic_dist_vector (struct data_dependence_relation *res,
- varray_type *classic_dist)
+ varray_type *classic_dist,
+ unsigned nb_loops)
{
- unsigned i, nb_loops;
+ unsigned i;
lambda_vector dist_v, init_v;
- nb_loops = current_loops->num;
dist_v = lambda_vector_new (nb_loops);
init_v = lambda_vector_new (nb_loops);
@@ -633,32 +1260,32 @@ build_classic_dist_vector (struct data_d
for (i = 0; i < DDR_NUM_SUBSCRIPTS (res); i++)
{
struct subscript *subscript = DDR_SUBSCRIPT (res, i);
-
- if (SUB_DISTANCE (subscript) != chrec_top)
+
+ if (SUB_DISTANCE (subscript) == chrec_top)
+ return;
+
+ if (TREE_CODE (SUB_CONFLICTS_IN_A (subscript)) == POLYNOMIAL_CHREC)
{
- if (TREE_CODE (SUB_CONFLICTS_IN_A (subscript)) == POLYNOMIAL_CHREC)
+ int dist;
+ unsigned loop_nb;
+ loop_nb = CHREC_VARIABLE (SUB_CONFLICTS_IN_A (subscript));
+ dist = int_cst_value (SUB_DISTANCE (subscript));
+
+ /* This is the subscript coupling test.
+ | loop i = 0, N, 1
+ | T[i+1][i] = ...
+ | ... = T[i][i]
+ | endloop
+ There is no dependence. */
+ if (init_v[loop_nb] != 0
+ && dist_v[loop_nb] != dist)
{
- int dist;
- unsigned loop_nb;
- loop_nb = CHREC_VARIABLE (SUB_CONFLICTS_IN_A (subscript));
- dist = int_cst_value (SUB_DISTANCE (subscript));
-
- /* This is the subscript coupling test.
- | loop i = 0, N, 1
- | T[i+1][i] = ...
- | ... = T[i][i]
- | endloop
- There is no dependence. */
- if (init_v[loop_nb] != 0
- && dist_v[loop_nb] != dist)
- {
- DDR_ARE_DEPENDENT (res) = chrec_bot;
- return;
- }
-
- dist_v[loop_nb] = dist;
- init_v[loop_nb] = 1;
+ DDR_ARE_DEPENDENT (res) = chrec_bot;
+ return;
}
+
+ dist_v[loop_nb] = dist;
+ init_v[loop_nb] = 1;
}
}
@@ -700,6 +1327,106 @@ build_classic_dist_vector (struct data_d
VARRAY_PUSH_GENERIC_PTR (*classic_dist, dist_v);
}
+/* Compute the classic per loop direction vector. */
+
+static void
+build_classic_dir_vector (struct data_dependence_relation *res,
+ varray_type *classic_dir,
+ unsigned nb_loops)
+{
+ unsigned i;
+ lambda_vector dir_v, init_v;
+
+ dir_v = lambda_vector_new (nb_loops);
+ init_v = lambda_vector_new (nb_loops);
+ lambda_vector_clear (dir_v, nb_loops);
+ lambda_vector_clear (init_v, nb_loops);
+
+ if (DDR_ARE_DEPENDENT (res) != NULL_TREE)
+ return;
+
+ for (i = 0; i < DDR_NUM_SUBSCRIPTS (res); i++)
+ {
+ struct subscript *subscript = DDR_SUBSCRIPT (res, i);
+
+ if (TREE_CODE (SUB_CONFLICTS_IN_A (subscript)) == POLYNOMIAL_CHREC
+ && TREE_CODE (SUB_CONFLICTS_IN_B (subscript)) == POLYNOMIAL_CHREC)
+ {
+ unsigned loop_nb = CHREC_VARIABLE (SUB_CONFLICTS_IN_A (subscript));
+ enum data_dependence_direction dir = dir_star;
+
+ if (SUB_DISTANCE (subscript) == chrec_top)
+ {
+
+ }
+ else
+ {
+ int dist = int_cst_value (SUB_DISTANCE (subscript));
+
+ if (dist == 0)
+ dir = dir_equal;
+ else if (dist > 0)
+ dir = dir_positive;
+ else if (dist < 0)
+ dir = dir_negative;
+ }
+
+ /* This is the subscript coupling test.
+ | loop i = 0, N, 1
+ | T[i+1][i] = ...
+ | ... = T[i][i]
+ | endloop
+ There is no dependence. */
+ if (init_v[loop_nb] != 0
+ && (enum data_dependence_direction) dir_v[loop_nb] != dir)
+ {
+ DDR_ARE_DEPENDENT (res) = chrec_bot;
+ return;
+ }
+
+ dir_v[loop_nb] = dir;
+ init_v[loop_nb] = 1;
+ }
+ }
+
+ /* There is a distance of 1 on all the outer loops:
+
+ Example: there is a dependence of distance 1 on loop_1 for the array A.
+ | loop_1
+ | A[5] = ...
+ | endloop
+ */
+ {
+ struct loop *lca, *loop_a, *loop_b;
+ struct data_reference *a = DDR_A (res);
+ struct data_reference *b = DDR_B (res);
+
+ loop_a = loop_of_stmt (DR_STMT (a));
+ loop_b = loop_of_stmt (DR_STMT (b));
+
+ /* Get the common ancestor loop. */
+ lca = find_common_loop (loop_a, loop_b);
+
+ /* For each outer_loop where init_v is not set, the accesses are
+ in dependence of distance 1 in the loop. */
+ if (lca != loop_a
+ && lca != loop_b
+ && init_v[loop_num (lca)] == 0)
+ dir_v[loop_num (lca)] = dir_positive;
+
+ lca = outer_loop (lca);
+ if (lca)
+ while (loop_depth (lca) != 0)
+ {
+ if (init_v[loop_num (lca)] == 0)
+ dir_v[loop_num (lca)] = dir_positive;
+ lca = outer_loop (lca);
+ }
+ }
+
+ VARRAY_PUSH_GENERIC_PTR (*classic_dir, dir_v);
+}
+
/* For all the subscripts, set the same value: CHREC. */
static void
@@ -723,6 +1450,23 @@ set_all_subscripts_to (struct data_depen
}
}
+/* Determine whether the access functions are affine functions, in
+ which case the dependence tester can be runned. */
+
+static bool
+access_functions_are_affine_or_constant_p (struct data_reference *a)
+{
+ unsigned int i;
+ varray_type fns = DR_ACCESS_FNS (a);
+
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (fns); i++)
+ if (!evolution_function_is_constant_p (VARRAY_TREE (fns, i))
+ && !evolution_function_is_affine_multivariate_p (VARRAY_TREE (fns, i)))
+ return false;
+
+ return true;
+}
+
/* This computes the affine dependence relation between A and B.
CHREC_BOT is used for representing the independence between two
accesses, while CHREC_TOP is used for representing the unknown
@@ -732,7 +1476,7 @@ set_all_subscripts_to (struct data_depen
relation the first time we detect a CHREC_BOT element for a given
subscript. */
-void
+static void
compute_affine_dependence (struct data_dependence_relation *ddr)
{
struct data_reference *dra = DDR_A (ddr);
@@ -773,26 +1517,50 @@ compute_affine_dependence (struct data_d
fprintf (dump_file, ")\n");
}
-
+/* Compute all the data dependence relations. */
-/* This section contains all the entry points. */
+static void
+compute_all_dependences (varray_type datarefs,
+ varray_type *dependence_relations)
+{
+ unsigned int i, j;
+
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
+ for (j = 0; j < VARRAY_ACTIVE_SIZE (datarefs); j++)
+ {
+ struct data_reference *a, *b;
+ struct data_dependence_relation *ddr;
-/* Entry point. Search the data references in a loop nest. Record
- the information into a list of DATA_REFERENCE structures.
+ a = VARRAY_GENERIC_PTR (datarefs, i);
+ b = VARRAY_GENERIC_PTR (datarefs, j);
+ ddr = initialize_data_dependence_relation (a, b);
+
+ VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
+ compute_affine_dependence (ddr);
+ compute_distance_vector (ddr);
+ compute_direction_vector (ddr);
+ }
+}
+
+/* Search the data references in LOOP, and record the information into
+ DATAREFS.
FIXME: This is a "dumb" walker over all the trees in the loop body.
Find another technique that avoids this costly walk. This is
acceptable for the moment, since this function is used only for
debugging purposes. */
-void
-find_data_references (varray_type *datarefs)
+static void
+find_data_references_in_loop (struct loop *loop, varray_type *datarefs)
{
basic_block bb;
block_stmt_iterator bsi;
FOR_EACH_BB (bb)
{
+ if (!flow_bb_inside_loop_p (loop, bb))
+ continue;
+
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
tree expr = bsi_stmt (bsi);
@@ -835,6 +1603,35 @@ find_data_references (varray_type *datar
}
}
+
+
+/* This section contains all the entry points. */
+
+/* Yet another entry point. "Give me a loop nest, I will return you a
+ set of distance/direction vectors." */
+
+void
+compute_data_dependences_for_loop (unsigned nb_loops,
+ struct loop *loop,
+ varray_type *datarefs,
+ varray_type *dependence_relations,
+ varray_type *classic_dist,
+ varray_type *classic_dir)
+{
+ unsigned int i;
+
+ find_data_references_in_loop (loop, datarefs);
+ compute_all_dependences (*datarefs, dependence_relations);
+
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (*dependence_relations); i++)
+ {
+ struct data_dependence_relation *ddr;
+ ddr = VARRAY_GENERIC_PTR (*dependence_relations, i);
+ build_classic_dist_vector (ddr, classic_dist, nb_loops);
+ build_classic_dir_vector (ddr, classic_dir, nb_loops);
+ }
+}
+
/* Entry point. Analyze all the data references and the dependence
relations.
@@ -863,33 +1660,32 @@ analyze_all_data_dependences (struct loo
unsigned int i;
varray_type datarefs;
varray_type dependence_relations;
- varray_type classic_dist;
- int nb_data_refs;
-
- current_loops = loops;
-
+ varray_type classic_dist, classic_dir;
+ int nb_data_refs = 10;
+
+#if 0
+ dump_file = stderr;
+ dump_flags = 31;
+#endif
+
VARRAY_GENERIC_PTR_INIT (classic_dist, 10, "classic_dist");
- VARRAY_GENERIC_PTR_INIT (datarefs, 10, "datarefs");
- find_data_references (&datarefs);
- nb_data_refs = VARRAY_ACTIVE_SIZE (datarefs);
+ VARRAY_GENERIC_PTR_INIT (classic_dir, 10, "classic_dir");
+ VARRAY_GENERIC_PTR_INIT (datarefs, nb_data_refs, "datarefs");
VARRAY_GENERIC_PTR_INIT (dependence_relations,
nb_data_refs * nb_data_refs,
"dependence_relations");
- compute_all_dependences (datarefs, &dependence_relations);
- for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
- {
- struct data_dependence_relation *ddr;
- ddr = VARRAY_GENERIC_PTR (dependence_relations, i);
- build_classic_dist_vector (ddr, &classic_dist);
- }
-
- if (dump_file && (dump_flags & TDF_DETAILS))
+ /* Compute DDs on the whole function. */
+ compute_data_dependences_for_loop (loops->num, loop_from_num (loops, 0),
+ &datarefs, &dependence_relations,
+ &classic_dist, &classic_dir);
+
+ if (dump_file)
{
dump_data_dependence_relations (dump_file, dependence_relations);
fprintf (dump_file, "\n\n");
}
-
+
/* Don't dump distances in order to avoid to update the
testsuite. */
if (dump_file && (dump_flags & TDF_DETAILS))
@@ -899,7 +1695,15 @@ analyze_all_data_dependences (struct loo
fprintf (dump_file, "DISTANCE_V (");
print_lambda_vector (dump_file,
VARRAY_GENERIC_PTR (classic_dist, i),
- current_loops->num);
+ loops->num);
+ fprintf (dump_file, ")\n");
+ }
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (classic_dir); i++)
+ {
+ fprintf (dump_file, "DIRECTION_V (");
+ print_lambda_vector (dump_file,
+ VARRAY_GENERIC_PTR (classic_dir, i),
+ loops->num);
fprintf (dump_file, ")\n");
}
fprintf (dump_file, "\n\n");
@@ -910,7 +1714,6 @@ analyze_all_data_dependences (struct loo
unsigned nb_top_relations = 0;
unsigned nb_bot_relations = 0;
unsigned nb_basename_differ = 0;
- unsigned nb_non_distance_relations = 0;
unsigned nb_chrec_relations = 0;
for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
@@ -932,31 +1735,16 @@ analyze_all_data_dependences (struct loo
else
nb_bot_relations++;
}
-
+
else
- {
- unsigned j;
-
- nb_chrec_relations++;
-
- for (j = 0; j < DDR_NUM_SUBSCRIPTS (ddr); j++)
- {
- struct subscript *subscript = DDR_SUBSCRIPT (ddr, j);
-
- if (SUB_DISTANCE (subscript) == chrec_top)
- {
- nb_non_distance_relations++;
- break;
- }
- }
- }
+ nb_chrec_relations++;
}
fprintf (dump_file, "\n(\n");
fprintf (dump_file, "%d\tnb_top_relations\n", nb_top_relations);
fprintf (dump_file, "%d\tnb_bot_relations\n", nb_bot_relations);
fprintf (dump_file, "%d\tnb_basename_differ\n", nb_basename_differ);
- fprintf (dump_file, "%d\tnb_non_distance_relations\n", nb_non_distance_relations);
+ fprintf (dump_file, "%d\tnb_distance_relations\n", (int) VARRAY_ACTIVE_SIZE (classic_dist));
fprintf (dump_file, "%d\tnb_chrec_relations\n", nb_chrec_relations);
fprintf (dump_file, "\n)\n");
@@ -966,5 +1754,7 @@ analyze_all_data_dependences (struct loo
varray_clear (dependence_relations);
varray_clear (datarefs);
varray_clear (classic_dist);
+ varray_clear (classic_dir);
}
+
Index: tree-data-ref.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-data-ref.h,v
retrieving revision 1.1.2.8
diff -d -u -p -r1.1.2.8 tree-data-ref.h
--- tree-data-ref.h 23 Mar 2004 20:13:28 -0000 1.1.2.8
+++ tree-data-ref.h 15 Apr 2004 14:47:29 -0000
@@ -138,16 +138,11 @@ struct data_dependence_relation GTY(())
extern void analyze_all_data_dependences (struct loops *);
-extern void find_data_references (varray_type *);
-
-extern void compute_distance_vector (struct data_dependence_relation *);
-extern void compute_direction_vector (struct data_dependence_relation *);
-extern void compute_affine_dependence (struct data_dependence_relation *);
+extern void compute_data_dependences_for_loop (unsigned, struct loop *,
+ varray_type *, varray_type *,
+ varray_type *, varray_type *);
+extern struct data_reference *analyze_array (tree, tree);
-extern void debug_data_reference (struct data_reference *);
-extern void debug_data_references (varray_type);
-extern void debug_data_dependence_relation (struct data_dependence_relation *);
-extern void debug_data_dependence_relations (varray_type);
extern void dump_data_reference (FILE *, struct data_reference *);
extern void dump_data_references (FILE *, varray_type);
@@ -156,8 +151,6 @@ extern void dump_data_dependence_relatio
extern void dump_data_dependence_relations (FILE *, varray_type);
extern void dump_data_dependence_direction (FILE *,
enum data_dependence_direction);
-extern void compute_all_dependences (varray_type, varray_type *);
-extern struct data_reference *analyze_array (tree, tree);
@@ -184,8 +177,5 @@ array_base_name_differ_p (struct data_re
return true;
}
-
-/* Flag to indicate availability of dependency info. */
-extern bool dd_info_available;
#endif /* GCC_TREE_DATA_REF_H */
Index: tree-dg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-dg.c,v
retrieving revision 1.1.2.7
diff -d -u -p -r1.1.2.7 tree-dg.c
--- tree-dg.c 23 Mar 2004 20:13:28 -0000 1.1.2.7
+++ tree-dg.c 15 Apr 2004 14:47:30 -0000
@@ -60,7 +60,6 @@ static dependence_node alloc_dependence_
static dependence_edge alloc_dependence_edge (void);
static dependence_node dg_create_node (tree);
static dependence_edge dg_find_edge (dependence_node, dependence_node, bool);
-static bool gate_ddg (void);
static void dump_dg (FILE *, int);
static void dg_delete_edges (void);
static void dg_delete_node (dependence_node);
@@ -73,6 +72,8 @@ static int dependence_graph_size = 25;
static GTY (()) varray_type dependence_graph;
static GTY (()) varray_type datarefs;
static GTY (()) varray_type dependence_relations;
+static GTY (()) varray_type classic_dist;
+static GTY (()) varray_type classic_dir;
/* Total dependence node count. */
static int n_dependence_node = 0;
@@ -87,21 +88,21 @@ void dg_init_graph (void)
}
/* Create dependency graph. */
-void dg_create_graph (void)
+void dg_create_graph (struct loops *loops)
{
unsigned int i;
- int nb_data_refs;
+ VARRAY_GENERIC_PTR_INIT (classic_dist, 10, "classic_dist");
+ VARRAY_GENERIC_PTR_INIT (classic_dir, 10, "classic_dir");
VARRAY_GENERIC_PTR_INIT (datarefs, 10, "datarefs");
- find_data_references (&datarefs);
- nb_data_refs = VARRAY_ACTIVE_SIZE (datarefs);
- VARRAY_GENERIC_PTR_INIT (dependence_relations,
- nb_data_refs * nb_data_refs,
+ VARRAY_GENERIC_PTR_INIT (dependence_relations, 10 * 10,
"dependence_relations");
/* Analyze data references and dependence relations using scev. */
- compute_all_dependences (datarefs, &dependence_relations);
+ compute_data_dependences_for_loop (loops->num, loop_from_num (loops, 0),
+ &datarefs, &dependence_relations,
+ &classic_dist, &classic_dir);
/* Initialize. */
dg_init_graph ();
@@ -142,7 +143,6 @@ void dg_create_graph (void)
{
dump_dg (dump_file, dump_flags);
}
-
}
/* Delete data dependence graph. */
@@ -165,6 +165,12 @@ dg_delete_graph (void)
if (dependence_relations)
VARRAY_CLEAR (dependence_relations);
+ if (classic_dir)
+ VARRAY_CLEAR (classic_dir);
+
+ if (classic_dist)
+ VARRAY_CLEAR (classic_dist);
+
/* Clear dependence graph itself. */
VARRAY_CLEAR (dependence_graph);
@@ -507,56 +513,6 @@ ddg_distance_between_stmts (tree stmt1,
return SUB_DISTANCE (sub);
}
-
-
-
-/*---------------------------------------------------------------------------
- Pass management
----------------------------------------------------------------------------*/
-
-static bool
-gate_ddg (void)
-{
- return dd_info_available && flag_ddg && flag_scalar_evolutions != 0;
-}
-
-struct tree_opt_pass pass_ddg =
-{
- "ddg", /* name */
- gate_ddg, /* gate */
- dg_create_graph, /* execute */
- NULL, /* sub */
- NULL, /* next */
- 0, /* static_pass_number */
- TV_DEP_GRAPH, /* tv_id */
- PROP_scev, /* properties_required */
- 0, /* properties_provided */
- 0, /* properties_destroyed */
- 0, /* todo_flags_start */
- 0 /* todo_flags_finish */
-};
-
-static bool
-gate_delete_ddg (void)
-{
- return flag_ddg && flag_scalar_evolutions != 0 && dependence_graph;
-}
-
-struct tree_opt_pass pass_delete_ddg =
-{
- "delete ddg", /* name */
- gate_delete_ddg, /* gate */
- dg_delete_graph, /* execute */
- NULL, /* sub */
- NULL, /* next */
- 0, /* static_pass_number */
- TV_DEP_GRAPH, /* tv_id */
- 0, /* properties_required */
- 0, /* properties_provided */
- 0, /* properties_destroyed */
- 0, /* todo_flags_start */
- 0 /* todo_flags_finish */
-};
/*---------------------------------------------------------------------------
Printing and debugging
Index: tree-dg.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-dg.h,v
retrieving revision 1.1.2.3
diff -d -u -p -r1.1.2.3 tree-dg.h
--- tree-dg.h 21 Feb 2004 01:09:47 -0000 1.1.2.3
+++ tree-dg.h 15 Apr 2004 14:47:30 -0000
@@ -67,7 +67,7 @@ typedef struct dependence_node_def *depe
#define DN_ID(node) (node->node_id)
/* Create dependency graph. */
-extern void dg_create_graph (void);
+extern void dg_create_graph (struct loops *);
/* Delete dependency graph. */
extern void dg_delete_graph (void);
Index: tree-elim-check.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-elim-check.c,v
retrieving revision 1.1.2.5
diff -d -u -p -r1.1.2.5 tree-elim-check.c
--- tree-elim-check.c 30 Mar 2004 21:06:44 -0000 1.1.2.5
+++ tree-elim-check.c 15 Apr 2004 14:47:30 -0000
@@ -212,7 +212,7 @@ try_eliminate_check (tree cond)
if (automatically_generated_chrec_p (nb_iters))
return;
-
+
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "(try_eliminate_check \n");
Index: tree-fold-const.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-fold-const.h,v
retrieving revision 1.1.2.6
diff -d -u -p -r1.1.2.6 tree-fold-const.h
--- tree-fold-const.h 30 Mar 2004 17:45:52 -0000 1.1.2.6
+++ tree-fold-const.h 15 Apr 2004 14:47:30 -0000
@@ -39,30 +39,6 @@ extern tree tree_fold_factorial (tree);
-/* When computing on chrecs, determine the type of the result from the
- types TYPE0 and TYPE1 of the operands. */
-
-static inline tree
-chrec_merge_types (tree type0,
- tree type1)
-{
- if (type0 == type1)
- return type0;
-
- if (type0 == char_type_node
- || type1 == char_type_node)
- return char_type_node;
-
- if (type0 == integer_type_node
- || type1 == integer_type_node)
- return integer_type_node;
-
- /* FIXME. */
- return type0;
-}
-
-
-
/* Fold the addition. */
static inline tree
Index: tree-scalar-evolution.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-scalar-evolution.c,v
retrieving revision 1.1.2.30
diff -d -u -p -r1.1.2.30 tree-scalar-evolution.c
--- tree-scalar-evolution.c 15 Apr 2004 01:01:47 -0000 1.1.2.30
+++ tree-scalar-evolution.c 15 Apr 2004 14:47:30 -0000
@@ -306,17 +306,6 @@ static struct loops *current_loops;
static varray_type scalar_evolution_info;
static varray_type already_instantiated;
-/* Statistics counters. */
-static unsigned stats_nb_chrecs = 0;
-static unsigned stats_nb_peeled_affine = 0;
-static unsigned stats_nb_affine = 0;
-static unsigned stats_nb_affine_multivar = 0;
-static unsigned stats_nb_higher_poly = 0;
-static unsigned stats_nb_expo = 0;
-static unsigned stats_nb_chrec_top = 0;
-static unsigned stats_nb_interval_chrec = 0;
-static unsigned stats_nb_undetermined = 0;
-
/* Flag to indicate availability of dependency info. */
bool dd_info_available;
@@ -377,43 +366,6 @@ loop_phi_node_p (tree phi)
return loop_of_stmt (phi)->header == bb_for_stmt (phi);
}
-/* Select the evolution function in the current LOOP and in the
- outer containing loops. */
-
-static tree
-select_outer_and_current_evolutions (struct loop *loop, tree chrec)
-{
- switch (TREE_CODE (chrec))
- {
- case POLYNOMIAL_CHREC:
- if (flow_loop_nested_p (loop_from_num (current_loops,
- CHREC_VARIABLE (chrec)),
- loop))
- return build_polynomial_chrec
- (CHREC_VARIABLE (chrec),
- select_outer_and_current_evolutions (loop, CHREC_LEFT (chrec)),
- select_outer_and_current_evolutions (loop, CHREC_RIGHT (chrec)));
-
- else
- return select_outer_and_current_evolutions (loop, CHREC_LEFT (chrec));
-
- case EXPONENTIAL_CHREC:
- if (flow_loop_nested_p (loop_from_num (current_loops,
- CHREC_VARIABLE (chrec)),
- loop))
- return build_exponential_chrec
- (CHREC_VARIABLE (chrec),
- select_outer_and_current_evolutions (loop, CHREC_LEFT (chrec)),
- select_outer_and_current_evolutions (loop, CHREC_RIGHT (chrec)));
-
- else
- return select_outer_and_current_evolutions (loop, CHREC_LEFT (chrec));
-
- default:
- return chrec;
- }
-}
-
/* Compute the overall effect of a LOOP on a variable.
1. compute the number of iterations in the loop,
2. compute the value of the variable after crossing the loop.
@@ -1181,7 +1133,7 @@ first_iteration_non_satisfying_noev_ev (
tree init0, init1, step1;
tree nb_iters;
- ev_in_this_loop = evolution_function_in_loop_num (chrec1, loop_nb);
+ ev_in_this_loop = hide_evolution_in_other_loops_than_loop (chrec1, loop_nb);
if (!evolution_function_is_affine_p (ev_in_this_loop))
/* For the moment handle only polynomials of degree 1. */
return chrec_top;
@@ -1438,7 +1390,7 @@ first_iteration_non_satisfying_ev_noev (
tree init0, init1, step0;
tree nb_iters;
- ev_in_this_loop = evolution_function_in_loop_num (chrec0, loop_nb);
+ ev_in_this_loop = hide_evolution_in_other_loops_than_loop (chrec0, loop_nb);
if (!evolution_function_is_affine_p (ev_in_this_loop))
/* For the moment handle only polynomials of degree 1. */
return chrec_top;
@@ -1710,6 +1662,8 @@ first_iteration_non_satisfying_1 (enum t
tree chrec0,
tree chrec1)
{
+ tree res, other_evs;
+
if (automatically_generated_chrec_p (chrec0)
|| automatically_generated_chrec_p (chrec1))
return chrec_top;
@@ -1718,21 +1672,40 @@ first_iteration_non_satisfying_1 (enum t
{
if (no_evolution_in_loop_p (chrec1, loop_nb))
return first_iteration_non_satisfying_noev_noev (code, loop_nb,
- chrec0, chrec1);
+ chrec0, chrec1);
else
- return first_iteration_non_satisfying_noev_ev (code, loop_nb,
- chrec0, chrec1);
+ {
+ res = first_iteration_non_satisfying_noev_ev (code, loop_nb,
+ chrec0, chrec1);
+ if (res == chrec_top)
+ return res;
+
+ other_evs = hide_evolution_in_loop (chrec1, loop_nb);
+ other_evs = chrec_replace_initial_condition
+ (other_evs, convert (chrec_type (other_evs), integer_zero_node));
+ }
}
else
{
if (no_evolution_in_loop_p (chrec1, loop_nb))
- return first_iteration_non_satisfying_ev_noev (code, loop_nb,
- chrec0, chrec1);
+ {
+ res = first_iteration_non_satisfying_ev_noev (code, loop_nb,
+ chrec0, chrec1);
+ if (res == chrec_top)
+ return res;
+
+ other_evs = hide_evolution_in_loop (chrec0, loop_nb);
+ other_evs = chrec_replace_initial_condition
+ (other_evs, convert (chrec_type (other_evs), integer_zero_node));
+ }
else
return first_iteration_non_satisfying_ev_ev (code, loop_nb,
chrec0, chrec1);
}
+
+ res = chrec_fold_minus (chrec_type (res), res, other_evs);
+ return res;
}
/* Try to compute the first iteration I of LOOP_NB that does not satisfy
@@ -1790,18 +1763,6 @@ first_iteration_non_satisfying (enum tre
/* Helper function. */
static inline tree
-cannot_analyze_loop_nb_iterations_yet (void)
-{
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, " (nb_iterations cannot be determined))\n");
-
- /* Do not update the loop->nb_iterations. */
- return chrec_top;
-}
-
-/* Helper function. */
-
-static inline tree
set_nb_iterations_in_loop (struct loop *loop,
tree res)
{
@@ -2330,9 +2291,36 @@ follow_ssa_edge_inner_loop_phi (struct l
tree *evolution_of_loop)
{
struct loop *loop = loop_of_stmt (loop_phi_node);
- tree ev = compute_overall_effect_of_inner_loop (loop,
- PHI_RESULT (loop_phi_node));
+ tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node));
+
+ /* Sometimes, the inner loop is too difficult to analyze, and the
+ result of the analysis is a symbolic parameter. */
+ if (ev == PHI_RESULT (loop_phi_node))
+ {
+ bool res = false;
+ int i;
+
+ for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
+ {
+ tree arg = PHI_ARG_DEF (loop_phi_node, i);
+ basic_block bb;
+
+ /* Follow the edges that exit the inner loop. */
+ bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
+ if (!flow_bb_inside_loop_p (loop, bb))
+ res = res || follow_ssa_edge_in_rhs (outer_loop, arg, halting_phi,
+ evolution_of_loop);
+ }
+
+ /* If the path crosses this loop-phi, give up. */
+ if (res == true)
+ *evolution_of_loop = chrec_top;
+ return res;
+ }
+
+ /* Otherwise, compute the overall effect of the inner loop. */
+ ev = compute_overall_effect_of_inner_loop (loop, ev);
return follow_ssa_edge_in_rhs (outer_loop, ev, halting_phi,
evolution_of_loop);
}
@@ -2812,6 +2800,15 @@ instantiate_parameters (struct loop *loo
{
tree res, op0, op1, op2;
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "(instantiate_parameters \n");
+ fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
+ fprintf (dump_file, " (chrec = ");
+ print_generic_expr (dump_file, chrec, 0);
+ fprintf (dump_file, ")\n");
+ }
+
if (chrec == NULL_TREE
|| automatically_generated_chrec_p (chrec))
res = chrec;
@@ -2835,6 +2832,7 @@ instantiate_parameters (struct loop *loo
else
{
+ VARRAY_PUSH_TREE (already_instantiated, chrec);
res = analyze_scalar_evolution (loop, chrec);
/* If the analysis yields a parametric chrec, instantiate
@@ -2842,11 +2840,9 @@ instantiate_parameters (struct loop *loo
never be instantiated twice, avoiding the cyclic
instantiation in mixers. */
if (chrec_contains_symbols (res))
- {
- VARRAY_PUSH_TREE (already_instantiated, chrec);
- res = instantiate_parameters (loop, res);
- VARRAY_POP (already_instantiated);
- }
+ res = instantiate_parameters (loop, res);
+
+ VARRAY_POP (already_instantiated);
}
}
else
@@ -2944,6 +2940,13 @@ instantiate_parameters (struct loop *loo
break;
}
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, " (res = ");
+ print_generic_expr (dump_file, res, 0);
+ fprintf (dump_file, "))\n");
+ }
+
return res;
}
@@ -2970,11 +2973,12 @@ instantiate_parameters (struct loop *loo
tree
number_of_iterations_in_loop (struct loop *loop)
{
+ enum tree_code code;
tree res;
tree cond, test, opnd0, opnd1;
tree chrec0, chrec1;
edge exit;
-
+
/* Determine whether the number_of_iterations_in_loop has already
been computed. */
res = loop_nb_iterations (loop);
@@ -2993,34 +2997,20 @@ number_of_iterations_in_loop (struct loo
if (exit->flags & EDGE_TRUE_VALUE)
test = invert_truthvalue (test);
- switch (TREE_CODE (test))
+ code = TREE_CODE (test);
+ switch (code)
{
case SSA_NAME:
/* "while (opnd0 != 0)". */
+ code = NE_EXPR;
chrec0 = analyze_scalar_evolution (loop, test);
chrec1 = integer_zero_node;
-
+
if (chrec0 == chrec_top)
/* KEEP_IT_SYMBOLIC. */
chrec0 = test;
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
- fprintf (dump_file, " (loop_while_expr_is_true: ");
- print_generic_expr (dump_file, test, 0);
- fprintf (dump_file, ")\n (chrec0 = ");
- print_generic_expr (dump_file, chrec0, 0);
- fprintf (dump_file, ")\n");
- }
-
- if (chrec_contains_undetermined (chrec0))
- return cannot_analyze_loop_nb_iterations_yet ();
-
- else
- return set_nb_iterations_in_loop
- (loop, first_iteration_non_satisfying (NE_EXPR, loop->num,
- chrec0, chrec1));
+
+ goto end;
case LT_EXPR:
case LE_EXPR:
@@ -3043,29 +3033,39 @@ number_of_iterations_in_loop (struct loo
if (chrec1 == chrec_top)
/* KEEP_IT_SYMBOLIC. */
chrec1 = opnd1;
+
+ goto end;
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
- fprintf (dump_file, " (loop_while_expr_is_true: ");
- print_generic_expr (dump_file, test, 0);
- fprintf (dump_file, ")\n (chrec0 = ");
- print_generic_expr (dump_file, chrec0, 0);
- fprintf (dump_file, ")\n (chrec1 = ");
- print_generic_expr (dump_file, chrec1, 0);
- fprintf (dump_file, ")\n");
- }
-
- if (chrec_contains_undetermined (chrec0)
- || chrec_contains_undetermined (chrec1))
- return cannot_analyze_loop_nb_iterations_yet ();
-
- return set_nb_iterations_in_loop
- (loop, first_iteration_non_satisfying (TREE_CODE (test), loop->num,
- chrec0, chrec1));
default:
return set_nb_iterations_in_loop (loop, chrec_top);
}
+
+ end:
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
+ fprintf (dump_file, " (loop_while_expr_is_true: ");
+ print_generic_expr (dump_file, test, 0);
+ fprintf (dump_file, ")\n (chrec0 = ");
+ print_generic_expr (dump_file, chrec0, 0);
+ fprintf (dump_file, ")\n (chrec1 = ");
+ print_generic_expr (dump_file, chrec1, 0);
+ fprintf (dump_file, ")\n");
+ }
+
+ if (chrec_contains_undetermined (chrec0)
+ || chrec_contains_undetermined (chrec1))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, " (nb_iterations cannot be determined))\n");
+
+ /* Do not update the loop->nb_iterations. */
+ return chrec_top;
+ }
+
+ res = first_iteration_non_satisfying (code, loop->num, chrec0, chrec1);
+
+ return set_nb_iterations_in_loop (loop, res);
}
/* One of the drivers for testing the scalar evolutions analysis.
@@ -3076,92 +3076,162 @@ static void
number_of_iterations_for_all_loops (varray_type exit_conditions)
{
unsigned int i;
+ unsigned nb_chrec_top_loops = 0;
+ unsigned nb_static_loops = 0;
for (i = 0; i < VARRAY_ACTIVE_SIZE (exit_conditions); i++)
- number_of_iterations_in_loop
- (loop_of_stmt (VARRAY_TREE (exit_conditions, i)));
+ {
+ tree res = number_of_iterations_in_loop
+ (loop_of_stmt (VARRAY_TREE (exit_conditions, i)));
+ if (res == chrec_top)
+ nb_chrec_top_loops++;
+ else
+ nb_static_loops++;
+ }
if (dump_file)
- print_loop_ir (dump_file);
+ {
+ fprintf (dump_file, "\n(\n");
+ fprintf (dump_file, "-----------------------------------------\n");
+ fprintf (dump_file, "%d\tnb_chrec_top_loops\n", nb_chrec_top_loops);
+ fprintf (dump_file, "%d\tnb_static_loops\n", nb_static_loops);
+ fprintf (dump_file, "%d\tnb_total_loops\n", current_loops->num);
+ fprintf (dump_file, "-----------------------------------------\n");
+ fprintf (dump_file, ")\n\n");
+
+ print_loop_ir (dump_file);
+ }
}
+/* Counters for the stats. */
+
+struct chrec_stats
+{
+ unsigned nb_chrecs;
+ unsigned nb_peeled;
+ unsigned nb_affine;
+ unsigned nb_affine_multivar;
+ unsigned nb_higher_poly;
+ unsigned nb_expo;
+ unsigned nb_chrec_top;
+ unsigned nb_interval_chrec;
+ unsigned nb_undetermined;
+};
+
/* Reset the counters. */
static inline void
-reset_chrecs_counters (void)
+reset_chrecs_counters (struct chrec_stats *stats)
{
- stats_nb_chrecs = 0;
- stats_nb_peeled_affine = 0;
- stats_nb_affine = 0;
- stats_nb_affine_multivar = 0;
- stats_nb_higher_poly = 0;
- stats_nb_expo = 0;
- stats_nb_chrec_top = 0;
- stats_nb_interval_chrec = 0;
- stats_nb_undetermined = 0;
+ stats->nb_chrecs = 0;
+ stats->nb_peeled = 0;
+ stats->nb_affine = 0;
+ stats->nb_affine_multivar = 0;
+ stats->nb_higher_poly = 0;
+ stats->nb_expo = 0;
+ stats->nb_chrec_top = 0;
+ stats->nb_interval_chrec = 0;
+ stats->nb_undetermined = 0;
}
-/* Gather statistics about CHREC. */
+/* Dump the contents of a CHREC_STATS structure. */
-static inline void
-gather_chrec_stats (FILE *file, tree chrec)
+static void
+dump_chrecs_stats (FILE *file, struct chrec_stats *stats)
{
- stats_nb_chrecs++;
- fprintf (file, "(classify_chrec ");
- print_generic_expr (file, chrec, 0);
- fprintf (file, "\n");
+ fprintf (file, "\n(\n");
+ fprintf (file, "-----------------------------------------\n");
+ fprintf (file, "%d\taffine univariate chrecs\n", stats->nb_affine);
+ fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar);
+ fprintf (file, "%d\tdegree greater than 2 polynomials\n",
+ stats->nb_higher_poly);
+ fprintf (file, "%d\taffine peeled chrecs\n", stats->nb_peeled);
+ fprintf (file, "%d\texponential chrecs\n", stats->nb_expo);
+ fprintf (file, "%d\tchrec_top chrecs\n", stats->nb_chrec_top);
+ fprintf (file, "%d\tinterval chrecs\n", stats->nb_chrec_top);
+ fprintf (file, "-----------------------------------------\n");
+ fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs);
+ fprintf (file, "%d\twith undetermined coefficients\n",
+ stats->nb_undetermined);
+ fprintf (file, "-----------------------------------------\n");
+ fprintf (file, "%d\tchrecs in the scev database\n",
+ (int) VARRAY_ACTIVE_SIZE (scalar_evolution_info));
+ fprintf (file, "-----------------------------------------\n");
+ fprintf (file, ")\n\n");
+}
+
+/* Gather statistics about CHREC. */
+static void
+gather_chrec_stats (tree chrec, struct chrec_stats *stats)
+{
+ if (dump_file && (dump_flags & TDF_STATS))
+ {
+ fprintf (dump_file, "(classify_chrec ");
+ print_generic_expr (dump_file, chrec, 0);
+ fprintf (dump_file, "\n");
+ }
+
+ stats->nb_chrecs++;
+
if (chrec == NULL_TREE)
- return;
+ {
+ stats->nb_undetermined++;
+ return;
+ }
switch (TREE_CODE (chrec))
{
case POLYNOMIAL_CHREC:
if (evolution_function_is_affine_p (chrec))
{
- fprintf (file, " affine_univariate\n");
- stats_nb_affine++;
+ if (dump_file && (dump_flags & TDF_STATS))
+ fprintf (dump_file, " affine_univariate\n");
+ stats->nb_affine++;
}
-
else if (evolution_function_is_affine_multivariate_p (chrec))
{
- fprintf (file, " affine_multivariate\n");
- stats_nb_affine_multivar++;
- }
-
- else if (evolution_function_is_peeled_affine_p (chrec))
- {
- fprintf (file, " peeled_affine\n");
- stats_nb_peeled_affine++;
+ if (dump_file && (dump_flags & TDF_STATS))
+ fprintf (dump_file, " affine_multivariate\n");
+ stats->nb_affine_multivar++;
}
-
else
{
- fprintf (file, " higher_degree_polynomial\n");
- stats_nb_higher_poly++;
+ if (dump_file && (dump_flags & TDF_STATS))
+ fprintf (dump_file, " higher_degree_polynomial\n");
+ stats->nb_higher_poly++;
}
break;
case EXPONENTIAL_CHREC:
- stats_nb_expo++;
- fprintf (file, " exponential\n");
+ if (dump_file && (dump_flags & TDF_STATS))
+ fprintf (dump_file, " exponential\n");
+ stats->nb_expo++;
break;
case INTERVAL_CHREC:
if (chrec == chrec_top)
{
- stats_nb_chrec_top++;
- fprintf (file, " chrec_top\n");
+ if (dump_file && (dump_flags & TDF_STATS))
+ fprintf (dump_file, " chrec_top\n");
+ stats->nb_chrec_top++;
}
else
{
- stats_nb_interval_chrec++;
- fprintf (file, " interval chrec\n");
+ if (dump_file && (dump_flags & TDF_STATS))
+ fprintf (dump_file, " interval chrec\n");
+ stats->nb_interval_chrec++;
}
break;
+
+ case PEELED_CHREC:
+ if (dump_file && (dump_flags & TDF_STATS))
+ fprintf (dump_file, " peeled chrec\n");
+ stats->nb_peeled++;
+ break;
default:
break;
@@ -3169,38 +3239,13 @@ gather_chrec_stats (FILE *file, tree chr
if (chrec_contains_undetermined (chrec))
{
- fprintf (file, " undetermined\n");
- stats_nb_undetermined++;
+ if (dump_file && (dump_flags & TDF_STATS))
+ fprintf (dump_file, " undetermined\n");
+ stats->nb_undetermined++;
}
- fprintf (file, ")\n");
-}
-
-/* Dump the stats about the chrecs. */
-
-static inline void
-dump_chrecs_stats (FILE *file)
-{
- fprintf (file, "\n(\n");
- fprintf (file, "-----------------------------------------\n");
- fprintf (file, "%d\taffine univariate chrecs\n", stats_nb_affine);
- fprintf (file, "%d\taffine multivariate chrecs\n",
- stats_nb_affine_multivar);
- fprintf (file, "%d\tdegree greater than 2 polynomials\n",
- stats_nb_higher_poly);
- fprintf (file, "%d\taffine peeled chrecs\n", stats_nb_peeled_affine);
- fprintf (file, "%d\texponential chrecs\n", stats_nb_expo);
- fprintf (file, "%d\tchrec_top chrecs\n", stats_nb_chrec_top);
- fprintf (file, "%d\tinterval chrecs\n", stats_nb_chrec_top);
- fprintf (file, "-----------------------------------------\n");
- fprintf (file, "%d\ttotal chrecs\n", stats_nb_chrecs);
- fprintf (file, "%d\twith undetermined coefficients\n",
- stats_nb_undetermined);
- fprintf (file, "-----------------------------------------\n");
- fprintf (file, "%d\tchrecs in the scev database\n",
- (int) VARRAY_ACTIVE_SIZE (scalar_evolution_info));
- fprintf (file, "-----------------------------------------\n");
- fprintf (file, ")\n\n");
+ if (dump_file && (dump_flags & TDF_STATS))
+ fprintf (dump_file, ")\n");
}
/* One of the drivers for testing the scalar evolutions analysis.
@@ -3217,8 +3262,9 @@ static void
analyze_scalar_evolution_for_all_loop_phi_nodes (varray_type exit_conditions)
{
unsigned int i;
-
- reset_chrecs_counters ();
+ struct chrec_stats stats;
+
+ reset_chrecs_counters (&stats);
for (i = 0; i < VARRAY_ACTIVE_SIZE (exit_conditions); i++)
{
@@ -3237,12 +3283,12 @@ analyze_scalar_evolution_for_all_loop_ph
analyze_scalar_evolution (loop, PHI_RESULT (phi)));
if (dump_file && (dump_flags & TDF_STATS))
- gather_chrec_stats (dump_file, chrec);
+ gather_chrec_stats (chrec, &stats);
}
}
if (dump_file && (dump_flags & TDF_STATS))
- dump_chrecs_stats (dump_file);
+ dump_chrecs_stats (dump_file, &stats);
}
/* Classify the chrecs of the whole database. */
@@ -3251,20 +3297,21 @@ void
gather_stats_on_scev_database (void)
{
unsigned i;
+ struct chrec_stats stats;
if (!dump_file)
return;
- reset_chrecs_counters ();
+ reset_chrecs_counters (&stats);
for (i = 0; i < VARRAY_ACTIVE_SIZE (scalar_evolution_info); i++)
{
struct scev_info_str *elt =
VARRAY_GENERIC_PTR (scalar_evolution_info, i);
- gather_chrec_stats (dump_file, elt->chrec);
+ gather_chrec_stats (elt->chrec, &stats);
}
- dump_chrecs_stats (dump_file);
+ dump_chrecs_stats (dump_file, &stats);
}
@@ -3464,6 +3511,24 @@ gate_scev_vectorize (void)
return current_loops && flag_tree_vectorize != 0;
}
+static bool
+gate_ddg (void)
+{
+ return dd_info_available && flag_ddg && flag_scalar_evolutions != 0;
+}
+
+static bool
+gate_delete_ddg (void)
+{
+ return flag_ddg && flag_scalar_evolutions != 0;
+}
+
+static void
+create_dg_graph (void)
+{
+ dg_create_graph (current_loops);
+}
+
struct tree_opt_pass pass_scev =
{
NULL, /* name */
@@ -3602,6 +3667,38 @@ struct tree_opt_pass pass_scev_done =
0, /* static_pass_number */
0, /* tv_id */
PROP_cfg | PROP_ssa, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ 0 /* todo_flags_finish */
+};
+
+struct tree_opt_pass pass_ddg =
+{
+ "ddg", /* name */
+ gate_ddg, /* gate */
+ create_dg_graph, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_DEP_GRAPH, /* tv_id */
+ PROP_scev, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ 0 /* todo_flags_finish */
+};
+
+struct tree_opt_pass pass_delete_ddg =
+{
+ "delete ddg", /* name */
+ gate_delete_ddg, /* gate */
+ dg_delete_graph, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_DEP_GRAPH, /* tv_id */
+ 0, /* properties_required */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */