Comment écrire une boucle dans C afin que le compilateur utilise la branche sur zéro après la décrémentation

Question

Les processeurs sont connus pour avoir des instructions spéciales pour décrémenter un compteur et une branche si le compteur est nul avec une latence très faible car l'instruction de branchement n'a pas besoin d'attendre le compteur décrément passant à travers une unité entière.

Voici un lien vers l'instruction ppc:

https://www.ibm.com/support/knowledgecenter/ssw_aix_53/com.ibm.aix.aixassem/doc/alangref/bc.htm

Ma façon habituelle de faire ce que je crois déclenche un compilateur pour générer les instructions appropriées se présente comme suit:

unsigned int ctr = n; 
while(ctr--) 
    a[ctr] += b[ctr]; 

Lisibilité est haut et c'est une boucle de décrémentation ramifiée sur zéro. Comme vous voyez la branche se produit techniquement si le compteur est zéro avant la décrémentation. J'espérais que le compilateur pourrait faire de la magie et le faire fonctionner de toute façon. Q: Un compilateur doit-il casser les règles fondamentales de C afin de le réduire à des instructions spéciales de décrémentation et de branchement (le cas échéant)?

Une autre approche:

unsigned int ctr = n+1; 
while(--ctr) { 
    a[ctr-1] += b[ctr-1]; 
} 

La branche maintenant se produire après décrémentation mais il y a des constantes d'itinérance rend le code laid. Une variable "index" étant un de moins que le compteur ferait paraître un peu plus joli je suppose. En regardant les instructions ppc disponibles, le calcul supplémentaire de la recherche des adresses a et b peut toujours tenir compte d'une seule instruction, car la charge peut également effectuer une opération arithmétique (ajouter). Pas si sûr au sujet d'autres ensembles d'instructions. Mon problème principal est si n + 1 est plus grand qu'un max. Q: Le décrément le ramènera-t-il au maximum et à la boucle comme d'habitude?

Q: Y a-t-il un motif plus couramment utilisé en C pour permettre l'instruction commune? Edit: ARM a une opération de décrémentation et de branchement, mais ne se branche que si la valeur n'est pas zéro. Il semble y avoir une condition supplémentaire, tout comme le ppc bc. Comme je le vois, c'est du point de vue de C c'est à peu près la même chose, donc je m'attends à ce qu'un fragment de code soit compilable à cette forme aussi sans aucune violation de la norme C. http://www.heyrick.co.uk/armwiki/Conditional_execution

---

Edit: Intel a pratiquement la même instruction de branchement comme ARM: http://cse.unl.edu/~goddard/Courses/CSCE351/IntelArchitecture/InstructionSetSummary.pdf

Answer 1

Qu'en est-ce:

do 
{ 
    a[ctr] += b[ctr]; 
} 
while(--ctr); 

Vous auriez besoin d'un contrôle supplémentaire, cependant:

if(n != 0) 
{ 
    /*...*/ 
} 

si vous ne pouvez pas le garantir par d'autres moyens ...

Oh, et être conscient que ctr a des valeurs différentes finales en fonction de la variante boucle que vous sélectionnez (0 dans le mien et votre second, ~ 0 dans votre premier) ...

Answer 2

Cela va dépendre les efforts des auteurs d'optimisation de votre compilateur. Par exemple, un code d'opération bdz peut être utilisé en bas d'une boucle pour "sauter" un autre saut qui revient en haut. (Ce serait une mauvaise idée, mais cela pourrait arriver.Il est beaucoup plus probable que ce soit de décrémenter et de ramifier si NON, ce que le PPC supporte également.

loop: 
    blah 
    blah 

    bdnz ... loop 

fallthru: 

Sauf si vous avez une raison impérieuse d'essayer de jeu les opcodes, je vous suggère que vous essayez d'écrire un code propre, lisible qui minimise les effets secondaires. Votre propre changement de post-décrémentation à pré-décrémentation est un bon exemple de cet effet secondaire moins utilisé pour le compilateur.

De cette façon, vous obtiendrez le meilleur pour votre argent d'optimisation. S'il existe une plate-forme qui nécessite une version spéciale de votre code, vous pouvez l'inclure dans son intégralité et soit inclure l'assemblage en ligne, soit réécrire le code conjointement avec la lecture de la sortie de l'assemblage et l'exécution du profileur.

Answer 3

Dépend certainement du compilateur, mais c'est une instruction qui est géniale pour les performances, donc je m'attendrais à ce que les compilateurs essaient de maximiser leur utilisation.

Étant donné que vous liez une référence AIX, je suppose que vous exécutez xlc. Je n'ai pas accès à une machine AIX mais j'ai accès à xlc sur une machine Z. La contrepartie Z équivalente est l'instruction BCTR (Branch On Count).

J'ai essayé 5 exemples et vérifié la liste

int len = strlen(argv[1]); 
//Loop header 
argv[1][counter] += argv[2][counter]; 

les en-têtes de boucle suivantes:

for (int i = 0; i < len; i++) 
for (int i = len-1; i >= 0; i--) 
while(--len) 
while(len--) 
while(len){ 
    len--; 

Tous les 5 exemples utiliser la branche sur le nombre à -O1 et plus, et aucun d'entre eux utilisent à 0.

Je ferais confiance à un compilateur moderne pour pouvoir trouver une branche sur zéro opportunités avec n'importe quelle structure de boucle standard.