[autovect] Why all these redundant computations?

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

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,