README

Autor: Mikołaj Błaż
Nr indeksu: 346862
Data: 15.01.2018


# Kompilator Latte
## Struktura katalogów
Kompilator został zbudowany przy użyciu narzędzi BNFC, Alex oraz Happy.

Folder src/ zawiera początkowo plik Latte.cf, z którego zostaną wygenerowane
wszystkie pliki potrzebne do parsowania programów Latte.

Folder src/Llvm/ zawiera wszystkie pliki źródłowe specyficzne dla kompilatora.

Katalog lib/ zawiera plik jasmin.jar oraz plik runtime.ll z którego
(po uruchomieniu make) powstanie plik runtime.bc potrzebny podczas wykonywania
programów w języku Latte.

## Uruchamianie
Tak jak w wymaganiach zadania, aby skompilować i uruchomić program Latte
znajdujący się w pliku foo/bar/baz.lat, należy wykonać z korzenia projektu:
./latc foo/bar/baz.lat
lli foo/bar/baz.bc

Dodatkowo zostanie wygenerowany plik foo/bar/baz.ll.


# Działanie kompilatora
Kompilator podzielony jest logicznie na Frontend i Backend.
Oba działają na programie Latte w spostaci abstrakcyjnej składni,
wygenerowanej przez lekser i parser, wygenerowane przez programy Alex i Happy.

## Rdzeń (część wspólna)
Obie części korzystają ze wspólnych plików Core.hs oraz State.hs.
- Core.hs zawiera definicje podstawowych typów danych i operacji na nich.
- State.hs zawiera opis stanu (GenState), który jest używany podczas kompilowania
programów, oraz operacje na tym stanie.

Dodatkowo w pliku StdLib.hs znajdują się deklaracje funkcji bibliotecznych
jeżyka Latte, w postaci drzewa składni.

## Frontend
Całość znajduje się w pliku Frontend.hs.
Działanie frontendu obejmuje:
- sprawdzenie poprawności typów
- sprawdzenie poprawności identyfikatorów, deklaracji, itp.

__Dodatkowe optymalizacje__:
- upraszczanie wyrażeń logicznych, np.:
 - true || false -----> true
 - true && x     -----> x

- Optymalizowanie intrukcji warunkowych (if, while) w przypadku,
gdy warunek jest trywialny (po uproszczeniu), np.
 - while (true && false) bodyStmt; -------> empty instruction

- Sprawdzanie występowania instrukcji return (dla funkcji nie-void)
oraz usuwanie martwego kodu po takich instrukcjach.
Sprawdzenie następuje po uproszczeniu wyrażeń logicznych i instrukcji warunkowych, np.
 - {if (true) return 7; else return 0;} int x; return 0; -------> return 7,
 - ale: if (x) return 1; else x = 0;  --------> bez zmian

Drzewo składni jest przechodzone jednokrotnie, a więc wszystkie powyższe
działania wykonywane są równocześnie.
Dzieje się to w funkcjach:
analyzeProgram, analyzeTopDef, analyzeBlock, itd. (analyze*)


## Backend
### Generator
Główna logika backendu znajduje się w pliku Generator.hs.
Tam właśnie kolejno przetwarzane są funkcje (processTopDef).
Przetworzenie funkcji obejmuje:
- prawie całkowite wyczyszczenie stanu kompilatora
(oprócz licznika identyfikatorów, środowiska funkcji i puli stałych napisowych)
- Przetworzenie argumentów i ciała funkcji.
W tej części wygenerowany kod jest emitowany do stanu.
- Na końcu, wyciągnięcie ze stanu wygenerowanych instrukcji i zwrócenie ich wyżej.


Przetwarzanie ciała funkcji polega mocno na obecności __stanu__, w którym znajduje
się informacja o aktualnym bloku prostym (Llvm), w którym się znajdujemy.
Poprawność etykietowania bloków prostych zapewniają 2 niezmienniki instrukcji gen*,
opisane w okolicach linii 90 w pliku Generator.hs.

Bloki proste są zakańczane przez intrukcje terminujące (_br_ i _ret_, emitowane
przez funkcje genJmp, genBr, genRet, genVRet, na samym końcu pliku w sekcji _Terminators_).

Przed wyemitowaniem każdej instrukcji, emitowany jest komentarz z wypisaną tą instrukcją
(genStmtCommentWrapper), co ułatwia zrozumienie kodu w plikach *.ll

Generowany kod jest w postaci SSA, ale zmienne lokalne znajdują się w pamięci a nie w rejestrach.

### Emitter
Ten moduł emituje właściwy kod.
Dopiero tutaj istotna jest architektura docelowa, wcześniejsze transformacje
były niezależne od architektury (chociaż nastawione na Llvm).

Funkcje emit* emitują kod do stanu, zaś instrukcje output* wykonywane są poza monadą GenM
i zwracają instrukcje w wyniku.


# Dospecyfikowanie języka Latte
* Instrukcja _SExp_ może być jedynie wywołaniem funkcji
* Porównanie '==' i '!=' może odbywać się między dowolnymi typami (niefunkcyjnymi)
* Porównania '<', '>', '<=', '>=' mogą odbywać się tylko między typami _int_ i _boolean_
* Po instrukcji return mogą występować kolejne instrukcje (nie jest to błąd),
  jednak takie instrukcje są wykrywane i usuwane na etapie frontendu.
* Funkcja _readString_ wczytuje całą linię, ale maksymalnie 4096 znaków.
  W przypadku próby wczytania dłuższych linii, zachowanie jest niezdefiniowane.
* Funkcja _readInt_ wczytuje liczbę oraz białe znaki występujące na wejściu
po tej liczbie (m.in. znak '\n')


# Rozszerzenia

## Tablice
Uwagi:
* Tablice mogą być dowolnego wymiaru, np. poprawny jest kod:
```
int[] a = new int [4];
a[1] = 38;
int[][] b2 = new int[][3];
b2[2] = a;
printInt(b2[2][1]);
```
i wypisuje on 33 na wyjście.
Tak samo jak w Javie, długości tablic "wewnętrznych" nie muszą byc takie same.
Działa również zagnieżdżona pętla `for`, np. jeśli `array2d` jest zainicjalizowaną
tablicą typu `string [][]`, to poprawny jest następujący kod:
```
for (string[] array1d : array2d) {
  for (string x : array1d) {
    printString(x);
  }
}
```

* Tablice nie są inicjalizowane domyślną wartością.

* Zakresy tablic nie są sprawdzane, podobnie nie ma sprawdzenia czy rozmiar
nowo tworzonej tablicy jest dodatni - nieprawidłowe pod tym względem operacje
(np. new int[-1]) skutkują niezdefiniowanym zachowaniem.
* Szczegóły konstrukcji `for (int x : a) stmt`:
Zmienna `x` jest nowo zadeklarowaną zmienną i jej deklaracja obowiązuje
wewnątrz instrukcji (bloku) `stmt`. Może być w nim przedefiniowana, podobnie
zmienna `x` może występować na zewnątrz instrukcji `for`, a nawet może być
użyta w wyrażeniu `a`, tzn. poprawny jest następujący kawałek kodu:
```
int [] x = new int[5];
for (int x : x) {
  printInt(x);
  boolean x;
}
```

Kontrukcja `for (type x : a) stmt` jest tłumaczona na etapie frontendu na:
```
{
  type[] _arr = a;
  int _i = 0;
  type x;
  while (_i < _arr.length) {
    x = _arr[_i];
    stmt;
    _i++;
  }
}
```
Przy czym zmienne `_i` i `_arr` są niepoprawnymi zmiennymi Latte
(ze względu na znak _ na początku) - dzięki temu zapewniona jest poprawność powyższej uwagi o widoczności zmiennych.

## Struktury
* Wskaźnik _null_ jest typowany, składnia: `(typ)null` (istotny jest brak spacji po nawiasie).
Jawne określenie typu dla wskaźnika jest możliwe (wymagane) tylko dla _null_.