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

    <tr>
        <th>Summary</th>
        <td>
            [AMDGPU] `sort` in `AMDGPURewriteAGPRCopyMFMAImpl::eliminateSpillsOfReassignedVGPRs()` needs to have strictly weak ordering
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            backend:AMDGPU
      </td>
    </tr>

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

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

<pre>
    We ran into an `std::sort` crash at 
https://github.com/llvm/llvm-project/blob/d0da85745dac153705bf1e2c465a8f487068085e/llvm/lib/Target/AMDGPU/AMDGPURewriteAGPRCopyMFMA.cpp#L484-L494
 with input data
 
```
sort 0x561ecd3d3db0,0x561eaba91d10  25
  weight 0.000000e+00,0.000000e+00
  size 650370,662754
  slot 732,733
```

The logic for the current comparator of the sort is not strict weak order for this case, because both `cmp(a, b)` (a.slot < b.slot) and `cmp(b, a)` (b.size > a.size)  are `true`. 

However, `std::sort` requires strict weak ordering, otherwise it will access out of range / crash with memory corruption: 
https://stackoverflow.com/questions/24048022/what-causes-stdsort-to-access-address-out-of-range
https://schneide.blog/2010/11/01/bug-hunting-fun-with-stdsort/#:~:text=Ok%2C%20the%20problem%20is%20that,havoc%20inside%20std::sort.&text=The%20really%20annoying%20thing%20about,give%20you%20lot's%20of%20headaches.

Proposing to change 

</pre>
<img width="1" height="1" alt="" src="http://email.email.llvm.org/o/eJyUVE1z6yYU_TV4w0iDQJ8LL_ScOu3My7xMmrZrBNcSDQY9QPZzF_3tHZDSNE27eB6PuOJyju4Xh3uvRgOwR9UnROkV1BWUmMAgSlF1t-NLmKzbv-3vBitv-98AO26wMsFibjCqiQ8SsR6x3lsXUE2wcNxPmAeMSD-FMPvopkdEj6MK0zLkwp4RPWp9eV2y2dnfQQREj4O2A6JHSSRvq6asJBdFxRpSDacCqCjrirensm1I3ZK2gn_wqIh75m6EyNM_3N0__vK38QRXpwL0949PBzvfHo4PfS7mGVH2uWzL7HPZlYj0-KrChJWZl4AlDzxuIdKjmmx_kpLE5FtVFyAkk0wOBNHDusEH3hWyIBjTKkLxFdQ4BUxykn6A6CeSjr_fiEe9-gNwXRHWxAN1TZuqXB3aBtwwiuihYexf0SDSP0-AtR2VwCfrcJgAi8U5MAELe56548E6bE_Jk4JXHhsbsA9OiYCvwF-wdRLchlceC-4B0QMeQPDFAx5smGKnxXlGtOXJhWgXex3f8xQiYgc8JBPRDnMj3xBDRPA3xJCnbBH7AfNkRgTmDiIkuAVQTXK8pvejvcIFXGT4r1lz8HVRDvzHdJQZI8iGCdxVecAq4KvSGnMhwHtslxDL4rgZASN63MY2TcAZztbdsLDOLXNQ1iDWf5xmH7h4sRdwJ22v21B_XcBHgEf0SEtStoRSRI_XiYcsFdNnPsgYfRZstoaScSldXO0SMnvKUkgfvyYmA0pCPmg7RnZSEESPRYHokcTHsIzZtJigzJidFpPFTF4_ligYYv2fiPUBvgXE7r68IFrRQ3yQMEFaZ2cHDedkK7-5eED0MPGLFeu-8Uqux9-1I0e03qifNzoHXOtbMrkx9pZ6kjhfLT7YJdKP6rJCbnZJa5qjZg3BntIyAZdcTODzdTQenZ2tV2bEwWIxrY0k_U7umexYx3ewL5qq6xirq2Y37cuhrTjURSUI7QirJLATI9ESVVeemp3aU0KrgpC2KGnDmrxoGSkYE5XsCsJKQCWBM1c6j5qTWzfulPcL7Iualh3ZaT6A9pugDly8gIn1eZWiJKtunwRvWEaPSqKVD_6NLaigkyBvkOouDf026yrJ7f_q2U_nWa_dAK3OyvAAP89Ka__l9ASb2stf7x-fPKLtdhkNgPSxfBO_wHaH9O39LdotTu-_W8dTYeIt2Gpz2dO_AgAA__8HLvwl">