ivopts improvement

On 03/04/2011 11:37 PM, Zdenek Dvorak wrote:
> Hi,
> 
>>    /* Whether the loop body includes any function calls.  */
>>    bool body_includes_call;
>> +
>> +  /* Whether the loop body includes any function calls that possibly have side
>> +     effects.  */
>> +  bool body_includes_side_effect_call;
>>  };
>>  
>>  /* An assignment of iv candidates to uses.  */
>> @@ -456,6 +460,20 @@
>>    return exit;
>>  }
>>  
>> +/* Returns true if single_exit (DATA->current_loop) is the only possible exit.
>> +   Uses the same logic as loop_only_exit_p.  */
> 
> why are you duplicating the functionality, instead of simply caching the result
> of loop_only_exit_p?
> 

I was trying to avoid iterating over the loop body twice, once for
body_includes_call and once for body_includes_side_effect_call (or
loop_only_exit_p). But indeed, duplicating functionality is not ideal
either. I additionally tried a version which both does not duplicate
functionality, and is runtime efficient, but the implementation became
very convoluted, so I settled for your suggestion of caching the result
of loop_only_exit_p.

>> +/* Tries to detect
>> +     NIT == (use_iv_max < USE->iv->base)
>> +            ? 0
>> +            : (use_iv_max - USE->iv->base)
>> +   where
>> +     use_iv_real_base == (USE->iv->base - USE->iv->step)
>> +     && CAND->iv->base == base_ptr + use_iv_real_base
>> +   and returns the exclusive upper bound for CAND->var_after:
>> +     base_ptr + use_iv_max.  */
>> +
>> +static tree
>> +get_lt_bound (struct iv_use *use, struct iv_cand *cand, tree nit)
>> +{
> ...
>> +  /* use_iv_real_base == use->iv->base - use->iv->step.  */
>> +  use_iv_real_base = fold_build_plus (MINUS_EXPR, use->iv->base, use->iv->step);
>> +
>> +  /* cand_iv_base.  */
>> +
>> +  /* cand->iv->base == base_ptr + use_iv_real_base.  */
> ...
>> +  /* 0.  */
> ...
> 
> This function seriously needs better comments.  All that are currently present just
> give relations between variables that can be as easily seen from the code (but
> do not at all explain what the variables are supposed to mean), 

I see.

> or make no sense
> (what does the 0. comment mean?)

I was trying to repeat parts of the function header comment bit by bit,
but got too terse in the process.

> Otherwise the patch looks ok (but I would still like to see get_lt_bound with proper
> comments, currently I don't really understand what happens there),

changes compared to last submission:
iterator.6.3-ml.patch:
- split up fold_build_plus into fold_build_plus and robust_plus, in
  order to reuse robust_plus in fold_plus in iterator.6.6-ml.patch.
iterator.6.4-ml.patch:
- just cache result of loop_only_exit_p.
- make loop_only_exit_p robust against exit == NULL.
iterator.6.5-ml.patch:
- new patch. keep ssa_name field valid.
iterator.6.6-ml.patch:
- improved comments.
- factored out folding functionality into fold_plus and
  fold_walk_def_plus.
- detect use loop bound based on use->stmt rather than on the nit
  COND_EXPR.
- improved code to handle 'int' iterator.
- improved code to handle '<=' case.
- improved code to handle negative step.
- improved code to handle iv increments after loop exit.
iterator.6.6-ml.test.patch:
- duplicated test for int iterator.

reg-tested on x86_64.

I hope the comments are better now.

Thanks,
- Tom

Hi,

> diff -u gcc/tree-ssa-loop-ivopts.c gcc/tree-ssa-loop-ivopts.c
> --- gcc/tree-ssa-loop-ivopts.c	(working copy)
> +++ gcc/tree-ssa-loop-ivopts.c	(working copy)
> @@ -1194,6 +1300,7 @@ record_use (struct ivopts_data *data, tr
>  	    gimple stmt, enum use_type use_type)
>  {
>    struct iv_use *use = XCNEW (struct iv_use);
> +  tree tmp;
>  
>    use->id = n_iv_uses (data);
>    use->type = use_type;
> @@ -1204,11 +1311,14 @@ record_use (struct ivopts_data *data, tr
>  
>    /* To avoid showing ssa name in the dumps, if it was not reset by the
>       caller.  */
> +  tmp = iv->ssa_name;
>    iv->ssa_name = NULL_TREE;
>  
>    if (dump_file && (dump_flags & TDF_DETAILS))
>      dump_use (dump_file, use);
>  
> +  iv->ssa_name = tmp;
> +
>    VEC_safe_push (iv_use_p, heap, data->iv_uses, use);
>  
>    return use;

this is not ok.  You can get the ssa name from extract_cond_operands.

> +  /* Determine if the exit test is formulated in terms of the phi or the
> +     increment of the use iv.  */
> +  use_uses_inced_iv
> +    = gimple_code (SSA_NAME_DEF_STMT (use->iv->ssa_name)) != GIMPLE_PHI;
> +
> +  /* Determine if the exit test is before or after the increment of the
> +     cand.  */
> +  use_after_cand_inc
> +    = stmt_after_increment (data->current_loop, cand, use->stmt);
> +
> +  /* For now, we only handle these cases.  */
> +  if (use_after_cand_inc != use_uses_inced_iv)
> +    return false;

what is this trying to achieve?  USE_USES_INCED_IV is pretty much meaningless --
the value of USE does not depend in any way on whether it comes directly from
a PHI node or from some other calculation.

> +  /* Calculate bound.  */
> +  bound = fold_build_plus (PLUS_EXPR, base_ptr,
> +			   fold_convert (sizetype, use_lt_bound));
> +  if (bound == NULL_TREE)
> +    return false;

How could the result be NULL_TREE?

Zdenek