[autovect] Why all these redundant computations?

[autovect] Why all these redundant computations?

[Sebastian Pop]

Hello,

I was just looking at the output of the data dep analyzer for
ltrans-1.c and I was quite surprised to see that array indexes are
analyzed twice, as in the following output:

(analyze_array 
  (ref = u[D.1485_16];
)
(analyze_scalar_evolution 
  (loop_nb = 1)
  (scalar = D.1485_16)
(get_scalar_evolution 
  (scalar = D.1485_16)
  (scalar_evolution = {0, +, 1336}_1))
(set_scalar_evolution 
  (scalar = D.1485_16)
  (scalar_evolution = {0, +, 1336}_1))
)
(instantiate_parameters 
  (loop_nb = 1)
  (chrec = {0, +, 1336}_1)
  (res = {0, +, 1336}_1))
)

Here D.1485_16 has an evolution already stored in the cache.  However,
just below we get a full recomputation of the same D.1485_16:

(analyze_scalar_evolution 
  (loop_nb = 1)
  (scalar = D.1485_16)
(get_scalar_evolution 
  (scalar = D.1485_16)
  (scalar_evolution = {0, +, 1336}_1))
(analyze_scalar_evolution 
  (loop_nb = 1)
  (scalar = i_3)
(get_scalar_evolution 
  (scalar = i_3)
  (scalar_evolution = {0, +, 1}_1))
(analyze_initial_condition 
  (loop_phi_node = 
i_3 = PHI <i_20(8), 0(5)>;)
  (init_cond = 0))
(analyze_evolution_in_loop 
  (loop_phi_node = i_3 = PHI <i_20(8), 0(5)>;)
(add_to_evolution 
  (loop_nb = 1)
  (chrec_before = 0)
  (to_add = 1)
  (res = {0, +, 1}_1))
  (evolution_function = {0, +, 1}_1))
(set_scalar_evolution 
  (scalar = i_3)
  (scalar_evolution = {0, +, 1}_1))
)
(analyze_scalar_evolution 
  (loop_nb = 1)
  (scalar = 1336)
(get_scalar_evolution 
  (scalar = 1336)
  (scalar_evolution = 1336))
)
(set_scalar_evolution 
  (scalar = D.1485_16)
  (scalar_evolution = {0, +, 1336}_1))
)

The problem seems to be that analyze_offset_expr calls the scev
analyzer explicitely asking for recomputation (third parameter is
true):

  /* 2. Variable. Try to substitute with initial_condition of the corresponding
     access_fn in the current loop.  */
  if (SSA_VAR_P (expr))
    {
      tree access_fn = analyze_scalar_evolution (loop, expr, true, 
						 &unknown_evolution);

Why should we start the analysis from scratch in this case?  The same
question could be asked for all the uses of analyze_scalar_evolution
in the vectorizer...  Grepping for analyze_scalar_evolution, you get
the following places (in autovect branch) that explicitely ask for
scev recomputation:

tree-vect-analyze.c:551:      access_fn = analyze_scalar_evolution (loop, def, true, &unknown_evolution);
tree-vect-analyze.c:2226:	(loop, analyze_scalar_evolution (loop, PHI_RESULT (phi), true, 
tree-vect-transform.c:605:        access_fn = analyze_scalar_evolution (loop, def, true,
tree-vect-transform.c:2548:      access_fn = analyze_scalar_evolution (loop, PHI_RESULT (phi), true,
tree-data-ref.c:940:  tree access_fn = analyze_scalar_evolution (loop, ptr_ref, true, 
tree-data-ref.c:1151:      tree access_fn = analyze_scalar_evolution (loop, expr, true, 

Re: [autovect] Why all these redundant computations?

[Dorit Naishlos]

> ...
>
> The problem seems to be that analyze_offset_expr calls the scev
> analyzer explicitely asking for recomputation (third parameter is
> true):
>
> ...
>
> Why should we start the analysis from scratch in this case?  The same
> question could be asked for all the uses of analyze_scalar_evolution
> in the vectorizer...  Grepping for analyze_scalar_evolution, you get
> the following places (in autovect branch) that explicitely ask for
> scev recomputation:
>

I don't think there was an intention to force recomputation - probably just
overlooked what the third argument actually stands for. These occurrences
could probably be changed to false.

dorit

Re: [autovect] Why all these redundant computations?

[Daniel Berlin]

On Mon, 2005-08-01 at 17:27 +0300, Dorit Naishlos wrote:
> 
> 
> 
> > ...
> >
> > The problem seems to be that analyze_offset_expr calls the scev
> > analyzer explicitely asking for recomputation (third parameter is
> > true):
> >
> > ...
> >
> > Why should we start the analysis from scratch in this case?  The same
> > question could be asked for all the uses of analyze_scalar_evolution
> > in the vectorizer...  Grepping for analyze_scalar_evolution, you get
> > the following places (in autovect branch) that explicitely ask for
> > scev recomputation:
> >
> 
> I don't think there was an intention to force recomputation - probably just
> overlooked what the third argument actually stands for. These occurrences
> could probably be changed to false.
> 

Yeah, i agree with dorit.
The only other possible reason i can think of is that it fixed a bug
somewhere due to not properly invalidating the cache, and that fix was
just copied around.

> dorit
> 

Re: [autovect] Why all these redundant computations?

[Sebastian Pop]

Daniel Berlin wrote:
> On Mon, 2005-08-01 at 17:27 +0300, Dorit Naishlos wrote:
> > 
> > I don't think there was an intention to force recomputation - probably just
> > overlooked what the third argument actually stands for. These occurrences
> > could probably be changed to false.
> > 
> 
> Yeah, i agree with dorit.
> The only other possible reason i can think of is that it fixed a bug
> somewhere due to not properly invalidating the cache, and that fix was
> just copied around.
> 

Okay, then I'll try to bootstrap and test with these flags passed to
false.

Thanks.