Apa sebenarnya instruksi PHI dan bagaimana menggunakannya di LLVM

91

LLVM memiliki instruksi phi dengan penjelasan yang cukup aneh:

Instruksi 'phi' digunakan untuk mengimplementasikan node φ dalam grafik SSA yang mewakili fungsi tersebut.

Biasanya digunakan untuk mengimplementasikan percabangan. Jika saya mengerti dengan benar, itu diperlukan untuk membuat analisis ketergantungan mungkin dan dalam beberapa kasus dapat membantu untuk menghindari pemuatan yang tidak perlu. Namun masih sulit untuk memahami apa yang dilakukannya.

Contoh Kaleidoskop menjelaskannya dengan cukup baik untuk ifkasus. Namun tidak begitu jelas bagaimana mengimplementasikan operasi logis seperti &&dan ||. Jika saya mengetik berikut ini ke compiler llvm online :

void main1(bool r, bool y) {
    bool l = y || r;
}

Beberapa baris terakhir benar-benar membingungkan saya:

; <label>:10                                      ; preds = %7, %0
%11 = phi i1 [ true, %0 ], [ %9, %7 ]
%12 = zext i1 %11 to i8

Sepertinya node phi menghasilkan hasil yang bisa digunakan. Dan saya mendapat kesan bahwa phi node hanya menentukan dari mana nilai jalur berasal.

Bisakah seseorang menjelaskan apa itu simpul Phi, dan bagaimana menerapkannya ||?

vwvw
sumber
1
The phisimpul merupakan solusi dari masalah di compiler untuk mengkonversi IR menjadi "Static tunggal tugas" bentuk. Untuk memahami lebih baik tentang solusi, saya sarankan untuk lebih memahami masalahnya. Jadi saya akan memberi tahu Anda " Mengapa phinode ".
Vraj Pandya

Jawaban:

77

Node phi adalah instruksi yang digunakan untuk memilih nilai tergantung pada pendahulu dari blok saat ini (Lihat di sini untuk melihat hierarki penuh - ini juga digunakan sebagai nilai, yang merupakan salah satu kelas yang diwarisi darinya).

Node phi diperlukan karena struktur gaya SSA (penugasan tunggal statis) dari kode LLVM - misalnya, fungsi C ++ berikut

void m(bool r, bool y){
    bool l = y || r ;
}

diterjemahkan ke dalam IR berikut: (dibuat melalui clang -c -emit-llvm file.c -o out.bc- dan kemudian dilihat melalui llvm-dis)

define void @_Z1mbb(i1 zeroext %r, i1 zeroext %y) nounwind {
entry:
  %r.addr = alloca i8, align 1
  %y.addr = alloca i8, align 1
  %l = alloca i8, align 1
  %frombool = zext i1 %r to i8
  store i8 %frombool, i8* %r.addr, align 1
  %frombool1 = zext i1 %y to i8
  store i8 %frombool1, i8* %y.addr, align 1
  %0 = load i8* %y.addr, align 1
  %tobool = trunc i8 %0 to i1
  br i1 %tobool, label %lor.end, label %lor.rhs

lor.rhs:                                          ; preds = %entry
  %1 = load i8* %r.addr, align 1
  %tobool2 = trunc i8 %1 to i1
  br label %lor.end

lor.end:                                          ; preds = %lor.rhs, %entry
  %2 = phi i1 [ true, %entry ], [ %tobool2, %lor.rhs ]
  %frombool3 = zext i1 %2 to i8
  store i8 %frombool3, i8* %l, align 1
  ret void
}

Jadi apa yang terjadi disini? Tidak seperti kode C ++, di mana variabel bool lbisa berupa 0 atau 1, di LLVM IR harus ditentukan sekali . Jadi kami memeriksa apakah %toboolbenar, dan kemudian melompat ke lor.endatau lor.rhs.

Dalam lor.endkami akhirnya memiliki nilai || operator. Jika kami tiba dari blok masuk - maka itu benar. Jika tidak, itu sama dengan nilai %tobool2- dan itulah yang kami dapatkan dari garis IR berikut:

%2 = phi i1 [ true, %entry ], [ %tobool2, %lor.rhs ]
Guy Adini
sumber
6
TL; DR φ node adalah ekspresi terner. Orang mungkin berpendapat bahwa itu tidak berisi kondisi, tetapi sebenarnya, setelah mengonversi ke kode final, Anda tidak dapat menentukan sebaliknya yang mana dari argumen yang aktif, jadi φ harus memiliki kondisi juga.
Hi-Angel
31

Anda tidak perlu menggunakan phi sama sekali. Buat saja banyak variabel sementara. Pass pengoptimalan LLVM akan menangani pengoptimalan variabel sementara dan akan menggunakan node phi untuk itu secara otomatis.

Misalnya, jika Anda ingin melakukan ini:

x = 4;
if (something) x = x + 2;
print(x);

Anda dapat menggunakan node phi untuk itu (dalam pseudocode):

  1. tetapkan 4 hingga x1
  2. if (! sesuatu) bercabang ke 4
  3. hitung x2 dari x1 dengan menambahkan 2
  4. tetapkan x3 phi dari x1 dan x2
  5. panggilan cetak dengan x3

Tetapi Anda dapat melakukannya tanpa node phi (dalam pseudocode):

  1. mengalokasikan variabel lokal pada stack yang disebut x
  2. memuat ke temp nilai x1 4
  3. simpan x1 sampai x
  4. if (! sesuatu) bercabang ke 8
  5. memuat x ke temp x2
  6. tambahkan x2 dengan 4 ke temp x3
  7. simpan x3 sampai x
  8. memuat x ke temp x4
  9. panggil cetak dengan x4

Dengan menjalankan pengoptimalan lewat dengan llvm, kode kedua ini akan dioptimalkan ke kode pertama.

Mārtiņš Možeiko
sumber
4
Dari apa yang telah saya baca sepertinya ada beberapa batasan yang perlu diingat di sini. mem2reg adalah pass pengoptimalan yang dipermasalahkan, dan memiliki beberapa keterbatasan yang ditunjukkan dalam contoh Kaleidoskop . Namun, sepertinya ini adalah cara yang disukai untuk menangani masalah dan digunakan oleh Clang.
Matthew Sanders