[Antique-Hackers] C64-kompilatorns middle stage fungerar

[John Lorentzson]

Jag har nu skrivit klart och kommittat en första version av kompilatorns 
middle stage. Den kompilerar syntaxträdsnoder till en intermediate 
representation (IR) som kan optimeras.

IR har följande struktur:

Programmet startar i en dubbellänkad lista av IBLOCK. Ett IBLOCK pekar 
till den första och sista IR-instruktionen som den innehåller, samt 
nästa och föregående IBLOCK. En IR-instruktion pekar till nästa och 
föregående IR-instruktion, vilken data som IR-instruktionen tar som 
input, och ett objekt data som den kan ge som output. IR-instruktioner 
är subklasser av IR-INST.

Inputs är instanser av IR-DATA, som håller koll på en definition (den 
instruktion vars output datan är) och användare (instruktioner som tar 
datan som input). Ett IR-RESULT har endast en användare och är oftast 
skapat som returvärde eller temporär resultat. En subklass av 
IR-REUSABLE har istället flera användare och är oftast variabler eller 
temporära resultat som en optimering har gjort återanvändbar. 
IR-instruktioner kan ha en output. Dessa outputs är också IR-DATA och 
kan användas som inputs till andra IR-instruktioner. När en 
IR-instruktions inputlista ändras uppdateras även all relevant datas 
användarlistor. När en output ändras sker liknande uppdatering för 
outputens definition. Att IR-DATA håller koll på användare själv gör det 
trivialt att se om data är oanvänd, samt att följa datans flöde.

Kompilering sker primärt genom den generiska funktionen COMPILE-NODE. En 
metod görs som specialiserar med en syntaxträdnod som första parameter 
och tar som andra parameter en "BUILDER". Metoden skapar där passande 
IR-instruktioner som ges till funktionen BUILD-INSERT tillsammans med en 
BUILDER. Den sätter in IR-instruktionen i det IBLOCK som BUILDER just nu 
bygger upp. Returvärdet är, om relevant för noden, en IR-RESULT som ska 
användas som "nodens" outputvärde. IR-RESULT objekt skapas manuellt i 
dessa metoder och ges till IR-instruktionerna genom deras initargs.

När branching ska genereras måste nuvarande IBLOCKet avslutas eftersom 
flödet i ett IBLOCK måste vara linjärt förutom den sista instruktionen, 
som måste vara en speciell typ av instruktion. Vi skapar två eller tre 
nya IBLOCK (beroende på om vi har en "else" eller inte), och sätter 
sedan in en instruktion IR-IF som den sista i IBLOCKet.

Den sista instruktionen i ett IBLOCK får endast vara en IR-TERMINATOR. 
Dessutom får en IR-TERMINATOR endast vara den sista instruktionen i ett 
IBLOCK. Den har en lista med destinationer som den kan hoppa till från 
slutet av sitt IBLOCK. Nuvarande IBLOCKet avslutas med BUILD-INSERT-END 
som tar en IR-TERMINATOR samt en BUILDER. För att branching ska fungera 
så behövs mer än en destination, så ett nytt IBLOCK kan skapas och göras 
det aktiva IBLOCKet av en BUILDER genom BUILD-BEGIN. Efter 
IBLOCK-konstruktion länkas alla nåbara IBLOCK ihop i en linjär ordning 
genom deras sista instruktioners destinationer.

Både vanliga "if"s och loopar implementeras genom IR-IF samt lite extra 
arbete omkring den ("if" behöver ett testuttryck och kan ha en "else" 
som insättning av jumps nödvändigt, loopar behöver inkrementering och 
testning av en variabel).

Optimering görs relativt enkel både genom att data håller koll på sina 
användningar och definitioner, och att det finns simpla funktioner för 
att flytta, radera, och sätta in instruktioner i ett färdigbyggt IBLOCK. 
Det finns just nu optimeringar för deduplicering av funktionsargument 
(endast för konstanter just nu), omordning av argumentladdning för att 
förenkla generering av bra 6502-kod (simpla "ladda konstant", "ladda 
variabel" hamnar närmast anropet, funktionsanrop som argument hamnar 
tidigare), simpel constant folding (att flytta beräkningar med 
konstanter till compile-time) för kommutativa operationer (just nu 
addition och multiplikation), och radering av bieffektfria instruktioner 
vars output inte används.

Vidare optimering kan bli nödvändig eller användbar, och kompilatorn 
borde göras medveten om deklarerade assemblyrutiner så att den kan veta 
om en assemblyrutin som tar konstanta argument kan evalueras vid 
compile-time eller måste anropas. Jag kommer förhoppningsvis påbörja 
kodgenerering av 6502-assembly ikväll.

-duuq-