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

    <tr>
        <th>Summary</th>
        <td>
            [analyzer] Serious slowdown on FFmpeg sheervideo.c when using ArrayBoundV2
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            clang:static analyzer
      </td>
    </tr>

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

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

<pre>
    When release testing on top of clang-18, I noticed some significant (many X) slowdown on certain projects, e.g. on FFmpeg.
When investigated, the most impacted TU was `sheervideo.c`, where we had 33 seconds in the past, but now it takes around 1.23 **hours** to analyze. At that point, I'd count it as a hang.

After bisecting, the blamed change was #72107 `Switch to PostStmt callbacks in ArrayBoundV2`.

I used `perf` to get a glimps on where we spend our time, and here is how it looks:

The `OOBv2` checker checks array subscripts, and then it spends most of its time on traversing symbols to see if any of it is tainted.

I've also checked that prior to this change, the maximum `Sym->computeComplexity()` within `getTaintedSymbolsImpl` was significantly lower than after the change. After the change this maximal complexity was more around the threshold (35), 30-33.

I dumped the state when the `getTaintedSymbolsImpl` appeared 63 times in the call stack and the state dump itself, was huge.
Several if not all lines individually taking up 26 Megabytes.
Many of these lines encoded the history of some "hashing-like" computation.

I'm not there yet to make suggestions for a fix, but I anyways wanted to let you know. @NagyDonat

Here is the preprocessed reproducer:
[sheervideo.zip](https://github.com/llvm/llvm-project/files/15009479/sheervideo.zip)

Here is the command to run it:
```
./build/bin/clang -cc1 -analyze -analyzer-checker=core,alpha.security -analyze-function=decode_c82p -analyzer-display-progress preprocessed_sheervideo.c
```
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJycVk1v4zYQ_TX0ZWBDpmTLOvjgbGo0h-0WyPbjtqDIkcSaIgWSslf764uh5KyzBQq0QBAp0fDxzcybR4oQdGsRj2z3xHbPKzHGzvljiCgunTCr2qnp-EeHFjwaFAEhYojatuAsRDeAa0AaYdv19sD4B3gB66KWqCC4HoHAdaOlsBEYP_TCTvAn4xUE427K3SzBSPRRaAuDd3-hjIFwcNNu6Nv53A_Yblj2zLJT4qHtlRi0IqKiyNgh9C5E0P0gZEQFn3-DmwjA9lnoEP1VK3QbyfYZhd869Ag3hE4oyHMIKJ1VAbRNSIMIkcLqMYJ1N9ARorhgAOHdaBVsNzwHxk-Mnzo3-jC_QnQgrDDTN9zAKULsRITBaZuwXhgvFUg32kh4IoCATth7VvPvUxPRQ60DSirvPbPaiB4VSIrHOS2el3yblZTf601H2dHuv7oQX2MfQQpjaiEvKaOT92J6IuK_c7bP3m34AmNARSgD-obtM4JpMYKA1uh-CFT-t2qFAa0CN3qIukdiJ6yC9FUH6OZKGecugeXLBoxv2e5J96JFtntm_NDFOKTP_Mz4udWxG-uNdD3jZ2Ou98d6kQHjZxECkhzOe37IisOO8TOv8rrkvFzXWZ2ti7KW66oqDuum4DWKKle7QjFePSb6uUPK8tOnpysVAWSH8oJ-flJjvZggjHWQXg-z-ii3mMQW58zDLDHXgI4hlSDp34sr-kDTEKa-diZQDQMi6AZI6imeCkT6jqjeN4Dx8oogTHALJ7UIx2vnCSl2Oiytf1O6-Kr7sU_Nn_o1y3-Srh_GiB9cPxj8quPE-IEqsM_gpmOnLcW2GD_PFF5noi_9YFKICI9DaiYw7oaeiFgQSZO07UxiA6cf_jNTTKSEAfnGIeH2zuN9bmhJ7DyGzhlFVpDviCT_AHm2zvMflKnGfsB5UYgiIulwns9_y0UMAwqPCvZ5atHbUNNMEJC83Du7wNI-1FE0TfIGEaAbW1zYvOIVvTDUTOsiEIjRNsEqfdVqFMZMZA8kgHEAvoeP2Ip6ihgWiI-LCmKHAZfVaKVTS3adDtH5FJL8knHeidBp266NviDjHOb-iqid_Yd8-kQspjGcMJJmenFBCGPbkkk6G6BxHgQ0-uvd1l5ImjcxBbgJqiKtMhhhciNcrLttgBXZL6Kdnp0V8XHLn5dxT0bpcfBOYiATSe9qlOi_T__u6cF9v-nhf3pAow2SBWx3WVYVZcX4-Qfc99P-yFG6vk8Nd-BHGubv7PbZ8pP-3DB-rkdtFD21ZfyczjRYS7mF9eLsby9-vVgIy5-l8zSbwgyd2ASUoyf13yPXzWgltYHlzwqp7V_kgQ8PSEqHwYiJEm49hvCurl_enV_via_UMVdVXokVHrflNs-Lqij2q-64L_OqKCTf73mjdkVRZhVmBZZZWW-b-sBX-sgzXmTFttzSc7_Z5lvJVZXvmqzCbZ6zIsNeaLOhVmycb1c6hBGPhyordisjajQh3Rc4T2Vi-YnGScv7GegZ53SZ8MfUzHpsAysyo0MM3zGjjiZdO94W7Z7hFb12Y3h3PZivAPBYi9kPxuS8j2fcavTm-J8llrIjjaUE_w4AAP__GnD-hg">