Döngü açma

Yürütme zamanı gösterge aritmetiğinin statik şekilde ortadan kaldırılması

"Sıkı" döngülerdeki fazla zaman yükü, "döngü sonu" testleri ile olabileceği gibi, bir dizinin sonraki elemanına geçmeyi sağlayan gösterge indisini arttırma işlemi (gösterge aritmetiği) sebebiyle olur. Optimizasyon sağlayan bir derleyici ya da çevirici her ayrı ayrı referanslanmış dizi değişkeninin değerini hesapladığı takdirde, kodları direkt olarak makine dili buyruklarına çevirir ve böylece yürütme zamanında fazladan aritmetik operasyon yapılmasına gerek kalmaz.

Dinamik döngü açma

Döngü açmanın faydaları programda kullanılan dizinin büyüklüğüne bağlı olduğu için çoğunlukla yürütme zamanından önce bilinememektedir. JIT yapan derleyiciler döngülerin standart bir şekilde çalıştırılmasına veya ayrı ayrı buyrukları sıralayarak farklı bir kod oluşturup döngülerin açılmasına karar verebilirler. Bu esneklik just-in-time derlemenin statik veya manuel olarak döngülerin açılmasına göre büyük üstünlük sağladığını gösterir.
Assembly dili programcıları da verimli dallanma tablolarında kullanılan tekniğe benzer bir teknik kullanarak dinamik döngü açma tekniğinden faydalanabilmektedir. Aşağıdaki örnek IBM 360 veya Z mimarisini kullanan çevirici kodlarıyla yazılmıştır. 256 baytlık ve 50 elemanlı 2 dizi olan FROM ve TO dizilerinde, 'FROM' dizisinin 100 baytını 'TO' dizisine kopyalama işlemi gerçekleştirilmektedir.

Assembler örneği (IBM 360 veya Z Mimarisi)

* initialize all the registers to point to arrays etc  (R14 is return address)
         LM    R15,R2,INIT                       load R15= '16', R0=number in array, R1--> 'FROM array', R2--> 'TO array'
LOOP     EQU   *
         SR    R15,R0                            get 16 minus the number in the array
         BNP   ALL                               if n > 16 need to do all of the sequence, then repeat
* (if # entries = zero, R15 will now still be 16, so all the MVC's will be bypassed)
* calculate an offset (from start of MVC sequence) for unconditional branch to 'unwound' MVC loop
         MH    R15,=AL2(ILEN)                    multiply by length of (MVC..) instruction (=6 in this example)
         B     ALL(R15)                          indexed branch instruction (to MVC with drop through)
* Assignment (move) table - (first entry has maximum allowable offset with single register = X'F00' in this example)
ALL      MVC   15*256(100,R2),15*256(R1)         * move 100 bytes of 16th entry  from array 1 to array 2 (with drop through)
ILEN     EQU   *-ALL                                         length of (MVC...) instruction sequence; in this case =6
         MVC   14*256(100,R2),14*256(R1)         *
         MVC   13*256(100,R2),13*256(R1)         *
         MVC   12*256(100,R2),12*256(R1)         * All 16 of these 'move character' instructions use base plus offset addressing
         MVC   11*256(100,R2),11*256(R1)         * and each to/from offset decreases by the length of one array element (256).
         MVC   10*256(100,R2),10*256(R1)         * This avoids pointer arithmetic being required for each element up to a 
         MVC   09*256(100,R2),09*256(R1)         * maximum permissible offset within the instruction of X'FFF'. The instructions 
         MVC   08*256(100,R2),08*256(R1)         * are in order of decreasing offset, so the first element in the set is moved
         MVC   07*256(100,R2),07*256(R1)         * last.
         MVC   06*256(100,R2),06*256(R1)         *
         MVC   05*256(100,R2),05*256(R1)         *
         MVC   04*256(100,R2),04*256(R1)         *
         MVC   03*256(100,R2),03*256(R1)         *
         MVC   02*256(100,R2),02*256(R1)         *
         MVC   01*256(100,R2),01*256(R1)         move 100 bytes of 2nd entry
         MVC   00*256(100,R2),00*256(R1)         move 100 bytes of 1st entry
*
         S     R0,MAXM1                          reduce Count = remaining entries to process
         BNPR  R14                               ... no more, so return to address in R14
         AH    R1,=AL2(16*256)                   increment 'FROM' register pointer beyond first set
         AH    R2,=AL2(16*256)                   increment 'TO'   register pointer beyond first set
         L     R15,MAXM1                         re-load (maximum MVC's) in R15 (destroyed by calculation earlier)
         B     LOOP                              go and execute loop again
*
* ----- Define static Constants and variables (These could be passed as parameters) ---------------------------------  *
INIT     DS    0A                                4 addresses (pointers) to be pre-loaded with a 'LM' instruction
MAXM1    DC    A(16)                             maximum MVC's 
N        DC    A(50)                             number of actual entries in array (a variable, set elsewhere)
         DC    A(FROM)                           address of start of array 1 ("pointer")
         DC    A(TO)                             address of start of array 2 ("pointer")
* ----- Define static Arrays (These could be dynamically acquired) --------------------------------------------------  *
FROM     DS    50CL256                          array of (max) 50 entries of 256 bytes each
TO       DS    50CL256                          array of (max) 50 entries of 256 bytes each
Bu örnekte, klasik döngü kullanımıyla 50 iterasyonluk bir döngü ile yaklaşık 202 buyruk çalıştırılacakken, dinamik kod ile 89 buyrukta tamamlanabilecektir. Dizi 2 girdi ile yapılsaydı yaklaşık olarak yine normal, açılmamış döngüde harcanan zamana denk olacaktı. Koddaki artış ise 108 bayt kadar olup, binlerce girdi ile denense bile aynı sonucu verecekti. Tabii ki benzer yöntemler birden fazla buyruk işin içine katıldığında da birleşik buyruk uzunluğu ayarlanarak kullanılabilir. Örneğin yukarıdaki kod parçasında kopyalanan 100 bayttan hemen sonra kopyaladığımız kısımları silmek istersek fazladan temizleme buyruğu her MVC buyruğu çağırıldıktan sonra eklenebilir.' XC xx*256+100(156,R1),xx*256+100(R2)'(buradaki 'xx' bir üst satırdaki MVC buyruğundaki değerdir).

C örneği

Aşağıdaki örnek C programlama dilinde yazılmış bir döngü açma programıdır. Yukarıdaki assembler örneğinin aksine, gösterge/indis aritmetiği compiler tarafından kullanılmaktadır. Bunun sebebi dizinin adreslenmesinde kullanılan (i) değişkenidir. Tam optimizasyon için indislerin gerçek değerlerinin (i) değişken değeriyle değiştirilmesi gerekmektedir.
#include<stdio.h> #define TOGETHER (8)int main(void){ 
 int i = 0; 
 int entries = 50;                                 /* total number to process     */
 int repeat;                                       /* number of times for while.. */
 int left =0;                                      /* remainder (process later)   *//* If the number of elements is not be divisible by BLOCKSIZE,                    */ 
/*  get repeat times required to do most processing in the while loop             */

 repeat = (entries / TOGETHER);         /* number of times to repeat   */
 left  =  entries - (repeat * TOGETHER);           /* calculate remainder          *//* Unroll the loop in 'bunches' of 8                                              */ 
 while( repeat-- > 0 ) 
 { 
    printf("process(%d)\n", i); 
    printf("process(%d)\n", i+1); 
    printf("process(%d)\n", i+2); 
    printf("process(%d)\n", i+3); 
    printf("process(%d)\n", i+4); 
    printf("process(%d)\n", i+5); 
    printf("process(%d)\n", i+6); 
    printf("process(%d)\n", i+7);

    /* update the index by amount processed in one go                            */ 
    i += TOGETHER; 
 } 
/* Use a switch statement to process remaining by jumping to the case label      */ 
/*  at the label that will then drop through to complete the set                 */

    switch (left) 
    { 
        case 7 : printf("process(%d)\n", i +6);           /* process and rely on drop through drop through */
        case 6 : printf("process(%d)\n", i +5); 
        case 5 : printf("process(%d)\n", i +4);  
        case 4 : printf("process(%d)\n", i +3);  
        case 3 : printf("process(%d)\n", i +2); 
        case 2 : printf("process(%d)\n", i +1);          /* two left                                      */
        case 1 : printf("process(%d)\n", i   );          /* just one left to process                      */ 
        case 0 :                                         /* none left                                     */
    }}

Not

Bu madde, İngilizce Wikipedia'nın loop unwinding sayfasından çevrilmiştir.