Re: [PATCH 3/4] Do not check whether memory references accessed in every iteration trap.

[Sebastian Pop <sebpop at gmail dot com>]

On Fri, Aug 13, 2010 at 04:24, Richard Guenther <rguenther@suse.de> wrote:
>> -/* { dg-final { scan-tree-dump-times "OUTER LOOP VECTORIZED" 1 "vect" { xfail vect_no_align } } } */
>> +/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 2 "vect" } } */
>> ?/* { dg-final { cleanup-tree-dump "vect" } } */
>>
>
> As this was testing for outer loop vectorization please duplicate the
> test and disable if-conversion in one variant.

I removed these changes as they are not needed anymore: the
if-conversion with memory accesses is not enabled in -O3.

>> +
>> +/* Return true when the base objects of data references A and B are
>> + ? the same memory object. ?*/
>> +
>> +static inline bool
>> +same_data_refs_base_objects (data_reference_p a, data_reference_p b)
>> +{
>> + ?return DR_NUM_DIMENSIONS (a) == DR_NUM_DIMENSIONS (b)
>> + ? ?&& dr_may_alias_p (a, b)
>> + ? ?&& operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), 0);
>
> I don't see why the dr_may_alias_p check is necessary here. ?In fact
> it might even pessimize what you want to check.

I agree, there is no reason to have the call to dr_may_alias_p: I
removed it.

>
>> +}
>> +
>> +/* Return true when the data references A and B are accessing the same
>> + ? memory object with the same access functions. ?*/
>
> Isn't this too special again?
>
>> +static inline bool
>> +same_data_refs (data_reference_p a, data_reference_p b)

I do not understand what you are suggesting here.
Should I make the two functions same_data_refs and
same_data_refs_base_objects static and put them in tree-if-conv.c?

>> diff --git a/gcc/tree-if-conv.c b/gcc/tree-if-conv.c
>> index cac5a3b..f0bc026 100644
>> --- a/gcc/tree-if-conv.c
>> +++ b/gcc/tree-if-conv.c
>> @@ -441,6 +441,166 @@ if_convertible_phi_p (struct loop *loop, basic_block bb, gimple phi)
>> ? ?return true;
>> ?}
>>
>> +/* Returns true when the memory reference A at position P in the data
>> + ? references vector DRS and executed under the condition CA, is read
>
> "and" executed? ?Is A executed under condition CA or is the whole
> vector DRS? ?Please clarify the comment...
>

I added one more sentence to clarify the comment:

/* Returns true when the memory reference A at position POS in the
   data references vector DRS and executed under the condition CA, is
   read or written unconditionally.  In other words, this function
   returns true when there exist other accesses to the same data
   reference with predicates that add up (OR-up) to the true
   predicate: this ensures that the data reference A is touched (read
   or written) on every iteration of the if-converted loop.  */

>> + ? or written unconditionally. ?*/
>> +
>> +static bool
>> +memref_read_or_written_unconditionally (int pos, data_reference_p a,
>> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? VEC (data_reference_p, heap) *drs,
>> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? tree ca)
>> +{
>> + ?int i;
>> + ?data_reference_p b;
>> +
>> + ?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)
>> + ? ? ? ? || is_true_predicate (ca = fold_or_predicates (ca, cb)))
>> + ? ? ? return true;
>
> ... else this doesn't make sense? ?B is either executed unconditionally
> (is_true_predicate (cb)) or at least A or B is executed
> uncontionally. ?Why is the latter case worth specializing? ?In fact
> you are probably doing redundant work in fold_or_predicates all the
> time in practice (cb will be the same most of the time).
>

This condition stands for:

>> + ? ? if (is_true_predicate (cb)

1. A is touched at every iteration when there exist a data ref B with
the same base as A and that is executed unconditionally.

>> + ? ? ? ? || is_true_predicate (ca = fold_or_predicates (ca, cb)))

2. A is also touched at every iteration when B is predicated by a
condition that is a complement of CA.  CA is first initialized to the
predicate of A, and then CA is OR-ed to all the predicates under which
the same data reference is touched.  If eventually CA becomes the true
predicate, then each iteration of the loop contains a path touching
the data reference A.

>> + ? ? ?}
>> +
>> + ?return false;
>> +}
>> +
>> +/* Returns true when the memory references of STMT are read or written
>> + ? unconditionally. ?*/
>> +
>> +static bool
>> +memrefs_read_or_written_unconditionally (gimple stmt,
>> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?VEC (data_reference_p, heap) *drs)
>> +{
>> + ?int i;
>> + ?data_reference_p a;
>> + ?tree ca = bb_predicate (gimple_bb (stmt));
>> +
>> + ?for (i = 0; VEC_iterate (data_reference_p, drs, i, a); i++)
>> + ? ?if (DR_STMT (a) == stmt
>
> Ick. ?Why not check DR_STMT (b) != stmt in
> memref_read_or_written_unconditionally and avoid all this linear
> searching mess?
>

Could you please be more specific: I do not understand what you
are asking here.

The algorithm is O (n^2) with n the number of data references in the
innermost loops.  This is because for each data reference we try to
prove that it is executed unconditionally, i.e., that there exist
other data references with the same base that are accessed on
different paths at every iteration.

>
> Please rework the patch according to the requested changes.
>

I sent the combined patch separately.

Sebastian