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

Question

Good day overflowers.

I'm writing the math functions for a small LLVM-based programming language, and I'm currenly stumped by how to implement the common rounding fuctions 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 precicion 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

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 2

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.