What makes a nested function in gcc so complicated?

Question

Disclaimer: I'm not a compiler expert, but some of my best friends are! :)

I do a lot of embedded systems programming where stack (and other memory) is limited. Most of my code is written in gcc, so I thought nested functions could be useful for reducing stack usage. Here's an example of what I had in mind:

(Though the algorithm isn't important for this question, assume that list_traverse takes a pointer to a list head and a function. The contains_aux() function gets called with each element in turn.)

bool list_contains(list_t *head, list_t *item) {
  bool found = false;
  void contains_aux(list_t *list) {
    if (list == item) {
      found = true;
    }
  }
  list_traverse(head, contains_aux);
  return found;
}

I assumed that the nested contains_aux() function would be able to directly reference its lexically closed variables (found and item). But I was wrong.

Instead, looking at the generated code, I see that it installs some sort of trampoline function on the stack and calls that before getting to the contains_aux() function.

I know that contains_aux() can't share the same stack frame as list_contains() because there's an intervening function on the stack (list_traverse()), but -- geez -- it seems like the compiler could pass the frame pointer from list_contains() so contains_aux() could access its locals.

Is there a reason it doesn't work this way? Is there a way I could torture the compiler into doing that? Or should I just resign myself using un-nested functions and passing a "context" object to contains_aux()?

Answer 1

I don't see any obvious reason why the compiler could not inline the call to list_traverse, assuming that it is a simple and that its definition is available in the translation unit. But apparently it doesn't. (Actually, I do see an obvious reason: "It would be a lot of work, and the benefit might not be great." Not saying that that statement is necessarily valid, but a reason can be just a suspicion.)

Without inlining, though, it's very difficult to see how the trampoline could be avoided. The frame containing the variables has to be passed through list_traverse so that it can be handed off to contains_aux. But presumably list_traverse is used elsewhere, and those other calls might not even involve a nested function, in which case there would be no stack frame to be passed through. There's nothing in list_traverse's prototype which specifies that it might be called with a nested function, so if it has external linkage, it needs to be usable with the standard calling convention, which has no room for hidden parameters. And if it is called with a nested function, there is no guarantee that the nested function it is called with was nested in the same way. (For example, there might be more than one stack frame which needs to accompany the closure, if the bound variables come from different places in the call stack.)

So aside from inlining, the only safe solution is to manufacture something which can be called like an ordinary function, thereby conforming with the type of list_traverse's first argument.

As evidence that inlining is possible, I offer the following C++ program, in which the same compiler happily inlines the lambda:

struct list_t {
    int value;
    list_t* next;
};

template<typename F>
void list_traverse(list_t* head, F check) {
    while (head && check(head))
        head = head->next;
}

bool list_contains(list_t *head, list_t* item) {
    bool found = false;
    list_traverse(head, [&](list_t *list)->auto {
        return list == item ? (found = true, false) : true;
        });
    return found;
}

(Alternatively, with a strangely bloated result: https://gcc.godbolt.org/z/s9XqW7).

I do understand that inlining might not be exactly what you're looking for, though.