- Neni mozne chapat prirazeni virtualnich registru fyzicky jako ulohu ano/ne.
- Uspora toho, ze bychom pouzili mene registru nez nam architektura dava k dispozici neni velka.
- Proc se to dela na castecne sekvencnim poradi instrukci a ne na DAGu 
  - Scheduler pred alokaci registru rozhazi instrukce tak, aby to vyhovovalo dane architekture.
  - Druhy duvod je, ze extrahovat to z jine reprezentace je pomerne tezke.
  
   r1   r2
   (I1) (I2)    
  r3 \ / r4   (I5) r5
     (I3)      | r6
      | r5    (I6) r6
     (I4)      | r7
       
   - Z tohoto bychom meli rict, ktere dvojice registru z toho prikladu jsou zavisle.
   - Extrakce z DAGu je velmi tezka a vetsinou pokusy o jejich implementaci konci neuspesne.
- Povazuje se za dulezitejsi schopnosti paralelizmu nez usetreni registru. Paralelizmus by mel vyvazit prave usetreni jednoho dvou registru.
- Odbocka:
   
   add r3, r1, r2
   
   add r1, r2       - pokud jsme na takoveto platforme, kde r2 se pricte k r1;
    -> upravim na:
       
       mov r3, r1
       add r3, r2    <- je moznost jeste udelat optimalizaci, protoze operace je komutativni, takze je mozne, ze vymenou neco usetrim, tj.:
       
       mov r3, r2   <- r3, r2 mohou byt ten samy registr, pokud r2 konci platnost pred r3
       add r3, r1
       
     Usetreni instrukce mov lze v pripade stotozeni, nicmene je potreba se podivat na globalni rozsahy platnosti registru. 
      
Alokace registru
- Zasobnik proto, ze pak chci pridavat v obracenem poradi, nez jsem vkladal.
- V okamziku, zee nemam zadny vrchol, ktery ma stupen mensi nez n, tak to muze a nemusi znamenat problem.
  - Vyberu nejaky vrchol a ulozim ho na zasobnik
- P(v) je cena za spill-code vrcholu (promenne), odpovida to tomu, ze pokud nemuzu vybrat zadny vrchol nema stupen mensi nez n, tak muzu k tomu pristupovat tak, ze:
  a) pesimisticky - vybiram nejlacinejsi obet
  b) optimisticky - vybiram nejmensi stupen
  c) Jeste jedna mozna heuristika, vyberu maximalni stupen (sice je mala sance, ze ho obarvim ale jeho odebranim se odebere hodne hran).
  
  NP uloha, pro kterou vsak nase reseni v polynomialnim case jsou pomerne blizko k idealnimu reseni.
  

- Hledaji se komponenty s doporucujicimi hranami, ale nesmim zanedbat zakazove hrany. 
  - Taky tezka uloha, ale tim, ze ty komponenty nejsou velke, tak muzu vyzkouset i vsechny moznosti.
  - Komponenta se ztotozni do jednoho uzlu. Muze se tim stat, ze pak nenalezeneme pak obarveni. Proto se moc neztohotznuje.

Doplnovani spill-kodu
- Algoritmus je, ze odebiram vrcholy tak, ze odeberu ten vrchol s nejmensim stupnem a pri vraceni vybiram prvni barvu, ktera je volna - je to opet neidealni reseni, ale funguje dobre.
- Pokud mame stesti, tak pro instukci add existuje instrukce ve tvaru "registr,pamet".
- Z jedne instrukce add registr registr, se stane:

  mov rx, [..]
  add rx. [..]
  mov [..], rx
  
  aby se dala sance nasledujicimu scheduleru, tak se instrukce, ktera precte pamet a zapisuje do pameti se pouziva vice instrukci, napr.
  
  mov ry, [...]
  mov rx, [...]
  add rx, ry
  mov [...], rx
  
- Nedostatek registru je globalni problem, tj. pro spill-code muz nejake registry pouzit navic - optimisticky predpoklad, 
  a) amaterske reseni: vyhradim si par registru na podobne problemy
  b) pouziju push a pop pro registr
  c) pridam pomocne vrcholy (prazdne kolecko) pro kazde misto, kde se s danou promennou pracuje - z jednoho vrcholu se stanou skupinky
     Plna kolecka predstavuji promennou jako takovou.
     Hrany davam pouze mezi prazdna kolecka. 
     Pouze pokud pracuji se spill-kodem, tak se uvazuji prazdna kolecka.
     
     
Varianta A) Vyber instrukci 

Varianta B) Analyza rozsahu platnosti (struktura na zakladni bloky, ve slidech)

Varianta C) Scheduling - je potreba ziskat informace o casovani instrukci; potreba odhadnout casy podle grafu


CVICENI: Infrastruktura zakladnich bloku

I ... custom data

basic_blocks ... cely control flow graph (kolik instancni budeme mit zalezi na nas, mela by stacit jedna)

tvari se to jako kontejner pro zakladni bloky:
- obycejny begin() a end() - projdou vsemi zakladnimi bloky v takovem poradi, ve kterem jsme je vytvorili
- canonical_begin(), canonical_end() .. stejne jako vyse, ale vrati nam to v topologickem usporadani (snazi se to postupovat tak, ze to jde podle sipek v grafu) - s uspechem to lze pouzit pro zaverecnou serializaci kodu
- hledani zakladnich bloku: find_by_other_UID, find_by_UID
  - pokud bychom meli dve instance basic_blocks (jeden pro jeden pro zasobnikovy kod a jeden pro registrovy kod, tak se svazou pomoci UIDu)
- get_start_block() - prvni blok procedury 
  - vraci iteratory, pokud aplikujeme na to hvezdicku, tak dostaneme data!!!!
- manipuluje se s uzly pomoci nejakych iteratoru - je potreba vedet, ze nektere iteratory prezijou manipulaci s datovou strukturou jako takovou
  - Interne jako kontejner list, tj. behem konstruovani je mozne pridavat hrany

basic_block
- get_data -- nese vsechna uzitecna data pro nas
- get_outgoing_jumps - vsechny vystupni hrany
- hrana na sebe prozradi zdrojovy a cilovy blok (mlaskal::jump<I>)
- Pokud se ptame na vystupni hrany nejakeho BB, tak muzeme rozlisit hrany na: 
  - Jednotlive hrany jsou opatreny barvami.
  - V kontejneru map (barva, hrana)
  - UID_provider - generuje tri barvy (jump_on_false, jump_on_true, jump_on_...)
  - find_by_color !
- Vic z te struktury asi nedostaneme

Jak se vyrobi zakladni bloky?
- Musime si rozsekat na kousky vstupni kod. Pro kazdou proceduru vytvorime basic_blocks a pak pridavame jednotlive bloky - pomoci create_block(), bez jakehokoli propojeni s ostatnimi bloky. Prvni volani create_block znaci primarni blok! (ten pak dostaneme pomoci get_start_block())
- Kdyz potrebujeme pridat hranu, tak se to dela na pomoci add_jump (meli bychom dodrzovat omezeni, ze barvy jsou ruzne pro kazdy vrchol)
- Jak vypada rozsekani procedury na zakladni bloky:
  - Na kazdou proceduru je zavolan nejaky funktor
  - Dostaneme blok instrukci 
    - musime najit kde BB zacinaji a konci 
    - vsimame si veskerych skokovych instrukci (z metadat se to da zjistit, ktere to jsou)
    - kdyz najdeme instrukci, ktera skace, tak za ni je konec BB, a tam kam skace je zacatek BB, tj. jednim pruchodem nam pribyvaji predely mezi BB.
    - Meli bychom si predely nekde pamatovat - kde? Vyuzijeme, ze kazda instrukce ma svuj UID, udelame si datovou strukturu, ve ktere muzeme indexovat pomoci UID (zakladni blok pak napr. odpovida UIDu prvni instrkce BB). Struktura basic_blocks nam umoznuje pamatovat si other_UID, uz pri prvnim pruchodu muzeme zalozit zakladni bloky. Dokonce uz v teto fazi vim, kam jsou zakladni bloky navazane (neni pravda!). Generovani hran musim delat az v druhem pruchodu!!! Propojim BB, ve kterych zatim nebude zadne instrukce. Udelam dalsi pruchod pres instrukce a pro kazdou instrukci se ptam, zda neexistuje v basic_blocks nejaky BB, ktery zacina danou instrukci a zacneme plnit BB. Pak bud zkopirujeme nebo si napr. zapamatujeme, ktere instrukce tam patri. Posledni skokovou instrukci si muzeme pamatovat a nemusime. Doplnime skoky (podle UIDu). Neprovedeni skoku (neprimy skok) znamena propojeni dvou za sebou jdoucich BB. Dvoupruchodovy algoritmus - sami mame naprogramovat. Neni potreba zadna dalsi datova struktura.
    
    instrukce    ->   () () () ()
    
  - Rozsahy platnosti promennych budou v datove strukture, ktera patri k BB. Spocteme lokalne (dokonce se to da udelat pri druhem pruchodu alg. vyse).
  - Do tajemneho datoveho typu I strcime vektory.
  - Je potreba udelat rozsahy platnosti:
  
              var ->
    osa x   |     
    (|cas") v
    
    - je dobre to drzet jako seznam intervalu, popr. jako booleovskou maticu (predpokladejte, ze mate polynomialni mnozstvi pameti)
    
  - Kazda procedura si o sobe nese informace o poctu pouzitych registru.
- Instrukce v namespace "ai". Instrukce typu ICSPT_LSTKOFFS jsou instrukce, ktere pracuji s promennou na lokalnim zasobniku.
  - Pro alokator registru si vystacime s metadaty a nemusime pracovat s jednotlivymi instrukcemi
  - Kdo bude pracovat na schedulingu, tak muze pouzit to same, ale jeste mu bude chybet informace o casovani (rucne to vyextrahujeme z manualu k instrukcim)
  -   