Support for aliasing with variable strides

[James Greenhalgh]

On Thu, Dec 14, 2017 at 11:00:36AM +0000, Richard Biener wrote:
> On Fri, Nov 17, 2017 at 11:17 PM, Richard Sandiford
> <richard.sandiford@linaro.org> wrote:
> > This patch adds runtime alias checks for loops with variable strides,
> > so that we can vectorise them even without a restrict qualifier.
> > There are several parts to doing this:
> >
> > 1) For accesses like:
> >
> >      x[i * n] += 1;
> >
> >    we need to check whether n (and thus the DR_STEP) is nonzero.
> >    vect_analyze_data_ref_dependence records values that need to be
> >    checked in this way, then prune_runtime_alias_test_list records a
> >    bounds check on DR_STEP being outside the range [0, 0].
> >
> > 2) For accesses like:
> >
> >      x[i * n] = x[i * n + 1] + 1;
> >
> >    we simply need to test whether abs (n) >= 2.
> >    prune_runtime_alias_test_list looks for cases like this and tries
> >    to guess whether it is better to use this kind of check or a check
> >    for non-overlapping ranges.  (We could do an OR of the two conditions
> >    at runtime, but that isn't implemented yet.)
> >
> > 3) Checks for overlapping ranges need to cope with variable strides.
> >    At present the "length" of each segment in a range check is
> >    represented as an offset from the base that lies outside the
> >    touched range, in the same direction as DR_STEP.  The length
> >    can therefore be negative and is sometimes conservative.
> >
> >    With variable steps it's easier to reaon about if we split
> >    this into two:
> >
> >      seg_len:
> >        distance travelled from the first iteration of interest
> >        to the last, e.g. DR_STEP * (VF - 1)
> >
> >      access_size:
> >        the number of bytes accessed in each iteration
> >
> >    with access_size always being a positive constant and seg_len
> >    possibly being variable.  We can then combine alias checks
> >    for two accesses that are a constant number of bytes apart by
> >    adjusting the access size to account for the gap.  This leaves
> >    the segment length unchanged, which allows the check to be combined
> >    with further accesses.
> >
> >    When seg_len is positive, the runtime alias check has the form:
> >
> >         base_a >= base_b + seg_len_b + access_size_b
> >      || base_b >= base_a + seg_len_a + access_size_a
> >
> >    In many accesses the base will be aligned to the access size, which
> >    allows us to skip the addition:
> >
> >         base_a > base_b + seg_len_b
> >      || base_b > base_a + seg_len_a
> >
> >    A similar saving is possible with "negative" lengths.
> >
> >    The patch therefore tracks the alignment in addition to seg_len
> >    and access_size.
> >
> > Tested on aarch64-linux-gnu (with and without SVE), x86_64-linux-gnu
> > and powerpc64le-linux-gnu.  OK to install?
> 
> Ok.

The AArch64 tests are OK.

Thanks,
James

> > PS. This is the last SVE patch for GCC 8!

Congratulations! These patches have seen some outstanding work; both on your
part and equally on the part of all the reviewers!