emscripten-core / emscripten-core/emscripten
Nested loop vectorization
- 主要言語
- C++
- スター
- 27.6k
- フォーク
- 3.6k
- 平均マージ
- 1日 14時間
- マージ済み PR(30日)
- 125
説明
I have a nested loop that computes data in two dimensions, like this:
```c
for (int i = satellites_start; i < satellites_end; i++)
{
for (int j = dates_start; j < dates_end; j++)
{
// calculations go here
}
}
```
I compile with `-O3 -msimd128 -Rpass=loop-vectorize -Rpass-missed=loop-vectorize -Rpass-analysis=loop-vectorize` options. The inner loop is automatically vectorized, but not the outer loop (as expected by default).
I have found that in LLVM it is possible to enable nested loop vectorization by using "VPlan native path" instead of the default "standard path" (if I understand correctly) and I want to try. Here's what I did:
1. I added `-mllvm -enable-vplan-native-path` to options. Emscripten doesn't error so I assume the option is passed to LLVM.
2. I added `#pragma clang loop vectorize(enable) vectorize_width(2)` above the outer loop (otherwise it still only vectorizes the inner loop).
This is what output I get:
```
src-cpp/common.cpp:653:3: remark: loop not vectorized: loop control flow is not understood by vectorizer [-Rpass-analysis]
653 | for (int i = satellites_start; i < satellites_end; i++)
| ^
src-cpp/common.cpp:653:3: remark: loop not vectorized: Unsupported outer loop [-Rpass-analysis]
src-cpp/common.cpp:653:3: remark: loop not vectorized (Force=true, Vector Width=2) [-Rpass-missed=loop-vectorize]
src-cpp/common.cpp:653:3: warning: loop not vectorized: the optimizer was unable to perform the requested transformation; the transformation might be disabled
or specified as part of an unsupported transformation ordering [-Wpass-failed=transform-warning]
```
However I tried this code in someone's example and it was successfully vectorized:
```c
void example(int n, int a[1024][1024], int b[1024][1024])
{
#pragma clang loop vectorize(enable) vectorize_width(4)
for (int i = 1; i < n; i++) {
for (int j = 0; j < n; j++) {
a[j][i] = a[j][i-1] + b[i][j];
}
}
}
```
So I decided to make my code dumber and dumber until it is vectorized, but even this function (which at this point doesn't do anything useful) won't get vectorized together with outer loop:
```c
void calculate_doppler_factor_test(
int satellites_start, int satellites_end,
int dates_start, int dates_end, int dates_count,
double *__restrict doppler_factors)
{
#pragma clang loop vectorize(enable) vectorize_width(2)
for (int i = satellites_start; i < satellites_end; i++)
{
for (int j = dates_start; j < dates_end; j++)
{
int doppler_factor_index = (i * dates_count + j);
doppler_factors[doppler_factor_index] = 1.0;
}
}
}
```
Just like with my original code, as soon as I remove `#pragma`, it vectorizes the inner loop though.
I would imagine that if inner loop vectorizes, outer loop should too, if it only contains the inner loop and nothing else. Obviously that's not the case. So I wonder, compared to the standard LLVM vectorization, what are additional constraints on loops for outer loop vectorization?
I tested this on Emscripten 4.0.16.
コントリビューションガイド
調査の方向性
Emscripten 4.0.16、-O3、-msimd128、loop-vectorizer の remark、および -enable-vplan-native-path を使用して、src-cpp/common.cpp の 653 行目付近の診断を再現します。pragma による例と最小限の calculate_doppler_factor_test ケースを比較し、その後 VPlan native path と outer-loop vectorizer のエントリポイントを調べます。完了とは、サポートされている制約、または明確に範囲を限定したコンパイラ変更を特定することです。
索引モデルが issue の本文から書いたものです。
評価
- 技術スタック
- cpp, wasm
- 領域
- compilers, performance
- issue の種類
- 機能追加
- 難易度
- 5/5
- 見積もり時間
- 1週間以上
- 活発さ
- 停滞
- 明瞭さ
- 説明が足りない
- 初心者へのやさしさ
- 25/100