Mengapa deteksi kode mati tidak dapat sepenuhnya dipecahkan oleh kompiler?

Kompiler yang telah saya gunakan di C atau Java memiliki pencegahan kode mati (peringatan ketika sebuah baris tidak akan pernah dieksekusi). Profesor saya mengatakan bahwa masalah ini tidak akan pernah bisa diselesaikan sepenuhnya oleh kompiler. Saya bertanya-tanya mengapa itu. Saya tidak terlalu terbiasa dengan pengkodean kompiler yang sebenarnya karena ini adalah kelas berbasis teori. Tapi saya bertanya-tanya apa yang mereka periksa (seperti string input yang mungkin vs input yang dapat diterima, dll), dan mengapa itu tidak cukup.

Masalah kode mati terkait dengan masalah Berhenti .

Alan Turing membuktikan bahwa mustahil untuk menulis algoritma umum yang akan diberikan suatu program dan dapat memutuskan apakah program itu berhenti untuk semua input. Anda mungkin dapat menulis algoritma seperti itu untuk jenis program tertentu, tetapi tidak untuk semua program.

Bagaimana ini berhubungan dengan kode mati?

Masalah Henti dapat direduksi menjadi masalah menemukan kode mati. Artinya, jika Anda menemukan algoritma yang dapat mendeteksi kode mati di program apa pun , maka Anda dapat menggunakan algoritma itu untuk menguji apakah suatu program akan berhenti. Karena itu telah terbukti tidak mungkin, maka menulis algoritma untuk kode mati juga tidak mungkin.

Bagaimana Anda mentransfer algoritme untuk kode mati ke algoritme untuk masalah Berhenti?

Sederhana: Anda menambahkan satu baris kode setelah akhir program yang ingin Anda periksa penghentiannya. Jika detektor kode mati Anda mendeteksi bahwa baris ini sudah mati, maka Anda tahu bahwa programnya tidak berhenti. Jika tidak, maka Anda tahu bahwa program Anda berhenti (sampai ke baris terakhir, dan kemudian ke baris kode yang ditambahkan).

Compiler biasanya memeriksa hal-hal yang dapat dibuktikan pada saat kompilasi untuk mati. Misalnya, blok yang bergantung pada kondisi yang dapat dianggap salah pada waktu kompilasi. Atau pernyataan apa pun setelah return(dalam lingkup yang sama).

Ini adalah kasus-kasus khusus, dan oleh karena itu dimungkinkan untuk menulis sebuah algoritma untuk mereka. Dimungkinkan untuk menulis algoritma untuk kasus yang lebih rumit (seperti algoritma yang memeriksa apakah suatu kondisi secara sintaksis merupakan kontradiksi dan karenanya akan selalu kembali salah), tetapi tetap saja, itu tidak akan mencakup semua kasus yang mungkin.

Baiklah, mari kita ambil bukti klasik dari ketidakpastian masalah penghentian dan ubah detektor penghenti menjadi detektor kode mati!

Program C #

using System;
using YourVendor.Compiler;

class Program
{
    static void Main(string[] args)
    {
        string quine_text = @"using System;
using YourVendor.Compiler;

class Program
{{
    static void Main(string[] args)
    {{
        string quine_text = @{0}{1}{0};
        quine_text = string.Format(quine_text, (char)34, quine_text);

        if (YourVendor.Compiler.HasDeadCode(quine_text))
        {{
            System.Console.WriteLine({0}Dead code!{0});
        }}
    }}
}}";
        quine_text = string.Format(quine_text, (char)34, quine_text);

        if (YourVendor.Compiler.HasDeadCode(quine_text))
        {
            System.Console.WriteLine("Dead code!");
        }
    }
}

Jika YourVendor.Compiler.HasDeadCode(quine_text)kembali false, maka saluran System.Console.WriteLn("Dead code!");tidak akan pernah dieksekusi, jadi program ini sebenarnya melakukannya memiliki kode mati, dan detektor yang salah.

Tetapi jika itu kembali true, maka garisSystem.Console.WriteLn("Dead code!"); akan dieksekusi, dan karena tidak ada lagi kode dalam program, tidak ada kode mati sama sekali, jadi sekali lagi, detektor itu salah.

Jadi begitulah, detektor kode mati yang hanya mengembalikan "Ada kode mati" atau "Tidak ada kode mati" terkadang harus menghasilkan jawaban yang salah.

Jika masalah penghentian terlalu jelas, pikirkan seperti ini.

Ambil masalah matematika yang diyakini benar untuk semua bilangan bulat positif ini n , tapi belum terbukti benar untuk setiap n . Contoh yang baik adalah dugaan Goldbach , bahwa setiap bilangan bulat positif bahkan lebih besar dari dua dapat diwakili oleh jumlah dua bilangan prima. Kemudian (dengan perpustakaan bigint yang sesuai) jalankan program ini (pseudocode berikut):

 for (BigInt n = 4; ; n+=2) {
     if (!isGoldbachsConjectureTrueFor(n)) {
         print("Conjecture is false for at least one value of n\n");
         exit(0);
     }
 }

Implementasi isGoldbachsConjectureTrueFor()dibiarkan sebagai latihan untuk pembaca tetapi untuk tujuan ini bisa menjadi iterasi sederhana atas semua bilangan prima kurang darin

Sekarang, secara logis di atas harus sama dengan:

 for (; ;) {
 }

(yaitu loop tak terbatas) atau

print("Conjecture is false for at least one value of n\n");

sebagai dugaan Goldbach harus benar atau tidak benar. Jika kompiler selalu dapat menghilangkan kode mati, pasti akan ada kode mati untuk dihilangkan di sini dalam kedua kasus. Namun, dalam melakukannya, paling tidak kompiler Anda harus menyelesaikan masalah sulit yang sewenang-wenang. Kami dapat memberikan masalah yang terbukti sulit yang harus diselesaikan (misalnya masalah NP-complete) untuk menentukan bit kode mana yang harus dihilangkan. Misalnya jika kita mengambil program ini:

 String target = "f3c5ac5a63d50099f3b5147cabbbd81e89211513a92e3dcd2565d8c7d302ba9c";
 for (BigInt n = 0; n < 2**2048; n++) {
     String s = n.toString();
     if (sha256(s).equals(target)) {
         print("Found SHA value\n");
         exit(0);
     }
 }
 print("Not found SHA value\n");

kami tahu bahwa program akan mencetak "Nilai SHA yang ditemukan" atau "Nilai tidak ditemukan SHA" (poin bonus jika Anda dapat memberi tahu saya mana yang benar). Namun, bagi seorang kompiler untuk dapat mengoptimalkan secara wajar yang akan mengambil urutan 2 ^ 2048 iterasi. Ini sebenarnya akan menjadi optimisasi yang hebat karena saya memprediksi program di atas akan (atau mungkin) berjalan sampai kematian panas alam semesta daripada mencetak apa pun tanpa optimasi.

Saya tidak tahu apakah C ++ atau Java memiliki Evalfungsi tipe, tetapi banyak bahasa memungkinkan Anda melakukan metode panggilan dengan nama . Pertimbangkan contoh VBA (dibuat-buat) berikut ini.

Dim methodName As String

If foo Then
    methodName = "Bar"
Else
    methodName = "Qux"
End If

Application.Run(methodName)

Nama metode yang dipanggil tidak mungkin diketahui sampai runtime. Oleh karena itu, menurut definisi, kompiler tidak dapat mengetahui dengan pasti bahwa metode tertentu tidak pernah dipanggil.

Sebenarnya, mengingat contoh memanggil metode dengan nama, logika percabangan bahkan tidak diperlukan. Cukup mengatakan

Application.Run("Bar")

Lebih dari yang dapat ditentukan oleh kompiler. Ketika kode dikompilasi, semua kompiler tahu adalah bahwa nilai string tertentu diteruskan ke metode itu. Itu tidak memeriksa untuk melihat apakah metode itu ada sampai runtime. Jika metode tidak dipanggil di tempat lain, melalui metode yang lebih normal, upaya untuk menemukan metode mati dapat mengembalikan hasil positif palsu. Masalah yang sama ada dalam bahasa apa pun yang memungkinkan kode dipanggil melalui refleksi.

Kode mati tanpa syarat dapat dideteksi dan dihapus oleh kompiler tingkat lanjut.

Tetapi ada juga kode mati bersyarat. Itu adalah kode yang tidak dapat diketahui pada saat kompilasi dan hanya dapat dideteksi selama runtime. Sebagai contoh, sebuah perangkat lunak dapat dikonfigurasi untuk menyertakan atau mengecualikan fitur tertentu tergantung pada preferensi pengguna, membuat bagian-bagian tertentu dari kode tampaknya mati dalam skenario tertentu. Itu bukan kode mati sungguhan.

Ada alat khusus yang dapat melakukan pengujian, menyelesaikan dependensi, menghapus kode mati bersyarat dan menggabungkan kembali kode yang berguna saat runtime untuk efisiensi. Ini disebut penghapusan kode mati dinamis. Tapi seperti yang Anda lihat itu di luar lingkup kompiler.

Contoh sederhana:

int readValueFromPort(const unsigned int portNum);

int x = readValueFromPort(0x100); // just an example, nothing meaningful
if (x < 2)
{
    std::cout << "Hey! X < 2" << std::endl;
}
else
{
    std::cout << "X is too big!" << std::endl;
}

Sekarang asumsikan bahwa port 0x100 dirancang untuk mengembalikan hanya 0 atau 1. Dalam hal ini kompiler tidak dapat mengetahui bahwa elseblok tidak akan pernah dieksekusi.

Namun dalam contoh dasar ini:

bool boolVal = /*anything boolean*/;

if (boolVal)
{
  // Do A
}
else if (!boolVal)
{
  // Do B
}
else
{
  // Do C
}

Di sini kompiler dapat menghitung elseblok adalah kode mati. Jadi kompilator dapat memperingatkan tentang kode mati hanya jika memiliki cukup data untuk mengetahui kode mati dan juga harus tahu bagaimana menerapkan data itu untuk mengetahui apakah blok yang diberikan adalah kode mati.

EDIT

Kadang-kadang data tidak tersedia pada waktu kompilasi:

// File a.cpp
bool boolMethod();

bool boolVal = boolMethod();

if (boolVal)
{
  // Do A
}
else
{
  // Do B
}

//............
// File b.cpp
bool boolMethod()
{
    return true;
}

Saat mengkompilasi a.cpp, kompiler tidak dapat mengetahui bahwa boolMethodselalu kembali true.

Kompiler akan selalu kekurangan beberapa informasi konteks. Misalnya Anda mungkin tahu, bahwa nilai ganda tidak pernah melebihi 2, karena itu adalah fitur fungsi matematika, yang Anda gunakan dari perpustakaan. Kompiler bahkan tidak melihat kode di perpustakaan, dan ia tidak pernah dapat mengetahui semua fitur dari semua fungsi matematika, dan mendeteksi semua cara yang rumit dan rumit untuk mengimplementasikannya.

Kompiler tidak selalu melihat keseluruhan program. Saya bisa memiliki program yang memanggil perpustakaan bersama, yang memanggil kembali ke fungsi dalam program saya yang tidak dipanggil secara langsung.

Jadi fungsi yang mati sehubungan dengan perpustakaan yang dikompilasi dapat menjadi hidup jika perpustakaan itu diubah saat runtime.

Jika kompiler dapat menghilangkan semua kode mati secara akurat, itu akan disebut interpreter .

Pertimbangkan skenario sederhana ini:

if (my_func()) {
  am_i_dead();
}

my_func() dapat berisi kode arbitrer dan agar kompiler dapat menentukan apakah mengembalikan benar atau salah, ia harus menjalankan kode atau melakukan sesuatu yang secara fungsional setara dengan menjalankan kode.

Gagasan kompiler adalah bahwa ia hanya melakukan analisis sebagian kode, sehingga menyederhanakan pekerjaan dari lingkungan berjalan yang terpisah. Jika Anda melakukan analisis lengkap, itu bukan kompiler lagi.

Jika Anda menganggap kompiler sebagai fungsi c(), di mana c(source)=compiled code, dan lingkungan yang berjalan sebagai r(), di mana r(compiled code)=program output, maka untuk menentukan output untuk kode sumber apa pun Anda harus menghitung nilai r(c(source code)). Jika penghitungan c()membutuhkan pengetahuan tentang nilai r(c())untuk input apa pun, tidak perlu untuk terpisah r()dan c(): Anda hanya dapat memperoleh fungsi i()dari c()itu i(source)=program output.

Yang lain mengomentari masalah penghentian dan sebagainya. Ini biasanya berlaku untuk bagian-bagian fungsi. Namun bisa sulit / tidak mungkin untuk mengetahui apakah bahkan seluruh tipe (kelas / dll) digunakan atau tidak.

Di .NET / Java / JavaScript dan lingkungan yang didorong oleh runtime lainnya, tidak ada yang menghentikan tipe yang dimuat melalui refleksi. Ini populer dengan kerangka kerja injeksi ketergantungan, dan bahkan lebih sulit untuk dipertimbangkan dalam menghadapi deserialisasi atau pemuatan modul dinamis.

Kompiler tidak dapat mengetahui apakah tipe seperti itu akan dimuat. Nama mereka dapat berasal dari file konfigurasi eksternal saat runtime.

Anda mungkin ingin mencari di sekitar pohon goyang yang merupakan istilah umum untuk alat yang berusaha untuk menghapus subgraph kode yang tidak digunakan dengan aman.

Ambil fungsi

void DoSomeAction(int actnumber) 
{
    switch(actnumber) 
    {
        case 1: Action1(); break;
        case 2: Action2(); break;
        case 3: Action3(); break;
    }
}

Bisakah Anda membuktikan bahwa actnumbertidak akan pernah 2demikian yang Action2()tidak pernah disebut ...?

Saya tidak setuju tentang masalah penghentian. Saya tidak akan menyebut kode tersebut mati meskipun dalam kenyataannya tidak akan pernah tercapai.

Sebagai gantinya, mari pertimbangkan:

for (int N = 3;;N++)
  for (int A = 2; A < int.MaxValue; A++)
    for (int B = 2; B < int.MaxValue; B++)
    {
      int Square = Math.Pow(A, N) + Math.Pow(B, N);
      float Test = Math.Sqrt(Square);
      if (Test == Math.Trunc(Test))
        FermatWasWrong();
    }

private void FermatWasWrong()
{
  Press.Announce("Fermat was wrong!");
  Nobel.Claim();
}

(Abaikan kesalahan jenis dan melimpah) Kode mati?

Lihatlah contoh ini:

public boolean isEven(int i){

    if(i % 2 == 0)
        return true;
    if(i % 2 == 1)
        return false;
    return false;
}

Kompiler tidak dapat mengetahui bahwa int hanya bisa genap atau ganjil. Oleh karena itu kompiler harus dapat memahami semantik kode Anda. Bagaimana seharusnya ini diterapkan? Kompiler tidak dapat memastikan bahwa pengembalian terendah tidak akan pernah dieksekusi. Karenanya kompiler tidak dapat mendeteksi kode mati.