[SCEV] Add [zs]ext{C,+,x} -> (D + [zs]ext{C-D,+,x})<nuw><nsw> transform

as well as sext(C + x + ...) -> (D + sext(C-D + x + ...))<nuw><nsw>

similar to the equivalent transformation for zext's

if the top level addition in (D + (C-D + x * n)) could be proven to

not wrap, where the choice of D also maximizes the number of trailing

zeroes of (C-D + x * n), ensuring homogeneous behaviour of the

transformation and better canonicalization of such AddRec's

(indeed, there are 2^(2w) different expressions in `B1 + ext(B2 + Y)` form for

the same Y, but only 2^(2w - k) different expressions in the resulting `B3 +

ext((B4 * 2^k) + Y)` form, where w is the bit width of the integral type)

This patch generalizes sext(C1 + C2*X) --> sext(C1) + sext(C2*X) and

sext{C1,+,C2} --> sext(C1) + sext{0,+,C2} transformations added in

r209568 relaxing the requirements the following way:

- C2 doesn't have to be a power of 2, it's enough if it's divisible by 2 a sufficient number of times;
- C1 doesn't have to be less than C2, instead of extracting the entire C1 we can split it into 2 terms: (00...0XXX + YY...Y000), keep the second one that may cause wrapping within the extension operator, and move the first one that doesn't affect wrapping out of the extension operator, enabling further simplifications;
- C1 and C2 don't have to be positive, splitting C1 like shown above produces a sum that is guaranteed to not wrap, signed or unsigned;
- in AddExpr case there could be more than 2 terms, and in case of AddExpr the 2nd and following terms and in case of AddRecExpr the Step component don't have to be in the C2*X form or constant (respectively), they just need to have enough trailing zeros, which in turn could be guaranteed by means other than arithmetics, e.g. by a pointer alignment;
- the extension operator doesn't have to be a sext, the same transformation works and profitable for zext's as well.

Apparently, optimizations like SLPVectorizer currently fail to

vectorize even rather trivial cases like the following:

double bar(double *a, unsigned n) {

double x = 0.0; double y = 0.0; for (unsigned i = 0; i < n; i += 2) { x += a[i]; y += a[i + 1]; } return x * y;

}

If compiled with `clang -std=c11 -Wpedantic -Wall -O3 main.c -S -o - -emit-llvm`

(!{!"clang version 7.0.0 (trunk 337339) (llvm/trunk 337344)"})

it produces scalar code with the loop not unrolled with the unsigned `n` and

`i` (like shown above), but vectorized and unrolled loop with signed `n` and

`i`. With the changes made in this commit the unsigned version will be

vectorized (though not unrolled for unclear reasons).

How it all works:

Let say we have an AddExpr that looks like (C + x + y + ...), where C

is a constant and x, y, ... are arbitrary SCEVs. Let's compute the

minimum number of trailing zeroes guaranteed of that sum w/o the

constant term: (x + y + ...). If, for example, those terms look like

follows:

i

XXXX...X000

YYYY...YY00

...

ZZZZ...0000

then the rightmost non-guaranteed-zero bit (a potential one at i-th

position above) can change the bits of the sum to the left (and at

i-th position itself), but it can not possibly change the bits to the

right. So we can compute the number of trailing zeroes by taking a

minimum between the numbers of trailing zeroes of the terms.

Now let's say that our original sum with the constant is effectively

just C + X, where X = x + y + .... Let's also say that we've got 2

guaranteed trailing zeros for X:

j

CCCC...CCCC

XXXX...XX00 // this is X = (x + y + ...)

Any bit of C to the left of j may in the end cause the C + X sum to

wrap, but the rightmost 2 bits of C (at positions j and j - 1) do not

affect wrapping in any way. If the upper bits cause a wrap, it will be

a wrap regardless of the values of the 2 least significant bits of C.

If the upper bits do not cause a wrap, it won't be a wrap regardless

of the values of the 2 bits on the right (again).

So let's split C to 2 constants like follows:

0000...00CC = D

CCCC...CC00 = (C - D)

and represent the whole sum as D + (C - D + X). The second term of

this new sum looks like this:

CCCC...CC00

XXXX...XX00

- // let's add them up

YYYY...YY00

The sum above (let's call it Y)) may or may not wrap, we don't know,

so we need to keep it under a sext/zext. Adding D to that sum though

will never wrap, signed or unsigned, if performed on the original bit

width or the extended one, because all that that final add does is

setting the 2 least significant bits of Y to the bits of D:

YYYY...YY00 = Y

0000...00CC = D

- <nuw><nsw>

YYYY...YYCC

Which means we can safely move that D out of the sext or zext and

claim that the top-level sum neither sign wraps nor unsigned wraps.

Let's run an example, let's say we're working in i8's and the original

expression (zext's or sext's operand) is 21 + 12x + 8y. So it goes

like this:

0001 0101 * 21
XXXX XX00 * 12x

YYYY Y000 // 8y

0001 0101 * 21
ZZZZ ZZ00 * 12x + 8y

0000 0001 * D
0001 0100 * 21 - D = 20

ZZZZ ZZ00 // 12x + 8y

0000 0001 * D
WWWW WW00 * 21 - D + 12x + 8y = 20 + 12x + 8y

therefore zext(21 + 12x + 8y) = (1 + zext(20 + 12x + 8y))<nuw><nsw>

This approach could be improved if we move away from using trailing

zeroes and use KnownBits instead. For instance, with KnownBits we could

have the following picture:

i

10 1110...0011 * this is C
XX X1XX...XX00 * this is X = (x + y + ...)

Notice that some of the bits of X are known ones, also notice that

known bits of X are interspersed with unknown bits and not grouped on

the rigth or left.

We can see at the position i that C(i) and X(i) are both known ones,

therefore the (i + 1)th carry bit is guaranteed to be 1 regardless of

the bits of C to the right of i. For instance, the C(i - 1) bit only

affects the bits of the sum at positions i - 1 and i, and does not

influence if the sum is going to wrap or not. Therefore we could split

the constant C the following way:

i

00 0010...0011 = D

10 1100...0000 = (C - D)

Let's compute the KnownBits of (C - D) + X:

XX1 1 = carry bit, blanks stand for known zeroes

10 1100...0000 = (C - D)

XX X1XX...XX00 = X

XX X0XX...XX00

Will this add wrap or not essentially depends on bits of X. Adding D

to this sum, however, is guaranteed to not to wrap:

0 X

00 0010...0011 = D

sX X0XX...XX00 = (C - D) + X

sX XXXX XX11

As could be seen above, adding D preserves the sign bit of (C - D) +

X, if any, and has a guaranteed 0 carry out, as expected.

The more bits of (C - D) we constrain, the better the transformations

introduced here canonicalize expressions as it leaves less freedom to

what values the constant part of ((C - D) + x + y + ...) can take.

Reviewed By: mzolotukhin, efriedma

Differential Revision: https://reviews.llvm.org/D48853