[Bug c++/98801] New: Request for a conditional move built-in function

[Bug c++/98801] New: Request for a conditional move built-in function

[jeffhurchalla at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98801

            Bug ID: 98801
           Summary: Request for a conditional move built-in function
           Product: gcc
           Version: 10.2.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: jeffhurchalla at gmail dot com
  Target Milestone: ---

There are a number of idiomatic ways to hint to gcc to generate a conditional
move, but there is no way that is documented/guaranteed.  In practice, they do
not always result in a conditional move.  I would like to request a builtin
function that generates a conditional move.

The current situation:
Perhaps the most common hint is to write
a = (cond) ? x : y
Another way is to bit-hack, and hope the compiler transforms it to cmov.  E.g.
a = ((-cond) & x) | ((cond-1) & y)
There are more ways still, see
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=93165 .  None can be relied on for
the purpose.

Certainly a conditional move can be accomplished via inline asm, but this is
non-portable across ISAs, it's bug-prone, and it seems to hinder the optimizer.

The existing function __builtin_expect_with_probability is interesting: in
theory it seems like it might allow a user to get conditional moves via a
probability of 0.5.  I'm unsure if this works as desired in practice; its
documentation does not mention anything about conditional moves or
unpredictable branches.  (Also note that a probability of 0.5 does not
necessarily mean a condition is unpredictable - e.g. a condition could
alternate between true and false each time it's executed.)
Perhaps also interesting is clang's __builtin_unpredictable, which is
documented as a way to indicate to the compiler that a branch condition is
unpredictable.  I'm unsure here too if this affects conditional moves; their
docs don't mention it.

Personally, I'd like conditional moves for performance in situations where I
know a branch is completely unpredictable.  However, cmovs appear to also be
useful for security, to avoid timing attacks.

[Bug c++/98801] Request for a conditional move built-in function

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98801

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
I don't think we need a builtin. Because we could just improve the code
generation instead.

[Bug c++/98801] Request for a conditional move built-in function

[jeffhurchalla at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98801

--- Comment #2 from Jeff Hurchalla <jeffhurchalla at gmail dot com> ---
Relying on improved codegen, I believe we have the current problem that there
are times that a programmer knows a conditional is unpredictable, yet it would
be impossible for a compiler to know.  There's no documented way for a
programmer to inform the compiler.  There might also be cases (beyond my realm)
for security where execution time can't be allowed to vary due to a
mispredicted branch - again with no way to tell the compiler to use a
conditional move, or branchless code.  Barring a built-in function for
conditional move, I'd alternatively request a documented canonical form to use
in C that provides conditional moves when the ISA supports it (hypothetically,
the earlier ugly bit-hack example could work for this due to its clear intent,
whereas the ternary operator example could not due to unclear intent).  Without
a canonical form, could a compiler anticipate the near infinite number of ways
a programmer might express it in C, even when the intent is clear?
I'd certainly prefer a conditional move built-in function, if it's a
possibility.  It's clear and simple from a user's point of view.  The
translation to a machine instruction also seems pretty direct and limited in
scope.  Most ISAs support the instruction - ARM aarch64/A64/A32, x86_64, PPC. 
The one I know of that doesn't automatically is RISC-V, which needs the bit
manipulation extension.

[Bug c++/98801] Request for a conditional move built-in function

[jeffhurchalla at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98801

--- Comment #3 from Jeff Hurchalla <jeffhurchalla at gmail dot com> ---
My last comment went long:
I'd kindly request some way to inform gcc to generate a conditional move,
regardless of method.

[Bug middle-end/98801] Request for a conditional move built-in function

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98801

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|c++                         |middle-end
           Severity|normal                      |enhancement
   Last reconfirmed|                            |2021-01-25
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
Slight complication arises because people will want to have cmoves with a
memory destination.  So possibly

void __builtin_cmov (T *dest, bool, T, T, void *);

preferably usable in a type-generic way.  The void * is at least internally
required to carry type-based alias info of the destination.

That won't solve the eventual request to have cmov _from_ memory ... (if we
leave all of the memory combining to RTL people will again complain that
it's subject to compilers discretion).

[Bug middle-end/98801] Request for a conditional move built-in function

[peter at cordes dot ca]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98801

Peter Cordes <peter at cordes dot ca> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |peter at cordes dot ca

--- Comment #5 from Peter Cordes <peter at cordes dot ca> ---
(In reply to Richard Biener from comment #4)
> Slight complication arises because people will want to have cmoves with a
> memory destination.

Do we even want to provide this?  Most ISAs can't branchlessly conditionally
store, except via an RMW (which wouldn't be thread-safe for the no-store case
if not atomic) or something really clunky.  (Like x86  rep stos  with count=0
or 1.)

ARM predicated instructions allow branchless load or store that doesn't disturb
the memory operand (and won't even fault on a bad address).

I guess another option to emulate it could be to make a dummy local and cmov to
select a store address = dummy : real.  But that's something users can build in
the source using a non-memory conditional-select builtin that exposes the much
more widely available ALU conditional-select functionality like x86 CMOV,
AArch64 CSEL, MIPS MVN, etc.


> That won't solve the eventual request to have cmov _from_ memory ... (if we
> leave all of the memory combining to RTL people will again complain that
> it's subject to compilers discretion).

It might be sufficient for most use-cases like defending against timing
side-channels to not really try to allow conditional loads (from maybe-invalid
pointers).

----

I'm not sure if the motivation for this includes trying to make code without
data-dependent branching, to defend against timing side-channels.

But if we do provide something like this, people are going to want to use it
that way.  That's one case where best-effort behaviour at the mercy of the
optimizer for a ternary (or having to manually check the asm) is not great. 
Stack Overflow has gotten a few Q&As from people looking for guaranteed CMOV
for reasons like that.

So I think we should be wary of exposing functionality that most ISAs don't
have.  OTOH, failing to provide a way to take advantage of functionality that
some ISAs *do* have is not great, e.g. ISO C failing to provide popcnt and
bit-scan (clz / ctz) has been a problem for C for a long time.

But for something like __builtin_clz, emulating on machines that don't have
hardware support still works.  If we're trying to support a guarantee of no
data-dependent branching, that limits the emulation possibilities or makes them
clunkier.  Especially if we want to support ARM's ability to not fault / not
access memory if the condition is false.

The ALU-select part can be emulated with AND/OR, so that's something we can
provide on any target.

Folding memory operands into a predicated load on ARM could actually introduce
data-dependent cache access, vs. an unconditional load and a predicated reg-reg
MOV.  So this becomes somewhat thorny, and some design work to figure out what
documented guarantees to provide will be necessary.  Performance use-cases
would certainly rather just have a conditional load in one instruction.

[Bug middle-end/98801] Request for a conditional move built-in function

[jeffhurchalla at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98801

--- Comment #6 from Jeff Hurchalla <jeffhurchalla at gmail dot com> ---
I'd be quite satisfied with the simpler option that Peter Cordes wrote:

> a non-memory conditional-select builtin that exposes the much more widely
> available ALU conditional-select functionality like x86 CMOV, AArch64 CSEL,
> MIPS MVN, etc.
...
> The ALU-select part can be emulated with AND/OR, so that's something we can
> provide on any target.

A predicated reg-reg move like this is appealing to me for my needs.  It seems
common in ISAs and emulatable when not present.

I perceive that the security use-case for cmovs could be more important than my
motivation for them (my motivation: performance in critical loops containing
unpredictable conditionals).  I suspect the guarantees needed for security
would satisfy me despite having a different motivation.

[Bug middle-end/98801] Request for a conditional move built-in function

[jeffhurchalla at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98801

--- Comment #7 from Jeff Hurchalla <jeffhurchalla at gmail dot com> ---
It might be good to ignore my suggestion to satisfy security needs - if for no
other reason than I can't speak well to those needs.  I get the sense crypto's
need to avoid optimizations can be complicated, for example
https://lists.llvm.org/pipermail/llvm-dev/2019-September/135079.html

( Interestingly, the writer mentioned there exists a non-upstreamed patch for
clang/llvm that has an intrinsic called __builtin_ct_choose, which provides a
guaranteed constant time conditional select.  See
https://www.computer.org/csdl/pds/api/csdl/proceedings/download-article/12OmNqJZgIG/pdf
)

So I'd limit my request to a conditional move builtin, just motivated by desire
for performance in situations where a predicate is unpredictable.

FYI, clang's __built_unpredictable seems suitable at first, but it's not as
good as it seems.  It's a hint that doesn't always survive optimization passes,
which puts it in the same category as the ternary operator idiom.  Any change
to compiler flags or version means rechecking generated assembly, which is
awkward even the first time.

[Bug middle-end/98801] Request for a conditional move built-in function

[richard.yao at alumni dot stonybrook.edu]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98801

Richard Yao <richard.yao at alumni dot stonybrook.edu> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |richard.yao at alumni dot stonybro
                   |                            |ok.edu

--- Comment #8 from Richard Yao <richard.yao at alumni dot stonybrook.edu> ---
I just filed #110007 to ask for __builtin_unpredictable(). Something like
__builtin_unpredictable(condition) ? a : b should be equivalent to a
__builtin_cmov(). __builtin_unpredictable() is already implemented in Clang
(although it does not yet pass it to the backend), so adopting it would be
preferable to implementing an entirely new builtin.