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

    <tr>
        <th>Summary</th>
        <td>
            LLVM should vectorize linear search if possible
        </td>
    </tr>

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

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

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

<pre>
    For example, code like this is almost unchanged when compiled:

```llvm
define i1 @does_contain(ptr %span, i64 %len, i32 %needle) {
start:
    br label %loop_header
loop_header:
 %idx = phi i64 [0, %start], [%next_idx, %loop_body]
    %need_to_stop = icmp eq i64 %idx, %len
    br i1 %need_to_stop, label %done, label %loop_body
loop_body:
    %current_value_ptr = getelementptr i32, ptr %span, i64 %idx
    %current_value = load i32, ptr %current_value_ptr, align 4
    %it_is_current = icmp eq i32 %current_value, %needle

 %next_idx = add nuw i64 %idx, 1
    br i1 %it_is_current, label %done, label %loop_header
done:
    %found = phi i1 [0, %loop_header], [1, %loop_body]
    ret i1 %found
}
```

I think, it is possible to optimize this loop by vectorizing:
E.g.:
```llvm
define i1 @does_contain_simd(ptr %span, i64 %len, i32 %needle) {
start:
 %tmp_0 = insertelement <4 x i32> poison, i32 %needle, i64 0
 %vect_needle = shufflevector <4 x i32> %tmp_0, <4 x i32> poison, <4 x i32> zeroinitializer
    br label %vector_loop_header
vector_loop_header:
    %vect_idx = phi i64 [0, %start], [%vect_next_idx, %vector_loop_body]
    %vect_upper_bound = add nuw i64 %vect_idx, 4
    %vect_in_bounds = icmp ule i64 %vect_upper_bound, %len
    br i1 %vect_in_bounds, label %vector_loop_body, label %tail_loop_header
vector_loop_body:
    %vect_current_value_ptr = getelementptr i32, ptr %span, i64 %vect_idx
    %vect_current_value = load <4 x i32>, ptr %vect_current_value_ptr, align 4
    %cmp_res = icmp eq <4 x i32> %vect_needle, %vect_current_value
    %cmp_res2 = bitcast <4 x i1> %cmp_res to i4
    %vect_found = icmp ne i4 %cmp_res2, 0
 %vect_next_idx = add nuw i64 %vect_idx, 4
    br i1 %vect_found, label %done, label %vector_loop_header

tail_loop_header:
    %idx = phi i64 [%vect_idx, %vector_loop_header], [%next_idx, %tail_loop_body]
 %need_to_stop = icmp eq i64 %idx, %len
    br i1 %need_to_stop, label %done, label %tail_loop_body
tail_loop_body:
    %current_value_ptr = getelementptr i32, ptr %span, i64 %idx
    %current_value = load i32, ptr %current_value_ptr, align 4
    %it_is_current = icmp eq i32 %current_value, %needle

    %next_idx = add nuw i64 %idx, 1
    br i1 %it_is_current, label %done, label %tail_loop_header
done:
 %found = phi i1 [0, %tail_loop_header], [1, %tail_loop_body], [1, %vector_loop_body]
    ret i1 %found
}
```

Currently, it doesn't happening:
Example with LLVM IR: [godbolt](https://godbolt.org/#z:OYLghAFBqd5QCxAYwPYBMCmBRdBLAF1QCcAaPECAMzwBtMA7AQwFtMQByARg9KtQYEAysib0QXACx8BBAKoBnTAAUAHpwAMvAFYTStJg1C1aANxakl9ZATwDKjdAGFUtAK4sGexwBk8DTAA5DwAjTGIQACYNUgAHVAVCOwYXd089eMTbAT8A4JYwiOjLTGtshiECJmICVI8vLhKy5Mrqglyg0PComIUqmrr0xr62jvzCnoBKS1Q3YmR2DiwaAIBqPC5VgAF0VEwFAH00QSZ/CFiCYlWAUkiAVgVYw1J1gDZJG/v6Bhe8AGZIp87gFMOh6JMbgB2ABC1w0AEERjUQHD4at0asQlcDGFaEDaKhULEDghMEwsMRUQSiSSyRSUQiMUC8OhVDc/gARVaxBB4N4fa53aExIFIgiCjkvQWw%2B4BVQEA4s1RSr6E4khDAATwlqKZt2BmFBByIBz6RPZXLwyBYsVWmAAjvzmayVXdvrqMVj1pt9SD0MbUKaiLEXjjSkDdgFQ0xcfi1QcNehtQjqeqtQy0Rj9cg5sRGArTGI3JgDhcrtdOatgJgCKVMGxBGX1gCXk39Y9nk79UqPejs7n8wdC%2B5MBbVgTyc3Iq3LkCc8Q84Ih0WS2WXmI8MAGKtJL3mQq8Id54uCGOrTa7Y7/oD%2BwvB8Pi66/fRUXvfZh5YrWWPyehVgw3AAdy7e4lReLg9y9DZ90VI8B0EaNY31SNMEQ8N9VTWlyXCVEUIzPV7n4NwGD/CsuR5PloOlEUMPjUlsMpO5JRuIVGjjGlE21Ji9zzU8qMI2YSNfSEOVfBFcMwFZR2gnY9iPWRTgYU08BYdBzlndsnh%2BEC3UYX4ASBZ9MAha4YVRMV8Kze4CBtA4NDPBglBqOsG1PCsnA%2BNlrwrbBuVQQ8BH0m9ZUNMFUKdDQ33uUxMBsA4jLHBQEDcKgqHoGKbBIdkPNWLyAR8oEbOJGi/hyvLIgK%2BIAu09zPKnAqAC9wn8hgkg3JrKUZT1sRjdDotiohiAOTD6IpVEMsG4a6LpbooruCavzZMjuV5LshRo%2B4xQlKUhX1Ba5QPF0gQmkgpo4rUdS6vt%2BritxYlicIE0E0jK1/f8gJ0hawJ3OavqUjViPQBQz2tW03HoT6BoOO6HqGgGSNdd0rsxK5%2BPmqH/CewGFDQvE9oG07MM43HCtOWgzuJUacIRE6hqJ9Nfqh497xXUsNMrata3oVym2vGdy02rTfneY6MdZRm4uZpcH1HZaJxesr6r%2BbB%2BdFyX4ILVm11WDctx%2B5Hs1svNgeW89bQdbK6u85W1YVIzXQWqXNZHObQYOY2b0rEJCFEPpLdy70CsN4ljdWIh1l3A2boVIiSJBi81jwAV7jdj2XkiqP0big7Fp/dA/wA4C8BF/G4u%2ByPM3RKCfWjg5Y/QEnkIEcKwzx6PCemhixPhKo6AprD6TmpUxwotaZSzw7lVtjuaSpxjmOld9P2%2B/Ve/J%2Bmk0uyvDNCgMg3NU3QcvHSV6%2BRhINRmuDSNE0zRDcderbu4UMb6yyf7zjUTXj%2BGczp3lxHGzcsHMawuXzLzFs3INKC07MXZOdwex/w1gA4sY55ZTlVreE8KDVyXHXLQTc24K4EQQQeOCd5BDx3NleAyWCWYjifKFF84lM452HstN6hcT5HQgsjauMFDxHA1q/Z%2BzcRHfxGjNTq8I8JzXriPVaVF1qugkZ3MaTEdrQjYqvd%2BG8uIL1Yg7AmdN4yf24sjXi3ogT12EhyDg0xaCcDuLwLwHAtCkFQJwHwPgABqABZVYABJAASqsBQsx5iy0iH8HgpACCaHsdMAA1iAO4XAAB0kJIiSC4H8SEABOGJGg/iSEkAADmkI4jgkgXEJI8ZwXgCgQAxHiW4%2BxpA4CwCQGgG0dBwjkEoD02IfSIh4HmAYIwXBXgaBiFgUwVpMA%2BLwJgQCAB5B6rjYk0FoLWYgTSIAhDqd7ZgxBNScFicc6ompVkhG0ANc5vAemuVWQwWgZy2mkCwCENwwAnBiFoE07gvAsAsEMMAcQHz8B5hsHgGKgL3Eflim4WsDzyCCFKHUghWIrkuCwHUy4KkHnTDSkwYACglkrPWYwVF/BBAiDEOwKQMhBCKBUOoD5uhGgTOMGYCwWKmmQGmEScogKAC0qy/i8FQDFBcLJ9jwGmFYAayQHAkUGF4P4%2BTSC%2BH8J0Ao3RIjTkyEkAQ6qQCariAkE1DAxhdCKNOJVMKBCtAGK4eo5rXhNGVc6/o7RdXjANQ631Zq/ierFLa/V9rFURIWBIBxTjakfM8RwVYyBuWrCmekjQWbVgQFwIQLKtwYmTF4K0rQkxphz0oMkkA5T0mREhHcMprxoivDKfk14dw0meqqTU0grj3HJsac0uJCSK36E4JERNg6GmjraeOmViR7CSCAA%3D%3D)
Example in C++: [godbolt](https://godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(filename:'1',fontScale:14,fontUsePx:'0',j:1,lang:c%2B%2B,selection:(endColumn:9,endLineNumber:11,positionColumn:9,positionLineNumber:11,selectionStartColumn:9,selectionStartLineNumber:11,startColumn:9,startLineNumber:11),source:'%23include+%3Calgorithm%3E%0A%23include+%3Ccstdint%3E%0A%23include+%3Cspan%3E%0A%0A%0Abool+does_contain(const+std::span%3Cuint32_t%3E+span,+const+uint32_t+needle)%7B%0A++++return+std::any_of(%0A++++++++span.begin(),%0A++++++++span.end(),%0A++++++++%5Bneedle%5D(uint32_t+x)%7B%0A++++++++++++return+x%3D%3Dneedle%3B%0A++++++++%7D%0A++++)%3B%0A%7D'),l:'5',n:'0',o:'C%2B%2B+source+%231',t:'0')),k:50,l:'4',n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:clang1600,deviceViewOpen:'1',filters:(b:'0',binary:'1',binaryObject:'1',commentOnly:'0',debugCalls:'1',demangle:'0',directives:'0',execute:'1',intel:'0',libraryCode:'0',trim:'1'),flagsViewOpen:'1',fontScale:14,fontUsePx:'0',j:1,lang:c%2B%2B,libs:!(),options:'-O3',overrides:!((name:stdver,value:c%2B%2B20)),selection:(endColumn:1,endLineNumber:1,positionColumn:1,positionLineNumber:1,selectionStartColumn:1,selectionStartLineNumber:1,startColumn:1,startLineNumber:1),source:1),l:'5',n:'0',o:'+x86-64+clang+16.0.0+(Editor+%231)',t:'0')),k:50,l:'4',n:'0',o:'',s:0,t:'0')),l:'2',n:'0',o:'',t:'0')),version:4)


</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzkWlmTqsqy_jWsF2OvYFR86IcqJhFRccDhpQOhhGKWQcBffwO0be22197n3HPPy40w6KiqzC-zsjI_Emgrz7EbI_RGcJDgxF9WWXhJ9gZiF4XYTvK5l-Spl2RJ_uuQOM2bnGQ9VFtRGiKCFnp24qBeiAPUKzyc93Des8IoyYteGdueFbvI6VUeint2EqU4RA7BAIIUCfLj2ievvzA8R9cpBx1xjHqY6hEs6SQof7eTuLBwTNB8WmQ9guby1Ipb47jPtsMQXUcM3Y5ihJzWt2GPGMArZF5YWXG33Ov1eoesF1oHFHbqSZK-e8hyUHYVeJy4KxE0h526RzBiL_Xw1TQHydZw61FngRO7IQc7N-riHTv1TaDDbAPYCt3duLn7XiTveZGkHTq2o7SHTh-be4BA8dMG2gg967eC9205SYyeJj5d-NxlN3wMDEFzdpllKC7ez1ZYovcu5IzYc1GBQhShuGhnMEO32K_Po3X5R8AOLEws5wvGN6vtmhViN-6xT2i4eMf5-038OWLXBHhCusXulhQPmdd7OKMOxXKcXlxWX-JOvQj5kwf_IOaPudVJfAn4MSlj5zOzqMfEegS4pxf1x6TKUHFztAO-bXogfqm4x2CobfXGQXeGRVvEaZLn-BCiXpH0krTAEb7cKry12Ts0vTOyiyTDFxy79_1Iv93fnwX-L5T2e44j5z9W3wTNFVH6Tl6TI85R9pG6PYIR2F7dpR4j9dIE58kr7Ktp8hOv3e37dbVDzb3yeAzRNQhfUD_Md4f0g73n-QvKEhzjAlshvnxkyleautp6_5ZRL-a_5Ffn_L9EXrftPjHYo51XRNbplGmKsvfDPaG_FNWHJy0k-8LH-Kqaf5Z1GaIn5QcDf6TFZ7ynmvy2kcfFwsLhn2P8ijI7a_9r3rxH58_Qnwz6lEUPuK_d-YlQ7Sh9z1D-RKXfMvqhAB7y4dnIK1S6gz3gwrbyz_Kjbqgfpoukh1_kwycxdn611ME-YreefC_Snzn9h_R7TprjR279zOo_leL1-i2FviTLi0r84ttrE3_oLj5NPlfmf7W_-OLEl1j8P-40Phq9_-tm4zV3PXccf9NufIP41nN8T7Xn9T_eJv6N1kS47jxsbs1J2zbEBD0oep6Vpih-6j-uzyW9ChdebzIx9Z66IBjQuucmziEJr3c53iuKNG-1aJmg5dvS7yRzuwnmQjBgtpu4HpDhyeEMoQa7ar6DuhDBhQMnQKYMwQbWXBKAfqlgoYMBMCq50A3YgIU71ApjJ4EmxwfS2AKh5iEEWgLjFQBrMEoroJ-BvFsti7FLCZQFprUVhMM9WFWi5jtAkdcF0NhcQXUFA15cAcCJFfBXimoAYTddu2BkAlOYVbutQ_JDpK8OYMUDdryr8MyfrJQi97AkjCNVMFX-PPG0htOzkxs2LjkXkkhdn6IsI-usT_vnixAnUFtSBrOLFrSIKwuo8DQXONMFMmlKlQxGJGks9wQtCzIWduEGrAMMTNfcVdSYcsX9WCFo-dyHHuKBsldTfuDK-szrj_WDC2kABaoigSQt_LUxElmrIK3cCG1RkS1JtDRvPZFE19OlKtcXa2OJl8tmsVwbWF8L_MwzRbs9JLAwrRpCdsoeLY6xpFqVVRcLfnA2NhVBczRkoWlIgM2pxTLrS2zgiQCsqvCk7QsaRjKEjQov_cV8v51UDdzl5iYCwD9fIqsxt845O-mmT6XFcCmS-mGtWXgibX1_GYiOKxtkbR8xZdhT5BWGf0KnwmjIhT-0XS5fKCBbKSozdkXPzgpnZhXu2BU0U1dqqGwpV9gGzHA3jIPBcH2aIz8fxHzlCJ3XnA4PprtqbEY9MZNAsHmDZ1WP3CzpzTZSeR0oWjGeMJFx4lWHY0tBmWUra7AbELSciB1GdYb8HPf7BC0fF-vt-bj3uF222cwb5JluxQDgNAPEhgs0cYfNUNwPSVPlISlZ0x1DLae6ZPDTobnahM1WMKW1epmbg5idVorYHnpeLrh5mMxCaa3P_XWY6-mMGy9K1VR8Xwklmhrj4eWy5k-6Su-W0-NSmplHKNt6Je8XtBvvhni-Wazc3Zrk4c6BlzB28tjrfJcEZr3bsmAJ90MdeBa7Mxe6yWsXxAqwAOxUnEM3hKdZrlBzIY9BpzUNsyo7wNI0DB6OyGi4X091ea05osEw5brWYQ5YfzKChiTamnsaJYp2gKoTzKebSQMWfCIdZmMFE7TsNeeJ6modrApKcniZazE4AWFYxbznBi4zzrT1fkXlC98RkwInHgazldhXU1PSc4W1-pP0kCRZKVjny173S5Ob5N4iuSZlbYTa2ttS0OKMuUy6RhS4acJma2fZPxedTIaLehdiW5VIifQ1qj1G3h2TnlWNmZl1Pq19E88NaFzoYkMyo2TVh8ls1h-dFFdZTh2HzPJa4zqseXQatWeGKkUWjbM0TBRyoOssMxKK2ca9lOO1ZasLqe-dxsPp8eSxw0G9XedTPbMKi0nMJqLPitOQdLY6xmjX1539ImLLfWqPqNHeGtcoz_pZZ-sAuz-O3GxZdWJGFLUR7aK-pvUop_Lz1EUbfngwnIPWL3luQ-1M9bI1NqftdD-aHYzdbEcfyEwaC7I0TydOMyCFfMqGvrNRPSpkAH1ITBUvxxDzlF8Bc-A7Pr0N8GlOHrA7kFOClp2WxyvACjxs6Vxhy86DZq4zC004bnyX2xG0bEhxoEq2Vl3q_lxAkYfruaclfZBmYn8Vpeu6Sgprv7xUg9As_NJaprUfzUJnOKc7QIKWTUTQ8rgbRQFZNmdxKri6y0zXjGGfR0uz360tPHW6iEpxOZXIy0K0HZQdSnatH_pNcxxc_PVq63eCin1JmbAeKRc7H-lWVW4vk4ucM-pUE8iBvt3PnArV7fYoF7D5juP2q9DMkMRrotlsR9uJsbJpVmMlwzDQTHA4KNbMNESg2QibnY-PmizzbKizHD3Ki2nfs1fcyHBz3yp1WaxHgDoRtLzvnLnYi9GxVvzp6sSr_PiyzfDctEyZOpVusGd0ayU5meHvTmfn6jxfqhNq5w5A5EzZ5kizub_FTOKuKFryGtEla0uwxXJSTaoRKIRANsbVqJq7AJ4A3Js7AMcALE85NPKaww2JR_zITYEgWKPc0QGgMJixWwAgGYxVvBTYEb-UAJwpY6W9U-OlFAAgRoHK-m7gbqWxyu-rrSu4BqhHeMN2XtYpYIVKMBRXIR1Y-YGUiCStHpeqx44isFOrLdy6FsSyu67MVL_yy6Qau4YAIAf7mb8LSDmZbHbuaqkCTzw5g71bw-nSlrFt95MoNQNPIcHU5s4ARaW5MaqNu2_oKBAqQZpWFYghlhOJHLhnkINc0nVgG6MLDzkvH7mK5k4Y6RjiiN3k4qURBFkbrV1vo2ZBKVSjdcNqwSheicug2gHBDYNsvtlVZpvsEAIsSrNKM3QPChpczxKRKz3FXc10ZSdUGy2KDCWSlnbiakAgT00bOF42RBnak_HQr5RI3gGrMUYgWCsyO79GbbW83p1G_JgECbNQ_VXQSAEw-idDsDIMAokSQe05gjadjU1dg0IBFI1FCZdtvali2u3NKBksnK0PpkafofZtomGUyROrLaRhJq8X6gaqsF75VnDU-UVl7hpYbjIhQoFvbA6ma8iVaky0otpFK5nVyMwI6tS7kIkeBIBbkdFC8ka2nmZ1gs-idgwo1qnICJ1OqzXpZj4zGueWTZZjYakxfYkdS4up21ciP7PQLDLxYiAsBdCeOCPeLsPnThLHPYFoSx_-G31k15jSFEHzBM3_PPAIBtiJgyQHF0n7MIK7Vf6IQxRbUde80wOKoAcELRyTuFjaVtjOUuxtYp2jeX0VI69ifrtM0EJode2xfSOw7iLkKER2gZP4agfFjpCEZdQOhwQtoNiZ4BhNy-jQPbxSLVCa5LhVeZL8mPwufjexLKyseFJ6Xnqh-l3jpWC3kpSZfQtQuzsGx3ZYOqg7Mo4RrNBNMlx4UTuSCJojwSsxOy8c3D5d_Uno-uj5IHG7HJIkJGj45UuFncR5QdAwL7pPHgz4UBdKHBcM_f5hDd4eaQkafuh8SsD7y06C5gbwZhTefxkqyix-NGPFzXty7BLri-zjr7X5-4DcztVrKP9eHsXOP5MmaI67e851lfKwpfrH3fz0u--y_qzUOzzzdzjcQHwhMXxU7UQG152F12zirnUUP1VVch0Jj9UEbzl4nWBuZVo86g2vyAHBAI78NMH-wcR10HIL-QJNeE0h3Re2BwK5zzDAbomA6pMtmoPO2EYmRtUsRfEzu-CwQNmV0vjDk2MHHFtZ8yR9nZodfGQXTwt2EkUoLmZx2DxhOOhQuoIVhvmTuIMiK3ZD9CyLs5Ymzih_mkY1ssvimRNxXKDwSSrEh8zKGiFxnkGLDEePqm0sj6Hl5q-j8R_g2hAf8oeTag0mact-t239NWNuB39GWYYd9CjN3-g_L5xzd7DXF01PNmjynmB_4HXqFa-_onXqR1r_mdW_L33X_K7wSu6J06l_XJAtNfD9v_psS6LdMdCQ6v8mf5NdWfIfd9Z7iQ7_G1X64Dz9tyCvlM8oy6-nyd4bk-v1l_PGOENmaP1Cb1Sf53iK5Rj2l_fWd4Y2S9tDqz84kiyyHI4kB4dWEjGWY9u_8BtN0gzZJxlqwPIc-9vqM4gdcAN-QFocO0AES6LIwuHvMDxHbS_zC-d5id76DDlkf3XvGvPufwVoOkZVr1skaJrgxF_ZW6vz16F0c4IlQ5wX-SdKgYsQvXUv5XIvKUPn_gUR9UIcIyvr5cjKbK-Hj_fPj7_KLHz70mXhwisPv-0kImi5-7R4_fNXmiUdEdFy51NO0HLn8_8EAAD__wns4og">