llvm / llvm/llvm-project

[StructurizeCFG] Loop-carried value updated on only one back-edge is replaced with poison (miscompile)

Open
#210,695 2 comments 0 reactions 0 assignees View on GitHub
llvm:transforms miscompilation
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.