How to implement floor, ceil and round in LLVM bitcode?

Question

I'm writing the maths functions for a small LLVM-based programming language, and I'm currently stumped by how to implement the common rounding functions floor, ceil and round (to even). Firstly because I haven't found any algorithm descriptions for these functions, secondly because I'm not familiar with what capabilities LLVM has w. rounding.

Being able to round negative numbers correctly is a must, rounding to a specific precision is not. Rounding to an integral value will do. Simply being pointed to any existing implementations that can be used from LLVM bitcode will also work.

Answer 1

You're going to want to start with the LLVM language reference manual.

You might start by implementing trunc( ) like something along these lines (warning, don't actually use this; it's intended as an example, and isn't correct. See discussion below):

define float @trunc(float %x) {
    %rounded = fptosi float %x to i32
    %asFloat = sitofp i32 %rounded to float
    ret float %asFloat
}

The fptosi ... to ... instruction is documented as rounding a floating-point value to an integer value according to the round-to-zero rounding mode. The sitofp ... to ... instruction converts that value back into a floating-point value to return.

However, there is a problem with this implementation; reading the language reference that I linked to, "the behavior of fptosi ... to ... is undefined if the result of rounding to the nearest integer cannot fit in the destination type."

This is pretty easy to work around, though, because all sufficiently large floating-point numbers are already integers, and don't need to be rounded; if the absolute value of x is greater than or equal to 2^23, you can just return x itself.

(This is all for single precision; for double, you will likely want to use i64, and you will need to use a threshold of 2^52)

For the other operations, like floor and round, you can begin with trunc, then check the residual x - trunc(x) and adjust the result accordingly.

Alternatively, you could call out to your host platform's C library, which already includes these functions. This is an approach taken by many programming languages.

Answer 2

If you look on Google Code Search, there are a few results. The linked example assumes IEEE floating point numbers. Ordinarily, compilers for common PCs just compile floor to floating point instructions. For example the original 387 arithmetic processor has the instruction FPREM which more or less does a piece of what you need for floor.

Answer 3

I have implemented floor for float vectors the following way: 'truncate' the value x, then compare x and trunc(x). Where trunc(x)>x, subtract 1, because floor(x) must be always at most x. I have coded this in Haskell. I do not know, whether this helps you. See floorLogical in http://code.haskell.org/~thielema/llvm-extra/src/LLVM/Extra/Vector.hs

Round to even is generally expensive and not of much use. I simply use floor(x+0.5). In SSE4.1 there are also roundss, roundps et.al.