Builtin for consulting value analysis (better ffs() code gen)

[Andrew Cooper <andrew.cooper3@citrix.com>]

Hello,

I've come across an issue that I would have thought there would be a
builtin for, but perhaps that's just wishful thinking.  I'd like to be
able to write something like this:

    if (__builtin_expr_is_true(x > 0))
        ... // one thing
    else
        ... // something else

This stems from trying to clean up the mess of bit operation helpers in Xen.

On x86, __builtin_ffs() doesn't have great code generation.  This is a
consequence of the BSF instruction having miserable semantics, and the
builtin emits code with a branch or cmov to compensate for undefined
case of passing 0 in.

On x86_64 at least, Intel and AMD have made enough guarantees in writing
to allow a condition-less form:

    mov $-1, %dst
    bsf %src, %dst
    add $1, %dst

which is good, but not great.  It is common to have an __ffs() variant
which states that a src of 0 is undefined, and while this makes a
reasonable improvement to the code generation within loops, it's still
not great to rely on the programmer to get this right.

A common pattern to find is something like:

    while (x) {
        int b = ffs(x);
        ... // do something with x and b

where range analysis can know that x is nonzero.  Indeed, the builtin
manages to spot this, and emits a condition-less form too.

However, doing this for a local implementation of ffs() doesn't work.  With:

unsigned int my_ffs(unsigned int x)
{
    int res;

    if (x) {
        asm ("bsf ..." : "=r" (res) : "rm" (x));
    } else {
        res = -1;
        asm ("bsf ..." : "+r" (res) : "rm" (x));
    }

    return res + 1;
}

the while() example above really does get generated with ideal form. 
However, in general code where the value of x is unknown, the entire
if/else chain is emitted, which is strictly worse than just emitting the
else case which is the safe catch-all.

I suppose that what I'm looking for is something a little like
__builtin_constant_p() which can either be used in a straight if(), or
in a __builtin_choose_expr().

Anyway - is there a way of doing this that I've managed to overlook?

~Andrew