Optimisation de boucles... - Page 1

Il semblerait que gcc se comporte bizarrement pour l'optimisation des boucles...
j'ai dans mon code une boucle comme ceci : for (i = 0; i < 6; i++)
Vu que la variable i n'est utilisée nulle part ailleurs, je m'attendais à ce que le compilateur n'en tienne pas compte (elle est déclarée tout simplement comme int) et retienne uniquement la chose importante, à savoir que la boucle est exécutée six fois, puis optimise en conséquence. Or ce n'est pas ce qu'il fait : il initialise un registre à 0, fait des addq et le compare à 5 pour tester s'il sort de la boucle...
j'essaye donc : for (i = 6; i; i--)
et là, il fait un subq en plein milieu des instructions situées à l'intérieur de la boucle () et un tst à la fin pour savoir s'il sort !
pour avoir le code que je voudrais, il faut que j'utilise : for (i = 6; --i; )
(J'utilise tigcc 0.95 bêta avec -Os)

Donc :
-- est-ce que je surestime le compilateur et qu'il vaut mieux que je récrive toutes les boucles dont je n'utilise pas la variable ?
-- ou est-ce qu'il y a un flag d'optimisation que j'aurais dû activer spécifiquement ? (mais je ne vois pas quoi)
-- ou est-ce un bug ?

Edit : j'ai rien dit

C'est bien i-- pour avoir 6 itérations

Et au vu de tes résultats, GCC n'a pas l'air de prendre vraiment l'initiative de faire des dbf dans les boucles, sauf si tu lui mets le code de BiHi, donc change ton code si tu veux qu'il fasse ça.

Ah oui, parce qu'il évalue la condition pour la première fois *avant* la première itération, évidemment.
(voilà pourquoi je préfère le for (i = 0; i < 6; i++) )
Toutes mes excuses...

Bon ben je vais modifier mes boucles alors.
Euh, dbf = decrement and branch if false ? je ne savais pas que ça existait (je ne connais pas grand-chose en assembleur), mais ce n'est pas ce que j'obtiens : j'ai subq.w #1,%d1 suivi de bne il me semble

Essaye:

 do
 {
 } while (--i);

C'est bizarre, même GCC 3.3 n'optimise pas ça? Il m'avait semblé, pourtant. Ca dépend peut-être des cas.

if false

Pas tout à fait, "if not false"

PpHd> while (i--) pour avoir un dbf, pas while (--i)...

Pourtant logiquement ça devrait être --i vu que le 68000 décrément le registre avant d'effectuer le test

Non, car le dbf teste si i=-1, alors que nous on veut que ça quitte si i=0.

Pollux: ca depend des architectures.

"dbf" ça dit pourtant assez précisément de quelle architecture je parlais

C'etait juste pour te dire que je travaille sur plein d'archi differentes.

Bon, alors j'ai fait quelques tests et je conclus à ma troisième possibilité : il y a un bug. Kevin ?
En fait -Os déconne complètement, la preuve, ça optimise mieux avec -O :
j'ai compilé ce code :

extern int flag, machin, truc;
void bouclecomplexe () {
  int i;
  asm ("|for de base");
  for (i = 0; i < 42; i++) {
    if (flag) machin |= truc;
    else machin &= truc;
  }

  asm ("|for à l'envers");
  for (i = 42; i--; ) {
    if (flag) machin |= truc;
    else machin &= truc;
  }

  asm ("|do-while avec --i");
  i = 42; do {
    if (flag) machin |= truc;
    else machin &= truc;
  } while (--i);

  asm ("|do-while avec i--");
  i = 41; do {
    if (flag) machin |= truc;
    else machin &= truc;
  } while (i--);
}

Voici ce que donne -Os : bouclecomplexe:      link.w %a6,#0      movm.l #0x1c00,-(%sp) #APP      |for de base #NO_APP      clr.w %d3      move.w flag,%d5      move.w machin,%d2      move.w truc,%d4      jbra .L2      .even .L8:      move.w %d2,%d1      addq.w #1,%d3      or.w %d4,%d2      tst.w %d5      jbne .L2      move.w %d1,%d2      and.w %d4,%d2 .L2:      cmp.w #41,%d3      jble .L8      move.w %d2,machin #APP      |for à l'envers #NO_APP      moveq.l #42,%d3      move.w flag,%d4      move.w truc,%a0      jbra .L32      .even .L15:      move.w %d2,%d1      move.w %a0,%d0      or.w %d0,%d2      tst.w %d4      jbne .L32      move.w %d1,%d2      and.w %d0,%d2 .L32:      dbra %d3,.L15      move.w %d2,machin #APP      |do-while avec --i #NO_APP      moveq.l #42,%d3      move.w flag,%a1      move.w truc,%d4 .L16:      move.w %a1,%d5      move.w %d2,%d1      move.w %d3,%a0      subq.w #1,%a0      or.w %d4,%d2      tst.w %d5      jbne .L18      move.w %d1,%d2      and.w %d4,%d2 .L18:      move.w %a0,%d3      jbne .L16      move.w %d2,machin #APP      |do-while avec i-- #NO_APP      moveq.l #41,%d3      move.w %d2,%d1      move.w truc,%d2 .L22:      move.w %d3,%a0      subq.w #1,%a0      tst.w %d5      jbeq .L25      or.w %d2,%d1      jbra .L24      .even .L25:      and.w %d2,%d1 .L24:      move.w %a0,%d3      cmp.w #-1,%d3      jbne .L22      move.w %d1,machin      movm.l (%sp)+,#0x38      unlk %a6      rts
Non seulement il pessimise les boucles comme un gros taré, mais en plus il fait des manipulations de registres totalement ésotériques...

Par contre, avec -O on a ce à quoi on s'attend : les solutions de BiHi et Pollux donnent toutes deux exactement le même résultat (initialisation à 41 et dbra à la fin) (dbra = dbf ??), mais celle de PpHd donne un subq suivi de bne.

Avec -O2, c'est encore mieux car il retourne la première boucle (tout de même !) mais il ne la finit pas par un dbra : il met subq suivi de jbpl (c'est quoi jbpl ?) À part ça il ne change pas grand-chose, sauf qu'il modifie les if pour que dans un cas ça branche deux fois et dans l'autre pas du tout, au lieu de une fois dans chaque (je ne comprends pas l'intérêt, mais au moins ça ne change pas la taille...)

Alors j'ai cherché s'il y avait un flag spécifique activé par -Os et pas par -O2 qui faisait tout merder, mais je n'en ai pas trouvé dans la doc (d'ailleurs la doc est fausse par endroits, elle dit que -fomit-frame-pointer est activé par -Os, or ce n'est pas le cas...)

Tu utilises quelle version de GCC ?
Parce que moi dans mes benchs de fonction, en général, je fais un for(i=... ; i-- ; ) et ça me génère un code correct, il me semble...

La dernière, 0.95 bêta.
Ce que tu dis fonctionne presque correctement en -Os, sauf que si la valeur initiale est constante il y a une instruction branch inutile vers le test de sortie entre l'initialisation et le début de la boucle (inutile puisqu'on sait que la valeur initiale est non nulle et donc que la boucle est forcément exécutée au moins une fois).
Cette instruction disparaît en -O et en -O2.

Conclusion: Toujours compile en O2

C'est ce que je suis en train de me dire, effectivement...
mais c'est quand même *beaucoup* plus gros (pas dans cet exemple, mais en moyenne) :\
Mais on doit pouvoir trouver une combinaison de -O2 et d'autres flags qui évitent de faire du code trop gros ?
ou alors il faut que Kevin débugge le -Os

L'optimisation-vitesse copie le test de fin de boucle à 2 endroits, au début et à la fin. Donc, pour:
while(cond) {
...
}
plutôt que:
goto test;
next:
...
test: if (cond) goto next;
on a en optimisation-vitesse:
if (!cond) goto end;
next:
...
test: if (cond) goto next;
end:
Cela augmente généralement la taille (le if est dupliqué), mais dans certains cas peut permettre des optimisations suivantes qui entre autre diminuent la taille. Si tu me trouves une condition sous laquelle copier le test de fin de boucle donne toujours un gain de taille, je veux bien mettre du code pour toujours faire la copie dans ce cas (et en -Os seulement dans ce cas).

Et au fait, je signale que l'utilisation de dbf n'est pas nécessairement un gain en -Os. subq.w+bne.s prennent la même taille qu'un dbf (4 octets) et peuvent souvent permettre d'économiser un subq au départ (juste avant l'entrée dans la boucle), donc 2 octets.

C'est forcément un gain de taille si l'on sait à la compilation si la condition est réalisée ou pas la première fois (autrement dit si c'est une constante), puisqu'on peut la virer. C'est en particulier vrai dans le cas d'une boucle à nombre d'itérations fixe.

Tu as une idée de pourquoi avec la méthode Pollux on n'obtient pas un dbra en -Os ?

./19 > donc ça justifie que la version PpHd ne donne pas de dbf.

Sally
: C'est forcément un gain de taille si l'on sait à la compilation si la condition est réalisée ou pas la première fois (autrement dit si c'est une constante), puisqu'on peut la virer. C'est en particulier vrai dans le cas d'une boucle à nombre d'itérations fixe.

Non. Qu'il y ait un saut vers test ou vers end ne change rien à la taille. Ce n'est pas ça.

Tu as une idée de pourquoi avec la méthode Pollux on n'obtient pas un dbra en -Os ?

Probablement parce que l'optimisation qui génère les dbf ne reconnaît pas le code qu'il y a en -Os. GCC copie en général toujours les tests des boucles. C'est un patch local TIGCC qui désactive ça en -Os (mais je ne suis pas celui qui l'a inventé, il a été essayé par certains développeurs de GCC, mais il a été refusé parce qu'il donne du code mauvais sur certaines plateformes, et comme tu vois, c'est parfois le cas même sur 68k mais il est très efficace sur Backgammon, et c'est un gain aussi pour TI-Chess, et il fait aussi intuitivement la bonne chose, donc je veux le garder).

Si le résultat de la première évaluation de cond (à l'arrivée dans la boucle) est calculable à la compilation (c'est en particulier le cas si on a un nombre d'itérations fixe, on est d'accord ?)
alors dans ton :
if (!cond) goto end;
next:
...
if (cond) goto next;
end:
le premier if est un if (constante). Donc suivant qu'il est vrai ou faux, soit tu vires carrément tout, soit tu simplifies en :

next:
...
if (cond) goto next;

Dans les deux cas, tu gagnes en taille, non ?

GCC copie en général toujours les tests des boucles.

Sauf qu'en l'occurence c'est un do-while, donc ça n'aurait aucun sens...
ce qui est très curieux, c'est qu'il met le subq beaucoup plus tôt qu'où il devrait être, ce qui n'a aucun intérêt. Et le contenu de la boucle n'y est pas pour rien, j'ai d'abord essayé avec un cas plus simple (juste un appel de fonction dans la boucle) et je n'avais pas ce problème. Apparemment, il tient à décrémenter le compteur AVANT le if qui est dans la boucle, pour une raison que j'ignore. Je pense que le problème est là : du coup, la décrémentation et le test ne se suivent plus et c'est peut-être pour ça qu'il ne voit pas que ça pourrait être optimisé en dbf ?

Autre question, je sais je suis chiant mais pourquoi diantre va-t-il mettre son compteur de boucle dans a0 ???

Pourquoi pas ?

Sally :
Si le résultat de la première évaluation de cond (à l'arrivée dans la boucle) est calculable à la compilation (c'est en particulier le cas si on a un nombre d'itérations fixe, on est d'accord ?)
alors dans ton :
if (!cond) goto end;
next:
...
if (cond) goto next;
end:
le premier if est un if (constante). Donc suivant qu'il est vrai ou faux, soit tu vires carrément tout, soit tu simplifies en :

next:
...
if (cond) goto next;
Dans les deux cas, tu gagnes en taille, non ?

Oui, tu as raison. Reste à savoir comment tester que c'est connu en temps de compilation...

Sally
: Autre question, je sais je suis chiant mais pourquoi diantre va-t-il mettre son compteur de boucle dans a0 ???

Parce que l'allocation de registres décide que c'est ce qu'il y a de plus avantageux.

Pourquoi pas ?

Pardon, j'ai mal posé ma question... pourquoi il le met dans d3, puis le move dans a0, puis le décrémente, puis le re-move dans d3, puis teste la valeur, alors qu'il ne se sert même pas de d3 par ailleurs ? (cf. le code que j'ai posté en ./13)

>Parce que l'allocation de registres décide que c'est ce qu'il y a de plus avantageux.
Parce que GCC est assez muti-processeurs et que sur tous les autres processeurs, il y a des pipelines qui rendent ce qu'il fait plus avantageux.

Sally> En effet, c'est curieux.. Peut-être pour sauver d3 au cas où tu appellerais une fonction de la ROM...

Là encore, il ne fait ça qu'en -Os. Voici le code que j'obtiens en -O :

|do-while avec i--
#NO_APP
	moveq.l #41,%d0
	move.w flag,%d3
	move.w truc,%d2
	.even
.L22:
	tst.w %d3
	jbeq .L25
	or.w %d2,%d1
	jbra .L24
	.even
.L25:
	and.w %d2,%d1
.L24:
	dbra %d0,.L22
	move.w %d1,machin

En -O2 j'ai la même chose, sauf pour le if comme je l'ai dit plus haut.