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

    <tr>
        <th>Summary</th>
        <td>
            [LoopVectorize] Clang fails to vectorize simple polynomial hash
        </td>
    </tr>

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

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

    <tr>
      <th>Reporter</th>
      <td>
          max-quazan
      </td>
    </tr>
</table>

<pre>
    Here is example of a simple polynomial hash that could not be auto-vectorized with SSE 4.1 (LV could not prove legality):

https://godbolt.org/z/3bWenc7EG

Original test:
```
unsigned rabin_karp_naive(unsigned *s, unsigned len) {
    unsigned hash = 0;
    for (unsigned i = 0; i < len; i++) {
        hash *= 31;
        hash += s[i];
    }
    return hash;
}
```
This is a very typical example of polynomial hash, used, for example, in Rabin-Karp algorithm (https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm). Another iconic application is Java String hashcode.

When we restructure the code into its equivalent, LV can vectorize it:
```
unsigned rabin_karp_vector(unsigned *s, unsigned len) {
    unsigned hash = 0;
    unsigned k[4] = {31 * 31 * 31, 31 * 31, 31, 1};
    const unsigned vector_factor = 4;
    const unsigned tail = len % vector_factor;
    const unsigned vector_iters = len - tail;
    unsigned i = 0;
    for (i = 0; i < vector_iters; i += 4) {
        for (unsigned j = 0; j < 4; j++) {
            hash += k[j] * s[i + j];
        }
        for (unsigned j = 0; j < 4; j++) {
            k[j] *= 31 * 31 * 31 * 31;
        }
    }
    for (; i < len; i++) {
        hash *= 31;
        hash += s[i];
    }
    return hash;
}
```
It would be nice if the original example was vectorizable.
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzVVkuP4ygQ_jX4Uorl4DiJDz6kX_saaaXt0cyxhW0ckybgAZxM-tdvQRLHyfS2dqW5rNsBylV8FMVXRZe6PhS_csNBWODf2baTHHQDDKwI407Lg9JbwSS0zLbgWuag0r2sQWkHJQfWOz3Z8cppI954DXvhWnh-foRZPAVCl5--jOw7o3ccJF8zKdyB0JykK5I8kOTUts511n-jT_iudV1q6WJt1ii94S8tv3JVLR5_GU_604i1UOih49ZdAOfJ6Q1ir6xYK_TPsFKol1dmuhfFxI6ji4OO0JUl9B6GD5IrdBLI4u6IAvgMyhAQkj5AQtKRvtEGxqBisAnD-wDqBULvwnuD758jNF35men0Cn6kvvNqS7I7QbKHKyOyeLgIhrveqDBpMBoMbsL0uUUi4Mtgx80B3KETFUZ2RI0bRoRwWV773u_8ZOlFoeAvH-zJHxhsYHKNDHHt1gfn-py5ivfiVXS8Fux02F7GLswnNHuk2CwTbPLUo70MaBi-GFbIrZYbEJVWogLWdRLddkIrv5ff2Y7BszNCrYPLla55PCbQ15Yr2HMMlHWmrzBaHInOwRviLpwG4TA9vvVix_DwnN-cpzVTMBAfTf4L9Y7zfjr3Bv0rsmKGrAg2CJH6XFzB0PmVbgTfTj0vxoAYUOsusEe3Xxrmu4A9-8jcMSGDFe4F18qu5_-LhYTjxg4IkwD4_obFP2fiDwk4Bj99PebS7N1kvE3ozQVvE_BmYfhBOt_mrD-dTTgdjH9IYK-BzW0a_5DKP8-dsQvHKnNNkDM1PnTnSjj59f-oc7852IdbCW8wLBmYvk1IeX2-S84Vb8_skOSslDyOeDGdZ3me0SSdR3WR1nmas8gJJ3mBPn7Suvtyrgo-wPeSYeFpkLkWsJRcKsb7V2zUG1nc3INY6PoyrjRWuycpd-dugtfpBuFQFNb2HOvHUzbP8zxqi5wmTTPLl_k844xWVZbXKS3LJk-XS1ZVaSRZyaX1HhNKFd9DgMAx-hyJgiaUJkv8y2eLaRY3C_-UJa_KpOZVRWYJ3-KWYu-Hr9mRKYJLZb-2qJTCOntRMhvIGgLk8fGfhlabYsu-T7717I2pKKxeBO__BglKeBA">