Remove the default branch of a switch #73446

DianQK · 2023-11-26T12:33:35Z

When the default branch is the last case, we can transform that branch into a concrete branch with an unreachable default branch.

define i64 @src(i64 %0) {
  %2 = urem i64 %0, 4
  switch i64 %2, label %5 [
    i64 1, label %3
    i64 2, label %3
    i64 3, label %4
  ]

3:                                                ; preds = %1, %1
  br label %5

4:                                                ; preds = %1
  br label %5

5:                                                ; preds = %1, %4, %3
  %.0 = phi i64 [ 2, %4 ], [ 1, %3 ], [ 0, %1 ]
  ret i64 %.0
}

define i64 @tgt(i64 %0) {
  %2 = urem i64 %0, 4
  switch i64 %2, label %unreachable [
    i64 0, label %5
    i64 1, label %3
    i64 2, label %3
    i64 3, label %4
  ]

unreachable:                              ; preds = %1
  unreachable

3:                                                ; preds = %1, %1
  br label %5

4:                                                ; preds = %1
  br label %5

5:                                                ; preds = %1, %4, %3
  %.0 = phi i64 [ 2, %4 ], [ 1, %3 ], [ 0, %1 ]
  ret i64 %.0
}

alive: https://alive2.llvm.org/ce/z/Y-PGXv
from: rust-lang/rust#118306

@src

…th that case (#76669) When the default branch is the last case, we can transform that branch into a concrete branch with an unreachable default branch. ```llvm target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-unknown-linux-gnu" define i64 @src(i64 %0) { %2 = urem i64 %0, 4 switch i64 %2, label %5 [ i64 1, label %3 i64 2, label %3 i64 3, label %4 ] 3: ; preds = %1, %1 br label %5 4: ; preds = %1 br label %5 5: ; preds = %1, %4, %3 %.0 = phi i64 [ 2, %4 ], [ 1, %3 ], [ 0, %1 ] ret i64 %.0 } define i64 @tgt(i64 %0) { %2 = urem i64 %0, 4 switch i64 %2, label %unreachable [ i64 0, label %5 i64 1, label %3 i64 2, label %3 i64 3, label %4 ] unreachable: ; preds = %1 unreachable 3: ; preds = %1, %1 br label %5 4: ; preds = %1 br label %5 5: ; preds = %1, %4, %3 %.0 = phi i64 [ 2, %4 ], [ 1, %3 ], [ 0, %1 ] ret i64 %.0 } ``` Alive2: https://alive2.llvm.org/ce/z/Y-PGXv After transform to a lookup table, I believe `tgt` is better code. The final instructions are as follows: ```asm src: # @src and edi, 3 lea rax, [rdi - 1] cmp rax, 2 ja .LBB0_1 mov rax, qword ptr [8*rdi + .Lswitch.table.src-8] ret .LBB0_1: xor eax, eax ret tgt: # @tgt and edi, 3 mov rax, qword ptr [8*rdi + .Lswitch.table.tgt] ret .Lswitch.table.src: .quad 1 # 0x1 .quad 1 # 0x1 .quad 2 # 0x2 .Lswitch.table.tgt: .quad 0 # 0x0 .quad 1 # 0x1 .quad 1 # 0x1 .quad 2 # 0x2 ``` Godbolt: https://llvm.godbolt.org/z/borME8znd Closes #73446.

DianQK · 2024-01-18T13:38:08Z

Reopen as #76669 and #77831 were reverted.

cc @qiongsiwu

…tchs, r=<try> Replace the default branch with an unreachable branch If it is the last variant Fixes rust-lang#119520. LLVM currently has limited ability to eliminate dead branches in switches, even with the patch of llvm/llvm-project#73446. The main reasons are as follows: - Additional costs are required to calculate the range of values, and there exist many scenarios that cannot be analyzed accurately. - Matching values by bitwise calculation cannot handle odd branches, nor can it handle values like `-1, 0, 1`. See [SimplifyCFG.cpp#L5424](https://github.com/llvm/llvm-project/blob/llvmorg-17.0.6/llvm/lib/Transforms/Utils/SimplifyCFG.cpp#L5424) and https://llvm.godbolt.org/z/qYMqhvMa8 - The current range information is continuous, even if the metadata for the range is submitted. See [ConstantRange.cpp#L1869-L1870](https://github.com/llvm/llvm-project/blob/llvmorg-17.0.6/llvm/lib/IR/ConstantRange.cpp#L1869-L1870). - The metadata of the range may be lost in passes such as SROA. See https://rust.godbolt.org/z/e7f87vKMK. Although we can make improvements, I think it would be more appropriate to put this issue to rustc first. After all, we can easily know the possible values. Note that we've currently found a slow compilation problem in the presence of unreachable branches. See llvm/llvm-project#78578. r? compiler

…tchs, r=oli-obk Replace the default branch with an unreachable branch If it is the last variant Fixes rust-lang#119520. LLVM currently has limited ability to eliminate dead branches in switches, even with the patch of llvm/llvm-project#73446. The main reasons are as follows: - Additional costs are required to calculate the range of values, and there exist many scenarios that cannot be analyzed accurately. - Matching values by bitwise calculation cannot handle odd branches, nor can it handle values like `-1, 0, 1`. See [SimplifyCFG.cpp#L5424](https://github.com/llvm/llvm-project/blob/llvmorg-17.0.6/llvm/lib/Transforms/Utils/SimplifyCFG.cpp#L5424) and https://llvm.godbolt.org/z/qYMqhvMa8 - The current range information is continuous, even if the metadata for the range is submitted. See [ConstantRange.cpp#L1869-L1870](https://github.com/llvm/llvm-project/blob/llvmorg-17.0.6/llvm/lib/IR/ConstantRange.cpp#L1869-L1870). - The metadata of the range may be lost in passes such as SROA. See https://rust.godbolt.org/z/e7f87vKMK. Although we can make improvements, I think it would be more appropriate to put this issue to rustc first. After all, we can easily know the possible values. Note that we've currently found a slow compilation problem in the presence of unreachable branches. See llvm/llvm-project#78578. r? compiler

…witchs, r=oli-obk Replace the default branch with an unreachable branch If it is the last variant Fixes rust-lang#119520. LLVM currently has limited ability to eliminate dead branches in switches, even with the patch of llvm/llvm-project#73446. The main reasons are as follows: - Additional costs are required to calculate the range of values, and there exist many scenarios that cannot be analyzed accurately. - Matching values by bitwise calculation cannot handle odd branches, nor can it handle values like `-1, 0, 1`. See [SimplifyCFG.cpp#L5424](https://github.com/llvm/llvm-project/blob/llvmorg-17.0.6/llvm/lib/Transforms/Utils/SimplifyCFG.cpp#L5424) and https://llvm.godbolt.org/z/qYMqhvMa8 - The current range information is continuous, even if the metadata for the range is submitted. See [ConstantRange.cpp#L1869-L1870](https://github.com/llvm/llvm-project/blob/llvmorg-17.0.6/llvm/lib/IR/ConstantRange.cpp#L1869-L1870). - The metadata of the range may be lost in passes such as SROA. See https://rust.godbolt.org/z/e7f87vKMK. Although we can make improvements, I think it would be more appropriate to put this issue to rustc first. After all, we can easily know the possible values. Note that we've currently found a slow compilation problem in the presence of unreachable branches. See llvm/llvm-project#78578. r? compiler

…tchs, r=oli-obk Replace the default branch with an unreachable branch If it is the last variant Fixes rust-lang#119520. LLVM currently has limited ability to eliminate dead branches in switches, even with the patch of llvm/llvm-project#73446. The main reasons are as follows: - Additional costs are required to calculate the range of values, and there exist many scenarios that cannot be analyzed accurately. - Matching values by bitwise calculation cannot handle odd branches, nor can it handle values like `-1, 0, 1`. See [SimplifyCFG.cpp#L5424](https://github.com/llvm/llvm-project/blob/llvmorg-17.0.6/llvm/lib/Transforms/Utils/SimplifyCFG.cpp#L5424) and https://llvm.godbolt.org/z/qYMqhvMa8 - The current range information is continuous, even if the metadata for the range is submitted. See [ConstantRange.cpp#L1869-L1870](https://github.com/llvm/llvm-project/blob/llvmorg-17.0.6/llvm/lib/IR/ConstantRange.cpp#L1869-L1870). - The metadata of the range may be lost in passes such as SROA. See https://rust.godbolt.org/z/e7f87vKMK. Although we can make improvements, I think it would be more appropriate to put this issue to rustc first. After all, we can easily know the possible values. Note that we've currently found a slow compilation problem in the presence of unreachable branches. See llvm/llvm-project#78578. r? compiler

…tchs, r=<try> Replace the default branch with an unreachable branch If it is the last variant Fixes rust-lang#119520. LLVM currently has limited ability to eliminate dead branches in switches, even with the patch of llvm/llvm-project#73446. The main reasons are as follows: - Additional costs are required to calculate the range of values, and there exist many scenarios that cannot be analyzed accurately. - Matching values by bitwise calculation cannot handle odd branches, nor can it handle values like `-1, 0, 1`. See [SimplifyCFG.cpp#L5424](https://github.com/llvm/llvm-project/blob/llvmorg-17.0.6/llvm/lib/Transforms/Utils/SimplifyCFG.cpp#L5424) and https://llvm.godbolt.org/z/qYMqhvMa8 - The current range information is continuous, even if the metadata for the range is submitted. See [ConstantRange.cpp#L1869-L1870](https://github.com/llvm/llvm-project/blob/llvmorg-17.0.6/llvm/lib/IR/ConstantRange.cpp#L1869-L1870). - The metadata of the range may be lost in passes such as SROA. See https://rust.godbolt.org/z/e7f87vKMK. Although we can make improvements, I think it would be more appropriate to put this issue to rustc first. After all, we can easily know the possible values. Note that we've currently found a slow compilation problem in the presence of unreachable branches. See llvm/llvm-project#78578. r? compiler

…tchs, r=<try> Replace the default branch with an unreachable branch If it is the last variant Fixes rust-lang#119520. Fixes rust-lang#110097. LLVM currently has limited ability to eliminate dead branches in switches, even with the patch of llvm/llvm-project#73446. The main reasons are as follows: - Additional costs are required to calculate the range of values, and there exist many scenarios that cannot be analyzed accurately. - Matching values by bitwise calculation cannot handle odd branches, nor can it handle values like `-1, 0, 1`. See [SimplifyCFG.cpp#L5424](https://github.com/llvm/llvm-project/blob/llvmorg-17.0.6/llvm/lib/Transforms/Utils/SimplifyCFG.cpp#L5424) and https://llvm.godbolt.org/z/qYMqhvMa8 - The current range information is continuous, even if the metadata for the range is submitted. See [ConstantRange.cpp#L1869-L1870](https://github.com/llvm/llvm-project/blob/llvmorg-17.0.6/llvm/lib/IR/ConstantRange.cpp#L1869-L1870). - The metadata of the range may be lost in passes such as SROA. See https://rust.godbolt.org/z/e7f87vKMK. Although we can make improvements, I think it would be more appropriate to put this issue to rustc first. After all, we can easily know the possible values. Note that we've currently found a slow compilation problem in the presence of unreachable branches. See llvm/llvm-project#78578. r? compiler

…tchs, r=oli-obk Replace the default branch with an unreachable branch If it is the last variant Fixes rust-lang#119520. Fixes rust-lang#110097. LLVM currently has limited ability to eliminate dead branches in switches, even with the patch of llvm/llvm-project#73446. The main reasons are as follows: - Additional costs are required to calculate the range of values, and there exist many scenarios that cannot be analyzed accurately. - Matching values by bitwise calculation cannot handle odd branches, nor can it handle values like `-1, 0, 1`. See [SimplifyCFG.cpp#L5424](https://github.com/llvm/llvm-project/blob/llvmorg-17.0.6/llvm/lib/Transforms/Utils/SimplifyCFG.cpp#L5424) and https://llvm.godbolt.org/z/qYMqhvMa8 - The current range information is continuous, even if the metadata for the range is submitted. See [ConstantRange.cpp#L1869-L1870](https://github.com/llvm/llvm-project/blob/llvmorg-17.0.6/llvm/lib/IR/ConstantRange.cpp#L1869-L1870). - The metadata of the range may be lost in passes such as SROA. See https://rust.godbolt.org/z/e7f87vKMK. Although we can make improvements, I think it would be more appropriate to put this issue to rustc first. After all, we can easily know the possible values. Note that we've currently found a slow compilation problem in the presence of unreachable branches. See llvm/llvm-project#78578. r? compiler

…li-obk Replace the default branch with an unreachable branch If it is the last variant Fixes #119520. Fixes #110097. LLVM currently has limited ability to eliminate dead branches in switches, even with the patch of llvm/llvm-project#73446. The main reasons are as follows: - Additional costs are required to calculate the range of values, and there exist many scenarios that cannot be analyzed accurately. - Matching values by bitwise calculation cannot handle odd branches, nor can it handle values like `-1, 0, 1`. See [SimplifyCFG.cpp#L5424](https://github.com/llvm/llvm-project/blob/llvmorg-17.0.6/llvm/lib/Transforms/Utils/SimplifyCFG.cpp#L5424) and https://llvm.godbolt.org/z/qYMqhvMa8 - The current range information is continuous, even if the metadata for the range is submitted. See [ConstantRange.cpp#L1869-L1870](https://github.com/llvm/llvm-project/blob/llvmorg-17.0.6/llvm/lib/IR/ConstantRange.cpp#L1869-L1870). - The metadata of the range may be lost in passes such as SROA. See https://rust.godbolt.org/z/e7f87vKMK. Although we can make improvements, I think it would be more appropriate to put this issue to rustc first. After all, we can easily know the possible values. Note that we've currently found a slow compilation problem in the presence of unreachable branches. See llvm/llvm-project#78578. r? compiler

DianQK · 2024-05-25T02:40:33Z

Context: #78582 should have unlocked this PR.
Relanded: 64ed699 and 7dc2f66.

cc @qiongsiwu

DianQK added llvm:optimizations missed-optimization labels Nov 26, 2023

DianQK mentioned this issue Nov 26, 2023

Missed optimization: _ => 0 generates worse code than 0 => 0, _ => unreachable!() rust-lang/rust#118306

Closed

DianQK self-assigned this Nov 27, 2023

DianQK mentioned this issue Jan 1, 2024

[SimplifyCFG] When only one case value is missing, replace default with that case #76669

Merged

DianQK closed this as completed in #76669 Jan 3, 2024

EugeneZelenko added llvm:transforms and removed llvm:optimizations labels Jan 3, 2024

DianQK mentioned this issue Jan 16, 2024

[SimplifyCFG] eliminateDeadSwitchCases does not eliminate dead branches. #78281

Open

DianQK reopened this Jan 18, 2024

DianQK mentioned this issue Jan 23, 2024

Replace the default branch with an unreachable branch If it is the last variant rust-lang/rust#120268

Merged

DianQK closed this as completed in 64ed699 May 25, 2024

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Remove the default branch of a switch #73446

Remove the default branch of a switch #73446

DianQK commented Nov 26, 2023

DianQK commented Jan 18, 2024 •

edited

Loading

DianQK commented May 25, 2024 •

edited

Loading

Remove the default branch of a switch #73446

Remove the default branch of a switch #73446

Comments

DianQK commented Nov 26, 2023

DianQK commented Jan 18, 2024 • edited Loading

DianQK commented May 25, 2024 • edited Loading

DianQK commented Jan 18, 2024 •

edited

Loading

DianQK commented May 25, 2024 •

edited

Loading