This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [lno] Fix the check elimination
- From: Dorit Naishlos <DORIT at il dot ibm dot com>
- To: Sebastian Pop <sebastian dot pop at cri dot ensmp dot fr>
- Cc: gcc-patches at gcc dot gnu dot org
- Date: Wed, 31 Mar 2004 14:43:26 +0200
- Subject: Re: [lno] Fix the check elimination
I needed the following tiny patch to tree-scalar-evolutions.c in order to
be able to bootstrap on powerpc-apple-darwin7.0.0, because of the following
error:
../../gcc/gcc/tree-scalar-evolution.c: In function `dump_chrecs_stats':
../../gcc/gcc/tree-scalar-evolution.c:3470: warning: int format, size_t arg
(arg 3)
make[2]: *** [tree-scalar-evolution.o] Error 1
make[1]: *** [stage2_build] Error 2
make: *** [bootstrap] Error 2
ok to commit?
dorit
Index: tree-scalar-evolution.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-scalar-evolution.c,v
retrieving revision 1.1.2.26
diff -c -3 -p -r1.1.2.26 tree-scalar-evolution.c
*** tree-scalar-evolution.c 30 Mar 2004 17:45:52 -0000 1.1.2.26
--- tree-scalar-evolution.c 30 Mar 2004 22:17:26 -0000
*************** dump_chrecs_stats (FILE *file)
*** 3467,3473 ****
stats_nb_undetermined);
fprintf (file, "-----------------------------------------\n");
fprintf (file, "%d\tchrecs in the scev database\n",
! VARRAY_ACTIVE_SIZE (*scalar_evolution_info));
fprintf (file, "-----------------------------------------\n");
fprintf (file, ")\n\n");
}
--- 3467,3473 ----
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");
}
Sebastian Pop
<sebastian.pop@cri To: gcc-patches@gcc.gnu.org
.ensmp.fr> cc:
Sent by: Subject: [lno] Fix the check elimination
gcc-patches-owner@
gcc.gnu.org
30/03/2004 18:39
Hello,
I finished by putting enough constraints on the loop nb_iter detection
and check-elim such that the compiler bootstrap with -ftree-elim-check
I have also unified the nb_iter and check-elim analyzers since they
both rely on the detection of the first iteration that does not
satisfy an if condition.
Bootstrapped with the following flags:
-O2 -ftree-elim-checks -fdump-tree-elck-details -fscalar-evolutions
-fdump-tree-scev -fall-data-deps -fdump-tree-ddall
* tree-chrec.c (chrec_contains_symbols): Factorize conditions,
chrec_not_analyzed_yet is a NULL_TREE.
* tree-chrec.h (prove_truth_value_{lt, le, ge, ne, gt, eq}.c):
Removed.
(evolution_function_is_multivariate,
evolution_function_is_peeled_affine_p): New.
* tree-data-ref.c (analyze_all_data_dependences): Dump some
statistics on the data dependences.
* tree-elim-check.c (not_code, prove_truth_value): New.
(try_eliminate_check): Use prove_truth_value.
* tree-fold-const.h (tree_is_ne): New.
* tree-scalar-evolution.c (types_forbid_solutions_p,
first_iteration_non_satisfying_noev_noev,
first_iteration_non_satisfying_noev_ev,
first_iteration_non_satisfying_ev_noev,
first_iteration_non_satisfying_ev_ev,
first_iteration_non_satisfying_1,
first_iteration_non_satisfying,
gather_stats_on_scev_database): New functions.
(nb_iterations_less, nb_iterations_eq, nb_iterations_ne):
Removed.
(set_nb_iterations_in_loop): Be more careful on overflow.
(number_of_iterations_in_loop): Use
first_iteration_non_satisfying.
* tree-scalar-evolution.h (first_iteration_non_satisfying,
gather_stats_on_scev_database): Declared.
Index: tree-chrec.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-chrec.c,v
retrieving revision 1.1.2.10
diff -c -3 -p -r1.1.2.10 tree-chrec.c
*** tree-chrec.c 23 Mar 2004 20:13:27 -0000 1.1.2.10
--- tree-chrec.c 30 Mar 2004 14:44:05 -0000
*************** chrec_contains_symbols (tree chrec)
*** 1922,1932 ****
bool
chrec_contains_undetermined (tree chrec)
{
- if (chrec == NULL_TREE)
- return false;
-
if (chrec == chrec_top
! || chrec == chrec_not_analyzed_yet)
return true;
switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
--- 1922,1930 ----
bool
chrec_contains_undetermined (tree chrec)
{
if (chrec == chrec_top
! || chrec == chrec_not_analyzed_yet
! || chrec == NULL_TREE)
return true;
switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
Index: tree-chrec.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-chrec.h,v
retrieving revision 1.1.2.7
diff -c -3 -p -r1.1.2.7 tree-chrec.h
*** tree-chrec.h 23 Mar 2004 20:13:28 -0000 1.1.2.7
--- tree-chrec.h 30 Mar 2004 14:44:05 -0000
*************** static inline bool chrec_should_remain_s
*** 116,128 ****
/* Analyzers. */
extern void analyze_overlapping_iterations (tree, tree, tree *, tree *);
- static inline bool prove_truth_value_lt (tree, tree, tree, bool *);
- static inline bool prove_truth_value_le (tree, tree, tree, bool *);
- static inline bool prove_truth_value_ge (tree, tree, tree, bool *);
- static inline bool prove_truth_value_ne (tree, tree, tree, bool *);
- static inline bool prove_truth_value_gt (tree, tree, tree, bool *);
- static inline bool prove_truth_value_eq (tree, tree, tree, bool *);
-
/* Constructors. */
--- 116,121 ----
*************** evolution_function_is_affine_or_constant
*** 294,434 ****
|| evolution_function_is_constant_p (chrec);
}
! /* Determines which expressions are simpler to be {handled | kept} in a
! symbolic form. */
!
! static inline bool
! chrec_should_remain_symbolic (tree evfun)
! {
! if (evfun == NULL_TREE
! || evfun == chrec_top)
! return true;
!
! return false;
! }
!
! /* Determines whether EXPR does not contains chrec expressions. */
!
! static inline bool
! tree_does_not_contain_chrecs (tree expr)
! {
! return !tree_contains_chrecs (expr);
! }
!
! /* Determines whether "CHREC0 (x) > CHREC1 (x)" for all the integers x
! such that "0 <= x < nb_iter". When this property is statically
! computable, set VALUE and return true. */
!
! static inline bool
! prove_truth_value_gt (tree chrec0,
! tree chrec1,
! tree nb_iters ATTRIBUTE_UNUSED,
! bool *value)
! {
! tree diff = chrec_fold_minus (integer_type_node, chrec0, chrec1);
! return chrec_is_positive (diff, value);
! }
!
! /* Determines whether "CHREC0 (x) < CHREC1 (x)" for all the integers x
! such that "0 <= x <= nb_iters". When this property is statically
! computable, set VALUE and return true. */
static inline bool
! prove_truth_value_lt (tree chrec0,
! tree chrec1,
! tree nb_iters,
! bool *value)
{
! return prove_truth_value_gt (chrec1, chrec0, nb_iters, value);
}
! /* Determines whether "CHREC0 (x) <= CHREC1 (x)" for all the integers
! x such that "0 <= x <= nb_iters". When this property is statically
! computable, set VALUE and return true. */
! static inline bool
! prove_truth_value_le (tree chrec0,
! tree chrec1,
! tree nb_iters,
! bool *value)
{
! if (prove_truth_value_gt (chrec0, chrec1, nb_iters, value))
! {
! *value = !*value;
! return true;
! }
! return false;
! }
!
! /* Determines whether "CHREC0 (x) >= CHREC1 (x)" for all the integers
! x such that "0 <= x <= nb_iters". When this property is statically
! computable, set VALUE and return true. */
- static inline bool
- prove_truth_value_ge (tree chrec0,
- tree chrec1,
- tree nb_iters,
- bool *value)
- {
- if (prove_truth_value_gt (chrec1, chrec0, nb_iters, value))
- {
- *value = !*value;
- return true;
- }
-
return false;
}
! /* Determines whether "CHREC0 (x) == CHREC1 (x)" for all the integers
! x such that "0 <= x <= nb_iters". When this property is statically
! computable, set VALUE and return true. */
static inline bool
! prove_truth_value_eq (tree chrec0,
! tree chrec1,
! tree nb_iters ATTRIBUTE_UNUSED,
! bool *value)
{
! tree diff;
!
! if (TREE_TYPE (initial_condition (chrec0))
! != TREE_TYPE (initial_condition (chrec1)))
! return false;
!
! diff = chrec_fold_minus (integer_type_node, chrec0, chrec1);
! if (TREE_CODE (diff) == INTEGER_CST)
! {
! if (integer_zerop (diff))
! *value = true;
!
! else
! *value = false;
!
! return true;
! }
! else
! return false;
}
! /* Determines whether "CHREC0 (x) != CHREC1 (x)" for all the integers
! x such that "0 <= x <= nb_iters". When this property is statically
! computable, set VALUE and return true. */
static inline bool
! prove_truth_value_ne (tree chrec0,
! tree chrec1,
! tree nb_iters,
! bool *value)
{
! if (prove_truth_value_eq (chrec0, chrec1, nb_iters, value))
! {
! *value = !*value;
! return true;
! }
!
! return false;
}
#endif /* GCC_TREE_CHREC_H */
--- 287,334 ----
|| evolution_function_is_constant_p (chrec);
}
! /* Determine whether the given tree is a multivariate evolution. */
static inline bool
! evolution_function_is_multivariate (tree chrec)
{
! return !evolution_function_is_univariate_p (chrec);
}
! /* Determine whether the given tree is an affine peeled chrec. */
! static inline bool
! evolution_function_is_peeled_affine_p (tree chrec)
{
! if (chrec == NULL_TREE)
! return false;
! if (TREE_CODE (chrec) == PEELED_CHREC)
! return (evolution_function_is_affine_or_constant_p (CHREC_LEFT
(chrec))
! && evolution_function_is_affine_p (CHREC_RIGHT (chrec)));
return false;
}
! /* Determines which expressions are simpler to be {handled | kept} in a
! symbolic form. */
static inline bool
! chrec_should_remain_symbolic (tree evfun)
{
! if (evfun == NULL_TREE
! || evfun == chrec_top)
! return true;
! return false;
}
! /* Determines whether EXPR does not contains chrec expressions. */
static inline bool
! tree_does_not_contain_chrecs (tree expr)
{
! return !tree_contains_chrecs (expr);
}
#endif /* GCC_TREE_CHREC_H */
Index: tree-data-ref.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-data-ref.c,v
retrieving revision 1.1.2.12
diff -c -3 -p -r1.1.2.12 tree-data-ref.c
*** tree-data-ref.c 25 Mar 2004 15:15:34 -0000 1.1.2.12
--- tree-data-ref.c 30 Mar 2004 14:44:05 -0000
*************** analyze_all_data_dependences (struct loo
*** 883,897 ****
ddr = VARRAY_GENERIC_PTR (dependence_relations, i);
build_classic_dist_vector (ddr, &classic_dist);
}
!
! if (dump_file)
{
dump_data_dependence_relations (dump_file, dependence_relations);
fprintf (dump_file, "\n\n");
}
-
! /* Don't dump distances for avoiding to update the testsuite. */
if (dump_file && (dump_flags & TDF_DETAILS))
{
for (i = 0; i < VARRAY_ACTIVE_SIZE (classic_dist); i++)
--- 883,897 ----
ddr = VARRAY_GENERIC_PTR (dependence_relations, i);
build_classic_dist_vector (ddr, &classic_dist);
}
!
! if (dump_file && (dump_flags & TDF_DETAILS))
{
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))
{
for (i = 0; i < VARRAY_ACTIVE_SIZE (classic_dist); i++)
*************** analyze_all_data_dependences (struct loo
*** 903,908 ****
--- 903,966 ----
fprintf (dump_file, ")\n");
}
fprintf (dump_file, "\n\n");
+ }
+
+ if (dump_file && (dump_flags & TDF_STATS))
+ {
+ 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++)
+ {
+ struct data_dependence_relation *ddr;
+ ddr = VARRAY_GENERIC_PTR (dependence_relations, i);
+
+ if (DDR_ARE_DEPENDENT (ddr) == chrec_top)
+ nb_top_relations++;
+
+ else if (DDR_ARE_DEPENDENT (ddr) == chrec_bot)
+ {
+ struct data_reference *a = DDR_A (ddr);
+ struct data_reference *b = DDR_B (ddr);
+
+ if (DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b)
+ || array_base_name_differ_p (a, b))
+ nb_basename_differ++;
+ 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;
+ }
+ }
+ }
+ }
+
+ 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_chrec_relations\n",
nb_chrec_relations);
+ fprintf (dump_file, "\n)\n");
+
+ gather_stats_on_scev_database ();
}
varray_clear (dependence_relations);
Index: tree-elim-check.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-elim-check.c,v
retrieving revision 1.1.2.3
diff -c -3 -p -r1.1.2.3 tree-elim-check.c
*** tree-elim-check.c 23 Mar 2004 20:54:46 -0000 1.1.2.3
--- tree-elim-check.c 30 Mar 2004 14:44:05 -0000
*************** Software Foundation, 59 Temple Place - S
*** 69,88 ****
#include "tree-pass.h"
#include "flags.h"
! static void remove_redundant_check (tree, bool);
! static void try_eliminate_check (tree);
! static void scan_all_loops_r (struct loop *);
/* Remove the check by setting the condition COND to VALUE. */
! static void
remove_redundant_check (tree cond, bool value)
{
/* A dead COND_EXPR means the condition is dead. We don't change any
flow, just replace the expression with a constant. */
! if (dump_file && (dump_flags & TDF_STATS))
fprintf (dump_file, "Replacing one of the conditions.\n");
!
if (value == true)
COND_EXPR_COND (cond) = integer_one_node;
--- 69,194 ----
#include "tree-pass.h"
#include "flags.h"
! /* Return the negation of the comparison code. */
!
! static inline enum tree_code
! not_code (enum tree_code code)
! {
! switch (code)
! {
! case EQ_EXPR:
! return NE_EXPR;
! case NE_EXPR:
! return EQ_EXPR;
! case LT_EXPR:
! return GE_EXPR;
! case LE_EXPR:
! return GT_EXPR;
! case GT_EXPR:
! return LE_EXPR;
! case GE_EXPR:
! return LT_EXPR;
!
! default:
! return code;
! }
! }
!
! /* Determine whether "CHREC0 (x) CODE CHREC1 (x)", for all the
! integers x such that "0 <= x <= NB_ITERS_IN_LOOP". When this
! property is statically computable, set VALUE and return true. */
!
! static bool
! prove_truth_value (enum tree_code code,
! unsigned loop_nb,
! tree chrec0,
! tree chrec1,
! tree nb_iters_in_loop,
! bool *value)
! {
! tree nb_iters_in_then, nb_iters_in_else;
!
! if (dump_file && (dump_flags & TDF_DETAILS))
! {
! fprintf (dump_file, " (nb_iters_in_loop = ");
! print_generic_expr (dump_file, nb_iters_in_loop, 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 (automatically_generated_chrec_p (nb_iters_in_loop))
! return false;
!
! /* Compute the number of iterations that fall in the THEN clause,
! and the number of iterations that fall in the ELSE clause. */
! nb_iters_in_then = first_iteration_non_satisfying
! (code, loop_nb, chrec0, chrec1);
! nb_iters_in_else = first_iteration_non_satisfying
! (not_code (code), loop_nb, chrec0, chrec1);
!
! if (dump_file && (dump_flags & TDF_DETAILS))
! {
! fprintf (dump_file, " (nb_iters_in_then = ");
! print_generic_expr (dump_file, nb_iters_in_then, 0);
! fprintf (dump_file, ")\n (nb_iters_in_else = ");
! print_generic_expr (dump_file, nb_iters_in_else, 0);
! fprintf (dump_file, ")\n");
! }
!
! if (nb_iters_in_then == chrec_top
! || nb_iters_in_else == chrec_top)
! return false;
!
! if (nb_iters_in_then == chrec_bot
! && integer_zerop (nb_iters_in_else))
! {
! *value = true;
! return true;
! }
!
! if (nb_iters_in_else == chrec_bot
! && integer_zerop (nb_iters_in_then))
! {
! *value = false;
! return true;
! }
!
! if (TREE_CODE (nb_iters_in_then) == INTEGER_CST
! && TREE_CODE (nb_iters_in_else) == INTEGER_CST)
! {
! if (integer_zerop (nb_iters_in_then)
! && tree_is_gt (nb_iters_in_else, nb_iters_in_loop))
! {
! *value = false;
! return true;
! }
!
! if (integer_zerop (nb_iters_in_else)
! && tree_is_gt (nb_iters_in_then, nb_iters_in_loop))
! {
! *value = true;
! return true;
! }
!
! return false;
! }
!
! return false;
! }
/* Remove the check by setting the condition COND to VALUE. */
! static inline void
remove_redundant_check (tree cond, bool value)
{
/* A dead COND_EXPR means the condition is dead. We don't change any
flow, just replace the expression with a constant. */
! if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Replacing one of the conditions.\n");
!
if (value == true)
COND_EXPR_COND (cond) = integer_one_node;
*************** try_eliminate_check (tree cond)
*** 103,110 ****
tree chrec0, chrec1;
unsigned loop_nb = loop_num (loop_of_stmt (cond));
tree nb_iters = number_of_iterations_in_loop (loop_of_stmt (cond));
!
! if (dump_file && (dump_flags & TDF_STATS))
{
fprintf (dump_file, "(try_eliminate_check \n");
fprintf (dump_file, " (cond = ");
--- 209,219 ----
tree chrec0, chrec1;
unsigned loop_nb = loop_num (loop_of_stmt (cond));
tree nb_iters = number_of_iterations_in_loop (loop_of_stmt (cond));
!
! if (automatically_generated_chrec_p (nb_iters))
! return;
!
! if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "(try_eliminate_check \n");
fprintf (dump_file, " (cond = ");
*************** try_eliminate_check (tree cond)
*** 123,129 ****
break;
chrec0 = instantiate_parameters (loop_nb, chrec0);
! if (dump_file && (dump_flags & TDF_STATS))
{
fprintf (dump_file, " (test = ");
print_generic_expr (dump_file, test, 0);
--- 232,238 ----
break;
chrec0 = instantiate_parameters (loop_nb, chrec0);
! if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " (test = ");
print_generic_expr (dump_file, test, 0);
*************** try_eliminate_check (tree cond)
*** 135,141 ****
fprintf (dump_file, ")\n");
}
! if (prove_truth_value_ne (chrec0, integer_zero_node, nb_iters,
&value))
remove_redundant_check (cond, value);
break;
--- 244,251 ----
fprintf (dump_file, ")\n");
}
! if (prove_truth_value (NE_EXPR, loop_nb, chrec0, integer_zero_node,
! nb_iters, &value))
remove_redundant_check (cond, value);
break;
*************** try_eliminate_check (tree cond)
*** 158,164 ****
chrec0 = instantiate_parameters (loop_nb, chrec0);
chrec1 = instantiate_parameters (loop_nb, chrec1);
! if (dump_file && (dump_flags & TDF_STATS))
{
fprintf (dump_file, " (test = ");
print_generic_expr (dump_file, test, 0);
--- 268,274 ----
chrec0 = instantiate_parameters (loop_nb, chrec0);
chrec1 = instantiate_parameters (loop_nb, chrec1);
! if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " (test = ");
print_generic_expr (dump_file, test, 0);
*************** try_eliminate_check (tree cond)
*** 172,219 ****
fprintf (dump_file, ")\n");
}
! switch (TREE_CODE (test))
! {
! case LT_EXPR:
! if (prove_truth_value_lt (chrec0, chrec1, nb_iters, &value))
! remove_redundant_check (cond, value);
! break;
!
! case LE_EXPR:
! if (prove_truth_value_le (chrec0, chrec1, nb_iters, &value))
! remove_redundant_check (cond, value);
! break;
!
! case GT_EXPR:
! if (prove_truth_value_gt (chrec0, chrec1, nb_iters, &value))
! remove_redundant_check (cond, value);
! break;
!
! case GE_EXPR:
! if (prove_truth_value_ge (chrec0, chrec1, nb_iters, &value))
! remove_redundant_check (cond, value);
! break;
!
! case EQ_EXPR:
! if (prove_truth_value_eq (chrec0, chrec1, nb_iters, &value))
! remove_redundant_check (cond, value);
! break;
!
! case NE_EXPR:
! if (prove_truth_value_ne (chrec0, chrec1, nb_iters, &value))
! remove_redundant_check (cond, value);
! break;
!
! default:
! break;
! }
break;
default:
break;
}
! if (dump_file && (dump_flags & TDF_STATS))
fprintf (dump_file, ")\n");
}
--- 282,297 ----
fprintf (dump_file, ")\n");
}
! if (prove_truth_value (TREE_CODE (test), loop_nb, chrec0, chrec1,
! nb_iters, &value))
! remove_redundant_check (cond, value);
break;
default:
break;
}
! if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, ")\n");
}
Index: tree-fold-const.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-fold-const.h,v
retrieving revision 1.1.2.5
diff -c -3 -p -r1.1.2.5 tree-fold-const.h
*** tree-fold-const.h 23 Mar 2004 20:13:28 -0000 1.1.2.5
--- tree-fold-const.h 30 Mar 2004 14:44:06 -0000
*************** tree_is_eq (tree a, tree b)
*** 257,261 ****
--- 257,269 ----
return (tree_int_cst_sgn (cmp) != 0);
}
+ /* Given two integer constants A and B, determine whether "A != B". */
+
+ static inline bool
+ tree_is_ne (tree a, tree b)
+ {
+ tree cmp = fold (build (NE_EXPR, boolean_type_node, a, b));
+ return (tree_int_cst_sgn (cmp) != 0);
+ }
#endif /* GCC_TREE_FOLD_H */
Index: tree-scalar-evolution.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-scalar-evolution.c,v
retrieving revision 1.1.2.25
diff -c -3 -p -r1.1.2.25 tree-scalar-evolution.c
*** tree-scalar-evolution.c 27 Mar 2004 18:29:36 -0000
1.1.2.25
--- tree-scalar-evolution.c 30 Mar 2004 14:44:06 -0000
*************** Software Foundation, 59 Temple Place - S
*** 266,272 ****
static bool loop_phi_node_p (tree);
! static tree compute_overall_effect_of_inner_loop (tree);
static void set_scalar_evolution (tree, tree);
static void set_scalar_evolution_outer_value (tree, tree);
--- 266,272 ----
static bool loop_phi_node_p (tree);
!
static void set_scalar_evolution (tree, tree);
static void set_scalar_evolution_outer_value (tree, tree);
*************** static varray_type already_instantiated_
*** 305,311 ****
/* Statistics counters. */
static unsigned stats_nb_chrecs = 0;
! static unsigned stats_nb_peeled = 0;
static unsigned stats_nb_affine = 0;
static unsigned stats_nb_affine_multivar = 0;
static unsigned stats_nb_higher_poly = 0;
--- 305,311 ----
/* 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;
*************** chrec_is_positive (tree chrec, bool *val
*** 695,705 ****
symbolic. */
static tree
! set_scev_keep_symbolic (tree var,
tree chrec)
{
if (chrec == chrec_not_analyzed_yet)
return chrec;
switch (TREE_CODE (chrec))
{
--- 695,709 ----
symbolic. */
static tree
! set_scev_keep_symbolic (tree def,
tree chrec)
{
if (chrec == chrec_not_analyzed_yet)
return chrec;
+
+ if (chrec == chrec_top)
+ /* return def; */
+ return chrec;
switch (TREE_CODE (chrec))
{
*************** set_scev_keep_symbolic (tree var,
*** 708,721 ****
case INDIRECT_REF:
case COMPONENT_REF:
/* KEEP_IT_SYMBOLIC. */
! chrec = var;
! break;
default:
! break;
}
-
- return chrec;
}
/* Associate CHREC to SCALAR. */
--- 712,722 ----
case INDIRECT_REF:
case COMPONENT_REF:
/* KEEP_IT_SYMBOLIC. */
! return def;
default:
! return chrec;
}
}
/* Associate CHREC to SCALAR. */
*************** multiply_evolution (unsigned loop_nb,
*** 1327,1612 ****
/* This section deals with the approximation of the number of
iterations a loop will run. */
! /* Try to compute the number of iterations in LOOP_NB such that:
! - when (CODE is LE_EXPR) the loop exits when CHREC0 > CHREC1,
! - when (CODE is LT_EXPR) the loop exits when CHREC0 >= CHREC1.
! */
static tree
! nb_iterations_less (enum tree_code code,
! unsigned loop_nb,
! tree chrec0,
! tree chrec1)
{
! tree other_ev0, other_ev1, other_evolutions;
! tree res = chrec_top;
! if (automatically_generated_chrec_p (chrec0)
! || automatically_generated_chrec_p (chrec1))
return chrec_top;
! other_ev0 = chrec0;
! other_ev1 = chrec1;
!
! chrec0 = evolution_function_in_loop_num (chrec0, loop_nb);
! chrec1 = evolution_function_in_loop_num (chrec1, loop_nb);
! /* Compute the evolutions on other dimensions. */
! other_ev0 = chrec_fold_minus (integer_type_node, chrec0, other_ev0);
! other_ev1 = chrec_fold_minus (integer_type_node, chrec1, other_ev1);
! other_evolutions = chrec_fold_plus (integer_type_node, other_ev0,
other_ev1);
! if (evolution_function_is_affine_or_constant_p (chrec0)
! && evolution_function_is_affine_or_constant_p (chrec1))
{
! tree type0, type1;
! tree left0, left1, right0, right1;
! type0 = chrec_type (chrec0);
! type1 = chrec_type (chrec1);
! switch (TREE_CODE (chrec0))
! {
! case POLYNOMIAL_CHREC:
! left0 = CHREC_LEFT (chrec0);
! right0 = CHREC_RIGHT (chrec0);
! break;
!
! case INTEGER_CST:
! left0 = chrec0;
! right0 = integer_zero_node;
! break;
!
! default:
return chrec_top;
! }
! switch (TREE_CODE (chrec1))
! {
! case POLYNOMIAL_CHREC:
! left1 = CHREC_LEFT (chrec1);
! right1 = CHREC_RIGHT (chrec1);
! break;
!
! case INTEGER_CST:
! left1 = chrec1;
! right1 = integer_zero_node;
! break;
!
! default:
return chrec_top;
! }
! if (TREE_CODE (left0) != INTEGER_CST
! || TREE_CODE (left1) != INTEGER_CST
! || TREE_CODE (right0) != INTEGER_CST
! || TREE_CODE (right1) != INTEGER_CST)
! return chrec_top;
! if (code == LE_EXPR)
! {
! if (tree_is_gt (left0, left1))
! return other_evolutions;
!
! if (tree_is_gt (TYPE_MIN_VALUE (type1),
! TYPE_MAX_VALUE (type0)))
! return chrec_bot;
! }
! else
! {
! if (tree_is_ge (left0, left1))
! return other_evolutions;
!
! if (tree_is_ge (TYPE_MIN_VALUE (type1),
! TYPE_MAX_VALUE (type0)))
! return chrec_bot;
! }
! /* No evolution. */
! if (integer_zerop (right0)
! && integer_zerop (right1))
! return chrec_bot;
! /* No evolution on chrec0. */
! if (integer_zerop (right0))
! {
! tree nb_iters;
! tree tmin, tmax;
!
! tmin = TYPE_MIN_VALUE (type1);
! tmax = TYPE_MAX_VALUE (type1);
!
! if (code == LE_EXPR)
! {
! if (tree_is_gt (tmin, left0))
! return chrec_bot;
!
! if (tree_int_cst_sgn (right1) > 0)
! nb_iters = tree_fold_plus
! (integer_type_node,
! tree_fold_floor_div
! (integer_type_node,
! tree_fold_minus (integer_type_node, tmax,
left1),
! right1), integer_one_node);
!
! else
! nb_iters = tree_fold_plus
! (integer_type_node,
! tree_fold_floor_div
! (integer_type_node,
! tree_fold_minus (type1, left1, left0),
! tree_fold_abs (type1, right1)),
! integer_one_node);
!
! /* Verify the result. */
! if (tree_is_gt
! (left0,
! tree_fold_plus (type1, left1,
! tree_fold_multiply
! (integer_type_node,
nb_iters, right1))))
! return chrec_fold_plus
! (chrec_type (res), nb_iters, other_evolutions);
!
! else
! /* Difficult cases fall down there. */
! return chrec_top;
! }
! else
! {
! if (tree_is_ge (tmin, left0))
! return chrec_bot;
!
! if (tree_int_cst_sgn (right1) > 0)
! nb_iters = tree_fold_ceil_div
! (integer_type_node,
! tree_fold_minus (integer_type_node, tmax,
left1),
! right1);
!
! else
! nb_iters = tree_fold_ceil_div
! (integer_type_node,
! tree_fold_minus (type1, left1, left0),
! tree_fold_abs (type1, right1));
!
! /* Verify the result. */
! if (tree_is_ge
! (left0,
! tree_fold_plus (type1, left1,
! tree_fold_multiply
! (integer_type_node,
nb_iters, right1))))
! return chrec_fold_plus
! (chrec_type (res), nb_iters, other_evolutions);
!
! else
! /* Difficult cases fall down there. */
! return chrec_top;
! }
! }
!
! /* No evolution on chrec1. */
! if (integer_zerop (right1))
! {
! tree nb_iters;
! tree tmin, tmax;
!
! tmin = TYPE_MIN_VALUE (type0);
! tmax = TYPE_MAX_VALUE (type0);
!
! if (code == LE_EXPR)
! {
! if (tree_is_gt (left1, tmax))
! return chrec_bot;
!
! if (tree_int_cst_sgn (right0) < 0)
! nb_iters = tree_fold_plus
! (integer_type_node,
! tree_fold_floor_div
! (integer_type_node,
! tree_fold_minus (integer_type_node, left0,
tmin),
! tree_fold_abs (type0, right0)),
integer_one_node);
!
! else
! nb_iters = tree_fold_plus
! (integer_type_node,
! tree_fold_floor_div
! (integer_type_node,
! tree_fold_minus (type1, left1, left0),
! right0), integer_one_node);
!
! /* Verify the result. */
! if (tree_is_le
! (left1,
! tree_fold_plus (type0, left0,
! tree_fold_multiply
! (integer_type_node,
nb_iters, right0))))
! return chrec_fold_plus
! (chrec_type (res), nb_iters, other_evolutions);
!
! else
! /* Difficult cases fall down there. */
! return chrec_top;
! }
! else
! {
! if (tree_is_ge (left1, tmax))
! return chrec_bot;
!
! if (tree_int_cst_sgn (right0) < 0)
! nb_iters = tree_fold_ceil_div
! (integer_type_node,
! tree_fold_minus (integer_type_node, left0,
tmin),
! tree_fold_abs (type0, right0));
!
! else
! nb_iters = tree_fold_ceil_div
! (integer_type_node,
! tree_fold_minus (type1, left1, left0),
! right0);
!
! /* Verify the result. */
! if (tree_is_lt
! (left1,
! tree_fold_plus (type0, left0,
! tree_fold_multiply
! (integer_type_node,
nb_iters, right0))))
! return chrec_fold_plus
! (chrec_type (res), nb_iters, other_evolutions);
!
! else
! /* Difficult cases fall down there. */
! return chrec_top;
! }
! }
! /* Evolution on chrec0 and chrec1. */
! else
! return chrec_top;
}
! else
! return chrec_top;
}
! /* Try to compute the number of iterations in LOOP_NB such that the
! loop exits when CHREC0 != CHREC1. */
static tree
! nb_iterations_eq (unsigned loop_nb ATTRIBUTE_UNUSED,
! tree chrec0 ATTRIBUTE_UNUSED,
! tree chrec1 ATTRIBUTE_UNUSED)
{
return chrec_top;
}
! /* Try to compute the number of iterations in LOOP_NB such that the
! loop exits when CHREC0 == CHREC1. */
static tree
! nb_iterations_ne (unsigned loop_nb ATTRIBUTE_UNUSED,
! tree chrec0 ATTRIBUTE_UNUSED,
! tree chrec1 ATTRIBUTE_UNUSED)
{
! return chrec_top;
}
/* Helper function. */
--- 1328,2037 ----
/* This section deals with the approximation of the number of
iterations a loop will run. */
! /* Helper function that determines whether the considered types are
! compatible for finding a solution. */
! #if 0
! static bool
! types_forbid_solutions_p (enum tree_code code,
! tree type0,
! tree type1)
! {
! switch (code)
! {
! case LE_EXPR:
! return tree_is_le (TYPE_MAX_VALUE (type0),
! TYPE_MIN_VALUE (type1));
!
! case LT_EXPR:
! return tree_is_lt (TYPE_MAX_VALUE (type0),
! TYPE_MIN_VALUE (type1));
!
! case EQ_EXPR:
! return false;
!
! case NE_EXPR:
! return (tree_is_lt (TYPE_MAX_VALUE (type0),
! TYPE_MIN_VALUE (type1))
! || tree_is_lt (TYPE_MAX_VALUE (type1),
! TYPE_MIN_VALUE (type0)));
!
! default:
! abort ();
! return false;
! }
! }
! #endif
!
! /* Helper function for the case when both evolution functions don't
! have an evolution in the considered loop. */
static tree
! first_iteration_non_satisfying_noev_noev (enum tree_code code,
! unsigned
loop_nb ATTRIBUTE_UNUSED,
! tree chrec0,
! tree chrec1)
{
! tree init0 = initial_condition (chrec0);
! tree init1 = initial_condition (chrec1);
! if (TREE_CODE (init0) != INTEGER_CST
! || TREE_CODE (init1) != INTEGER_CST)
! return chrec_top;
!
! if (!evolution_function_is_constant_p (chrec0)
! || !evolution_function_is_constant_p (chrec1))
return chrec_top;
! switch (code)
! {
! case LE_EXPR:
! if (tree_is_gt (init0, init1))
! return integer_zero_node;
! else
! return chrec_bot;
!
! case LT_EXPR:
! if (tree_is_ge (init0, init1))
! return integer_zero_node;
! else
! return chrec_bot;
!
! case EQ_EXPR:
! if (tree_is_eq (init0, init1))
! return integer_zero_node;
! else
! return chrec_bot;
!
! case NE_EXPR:
! if (tree_is_ne (init0, init1))
! return integer_zero_node;
! else
! return chrec_bot;
!
! default:
! return chrec_top;
! }
! }
!
! /* Helper function for the case when CHREC0 has no evolution and
! CHREC1 has an evolution in the considered loop. */
!
! static tree
! first_iteration_non_satisfying_noev_ev (enum tree_code code,
! unsigned
loop_nb,
! tree chrec0,
! tree chrec1)
! {
! tree type1 = chrec_type (chrec1);
! /* tree tmax = TYPE_MAX_VALUE (type1); */
! tree ev_in_this_loop;
! tree init0, init1, step1;
! tree nb_iters;
!
! ev_in_this_loop = evolution_function_in_loop_num (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;
! init1 = CHREC_LEFT (ev_in_this_loop);
! step1 = CHREC_RIGHT (ev_in_this_loop);
! init0 = initial_condition (chrec0);
! if (TREE_CODE (init0) != INTEGER_CST
! || TREE_CODE (init1) != INTEGER_CST
! || TREE_CODE (step1) != INTEGER_CST)
! /* For the moment we deal only with INTEGER_CSTs. */
! return chrec_top;
! switch (code)
{
! case LE_EXPR:
! {
! if (tree_is_gt (init0, init1))
! {
! if (evolution_function_is_constant_p (chrec0))
! /* Example: "while (2 <= {0, +, 1}_2)". */
! return integer_zero_node;
! else
! /* Example: "while ({2, +, -1}_1 <= {0, +, 1}_2)". The
! number of iterations in loop_2 during the first
two
! iterations of loop_1 is equal to 0. */
! return chrec_top;
! }
!
! if (tree_int_cst_sgn (step1) > 0)
! {
! if (evolution_function_is_constant_p (chrec0))
! /* Example: "while (2 <= {3, +, 1}_2)". */
! return chrec_top;
! /* nb_iters = tree_fold_plus
! (integer_type_node,
! tree_fold_floor_div (integer_type_node,
! tree_fold_minus (integer_type_node,
! tmax, init1),
! step1),
! integer_one_node);
! */
! else
! /* Example: "while ({2, +, 1}_1 <= {3, +, 1}_2)". */
! return chrec_top;
! }
!
! else
! {
! if (evolution_function_is_constant_p (chrec0))
! /* Example: "while (2 <= {3, +, -1}_2)". */
! nb_iters = tree_fold_plus
! (integer_type_node,
! tree_fold_floor_div (integer_type_node,
! tree_fold_minus
(integer_type_node,
!
init1, init0),
! tree_fold_abs
(integer_type_node,
!
step1)),
! integer_one_node);
! else
! /* Example: "while ({2, +, 1}_1 <= {3, +, -1}_2)". */
! return chrec_top;
! }
!
! /* Verify the result. */
! if (evolution_function_is_constant_p (chrec0)
! && tree_is_gt (init0,
! tree_fold_plus (type1, init1,
!
tree_fold_multiply
!
(integer_type_node,
! nb_iters,
step1))))
! return nb_iters;
!
! else
! /* Difficult cases fall down there. Example: When the
! evolution step is big enough the wrapped value can be
! bigger than init0. In these cases the loop may end after
! several wraps, or never end. */
! return chrec_top;
! }
! case LT_EXPR:
! {
! if (tree_is_ge (init0, init1))
! {
! if (evolution_function_is_constant_p (chrec0))
! /* Example: "while (2 < {0, +, 1}_2)". */
! return integer_zero_node;
! else
! /* Example: "while ({2, +, 1}_1 < {0, +, 1}_2)". */
! return chrec_top;
! }
!
! if (tree_int_cst_sgn (step1) > 0)
! {
! if (evolution_function_is_constant_p (chrec0))
! /* Example: "while (2 < {3, +, 1}_2)". */
! return chrec_top;
! /* nb_iters = tree_fold_ceil_div
! (integer_type_node,
! tree_fold_minus (integer_type_node, tmax, init1),
! step1);
! */
! else
! /* Example: "while ({2, +, 1}_1 < {3, +, 1}_2)". */
! return chrec_top;
! }
! else
! {
! if (evolution_function_is_constant_p (chrec0))
! /* Example: "while (2 < {3, +, -1}_2)". */
! nb_iters = tree_fold_ceil_div
! (integer_type_node,
! tree_fold_minus (type1, init1, init0),
! tree_fold_abs (type1, step1));
! else
! /* Example: "while ({2, +, 1}_1 < {3, +, -1}_2)". */
! return chrec_top;
! }
!
! /* Verify the result. */
! if (evolution_function_is_constant_p (chrec0)
! && tree_is_ge (init0,
! tree_fold_plus (type1, init1,
!
tree_fold_multiply
!
(integer_type_node,
! nb_iters,
step1))))
! return nb_iters;
!
! else
! /* Difficult cases fall down there. */
! return chrec_top;
! }
! case EQ_EXPR:
! {
! if (tree_is_ne (init0, init1))
! {
! if (evolution_function_is_constant_p (chrec0))
! /* Example: "while (2 == {0, +, 1}_2)". */
! return integer_zero_node;
! else
! /* Example: "while ({2, +, -1}_1 == {0, +, 1}_2)". */
! return chrec_top;
! }
!
! if (evolution_function_is_constant_p (chrec0))
! {
! if (integer_zerop (step1))
! /* Example: "while (2 == {2, +, 0}_2)". */
! return chrec_bot;
! else
! return integer_one_node;
! }
! else
return chrec_top;
! }
! case NE_EXPR:
! {
! if (tree_is_eq (init0, init1))
! {
! if (evolution_function_is_constant_p (chrec0))
! /* Example: "while (0 != {0, +, 1}_2)". */
! return integer_zero_node;
! else
! /* Example: "while ({0, +, -1}_1 != {0, +, 1}_2)". */
! return chrec_top;
! }
!
! if (tree_int_cst_sgn (step1) > 0)
! {
! if (evolution_function_is_constant_p (chrec0))
! {
! if (tree_is_gt (init0, init1))
! {
! tree diff = tree_fold_minus
(integer_type_node,
!
init0, init1);
! if (tree_fold_divides_p (integer_type_node,
step1, diff))
! /* Example: "while (3 != {2, +, 1}_2)". */
! nb_iters = tree_fold_exact_div
! (integer_type_node, diff, step1);
! else
! /* Example: "while (3 != {2, +, 2}_2)". */
! return chrec_top;
! }
! else
! /* Example: "while (2 != {3, +, 1}_2)". */
! return chrec_top;
! }
! else
! /* Example: "while ({2, +, 1}_1 != {3, +, 1}_2)". */
! return chrec_top;
! }
!
! else
! {
! if (evolution_function_is_constant_p (chrec0))
! {
! if (tree_is_lt (init0, init1))
! {
! tree diff = tree_fold_minus
(integer_type_node,
!
init1, init0);
! if (tree_fold_divides_p (integer_type_node,
step1, diff))
! /* Example: "while (2 != {3, +, -1}_2)". */
! nb_iters = tree_fold_exact_div
! (integer_type_node, diff,
! tree_fold_abs (integer_type_node,
step1));
! else
! /* Example: "while (2 != {3, +, -2}_2)". */
! return chrec_top;
! }
! else
! /* Example: "while (3 != {2, +, -1}_2)". */
! return chrec_top;
! }
! else
! /* Example: "while ({2, +, 1}_1 != {3, +, -1}_2)". */
! return chrec_top;
! }
!
! /* Verify the result. */
! if (evolution_function_is_constant_p (chrec0)
! && tree_is_eq (init0,
! tree_fold_plus (type1, init1,
!
tree_fold_multiply
!
(integer_type_node,
! nb_iters,
step1))))
! return nb_iters;
!
! else
! /* Difficult cases fall down there. */
return chrec_top;
! }
!
! default:
! return chrec_top;
! }
! return chrec_top;
! }
!
! /* Helper function for the case when CHREC1 has no evolution and
! CHREC0 has an evolution in the considered loop. */
!
! static tree
! first_iteration_non_satisfying_ev_noev (enum tree_code code,
! unsigned
loop_nb,
! tree chrec0,
! tree chrec1)
! {
! tree type0 = chrec_type (chrec0);
! /* tree tmin = TYPE_MIN_VALUE (type0); */
! tree ev_in_this_loop;
! tree init0, init1, step0;
! tree nb_iters;
!
! ev_in_this_loop = evolution_function_in_loop_num (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;
!
! init0 = CHREC_LEFT (ev_in_this_loop);
! step0 = CHREC_RIGHT (ev_in_this_loop);
! init1 = initial_condition (chrec1);
! if (TREE_CODE (init1) != INTEGER_CST
! || TREE_CODE (init0) != INTEGER_CST
! || TREE_CODE (step0) != INTEGER_CST)
! /* For the moment we deal only with INTEGER_CSTs. */
! return chrec_top;
!
! switch (code)
! {
! case LE_EXPR:
! {
! if (tree_is_gt (init0, init1))
! {
! if (evolution_function_is_constant_p (chrec1))
! /* Example: "while ({2, +, 1}_2 <= 0)". */
! return integer_zero_node;
!
! else
! /* Example: "while ({2, +, 1}_2 <= {0, +, 1}_1)". */
! return chrec_top;
! }
!
! if (tree_int_cst_sgn (step0) < 0)
! {
! if (evolution_function_is_constant_p (chrec1))
! /* Example: "while ({2, +, -1}_2 <= 3)". */
! return chrec_top;
! /* nb_iters = tree_fold_plus
! (integer_type_node,
! tree_fold_floor_div (integer_type_node,
! tree_fold_minus (integer_type_node,
! init0, tmin),
! tree_fold_abs (integer_type_node,
! step0)),
! integer_one_node);
! */
! else
! /* Example: "while ({2, +, -1}_2 <= {3, +, 1}_1)". */
! return chrec_top;
! }
! else
! {
! if (evolution_function_is_constant_p (chrec1))
! /* Example: "while ({2, +, 1}_2 <= 3)". */
! nb_iters = tree_fold_plus
! (integer_type_node,
! tree_fold_floor_div (integer_type_node,
! tree_fold_minus
(integer_type_node,
!
init1, init0),
! step0),
! integer_one_node);
! else
! /* Example: "while ({2, +, 1}_2 <= {3, +, 1}_1)". */
! return chrec_top;
! }
!
! /* Verify the result. */
! if (evolution_function_is_constant_p (chrec1)
! && tree_is_gt (tree_fold_plus (type0, init0,
!
tree_fold_multiply
!
(integer_type_node,
! nb_iters,
step0)),
! init1))
! return nb_iters;
!
! else
! /* Difficult cases fall down there. */
! return chrec_top;
! }
! case LT_EXPR:
! {
! if (tree_is_ge (init0, init1))
! {
! if (evolution_function_is_constant_p (chrec1))
! /* Example: "while ({2, +, 1}_2 < 0)". */
! return integer_zero_node;
!
! else
! /* Example: "while ({2, +, 1}_2 < {0, +, 1}_1)". */
! return chrec_top;
! }
!
! if (tree_int_cst_sgn (step0) < 0)
! {
! if (evolution_function_is_constant_p (chrec1))
! /* Example: "while ({2, +, -1}_2 < 3)". */
! return chrec_top;
! /* nb_iters = tree_fold_ceil_div
! (integer_type_node,
! tree_fold_minus (integer_type_node, init0, tmin),
! tree_fold_abs (integer_type_node, step0));
! */
! else
! /* Example: "while ({2, +, -1}_2 < {3, +, 1}_1)". */
! return chrec_top;
! }
! else
! {
! if (evolution_function_is_constant_p (chrec1))
! /* Example: "while ({2, +, 1}_2 < 3)". */
! nb_iters = tree_fold_ceil_div
! (integer_type_node,
! tree_fold_minus (integer_type_node, init1,
init0),
! step0);
! else
! /* Example: "while ({2, +, 1}_2 < {3, +, 1}_1)". */
! return chrec_top;
! }
!
! /* Verify the result. */
! if (evolution_function_is_constant_p (chrec1)
! && tree_is_ge (tree_fold_plus (type0, init0,
!
tree_fold_multiply
!
(integer_type_node,
! nb_iters,
step0)),
! init1))
! return nb_iters;
!
! else
! /* Difficult cases fall down there. */
! return chrec_top;
! }
! case EQ_EXPR:
! {
! if (tree_is_ne (init0, init1))
! {
! if (evolution_function_is_constant_p (chrec1))
! /* Example: "while ({2, +, 1}_2 == 0)". */
! return integer_zero_node;
! else
! /* Example: "while ({2, +, -1}_2 == {0, +, 1}_1)". */
! return chrec_top;
! }
!
! if (evolution_function_is_constant_p (chrec1))
! {
! if (integer_zerop (step0))
! /* Example: "while ({2, +, 0}_2 == 2)". */
! return chrec_bot;
! else
! return integer_one_node;
! }
! else
! return chrec_top;
! }
! case NE_EXPR:
! {
! if (tree_is_eq (init0, init1))
! {
! if (evolution_function_is_constant_p (chrec1))
! /* Example: "while ({0, +, 1}_2 != 0)". */
! return integer_zero_node;
! else
! /* Example: "while ({0, +, -1}_2 != {0, +, 1}_1)". */
! return chrec_top;
! }
!
! if (tree_int_cst_sgn (step0) > 0)
! {
! if (evolution_function_is_constant_p (chrec1))
! {
! if (tree_is_lt (init0, init1))
! {
! tree diff = tree_fold_minus
(integer_type_node,
!
init1, init0);
! if (tree_fold_divides_p (integer_type_node,
step0, diff))
! /* Example: "while ({2, +, 1}_2 != 3)". */
! nb_iters = tree_fold_exact_div
! (integer_type_node, diff, step0);
! else
! /* Example: "while ({2, +, 2}_2 != 3)". */
! return chrec_top;
! }
! else
! /* Example: "while ({3, +, 1}_2 != 2)". */
! return chrec_top;
! }
! else
! /* Example: "while ({2, +, 1}_2 != {3, +, 1}_1)". */
! return chrec_top;
! }
!
! else
! {
! if (evolution_function_is_constant_p (chrec1))
! {
! if (tree_is_gt (init0, init1))
! {
! tree diff = tree_fold_minus
(integer_type_node,
!
init0, init1);
! if (tree_fold_divides_p (integer_type_node,
step0, diff))
! /* Example: "while ({3, +, -1}_2 != 2)". */
! nb_iters = tree_fold_exact_div
! (integer_type_node, diff,
! tree_fold_abs (integer_type_node,
step0));
! else
! /* Example: "while ({3, +, -2}_2 != 2)". */
! return chrec_top;
! }
! else
! /* Example: "while ({2, +, -1}_2 != 3)". */
! return chrec_top;
! }
! else
! /* Example: "while ({2, +, -1}_2 != {3, +, -1}_1)". */
! return chrec_top;
! }
! /* Verify the result. */
! if (evolution_function_is_constant_p (chrec1)
! && tree_is_eq (tree_fold_plus (type0, init0,
!
tree_fold_multiply
!
(integer_type_node,
! nb_iters,
step0)),
! init1))
! return nb_iters;
! else
! /* Difficult cases fall down there. */
! return chrec_top;
! }
! default:
! return chrec_top;
}
! return chrec_top;
}
! /* Helper function for the case when both CHREC0 and CHREC1 has an
! evolution in the considered loop. */
static tree
! first_iteration_non_satisfying_ev_ev (enum tree_code code,
! unsigned loop_nb
ATTRIBUTE_UNUSED,
! tree chrec0
ATTRIBUTE_UNUSED,
! tree chrec1
ATTRIBUTE_UNUSED)
{
+ switch (code)
+ {
+ case LE_EXPR:
+
+ case LT_EXPR:
+
+ case EQ_EXPR:
+
+ case NE_EXPR:
+
+ default:
+ return chrec_top;
+ }
+
return chrec_top;
}
! /* Helper function. */
static tree
! first_iteration_non_satisfying_1 (enum tree_code code,
! unsigned loop_nb,
! tree chrec0,
! tree chrec1)
{
! if (automatically_generated_chrec_p (chrec0)
! || automatically_generated_chrec_p (chrec1))
! return chrec_top;
!
! if (no_evolution_in_loop_p (chrec0, loop_nb))
! {
! if (no_evolution_in_loop_p (chrec1, loop_nb))
! return first_iteration_non_satisfying_noev_noev (code,
loop_nb,
!
chrec0, chrec1);
! else
! return first_iteration_non_satisfying_noev_ev (code, loop_nb,
!
chrec0, chrec1);
! }
!
! else
! {
! if (no_evolution_in_loop_p (chrec1, loop_nb))
! return first_iteration_non_satisfying_ev_noev (code, loop_nb,
!
chrec0, chrec1);
! else
! return first_iteration_non_satisfying_ev_ev (code, loop_nb,
!
chrec0, chrec1);
! }
! }
!
! /* Try to compute the first iteration I of LOOP_NB that does not satisfy
! CODE: in the context of the computation of the number of iterations:
! - if (CODE is LE_EXPR) the loop exits when CHREC0 (I) > CHREC1 (I),
! - if (CODE is LT_EXPR) the loop exits when CHREC0 (I) >= CHREC1 (I),
! - if (CODE is EQ_EXPR) the loop exits when CHREC0 (I) != CHREC1 (I),
! ...
!
! The result is one of the following:
! - CHREC_TOP when the analyzer cannot determine the property,
! - CHREC_BOT when the property is always true,
! - an INTEGER_CST tree node,
! - a CHREC,
! - an expression containing SSA_NAMEs.
! */
!
! tree
! first_iteration_non_satisfying (enum tree_code code,
! unsigned loop_nb,
! tree chrec0,
! tree chrec1)
! {
! switch (code)
! {
! case LT_EXPR:
! return first_iteration_non_satisfying_1 (LT_EXPR, loop_nb,
! chrec0,
chrec1);
!
! case LE_EXPR:
! return first_iteration_non_satisfying_1 (LE_EXPR, loop_nb,
! chrec0,
chrec1);
!
! case GT_EXPR:
! return first_iteration_non_satisfying_1 (LT_EXPR, loop_nb,
! chrec1,
chrec0);
!
! case GE_EXPR:
! return first_iteration_non_satisfying_1 (LE_EXPR, loop_nb,
! chrec1,
chrec0);
!
! case EQ_EXPR:
! return first_iteration_non_satisfying_1 (EQ_EXPR, loop_nb,
! chrec0,
chrec1);
!
! case NE_EXPR:
! return first_iteration_non_satisfying_1 (NE_EXPR, loop_nb,
! chrec0,
chrec1);
!
! default:
! return chrec_top;
! }
}
/* Helper function. */
*************** set_nb_iterations_in_loop (struct loop *
*** 1630,1635 ****
--- 2055,2067 ----
/* After the loop copy headers has transformed the code, each loop
runs at least once. */
res = chrec_fold_plus (chrec_type (res), res, integer_one_node);
+ /* FIXME HWI: However we want to store one iteration less than the
+ count of the loop in order to be compatible with the other
+ nb_iter computations in loop-iv. This also allows the
+ representation of nb_iters that are equal to MAX_INT. */
+ if (TREE_CODE (res) == INTEGER_CST
+ && TREE_INT_CST_LOW (res) == 0)
+ res = chrec_top;
if (dump_file && (dump_flags & TDF_DETAILS))
{
*************** follow_ssa_edge_in_condition_phi (unsign
*** 2103,2108 ****
--- 2535,2543 ----
tree evolution_of_branch;
tree init_cond = initial_condition (*evolution_of_loop);
+ /* Disabled for the moment. */
+ return false;
+
res = follow_ssa_edge_in_condition_phi_branch
(0, loop_nb, condition_phi, halting_phi, &evolution_of_branch,
init_cond);
*************** number_of_iterations_in_loop (struct loo
*** 2852,2858 ****
else
return set_nb_iterations_in_loop
! (loop, nb_iterations_ne (loop_nb, chrec0, chrec1));
case LT_EXPR:
case LE_EXPR:
--- 3287,3294 ----
else
return set_nb_iterations_in_loop
! (loop, first_iteration_non_satisfying (NE_EXPR, loop_nb,
!
chrec0, chrec1));
case LT_EXPR:
case LE_EXPR:
*************** number_of_iterations_in_loop (struct loo
*** 2891,2926 ****
if (chrec_contains_undetermined (chrec0)
|| chrec_contains_undetermined (chrec1))
return cannot_analyze_loop_nb_iterations_yet ();
!
! switch (TREE_CODE (test))
! {
! case LT_EXPR:
! return set_nb_iterations_in_loop
! (loop, nb_iterations_less (LT_EXPR, loop_nb, chrec0,
chrec1));
!
! case LE_EXPR:
! return set_nb_iterations_in_loop
! (loop, nb_iterations_less (LE_EXPR, loop_nb, chrec0,
chrec1));
!
! case GT_EXPR:
! return set_nb_iterations_in_loop
! (loop, nb_iterations_less (LT_EXPR, loop_nb, chrec1,
chrec0));
!
! case GE_EXPR:
! return set_nb_iterations_in_loop
! (loop, nb_iterations_less (LE_EXPR, loop_nb, chrec1,
chrec0));
!
! case EQ_EXPR:
! return set_nb_iterations_in_loop
! (loop, nb_iterations_eq (loop_nb, chrec0, chrec1));
!
! case NE_EXPR:
! return set_nb_iterations_in_loop
! (loop, nb_iterations_ne (loop_nb, chrec0, chrec1));
!
! default:
! return set_nb_iterations_in_loop (loop, chrec_top);
! }
default:
return set_nb_iterations_in_loop (loop, chrec_top);
--- 3327,3336 ----
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_nb,
! chrec0,
chrec1));
default:
return set_nb_iterations_in_loop (loop, chrec_top);
*************** static inline void
*** 2952,2958 ****
reset_chrecs_counters (void)
{
stats_nb_chrecs = 0;
! stats_nb_peeled = 0;
stats_nb_affine = 0;
stats_nb_affine_multivar = 0;
stats_nb_higher_poly = 0;
--- 3362,3368 ----
reset_chrecs_counters (void)
{
stats_nb_chrecs = 0;
! stats_nb_peeled_affine = 0;
stats_nb_affine = 0;
stats_nb_affine_multivar = 0;
stats_nb_higher_poly = 0;
*************** gather_chrec_stats (FILE *file, tree chr
*** 2972,2977 ****
--- 3382,3390 ----
print_generic_expr (file, chrec, 0);
fprintf (file, "\n");
+ if (chrec == NULL_TREE)
+ return;
+
switch (TREE_CODE (chrec))
{
case POLYNOMIAL_CHREC:
*************** gather_chrec_stats (FILE *file, tree chr
*** 2987,2992 ****
--- 3400,3411 ----
stats_nb_affine_multivar++;
}
+ else if (evolution_function_is_peeled_affine_p (chrec))
+ {
+ fprintf (file, " peeled_affine\n");
+ stats_nb_peeled_affine++;
+ }
+
else
{
fprintf (file, " higher_degree_polynomial\n");
*************** gather_chrec_stats (FILE *file, tree chr
*** 2995,3005 ****
break;
- case PEELED_CHREC:
- stats_nb_peeled++;
- fprintf (file, " peeled\n");
- break;
-
case EXPONENTIAL_CHREC:
stats_nb_expo++;
fprintf (file, " exponential\n");
--- 3414,3419 ----
*************** gather_chrec_stats (FILE *file, tree chr
*** 3015,3021 ****
{
stats_nb_interval_chrec++;
fprintf (file, " interval chrec\n");
! }
break;
default:
--- 3429,3435 ----
{
stats_nb_interval_chrec++;
fprintf (file, " interval chrec\n");
! }
break;
default:
*************** gather_chrec_stats (FILE *file, tree chr
*** 3029,3035 ****
}
fprintf (file, ")\n");
-
}
/* Dump the stats about the chrecs. */
--- 3443,3448 ----
*************** dump_chrecs_stats (FILE *file)
*** 3040,3055 ****
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\tpeeled 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, "-----------------------------------------\n");
! fprintf (file, "%d\twith undetermined coefficients\n",
stats_nb_undetermined);
fprintf (file, "-----------------------------------------\n");
fprintf (file, ")\n\n");
}
--- 3453,3473 ----
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",
! VARRAY_ACTIVE_SIZE (*scalar_evolution_info));
fprintf (file, "-----------------------------------------\n");
fprintf (file, ")\n\n");
}
*************** analyze_scalar_evolution_for_all_loop_ph
*** 3097,3102 ****
--- 3515,3542 ----
if (dump_file && (dump_flags & TDF_STATS))
dump_chrecs_stats (dump_file);
+ }
+
+ /* Classify the chrecs of the whole database. */
+
+ void
+ gather_stats_on_scev_database (void)
+ {
+ unsigned i;
+
+ if (!dump_file)
+ return;
+
+ reset_chrecs_counters ();
+
+ 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, MI_INNER_LOOPS_CHREC (elt));
+ }
+
+ dump_chrecs_stats (dump_file);
}
Index: tree-scalar-evolution.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-scalar-evolution.h,v
retrieving revision 1.1.2.7
diff -c -3 -p -r1.1.2.7 tree-scalar-evolution.h
*** tree-scalar-evolution.h 23 Mar 2004 20:13:28 -0000
1.1.2.7
--- tree-scalar-evolution.h 30 Mar 2004 14:44:06 -0000
*************** Software Foundation, 59 Temple Place - S
*** 22,27 ****
--- 22,29 ----
#ifndef GCC_TREE_SCALAR_EVOLUTION_H
#define GCC_TREE_SCALAR_EVOLUTION_H
+ extern tree first_iteration_non_satisfying (enum tree_code, unsigned,
+ tree,
tree);
extern tree number_of_iterations_in_loop (struct loop *);
extern tree get_loop_exit_condition (struct loop *);
*************** extern void scev_finalize (void);
*** 30,35 ****
--- 32,38 ----
extern tree analyze_scalar_evolution (unsigned, tree);
extern tree instantiate_parameters (unsigned, tree);
extern void eliminate_redundant_checks (void);
+ extern void gather_stats_on_scev_database (void);
struct scev_info_str {