[4/4] Speed-up ifcvt_memrefs_wont_trap caching previous results.

This patch speeds up the ifcvt_memrefs_wont_trap computation by
caching the results of the computations in the data references ->aux
fields.

	* tree-if-conv.c (struct ifc_dr): New.
	(memref_read_or_written_unconditionally): Use the cached values
	when possible.
	(write_memref_written_at_least_once): Same.
	(if_convertible_loop_p): Initialize and free DR->aux fields.
---
 gcc/tree-if-conv.c |   53 ++++++++++++++++++++++++++++++++++++++++++++++++---
 1 files changed, 49 insertions(+), 4 deletions(-)

On Thu, 8 Jul 2010, Sebastian Pop wrote:

> This patch speeds up the ifcvt_memrefs_wont_trap computation by
> caching the results of the computations in the data references ->aux
> fields.
> 
> 	* tree-if-conv.c (struct ifc_dr): New.
> 	(memref_read_or_written_unconditionally): Use the cached values
> 	when possible.
> 	(write_memref_written_at_least_once): Same.
> 	(if_convertible_loop_p): Initialize and free DR->aux fields.
> ---
>  gcc/tree-if-conv.c |   53 ++++++++++++++++++++++++++++++++++++++++++++++++---
>  1 files changed, 49 insertions(+), 4 deletions(-)
> 
> diff --git a/gcc/tree-if-conv.c b/gcc/tree-if-conv.c
> index f0bc026..655c168 100644
> --- a/gcc/tree-if-conv.c
> +++ b/gcc/tree-if-conv.c
> @@ -441,6 +441,17 @@ if_convertible_phi_p (struct loop *loop, basic_block bb, gimple phi)
>    return true;
>  }
>  
> +/* Records the status of a data reference.  This struct is attached to
> +   each DR->aux field.  */
> +
> +struct ifc_dr {
> +  /* -1 when not initialized, 0 when false, 1 when true.  */
> +  int dr_is_written_at_least_once;
> +
> +  /* -1 when not initialized, 0 when false, 1 when true.  */
> +  int dr_is_rw_unconditionally;
> +};
> +
>  /* Returns true when the memory reference A at position P in the data
>     references vector DRS and executed under the condition CA, is read
>     or written unconditionally.  */
> @@ -452,17 +463,27 @@ memref_read_or_written_unconditionally (int pos, data_reference_p a,
>  {
>    int i;
>    data_reference_p b;
> +  int x = ((struct ifc_dr *) a->aux)->dr_is_rw_unconditionally;

These casts are ugly.  Please add a #define like

#define DR_IFCVT(dr) ((struct ifc_dr *) a->aux)

and use that.

Ok with that change.

Richard.

> +
> +  if (x != -1)
> +    return x;
>  
>    for (i = 0; VEC_iterate (data_reference_p, drs, i, b); i++)
>      if (i != pos && same_data_refs (a, b))
>        {
>  	tree cb = bb_predicate (gimple_bb (DR_STMT (b)));
>  
> -	if (is_true_predicate (cb)
> +	if (((struct ifc_dr *) b->aux)->dr_is_rw_unconditionally == 1
> +	    || is_true_predicate (cb)
>  	    || is_true_predicate (ca = fold_or_predicates (ca, cb)))
> -	  return true;
> +	  {
> +	    ((struct ifc_dr *) a->aux)->dr_is_rw_unconditionally = 1;
> +	    ((struct ifc_dr *) b->aux)->dr_is_rw_unconditionally = 1;
> +	    return true;
> +	  }
>        }
>  
> +  ((struct ifc_dr *) a->aux)->dr_is_rw_unconditionally = 0;
>    return false;
>  }
>  
> @@ -497,6 +518,10 @@ write_memref_written_at_least_once (int pos, data_reference_p a,
>  {
>    int i;
>    data_reference_p b;
> +  int x = ((struct ifc_dr *) a->aux)->dr_is_written_at_least_once;
> +
> +  if (x != -1)
> +    return x;
>  
>    for (i = 0; VEC_iterate (data_reference_p, drs, i, b); i++)
>      if (i != pos
> @@ -505,11 +530,17 @@ write_memref_written_at_least_once (int pos, data_reference_p a,
>        {
>  	tree cb = bb_predicate (gimple_bb (DR_STMT (b)));
>  
> -	if (is_true_predicate (cb)
> +	if (((struct ifc_dr *) b->aux)->dr_is_written_at_least_once == 1
> +	    || is_true_predicate (cb)
>  	    || is_true_predicate (ca = fold_or_predicates (ca, cb)))
> -	  return true;
> +	  {
> +	    ((struct ifc_dr *) a->aux)->dr_is_written_at_least_once = 1;
> +	    ((struct ifc_dr *) b->aux)->dr_is_written_at_least_once = 1;
> +	    return true;
> +	  }
>        }
>  
> +  ((struct ifc_dr *) a->aux)->dr_is_written_at_least_once = 0;
>    return false;
>  }
>  
> @@ -972,6 +1003,7 @@ if_convertible_loop_p (struct loop *loop)
>    edge_iterator ei;
>    basic_block exit_bb = NULL;
>    bool res = false;
> +  data_reference_p dr;
>    VEC (data_reference_p, heap) *refs;
>    VEC (ddr_p, heap) *ddrs;
>  
> @@ -1048,6 +1080,14 @@ if_convertible_loop_p (struct loop *loop)
>  
>    res = false;
>  
> +  if (flag_tree_loop_if_convert_memory_writes)
> +    for (i = 0; VEC_iterate (data_reference_p, refs, i, dr); i++)
> +      {
> +	dr->aux = XNEW (struct ifc_dr);
> +	((struct ifc_dr *) dr->aux)->dr_is_written_at_least_once = -1;
> +	((struct ifc_dr *) dr->aux)->dr_is_rw_unconditionally = -1;
> +      }
> +
>    for (i = 0; i < loop->num_nodes; i++)
>      {
>        basic_block bb = ifc_bbs[i];
> @@ -1069,6 +1109,11 @@ if_convertible_loop_p (struct loop *loop)
>      fprintf (dump_file, "Applying if-conversion\n");
>  
>   cleanup:
> +
> +  if (flag_tree_loop_if_convert_memory_writes)
> +    for (i = 0; VEC_iterate (data_reference_p, refs, i, dr); i++)
> +      free (dr->aux);
> +
>    free_data_refs (refs);
>    free_dependence_relations (ddrs);
>    return res;
>