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

    <tr>
        <th>Summary</th>
        <td>
            [GVN] Missed partial redundancy elimination opportunity of load through select instruction
        </td>
    </tr>

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

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

    <tr>
      <th>Reporter</th>
      <td>
          skachkov-sc
      </td>
    </tr>
</table>

<pre>
    ### Reproduction
```c
int test(int i, int N, int *A)
{
    if (i != (N - 1) && A[i] > A[i+1])
        ++i;
    return A[i];
}
```
Compiled with: `-O3 -S -emit-llvm`

The latest load can be replaced with select between already loaded values, so we will have 2 loads on the execution path instead of 3. Pseudocode:
```c
int test(int i, int N, int *A)
{
    int tmp1 = A[i];
    bool cond = false;
    if (i != (N - 1)) {
        int tmp2 = A[i+1];
        cond = tmp1 > tmp2;
    }
    return cond ? tmp2 : tmp1;
}
```

However, GVN pass can't process such case through select instruction. LLVM IR (-O3 -S -emit-llvm):
```llvm
entry:
  %sub = add nsw i32 %N, -1
  %cmp.not = icmp eq i32 %sub, %i
  br i1 %cmp.not, label %if.end, label %land.lhs.true

land.lhs.true:                                    ; preds = %entry
  %idxprom = sext i32 %i to i64
  %arrayidx = getelementptr inbounds i32, ptr %A, i64 %idxprom
  %0 = load i32, ptr %arrayidx, align 4, !tbaa !5
  %add = add nsw i32 %i, 1
  %idxprom1 = sext i32 %add to i64
  %arrayidx2 = getelementptr inbounds i32, ptr %A, i64 %idxprom1
  %1 = load i32, ptr %arrayidx2, align 4, !tbaa !5
  %cmp3 = icmp sgt i32 %0, %1
  %spec.select = select i1 %cmp3, i32 %add, i32 %i
  br label %if.end

if.end:                                           ; preds = %land.lhs.true, %entry
  %i.addr.0 = phi i32 [ %i, %entry ], [ %spec.select, %land.lhs.true ]
  %idxprom4 = sext i32 %i.addr.0 to i64
  %arrayidx5 = getelementptr inbounds i32, ptr %A, i64 %idxprom4
  %2 = load i32, ptr %arrayidx5, align 4, !tbaa !5
  ret i32 %2
```

There is already some support of pointer-select in GVN pass (https://reviews.llvm.org/D118143), so I assume more generalized solution (select between indices) is required. This issue affects the performance of SPEC2017 520.omnetpp_r benchmark (the example is minimized from rather hot cMessageHeap::shiftup method), and looks like GCC is able to do PRE here.
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJytVttu2zgQ_Rr5ZWBBoiQ7fvCDc2sLNN2iLfpa0OLI4oYSVZKKm_36HVK2IsebJkBXEGxe5nZmDjnaavG4jlg2vPAFO6NFXzqp2yi5jpJNtEiGtxzmsnXg0LqIXfihjNgV-MGn4yBim03EVgft5eUwAHpkBV6LftIou_bjTzCHlIRpvKAXNlFxKaOC9rKbw4RdprQwGoTDQ-v0yiib2DfoetOORsa9aHn9DMswvdJNJxUK2EtXR9kGaGf-VwbzrzDHRrq5Ug_NKD38fqsRFPcJAKW5gJK3sEVy3SleHkyBRYWlo3W3R2yBK4NcPAYFEnngqkfr02U17JFUlIKaPyCwIGJBt-DID_7CsveVgI6TVdlaR3ZAV5DF8NliL3SpBVLk_3-pvGrTpeALdZZQL7HVWkGpWxFEKq4snuy_XOxQ76mziUM2cXiofPZMcvR5iO8m6J2IjQWfsOKgdnv0sgn6r3Jk-H2v9_iAxuft3fdPVA5rfeUjtnRAB6ZEmtu-rGnRItXO6H430sDXzQxHKoaPH7_fwYcvPh_nVKPcnNUybIQlbJ15HAX8EShsvw2p4EJAa_cgM-aXQ4Hn6USwbLq41S4IS5oA_jwKkw0vTiN5VNgakOlEze8rvkUVpKoYW3GypHgrYlXbmHDiNG-nG9lYw989VBLKKdIxGHhTDLifsEjxi3LehG2Lv9wRiASnQS7yiSg3hj-SfJDdoaOCNGSucwSw3eq-JS-k7cH4NdLYhLOxyCeOJvaSYCgc_FO1oyO_xJXctZAPSU3dlnP_X0zDEuK_yhYOaHqOND2D6hVfBMv-CO3Uf_oaXPY2vESj7Il6djfiSA7Mmzq1HZbx4egMuIdTdCRkFmIe8zCZTfn7nK4TUh5W3sbGl0h5yuwBxRlRY4rPxANpuloOcRaXY62POhA63NVxb5KBg9SJtyB9RpL8_Dwc3b_IlOKPmDK1yF5jSvEGptBNfYyd_eYyphZsEKQd-6rVDdL123XaON8dO03dBM18vH-fLm26dmvnOuuvUXZLr8EHiXsb-2s21mZHS9dpepHmWehUoUd_AFLtyUejyfEOWzSE5B9q5VaroUGT3WdNX7ZClr7Nr3yoBn_2kvgTw7eappLsIfCqIg0ben2HptKm4W2JHsLXzzdXLEmXULAk1k2Lrut-GDLelnXDzb13OHwi8KZTIRuNbGUToqr87WjokwEN1HTpl3fUn_gO3yPvPPBsY2tZub6DBl2txQEpcYwqqO8tKHmP8O7qKiR5S-aJQULD5y834HMfz3CdLuhJV2mynIl1JlbZis-cdArXRGJKt_-IuyOYFE7HjZNcUQ4EEYsQPgIqCrXlIXU61K1vpXv0yAOHXu6gs96o9WkJd_TJ1W_jkm5qdjv00fA3J5L-Hc7Qbcg31eK2uCgWq1m9TouqWpVVLhK2YOxC5MsyL5dFJcqLFEWVz8L9YT2YiLEW90PJaEzAZnLNEsbShOVplhdJEVfLVZFUaZ6ssqpYsTzKE2y4VCOtZmYdQtr2O0ubSlr3xLkZ0YsOBobcefu8p7KYtb3nZX2vH-a2nAX36xD-v3rXXYw">