Hi,
In downstream LLVM compiler, we have this optimization (developed back in 2012) that if we have expensive array index computation that only depends on the loop induction variables. At the same time the ranges and increments of these induction variables are known at compile time. Then we can precompute the array indexes at compile time and place them in a static array, and then look up at run time.
I have posted this optimization in PR 90263. Introducing a PrecomputeLoopExpressionsPass in IR optimization pipeline.
To demonstrate this idea, use test.c below. This is a reduced test from customer mp3decoder codebase.
extern int cos_table[4 * 36];
void foo(int out[36]) {
int p, m, N, sum;
N = 36;
for (p=0; p<N; p++){
sum = 0;
for (m=0; m < N/2; m++)
sum += cos_table[((2*p+1+N/2)*(2*m+1))%(4*36)];
out[p] = sum;
}
}
Sub-expression “…(2m+1))%144” is expensive and cannot be hoisted outside.
PrecomputeLoopExpressionsPass will create a static array Temp[36][18], use expression “((2p+1+N/2)(2m+1))%144" to initialize Temp. Then transform original array index computation "cos_table[((2p+1+N/2)(2m+1))%144]” into a lookup from Temp “cos_table[[Temp[p][m]]”.
Apply PR90263, run below command to see the IR and assembly difference.
clang --target=aarch64 -mcpu=cortex-x4 -march=armv8.7-a -S -O3 test.c -fno-unroll-loops -o pcle.ll -emit-llvm
append “-mllvm -disable-pcle” to disable PrecomputeLoopExpresions to get baseline output.
Then you will see PCLE cuts 3 instructions from innermost loop in the generated assembly.
.LBB0_2: // baseline
// Parent Loop BB0_1 Depth=1
// => This Inner Loop Header: Depth=2
umulh x1, x17, x12
subs w16, w16, #1
add x17, x17, x11
lsr x1, x1, #7
mul x1, x1, x13
ldr w1, [x18, x1]
add x18, x18, x9
add w15, w1, w15
b.ne .LBB0_2
.LBB0_2: // with PCLE
// Parent Loop BB0_1 Depth=1
// => This Inner Loop Header: Depth=2
ldr w13, [x9, x12]
add x12, x12, #4
cmp x12, #72
ldr w13, [x10, x13, lsl #2]
add w11, w13, w11
b.ne .LBB0_2
In IR generated, you will see that
sequence
%mul6 = shl nuw nsw i32 %m.023, 1
%add7 = or disjoint i32 %mul6, 1
%mul8 = mul nuw nsw i32 %add7, %1
%rem = urem i32 %mul8, 144
is replaced with
%txgep = getelementptr [36 x [18 x i32]], ptr @tx0, i64 0, i64 %indvars.iv27, i64 %indvars.iv
%txld = load i32, ptr %txgep, align 4
Although PR90263 optimization is able to speedup that customer mp3decoder benchmark by 50%. I don’t see other internal benchmarks benefit from such optimization.
There are two major limitations:
- The ranges and increments of loop induction variables need to be compile-time known. And array index computation depends only on these induction variables, with no other runtime variables.
- The current implementation use type extension from i32 (computation based on induction variable) to i64 (GEP offset) to detect candidate expressions. But not general enough to apply to cases like function calls.
There are similar patterns in ffmpeg https://ffmpeg.org/
tests/checkasm/vp9dsp.c
static void fdct_1d(double *out, const double *in, int sz)
{
int k, n;
for (k = 0; k < sz; k++) {
out[k] = 0.0;
for (n = 0; n < sz; n++)
out[k] += in[n] * cos(M_PI * (2 * n + 1) * k / (sz * 2.0));
}
out[0] *= M_SQRT1_2;
}
If ‘sz’ is compile-time known, “cos(M_PI * (2 * n + 1) * k / (sz * 2.0))” should be optimized in a similar way. But we need to figure out better ways to detect candidate expressions.
I want to share this optimization to get more feedbacks.
And see if there are other benchmarks that can benefit from such optimization.
Also want to see if there are enough interest to bring such optimization into main.
Thanks, -Huihui