Re: [PATCH] Optimize (CST1 << A) == CST2 (PR tree-optimization/66299)

[Jakub Jelinek <jakub@redhat.com>]

On Thu, May 28, 2015 at 02:15:45PM +0200, Marek Polacek wrote:
> This PR points out that we weren't able to optimize 1 << x == 2 to just
> x == 1.  This is my attempt to fix that: if we see (CST1 << A) == CST2
> and CST2 is a multiple of CST1, use log2 to get rid of the shift, but
> only if the result of the shift is a natural number (including zero).

Is CST2 a multiple of CST1 the best test though?
I mean say in
(0x8001U << x) == 0x20000U
0x20000U isn't a multiple of 0x8001U, yet there is only one
valid value of x for which it holds (17), so we could very well
optimize that to x == 17.
If popcount of the CST1 is 1, then multiple_of_p is supposedly sufficient
(have you checked if CST1 is negative that it still works?), for others
supposedly we could have a helper function that would just try
in a loop all shift counts from 0 to precision - 1, and note when
(CST1 << b) == CST2 - if for no b, then it should fold regardless of
has_single_use to false or true, if for exactly one shift count, then
use a comparison against that shift count, otherwise give up?
Supposedly (CST1 >> A) == CST2 can be handled similarly.

> If CST2 is not a multiple of CST1, then the whole expression can be
> discarded, but I'd like to do that as a follow-up.
> (It would help if our current match.pd grammar allowed us to use "else",
> any plans on doing that?)

	Jakub