OpenMP SIMD无符号长整型逻辑AND未生成ANDPS指令问题

需求背景 #

• 本实现用于解决RRFRNDS问题（核心需求为查找拥有共同好友的用户对），实现思路是将64位好友标识位（标记是否为好友）打包存入unsigned long long类型变量中。
• SIMD实现方案：对两组关系向量做按位AND运算，再通过OR归约，该逻辑完全符合OpenMP规约模式要求。

编译环境与参数 #

运行环境为2019款Intel i7 MacBookPro，使用g++-11编译，编译指令如下：
g++-11 friends.cpp -S -O3 -fopenmp -fsanitize=address -Wshadow -Wall -march=native --std=c++17;

初始实现代码 #

#include <vector>
#include <algorithm>
#include "iostream"
#include <cmath>
#include <numeric>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
ull find_sol(vector<vector<ull>> & input_data, int q) {
    bool not_friend = false;
    ull cnt = 0;
    int size_arr = (int) input_data[0].size();
    for (int i = 0; i < q; ++i){
        for (int j = i+1; j < q; ++j){
            int step = j/64;
            int remainder = j - 64*step;
            not_friend = (input_data[i].at(step) >> remainder) % 2 == 0;
            if(not_friend){
                bool counter = false;
                vector<ull> & v1 = input_data[i];
                vector<ull> & v2 = input_data[j];
                #pragma omp simd reduction(|:counter)
                for (int c = 0; c < size_arr; ++c){
                    __asm__ ("entry");
                    counter |= (v1[c] & v2[c])>0;
                    __asm__ ("exit");
                }
                if(counter>0)cnt++;
            }
        }
    }
    return cnt << 1;
}
int main(){
    int q;
    cin >> q;
    vector<vector<ull>> input_data(q,vector<ull>(1 + q/64,0ULL));
    for (int i = 0; i < q; ++i){
        string s;
        cin >> s;
        for (int j = 0; j < 1 + q/64; ++j){
            string str = s.substr(j*64,64);
            reverse(str.begin(),str.end());
            ull ul = std::stoull(str,nullptr,2);
            input_data.at(i).at(j) = ul;
        }
    }
    cout << find_sol(input_data,q) << endl;
}

问题现象 #

查看循环对应的汇编代码，未发现预期的SIMD指令（尤其是ANDPS），对应汇编输出如下：

entry# 0 "" 2
cmpb    $0, (%rbx)
jne L53
movq    (%r8), %rdx
leaq    0(,%rax,8), %rdi
addq    %rdi, %rdx
movq    %rdx, %r15
shrq    $3, %r15
cmpb    $0, (%r15,%rcx)
jne L54
cmpb    $0, (%r11)
movq    (%rdx), %rdx
jne L55
addq    (%r9), %rdi
movq    %rdi, %r15
shrq    $3, %r15
cmpb    $0, (%r15,%rcx)
jne L56
andq    (%rdi), %rdx
movzbl  (%r12), %edx
setne   %dil
cmpb    %r13b, %dl
jg  L21
testb   %dl, %dl
jne L57
L21:
orb %dil, -32(%r10)

调整后代码及现象 #

将汇编标记移出循环，并且将二值化判断改为直接做OR归约，调整后代码如下，但仍未生成SIMD指令：

ull counter = 0;
vector<ull> & v1 = input_data[i];
vector<ull> & v2 = input_data[j];
__asm__ ("entry" :::);
#pragma omp simd reduction(|:counter)
for (int c = 0; c < size_arr; ++c){
    counter |= v1[c] & v2[c];
}
__asm__ ("exit" :::);
if(counter!=0)cnt++;

问题原因分析 #

• 编译参数携带-fsanitize=address：地址消毒工具会插入大量内存访问检查逻辑，默认禁用SIMD向量化避免边界检查失效，去掉该参数即可恢复向量化逻辑判断。
• at()方法的边界检查阻断向量化：STL的at()方法自带越界检查，会引入额外分支逻辑，g++的OpenMP SIMD实现无法对带分支的循环做向量化，将所有input_data.at(xxx)替换为operator[]直接访问即可消除分支干扰。
• 指令类型匹配问题：你当前操作的是无符号64位整数，编译器默认优先生成整数SIMD指令（如VPAND）而非浮点的ANDPS，两者逻辑等价、性能差异极小，无需刻意追求ANDPS指令。
• 循环长度过短导致向量化收益不足：当q小于2048时，size_arr = 1 + q/64最大仅为33，循环迭代次数太少，编译器判断向量化带来的性能收益低于寄存器调度、指令预热的开销，主动放弃向量化。

向量化失败告警开启方法 #

编译时增加参数-fopt-info-vec-missed -fopenmp-simd，控制台会输出具体循环的向量化失败原因，包括存在分支、边界检查、循环长度不足等信息。

内容的提问来源于stack exchange，提问作者Guillaume