Оптимизация базовых блоков

Опубликовано: 17 Сентября, 2022

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

Существует два типа оптимизации основных блоков:

  1. Преобразования, сохраняющие структуру
  2. Алгебраические преобразования

Преобразования, сохраняющие структуру:

Преобразование с сохранением структуры на базовых блоках включает:

  1. Устранение мертвого кода
  2. Устранение общего подвыражения
  3. Переименование временных переменных
  4. Обмен двумя независимыми соседними утверждениями

1. Устранение мертвого кода:

Мертвый код определяется как часть кода, которая никогда не выполняется во время выполнения программы. Таким образом, для оптимизации такой код или мертвый код устраняется. Код, который никогда не выполняется во время программы (мертвый код), требует времени, поэтому для оптимизации и ускорения он исключается из кода. Устранение мертвого кода увеличивает скорость работы программы, поскольку компилятору не нужно переводить мертвый код.

Пример:

// Program with Dead code
int main()
{
    x = 2 
    if (x > 2) 
      cout << "code"; // Dead code
    else 
      cout << "Optimization";
    return 0;
}
// Optimized Program without dead code
int main()
{
    x = 2;
    cout << "Optimization"; // Dead Code Eliminated
    return 0;
}

2. Устранение общих подвыражений:

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

Пример:

3. Переименование временных переменных:

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

Пример: Оператор t = a + b можно изменить на x = a + b, где t — временная переменная, а x — новая временная переменная без изменения значения базового блока.

4. Обмен двумя независимыми соседними утверждениями:

Если в блоке есть два смежных оператора, которые независимы, их можно поменять местами, не влияя на базовое значение блока.

Пример:

t1 = a + b
t2 = c + d 

Эти два независимых оператора блока можно поменять местами, не влияя на значение блока.

Алгебраическое преобразование:

Можно использовать бесчисленные алгебраические преобразования, чтобы преобразовать набор выражений, вычисляемых базовым блоком, в алгебраически эквивалентный набор. Некоторые из алгебраических преобразований базовых блоков включают:

  1. Постоянное складывание
  2. Копировать распространение
  3. Снижение силы

1. Постоянное складывание:

Решите непрерывные константы, чтобы компилятору не нужно было решать это выражение.

Пример:

x = 2 * 3 + y   x = 6 + y  (Optimized code)

2. Копирование распространения:

Он бывает двух типов: переменное распространение и постоянное распространение.

Переменное распространение:

                                     x = y                  ⇒ z = y + 2 (Optimized code)

                                     z = x + 2

Постоянное распространение:

                                      x = 3               z = 3 + a (Optimized code)

                                      z = x + a 

3. Снижение силы:

Заменить дорогую инструкцию/инструкцию на более дешевую.

x = 2 * y (costly)    x = y + y (cheaper)
x = 2 * y (costly)  ⇒ x = y << 1 (cheaper)

Оптимизация цикла:

Оптимизация цикла включает следующие стратегии:

  1. Движение кода и снижение частоты
  2. Исключение индукционной переменной
  3. Слияние/объединение циклов
  4. Развертывание цикла

1. Движение кода и снижение частоты

Переместите инвариантный код цикла за пределы цикла.

// Program with loop variant inside loop
int main()
{
    for (i = 0; i < n; i++) {
        x = 10;
        y = y + i;
    }
    return 0;
}
// Program with loop variant outside loop
int main()
{
    x = 10;
    for (i = 0; i < n; i++)
        y = y + i;
    return 0;
}

2. Исключение индукционной переменной:

Удалите различные ненужные переменные индукции, используемые в цикле.

// Program with multiple induction variables
int main()
{
    i1 = 0;
    i2 = 0;
    for (i = 0; i < n; i++) {
        A[i1++] = B[i2++];
    }
    return 0;
}
// Program with one induction variable
int main()
{
    for (i = 0; i < n; i++) {
        A[i] = B[i]; // Only one induction variable
    }
    return 0;
}

3. Слияние/объединение циклов:

Если выполняемые операции можно выполнить в одном цикле, то объедините или объедините циклы.

// Program with multiple loops
int main()
{
    for (i = 0; i < n; i++)
        A[i] = i + 1;
    for (j = 0; j < n; j++)
        B[j] = j - 1;
}
return 0;
}  
// Program with one loop when multiple loops are merged
int main()
{
    for (i = 0; i < n; i++) {
        A[i] = i + 1;
        B[i] = i - 1;
    }
    return 0;
}

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

Если существует простой код, который может уменьшить количество выполнений цикла, то цикл можно заменить этими кодами.

// Program with loops
int main()
{
    for (i = 0; i < 3; i++)
        cout << "Cd";
    return 0;
}
// Program with simple code without loops
int main()
{
    cout << "Cd";
    cout << "Cd";
    cout << "Cd";
    return 0;
}