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

[Marc Glisse <marc.glisse@inria.fr>]

On Thu, 28 May 2015, Marek Polacek wrote:

> This PR points out that we weren't able to optimize 1 << x == 2 to just
> x == 1.

Side note: if we are looking for extra patterns to simplify, llvm has an 
almost unlimited supply. Here are a few we don't seem to have (there are 
more where those came from), of course several need constraining / 
generalizing, it is just a list of hints I wrote for myself.

(A|B) & ~(A&B) -> A^B
(A | B) & ((~A) ^ B) -> (A & B)
(A & (~B)) | (A ^ B) -> (A ^ B)
((B | C) & A) | B -> B | (A & C)
A | ( A ^ B) -> A |  B
A | (~A ^ B) -> A | ~B
(A ^ B) & ((B ^ C) ^ A) -> (A ^ B) & ~C
(A ^ B) | ((B ^ C) ^ A) -> (A ^ B) | C
(A & B) | (A ^ B) -> (A | B)
A | ~(A ^ B) -> A | ~B
(A & B) | ((~A) ^ B) -> (~A ^ B)
~(~X & Y) -> (X | ~Y)
~(~X >>s Y) -> (X >>s Y)
(A & B)^(A | B) -> A ^ B
(A | ~B) ^ (~A | B) -> A ^ B
(A & ~B) ^ (~A & B) -> A ^ B
(A ^ C)^(A | B) -> ((~A) & B) ^ C
(A & B) ^ (A ^ B) -> (A | B)
(A & ~B) ^ (~A) -> ~(A & B)
(A&B)+(A^B) -> A|B
(A&B)+(A|B) -> A+B
(A|B)-(A^B) -> A&B
((X | Y) - X) -> (~X & Y)
fmax(x,NaN) -> x
fmax(a,fmax(a,b)) -> fmax(a,b)
(X+2) >u X -> x <u 256-2
(1 << X) <  30 -> X <= 4
((X & ~7) == 0) -> X < 8
2 * X < 5 -> X <= 2
((1 << x)&8) == 0 -> x != 3
((1 << x)&7) == 0 -> x > 2
Y - Z < X - Z -> Y < X
3 * X == 3 * Y -> X == Y
A >> 3 == B >> 3 -> (A ^ B) < 8
(float)int <= 4.4 -> int <= 4
x unle x -> x ord x


> +/* (CST1 << A) == CST2 -> A == log2 (CST2 / CST1)
> +   (CST1 << A) != CST2 -> A != log2 (CST2 / CST1)
> +   if CST2 is a multiple of CST1.  */
> +(for cmp (ne eq)
> + (simplify
> +  (cmp (lshift@3 INTEGER_CST@0 @1) INTEGER_CST@2)
> +  (if ((TREE_CODE (@3) != SSA_NAME || has_single_use (@3))
> +       && wi::multiple_of_p (@2, @0, TYPE_SIGN (type)))

Doesn't "type" refer to the result of the EQ_EXPR here?


On Thu, 28 May 2015, Jakub Jelinek wrote:

> 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?

ctz(CST2)-ctz(CST1) should provide a single candidate without looping. 
ctz(CST1) is also relevant when CST2==0.

-- 
Marc Glisse