02 June, 2011

On the transparent conversion of Indirect (mutual) recursion to "no nested calls"

In a previous post I've shown how to implement functions in recursion-like style without nested call (real recursion). Implementing algorithms this way helps to save some memory (stack).
It made me wonder if we can convert/optimize mutual recursion in a way transparent to users. As basic example I chose following code:
int even(int n)
{
    if (n == 0)
        return 1;
    else
        return odd(abs(n) - 1);
}

int odd(int n)
{
    if (n == 0)
        return 0;
    else
        return even(abs(n) - 1);
}

Like in previous example I decided to use context manipulations plus function wrappers for even() and odd().
Unfortunately there is no way to wrap functions (symbols) referenced in same file as the symbol (check this). It gives some limitations: in our case even() and odd() should be separated into different source files. In common case our approach will not work with normal recursion (a()->a()) without source modification (not just recompiling with wrapper library as I wanted). Note, that if even() and odd() are in the shared library (most likely), then you can use LD_PRELOAD to wrap these functions and it will work just fine.

even.c:
int odd(int);

int even(int n)
{
    if (n == 0)
        return 1;
    else
        return odd(abs(n) - 1);
}

odd.c:
int even(int);

int odd(int n)
{
    if (n == 0)
        return 0;
    else
        return even(abs(n) - 1);
}


wrapped.c:
int __real_even(int n);
int __real_odd(int n);

volatile int even_odd_arg;
int (*volatile fp)(int);
volatile int even_odd_res;


void dispatch(ucontext_t *_return_context) {
    static ucontext_t *return_context = 0;
    if (return_context == NULL) {
        return_context = _return_context;
    }
    even_odd_res = fp(even_odd_arg);

    setcontext(return_context);
}

ucontext_t* get_dispatcher_context(ucontext_t* return_context)
{
    static ucontext_t dispatcher_context;
    static char iterator_stack[SIGSTKSZ];
    static initialized = 0;

    if (initialized)
        return &dispatcher_context;

    dispatcher_context.uc_stack.ss_sp   = iterator_stack;
    dispatcher_context.uc_stack.ss_size = sizeof(iterator_stack);
    getcontext(&dispatcher_context);

    makecontext(&dispatcher_context, (void (*)(void)) dispatch,
                1, return_context);

    return &dispatcher_context;
}

int __wrap_even(int n) {
    ucontext_t this_context;
    even_odd_arg = n;
    fp = __real_even;
    swapcontext(&this_context, get_dispatcher_context(&this_context));

    return even_odd_res;
}


int __wrap_odd(int n) {
    ucontext_t this_context;
    even_odd_arg = n;
    fp = __real_odd;
    swapcontext(&this_context, get_dispatcher_context(&this_context));
    return even_odd_res;
}


main.c:
int even(int);

int main()
{
    int i;
    for (i = 0; i <= 10; i++) {
        int is_even = even(i);
        if (is_even)
            printf("%d is even\n", i);
        else
            printf("%d is odd\n", i);
    }
    return 0;
}

To compile use "gcc -c -O0 *.c; gcc *.o -Wl,-wrap,even -Wl,-wrap,odd -o test_mut_rec".

3 comments:

Anonymous said...

why does it need volatile?
Alex

Evgeniy Ivanov said...

When we switch contexts registers are reloaded, thus we need a guarantee that variable is stored in the memory (not in register).
Recently I had a bug with this: ACK (compiler) generated wrong code for volatile.

Andy Shevchenko said...

You may use memory barriers instead. volatile is usually a bad idea.