In che modo GCC può srotolare un ciclo se il suo numero di iterazioni è sconosciuto al momento della compilazione?

Question

Stavo leggendo il optimization options for GCC quando ho trovato l'opzione -funroll-all-loops.

La sua descrizione si legge:

Srotolare tutti i loop, anche se il loro numero di iterazioni è incerto quando si entra il ciclo. Questo di solito rende i programmi più lenti. '-funroll-tutti-loops' implica le stesse opzioni '-funroll-loops'

Come può il compilatore srotolare un ciclo se il suo numero di iterazioni è sconosciuto al momento della compilazione? Il compilatore non ha bisogno di queste informazioni per srotolarlo? Quale codice C corrispondente genera e in quali contesti potrebbe essere utile se di solito fa girare i programmi più lentamente?

Answer 1

in quali contesti potrebbe essere utile se di solito i programmi girano più lentamente?

Bene, si presume che se si sceglie questa opzione si sa cosa si sta facendo, se non si dovrebbe non utilizzare questa opzione.

cosa sta gcc sta per fare, bene ho usato questo programma di esempio:

#include <stdio.h> 

void f(int j) 
{ 
    for(int k = 0; k < j; ++k) 
    { 
    printf("%d\n", k) ; 
    } 
} 

e provato con Godbolt e genera una tabella di salto in base al numero di iterazioni sinistra (see it live):

cmpl $1, %ebp 
movl $1, %ebx 
je .L1 
testl %r12d, %r12d 
je .L27 
cmpl $1, %r12d 
je .L28 
cmpl $2, %r12d 
je .L29 
cmpl $3, %r12d 
je .L30 
cmpl $4, %r12d 
je .L31 
cmpl $5, %r12d 
je .L32 
cmpl $6, %r12d 
je .L33 

Answer 2

Non si può presumere che ci sia una cosa come corrispondente codice C per la rappresentazione intermedia di un compilatore. Ma in questo caso, mi aspetto che l'equivalente più vicino sia qualcosa come Duff's Device, che è una sequenza (di solito in un ciclo) che può essere inserita in una posizione calcolata.

Answer 3

Si può fare qualcosa di simile:

while(n >= 8){ 
    foo(); foo(); foo(); foo(); foo(); foo(); foo(); foo(); 
    n -= 8; 
} 
while(n > 0){ 
    foo(); 
    n--; 
} 

Naturalmente, dispositivo di Duff farebbe risparmiare dover scrivere il secondo ciclo.

Perché farlo? Questo dipende dall'utilizzatore. Se foo() spende più di un paio di cicli, o se il loop originale richiede meno che il 5% del tempo totale orologio a muro, o se n è tipicamente piccola, è probabilmente non vale la pena.

Answer 4

Ecco po 'di codice C che mostra come farlo:

int iterations = 100; 
int unrollValue = 8; 

while (iterations%unrollvalue) 
{ 
    // insert loop code here 
    iterations--; 
} 

while (iterations) 
{ 
    // insert unrollValue copies of loop code here 
    iterations-= unrollValue; 
} 

Il compilatore sostituirà il primo ciclo con un salto relativo, ma che non è facile rappresentare in C. Si noti che srotolando da una potenza di 2 consente al compilatore di utilizzare una maschera anziché l'operazione di divisione (costosa).