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

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;