Faire le C et le C++ optimiseurs généralement connaître les fonctions ont pas d'effets secondaires?

Question

Dire pour la très les fonctions mathématiques courantes, telles que sin, cos, etc... ne le compilateur se rendre compte qu'ils ont pas d'effets secondaires et avoir la capacité de les déplacer à l'extérieur des boucles? Par exemple

// Unoptimized

double YSinX(double x,int y)
{
   double total = 0.0;
   for (int i = 0; i < y; i++)
      total += sin(x);
   return total;
}

// Manually optimized

double YSinX(double x,int y)
{
   double total = 0.0, sinx = sin(x);
   for (int i = 0; i < y; i++)
      total += sinx;
   return total;
}

Si on le peut, est-il possible de déclarer une fonction comme n'ayant pas d'effets secondaires, et donc être sûr d'optimiser de cette façon? Initiale de profilage de VS2010 app suggère que l'optimisation est bénéfique.

Voir aussi cette question connexe, qui est proche, mais n'est pas tout à fait la réponse à ma propre.

Edit: Quelques grandes réponses. Celui que j'ai accepté reposait autant sur les commentaires qu'il a provoqué que la réponse elle-même, notamment l'article lié, et le fait que le levage peut ne pas se produire dans les situations où l' errno est défini (c'est à dire un effet secondaire). En tant que tel, et dans le contexte de ce que je fais, ce type de manuel d'optimisation semble faire sens.

Answer 1

GCC a deux attributs, pure et const, qui peut être utilisé pour marquer de cette fonction. Si la fonction n'a aucun effet secondaire, et son résultat ne dépend que de ses arguments, la fonction doit être déclarée const, si les résultats peuvent également dépendre d'une variable globale, la fonction doit être déclarée pure. Les versions récentes ont également un -Wsuggest-attribute option d'avertissement qui peuvent les fonctions de point qui doit être déclarée const ou pure.

Answer 2

Ces deux citations répondre à votre question. Ils sont originaires de la norme C11. IIRC C++11 a quelque chose de similaire.

§5.1.2.3p4:

Dans la machine abstraite, toutes les expressions sont évaluées comme spécifié par la sémantique. Une mise en œuvre effective n'a pas besoin d'évaluer le cadre d'un expression si l'on peut en déduire que sa valeur n'est pas utilisée et qu'aucun besoin d'effets secondaires sont produites (y compris les éventuels causés par l'appel d'une la fonction ou l'accès à un objet volatile).

§5.1.2.3p6:

Au moins les exigences de la conformité de la mise en œuvre sont:

- Accède à la volatilité des objets sont évalués strictement selon les les règles de la machine abstraite.

- À la fin du programme, toutes les données écrites dans les fichiers doivent être identique au résultat que l'exécution du programme en fonction de la sémantique abstraite aurait produit.

- L'entrée et la sortie de la dynamique de dispositifs interactifs prennent lieu tel que spécifié dans 7.21.3. Le but de ces exigences est que les barrettes de mémoire ou de la ligne de tampon de sortie dès que possible, pour s'assurer que invitant les messages apparaissent avant un programme en attente pour d'entrée.

C'est le comportement observable du programme.

Considérons le programme suivant:

double YSinX(double x,int y)
{
    double total = 0.0;
    for (int i = 0; i < y; i++)
        total += sin(x);
    return total;
}

int main(void) {
    printf("%lf\n", YSinX(PI, 4));
}

Votre compilateur peut se rendre compte que ce programme imprime 0.0\n à chaque fois, et l'optimisation de votre programme :

int main(void) { puts("0.0"); }

C'est, en fournissant votre compilateur peut prouver que ni sin ni YsinX cause aucun besoin d'effets secondaires. Noter qu'ils peuvent (et probablement le faire) encore causer des effets secondaires, mais ils ne sont pas nécessaires pour produire la sortie de ce programme.

Vous avez posé une question sur le "compilateur". Si vous faites allusion à tous les C ou C++ implémentations, il n'y a aucune garantie d'optimisations et d'un C mise en œuvre n'a même pas besoin d'être un compilateur. Si vous faites allusion à un particulier C ou C++ mise en œuvre, je ne sais pas ce que vous faites allusion, et il n'a pas d'importance de toute façon. Si votre C ou C++ compilateur n'est pas de produire un code optimal, obtenir un nouveau compilateur ou de produire de l'optimisation de vous-même (de préférence par la modification de votre compilateur, de sorte que vous pouvez envoyer un patch pour les développeurs et ont l'optimisation automatiquement propagé à d'autres projets).

Answer 3

Ce qui est nécessaire pour permettre le levage de cette sous-expression en dehors de la boucle n'est pas la pureté, mais idempotence.

Idempotence signifie qu'une fonction peut avoir les mêmes effets secondaires et le résultat si elle est appelée une fois que si elle est appelée plusieurs fois avec les mêmes arguments. Par conséquent, le compilateur peut mettre l'appel de la fonction en dehors de la boucle, protégé uniquement par un conditionnel (par itération de la boucle au moins une fois?). Le code après le levage d'optimisation serait alors de:

double YSinX(double x,int y)
{
   double total = 0.0;
   int i = 0;
   if (i < y) {
       double sinx = sin(x);  // <- this goes between the loop-initialization
                              // first test of the condition expression
                              // and the loop body
       do {
          total += sinx;
          i++;
       } while (i < y);
   }
   return total;
}

La distinction entre __attribute__(pure) et idempotent est important parce que, comme l'adl notes dans son commentaire, ces fonctions n'ont un effet secondaire d'un paramètre errno.

Attention, cependant, parce que idempotence s'applique uniquement aux appels répétés sans période d'instructions. Le compilateur devra effectuer des flux de données, l'analyse de prouver que la fonction et le code intervenant n'interagissent pas (par exemple, le code intervenant utilise seulement les gens dont les adresses ne sont jamais pris), avant de pouvoir profiter d'idempotence. Ce n'est pas nécessaire lorsque la fonction est connue pour être pur. Mais la pureté est beaucoup plus l'état qui ne s'applique pas à de très nombreuses fonctions.

Answer 4

Je pense, oui. Si vous obtenez compilateur démontage de sortie, vous pouvez voir que, le péché est appelé dans une autre étiquette que celle de la boucle de l'étiquette de "pour": (compilé avec g++ -O1 -O2 -O3)

Leh_func_begin1:
        pushq   %rbp
Ltmp0:
        movq    %rsp, %rbp
Ltmp1:
        pushq   %rbx
        subq    $8, %rsp
Ltmp2:
        testl   %edi, %edi
        jg      LBB1_2
        pxor    %xmm1, %xmm1
        jmp     LBB1_4
LBB1_2:
        movl    %edi, %ebx
        callq   _sin ;sin calculated
        pxor    %xmm1, %xmm1
        .align  4, 0x90
LBB1_3:
        addsd   %xmm0, %xmm1
        decl    %ebx
        jne     LBB1_3 ;loops here till i reaches y
LBB1_4:
        movapd  %xmm1, %xmm0

J'espère que je suis correct.