<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/69864>69864</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            Possible optimization for conditional jumps
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            new issue
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          DMaroo
      </td>
    </tr>
</table>

<pre>
    The following C code,

```c
int id(int n) {
    return n;
}

int inc(int n) {
    return n + 1;
}

int dec(int n) {
    return n - 1;
}

int parity(int n) {
    return n & 0x1;
}

int half(int n) {
 return n >> 1;
}

int execute(int op, int val) {
    int result = -1;
    switch (op) {
        case 78:
            result = id(val);
            break;
        case 67:
            result = inc(val);
            break;
        case 42:
            result = dec(val);
            break;
        case -10:
            result = parity(val);
            break;
        case 32:
            result = half(val);
        default:
            break;
    }

 return result;
}
```

compiles down to the following assembly when using clang 17.0.1 on x86-64 Linux (copied as obtained from [godbolt.org](https://godbolt.org/)).

```assembly
id: # @id
        mov     eax, edi
 ret
inc:                                    # @inc
        lea     eax, [rdi + 1]
        ret
dec:                                    # @dec
        lea     eax, [rdi - 1]
        ret
parity: # @parity
        mov     eax, edi
        and eax, 1
        ret
half:                                   # @half
 mov     eax, edi
        sar     eax
        ret
execute: # @execute
        mov     eax, -1
 cmp     edi, 41
        jle     .LBB5_1
        cmp     edi, 42
 je      .LBB5_8
        cmp     edi, 67
        je      .LBB5_7
 cmp     edi, 78
        je      .LBB5_10
.LBB5_11:
 ret
.LBB5_1:
        cmp     edi, -10
        je      .LBB5_9
 cmp     edi, 32
        jne     .LBB5_11
        sar esi
.LBB5_10:
        mov     eax, esi
        ret
.LBB5_8:
 dec     esi
        mov     eax, esi
        ret
.LBB5_7:
 inc     esi
        mov     eax, esi
        ret
.LBB5_9:
 and     esi, 1
        mov     eax, esi
 ret
```

Here, the concerning chunk is the compare and jump instructions in the `execute` function. They are as follows.

```assembly
cmp     edi, 41
jle     .LBB5_1
cmp edi, 42
je      .LBB5_8
```

This has 2 `cmp` instructions, which really aren't necessary. We can achieve the same effect with just one `cmp` instruction as follows.

```assembly
cmp     edi, 42
jl .LBB5_1
je      .LBB5_8
```

This optimization would work a long as there is no branch target in this chunk (which is the case in this example). In fact, GCC (13.2) does perform this optimization for the example code.

Also, the choice of arbitrary numbers in the example is irrelevant as long as they are not uniform enough to be used for a lookup table, so cases with uniformly increasing values in the switch-case would be optimized to a lookup table based dispatch, and we would not be able to observe this behavior there.

Just for reference, here is the assembly generated by GCC 13.2 on x86-64 Linux.

```assembly
id:
 mov     eax, edi
        ret
inc:
        lea     eax, [rdi+1]
 ret
dec:
        lea     eax, [rdi-1]
 ret
parity:
        mov     eax, edi
        and     eax, 1
 ret
half:
        mov     eax, edi
        sar     eax
 ret
execute:
        cmp     edi, 42
        je      .L8
 jle     .L17
        lea     eax, [rsi+1]
        cmp     edi, 67
 je      .L7
        cmp     edi, 78
        mov     eax, -1
 cmove   eax, esi
        ret
.L17:
        mov     eax, esi
 and     eax, 1
        cmp     edi, -10
        je      .L7
 sar     esi
        mov     eax, -1
        cmp     edi, 32
 cmove   eax, esi
        ret
.L8:
        lea     eax, [rsi-1]
.L7:
        ret
```
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJysWMuO8jwSfRqzKYESBwgsWDTN33PRP9IsPmmWI8cpiLsdG9kONPP0IzsXIIRLfzNRqyF2zqmLy-UTmLVipxBXZLYms82IVa7QZrX5BzNajzKdn1a_CoStllIfhdrBO3CdI6HvJNqQ6K35P4_qP17fC-VA5IQu_BdF6BJIuq6nAAAMusooUCRpBkm6uaQLcMWf4oHQNcSPWHJ8gWX8mGPPjHCnV5yZQ_T9kKpgcjtMdGZJ_iDJH489wm_klcOGSe8JfQf_7cDkjXt-3KCtpAOSbGB8Jvaz9igcL4DQhWfpQf3FmUVIFyR5ux6vI-9ow2LX5q_42yszyL5uZgL5PH1KHkrh99in9Bl7XSK_xz6Oo2f0XfX8noXkqf9NTd2hz3HLKukGSW7N9mqtrcra2kBFttv-EsR1uRcSLeT6qMBpcFf9g1mLZSZPcCxQQWX9GJdM7SBOJ9EkBq3gezEfz6fwp1DVt69NrvcCc2AWdOaYUJjD1ugSyGy903mmpZtosyOzDaGLwrm99eHSD0I_Lqf9wJLQ5WSwc7V-NbssJ8kbEJoAmUYiv85dqQ_hE9m333mYi3O62k3KPf6FqzWh-LUNiezSBpmtTS6afjfbXD_bmfWl_COzHvCC2fEjo02Bn9PVDLyWsuZiKm_n4jt2Qp2_FF3jRwDUXM_MW2a6-WHrbcs9h9mOPIpz3AbDy309ngs_Pu0F-SkxfE7-XK9n_-5N9rG0mf6sMQ1o8RA0T3sGr7DpsJfp4hEobnZ9cxefW0yXtDacfvPp2Rm3VMOGlsPeJbQHUlc5jG9XGK248uu2d_frxIo75dDmvCPIkdfIPuSHlBeHoVD_H8rlmdJvs5bydqvd5e0IBxv-X9F4PRj6PNeKo1GhqReV-gJhm_FyzwwGBz6rcg9CWWcq7oRWFoQKD5F5t6nmEWwrFaYn8KvAEwS0bQ4S-0oPv7PnBveaf7a3vwa312ACfhXCQsEsUB8CL_fe_csAPe2xELwAg0zKEIwiNHWgkKO1zJwm8C8EzhQwXgg8YEiIZSUCbrfIHRyFK-Czsg60wmE7_2N-2rjldWp-mAe9d6IU_2HBoaOuZA5Hbb6AgdTh-PeRGfSFoTRkhilegGNmh66uA2Gb0iF0USetrSGvh9pH8JuVe4n-OIe_Kdgy7nwQf3l_97g4mVAvZ3ONFvZottqUNe7Kva02gbkhC282V5l7k1Z3pV1owRH0FpjJhDPMnEBVZYamK-CWR1gQxqDEA1POh3wRel3JSjuolAh-odLVrvBKKUOorBc32oR86a9qD45lMuwvq0MKbF0KDVqefJ8wyIKQOjBZYedOLe7HIW_1SmTYJgBzb_DaCGTMW8-F3TPHC2_T79dji_ZOZwjhUadBZxZNqFRhIcOCHUSdT3OdxL_7ovUhGdyiQcVDNG0ReEc7TbhDhYY5zCE7hbX0C9lXhC_rtxcP_55qe0EQEbq-EEQ9-fUCfjyE7nTUz5XTxXzcp21k089Ib_XQgBB6TaU017mLtKLi3Ifj9GnObC_nw0Y7lXO2lj4E9BXOffmmD_jaiRvfvs7ePVfvrN2wrw9UUhtkt2xPFMP4saVOWf0g7NtfCAZX8aLyvdt9zK3QGOWrJF8mSzbCVTxfpstpOo2TUbHKo222yKN5vEj4gsZpPsu320WSMJ4kcZTSkVjRiCZxRGk0jZIkmUyXETKMlovZIsI0p17Dl0zIiZSH0r8hjoS1Fa7my8V8OpIsQ2nDz2KUKjxCmCSUktlmZFYeM86qnSXTSArr7JnFCSdx9U9trfCd8ubE4Vrlwt8xGbSQHVVGrnrvrcIVVTbhuiT0wzM3H-O90Z_oz7qP4I8l9CP4-98AAAD__x81RIA">