This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[Committed] Constant fold "X & ~X" and friends
- From: Roger Sayle <roger at eyesopen dot com>
- To: gcc-patches at gcc dot gnu dot org
- Date: Sun, 27 Jun 2004 09:37:25 -0600 (MDT)
- Subject: [Committed] Constant fold "X & ~X" and friends
The following patch adds support for constant folding expressions of
the form "X op ~X" at the tree-level. Many of these transformations
are already implemented in the RTL optimizers, but performing them
earlier should assist tree-ssa. We now optimize the following
X & ~X -> 0
~X & X -> 0
X | ~X -> -1
~X | X -> -1
X ^ ~X -> -1
~X ^ X -> -1
X && !X -> false
!X && X -> false
X || !X -> true
!X || X -> true
X ^^ !X -> true
!X ^^ X -> true
All of which where the expression "X" has no side-effects.
I also cleaned up the TRUTH_XOR_EXPR case in fold. Now that the tree.c
knows that TRUTH_XOR_EXPR is a commutative operator, "fold" will always
canonicalize constant operands last, so we no longer have to test whether
either operand is constant when pattern matching some transformations.
The following patch has been tested on i686-pc-linux-gnu with a full
"make bootstrap", all default languages, and regression tested with a
top-level "make -k check" with no new failures.
Committed to mainline CVS.
2004-06-27 Roger Sayle <roger@eyesopen.com>
* fold-const.c (fold) <BIT_IOR_EXPR>: Optimize ~X|X and X|~X as -1.
<BIT_XOR_EXPR>: Optimize ~X|X and X|~X as -1.
<BIT_AND_EXPR>: Optimize ~X&X and X&~X as 0.
<TRUTH_AND_EXPR, TRUTH_ANDIF_EXPR>: Optimize !X&&X and X&&!X as false.
<TRUTH_OR_EXPR, TRUTH_ORIF_EXPR>: Optimize !X||X and !X||X as true.
<TRUTH_XOR_EXPR>: Optimize !X^X and X^X! as true. Now that
TRUTH_XOR_EXPR is a commutative tree code, don't test whether arg0
is a constant.
* gcc.dg/20040527-1.c: New test case.
Index: fold-const.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/fold-const.c,v
retrieving revision 1.410
diff -c -3 -p -r1.410 fold-const.c
*** fold-const.c 25 Jun 2004 01:28:34 -0000 1.410
--- fold-const.c 27 Jun 2004 01:49:37 -0000
*************** fold (tree expr)
*** 7185,7190 ****
--- 7185,7211 ----
return non_lvalue (fold_convert (type, arg0));
if (operand_equal_p (arg0, arg1, 0))
return non_lvalue (fold_convert (type, arg0));
+
+ /* ~X | X is -1. */
+ if (TREE_CODE (arg0) == BIT_NOT_EXPR
+ && operand_equal_p (TREE_OPERAND (arg0, 0), arg1, 0))
+ {
+ t1 = build_int_2 (-1, -1);
+ TREE_TYPE (t1) = type;
+ force_fit_type (t1, 0);
+ return omit_one_operand (type, t1, arg1);
+ }
+
+ /* X | ~X is -1. */
+ if (TREE_CODE (arg1) == BIT_NOT_EXPR
+ && operand_equal_p (arg0, TREE_OPERAND (arg1, 0), 0))
+ {
+ t1 = build_int_2 (-1, -1);
+ TREE_TYPE (t1) = type;
+ force_fit_type (t1, 0);
+ return omit_one_operand (type, t1, arg0);
+ }
+
t1 = distribute_bit_expr (code, type, arg0, arg1);
if (t1 != NULL_TREE)
return t1;
*************** fold (tree expr)
*** 7216,7221 ****
--- 7237,7262 ----
if (operand_equal_p (arg0, arg1, 0))
return omit_one_operand (type, integer_zero_node, arg0);
+ /* ~X ^ X is -1. */
+ if (TREE_CODE (arg0) == BIT_NOT_EXPR
+ && operand_equal_p (TREE_OPERAND (arg0, 0), arg1, 0))
+ {
+ t1 = build_int_2 (-1, -1);
+ TREE_TYPE (t1) = type;
+ force_fit_type (t1, 0);
+ return omit_one_operand (type, t1, arg1);
+ }
+
+ /* X ^ ~X is -1. */
+ if (TREE_CODE (arg1) == BIT_NOT_EXPR
+ && operand_equal_p (arg0, TREE_OPERAND (arg1, 0), 0))
+ {
+ t1 = build_int_2 (-1, -1);
+ TREE_TYPE (t1) = type;
+ force_fit_type (t1, 0);
+ return omit_one_operand (type, t1, arg0);
+ }
+
/* If we are XORing two BIT_AND_EXPR's, both of which are and'ing
with a constant, and the two constants have no bits in common,
we should treat this as a BIT_IOR_EXPR since this may produce more
*************** fold (tree expr)
*** 7243,7248 ****
--- 7284,7300 ----
return omit_one_operand (type, arg1, arg0);
if (operand_equal_p (arg0, arg1, 0))
return non_lvalue (fold_convert (type, arg0));
+
+ /* ~X & X is always zero. */
+ if (TREE_CODE (arg0) == BIT_NOT_EXPR
+ && operand_equal_p (TREE_OPERAND (arg0, 0), arg1, 0))
+ return omit_one_operand (type, integer_zero_node, arg1);
+
+ /* X & ~X is always zero. */
+ if (TREE_CODE (arg1) == BIT_NOT_EXPR
+ && operand_equal_p (arg0, TREE_OPERAND (arg1, 0), 0))
+ return omit_one_operand (type, integer_zero_node, arg0);
+
t1 = distribute_bit_expr (code, type, arg0, arg1);
if (t1 != NULL_TREE)
return t1;
*************** fold (tree expr)
*** 7625,7630 ****
--- 7677,7691 ----
if (integer_zerop (arg0))
return omit_one_operand (type, arg0, arg1);
+ /* !X && X is always false. */
+ if (TREE_CODE (arg0) == TRUTH_NOT_EXPR
+ && operand_equal_p (TREE_OPERAND (arg0, 0), arg1, 0))
+ return omit_one_operand (type, integer_zero_node, arg1);
+ /* X && !X is always false. */
+ if (TREE_CODE (arg1) == TRUTH_NOT_EXPR
+ && operand_equal_p (arg0, TREE_OPERAND (arg1, 0), 0))
+ return omit_one_operand (type, integer_zero_node, arg0);
+
truth_andor:
/* We only do these simplifications if we are optimizing. */
if (!optimize)
*************** fold (tree expr)
*** 7712,7733 ****
TRUTH_OR_EXPR. */
if (TREE_CODE (arg0) == INTEGER_CST && ! integer_zerop (arg0))
return omit_one_operand (type, arg0, arg1);
goto truth_andor;
case TRUTH_XOR_EXPR:
! /* If either arg is constant zero, drop it. */
! if (integer_zerop (arg0))
! return non_lvalue (fold_convert (type, arg1));
if (integer_zerop (arg1))
return non_lvalue (fold_convert (type, arg0));
! /* If either arg is constant true, this is a logical inversion. */
! if (integer_onep (arg0))
! return non_lvalue (fold_convert (type, invert_truthvalue (arg1)));
if (integer_onep (arg1))
return non_lvalue (fold_convert (type, invert_truthvalue (arg0)));
/* Identical arguments cancel to zero. */
if (operand_equal_p (arg0, arg1, 0))
return omit_one_operand (type, integer_zero_node, arg0);
return t;
case EQ_EXPR:
--- 7773,7811 ----
TRUTH_OR_EXPR. */
if (TREE_CODE (arg0) == INTEGER_CST && ! integer_zerop (arg0))
return omit_one_operand (type, arg0, arg1);
+
+ /* !X || X is always true. */
+ if (TREE_CODE (arg0) == TRUTH_NOT_EXPR
+ && operand_equal_p (TREE_OPERAND (arg0, 0), arg1, 0))
+ return omit_one_operand (type, integer_one_node, arg1);
+ /* X || !X is always true. */
+ if (TREE_CODE (arg1) == TRUTH_NOT_EXPR
+ && operand_equal_p (arg0, TREE_OPERAND (arg1, 0), 0))
+ return omit_one_operand (type, integer_one_node, arg0);
+
goto truth_andor;
case TRUTH_XOR_EXPR:
! /* If the second arg is constant zero, drop it. */
if (integer_zerop (arg1))
return non_lvalue (fold_convert (type, arg0));
! /* If the second arg is constant true, this is a logical inversion. */
if (integer_onep (arg1))
return non_lvalue (fold_convert (type, invert_truthvalue (arg0)));
/* Identical arguments cancel to zero. */
if (operand_equal_p (arg0, arg1, 0))
return omit_one_operand (type, integer_zero_node, arg0);
+
+ /* !X ^ X is always true. */
+ if (TREE_CODE (arg0) == TRUTH_NOT_EXPR
+ && operand_equal_p (TREE_OPERAND (arg0, 0), arg1, 0))
+ return omit_one_operand (type, integer_one_node, arg1);
+
+ /* X ^ !X is always true. */
+ if (TREE_CODE (arg1) == TRUTH_NOT_EXPR
+ && operand_equal_p (arg0, TREE_OPERAND (arg1, 0), 0))
+ return omit_one_operand (type, integer_one_node, arg0);
+
return t;
case EQ_EXPR:
/* { dg-do link } */
/* { dg-options "-O2" } */
extern void link_error (void);
void test(int x)
{
if ((x & ~x) != 0)
link_error ();
if ((~x & x) != 0)
link_error ();
if ((x ^ ~x) != -1)
link_error ();
if ((~x ^ x) != -1)
link_error ();
if ((x | ~x) != -1)
link_error ();
if ((~x | x) != -1)
link_error ();
if (x && !x)
link_error ();
if (!x && x)
link_error ();
if (!(x || !x))
link_error ();
if (!(!x || x))
link_error ();
}
int main()
{
test (0);
test (1);
test (-1);
return 0;
}
Roger
--
Roger Sayle, E-mail: roger@eyesopen.com
OpenEye Scientific Software, WWW: http://www.eyesopen.com/
Suite 1107, 3600 Cerrillos Road, Tel: (+1) 505-473-7385
Santa Fe, New Mexico, 87507. Fax: (+1) 505-473-0833