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

    <tr>
        <th>Summary</th>
        <td>
            GVN (MemDep): Pathological or infinite behavior
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            llvm:GVN
      </td>
    </tr>

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

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

<pre>
    GVN triggers either a pathological behavior or it's going into an infinite loop in the attached repoducer.

The reason is its use of MemDepAnalysis, specifically 30-50% of the time is spent in `getNonLocalPointerDependency`, out of which most of the time is in the `std::sort` called from `SortNonLocalDepInfoCache`
The cache used keeps expanding to order of tens of thousands entries and I don't see a cap for this or a clear indication this didn't go into an infinite loop.

Reproducer:
`bin/opt --passes=gvn LoopInterchange.bc` on attached file (note: this is a large input!)

[LoopInterchange.bc.txt](https://github.com/user-attachments/files/21419390/LoopInterchange.bc.txt)
</pre>
<img width="1" height="1" alt="" src="http://email.email.llvm.org/o/eJx8U82O4zYTfBr60rBBkZY9OuigXcOLAfYbLL4Ee6elltSJzCbYrcnO2we0ZrNB_k6ExGZVdRUqiNAUEVtTfzD1ZRdWnTm3YaEYZHfj4a399PUFNNM0YRZA0hkzBEhBZ154oj4scMM5vBJn4Aykxp0FJqY4AUVlCBEojhRJERbmBBRBZ4SgGvoZB8iYeFh7zAdjO2O7n2eEjEE4AgmQCqyCwCP8D-8XTF0My5uQGPcRJGFPYxGxvIG3-9oaV5fRQqB0x4IgCaMWVnOyE-oLx8_ch-ULU1TMF0wYB4z9mznZgsmrFoTfZupnuLPoX_He9ZuTFR2M74zvhLOak4UiBAcYM9_L_U-c_6C7YHqOI38sOxembc--fJb9BvgVMQngtxTiUMxTBs4D5gc9Rtlk8CohDgIYNRMKhDjAMwwcjTsrCCIE6EOCkTPoTFIyCdAvGDJQHKgPShy3q4GG7dnE_xzVeyD_x5S3hMq2tjMne6No3JWTwn6fggiK8ZfpNcJn5vRcfO3nECc83PriC8cfcY-0IBj3FFnR-G6TQgIBlpAnBIppVeMq45qN3tQf_o560G9q6otxT7NqkiLMXY27TqTzejv0fDfuugrm_UZ8x6hi3LWwl9NVx6rxjTXu-i_grtkNrR8a34QdttW59r5x57raze0x1Ngf3eBOwdpzVY3nUDvvmtv5qQ-npt9R66yr7dkdXeWdrw7WhvE41mfvm7Hyx9EcLd4DLYdleb0fOE87ElmxrWpb-2q3hBsu8milc2XE-O7T1xfjXGlpbsuv_W2dxBztQqLyA0dJF3y01rinrTHFSd_Blz93tlT1e9Tf-7tb89L-h50PIduxT5l_wV6Nuz6EF0vftb-27vcAAAD__83xcL8">