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

    <tr>
        <th>Summary</th>
        <td>
            Optimization opportunity: ((((a) > (b)) - ((a) < (b))) < 0) -> ((a) < (b))
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
      </td>
    </tr>

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

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

<pre>
    When trying to make a binary search function used in ZFS run faster, I noticed that Clang misses a high level optimization opportunity, which is `((((a) > (b)) - ((a) < (b))) < 0) -> ((a) < (b))`.

Other variations of this include:

* `((((a) > (b)) - ((a) < (b))) <= 0) -> ((a) <= (b))`
* `((((a) > (b)) - ((a) < (b))) == -1) -> ((a) < (b))`
* `((((a) > (b)) - ((a) < (b))) == 1) -> ((a) > (b))`
* `((((a) > (b)) - ((a) < (b))) == 0) -> ((a) == (b))`
* `((((a) > (b)) - ((a) < (b))) > 0) -> ((a) > (b))`.
* `((((a) > (b)) - ((a) < (b))) >= 0) -> ((a) >= (b))`.

* `((((a) >= (b)) - ((a) <= (b))) < 0) -> ((a) < (b))`
* `((((a) >= (b)) - ((a) <= (b))) <= 0) -> ((a) <= (b))`
* `((((a) >= (b)) - ((a) <= (b))) == -1) -> ((a) < (b))`
* `((((a) >= (b)) - ((a) <= (b))) == 1) -> ((a) > (b))`
* `((((a) >= (b)) - ((a) <= (b))) == 0) -> ((a) == (b))`
* `((((a) >= (b)) - ((a) <= (b))) > 0) -> ((a) > (b))`.
* `((((a) >= (b)) - ((a) <= (b))) >= 0) -> ((a) >= (b))`.

`(((a) > (b)) - ((a) < (b)))` is a trick to generate -1, 0 or 1 when comparing two integers (signed or unsigned) and when comparators using this trick are inlined into the caller, the above transformations become applicable.

Getting back to binary search, the idea to make binary search faster was to eliminate a control hazard from the binary search function by making the loop body branchless. The following site explains the control hazard and shows to how avoid it:

https://en.algorithmica.org/hpc/data-structures/binary-search/#the-bottleneck

This site provides benchmarks that confirm that avoiding the control hazard makes binary search faster:

https://github.com/scandum/binary_search/tree/master

The comparators used in ZFS are expected to return -1, 0, or 1, so `(((a) > (b)) - ((a) < (b)))` is often used in them. Since I wanted to avoid control hazards in binary search, I wrote a macro that can be used to do C++-style inlining of comparators into the binary search function by making a different version for each. Unfortunately, LLVM/Clang reintroduced the control hazard when all of this was put together. Here is a minimal version that avoids the macro so that it is easy to see which lines correspond to which instructions:

https://gcc.godbolt.org/z/KbKc6zqjT

On amd64, if I comment out line 35 and uncomment line 36, the control hazard vanishes, but the code generation is less than ideal. If I instead uncomment line 37 instead of 36, Clang generates what I wanted in the first place, but I cannot use it because I need the compiler to inline the existing comparison function.

If I compile for rv64gc, LLVM/Clang does not generate a control hazard for any of those versions, although it still generates different code. Line 35 gives a 13 instruction loop. Line 36 gives a 16 instruction loop. Line 37 gives a 12 instruction loop.

For comparison, GCC 13.1 generates a 15-instruction loop for amd64 without any control hazards for both versions on lines 35 and 36, although it also misses this optimization opportunity.

If LLVM had an optimization pass that recognized the equivalency of the above expressions, then it would generate code corresponding to what it generated before I had done the abstraction needed to make this function useful in production.

I will switch my code to use line 36 at the expense of code generation on RISC-V, but I would be happier if LLVM/Clang implemented this optimization.
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJy8WN-P4jgS_mvCSwkUAqThgYcZutlDO6eVbub2pHs5VZwK8Y5jZ20Hhv7rT-Uk_FzmdvrolVoNJBVX1VffV64YnZNbTbSMZh-j2fMAG18au7QHNIPM5Iflv0rS4O1B6i14AxV-JUDIpEZ7AEdoRQlFo4WXRkPjKAep4d_rz2AbDQU6TzZKVrABbbwUlIMv0cNKod5CJZ0jBwil3JagaEcKTO1lJV8xrGfq2ljfaOkPvMi-lKIE6SBK4yiZH_8wShYQTV4gSuZZlCz45xAu7q3O7vVX4mDXPXfHNI1HUfwcxR_a_7_4kizs0MoQoANTgC-lA6mFanKKJh_OzaPkw2NijSbPd8PlexcRP9b3M68_HP8prN7B8x3HL-_u-A7cz-8M98s9xy9_TMtHuf1Oyi83KY_-JMkvH7yJ4mrdH5Llu_h-rMzeEMFDxfZW_w-S3FvdP054b4jgcfJ7i_P_Q4RnQfx4A4jSmLdVBG-l-Mr7_JY0WfQUyLiCGIyFMex5GBCmqtGGeWBvQGpPW7KOFwyjRM6mjW6_szfU-fmD6I110LiwAG-drU-0BFIrqcME4Q34kkCgUu38wL8wMzsCb1G7wtiq24EzEqYiwLpWUmCm6AKXn8h79pRhm9fF4NIvLHPC43BzNdqECQb26NiAlKykZlgQhNHeGgUlvqLNobCmCovdGY2yAy_fJk2gjKmB5yvILGpRKnJuBF9KgsIoZfZs56QnoG-1QqldC8elSwbWlWYfQivNHnBnZA7SX00hpfe142vJOkrWpEeotsZKX1ZS4MjYbZSsy1pEyTpHj0PnbSN8Y8lFybrNZtjjtY6SiS9pmBnvFWkSX88dfeFyhrBra3YyJ66OFmWF9qtrBz9hdCFt1f4I8faQXCXHtXB_WIzvZreVvmyykTBVlKydQJ031TGN_xzT8JYoStZVu-BFCnTF09NEyxSlbzUJz2OsAUu-sbpXCP9jkfCnM_AQQZrC02mq9iVVI_gstSDYwB51F0db9kv8eCK9JfsG9tYE9lYorOlKghoyar14A7mBVZR8jJKPQ-cPqlMlV8kUF9AcVfo_GY-Qy6IgS9rDjqzju4WxQCjKEfxTF2HIR08qjPmfPv369yhZt-8IliTnlTftu8MNT0JnQaWOkzhLtW48eLMlntZH8Dfi3sLtrZJaVqiOQZxY2AqsRcV1wEjPTxG6A-PiiLoXEG5SDoSxllxtdECtezXRrXi4MX2fpkKMtibPjPKdAF-jZP1z9rNIX3__7cvFK4cGrPJ0ysjIAjZcg4qRNI0PocBkFlpBo_s77dW0b29XiO1QS1eyuleQMVDBJKe-5zMw0gG3JMZBh_aoRrBh55wh4a2zp-MdU3Su2_r1G4mDPWN65G3LZyikdR5qhYL6eDbMSG08M5JrkJFA_roBTUcOVLVUZBn5dtMIl-mbdKHbd1uUY551dLzYFTYdjrxIYKLdpdOtuCFfbsjxi-tpO7zt-8YC6kNLP-Oo51aAF5UvTbMtOQ3npVJncJwkweCP4FNXyq3chXfi8eScTmHH6I3Sk1F61-jpZJTcGp2jsTb2DDGO-6fVCsaT0fgsXITxbHi9TJs9sxP2klP1AYvrVsRWmfHlERvg54OKOu62jDmHC5Uz_QFB0PW9g4HrwnIBoUTeHi-fqdF1m5AlYbZavnZsot8buUNFWnRl7EcN-lZbcsdqem410sPeNCo_USJo59QNuoOSfddBerMcMiqMZRpzcLnpOIuZ8xZbSJnfbRMOk0hI-_xspWgU66YO7fCW1LBnhrm99KKE6tAG5k3QUdcSAH2nlJq0o7alX0rfaPjH5vNq-OtJj23CGUGJdS3Jch-60ImsakXcDQKiV8UaDfLlJF9MFjig5TidTyfpfDZdDMpluhhnRZxOxHyRzTAbj-fpdCYWNMufxPRpTAO5TOJkEs_G8ziOF_FiRJM4oyyZpU_pLJ3TPJrGVKFUI6V2FXfSgXSuoWWaPC3igcKMlOuPtuySjYZZs3XRNFbSeXd6zEuvaPnLvcOnyQf4aw6cBo1Vy--MNBxw9zGsrfmNhI-SdUiax7WQ938DAAD__9Jsuz8">