- Nepodminenym skokum se snazime vyhnout.
- Backend (BE) to rozbije na kousky (na zakladni bloky), vystupem BE je serializovany program, napr:

      1 -- 
      2   \
 --   3 <-/----\
 |    4 -------/
 \->  5
 
 
 Resime duplikaci, abychom se vyhnuli nepodminenycm skokum:
 
 [ 1 ]
   |  \
   |   2           /\  
   v   3  ------\ v  \
   3   /         4    |
   |  /          3    |
   v /           \----/
   5

- Je dokazano, ze touto duplikaci muze narust kod exponencialne - v realnem pripade je to ridke.
- Nevyhody:
  * Nekdy stezuje a nekdy pomaha predikci skoku
  * Prida to praci prekladaci   
- Vyhody:
  * Zvetsi se zakladni bloky, tj. je mozne udelat vice optimalizaci (urcite se tyka vsech lokalnich optimalizaci (tj. v ramci zakladnich bloku)   
- Neda se rict, ktery postup je lepsi (maximalne pomoci benchmarku)

Odstraneni zavislosti po analyze aliasu - obrazek
- Modre sipky znamenaji preneseni dat; cervene znaci zavislost.
- Zelena cara znaci, ze promennou si odnekud prectu (nekde predtim musel byt store, jinak je to blbej program)
- Cervena znaci, ze promenna neni potreba (ale urcuje poradi instrukci; vynucuje synchronizaci)
- Zlutozelena - nejiste cteni nekdy v budoucnu (v jinem zakladnim bloku)
- Fialova cara - data nejsou zapotrebi, neni potreba vedet, co se s promennou predtim delo

Slide: Nesekvecni mezikod s rozsahy platnosti
- Tlusta fialova znaci jednu promennou a tlusta zelena znaci druhou - resp. jejich platnosti
- Je videt, ze promenna z je pouzita ve dvou oblastech souvislosti a je mozne jednu prejmenovat

Slide: Urceni rozhranni BB
- Principialne je mozne mit promennou na ruznych mistech pri predavani z jednoho bloku do do dalsiho (do vsech zavislych stejne) - delaji to jen nektere prekladace. Uz v podstate neexistuji promenne, jde spise o komunikaci na rozhranni bloku. Komplikuje to ulohu, ale dava to prekladaci vetsi volnost pro optimalizaci.

Slide: Nahrada promennych rozhranm BB
- Odstranil jsem z obrazku vsechny load & store instrukce, snaha o to, aby producent se dohodl s konzumenty na tom, kde data budou.
- Pozn.: Dokonce blok vpravo nahore zjistil, ze se prohazuji dve promenne.

Slide: Nesekvencni mezikod bez promennych

            1
           /  \
  /--->   3    2 
  |      / \   |
  |     5   4  |  
  |          \ v 
  |           3
  |          / \
  \------   4   5 
    
  - Sipka (2 --> 3) je ekvivalentni uprava (nemusim to vest na 3 nalevo od 2) jelikoz si muzeme predstavit, ze graf predstavuje konecny automat a oba automaty prijimaji stejny jazyk. Prinos tohoto je v tom, ze 
  - Obecne poznat, kdy a jak se ma duplikovat je tezke.

Slide: Nesekvecni mezikod po preznaceni
- Sikovnym preznacenim se budou promenne budou stehovat mezi bloky tak, ze usetrim load&store instrukce.
- Tim, ze na sebe rozhranni pasuji, usetrime load&store instrukce.


Odbocka
- Prekladac ma ohodnocovaci funkci a ta nemuze byt moc slozita, aby prekladac bezel rychle (proto se neda optimalizovat na presny procesor)
- Pozn: profilem rizena optimalizace - ohodnocovaci funkce pocita na typickych datech pro program - v lepsich prekladacich

Slide: Algoritmus: Urceni rozsahu platnosti
- Pousteno v okamziku, kdy je procedura rozsekana na zakladni bloky 
- Neda se to takto delat u promennych s aliasy.
- Priznaky 
  - W - jako prvni do promenne zapisuju (pak uz se muze dit cokoli)
  - R - ctu pred prvnim zapisem
  - L -
- Ziva = musi byt pro promennou vyhrazeno misto
- Promenna je ziva na konci zakladniho bloku, pokud je ziva na zacatku nejakeho z jeho nasledniku.
- Priznaky L se siri proti smeru control flow grafu a hleda se prvni zapis promenne.


Cviceni

- call avsolutni adresa
- uloha b) alokace registru: vstupem bude program, ktery plytva registry
- uloha a) INITI zustanou
  * call (zakladni blok c. 3)
  * instrukce LLDI nechala vysledek na zasobniku, prepisu na ELLDI + PUSH
   
                       _
       |-    | |_     |_   |
    p1 |-    |   |    |_   v
       |-    |  -     |_  R1  - EPUSH R1
             | |       _       |
             |#|      |        |
             | |      |        |
             | |_     |        |
       |-    |  _|    |        |
    p2 |-    | |      |_R2   |-_|
       |-    |#              |          
  CALL |                     |_ EPUSHR R2
  DTOR |                        CALL
  DTOR |                        DTORR
                                DTORI
                                -
                                EPOPI R7 

   Volat tolikrat EPUSH kolik ma procedura parametru 
   (potreba resit typ - podivat se do metadat funkce? Ne, pres simulaci (resp. vysledovani) zasobniku, pamatovat si typu)    
       
   EPOP - 

                                 
- Primarni kod na zacatku neuklada a na konci neobnovovuje registry - nevime, kolik jich potrebujeme na zacatku; po vygenerovani primarniho kodu  uz to vime a tak prigeneruje spoustu epush a epop. PROTO MUSIME OPRAVIT ADRESY V KODU!!                              
- Return se zahodil a prida se tam pri nejake dalsi fazi.
- V prvnim pruchodu vytvori primarni kod a zjisti se pocet nutnych registru.
- V druhem pruchodu se pricte offset k adresam v instrukci.
- radek 87: RET 
- Analyza rozsahu platnosti musi bezet nad zakladnimi bloky

Alokator registru
- Finta: Musi se provest analyza rozsahu platnosti
 
   |   |   |
   |   |   |    push F0
       |   |         F1
           |     _
   F0             \    
   |   F1         |
   |   |   F0     |
       |   |      >
           |      |
   F0             |
   |   F1         |
       |         _/
                                 
           | 
       |   |    pop F1
   |   |   |    pop F0
       
 
the_rmgen -- hlavni procedura (obsahuje dva pruchody) - nemenit!! (sem spadaji interproceduralni optimalizace)
- primary_ic ... primarni mezikod 
- abstract_id
  - soucasti jsou konstanty, identifikatory, ...
- zpracovavame instrukci a adresu na konstantu musime zmenit na adresu nove kopie konstanty!!!
  - kopirovani konstant a identifikatoru se dela tak, ze 
- functor_function_info_copy -- nemenit
- function_generate_code 
  - primary_code
  - register_function_ - vysledny mezikod
  - Vse se dela najednou, nerozbiji se na zakladni bloky -> najdeme jen jediny funktor na pruchod kodem
  - functor_instruction_primary_to_final -> okopiruje instrukce ze vstupu do finalniho kodu, aby sel projekt prelozit
    - ai_factory::clone_ai_instr - okopiruje instrukci, ale instrukce se okopiruji se spatnymi ukazateli
- podivat se na to, jaka jsou k dispozici metadata - usetri to dost prace!

Pr.  
  Zdrojovy blok              Cil

    ...                      ...
    ... / UID = 1000                     ...
   BFLM <       [label=1000] BFLM     (okopiroval jsem, nove UID)  add_label  <- musim si pamatovat UID sveho zdrojoveho protejska    
        |
   JMP  /
  
  
  - Kazda instrukce ma svuj unikatni identifikator UID (samy se generuji)
  - Bloky se vazou pres UID a OTHER_UID
  - V cili je mozne hleda pomoci UID navesti (podivam se na JMP vlevo, odkaze me na BFLM vlevo a tim se dostanu na label=1000
  
  - ic_instrtab -- pro kazdy operacni kod dostaneme info (napr. to, ze instrukce je instrukce relativniho typu (vede dovnitr procedury - napr. na ten label vyse) )
  - info.stkp_type_ == ICSPT_LITINT  ... reseni konstant a reseni spatnych ukazatelu
    - pres hvezdicku precteme hodnotu 
    - resi to i nepouzivane konstanty
    - find_other_UID fce
  - functor_print_ .. nadstandardni vystup
    - in3_ptype .. instrukce maji operandy a toto je typ tretiho operandu (jde zjistit, jestli instrukce ma tri operandy)
  
  z kodu nepozname, kde konci inicializace promennych, protoze muze byt:
    init
    init
    init
    init  <- tato je napr.pro volani funkce

    v nejake tabulce najdeme, odkud kam trva inicializace promenne/struktury - tuto informaci musime zapsat i do vystupu finalniho kodu - dohledanim podle UIDu
    - final_var->set_icip_start;  set_icip_end 
