Bisakah saya memberi petunjuk pengoptimal dengan memberikan kisaran integer?

Saya menggunakan inttipe untuk menyimpan nilai. Dengan semantik program, nilainya selalu bervariasi dalam kisaran yang sangat kecil (0 - 36), dan int(bukan a char) digunakan hanya karena efisiensi CPU.

Sepertinya banyak optimasi aritmatika khusus dapat dilakukan pada sejumlah kecil bilangan bulat. Banyak pemanggilan fungsi pada bilangan bulat itu mungkin dioptimalkan menjadi satu set kecil operasi "ajaib", dan beberapa fungsi bahkan mungkin dioptimalkan ke dalam pencarian tabel.

Jadi, apakah mungkin untuk memberitahu kompiler bahwa ini intselalu dalam kisaran kecil, dan apakah mungkin bagi kompiler untuk melakukan optimasi tersebut?

Ya itu mungkin. Misalnya, untuk gccAnda dapat menggunakan __builtin_unreachableuntuk memberi tahu kompiler tentang kondisi yang tidak mungkin, seperti:

if (value < 0 || value > 36) __builtin_unreachable();

Kami dapat membungkus kondisi di atas dalam makro:

#define assume(cond) do { if (!(cond)) __builtin_unreachable(); } while (0)

Dan gunakan seperti ini:

assume(x >= 0 && x <= 10);

Seperti yang Anda lihat , gcclakukan optimasi berdasarkan informasi ini:

#define assume(cond) do { if (!(cond)) __builtin_unreachable(); } while (0)

int func(int x){
    assume(x >=0 && x <= 10);

    if (x > 11){
        return 2;
    }
    else{
        return 17;
    }
}

Menghasilkan:

func(int):
    mov     eax, 17
    ret

Namun satu kelemahannya adalah bahwa jika kode Anda pernah melanggar asumsi seperti itu, Anda mendapatkan perilaku yang tidak jelas .

Itu tidak memberi tahu Anda ketika ini terjadi, bahkan di build debug. Untuk men-debug / menguji / menangkap bug dengan asumsi lebih mudah, Anda dapat menggunakan makro asumsi / klaim hybrid (kredit ke @ David Z), seperti ini:

#if defined(NDEBUG)
#define assume(cond) do { if (!(cond)) __builtin_unreachable(); } while (0)
#else
#include <cassert>
#define assume(cond) assert(cond)
#endif

Dalam membangun debug (dengan NDEBUG tidak didefinisikan), ia bekerja seperti biasa assert, mencetak pesan kesalahan dan abortprogram, dan dalam rilis build itu menggunakan asumsi, menghasilkan kode yang dioptimalkan.

Perhatikan, bagaimanapun, bahwa itu bukan pengganti biasa assert- condtetap dalam rilis rilis, jadi Anda tidak harus melakukan sesuatu seperti assume(VeryExpensiveComputation()).

Ada dukungan standar untuk ini. Apa yang harus Anda lakukan adalah memasukkan stdint.h( cstdint) dan kemudian menggunakan jenisnya uint_fast8_t.

Ini memberitahu kompiler bahwa Anda hanya menggunakan angka antara 0 - 255, tetapi itu bebas untuk menggunakan tipe yang lebih besar jika itu memberikan kode lebih cepat. Demikian pula, kompiler dapat mengasumsikan bahwa variabel tidak akan pernah memiliki nilai di atas 255 dan kemudian melakukan optimasi yang sesuai.

Jawaban saat ini baik untuk kasus saat Anda tahu pasti kisarannya, tetapi jika Anda masih menginginkan perilaku yang benar saat nilainya di luar kisaran yang diharapkan, maka tidak akan berfungsi.

Untuk itu, saya menemukan teknik ini dapat bekerja:

if (x == c)  // assume c is a constant
{
    foo(x);
}
else
{
    foo(x);
}

Idenya adalah pertukaran kode-data: Anda memindahkan 1 bit data (apakah x == c) ke dalam logika kontrol .
Ini mengisyaratkan ke pengoptimal yang xsebenarnya adalah konstanta yang diketahui c, mendorongnya untuk menyesuaikan dan mengoptimalkan permintaan pertama foosecara terpisah dari yang lain, mungkin cukup berat.

Pastikan untuk benar-benar memasukkan kode ke dalam satu subrutin foo, - jangan menduplikasi kodenya.

Contoh:

Agar teknik ini berfungsi, Anda harus sedikit beruntung - ada kasus di mana kompiler memutuskan untuk tidak mengevaluasi hal-hal secara statis, dan mereka agak sewenang-wenang. Tetapi ketika berhasil, itu bekerja dengan baik:

#include <math.h>
#include <stdio.h>

unsigned foo(unsigned x)
{
    return x * (x + 1);
}

unsigned bar(unsigned x) { return foo(x + 1) + foo(2 * x); }

int main()
{
    unsigned x;
    scanf("%u", &x);
    unsigned r;
    if (x == 1)
    {
        r = bar(bar(x));
    }
    else if (x == 0)
    {
        r = bar(bar(x));
    }
    else
    {
        r = bar(x + 1);
    }
    printf("%#x\n", r);
}

Cukup gunakan -O3dan perhatikan konstanta pra-evaluasi 0x20dan 0x30edalam output assembler .

Saya hanya ingin mengatakan bahwa jika Anda ingin solusi yang lebih standar C ++, Anda dapat menggunakan [[noreturn]]atribut untuk menulis sendiriunreachable .

Jadi saya akan mengarahkan kembali contoh bagus deniss ' untuk menunjukkan:

namespace detail {
    [[noreturn]] void unreachable(){}
}

#define assume(cond) do { if (!(cond)) detail::unreachable(); } while (0)

int func(int x){
    assume(x >=0 && x <= 10);

    if (x > 11){
        return 2;
    }
    else{
        return 17;
    }
}

Yang seperti yang Anda lihat , menghasilkan kode yang hampir identik:

detail::unreachable():
        rep ret
func(int):
        movl    $17, %eax
        ret

Kelemahannya tentu saja, bahwa Anda mendapatkan peringatan bahwa suatu [[noreturn]]fungsi memang kembali.