3

私がこのような関数を持っているとしましょう：

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を返します。-O2オプションを指定してclangを使用してコンパイルし、分解されたコードを見ると、LLVMはこの関数を。として正しくコンパイルしますreturn 1;。

私の質問は：llvmは静的値analysysをどのように実行しますか？最も弱い前提条件のテクニック？値の伝播？ホアのテクニック？

4

1 に答える 1

5

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

...そして今、最初の条件は明らかにノーオペレーションです。a_2とb_2は同じ式であるため、2 番目は常に true でなければなりません (ブロック 5 のパス) 。結果は

  return 1;
于 2012-11-09T01:45:08.317 に答える