This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
List of simplifications we should perform
- To: <gcc at gcc dot gnu dot org>
- Subject: List of simplifications we should perform
- From: Daniel Berlin <dan at www dot cgsoftware dot com>
- Date: Fri, 11 May 2001 02:16:33 -0400 (EDT)
This is a list of simplifications, gleaned from the comments of SGI's
pro64 compiler (It's GPLv2, so don't worry),
which has 150k worth of generic simplification code (They use it on more
than one representation type, so they just require that certain
operations be defined to tell you things about whatever types you are
trying to simplify).
It would be a nice beginner project, or even something for someone to do
when bored, to keep this list somewhere, and check off what simplify-rtx
does right now, and implement the rest in some random order.
It is, after all, just math.
Unless of course, we already do all of these, in which case, good.
However, if we don't, it would be good to know exactly which ones we
*don't do*, because adding simplifications to simplify_rtx is a good way
to start to ease into dealing with RTL. It gives you a chance to
manipulate RTL, and see direct results in your code, and it's not very
difficult.
For those wondering (fair use, whatever), this list is approximately
1/15.8 of the entire file by size, which is a paltry 6%, unless it's too
late for me to be up.
It contains nothing you can't find in a math book, anyway.
Higher the level, the less accuracy we require.
R:* = Roundoff level, also controls what gets done in a lot of cases.
R:1 = Allows constant folding of intrinsics
R:2 = Allow arbitrary reassociation
R:3 = Do any mathematically valid rearrangement
I:* = IEEE754 level, also controls things like division splitting, and reciprocal square root.
Simplifications for ABS:
ABS(ABS(x)) ABS(X)
ABS(-x) ABS(x)
ABS(CVT) CVT(ABS)
Simplifications for ~ and !:
! ! j j
~ ~ j j
! <comp> inverse comp, IEEE_comparisons false for floating point
~(a | b) a nor b
~(a nor b) a or b
Simplifications for unary - :
-(-x) x
-(x-y) y-x
-(x*c1) x*-c
-(x/c1) x/-c
-(c1/x) -c/x
Simplifications for sqrt, recip and rsqrt:
SQRT(RECIP(x)) RSQRT(x)
RECIP(SQRT(x)) RSQRT(x)
RECIP(RECIP(x)) x Roundoff:ROUNDOFF_SIMPLE needed
RECIP(RSQRT(x)) SQRT(x)
RSQRT(RECIP(x)) SQRT(x)
All of these require Rsqrt_Allowed to generate RSQRT,
Simplifications for conversions:
REALPART (COMPLEX(a,b)) a
IMAGPART (COMPLEX(a,b)) b
t1CVT(t2CVT(a)) x, if x is of type t1 and t2 is a more precise type than t1.
t1CVT(t2CVT(x)) t1CVT(x) if t2CVT(x) can represent all possible values of x
t1TRUNC(t2CVT(x)) t1TRUNC or t1CVT(x) if t2CVT(x) can represent all possible values of x
t1TAS(a) a if type of A is t1
Simplifications for +, -
x +- 0 x
0 - x -x
-x + y y - x
x - (-y) x + y
x + (-y) x - y
-x - y -(x+y)
x - c x + (-c)
Aggressive:
x - x 0 R:2 for floating point (so that Inf-Inf=0 is acceptable)
The following are done for floating-point only if reassociation is on:
(x+c1) - c2 x + (c1 - c2) R:2 for floating types (comments on the 2?)
(x-c) + y (x+y) +- c R:2 for floating types (comments on the 2?)
(x-c1) +- c2 x + (-c1 +- c2) R:2 for floating types (comments on the 2?)
(c1-x) +- c2 (c1 +- c2) - x R:2 for floating types (comments on the 2?)
(x+-c) - y (x-y) +- c R:2 for floating types (comments on the 2?)
(c-x) + y (y-x) + c R:2 for floating types (comments on the 2?)
(c-x) - y c - (x+y) R:2 for floating types (comments on the 2?)
x + (y - x) y R:2 for floating types (comments on the 2?)
x - (x + y) -y R:2 for floating types (comments on the 2?)
x - (y + x) -y R:2 for floating types (comments on the 2?)
x - (x - y) y R:2 for floating types (comments on the 2?)
also all 4 op cases of the form
(x op y) op (w op z) are check for constant fols and cancellation.
z*x + z*(y - x) y*z R:2 for floating types (comments on the 2?)
z*x - z*(x + y) -y*z R:2 for floating types (comments on the 2?)
z*x - z*(y + x) -y*z R:2 for floating types (comments on the 2?)
z*x - z*(x - y) y*z R:2 for floating types (comments on the 2?)
/* Try to distribute, if possible */
/* z*x op z*y z*(x op y) r:2 for floating types */
Simplifications for *
x * 1 x
x * 0 0 I:1 (because of 0*Infinity)
x * -1 -x
-x * c x * (-c)
-x * -y simplify(x*y)
-x * y -simplify(x*y)
x * -y -simplify(x*y)
(a +- c1)*c2 a*c2 +- c1*c2
(c1 - a)*c2 c1*c2 - c2*a
(c1 - c2*a)*c3 c1*c3 - c2*c3*a
(c2*a +- c1)*c3 c2*c3*a +- c1*c3
Aggressive:
a*rsqrt(a) sqrt(a) Round >= Roundoff_simple
sqrt(a)*recip(a) 1/sqrt(a) "
Simplifications for /
-x/-y x/y
x / 1 x
x / (-1) -x
1.0/a RECIP(a)
-1.0/a -RECIP(a)
j/(2**N) j ASHR N (if J is unsigned)
j/N TRUNC(DBLE(j)*((1.0d0/DBLE(N)*(1+2**-40)))),
if j is 32 bits. (Yes, this really works).
a / c a * 1.0/c, if |c| is 2**k
a / b a * RECIP(b) R:3,I:3 (this is a very bad thing to do)
Aggressive:
a / sqrt(a) sqrt(a) R:2
sqrt(a) / a 1/sqrt(a) r:2 [simplifier will turn this into RSQRT if allowed]
a/a 1
Simplifications for MOD and REM
j mod 1 0
j mod -1 0
0 mod j 0
j rem 1 0
j rem -1 0
0 rem j 0
j mod (2**N) j & (2**N-1)
j mod -(2**N) (j & (2**N-1)) - 2**N If j is signed
j rem (2**N) j & (2**N-1) If j is unsigned
To be done:
j rem (2**N) (j & (2**N-1)) -
((-(j.lt.0) & (2**N))) If j is signed
j rem -(2**N) (j & (2**N-1)) -
((-(j.lt.0) & (2**N))) If j is signed
Simplifications for **
1 ** x 1
-1 ** N 1 - (N&1)<<1
x ** 0 1
x ** 1 x
a ** 0.5 SQRT(a)
a ** -0.5 1.0/SQRT(a) (RSQRT will be generated by simplifier)
a ** -1.0 1.0/a (RECIP will be generated by the simplifier)
Simplifications for MIN and MAX
MAX(x,c) x if c is smallest possible value
MIN(x,c) x if c is largest possible value
MAX(x,c) c if c is largest possible value
MIN(x,c) c if c is smallest possible value
The above are currently only done for integer types
Aggressive:
MAX(x,x), MIN(x,x) x
Simplifications for &
j & 0 0
j & -1 j
(j==0) & (k==0) (j|k)==0
~j & ~k ~(j|k) Generates NOR
<comp> & 1 <comp>
(j | c1) & c2 j & c2 if (c1&c2 == 0)
(j >> shift) & c1 j >> shift if mask has ones in the shift_size - shift lower bits
Aggressive:
~j & j 0
j & j j
(j >> c2) & mask extract (if enabled)
Simplifications for |
j | 0 j
j | -1 -1
(j & c2) | c1 (j | c1) & (c1|c2) might simplify if c1|c2 = -1
~j | ~k ~(j & k)
(j!=0) | (k!=0) (j|k)!=0
<comp> | 1 1
x & mask1 | compose (0,y) (if appropriate)
compose (x,y)
Aggressive:
~j | j -1
j | j j
Simplifications for bitwise Nor
Just create NOT (a|b). The NOT simplifier will create BNOR if necessary
Simplifications for ^
j ^ 0 j
j ^ -1 ~j
<comp> ^ 1 <inverse comp> IEEE_comparisons off for floating
compares
Aggressive:
j ^ j 0
j ^ ~j -1
Simplifications for &&
j && 0 0
j && 1 j
!j && !k !(j || k) Generates NOR
Aggressive:
!j && j 0 A
j && j j A
Simplifications for ||
j || 0 j
j || 1 1
!j || !k !(j && k)
Aggressive:
!j || j 1 A
j || j j A
Simplifications for && (with control flow)
j && 1 j
0 && j 0
1 && j j
Simplifications for <<, >>
j >> c1 j if (c1 & shiftsize-1) == 0
j << c1 j if (c1 & shiftsize-1) == 0
(j << c2) << c1 j << c1+c2, unless c1 + c2 >= max shift, in which case 0
(j >> c2) >> c1 j >> c1+c2, unless c1 + c2 >= max shift, in which case 0
(j >> c1) << c1 j & ~((1<<c1)-1)
(j << c1) lshr c1 j & ((1<<(wordsize-c1))-1)
(j<<c1) >> c2 appropriate EXTRACT
(j & mask) << c1 appropriate COMPOSE
(j >> c1) 0 if j is a load of an unsigned
short type and (c1 mod lengthofshift) > (lengthoftype)
(integerCVT(X) << c1) X if c1 >= 32
(j << 32) ashr 32 I8U4CVT (j)
j shift (k & mask) j << k if mask & (shift_size-1) == shift_size-1
(j & mask) << k j << k if lower (shift_length - k) bits are all 1's.
(j & c1) >> k j >> k &
Helper routine for simplifying expressions like
x+y relop x+z -> y relop z
x+y relop x -> y relop 0
-x relop -y -> y relop x
Simplifications for ==, !=
(x reloporlogop y)==1 x reloporlogop y
(x reloporlogop y)!=0 x reloporlogop y
(x relop y)==0 x inverserelop Y
(x relop y)!=1 x inverserelop Y
(x logop y)==0 !(x logop Y)
(x logop y)!=1 !(x logop Y)
(j & c2) != c1 1 if (c1 & ~c2) is non-zero
(j & c2) == c1 0 if (c1 & ~c2) is non-zero
(j | c2) != c1 1 if (c2 & ~c1) is non-zero
(j | c2) == c1 0 if (c2 & ~c1) is non-zero
(~j & c2) == 0 (j & c2) != 0 if c2 is a power of 2
(j +- c2) relop c1 j relop (c1 -+ c2)
(c2 - j) relop c1 j relop (c2 - c1)
(j * c2) op c1 j op c1/c2 if c2 divides c1
Aggressive:
j==j 1 A
j!=j 0 A
a==a 1 A, IEEE_comparisons is off
a!=a 0 A, IEEE_comparisons is off
x+-y op x+-z y op z (and related) A, IEEE_comparisons is off, Enable_Cfold_Reassociate on
x+-y op x y op 0 A, IEEE_comparisons is off, Enable_Cfold_Reassociate on
Simplifications for <, > <=, >=
For integers only:
x >= MIN VALUE 1
x > MAX VALUE 0
x <= MAX VALUE 1
x < MIN VALUE 0
(x +- c2) op c1 x op (c1 -+ c2)
(c2 - x) op c1 x reversed op (c2 - c1)
x*c1 op c2 x newop c3, c3 is something close to c2/c1
i <= N + -1 i < N
i > N + -1 i >= N
i < N + 1 i <= N
i >= N + 1 i > N
Aggressive:
x <= x 1 (For floating types only if !Force_IEEE_Comparisons)
x >= x 1 "
x < x 0 "
x > x 0 "
Do the transformation
SELECT(x, c0, c1) op c2 -> SELECT(x,c0 op c2, c1 op c2)
Simplifications for CVTL
CVTL (SELECT(X,c1,c2)) -> SELECT(X,CVTL(C1),CVTL(C2))
CVTL n1(CVTL n2(k0)), n2 <= n1 -> cvtl n2(k0)
CVTL n1(CVTL n2(k0)), n2 > n1 -> cvtl n1(k0)
CVTL n (X & c1) -> cvtl n (x) if (1<<n)-1 & c1 = (1<<n)-1
cvtl n (cvtl n (x) op y) -> cvtl n (x op y), op is ADD,SUB,MPY,BIOR,BAND,BXOR,SHL
cvtl n (op cvtl n (x) ) -> cvtl n (op x), op is NEG, BNOT
cvtl n (op cvtl n (x) ) -> op cvtl n (x)), op is ABS
Simplifications for SELECT
FALSE ? x : y y
TRUE ? x : y x
x ? y : y y
boolexpr ? 1 : 0 boolexpr
x ? 1 : 0 NE(x,0)
x ? 0 : 1 NOT(x)
Simplifications for intrinsics (general)
simple reassociations:
---------------------
(j op c1) op c2 j op (c1 op c2) op is +,*,&,|,^,MAX,MIN
(a op c1) op c2 a op (c1 op c2) R:2 op is +,*
(a op c1) op c2 a op (c1 op c2) op is MAX, MIN
(j op c1) op k (j op k) op c1 op is +,*,&,|,^,MAX,MIN
(a op c1) op b (a op b) op c1 R:2 op is +,*
(a op c1) op b (a op b) op c1 op is MAX, MIN
(j op c1) op (k op c2) (j op k) op (c1 op c2) op is +,*,&,|,^,MAX,MIN
(a op c1) op (b op c2) (a op b) op (c1 op c2) R:2 op is +,*
(a op c1) op (b op c2) (a op b) op (c1 op c2) op is MAX, MIN
k op (j op c1) (k op j) op c1 op is +,*,&,|,^,MAX,MIN
b op (a op c1) (b op a) op c1 R:2 op is +,*
b op (a op c1) (b op a) op c1 op is MAX, MIN