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

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 -Ofastvous 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 définit simplement la réponse à 960 sans boucle.

Cependant, si vous modifiez 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 et pourquoi est-ce exactement la même chose pour clang et gcc?

La limite pour la même boucle si vous remplacez floatpar doubleest 479. C'est la même chose pour gcc et clang à nouveau.

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 sache. gcc d'autre part est sensible à la valeur exacte et n'a pas de limite supérieure. Par exemple , il n'a pas d' optimiser la boucle lorsque la limite est de 200 (ainsi que beaucoup d' autres valeurs) , mais il ne lorsque la limite est de 202 et 20002 (ainsi que beaucoup d' autres valeurs).

TL; DR

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

La raison d'être de la limite est d'éviter un déroulement de boucle trop agressif, qui peut être une arme à double tranchant .

Version GCC <= 6.3.0

L'option d'optimisation pertinente pour GCC est -fpeel-loops, qui est activée indirectement avec l'indicateur -Ofast(l'accent est mis sur moi):

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

Activé avec -O3et / 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 vient 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;
    }

donc la try_peel_loopfonction retourne false.

Une sortie plus détaillée peut être atteinte 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 de modifier les limites en plaçant avec les paramètres max-completely-peeled-insns=net max-completely-peel-times=n:

max-completely-peeled-insns

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

max-completely-peel-times

Le nombre maximum d'itérations d'une boucle pour convenir à un pelage complet.

Pour en savoir plus sur insns, vous pouvez vous référer au manuel GCC Internals .

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

Bruit

Je ne sais pas ce que fait réellement Clang et comment ajuster ses limites, mais comme je l'ai observé, vous pouvez le forcer à évaluer la valeur finale en marquant la boucle avec unroll pragma , et il le supprimera complètement:

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

se traduit par:

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

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

1. Le compilateur déroule complètement la boucle si le compteur de boucles 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 d'instructions avec 1000), les opérations ne peuvent pas être regroupées.

Le compilateur pourrait voir que le déroulement de 1000 instructions équivaut à un seul ajout, mais les étapes 1 et 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 regroupées (exemple: un appel de fonction ne peut pas être groupé).

Remarque: Il s'agit d'un cas secondaire: qui utilise une boucle pour ajouter à nouveau la même chose? Dans ce cas, ne comptez pas sur le déroulement / l'optimisation possible du compilateur; écrivez directement l'opération appropriée dans une instruction.

Très bonne question!

Vous semblez avoir atteint une limite sur le nombre d'itérations ou d'opérations que le compilateur essaie 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 compilateurs de Godbolt pour comparer l'impact des différents compilateurs et options sur le code généré: gcc 6.2et icc 17toujours en ligne le code pour 960, alors que ce clang 3.9n'est pas le cas (avec la configuration Godbolt par défaut, il s'arrête en fait à 73).