Nazvoslovi
==========
Zvlastni nazvoslovi v prekladacich.

* globalni

Hardwary jsou s(h)ity na imperativni programovaci jazyky.

* procedura u prekladacu znamena funkci (tj. muze vracet nejakou navratovou hodnotu)
* Call graph (CG) - graf volani procedur

    P0
   /  \
  P1  P2 <--\
   \  /     |
    P3 ----/
 
* Call tree (neco jineho nez CG)

     P0
   / | \
  P1 P1 P2 
     |  | 
     v  v
    P3  P3
  /  |
 v   v
 P2  P2  
 
 - runtinemova zalezitost
 - stromy jsou velike (pokud by byla smycka s milionem pruchodu, tak bude mit graf vice jak milion uzlu)
 - hypoteticka zalezitost
 - dana vetev se nazyva "call stack"
 
 * Procedura P0:
  
  Control-flow graph
  
         |
         v
      [|||||]        <- bloky (basic blocks)
       /   \
      v     v 
   [|||]  [|||] <---\ (nepodmineny skok)
  /   \     /  \    / 
[|||]  [|||||] [|||] 
  |       |  
  v       v

- Pokud mame CFG strukturovaneho jazyka, pak CFG je rovinny (zajimave, ale k nicemu)    
- Otazka, jak reprezentovat switch
- CFG lze jednoduse nagenerovat
- U optimalizaci se obcas rozhoduje, ktera promenna se da do registru, vyhrava napr. ta, ktera se pouziva ve smycce
  - CFG nepozna napr. vnitrni smycky, jinak ale CFG poskytuje vetsinu informaci pro preklad.

* Basic block
- formalne: nejdelsi blok kodu bez skoku
- konci: pokud je konec funkce, skok nebo ...
- DATA-FLOW GRAPH ~= DAG (directed acyclic graph)
  
          [X]  [Y]  [Z]   .. promenne
           |\    \  /|
           | \ /- +  |
           - </\  /  |
         / |    *    |
        /  |    |    |
       v   v    v    v
      [t] [X]  [Y]  [Z]
    
      y' := y + z;
      t  := x - y';
      y  := x * y';
      x  := t;
    
     ---
     
      [x]    [k]    [m]      [i]     [j]
      |\ \   /       |        |       |
      | \  \/        |        |       |
      |  RDI\      RDI        |       
      |   |  v    ,  |        |       .
      |   |  RDI  ,  |        |       .
      |   v   v   ,  |        |       .
      |   a   b   ,  |        |
      \   |       ,  |       /
       \  |  ,,,,,,  |      /
        \ v v        |     /
         WRI <------ +----/           |
                    /                 |
              /----/                  |
           WRI <----------------------/ 
         /
        /
       v
      [x] 
    
      a := x[k];
      b := x[m];
      x[i] := a;
      x[j] := b;
      
      Data-flow graph by mel rict, ktery z 4! permutaci poradi provadeni instrukci je spravny
      
      ,,,, - znaci poradi provadeni instrukci (nemusi tam byt, ale je to lepsi)
      - Se strukturami mohu zachazet jinak nez s obycejnymi promennymi:
        (mohu jen dodat carovane sipky, tak abych docilil spravneho poradi provadeni kodu)
        
     ,,,,,,  [k]      [m]     [i]      [j]
      ,    ,,/,,,,,,,  |       |        |
       ,,, v  /     v  |       |        |
       ,< RDI        RDI       |       
       ,   |       ,  |        |        .
       ,   |       ,  |        |        .
       ,   |       ,  |        |        .
       ,   |a      ,  | b      |
       ,   |       ,  |        /
       ,   |  ,,,,,,  |       /
       ,   v v        |      /
       ,>  WRI <------+----/            |
           ,          /                 |
           v    /----/                  |
           WRI <------------------------/ 
         ,
        ,
       v
      [x] 
    
    
   - Na zacatku je DAG neco jako strom vyrazu, na konci prekladace uz graf jen vyjadruje poradi instrukci (tj. zbyvaji sipky ",,,,")
   - Na zacatku grafu rikame DAG nebo Data-flow graf, na konci DAG.
   - Otazka: Co kdybych se vykaslal na dvouvrstevnatost a spojil DAGy do jednoho?
     Odpoved: Neni to dobry napad, protoze cykly :-), zmizi synchronizace. 
     (zapomenu, v kolikate iteraci jsem, nemuzu michat hodnoty z ruznych iteraci)
   - Prumerna velikost zakladnich bloku je kolem 5 instrukci (zde se mnoho optimalizaci udelat neda)
   
   
Depedence a antidependence   
==========================
* Dependence znamena, ze jedna instrukce musi byt pred druhou (tj. plna i carkovana cara)
* Dopredna dependence - instrukce konzumuje vysledek predchozi instrukce
   (Write -> Read)
* Antidependence - 
  - Read ,,,,> Write
  - Write ,,,,> Write (pokud nezapisuju na ruzna mista, tak musim hlidat poradi)  
* Antidependence vznika napr. takto:
  a := b;
  b := c;  >>> prejmenovanim b na b' muzu dosahnout odstraneni antidependence (dopredne zavislosti takhle odstranit nemuzu)
           >>> nefunguje ve smyckach (tam se to musi resit jinak - kopirovanim tela smycky napr. - tj. zvetsi se delka kodu)
  
  - Prohazovani instrukci obcas neni mozne kvuli tomu, ze instrukce meni nejaky priznak v procesoru.
    a := b + c
    if x > y
    ============
    mov a, b
    add a, c   \ 
    cmp x, y   /  nemohu prohodit instrukce (add nastavuje nejake priznaky, ktere nastavuje i cmp) -- 
    jg   ...      na nejakem procesoru (striktne jde o Write Write problem); prohozeni by se mi hodilo, mov by bezelo s cmp a add s jg;
                  if (b + c > 0) jde prelozit jednou instrukci, kvuli nulovemu priznaku
    
    
