itmo_conspects

Лекция 6. Анализ и оптимизации компилятора

Оптимизации

Оптимизации компилятора - это преобразования программы, которые делают её быстрее, компактнее или экономичнее, не изменяя поведение. Оптимизации компилятора бывают:

Локальные - действуют внутри одного базового блока, например, свертка констант, удаление мертвого кода
Глобальные - анализируют всю функцию или граф потока управления (CFG), например, устранение общих подвыражений, перемещение инвариантов циклов
Межфункциональные (interprocedural) - охватывают несколько функций, например, inlining (встраивание), link-time optimization (оптимизация на этапе компоновки)

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

Глазок (Peephole) - локальная оптимизация, рассматривающая маленькие фрагменты кода (2–5 инструкций) и заменяющая их на более эффективные эквиваленты. Например, такой код:
```
  int a = b + 3;
  int d = a + 5;

  int c = d * 2;
```
заменяется на:
```
  int d = b + 5;

  int c = d * 2;
```
Схлопывание (или свертка) констант (Constant Folding) - вычисление выражений на этапе компиляции
```
  int x = 2 * 3; // заменяется на int x = 6;
```
Удаление мертвого кода (Dead Code Elimination) - удаление кода, результат которого не используется, а также кода после return или неиспользуемых переменных
Устранение общих подвыражений (Common Subexpression Elimination) - устранение общих подвыражений, таким образом, их вычисление производится один раз. Например,
```
  a = ((b - c) % d) * ((b - c) / e);
```
превращается в:
```
  f = (b - c);
  a = (f % d) * (f / e);
```

Встраивание (Inlining) - подстановка тела функции вместо вызова. Например:

  int square(int x) { 
      return x * x; 
  }
  int y = square(5); // заменяется на int y = 5 * 5;

Loop Invariant Code Motion - вынос из цикла выражений, не зависящих от итерации. Например,

  for (int i = 0; i < N; i++) {
      int x = N * N;
      int j = x * i;
  }

превращается в:

  int x = N * N;
  for (int i = 0; i < N; i++) {
      int j = x * i;
  }

Induction Variable Elimination - устранение или объединение переменных, изменяющихся линейно с номером итерации. Например,
```
  for (int i = 0; i < N; i++) {
      j = 2 * i + 1;
      A[j] = 0;
  }
```
превращается в:
```
  for (int j = 1; j < 2 * N; j += 2) A[j] = 0;
```
Раскрутка цикла (Loop Peeling) - отделение первых итераций цикла для оптимизации граничных условий. Например,
```
  for (int i = 0; i < N; i++) A[i] = f(i);
```
превращается в:
```
  A[0] = f(0);
  for (int i = 1; i < N; i++) A[i] = f(i);
```
Loop Unrolling (развёртывание цикла) - выполнение нескольких итераций за одну, чтобы уменьшить количество сравнений
```
  for (int i = 0; i < N; i++) A[i]++;
```
превращается в:
```
  for (int i = 0; i < N; i += 4) {
      A[i]++; A[i+1]++; A[i+2]++; A[i+3]++;
  }
```

Loop Fission - один цикл на два для улучшения кэш-локальности или параллелизма. Например,

  for (int i = 0; i < N; i++) {
      A[i] = f(i);
      B[i] = g(A[i]);
  }

превращается в:

  for (int i = 0; i < N; i++) A[i] = f(i);
  for (int i = 0; i < N; i++) B[i] = g(A[i]);

Loop Fusion - слияние два цикла, проходящих по тем же данным. Например,

  for (int i = 0; i < N; i++) A[i] = B[i] + 1;
  for (int i = 0; i < N; i++) C[i] = A[i] * 2;

превращается в:

  for (int i = 0; i < N; i++) {
      A[i] = B[i] + 1;
      C[i] = A[i] * 2;
  }

Анализ кода

Для большинства оптимизаций используется анализ граф управления потоком (Control Flow Graph, CFG) программы. Для него применяются обходы графа:

DFS (Depth-First Search) - поиск в глубину, используется для построения деревьев и обнаружения циклов
RPO (Reverse Post Order) - порядок обхода, при котором каждый узел посещается после своих предков, удобен для итеративных алгоритмов анализа данных

Блок V доминирует над блоком W, если любой путь от входа в функцию до W проходит через V. Блок V называют доминатором. Начальный блок доминирует над всеми

Дерево доминаторов строится при помощи DFS и служит для оптимизаций, анализа циклов и построения SSA-формы

Цикл в графе потока управления определяется через наличие обратного ребра (back-edge) - перехода из блока B в блок A, где A доминирует над B.

Основные понятия:

Back-edge - ребро, указывающее назад в цикл
Header - первый блок цикла (точка входа), доминирует над всеми блоками цикла
Latch - блок, из которого выполняется переход обратно к Header
Preheader - блок перед циклом, используется для вставки кода, выполняющегося один раз перед входом в цикл
Exiting edge - ребро, по которому управление выходит из цикла
Exit block - блок, куда программа попадает после выхода из цикла
Entering block (или Loop predecessor) - блок, ведущий в Header
Irreducible loop - цикл с несколькими входами, который не может быть представлен единственным Header
Countable loop - цикл с известным числом итераций, например for (int i = 0; i < N; i++)

Алгоритм анализа циклов обычно выполняется так:

Строится граф управления потока функции
Для каждого ребра B -> A проверяется, доминирует ли A над B. Если да, то это обратное ребро
Из найденных обратных рёбер выделяются множества блоков, формирующих циклы
Для каждого цикла определяются header, latch, preheader и выходы
Строится иерархия вложенности циклов (дерево цикла), что помогает выполнять оптимизации, такие как loop unrolling, fusion, invariant motion и другие

This site is open source. Improve this page.