Gyakorlattal kapcsolatos anyagok

Gyakorlat időpont
Csütörtök 12:30-14:00
Gyakorlat helyszín
D 4-202

1. Gyakorlat

Témakörök

  • Áttekintés: fordítók architektúrája, rekruzív leszállás, balrekurzió eliminálása, optimalizáció, ütemezés, instruction selection, regiszter allokáció, cpu architektúrák, out of order execution, SIMD, CPU pipeline

A diasor elérhető innen.

2. Gyakorlat

Témakörök

  • Típusrendszer feladatai
  • Köztes reprezentációk: ábrázolás, absztrakciós szint, felhasznált nevek
  • Absztrakt szintaxisfa, konkrét szintaxisfa, szintaxis DAG, control flow graph, függőségi gráf, hívási gráf, lineáris kód, static single-assignment forma
  • Clang által generált LLVM IR, mem2reg pass SSA-vá alakításhoz

3. Gyakorlat

Témakörök

  • Memória és a generált kód kapcsolata, aliasing, C strict aliasing szabályok következményei (http://blog.regehr.org/archives/1307), heap vs stack
  • Függvényekkel kapcsolatos kérdések, stack, aktivációs rekord, korutinok, rekurzió, visszatérési cím, végrekurzió, inline, virtuális hívások, devirtualizáció, paraméter átadási módok, miért érdemes valamit kis típusokat érték szerint?
  • Szimbólumtáblák reprezentációja, open addressing hash táblák, pointer/adat union (https://www.youtube.com/watch?v=vElZc6zSIXM)
  • Kód/ciklus verziózás
  • Késleltetések, amit mindenkinek tudni érdemes (https://gist.github.com/jboner/2841832)
  • Branch prediction segítése, likely, unlikely makrók
  • Könyv a párhuzamos programozásról, CPU architektúrákat jól leírja: https://www.kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook.html

4. Gyakorlat

Témakörök

  • Latency vs throughput, optimalizáció feladatai, honnan jönnek az optimalizációs lehetőségek?, deoptimalizáció
  • Optimalizáció hatóköre: lokális, regionális (ciklus, extended basic block, ...), globális, interprocedurális, fordítási egységek közötti
  • Dominál, poszt-dominál reláció
  • Local value numbering, nevek szerepe, kiegészítés kommutativitással, constant foldinggal, algebrai azonosságokkal, általánosítás extended basic blockokra
  • SSA előnyei value numbering algoritmusoknál, indirrekt értékadások (pointerek) hatása value numberingre

5. Gyakorlat

Témakörök

  • Fák kiegyensúlyozása: megfelelő részfák megtalálása (gyökerek), számozás, újraépítés
  • Loop unrolling hatása a többi optimalizációra
  • Liveness analízis, inicializálatlan változók megtalálása, dead store-ok megtalálása, SSA-nál fölösleges fi csúcsok eliminálása, regiszter allokációnál felhasználás
  • Data flow egyenletrendszerek felírása, fix-pont iterációs megoldásuk
  • Liveness analízis és globálisok, pointerek. Data flow analízis és a lehetetlen útvonalak.
  • Basic blockok sorrendjének meghatározása (profile vagy statikus becslés alapján)

6. Gyakorlat

Témakörök

  • Inteprocedurális optimalizálások
  • Inlining, "inline" kulcsszó C++-ban, outlining, miért nem optimális a bottum up módszer? (pl.: predikált algoritmusok)
  • Függvények sorrendjének meghatározása kódgeneráláskor
  • Dominancia halmazok számolása
  • Gráfbejárások: preorder, postorder, reverse postorder, szélességi
  • Backward vs forward dataflow problémák, SSA konstruálás, Dominance Frontier számolás, IDOM, Dominator tree.

7. Gyakorlat

Témakörök

  • Javítások a 6. gyakorlathoz, Maximal SSA, Semi pruned SSA, Pruned SSA, Minimal SSA, megkonstruálásuk, Reaching definition analízis, globális nevek.

8. Gyakorlat

Témakörök

  • Phi csúcsok eliminálása, kritikus él fogalma, transform + cleanup paradigma
  • Sparse simple constant propagation, hálók
  • Call Graph készítés, hívások közti konstans propagáció, call graph becslése
  • Elérhetetlen és haszontalan kód törlése, kontrol függőség fogalma

9. Gyakorlat

Témakörök

  • Code motion probléma általában, redundáns, részlegesen redundáns kifejezések
  • Lazy code motion algoritmus (prezi)
  • Végrekurzió optimalizálása
  • Dominator based value numbering
  • Optimalizációt segítő transzformációk: superblock klónozás, függvény klónozás, loop unswitching, ekvivalens regiszterek átnevezése

10. Gyakorlat

Témakörök

  • Strength reduction
  • Kódgenerálás lépései: instruction selection, instruction scheduling, register allocation
  • Szuperoptimalizáció, tree walk instruction selection, tree tiling instruction selection
  • Statikus vs dinamikus ütemezés
  • Függőségi gráf, kritikus útvonal, antifüggőség, lista ütemezés algoritmus, ütemezés kibővítése régiókra
  • Regiszter allokáció problémája, top down/bottom up megközelítés, gráf színezés, inference graph