14.3 Optimalizáló, as-if és UB következményei

Az optimalizáló nem a forráskód sorait próbálja gyorsabban végrehajtani, hanem olyan gépi programot állít elő, amely a C nyelvi szerződésén belül ugyanazt a megfigyelhető viselkedést valósítja meg. Ehhez műveleteket tüntethet el, függvényhatárokat bonthat le, és átrendezheti a számításokat. A fejlesztő feladata ezért nem az, hogy egy konkrét utasítássorrendet „belelásson” a C programba, hanem hogy pontosan ismerje az optimalizálás előfeltételeit.

A fejezet az effective type és aliasing, a kiértékelési sorrend, valamint a C forrás és assembly kapcsolatának szabályaira épít. Központi állítása: egy futtatás eredménye megfigyelés, nem a nyelvi szerződés módosítása.

14.3.1 Az as-if szabály és a megfigyelhető viselkedés

ISO C17. Az as-if szabály az optimalizálási szabadság szokásos összefoglalása: a megvalósítás eltérhet az absztrakt gép lépéseitől, amennyiben megőrzi a szabvány által megkövetelt megfigyelhető viselkedést (observable behavior).

Ide tartoznak a szabvány szerinti volatile hozzáférések, valamint a fájl- és interaktív I/O-ra előírt követelmények. Egy közönséges lokális változó minden köztes értéke, egy függvény tényleges meghívása vagy a gépi utasítások száma önmagában nem megfigyelhető viselkedés ebben az értelemben. A futásidő üzemi szempontból fontos, de nem olyan változatlan mennyiség, amelyet az as-if szabály megkövetel.

Három alapvető transzformáció:

• Konstanskiértékelés (constant folding): egy fordításkor ismert kifejezés helyettesítése az értékével.
• Holt kód eliminálása (dead code elimination): olyan számítás eltávolítása, amely nem befolyásol megkövetelt megfigyelhető viselkedést.
• Behelyettesítés (inlining): a hívás helyettesítése a függvénytörzs megfelelő változatával. Ez további optimalizálásokat tesz lehetővé.

Az inlininghez nem szükséges az inline kulcsszó, és a kulcsszó nem is garantálja a behelyettesítést.

14.3.1.1 Kidolgozott példa és laborprofil

Az alábbi opt.c teljes, C17-es program. A számtani minták nem igényelnek konkrét egészszélességet.

Választott laborprofil: Linux, x86-64 System V ABI, LP64, CHAR_BIT == 8; GCC 14.2.0 vagy Clang 19.1.7, glibc 2.40 és GNU binutils 2.43.1. Ezek rögzített vizsgálati verziók, nem itt végrehajtott fordítás adatai. A parancsokhoz a megfelelő helyi toolchaint kell kiválasztani.

#include <limits.h>
#include <stddef.h>
#include <stdio.h>

static unsigned bias(unsigned x)
{
    return x + 3u;
}

unsigned folded(void)
{
    unsigned discarded = 9u * 9u;
    (void)discarded;
    return bias(4u * 2u);
}

int checked_inc(int x, int *out)
{
    if (x == INT_MAX)
        return 0;

    *out = x + 1;
    return 1;
}

void add(size_t n, float *restrict dst,
         const float *restrict src)
{
    for (size_t i = 0; i < n; ++i)
        dst[i] += src[i];
}

int main(void)
{
    float dst[] = {1.0f, 2.0f, 3.0f, 4.0f};
    const float src[] = {10.0f, 20.0f, 30.0f, 40.0f};
    int next = 0;

    int ok = checked_inc(41, &next);
    add(4, dst, src);

    printf("%u %d %d %.0f\n",
           folded(), ok, next, (double)dst[3]);
    return 0;
}

A mutatók nem tulajdonolnak tárolót. Szerződésük:

Fordítás és assembly előállítása:

gcc -std=c17 -Wall -Wextra -Wpedantic -O0 opt.c -o opt-O0
gcc -std=c17 -Wall -Wextra -Wpedantic -O2 opt.c -o opt-O2

gcc -std=c17 -O2 -march=x86-64 -mtune=generic \
    -fopt-info-vec-optimized -fopt-info-vec-missed \
    -S opt.c -o opt-gcc.s

clang -std=c17 -O2 -march=x86-64 -mtune=generic \
    -Rpass=loop-vectorize -Rpass-missed=loop-vectorize \
    -Rpass-analysis=loop-vectorize \
    -S opt.c -o opt-clang.s

A program nyelvi levezetés alapján várt kimenete 11 1 42 44; ez nem közölt mérési eredmény.

A folded egyszerűsítése lépésenként:

1. A 4u * 2u értéke 8u.
2. A bias(8u) eredménye 11u.
3. A discarded értéke sem a visszatérési értéket, sem más megfigyelhető hatást nem befolyásol.
4. A függvény ezért viselkedésében egyenértékű a return 11u; törzzsel.

Bizonyításvázlat. A számítások eredménye ábrázolható, nincs I/O vagy volatile hozzáférés, és a megszüntetett lokális objektumhoz nem marad hozzáférés. A behelyettesítés és az értékegyszerűsítés tehát nem változtatja meg a megfigyelhető eredményt.

Ez nem garantál egy konkrét assemblyalakot. A -O0 sem jelent minden fordításkori egyszerűsítést kizáró, soronkénti gépi leképezést.

14.3.2 Aliasing, strict aliasing és restrict

Az alias analysis azt vizsgálja, hogy két hozzáférés érintheti-e ugyanazt a tárolót. Ha egy írás módosíthat egy korábban beolvasott értéket, a fordító nem használhatja automatikusan újra a régi értéket.

ISO C17. Az effective type hozzáférési szabályait gyakran strict aliasing néven említjük. A megengedett típuskombinációkat az aliasingról szóló rész rögzíti. Egy pointerkonverzió önmagában nem teszi szabályossá az új típuson keresztüli dereferálást.

Például egy helyi float f objektum *(int *)&f alakú olvasása nem válik helyessé attól, hogy az adott targeten a két típus mérete és igazítása megfelelő lenne. Az objektumreprezentáció vizsgálatára használjunk karaktertípusú hozzáférést vagy megfelelő memcpy-másolást; ez utóbbi után a célreprezentáció érvényességét is figyelembe kell venni.

A restrict másfajta információt ad. Nem típusok közötti különbséget, hanem egy blokk végrehajtása során érvényes hozzáférési ígéretet fejez ki. Leegyszerűsítve: ha egy objektumot egy korlátozott pointeren alapuló hozzáféréssel érünk el, és az objektum módosul is, az érintett hozzáféréseknek követniük kell a restrict előírt kapcsolatait.

Ez nem azt jelenti, hogy bármely két restrict pointerértéknek különböznie kell. A tényleges hozzáférések számítanak.

Az add számára könnyen ellenőrizhető, elegendő hívási szerződés:

• a cél- és forrástartomány elegendő elemet tartalmaz;
• a hozzáfért tartományok nem fedik egymást;
• az objektumok a teljes hívás alatt élnek.

Ekkor a célba írás nem módosíthat később beolvasandó forráselemet. n == 0 esetén a törzs nem végez pointeraritmetikát vagy memória-hozzáférést.

Fordítómegvalósítás. A GCC és Clang -fno-strict-aliasing kapcsolója módosítja a típusokon alapuló aliasfeltételezések használatát. Ez nem általános javítás hibás C programokra: nem old meg bounds-, alignment-, lifetime- vagy restrict-sértést. A helyes megoldás az érvényes hozzáférési szerződés.

14.3.3 Signed overflow és objektumhatárok

ISO C17. Az előjeles egész túlcsordulása nem definiált viselkedés. Ez nem csupán azt jelenti, hogy az eredmény „furcsa” lehet: az érintett végrehajtás viselkedésére a szabvány nem ír elő követelményt.

Az alábbi C17-részlet hibás, ha minden int bemenetre működő túlcsordulásvizsgálatnak szánjuk:

/* UB-s tanítási példa x == INT_MAX esetén. */
int grows(int x)
{
    return x + 1 > x;
}

Definiált végrehajtásban:

$$x \leq \mathrm{INT\_MAX}-1.$$

Ebből következik:

$$x+1>x.$$

A fordító ezért a teljes törzset helyettesítheti return 1; utasítással. Nem köteles az INT_MAX esetét hardveres körbefordulásként kezelni. Ha egy konkrét fordítás mégis ilyen viselkedést mutat, az nem teszi szabályossá a programot.

A checked_inc ezzel szemben a művelet előtt ellenőrzi a veszélyes bemenetet. A feltétel hamis ágában az összeadás bizonyíthatóan ábrázolható; hibánál az eredményobjektum változatlan marad.

Az unsigned eset eltér: az összeadás modulo $\mathrm{UINT\_MAX}+1$ történik, ahol az összeg itt matematikai jelölés. Ezért egy unsigned x értékre az x + 1u > x feltétel hamis lehet, mégpedig x == UINT_MAX esetén.

Az objektumhatárok ugyanezt a gondolkodást igénylik. Hibás C17-függvénytörzs-részlet:

/* Hibás: az ellenőrzés túl későn történik. */
int value = a[i];
if (i >= n)
    return -1;
return value;

Itt a a hívó élő, n elemű int tömbjének kölcsönzött elérése, i és n típusa size_t. Az élettartamnak a hívás végéig tartania kell. Ha i >= n, már az első sor megsérti a hozzáférés szerződését; a későbbi hibakód nem menti meg a végrehajtást.

A javítás az ellenőrzés előrehozása. Az i < n feltétel azonban önmagában nem igazolja a pointert: a tároló mérete, élettartama és olvashatósága külön előfeltétel.

14.3.4 Vektorizálás és ciklustranszformációk

A vektorizálás több iteráció műveletét végzi el SIMD-utasításokkal. Más gyakori ciklustranszformáció a cikluskibontás, a ciklusinvariáns számítás kiemelése és a ciklusok összevonása.

Az add esetében a diszjunkt tartományok miatt nincs iterációk közötti memóriafüggőség: az egyik iteráció írása nem változtatja meg a másik által olvasott értéket. Ez lehetővé teheti több elem párhuzamos feldolgozását.

A lehetőség azonban nem garancia. A fordító költségmodellje figyelembe veheti a ciklushosszt, az igazítást, a maradékelemek kezelését és a rendelkezésre álló utasításkészletet. restrict nélkül is készülhet vektoros változat, például futásidejű átfedésvizsgálattal és skalár tartalékággal.

Lebegőpontos redukciónál külön akadály az összeadási sorrend:

$$(a+b)+c \neq a+(b+c)$$

lehet a kerekítés miatt. Egy soros összegzés tetszőleges újracsoportosítása ezért nem következik az as-if szabályból. A -ffast-math jellegű kapcsolók további numerikus feltételezéseket engednek; ezek külön szerződést igényelnek.

A laborparancsok optimization remark üzenetei az alkalmazott vagy elutasított transzformációkat magyarázzák. Nem helyességi bizonyítványok. Egy „vectorized” üzenet nem igazolja, hogy a hívó betartotta a restrict szerződést, és nem jelent mért gyorsulást sem.

14.3.5 Külön fordítás, LTO és PGO

Külön fordításkor a fordító gyakran csak egy külső függvény deklarációját ismeri. Nem látja a törzsét, ezért bizonyos mellékhatásokkal és adatfüggőségekkel számolnia kell. Típusinformáció, ismert könyvtári szerződés vagy más igazolt információ így is segíthet, de a láthatóság korlátozott.

A link-time optimization, azaz LTO fordítási egységeken át teszi elérhetővé az optimalizáláshoz szükséges reprezentációt. Lehetővé tehet egységek közötti inliningot, konstanspropagációt és holt kód eltávolítását. GCC- és Clang-környezetben tipikus kapcsolója a -flto; a fordítási és linkelési lépésnek, valamint a linkernek együtt kell támogatnia.

A profile-guided optimization, azaz PGO reprezentatív futások profilját használja. A gyakori ágak, hívási célok és kódutak alapján módosíthatja például a kódelrendezést vagy az inlining döntéseit.

A profil gyakoriságot jelez, nem nyelvi lehetetlenséget bizonyít. Egy ritka, de definiált ág helyességét továbbra is meg kell őrizni. Elavult vagy nem reprezentatív profil ronthatja a teljesítményt.

LTO és PGO gyakran tesz láthatóvá korábban rejtett UB-következményeket. Ilyenkor nem az optimalizálás „rontotta el” a szerződést: több információ alapján érvényesítette a program által vállalt feltételeket.

14.3.6 A volatile korlátai és gyakori tévedések

ISO C17. A volatile minősítés az érintett hozzáféréseket a megfigyelhető viselkedéshez kapcsolja; annak részlete, hogy mi számít hozzáférésnek, implementáció által meghatározott.

Ha a példabeli discarded objektum volatile unsigned lenne, a hozzáféréseit nem lehetne közönséges holt lokális változóként elhagyni. A jobb oldali 9u * 9u konstanskiértékelése ettől még megengedett.

A volatile ugyanakkor nem:

• teszi atomikussá az összetett műveleteket;
• hoz létre szálak közötti szinkronizációt;
• általános compiler barrier vagy hardveres memóriakorlát;
• javítja ki a signed overflow-t vagy az érvénytelen dereferálást.

A barriermechanizmusokat a következő kapcsolódó rész, a publikalás szabályait a happens-before tárgyalása választja szét.

Gyakori diagnosztikai hiba az optimalizálás kikapcsolását javításnak tekinteni. A -O0 és -O2 közötti eltérés hasznos jel, de önmagában sem UB-t, sem fordítóhibát nem bizonyít. Először a nyelvi szerződést, majd a kapcsolók feltételeit, végül a gépi megvalósítást kell vizsgálni. Ugyanígy a warningok hiánya sem bizonyítja a program helyességét.

14.3.7 Feladatok

14.3.7.1 Magyarázó feladat: eltűnő számítások

Indokold meg, miért helyettesíthető a folded törzse return 11u; utasítással. Mi változik, ha a discarded volatile unsigned típusú?

14.3.7.2 Kódolási feladat: ellenőrzött összeadás

Írj C17-ben checked_add(int a, int b, int *out) függvényt. Túlcsordulás esetén adjon 0-t, és ne módosítsa a célobjektumot; siker esetén tárolja az összeget, és adjon 1-et. Az ellenőrzés maga sem okozhat túlcsordulást.

14.3.7.3 Diagnosztikai feladat: átfedő tartományok

Az add függvényt így hívnánk:

/* UB-s tanítási hívás; nem helyességi teszt. */
float a[5] = {1.0f, 2.0f, 3.0f, 4.0f, 5.0f};
add(4, a + 1, a);

Az a tömb a hívó tulajdona, és a teljes hívás alatt él. Mi sérül mégis? Mi lenne a soros ciklus eredménye a restrict nélküli változatban? Miért nem bizonyíték a vektorizálási jelentés?

14.3.8 Megoldások

14.3.8.1 Az eltűnő számítások indoklása

A konstansszorzás eredménye 8u, a bias ezt 11u-ra alakítja. A közönséges discarded objektum számítása és olvasása nem befolyásolja a megfigyelhető eredményt.

volatile esetén a hozzáféréseket meg kell őrizni a megvalósítás hozzáférési szabályai szerint, de a szorzás továbbra is fordításkor kiértékelhető. Az ellenőrzési feltétel tehát nem egy konkrét utasításszám, hanem a megkövetelt hozzáférések és a visszatérési érték megőrzése.

14.3.8.2 Az ellenőrzött összeadás megvalósítása

C17-részlet, az opt.c fájlba illeszthető; a szükséges <limits.h> már szerepel benne:

int checked_add(int a, int b, int *out)
{
    if (b > 0 && a > INT_MAX - b)
        return 0;

    if (b < 0 && a < INT_MIN - b)
        return 0;

    *out = a + b;
    return 1;
}

Pozitív b esetén az INT_MAX - b, negatív b esetén az INT_MIN - b ábrázolható. A rövidzáras kiértékelés biztosítja, hogy csak a megfelelő kivonás történjen meg. Az összeadásig eljutva az eredmény már bizonyítottan tartományon belüli.

Az out kölcsönzött pointer; sikerágon élő, írható int objektumot kell jelölnie. A függvény nem őrzi meg. Ellenőrzési esetek: (INT_MAX, 1) és (INT_MIN, -1) sikertelen; (INT_MAX, -1), (INT_MIN, 1) és (0, 0) sikeres. Hibánál egy előzetesen beállított célértéknek változatlannak kell maradnia.

14.3.8.3 Az átfedés diagnózisa

A módosított céltartomány és az olvasott forrástartomány átfed: ugyanazokat az elemeket a két, egymástól független restrict hozzáférési útvonalon érjük el. A hívás ezért megsérti a szerződést; nincs garantált eredménye.

A restrict nélküli soros ciklus eredménye:

$$[1,\ 3,\ 6,\ 10,\ 15].$$

Minden iteráció az előző iteráció által már módosított forráselemet olvassa. Ez valódi ciklusfüggőség. Ellenőrzéskor ezt a definiált változatot kell a soros szemantikával összevetni; az UB-s változat „helyesnek látszó” eredménye és optimalizálási jelentése nem bizonyít semmit a hívás érvényességéről.

14.3.9 Összefoglaló

Az optimalizálás a definiált viselkedés megőrzésére épül, nem a forrássorok megőrzésére. Az aliasing-, restrict-, overflow- és bounds-szabályok ezért közvetlenül befolyásolják a keletkező gépi kódot. Az LTO több információt, a PGO költségbecslést, az optimization remark diagnosztikát ad. Egyik sem helyettesíti az érvényes nyelvi szerződést, és a megfigyelt futási eredmény sem írhatja azt felül.