[PATCH] PR opt/3995: Optimize (A&C)!=0 into A<0 (take 2)
Roger Sayle
roger@eyesopen.com
Sun May 5 11:22:00 GMT 2002
On Sat, 4 May 2002, Richard Henderson wrote:
> I think you should also handle unsigned types. You should
> render "uint & c" as "(signed int)uint < 0".
That's a neat improvement. Its implemented in the revision of the
patch below. Examining a few examples, this always improves code
but also creates optimization opportunities that are missed elsewhere.
For example "(c!=0) && (c>=0)" produces wierd but correct output when
the first comparison is unsigned but the second is signed. I'll work
on an additional follow-up patch to address this issue.
> > + hi = (unsigned HOST_WIDE_INT) 1 << (width - HOST_BITS_PER_WIDE_INT);
> width - HOST_BITS_PER_WIDE_INT - 1
Doh!
I've now taken Kaveh's advice and added a new testcase, 20020505-1.c,
that checks that these optimizations (and the one immediately preceding
in fold) produce the expected results at run-time. We can't check that
the optimization is applied, but we might as well test for correctness.
Once again tested with a complete "make bootstrap" and "make -k check"
on i686-pc-linux-gnu with all languages except Ada. There are no new
testsuite regressions, and the new testcase passes both with and without
this patch applied.
Ok for mainline and to close PR 3995?
And the fold-const.c warning fix patch?
Many thanks once again,
Roger
2002-05-05 Roger Sayle <roger@eyesopen.com>
PR opt/3995.
* fold-const.c (sign_bit_p): New function.
(fold) [EQ_EXPR]: Use this to convert (A & C) == 0 into A >= 0 and
(A & C) != 0 into A < 0, when constant C is the sign bit of A's type.
Reapply fold when converting (A & C) == C into (A & C) != 0.
(fold_binary_op_with_conditional_arg): Fix typo in comment.
* gcc.c-torture/execute/20020505-1.c: New test case.
Index: fold-const.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/fold-const.c,v
retrieving revision 1.198
diff -c -3 -p -r1.198 fold-const.c
*** fold-const.c 23 Apr 2002 23:31:02 -0000 1.198
--- fold-const.c 5 May 2002 14:37:37 -0000
*************** static tree decode_field_reference PARAM
*** 86,91 ****
--- 86,92 ----
enum machine_mode *, int *,
int *, tree *, tree *));
static int all_ones_mask_p PARAMS ((tree, int));
+ static tree sign_bit_p PARAMS ((tree, tree));
static int simple_operand_p PARAMS ((tree));
static tree range_binop PARAMS ((enum tree_code, tree, tree, int,
tree, int));
*************** all_ones_mask_p (mask, size)
*** 2633,2638 ****
--- 2634,2688 ----
size_int (precision - size), 0));
}
+ /* Subroutine for fold: determine if VAL is the INTEGER_CONST that
+ represents the sign bit of EXP's type. If EXP represents a sign
+ or zero extension, also test VAL against the unextended type.
+ The return value is the (sub)expression whose sign bit is VAL,
+ or NULL_TREE otherwise. */
+
+ static tree
+ sign_bit_p (exp, val)
+ tree exp;
+ tree val;
+ {
+ unsigned HOST_WIDE_INT lo;
+ HOST_WIDE_INT hi;
+ int width;
+ tree t;
+
+ /* Tree EXP must have a integral type. */
+ t = TREE_TYPE (exp);
+ if (! INTEGRAL_TYPE_P (t))
+ return NULL_TREE;
+
+ /* Tree VAL must be an integer constant. */
+ if (TREE_CODE (val) != INTEGER_CST
+ || TREE_CONSTANT_OVERFLOW (val))
+ return NULL_TREE;
+
+ width = TYPE_PRECISION (t);
+ if (width > HOST_BITS_PER_WIDE_INT)
+ {
+ hi = (unsigned HOST_WIDE_INT) 1 << (width - HOST_BITS_PER_WIDE_INT - 1);
+ lo = 0;
+ }
+ else
+ {
+ hi = 0;
+ lo = (unsigned HOST_WIDE_INT) 1 << (width - 1);
+ }
+
+ if (TREE_INT_CST_HIGH (val) == hi && TREE_INT_CST_LOW (val) == lo)
+ return exp;
+
+ /* Handle extension from a narrower type. */
+ if (TREE_CODE (exp) == NOP_EXPR
+ && TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (exp, 0))) < width)
+ return sign_bit_p (TREE_OPERAND (exp, 0), val);
+
+ return NULL_TREE;
+ }
+
/* Subroutine for fold_truthop: determine if an operand is simple enough
to be evaluated unconditionally. */
*************** count_cond (expr, lim)
*** 4172,4178 ****
return MIN (lim, 1 + ctrue + cfalse);
}
! /* Transform `a + (b ? x : y)' into `x ? (a + b) : (a + y)'.
Transform, `a + (x < y)' into `(x < y) ? (a + 1) : (a + 0)'. Here
CODE corresponds to the `+', COND to the `(b ? x : y)' or `(x < y)'
expression, and ARG to `a'. If COND_FIRST_P is non-zero, then the
--- 4222,4228 ----
return MIN (lim, 1 + ctrue + cfalse);
}
! /* Transform `a + (b ? x : y)' into `b ? (a + x) : (a + y)'.
Transform, `a + (x < y)' into `(x < y) ? (a + 1) : (a + 0)'. Here
CODE corresponds to the `+', COND to the `(b ? x : y)' or `(x < y)'
expression, and ARG to `a'. If COND_FIRST_P is non-zero, then the
*************** fold (expr)
*** 6047,6054 ****
&& TREE_CODE (arg0) == BIT_AND_EXPR
&& integer_pow2p (TREE_OPERAND (arg0, 1))
&& operand_equal_p (TREE_OPERAND (arg0, 1), arg1, 0))
! return build (code == EQ_EXPR ? NE_EXPR : EQ_EXPR, type,
! arg0, integer_zero_node);
/* If X is unsigned, convert X < (1 << Y) into X >> Y == 0
and similarly for >= into !=. */
--- 6097,6121 ----
&& TREE_CODE (arg0) == BIT_AND_EXPR
&& integer_pow2p (TREE_OPERAND (arg0, 1))
&& operand_equal_p (TREE_OPERAND (arg0, 1), arg1, 0))
! return fold (build (code == EQ_EXPR ? NE_EXPR : EQ_EXPR, type,
! arg0, integer_zero_node));
!
! /* If we have (A & C) != 0 where C is the sign bit of A, convert
! this into A < 0. Similarly for (A & C) == 0 into A >= 0. */
! if ((code == EQ_EXPR || code == NE_EXPR)
! && TREE_CODE (arg0) == BIT_AND_EXPR
! && integer_zerop (arg1))
! {
! tree arg00 = sign_bit_p (TREE_OPERAND (arg0, 0),
! TREE_OPERAND (arg0, 1));
! if (arg00 != NULL_TREE)
! {
! tree stype = (*lang_hooks.types.signed_type) (TREE_TYPE (arg00));
! return fold (build (code == EQ_EXPR ? GE_EXPR : LT_EXPR, type,
! convert (stype, arg00),
! convert (stype, integer_zero_node)));
! }
! }
/* If X is unsigned, convert X < (1 << Y) into X >> Y == 0
and similarly for >= into !=. */
*** /dev/null Thu Aug 30 14:30:55 2001
--- gcc.c-torture/execute/20020505-1.c Sun May 5 11:10:32 2002
***************
*** 0 ****
--- 1,320 ----
+ /* Copyright (C) 2002 Free Software Foundation.
+
+ Test that (A & C1) op C2 optimizations behave correctly where C1 is
+ a constant power of 2, op is == or !=, and C2 is C1 or zero.
+
+ Written by Roger Sayle, 5th May 2002. */
+
+ extern void abort (void);
+
+ void test1 (char c, int set);
+ void test2 (unsigned char c, int set);
+ void test3 (short s, int set);
+ void test4 (unsigned short s, int set);
+ void test5 (int i, int set);
+ void test6 (unsigned int i, int set);
+ void test7 (long long l, int set);
+ void test8 (unsigned long long l, int set);
+
+ void
+ test1 (char c, int set)
+ {
+ if ((c & 0x80) == 0)
+ {
+ if (set) abort ();
+ }
+ else
+ if (!set) abort ();
+
+ if ((c & 0x80) != 0)
+ {
+ if (!set) abort ();
+ }
+ else
+ if (set) abort ();
+
+ if ((c & 0x80) == 0x80)
+ {
+ if (!set) abort ();
+ }
+ else
+ if (set) abort ();
+
+ if ((c & 0x80) != 0x80)
+ {
+ if (set) abort ();
+ }
+ else
+ if (!set) abort ();
+ }
+
+ void
+ test2 (unsigned char c, int set)
+ {
+ if ((c & 0x80) == 0)
+ {
+ if (set) abort ();
+ }
+ else
+ if (!set) abort ();
+
+ if ((c & 0x80) != 0)
+ {
+ if (!set) abort ();
+ }
+ else
+ if (set) abort ();
+
+ if ((c & 0x80) == 0x80)
+ {
+ if (!set) abort ();
+ }
+ else
+ if (set) abort ();
+
+ if ((c & 0x80) != 0x80)
+ {
+ if (set) abort ();
+ }
+ else
+ if (!set) abort ();
+ }
+
+ void
+ test3 (short s, int set)
+ {
+ if ((s & 0x8000) == 0)
+ {
+ if (set) abort ();
+ }
+ else
+ if (!set) abort ();
+
+ if ((s & 0x8000) != 0)
+ {
+ if (!set) abort ();
+ }
+ else
+ if (set) abort ();
+
+ if ((s & 0x8000) == 0x8000)
+ {
+ if (!set) abort ();
+ }
+ else
+ if (set) abort ();
+
+ if ((s & 0x8000) != 0x8000)
+ {
+ if (set) abort ();
+ }
+ else
+ if (!set) abort ();
+ }
+
+ void
+ test4 (unsigned short s, int set)
+ {
+ if ((s & 0x8000) == 0)
+ {
+ if (set) abort ();
+ }
+ else
+ if (!set) abort ();
+
+ if ((s & 0x8000) != 0)
+ {
+ if (!set) abort ();
+ }
+ else
+ if (set) abort ();
+
+ if ((s & 0x8000) == 0x8000)
+ {
+ if (!set) abort ();
+ }
+ else
+ if (set) abort ();
+
+ if ((s & 0x8000) != 0x8000)
+ {
+ if (set) abort ();
+ }
+ else
+ if (!set) abort ();
+ }
+
+ void
+ test5 (int i, int set)
+ {
+ if ((i & 0x80000000) == 0)
+ {
+ if (set) abort ();
+ }
+ else
+ if (!set) abort ();
+
+ if ((i & 0x80000000) != 0)
+ {
+ if (!set) abort ();
+ }
+ else
+ if (set) abort ();
+
+ if ((i & 0x80000000) == 0x80000000)
+ {
+ if (!set) abort ();
+ }
+ else
+ if (set) abort ();
+
+ if ((i & 0x80000000) != 0x80000000)
+ {
+ if (set) abort ();
+ }
+ else
+ if (!set) abort ();
+ }
+
+ void
+ test6 (unsigned int i, int set)
+ {
+ if ((i & 0x80000000) == 0)
+ {
+ if (set) abort ();
+ }
+ else
+ if (!set) abort ();
+
+ if ((i & 0x80000000) != 0)
+ {
+ if (!set) abort ();
+ }
+ else
+ if (set) abort ();
+
+ if ((i & 0x80000000) == 0x80000000)
+ {
+ if (!set) abort ();
+ }
+ else
+ if (set) abort ();
+
+ if ((i & 0x80000000) != 0x80000000)
+ {
+ if (set) abort ();
+ }
+ else
+ if (!set) abort ();
+ }
+
+ void
+ test7 (long long l, int set)
+ {
+ if ((l & 0x8000000000000000LL) == 0)
+ {
+ if (set) abort ();
+ }
+ else
+ if (!set) abort ();
+
+ if ((l & 0x8000000000000000LL) != 0)
+ {
+ if (!set) abort ();
+ }
+ else
+ if (set) abort ();
+
+ if ((l & 0x8000000000000000LL) == 0x8000000000000000LL)
+ {
+ if (!set) abort ();
+ }
+ else
+ if (set) abort ();
+
+ if ((l & 0x8000000000000000LL) != 0x8000000000000000LL)
+ {
+ if (set) abort ();
+ }
+ else
+ if (!set) abort ();
+ }
+
+ void
+ test8 (unsigned long long l, int set)
+ {
+ if ((l & 0x8000000000000000LL) == 0)
+ {
+ if (set) abort ();
+ }
+ else
+ if (!set) abort ();
+
+ if ((l & 0x8000000000000000LL) != 0)
+ {
+ if (!set) abort ();
+ }
+ else
+ if (set) abort ();
+
+ if ((l & 0x8000000000000000LL) == 0x8000000000000000LL)
+ {
+ if (!set) abort ();
+ }
+ else
+ if (set) abort ();
+
+ if ((l & 0x8000000000000000LL) != 0x8000000000000000LL)
+ {
+ if (set) abort ();
+ }
+ else
+ if (!set) abort ();
+ }
+
+ int
+ main ()
+ {
+ test1 (0x00, 0);
+ test1 (0x7f, 0);
+ test1 (0x80, 1);
+ test1 (0xff, 1);
+
+ test2 (0x00, 0);
+ test2 (0x7f, 0);
+ test2 (0x80, 1);
+ test2 (0xff, 1);
+
+ test3 (0x0000, 0);
+ test3 (0x7fff, 0);
+ test3 (0x8000, 1);
+ test3 (0xffff, 1);
+
+ test4 (0x0000, 0);
+ test4 (0x7fff, 0);
+ test4 (0x8000, 1);
+ test4 (0xffff, 1);
+
+ test5 (0x00000000, 0);
+ test5 (0x7fffffff, 0);
+ test5 (0x80000000, 1);
+ test5 (0xffffffff, 1);
+
+ test6 (0x00000000, 0);
+ test6 (0x7fffffff, 0);
+ test6 (0x80000000, 1);
+ test6 (0xffffffff, 1);
+
+ test7 (0x0000000000000000LL, 0);
+ test7 (0x7fffffffffffffffLL, 0);
+ test7 (0x8000000000000000LL, 1);
+ test7 (0xffffffffffffffffLL, 1);
+
+ test8 (0x0000000000000000LL, 0);
+ test8 (0x7fffffffffffffffLL, 0);
+ test8 (0x8000000000000000LL, 1);
+ test8 (0xffffffffffffffffLL, 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
More information about the Gcc-patches
mailing list