This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

RE: [PATCH] Reassociate X == CST1 || X == CST2 if popcount (CST2 - CST1) == 1 into ((X - CST1) & ~(CST2 - CST1)) == 0



> -----Original Message-----
> From: Jakub Jelinek [mailto:jakub@redhat.com]
> Sent: Thursday, October 10, 2013 7:13 PM
> To: Zhenqiang Chen
> Cc: gcc-patches@gcc.gnu.org
> Subject: Re: [PATCH] Reassociate X == CST1 || X == CST2 if popcount (CST2
-
> CST1) == 1 into ((X - CST1) & ~(CST2 - CST1)) == 0
> 
> On Mon, Aug 05, 2013 at 04:08:58PM +0800, Zhenqiang Chen wrote:
> > ChangeLog
> > 2013-08-05  Zhenqiang Chen  <zhenqiang.chen@arm.com>
> >
> > 	* tree-ssa-reassoc.c (optimize_range_tests): Reasociate
> > 	X == CST1 || X == CST2 if popcount (CST2 - CST1) == 1 into
> > 	((X - CST1) & ~(CST2 - CST1)) == 0.
> >
> > testsuite/ChangeLog
> > 2013-08-05  Zhenqiang Chen  <zhenqiang.chen@arm.com>
> >
> > 	* gcc.dg/reassoc1.c: New testcase.
> 
> +  /* Optimize X == CST1 || X == CST2
> +     if popcount (CST2 - CST1) == 1 into
> +     ((X - CST1) & ~(CST2 - CST1)) == 0.  */  if (!any_changes &&
> + (opcode == BIT_IOR_EXPR))
> 
> Wouldn't it be better to put it into the same loop that handles the other
> merges, rather than separate?  

As you had mentioned, the transition in this patch does not reduce
instructions. But the preexisting optimization does. So we prefer to do the
preexisting optimization first. E.g.

X == 10 || X == 12 || X == 26

The preexisting one will optimize X == 10 || X == 26. And the patch will
transfer X == 10 || X == 12.

So I prefer to separate them.

> Why the !any_changes guard?  Why opcode
> == BIT_IOR_EXPR guard?  Can't you optimize X != CST1 && X != CST2 if
> popcount (CST2 - CST1) == 1 similarly into ((X - CST1) & ~(CST2 - CST1))
!= 0?

They are not necessary. Patch is updated to check only the BRANCH_COST.
 
> Also, like the preexisting optimization has been generalized for ranges,
can't
> you generalize this one too?
> 
> I mean if you have say:
> (X - 43U) <= 3U || (X - 75U) <= 3U
> (originally e.g. X == 43 || X == 76 || X == 44 || X == 78 || X == 77 || X
== 46 ||
> X == 75 || X == 45) where popcount (75U - 43U) == 1, can't this be:
> ((X - 43U) & ~(75U - 43U)) <= 3U
> 
> For X in [LOWCST1, HIGHCST1] || X in [LOWCST2, HIGHCST2] the
> requirements for this optimization would be
> 1) LOWCST2 > HIGHCST1
> 2) HIGHCST1 - LOWCST1 == HIGHCST2 - LOWCST2
> 3) popcount (LOWCST2 - LOWCST1) == 1
> 
> 1) and 2) are the same requirements for the other optimization, while 3)
> would be specific to this and would be used only if popcount (LOWCST1 ^
> LOWCST2) != 1.
> Because of 1), LOWCST2 - LOWCST1 should be bigger than
> HIGHCST1 - LOWCST1 (i.e. the value we <= against in the end), thus IMHO it
> should work fine even after generalization.

Patch is updated.

 > +	    if (tree_log2 (tem) < 0)
> +	      continue;
> 
> This is I guess cheaper than what I was doing there:
>           gcc_checking_assert (!integer_zerop (lowxor));
>           tem = fold_binary (MINUS_EXPR, type, lowxor,
>                              build_int_cst (type, 1));
>           if (tem == NULL_TREE)
>             continue;
>           tem = fold_binary (BIT_AND_EXPR, type, lowxor, tem);
>           if (tem == NULL_TREE || !integer_zerop (tem))
>             continue;
> to check for popcount (x) == 1.  Can you replace it even in the
preexisting
> code?
> 	if (tree_log2 (lowxor) < 0)
> 	  continue;

Updated.

> Of course, if the two optimizations are merged into the same loop, then
> some of the continue will need to be replaced by just conditional code
inside
> of the loop, handling the two different optimizations.
> 
> Thanks for working on this.
> 
> 	Jakub

Bootstrap and no make check regression on X86-64 and ARM.

Thanks!
-Zhenqiang

Attachment: reassoc-new.patch
Description: Binary data


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]