edA-qa mort-ora-y via llvm-dev
2018-Mar-30 09:58 UTC
[llvm-dev] 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
John Regehr via llvm-dev
2018-Mar-30 16:57 UTC
[llvm-dev] Floor-integer-div and integer sign operations?
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? >
Stephen Canon via llvm-dev
2018-Mar-30 17:21 UTC
[llvm-dev] Floor-integer-div and integer sign operations?
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
Possibly Parallel Threads
- Floor-integer-div and integer sign operations?
- Re: [PATCH v2 nbdkit 4/6] common: Add a directory for common code shared by plugins and filters.
- NEAR non-leaf subqueries
- [PATCH v2 nbdkit 4/6] common: Add a directory for common code shared by plugins and filters.
- Re: [PATCH v2 nbdkit 4/6] common: Add a directory for common code shared by plugins and filters.