llvm-project.git/llvm/test/Transforms/JumpThreading/select.ll, branch users/nico/python-2

Revert "[JumpThreading] Thread over BB with only an unconditional branch" (#88907)

2024-04-16T14:52:19+00:00

Reverts llvm/llvm-project#86312

[JumpThreading] Thread over BB with only an unconditional branch (#86312)

2024-04-16T10:51:03+00:00

Fixes #76609
This patch does:
- relax the phis constraint in `CanRedirectPredsOfEmptyBBToSucc`
- guarantee the BB has multiple different predecessors to redirect, so
that we can handle the case without phis in BB. Without this change and
phi constraint, we may redirect the CommonPred.

The motivation is consistent with JumpThreading. We always want the
branch to jump more direct to the destination, without passing the
middle block. In this way, we can expose more other optimization
opportunities.

An obivous example proposed by @dtcxzyw is like:
```llvm
define i32 @test(...) {
entry:
   br i1 %c, label %do.end, label %if.then

if.then:                                          ; preds = %entry
   %call2 = call i32 @dummy()
   %tobool3.not = icmp eq i32 %call2, 0
   br i1 %tobool3.not, label %do.end, label %return

do.end:                                           ; preds = %entry, %if.then
   br label %return

return:                                           ; preds = %if.then, %do.end
   %retval.0 = phi i32 [ 0, %do.end ], [ %call2, %if.then ]
   ret i32 %retval.0
}
```
`entry` can directly jump to return, without passing `do.end`, and then
the if-else pattern can be simplified further:
```llvm
define i32 @test(...) {
entry:
   br i1 %c, label %return, label %if.then

if.then:                                          ; preds = %entry
   %call2 = call i32 @dummy()
   br label %return

return:                                           ; preds = %if.then
   %retval.0 = phi i32 [ 0, %entry ], [ %call2, %if.then ]
   ret i32 %retval.0
}
```

[JT][CT] Preserve exisiting BPI/BFI during JumpThreading

2023-02-16T09:08:34+00:00

Currently, JT creates and updates local instances of BPI\BFI. As a result global ones have to be invalidated if JT made any changes.
In fact, JT doesn't use any information from BPI/BFI for the sake of the transformation itself. It only creates BPI/BFI to keep them up to date. But since it updates local copies (besides cases when it updates profile metadata) it just waste of time.

Current patch is a rework of D124439. D124439 makes one step and replaces local copies with global ones retrieved through AnalysisPassManager. Here we do one more step and don't create BPI/BFI if the only reason of creation is to keep BPI/BFI up to date. Overall logic is the following. If there is cached BPI/BFI then update it along the transformations. If there is no existing BPI/BFI, then create it only if it is required to update profile metadata.

Please note if BPI/BFI exists on exit from JT (either cached or created) it is always up to date and no reason to invalidate it.

Reviewed By: mkazantsev

Differential Revision: https://reviews.llvm.org/D136827

Revert "[JT][CT] Preserve exisiting BPI/BFI during JumpThreading"

2023-01-27T08:35:32+00:00

This reverts commit 26e7cb24cb5dfa560683064d37f560558f00aa67.

[JT][CT] Preserve exisiting BPI/BFI during JumpThreading

2023-01-27T08:00:16+00:00

Currently, JT creates and updates local instances of BPI\BFI. As a result global ones have to be invalidated if JT made any changes.
In fact, JT doesn't use any information from BPI/BFI for the sake of the transformation itself. It only creates BPI/BFI to keep them up to date. But since it updates local copies (besides cases when it updates profile metadata) it just waste of time.

Current patch is a rework of D124439. D124439 makes one step and replaces local copies with global ones retrieved through AnalysisPassManager. Here we do one more step and don't create BPI/BFI if the only reason of creation is to keep BPI/BFI up to date. Overall logic is the following. If there is cached BPI/BFI then update it along the transformations. If there is no existing BPI/BFI, then create it only if it is required to update profile metadata.

Please note if BPI/BFI exists on exit from JT (either cached or created) it is always up to date and no reason to invalidate it.

Reviewed By: mkazantsev

Differential Revision: https://reviews.llvm.org/D136827

[JumpThreading] Preserve profile metadata during select unfolding, take 2

2023-01-16T12:04:23+00:00

Jump threading can replace select and unconditional branch with
conditional branch, but when doing so loses profile information.

This destructive transform can eventually lead to a performance
degradation due to folding of branches in
shouldFoldCondBranchesToCommonDestination as branch probabilities
are no longer known.

The first version was reverted due to assert caused by i32 overflow,
fixed in this version.

Patch by Roman Paukner!

Differential Revision: https://reviews.llvm.org/D138132
Reviewed By: mkazantsev

Revert "[JumpThreading] Preserve profile metadata during select unfolding"

2023-01-10T10:54:50+00:00

This reverts commit 957952dbf2f34ed552e8e1f8c35eed17eee2ea38.

Addition in the newly added code can overflow.  As a result, the
constructor of `BranchProbability()` can trigger an assertion. See
the discussion on https://reviews.llvm.org/D138132 for more details.

[JumpThreading] Fix test to require asserts

2023-01-09T22:51:08+00:00

[JumpThreading] Preserve profile metadata during select unfolding

2023-01-09T09:14:58+00:00

Jump threading can replace select and unconditional branch with
conditional branch, but when doing so loses profile information.

This destructive transform can eventually lead to a performance
degradation due to folding of branches in
shouldFoldCondBranchesToCommonDestination as branch probabilities
are no longer known.

Patch by Roman Paukner!

Differential Revision: https://reviews.llvm.org/D138132
Reviewed By: mkazantsev

JumpThreading: Convert tests to -passes

2022-11-27T16:19:28+00:00