Развертывание цикла

Развертывание цикла , также известное как разматывание цикла , представляет собой метод преобразования цикла , который пытается оптимизировать скорость выполнения программы за счет ее двоичного размера, что представляет собой подход, известный как компромисс между пространством и временем . Преобразование может быть выполнено вручную программистом или оптимизирующим компилятором . На современных процессорах развертывание цикла часто является контрпродуктивным, поскольку увеличенный размер кода может привести к большему количеству промахов в кэше; ср. Устройство Даффа . ^[1]

Целью раскручивания цикла является увеличение скорости программы за счет сокращения или исключения инструкций, управляющих циклом, таких как арифметика указателей и тесты «конца цикла» на каждой итерации; ^[2] снижение отраслевых штрафов; а также сокрытие задержек, в том числе задержки чтения данных из памяти. ^[3] Чтобы устранить эти вычислительные издержки , циклы можно переписать как повторяющуюся последовательность аналогичных независимых операторов. ^[4]

Развертывание цикла также является частью некоторых формальных методов проверки , в частности проверки ограниченной модели . ^[5]

Преимущества [ править ]

Накладные расходы в «жестких» циклах часто состоят из инструкций по увеличению указателя или индекса до следующего элемента в массиве ( арифметика указателей ), а также тестов «конца цикла». Если оптимизирующий компилятор или ассемблер способен предварительно вычислить смещения для каждой отдельной переменной массива, на которую ссылаются, их можно встроить непосредственно в инструкции машинного кода , поэтому не требуется никаких дополнительных арифметических операций во время выполнения.

Значительный выигрыш может быть достигнут, если сокращение количества выполняемых инструкций компенсирует любое снижение производительности, вызванное любым увеличением размера программы.
Штраф за ветку сведен к минимуму. ^[6]
Если операторы в цикле независимы друг от друга (т. е. операторы, которые встречаются раньше в цикле, не влияют на операторы, следующие за ними), эти операторы потенциально могут выполняться параллельно .
Может быть реализован динамически, если количество элементов массива неизвестно во время компиляции (как в устройстве Даффа ).

Оптимизирующие компиляторы иногда выполняют развертывание автоматически или по запросу.

Недостатки [ править ]

Увеличение размера программного кода, что может быть нежелательно, особенно для встроенных приложений, также может привести к увеличению количества промахов в кэше инструкций, что может отрицательно повлиять на производительность.
Если код не выполняется прозрачно оптимизирующим компилятором, он может стать менее читабельным .
Если код в теле цикла включает вызовы функций, может оказаться невозможным совместить развертывание со встраиванием , поскольку увеличение размера кода может оказаться чрезмерным. Таким образом, между двумя оптимизациями может быть компромисс.
Возможное увеличение использования регистров за одну итерацию для хранения временных переменных. ^{[ сомнительно – обсудить ]}, что может снизить производительность, хотя многое будет зависеть от возможных оптимизаций. ^[7]
Если не считать очень маленького и простого кода, развернутые циклы, содержащие ветки, работают даже медленнее, чем рекурсии. ^[8]

Статическое/ручное развертывание цикла [ править ]

Ручное (или статическое) развертывание цикла предполагает, что программист анализирует цикл и интерпретирует итерации в последовательность инструкций, что снижает накладные расходы цикла. В этом отличие от динамического развертывания, которое выполняется компилятором.

Простой пример руководства на C [ править ]

Процедура компьютерной программы заключается в удалении 100 элементов из коллекции. Обычно это достигается с помощью for-loop, который вызывает функцию delete(item_number) . Если эту часть программы необходимо оптимизировать, а накладные расходы цикла требуют значительных ресурсов по сравнению с ресурсами для функции delete(x) , для ускорения ее можно использовать раскрутку.

Обычный цикл	После развертывания цикла
int x; for (x = 0; x < 100; x++) { delete(x); }	int x; for (x = 0; x < 100; x += 5 ) { delete(x); delete(x + 1); delete(x + 2); delete(x + 3); delete(x + 4); }

В результате этой модификации новой программе приходится делать всего 20 итераций вместо 100. После этого необходимо выполнить только 20% переходов и условных переходов, что представляет собой за многие итерации потенциально значительное уменьшение накладные расходы на администрирование цикла. Чтобы получить оптимальную выгоду, в развернутом коде не следует указывать переменные, требующие арифметики указателей . Обычно для этого требуется адресация « база плюс смещение», а не индексированная ссылка.

С другой стороны, эта ручная развертка цикла увеличивает размер исходного кода с 3 до 7 строк, которые необходимо создавать, проверять и отлаживать, и компилятору, возможно, придется выделить больше регистров для хранения переменных в итерации расширенного цикла. ^{[ сомнительно – обсудить ]}. Кроме того, переменные управления циклом и количество операций внутри развернутой структуры цикла должны выбираться тщательно, чтобы результат действительно был таким же, как в исходном коде (при условии, что это более поздняя оптимизация уже работающего кода). Например, рассмотрим последствия, если количество итераций не делится на 5. Требуемые вручную поправки также становятся несколько более сложными, если условия тестирования являются переменными. См. также устройство Даффа .

Ранняя сложность [ править ]

В простом случае управление циклом — это просто административные издержки, которые упорядочивают продуктивные операторы. Сам по себе цикл ничего не дает для достижения желаемых результатов, а просто избавляет программиста от утомительного повторения кода сто раз, что можно было бы сделать с помощью препроцессора, генерирующего репликации, или текстового редактора. Сходным образом, ifОператоры и другие операторы управления потоком могут быть заменены репликацией кода, за исключением того, что раздувание кода результатом может стать . Компьютерные программы легко отслеживают комбинации, но программисты находят это повторение скучным и допускают ошибки. Учитывать:

Обычный цикл

После развертывания цикла

for i := 1:8 do
    if i mod 2 = 0 then do_even_stuff(i) 
                   else do_odd_stuff(i);
    next i;

do_odd_stuff(1); do_even_stuff(2);
do_odd_stuff(3); do_even_stuff(4);
do_odd_stuff(5); do_even_stuff(6);
do_odd_stuff(7); do_even_stuff(8);

Но, конечно, выполняемый код не обязательно должен быть вызовом процедуры, и в следующем примере в вычислении используется индексная переменная:

Обычный цикл	После развертывания цикла
x(1) := 1; for i := 2:9 do x(i) := x(i - 1) * i; print i, x(i); next i;	x(1) := 1; x(2) := x(1) * 2; print 2, x(2); x(3) := x(2) * 3; print 3, x(3); x(4) := x(3) * 4; print 4, x(4); ... etc.

который, если его скомпилировать, может создать много кода ( пресловутые операторы печати ), но возможна дальнейшая оптимизация. ссылаются только на x(i) и x(i - 1) В этом примере в цикле (последний только для создания нового значения x(i) нет ), поэтому, учитывая, что более поздних ссылок на массив x, разработанный здесь, , его использование можно заменить простой переменной. Однако такое изменение будет означать простую переменную, значение которой будет изменено , тогда как, если оставить массив, анализ компилятора может заметить, что значения массива являются постоянными, каждое из которых получено из предыдущей константы, и, следовательно, переносит постоянные значения, так что код становится

print 2, 2;
print 3, 6;
print 4, 24;
...etc.

В общем случае содержимое цикла может быть большим и включать сложную индексацию массива. В этих случаях, вероятно, лучше всего оставить оптимизацию компиляторов для развертывания. Репликация самых внутренних циклов может позволить множество возможных оптимизаций, но даст лишь небольшой выигрыш, если n не велико.

Развертывание циклов WHILE [ править ]

Рассмотрим псевдокод цикла WHILE, подобный следующему:

Обычный цикл

После развертывания цикла

Развернутый и «настроенный» цикл

WHILE (condition) DO
    action
ENDWHILE
.
.
.
.
.
.

WHILE (condition) DO
    action
    IF NOT(condition) THEN GOTO break
    action
    IF NOT(condition) THEN GOTO break
    action
ENDWHILE
LABEL break:
.

IF (condition) THEN
    REPEAT
        action
        IF NOT(condition) THEN GOTO break
        action
        IF NOT(condition) THEN GOTO break
        action
    WHILE (condition)
LABEL break:

В этом случае развертывание происходит быстрее, поскольку ENDWHILE (переход к началу цикла) будет выполняться на 66% реже.

Еще лучше, «измененный» пример псевдокода, который может выполняться автоматически некоторыми оптимизирующими компиляторами, полностью исключая безусловные переходы.

Динамическое развертывание [ править ]

Поскольку преимущества развертывания цикла часто зависят от размера массива, который часто может быть неизвестен до времени выполнения, JIT- компиляторы (например) могут определить, следует ли вызывать «стандартную» последовательность циклов или вместо этого генерировать (относительно короткую) последовательность циклов. ) последовательность отдельных инструкций для каждого элемента. Эта гибкость является одним из преимуществ методов «точно в срок» по сравнению со статической или ручной оптимизацией в контексте развертывания цикла. В этой ситуации часто бывает при относительно небольших значениях n экономия , поскольку требуется довольно небольшое (если вообще вообще) увеличение общего размера программы (которое можно включить только один раз, как часть стандартной библиотеки).

Программисты на языке ассемблера (в том числе оптимизирующие составители компиляторов) также могут извлечь выгоду из техники динамического развертывания цикла, используя метод, аналогичный тому, который используется для эффективных таблиц ветвей . Здесь преимущество является наибольшим, когда максимальное смещение любого поля, на которое ссылаются, в конкретном массиве меньше максимального смещения, которое может быть указано в машинной инструкции (которое будет отмечено ассемблером, если оно будет превышено).

Пример ассемблера (IBM/360 или Z/Architecture) [ править ]

Этот пример предназначен для ассемблеров IBM/360 или Z/Architecture и предполагает, что поле размером 100 байт (с нулевым смещением) должно быть скопировано из массива FROM в массив TO — оба имеют 50 записей с длиной элемента 256 байт каждая.

* The return address is in R14.
* Initialize registers R15, R0, R1, and R2 from data defined at the end of 
* the program starting with label INIT/MAXM1.
         LM    R15,R2,INIT                  Set R15 = maximum number of MVC
*                                           instructions (MAXM1 = 16), 
*                                           R0 = number of entries of array,
*                                           R1 = address of 'FROM' array, and
*                                           R2 = address of 'TO' array.
*
* The loop starts here.
LOOP     EQU   *                            Define LOOP label.
* At this point, R15 will always contain the number 16 (MAXM1).
         SR    R15,R0                       Subtract the remaining number of 
*                                           entries in the array (R0) from R15.
         BNP   ALL                          If R15 is not positive, meaning we
*                                           have more than 16 remaining entries
*                                           in the array, jump to do the entire
*                                           MVC sequence and then repeat.
*
* Calculate an offset (from start of MVC sequence) for unconditional branch to 
* the 'unwound' MVC loop below.
* If the number of remaining entries in the arrays is zero, R15 will be 16, so 
* all the MVC instructions will be bypassed.
         MH    R15,=AL2(ILEN)               Multiply R15 by the length of one
*                                           MVC instruction.
         B     ALL(R15)                     Jump to ALL+R15, the address of the
*                                           calculated specific MVC instruction 
*                                           with drop through to the rest of them.
*
* MVC instruction 'table'. 
* First entry has maximum allowable offset with single register = hexadecimal F00
* (15*256) in this example.
* All 16 of the following MVC ('move character') instructions use base-plus-offset 
* addressing and each to/from offset decreases by the length of one array element
* (256). This avoids pointer arithmetic being required for each element up to a 
* maximum permissible offset within the instruction of hexadecimal FFF 
* (15*256+255). The instructions are in order of decreasing offset, so the last 
* element in the set is moved first.
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                        Set ILEN to the length of the previous
*                                           MVC instruction.
         MVC   14*256(100,R2),14*256(R1)    Move 100 bytes of 15th entry.
         MVC   13*256(100,R2),13*256(R1)    Move 100 bytes of 14th entry.
         MVC   12*256(100,R2),12*256(R1)    Move 100 bytes of 13th entry.
         MVC   11*256(100,R2),11*256(R1)    Move 100 bytes of 12th entry.
         MVC   10*256(100,R2),10*256(R1)    Move 100 bytes of 11th entry.
         MVC   09*256(100,R2),09*256(R1)    Move 100 bytes of 10th entry.
         MVC   08*256(100,R2),08*256(R1)    Move 100 bytes of 9th entry.
         MVC   07*256(100,R2),07*256(R1)    Move 100 bytes of 8th entry.
         MVC   06*256(100,R2),06*256(R1)    Move 100 bytes of 7th entry.
         MVC   05*256(100,R2),05*256(R1)    Move 100 bytes of 6th entry.
         MVC   04*256(100,R2),04*256(R1)    Move 100 bytes of 5th entry.
         MVC   03*256(100,R2),03*256(R1)    Move 100 bytes of 4th entry.
         MVC   02*256(100,R2),02*256(R1)    Move 100 bytes of 3rd entry.
         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 the number of remaining entries
*                                           to process.
         BNPR  R14                          If no more entries to process, return
*                                           to address in R14.
         AH    R1,=AL2(16*256)              Increment 'FROM' array pointer beyond
*                                           first set.
         AH    R2,=AL2(16*256)              Increment 'TO' array pointer beyond
*                                           first set.
         L     R15,MAXM1                    Reload the maximum number of MVC 
*                                           instructions per batch into R15
*                                           (destroyed by the calculation in the 
*                                           first instruction of the loop).
         B     LOOP                         Execute loop again.
*
* Static constants and variables (these could be passed as parameters, except 
* MAXM1).
INIT     DS    0A                           4 addresses (pointers) to be 
*                                           pre-loaded with the 'LM' instruction
*                                           in the beginning of the program.
MAXM1    DC    A(16)                        Maximum number of MVC instructions
*                                           executed per batch.
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").
*
* Static arrays (these could be dynamically acquired).
FROM     DS    50CL256                      Array of 50 entries of 256 bytes each.
TO       DS    50CL256                      Array of 50 entries of 256 bytes each.

В этом примере потребуется примерно 202 инструкции при «обычном» цикле (50 итераций), тогда как приведенный выше динамический код потребует только около 89 инструкций (или экономия примерно 56%). Если бы массив состоял только из двух записей, он все равно выполнялся бы примерно за то же время, что и исходный развернутый цикл. Увеличение размера кода составляет всего около 108 байт — даже если в массиве тысячи записей.

Подобные методы, конечно, можно использовать и там, где задействовано несколько инструкций, при условии, что длина объединенной команды корректируется соответствующим образом. Например, в этом же примере, если требуется очистить остальную часть каждой записи массива до нулевых значений сразу после копирования 100-байтового поля, дополнительная инструкция очистки: XC xx*256+100(156,R1),xx*256+100(R2), можно добавлять сразу после каждого MVC в последовательности (где xx соответствует значению в MVC над ним).

Конечно, вполне возможно сгенерировать приведенный выше код «встроенно», используя один макрос ассемблера, указав всего четыре или пять операндов (или, альтернативно, превратить его в библиотечную подпрограмму, доступ к которой осуществляется простым вызовом, передавая список параметры), что делает оптимизацию легко доступной.

Пример C [ править ]

В следующем примере демонстрируется динамическое развертывание цикла для простой программы, написанной C. на В отличие от приведенного выше примера ассемблера, арифметика указателей/индексов в этом примере по-прежнему генерируется компилятором, поскольку переменная (i) по-прежнему используется для обращения к элементу массива. Полная оптимизация возможна только в том случае, если в операторах замены используются абсолютные индексы.

#include <stdio.h>

/* The number of entries processed per loop iteration.                        */
/* Note that this number is a 'constant constant' reflecting the code below.  */
#define BUNCHSIZE (8)

int main(void)
{ 
  int i = 0;                                    /* counter */
  int entries = 50;                             /* total number to process    */
  int repeat;                                   /* number of while repetitions*/
  int left = 0;                                 /* remainder (process later)  */ 
 
  /* If the number of elements is not be divisible by BUNCHSIZE,              */ 
  /* get repeat times required to do most processing in the while loop        */

  repeat = (entries / BUNCHSIZE);                /* number of times to repeat */
  left   = (entries % BUNCHSIZE);                /* calculate remainder       */

  /* Unroll the loop in 'bunches' of 8                                        */ 
  while (repeat--) 
  { 
    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 += BUNCHSIZE;
  }

  /* 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                    */
     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                  */
  } 
}

Дублирования кода можно было избежать, если записать две части вместе, как в устройстве Даффа .

Пример развертывания цикла ассемблера C в MIPS ^[9][ редактировать ]

В следующем примере будет вычислено скалярное произведение двух векторов A и B из 100 элементов типа double. Вот код на C:

double dotProduct = 0;
for (int i = 0; i < 100; i++) {
  dotProduct += A[i]*B[i];
}

Преобразование в ассемблер MIPS [ править ]

Ниже приведен ассемблерный код MIPS, который вычисляет скалярное произведение двух векторов со 100 элементами, A и B, перед реализацией развертывания цикла. В приведенном ниже коде отсутствует инициализация цикла:

Инициализируйте количество циклов ($7) до 100.
Инициализируйте скалярное произведение ($f10) равным 0.
Инициализировать A[i] указатель ($5) на базовый адрес A.
Инициализировать B[i] указатель ($6) на базовый адрес B.

Обратите внимание, что размер одного элемента массивов (a double) составляет 8 байт.

    loop3:
            l.d     $f10, 0($5)       ; $f10 ← A[i]
            l.d     $f12, 0($6)       ; $f12 ← B[i]
            mul.d   $f10, $f10, $f12  ; $f10 ← A[i]*B[i]
            add.d   $f8, $f8, $f10    ; $f8 ← $f8 + A[i]*B[i]
            addi    $5, $5, 8         ; increment pointer for A[i] by the size
                                      ; of a double.
            addi    $6, $6, 8         ; increment pointer for B[i] by the size
                                      ; of a double.
            addi    $7, $7, -1        ; decrement loop count
    test:
            bgtz    $7, loop3         ; Continue if loop count > 0

Развертывание цикла в MIPS [ править ]

Далее происходит то же самое, что и выше, но с развертыванием цикла, реализованным с коэффициентом 4. Еще раз обратите внимание, что размер одного элемента массивов (a double) составляет 8 байт; таким образом, смещения 0, 8, 16, 24 и смещение 32 в каждой петле.

    loop3:
            l.d     $f10, 0($5)         ; iteration with displacement 0
            l.d     $f12, 0($6)
            mul.d   $f10, $f10, $f12
            add.d   $f8, $f8, $f10

            l.d     $f10, 8($5)         ; iteration with displacement 8
            l.d     $f12, 8($6)
            mul.d   $f10, $f10, $f12
            add.d   $f8, $f8, $f10

            l.d     $f10, 16($5)        ; iteration with displacement 16
            l.d     $f12, 16($6)
            mul.d   $f10, $f10, $f12
            add.d   $f8, $f8, $f10

            l.d     $f10, 24($5)        ; iteration with displacement 24
            l.d     $f12, 24($6)
            mul.d   $f10, $f10, $f12
            add.d   $f8, $f8, $f10

            addi    $5, $5, 32
            addi    $6, $6, 32
            addi    $7, $7, -4
    test:
            bgtz    $7, loop3           ; Continue loop if $7 > 0

См. также [ править ]

Ссылки [ править ]

^ Цо, Тед (22 августа 2000 г.). «Re: [PATCH] Re: Перемещение драйверов ввода, нужно несколько слов от вас» . lkml.indiana.edu . Список рассылки ядра Linux . Проверено 22 августа 2014 г. У Джима Геттиса есть замечательное объяснение этого эффекта на X-сервере. Оказывается, что с учетом прогнозов ветвей и изменения относительной скорости процессора по сравнению с памятью за последнее десятилетие, развертывание цикла практически бессмысленно. Фактически, за счет исключения всех экземпляров устройства Даффа с сервера XFree86 4.0 размер сервера уменьшился на _половину_а_ _мегабайт_ (!!!) и стал загружаться быстрее, поскольку удаление всего этого лишнего кода означало, что X-сервер не так сильно терял строки кэша.
^ Уллман, Джеффри Д.; Ахо, Альфред В. (1977). Принципы проектирования компилятора . Ридинг, Массачусетс: Паб Addison-Wesley. Ко. стр. 471–2 . ISBN 0-201-10073-8 .
^ Петерсен, В.П., Арбенс, П. (2004). Введение в параллельные вычисления . Издательство Оксфордского университета. п. 10 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ Николау, Александру (1985). «Петлевое квантование: раскручивание для использования мелкозернистого параллелизма». Технический отчет кафедры компьютерных наук. Итака, Нью-Йорк: Корнельский университет. OCLC 14638257 . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
^ Проверка модели с использованием SMT и теории списков
^ Туман, Агнер (29 февраля 2012 г.). «Оптимизация подпрограмм на языке ассемблера» (PDF) . Инженерный колледж Копенгагенского университета. п. 100 . Проверено 22 сентября 2012 г. 12.11 Развертывание цикла
^ Саркар, Вивек (2001). «Оптимизированное развертывание вложенных циклов». Международный журнал параллельного программирования . 29 (5): 545–581. дои : 10.1023/А:1012246031671 . S2CID 3353104 .
^ Адам Хорват «Раскручивание кода - производительность еще далека»
^ «Разворачивание цикла» . Университет Миннесоты .

Дальнейшее чтение [ править ]

Кеннеди, Кен; Аллен, Рэнди (2001). Оптимизация компиляторов для современных архитектур: подход, основанный на зависимостях . Морган Кауфманн. ISBN 1-55860-286-0 .

Внешние ссылки [ править ]

Глава 7, страницы с 8 по 10 , Майкла Абраша » «Черной книги по графическому программированию посвящена развертыванию цикла с примером на ассемблере x86.
Обобщенная развертка цикла дает краткое введение.
Оптимизация подпрограмм на языке ассемблера. Справочник Агнера Фога по оптимизации с использованием техники развертывания цикла (2012).

[lkml-0008.2/0171-1] Цо, Тед (22 августа 2000 г.). «Re: [PATCH] Re: Перемещение драйверов ввода, нужно несколько слов от вас» . lkml.indiana.edu . Список рассылки ядра Linux . Проверено 22 августа 2014 г. У Джима Геттиса есть замечательное объяснение этого эффекта на X-сервере. Оказывается, что с учетом прогнозов ветвей и изменения относительной скорости процессора по сравнению с памятью за последнее десятилетие, развертывание цикла практически бессмысленно. Фактически, за счет исключения всех экземпляров устройства Даффа с сервера XFree86 4.0 размер сервера уменьшился на _половину_а_ _мегабайт_ (!!!) и стал загружаться быстрее, поскольку удаление всего этого лишнего кода означало, что X-сервер не так сильно терял строки кэша.

[2] Уллман, Джеффри Д.; Ахо, Альфред В. (1977). Принципы проектирования компилятора . Ридинг, Массачусетс: Паб Addison-Wesley. Ко. стр. 471–2 . ISBN 0-201-10073-8 .

[3] Петерсен, В.П., Арбенс, П. (2004). Введение в параллельные вычисления . Издательство Оксфордского университета. п. 10 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )

[4] Николау, Александру (1985). «Петлевое квантование: раскручивание для использования мелкозернистого параллелизма». Технический отчет кафедры компьютерных наук. Итака, Нью-Йорк: Корнельский университет. OCLC 14638257 . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[5] Проверка модели с использованием SMT и теории списков

[fog2012-6] Туман, Агнер (29 февраля 2012 г.). «Оптимизация подпрограмм на языке ассемблера» (PDF) . Инженерный колледж Копенгагенского университета. п. 100 . Проверено 22 сентября 2012 г. 12.11 Развертывание цикла

[7] Саркар, Вивек (2001). «Оптимизированное развертывание вложенных циклов». Международный журнал параллельного программирования . 29 (5): 545–581. дои : 10.1023/А:1012246031671 . S2CID 3353104 .

[8] Адам Хорват «Раскручивание кода - производительность еще далека»

[9] «Разворачивание цикла» . Университет Миннесоты .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

v т и Оптимизация компилятора
Базовый блок	Оптимизация глазка Нумерация локальных значений
Петля	Автоматическое распараллеливание Автоматическая векторизация Индукционная переменная Петля слияния Движение кода, инвариантное к циклу Инверсия цикла Перестановка петель Оптимизация гнезда циклов Разделение цикла Развертывание цикла Выключение петли Конвейерная обработка программного обеспечения Снижение прочности
Поток данных анализ	Доступное выражение Удаление общего подвыражения Постоянное складывание мертвого магазина Устранение Распознавание и устранение индукционных переменных Анализ переменных в реальном времени Использовать-определить цепочку
SSA на основе	Глобальная нумерация значений Разреженное условное постоянное распространение
Генерация кода	Планирование инструкций Выбор инструкции Распределение регистров Рематериализация
Функциональный	Вырубка лесов Устранение хвостового вызова
Глобальный	Межпроцедурная оптимизация
Другой	Устранение проверки границ Выполнение функции во время компиляции Устранение мертвого кода Шаблоны выражений Встроенное расширение Перейти к потоку Частичная оценка Оптимизация на основе профиля
Статический анализ	Анализ псевдонимов Анализ доступа к массиву Анализ потока управления Анализ потока данных Анализ зависимостей Анализ побега Анализ указателя Анализ формы Анализ диапазона значений