llvm dev - Mar 2018 - Floor-integer-div and integer sign operations?

I'm looking for ways to do some basic operations without using branches.

The key operation I want is a floored/round-to-negative-infinity integer
division (as opposed to the default round-to-zero).

    7 floordiv 5 = 1
    -3 floordiv 5 = -1
    -6 floordiv 5 = -2

As I guess that doesn't exist, the operation can be constructed as:

   (a/b) + (a>>31)

Assuming a is 32 bits. I can probably check the bit count, but perhaps
there's an op that does this already.


I'm also looking for a `sign(a) => (-1,0,1)` operation. Is there some
easy way to do this without branches? That is, have I overlooked from IR
function?

-- 
edA-qa mort-ora-y  
	http://mortoray.com/

Creator of the Leaf language
	http://leaflang.org/

Streaming algorithms, AI, and design on Twitch
	https://www.twitch.tv/mortoray

Twitter
	edaqa

Hacker's Delight or this web page are probably the best references for 
tricks like this:

https://graphics.stanford.edu/~seander/bithacks.html#CopyIntegerSign

John


On 03/30/2018 03:58 AM, edA-qa mort-ora-y via llvm-dev
wrote:
> I'm looking for ways to do some basic operations without using
branches.
> 
> The key operation I want is a floored/round-to-negative-infinity integer
> division (as opposed to the default round-to-zero).
> 
>      7 floordiv 5 = 1
>      -3 floordiv 5 = -1
>      -6 floordiv 5 = -2
> 
> As I guess that doesn't exist, the operation can be constructed as:
> 
>     (a/b) + (a>>31)
> 
> Assuming a is 32 bits. I can probably check the bit count, but perhaps
> there's an op that does this already.
> 
> 
> I'm also looking for a `sign(a) => (-1,0,1)` operation. Is there
some
> easy way to do this without branches? That is, have I overlooked from IR
> function?
>

I should note that your flooring division is incorrect for exact cases, e.g. a =
–2, b = 1 should produce –2 but you’ll get –3. Assuming you know b > 0 you
want something more like:

mask = a >> 31
(a – (b–1 & mask)) / b

and you may or may not need to handle the possibility of the subtract
overflowing, depending on how robust you need to be.

– Steve
> On Mar 30, 2018, at 12:57 PM, John Regehr via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> Hacker's Delight or this web page are probably the best references for
tricks like this:
> 
> https://graphics.stanford.edu/~seander/bithacks.html#CopyIntegerSign
> 
> John
> 
> 
> On 03/30/2018 03:58 AM, edA-qa mort-ora-y via llvm-dev wrote:
>> I'm looking for ways to do some basic operations without using
branches.
>> The key operation I want is a floored/round-to-negative-infinity
integer
>> division (as opposed to the default round-to-zero).
>>     7 floordiv 5 = 1
>>     -3 floordiv 5 = -1
>>     -6 floordiv 5 = -2
>> As I guess that doesn't exist, the operation can be constructed as:
>>    (a/b) + (a>>31)
>> Assuming a is 32 bits. I can probably check the bit count, but perhaps
>> there's an op that does this already.
>> I'm also looking for a `sign(a) => (-1,0,1)` operation. Is there
some
>> easy way to do this without branches? That is, have I overlooked from
IR
>> function?
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev