dead

[cdimauro]

• 

Ehm, quale sarebbe? Non me lo ricordo adesso.

Per come e' fatto il datapath esiste un effetto collaterale della BRA che può essere abilitato (specificando un registro destinazione) e nel caso fa le seguenti faccende

1) copia PC+sizeof(instruction) nel registro destinazione
2) copia quanto specificato come sorgente (una costante immediata, o il contenuto di un registro) in PC

in pratica si comporta come una jsr ma senza toccare lo stack, difatti e' possibile ripristinare all'indietro il PC con la stessa BRA specificando nessun registro destinazione e per sorgente lo stesso registro usato per salvare PC+sizeof(instruction)

Ah, OK, ci sono. E' che questo funzionamento si chiama in gergo "branch & link" (ed è tipico di tanti RISC), per cui m'ero perso...

[cdimauro]

• 

Però quelle ALU addizionali sono comode per migliorare le prestazioni.

Indubbiamente, tuttavia richiedono una estensione di ciclo macchina per dare il tempo ad una rete di calcolo a due tre livelli di elaborare l'EA propagandone il segnale in modo sincrono nell'apposito registro di datapath, il che quindi mi scoccia un po' perché vorrei uniformita' di ciclo - idealmente - per tutte le istruzioni.

Ho capito, ma in fin dei conto quanto ti costa questa modifica? Perché le prestazioni possono essere molto elevate. Immagina tutti i casi di spostamento o ricerca di dati, operazioni molto frequenti, dove l'incremento o decremento automatico del puntatore "gratis" sarebbe un bel vantaggio.

[cdimauro]

• 

In parte sì, ma io intendo una serializzazione vera e propria di tutto l'albero, cioè la messa su file dell'intera struttura dati invariata. Probabilmente andando nel pratico conviene di più quel metodo, visto che tutti i maggiori compilatori si sono stabilizzati su questo metodo.

Probabilmente è più semplice da elaborare,. Cmq, nel caso dell'IR di LLVM, esiste sia in forma testuale (utile da leggere per le persone), sia in forma binaria (memorizzata o su file o in memoria). La documentazione dice che il formato binario è simile a un XML (quindi una albero). Il formato testuale invece è così:

Codice: [Seleziona]

; ModuleID = 'base.c'
target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
target triple = "x86_64-pc-linux-gnu"

; Function Attrs: nounwind uwtable
define i32 @foo(i32 %a, i32 %b) #0 {
  %1 = alloca i32, align 4
  %2 = alloca i32, align 4
  store i32 %a, i32* %1, align 4
  store i32 %b, i32* %2, align 4
  br label %3

; <label>:3                                       ; preds = %6, %0
  %4 = load i32* %1, align 4
  %5 = icmp sgt i32 %4, 0
  br i1 %5, label %6, label %11

; <label>:6                                       ; preds = %3
  %7 = load i32* %2, align 4
  %8 = mul nsw i32 %7, 2
  %9 = load i32* %1, align 4
  %10 = sub nsw i32 %8, %9
  store i32 %10, i32* %2, align 4
  br label %3

; <label>:11                                      ; preds = %3
  %12 = load i32* %2, align 4
  ret i32 %12
}

; Function Attrs: nounwind uwtable
define i32 @main() #0 {
  %1 = alloca i32, align 4
  %a = alloca i32, align 4
  store i32 0, i32* %1
  %2 = call i32 @foo(i32 3, i32 4)
  store i32 %2, i32* %a, align 4
  %3 = load i32* %a, align 4
  ret i32 %3
}

attributes #0 = { nounwind uwtable "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }

!llvm.ident = !{!0}

!0 = metadata !{metadata !"Ubuntu clang version 3.4-1~exp1 (trunk) (based on LLVM 3.4)"}
Generato compilando senza nessuna ottimizzazione (-O0) a partire da questo programmino inutile:

Codice: [Seleziona]

int foo(int a, int b)
{
    while(a>0)
        b = b*2 - a;

    return b;
}

int main()
{
    int a = foo(3,4);
    return a;
}

È in formato SSA, quindi con infinite variabili temporanee %xxx (xxx = numero), e come si vede ogni volta che una variabile è usata viene anche specificata la dimensione dell'operando.

Sì, ma non è così semplice realizzare un backend. Mi sono smazzato anche il link che mi hai fornito riguardo all'assembler/disassembler, e c'è parecchio lavoro. Oltre al fatto che LLVM in alcune parti è ancora immaturo o incompleto, per cui ti costringe anche a scrivere direttamente codice C++ se vuoi sfruttare (molto) meglio le caratteristiche della tua ISA. Ad esempio è quello che hanno fatto per supportare l'FPU x86 di x86/x64.

Rimane comunque il casino immenso di dover ricorrere a un assemblatore e linker esterno per generare codice.

Altra cosa, purtroppo manca ancora l'architettura 68000. Per cui credo che certe ottimizzazioni non siano state nemmeno prese in considerazione da chi ha sviluppato LLVM. Anche se devo dire che qualcosa per PowerPC c'è, e pure per ARM, per cui magari si può vedere come hanno implementato o risolto certi problemi.

In ogni caso non è facile scrivere un nuovo backend per LLVM. Sulla carta sembra di sì, ma gli esempi che ci sono riguardano architetture RISC molto semplici; non a caso....

[cdimauro]

• 

p.s.
vedi perché pepita inizialmente usava BRAM per avere oltre 1024 registri ? Tutti quei modelli di compilatori assumono che l'architettura virtuale abbia infiniti registri, poi fanno seguire una fase di fitting in cui si ripiega sulle risorse finite del target reale

io ho attualmente riservato 10 bit, e posso averne anche 12 volendo, quanto aiuta ?

Non ti serviranno mai tutti quei registri. I registri virtuali dell'SSA servono soltanto a semplificare la vita a chi scrive gli algoritmi di ottimizzazione, ma alla fine vengono poi ridotti / mappati in quelli fisici, che sono pochi.

Oggi con 16 registri copri la stragrande maggioranza dei casi. 32 sono grasso che cola...

[cdimauro]

• 

Ho capito, ma in fin dei conto quanto ti costa questa modifica?

Costa parecchio, manda fuori di almeno un giro tutta la sincronia del datapath, ovvero costa di almeno 2 stadi in più necessari per propagare ed elaborare l'EA

OK, ma non mi pare molto, visti anche i vantaggi. Quant'è lunga la tua pipeline?

[Z80Fan]

• 

p.s.
vedi perché pepita inizialmente usava BRAM per avere oltre 1024 registri ? Tutti quei modelli di compilatori assumono che l'architettura virtuale abbia infiniti registri, poi fanno seguire una fase di fitting in cui si ripiega sulle risorse finite del target reale

io ho attualmente riservato 10 bit, e posso averne anche 12 volendo, quanto aiuta ?

Io continuo a credere che 1024 son troppi, di sicuro non per problemi col compilatore (che più registri ha meglio è), ma per problematiche tipo salvataggio del contesto durante context-switch.

In più, è vero che i compilatori lavorano come se avessero un numero infinito di variabili, ma quel che conta è vedere quali sono i valori che rimangono effettivamente nei registri, perchè se abbiamo ad esempio un codice del genere:

Codice: [Seleziona]

%0 = 3
%1 = %0 + 5
%2 = %1 / 4
%3 = %2 + %0
è evidente che quel che ci serviva erano solo 2 registri invece che 4 variabili temporanee SSA!

Per esempio, ho compilato con clang un file di un mio videogioco che contiene una funziona assai complessa, con switch -O3, e l'IR generato raggiungeva le 3000 variabili temporanee!
Vuol questo dire che quella funzione girerebbe più velocemente su un processore da 3000 registri? Probabilmente no, perchè molti pezzi della funzione sono calcoli a se stanti che generano pochi valori in output (anzi, in questo caso inseriscono dei valori in delle liste).

Bisognerebbe avere un tool che trova il minor numero di registri per avere un'esecuzione ottimale del codice... probabilmente si può hackerare LLVM per ottenere una simile statistica ma non voglio nemmeno pensare la quantità di lavoro (probabilmente il codice si presta già, ma bisognerebbe imparare tutto il sorgente prima di metterci mano, e io ho solo una vita).

Piuttosto userei la BRAM, come ti avevo accennato, per creare più set di registri che l'OS può scambiare con una singola istruzione, per avere context-switch velocissimi.

Sì, ma non è così semplice realizzare un backend. Mi sono smazzato anche il link che mi hai fornito riguardo all'assembler/disassembler, e c'è parecchio lavoro. Oltre al fatto che LLVM in alcune parti è ancora immaturo o incompleto, per cui ti costringe anche a scrivere direttamente codice C++ se vuoi sfruttare (molto) meglio le caratteristiche della tua ISA. Ad esempio è quello che hanno fatto per supportare l'FPU x86 di x86/x64.

Mai detto fosse "facile", ma sicuramente è "più facile" rispetto altri sistemi; vuoi parlare di GCC?
LLVM almeno ha TableGen che ti permette di generare gran parte della struttura automaticamente, almeno le parti più "noiose"...
Secondo me, più che immaturità, è un po' un'esigenza: credo sia difficile accontentare così tante architetture diverse in un singolo sistema, quindi molte cose le fanno gestire a mano piuttosto che appesantire TableGen.

Rimane comunque il casino immenso di dover ricorrere a un assemblatore e linker esterno per generare codice.

Beh se vuoi avere solo un output binario per test e statistiche, lasci stare i linker e crei solo l'assemblatore integrato,che in realtà non è un assemblatore, semplicemente una passata che invece di generare li codice in formato testuale (assembly), lo genera direttamente in binario.
Intanto fai questo, che ti porta già a molte cose interessanti.

Altra cosa, purtroppo manca ancora l'architettura 68000. Per cui credo che certe ottimizzazioni non siano state nemmeno prese in considerazione da chi ha sviluppato LLVM. Anche se devo dire che qualcosa per PowerPC c'è, e pure per ARM, per cui magari si può vedere come hanno implementato o risolto certi problemi.

C'era un backend di terze parti per 68k, però era sia riferito a una vecchissima versione di LLVM (2.qualcosa), che era ben diversa dalle ultime. Avevo provato ad adattarla in un'ultima versione, ma non c'ero riuscito, avevano cambiato molte cose. Ho provato pure a compilarla nella versione di LLVM che dicevano loro, ma anche li non compilava. Credo che quella patch fosse incompleta e non avesse mai funzionato.

PowerPC dovrebbe essere molto ben supportata, IBM stessa è interessata al progetto. ARM dovrebbe essere sulla stessa strada.

E comunque LLVM ha backend anche per processori ben più limitati del 68k, quindi non credo ti devi preoccupare.
Ho visto che alcuni hanno creato un backend per Z80, devo dargli sicuramente un'occhiata!

[cdimauro]

• 

p.s.
vedi perché pepita inizialmente usava BRAM per avere oltre 1024 registri ? Tutti quei modelli di compilatori assumono che l'architettura virtuale abbia infiniti registri, poi fanno seguire una fase di fitting in cui si ripiega sulle risorse finite del target reale

io ho attualmente riservato 10 bit, e posso averne anche 12 volendo, quanto aiuta ?

Io continuo a credere che 1024 son troppi, di sicuro non per problemi col compilatore (che più registri ha meglio è), ma per problematiche tipo salvataggio del contesto durante context-switch.

Già. Il processore passerebbe parecchio tempo prezioso a salvare e caricare tutti quei registri...

In più, è vero che i compilatori lavorano come se avessero un numero infinito di variabili, ma quel che conta è vedere quali sono i valori che rimangono effettivamente nei registri, perchè se abbiamo ad esempio un codice del genere:

Codice: [Seleziona]

%0 = 3
%1 = %0 + 5
%2 = %1 / 4
%3 = %2 + %0
è evidente che quel che ci serviva erano solo 2 registri invece che 4 variabili temporanee SSA!

Per esempio, ho compilato con clang un file di un mio videogioco che contiene una funziona assai complessa, con switch -O3, e l'IR generato raggiungeva le 3000 variabili temporanee!
Vuol questo dire che quella funzione girerebbe più velocemente su un processore da 3000 registri? Probabilmente no, perchè molti pezzi della funzione sono calcoli a se stanti che generano pochi valori in output (anzi, in questo caso inseriscono dei valori in delle liste).

Infatti poi provvede l'ottimizzatore a scegliere oculatamente i registri reali. Non c'è da preoccuparsi.

Bisognerebbe avere un tool che trova il minor numero di registri per avere un'esecuzione ottimale del codice... probabilmente si può hackerare LLVM per ottenere una simile statistica ma non voglio nemmeno pensare la quantità di lavoro (probabilmente il codice si presta già, ma bisognerebbe imparare tutto il sorgente prima di metterci mano, e io ho solo una vita).

Dovrebbe esserci già qualcosa del genere, anche se mi sembra che LLVM non utilizzi l'algoritmo di colorazione dei grafi per conoscere quali registri utilizzare effettivamente. Ma non ci metto la mano sul fuoco: ho letto una caterva di informazioni su LLVM, e può essere che mi sia sbagliato.

Piuttosto userei la BRAM, come ti avevo accennato, per creare più set di registri che l'OS può scambiare con una singola istruzione, per avere context-switch velocissimi.

ARM-style, insomma. Comodo se t'interessa un sistema real-time. Ma mi sembra che soluzioni del genere creino problemi d'implementazione; infatti ARMv8 aka ARM64 non supporta più lo shadowing dei registri nelle diverse modalità d'esecuzione.

Sì, ma non è così semplice realizzare un backend. Mi sono smazzato anche il link che mi hai fornito riguardo all'assembler/disassembler, e c'è parecchio lavoro. Oltre al fatto che LLVM in alcune parti è ancora immaturo o incompleto, per cui ti costringe anche a scrivere direttamente codice C++ se vuoi sfruttare (molto) meglio le caratteristiche della tua ISA. Ad esempio è quello che hanno fatto per supportare l'FPU x86 di x86/x64.

Mai detto fosse "facile", ma sicuramente è "più facile" rispetto altri sistemi; vuoi parlare di GCC?

Sai quanto ami GCC, vero?

LLVM almeno ha TableGen che ti permette di generare gran parte della struttura automaticamente, almeno le parti più "noiose"...
Secondo me, più che immaturità, è un po' un'esigenza: credo sia difficile accontentare così tante architetture diverse in un singolo sistema, quindi molte cose le fanno gestire a mano piuttosto che appesantire TableGen.

No, è proprio immaturità. Infatti c'è scritto che estenderanno questa parte per supportare un po' di altre cose e ricorrere il meno possibile al C++ scritto a manina. Anzi, il loro desiderio è di non ricorrervi proprio: avere tutto TableGen-driven...

Rimane comunque il casino immenso di dover ricorrere a un assemblatore e linker esterno per generare codice.

Beh se vuoi avere solo un output binario per test e statistiche, lasci stare i linker e crei solo l'assemblatore integrato,che in realtà non è un assemblatore, semplicemente una passata che invece di generare li codice in formato testuale (assembly), lo genera direttamente in binario.
Intanto fai questo, che ti porta già a molte cose interessanti.

No, in questo modo i risultati non sarebbero ottimali. Bisogna generare più passate per ottimizzare al meglio gli offset dei salti e dei riferimenti alla memoria.

La densità di codice è molto importante.

Altra cosa, purtroppo manca ancora l'architettura 68000. Per cui credo che certe ottimizzazioni non siano state nemmeno prese in considerazione da chi ha sviluppato LLVM. Anche se devo dire che qualcosa per PowerPC c'è, e pure per ARM, per cui magari si può vedere come hanno implementato o risolto certi problemi.

C'era un backend di terze parti per 68k, però era sia riferito a una vecchissima versione di LLVM (2.qualcosa), che era ben diversa dalle ultime. Avevo provato ad adattarla in un'ultima versione, ma non c'ero riuscito, avevano cambiato molte cose. Ho provato pure a compilarla nella versione di LLVM che dicevano loro, ma anche li non compilava. Credo che quella patch fosse incompleta e non avesse mai funzionato.

So che ci sta lavorando qualcuno vicino ad AROS. In particolare è interessato ad AROS/68K. Ma credo che sia(no) ancora in alto mare. Purtroppo.

PowerPC dovrebbe essere molto ben supportata, IBM stessa è interessata al progetto. ARM dovrebbe essere sulla stessa strada.

Sì, ho visto. Infatti per alcune cose si può sbirciare a queste architetture, anche se non quanto sia diversa l'implementazione del loro backend.

E comunque LLVM ha backend anche per processori ben più limitati del 68k, quindi non credo ti devi preoccupare.
Ho visto che alcuni hanno creato un backend per Z80, devo dargli sicuramente un'occhiata!

Beh, ma lo Z80 è semplice. E' quasi un RISC.

Il 68K è una brutta bestia (in tutti sensi, sia positivamente sia negativamente), e certe cosucce non le ritrovi nelle altre architetture supportate da LLVM.

Per questo motivo immagino che bisognerebbe cambiare un po' anche l'ottimizzatore, e questo credo che non sia così facile come scrivere "soltanto" il backend...

[Z80Fan]

• 

No, è proprio immaturità. Infatti c'è scritto che estenderanno questa parte per supportare un po' di altre cose e ricorrere il meno possibile al C++ scritto a manina. Anzi, il loro desiderio è di non ricorrervi proprio: avere tutto TableGen-driven...

Sarebbe una magnifica cosa! Vedendo l'incredibile sviluppo di questo progetto, probabilmente ci arriveranno in pochi anni.

No, in questo modo i risultati non sarebbero ottimali. Bisogna generare più passate per ottimizzare al meglio gli offset dei salti e dei riferimenti alla memoria.

Questo interessa anche a me perchè in un po' tutte le mie ISA metto (se ci stanno) delle istruzioni per salti "veloci" che indicano l'offset in word a cui saltare direttamente nell'opcode (senza un dato immediato insomma); non credo sia una cosa così stramba che non ci abbiano pensato; probabilmente vengono già eseguite più passate per poter scegliere sempre meglio la miglior istruzione da usare...

Il 68K è una brutta bestia (in tutti sensi, sia positivamente sia negativamente), e certe cosucce non le ritrovi nelle altre architetture supportate da LLVM.

Hai qualche esempio?

Per questo motivo immagino che bisognerebbe cambiare un po' anche l'ottimizzatore, e questo credo che non sia così facile come scrivere "soltanto" il backend...

Si possono aggiungere passate di ottimizzazione che lavorano però sull'IR; non so invece se ci sono ottimizzazioni sul codice macchina.
Intanto comincio a leggere questo link, e se trovo qualcosa di interessante lo riporto qui.
http://llvm.org/docs/CodeGenerator.html

@legacy:
Esatto, come pensavo io. Bisognerebbe vedere se dare 16 o 32 registri, forse Cesare può darci qualche consiglio...

[cdimauro]

• 

OK, ma non mi pare molto, visti anche i vantaggi. Quant'è lunga la tua pipeline?

Non l'ho implementata, ma e' in fase di bozza, dato che la maggior parte delle istruzioni impiega 5 step, pensavo a 5 stadi, pero' per il calcolo dell'EA complesso ne servono altri 2 per un totale di 7.

Due in più su 5 sono decisamente tanti. Devo supporre che la tua architettura lavori a clock bassi, vista la pipeline così corta.

In questo caso sarebbe meglio evitare di aggiungere i due stadi, a meno che non organizzi meglio la pipeline e riesci a spalmare nei due stadi altro "lavoro utile", riuscendo quindi a far salire il clock raggiungibile.

Io continuo a credere che 1024 son troppi, di sicuro non per problemi col compilatore (che più registri ha meglio è), ma per problematiche tipo salvataggio del contesto durante context-switch.

il push pop automatico e' vietato perche' costa 2 cicli in piu', per cui e' manuale, o meglio opzionale, come lo e' nel MIPS.
Quello che posso fare e' usare un indice aggiuntivo per spiazzare al volo quei registri creando un registro speciale di indice per i softregister, in questo modo puoi dividere quei 1024 registri per 32 ottenendo 32 indici di offset, ovvero puoi servire all'istante 32 context switch senza spostare assolutamente nulla, ti basta caricare il taskID nel registro indice dei registri e questo verra' aggiunto

ovvero ottieni una cosa del genere
typedef struct
{
uint32_t r[32];
} reg_t;

reg_t reg[32];
uint32_t reg_i;

uint32_t taskid;

….


reg_i = taskid; /* context switch */
reg[taskid].r[..] = ….


tutto questo in hw, attivabile a piacere, o disattibabile, ma se attivato il context switch costa solo l'indice taskid

Niente indici da sommare, legacy. Supponendo di avere 1024 registri totali da voler suddividere in blocchi da 32 registri, ti basta organizzare i task id in modo da essere già in partenza shiftati a sinistra di 5. In questo modo per accedere al registro 23 del terzo task (che ha id 2 << 5 = 64), è sufficiente eseguire l'or: 64 OR 23 = 87.
L'or è meno dispendioso di una somma, e nel caso di implementazione hardware hai il vantaggio di... non eseguirlo nemmeno. Infatti prendi le 5 linee (se hai 32 registri) che indicano il registro a cui si vuole accedere, le 5 linee "alte" (dalla sesta alla decima; ignorando, quindi, le 5 linee / bit bassi) del task id, le "metti assieme", e hai ottenuto il tuo id del registro. Semplice e veloce...

essendo stack e memoria esterna alla fpga, volendo posso usare tutta la bram che mi avanza per avere + task servibili in hw, quindi bram per farne registri, attualmente ho 12 bit disponibili quindi 4096 registri massimi (ognuno da 32bit), quindi 128 task servibili ognuno da 32 registri da 32 bit.

vanno bene 32 registri fisici per task ?

Dipende da quello che devi farci col tuo processore. Per usi embedded direi che 16 sono già tantissimi. Per un uso con algoritmi più complessi, mettine 32 e dormi sonni tranquilli...

[cdimauro]

• 

No, è proprio immaturità. Infatti c'è scritto che estenderanno questa parte per supportare un po' di altre cose e ricorrere il meno possibile al C++ scritto a manina. Anzi, il loro desiderio è di non ricorrervi proprio: avere tutto TableGen-driven...

Sarebbe una magnifica cosa! Vedendo l'incredibile sviluppo di questo progetto, probabilmente ci arriveranno in pochi anni.

Beh, sono anni che ci lavorano. E dietro ormai c'è pure Apple...

No, in questo modo i risultati non sarebbero ottimali. Bisogna generare più passate per ottimizzare al meglio gli offset dei salti e dei riferimenti alla memoria.

Questo interessa anche a me perchè in un po' tutte le mie ISA metto (se ci stanno) delle istruzioni per salti "veloci" che indicano l'offset in word a cui saltare direttamente nell'opcode (senza un dato immediato insomma);

Figurati la mia, che ha pure un'altra cosuccia interessante a riguardo.

non credo sia una cosa così stramba che non ci abbiano pensato; probabilmente vengono già eseguite più passate per poter scegliere sempre meglio la miglior istruzione da usare...

Non è che non ci abbiano pensato, ma hanno scaricato tutto sull'assemblatore. Di queste cose, infatti, è lui che ne occupa, impiegando più passate per ottimizzare al meglio salti e offset.

Il 68K è una brutta bestia (in tutti sensi, sia positivamente sia negativamente), e certe cosucce non le ritrovi nelle altre architetture supportate da LLVM.

Hai qualche esempio?

Le istruzioni con due operandi in memoria, ad esempio. Nessuna di quelle architetture le supporta; soltanto il 68K. Per cui al 99% non c'avranno nemmeno pensato a come supportarle.

Per questo motivo immagino che bisognerebbe cambiare un po' anche l'ottimizzatore, e questo credo che non sia così facile come scrivere "soltanto" il backend...

Si possono aggiungere passate di ottimizzazione che lavorano però sull'IR; non so invece se ci sono ottimizzazioni sul codice macchina.
Intanto comincio a leggere questo link, e se trovo qualcosa di interessante lo riporto qui.
http://llvm.org/docs/CodeGenerator.html

E' quello che mi sono smazzato ieri.

@legacy:
Esatto, come pensavo io. Bisognerebbe vedere se dare 16 o 32 registri, forse Cesare può darci qualche consiglio...

Prima deve dirci lui cosa vuole farne di quel processore.

[Z80Fan]

• 

Beh, sono anni che ci lavorano. E dietro ormai c'è pure Apple...

Beh Apple c'era già dal 2005 (che si è comprata gli sviluppatori originali per continuare il progetto), ma insomma, 8-9 anni saranno anche tanti, però in confronto agli altri compilatori esistenti che son ben più vecchi si può dire che ha subito un'evoluzione molto veloce, e poi solo da pochi anni è diventato un compilatore "serio" che poteva competere con la concorrenza...

Non è che non ci abbiano pensato, ma hanno scaricato tutto sull'assemblatore. Di queste cose, infatti, è lui che ne occupa, impiegando più passate per ottimizzare al meglio salti e offset.

Capisco. Tu credi che si possa fare un'ottimizzazione del genere direttamente durante la selezione delle istruzioni? Perchè credo che per questo ti serva già sapere quanto è lungo il blocco di codice tra il salto e la destinazione per scegliere l'istruzione migliore...
Si, forse si può fare, come ultimissimo passaggio dell'ottimizzatore. Bisognerebbe leggere la lista di passate già implementate per vedere se c'è qualcosa del genere. Per il momento puoi sempre fare un trick: a LLVM indichi che il tuo target ha un'istruzione "di salto", e poi durante la generazione del linguaggio macchina, per quella istruzione vedi quanto distante è il target del salto e scegli la "vera" istruzione da usare.

Le istruzioni con due operandi in memoria, ad esempio. Nessuna di quelle architetture le supporta; soltanto il 68K. Per cui al 99% non c'avranno nemmeno pensato a come supportarle.

Bisognerebbe dargli una tale istruzione e vedere come si comporta. Se l'IR ha la possibilità di fare trasferimenti memoria-memoria, allora credo che già la selezione delle istruzioni farà quel lavoro...

nelle considerazioni fatte poi pensavo a quanto e' fastidioso usare lo stack perché costa cicli asincroni esterni potenzialmente lunghissimi (rispetto ai cicli cpu) a seconda di quanto e' lenta la ram

E usare la BRAM come stack interno? Visto che lo stack è la zona di memoria forse più usata, ha senso tenerla lì. Per semplificare il funzionamento, puoi fare che quando il processo corrente va oltre il limite (superiore o inferiore) di stack interno, viene eseguito un interrupt e l'OS può salvare in RAM lo stack interno e riposizionare lo SP interno.
Questo però ti rallenta un context switch perchè devi salvare e ripristinare anche lo stack, e in più ci possono essere casi patologici dove un processo entra ed esce da molte funzioni, e il suo stack pointer è proprio al limite della pagina di ram interna: l'OS verrebbe chiamato ogni volta con incredibile rallentamento dell'esecuzione, quindi forse è meglio lasciar fare alla cache.

[Z80Fan]

• 

Beh se vuoi fare qualcosa di embedded credo che 4-8 KB siano sufficienti, a meno che tu non stia pensando di fare strani algoritmi ricorsivi!

Le istruzioni con due operandi in memoria, ad esempio. Nessuna di quelle architetture le supporta; soltanto il 68K. Per cui al 99% non c'avranno nemmeno pensato a come supportarle.

Bisognerebbe dargli una tale istruzione e vedere come si comporta. Se l'IR ha la possibilità di fare trasferimenti memoria-memoria, allora credo che già la selezione delle istruzioni farà quel lavoro...

Continuando su questo discorso: ho (ri)letto questa guida che spiega i vari passaggi in cui passa un'istruzione in LLVM:
http://eli.thegreenplace.net/2012/11/24/life-of-an-instruction-in-llvm/

e ho fatto un po' di prove su una semplice funzione:
Son partito da questo sorgente:

Codice: [Seleziona]

void prova(int a[10], int b[10])
{
    for(int i = 0; i < 10; i++)
         a[i] += b[i];
}
Passandolo per Clang, generando l'IR e ottimizzandolo un po', esce questo IR (ho rimosso delle parti non importanti per questo discorso):

Codice: [Seleziona]

; Function Attrs: nounwind uwtable
define void @prova(i32* nocapture %a, i32* nocapture readonly %b) #0 {
  br label %1

; <label>:1                                       ; preds = %1, %0
  %indvars.iv = phi i64 [ 0, %0 ], [ %indvars.iv.next, %1 ]
  %2 = getelementptr inbounds i32* %b, i64 %indvars.iv
  %3 = load i32* %2, align 4, !tbaa !1
  %4 = getelementptr inbounds i32* %a, i64 %indvars.iv
  %5 = load i32* %4, align 4, !tbaa !1
  %6 = add nsw i32 %5, %3
  store i32 %6, i32* %4, align 4, !tbaa !1
  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
  %exitcond = icmp eq i64 %indvars.iv.next, 10
  br i1 %exitcond, label %7, label %1

; <label>:7                                       ; preds = %1
  ret void
}
Si vede che i caricamenti sono tutti separati, addirittura il calcolo dell'indirizzo di memoria (getelementptr) è separato dall'effettiva operazione di caricamento (load).
Questo codice entra in llc, che esegue tutti i passaggi fino alla generazione del codice macchina. Passati altri passaggi di ottimizzazione, dal DAG viene eseguito l'Instruction selection, che genera questo come primo passaggio:

Codice: [Seleziona]

# *** IR Dump Before Expand ISel Pseudo-instructions ***:
# Machine code for function prova: SSA
Function Live Ins: %RDI in %vreg2, %RSI in %vreg3

BB#0: derived from LLVM BB %0
    Live Ins: %RDI %RSI
%vreg3<def> = COPY %RSI; GR64:%vreg3
%vreg2<def> = COPY %RDI; GR64:%vreg2
%vreg5<def> = MOV32r0 %EFLAGS<imp-def,dead>; GR32:%vreg5
%vreg4<def> = SUBREG_TO_REG 0, %vreg5<kill>, 4; GR64:%vreg4 GR32:%vreg5
    Successors according to CFG: BB#1

BB#1: derived from LLVM BB %1
    Predecessors according to CFG: BB#0 BB#1
%vreg0<def> = PHI %vreg4, <BB#0>, %vreg1, <BB#1>; GR64_NOSP:%vreg0 GR64:%vreg4,%vreg1
%vreg6<def> = MOV32rm %vreg3, 4, %vreg0, 0, %noreg; mem:LD4[%scevgep2](tbaa=<badref>) GR32:%vreg6 GR64:%vreg3 GR64_NOSP:%vreg0
ADD32mr %vreg2, 4, %vreg0, 0, %noreg, %vreg6<kill>, %EFLAGS<imp-def,dead>; mem:ST4[%scevgep](tbaa=<badref>) LD4[%scevgep1](tbaa=<badref>) GR64:%vreg2 GR64_NOSP:%vreg0 GR32:%vreg6
%vreg1<def,tied1> = INC64r %vreg0<tied0>, %EFLAGS<imp-def,dead>; GR64:%vreg1 GR64_NOSP:%vreg0
%vreg7<def,tied1> = SUB64ri8 %vreg1<tied0>, 10, %EFLAGS<imp-def>; GR64:%vreg7,%vreg1
JNE_4 <BB#1>, %EFLAGS<imp-use>
JMP_4 <BB#2>
    Successors according to CFG: BB#2(4) BB#1(124)

BB#2: derived from LLVM BB %5
    Predecessors according to CFG: BB#1
RET

# End machine code for function prova.
Si vede che le istruzioni "virtuali" sono state sostituite con istruzioni reali del backend x86_64 (COPY, MOV32r0, MOV32rm, ADD32mr etc.), alcuni registri fissi sono stati già allocati (RSI, RDI, ovvero i due registri dove passare puntatori secondo la calling convention x86), mentre rimangono ancora dei registri virtuali SSA (%vreg0, %vreg1...).

Un'altra cosa molto interessante è che i vari gruppi di getelementptr/load/add/store sono stati sostituiti dalle due istruzioni più appropriate: MOV32rm e ADD32mr (che penso stiano per registro-memoria e memoria-registro).

Vengono quindi eseguite molti altri passaggi di ottimizzazione e selezione per scendere sempre più verso il linguaggio macchina, arrivando a questa rappresentazione:

Codice: [Seleziona]

# *** IR Dump Before Branch Probability Basic Block Placement ***:
# Machine code for function prova: Post SSA
Function Live Ins: %RDI in %vreg2, %RSI in %vreg3

BB#0: derived from LLVM BB %0
    Live Ins: %RDI %RSI
%EAX<def> = MOV32r0 %EFLAGS<imp-def,dead>, %RAX<imp-def>
    Successors according to CFG: BB#1

BB#1: derived from LLVM BB %1
    Live Ins: %RDI %RSI %RAX
    Predecessors according to CFG: BB#0 BB#1
%ECX<def> = MOV32rm %RSI, 4, %RAX, 0, %noreg; mem:LD4[%scevgep2](tbaa=<badref>)
ADD32mr %RDI, 4, %RAX, 0, %noreg, %ECX<kill>, %EFLAGS<imp-def,dead>; mem:ST4[%scevgep](tbaa=<badref>) LD4[%scevgep1](tbaa=<badref>)
%RAX<def,tied1> = INC64r %RAX<kill,tied0>, %EFLAGS<imp-def,dead>
CMP64ri8 %RAX, 10, %EFLAGS<imp-def>
JNE_4 <BB#1>, %EFLAGS<imp-use,kill>
    Successors according to CFG: BB#2(4) BB#1(124)

BB#2: derived from LLVM BB %5
    Predecessors according to CFG: BB#1
RET

# End machine code for function prova.
Si vede che tutti i registri fisici son stati allocati (infatti il commento iniziale indica "post SSA"), e da questa rappresentazione si può finalmente generare il linguaggio macchina finale (che in questo caso è assembly, ma può anche essere binario):

Codice: [Seleziona]

.text
.globl prova
.align 16, 0x90
.type prova,@function
prova:                                  # @prova
.cfi_startproc
# BB#0:
xorl %eax, %eax
.align 16, 0x90
.LBB0_1:                                # =>This Inner Loop Header: Depth=1
movl (%rsi,%rax,4), %ecx
addl %ecx, (%rdi,%rax,4)
incq %rax
cmpq $10, %rax
jne .LBB0_1
# BB#2:
ret
.Ltmp0:
.size prova, .Ltmp0-prova
.cfi_endproc


.ident "Ubuntu clang version 3.4-1~exp1 (trunk) (based on LLVM 3.4)"
.section ".note.GNU-stack","",@progbits

Un'altro output interessante è questo, che mostra vicino all'istruzione reale, la rappresentazione interna dello stadio MC:

Codice: [Seleziona]

.file "<stdin>"
.text
.globl prova
.align 16, 0x90
.type prova,@function
prova:                                  # @prova
.cfi_startproc
# BB#0:
xorl %eax, %eax              # <MCInst #5306 XOR32rr
                                        #  <MCOperand Reg:19>
                                        #  <MCOperand Reg:19>
                                        #  <MCOperand Reg:19>>
.align 16, 0x90
.LBB0_1:                                # =>This Inner Loop Header: Depth=1
movl (%rsi,%rax,4), %ecx     # <MCInst #1579 MOV32rm
                                        #  <MCOperand Reg:22>
                                        #  <MCOperand Reg:43>
                                        #  <MCOperand Imm:4>
                                        #  <MCOperand Reg:35>
                                        #  <MCOperand Imm:0>
                                        #  <MCOperand Reg:0>>
addl %ecx, (%rdi,%rax,4)     # <MCInst #84 ADD32mr
                                        #  <MCOperand Reg:39>
                                        #  <MCOperand Imm:4>
                                        #  <MCOperand Reg:35>
                                        #  <MCOperand Imm:0>
                                        #  <MCOperand Reg:0>
                                        #  <MCOperand Reg:22>>
incq %rax                    # <MCInst #949 INC64r
                                        #  <MCOperand Reg:35>
                                        #  <MCOperand Reg:35>>
cmpq $10, %rax               # <MCInst #577 CMP64ri8
                                        #  <MCOperand Reg:35>
                                        #  <MCOperand Imm:10>>
jne .LBB0_1                 # <MCInst #1131 JNE_1
                                        #  <MCOperand Expr:(.LBB0_1)>>
# BB#2:
ret                             # <MCInst #2321 RET>
.Ltmp0:
.size prova, .Ltmp0-prova
.cfi_endproc


.ident "Ubuntu clang version 3.4-1~exp1 (trunk) (based on LLVM 3.4)"
.section ".note.GNU-stack","",@progbits


Quindi, secondo me, se un backend ha un'istruzione che prende due indirizzi di memoria, il selettore delle istruzioni non dovrebbe aver difficoltà nel ridurre l'intero blocco getelementptr/load/getelementptr/load/add/store in una singola istruzione macchina.

[cdimauro]

• 

Credo che i vantaggi siano due: il primo è che più facile realizzare backend per architetture diverse usando un SSA piuttosto che un AST.

Il secondo è che l'SSA permette tutta una serie di ottimizzazioni che sono semplici più implementare rispetto all'AST.

Un AST può essere SSA-based

E' vero, ne può far uso, ma il concetto di AST è generale.

Ho trovato molto comodo ed elegante ottimizzare/modificare grosse quantità di informazioni su una struttura dati ad albero che su una sequenza di istruzioni di codice. Per esempio slinkando un nodo ti porti via o dietro tutto il codice blocco dipendente che è distribuito in tutto il ramo a cui fa riferimento il nodo, mentre su una sequenza la cosa è molto più complicata (o comunque va bene su modifiche molto locali e vicine tra di loro).

Un AST può anche far uso di sequenze per rappresentare certi tipi di dati. Ad esempio le tuple, liste, insiemi e dizionari in Python.

Nel mio WPython ho implementato diverse ottimizzazioni, sia usando la rappresentazione grezza che è state costruita dal parser (mi pare si chiamasse ASDL), sia nell'AST, sia nel peepholer. Ognuno ha pro e contro, e dunque ottimizzazioni che sono più o meno semplici.

Secondo me la generazione di codice intermedio o non deve essere verso la fine, quando il grosso del lavoro è in gran parte finito

Vedi sopra. Credo sia meglio sfruttare tutti gli stadi a disposizione.

[cdimauro]

• 

Due in più su 5 sono decisamente tanti. Devo supporre che la tua architettura lavori a clock bassi, vista la pipeline così corta.

Non e' pensata per implementazioni al Ghz, punto a quanto disponibile per le fpga di fascia bassa, ovvero 50 max 100Mhz, oltre ci sono casini anche con i tools di sviluppo, oltre al fatto che anche il mio LA non segue nulla oltre i 100Mhz.

A parte cio' ora e' senza pipeline o meglio ci sono gli stadi della pipeline ma non lavorano in parallelo ma in modo sequenziale, e fatta così impiega mediamente 2 colpi di clock per stadio (necessari per forti constraints di stabilizzazione interni), ovvero 2 x 5 = 10 colpi di clock per tutte le classi di istruzione eccetto le load store che aprono n cicli addizionali in base a quando risponde la controparte in DTACK (e potenzialmente potrebbe anche non rispondere mai tenendo la CPU sospesa … dovrò aggiungere hw di timeout, ovviamente esterno, con propagazione su /bus_err).

Cicli assolutamente regolari, e parlamo di una cadrega che con CLK=50Mhz sputa fuori 50Mhz/10 = 5MIPS senza pipeline e senza cache.

E' un bidone 

Capisco. Beh, hai puntato sulla semplicità di implementazione, piuttosto che a spremere al massimo quello che hai.

Comunque potresti prova a spalmare un po' di lavoro dei 5 stati nei 2 stadi di calcolo dell'EA. Magari in questo modo riesci a risparmiare qualche stadio, pur implementando l'EA più avanzata.

Altra cosa, visto che hai tanti registri potresti anche pensare di realizzare una bella unità SIMD.

[cdimauro]

• 

Altra conquista, oggi ho messo a posto un casino che non permetteva il test and branch, ovvero adesso e' possibile una cosa del genere

bra.ifeq $1,$2, offset   ; if (reg[$1]==reg[$2]) PC+=offset
bra.ifeq $1,$2, $3  ; if (reg[$1]==reg[$2]) PC=reg[$3]

prima dovevo passare dalla cmp
cmp.ifeq $4, $1,$2 ; if (reg[$1]==reg[$2]) reg[$4]=True else reg[$4]=False
bra $4, offset ; if (reg[$4]==True) PC+=offset
bra $4, $3 ; if (reg[$4]==True) PC=reg[$3]

Il casino era dato dallo stadio che accede in lettura alla bram registri per produrre {source1,source2,reg_target,EA_in,EA_out,EA_next_fetch}
(non tutti usati, dipende da cosa serve alla istruzione specifica, pero' quel modulo produce tutte le informazioni necessarie, tutto in parallelo)
due letture richiedevano uno stadio in + e quindi avevo spezzato su due istruzioni, adesso ho risolto quel casino e si risparmia anche un registro

Hai fatto benissimo, perché è un pattern molto ricorrente. Nella mia ISA purtroppo c'è poco spazio nella opcode table, per cui ho potuto definire soltanto quella di salto se due registri sono diversi; ovviamente in ottica loop (finché i valori sono diversi, si salta; si esce soltanto se sono uguali).