r263226 - in /trunk/gcc: ChangeLog match.pd tes...

[rsandifo@gcc.gnu.org]

Author: rsandifo
Date: Wed Aug  1 15:46:12 2018
New Revision: 263226

URL: https://gcc.gnu.org/viewcvs?rev=263226&root=gcc&view=rev
Log:
Fold pointer range checks with equal spans

When checking whether vectorised accesses at A and B are independent,
the vectoriser falls back to tests of the form:

    A + size <= B || B + size <= A

But in the common case that "size" is just the constant size of a vector
(or a small multiple), it would be more efficient to do:

   (size_t) (A + (size - 1) - B) > (size - 1) * 2

This patch adds folds to do that.  E.g. before the patch, the alias
checks for:

  for (int j = 0; j < n; ++j)
    {
      for (int i = 0; i < 16; ++i)
	a[i] = (b[i] + c[i]) >> 1;
      a += step;
      b += step;
      c += step;
    }

were:

	add     x7, x1, 15
	add     x5, x0, 15
	cmp     x0, x7
	add     x7, x2, 15
	ccmp    x1, x5, 2, ls
	cset    w8, hi
	cmp     x0, x7
	ccmp    x2, x5, 2, ls
	cset    w4, hi
	tst     w8, w4

while after the patch they're:

	add     x0, x0, 15
	sub     x6, x0, x1
	sub     x5, x0, x2
	cmp     x6, 30
	ccmp    x5, 30, 0, hi

The old scheme needs:

[A] one addition per vector pointer
[B] two comparisons and one IOR per range check

The new one needs:

[C] less than one addition per vector pointer
[C] one subtraction and one comparison per range check

The range checks are then ANDed together, with the same number of
ANDs either way.

With conditional comparisons (such as on AArch64), we're able to remove
the IOR between comparisons in the old scheme, but then need an explicit
AND or branch when combining the range checks, as the example above shows.
With the new scheme we can instead use conditional comparisons for
the AND chain.

So even with conditional comparisons, the new scheme should in practice
be a win in almost all cases.  Without conditional comparisons, the new
scheme removes at least one operation from [A] and one operation per
range check from [B], so should always give fewer operations overall.

2018-07-20  Richard Sandiford  <richard.sandiford@arm.com>

gcc/
	* match.pd: Optimise pointer range checks.

gcc/testsuite/
	* gcc.dg/pointer-range-check-1.c: New test.
	* gcc.dg/pointer-range-check-2.c: Likewise.

Added:
    trunk/gcc/testsuite/gcc.dg/pointer-range-check-1.c
    trunk/gcc/testsuite/gcc.dg/pointer-range-check-2.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/match.pd
    trunk/gcc/testsuite/ChangeLog