diff mbox

Fix optimize_range_tests_diff

Message ID 20141014160219.GF10376@tucnak.redhat.com
State New
Headers show

Commit Message

Jakub Jelinek Oct. 14, 2014, 4:02 p.m. UTC 
Hi!

When hacking on range reassoc opt, I've noticed we can emit
code with undefined behavior even when there wasn't one originally,
in particular for:
   (X - 43U) <= 3U || (X - 75U) <= 3U
   and this loop can transform that into
   ((X - 43U) & ~(75U - 43U)) <= 3U.  */
we actually don't transform it to what the comment says, but
   ((X - 43) & ~(75U - 43U)) <= 3U
i.e. the initial subtraction can be performed in signed type,
if in here X is e.g. INT_MIN or INT_MIN + 42, the subtraction
at gimple level would be UB (not caught by -fsanitize=undefined,
because that is handled much earlier).

Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

2014-10-14  Jakub Jelinek  <jakub@redhat.com>

	* tree-ssa-reassoc.c (optimize_range_tests_diff): Perform
	MINUS_EXPR in unsigned type to avoid undefined behavior.


	Jakub

Comments

Richard Biener Oct. 14, 2014, 5:18 p.m. UTC | #1 
On October 14, 2014 6:02:19 PM CEST, Jakub Jelinek <jakub@redhat.com> wrote:
>Hi!
>
>When hacking on range reassoc opt, I've noticed we can emit
>code with undefined behavior even when there wasn't one originally,
>in particular for:
>   (X - 43U) <= 3U || (X - 75U) <= 3U
>   and this loop can transform that into
>   ((X - 43U) & ~(75U - 43U)) <= 3U.  */
>we actually don't transform it to what the comment says, but
>   ((X - 43) & ~(75U - 43U)) <= 3U
>i.e. the initial subtraction can be performed in signed type,
>if in here X is e.g. INT_MIN or INT_MIN + 42, the subtraction
>at gimple level would be UB (not caught by -fsanitize=undefined,
>because that is handled much earlier).
>
>Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

OK.

Thanks,
Richard.

>2014-10-14  Jakub Jelinek  <jakub@redhat.com>
>
>	* tree-ssa-reassoc.c (optimize_range_tests_diff): Perform
>	MINUS_EXPR in unsigned type to avoid undefined behavior.
>
>--- gcc/tree-ssa-reassoc.c.jj	2014-10-13 17:54:33.000000000 +0200
>+++ gcc/tree-ssa-reassoc.c	2014-10-13 17:58:07.312705218 +0200
>@@ -2250,8 +2250,13 @@ optimize_range_tests_diff (enum tree_cod
>   if (tree_log2 (tem1) < 0)
>     return false;
> 
>+  type = unsigned_type_for (type);
>+  tem1 = fold_convert (type, tem1);
>+  tem2 = fold_convert (type, tem2);
>+  lowi = fold_convert (type, lowi);
>   mask = fold_build1 (BIT_NOT_EXPR, type, tem1);
>-  tem1 = fold_binary (MINUS_EXPR, type, rangei->exp, lowi);
>+  tem1 = fold_binary (MINUS_EXPR, type,
>+		      fold_convert (type, rangei->exp), lowi);
>   tem1 = fold_build2 (BIT_AND_EXPR, type, tem1, mask);
>   lowj = build_int_cst (type, 0);
>   if (update_range_test (rangei, rangej, 1, opcode, ops, tem1,
>
>	Jakub
Jeff Law Oct. 14, 2014, 5:23 p.m. UTC | #2 
On 10/14/14 10:02, Jakub Jelinek wrote:
> Hi!
>
> When hacking on range reassoc opt, I've noticed we can emit
> code with undefined behavior even when there wasn't one originally,
> in particular for:
>     (X - 43U) <= 3U || (X - 75U) <= 3U
>     and this loop can transform that into
>     ((X - 43U) & ~(75U - 43U)) <= 3U.  */
> we actually don't transform it to what the comment says, but
>     ((X - 43) & ~(75U - 43U)) <= 3U
> i.e. the initial subtraction can be performed in signed type,
> if in here X is e.g. INT_MIN or INT_MIN + 42, the subtraction
> at gimple level would be UB (not caught by -fsanitize=undefined,
> because that is handled much earlier).
>
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
>
> 2014-10-14  Jakub Jelinek  <jakub@redhat.com>
>
> 	* tree-ssa-reassoc.c (optimize_range_tests_diff): Perform
> 	MINUS_EXPR in unsigned type to avoid undefined behavior.
Any chance this fixes:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63302


Jeff
Jakub Jelinek Oct. 14, 2014, 5:40 p.m. UTC | #3 
On Tue, Oct 14, 2014 at 11:23:22AM -0600, Jeff Law wrote:
> On 10/14/14 10:02, Jakub Jelinek wrote:
> >When hacking on range reassoc opt, I've noticed we can emit
> >code with undefined behavior even when there wasn't one originally,
> >in particular for:
> >    (X - 43U) <= 3U || (X - 75U) <= 3U
> >    and this loop can transform that into
> >    ((X - 43U) & ~(75U - 43U)) <= 3U.  */
> >we actually don't transform it to what the comment says, but
> >    ((X - 43) & ~(75U - 43U)) <= 3U
> >i.e. the initial subtraction can be performed in signed type,
> >if in here X is e.g. INT_MIN or INT_MIN + 42, the subtraction
> >at gimple level would be UB (not caught by -fsanitize=undefined,
> >because that is handled much earlier).
> >
> >Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
> >
> >2014-10-14  Jakub Jelinek  <jakub@redhat.com>
> >
> >	* tree-ssa-reassoc.c (optimize_range_tests_diff): Perform
> >	MINUS_EXPR in unsigned type to avoid undefined behavior.
> Any chance this fixes:
> 
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63302

No.  For that I have right now:
-  if (tree_log2 (lowxor) < 0)
+  if (wi::popcount (wi::to_widest (lowxor)) != 1)
in my tree, though supposedly:
   if (wi::popcount (wi::zext (wi::to_widest (lowxor), TYPE_PRECISION (TREE_TYPE (lowxor)))) != 1)
might be better, as without zext it will supposedly
not say popcount is 1 for smaller precision signed minimum values.
My wide-int-fu is limited, so if there is a better way to do this, I'm all
ears.

	Jakub
Jeff Law Oct. 14, 2014, 5:48 p.m. UTC | #4 
On 10/14/14 11:40, Jakub Jelinek wrote:
> On Tue, Oct 14, 2014 at 11:23:22AM -0600, Jeff Law wrote:
>> On 10/14/14 10:02, Jakub Jelinek wrote:
>>> When hacking on range reassoc opt, I've noticed we can emit
>>> code with undefined behavior even when there wasn't one originally,
>>> in particular for:
>>>     (X - 43U) <= 3U || (X - 75U) <= 3U
>>>     and this loop can transform that into
>>>     ((X - 43U) & ~(75U - 43U)) <= 3U.  */
>>> we actually don't transform it to what the comment says, but
>>>     ((X - 43) & ~(75U - 43U)) <= 3U
>>> i.e. the initial subtraction can be performed in signed type,
>>> if in here X is e.g. INT_MIN or INT_MIN + 42, the subtraction
>>> at gimple level would be UB (not caught by -fsanitize=undefined,
>>> because that is handled much earlier).
>>>
>>> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
>>>
>>> 2014-10-14  Jakub Jelinek  <jakub@redhat.com>
>>>
>>> 	* tree-ssa-reassoc.c (optimize_range_tests_diff): Perform
>>> 	MINUS_EXPR in unsigned type to avoid undefined behavior.
>> Any chance this fixes:
>>
>> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63302
>
> No.  For that I have right now:
> -  if (tree_log2 (lowxor) < 0)
> +  if (wi::popcount (wi::to_widest (lowxor)) != 1)
> in my tree, though supposedly:
>     if (wi::popcount (wi::zext (wi::to_widest (lowxor), TYPE_PRECISION (TREE_TYPE (lowxor)))) != 1)
> might be better, as without zext it will supposedly
> not say popcount is 1 for smaller precision signed minimum values.
> My wide-int-fu is limited, so if there is a better way to do this, I'm all
> ears.
Ok.  Thanks for checking.

jeff
Richard Sandiford Nov. 18, 2014, 12:56 p.m. UTC | #5 
Jakub Jelinek <jakub@redhat.com> writes:
> On Tue, Oct 14, 2014 at 11:23:22AM -0600, Jeff Law wrote:
>> On 10/14/14 10:02, Jakub Jelinek wrote:
>> >When hacking on range reassoc opt, I've noticed we can emit
>> >code with undefined behavior even when there wasn't one originally,
>> >in particular for:
>> >    (X - 43U) <= 3U || (X - 75U) <= 3U
>> >    and this loop can transform that into
>> >    ((X - 43U) & ~(75U - 43U)) <= 3U.  */
>> >we actually don't transform it to what the comment says, but
>> >    ((X - 43) & ~(75U - 43U)) <= 3U
>> >i.e. the initial subtraction can be performed in signed type,
>> >if in here X is e.g. INT_MIN or INT_MIN + 42, the subtraction
>> >at gimple level would be UB (not caught by -fsanitize=undefined,
>> >because that is handled much earlier).
>> >
>> >Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
>> >
>> >2014-10-14  Jakub Jelinek  <jakub@redhat.com>
>> >
>> >	* tree-ssa-reassoc.c (optimize_range_tests_diff): Perform
>> >	MINUS_EXPR in unsigned type to avoid undefined behavior.
>> Any chance this fixes:
>> 
>> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63302
>
> No.  For that I have right now:
> -  if (tree_log2 (lowxor) < 0)
> +  if (wi::popcount (wi::to_widest (lowxor)) != 1)
> in my tree, though supposedly:
>    if (wi::popcount (wi::zext (wi::to_widest (lowxor), TYPE_PRECISION (TREE_TYPE (lowxor)))) != 1)
> might be better, as without zext it will supposedly
> not say popcount is 1 for smaller precision signed minimum values.
> My wide-int-fu is limited, so if there is a better way to do this, I'm all
> ears.

Sorry for the very late reply, but just:

  if (wi::popcount (lowxor) != 1)

should do what you want.

Thanks,
Richard
diff mbox

Patch

--- gcc/tree-ssa-reassoc.c.jj	2014-10-13 17:54:33.000000000 +0200
+++ gcc/tree-ssa-reassoc.c	2014-10-13 17:58:07.312705218 +0200
@@ -2250,8 +2250,13 @@  optimize_range_tests_diff (enum tree_cod
   if (tree_log2 (tem1) < 0)
     return false;
 
+  type = unsigned_type_for (type);
+  tem1 = fold_convert (type, tem1);
+  tem2 = fold_convert (type, tem2);
+  lowi = fold_convert (type, lowi);
   mask = fold_build1 (BIT_NOT_EXPR, type, tem1);
-  tem1 = fold_binary (MINUS_EXPR, type, rangei->exp, lowi);
+  tem1 = fold_binary (MINUS_EXPR, type,
+		      fold_convert (type, rangei->exp), lowi);
   tem1 = fold_build2 (BIT_AND_EXPR, type, tem1, mask);
   lowj = build_int_cst (type, 0);
   if (update_range_test (rangei, rangej, 1, opcode, ops, tem1,