llvm / llvm/llvm-project

[ProfInfo][CHR] Wrong synthetic branch probabilities upon chr

Open
#190,946 0 comments 0 reactions 0 assignees View on GitHub
PGO
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

### Biased branch created by CHR is flipped with respect to actual execution

When applying `chr` to the provided IR module, the branch probability for the transformed terminator of block `bb` is set to 100% for the true branch but it should be flipped, since the condition always evaluates to false. This behavior is caused by `chr` [assigning the merged guard branch synthetic weights](https://github.com/llvm/llvm-project/blob/main/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp#L1909) from the minimum constituent bias, which can incorrectly produce `!prof !{!"branch_weights", i32 1000, i32 0}` even when the merged condition is not actually always true (never in this particular case). This behavior is controlled with [bias threshold which default value is 0.99](https://github.com/llvm/llvm-project/blob/main/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp#L58).

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

```llvm
@e = dso_local local_unnamed_addr global i64 2, align 8
@d = internal unnamed_addr global i1 false, align 2
@f = dso_local local_unnamed_addr global i8 0, align 1
@b = internal unnamed_addr global i1 false, align 4
@g = dso_local local_unnamed_addr global i16 0, align 2
@c = dso_local local_unnamed_addr global i16 0, align 2
@a = dso_local local_unnamed_addr global i64 0, align 8

; Function Attrs: inlinehint mustprogress nofree norecurse nosync nounwind willreturn memory(readwrite, argmem: none, inaccessiblemem: none, target_mem0: none, target_mem1: none) uwtable
define dso_local void @main() local_unnamed_addr #0 !prof !37 {
bb:
%i = load i1, ptr @d, align 2
%i1 = zext i1 %i to i8
store i8 %i1, ptr @f, align 1, !tbaa !38
%i2 = load i1, ptr @b, align 4
%i3 = select i1 %i2, i16 9, i16 0, !prof !39
store i16 %i3, ptr @g, align 2, !tbaa !40
br i1 %i2, label %bb8, label %bb4, !prof !39

bb4: ; preds = %bb
%i5 = load i64, ptr @e, align 8, !tbaa !42
store i1 true, ptr @b, align 4
%i6 = trunc i64 %i5 to i32
%i7 = icmp slt i32 %i6, 1
br i1 %i7, label %bb9, label %bb8, !prof !39

bb8: ; preds = %bb4, %bb
store i1 true, ptr @d, align 2
br label %bb11

bb9: ; preds = %bb4
store i16 0, ptr @c, align 2, !tbaa !40
%i10 = select i1 %i, i64 0, i64 43, !prof !44
br label %bb11

bb11: ; preds = %bb9, %bb8
%i12 = phi i64 [ %i10, %bb9 ], [ 0, %bb8 ]
store i64 %i12, ptr @a, align 8, !tbaa !42
ret void
}

attributes #0 = { inlinehint mustprogress nofree norecurse nosync nounwind willreturn memory(readwrite, argmem: none, inaccessiblemem: none, target_mem0: none, target_mem1: none) uwtable "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }

!llvm.module.flags = !{!0, !1, !2, !3}
!llvm.ident = !{!32}
!llvm.errno.tbaa = !{!33}

!0 = !{i32 8, !"PIC Level", i32 2}
!1 = !{i32 7, !"PIE Level", i32 2}
!2 = !{i32 7, !"uwtable", i32 2}
!3 = !{i32 1, !"ProfileSummary", !4}
!4 = !{!5, !6, !7, !8, !9, !10, !11, !12, !13, !14}
!5 = !{!"ProfileFormat", !"InstrProf"}
!6 = !{!"TotalCount", i64 150}
!7 = !{!"MaxCount", i64 50}
!8 = !{!"MaxInternalCount", i64 50}
!9 = !{!"MaxFunctionCount", i64 50}
!10 = !{!"NumCounts", i64 5}
!11 = !{!"NumFunctions", i64 1}
!12 = !{!"IsPartialProfile", i64 0}
!13 = !{!"PartialProfileRatio", double 0.000000e+00}
!14 = !{!"DetailedSummary", !15}
!15 = !{!16, !17, !18, !19, !20, !21, !22, !23, !24, !25, !26, !27, !28, !29, !30, !31}
!16 = !{i32 10000, i64 50, i32 3}
!17 = !{i32 100000, i64 50, i32 3}
!18 = !{i32 200000, i64 50, i32 3}
!19 = !{i32 300000, i64 50, i32 3}
!20 = !{i32 400000, i64 50, i32 3}
!21 = !{i32 500000, i64 50, i32 3}
!22 = !{i32 600000, i64 50, i32 3}
!23 = !{i32 700000, i64 50, i32 3}
!24 = !{i32 800000, i64 50, i32 3}
!25 = !{i32 900000, i64 50, i32 3}
!26 = !{i32 950000, i64 50, i32 3}
!27 = !{i32 990000, i64 50, i32 3}
!28 = !{i32 999000, i64 50, i32 3}
!29 = !{i32 999900, i64 50, i32 3}
!30 = !{i32 999990, i64 50, i32 3}
!31 = !{i32 999999, i64 50, i32 3}
!32 = !{!"clang version 23.0.0git (https://github.com/llvm/llvm-project.git ca5bc14df1310bf92e4286a69df3a80065f0663a)"}
!33 = !{!34, !34, i64 0}
!34 = !{!"int", !35, i64 0}
!35 = !{!"omnipotent char", !36, i64 0}
!36 = !{!"Simple C/C++ TBAA"}
!37 = !{!"function_entry_count", i64 50}
!38 = !{!35, !35, i64 0}
!39 = !{!"branch_weights", i32 0, i32 50}
!40 = !{!41, !41, i64 0}
!41 = !{!"short", !35, i64 0}
!42 = !{!43, !43, i64 0}
!43 = !{!"long", !35, i64 0}
!44 = !{!"branch_weights", i32 50, i32 0}
```

#### Detailed Issue Analysis

The `chr` pass duplicates the region into a hot specialized path and a cold fallback path, then guards entry with a merged condition so biased branches/selects on the hot path can be constant-folded. The entry block containing the guard branch is shown below:

Image

The branch with condition on `%i7` evaluates to false because:
- Variable `%i2` evaluates to false, since `@b` is false
- Variable `%i3` evaluates to true, since the `xor` between true and `%i2` (false) is true
- Variable `%i4` evaluates to true, since it is the freeze of `%i3`
- Variable `%i5` evaluates to true, since the `select` with condition true selects `%i4`
- Variable `%i6` evaluates to false, since it is the freeze of `%i` and `%i` is loaded from `@d` which is false
- Variable `%i7` evaluates to false, since the `select` chooses `%i6` (because `%i5` is true)

Therefore, the branch condition `%i7` is false, and execution goes to `%split_nonchr`.

Notably, the `chr` code changes cause further passes to constant-fold what is set to be the specialized path while leaving the cold path unchanged. However, since the cold path according to `chr` is actually the only path executed, this results in subobtimal optimization decisions.

### Reproduction

We provide here the command to replicate this finding starting from the given IR.

```bash
opt before.ll -passes='require,chr' -S -o after.ll
```

#### BPI and BPI analysis
The BPI and BFI of the IR after the application of `chr` are the following:

```bash
opt -passes='print' after.ll
```

```
edge %bb -> %bb.split probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
edge %bb -> %bb.split.nonchr probability is 0x00000000 / 0x80000000 = 0.00%
edge %bb.split -> %bb8 probability is 0x00000000 / 0x80000000 = 0.00%
edge %bb.split -> %bb4 probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
edge %bb4 -> %bb9 probability is 0x00000000 / 0x80000000 = 0.00%
edge %bb4 -> %bb8 probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
edge %bb8 -> %bb11 probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
edge %bb9 -> %bb11 probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
edge %bb.split.nonchr -> %bb8.nonchr probability is 0x00000000 / 0x80000000 = 0.00%
edge %bb.split.nonchr -> %bb4.nonchr probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
edge %bb8.nonchr -> %bb11 probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
edge %bb4.nonchr -> %bb9.nonchr probability is 0x00000000 / 0x80000000 = 0.00%
edge %bb4.nonchr -> %bb8.nonchr probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
edge %bb9.nonchr -> %bb11 probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
```

```bash
opt -passes='print' after.ll
```

```
- bb: float = 1.0, int = 18014398509481984, count = 50
- bb.split: float = 1.0, int = 18014398501093376, count = 50
- bb4: float = 1.0, int = 18014398492704768, count = 50
- bb8: float = 1.0, int = 18014398492704768, count = 50
- bb9: float = 0.00000000046566, int = 8388607, count = 0
- bb.split.nonchr: float = 0.00000000046566, int = 8388608, count = 0
- bb8.nonchr: float = 0.00000000046566, int = 8388607, count = 0
- bb4.nonchr: float = 0.00000000046566, int = 8388607, count = 0
- bb9.nonchr: float = 0.0000000000000000002, int = 1, count = 0
- bb11: float = 1.0, int = 18014398509481984, count = 50
```

The profile captured by instrumenting the IR resulting after the application of the `chr` pass yields the following branch probabilities:
```
edge %bb -> %.split probability is 0x00000000 / 0x80000000 = 0.00%
edge %bb -> %.split.nonchr probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
edge %.split -> %bb13 probability is 0x40000000 / 0x80000000 = 50.00%
edge %.split -> %bb9 probability is 0x40000000 / 0x80000000 = 50.00%
edge %bb9 -> %bb14 probability is 0x30000000 / 0x80000000 = 37.50%
edge %bb9 -> %bb13 probability is 0x50000000 / 0x80000000 = 62.50%
edge %bb13 -> %bb24 probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
edge %bb14 -> %bb24 probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
edge %.split.nonchr -> %bb17 probability is 0x00000000 / 0x80000000 = 0.00%
edge %.split.nonchr -> %bb18 probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
edge %bb17 -> %bb24 probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
edge %bb18 -> %bb22 probability is 0x00000000 / 0x80000000 = 0.00%
edge %bb18 -> %bb17 probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
edge %bb22 -> %bb24 probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
```

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.