Анализ статических значений LLVM для оптимизации

Question

Допустим, у меня есть такая функция:

int foo(int a, int b, int d, int x){
  if (c) {a = 1; b = 1; d = a;}
  else {a = 2; b = 2; d = 1;}
  if (a == b) {x = d;} else {x = 0;}
  return x;
}

Эта тривиальная функция всегда возвращает 1. Компиляция с помощью clang с опцией -O2 и просмотр дизассемблированного кода. LLVM правильно компилирует эту функцию как return 1;,

Мой вопрос: как llvm выполняет анализ статических значений? самое слабое условие техники? распространение значения? Техники Хоара?

Answer 1

LLVM делает все что угодно: смотрите здесь.

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

clang -c -mllvm -print-after-all -O2 foo.c

определить, какая стадия делает что.

---

На самом деле, этот конкретный пример не очень волшебен!

Если вы преобразуете его в форму SSA, это будет выглядеть примерно так:

  // block 1
  if (c == 0) goto L1;
  // block 2
  a_0 = 1;
  b_0 = 1;
  d_0 = a_0;
  goto L2;
L1:
  // block 3
  a_1 = 2;
  b_1 = 2;
  d_1 = 1;
  goto L2;

L2:
  // block 4 (has two possible predecessors: block 2 or block 3)
  a_2 = PHI(a_0, a_1); // i.e. a_0 if we came from block 2, a_1 if we came from block 3
  b_2 = PHI(b_0, b_1); // i.e. b_0 if we came from block 2, b_1 if we came from block 3
  d_2 = PHI(d_0, d_1); // i.e. d_0 if we came from block 2, d_1 if we came from block 3
  if (a_2 != b_2) goto L3;
  // block 5
  x_0 = d_2;
  goto L4:
L3:
  // block 6
  x_1 = 0;
  goto L4;

L4:
  // block 7 (has two possible predecessors: block 5 or block 6)
  return PHI(x_0, x_1); // i.e. x_0 if we came from block 5, x_1 if we came from block 6

Простое распространение постоянных значений приводит к этому:

  // block 1
  if (c == 0) goto L1;
  // block 2
  a_0 = 1;
  b_0 = 1;
  d_0 = 1;
  goto L2;
L1:
  // block 3
  a_1 = 2;
  b_1 = 2;
  d_1 = 1;
  goto L2;

L2:
  // block 4
  a_2 = PHI(1, 2); // i.e. 1 if we came from block 2, 2 if we came from block 3
  b_2 = PHI(1, 2); // i.e. 1 if we came from block 2, 2 if we came from block 3
  d_2 = 1;         // PHI(d_0, d_1) == PHI(1, 1) i.e. 1 regardless of where we came from
  if (a_2 != b_2) goto L3;
  // block 5
  x_0 = 1;  // (we've deduced that d_2 == 1 regardless of control flow)
  goto L4:
L3:
  // block 6
  x_1 = 0;
  goto L4;

L4:
  // block 7
  return PHI(1, 0); // i.e. 1 if we came from block 5, 0 if we came from block 6

Упрощение удаления назначений, которые больше не используются ни для чего другого, дает следующее:

  // block 1
  if (c == 0) goto L1;
  // block 2
  goto L2;
L1:
  // block 3
  goto L2;

L2:
  // block 4
  a_2 = PHI(1, 2); // i.e. 1 if we came from block 2, 2 if we came from block 3
  b_2 = PHI(1, 2); // i.e. 1 if we came from block 2, 2 if we came from block 3
  if (a_2 != b_2) goto L3;
  // block 5
  goto L4:
L3:
  // block 6
  goto L4;

L4:
  // block 7
  return PHI(1, 0); // i.e. 1 if we came from block 5, 0 if we came from block 6

... и теперь первое условное выражение явно не разрешено; а вторая всегда должна быть истинной (блок 5 пути), потому что a_2 а также b_2 одно и то же выражение. Итак, результат

  return 1;