[StructurizeCFG] Loop-carried value updated on only one back-edge is replaced with poison (miscompile)
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
StructurizeCFG introduces poison for a loop-carried value on the back-edge where the value must be preserved.
In the test, %last is updated only on the latch -> header back-edge; on the "bypass" latch -> body back-edge it must keep its previous value. Every incoming of %last is well defined (0 or %min), so the input is poison-free and %last is always 0.
After opt -passes=structurizecfg, the reconstructed phi on the newly-created bypass edge is seeded with poison (%0 = phi i32 [ %min, %latch ], [ poison, %body ]); the poison flows back into %last and is consumed by the compare in latch — a value that can never be poison in the source becomes poison. This is a miscompile.
```llvm
; opt -S -passes=structurizecfg < %s
declare i32 @llvm.smin.i32(i32, i32)
define void @f(i1 %exit.cond, i1 %store.cond) {
entry:
br label %header
header:
%last = phi i32 [ 0, %entry ], [ %min, %latch ]
br label %body
body:
br i1 %exit.cond, label %calc, label %exit
calc:
%min = call i32 @llvm.smin.i32(i32 0, i32 0)
br label %latch
latch:
%cmp = icmp sgt i32 %min, %last
br i1 %store.cond, label %header, label %body
exit:
ret void
}
```
after structurizecfg:
```llvm
declare i32 @llvm.smin.i32(i32, i32) #0
define void @f(i1 %exit.cond, i1 %store.cond) {
entry:
%store.cond.inv = xor i1 %store.cond, true
br label %header
header: ; preds = %Flow1, %entry
%last = phi i32 [ 0, %entry ], [ %0, %Flow1 ]
br label %body
body: ; preds = %Flow, %header
br i1 %exit.cond, label %calc, label %Flow
calc: ; preds = %body
%min = call i32 @llvm.smin.i32(i32 0, i32 0)
br label %latch
Flow: ; preds = %latch, %body
%0 = phi i32 [ %min, %latch ], [ poison, %body ]
%1 = phi i1 [ %store.cond.inv, %latch ], [ true, %body ]
%2 = phi i1 [ %store.cond, %latch ], [ true, %body ]
br i1 %2, label %Flow1, label %body
latch: ; preds = %calc
%cmp = icmp sgt i32 %min, %last
br label %Flow
Flow1: ; preds = %Flow
br i1 %1, label %exit, label %header
exit: ; preds = %Flow1
ret void
}
attributes #0 = { nocallback nocreateundeforpoison nofree nosync nounwind speculatable willreturn memory(none) }
```
```
; %last is a loop-carried value:
; * on the %latch -> %header back-edge it is updated to %min;
; * on the "bypass" %latch -> %body back-edge it MUST keep its previous value.
; In the input every incoming value of %last is well defined (0 or %min), so the
; program is completely poison-free and %last is always 0.
;
; When StructurizeCFG flattens the two back-edges into a single structured loop
; it has to reconstruct SSA for %last on the newly-created bypass edge. Instead
; of forwarding the preserved value it seeds that edge with `poison`. The poison
; then flows back into %last and is consumed by the compare in %latch, so a
; value that could never be poison in the original program becomes poison. This
; is a miscompile.
;
; Actual (buggy) output -- note "[ poison, %body ]" feeding %last:
;
; Flow:
; %0 = phi i32 [ %min, %latch ], [ poison, %body ] ; <-- wrong
; header:
; %last = phi i32 [ 0, %entry ], [ %0, %Flow1 ]
;
; Expected: the bypass edge must forward the preserved value, not poison, e.g.
;
; Flow:
; %1 = phi i32 [ %min, %latch ], [ %0, %body ] ; %0 = preserved %last
;
```
Contributor guide
Research direction
Start by running the supplied LLVM IR reproducer with opt -S -passes=structurizecfg and inspect the StructurizeCFG transformation that reconstructs SSA for the flattened loop. Done means the bypass back-edge forwards the preserved loop-carried value rather than poison, with the reproducer demonstrating poison-free behavior.
Written by the indexing model from the issue text.
Assessment
- Domain
- compilers
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 48/100