Fa il Perfect Compiler le differenze della fonte di briscola

No:

Innanzitutto, notiamo che ci sono molte, molte sequenze di codice equivalenti ma diverse per quanto riguarda il codice macchina (figuriamoci altri linguaggi). Un caso semplice scambia due registri in cui le prestazioni sono equivalenti.

In secondo luogo, il carico di lavoro per programmi / applicazioni può essere molto variabile. Non esiste una perfetta sequenza di codice, solo migliore o peggiore per un determinato caso di prova o un insieme di casi di test. Dal momento che una sequenza può funzionare meglio su un test (o test), mentre un'altra sequenza su un altro test (o test) - in astratto - non possiamo giudicare in modo assoluto quale sequenza è migliore: dovremmo valutare l'importanza relativa dei casi di test , che, penso, vaga fuori dalla portata della tua domanda.

In terzo luogo, dovremmo notare che la nozione degli stessi algoritmi utilizzati da due persone diverse è problematica in quanto i compilatori usano una così grande varietà di euristiche governate da fattori di ottimizzazione. Non c'è ragione di credere, un priore, che i fattori di accordatura siano gli stessi anche se gli algoritmi lo sono. Tuttavia, anche se gli algoritmi sono uguali, dobbiamo esaminare il livello di astrazione dell'applicazione dell'algoritmo. Un algoritmo sufficientemente astratto consentirà una grande latitudine nell'ordinare soluzioni totalmente equivalenti, che risulterebbero, come solo un esempio, in diverse scelte di registro e quindi in diverse sequenze di codice.

No, questo è teoricamente impossibile. Il motivo è che questo corrisponde alla capacità di determinare l'equivalenza di due algoritmi, che appartiene alla classe dei problemi indecidibili.

Supponiamo che il tuo compilatore perfetto sia possibile. Quindi, puoi semplicemente trasformarlo in un dimostratore di equivalenza. Prendi l'algoritmo A e l'algoritmo B, compila entrambi e poi confronta semplicemente il codice macchina risultante. Poiché il confronto del codice macchina è banale (e quindi può essere implementato), il compilatore perfetto che descrivi deve essere impossibile da implementare.

Perché il test di equivalenza è impossibile da implementare? Vedi link .

In una certa misura, sì. Molte applicazioni sensibili alla sicurezza come Tor e Bitcoin creano un processo di compilazione che è build deterministico . Questo processo di compilazione consente a più persone di compilare lo stesso codice sorgente per produrre l'esatta build identica bit-to-bit.

Il grosso problema qui è determinare quale sia il codice sorgente equivalente. È possibile ottenere una lunga strada se si spoglia il codice compilato in modo che il codice che si ottiene build identica se semplicemente rinominare le variabili, e fare l'ottimizzazione dell'eliminazione del codice morto. Dovresti quindi evitare le ottimizzazioni non deterministiche, mentre continui a fare ottimizzazioni che possono eliminare le differenze superficiali tra i diversi modi in cui le persone scrivono il codice (ad esempio for-loop vs while-loop). Disabilitare le ottimizzazioni che potrebbero far sì che il compilatore produca codici duplicati contribuirebbe anche a ridurre ogni possibilità che il compilatore producesse un sacco di codice simile con solo lievi differenze per le ottimizzazioni (in gcc, forse abilitare l'ottimizzazione per le dimensioni). Più difficile è decidere se il codice che si basa su una serie di istruzioni if rispetto al codice che utilizza l'ereditarietà della classe per selezionare il percorso del codice dovrebbe essere considerato lo stesso se si comportano allo stesso modo.

Un altro aspetto che può rendere questo compilatore più o meno difficile da creare è il set di istruzioni della macchina target. Una macchina di destinazione basata su registro come x86 è probabilmente più difficile per questo scopo, dal momento che è necessario selezionare alcuni registri con le istruzioni e ci sono molti codici macchina funzionalmente equivalenti che sono diversi solo dalle loro allocazioni di registro. Un computer di destinazione basato sullo stack come JVM è probabilmente più semplice per questo scopo poiché il set di istruzioni presuppone sempre che la parte superiore dello stack sia ordinata in modi specifici, quindi il codice che funziona allo stesso modo sarebbe più probabile che finisca con un codice macchina simile di quello basato su registro lingua di destinazione. Nota che molti compilatori compilano in realtà prima un linguaggio intermedio basato su un linguaggio stack machine, prima di eseguire ottimizzazioni e allocazioni di registro.

In definitiva, tuttavia, ciò che rende questa roba davvero difficile è la definizione di ciò che è identico è molto soggettivo e non c'è sempre una risposta giusta. Cose come la garanzia di concorrenza, codice che altrimenti si comportano in modo identico in un'applicazione a thread singolo possono comportarsi in modo diverso nello scenario multi-thread a causa delle differenze nei punti di sequenza , dovrebbero essere trattati come lo stesso codice o diverso? O se un codice usa il bubble sort e l'altro usa l'ordinamento rapido, dovrebbero essere considerati come lo stesso o diverso codice? Per quanto riguarda il codice che sono solo diversi nel tipo di dati che usano (ad esempio, int vs float long, single vs double precision), dovrebbero essere considerati lo stesso codice o altro. Quando si analizzano questi problemi, ci sono molti worm in questo modo che rende non ovvio ciò che dovrebbe essere considerato equivalente rispetto a un codice diverso.