This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

List of simplifications we should perform


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



Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]