llvm / llvm/llvm-project

[ProfInfo][SimplifyCFG] Wrong profile information after condition folding

Open
#192,537 0 comments 0 reactions 1 assignee Claimed by @mtrofin View on GitHub
llvm:transforms PGO
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.

Image

Image

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.