Implementatie van GCC's Nested Functions (vs. C++ Lambdas)

Inleiding

In dit artikel wil ik uitleggen hoe de nested functions (geneste functies) van GCC zijn geïmplementeerd.

Ik zal niet ingaan op het adresseren van een geneste functie, aangezien dit het creëren van een trampoline kan vereisen. We hebben dit onderwerp — en hoe dit te omzeilen — al besproken in verschillende eerdere blogposts. In plaats daarvan wil ik het basismechanisme beschrijven dat wordt gebruikt om variabelen van een ouderfunctie te benaderen.

Geneste functies

Laten we beginnen met een zeer eenvoudig voorbeeld:

int foo(int k)
{
    int bar(int x) { return x + 1; }
    return bar(k);
}

In dit geval benadert de geneste functie geen enkele variabele van de ouderfunctie. De functie kan daarom simpelweg uit de ouderfunctie worden getild (lifted) en als een aparte functie worden gecompileerd. Dergelijke functies kunnen nog steeds nuttig zijn voor het definiëren van kleine hulpfuncties, of wanneer een type lokaal wordt gedefinieerd dat vervolgens in de geneste functie kan worden gebruikt.

WG14 overweegt momenteel voorstel N3884, dat dergelijke non-capturing lokale functies zou toestaan wanneer ze worden gedefinieerd met de static storage class.

Laten we nu echter kijken naar een voorbeeld waarbij een geneste functie wel een variabele van de ouderfunctie benadert:

int foo(int k)
{
    int bar(int x) { return x + k; }
    return bar(1);
}

Tijdens de uitvoering moet de geneste functie in staat zijn de variabele k van de ouderfunctie te vinden (ervan uitgaande dat deze niet volledig wordt geoptimaliseerd, wat in dit specifieke geval wel zou gebeuren). Traditioneel werd dit geïmplementeerd door een pointer naar het stack-frame van de ouder door te geven, waarna de variabele op de juiste stack-slot kon worden benaderd. Deze technieken werden gebruikt in PASCAL en soortgelijke talen; x86 heeft zelfs speciale instructies, namelijk enter and leave, om dit te ondersteunen. Dit is echter niet de manier waarop GCC deze functie tegenwoordig implementeert.

In GCC worden geneste functies verlaagd (lowered) in een vroege middle-end pass. Tijdens deze pass worden alle variabelen van de ouder die door de geneste functie worden benaderd, verzameld in één synthetische structuur. Een pointer naar deze structuur wordt vervolgens als een verborgen argument aan de geneste functie doorgegeven. Toegang tot dergelijke variabelen wordt herschreven naar toegang tot het overeenkomstige lid van deze structuur.

De resulterende code is in essentie het volgende (zie [Godbolt Example]):

struct frame { int k; };

static int bar(struct frame *f, int x)
{
    return x + f->k;
}

int foo(int k)
{
    struct frame frame = { k };
    return bar(&frame, 1);
}

Het belangrijkste voordeel van deze aanpak is dat de implementatie van geneste functies wordt ontkoppeld van de rest van de compiler. De compiler kan de statische pointer simpelweg behandelen als een aanvullend verborgen argument dat wijst naar een reguliere structuur. Andere variabelen van de ouderfunctie die niet door een kindfunctie worden benaderd, worden helemaal niet beïnvloed. Ook de frame-structuur zelf kan worden geoptimaliseerd als elke andere structuur in het programma. Zo wordt het bovenstaande voorbeeld door algemene optimizer-code, die niets specifieks weet over geneste functies, vereenvoudigd tot een simpele optelling:

"foo":
lea     eax, [rdi+1]
ret

Wanneer er sprake is van meerdere nestingsniveaus, bevat de structuur ook een link naar de frame-structuur één niveau hoger. Hierdoor ontstaat een lijst (keten) van frame-structuren, hoewel dit zelden nodig is.

Vergelijking met de lambda-functionaliteit van C++

Het is interessant om dit te vergelijken met de werking van lambda's in C++. Er zijn natuurlijk enkele oppervlakkige verschillen in hoe deze functionaliteit op taalniveau wordt aangeboden. Lambda's zijn functieliteralen die geen naam hebben en expressies zijn, terwijl de geneste functies van GCC reguliere functiedefinities zijn die in een geneste context verschijnen. Vanuit implementatiepunt staan is dit echter geen fundamenteel verschil.

Een ander verschil op taalniveau is dat het zichtbare type van de geneste functie in GCC een regulier functietype is. In tegenstelling hiermee is het type van een lambda in C++ een Voldemort-type: een uniek anoniem type dat niet benoemd kan worden.

Afgezien van deze twee verschillen is de semantiek van geneste functies een subset van die van C++ lambda's. In feite kan het bovenstaande voorbeeld simpelweg worden herschreven naar C++ door gebruik te maken van een lambda-object:

int foo(int k)
{
    auto bar = [&](int x) -> int { return x + k; };
    return bar(1);
}

Kijkt men iets dieper, dan is het implementatiemechanisme achter de geneste functies van GCC ook niet erg verschillend van hoe een C++ compiler een lambda vertaalt naar een callable object: C++ lambda's worden ook omgezet in structuren (of liever: callable objects in C++) die een kopie of referentie naar de gevangen (captured) variabelen bevatten.

struct bar_anonymous {
    int &k;
    int operator() (int x);
};

inline int bar_anonymous::operator() (int x)
{
    return x + k;
}

int foo(int k)
{
    bar_anonymous bar(k);
    return bar(1);
}

Er blijft één verschil over, wat het best kan worden uitgelegd met een voorbeeld waarin twee geneste functies voorkomen:

int foo(int k)
{
    int bar1(int x) { return x + 2 * k; }
    int bar2(int x) { return x + 3 * k; }
    return bar1(1) + bar2(1);
}

In dit geval creëert GCC één enkele frame-structuur in de ouderfunctie die k bevat, en beide geneste functies ontvangen exact dezelfde pointer naar deze gedeelde omgeving:

struct frame { int k; };

static int bar1(struct frame *f, int x)
{
    return x + 2 * f->k;
}

static int bar2(struct frame *f, int x)
{
    return x + 3 * f->k;
}

int foo(int k)
{
    struct frame frame = { k };
    return bar1(&frame, 1) + bar2(&frame, 1);
}

In contrast hiermee zal een C++ compiler twee aparte objecten produceren voor elke lambda-expressie, die elk een referentie bevatten naar dezelfde k-variabele op de stack:

struct bar1_anonymous {
    int &k;
    int operator() (int x);
};

inline int bar1_anonymous::operator() (int x)
{
    return x + k;
}

struct bar2_anonymous {
    int &k;
    int operator() (int x);
};

inline int bar2_anonymous::operator() (int x)
{
    return x + k;
}

int foo(int k)
{
    bar1_anonymous bar1(k);
    bar2_anonymous bar2(k);
    return bar1(1) + bar2(1);
}

Ondanks dit verschil in implementatie hebben de GNU C- en C++-versies van dit voorbeeld exact dezelfde semantiek.

Conclusie

De geneste functies van GCC komen overeen met een kleine semantische subset van C++ lambda's. Hoewel ze historisch gezien vanuit een andere aanpak zijn geëvolueerd, is hun implementatie niet fundamenteel anders. Een compiler die C++ al implementeert, zou een functie met dezelfde syntaxis en semantiek als de geneste functies van GCC kunnen aanbieden, gebaseerd op de bestaande ondersteuning voor lambda's.

Literatuur

• GCC, Nested Functions
• Jens Gustedt, N3884: Wording for "Local functions"
• Raymond Chen, The mysterious second parameter to the x86 ENTER instruction