This patch fixes PR tree-optimization/102950, which is a P2 regression,
by providing better range bounds for BIT_XOR_EXPR, BIT_AND_EXPR and
BIT_IOR_EXPR on signed integer types.  In general terms, any binary
bitwise operation on sign-extended or zero-extended integer types will
produce results that are themselves sign-extended or zero-extended.
More precisely, we can derive signed bounds from the number of leading
redundant sign bit copies, from the equation:
        clrsb(X op Y) >= min (clrsb (X), clrsb(Y))
and from the property that for any (signed or unsigned) range [lb, ub]
that clrsb([lb, ub]) >= min (clrsb(lb), clrsb(ub)).

These can be used to show that [-1, 0] op [-1, 0] is [-1, 0] or that
[-128, 127] op [-128, 127] is [-128, 127], even when tracking nonzero
bits would result in VARYING (as every bit can be 0 or 1).  This is
equivalent to determining the minimum type precision in which the
operation can be performed then sign extending the result.

One additional refinement is to observe that X ^ Y can never be
zero if the ranges of X and Y don't overlap, i.e. X can't be equal
to Y.

Previously, the expression "(int)(char)a ^ 233" in the PR was considered
VARYING, but with the above changes now has the range [-256, -1][1, 255],
which is sufficient to optimize away the call to foo.


This patch has been tested on x86_64-pc-linux-gnu with make bootstrap
and make -k check with no new failures.  Ok for mainline?


2022-02-01  Roger Sayle  <roger@nextmovesoftware.com>

gcc/ChangeLog
	PR tree-optimization/102950
	* range-op.cc (wi_optimize_signed_bitwise_op): New function to
	determine bounds of bitwise operations on signed types.
	(operator_bitwise_and::wi_fold): Call the above function.
	(operator_bitwise_or::wi_fold): Likewise.
	(operator_bitwise_xor::wi_fold): Likewise.  Additionally, the
	result can't be zero if the operands can't be equal.

gcc/testsuite/ChangeLog
	PR tree-optimization/102950
	gcc.dg/pr102950.c: New test case.
	gcc.dg/tree-ssa/evrp10.c: New test case.


Thanks in advance (and Happy Chinese New Year),
Roger
--