[ProfInfo][JumpThreading] updatePredecessorProfileMetadata may switch hotness for dead code
- 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).
#### 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
Assessment
This issue has not been assessed yet.