Re: Transform (x >> cst) != 0 to x >= (1 << cst) and (x >> cst) == 0 to x < (1 << cst)

[Marc Glisse]

On Tue, 3 Oct 2017, Jakub Jelinek wrote:

On Tue, Oct 03, 2017 at 12:54:39PM -0700, Prathamesh Kulkarni wrote:
Hi,
This follow-up patch implements the patterns mentioned in $subject.
Bootstrap+test in progress on x86_64-unknown-linux-gnu and aarch64-linux-gnu.
OK to commit if passes ?
Thanks,
Prathamesh

2017-10-03  Prathamesh Kulkarni  <prathamesh.kulka...@linaro.org>

        * match.pd ((X >> CST) == 0 -> X < (1 << CST)): New pattern.
        ((X >> CST) != 0 -> X >= (1 << CST)): Likewise.

build_int_cstu doesn't work for vectors, you want build_one_cst. I never 
know if we should check single_use or not :-(

testsuite/
        * gcc.dg/tree-ssa/cmpdiv.c: Add test-cases f3 and f4.

Why this way and not the other way around?

For high level gimple optimizations, X < CST is more convenient (and 
smaller, just one insn) than (X >> CST) == 0.

E.g. i?86/x86_64 and various other targets have shift instructions which
set condition codes, so (X >> 51) == 0 is certainly smaller
smaller and I believe cheaper than the latter.
Try:
void foo (void);

void
bar (unsigned long long x)
{
 if ((x >> 51) == 0)
   foo ();
}

void
baz (unsigned long long x)
{
 if (x < (1LL << 51))
   foo ();
}
with -Os on x86_64, the first function is 4 insns, 12 bytes,
the second one 5 insns, 21 bytes.

I wonder if this kind of instruction selection stuff shouldn't be
done in target.pd instead, with input from the target.

At a late stage, maybe during an RTL pass or expansion (or just before 
expansion) it would indeed be good to generate a shift for such 
comparisons, on targets where that sets a cc. The lack of this 
transformation could be considered a blocker for the other one, to avoid 
regressing on bar.

--
Marc Glisse