Re: [lno] 50% runtime performance regression since yesterday

[Sebastian Pop <sebastian dot pop at cri dot ensmp dot fr>]

On Wed, Jun 23, 2004 at 10:28:50AM +0200, Richard Guenther wrote:
> You introduced a 50% runtime performance regression to lno.  lno is now
> slightly worse than mainline with -O2 -funroll-loops on the tramp3d-v3
> testcase while it was 50% better before.
> 
> May it be all the removal of CHREC nodes?  

I don't think that removing the intervals is the problem.  Probably
the problem comes from the replace of the checks of chrec_top with the
calls to chrec_contains_undetermined.  Some parts of the analyzer have
to be more careful when testing for undetermined elements than the
users of the information because the analyzer only has a partial
knowledge during the analysis.  Unfortunately the call to
chrec_contains_undetermined contains a check for
chrec_not_analyzed_yet:

  if (chrec == chrec_dont_know
      || chrec == chrec_not_analyzed_yet
      || chrec == NULL_TREE)
    return true;

that could lead the analyzer to an over conservative answer before
even performing any analysis.

Does the following patch fix the optimization regression?

Sebastian.


*** tree-scalar-evolution.c.~1.1.2.61.~	Tue Jun 22 10:57:22 2004
--- tree-scalar-evolution.c	Wed Jun 23 09:11:15 2004
*************** Software Foundation, 59 Temple Place - S
*** 36,43 ****
       
     - When the definition is a MODIFY_EXPR: if the right hand side
     (RHS) of the definition cannot be statically analyzed, the answer
!    of the analyzer is: "don't know", that corresponds to the
!    conservative [-oo, +oo] element of the lattice of intervals.
     Otherwise, for all the variables that are not yet analyzed in the
     RHS, try to determine their evolution, and finally try to
     evaluate the operation of the RHS that gives the evolution
--- 36,42 ----
       
     - When the definition is a MODIFY_EXPR: if the right hand side
     (RHS) of the definition cannot be statically analyzed, the answer
!    of the analyzer is: "don't know".  
     Otherwise, for all the variables that are not yet analyzed in the
     RHS, try to determine their evolution, and finally try to
     evaluate the operation of the RHS that gives the evolution
*************** compute_overall_effect_of_inner_loop (st
*** 480,486 ****
  {
    bool val = false;
  
!   if (chrec_contains_undetermined (evolution_fn))
      return chrec_dont_know;
  
    else if (TREE_CODE (evolution_fn) == POLYNOMIAL_CHREC)
--- 479,485 ----
  {
    bool val = false;
  
!   if (evolution_fn == chrec_dont_know)
      return chrec_dont_know;
  
    else if (TREE_CODE (evolution_fn) == POLYNOMIAL_CHREC)
*************** compute_overall_effect_of_inner_loop (st
*** 491,497 ****
  	    loop_from_num (current_loops, CHREC_VARIABLE (evolution_fn));
  	  tree nb_iter = number_of_iterations_in_loop (inner_loop);
  
! 	  if (chrec_contains_undetermined (nb_iter))
  	    return chrec_dont_know;
  	  else
  	    {
--- 490,496 ----
  	    loop_from_num (current_loops, CHREC_VARIABLE (evolution_fn));
  	  tree nb_iter = number_of_iterations_in_loop (inner_loop);
  
! 	  if (nb_iter == chrec_dont_know)
  	    return chrec_dont_know;
  	  else
  	    {
*************** add_to_evolution_1 (unsigned loop_nb, 
*** 717,723 ****
        
      default:
        /* These nodes do not depend on a loop.  */
!       if (chrec_contains_undetermined (chrec_before))
  	return chrec_dont_know;
        return build_polynomial_chrec (loop_nb, chrec_before, to_add);
      }
--- 716,722 ----
        
      default:
        /* These nodes do not depend on a loop.  */
!       if (chrec_before == chrec_dont_know)
  	return chrec_dont_know;
        return build_polynomial_chrec (loop_nb, chrec_before, to_add);
      }
*************** analyze_scalar_evolution_1 (struct loop 
*** 1864,1870 ****
   set_and_end:
  
    /* Keep the symbolic form.  */
!   if (chrec_contains_undetermined (res))
      res = var;
  
    if (loop == def_loop)
--- 1863,1869 ----
   set_and_end:
  
    /* Keep the symbolic form.  */
!   if (res == chrec_dont_know)
      res = var;
  
    if (loop == def_loop)
*************** analyze_scalar_evolution (struct loop *l
*** 1905,1912 ****
  
    res = analyze_scalar_evolution_1 (loop, var, get_scalar_evolution (var));
  
!   if (TREE_CODE (var) == SSA_NAME && 
!       chrec_contains_undetermined (res))
      res = var;
  
    if (dump_file && (dump_flags & TDF_DETAILS))
--- 1904,1910 ----
  
    res = analyze_scalar_evolution_1 (loop, var, get_scalar_evolution (var));
  
!   if (TREE_CODE (var) == SSA_NAME && res == chrec_dont_know)
      res = var;
  
    if (dump_file && (dump_flags & TDF_DETAILS))