Поговорим об оптимизирующих компиляторах. Сказ второй: Доминирование

Перефразируя, доминирование можно описать так:

Узел A доминирует над узлом B тогда и только тогда, когда любой путь из начала графа в узел B проходит через узел A

Имхо, так проще понять о чем говорится

нет не то написал.

Спасибо.

Хотел задать вопрос по LLVM не связанный непосредственно с темой поста.

А как там решается проблема того, что некоторые фронтэнды разрешают неэквивалентные преобразования (например С и С++ UB таковыми являются)?
(как my best guess - должен быть флаг, в зависимости от которого запускать дополнительный набор peep-hole правил, но хотелось бы послушать как оно на самом деле).

Ведь если обрабатывать С \ С++ UB строгим образом - получите просадку производительности.
Но закладываться на С \ С++ UB очевидно тоже нельзя (иначе нельзя было бы использовать LLVM как бэкэнд для более строгих языков, того же Rust \ Haskell \ D \ ...).

============================================================
Т.е. условно если у вас есть:
a: i32;
if (a + 1 > a) { do_1() } else {do_2() };

gcc -O2 - скорее всего всегда будет выполняться do_1().
cargo run --release (rust) - будет делаться честная проверка и при переполнении выполняться do_2().

• Для начала, из графа удаляются все обратные рёбра циклов. Они нам не потребуются. Дальше рассматриваем граф без обратных рёбер.

На всякий случай, если кто тоже споткнулся, то это определение дано через одну статью :)

Можно я буду пользоваться комментариями в качестве личных заметок при чтении ваших статей? Вы дали ссылку на файл SROA.cpp, и выясняется, что SROA - это Scalar Replacement Of Aggregates. Очень интересное и говорящее название! Давайте отвлечёмся от финод, и посмотрим на более простой случай.

Мне кажется, что инлайнинг функций - это вид SROA (даже если в том .cpp его нет), только оно работает над кодом, а не над памятью. Если мы возьмём такой код, то инлайнинг позволяет избавиться от вызова print:

typedef struct {
  int x, y;
} point;

void print(point *p) {
  printf("(%d, %d)", p->x, p->y);
}

int main () {
  point p;
  p.x = 1;
  p.y = 2;
  print (&p);
  return 0;
}

То есть, после инлайнинга мы получим следующий код:

typedef struct {
  int x, y;
} point;

int main () {
  point p;
  p.x = 1;
  p.y = 2;
  printf("(%d, %d)", p.x, p.y);
  return 0;
}

Причём в данном случае основная польза не в том, что мы избавились от накладных расходов на вызов функции. Компилятору трудно что-то доказать про кусок памяти, когда работа с ним разбросана по множеству функций. А ведь если нет доказательства, нет и оптимизации (мы же не хотим, чтобы компилятор нам всё поломал?)

То есть, в данном случае польза от инлайнинга в том, что компилятор может теперь рассуждать об аргументах функции printf, поскольку они теперь живут в том же месте, где и была создана структура p.

То есть, польза в том, что мы не обязаны использовать load/store для доступа к полям структуры: SROA позволяет убрать агрегатную структуру point, и заменить её на две локальных переменных p_x и p_y:

int main () {
  int p_x = 1;
  int p_y = 2;
  printf("(%d, %d)", p_x, p_y);
  return 0;
}

А дальше проталкивание констант позволяет убрать и их:

int main () {
  printf("(%d, %d)", 1, 2);
  return 0;
}

Возвращаясь к данной статье, автор рассматривает фрейм функции как агрегатную структуру с параметрами и локальными переменными, и заменяет где можно доступ к этой структуре через load/store на SSA-значения. А это, в свою очередь, уже позволит компилятору делать рассуждения.