3 ms·
The C specification requires that (x<32) is 0 or 1, but that doesn't mean it is necessarily possible to do it branch-free on any particular computer.
by torrent-of-ions 9y ago
The C specification requires that (x<32) is 0 or 1, but that doesn't mean it is necessarily possible to do it branch-free on any particular computer.
- vidarh 9y agoMaybe there are cpu's where it isn't possible, but I don't think there are any non-joke systems where it isn't possible. There are just too many ways of doing it. E.g. on most architectures there'll be a straightforward way of doing it using an add/sub operator and taking advantage of overflow/underflow to set a carry flag, and then another operator or three to get the least significant bit set to the carry flag. Or you can do a straight lookup into a table on any architecture that supports a load from memory and an add, though it'd of course be hugely wasteful. On any architecture that also supports a right shift / integer division plus AND you could make that use less memory by shifting, masking, lookup up (any set bit =>0, no set bits => 1), and then and'ing the results together with an initial 1. And many, many more. I have a hard time picturing what an instruction set that would make it impossible to do that without branches would even look like. Of course that doesn't guarantee it will be the most efficient choice, and of course also doesn't guarantee that a compiler will know how to do it.
- pm215 9y agoIn this particular instance, 64-bit ARM (A64) has a conditional-set instruction, so "int cmp(int x) { return x < 32; }" compiles straightforwardly to "cmp w0, #0x1f; cset w0, le; ret". For 32-bit ARM you can use the conditional-execution you get on almost all instructions, so gcc emits "cmp r0, #31; movgt r0, #0; movle r0, #1; bx lr".