llvm / llvm/llvm-project

[ProfInfo][GlobalOpt] Unknown branch weights for newly created select instruction from profiled paths

Open
#198,284 1 comment 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 the `globalopt` pass, select instructions are create with `unknown` profile metadata, but the compiler should be able to accurately compute it as the instruction are created from profiled paths. The two `select` instructions are created in function [`TryToShrinkGlobalToBoolean`](https://github.com/llvm/llvm-project/blob/main/llvm/lib/Transforms/IPO/GlobalOpt.cpp#L1172) which **always** [sets unknown branch weights](https://github.com/llvm/llvm-project/blob/main/llvm/lib/Transforms/IPO/GlobalOpt.cpp#L1313).

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

```llvm
@f = global i32 -162249229
@i = global i32 7
@a = global i32 0
@c = global i16 0
@d = internal global i32 0
@e = global i32 0
@b = global i32 0

; Function Attrs: inlinehint
define i32 @main() #0 !prof !29 {
%1 = load i32, ptr @i, align 4
%2 = icmp eq i32 %1, 0
br i1 %2, label %14, label %3, !prof !30

3: ; preds = %0
%4 = load i32, ptr @f, align 4
%5 = icmp sgt i32 %4, 0
br i1 %5, label %16, label %6, !prof !30

6: ; preds = %3
%7 = load i16, ptr @c, align 2
%8 = icmp slt i16 %7, 1
br i1 %8, label %9, label %14, !prof !31

9: ; preds = %6
store i32 11, ptr @d, align 4
%10 = load i32, ptr @a, align 4
%.not = icmp eq i32 %10, 1
br i1 %.not, label %16, label %11, !prof !30

11: ; preds = %9
%12 = icmp slt i32 %1, 0
br i1 %12, label %common.ret1, label %13, !prof !30

common.ret1: ; preds = %16, %11
ret i32 0

13: ; preds = %11
store i16 0, ptr @c, align 2
br label %14

14: ; preds = %13, %6, %0
%15 = load i32, ptr @d, align 4
store i32 %15, ptr @e, align 4
br label %16

16: ; preds = %14, %9, %3
%17 = load i32, ptr @d, align 4
store i32 %17, ptr @b, align 4
br label %common.ret1
}

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 300}
!4 = !{!"MaxCount", i64 50}
!5 = !{!"MaxInternalCount", i64 50}
!6 = !{!"MaxFunctionCount", i64 50}
!7 = !{!"NumCounts", i64 6}
!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 6}
!14 = !{i32 100000, i64 50, i32 6}
!15 = !{i32 200000, i64 50, i32 6}
!16 = !{i32 300000, i64 50, i32 6}
!17 = !{i32 400000, i64 50, i32 6}
!18 = !{i32 500000, i64 50, i32 6}
!19 = !{i32 600000, i64 50, i32 6}
!20 = !{i32 700000, i64 50, i32 6}
!21 = !{i32 800000, i64 50, i32 6}
!22 = !{i32 900000, i64 50, i32 6}
!23 = !{i32 950000, i64 50, i32 6}
!24 = !{i32 990000, i64 50, i32 6}
!25 = !{i32 999000, i64 50, i32 6}
!26 = !{i32 999900, i64 50, i32 6}
!27 = !{i32 999990, i64 50, i32 6}
!28 = !{i32 999999, i64 50, i32 6}
!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='globalopt' -S -o after.ll
```

### Detailed analysis

The pass detected that `@d` is only ever stored two distinct values: 0 (its initializer) and 11 (in block `%9`). Since there are only two possible values, the actual `i32` is unnecessary, and a single bit is enough to represent it. At every load site of `@d`, the pass then reconstructs the original `i32` value using a select instruction (one for each read of the global variable).


Image


Image

The select instructions are associated with newly created `unknown` branch weights metadata, even if all the paths are completely profiled and the reconstruction of correct branch weights should be in principle feasible.

This affects badly the application of further optimization passes. Indeed, we observed a further application of the `jump-threading` pass introducing wrong branch probabilities similarly to what was happening in https://github.com/llvm/llvm-project/issues/187545 (an issues fixed in https://github.com/llvm/llvm-project/commit/fe286356ca34a530f8a6ccf0b630fc32fc69fc44). Of course, the wrong behavior of `jump-threading` is only caused by the `unknown` weights for the select instructions, which had correct weights in the previous issue.

Contributor guide

Open the contributing guide

Research direction

Start in llvm/lib/Transforms/IPO/GlobalOpt.cpp at TryToShrinkGlobalToBoolean, especially the select creation around line 1313, and reproduce the issue with opt before.ll -passes='globalopt' -S -o after.ll. Trace the profiled paths used to reconstruct the global values and verify that the resulting select instructions carry accurate branch_weights metadata instead of unknown weights.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
compilers
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
48/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.