[ProfInfo][SimplifyCFG] Wrong profile information after condition folding
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
In the provided IR module, after applying the `simplifycfg` pass, a condition folding results in branch probabilities no longer match the transformed control-flow. This issue is introduced by [`foldCondBranchOnValueKnownInPredecessorImpl`](https://github.com/llvm/llvm-project/blob/main/llvm/lib/Transforms/Utils/SimplifyCFG.cpp#L3499).
We tested LLVM at commit [42a77ce3d6ee47bf37351f3a7fb6bf5b341354e6](https://github.com/llvm/llvm-project/commit/42a77ce3d6ee47bf37351f3a7fb6bf5b341354e6).
```llvm
@d = local_unnamed_addr global [5 x i8] zeroinitializer
@a = local_unnamed_addr global i8 0
@b = local_unnamed_addr global i64 0
; Function Attrs: inlinehint nofree norecurse nosync nounwind memory(readwrite, argmem: none, inaccessiblemem: none, target_mem0: none, target_mem1: none)
define noundef i32 @main() local_unnamed_addr #0 !prof !29 {
bb:
%.pre = load i8, ptr @a, align 1
%.not = icmp eq i8 %.pre, 0
br label %.loopexit
.loopexit.loopexit: ; preds = %bb4
br label %.loopexit
.loopexit: ; preds = %.loopexit.loopexit, %bb
%i = phi i64 [ 1, %bb ], [ 0, %.loopexit.loopexit ]
%i1 = phi i1 [ true, %bb ], [ false, %.loopexit.loopexit ]
br label %bb2
bb2: ; preds = %bb4, %.loopexit
%i3 = phi i1 [ false, %bb4 ], [ %i1, %.loopexit ]
br i1 %i3, label %bb4, label %bb5, !prof !30
bb4: ; preds = %bb2
store i8 0, ptr @d, align 1
br i1 %.not, label %bb2, label %.loopexit.loopexit, !prof !31
bb5: ; preds = %bb2
store i64 %i, ptr @b, align 8
ret i32 0
}
attributes #0 = { inlinehint nofree norecurse nosync nounwind memory(readwrite, argmem: none, inaccessiblemem: none, target_mem0: none, target_mem1: none) }
!llvm.module.flags = !{!0}
!0 = !{i32 1, !"ProfileSummary", !1}
!1 = !{!2, !3, !4, !5, !6, !7, !8, !9, !10, !11}
!2 = !{!"ProfileFormat", !"InstrProf"}
!3 = !{!"TotalCount", i64 150}
!4 = !{!"MaxCount", i64 50}
!5 = !{!"MaxInternalCount", i64 50}
!6 = !{!"MaxFunctionCount", i64 50}
!7 = !{!"NumCounts", i64 3}
!8 = !{!"NumFunctions", i64 1}
!9 = !{!"IsPartialProfile", i64 0}
!10 = !{!"PartialProfileRatio", double 0.000000e+00}
!11 = !{!"DetailedSummary", !12}
!12 = !{!13, !14, !15, !16, !17, !18, !19, !20, !21, !22, !23, !24, !25, !26, !27, !28}
!13 = !{i32 10000, i64 50, i32 3}
!14 = !{i32 100000, i64 50, i32 3}
!15 = !{i32 200000, i64 50, i32 3}
!16 = !{i32 300000, i64 50, i32 3}
!17 = !{i32 400000, i64 50, i32 3}
!18 = !{i32 500000, i64 50, i32 3}
!19 = !{i32 600000, i64 50, i32 3}
!20 = !{i32 700000, i64 50, i32 3}
!21 = !{i32 800000, i64 50, i32 3}
!22 = !{i32 900000, i64 50, i32 3}
!23 = !{i32 950000, i64 50, i32 3}
!24 = !{i32 990000, i64 50, i32 3}
!25 = !{i32 999000, i64 50, i32 3}
!26 = !{i32 999900, i64 50, i32 3}
!27 = !{i32 999990, i64 50, i32 3}
!28 = !{i32 999999, i64 50, i32 3}
!29 = !{!"function_entry_count", i64 50}
!30 = !{!"branch_weights", i32 50, i32 50}
!31 = !{!"branch_weights", i32 50, i32 0}
```
#### Reproduction
The command to replicate this issue is the following:
```bash
opt before.ll -passes='simplifycfg' -S -o after.ll
```
The output `after.ll` is:
```llvm
define noundef i32 @main() local_unnamed_addr #0 !prof !29 {
bb:
%.pre = load i8, ptr @a, align 1
%.not = icmp eq i8 %.pre, 0
br label %.loopexit
.loopexit: ; preds = %bb4, %bb
%i = phi i64 [ 1, %bb ], [ 0, %bb4 ]
%i1 = phi i1 [ true, %bb ], [ false, %bb4 ]
br i1 %i1, label %bb4, label %bb5, !prof !30
bb4: ; preds = %.loopexit
store i8 0, ptr @d, align 1
br i1 %.not, label %bb5, label %.loopexit, !prof !31
bb5: ; preds = %bb4, %.loopexit
store i64 %i, ptr @b, align 8
ret i32 0
}
```
#### Detailed Issue Analysis
In the provided IR, we can identify two nested loops:
- The outer loop, L1, has its header at block `.loopexit`;
- The inner loop, L2, has its header at block `bb2`.
The execution flow is as follows: in the first (and only) iteration of L1, L2 is executed, and after its first iteration execution terminates through the edge from `bb2` to `bb5`. The branch probabilities in the IR before the application of the pass are correct: the edge from `bb4` to `.loopexit.loopexit` has weight 0, and the T/F probabilities from `bb2` are 50/50.
After applying `simplifycfg`, L1 is completely removed (because only a single iteration is always executed), and the terminating branch of block `bb2` is folded into the successor of L1's entry block (`.loopexit`). Also, the condition in `bb4` is inverted, creating a short-circuit to the exit block that avoid executing the loop condition twice.
In the resulting IR, the branch weights of the original terminating instruction of `bb2` get copied, but the new control-flow structure makes those weights stale. As a result, T/F probabilities remain 50/50, while they should be 100/0: the branch is executed once and the true branch is taken (execution terminates when the new edge from `bb4` to `bb5` is taken).
Below we provide the CFGs of the IR before (above) and after (below) the application of the pass.
Contributor guide
Assessment
This issue has not been assessed yet.