How to make gcc optimize function call with constant parameters at compile time?

Question

I am trying to parse user input and execute some tasks according to the commands given by user. As, in C, switch doesn't work with strings I have decided to use switch of hash values of strings to compare which command to execute.

Now, as maintaining the list of all hashes of all available commands in something like this

#define EXIT 6385204799
...

is really tedious task, I was wandering if there exist way to convince gcc to evaluate the hash function with constant parameter on compile time so I could use something like this

switch(hash(command)){
    case hash("exit"): exit();
    // I know, case labels must be compile time constants
    // but that should be fulfilled in my case
}

I know I could use for example metaprogramming but I am interested more in the solution with gcc.

Is it even possible?

#include <stdio.h>


unsigned long hash(const char *str)
{
        unsigned long hash = 5381;
        int c;

        while ((c = *str++))
                hash = ((hash << 5) + hash) + c;
        return hash;
}

int main( int argc, char **argv ) {
        char *command=NULL;
        size_t size=0;
        printf("Enter string:");
        getline(&command, &size, stdin);
        printf("%ld",hash("exit")); // I want this to evaluate in compile time
        printf("%ld",hash(command)); // and this not
        return 0;
}

Answer 1

Easiest way: If 4 characters are enough you could use literals like 'exit' / 'tixe' (depending on endianness) instead of a hash function. Note the single quotes.

Any way to make it a constant expression will be compiler dependent anyhow, so you might be able to use gcc's statement expression extension that allows macros to return a value. It looks like ({int hash=5381; /*do stuff*/ hash;}) ... but you may need to #pragma GCC push_options #pragma GCC optimize ("unroll-loops") before your case statements and #pragma GCC pop_options after.

One alternative is to map strings to enums and use a binary search of the alphabetized strings instead of a hash. You can use an X-macro to simplify adding and removing commands. In this example I used it for function prototypes and case statements as well (not necessary, just easier to work with for a simple example)

#include <string.h>
#define MYXMACRO(OP) \
  OP(bar) \
  OP(exit) \
  OP(foo)

#define AS_ENUM(x,...) MYENUM_##x,
enum { MYXMACRO(AS_ENUM) MYENUMCOUNT };
#undef AS_ENUM

#define AS_STRING(x,...) #x,
const char* mystrings[]= { MYXMACRO(AS_STRING) };
#undef AS_STRING

#define AS_PROTOTYPES(x,...) void do_##x(void);
MYXMACRO(AS_PROTOTYPES)
void do_default(void);
#undef AS_PROTOTYPES

int mybsearch(const char *command){
    size_t bot=0, top=MYENUMCOUNT, i=((bot+top)>>1)&(~1);
    int cmp;
    for (; bot<=top && i<=MYENUMCOUNT; i=((bot+top)>>1)&(~1)){
        cmp=strcmp(command,mystrings[i]);
        if (! cmp) return i; //match found
        else if (cmp>0) bot=i+1;
        else top=i-1;
    }
    return -1;
}

void do_command(const char * command){
#define AS_CASE(x,...)  case MYENUM_##x : do_##x(__VA_ARGS__);break;
  switch(mybsearch(command)){
    MYXMACRO(AS_CASE)
    default: do_default();
  }
}
#undef MYXMACRO

Answer 2

Is it even possible?

GCC cannot (for C - it can for C++, see below), but Clang/LLVM (version 3.9.1) can. Use the -O2 switch to enable level 2 optimisations (or higher).

Proof. See the disassembly - there is no call to a hash function, no loop; the compiler has calculated the hash at compile time. This reduced form of your test case:

#include <stdio.h>

static unsigned long hash(const char *str)
{
        unsigned long hash = 5381;
        int c;

        while ((c = *str++))
                hash = ((hash << 5) + hash) + c;
        return hash;
}

int main( int argc, char **argv ) {
        size_t size=0;
        printf("%ld",hash("exit")); // I want this to evaluate in compile time
        return 0;
}

Compiles to:

main:                                   # @main
# BB#0:
        push    rax
        #DEBUG_VALUE: main:argc <- %EDI
        #DEBUG_VALUE: main:argv <- %RSI
        #DEBUG_VALUE: main:size <- 0
        movabs  rsi, 6385204799
        mov     edi, .L.str
        xor     eax, eax
        call    printf
        xor     eax, eax
        pop     rcx
        ret

.L.str:
        .asciz  "%ld"

The line movabs rsi, 6385204799 directly loads the pre-calculated hash value into the rsi register.

However, the value will not be considered a compile-time constant for purposes of use in a case label in a switch statement. You need to use if ... else for comparison rather than switch.

In case you are interested, with modern C++ you can achieve this type of optimisation using GCC as well as Clang/LLVM, and you can even use a switch statement:

#include <cstdio>

static constexpr unsigned long hash(const char *str)
{
        unsigned long hash = 5381;
        int c = *str;

        while ((c = *str++))
                hash = ((hash << 5) + hash) + c;
        return hash;
}

int main( int argc, char **argv ) {
        size_t size=0;
        printf("%ld",hash("exit")); // I want this to evaluate in compile time

        switch((unsigned long)5 /* i.e. some number */) {
        case hash("exit"):
            // etc
            ;
        }

        return 0;
}

This is C++14 code, you will need to use -std=c++14 to compile it (or use GCC 6+ for which this is the default). (Of course, the code is not idiomatic C++ - it is intended to be as close as possible to the previous example).

Answer 3

You can build a C program which will rely on your hash function and which will generate your header definition file based on a configuration file.

config file: EXIT "exit" -> process config file -> header file (commands.h): #define EXIT 6385204799

Then you can include commands.h in your program in use the enum in your switch statement.

switch(hash(command)){
    case EXIT: exit();