Pourquoi une boucle simple est-elle optimisée lorsque la limite est de 959 mais pas de 960 ?

Question

Considérez cette simple boucle :

float f(float x[]) {
  float p = 1.0;
  for (int i = 0; i < 959; i++)
    p += 1;
  return p;
}

Si vous compilez avec gcc 7 (snapshot) ou clang (trunk) avec -march=core-avx2 -Ofast vous obtenez quelque chose de très similaire à.

.LCPI0_0:
        .long   1148190720              # float 960
f:                                      # @f
        vmovss  xmm0, dword ptr [rip + .LCPI0_0] # xmm0 = mem[0],zero,zero,zero
        ret

En d'autres termes, il fixe simplement la réponse à 960 sans boucle.

Cependant, si vous changez le code en :

float f(float x[]) {
  float p = 1.0;
  for (int i = 0; i < 960; i++)
    p += 1;
  return p;
}

L'assemblage produit effectue réellement la somme de la boucle ? Par exemple, clang donne :

.LCPI0_0:
        .long   1065353216              # float 1
.LCPI0_1:
        .long   1086324736              # float 6
f:                                      # @f
        vmovss  xmm0, dword ptr [rip + .LCPI0_0] # xmm0 = mem[0],zero,zero,zero
        vxorps  ymm1, ymm1, ymm1
        mov     eax, 960
        vbroadcastss    ymm2, dword ptr [rip + .LCPI0_1]
        vxorps  ymm3, ymm3, ymm3
        vxorps  ymm4, ymm4, ymm4
.LBB0_1:                                # =>This Inner Loop Header: Depth=1
        vaddps  ymm0, ymm0, ymm2
        vaddps  ymm1, ymm1, ymm2
        vaddps  ymm3, ymm3, ymm2
        vaddps  ymm4, ymm4, ymm2
        add     eax, -192
        jne     .LBB0_1
        vaddps  ymm0, ymm1, ymm0
        vaddps  ymm0, ymm3, ymm0
        vaddps  ymm0, ymm4, ymm0
        vextractf128    xmm1, ymm0, 1
        vaddps  ymm0, ymm0, ymm1
        vpermilpd       xmm1, xmm0, 1   # xmm1 = xmm0[1,0]
        vaddps  ymm0, ymm0, ymm1
        vhaddps ymm0, ymm0, ymm0
        vzeroupper
        ret

Pourquoi est-ce le cas et pourquoi est-ce exactement la même chose pour clang et gcc ?

---

La limite pour la même boucle si vous remplacez float avec double est de 479. C'est encore le cas pour gcc et clang.

Mise à jour 1

Il s'avère que gcc 7 (snapshot) et clang (trunk) se comportent très différemment. clang optimise les boucles pour toutes les limites inférieures à 960 pour autant que je puisse dire. gcc d'autre part est sensible à la valeur exacte et n'a pas de limite supérieure. Par exemple, il n'est pas d'optimiser la boucle lorsque la limite est de 200 (ainsi que de nombreuses autres valeurs) mais elle fait lorsque la limite est de 202 et 20002 (ainsi que de nombreuses autres valeurs).

Answer 1

TL;DR

Par défaut, l'instantané actuel de GCC 7 se comporte de manière incohérente, alors que les versions précédentes ont une limite par défaut en raison de PARAM_MAX_COMPLETELY_PEEL_TIMES qui est de 16. Elle peut être remplacée par la ligne de commande.

La raison d'être de cette limite est d'empêcher un déroulement trop agressif des boucles, ce qui peut être une source d'erreur. arme à double tranchant .

Version de GCC <= 6.3.0

L'option d'optimisation pertinente pour GCC est -fpeel-loops qui est activé indirectement avec l'indicateur -Ofast (c'est moi qui souligne) :

Épluchez les boucles pour lesquelles il y a suffisamment d'informations pour qu'elles ne qu'elles ne roulent pas beaucoup (à partir du retour du profil ou analyse statique ). Il active également l'épluchage complet de la boucle (c'est-à-dire suppression complète des boucles avec un petit nombre constant d'itérations ).

Activé avec -O3 et/ou -fprofile-use .

Plus de détails peuvent être obtenus en ajoutant -fdump-tree-cunroll :

$ head test.c.151t.cunroll 

;; Function f (f, funcdef_no=0, decl_uid=1919, cgraph_uid=0, symbol_order=0)

Not peeling: upper bound is known so can unroll completely

Le message provient de /gcc/tree-ssa-loop-ivcanon.c :

if (maxiter >= 0 && maxiter <= npeel)
    {
      if (dump_file)
        fprintf (dump_file, "Not peeling: upper bound is known so can "
         "unroll completely\n");
      return false;
    }

d'où try_peel_loop les fonctions de retour false .

Une sortie plus verbeuse peut être obtenue avec -fdump-tree-cunroll-details :

Loop 1 iterates 959 times.
Loop 1 iterates at most 959 times.
Not unrolling loop 1 (--param max-completely-peeled-times limit reached).
Not peeling: upper bound is known so can unroll completely

Il est possible d'ajuster les limites en plaçant avec max-completely-peeled-insns=n et max-completely-peel-times=n paramètres :

max-completely-peeled-insns

Le nombre maximum d'insns d'une boucle complètement épluchée.

max-completely-peel-times

Le nombre maximum d'itérations d'une boucle pour que l'épluchage soit complet. l'épluchage complet.

Pour en savoir plus sur les insns, vous pouvez vous référer à Manuel interne du GCC .

Par exemple, si vous compilez avec les options suivantes :

-march=core-avx2 -Ofast --param max-completely-peeled-insns=1000 --param max-completely-peel-times=1000

puis le code se transforme en :

f:
        vmovss  xmm0, DWORD PTR .LC0[rip]
        ret
.LC0:
        .long   1148207104

Clang

Je ne suis pas sûr de ce que Clang fait réellement et de la façon de modifier ses limites, mais comme je l'ai observé, vous pourriez le forcer à évaluer la valeur finale en marquant la boucle avec dérouler le pragme et il le supprimera complètement :

#pragma unroll
for (int i = 0; i < 960; i++)
    p++;

résultats dans :

.LCPI0_0:
        .long   1148207104              # float 961
f:                                      # @f
        vmovss  xmm0, dword ptr [rip + .LCPI0_0] # xmm0 = mem[0],zero,zero,zero
        ret

Answer 2

Après avoir lu le commentaire de Sulthan, je suppose que :

1. Le compilateur déroule complètement la boucle si le compteur de boucle est constant (et pas trop élevé).

2. Une fois qu'il est déroulé, le compilateur voit que les opérations de somme peuvent être regroupées en une seule.

Si la boucle n'est pas déroulée pour une raison quelconque (ici : elle générerait trop de déclarations avec 1000 ), les opérations ne peuvent pas être regroupées.

Le compilateur pourrait voir que le déroulage de 1000 instructions revient à une seule addition, mais les étapes 1 & 2 décrites ci-dessus sont deux optimisations distinctes, il ne peut donc pas prendre le "risque" de dérouler, ne sachant pas si les opérations peuvent être groupées (exemple : un appel de fonction ne peut pas être groupé).

Note : C'est un cas particulier : Qui utilise une boucle pour ajouter la même chose encore et encore ? Dans ce cas, ne comptez pas sur un éventuel déroulage/optimisation par le compilateur ; écrivez directement l'opération appropriée en une instruction.

Answer 3

Très bonne question !

Il semble que vous ayez atteint une limite quant au nombre d'itérations ou d'opérations que le compilateur tente de mettre en ligne lors de la simplification du code. Comme documenté par Grzegorz Szpetkowski, il existe des moyens spécifiques au compilateur pour modifier ces limites avec des pragmas ou des options de ligne de commande.

Vous pouvez également jouer avec L'explorateur de compilateur de Godbolt pour comparer l'impact de différents compilateurs et options sur le code généré : gcc 6.2 et icc 17 inline toujours le code pour 960, alors que clang 3.9 ne le fait pas (avec la configuration par défaut de Godbolt, il arrête en fait l'inlining à 73).