Mengapa loop sederhana dioptimalkan ketika batasnya adalah 959 tetapi tidak 960?

Pertimbangkan loop sederhana ini:

float f(float x[]) {
  float p = 1.0;
  for (int i = 0; i < 959; i++)
    p += 1;
  return p;
}

Jika Anda mengompilasi dengan gcc 7 (snapshot) atau dentang (trunk) dengan -march=core-avx2 -OfastAnda mendapatkan sesuatu yang sangat mirip.

.LCPI0_0:
        .long   1148190720              # float 960
f:                                      # @f
        vmovss  xmm0, dword ptr [rip + .LCPI0_0] # xmm0 = mem[0],zero,zero,zero
        ret

Dengan kata lain itu hanya mengatur jawaban ke 960 tanpa perulangan.

Namun, jika Anda mengubah kode menjadi:

float f(float x[]) {
  float p = 1.0;
  for (int i = 0; i < 960; i++)
    p += 1;
  return p;
}

Perakitan yang dihasilkan benar-benar melakukan jumlah loop? Misalnya dentang memberi:

.LCPI0_0:
        .long   1065353216              # float 1
.LCPI0_1:
        .long   1086324736              # float 6
f:                                      # @f
        vmovss  xmm0, dword ptr [rip + .LCPI0_0] # xmm0 = mem[0],zero,zero,zero
        vxorps  ymm1, ymm1, ymm1
        mov     eax, 960
        vbroadcastss    ymm2, dword ptr [rip + .LCPI0_1]
        vxorps  ymm3, ymm3, ymm3
        vxorps  ymm4, ymm4, ymm4
.LBB0_1:                                # =>This Inner Loop Header: Depth=1
        vaddps  ymm0, ymm0, ymm2
        vaddps  ymm1, ymm1, ymm2
        vaddps  ymm3, ymm3, ymm2
        vaddps  ymm4, ymm4, ymm2
        add     eax, -192
        jne     .LBB0_1
        vaddps  ymm0, ymm1, ymm0
        vaddps  ymm0, ymm3, ymm0
        vaddps  ymm0, ymm4, ymm0
        vextractf128    xmm1, ymm0, 1
        vaddps  ymm0, ymm0, ymm1
        vpermilpd       xmm1, xmm0, 1   # xmm1 = xmm0[1,0]
        vaddps  ymm0, ymm0, ymm1
        vhaddps ymm0, ymm0, ymm0
        vzeroupper
        ret

Mengapa ini dan mengapa persis sama untuk dentang dan gcc?

Batas untuk loop yang sama jika Anda ganti floatdengan doubleadalah 479. Ini sama untuk gcc dan berdering lagi.

Perbarui 1

Ternyata gcc 7 (snapshot) dan dentang (trunk) berperilaku sangat berbeda. dentang mengoptimalkan loop untuk semua batas kurang dari 960 sejauh yang saya tahu. gcc di sisi lain sensitif terhadap nilai yang tepat dan tidak memiliki batas atas. Misalnya ia tidak mengoptimalkan loop ketika batasnya adalah 200 (dan juga banyak nilai lainnya) tetapi ia melakukannya ketika batasnya adalah 202 dan 20002 (serta banyak nilai lainnya).

TL; DR

Secara default, snapshot GCC 7 saat ini berperilaku tidak konsisten, sedangkan versi sebelumnya memiliki batas default karena PARAM_MAX_COMPLETELY_PEEL_TIMES, yaitu 16. Ini dapat diganti dari baris perintah.

Alasan dari batasan ini adalah untuk mencegah loop yang terlalu agresif membuka gulungan, yang bisa menjadi pedang bermata dua .

Versi GCC <= 6.3.0

Opsi pengoptimalan yang relevan untuk GCC adalah -fpeel-loops, yang diaktifkan secara tidak langsung bersamaan dengan tanda -Ofast(penekanan adalah milikku):

Peel loop yang ada informasi cukup bahwa mereka tidak banyak roll (dari umpan balik profil atau analisis statis ). Ini juga mengaktifkan peeling loop lengkap (yaitu penghapusan lengkap loop dengan jumlah iterasi yang konstan kecil ).

Diaktifkan dengan -O3dan / atau -fprofile-use.

Rincian lebih lanjut dapat diperoleh dengan menambahkan -fdump-tree-cunroll:

$ head test.c.151t.cunroll 

;; Function f (f, funcdef_no=0, decl_uid=1919, cgraph_uid=0, symbol_order=0)

Not peeling: upper bound is known so can unroll completely

Pesannya dari /gcc/tree-ssa-loop-ivcanon.c:

if (maxiter >= 0 && maxiter <= npeel)
    {
      if (dump_file)
        fprintf (dump_file, "Not peeling: upper bound is known so can "
         "unroll completely\n");
      return false;
    }

karenanya try_peel_loopfungsi kembali false.

Lebih banyak keluaran verbal dapat dicapai dengan -fdump-tree-cunroll-details:

Loop 1 iterates 959 times.
Loop 1 iterates at most 959 times.
Not unrolling loop 1 (--param max-completely-peeled-times limit reached).
Not peeling: upper bound is known so can unroll completely

Dimungkinkan untuk mengubah batas dengan melakukan plaing dengan max-completely-peeled-insns=ndan max-completely-peel-times=nparams:

max-completely-peeled-insns

Jumlah maksimum lns dari loop sepenuhnya dikupas.

max-completely-peel-times

Jumlah maksimum iterasi loop yang sesuai untuk pengelupasan lengkap.

Untuk mempelajari lebih lanjut tentang perusahaan, Anda dapat merujuk ke Manual Internal GCC .

Misalnya, jika Anda mengompilasi dengan opsi berikut:

-march=core-avx2 -Ofast --param max-completely-peeled-insns=1000 --param max-completely-peel-times=1000

lalu kode berubah menjadi:

f:
        vmovss  xmm0, DWORD PTR .LC0[rip]
        ret
.LC0:
        .long   1148207104

Dentang

Saya tidak yakin apa yang sebenarnya dilakukan Dentang dan bagaimana mengubah batas-batasnya, tetapi seperti yang saya amati, Anda bisa memaksanya untuk mengevaluasi nilai akhir dengan menandai loop dengan pragma membuka gulungan , dan itu akan menghapusnya sepenuhnya:

#pragma unroll
for (int i = 0; i < 960; i++)
    p++;

hasil menjadi:

.LCPI0_0:
        .long   1148207104              # float 961
f:                                      # @f
        vmovss  xmm0, dword ptr [rip + .LCPI0_0] # xmm0 = mem[0],zero,zero,zero
        ret

Setelah membaca komentar Sulthan, saya kira itu:

1. Compiler sepenuhnya membuka gulungan loop jika penghitung loop konstan (dan tidak terlalu tinggi)

2. Setelah dibuka, kompiler melihat bahwa operasi penjumlahan dapat dikelompokkan menjadi satu.

Jika loop tidak terbuka untuk beberapa alasan (di sini: itu akan menghasilkan terlalu banyak pernyataan dengan 1000), operasi tidak dapat dikelompokkan.

Kompilator dapat melihat bahwa membuka gulungan dari 1000 pernyataan berjumlah satu tambahan, tetapi langkah 1 & 2 yang dijelaskan di atas adalah dua optimisasi terpisah, sehingga tidak dapat mengambil "risiko" membuka gulungan, tidak tahu apakah operasi dapat dikelompokkan (contoh: panggilan fungsi tidak dapat dikelompokkan).

Catatan: Ini adalah kasus sudut: Siapa yang menggunakan loop untuk menambahkan hal yang sama lagi? Dalam hal ini, jangan bergantung pada kompiler yang memungkinkan membuka gulungan / mengoptimalkan; langsung tulis operasi yang tepat dalam satu instruksi.

Pertanyaan yang sangat bagus

Anda tampaknya telah mencapai batas pada jumlah iterasi atau operasi yang coba dilakukan oleh kompiler saat menyederhanakan kode. Seperti yang didokumentasikan oleh Grzegorz Szpetkowski, ada cara khusus kompiler untuk mengubah batas ini dengan pragma atau opsi baris perintah.

Anda juga dapat bermain dengan Explorer Kompiler Godbolt untuk membandingkan bagaimana berbagai kompiler dan opsi berdampak pada kode yang dihasilkan: gcc 6.2dan icc 17masih sebaris kode untuk 960, sedangkan clang 3.9tidak (dengan konfigurasi default Godbolt, itu sebenarnya berhenti sebaris di 73).