Una domanda sulla natura dell'assemblaggio generato in C ++ e codice Algebra

3

Ho scritto questo codice:

#include <iostream>
int main()
{
    int a;
    std::cin >> a;
    if(a*a== 3){
        std::cout << a;
    }
    return 0;
}

In MSVC ho attivato tutti i flag di ottimizzazione. Mi aspettavo che dal momento che * a non può mai essere 3, il compilatore non dovrebbe generare codice per la sezione:

if(a*a== 3){
    std::cout << a;
}

Tuttavia ha generato il codice per la sezione. Non ho controllato GCC o LLVM / CLang.

Quali sono i limiti di aspettativa da un compilatore C ++ in questi scenari?

    
posta nature1729 26.04.2012 - 21:49
fonte

6 risposte

7

Il controllo di alcuni valori letterali piuttosto specifici come if (0) , if (1) , if (LOG_LEVEL > 1) ', ecc. è piuttosto routine.

Controllare che un numero sia un quadrato perfetto in modo che la quadratura di un intero possa produrre quel valore? Sarei sorpreso di vedere un compilatore farlo. Indubbiamente potrebbe essere fatto - è in realtà più semplice di un sacco di cose che sono state fatte. Allo stesso tempo, la maggior parte di tali ottimizzazioni fa sì che il compilatore funzioni almeno un pochino più lentamente, e dubito che qualcuno voglia rallentare il compilatore per qualcosa che probabilmente verrà usato ovunque così raramente.

    
risposta data 26.04.2012 - 22:06
fonte
3

L'ottimizzazione del compilatore è normalmente progettata per evitare ripetizioni, rami di località, eliminare copie al rientro, ecc. Possono rimuovere rami impossibili dopo un'analisi statica (che coinvolge solo costante)

Ma, normalmente, il compilatore non valuta le espressioni contenenti variabili poiché assume che il loro valore dipenda dall'input. I compilatori non possono produrre inferenza sui valori (dicendo "nessun intero può quadrare in 3" è -at tutti gli effetti- un teorema da dimostrare, e la dimostrazione automatica dei teoremi può essere dimostrata come non decidibile per MT problema: se complico molto l'espressione, dimostri che il "campo dell'esistenza" può richiedere ... la creatività: qualcosa che i computer non hanno per loro stessa natura: macchine a stati finiti).

Un compilatore può fare questo tipo di ottimizzazione solo per un numero finito e predeterminato di casi (e -frankly- Penso che le statistiche sulle richieste degli utenti non giustificano l'interesse per l'ottimizzazione dell'espressione scritta in modo appropriato per ingannare l'ottimizzatore in giro - e può sempre essere ingannato, dal momento che in qualsiasi caso riesci a gestirlo puoi sempre immaginarne un altro che non riesca a gestire). Tentare di risolvere questo tipo di problemi in un "modo generale" prima o poi troverà un caso che metterà il compilatore in un ciclo infinito o in uno stack overflow.

    
risposta data 28.04.2012 - 15:16
fonte
0

Considera cosa succede se l'input fallisce. a può essere lasciato con un valore indefinito e possono esserci le ilarità.

Prova a inizializzarlo per primo.

    
risposta data 26.04.2012 - 21:54
fonte
0

Esiste una ricerca sui cosiddetti compilatori "superoptimizzanti" che potrebbero individuare ciò, tuttavia non tutti sono disposti ad aspettare qualche ora per la compilazione del codice.

    
risposta data 28.04.2012 - 15:46
fonte
0

Penso che l'ottimizzazione del compilatore normalmente riduca (sotto) espressioni che dipendono solo dai valori costanti.

Se un'espressione contiene variabili il cui valore è associato in fase di esecuzione, è possibile controllare solo alcune proprietà di base, ad es. quando si confronta un numero intero senza segno con 0, come questo:

unsigned int c;

...

if (c < 0)
{
   ...
}

D'altra parte, non penso che abbia senso (o che sia anche possibile) che un compilatore cerchi di indagare su proprietà più complesse di un'espressione valide per tutti i possibili input e ottimizzarle in base a ciò. Cosa fare per esempio con:

unsigned int a, b, c, n;

std::cin >> a;
std::cin >> b;
std::cin >> c;
std::cin >> n;

if (n > 2 && pow(a, n) + pow(b, n) == pow(c, n))
{
    std::cout << "OK";
}

Oltre ai possibili errori di calcolo dovuti a arrotondamenti o overflow, il programma non eseguirà mai il corpo del blocco if (si veda questo articolo di wikipedia per qualche background), ma come dovrebbe un compilatore essere in grado di determinarlo?

I teoremi di dimostrazione (per non dire scoperti) sull'espressione matematica sono troppo complessi (o anche non calcolabili in certi casi) quindi non possono essere usati come tecnica di ottimizzazione del compilatore.

    
risposta data 15.09.2012 - 10:32
fonte
0

Sono abbastanza sicuro che ci sia una domanda simile su StackOverflow con una risposta eccellente di Eric Lippert, ma SO è giù proprio ora per un po 'di manutenzione. Pubblicherò un link quando lo trovo, ma il mio ricordo è che la risposta di Lippert era sulla falsariga di:

Sì, un compilatore può controllare quel tipo di cose, ma poiché il tempo e la manodopera sono limitati, ciò significherebbe non implementare qualche altra caratteristica. Si tratta solo di una questione di priorità.

Chiedo scusa a Eric Lippert se ho sbagliato ... Di nuovo, posterò un link una volta che SO è tornato.

Aggiornamento: Ecco la risposta che stavo pensando.

    
risposta data 15.09.2012 - 22:15
fonte

Leggi altre domande sui tag