10.4 Tipikus fordítói mintázatok felismerése

10.4.1 Motiváció és felismerési stratégia

Egy C-függvény optimalizált assembly-listáját (listing) vizsgálva gyakran hiába keressük a forrás minden műveletét. A függvényhívás egyszerű elágazássá válhat, egy ciklustest többször szerepelhet, egy aritmetikai kifejezés pedig teljesen eltűnhet. Ez nem feltétlenül hibás fordítás: a fordító más utasítássorozattal valósíthatja meg ugyanazt a megfigyelhető viselkedést.

A mérnöki feladat ezért nem a C-forrás mechanikus „visszafordítása”, hanem három kérdés megválaszolása:

1. Milyen számítást végez a megmaradt kód?
2. Mely optimalizálási mintázatok magyarázzák a szerkezetét?
3. Milyen teszt vagy eszközkimenet támasztja alá az értelmezést?

Az előfeltétel a Fordítói optimalizálási szintek hatása a generált kódra ismerete. Itt nem teljesítményt mérünk, hanem mintázatokat azonosítunk.

Architektúraprofil: az alfejezet minden assembly-példája A64 ISA, ARMv8-A, little-endian, Linux/AAPCS64 környezetre vonatkozik, az I. részben. A regiszterek és mnemonicok kizárólag ebben a kontextusban értendők.

10.4.2 Végpozíciós hívás: amikor nincs szükség visszatérésre a burkolóba

A végpozíciós hívás (tail call) olyan hívás, amely után a hívó függvénynek már nincs további érdemi teendője: a meghívott függvény eredményét közvetlenül továbbadja. A végpozíció lehetőséget ad optimalizálásra, de önmagában nem garantálja azt.

Például a későbbi labor lab_tail függvénye csak továbbítja az argumentumot a lab_leaf függvénynek, majd visszaadja annak eredményét.

A64 ISA: szokásos híváskor a BL a következő utasítás címét az X30 linkregiszterbe írja. A minimális végpozíciós hívás ehelyett ilyen lehet:

// A64 ISA, I. rész — illusztratív függvénytörzs.
lab_tail:
    b lab_leaf

A működés lépései:

1. A külső hívó BL utasítása már beállította az X30 visszatérési címét.
2. A lab_tail végén álló B nem módosítja az X30 tartalmát.
3. A lab_leaf szokásos RET utasítása ezért közvetlenül a külső hívóhoz tér vissza.

Ez a minimális burkoló elkerülheti az X30 mentését és visszaállítását, a saját veremkeretét, valamint a saját visszatérési utasítását. Az argumentum és az eredmény egyaránt a W0 regisztert használja, így ebben a példában átrendezésük sem szükséges.

Fontos korlát: a végpozíciós hívás nem jelenti általánosan a teljes prológus és epilógus eltűnését. Ha a függvény korábban veremkeretet hozott létre vagy megőrzendő regisztert módosított, azt az átadás előtt rendeznie kell. A veremargumentumok, a hívási konvenció, illetve egy lokális objektum szükséges élettartama is korlátozhatja az optimalizálást.

A64 kódolási megjegyzés: a közvetlen B és BL előjeles, 26 bites, néggyel skálázott eltolást kódol. Az elérési tartomány az utasítás címéhez képest −128 MiB-tól +128 MiB−4 bájtig terjed. Távoli célhoz a linker köztes ugrókódot is beilleszthet.

Önmagában egy B látványa nem bizonyít végpozíciós hívást: lehet ciklusvisszaugrás vagy függvényen belüli elágazás is. A cél és a környező vezérlés szükséges az értelmezéshez.

10.4.3 Cikluskibontás: több elem egy vezérlési lépésre

A cikluskibontás (loop unrolling) a ciklustest több egymás utáni példányát helyezi egy új ciklusiterációba.

Ha az eredeti ciklus iterációnként egy elemet dolgoz fel, négyszeres kibontásnál a fő ciklustest négy elemmel foglalkozik. Ennek lehetséges jelei:

• ismétlődő betöltés–feldolgozás műveletcsoportok;
• nagyobb mutatóléptetés;
• a hátralévő elemszám csökkentése egynél nagyobb értékkel;
• külön kód a maradék elemekhez.

Az alábbi A64 ISA részlet szemléltető fő ciklustest, nem rögzített GCC-kimenet. Belépéskor az X0 érvényes uint32_t elemekre mutat, az X1 pozitív, néggyel osztható elemszám, a W2 pedig a részösszeg:

// A64 ISA, I. rész — négyszeresen kibontott ciklusmag.
.Lfour:
    ldr  w3, [x0, #0]
    ldr  w4, [x0, #4]
    ldr  w5, [x0, #8]
    ldr  w6, [x0, #12]
    add  w2, w2, w3
    add  w2, w2, w4
    add  w2, w2, w5
    add  w2, w2, w6
    add  x0, x0, #16
    subs x1, x1, #4
    b.ne .Lfour

A64 kódolási korlátok: az itt használt LDR Wt nemnegatív eltolásos alakja 12 bites, néggyel skálázott eltolást fogad el. Az ADD és SUBS immediate alakjában 12 bites érték szerepelhet, opcionálisan 12 bites balra tolással. A B.NE előjeles, 19 bites, néggyel skálázott eltolásának tartománya −1 MiB és +1 MiB−4 bájt között van.

Levezetett vezérlési költség: pozitív, néggyel osztható $n$ elemszámnál az egyenként feldolgozó ciklus $n$, a négyszeresen kibontott fő ciklus $n/4$ ciklusvégi feltételvizsgálatot végezhet. Például 16 elemnél ez 16 helyett 4 vizsgálat. Ez nem ciklusszámmérés és nem négyszeres gyorsulási ígéret: az elemenkénti munka megmarad, a kódméret pedig nőhet.

Általánosan $n=4q+r$, ahol $q$ a teljes csoportok száma, $0\le r<4$ pedig a maradék elemszám. A fenti ciklusmag csak a teljes csoportokat kezeli. A fordítónak a nulla elemszámot és a maradékot is helyesen kell kezelnie.

A tényleges GCC-kód használhat végmutató-összehasonlítást, páros betöltéseket vagy több részösszeget is. A kibontást ezért nem egyetlen konkrét utasítássorozathoz kötjük.

10.4.4 Konstans-összecsukás és műveleterősség-csökkentés

A konstans-összecsukás (constant folding) fordításkor kiszámítható kifejezések kiértékelése. A (9 + 5) * 3 eredménye 42, ezért futáskor nem szükséges sem összeadást, sem szorzást végezni.

Egy lehetséges A64 ISA eredmény:

// A64 ISA, I. rész — lehetséges fordítói kimenet.
lab_fold:
    mov w0, #42
    ret

Az itt használt MOV egyetlen MOVZ utasítással megvalósítható alias: a 42 belefér a 16 bites immediate mezőbe. A 32 bites változatnál a mező elhelyezése 0 vagy 16 bites eltolással történhet. Nem minden 32 bites konstans tölthető be ezzel az egyutasításos formával.

A műveleterősség-csökkentés (strength reduction) más jelenség: egy futásidejű műveletet egyszerűbbnek ítélt művelettel helyettesít. Az előjel nélküli, 32 bites x * 8 például lehet:

// A64 ISA, I. rész — lehetséges fordítói kimenet.
lab_scale:
    lsl w0, w0, #3
    ret

Az A64 LSL Wd, Wn, #s immediate eltolása 0–31 között lehet; 64 bites Xn nézetben 0–63 között.

A két optimalizálás különbsége:

• a konstans-összecsukásnál a teljes eredmény ismert fordításkor;
• a műveleterősség-csökkentésnél x továbbra is futásidejű adat.

A labor uint32_t típust használ, ezért a számolás modulo $2^{32}$ történik. Előjeles C-kifejezéseknél az overflow és a balra tolás szabályai miatt nem szabad ugyanezt mechanikusan alkalmazni. Egy betöltött 42-es értékből pedig önmagában nem állapítható meg, hogy eredetileg összetett kifejezés vagy egyszerű literál szerepelt-e a forrásban.

10.4.5 Kidolgozott labor: három fordítás, azonos szemantika

Munkakönyvtár: ~/arm-labor/a64/a039/ — az alfejezet minden laborfájlja ide kerül, és minden parancs innen futtatandó (a könyvtárrendet a Labor-alapkörnyezet alfejezet írja le).

mkdir -p ~/arm-labor/a64/a039
cd ~/arm-labor/a64/a039

A labor célja qemu-user, AArch64 Linux. Az Ubuntu 24.04-es cross-eszközlánc mellett a statikus linkeléshez az AArch64 cross libc fejlesztői állományai is szükségesek.

A lab-patterns.c tartalma:

#include <stddef.h>
#include <stdint.h>

extern uint32_t lab_leaf(uint32_t x);

uint32_t lab_tail(uint32_t x)
{
    return lab_leaf(x);
}

uint32_t lab_fold(void)
{
    return (UINT32_C(9) + UINT32_C(5)) * UINT32_C(3);
}

uint32_t lab_scale(uint32_t x)
{
    return x * UINT32_C(8);
}

uint32_t lab_sum(const uint32_t *p, size_t n)
{
    uint32_t sum = 0;
    while (n != 0) {
        sum += *p++;
        --n;
    }
    return sum;
}

A lab-test.c biztosítja a másik fordítási egységben levő hívási célt és az ellenőrzést:

#include <inttypes.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>

uint32_t lab_tail(uint32_t x);
uint32_t lab_fold(void);
uint32_t lab_scale(uint32_t x);
uint32_t lab_sum(const uint32_t *p, size_t n);

uint32_t lab_leaf(uint32_t x)
{
    return x + UINT32_C(7);
}

int main(void)
{
    const uint32_t a[] = {
        1, 2, 3, 4, 5, 6, 7, 8, 9,
        10, 11, 12, 13, 14, 15, 16, 17
    };
    const uint32_t wrap[] = { UINT32_MAX, 1 };

    uint32_t t = lab_tail(5);
    uint32_t f = lab_fold();
    uint32_t s = lab_scale(9);

    if (t != 12 || f != 42 || s != 72)
        return 1;
    if (lab_scale(UINT32_MAX) != UINT32_C(0xfffffff8))
        return 1;
    if (lab_sum(NULL, 0) != 0 || lab_sum(wrap, 2) != 0)
        return 1;

    for (size_t n = 0; n <= sizeof a / sizeof a[0]; ++n) {
        uint32_t expected = (uint32_t)(n * (n + 1) / 2);
        if (lab_sum(a, n) != expected)
            return 1;
    }

    printf("tail=%" PRIu32 " fold=%" PRIu32
           " scale=%" PRIu32 " sum10=%" PRIu32 "\n",
           t, f, s, lab_sum(a, 10));
    puts("PASS");
    return 0;
}

A külön fordítási egység és a kikapcsolt linkidejű optimalizálás (link-time optimization, LTO) megakadályozza, hogy a lab_leaf törzse egyszerűen beágyazódjon a lab_tail függvénybe.

A vektorizálást most kikapcsoljuk, hogy a skaláris cikluskibontást könnyebb legyen felismerni. Ez oktatási beállítás, nem általános teljesítményajánlás.

# Host: Ubuntu 24.04 x86_64.
# Target: qemu-user, AArch64 Linux, A64 ARMv8-A, little-endian.
# Az alábbi parancsok Bash szintaxisúak.

aarch64-linux-gnu-gcc --version > lab-versions.txt
aarch64-linux-gnu-as --version >> lab-versions.txt
qemu-aarch64 --version >> lab-versions.txt

lab_flags=(
    -std=c11 -O2 -Wall -Wextra
    -march=armv8-a -mtune=generic
    -fno-lto -fno-pie
    -fno-tree-loop-vectorize -fno-tree-slp-vectorize
)

# C -> A64 assembly: alapváltozat.
aarch64-linux-gnu-gcc "${lab_flags[@]}" \
    -foptimize-sibling-calls -fno-unroll-loops \
    -S lab-patterns.c -o lab-base.s

# C -> A64 assembly: cikluskibontás ösztönzése.
aarch64-linux-gnu-gcc "${lab_flags[@]}" \
    -foptimize-sibling-calls -funroll-loops \
    -S lab-patterns.c -o lab-unroll.s

# C -> A64 assembly: végpozíciós hívás optimalizálása nélkül.
aarch64-linux-gnu-gcc "${lab_flags[@]}" \
    -fno-optimize-sibling-calls -fno-unroll-loops \
    -S lab-patterns.c -o lab-call.s

# Tesztkód fordítása AArch64 objektummá.
aarch64-linux-gnu-gcc "${lab_flags[@]}" \
    -c lab-test.c -o lab-test.o

# A64 assemble -> statikus Linux ELF -> qemu-user futtatás.
for lab_mode in base unroll call; do
    aarch64-linux-gnu-as -march=armv8-a \
        "lab-${lab_mode}.s" -o "lab-${lab_mode}.o"
    aarch64-linux-gnu-gcc -static -no-pie \
        "lab-${lab_mode}.o" lab-test.o -o "lab-${lab_mode}"
    aarch64-linux-gnu-objdump -dr \
        "lab-${lab_mode}.o" > "lab-${lab_mode}.dis"
    qemu-aarch64 "./lab-${lab_mode}"
    printf 'exit=%d\n' "$?"
done

Várt, nem ténylegesen futtatott eredmény: mindhárom program kiírja a tail=12 fold=42 scale=72 sum10=55, majd a PASS sort; a jelzett kilépési állapot exit=0. Az 1-es kilépési állapot szemantikai teszthibát jelent.

Az assembly-mintázatok viszont kiadás- és döntésfüggők:

A -funroll-loops nem ígér konkrét kibontási tényezőt minden ciklusra. Az objektum disassemblyjében a külső hívás mellett az AArch64 ELF R_AARCH64_CALL26, a közvetlen átadás mellett pedig R_AARCH64_JUMP26 relokáció is segítheti az azonosítást.

10.4.6 Tipikus hibák és ellenpróbák

„Nincs hívásutasítás, tehát a hívás eltűnt.”
Hipotézis: beágyazás történt. Ellenpróba: vizsgáljuk meg a célszimbólumra mutató A64 B utasítást és a relokációt. Lehet, hogy a hívási határ megmaradt, csak végpozíciós átadássá alakult.

„Négy betöltés biztosan négyszeres kibontás.”
Négy külön C-kifejezés is okozhat négy betöltést. Ellenőrizzük együtt a visszaugrási élt, a mutatólépést és a ciklusfeltételt.

„A kibontott ciklus minden elemszámra ugyanúgy léphet négyet.”
Ha az egyetlen kilépési feltétel a számláló nullává válása, a nem négyszeres elemszám problémát okozhat. A labor 0–17 elemre vizsgálja a függvényt, így több csoporthatárt és maradékot is lefed.

„Kevesebb ugrás ugyanannyi arányú gyorsulást jelent.”
Nem: nőhet a kódméret és a regiszternyomás, miközben az összeadások függőségi lánca megmaradhat. A labor nem mér latencyt, throughputot vagy hardveres ciklusszámot. QEMU alatt az abszolút futási idő amúgy sem tekinthető hardverhű AArch64-időnek.

10.4.7 Feladatok

1. (magyarázó, alapszint — cél: megértés-ellenőrzés) Kövesd az A64 X30 tartalmát a külső hívó → lab_tail → lab_leaf útvonalon! Miért elég a burkolóban egy B? Miért nem következik ebből, hogy minden végpozíciós hívásnak nincs veremkerete?

2. (implementációs, középszint — cél: rutinépítés) Egészítsd ki a labort uint32_t lab_mixed(uint32_t x) függvénnyel, amely x * 8 + (9 + 5) * 3 értékét adja vissza. Teszteld 9 és UINT32_MAX bemenettel! Mely optimalizálások működhetnek együtt?

3. (hibakeresési, középszint — cél: rutinépítés) A lab-call változatban a burkoló hívásutasítást és veremkezelést tartalmaz. Állíts fel hipotézist, vizsgáld meg az objektumot, majd egyetlen fordítási kapcsoló megváltoztatásával készíts ellenpróbát! Az eredmény mellett a lab_sum kibontását is értékeld a lab-unroll.dis alapján.

10.4.8 Megoldások

1. megoldás — Segítség. A BL és a B közül melyik írja át az X30-at? Ha a burkoló VÉGÉN álló utasítás nem nyúl hozzá, kinek a visszatérési címe marad érvényben?

1. megoldás — Teljes megoldás. A külső A64 BL beállítja az X30 értékét. A burkoló B utasítása ezt változatlanul hagyja, így a célfüggvény a külső hívóhoz térhet vissza. Szokásos belső BL esetén a burkolónak meg kellene őriznie saját visszatérési címét. Egy összetettebb burkoló azonban korábbi munkája miatt rendelkezhet veremkerettel; ezt a végpozíciós átadás előtt bontja le.

2. megoldás — Segítség. $9 \cdot 8 + 42 = 114$; UINT32_MAX $\cdot 8$ modulo $2^{32}$ mennyi, és ehhez hozzáadva 42-t, megint modulo $2^{32}$, mit kapsz?

2. megoldás — Teljes megoldás. A lab-patterns.c kiegészítése:

uint32_t lab_mixed(uint32_t x)
{
    return x * UINT32_C(8)
         + (UINT32_C(9) + UINT32_C(5)) * UINT32_C(3);
}

A lab-test.c deklarációihoz add hozzá a prototípust, a main ellenőrzéseihez pedig:

if (lab_mixed(9) != 114 || lab_mixed(UINT32_MAX) != 34)
    return 1;

Futtasd újra a teljes buildlépéssort. Az első eredmény $72+42=114$. A másodiknál az előjel nélküli szorzás eredménye 0xfffffff8, ehhez 42-t adva, modulo $2^{32}$, 34 keletkezik. A konstansrész összevonható, a szorzás eltolássá alakítható; az eltolás akár más A64 utasítás operandusába is beolvadhat.

3. megoldás — Segítség. A lab-call változatot explicit -fno-optimize-sibling-calls-lal fordítottuk — ez fordítói DÖNTÉS, nem C-nyelvi korlát. Mi történne, ha ezt a kapcsolót egyszerűen elhagynánk vagy megfordítanánk?

3. megoldás — Teljes megoldás. A hipotézis szerint nem a C-forrás tiltja az átalakítást, hanem a -fno-optimize-sibling-calls kapcsoló. Az A64 objektum vizsgálata:

# Target: qemu-userhez készített A64 objektum; hostoldali elemzés.
aarch64-linux-gnu-objdump -dr \
    --disassemble=lab_tail lab-call.o

Az ellenpróbához cseréld a tiltó kapcsolót -foptimize-sibling-calls értékre, és építsd újra ugyanazt a változatot. A tesztkimenetnek változatlannak kell maradnia, miközben megjelenhet a végpozíciós átadás. A cikluskibontás tényezőjét a visszaugrások között feldolgozott elemekből állapítsd meg, ne a teljes függvény betöltésszámából: a maradékkezelés külön műveleteket tartalmazhat.

10.4.9 Rövid összefoglaló

Az optimalizált assembly-lista értelmezésekor nem a C-forrás sorait, hanem az adatáramlást és a vezérlést követjük. A végpozíciós hívás megőrizheti a hívási határt, miközben elhagyja a burkoló saját visszatérési útját. A cikluskibontást az ismételt műveletcsoport, a nagyobb léptetés és a maradékkezelés együtt jelzi. A konstans-összecsukás eltünteti a fordításkor kiszámítható munkát; a változóval végzett szorzás eltolássá alakítása más optimalizálás. A pontos utasítássorrend fordítófüggő, ezért a felismerést disassemblyvel és határeseteket is tartalmazó tesztekkel ellenőrizzük. Az utasításszám változása önmagában nem teljesítménymérés.

• Végpozíciós hívás: közvetlen eredménytovábbítással záruló hívás.
• Cikluskibontás: több eredeti iteráció összevonása egy ciklustestbe.
• Konstans-összecsukás: ismert kifejezés fordításidejű kiértékelése.

10.4.10 Források és ellenőrzési hiányok

A linkek és a dokumentumverziók közös állapota az Olvasói útmutató forrásállapot-táblájában van; itt csak az alfejezet saját megállapításai szerepelnek.

• GCC: Options That Control Optimization — végpozíciós hívások, cikluskibontás és vektorizálási kapcsolók. Tartalmilag ellenőrizve: a legújabb listázott kiadás GCC 16.2.
• GNU Binutils: objdump — disassembly, szimbólumok és relokációk vizsgálata. Tartalmilag ellenőrizve: a jelenlegi kiadás binutils 2.47.
• Arm: Procedure Call Standard for the Arm 64-bit Architecture — regiszterszerepek és a hívási határon teljesítendő szerződés. Tartalmilag ellenőrizve: a jelenlegi kiadás 2025Q4 (2026-01-23), Release minőségű (az SME-részek Beta státuszúak).
• Arm Architecture Reference Manual for A-profile architecture — A64 utasításszemantika és kódolási korlátok. Ellenőrizve: a link él; a fejezetszám és a kiadásbetű az Arm-oldalak közös korlátja miatt nem ellenőrzött.

Ellenőrzési hiányok, amelyek a fenti ellenőrzés után is ténylegesen fennmaradnak: a programok nem kerültek tényleges fordításra vagy futtatásra. A telepített Ubuntu 24.04-es csomagok pontos verzióját, a statikus cross libc rendelkezésre állását és a GCC által választott kibontási tényezőt a hallgató laborjában kell rögzíteni. A bemutatott assembly-részletek lehetséges vagy szemléltető mintázatok, nem ellenőrzött fordítói kimenetek.