[llvm-bugs] [Bug 50405] New: Missed switch-to-lookup-table transformation for switch with "holes"

[via llvm-bugs]

https://bugs.llvm.org/show_bug.cgi?id=50405

            Bug ID: 50405
           Summary: Missed switch-to-lookup-table transformation for
                    switch with "holes"
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: Scalar Optimizations
          Assignee: unassignedbugs at nondot.org
          Reporter: hans at chromium.org
                CC: llvm-bugs at lists.llvm.org

Consider the code below, which is written in a way that should be perfect for
transforming to a lookup table:

$ cat /tmp/a.c
const char *g();

const char *f(int x) {
    char *ret;

    switch (x) {
        case 0:  ret = "0";  break;
        case 1:  ret = "1";  break;
        case 3:  ret = "3";  break;
        case 5:  ret = "5";  break;
        case 6:  ret = "6";  break;
        case 8:  ret = "8";  break;
        case 10: ret = "10"; break;
        case 11: ret = "11"; break;
        case 12: ret = "12"; break;
        case 15: ret = "15"; break;
        case 17: ret = "17"; break;
        case 19: ret = "19"; break;
        case 22: ret = "22"; break;
        case 24: ret = "24"; break;
        case 27: ret = "27"; break;
        case 29: ret = "29"; break;
        case 31: ret = "31"; break;
        case 32: ret = "32"; break;
        case 33: ret = "33"; break;
        case 35: ret = "35"; break;

        default: ret = 0;
    }

    if (!ret) { return g(); }

    return ret;
}

However, LLVM will lower the switch with a jump table:

$ bin/clang -target i686-unknown-linux -O2 -S -o - /tmp/a.c
        .text
        .file   "a.c"
        .globl  f                               # -- Begin function f
        .p2align        4, 0x90
        .type   f, at function
f:                                      # @f
# %bb.0:                                # %entry
        movl    4(%esp), %ecx
        cmpl    $35, %ecx
        ja      .LBB0_20
# %bb.1:                                # %entry
        movl    $.L.str, %eax
        jmpl    *.LJTI0_0(,%ecx,4)
.LBB0_21:                               # %sw.bb1
        movl    $.L.str.1, %eax
.LBB0_22:                               # %cleanup
        retl
.LBB0_20:                               # %if.then
        jmp     g                               # TAILCALL
.LBB0_2:                                # %sw.bb2
        movl    $.L.str.2, %eax
        retl
.LBB0_3:                                # %sw.bb3
        movl    $.L.str.3, %eax
        retl
.LBB0_4:                                # %sw.bb4
        movl    $.L.str.4, %eax
        retl
[...]





If the holes are plugged in the switch, the generated code is the expected:

$ cat /tmp/a.c
const char *g();

const char *f(int x) {
    char *ret;

    switch (x) {
        case 0:  ret = "0";  break;
        case 1:  ret = "1";  break;
        case 2:  ret = "1";  break;
        case 3:  ret = "3";  break;
        case 4:  ret = "3";  break;
        case 5:  ret = "5";  break;
        case 6:  ret = "6";  break;
        case 7:  ret = "6";  break;
        case 8:  ret = "8";  break;
        case 9:  ret = "8";  break;
        case 10: ret = "10"; break;
        case 11: ret = "11"; break;
        case 12: ret = "12"; break;
        case 13: ret = "12"; break;
        case 14: ret = "12"; break;
        case 15: ret = "15"; break;
        case 16: ret = "15"; break;
        case 17: ret = "17"; break;
        case 18: ret = "17"; break;
        case 19: ret = "19"; break;
        case 20: ret = "19"; break;
        case 21: ret = "19"; break;
        case 22: ret = "22"; break;
        case 23: ret = "22"; break;
        case 24: ret = "24"; break;
        case 25: ret = "24"; break;
        case 26: ret = "24"; break;
        case 27: ret = "27"; break;
        case 28: ret = "27"; break;
        case 29: ret = "29"; break;
        case 30: ret = "29"; break;
        case 31: ret = "31"; break;
        case 32: ret = "32"; break;
        case 33: ret = "33"; break;
        case 34: ret = "33"; break;
        case 35: ret = "35"; break;

        default: ret = 0;
    }

    if (!ret) { return g(); }

    return ret;
}

$ bin/clang -target i686-unknown-linux -O2 -S -o - /tmp/a.c
        .text
        .file   "a.c"
        .globl  f                               # -- Begin function f
        .p2align        4, 0x90
        .type   f, at function
f:                                      # @f
# %bb.0:                                # %entry
        movl    4(%esp), %eax
        cmpl    $36, %eax
        jae     .LBB0_2
# %bb.1:                                # %switch.lookup
        movl    .Lswitch.table.f(,%eax,4), %eax
        retl
.LBB0_2:                                # %if.then
        jmp     g                               # TAILCALL
.Lfunc_end0:
        .size   f, .Lfunc_end0-f
                                        # -- End function
[...]

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20210519/649a89b1/attachment.html>