------- Additional Comments From sebastian dot pop at cri dot ensmp dot fr
2005-01-02 23:15 -------
Subject: Re: [4.0 regression] Endless loop compiling simple file: Bug in
tree-scalar-evolution.c (instantiate_parameters_1)?
rakdver at gcc dot gnu dot org wrote:
>
> ------- Additional Comments From rakdver at gcc dot gnu dot org 2005-01-02
> 18:55 -------
> Caused by an exponential time complexity of instantiate_parameters.
> I am working on a patch.
>
The following patch solves the exponential time complexity.
Sorry for the inconvenient.
Sebastian
*************** instantiate_parameters_1 (struct loop *l
*** 1946,1960 ****
result again. Avoid the cyclic instantiation in mixers. */
bitmap_set_bit (already_instantiated, SSA_NAME_VERSION (chrec));
res = analyze_scalar_evolution (def_loop, chrec);
! res = instantiate_parameters_1 (loop, res, allow_superloop_chrecs);
bitmap_clear_bit (already_instantiated, SSA_NAME_VERSION (chrec));
return res;
case POLYNOMIAL_CHREC:
op0 = instantiate_parameters_1 (loop, CHREC_LEFT (chrec),
allow_superloop_chrecs);
op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec),
allow_superloop_chrecs);
if (CHREC_LEFT (chrec) != op0
|| CHREC_RIGHT (chrec) != op1)
chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
--- 2005,2026 ----
result again. Avoid the cyclic instantiation in mixers. */
bitmap_set_bit (already_instantiated, SSA_NAME_VERSION (chrec));
res = analyze_scalar_evolution (def_loop, chrec);
! if (res != chrec_dont_know)
! res = instantiate_parameters_1 (loop, res, allow_superloop_chrecs);
bitmap_clear_bit (already_instantiated, SSA_NAME_VERSION (chrec));
return res;
case POLYNOMIAL_CHREC:
op0 = instantiate_parameters_1 (loop, CHREC_LEFT (chrec),
allow_superloop_chrecs);
+ if (op0 == chrec_dont_know)
+ return chrec_dont_know;
+
op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec),
allow_superloop_chrecs);
+ if (op1 == chrec_dont_know)
+ return chrec_dont_know;
+
if (CHREC_LEFT (chrec) != op0
|| CHREC_RIGHT (chrec) != op1)
chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
*************** instantiate_parameters_1 (struct loop *l
*** 1963,1970 ****
--- 2029,2042 ----
case PLUS_EXPR:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
allow_superloop_chrecs);
+ if (op0 == chrec_dont_know)
+ return chrec_dont_know;
+
op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
allow_superloop_chrecs);
+ if (op1 == chrec_dont_know)
+ return chrec_dont_know;
+
if (TREE_OPERAND (chrec, 0) != op0
|| TREE_OPERAND (chrec, 1) != op1)
chrec = chrec_fold_plus (TREE_TYPE (chrec), op0, op1);
*************** instantiate_parameters_1 (struct loop *l
*** 1973,1980 ****
--- 2045,2058 ----
case MINUS_EXPR:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
allow_superloop_chrecs);
+ if (op0 == chrec_dont_know)
+ return chrec_dont_know;
+
op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
allow_superloop_chrecs);
+ if (op1 == chrec_dont_know)
+ return chrec_dont_know;
+
if (TREE_OPERAND (chrec, 0) != op0
|| TREE_OPERAND (chrec, 1) != op1)
chrec = chrec_fold_minus (TREE_TYPE (chrec), op0, op1);
*************** instantiate_parameters_1 (struct loop *l
*** 1983,1990 ****
--- 2061,2074 ----
case MULT_EXPR:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
allow_superloop_chrecs);
+ if (op0 == chrec_dont_know)
+ return chrec_dont_know;
+
op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
allow_superloop_chrecs);
+ if (op1 == chrec_dont_know)
+ return chrec_dont_know;
+
if (TREE_OPERAND (chrec, 0) != op0
|| TREE_OPERAND (chrec, 1) != op1)
chrec = chrec_fold_multiply (TREE_TYPE (chrec), op0, op1);
*************** instantiate_parameters_1 (struct loop *l
*** 2018,2027 ****
--- 2102,2120 ----
case 3:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
allow_superloop_chrecs);
+ if (op0 == chrec_dont_know)
+ return chrec_dont_know;
+
op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
allow_superloop_chrecs);
+ if (op1 == chrec_dont_know)
+ return chrec_dont_know;
+
op2 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 2),
allow_superloop_chrecs);
+ if (op2 == chrec_dont_know)
+ return chrec_dont_know;
+
if (op0 == chrec_dont_know
|| op1 == chrec_dont_know
|| op2 == chrec_dont_know)
*************** instantiate_parameters_1 (struct loop *l
*** 2038,2047 ****
case 2:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
allow_superloop_chrecs);
op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
allow_superloop_chrecs);
! if (op0 == chrec_dont_know
! || op1 == chrec_dont_know)
return chrec_dont_know;
if (op0 == TREE_OPERAND (chrec, 0)
--- 2131,2142 ----
case 2:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
allow_superloop_chrecs);
+ if (op0 == chrec_dont_know)
+ return chrec_dont_know;
+
op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
allow_superloop_chrecs);
! if (op1 == chrec_dont_know)
return chrec_dont_know;
if (op0 == TREE_OPERAND (chrec, 0)
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19224
