Можно ли убедить Clang автоматически векторизовать этот код без использования встроенных функций? - PullRequest
Новая
       37

Можно ли убедить Clang автоматически векторизовать этот код без использования встроенных функций?

2 голосов
/ 21 мая 2019

Представьте, что у меня есть эта наивная функция для обнаружения перекрытия сфер.Смысл этого вопроса не в том, чтобы на самом деле обсуждать лучший способ тестирования на сферы, поэтому это просто для иллюстрации. 

inline bool sphere_hit(float x1, float y1, float z1, float r1,
        float x2, float y2, float z2, float r2) {
    float xd = (x1 - x2);
    float yd = (y1 - y2);
    float zd = (z1 - z2);

    float max_dist = (r1 + r2);

    return xd * xd + yd * yd + zd * zd < max_dist * max_dist;
}

И я называю это вложенным циклом следующим образом: 

std::vector<float> xs, ys, zs, rs;
int n_spheres;
// <snip>
int n_hits = 0;
for (int i = 0; i < n_spheres; ++i) {
    for (int j = i + 1; j < n_spheres; ++j) {
        if (sphere_hit(xs[i], ys[i], zs[i], rs[i],
                xs[j], ys[j], zs[j], rs[j])) {
            ++n_hits;
        }
    }
}
std::printf("total hits: %d\n", n_hits);

Теперь clang (с -O3 -march=native) достаточно умен, чтобы понять, как векторизовать (и развернуть) этот цикл в 256-битные инструкции avx2.Круто!

Однако, если я сделаю что-нибудь более сложное, чем увеличение числа попаданий, например, вызову какой-нибудь произвольной функции handle_hit(i, j), вместо этого clang испускает наивную скалярную версию.

Хиты должны бытьочень редко, так что я думаю, что должно произойти проверка на каждой итерации векторизованного цикла, если значение истинно для любой дорожек, и переход на некоторый скалярный медленный путь, если так.Это должно быть возможно с vcmpltps, за которым следует vmovmskps.Тем не менее, я не могу заставить clang выдать этот код, даже если я окружаю вызов sphere_hit с помощью __builtin_expect(..., 0).

1 Ответ

2 голосов
/ 04 июня 2019

Действительно, можно убедить clang векторизовать этот код.С параметрами компилятора -Rpass-analysis=loop-vectorize -Rpass=loop-vectorize -Rpass-missed=loop-vectorize, clang утверждает, что операции с плавающей запятой векторизованы, что подтверждается выводом Godbolt .(Подчеркнутые красным for s - это не ошибки, а отчеты о векторизации).

Векторизация возможна путем сохранения результатов sphere_hit в виде символов во временном массиве hitx8.После этого результаты 8 sphere_hit проверяются на итерацию путем считывания 8 символов из памяти как одного uint64_t a.Это должно быть достаточно эффективным, поскольку условие a!=0 (см. Код ниже) все еще встречается редко, поскольку попадания в сферу очень редки.Более того, массив hitx8, скорее всего, большую часть времени находится в кеше L1 или L2.

Я не проверял код на корректность, но по крайней мере идея автоматической векторизации должна работать. 

/* clang -Ofast -Wall -march=broadwell -Rpass-analysis=loop-vectorize -Rpass=loop-vectorize -Rpass-missed=loop-vectorize */
#include<string.h>
char sphere_hit(float x1, float y1, float z1, float r1,
        float x2, float y2, float z2, float r2);
void handle_hit(int i, int j);

void vectorized_code(float* __restrict xs, float* __restrict ys, float* __restrict zs, float* __restrict rs, char* __restrict hitx8, int n_spheres){
    unsigned long long int a;
    for (int i = 0; i < n_spheres; ++i) {
        for (int j = i + 1; j < n_spheres; ++j){
            /* Store the boolean results temporarily in char array hitx8.     */
            /* The indices of hitx8 are shifted by i+1, so the loop           */
            /* starts with hitx8[0]                                           */
            /* char array hitx8 should have n_spheres + 8 elements            */
            hitx8[j-i-1] = sphere_hit(xs[i], ys[i], zs[i], rs[i],
                    xs[j], ys[j], zs[j], rs[j]);
        }
        for (int j = n_spheres; j < n_spheres+8; ++j){
            /* Add 8 extra zeros at the end of hitx8.                   */
            hitx8[j-i-1] = 0;     /* hitx8 is 8 elements longer than xs */
        }
        for (int j = i + 1; j < n_spheres; j=j+8){
            memcpy(&a,&hitx8[j-i-1],8);
            /* Check 8 sphere hits in parallel:                                   */
            /* one `unsigned long long int a` contains 8 boolean values here      */ 
            /* The condition a!=0 is still rare since sphere hits are very rare.  */
            if (a!=0ull){ 
                if (hitx8[j-i-1+0] != 0) handle_hit(i,j+0);
                if (hitx8[j-i-1+1] != 0) handle_hit(i,j+1);
                if (hitx8[j-i-1+2] != 0) handle_hit(i,j+2);
                if (hitx8[j-i-1+3] != 0) handle_hit(i,j+3);
                if (hitx8[j-i-1+4] != 0) handle_hit(i,j+4);
                if (hitx8[j-i-1+5] != 0) handle_hit(i,j+5);
                if (hitx8[j-i-1+6] != 0) handle_hit(i,j+6);
                if (hitx8[j-i-1+7] != 0) handle_hit(i,j+7);
            }
        }
    }
}


inline char sphere_hit(float x1, float y1, float z1, float r1,
        float x2, float y2, float z2, float r2) {
    float xd = (x1 - x2);
    float yd = (y1 - y2);
    float zd = (z1 - z2);

    float max_dist = (r1 + r2);

    return xd * xd + yd * yd + zd * zd < max_dist * max_dist;
}
...