This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[lno] spec failures


On Thu, May 20, 2004 at 12:01:20AM +0200, Zdenek Dvorak wrote:
> 
> Sebastian, this seems to be yours.  The bug works this way:
> 
> for (i = 0; i < n; i++)
>   for (j = 0; j < i; j++)
>     something ();
> 
> when you determine number of iterations of the inner loop,
> you see {0, +, 1}_2 as an induction variable and {0, +, 1}_1
> as an upper bound.  However in the
> first_iteration_non_satisfying_ev_noev you call initial_condition
> on the upper bound, which is clearly nonsense, as it returns 0
> and number_of_iterations_cond concludes that the inner loop does not
> roll at all.
> 

The answer of the analyzer has a sense: "0" is the number of
iterations for the first iteration in loop_1.  The problem is that the
analyzer forgets to keep track of the rest of the evolution for the
outer loop.  The first part of following patch fixes this problem.

	* tree-scalar-evolution.c (first_iteration_non_satisfying_1): 
	Include the evolution of the non varying chrec in other_evs.
	(number_of_iterations_in_loop): Don't instantiate the chrecs
	before the computation of loop counts.

Index: tree-scalar-evolution.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-scalar-evolution.c,v
retrieving revision 1.1.2.48
diff -c -c -3 -p -r1.1.2.48 tree-scalar-evolution.c
*** tree-scalar-evolution.c	19 May 2004 22:05:04 -0000	1.1.2.48
--- tree-scalar-evolution.c	24 May 2004 09:17:36 -0000
*************** first_iteration_non_satisfying_1 (enum t
*** 1276,1281 ****
--- 1276,1283 ----
  	    return res;
  	  
  	  other_evs = hide_evolution_in_loop (chrec1, loop_nb);
+ 	  other_evs = chrec_fold_minus (chrec_type (other_evs), 
+ 					other_evs, chrec0);
  	  other_evs = chrec_replace_initial_condition 
  	    (other_evs, convert (chrec_type (other_evs), integer_zero_node));
  	}
*************** first_iteration_non_satisfying_1 (enum t
*** 1294,1299 ****
--- 1296,1303 ----
  	    return res;
  	  
  	  other_evs = hide_evolution_in_loop (chrec0, loop_nb);
+ 	  other_evs = chrec_fold_minus (chrec_type (other_evs), 
+ 					other_evs, chrec1);
  	  other_evs = chrec_replace_initial_condition 
  	    (other_evs, convert (chrec_type (other_evs), integer_zero_node));
  	}
*************** number_of_iterations_in_loop (struct loo
*** 2664,2673 ****
        opnd1 = TREE_OPERAND (test, 1);
        chrec0 = analyze_scalar_evolution (loop, opnd0);
        chrec1 = analyze_scalar_evolution (loop, opnd1);
!       
!       chrec0 = instantiate_parameters (loop, chrec0);
!       chrec1 = instantiate_parameters (loop, chrec1);
!       
        if (chrec0 == chrec_top)
  	/* KEEP_IT_SYMBOLIC.  */
  	chrec0 = opnd0;
--- 2668,2674 ----
        opnd1 = TREE_OPERAND (test, 1);
        chrec0 = analyze_scalar_evolution (loop, opnd0);
        chrec1 = analyze_scalar_evolution (loop, opnd1);
! 
        if (chrec0 == chrec_top)
  	/* KEEP_IT_SYMBOLIC.  */
  	chrec0 = opnd0;


The second part is needed for dealing with more symbolic loop counts.

  niter_desc.niter = NULL_TREE;
  number_of_iterations_cond (type0, init0, step0, code, init1, step1, 
			     &niter_desc);
  if (niter_desc.niter != NULL_TREE
      && integer_onep (niter_desc.assumptions)
      && integer_zerop (niter_desc.may_be_zero))
    return niter_desc.niter;
  return chrec_top;

When one of the evolutions has a symbolic part, assumptions is one,
and the result is chrec_top.  The result is correct but maybe we would
like something more precise.  The following examples are from
ssa-chrec-06.c and ssa-chrec-27.c

(number_of_iterations_in_loop 
  [...]
  (loop_nb = 1)
  (loop_while_expr_is_true: a_21 <= 82)
  (chrec0 = {82, +, b_33 + 7}_1)
  (chrec1 = 82)
  (set_nb_iterations_in_loop = [-oo, +oo]))

(number_of_iterations_in_loop 
  [...]
  (loop_nb = 2)
  (loop_while_expr_is_true: a_15 < 0)
  (chrec0 = {a_14 + 3, +, 3}_2)
  (chrec1 = 0)
  (set_nb_iterations_in_loop = [-oo, +oo]))


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]