llvm / llvm/llvm-project

[ProfInfo][SimplifyCFG] Missing profile metadata after hoisting identical terminators

Open
#192,539 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, two identical terminators are hoisted, but profile information is not preserved even though it is present on one of them. Specifically, the metadata is present on the branch that, according to the profile, is always executed.
This is caused by [`hoistCommonCodeFromSuccessors`](https://github.com/llvm/llvm-project/blob/main/llvm/lib/Transforms/Utils/SimplifyCFG.cpp#L1853) not merging metadata for terminators (detailed analysis below).

We tested LLVM at commit [42a77ce3d6ee47bf37351f3a7fb6bf5b341354e6](https://github.com/llvm/llvm-project/commit/42a77ce3d6ee47bf37351f3a7fb6bf5b341354e6).

```llvm
@a = local_unnamed_addr global i32 0
@d = local_unnamed_addr global i32 0
@c = local_unnamed_addr global i32 0

; Function Attrs: inlinehint
define i32 @main() local_unnamed_addr #0 !prof !29 {
bb:
%i = load i32, ptr @d, align 4
%i1 = load i32, ptr @a, align 4
%i2 = icmp sgt i32 %i1, 0
br i1 %i2, label %bb5, label %bb3, !prof !30

bb3: ; preds = %bb
%i4 = icmp eq i32 %i, 0
br i1 %i4, label %common.ret, label %bb7, !prof !31

bb5: ; preds = %bb
%i6 = icmp eq i32 %i, 0
br i1 %i6, label %common.ret, label %bb7

common.ret: ; preds = %bb7, %bb5, %bb3
ret i32 0

bb7: ; preds = %bb5, %bb3
store i32 0, ptr @c, align 4
br label %common.ret
}

attributes #0 = { inlinehint }

!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 100}
!4 = !{!"MaxCount", i64 50}
!5 = !{!"MaxInternalCount", i64 50}
!6 = !{!"MaxFunctionCount", i64 50}
!7 = !{!"NumCounts", i64 4}
!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 2}
!14 = !{i32 100000, i64 50, i32 2}
!15 = !{i32 200000, i64 50, i32 2}
!16 = !{i32 300000, i64 50, i32 2}
!17 = !{i32 400000, i64 50, i32 2}
!18 = !{i32 500000, i64 50, i32 2}
!19 = !{i32 600000, i64 50, i32 2}
!20 = !{i32 700000, i64 50, i32 2}
!21 = !{i32 800000, i64 50, i32 2}
!22 = !{i32 900000, i64 50, i32 2}
!23 = !{i32 950000, i64 50, i32 2}
!24 = !{i32 990000, i64 50, i32 2}
!25 = !{i32 999000, i64 50, i32 2}
!26 = !{i32 999900, i64 50, i32 2}
!27 = !{i32 999990, i64 50, i32 2}
!28 = !{i32 999999, i64 50, i32 2}
!29 = !{!"function_entry_count", i64 50}
!30 = !{!"branch_weights", i32 0, i32 50}
!31 = !{!"branch_weights", i32 50, i32 0}
```

#### Reproduction
The following command reproduces the issue:
```bash
opt before.ll -passes='simplifycfg' -S -o after.ll
```
The output `after.ll` is:
```llvm
@a = local_unnamed_addr global i32 0
@d = local_unnamed_addr global i32 0
@c = local_unnamed_addr global i32 0

; Function Attrs: inlinehint
define i32 @main() local_unnamed_addr #0 !prof !29 {
bb:
%i = load i32, ptr @d, align 4
%i6 = icmp eq i32 %i, 0
br i1 %i6, label %common.ret, label %bb7

common.ret: ; preds = %bb, %bb7
ret i32 0

bb7: ; preds = %bb
store i32 0, ptr @c, align 4
br label %common.ret
}

[...]
!29 = !{!"function_entry_count", i64 50}
```

As shown above, after applying the pass, the hoisted terminator has no branch-weight metadata. As a result, branch probabilities are computed using heuristics instead of accurate profile information (as seen in the before/after CFGs below).


Image


Image

#### Detailed Issue Analysis

We found this issue to be caused by [`hoistCommonCodeFromSuccessors`](https://github.com/llvm/llvm-project/blob/main/llvm/lib/Transforms/Utils/SimplifyCFG.cpp#L1853). Here, the common successor basic blocks are iterated in successor order, thus `bb5` (the block with no profile metadata) is read before `bb3` (the block with profile metadata) and instructions from the first are used to construct the new hoisted block. In fact, the terminator hoisted is explicitely the first successor in the transformation (see [`hoistSuccIdenticalTerminatorToSwitchOrIf`](https://github.com/llvm/llvm-project/blob/main/llvm/lib/Transforms/Utils/SimplifyCFG.cpp#L2061)).
We found that this issue is caused by [`hoistCommonCodeFromSuccessors`](https://github.com/llvm/llvm-project/blob/main/llvm/lib/Transforms/Utils/SimplifyCFG.cpp#L1853). In this path, common successor basic blocks are iterated in successor order, so `bb5` (the block without profile metadata) is processed before `bb3` (the block with profile metadata), and instructions from the first are used to build the hoisted block. In fact, the hoisted terminator is explicitly taken from the first successor in this transformation (see [`hoistSuccIdenticalTerminatorToSwitchOrIf`](https://github.com/llvm/llvm-project/blob/main/llvm/lib/Transforms/Utils/SimplifyCFG.cpp#L2061)).

Notably, non-terminator instructions have all their [metadata merged](https://github.com/llvm/llvm-project/blob/main/llvm/lib/Transforms/Utils/SimplifyCFG.cpp#L2018), while terminators only have [debug locations merged](https://github.com/llvm/llvm-project/blob/main/llvm/lib/Transforms/Utils/SimplifyCFG.cpp#L2096).

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.