llvm / llvm/llvm-project

[ProfInfo][SimpleLoopUnswitch] Missing update of branch probabilities for hoisted conditional branch

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

Description

### Hoisted Block Terminator Has Incorrect Branch Probabilities After `simple-loop-unswitch`

When applying `simple-loop-unswitch` to the provided IR module, the hoisting of a loop-invariant conditional branch instruction does not update the associated branch weights to reflect the new execution frequency. This behavior seems to be introduced by the function [unswitchNontrivialInvariants](https://github.com/llvm/llvm-project/blob/main/llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp#L2403) where the branch is moved without any update of profile metadata, which in realty depends on the condition itself which is executed a lower amount of times.

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

```llvm
@d = global i8 0

; Function Attrs: inlinehint
define i32 @main() local_unnamed_addr #0 !prof !29 {
bb:
br label %bb1

bb1: ; preds = %._crit_edge1, %bb
%i = phi i32 [ 0, %bb ], [ %i17, %._crit_edge1 ]
%.mask = and i32 %i, 1
%i2 = icmp eq i32 %.mask, 0
br i1 %i2, label %.critedge.preheader, label %bb3, !prof !30

bb3: ; preds = %bb1
%i4 = srem i32 1, %i
%i5 = icmp eq i32 %i4, 0
br i1 %i5, label %._crit_edge1, label %.critedge.preheader, !prof !31

.critedge.preheader: ; preds = %bb3, %bb1
br label %.critedge

.critedge: ; preds = %bb14, %.critedge.preheader
%i6 = phi i16 [ %i15, %bb14 ], [ 0, %.critedge.preheader ]
%i7 = icmp eq i32 %i, 0
br label %bb8

bb8: ; preds = %bb11, %.critedge
%i9 = phi i32 [ 1, %.critedge ], [ %i12, %bb11 ]
%i10 = load volatile i8, ptr @d, align 1
br i1 %i7, label %bb11, label %.loopexit, !prof !32

bb11: ; preds = %bb8
%i12 = add i32 %i9, 1
%i13 = icmp eq i32 %i12, 6
br i1 %i13, label %._crit_edge, label %bb8, !prof !33, !llvm.loop !34

._crit_edge: ; preds = %bb11
br label %bb14, !llvm.loop !34

.loopexit: ; preds = %bb8
br label %bb14

bb14: ; preds = %.loopexit, %._crit_edge
%i15 = add i16 %i6, 1
%i16 = icmp eq i16 %i15, 6
br i1 %i16, label %._crit_edge1.loopexit, label %.critedge, !prof !37, !llvm.loop !38

._crit_edge1.loopexit: ; preds = %bb14
br label %._crit_edge1

._crit_edge1: ; preds = %._crit_edge1.loopexit, %bb3
%i17 = add i32 %i, -1
%i18 = icmp eq i32 %i17, -14
br i1 %i18, label %bb19, label %bb1, !prof !39

bb19: ; preds = %._crit_edge1
ret i32 0
}

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 6500}
!4 = !{!"MaxCount", i64 3900}
!5 = !{!"MaxInternalCount", i64 3900}
!6 = !{!"MaxFunctionCount", i64 300}
!7 = !{!"NumCounts", i64 7}
!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 3900, i32 1}
!14 = !{i32 100000, i64 3900, i32 1}
!15 = !{i32 200000, i64 3900, i32 1}
!16 = !{i32 300000, i64 3900, i32 1}
!17 = !{i32 400000, i64 3900, i32 1}
!18 = !{i32 500000, i64 3900, i32 1}
!19 = !{i32 600000, i64 3900, i32 1}
!20 = !{i32 700000, i64 1500, i32 2}
!21 = !{i32 800000, i64 1500, i32 2}
!22 = !{i32 900000, i64 350, i32 4}
!23 = !{i32 950000, i64 300, i32 5}
!24 = !{i32 990000, i64 50, i32 7}
!25 = !{i32 999000, i64 50, i32 7}
!26 = !{i32 999900, i64 50, i32 7}
!27 = !{i32 999990, i64 50, i32 7}
!28 = !{i32 999999, i64 50, i32 7}
!29 = !{!"function_entry_count", i64 50}
!30 = !{!"branch_weights", i32 350, i32 350}
!31 = !{!"branch_weights", i32 50, i32 300}
!32 = !{!"branch_weights", i32 1500, i32 3600}
!33 = !{!"branch_weights", i32 300, i32 1200}
!34 = distinct !{!34, !35, !36}
!35 = !{!"llvm.loop.mustprogress"}
!36 = !{!"llvm.loop.unroll.disable"}
!37 = !{!"branch_weights", i32 650, i32 3250}
!38 = distinct !{!38, !35, !36}
!39 = !{!"branch_weights", i32 50, i32 650}
```

#### Detailed Issue Analysis

The provided IR module consist of three nested loops (we name them L* for clarity):
- L1: the outermost loop with header `bb1`, having `%i` has its induction variable (14 iterations)
- L2: the middle loop with header `.critedge` (6 iterations)
- L3: the innermost loop with header `bb8` (5 iterations)

Below, we provide the CFG of the IR before (first image) and after (second image) the application of the pass.

Before entering L3, a condition in block `bb8` checks whether variable `%i` is equal to zero, resulting in L3's body to be executed only in the first iteration of the L1.

Image

Since this condition does not depend on L3's computations, `simple-loop-unswitch` hoists the conditional branch into the L2's header, without updating the branch counts. However, such counts are no longer accurate after the transformation, as the branch is executed a lower amount of times as part of the optimization. This reflects in incorrect BPI on the edges involved.

Image

### Reproduction
We provide the command to replicate this finding starting from the given IR module.

```bash
opt before.ll -passes='simple-loop-unswitch' -S -o after.ll
```
#### BPI Analysis

Analyzing the branch probabilities of `after.ll`, we can see that the block where the branch is moved into (`.critedge`) has a true probability of 29.41% and a false probability of 70.59%, which are exactly the probabilities of the same branch before applying the pass (incorrect after the IR updates).

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

```
[...]
edge %bb8 -> %bb11 probability is 0x25a5a5a6 / 0x80000000 = 29.41%
edge %bb8 -> %.loopexit probability is 0x5a5a5a5a / 0x80000000 = 70.59%
[...]
```

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

```
[...]
edge %.critedge -> %.critedge.split.us probability is 0x25a5a5a6 / 0x80000000 = 29.41%
edge %.critedge -> %.critedge.split probability is 0x5a5a5a5a / 0x80000000 = 70.59%
[...]
```

From profiles obtained by instrumenting the IR after the application of `simple-loop-unswitch`, the accurate resulting branch probabilities are: 7.69% for the true branch, and 92.31% for the false branch.

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.