This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Fix COND_EXPR foldings that are not happening
- From: Paolo Bonzini <bonzini at gnu dot org>
- To: gcc-patches at gcc dot gnu dot org
- Date: Tue, 08 Jun 2004 16:33:02 +0200
- Subject: Fix COND_EXPR foldings that are not happening
This patch fixes two problems with foldings of COND_EXPRs that "should"
be happening but actually are not.
The first is that fold looks for (A OP B ? A : C), but not for the
similar expression (A OP B ? C : A). This for example means that we do
produce an ABS_EXPR for (x > 0 ? x : -x), but not for (x < 0 ? -x : x).
Currently, phiopt handles that in the end, but fixing this will be
useful both at -O0 and when my patch is finished that bases phiopt on
fold. This is easily done by rewriting the missing template to the one
that is handled (using invert_truthvalue).
Some care is needed to avoid infinite loops. fold tries to invert the
expression if the "then" arm is simpler than the "else" arm: well, after
tree-ssa has been merged (but also before), I'd consider gcc to be
broken if it is still true that having a constant in the "then" arm
produces worse code than having it in the "else" arm. This is also not
helping canonicalization in any way (COND_EXPRs are not always
canonicalized, IIRC they can even keep a TRUTH_NOT_EXPR in the condition
for example).
What did happen was that inverting the arms triggered other foldings:
so, I replaced the inversion with the actual rewritings that it actually
caused to happen, that is, A ? 1 : B to A || B, or A ? 0 : B to !A && B.
The second problem is a missing optimization for (A & N ? N : 0) where N
is a power-of-two. This could be converted to A & N, and indeed fold
includes code to do so: but since the first operand of a COND_EXPR is a
truth value, A & N has already been folded by fold_single_bit_test to
either (A < 0) or to (A >> log2 N) & 1.
The easiest way to fix this is to reconstruct the BIT_AND_EXPR, A & N
(looking into the condition for a variable and supposing that it must be
A), call fold_single_bit_test again, and check that the results matches
the condition in the COND_EXPR. Failure to find A & N will cause the
condition not to be folded, but will not produce incorrect code.
Bootstrapped/regtested i686-pc-linux-gnu. Ok for mainline?
Paolo
gcc/ChangeLog:
2004-06-06 Paolo Bonzini <bonzini@gnu.org>
* fold-const.c (find_only_var): New function.
(fold) <COND_EXPR>: Fold (A OP B) ? C : A, A ? 1 : B,
A ? B : 0. Do not try to invert the two arms of a
COND_EXPR. Fix bitrot in the transformation of
(A & N) ? N : 0 to A & N, where N is power of two.
gcc/testsuite/gcc.dg/Paolo Bonzini
2004-06-06 Paolo Bonzini <bonzini@gnu.org>
* 20040606-1.c: New.
Index: fold-const.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/fold-const.c,v
retrieving revision 1.387
diff -c -r1.387 fold-const.c
*** fold-const.c 31 May 2004 17:01:16 -0000 1.387
--- fold-const.c 7 Jun 2004 12:46:50 -0000
***************
*** 100,105 ****
--- 100,106 ----
static int truth_value_p (enum tree_code);
static int operand_equal_for_comparison_p (tree, tree, tree);
static int twoval_comparison_p (tree, tree *, tree *, int *);
+ static tree find_only_var (tree op);
static tree eval_subst (tree, tree, tree, tree, tree);
static tree pedantic_omit_one_operand (tree, tree, tree);
static tree distribute_bit_expr (enum tree_code, tree, tree, tree);
***************
*** 5371,5376 ****
--- 5372,5454 ----
return NULL_TREE;
}
+ /* Find the only variable referenced inside OP. If there is none,
+ return NULL_TREE; if there is more than one, or if 'e' codes
+ other than truth expressions are encountered, return
+ error_mark_node. */
+ tree
+ find_only_var (tree op)
+ {
+ tree result = NULL_TREE;
+
+ for (;;)
+ {
+ enum tree_code code = TREE_CODE (op);
+ int class = TREE_CODE_CLASS (code);
+ switch (class)
+ {
+ case 'e':
+ if (!truth_value_p (code))
+ return error_mark_node;
+
+ if (code == TRUTH_NOT_EXPR)
+ goto unop;
+ else
+ goto binop;
+
+ case '2':
+ case '<':
+ binop:
+ {
+ tree arg1 = TREE_OPERAND (op, 1);
+ STRIP_NOPS (arg1);
+
+ /* Avoid useless recursion. */
+ if (TREE_CODE_CLASS (TREE_CODE (arg1)) != 'c')
+ {
+ arg1 = find_only_var (arg1);
+ if (arg1 == error_mark_node)
+ return arg1;
+
+ /* If we had already found a variable, fail. */
+ if (arg1 != NULL && result)
+ return error_mark_node;
+
+ result = arg1;
+ }
+ }
+ /* Fall through. */
+
+ case '1':
+ unop:
+ /* Tail recurse. */
+ op = TREE_OPERAND (op, 0);
+ STRIP_NOPS (op);
+ continue;
+
+ case 'c':
+ /* We reached a leaf node and it is not a variable. Return
+ what we had found so far. */
+ return result;
+
+ case 'x':
+ if (code != SSA_NAME)
+ return error_mark_node;
+ case 'd':
+ case 'r':
+ /* We reached a leaf node and it is a variable. If we had already
+ found a variable, fail. */
+ if (result)
+ return error_mark_node;
+ else
+ return op;
+
+ default:
+ return error_mark_node;
+ }
+ }
+ }
+
/* If CODE with arguments ARG0 and ARG1 represents a single bit
equality/inequality test, then return a simplified form of
***************
*** 8360,8378 ****
}
}
! /* If the second operand is simpler than the third, swap them
! since that produces better jump optimization results. */
! if (tree_swap_operands_p (TREE_OPERAND (t, 1),
! TREE_OPERAND (t, 2), false))
! {
! /* See if this can be inverted. If it can't, possibly because
! it was a floating-point inequality comparison, don't do
! anything. */
tem = invert_truthvalue (arg0);
!
! if (TREE_CODE (tem) != TRUTH_NOT_EXPR)
! return fold (build3 (code, type, tem,
! TREE_OPERAND (t, 2), TREE_OPERAND (t, 1)));
}
/* Convert A ? 1 : 0 to simply A. */
--- 8438,8458 ----
}
}
! /* Try swapping the arguments and inverting the conditional. */
! else if (TREE_CODE_CLASS (TREE_CODE (arg0)) == '<'
! && operand_equal_for_comparison_p (TREE_OPERAND (arg0, 0),
! TREE_OPERAND (t, 2),
! TREE_OPERAND (arg0, 1))
! && !HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (TREE_OPERAND (t, 2)))))
! {
tem = invert_truthvalue (arg0);
! if (TREE_CODE_CLASS (TREE_CODE (tem)) == '<')
! {
! tree folded = fold (build3 (COND_EXPR, type, tem,
! TREE_OPERAND (t, 2), arg1));
! if (TREE_CODE (folded) != COND_EXPR)
! return folded;
! }
}
/* Convert A ? 1 : 0 to simply A. */
***************
*** 8394,8410 ****
invert_truthvalue (arg0)));
/* Look for expressions of the form A & 2 ? 2 : 0. The result of this
! operation is simply A & 2. */
!
if (integer_zerop (TREE_OPERAND (t, 2))
- && TREE_CODE (arg0) == NE_EXPR
- && integer_zerop (TREE_OPERAND (arg0, 1))
&& integer_pow2p (arg1)
! && TREE_CODE (TREE_OPERAND (arg0, 0)) == BIT_AND_EXPR
! && operand_equal_p (TREE_OPERAND (TREE_OPERAND (arg0, 0), 1),
! arg1, OEP_ONLY_CONST))
! return pedantic_non_lvalue (fold_convert (type,
! TREE_OPERAND (arg0, 0)));
/* Convert A ? B : 0 into A && B if A and B are truth values. */
if (integer_zerop (TREE_OPERAND (t, 2))
--- 8474,8493 ----
invert_truthvalue (arg0)));
/* Look for expressions of the form A & 2 ? 2 : 0. The result of this
! operation is simply A & 2, but A & 2 has already been folded by
! fold_single_bit_test so we must do some additional checking. */
if (integer_zerop (TREE_OPERAND (t, 2))
&& integer_pow2p (arg1)
! && (tem = find_only_var (arg0)) != NULL_TREE
! && tem != error_mark_node)
! {
! tree result = fold (build2 (BIT_AND_EXPR, TREE_TYPE (tem),
! tem, arg1));
! tem = fold_single_bit_test (NE_EXPR, result, integer_zero_node,
! TREE_TYPE (arg0));
! if (tem && operand_equal_p (arg0, tem, 0))
! return pedantic_non_lvalue (fold_convert (type, result));
! }
/* Convert A ? B : 0 into A && B if A and B are truth values. */
if (integer_zerop (TREE_OPERAND (t, 2))
***************
*** 8425,8430 ****
--- 8508,8533 ----
tem, arg1)));
}
+ /* Convert A ? 0 : B into !A && B if A and B are truth values. */
+ if (integer_zerop (arg1)
+ && truth_value_p (TREE_CODE (arg0))
+ && truth_value_p (TREE_CODE (TREE_OPERAND (t, 2))))
+ {
+ /* Only perform transformation if ARG0 is easily inverted. */
+ tem = invert_truthvalue (arg0);
+ if (TREE_CODE (tem) != TRUTH_NOT_EXPR)
+ return pedantic_non_lvalue (fold (build2 (TRUTH_ANDIF_EXPR, type,
+ tem,
+ TREE_OPERAND (t, 2))));
+ }
+
+ /* Convert A ? 1 : B into A || B if A and B are truth values. */
+ if (integer_onep (arg1)
+ && truth_value_p (TREE_CODE (arg0))
+ && truth_value_p (TREE_CODE (TREE_OPERAND (t, 2))))
+ return pedantic_non_lvalue (fold (build2 (TRUTH_ORIF_EXPR, type,
+ arg0, TREE_OPERAND (t, 2))));
+
return t;
case COMPOUND_EXPR:
/* { dg-do compile } */
/* { dg-options "-O1 -fdump-tree-generic" } */
int f( int i)
{
int j = (i < 0) ? -i : i;
return j;
}
int g( int i)
{
int j = (i < 0) ? i : -i;
return j;
}
int h( int i)
{
int j = (i & 2) ? 2 : 0;
return j;
}
/* We should fold these COND_EXPRs into straightline code. */
/* { dg-final { scan-tree-dump-times "if" 0 "generic"} } */