#include <stdio.h>
#define MAX_BLOKU 100
#define MAX_PROM 100

 /* Typy pro reprezentaci programu.  */
unsigned n_prom; /* Proměnné očíslované od 0 do N_PROM - 1.*/

struct operand {          /* Operand výrazu.  Pokud je typ PROM,*/
  enum typop {PROM, CISLO} typ; /* je hodnota číslo proměnné,*/
  unsigned hodnota; };          /* jinak to je hodnota čísla.*/

struct vyraz{
  char operator;
  struct operand operandy[2]; };

 /* Pro ASSIGN je v data[0] identifikátor proměnné, do níž se přiřazuje,
     a ve vyraz přiřazovaný výraz.*/
 /* Pro LABEL je v data[0] číslo labelu.*/
 /* Pro IF je ve vyraz podmínka, v data[0] label, kam se skáče, je-li splněna,
     v data[1] kam se skáče, pokud splněna není.*/
 /* Pro GOTO je v data[0] label, na který skáče.  */
struct prikaz {
  enum prikazy {ASSIGN, LABEL, IF, GOTO} prikaz;
  struct vyraz vyraz;
  unsigned data[2];
  struct prikaz *dalsi, *predchozi; /* Příkazy jsou uloženy v seznamu.  */

struct hrana {  /* CFG.  */
  struct basic_block *z, *k; /* Hrana z bloku Z do bloku K.  */
  struct hrana *nasl_dalsi, *pred_dalsi; }; /* Hrany ve dvou seznamech: následníci a předchůdci bloku.  */

struct basic_block {
  unsigned index;     /* Číslo bloku, od 0 do N_BLOKU.  */
  struct hrana *pred, *nasl;   /* Seznam předchůdců a následníků.  */
  struct prikaz *prvni, *posledni; };   /* Příkazy v bloku.  */

unsigned n_bloku;  /* CFG se skládá z N_BLOKU bloků.  Počáteční blok má číslo 0.  */
struct basic_block cfg[MAX_BLOKU];

struct hodnota {  /* Hodnoty pro propagaci konstant. */
  enum hod { TOP, KONST, BOTTOM } hod;
  unsigned konstanta; };

struct hodnota ohodn_zac[MAX_BLOKU][MAX_PROM];  /* Ohodnocení proměnných na začátku a na konci bloku.  */
struct hodnota ohodn_kon[MAX_BLOKU][MAX_PROM];

void slij_hodnoty (struct hodnota *h, struct hodnota h1) {/* Slije H a H1 do H.  */
  if (h->hod == BOTTOM || h1.hod == TOP) return;
  if (h->hod == TOP || h1.hod == BOTTOM) { *h = h1; return; }
  if (h->konstanta != h1.konstanta)  h->hod = BOTTOM;
}

void slij (struct basic_block *bb) { /* Slití hodnot na začátku basic bloku*/
  struct hrana *p;                   /* z hodnot na koncích předcházejích bloků. */
  struct basic_block *pred;
  unsigned i;
  
  for (i = 0; i < n_prom; i++) ohodn_zac[bb->index][i].hod = TOP;
  for (p = bb->pred; p; p = p->pred_dalsi) {
    pred = p->z;
    for (i = 0; i < n_prom; i++) slij_hodnoty (&ohodn_zac[bb->index][i], ohodn_kon[pred->index][i]);
  }
}

void vyhodnot_vyraz (struct basic_block *bb, struct prikaz *prik) { /* Odsimuluje přiřazení PRIK. */
  unsigned vysl = prik->data[0];
  struct hodnota hod[2], vys;
  unsigned i;
  struct operand *op;

  for (i = 0; i < 2; i++) {
    op = &prik->vyraz.operandy[i];
    if (op->typ == PROM) hod[i] = ohodn_kon[bb->index][op->hodnota];
    else { hod[i].hod = KONST; hod[i].konstanta = op->hodnota; }
  }

  /* Pokud je alespon jeden z operandů TOP, je bezpečné vrátit TOP (byť
     v praxi je výhodnější konvergovat k BOTTOMu rychleji).  */
  if (hod[0].hod == TOP || hod[1].hod == TOP) vys.hod = TOP;
  else {
    vys.hod = KONST;
    switch (prik->vyraz.operator) {
    case '+': if (hod[0].hod == BOTTOM || hod[1].hod == BOTTOM)  vys.hod = BOTTOM;
              else vys.konstanta = hod[0].konstanta + hod[1].konstanta; break;	
    case '-': if (hod[0].hod == BOTTOM || hod[1].hod == BOTTOM) vys.hod = BOTTOM;
              else vys.konstanta = hod[0].konstanta - hod[1].konstanta; break;
    case '*': if ((hod[0].hod == KONST && hod[0].konstanta == 0)
		  || (hod[1].hod == KONST && hod[1].konstanta == 0)) vys.konstanta = 0;
              else if (hod[0].hod == BOTTOM || hod[1].hod == BOTTOM) vys.hod = BOTTOM;
              else vys.konstanta = hod[0].konstanta * hod[1].konstanta; break;
    case '/': if (hod[0].hod == KONST && hod[0].konstanta == 0) vys.konstanta = 0;
              else if (hod[0].hod == BOTTOM || hod[1].hod == BOTTOM) vys.hod = BOTTOM;
              else vys.konstanta = hod[0].konstanta / hod[1].konstanta; break;      
    default:  vys.hod = BOTTOM;
    }
  }
  ohodn_kon[bb->index][vysl] = vys;
}

int vyhodnot (struct basic_block *bb) {   /* Vyhodnotí výrazy v bloku BB,*/
  struct prikaz *prik;                  /*vrátí 1 pokud se změnilo ohodnocení na jeho konci.  */
  unsigned i;
  struct hodnota ohodn_stare[MAX_PROM];

  for (i = 0; i < n_prom; i++) {   /* Uložíme staré ohodnocení,*/
    ohodn_stare[i] = ohodn_kon[bb->index][i]; /* nové nainicializujeme na hodnoty na začátku.  */
    ohodn_kon[bb->index][i] = ohodn_zac[bb->index][i];
  }
  for (prik = bb->prvni; prik; prik = prik->dalsi) if (prik->prikaz == ASSIGN) vyhodnot_vyraz (bb, prik);

  for (i = 0; i < n_prom; i++)   /* Porovnáme se starým ohodnocením. */
    if (ohodn_stare[i].hod != ohodn_kon[bb->index][i].hod) return 1;

  return 0;
}

void cprop_dataflow (void) { /* Vyplní ohodnocení pro propagaci konstant.  */
  unsigned i, b;

  struct basic_block *zmenene[MAX_BLOKU], *bb;  /* Zmenene je seznam bloků, jejichž ohodnocení se změnilo a */
  unsigned pocet_zmenenych; /* je třeba ho přepočítat. Chováme se k němu pro jednoduchost */
  char je_zmeneny[MAX_BLOKU]; /* jako k zásobníku, i když bývá lepší používat jiné pořadí.  */
  struct hrana *n;

  for (b = 0; b < n_bloku; b++) 
    for (i = 0; i < n_prom; i++)
      ohodn_zac[b][i].hod = ohodn_kon[b][i].hod = TOP;
  for (i = 0; i < n_prom; i++) ohodn_zac[0][i].hod = BOTTOM;
  for (b = 0; b < n_bloku; b++) je_zmeneny[b] = 0; /* Na začátku je změněný jen počáteční blok.  */
  je_zmeneny[0] = 1;
  zmenene[0] = &cfg[0];
  pocet_zmenenych = 1;

  while (pocet_zmenenych > 0) {
    bb = zmenene[--pocet_zmenenych];
    je_zmeneny[bb->index] = 0;
    slij (bb);
    if (!vyhodnot (bb)) continue;

    /* Hodnoty na konci se změnily, je potřeba vložit následníky BB do seznamu, pokud už v něm nejsou.  */
    for (n = bb->nasl; n; n = n->nasl_dalsi) if (!je_zmeneny[n->k->index]) {
	je_zmeneny[n->k->index] = 1;
	zmenene[pocet_zmenenych++] = n->k;
    }
  }
}