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

    <tr>
        <th>Summary</th>
        <td>
            [GlobalISel] Hash collisions / hitting EmptyKey or TombstoneKey on map key in RegisterBankInfo
        </td>
    </tr>

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

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

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

<pre>
    We experience sporadic failures in [RegisterBankInfo::getOperandsMapping](https://github.com/llvm/llvm-project/blob/203757776826cfd164c537048ec90f5ada50cae2/llvm/lib/CodeGen/RegisterBankInfo.cpp#L334). These failures seem to be triggered by

`hash_code Hash = hash_combine_range(Begin, End);`

hitting the value of EmptyKey or TombstoneKey in the DenseMap member [MapOfOperandsMappings](https://github.com/llvm/llvm-project/blob/203757776826cfd164c537048ec90f5ada50cae2/llvm/include/llvm/CodeGen/RegisterBankInfo.h#L413). We still use LLVM 13, but the coding seems to have remained the same until to date.

We also see failures in [RegisterBankInfo::ValueMapping::verify](https://github.com/llvm/llvm-project/blob/203757776826cfd164c537048ec90f5ada50cae2/llvm/lib/CodeGen/RegisterBankInfo.cpp#L555) that seem to be triggered by hash collisions from

`hash_code Hash = hash_combine_range(Begin, End);`

To us it seems that this coding is not protected against these problems and therefore failures can happen randomly.

Already posted the problem in the Forum, but got no answer there:
https://discourse.llvm.org/t/registerbankinfo-getoperandsmapping-not-protected-against-hash-collisions-emptykey-tombstonekey/77659
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzMlU-P2zYTxj8NfRnYkEn9Peiwu47yBu8uArSL7DEYiSOJNUUKJLWpv31B2c46C6RoDy16kaAhOeLM73lI9F4Nhqhm2T3LDhtcwmhdPaHrcGnJkdu0Vp7qFwL6fSanyHQEfrYOpeqgR6UXRx6UAZbd_0KD8oHcPZrjJ9NbJu6YuBsofJ7JoZH-CedZmYFlB8bLMYTZxym8YbwZVBiXdtfZifFG69frazs7-xt1gfGm1bZlvOGJKLKiKPKS510v93naZaJI0pK6KukzlJglHRK_yaPiugcr6SMZxpv3-9x188y4eBQiZbzawfNInt6K80QTBAstQXBqGMiRhPbEkgNL7i7PPBnRj187Kwn-h34EJg5wCU2tMvTVoRmI8fKeBmUYf4APRjJeMXHP8uQ216hCUGaAMBK8ol4IbA8fpjmc_k8nsA6e7dT6YA3Fb2XWiQcynp5whommllyk8YTz5_5d5_2_3XplOr1Iegv8CYUxMkj3YmXwQuCD0hoWT_D4-OUJ4sADtEtYC-6sjE2KbHyEM-IrgaMJlSG5zvA4ESwmKB3HJQba3bb5hQC1tzHDX9Pxl8jiquA18kpO9af_qpqzLGO8gjBi-JmEV4VCZ7VWXlnjoXd2-qd0_Wxh8aDClVncVxiVv6JUHowNMDsbqAskAQdUxq-4PcV4q-NCNCtfR711N-g6NDDiPJOBqHg76dMPvO-0I5QnmK0PF4VcUl491Fi3TFeNDTaAsYDGfyN3_l-ke3boD6yl8p1dnKddBLSzbmC8iYTdBUyL5qhMb7cDBXvx43TW0dbYsP1e8fZS8TY2ePuGZUvR_Uc6bcPV-kc6Md4URZ5VG1kLWYkKN1Tvi32S7nNepZux5qIqsCwq0VGe9WUpRFHkiHm5T6o0yYuNqnnC00Ts0_1elEm1ExmvUIo2y4qKl13L0iQ6Sn-vbKO8X6guM55UG40tab9eHZwb-gbrIOM83iSuXvXeLoNnaaKVD_4tS1BBr3fOR21b1J9-Jc2yw1lgN2pkvIHrafjTA9AamHCG4_ksfG-GzeJ0_be9uRbiGW_WQv8IAAD__9NjWa8">