This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[lno] compute symbolic values for loop counts
- From: Sebastian Pop <sebastian dot pop at cri dot ensmp dot fr>
- To: OLGA at il dot ibm dot com, DORIT at il dot ibm dot com, gcc-patches at gcc dot gnu dot org
- Date: Tue, 27 Apr 2004 15:39:25 +0200
- Subject: [lno] compute symbolic values for loop counts
Hello,
This patch extends number_of_iterations_in_loop to compute symbolic
expression of the loop counts. Bootstrapped on amd64-unknown-freebsd5.2
BOOT_CFLAGS='-g -O2 -fscalar-evolutions -fdump-tree-scev-details
-fall-data-deps -fdump-tree-ddall -ftree-elim-checks -fdump-tree-elck-details'
* lambda-code.c (build_int_cst): Moved...
* tree-data-ref.c (int_cst_value): Moved...
* tree-ssa-loop-ivopts.c (int_cst_value, build_int_cst): Moved...
* tree.c (int_cst_value, build_int_cst): ...here.
* tree.h (int_cst_value, build_int_cst): Declare.
* tree-chrec.h (is_chrec, symbolic_parameter_expr_p): Removed.
* tree-chrec.c (evolution_function_is_affine_multivariat): Check that
the left part is a polynomial before taking its variable.
* tree-elim-check.c (prove_truth_value): Update the use of
tree_is_* functions.
* tree-fold-const.h (tree_is_ge, tree_is_gt, tree_is_le, tree_is_lt,
tree_is_eq, tree_is_ne): Return true when decidable, and use a
parameter for returning the result.
* tree-scalar-evolution.c (types_forbid_solutions_p): Removed.
(first_iteration_non_satisfying_noev_noev,
first_iteration_non_satisfying_noev_ev,
first_iteration_non_satisfying_ev_noev): Update the use of
tree_is_* functions. Use no_evolution_in_loop_p instead of
evolution_function_is_constant_p. Extends the analyzer to
symbolic loop counts.
(first_iteration_non_satisfying): Factorize code.
Index: lambda-code.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/lambda-code.c,v
retrieving revision 1.1.2.6
diff -c -3 -p -r1.1.2.6 lambda-code.c
*** lambda-code.c 25 Apr 2004 20:33:31 -0000 1.1.2.6
--- lambda-code.c 27 Apr 2004 13:38:38 -0000
*************** gcc_loopnest_to_lambda_loopnest (struct
*** 1341,1374 ****
}
- static tree build_int_cst (tree type, unsigned HOST_WIDE_INT val);
-
- /* Builds integer constant of type TYPE and value VAL.
- Borrowed from tree-ssa-loop-ivopts.c
- XXX: Move this into tree.c and remove from both files. */
-
- static tree
- build_int_cst (tree type, unsigned HOST_WIDE_INT val)
- {
- unsigned bits = TYPE_PRECISION (type);
- bool signed_p = !TYPE_UNSIGNED (type);
- bool negative = ((val >> (bits - 1)) & 1) != 0;
- tree ival;
-
- if (signed_p && negative)
- {
- val = val | (~(unsigned HOST_WIDE_INT) 0 << (bits - 1) << 1);
- ival = build_int_2 (val, -1);
- }
- else
- {
- val = val & ~(~(unsigned HOST_WIDE_INT) 0 << (bits - 1) << 1);
- ival = build_int_2 (val, 0);
- }
-
- return convert (type, ival);
- }
-
/* Convert a lambda body vector to a gcc tree. */
static tree
--- 1341,1346 ----
Index: tree-chrec.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-chrec.c,v
retrieving revision 1.1.2.18
diff -c -3 -p -r1.1.2.18 tree-chrec.c
*** tree-chrec.c 21 Apr 2004 17:18:54 -0000 1.1.2.18
--- tree-chrec.c 27 Apr 2004 13:38:39 -0000
*************** evolution_function_is_affine_multivariat
*** 1884,1889 ****
--- 1884,1890 ----
else
{
if (evolution_function_is_constant_p (CHREC_RIGHT (chrec))
+ && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
&& CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)
&& evolution_function_is_affine_multivariate_p
(CHREC_LEFT (chrec)))
Index: tree-chrec.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-chrec.h,v
retrieving revision 1.1.2.14
diff -c -3 -p -r1.1.2.14 tree-chrec.h
*** tree-chrec.h 21 Apr 2004 17:18:54 -0000 1.1.2.14
--- tree-chrec.h 27 Apr 2004 13:38:39 -0000
*************** extern tree chrec_not_analyzed_yet;
*** 40,47 ****
extern tree chrec_top;
extern tree chrec_bot;
- static inline bool automatically_generated_chrec_p (tree);
-
/* After having added an automatically generated element, please
include it in the following function. */
--- 40,45 ----
*************** tree_is_chrec (tree expr)
*** 69,80 ****
- /* Constructors. */
- static inline tree build_interval_chrec (tree, tree);
- static inline tree build_polynomial_chrec (unsigned, tree, tree);
- static inline tree build_exponential_chrec (unsigned, tree, tree);
- static inline tree build_peeled_chrec (unsigned, tree, tree);
-
/* Chrec folding functions. */
extern tree chrec_fold_plus (tree, tree, tree);
extern tree chrec_fold_minus (tree, tree, tree);
--- 67,72 ----
*************** extern bool chrec_contains_intervals (tr
*** 107,118 ****
extern bool tree_contains_chrecs (tree);
extern bool evolution_function_is_affine_multivariate_p (tree);
extern bool evolution_function_is_univariate_p (tree);
- static inline bool is_chrec (tree);
- static inline bool chrec_zerop (tree);
- static inline bool symbolic_parameter_expr_p (tree);
- 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);
--- 99,104 ----
*************** build_peeled_chrec (unsigned loop_num,
*** 171,196 ****
/* Observers. */
- /* Determine whether the given tree is a chain of recurrence or not. */
-
- static inline bool
- is_chrec (tree chrec)
- {
- if (chrec == NULL_TREE)
- return false;
-
- switch (TREE_CODE (chrec))
- {
- case POLYNOMIAL_CHREC:
- case EXPONENTIAL_CHREC:
- case INTERVAL_CHREC:
- return true;
-
- default:
- return false;
- }
- }
-
/* Determines whether CHREC is equal to zero. */
static inline bool
--- 157,162 ----
*************** chrec_zerop (tree chrec)
*** 205,234 ****
if (TREE_CODE (chrec) == INTERVAL_CHREC)
return (integer_zerop (CHREC_LOW (chrec))
&& integer_zerop (CHREC_UP (chrec)));
-
- return false;
- }
-
- /* Determines whether the expression CHREC is a symbolic parameter.
- Be aware of the fact that the expression is supposed to be part of
- an evolution function, and not an expression from the AST of the
- program.
-
- A symbolic parameter is matches the following pattern: "a variable
- that does not have a loop-phi node", this variable is either a loop
- invariant, or a secondary induction variable.
- */
-
- static inline bool
- symbolic_parameter_expr_p (tree chrec)
- {
- if (chrec == NULL_TREE)
- return false;
-
- if (TREE_CODE (chrec) == VAR_DECL
- || TREE_CODE (chrec) == PARM_DECL
- || TREE_CODE (chrec) == SSA_NAME)
- return true;
return false;
}
--- 171,176 ----
Index: tree-data-ref.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-data-ref.c,v
retrieving revision 1.1.2.16
diff -c -3 -p -r1.1.2.16 tree-data-ref.c
*** tree-data-ref.c 20 Apr 2004 13:49:24 -0000 1.1.2.16
--- tree-data-ref.c 27 Apr 2004 13:38:39 -0000
*************** subscript_dependence_tester (struct data
*** 1200,1224 ****
fprintf (dump_file, ")\n");
}
- /* Return value of a constant X.
- Borrowed from tree-ssa-loop-ivopts.c
- XXX: Move this into tree.c and remove from both files. */
-
- static HOST_WIDE_INT
- int_cst_value (tree x)
- {
- unsigned bits = TYPE_PRECISION (TREE_TYPE (x));
- unsigned HOST_WIDE_INT val = TREE_INT_CST_LOW (x);
- bool negative = ((val >> (bits - 1)) & 1) != 0;
-
- if (negative)
- val |= (~(unsigned HOST_WIDE_INT) 0) << (bits - 1) << 1;
- else
- val &= ~((~(unsigned HOST_WIDE_INT) 0) << (bits - 1) << 1);
-
- return val;
- }
-
/* Compute the classic per loop distance vector. */
static void
--- 1200,1205 ----
Index: tree-elim-check.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-elim-check.c,v
retrieving revision 1.1.2.8
diff -c -3 -p -r1.1.2.8 tree-elim-check.c
*** tree-elim-check.c 25 Apr 2004 20:33:42 -0000 1.1.2.8
--- tree-elim-check.c 27 Apr 2004 13:38:39 -0000
*************** Software Foundation, 59 Temple Place - S
*** 69,75 ****
#include "tree-pass.h"
#include "flags.h"
-
/* 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. */
--- 69,74 ----
*************** prove_truth_value (enum tree_code code,
*** 242,247 ****
--- 241,247 ----
tree nb_iters_in_loop,
bool *value)
{
+ bool val = false;
tree nb_iters_in_then, nb_iters_in_else;
if (automatically_generated_chrec_p (nb_iters_in_loop))
*************** prove_truth_value (enum tree_code code,
*** 287,300 ****
&& TREE_CODE (nb_iters_in_else) == INTEGER_CST)
{
if (integer_zerop (nb_iters_in_then)
! && tree_is_ge (nb_iters_in_else, nb_iters_in_loop))
{
*value = false;
return true;
}
if (integer_zerop (nb_iters_in_else)
! && tree_is_ge (nb_iters_in_then, nb_iters_in_loop))
{
*value = true;
return true;
--- 287,302 ----
&& TREE_CODE (nb_iters_in_else) == INTEGER_CST)
{
if (integer_zerop (nb_iters_in_then)
! && tree_is_ge (nb_iters_in_else, nb_iters_in_loop, &val)
! && val)
{
*value = false;
return true;
}
if (integer_zerop (nb_iters_in_else)
! && tree_is_ge (nb_iters_in_then, nb_iters_in_loop, &val)
! && val)
{
*value = true;
return true;
Index: tree-fold-const.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-fold-const.h,v
retrieving revision 1.1.2.7
diff -c -3 -p -r1.1.2.7 tree-fold-const.h
*** tree-fold-const.h 15 Apr 2004 15:27:51 -0000 1.1.2.7
--- tree-fold-const.h 27 Apr 2004 13:38:39 -0000
*************** tree_fold_divides_p (tree type,
*** 191,245 ****
/* Given two integer constants A and B, determine whether "A >= B". */
static inline bool
! tree_is_ge (tree a, tree b)
{
tree cmp = fold (build (GE_EXPR, boolean_type_node, a, b));
! return (tree_int_cst_sgn (cmp) != 0);
}
/* Given two integer constants A and B, determine whether "A > B". */
static inline bool
! tree_is_gt (tree a, tree b)
{
tree cmp = fold (build (GT_EXPR, boolean_type_node, a, b));
! return (tree_int_cst_sgn (cmp) != 0);
}
/* Given two integer constants A and B, determine whether "A <= B". */
static inline bool
! tree_is_le (tree a, tree b)
{
tree cmp = fold (build (LE_EXPR, boolean_type_node, a, b));
! return (tree_int_cst_sgn (cmp) != 0);
}
/* Given two integer constants A and B, determine whether "A < B". */
static inline bool
! tree_is_lt (tree a, tree b)
{
tree cmp = fold (build (LT_EXPR, boolean_type_node, a, b));
! return (tree_int_cst_sgn (cmp) != 0);
}
/* Given two integer constants A and B, determine whether "A == B". */
static inline bool
! tree_is_eq (tree a, tree b)
{
tree cmp = fold (build (EQ_EXPR, boolean_type_node, a, b));
! 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 */
--- 191,269 ----
/* Given two integer constants A and B, determine whether "A >= B". */
static inline bool
! tree_is_ge (tree a, tree b, bool *res)
{
tree cmp = fold (build (GE_EXPR, boolean_type_node, a, b));
! if (TREE_CODE (cmp) != INTEGER_CST)
! return false;
!
! *res = (tree_int_cst_sgn (cmp) != 0);
! return true;
}
/* Given two integer constants A and B, determine whether "A > B". */
static inline bool
! tree_is_gt (tree a, tree b, bool *res)
{
tree cmp = fold (build (GT_EXPR, boolean_type_node, a, b));
! if (TREE_CODE (cmp) != INTEGER_CST)
! return false;
!
! *res = (tree_int_cst_sgn (cmp) != 0);
! return true;
}
/* Given two integer constants A and B, determine whether "A <= B". */
static inline bool
! tree_is_le (tree a, tree b, bool *res)
{
tree cmp = fold (build (LE_EXPR, boolean_type_node, a, b));
! if (TREE_CODE (cmp) != INTEGER_CST)
! return false;
!
! *res = (tree_int_cst_sgn (cmp) != 0);
! return true;
}
/* Given two integer constants A and B, determine whether "A < B". */
static inline bool
! tree_is_lt (tree a, tree b, bool *res)
{
tree cmp = fold (build (LT_EXPR, boolean_type_node, a, b));
! if (TREE_CODE (cmp) != INTEGER_CST)
! return false;
!
! *res = (tree_int_cst_sgn (cmp) != 0);
! return true;
}
/* Given two integer constants A and B, determine whether "A == B". */
static inline bool
! tree_is_eq (tree a, tree b, bool *res)
{
tree cmp = fold (build (EQ_EXPR, boolean_type_node, a, b));
! if (TREE_CODE (cmp) != INTEGER_CST)
! return false;
!
! *res = (tree_int_cst_sgn (cmp) != 0);
! return true;
}
/* Given two integer constants A and B, determine whether "A != B". */
static inline bool
! tree_is_ne (tree a, tree b, bool *res)
{
tree cmp = fold (build (NE_EXPR, boolean_type_node, a, b));
! if (TREE_CODE (cmp) != INTEGER_CST)
! return false;
!
! *res = (tree_int_cst_sgn (cmp) != 0);
! return true;
}
#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.42
diff -c -3 -p -r1.1.2.42 tree-scalar-evolution.c
*** tree-scalar-evolution.c 23 Apr 2004 14:26:01 -0000 1.1.2.42
--- tree-scalar-evolution.c 27 Apr 2004 13:38:39 -0000
*************** multiply_evolution (unsigned loop_nb,
*** 1029,1068 ****
/* 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. */
--- 1029,1034 ----
*************** first_iteration_non_satisfying_noev_noev
*** 1072,1077 ****
--- 1038,1044 ----
tree chrec0,
tree chrec1)
{
+ bool val = false;
tree init0 = initial_condition (chrec0);
tree init1 = initial_condition (chrec1);
*************** first_iteration_non_satisfying_noev_noev
*** 1079,1117 ****
|| 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
--- 1046,1084 ----
|| TREE_CODE (init1) != INTEGER_CST)
return chrec_top;
switch (code)
{
case LE_EXPR:
! if (!tree_is_gt (init0, init1, &val))
! return chrec_top;
! break;
!
case LT_EXPR:
! if (!tree_is_ge (init0, init1, &val))
! return chrec_top;
! break;
!
case EQ_EXPR:
! if (!tree_is_eq (init0, init1, &val))
! return chrec_top;
! break;
!
case NE_EXPR:
! if (!tree_is_ne (init0, init1, &val))
! return chrec_top;
! break;
!
default:
return chrec_top;
}
+
+ if (val)
+ return integer_zero_node;
+ else if (evolution_function_is_constant_p (chrec0)
+ && evolution_function_is_constant_p (chrec1))
+ return chrec_bot;
+ else
+ return chrec_top;
}
/* Helper function for the case when CHREC0 has no evolution and
*************** first_iteration_non_satisfying_noev_ev (
*** 1123,1128 ****
--- 1090,1096 ----
tree chrec0,
tree chrec1)
{
+ bool val = false;
tree type1 = chrec_type (chrec1);
/* tree tmax = TYPE_MAX_VALUE (type1); */
tree ev_in_this_loop;
*************** first_iteration_non_satisfying_noev_ev (
*** 1137,1144 ****
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;
--- 1105,1114 ----
init1 = CHREC_LEFT (ev_in_this_loop);
step1 = CHREC_RIGHT (ev_in_this_loop);
init0 = initial_condition (chrec0);
! if (!no_evolution_in_loop_p (init0, loop_nb, &val)
! || val == false
! || !no_evolution_in_loop_p (init1, loop_nb, &val)
! || val == false
|| TREE_CODE (step1) != INTEGER_CST)
/* For the moment we deal only with INTEGER_CSTs. */
return chrec_top;
*************** first_iteration_non_satisfying_noev_ev (
*** 1147,1153 ****
{
case LE_EXPR:
{
! if (tree_is_gt (init0, init1))
{
if (evolution_function_is_constant_p (chrec0))
/* Example: "while (2 <= {0, +, 1}_2)". */
--- 1117,1123 ----
{
case LE_EXPR:
{
! if (tree_is_gt (init0, init1, &val) && val)
{
if (evolution_function_is_constant_p (chrec0))
/* Example: "while (2 <= {0, +, 1}_2)". */
*************** first_iteration_non_satisfying_noev_ev (
*** 1179,1185 ****
else
{
! if (evolution_function_is_constant_p (chrec0))
/* Example: "while (2 <= {3, +, -1}_2)". */
nb_iters = tree_fold_plus
(integer_type_node,
--- 1149,1156 ----
else
{
! if (evolution_function_is_constant_p (chrec0)
! || tree_does_not_contain_chrecs (chrec0))
/* Example: "while (2 <= {3, +, -1}_2)". */
nb_iters = tree_fold_plus
(integer_type_node,
*************** first_iteration_non_satisfying_noev_ev (
*** 1195,1206 ****
}
/* 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
--- 1166,1176 ----
}
/* Verify the result. */
! if (tree_is_gt (init0,
! tree_fold_plus
! (type1, init1, tree_fold_multiply
! (integer_type_node, nb_iters, step1)), &val)
! && val)
return nb_iters;
else
*************** first_iteration_non_satisfying_noev_ev (
*** 1213,1219 ****
case LT_EXPR:
{
! if (tree_is_ge (init0, init1))
{
if (evolution_function_is_constant_p (chrec0))
/* Example: "while (2 < {0, +, 1}_2)". */
--- 1183,1189 ----
case LT_EXPR:
{
! if (tree_is_ge (init0, init1, &val) && val)
{
if (evolution_function_is_constant_p (chrec0))
/* Example: "while (2 < {0, +, 1}_2)". */
*************** first_iteration_non_satisfying_noev_ev (
*** 1239,1245 ****
}
else
{
! if (evolution_function_is_constant_p (chrec0))
/* Example: "while (2 < {3, +, -1}_2)". */
nb_iters = tree_fold_ceil_div
(integer_type_node,
--- 1209,1216 ----
}
else
{
! if (evolution_function_is_constant_p (chrec0)
! || tree_does_not_contain_chrecs (chrec0))
/* Example: "while (2 < {3, +, -1}_2)". */
nb_iters = tree_fold_ceil_div
(integer_type_node,
*************** first_iteration_non_satisfying_noev_ev (
*** 1251,1262 ****
}
/* 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
--- 1222,1232 ----
}
/* Verify the result. */
! if (tree_is_ge (init0,
! tree_fold_plus
! (type1, init1, tree_fold_multiply
! (integer_type_node, nb_iters, step1)), &val)
! && val)
return nb_iters;
else
*************** first_iteration_non_satisfying_noev_ev (
*** 1266,1272 ****
case EQ_EXPR:
{
! if (tree_is_ne (init0, init1))
{
if (evolution_function_is_constant_p (chrec0))
/* Example: "while (2 == {0, +, 1}_2)". */
--- 1236,1242 ----
case EQ_EXPR:
{
! if (tree_is_ne (init0, init1, &val) && val)
{
if (evolution_function_is_constant_p (chrec0))
/* Example: "while (2 == {0, +, 1}_2)". */
*************** first_iteration_non_satisfying_noev_ev (
*** 1290,1296 ****
case NE_EXPR:
{
! if (tree_is_eq (init0, init1))
{
if (evolution_function_is_constant_p (chrec0))
/* Example: "while (0 != {0, +, 1}_2)". */
--- 1260,1266 ----
case NE_EXPR:
{
! if (tree_is_eq (init0, init1, &val) && val)
{
if (evolution_function_is_constant_p (chrec0))
/* Example: "while (0 != {0, +, 1}_2)". */
*************** first_iteration_non_satisfying_noev_ev (
*** 1302,1310 ****
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);
--- 1272,1281 ----
if (tree_int_cst_sgn (step1) > 0)
{
! if (evolution_function_is_constant_p (chrec0)
! || tree_does_not_contain_chrecs (chrec0))
{
! if (tree_is_gt (init0, init1, &val) && val)
{
tree diff = tree_fold_minus (integer_type_node,
init0, init1);
*************** first_iteration_non_satisfying_noev_ev (
*** 1327,1335 ****
else
{
! if (evolution_function_is_constant_p (chrec0))
{
! if (tree_is_lt (init0, init1))
{
tree diff = tree_fold_minus (integer_type_node,
init1, init0);
--- 1298,1307 ----
else
{
! if (evolution_function_is_constant_p (chrec0)
! || tree_does_not_contain_chrecs (chrec0))
{
! if (tree_is_lt (init0, init1, &val) && val)
{
tree diff = tree_fold_minus (integer_type_node,
init1, init0);
*************** first_iteration_non_satisfying_noev_ev (
*** 1352,1363 ****
}
/* 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
--- 1324,1334 ----
}
/* Verify the result. */
! if (tree_is_eq (init0,
! tree_fold_plus
! (type1, init1, tree_fold_multiply
! (integer_type_node, nb_iters, step1)), &val)
! && val)
return nb_iters;
else
*************** first_iteration_non_satisfying_ev_noev (
*** 1380,1385 ****
--- 1351,1357 ----
tree chrec0,
tree chrec1)
{
+ bool val = false;
tree type0 = chrec_type (chrec0);
/* tree tmin = TYPE_MIN_VALUE (type0); */
tree ev_in_this_loop;
*************** first_iteration_non_satisfying_ev_noev (
*** 1394,1401 ****
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;
--- 1366,1375 ----
init0 = CHREC_LEFT (ev_in_this_loop);
step0 = CHREC_RIGHT (ev_in_this_loop);
init1 = initial_condition (chrec1);
! if (!no_evolution_in_loop_p (init0, loop_nb, &val)
! || val == false
! || !no_evolution_in_loop_p (init1, loop_nb, &val)
! || val == false
|| TREE_CODE (step0) != INTEGER_CST)
/* For the moment we deal only with INTEGER_CSTs. */
return chrec_top;
*************** first_iteration_non_satisfying_ev_noev (
*** 1404,1410 ****
{
case LE_EXPR:
{
! if (tree_is_gt (init0, init1))
{
if (evolution_function_is_constant_p (chrec1))
/* Example: "while ({2, +, 1}_2 <= 0)". */
--- 1378,1384 ----
{
case LE_EXPR:
{
! if (tree_is_gt (init0, init1, &val) && val)
{
if (evolution_function_is_constant_p (chrec1))
/* Example: "while ({2, +, 1}_2 <= 0)". */
*************** first_iteration_non_satisfying_ev_noev (
*** 1435,1441 ****
}
else
{
! if (evolution_function_is_constant_p (chrec1))
/* Example: "while ({2, +, 1}_2 <= 3)". */
nb_iters = tree_fold_plus
(integer_type_node,
--- 1409,1416 ----
}
else
{
! if (evolution_function_is_constant_p (chrec1)
! || tree_does_not_contain_chrecs (chrec1))
/* Example: "while ({2, +, 1}_2 <= 3)". */
nb_iters = tree_fold_plus
(integer_type_node,
*************** first_iteration_non_satisfying_ev_noev (
*** 1450,1461 ****
}
/* 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
--- 1425,1434 ----
}
/* Verify the result. */
! if (tree_is_gt (tree_fold_plus
! (type0, init0, tree_fold_multiply
! (integer_type_node, nb_iters, step0)), init1, &val)
! && val)
return nb_iters;
else
*************** first_iteration_non_satisfying_ev_noev (
*** 1465,1471 ****
case LT_EXPR:
{
! if (tree_is_ge (init0, init1))
{
if (evolution_function_is_constant_p (chrec1))
/* Example: "while ({2, +, 1}_2 < 0)". */
--- 1438,1444 ----
case LT_EXPR:
{
! if (tree_is_ge (init0, init1, &val) && val)
{
if (evolution_function_is_constant_p (chrec1))
/* Example: "while ({2, +, 1}_2 < 0)". */
*************** first_iteration_non_satisfying_ev_noev (
*** 1492,1515 ****
}
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
--- 1465,1487 ----
}
else
{
! if (evolution_function_is_constant_p (chrec1)
! || tree_does_not_contain_chrecs (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 (tree_is_ge (tree_fold_plus
! (type0, init0, tree_fold_multiply
! (integer_type_node, nb_iters, step0)), init1, &val)
! && val)
return nb_iters;
else
*************** first_iteration_non_satisfying_ev_noev (
*** 1519,1525 ****
case EQ_EXPR:
{
! if (tree_is_ne (init0, init1))
{
if (evolution_function_is_constant_p (chrec1))
/* Example: "while ({2, +, 1}_2 == 0)". */
--- 1491,1497 ----
case EQ_EXPR:
{
! if (tree_is_ne (init0, init1, &val) && val)
{
if (evolution_function_is_constant_p (chrec1))
/* Example: "while ({2, +, 1}_2 == 0)". */
*************** first_iteration_non_satisfying_ev_noev (
*** 1543,1549 ****
case NE_EXPR:
{
! if (tree_is_eq (init0, init1))
{
if (evolution_function_is_constant_p (chrec1))
/* Example: "while ({0, +, 1}_2 != 0)". */
--- 1515,1521 ----
case NE_EXPR:
{
! if (tree_is_eq (init0, init1, &val) && val)
{
if (evolution_function_is_constant_p (chrec1))
/* Example: "while ({0, +, 1}_2 != 0)". */
*************** first_iteration_non_satisfying_ev_noev (
*** 1555,1563 ****
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);
--- 1527,1536 ----
if (tree_int_cst_sgn (step0) > 0)
{
! if (evolution_function_is_constant_p (chrec1)
! || tree_does_not_contain_chrecs (chrec1))
{
! if (tree_is_lt (init0, init1, &val) && val)
{
tree diff = tree_fold_minus (integer_type_node,
init1, init0);
*************** first_iteration_non_satisfying_ev_noev (
*** 1580,1588 ****
else
{
! if (evolution_function_is_constant_p (chrec1))
{
! if (tree_is_gt (init0, init1))
{
tree diff = tree_fold_minus (integer_type_node,
init0, init1);
--- 1553,1562 ----
else
{
! if (evolution_function_is_constant_p (chrec1)
! || tree_does_not_contain_chrecs (chrec1))
{
! if (tree_is_gt (init0, init1, &val) && val)
{
tree diff = tree_fold_minus (integer_type_node,
init0, init1);
*************** first_iteration_non_satisfying_ev_noev (
*** 1605,1616 ****
}
/* 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. */
--- 1579,1588 ----
}
/* Verify the result. */
! if (tree_is_eq (tree_fold_plus
! (type0, init0, tree_fold_multiply
! (integer_type_node, nb_iters, step0)), init1, &val)
! && val)
return nb_iters;
else
/* Difficult cases fall down there. */
*************** first_iteration_non_satisfying (enum tre
*** 1737,1766 ****
{
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;
}
--- 1709,1726 ----
{
switch (code)
{
+ case EQ_EXPR:
+ case NE_EXPR:
case LT_EXPR:
case LE_EXPR:
! return first_iteration_non_satisfying_1 (code, 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);
default:
return chrec_top;
}
Index: tree-ssa-loop-ivopts.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-loop-ivopts.c,v
retrieving revision 1.1.2.30
diff -c -3 -p -r1.1.2.30 tree-ssa-loop-ivopts.c
*** tree-ssa-loop-ivopts.c 25 Apr 2004 20:33:43 -0000 1.1.2.30
--- tree-ssa-loop-ivopts.c 27 Apr 2004 13:38:39 -0000
*************** cst_and_fits_in_hwi (tree x)
*** 497,543 ****
|| TREE_INT_CST_HIGH (x) == -1);
}
- /* Return value of a constant X. */
-
- static HOST_WIDE_INT
- int_cst_value (tree x)
- {
- unsigned bits = TYPE_PRECISION (TREE_TYPE (x));
- unsigned HOST_WIDE_INT val = TREE_INT_CST_LOW (x);
- bool negative = ((val >> (bits - 1)) & 1) != 0;
-
- if (negative)
- val |= (~(unsigned HOST_WIDE_INT) 0) << (bits - 1) << 1;
- else
- val &= ~((~(unsigned HOST_WIDE_INT) 0) << (bits - 1) << 1);
-
- return val;
- }
-
- /* Builds integer constant of type TYPE and value VAL. */
-
- static tree
- build_int_cst (tree type, unsigned HOST_WIDE_INT val)
- {
- unsigned bits = TYPE_PRECISION (type);
- bool signed_p = !TYPE_UNSIGNED (type);
- bool negative = ((val >> (bits - 1)) & 1) != 0;
- tree ival;
-
- if (signed_p && negative)
- {
- val = val | (~(unsigned HOST_WIDE_INT) 0 << (bits - 1) << 1);
- ival = build_int_2 (val, -1);
- }
- else
- {
- val = val & ~(~(unsigned HOST_WIDE_INT) 0 << (bits - 1) << 1);
- ival = build_int_2 (val, 0);
- }
-
- return convert (type, ival);
- }
-
/* Checks whether there exists number X such that X * B = A, counting modulo
2^BITS. */
--- 497,502 ----
Index: tree.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.c,v
retrieving revision 1.263.2.75.2.6
diff -c -3 -p -r1.263.2.75.2.6 tree.c
*** tree.c 25 Apr 2004 20:33:43 -0000 1.263.2.75.2.6
--- tree.c 27 Apr 2004 13:38:39 -0000
*************** needs_to_live_in_memory (tree t)
*** 5584,5587 ****
--- 5584,5628 ----
|| decl_function_context (t) != current_function_decl);
}
+ /* Return value of a constant X. */
+
+ HOST_WIDE_INT
+ int_cst_value (tree x)
+ {
+ unsigned bits = TYPE_PRECISION (TREE_TYPE (x));
+ unsigned HOST_WIDE_INT val = TREE_INT_CST_LOW (x);
+ bool negative = ((val >> (bits - 1)) & 1) != 0;
+
+ if (negative)
+ val |= (~(unsigned HOST_WIDE_INT) 0) << (bits - 1) << 1;
+ else
+ val &= ~((~(unsigned HOST_WIDE_INT) 0) << (bits - 1) << 1);
+
+ return val;
+ }
+
+ /* Builds integer constant of type TYPE and value VAL. */
+
+ tree
+ build_int_cst (tree type, unsigned HOST_WIDE_INT val)
+ {
+ unsigned bits = TYPE_PRECISION (type);
+ bool signed_p = !TYPE_UNSIGNED (type);
+ bool negative = ((val >> (bits - 1)) & 1) != 0;
+ tree ival;
+
+ if (signed_p && negative)
+ {
+ val = val | (~(unsigned HOST_WIDE_INT) 0 << (bits - 1) << 1);
+ ival = build_int_2 (val, -1);
+ }
+ else
+ {
+ val = val & ~(~(unsigned HOST_WIDE_INT) 0 << (bits - 1) << 1);
+ ival = build_int_2 (val, 0);
+ }
+
+ return convert (type, ival);
+ }
+
#include "gt-tree.h"
Index: tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.h,v
retrieving revision 1.342.2.154.2.11
diff -c -3 -p -r1.342.2.154.2.11 tree.h
*** tree.h 25 Apr 2004 20:33:44 -0000 1.342.2.154.2.11
--- tree.h 27 Apr 2004 13:38:40 -0000
*************** extern void init_ttree (void);
*** 3517,3522 ****
--- 3517,3524 ----
extern void build_common_tree_nodes (int);
extern void build_common_tree_nodes_2 (int);
extern tree build_range_type (tree, tree, tree);
+ extern HOST_WIDE_INT int_cst_value (tree);
+ extern tree build_int_cst (tree, unsigned HOST_WIDE_INT);
/* In function.c */
extern void setjmp_protect_args (void);