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

    <tr>
        <th>Summary</th>
        <td>
            LazyValueInfo::getConstantRangeAtUse returns incorrect range for shift instruction
        </td>
    </tr>

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

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

    <tr>
      <th>Reporter</th>
      <td>
          d-makogon
      </td>
    </tr>
</table>

<pre>
    Reproducer: https://godbolt.org/z/ez4xncxs8
Recently CorrelatedValuePropagation pass started using `LVI::getConstantRangeAtUse` which is expected to return more precise result than the previously used `LVI::getConstantRange`. This was introduced in 5c38c6a3aac48e45d8da3f30ff70942f434dfb53 by @nikic.
With this patch applied, I get a miscompilation on the above reproducer.
Unfortunately, alive2 was unable to prove that this is a miscompilation.

So I'll explain here why the transform perfomed is incorrect. So in the test function we have a loop which takes backedge exactly one time.
It executes `ashr %iv, %arg` on 1st iteration, so it actually is `ashr 127, %arg`. Let's assume that the `%arg` value is 1. Then `%shift` is equal to 63. The second time we enter the `loop` block, `shifted.iv` would be equal to `shift` which is 63. Then we'd have `%iv` equal to 128 and `%loop_cond` would be false, so we'd branch to `exit` and return `retval` which is equal to `shifted.iv` which is 63.

In the IR after CVP pass, we replace the `shifted.iv` input which was `shift` with its first operand (which is `iv`) and erases the shift instruction. Now let's analyze the return value of the function - it would still be `shifted.iv`, but it would be equal to 128 because no shift would be done.

So we get a different return value from the function.

The faulting transform is made in the following piece of code in CorrelatedValuePropagation.cpp:
```cpp
static bool processAShr(BinaryOperator *SDI, LazyValueInfo *LVI) {
  ...
 ConstantRange LRange = LVI->getConstantRangeAtUse(SDI->getOperandUse(0));
 unsigned OrigWidth = SDI->getType()->getIntegerBitWidth();
 ConstantRange NegOneOrZero =
      ConstantRange(APInt(OrigWidth, (uint64_t)-1, true), APInt(OrigWidth, 1));
  if (NegOneOrZero.contains(LRange)) {
    // ashr of -1 or 0 never changes the value, so drop the whole instruction
    ++NumAShrsRemoved;
 SDI->replaceAllUsesWith(SDI->getOperand(0));
 SDI->eraseFromParent();
    return true;
  }
```.
So it calculates the range of the first operand of the shift, which is `iv`, using `LVI::getConstantRangeAtUse`. And this function returns `empty-set` for `iv` and this is incorrect. Then we check whether `[-1, 1)` contains the operand range which is empty and we obviously get a positive result and thus erase the shift.

So I tried debugging `LVI::getConstantRangeAtUse`, but couldn't quickly figure out how to solve it.
Here is what I got:
1. When called on `iv` use in shift, it calls `LVI::getConstantRange` which returns `[-2147483648,128)`.
2. It traverses transitive uses of the value and tries to infer more precise range based on where the value is used. In the example we only have PHI users of the value, for which we call `getEdgeValueLocal` to get the value range on the edge from `loop` block to `exit` and it returns `[128,-2147483648)`.
3. It then intersects `[-2147483648,128)` with `[128,-2147483648)` and this is why we get empty set.

</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJyUV11v27gS_TXMyyCGTNmy_eAHJ9lgDQTbot22wH1ZUORI4g1NaknKjvvrL4aU7djt7d5bBA3Cj_k4c-ZwJELQrUVcs_kDmz_diSF2zq_V_U68utbZu9qp4_oT9t6pQaJn5Qa6GPvAyg3jz4w_t07VzsSJ8y3jz98Zf8bvszcr38KSFU-s2HxCiTaaIzw679GIiOqrMAN-9K4XrYjaWehFCBCi8BEVDEHbFlhVvHzdkpty02J8dDZEYeMnYVvcxC8BWVXAodOyAx0A33qUdDk68BgHb2HnPELvUeqA4DEMJkLshIXYpfW9dkMwRxgCql96Y1UxgT87HeAgAmgbMxYKtIW5LJeyEqUQcrbE2VwtlSibsmiaRbGa8WZWzlRTz0uoj8BmhdWvWk4yLt907CCS2V5E2YHoe6NRMf4IW2gxgoCdDtLtem0ySi7HLmq3p4xONRntfbGN83GwIqI5khVh9B55CnqwojZI4PSeLsdOxOxbhx_8jPby_58dbBlfGEMQG6EtdOgRDt0xxRK9sKFxfgc9-sbtCBXCSFKtZZzAZ0cwpaMYIjSDlSmXA0In9ggCjHP9WMgoXjFALeQrqhYB34Qk4jiLEPUOx8C2EfAN5RAxUN1E6DwwPtd7SprxufAtccNZmIYIOqJPadFucKAjCBkHYcyRQj0ZmPLF1fUJvGBkfBFAhDDszpAh3bg42ROTyc6UKIJ23A2dbiLtEzX_HoQh6KsynYGA0lmVMiIY0Eb0J8sEBt2rjZOvKaCqSMZQTfQ-Ud4NRkGNF7unI1cNMTojoBlfqAx2Di7bOV-f8iUIq8ZNCuAviu_KVyNMwBHA0WDthaWSJf_4ppN7sjO2H6sKj3EvzHWf3gZ9yetd5O8JuM3s2X4C0RBQj18_JrmgaA6pDYyQeMLv2qa2_RBHy9QGV0hR--kYoNE-RHA9-oQCX54jYVWR7DC-SpmhFwFDcpXMgLYh-iERegJ_uAOYE2esMMfvOaoRj8wU16S1cxvcEx8zzCFqYwjs2zQo03qIl5Pvi0_Vq1GKISBYN8Z1Pqacxdt2PuCoLko3DXq08TrExrvdVZBXBojAjRhMJI2-dL8OsBMKT73eOGPcgY70GmVKW7q8_d9fgYnse1Lg7K0q8g8tppUQRdQSaucMqZjEEDafO8_48kFb4Y8fqILRkRZsPj9tCbUX8f2YvGxt42idNJ6vgC0esk2AyWRMD640H17yL1Y-wcvX7T0rf_v5I8SXn59O2x8yh_IysYZ-ypOrwaanVsEHr9tvWsUuWb9c__PY00XGV-PC1kZs0T_omI7nvYvB64D_wPaDxQ_-X-gdGT4lSP-unzO-3Hzc2sj48hxJlr7loG2sZn9FCmFKa9EPmPJ4hJ_emd4mCbohQ--DmUhno9A2ML58GSNY3VQBIA8TkLTYNXA_BeehAIt79CA7upY7L5F0lCLlXZ8WD50z-L4d3xt-YPzhj2FHZAmfcOf2qC4Bj_CPMrIx5kvAQE_zzyr7s7KOh5I2PHu3-yiopW5rBXBqsgTpZZ0tnm4IPzl3qo4ghZEDdUtO3qdSn0TkSrjGxaxvpI0_qtjj_zFaTWBDbxSNCGexyhkki7jr4_E-YJLShppu9JKE8jRZvJsDxrcIZIfyFQ4dxg7TLTZ_yFxLXKoKONElpXPKLid-eUbIfXJ1QHD1aZTLuta7oKPen4e-HNEQsn5fUPphzoHoNSpQWA9t-78CdVJnSZprGV9E-HvQ8tUcodHt4BHcEKFzB1Lr4MweQZ9c_06jFM2VNFtsoXXxrH_TCXwjyKQwBhUNM2eESeq1vVQ608SEfxpiR_jeVZGw59PZYrYsq9mS8cdppu2ZhHwC20gyv0efnj4S_AzuQH-PpMsPR8LZazpGQ1-D_mYGTzWsRcj5HNIgebmuQxrFJzC--Pgmdr1JI5Kz5pgnmI-_b-mUv3ZNKBAJx5ceEx6UYIvxN9ViegNenMzDSHSJKBfPY1eNbmnyTG_g7Tj2k1lHxxs4E4CPV6C-g7PMcFJdNU19AWX8h0LkOeWXxq9ajgbz8YXPTRLwxLY7tS7VqlyJO1xPq8V8Va6q-equW9dlvVKqqtUKsRByIRtcclWWTTNXy6KY3-k1L3hZ8GI1LWaLcjVRMyn4XFWoZvMKK8FmBe6ENhNj9jv6FLzTIQy4roqKr-6MqNGE9InJ-fW3BuOcPjv9mi7e10Mb2KwwOsRwMRV1NLi-est_0ZLngpzFZ6wvEeSHse1u8GZ980GrYzfUE-l2jD9TEOOv-967f6OMjD-n5ALjzym__wQAAP__2Qbx_Q">