Pertanyaan GCC: perbedaan vectorization antara dua loop serupa


Saat dikompilasi dengan gcc -O3, mengapa loop berikut tidak melakukan vectorize (otomatis):

#define SIZE (65536)

int a[SIZE], b[SIZE], c[SIZE];

int foo () {
  int i, j;

  for (i=0; i<SIZE; i++){
    for (j=i; j<SIZE; j++) {
      a[i] = b[i] > c[j] ? b[i] : c[j];
    }
  }
  return a[0];
}

ketika yang berikut ini?

#define SIZE (65536)

int a[SIZE], b[SIZE], c[SIZE];

int foov () {
  int i, j;

  for (i=0; i<SIZE; i++){
    for (j=i; j<SIZE; j++) {
      a[i] += b[i] > c[j] ? b[i] : c[j];
    }
  }
  return a[0];
}

Satu-satunya perbedaan adalah apakah hasil dari ekspresi dalam lingkaran dalam adalah ditugaskan ke [i], atau ditambahkan ke [i].

Sebagai referensi -ftree-vectorizer-verbose=6 memberikan output berikut untuk loop (non-vectorizing) pertama.

v.c:8: note: not vectorized: inner-loop count not invariant.
v.c:9: note: Unknown alignment for access: c
v.c:9: note: Alignment of access forced using peeling.
v.c:9: note: not vectorized: live stmt not supported: D.2700_5 = c[j_20];

v.c:5: note: vectorized 0 loops in function.

Dan output yang sama untuk loop yang vectorizes adalah:

v.c:8: note: not vectorized: inner-loop count not invariant.
v.c:9: note: Unknown alignment for access: c
v.c:9: note: Alignment of access forced using peeling.
v.c:9: note: vect_model_load_cost: aligned.
v.c:9: note: vect_model_load_cost: inside_cost = 1, outside_cost = 0 .
v.c:9: note: vect_model_simple_cost: inside_cost = 1, outside_cost = 1 .
v.c:9: note: vect_model_reduction_cost: inside_cost = 1, outside_cost = 6 .
v.c:9: note: cost model: prologue peel iters set to vf/2.
v.c:9: note: cost model: epilogue peel iters set to vf/2 because peeling for alignment is unknown .
v.c:9: note: Cost model analysis:
  Vector inside of loop cost: 3
  Vector outside of loop cost: 27
  Scalar iteration cost: 3
  Scalar outside cost: 7
  prologue iterations: 2
  epilogue iterations: 2
  Calculated minimum iters for profitability: 8

v.c:9: note:   Profitability threshold = 7

v.c:9: note: Profitability threshold is 7 loop iterations.
v.c:9: note: LOOP VECTORIZED.
v.c:5: note: vectorized 1 loops in function.

32
2017-08-23 16:55


asal


Jawaban:


Dalam kasus pertama: kode menimpa lokasi memori yang sama a[i] dalam setiap iterasi. Ini secara inheren mengurutkan loop sebagai iterasi loop tidak independen.
(Kenyataannya, hanya iterasi terakhir yang benar-benar diperlukan. Jadi seluruh bagian dalam lingkaran dapat diambil.)

Dalam kasus kedua: GCC mengakui loop sebagai operasi reduksi - untuk mana ia memiliki penanganan case khusus untuk vectorize.

Vectorisasi kompilator sering diimplementasikan sebagai semacam "pencocokan pola". Berarti kompiler menganalisa kode untuk melihat apakah itu sesuai dengan pola tertentu yang dapat melakukan vectorize. Jika ya, itu mendapat vektor. Jika tidak, maka tidak.

Ini tampaknya menjadi kasus sudut di mana loop pertama tidak sesuai dengan pola pra-kode yang dapat ditangani oleh GCC. Tetapi kasus kedua sesuai dengan pola "pengurangan yang bisa disesuaikan".


Inilah bagian yang relevan dari kode sumber GCC yang memuntahkan itu "not vectorized: live stmt not supported: " pesan:

http://svn.open64.net/svnroot/open64/trunk/osprey-gcc-4.2.0/gcc/tree-vect-analyze.c

if (STMT_VINFO_LIVE_P (stmt_info))
{
    ok = vectorizable_reduction (stmt, NULL, NULL);

    if (ok)
        need_to_vectorize = true;
    else
        ok = vectorizable_live_operation (stmt, NULL, NULL);

    if (!ok)
    {
        if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
        {
            fprintf (vect_dump, 
                "not vectorized: live stmt not supported: ");
            print_generic_expr (vect_dump, stmt, TDF_SLIM);
        }
        return false;
    }
}

Mulai dari baris:

vectorizable_reduction (stmt, NULL, NULL);

Sudah jelas bahwa GCC sedang memeriksa untuk melihat apakah itu cocok dengan pola "pengurangan yang bisa disesuaikan".


30
2017-08-23 17:42



Vectorizer GCC mungkin tidak cukup pintar untuk vectorize loop pertama. Kasus tambahan lebih mudah di-vectorize karena a + 0 == a. Mempertimbangkan SIZE==4:

  0 1 2 3 i
0 X
1 X X
2 X X X
3 X X X X
j

X menunjukkan kombinasi i dan j kapan a akan ditugaskan atau ditingkatkan. Untuk kasus penambahan, kita dapat menghitung hasil b[i] > c[j] ? b[i] : c[j] untuk, katakanlah, j==1 dan i==0..4 dan memasukkannya ke dalam vektor D. Maka kita hanya perlu nol D[2..3] dan tambahkan vektor yang dihasilkan ke a[0..3]. Untuk kasus penugasan, itu sedikit lebih sulit. Kita tidak boleh hanya nol D[2..3], tetapi juga nol A[0..1] dan baru kemudian menggabungkan hasilnya. Saya rasa ini adalah tempat vectorizer gagal.


3
2017-08-23 17:29



Lingkaran pertama setara dengan

#define SIZE (65536)

int a[SIZE], b[SIZE], c[SIZE];

int foo () {
  int i, j;

  for (i=0; i<SIZE; i++){
    a[i] = b[i] > c[SIZE - 1] ? b[i] : c[SIZE - 1];
  }
  return a[0];
}

Masalah dengan ekspresi asli adalah bahwa itu benar-benar tidak terlalu masuk akal, jadi tidak terlalu mengejutkan bahwa gcc tidak dapat melakukan vektorisasi.


3
2017-08-23 18:24



Yang pertama hanya sepele mengubah [] berkali-kali (sementara). Yang kedua menggunakan nilai terakhir [] setiap waktu (tidak sementara).

Sampai versi patch, Anda bisa menggunakan variabel "volatile" untuk melakukan vectorize.

Menggunakan

int * c=malloc(sizeof(int));

untuk membuatnya selaras;

v.c:9: note: Unknown alignment for access: c

Menunjukkan "c" memiliki area penyimpanan yang berbeda dari b dan a.

Saya menganggap instruksi "movaps" -seperti menjadi "vectorized" (dari daftar instruksi SSE-AVX)

Sini: http://gcc.gnu.org/projects/tree-ssa/vectorization.html#using

contoh ke-6 dan ke-7 menunjukkan kesulitan yang sama.


1
2017-08-23 17:12