6.3 Ciklusszervezés: while/for/do-while mintázatok assemblyben

6.3.1 Miért számít a ciklus szerkezete?

Egy puffer feldolgozásakor nemcsak az fontos, mit végez a ciklusmag, hanem az is, hogy üres bemenetnél végrehajtódik-e, és egy kihagyott elem után biztosan továbblép-e az index. Assemblyben ezeket nem a C ciklusszintaxisa biztosítja: nekünk kell megfelelő helyre tenni az ellenőrzést, a léptetést és az ugrásokat.

Az if/else és switch leképezésénél megismert elágazásokból most ismétlődő vezérlési utakat építünk. Minden alábbi assemblyutasítás és regiszter az A64 ISA, AArch64, I. rész környezetéhez tartozik. A cél ARMv8-A, little-endian Linux-program, elsődlegesen qemu-aarch64 alatt.

Ciklusnak (loop) olyan vezérlési szerkezetet nevezünk, amely egy feltételtől függően ismételten végrehajt egy utasítássorozatot. A64-en nincs külön „C for” vagy „C while” utasítás: összehasonlítások, elágazások és visszafelé vezető vezérlési élek valósítják meg őket.

6.3.2 A három ciklusforma vezérlési mintája

Az alábbi C-részletekben n előjel nélküli, uint64_t típusú bemenet. A példákban az első n pozitív egész összegét számítjuk.

/* Szemantikai minták: n már rendelkezésre áll. */
uint64_t i = 1, sw = 0;
while (i <= n) {
    sw += i;
    ++i;
}

uint64_t sf = 0;
for (uint64_t j = 1; j <= n; ++j) {
    sf += j;
}

uint64_t k = 1, sd = 0;
do {
    sd += k;
    ++k;
} while (k <= n);

6.3.2.1 while: feltétel elöl

A feltétel-elöl tesztelő ciklus (pre-test loop) útvonala:

1. Inicializálás.
2. Feltételvizsgálat.
3. Hamis feltételnél kilépés.
4. Ciklusmag.
5. Visszaugrás a feltételvizsgálathoz.

Az A64-változatban az előjel nélküli i <= n feltétel tagadásával célszerű kilépni: CMP Xi, Xn után B.HI jelenti az előjel nélküli i > n esetet. Ha nincs elágazás, a végrehajtás a ciklusmaggal folytatódik.

n = 0 esetén az első vizsgálat már hamis C-feltételt talál, ezért a ciklusmag egyszer sem fut le.

6.3.2.2 for: inicializálás, feltétel, lépés

A for három fejlécösszetevőjét külön vezérlési pontként kezeljük:

A fenti összegző for az alábbi while mintára vezethető vissza:

uint64_t sf = 0;
{
    uint64_t j = 1;
    while (j <= n) {
        sf += j;
        ++j;
    }
}

A külső blokk a C-változó hatókörét is megőrzi. A64-en a két összegző ciklus utasításszerkezete akár teljesen azonos lehet.

Fontos korlát: ez az egyszerű átírás csak akkor kezeli helyesen a continue működését, ha azt is átalakítjuk. A for ciklusban a continue a lépéshez vezet; a while ciklusban közvetlenül a feltételhez.

6.3.2.3 do-while: feltétel hátul

A feltétel-hátul tesztelő ciklus (post-test loop) útvonala:

1. Inicializálás.
2. Ciklusmag.
3. Feltételvizsgálat.
4. Igaz feltételnél visszaugrás a ciklusmaghoz.

Az első belépés előtt nincs vizsgálat, ezért a ciklusmag legalább egyszer lefut. A példában n = 0 mellett is hozzáadjuk az első értéket: az eredmény 1, a számláló pedig 2.

A do-while tehát nem általában ekvivalens a while ciklussal. A példabeli összegzésnél n >= 1 esetén azonos az eredményük; az üres tartományhoz előzetes őrfeltétel (guard) kellene.

6.3.3 break és continue: pontos ugráscélok

A64-en mindkettő megvalósítható feltétel nélküli B elágazással. Nem az utasítás különbözik, hanem a célpont.

Egymásba ágyazott ciklusoknál a cél az adott C-utasítás által érintett legbelső szerkezethez tartozik. A C-ben switch is fogadhat break utasítást; ezért mindig a tényleges vezérlési célt kell kijelölni, nem pusztán a legközelebbi assemblycímkét.

6.3.4 Ciklusinvariáns: mit tudunk minden visszaérkezéskor?

A ciklusinvariáns (loop invariant) olyan állítás, amely egy kijelölt vezérlési pont minden elérésekor igaz. Nem feltétlenül igaz a ciklusmag minden köztes utasítása után.

Az összegző while feltételvizsgálati pontján legyen:

$$s=\frac{(i-1)i}{2}, \qquad 1\leq i\leq n+1.$$

Itt s, i és n dimenzió nélküli egész értékek. A laborban feltételezzük, hogy $0\leq n\leq255$, így sem a számláló, sem az összeg nem fordul át a 64 bites tartomány határán.

Levezetés:

• Inicializálás: i = 1, s = 0, tehát az állítás teljesül.
• Megőrzés: a ciklusmag előbb hozzáadja i értékét: $s'=(i-1)i/2+i=i(i+1)/2$. Ezután i' = i + 1, ezért ismét $s'=(i'-1)i'/2$.
• Kilépés: az első hamis feltételnél i = n + 1, ezért $s=n(n+1)/2$.

A helyes eredmény indoklása önmagában még nem mutatja a befejeződést. Ehhez megfigyeljük, hogy minden végrehajtott iteráció egyet csökkent a hátralévő elemek számán, azaz n - i + 1 értékén.

A bemeneti korlát lényeges: teljes uint64_t tartományban például n = UINT64_MAX mellett a számláló átfordulása megakadályozná a várt kilépést.

6.3.5 Kidolgozott példa: három összegzés és egy megszakított ciklus

Munkakönyvtár: ~/arm-labor/a64/a020/ — 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/a020
cd ~/arm-labor/a64/a020

A teljes program n = 5 mellett lefuttatja a három összegzést. Negyedikként ezt a C-mintát valósítja meg:

uint64_t filtered = 0;
for (uint64_t j = 1; j <= n; ++j) {
    if (j == 2)
        continue;
    if (j == 4)
        break;
    filtered += j;
}

A negyedik eredmény 1 + 3 = 4: a 2 kimarad, a 4 feldolgozása előtt pedig kilépünk.

Mentsük a következőt lab-loops.s néven. Az assemblyblokk A64 ISA-környezetű; a ponttal kezdődő direktívák GNU as, AArch64 ELF-direktívák, nem végrehajtott utasítások.

// A64 ISA, ARMv8-A, Linux, little-endian.
.text
.global _start
.global lab_done
.type _start, %function

_start:
    movz x9, #5                  // n, előjel nélküli 64 bit

    // while: X1 = i, X2 = összeg
    movz x1, #1
    movz x2, #0
.Lwhile_test:
    cmp  x1, x9
    b.hi .Lwhile_end
    add  x2, x2, x1
    add  x1, x1, #1
    b    .Lwhile_test
.Lwhile_end:

    // for: X3 = j, X4 = összeg
    movz x3, #1                  // inicializálás
    movz x4, #0
.Lfor_test:
    cmp  x3, x9                  // feltétel
    b.hi .Lfor_end
    add  x4, x4, x3              // ciklusmag
.Lfor_step:
    add  x3, x3, #1              // lépés
    b    .Lfor_test
.Lfor_end:

    // do-while: X5 = k, X6 = összeg
    movz x5, #1
    movz x6, #0
.Ldo_body:
    add  x6, x6, x5
    add  x5, x5, #1
    cmp  x5, x9
    b.ls .Ldo_body               // előjel nélküli <=

    // for break/continue használatával:
    // X7 = j, X10 = szűrt összeg
    movz x7, #1
    movz x10, #0
lab_filter_test:
    cmp  x7, x9
    b.hi .Lfilter_end

    cmp  x7, #2
    b.eq .Lfilter_step           // continue: nem a teszthez!
    cmp  x7, #4
    b.eq .Lfilter_end            // break

    add  x10, x10, x7
.Lfilter_step:
    add  x7, x7, #1
    b    lab_filter_test
.Lfilter_end:

lab_done:
    // Az n = 5 teszteset összegeredményeinek ellenőrzése.
    cmp  x2, #15
    b.ne .Lfail
    cmp  x4, x2
    b.ne .Lfail
    cmp  x6, x2
    b.ne .Lfail
    cmp  x10, #4
    b.ne .Lfail

    movz w0, #0                  // sikeres ellenőrzés
    b    .Lexit
.Lfail:
    movz w0, #1                  // eltérő eredmény
.Lexit:
    movz w8, #93                 // Linux AArch64 exit
    svc  #0

.size _start, .-_start
.section .note.GNU-stack,"",%progbits

Az A64-példa kódolási korlátai:

• A MOVZ 16 bites közvetlen értéket (immediate) helyez el egy 16 bites sávban. X-regiszternél a választható eltolás 0, 16, 32 vagy 48 bit; W-regiszternél 0 vagy 16. Itt minden eltolás 0.
• Az ADD és a CMP használt immediate-alakja 12 bites előjel nélküli értéket fogad, opcionális 12 bites balra tolással. Itt minden konstans eltolás nélkül kódolható.
• A B címkére mutató eltolása 26 bites előjeles, a B.cond eltolása 19 bites előjeles mező, mindkettő 4 bájtos léptékkel. A rövid program minden célpontja elérhető.
• Az SVC immediate-mezője 16 bites; a Linux-hívás itt SVC #0.

Az A64 CMP állítja az NZCV jelzőket, a következő feltételes elágazás pedig ezeket olvassa. A ciklusfeltételeknél az előjel nélküli C-típushoz ezért B.HI, illetve B.LS tartozik, nem az előjeles B.GT és B.LE.

6.3.6 Összeállítás, futtatás és állapotellenőrzés

A következő parancsok Ubuntu 24.04 x86_64 hoston, a könyv cross-eszközláncával használhatók.

# Target: qemu-user, AArch64 Linux, ARMv8-A, little-endian.
aarch64-linux-gnu-as -g -march=armv8-a -EL \
    -o lab-loops.o lab-loops.s

aarch64-linux-gnu-ld -m aarch64linux -e _start \
    -o lab-loops lab-loops.o

aarch64-linux-gnu-objdump -d lab-loops

qemu-aarch64 ./lab-loops
printf 'kilepesi_allapot=%d\n' "$?"

Várt, nem itt mért eredmény: nincs programkimenet, a shell kilepesi_allapot=0 sort ír. Az 1 állapot azt jelzi, hogy valamelyik összeg eltér az n = 5 tesztesethez rögzített értéktől. Ez az önellenőrzés nem általános bemeneti tesztkeret.

Az A64-regiszterek várt állapota a lab_done címke első utasítása előtt:

Az első terminálban indítsuk a GDB-kapcsolatra váró emulációt:

# Target: qemu-user; a folyamat a debuggerre vár.
qemu-aarch64 -g 1234 ./lab-loops

A második terminálban:

# Target: a fenti qemu-user folyamat; várt állapot a táblázatban.
gdb-multiarch -q ./lab-loops \
    -ex 'target remote localhost:1234' \
    -ex 'break lab_done' \
    -ex 'continue' \
    -ex 'info registers x9 x1 x2 x3 x4 x5 x6 x7 x10'

A GDB gyakran hexadecimálisan is megjeleníti az értékeket: 15 = 0xf. A continue debuggerparanccsal az ellenőrzés és a kilépés is végrehajtható.

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

Egy iterációval kevesebb. Ha az A64 B.HI helyett B.HS szerepel a felső tesztben, akkor már i == n esetén kilépünk. n = 5 mellett az összeg 10, nem 15. Hipotézis: hibás határreláció. Az objdump kimenetében ellenőrizzük az elágazást, majd kizárólag a feltételkódot javítsuk.

Végtelen ciklus a continue miatt. Ha a szűrt ciklus 2 esetén közvetlenül lab_filter_test címkére ugrik, X7 változatlanul 2 marad. A következő kör ugyanoda jut. GDB-ben megszakítás után az ismétlődő utasításút és X7 értéke igazolja a hipotézist.

Az üres bemenetet nem teszteljük. n = 1 mellett mindhárom összegzés 1 eredményt ad, tehát ez nem különbözteti meg a belépési szabályokat. n = 0 mellett viszont a while és a for összege 0, a do-while összege 1.

Más összehasonlítás jelzőit használjuk. A feltételes A64-elágazás nem „emlékszik” a C-kifejezésre: az aktuális NZCV-t használja. Ha a megfelelő CMP után más jelzőmódosító utasítás kerül, a vizsgált feltétel megváltozhat. Az utasításszintű léptetés ezt láthatóvá teszi.

6.3.8 Feladatok

1. (magyarázó, középszint — cél: megértés-ellenőrzés) Adjuk meg a három összegzés ciklusmagjának végrehajtásszámát és eredményét n = 0, 1, illetve 5 mellett. Miért nem elég a for szöveges átírása while alakra, ha a ciklusmag continue utasítást tartalmaz?

2. (implementációs, középszint — cél: rutinépítés) Cseréljük le a labor első, while szervezésű összegzését előzetes őrfeltétellel ellátott, feltétel-hátul tesztelő változatra. X1 és X2 végállapota minden 0 <= n <= 255 bemenetre maradjon azonos az eredetivel.

3. (hibakeresési, középszint — cél: megértés-ellenőrzés) A szűrt ciklus continue ágának célját szándékosan módosítsuk lab_filter_test címkére. Állítsuk össze újra a programot, és GDB-vel azonosítsuk a befejeződést megakadályozó állapotot. Egyetlen módosítással javítsuk, majd ellenőrizzük ismét a kilépési állapotot.

6.3.9 Megoldások

1. megoldás — Segítség. Kövesd külön-külön a három ciklus számlálóját n=0-ra — melyik fut le legalább egyszer akkor is, ha a feltétel már a belépéskor hamis? A continue/for kérdéshez nézd meg, hova ugrik a for fejlécének “lépés” része a while-átiratban.

1. megoldás — Teljes megoldás. A levezetett eredmények:

A for ciklusban a continue végrehajtja a fejléc lépését is. A naiv while-átiratban átugraná a ciklusmag végére helyezett léptetést. Az ekvivalenciához ezt az útvonalat külön meg kell őrizni.

2. megoldás — Segítség. Illessz egy cmp/b.hi párt a ciklusmag elé, amely n=0 esetén közvetlenül a vég címkére ugrik, mielőtt a do-while-stílusú test lefutna.

2. megoldás — Teljes megoldás. Az első összegző blokk helyére az alábbi A64-részlet tehető:

// A64 ISA; a lab-loops.s első ciklusának helyettesítő blokkja.
    movz x1, #1
    movz x2, #0
    cmp  x1, x9
    b.hi .Lguarded_end

.Lguarded_body:
    add  x2, x2, x1
    add  x1, x1, #1
    cmp  x1, x9
    b.ls .Lguarded_body
.Lguarded_end:

Az őrfeltétel üres tartománynál megakadályozza az első végrehajtást. Egyébként ugyanazokat az értékeket adjuk össze, ugyanannyi léptetéssel. Az eredeti buildparancsokkal n = 5 mellett továbbra is 0 a várt kilépési állapot.

Ha a bemenetet 0 értékre módosítjuk, a lab_done ponton X1 várt értéke 1, X2 értéke 0. A program változatlan, n = 5 értékre rögzített végellenőrzése ekkor szándékosan hibát jelez.

3. megoldás — Segítség. Tegyél töréspontot lab_filter_test-re, és figyeld X7-et egymás utáni megállásokkor — ha ugyanaz az érték ismétlődik, a léptetés nem fut le a continue ágon.

3. megoldás — Teljes megoldás. A hibás programban X7 eléri a 2 értéket, majd a léptetést megkerülve visszaugrik a teszthez. GDB-ben a lab_filter_test töréspont ismételt elérésekor X7 tartósan 2; X10 már 1.

A javítás: a B.EQ célja ismét .Lfilter_step legyen. Így a kihagyott elem után X7 3 lesz, később pedig 4 mellett a break kiléptet. Újraösszeállítás után a várt kilépési állapot 0.

6.3.10 Rövid összefoglaló

A C ciklusformák A64-en összehasonlításokból, elágazásokból és gondosan kijelölt vezérlési pontokból állnak. A while belépés előtt ellenőriz, a do-while csak a ciklusmag után, ezért az utóbbi legalább egyszer végrehajtódik. A for inicializálásra, feltételre és lépésre bontható; while alakra visszavezetésekor a continue útvonalát is meg kell őrizni. A helyességet nemcsak a végső összeg, hanem a számlálók és a határesetek vizsgálata is támogatja. A ciklusinvariáns az állapot és az elvárt eredmény kapcsolatát teszi követhetővé. A befejeződést külön indokoljuk, figyelve a számláló átfordulására.

• Ciklusinvariáns: kijelölt cikluspontban mindig igaz állítás.
• Őrfeltétel: a ciklusmag első végrehajtását engedélyező vizsgálat.
• Lépéspont: a for normál és continue útvonalának közös léptetési helye.

6.3.11 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.

• Arm A-profile architektúra-dokumentáció: DDI0487; A64 összehasonlítások, feltételkódok és elágazáskódolások. 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.
• GNU assembler kézikönyv: AArch64 szintaxis, címkék és ELF-direktívák. Ellenőrizve: a jelenlegi kiadás binutils 2.47.
• GNU GDB kézikönyv: távoli hibakeresés, töréspontok és regisztervizsgálat. Ellenőrizve, de verzió-megjegyzéssel: a „current” fejlesztői pillanatkép (közös verziókorlát).

Ellenőrzési hiányok, amelyek a fenti ellenőrzés után is ténylegesen fennmaradnak: a program összeállítása és QEMU-futtatása itt nem történt meg; minden eredmény levezetett, várt állapot. Az Ubuntu 24.04-en telepített konkrét eszközverziókkal a laborban kell ellenőrizni a buildet és a debuggerkapcsolatot. Teljesítménymérést nem végeztünk.