Önálló laboratórium beszámoló
Dolgozat címe: Elágazás és ciklus keresés fordítóprogram köztes reprezentációjában Konzulens(ek) neve: Feldhoffer Gergely (Külső cég neve: StreamNovation Ltd. címe: H-1083 Budapest, Práter utca 50/A, Hungary
A Hallgató a kitűzött feladatot megfelelő színvonalon és a kiírásnak megfelelően teljesítette
nem teljesítette
____________________________ Konzulens aláírása
Hallgató neve: Jani Mátyás Képzés: Mérnök Informatikus MSc Leadás dátuma: 2010. 12. 08.
Elágazás és ciklus keresés fordítóprogram köztes reprezentációjában Készítette: Jani Mátyás
Konzulens: Feldhoffer Gergely 2010
Tartalomjegyzék 1. A környezet.......................................................................................................................................4 1.1. A SIMD architektúra.................................................................................................................4 1.2. OpenCL környezet rövid bemutatása........................................................................................4 1.3. OpenCL példa...........................................................................................................................5 1.4. A feladat részletezése................................................................................................................6 2. Vezérlési szerkezetek........................................................................................................................7 2.1. Egyszerű utasítások, kifejezések...............................................................................................7 2.2. Szekvencia................................................................................................................................7 2.3. Feltétel nélküli vezérlésátadás..................................................................................................7 2.4. Elágazás....................................................................................................................................7 2.5. Esetkiválasztásos elágazás........................................................................................................7 2.6. Ciklusok....................................................................................................................................8 2.7. Szintaxisfa.................................................................................................................................8 3. Ciklusok, elágazások keresése..........................................................................................................8 3.1. Ciklusok keresése a vezérlésfolyam-gráfban............................................................................8 3.2. Elágazások keresése................................................................................................................10 4. Szintaxisfa felépítése, objektumhierarchia.....................................................................................12 4.1. virtual_node............................................................................................................................12 4.2. single.......................................................................................................................................12 4.3. sequence..................................................................................................................................12 4.4. branch......................................................................................................................................12 4.5. loop.........................................................................................................................................12 4.6. cfg...........................................................................................................................................13 4.7. vnlist........................................................................................................................................13 5. Példa futás......................................................................................................................................13 6. Összegzés, előfordult nehézségek..................................................................................................16 7. Köszönet.........................................................................................................................................17 8. Hivatkozások..................................................................................................................................18
3
1. A környezet A StreamNovation Ltd. cégnél egyik projektjébe, a Minotaurus fejlesztésébe kapcsolódtam be Önálló Laboratórium tárgyam keretében. Ez a projekt egy készülőben fordítóprogram plug-in ami azt teszi lehetővé, hogy egy adott program forráskódjának átírása nélkül felismerje azokat a részeket amiket (SIMD technológiával) párhuzamosítani lehet, és próbálja meg a fordítandó programot úgy áttranszformálni, hogy a generált program majd a párhuzamos futást lehetővé tevő OpenCL környezetben fusson. A Minotaurus szoftver a gcc fordítóprogramra épül, annak a kiterjesztése. A fordítandó programot a gcc egy köztes struktúrára fordítja a futtatható kód generálása előtt a több platform támogatása, modulárisabb felépítés illetve kód optimalizálások miatt. Ezt a köztes struktúrát GimpleGraph-nak hívják és ezt használja a Minotaurus a saját, OpenCL-es kód generálásához. A párhuzamosítható részek megtalálása sajnos nem elég, meg kell azt is vizsgálni, hogy vajon gyorsabb lesz-e a párhuzamosan futó program. Ehhez először meg kell érteni az OpenCL környezetet és a SIMD architektúra működési elvét.
1.1. A SIMD architektúra A SIMD rövidítés (Single Instruction Multiple Data) jelentése az, hogy a vezérlő egység egyetlen utasítást egyszerre több adaton végez párhuzamosan. Ehhez egyrészt szükség van több műveletvégrehajtó egységre, valamint több adatútra is, hogy el lehessen juttatni egyszerre az adatokat azokhoz. Az ilyen módon történő párhuzamosítást nevezik még adat párhuzamosításnak is. Ezek a módszerek eléggé érzékenyek az elágazásra: ha egy műveletet csak feltételhez kötötten kell végrehajtani és az adott feltétel nem mindegyik szálon teljesül, akkor csökken az egyszerre futtatható szálak száma, hiszen egyszerre csak egy utasítást lehet végrehajtani és amelyik szálon nem teljesül a feltétel, azokat a szálakat nem lehet a többivel egy időben futtatni. Nagyszerűen alkalmazhatók azonban vektoros számolásokra (amikor a vektor összes komponensével ugyanazt kell végrehajtani), ezért hívják sokszor az ilyen módon működő egységeket vektorprocesszoroknak. Manapság eléggé elterjedtek az ilyen egységek, a központi processzorokban is találhatóak ilyen módon működő alrészek (pl. MMX, SSE utasítások). Van még több ilyen módon működő eszköz, például ilyenek a videó kártyák is. Az OpenCL környezetben lehetőség van a különböző ilyen típusú eszközök programozására egységes felületen keresztül.
1.2. OpenCL környezet rövid bemutatása Az OpenCL az Open Computing Language rövidítése, és egy nyílt, szabadon hozzáférhető szabvány, párhuzamos programozásra. Hasonlóan a 3.0-ás OpenGL-hez, az OpenCL API-t is a Khronos Group fejlesztette ki, aminek a tagja több neves hardver- és szoftvergyártó cég. Nagy előnye, hogy platformfüggetlen, hardver és szoftver tekintetben is. Ennek ellenére – mivel nem régen jelent csak meg – jelenleg nem működik minden hardveren, de a támogatott eszközök listája növekszik. Az OpenCL segítségével viszonylag könnyen kihasználhatjuk a grafikus gyorsítókártyánkon lévő shader
4
processzorok nyújtotta teljesítményt: támogatja az adat és a feladat párhuzamosítást is, könnyen lehet a legtöbb c-s adattípust (tömböket, struktúrákat is) be- illetve kimeneti paraméterként használni, lényegében a GLSL-t nehézkessé tevő problémák megszűntek vele. Az OpenCL platform egy host-ból és egy vagy több hozzá kapcsolódó „Compute Device”-ból (számítási eszközből) áll (ilyen például a videó kártya) [1]. A host az egy sima, operációs rendszeren futó alkalmazás, az adja ki az utasítást a számítási eszközöknek. A számítási eszköz egy vagy több „Compute Unit”-ot (számítási egységet) tartalmaz, melyekkel SIMD (Single Instruction Multiple Data) vagy SPMD (Single Program Multiple Data) módon tudnak több feladatot („Processing Element”) párhuzamosan futtatni.
1.1. ábra: OpenCL platform modell [1] Mivel két különböző eszközből áll a platform ezért ezekhez külön kell megírni kódot. A host-on futó rész egy hagyományos módon, tetszőleges programozási nyelven megírt program, ezt indíthatjuk közvetlenül az operációs rendszerből és ez indíthatja el az OpenCL eszközön futó programrészeket, a kerneleket. A kerneleket a szabvány szerint a C nyelven lehet írni (C99, C nyelv '99-ben történt kiterjesztésével), néhány egyéb kiegészítéssel (pl. vektorműveletek), valamint néhány megszorítással (nincs rekurzió, dinamikus memória allokáció) [1].
1.3. OpenCL példa Az OpenCL futtatási modell és a hagyományos programozás közötti különbség az alábbi példa kódrészleteken látható: // Skalárral való szorzás for (int xx = 0; xx<XSIZE-1; xx=xx+1) { vec[xx] = cc*vec[xx]; }
1.1. kódrészlet: Hagyományos programozás Az algoritmus egy vektort szoroz meg egy számmal (minden koordinátát megszorozza cc-vel).
5
// Itt nincs ciklus, csak egy darab szorzás kernel void scalar_mult(global float* vec, global float cc) { unsigned int xx = (int)get_global_id(0); vec[xx]=cc*vec[xx]; }
1.2. kódrészlet: Az OpenCL-es kernel, ez fut több példányban az eszközön
clSetKernelArg(ckMyKernel, 0, sizeof(cl_mem), (void *) &vec); clSetKernelArg(ckMyKernel, 1, sizeof(cl_float), (void *) &cc); clEnqueueNDRangeKernel(cqCommandQue, ckMyKernel, 1, NULL, globalWorkSize, localWorkSize, 0, NULL, NULL);
1.3. kódrészlet: A fenti kernelt indító host programrész A fenti példában látható, hogy a műveletet hagyományos módon egy ciklusban oldhatjuk meg, OpenCL környezetben viszont a ciklus eltűnik, hiszen a ciklus egymás után történő iterálása helyett a sok processzoron egymással párhuzamosan futnak ezek a szorzás műveletek. A host program először beállítja a kernel függvény paramétereit a clSetKernelArg utasítással, majd elindítja a kernel példányait clEnqueueNDRangeKernel hívással. Itt a globalWorkSize illetve localWorkSize változók tartalmaznak információt arra vonatkozólag, hogy hány példány fusson. Ezután a futó kernelek (work-item-ek) külön indexet kapnak, így le lehet kérni az eszközön futó kernelpéldányokban az indexüket (get_global_id(0)). Ezzel már tudjuk indexelni a tömböt úgy, hogy két futó szál ugyanazt az elemet ne próbálja meg elérni.
1.4. A feladat részletezése Az OpenCL kódot a Minotaurus a gcc köztes reprezentációjából, a gimplegraph-ból állítja elő, amiben már nem szerepelnek a magasabb szintű vezérlési struktúrák. Az egymás után sorban végrehajtható kódrészeket (szekvenciákat) úgynevezett basicblock-okban tárolja. Ezeknek van egy azonosítója (basicblock_id), majd tartalmazza egy assembly-hez hasonló, de nem harver specifikus nyelven az egyes utasításokat [2]. A vezérlésfolyamot basicblock-ok egymásra következése adja: minden basicblock végén jelezve van, hogy melyik basicblock következik utána (succ_bb basicblock_id). Elágazás esetén a basicblock tartalmaz egy branch nevű mezőt, ebből derül ki a feltétel, valamint az, hogy igaz/hamis feltétel esetén melyik a következő basicblock.
Az elágazás basicblock-jának végén ugyanúgy megtalálható az, hogy melyik
basicblock-ok követik (succ_bb basicblock_id1 basicblock_id2), de itt nincs feltüntetve az, hogy melyik az igaz és melyik a hamis ág. Ez redundáns információ, azonban megkönnyíti a feldolgozást. A ciklusok csak a vezérlésfolyamban található irányított körökből derül ki, tehát ezeken a rákövetkezés információkon kívül
6
semmi nem utal rájuk. Feladatom a ciklusok és elágazások felderítése volt ilyen gimplagraph struktúrában. A feladatom szükségességét két dolog is indokolta. Az egyik ok, amiért szükség volt erre, az az, hogy bár az OpenCL szabvány nem tiltja meg a feltétel nélküli vezérlésátadásokat (goto), viszont néhány megvalósításból ezek hiányoznak. Emiatt sajnos a Minotaurus által generált kód nem tartalmazhatna ilyen vezérlésátadást. A másik ok a párhuzamosítható részek felfedezése: általában azok a ciklusok, amiknek az egymás utáni lefutásait nem befolyásolják egymást, nincs adatfüggőség közöttük, akkor azokat párhuzamosan is végre lehet hajtani. A ciklusok és elágazások megtalálása mellett feladatom volt ezek helyzetének és egymásba ágyazásának vizsgálatára is, tehát lényegében egy szintaxisfát kellett építenem belőlük, lényegében a decompilerek (lefordított kódból készít forráskódot) által megvalósított feladatok egy részét kellett elkészítenem.
2. Vezérlési szerkezetek A gimplegraph feldolgozásához szükség volt a vezérlési szerkezetek ismeretére. Ezek adják meg a program vázát. A vezérlési szerkezetek általában utasítások kombinációja, amelyek maguk is összetett utasításoknak számítanak, így egymásba lehet őket ágyazni [3]. Az alábbiakban bemutatom az egyes vezérlési szerkezeteket, kezdve az egyszerű utasításokkal, majd utána az összetett utasítások jönnek.
2.1. Egyszerű utasítások, kifejezések Két különböző dolognak számíthatnak, mert a kifejezésnek értéke is van, de most jelen esetben fölösleges megkülönböztetni ezeket. Ilyenek például az értékadás, az összeadás, stb. Ezeknek a kombinációjából, értéktől függő végrehajtásukból összetett utasításokat lehet létrehozni.
2.2. Szekvencia Utasítások sorozata, amiket egymás után sorrendben hajt végre a program.
2.3. Feltétel nélküli vezérlésátadás Egy adott utasításról egy tetszőleges, címkével ellátott másik utasításra ugorhat. A program végrehajtása onnan folytatódik. Általában a „goto” kulcsszó használatos a legtöbb nyelven erre. Használata sokszor átláthatatlan programhoz vezethet, ezért legtöbben inkább kerülik.
2.4. Elágazás Egy adott feltétel értékétől függően (igaz/hamis) adott utasítás(ok) végrehajtása.
2.5. Esetkiválasztásos elágazás Egy (nem feltétlen logikai) kifejezés értékétől függően adott utasítás(ok) végrehajtása. C nyelveken az egymás utáni ágak „egymásra folyhatnak”, azaz a kifejezés értékétől függően egy adott utasítást hajtunk végre, majd annak lefutása után, ha annak a végén nincs „break” kulcsszó, akkor a forráskódban rá következő „ágat” (kifejezés másik értékéhez tartozó utasítást) is végrehajtja a program.
7
2.6. Ciklusok Utasítás(ok) – feltételtől függő – ismételt végrehajtása. Két alapvető típusa van, attól függően, hogy a vezérlés hol hagyhatja el. Az elől tesztelős ciklus először ellenőrzi a feltételt, majd ha igaz, végrehajtja a ciklusmagot (utasítást). Amennyiben a végére ért, megint ellenőrzi a feltételt, és ha igaz, megint végrehajtja a ciklusmagot. Akkor lép ki a ciklusból, ha egy ciklusmag lefutás után nem lesz igaz a feltétel. A hátultesztelős először lefuttatja a ciklusmagot és csak utána ellenőrzi a feltételt, de ezt leszámítva ugyanúgy működik. A ciklusok tartalmazhatnak egyéb vezérlésre utaló kulcsszavakat, például a C nyelvben a „break” kulcsszó használatával a ciklusmagból is ki lehet léptetni a vezérlést a ciklusból, a „continue”-val pedig a ciklusmag közepéből újra az elejére lehet jutni úgy, hogy az alatta található utasítások nem futnak le.
2.7. Szintaxisfa A vezérlési szerkezetek egymásba ágyazásuk folytán egy fában reprezentálhatók. Ennek a csomópontjaiban az egyes összetett utasítások, leveleiben az egyszerű utasítások találhatók.
3. Ciklusok, elágazások keresése A vezérlési szerkezetek kereséséhez a vezérlésfolyam-gráf (angolul Control Flow Graph, CFG) adhat segítséget, ezért először azt kellett létrehozni a gimplegraph-ból. Ez egy olyan irányított gráf, aminek a csúcsaiban az egyes utasítások találhatók, az élek pedig a rá következő utasításokra mutatnak. A gimplegraph-ban az egyes basicblock-okban az utasítások egymás után hajtódnak végre, így ezeket az utasításokat nem kell külön csomópontokba helyezni, elég, ha az egész basicblock-ból csak egyetlen csomópont keletkezik, mert tudni fogjuk a belső vezérlési sorrendet. Ezek alapján a vezérlésfolyam-gráf csomópontjainak az egyes basicblock-okat feleltettem meg, éleknek pedig a basicblock-okban található információ alapján a basicblock-ok egymásra következését.
3.1. Ciklusok keresése a vezérlésfolyam-gráfban A ciklusokat a gráfban az irányított körök jelzik. Ezeknek a megtalálására az algoritmusom a következő: 1. az belépési pontot beteszem egy S verembe 2. létrehozok egy halmazt (L) a már látogatott elemeknek 3. létrehozok egy listát (P) a jelenlegi utasítás útvonalnak (belépési pontból hogyan jutottam el az aktuális elemig) 4. Amíg S nem üres: 1. kiveszem S tetejéről a következő elemet, N-ként hivatkozom rá ezentúl 2. beleteszem L-be N-t 3. ha N megtalálható P-ben, akkor törlöm P-ből N-et és az utána következő elemeket (P-ben minden csak egyszer fordulhat elő elem) 4. elteszem P-be N-et 5. ha van olyan N gyerekei között olyan, hogy benne van P-ben, akkor találtam egy ciklust,
8
aminek a belépési pontja az a gyerek elem lesz (ez mindenképpen benne lesz L-ben) 6. beleteszem S-be N azon gyerekeit, amik nincsenek benne L-ben Ezzel meg lehet találni a ciklusok belépési pontját (az a basicblock a ciklusban, amihez először jut el a vezérlés – erre ugrik vissza a vezérlés a ciklus végén) valamint azokat a csomópontokat amik visszavezetnek a belépési pontokra (ciklus vége, vagy „continue”, ezentúl visszatérési pontnak hívom őket). A ciklusok egymásba ágyazásához szükség van még megtalálni, hogy melyik basicblock-ok tartoznak a ciklusmaghoz vagy a feltételhez, és melyek amik nem. Azokat a basicblock-okat veszem ciklus belső utasításainak, amelyekből újra vissza lehet jutni egy irányított úton a ciklus visszatérési pontjaihoz úgy, hogy az út nem érinti a ciklus belépési pontját. Ez a definíció nem tartalmaz minden elemet amire a forráskód alapján gondolhatnánk, hiszen egy olyan ciklusmagot feltételezve, amelyben van egy elágazás, aminek egyik ágán „break”-el kilép a ciklus, azt az elágazás ágat a fenti definíció alapján nem veszem ciklusba tartozó utasításnak, a forráskódban viszont a cikluson belülre kell írni. Emiatt és egyéb problémák miatt egyelőre csak az egy kilépési illetve egy visszatérési pontot tartalmazó ciklusokkal foglalkoztam. Az algoritmus ami megtalálja a ciklus belső elemeit (a fenti definíció alapján): 1. L egy olyan halmaz, amibe a már látogatott elemeket teszem 2. S egy olyan verem, amibe a vizsgálandó elemeket teszem 3. beleteszem a ciklus visszatérési pontjait L-be és S-be 4. amíg S nem üres 1. kiveszem S legfelső elemét, legyen ez N 2. ha N nem a ciklus belépési pontja és nincs benne L-ben, akkor beteszem N-et L-be 3. ha N nem a ciklus belépési pontja, akkor beteszem N szüleit (vezérlési élek megfordítottját figyelembe véve a rákövetkezőket) S-be 4. ha N az egész függvény/program belépési pontja akkor hibás ciklust találtam és nem folytatom tovább az eljárást Az algoritmussal lényegében a ciklus visszatérési pontjaiból indulok visszafelé az éleken, és minden elemet beleteszem L-be, amíg a ciklus elejéhez nem érek. A futás után L-ben a ciklus (definícióm szerinti) belső elemei lesznek. Az utolsó pontban a hibás ciklus akkor léphet elő, ha úgy jutok vissza a függvény kezdőpontjába, hogy közben nem érintettem a ciklus kezdőpontját, ami csak abban az esetben lehetséges, ha a cikluson kívülről el lehet jutni a ciklus belsejébe, nem a ciklus belépési pontján keresztül. Ezzel az esettel nem foglalkozom, csak „goto”-val lehet kiváltani.
9
3.1. ábra. Ciklus CFG-je, aminek a belsejébe kívülről bekerülhet a vezérlés [4] Miután a ciklusokat megtalálom, az egymásba ágyazásukat vizsgáltam. Először sorba rendezem a ciklusokat a tartalmazott basicblock-ok száma szerint növekvő sorba, majd kivonom a legrövidebbet az összes többiből (kiveszem az elemeik közül a legrövidebb ciklus által is tartalmazott elemeket), és egy virtuális csomóponttal helyettesítem. Ezt ismételve az egyre több basicblock-ot tartalmazó ciklusok felé a végén az egymásba ágyazott ciklusoknál a belső ciklust mindig egy virtuális csomópont helyettesíti a külsőben. A sorba rendezést elég csak egyszer, az elején végrehajtani: amelyik ciklus az elején hosszabb volt mint a másik, az közben – hiába lett belőle kivéve akármennyi elem is belső ciklusainak helyettesítése folytán, soha nem lehet az elején nála rövidebb belsejében, akkor sem, ha közben rövidebb lett. A ciklusok vizsgálatánál még az elöl- vagy hátultesztelősség eldöntésére lehet szükség, ezt ugyan nem valósítottam meg, de lényegében abból lehet erre következtetni, hogy elöltesztelős esetén a kilépési pont és a belépési pont megegyezik.
3.2. Elágazások keresése Elágazások keresésének csak a ciklusok megtalálása után álltam neki. A ciklusok megtalálása után megvannak azok egymásba ágyazása is, azonban a főprogramban és a ciklusok belsejében még mindig egy vezérlésfolyam-gráf található. A ciklusokat (tehát irányított köröket) nem tartalmazó vezérlésfolyam gráfot megpróbáltam elágazásokká és szekvenciákká alakítani. Csak azzal az esettel foglalkoztam, amikor egy helyen kettéágazik a végrehajtási lánc, majd újra összeér, de kívülről más helyről egyik ágba sem érkezhet a vezérlés, csak a közös kettéágazó pontból kiindulva. A C nyelvben található „switch” esetkiválasztásos elágazás nem ilyen, így azzal nem foglalkoztam egyelőre.
10
3.2. ábra. C nyelven egy switch lehetséges CFG reprezentációja [4] Az algoritmusom két részből áll. Először megpróbálom az egész rész-vezérlésfolyam-gráfot szekvenciaként feldolgozni, meghívom a rész-gráf belépési pontjára a Szekvencia függvényt Szekvencia (kezdő elem): 1. legyen N a kezdő elem 2. L listában tárolom a szekvencia elemeit 3. kilep logikai változó hamis 4. amíg (nem kilep) és (N szülőinek /visszamenő éleken rákövetkezők/ száma <=1) 1. ha N gyerekeinek /előre menő éleken rákövetkezők/ száma > 0 1. amíg több mint egy gyereke van N-nek 1. N = Elágazás (N); 2. ha több mint egy gyerek van N-nek: beleteszem N-et L-be 2. beleteszem N-et L-be 3. N = N gyereke 2. különben ha N gyerekeinek száma = 0 1. beleteszem N-et L-be 2. kilep-et igaz-ra állítom 5. kiveszem L elemeit a vezérlésfolyam gráfból és helyükre beteszek egy virtuális csomópontot amiben eltárolom L elemeit: ez lesz a szekvencia 6. visszatérek a létrejött szekvenciával Elágazás(kezdő elem) 1. B tartalmazza majd a ciklus ágait (szekvenciák) 2. C a feltételt 3. ha a kezdő elemnek a gyerekeinek száma <2 1. visszatérek a kezdőelemmel 4. különben
11
1. C legyen a kezdő elem 2. végigiterálva a kezdő elem összes Ni gyerekén 1. Bi = Szekvencia(Ni); 3. kiveszem a vezérlésfolyam-gráfból Bi-ket és C-t, helyükre egy virtuális csomópontot helyezek, ez tartalmazza majd az elágazást 4. visszatérek ezzel az elágazással Lényegében ez a két függvény egymást hívja meg rekurzívan, és feldolgozza a gráfot. Eredményül egyetlen szekvenciát kapunk, amiben benne lesznek a ciklusok és elágazások, amelyekben újabb szekvenciák találhatók, stb. Sajnos megvan ennek az algoritmusnak az a hibája, hogy nem találja meg a nem átalakítható elemeket. Míg a ciklusok esetén meg tudtam mondani, hogy most ez a ciklus tényleg csak egy kilépési és egy visszatérési pontot tartalmaz, addig ennél nem tudom megmondani, hogy olyan gráfot dolgoztam-e föl amire jól működik az algoritmusom. Ezt problémát jelenleg még nem kezelem. Valószínűleg a végleges, használható megvalósítás előtt a vezérlésfolyamot átalakítja egy másik egység, olyan formájúra, hogy azon könnyen lefuttathatóak legyenek az algoritmusaim.
4. Szintaxisfa felépítése, objektumhierarchia Az egyes utasításokat illetve összetett utasításokat úgy kellett terveznem, hogy önmagukban tartalmazhassanak esetleg más utasításokat, ezért egy közös őstől származtatom őket (virtual_node). Minden vezérlési struktúra osztálya ebből származik.
4.1. virtual_node Van egy id nevű azonosítója (vnid típusú), valamint egy típusa amivel azonosítani lehet majd.
4.2. single Egyetlen basicblock-ot tartalmaz. A szintaxisfa leveleiben található, igazából eltárolja az eredeti gimplegraph-ban található azonosítóját a basicblocknak.
4.3. sequence Szekvencia. Egy listában tárolja a vnid azonosítókat, amiket sorban tartalmaz (ezek lehetnek single utasítások, de akár más is, pl. elágazás, másik szekvencia, stb.).
4.4. branch Elágazás. Egy külön mezőben eltárolja a feltételt tartalmazó virtual_node azonosítóját, valamint egy listában tartalmazza az egyes ágak vnid-jét (ezek mindenképpen szekvenciák jelenleg).
4.5. loop Ciklus, tartalmazza a feltétel vnid-jét valamint a ciklustörzs vnid-jét.
12
4.6. cfg A csomópontokat egy halmazban tárolja (vnid-k), valamint az irányított éleket is eltárolja egy olyan táblában, aminek egy csomópont (vnid) a kulcsa, az értéke pedig egy halmaz a rá következő elemek vnidjével.
4.7. vnlist Ez nem vezérlési szerkezetet tárol, hanem az egyes azonosítókhoz tartozó objektumokat tartalmazza, ezen keresztül lehet elérni azonosító alapján a megfelelő objektumot. A célja az, hogy egy olyan azonosítóval lehessen hivatkozni az egyes utasításokra, ami biztos, hogy egyedi (minden hozzáadásnál növelem az értékét), valamint a végén az egyes elemek felszabadítását egy objektum kezelje. Nyilván, ha a virtual_nodeok mutatóit tárolnám és id helyett azt használnám, az is egyedi lenne és megfelelne, kiírásnál jobban látszik, ha 0-től induló számokkal hivatkozok rájuk és nem memóriacímekkel, valamint így össze vannak gyűjtve egy helyre az objektumok, ha egyszerre kéne valami utasítást végrehajtani rajta. Persze lehet, hogy nem ez volt a jobb döntés, de ezt nyilván át lehet viszonylag egyszerűen írni.
5. Példa futás Az alábbi forráskódra futtattam a programot: transform_matrix_neigh
(in,m1,[wi](Nei in,int x, int y)->float{ float sum=0; float wsum=0; for(int i=0;i<wi;i++) for(int j=0;j<wi;j++) { float w=cos(i-neigh_size)*2+1+cos(j-neigh_size)*2+1; wsum += w; sum+=in(i,j)*w; if (i>j) { wsum += 0.1; } else { wsum -= 0.1; } } int i = x; if (i>5) { sum = i-1; for (int s = 0; s<10; s++) sum+=0.3*s; } else { sum = i+1; } return sum/wsum; });
5.1. kódrészlet: a programnak adott forráskód bemenet Ez a lambda függvény eredetileg a Julia-halmaz számításához lett létrehozva, a tesztelés miatt beletettem néhány elágazást és újabb ciklusokat. Ezek miatt végül is semmi értelmeset nem számol ki a függvény, de most nem is volt az cél. A gimplegraph-ból felépített vezérlésfolyam gráf (a csomópontokban a basicblock id-k láthatók, az 1.
13
mindig a belépési pont, valamint a kilépési pont (itt 16-os azonosítóval) össze van kötve mindig a belépési ponttal):
5.1. ábra. a tesztprogram vezérlésfolyam gráfja Látható, hogy az első ciklusba a 9-es azonosítójú basicblock-nál lép be, ami tartalmazza a 2. ciklust, ami a 7-es azonosítójú basicblock-nál kezdődik. Ez a kód elején található két „for” ciklus. A 3-as azonosítójú basicblocknál található a belső ciklusban látható elágazás, az első egymásbaágyazott ciklus után található elágazás pedig a 11-es azonosítónál található. Ennek egyik ágában, a 14-es azonosítójú basicblock-nál található a belső ciklus.
14
A visszaalakított szintaxisfa:
5.2. ábra. a vezérlésfolyam gráfból felírt szintaxisfa Az egybefüggő vonalon lévő nyilak a vezérlésfolyam irányát jelzik, a szaggatott vonal pedig egy vezérlési szerkezetet és az általa tartalmazott alrészeket köti össze. A szekvenciák téglalapokban, az elágazások rombuszokban, az elágazások törzse trapézban, a ciklusok megint csak téglalapban találhatóak. Az egyszerű basicblock-ok ellipszisekben találhatóak. A szögletes zárójelben a vnid azonosítók láthatóak, sima zárójelen belül pedig a basicblock-ok azonosítói. Látszik, hogy az egész függvénytörzs egy szekvenciaként írható fel, aminek az első eleme az 1. basicblock, stb. Az is látszik, hogy a kilépési pont a 16. basicblock, hiszen a nyilakat követve oda lehet eljutni és annak már nincs rákövetkezője.
15
Egyszerűbb azonban struktogram szerű kimenetet vizsgálni:
5.3. ábra. a példaprogram struktogramja, visszaalakítás után Szürkével a szekvenciákat, zölddel az elágazásokat sárgával a ciklusokat jeleztem. Az elágazásoknál a bal- illetve jobboldal a két ágat jelenti, a szekvenciánál az egymás alattiság jelenti a rákövetkezéseket. A basicblock-ok száma egyébként nem jelent sokat arra nézve, hogy hol található a kód érdemi része, hiszen a 9. 10. 17. basicblock majdnem üres, ellenben a 3. basicblock, amiben az elágazás feltétele is van, az tartalmazza az elágazásfeltétel előtt a lényegi számolós részt, a két egymásba ágyazott ciklus magját.
6. Összegzés, előfordult nehézségek A legtöbb gondom abból adódott munka során, hogy a programommal nem írhattam a képernyőre (stdout), csak egy string-et visszaadva azt a log fájlba írta a rendszer. Mivel a program egy lefutása fél percig tartott, így nehéz volt a hibákat megtalálni, mivel fél percet kellett várnom az eredményre. Mivel egymásba ágyazott rekurziót is használok az elágazások megtalálásánál, ezért előfordult, hogy egy hiba miatt végtelen ciklusba ütköztem. Ezt csak onnan tudtam megállapítani, hogy fél percnél tovább futott a tesztelésnél. Ilyenkor azonban a log fájlba sem került bele a kimenetem, mert kiírás előtt végtelen ciklusba esett már a program. Szerencsére végül sikerült megírnom, tehát a tárgyalt megkötések mellett képes a programom a gimplegraph köztes reprezentációt átalakítani szintaxisfába, melyből a kód generálása már nem okoz
16
nagyobb nehézségeket.
7. Köszönet Szeretnék köszönetet mondani Feldhoffer Gergelynek, akinek hasznos ötletei továbblendítették a munkámat ha elakadtam valahol. Ezenkívül a StreamNovation-ben dolgozóknak, akikkel közösen jó hangulatban lehetett végezni a munkát és szintén támogattak, segítettek, ha kérdésem volt.
17
8. Hivatkozások [1] Khronos OpenCL Working Group, OpenCL Specification [2] Richard M. Stallman and the GCC Developer Community, GCC internals, pp. 279-280 [3] Nyékyné Gaizler Judit, Programozási nyelvek, Kiskapu Kft., Budapest, 2003, pp. 61-101 [4] C. Cifuentes, „Reverse Compilation Techniques”, Ph. D. thesis at Queensland University of Technology, 1994, pp. 130-144
18
