Inconsistent JumpThreading behavior in estimating branch probabilities

### Unexpected probabilities introduced by `jump-threading` within `O2` (unlike standalone use)

If `jump-threading` runs on the provided IR module, the optimization of the `select` instruction on the exit block `bb18` transforms an unconditional branch into a conditional one. This scenario happens naturally as part of `O2` optimization.

We note here that the compiler assigns equal branch probabilities (50% / 50%) to the newly created branch. However, the condition always evaluates to `false`, hence we expected a 100% probability to be set instead.

Investigating this further, we noted a difference if `jump-threading` is applied individually: we bisect and collect the IR that the `O2` pipeline has produced right before `jump-threading` kicks in, and then apply `jump-threading` with `opt` (the pass settings are identical). The profile information is now different, and coherent with what we expected for the newly created branch.

We deduce the pass is capable of computing the right (?) values, but it behaves differently when applied in the full pipeline.

A possible explanation of the issue is given below (TL DR: missed BPI recalculation/invalidation).

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

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

; Function Attrs: cold mustprogress nofree norecurse nosync nounwind willreturn memory(readwrite, argmem: none, inaccessiblemem: none, target_mem0: none, target_mem1: none) uwtable
define dso_local noundef i32 @g() local_unnamed_addr #0 !prof !38 {
bb:
%i = load i8, ptr @d, align 1, !tbaa !39
%i1 = add i8 %i, 1
store i8 %i1, ptr @d, align 1, !tbaa !39
%i2 = icmp eq i8 %i1, 0
br i1 %i2, label %bb4, label %bb3

bb3: ; preds = %bb
store i32 0, ptr @c, align 4, !tbaa !34
br label %bb14

bb4: ; preds = %bb
%i5 = load i1, ptr @b, align 2
%i6 = select i1 %i5, i32 0, i32 2
%i7 = load i32, ptr @c, align 4, !tbaa !34
%i8 = xor i32 %i7, %i6
store i32 %i8, ptr @c, align 4, !tbaa !34
%i9 = icmp eq i32 %i7, %i6
br i1 %i9, label %bb13, label %bb10

bb10: ; preds = %bb4
%i11 = load i32, ptr @f, align 4, !tbaa !34
%i12 = or i32 %i11, 9
store i32 %i12, ptr @f, align 4, !tbaa !34
br label %bb14

bb13: ; preds = %bb4
store i1 true, ptr @b, align 2
br label %bb14

bb14: ; preds = %bb13, %bb10, %bb3
br i1 %i2, label %bb18, label %bb15

bb15: ; preds = %bb14
%i16 = load i32, ptr @e, align 4, !tbaa !34
%i17 = or i32 %i16, 9
store i32 %i17, ptr @e, align 4, !tbaa !34
br label %bb18

bb18: ; preds = %bb15, %bb14
ret i32 4
}

; 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 noundef i32 @main() local_unnamed_addr #1 !prof !40 {
bb:
%i = load i8, ptr @d, align 1, !tbaa !39
%i1 = add i8 %i, 1
store i8 %i1, ptr @d, align 1, !tbaa !39
%i2 = icmp eq i8 %i1, 0
br i1 %i2, label %bb4, label %bb3, !prof !41

bb3: ; preds = %bb
store i32 0, ptr @c, align 4, !tbaa !34
br label %bb14

bb4: ; preds = %bb
%i5 = load i1, ptr @b, align 2
%i6 = select i1 %i5, i32 0, i32 2
%i7 = load i32, ptr @c, align 4, !tbaa !34
%i8 = xor i32 %i7, %i6
store i32 %i8, ptr @c, align 4, !tbaa !34
%i9 = icmp eq i32 %i7, %i6
br i1 %i9, label %bb13, label %bb10

bb10: ; preds = %bb4
%i11 = load i32, ptr @f, align 4, !tbaa !34
%i12 = or i32 %i11, 9
store i32 %i12, ptr @f, align 4, !tbaa !34
br label %bb14

bb13: ; preds = %bb4
store i1 true, ptr @b, align 2
br label %bb14

bb14: ; preds = %bb13, %bb10, %bb3
br i1 %i2, label %bb18, label %bb15, !prof !41

bb15: ; preds = %bb14
%i16 = load i32, ptr @e, align 4, !tbaa !34
%i17 = or i32 %i16, 9
store i32 %i17, ptr @e, align 4, !tbaa !34
br label %bb18

bb18: ; preds = %bb15, %bb14
%i19 = load i1, ptr @b, align 2
%i20 = select i1 %i19, i32 0, i32 2, !prof !41
store i32 %i20, ptr @a, align 4, !tbaa !34
ret i32 0
}

attributes #0 = { cold 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" }
attributes #1 = { 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, !4}
!llvm.ident = !{!33}
!llvm.errno.tbaa = !{!34}

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

### Reproduction

We provide here steps to replicate this finding starting from the given IR. Specifically, the following commands will generate two identical IR files (both obtained after the application of `jump-threading` in the two scenarios) that will differ in block frequencies and branch probabilities:

**Note:** the `O2` pipeline, when used to optimize the provided IR, applies the `jump-threading` pass **twice**. We let the first occurrence run as it does not introduce any issue, and we focus our analysis on the second application of the pass.

#### Individual application of `jump-threading`

First, we generate the IR **before** `jump-threading` runs:

```bash
opt module.ll -passes='default' --opt-bisect-limit=95 -S -o before.ll
```

Then, we apply `jump-threading` individually:

```bash
opt before.ll -passes='jump-threading' -S -o after.ll
```

In this case, the resulting IR contains the **expected branch probabilities** for the newly introduced conditional branch.

#### Application within `O2`

Now, we run the full O2 pipeline to optimize the initial IR, and stop the execution right after the `jump-threading` pass:

```bash
opt module.ll -passes='default' --opt-bisect-limit=96 -S -o after-pipeline.ll
```

The resulting IR now contains **unexpected branch probabilities (50/50)** for the same branch.

#### BFI and BPI Analysis

By analyzing the block frequencies and branch probabilities of `after.ll` and `after-pipeline.ll`:

```bash
opt -passes='print' after.ll
```
```bash
opt -passes='print' after-pipeline.ll
```
we note there is a probability mismatch between the two IRs (`after.ll` on top and `after-pipeline.ll` on bottom):

```
. . .
edge %bb18 -> %0 probability is 0x00000000 / 0x80000000 = 0.00%
edge %bb18 -> %1 probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
edge %0 -> %1 probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
```
```
. . .
edge %bb18 -> %0 probability is 0x40000000 / 0x80000000 = 50.00%
edge %bb18 -> %1 probability is 0x40000000 / 0x80000000 = 50.00%
edge %0 -> %1 probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
```

Consequently a block frequency mismatch on the last two blocks is present. (`after.ll` on top and `after-pipeline.ll` on bottom):

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

```
block-frequency-info: main
- bb: float = 1.0, int = 18014398509481984, count = 10
- bb4: float = 0.00000000046566, int = 8388608, count = 0
- bb10: float = 0.00000000023283, int = 4194304, count = 0
- bb18.thread: float = 0.00000000023283, int = 4194304, count = 0
- bb18: float = 1.0, int = 18014398501093376, count = 10
**- : float = 0.00000000069849, int = 12582911, count = 0
- : float = 1.0, int = 18014398509481984, count = 10**
```
```
block-frequency-info: main
- bb: float = 1.0, int = 18014398509481984, count = 10
- bb4: float = 0.00000000046566, int = 8388608, count = 0
- bb10: float = 0.00000000023283, int = 4194304, count = 0
- bb18.thread: float = 0.00000000023283, int = 4194304, count = 0
- bb18: float = 1.0, int = 18014398501093376, count = 10
**- : float = 0.5, int = 9007199256838144, count = 5
- : float = 1.0, int = 18014398509481984, count = 10**
```

### Tentative Issue Analysis

We tried to add the re-calculation of BPI after the `jump-threading` application in the pipeline, and this resulted is the correct values being computed. This may suggest that some transformation modifies the IR/control-flow structure in a way that invalidates BFI/BPI without properly updating or invalidating the cached analysis results used by the optimizer, leading to incorrect probabilities being set by `jump-threading`.

```bash
opt after-pipeline.ll -passes='require' -S -o after-pipeline-branch-prob.ll
```
```bash
opt -passes='print' -disable-output repro/after-pipeline-branch-prob.ll
```

```
. . .
edge %bb18 -> %0 probability is 0x40000000 / 0x80000000 = 50.00%
edge %bb18 -> %1 probability is 0x40000000 / 0x80000000 = 50.00%
edge %0 -> %1 probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
```