llvm / llvm/llvm-project

[GVN][LV] - GVN load PRE creates phi nodes that prevent loop vectorization.

Open
#222,277 6 comments 0 reactions 2 assignees Claimed by @fhahn View on GitHub
llvm:GVN missed-optimization vectorizers
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

GVN's load PRE optimization hoists cross-iteration redundant loads into
phi nodes, which the loop vectorizer does not recognize as inductions or
reductions, causing it to bail out.

When a loop body has computation on both sides of the induction variable
increment, subsequent iterations can reuse values loaded in the previous
iteration. GVN load PRE detects this and replaces the redundant loads
with phi nodes that carry the value forward. While this saves loads in
scalar execution, it creates phi nodes that the loop vectorizer cannot
classify, blocking vectorization entirely.

```c
void v097(int n, int *a, int *b, int *c, int *d, int *e) {
int i = 0;
L10:
if (i >= n-1) goto L20;
b[i] = b[i] + d[i] * e[i];
i = i + 1;
a[i] = c[i] + d[i] * e[i];
goto L10;
L20: ;
}
```

After the increment, d[i] and e[i] for the a[i] computation are
loaded. On the next iteration, the b[i] computation needs d[i] and
e[i] again, but i has advanced, so these are the same values just
loaded. Load PRE replaces the reload with phi nodes.

```llvm
target datalayout = "e-m:e-p:64:64-i64:64-i128:128-n32:64-S128"
target triple = "riscv64-unknown-linux-gnu"
define void @v097(i32 %n, ptr noalias %a, ptr noalias %b, ptr noalias readonly %c, ptr noalias readonly %d, ptr noalias readonly %e) #0 {
entry:
%cmp = icmp sgt i32 %n, 1
br i1 %cmp, label %preheader, label %exit
preheader:
%sub = add nsw i32 %n, -1
%trip = zext nneg i32 %sub to i64
%d.init = load i32, ptr %d, align 4
%e.init = load i32, ptr %e, align 4
br label %loop
loop:
%e.pre = phi i32 [ %e.init, %preheader ], [ %e.next, %loop ]
%d.pre = phi i32 [ %d.init, %preheader ], [ %d.next, %loop ]
%iv = phi i64 [ 0, %preheader ], [ %iv.next, %loop ]
%b.ptr = getelementptr inbounds i32, ptr %b, i64 %iv
%b.val = load i32, ptr %b.ptr, align 4
%mul1 = mul nsw i32 %e.pre, %d.pre
%sum1 = add nsw i32 %mul1, %b.val
store i32 %sum1, ptr %b.ptr, align 4
%iv.next = add nuw nsw i64 %iv, 1
%c.ptr = getelementptr inbounds i32, ptr %c, i64 %iv.next
%c.val = load i32, ptr %c.ptr, align 4
%d.ptr = getelementptr inbounds i32, ptr %d, i64 %iv.next
%d.next = load i32, ptr %d.ptr, align 4
%e.ptr = getelementptr inbounds i32, ptr %e, i64 %iv.next
%e.next = load i32, ptr %e.ptr, align 4
%mul2 = mul nsw i32 %e.next, %d.next
%sum2 = add nsw i32 %mul2, %c.val
%a.ptr = getelementptr inbounds i32, ptr %a, i64 %iv.next
store i32 %sum2, ptr %a.ptr, align 4
%done = icmp eq i64 %iv.next, %trip
br i1 %done, label %exit, label %loop
exit:
ret void
}
attributes #0 = { vscale_range(4,1024) "target-cpu"="generic-rv64" "target-features"="+64bit,+v" }
```

```
LV: Found a loop: loop
LV: Not vectorizing: Found an unidentified PHI %e.pre = phi i32 [ %e.init, %preheader ], [ %e.next, %loop ]
```

Expected IR (vectorizes successfully)
Replacing the PRE phis with explicit loads at %iv restores vectorization:

```llvm
loop:
%iv = phi i64 [ 0, %preheader ], [ %iv.next, %loop ]
; Rematerialized loads instead of PRE phis
%d.ptr0 = getelementptr inbounds i32, ptr %d, i64 %iv
%d.val0 = load i32, ptr %d.ptr0, align 4
%e.ptr0 = getelementptr inbounds i32, ptr %e, i64 %iv
%e.val0 = load i32, ptr %e.ptr0, align 4
%b.ptr = getelementptr inbounds i32, ptr %b, i64 %iv
%b.val = load i32, ptr %b.ptr, align 4
%mul1 = mul nsw i32 %e.val0, %d.val0
%sum1 = add nsw i32 %mul1, %b.val
store i32 %sum1, ptr %b.ptr, align 4
...
```

This produces:

```
LV: Found a vectorizable loop (vscale x 4)
```

While the following workaround exists, I wonder if this can be done in code without having to use the option `-mllvm -enable-load-pre=false` disables load PRE globally and restores vectorization.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.