llvm / llvm/llvm-project

[ProfInfo][JumpThreading] updatePredecessorProfileMetadata may switch hotness for dead code

Open
#198,283 0 comments 0 reactions 0 assignees View on GitHub
llvm:optimizations PGO
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

In the provided IR module, upon the application of `jump-threading`, no code transformation are performed but profile metadata gets attached to a dead basic block making it and its successors hot. The attachment of synthetic metadata is done by [`updatePredecessorProfileMetadata`](https://github.com/llvm/llvm-project/blob/main/llvm/lib/Transforms/Scalar/JumpThreading.cpp#L152).

We tested this behavior using LLVM commit [`5e814e26dd72d14ac1118a647210294d38c8d01e`](https://github.com/llvm/llvm-project/commit/5e814e26dd72d14ac1118a647210294d38c8d01e).

```llvm
@a = local_unnamed_addr global i8 0
@b = local_unnamed_addr global i8 0
@h = local_unnamed_addr global i8 0
@c = local_unnamed_addr global i16 0
@d = local_unnamed_addr global i16 0
@n = local_unnamed_addr global i16 0
@g = local_unnamed_addr global i32 0
@j = local_unnamed_addr global i32 0
@m = local_unnamed_addr global i32 0
@o = local_unnamed_addr global i32 0
@s = local_unnamed_addr global i32 0
@t = local_unnamed_addr global i32 0

; Function Attrs: inlinehint minsize
define i32 @main() local_unnamed_addr #0 !prof !29 {
bb:
%i = load i32, ptr @t, align 4
br label %bb1

bb1: ; preds = %bb73, %bb
%i2 = phi i32 [ %i10, %bb73 ], [ 0, %bb ]
%i3 = phi i16 [ 0, %bb73 ], [ 1, %bb ]
%i4 = phi i32 [ %i11, %bb73 ], [ %i, %bb ]
%i5 = phi i8 [ %i74, %bb73 ], [ 0, %bb ]
%i6 = icmp samesign ult i8 %i5, 6
br i1 %i6, label %bb7, label %common.ret, !prof !30

bb7: ; preds = %bb1
%i8 = icmp eq i32 %i4, 0
br label %bb9

bb9: ; preds = %._crit_edge3, %bb7
%i10 = phi i32 [ 0, %bb7 ], [ %i16, %._crit_edge3 ]
%i11 = phi i32 [ 0, %bb7 ], [ %i19, %._crit_edge3 ]
%i12 = phi i32 [ 1, %bb7 ], [ 0, %._crit_edge3 ]
%i13 = phi i16 [ 1, %bb7 ], [ %i30, %._crit_edge3 ]
%i14 = phi i1 [ %i8, %bb7 ], [ false, %._crit_edge3 ]
br i1 %i14, label %bb73, label %bb15, !prof !31

bb15: ; preds = %bb23, %bb9
%i16 = phi i32 [ 0, %bb9 ], [ %i24, %bb23 ]
%i17 = phi i1 [ true, %bb9 ], [ false, %bb23 ]
br label %bb18

bb18: ; preds = %bb20, %bb15
%i19 = phi i32 [ 1, %bb20 ], [ 0, %bb15 ]
br i1 %i17, label %bb20, label %._crit_edge2

bb20: ; preds = %bb18
%i21 = load i32, ptr @g, align 4
%i22 = icmp eq i32 %i21, 0
br i1 %i22, label %bb18, label %bb23

bb23: ; preds = %bb26, %bb20
%i24 = phi i32 [ 1, %bb20 ], [ 0, %bb26 ]
%i25 = icmp eq i32 %i2, 0
br i1 %i25, label %bb15, label %bb26

bb26: ; preds = %bb23
%i27 = load i16, ptr @c, align 2
%i28 = icmp eq i16 %i27, 0
br i1 %i28, label %bb23, label %common.ret

common.ret: ; preds = %bb34, %bb26, %bb1
ret i32 0

._crit_edge2: ; preds = %bb31, %bb18
%i29 = phi i1 [ false, %bb18 ], [ true, %bb31 ]
%i30 = phi i16 [ %i13, %bb18 ], [ 0, %bb31 ]
br i1 %i29, label %._crit_edge3, label %bb31

bb31: ; preds = %bb37, %._crit_edge2
%i32 = phi i16 [ %i38, %bb37 ], [ %i30, %._crit_edge2 ]
%i33 = icmp eq i16 %i32, 0
br i1 %i33, label %._crit_edge2, label %bb34

bb34: ; preds = %bb31
%i35 = load i32, ptr @j, align 4
%i36 = icmp eq i32 %i35, 0
br i1 %i36, label %bb37, label %common.ret

bb37: ; preds = %bb34
%i38 = add i16 %i32, 1
br label %bb31

._crit_edge3: ; preds = %._crit_edge1, %._crit_edge2
%i39 = phi i16 [ 1, %._crit_edge1 ], [ %i3, %._crit_edge2 ]
%i40 = phi i32 [ 0, %._crit_edge1 ], [ %i12, %._crit_edge2 ]
%i41 = icmp eq i16 %i39, 0
br i1 %i41, label %bb9, label %._crit_edge1

._crit_edge1: ; preds = %._crit_edge, %._crit_edge3
%i42 = phi i32 [ 1, %._crit_edge ], [ %i40, %._crit_edge3 ]
%i43 = phi i32 [ %i47, %._crit_edge ], [ 0, %._crit_edge3 ]
%i44 = phi i32 [ 0, %._crit_edge ], [ 1, %._crit_edge3 ]
%i45 = icmp eq i32 %i42, 0
br i1 %i45, label %._crit_edge3, label %._crit_edge

._crit_edge: ; preds = %bb72, %bb69, %bb52, %._crit_edge1
%i46 = phi i32 [ 0, %bb52 ], [ 0, %bb72 ], [ 0, %bb69 ], [ %i44, %._crit_edge1 ]
%i47 = phi i32 [ 0, %bb52 ], [ 0, %bb72 ], [ 0, %bb69 ], [ 1, %._crit_edge1 ]
%i48 = icmp eq i32 %i46, 0
br i1 %i48, label %._crit_edge1, label %bb49

bb49: ; preds = %._crit_edge
%i50 = load i32, ptr @o, align 4
%i51 = icmp eq i32 %i50, 0
br i1 %i51, label %bb69, label %bb52

bb52: ; preds = %bb49
%i53 = icmp eq i32 %i43, 0
br i1 %i53, label %bb54, label %._crit_edge

bb54: ; preds = %bb52
%i55 = load i16, ptr @d, align 2
%i56 = icmp eq i16 %i55, 0
br i1 %i56, label %bb61, label %bb57

bb57: ; preds = %bb54
%i58 = sext i16 %i55 to i32
%i59 = srem i32 1, %i58
%i60 = trunc nuw nsw i32 %i59 to i16
br label %bb61

bb61: ; preds = %bb57, %bb54
%i62 = phi i16 [ %i60, %bb57 ], [ 0, %bb54 ]
store i16 %i62, ptr @n, align 2
%i63 = load i8, ptr @b, align 1
%i64 = icmp ne i8 %i63, 0
%i65 = load i8, ptr @a, align 1
%i66 = icmp eq i8 %i65, 0
%i67 = select i1 %i64, i1 %i66, i1 false
br i1 %i67, label %bb68, label %bb69

bb68: ; preds = %bb61
store i32 0, ptr @m, align 4
br label %bb69

bb69: ; preds = %bb68, %bb61, %bb49
%i70 = load i8, ptr @h, align 1
%i71 = icmp eq i8 %i70, 0
br i1 %i71, label %._crit_edge, label %bb72

bb72: ; preds = %bb69
store i32 0, ptr @s, align 4
br label %._crit_edge

bb73: ; preds = %bb9
%i74 = add nuw nsw i8 %i5, 1
br label %bb1
}

attributes #0 = { inlinehint minsize }

!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 650}
!4 = !{!"MaxCount", i64 300}
!5 = !{!"MaxInternalCount", i64 300}
!6 = !{!"MaxFunctionCount", i64 0}
!7 = !{!"NumCounts", i64 19}
!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 300, i32 2}
!14 = !{i32 100000, i64 300, i32 2}
!15 = !{i32 200000, i64 300, i32 2}
!16 = !{i32 300000, i64 300, i32 2}
!17 = !{i32 400000, i64 300, i32 2}
!18 = !{i32 500000, i64 300, i32 2}
!19 = !{i32 600000, i64 300, i32 2}
!20 = !{i32 700000, i64 300, i32 2}
!21 = !{i32 800000, i64 300, i32 2}
!22 = !{i32 900000, i64 300, i32 2}
!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 300, i32 50}
!31 = !{!"branch_weights", i32 300, i32 0}
```

#### Reproduction
The following command reproduces the issue:
```bash
opt before.ll -passes='jump-threading' -S -o after.ll
```
Applying the pass to the provided IR does not transform its structure. The only change is the addition of profile metadata to the terminator instruction of the block `._crit_edge3`. This block lies on a path that is traversed zero times according to the existing profile information. However, the addition of this synthetic profile metadata incorrectly causes the block, and its successors, to become hot. This behavior is shown below by the CFGs of the IR before the application of the pass (first image) and after the application of the pass (second image).


Image




Image

#### BFI Analysis
Analyzing the BFI dump before and after the application of the pass we can see how the frequency of `._crit_edge3` and its successors change:
```bash
opt before.ll -passes='print' --disable-output
```
```
Printing analysis results of BFI for function 'main':
block-frequency-info: main
( . . . )
- ._crit_edge3: float = 0.000000003725, int = 9586175, count = 0
- ._crit_edge1: float = 0.00000011547, int = 297171440, count = 0
- ._crit_edge: float = 0.0000035797, int = 9212314648, count = 0
- bb49: float = 0.0000034678, int = 8924429815, count = 0
- bb52: float = 0.0000021674, int = 5577768634, count = 0
- bb54: float = 0.00000081277, int = 2091663238, count = 0
- bb57: float = 0.00000050798, int = 1307289523, count = 0
- bb61: float = 0.00000081277, int = 2091663238, count = 0
- bb68: float = 0.00000040639, int = 1045831619, count = 0
- bb69: float = 0.0000021132, int = 5438324418, count = 0
- bb72: float = 0.0000013208, int = 3398952761, count = 0
- bb73: float = 6.0, int = 15440913003333924, count = 300
```
```bash
opt after.ll -passes='print' --disable-output
```
```
Printing analysis results of BFI for function 'main':
block-frequency-info: main
( . . . )
- ._crit_edge3: float = 0.24998, int = 18159675925272, count = 12
- ._crit_edge1: float = 7.9993, int = 581109629338128, count = 400
- ._crit_edge: float = 247.98, int = 18014398509481984, count = 12399
- bb49: float = 240.23, int = 17451448556060672, count = 12011
- bb52: float = 150.14, int = 10907155347537920, count = 7507
- bb54: float = 56.304, int = 4090183255326720, count = 2815
- bb57: float = 35.19, int = 2556364534579200, count = 1759
- bb61: float = 56.304, int = 4090183255326720, count = 2815
- bb68: float = 28.152, int = 2045091627663360, count = 1408
- bb69: float = 146.39, int = 10634476463849472, count = 7320
- bb72: float = 91.494, int = 6646547789905920, count = 4575
- bb73: float = 6.0, int = 435868824700908, count = 300
```

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.