[Bug tree-optimization/19224] [4.0 regression] Endless loop compiling simple file: Bug in tree-scalar-evolution.c (instantiate_parameters_1)?

[sebastian dot pop at cri dot ensmp dot fr]

------- 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