middle-end: Parity and popcount folding optimizations.

middle-end: Parity and popcount folding optimizations.

This patch implements several constant folding optimizations
for __builtin_parity and friends.  We canonicalize popcount(x)&1
as parity(x) in gimple, and potentially convert back again when
we expand to RTL.  parity(~x) is simplified to parity(x), which
is true for all integer modes with an even number of bits.
But probably most usefully, parity(x)^parity(y) can be simplified
to a parity(x^y), requiring only a single libcall or popcount.

This patch optimizes popcount and parity of an argument known to have
at most a single bit set, to be that single bit.  Hence, popcount(x&8)
is simplified to (x>>3)&1.   This generalizes the existing optimization
of popcount(x&1) being simplified to x&1, which is cleaned up with
this patch.

2020-07-28  Roger Sayle  <roger@nextmovesoftware.com>
	    Richard Biener  <rguenther@suse.de>

gcc/ChangeLog
	* match.pd (popcount(x)&1 -> parity(x)): New simplification.
	(parity(~x) -> parity(x)): New simplification.
	(parity(x)^parity(y) -> parity(x^y)): New simplification.
	(parity(x&1) -> x&1): New simplification.
	(popcount(x) -> x>>C): New simplification.

gcc/testsuite/ChangeLog
	* gcc.dg/fold-popcount-5.c: New test.
	* gcc.dg/fold-parity-1.c: Likewise.
	* gcc.dg/fold-parity-2.c: Likewise.
	* gcc.dg/fold-parity-3.c: Likewise.
	* gcc.dg/fold-parity-4.c: Likewise.
	* gcc.dg/fold-parity-5.c: Likewise.