How to make GCC evaluate functions at compile time?

Question

I am thinking about the following problem: I want to program a microcontroller (let's say an AVR mega type) with a program that uses some sort of look-up tables.

The first attempt would be to locate the table in a separate file and create it using any other scripting language/program/.... In this case there is quite some effort in creating the necessary source files for C.

My thought was now to use the preprocessor and compiler to handle things. I tried to implement this with a table of sine values (just as an example):

#include <avr/io.h>
#include <math.h>

#define S1(i,n) ((uint8_t) sin(M_PI*(i)/n*255))
#define S4(i,n) S1(i,n), S1(i+1,n), S1(i+2,n), S1(i+3,n)

uint8_t lut[] = {S4(0,4)};

void main()
{
    uint8_t val, i;

    for(i=0; i<4; i++)
    {
        val = lut[i];
    }
}

If I compile this code I get warnings about the sin function. Further in the assembly there is nothing in the section .data. If I just remove the sin in the third line I get the data in the assembly. Clearly all information are available at compile time.

Can you tell me if there is a way to achieve what I intent: The compiler calculates as many values as offline possible? Or is the best way to go using an external script/program/... to calculate the table entries and add these to a separate file that will just be #included?

Impassion

"quite some effort" - with a good scripting language? certainly less, than attacking the problem with C.... – Boogie

C++11 (improved with C++14)has constexpr as a hint to the compiler to execute a function at compile-time. – Standfast

@johannes: constexpr is no advantage. It merely allows an expression being evaluated at compile time (and even forcing the compiler to to it, e.g. by assigning to an enumeration doesn't prevent it from re-evaluating at runtime at a different location in the same source file!). It does not enforce or hint anything. That said, my GCC optimizes the code snippet in the OP just fine into a compiletime-evaluated lookup table (without any particular special dance). – Bautzen

As I commented below the warning about sin will become an error if you use -fno-builtin which is because gcc is currently treating most math functions as constant expressions if it uses the builtin version. – Twin

Your sin will only return -1/255,0 or 1. Maybe you will use ` ((uint8_t) (sin(M_PI*(i)/n)+1)/2*255)` – Chesnut

Answer 1

The general problem here is that sin call makes this initialization de facto illegal, according to rules of C language, as it's not constant expression per se and you're initializing array of static storage duration, which requires that. This also explains why your array is not in .data section.

C11 (N1570) §6.6/2,3 Constant expressions (emphasis mine)

A constant expression can be evaluated during translation rather than runtime, and accordingly may be used in any place that a constant may be.

Constant expressions shall not contain assignment, increment, decrement, function-call, or comma operators, except when they are contained within a subexpression that is not evaluated.115)

However as by @ShafikYaghmour's comment GCC will replace sin function call with its built-in counterpart (unless -fno-builtin option is present), that is likely to be treated as constant expression. According to 6.57 Other Built-in Functions Provided by GCC:

GCC includes built-in versions of many of the functions in the standard C library. The versions prefixed with __builtin_ are always treated as having the same meaning as the C library function even if you specify the -fno-builtin option.

Vernita

This likely works because currently gcc treats math builtins as it they were constant expressions, using-fno-builtin makes similar code fail using gcc but it only generates a warning otherwise. – Twin

@ShafikYaghmour: Why is then there no data in the disassembly. I am completely unsure, what will happen if I try to access the data... – Impassion

@ChristianWolf: You can force it by __builtin_sin, but I agree with Shafik, that it should likely works. Maybe you are using some avr-gcc port, that does not support it? – Vernita

@GrzegorzSzpetkowski: If I try this (replacing sin with __builtin_sin) the data gets registered in the .bss section and zeroed at startup -- I verified by enlarging the array and looking for the array size. – Impassion

Ahh, I got it. I forgot a pair of paramtesis. Thus I evaluated always a multiple of pi (which is in fact 0 and get's optimized out). On correcting that it works correctly. – Impassion

Answer 2

What you are trying is not part of the C language. In situations like this, I have written code following this pattern:

#if GENERATE_SOURCECODE
int main (void)
{
    ... Code that uses printf to write C code to stdout
}
#else
    // Source code generated by the code above
    ... Here I paste in what the code above generated

    // The rest of the program
#endif

Every time you need to change it, you run the code with GENERATE_SOURCECODE defined, and paste in the output. Works well if your code is self contained and the generated output only ever changes if the code generating it changes.

Lacerate

This is not optimal in the sense that I am cross compiling. Thus it mightz or might not be ok. I guess the effort is quit higer than mantaining two different files as all the header files have to be exchanged and therefore inside the #if blocks. Looks nasty to me, sorry. – Impassion

Answer 3

First of all, it should go without saying that you should evaluate (probably by experiment) whether this is worth doing. Your lookup table is going to increase your data size and programmer effort, but may or may not provide a runtime speed increase that you need.

If you still want to do it, I don't think the C preprocessor can do it straightforwardly, because it has no facilities for iteration or recursion.

The most robust way to go about this would be to write a program in C or some other language to print out C source for the table, and then include that file in your program using the preprocessor. If you are using a tool like make, you can create a rule to generate the table file and have your .c file depend on that file.

On the other hand, if you are sure you are never going to change this table, you could write a program to generate it once and just paste it in.

Yoghurt