Kapan Undefined Behavior in C melompati penghalang kausalitas

Beberapa kompiler C hiper-modern akan menyimpulkan bahwa jika suatu program akan memanggil Perilaku Tidak Terdefinisi ketika diberi input tertentu, input seperti itu tidak akan pernah diterima. Akibatnya, kode apa pun yang tidak relevan kecuali jika input tersebut diterima dapat dihilangkan.

Sebagai contoh sederhana, diberikan:

void foo(uint32_t);

uint32_t rotateleft(uint_t value, uint32_t amount)
{
  return (value << amount) | (value >> (32-amount));
}

uint32_t blah(uint32_t x, uint32_t y)
{
  if (y != 0) foo(y);
  return rotateleft(x,y);
}

seorang kompiler dapat menyimpulkan bahwa karena evaluasi value >> (32-amount)akan menghasilkan Perilaku Tidak Terdefinisi ketika amountnol, fungsi blahtidak akan pernah dipanggil dengan ysama dengan nol; panggilan untuk foodemikian bisa dibuat tanpa syarat.

Dari apa yang bisa saya katakan, filosofi ini tampaknya telah bertahan sekitar tahun 2010. Bukti paling awal yang saya lihat dari akarnya kembali ke tahun 2009, dan itu telah diabadikan dalam standar C11 yang secara eksplisit menyatakan bahwa jika Perilaku Tidak Terdefinisi terjadi pada setiap titik dalam pelaksanaan program, perilaku seluruh program secara surut menjadi tidak terdefinisi.

Apakah gagasan bahwa kompiler harus berusaha untuk menggunakan Perilaku Undefined untuk membenarkan optimasi reverse-kausal (yaitu Perilaku Undefined di rotateleftfungsi harus menyebabkan compiler untuk mengasumsikan bahwa blahharus telah disebut dengan non-nol y, apakah tidak apa-apa akan pernah menyebabkan yuntuk memegang nilai tidak nol) secara serius diadvokasi sebelum 2009? Kapan hal seperti itu pertama kali diusulkan secara serius sebagai teknik optimasi?

[Tambahan]

Beberapa kompiler telah, bahkan di Abad ke-20, menyertakan opsi untuk memungkinkan beberapa jenis kesimpulan tentang loop dan nilai yang dihitung di dalamnya. Misalnya diberikan

int i; int total=0;
for (i=n; i>=0; i--)
{
  doSomething();
  total += i*1000;
}

kompiler, bahkan tanpa inferensi opsional, dapat menulis ulang sebagai:

int i; int total=0; int x1000;
for (i=n, x1000=n*1000; i>0; i--, x1000-=1000)
{
  doSomething();
  total += x1000;
}

karena perilaku kode itu akan sama persis dengan yang asli, bahkan jika kompilator menentukan bahwa intnilai selalu membungkus mod-65536 mode dua-pelengkap . Opsi tambahan-inferensi akan membiarkan kompiler mengenali bahwa karena idan x1000harus melewati nol pada saat yang sama, variabel sebelumnya dapat dihilangkan:

int total=0; int x1000;
for (x1000=n*1000; x1000 > 0; x1000-=1000)
{
  doSomething();
  total += x1000;
}

Pada sistem di mana intnilai dibungkus mod 65536, upaya untuk menjalankan salah satu dari dua loop pertama dengan n33 akan menghasilkan doSomething()dipanggil 33 kali. Loop terakhir, sebaliknya, tidak akan meminta doSomething()sama sekali, meskipun doa pertama doSomething()akan mendahului aritmatika melimpah. Perilaku seperti mungkin dianggap "non-kausal", tetapi efek yang cukup baik dibatasi dan ada banyak kasus di mana perilaku akan terbukti berbahaya (dalam kasus di mana fungsi yang diperlukan untuk menghasilkan beberapa nilai ketika diberikan setiap masukan, tetapi nilai mungkin sewenang-wenang jika input tidak valid, memiliki loop selesai lebih cepat ketika diberi nilai tidak valid sebesarnsebenarnya akan bermanfaat). Lebih lanjut, dokumentasi kompiler cenderung meminta maaf karena fakta bahwa itu akan mengubah perilaku program apa pun - bahkan yang terlibat di UB.

Saya tertarik ketika sikap penulis kompiler berubah dari gagasan bahwa platform harus ketika mendokumentasikan beberapa kendala perilaku yang dapat digunakan bahkan dalam kasus-kasus yang tidak diamanatkan oleh Standar, dengan gagasan bahwa setiap konstruksi yang akan bergantung pada perilaku yang tidak diamanatkan oleh Standar harus dicap tidak sah bahkan jika pada kebanyakan kompiler yang ada itu akan berfungsi dengan baik atau lebih baik daripada kode yang memenuhi persyaratan yang sama memenuhi persyaratan yang sama (sering memungkinkan optimasi yang tidak mungkin dilakukan dalam kode yang sepenuhnya mematuhi).

Perilaku tidak terdefinisi digunakan dalam situasi di mana tidak layak bagi spec untuk menentukan perilaku, dan selalu ditulis untuk memungkinkan benar-benar perilaku yang mungkin.

Aturan yang sangat longgar untuk UB sangat membantu ketika Anda berpikir tentang apa yang harus melalui kompiler penyesuai spesifikasi. Anda mungkin memiliki daya kuda kompilasi yang cukup untuk mengeluarkan kesalahan ketika Anda melakukan UB yang buruk dalam satu kasus, tetapi menambahkan beberapa lapisan rekursi dan sekarang yang terbaik yang dapat Anda lakukan adalah peringatan. Spec tidak memiliki konsep "peringatan," jadi jika spec telah memberikan perilaku, itu harus menjadi "kesalahan."

Alasan kita melihat semakin banyak efek samping dari ini adalah dorongan untuk optimasi. Menulis spec optimizer yang sesuai sulit. Menulis pengoptimal konform spesifikasi yang juga terjadi untuk melakukan pekerjaan yang sangat baik menebak apa yang Anda maksudkan ketika Anda pergi ke luar spek itu brutal. Lebih mudah pada kompiler jika mereka menganggap UB berarti UB.

Ini terutama berlaku untuk gcc, yang mencoba mendukung banyak set instruksi dengan kompiler yang sama. Jauh lebih mudah untuk membiarkan UB menghasilkan perilaku UB daripada mencoba untuk bergulat dengan semua cara setiap kode UB bisa salah di setiap platform, dan memasukkannya ke dalam frasa awal pengoptimal.

"Perilaku tidak terdefinisi mungkin menyebabkan kompiler untuk menulis ulang kode" telah terjadi sejak lama, dalam optimisasi loop.

Ambil satu lingkaran (a dan b adalah penunjuk untuk digandakan, misalnya)

for (i = 0; i < n; ++i) a [i] = b [i];

Kami menambah int, kami menyalin elemen array, kami membandingkan dengan batas. Kompilator pengoptimal pertama-tama menghapus pengindeksan:

double* tmp1 = a;
double* tmp2 = b;
for (i = 0; i < n; ++i) *tmp1++ = *tmp2++;

Kami menghapus kasing n <= 0:

i = 0;
if (n > 0) {
    double* tmp1 = a;
    double* tmp2 = b;
    for (; i < n; ++i) *tmp1++ = *tmp2++;
}

Sekarang kita menghilangkan variabel i:

i = 0;
if (n > 0) {
    double* tmp1 = a;
    double* tmp2 = b;
    double* limit = tmp1 + n;
    for (; tmp1 != limit; tmp1++, tmp2++) *tmp1 = *tmp2;
    i = n;
}

Sekarang jika n = 2 ^ 29 pada sistem 32 bit atau 2 ^ 61 pada sistem 64 bit, pada implementasi tipikal kita akan memiliki batas tmp1 ==, dan tidak ada kode yang dieksekusi. Sekarang ganti tugas dengan sesuatu yang membutuhkan waktu lama sehingga kode asli tidak akan pernah mengalami crash yang tak terhindarkan karena terlalu lama, dan kompiler telah mengubah kode.

Selalu menjadi kasus dalam C dan C ++ bahwa sebagai akibat dari perilaku yang tidak terdefinisi, apa pun bisa terjadi. Oleh karena itu juga selalu menjadi kasus bahwa kompiler dapat membuat asumsi bahwa kode Anda tidak memunculkan perilaku tidak terdefinisi: Entah tidak ada perilaku yang tidak terdefinisi dalam kode Anda, maka anggapan itu benar. Atau ada perilaku yang tidak terdefinisi dalam kode Anda, maka apa pun yang terjadi sebagai akibat dari asumsi yang salah dicakup oleh " apa pun bisa terjadi".

Jika Anda melihat fitur "pembatasan" dalam C, inti keseluruhan dari fitur ini adalah bahwa kompiler dapat mengasumsikan tidak ada perilaku yang tidak terdefinisi, jadi di sana kami mencapai titik di mana kompiler tidak hanya dapat tetapi sebenarnya harus berasumsi tidak ada yang tidak terdefinisi tingkah laku.

Pada contoh yang Anda berikan, instruksi assembler yang biasanya digunakan pada komputer berbasis x86 untuk menerapkan shift kiri atau kanan akan bergeser 0 bit jika jumlah shift 32 untuk kode 32 bit atau 64 untuk kode 64 bit. Ini dalam kebanyakan kasus praktis akan mengarah pada hasil yang tidak diinginkan (dan hasil yang tidak sama seperti pada ARM atau PowerPC, misalnya), sehingga kompiler cukup dibenarkan untuk menganggap bahwa perilaku tidak terdefinisi semacam ini tidak terjadi. Anda dapat mengubah kode Anda menjadi

uint32_t rotateleft(uint_t value, uint32_t amount)
{
   return amount == 0 ? value : (value << amount) | (value >> (32-amount));
}

dan menyarankan kepada pengembang gcc atau Dentang bahwa pada kebanyakan prosesor kode "jumlah == 0" harus dihapus oleh kompiler, karena kode assembler yang dihasilkan untuk kode shift akan menghasilkan hasil yang sama dengan nilai ketika jumlah == 0.

Ini karena ada bug dalam kode Anda:

uint32_t blah(uint32_t x, uint32_t y)
{
    if (y != 0) 
    {
        foo(y);
        return x; ////// missing return here //////
    }
    return rotateleft(x, y);
}

Dengan kata lain, itu hanya melompati penghalang kausalitas jika kompilator melihat bahwa, dengan input tertentu, Anda memohon perilaku tidak terdefinisi tanpa keraguan .

Dengan kembali tepat sebelum doa perilaku tidak terdefinisi, Anda memberi tahu kompiler bahwa Anda secara sadar mencegah perilaku tidak terdefinisi tersebut untuk dieksekusi, dan kompilator mengakui hal itu.

Dengan kata lain, ketika Anda memiliki kompiler yang mencoba untuk menegakkan spesifikasi dengan cara yang sangat ketat, Anda harus mengimplementasikan setiap validasi argumen yang mungkin dalam kode Anda. Selanjutnya, validasi ini harus terjadi sebelum doa dari perilaku yang tidak terdefinisi tersebut.

Tunggu! Dan masih ada lagi!

Sekarang, dengan kompiler melakukan hal-hal yang super-gila namun super-logis, Anda harus memberi tahu kompiler bahwa suatu fungsi tidak seharusnya melanjutkan eksekusi. Dengan demikian, noreturnkata kunci pada foo()fungsi sekarang menjadi wajib .