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

    <tr>
        <th>Summary</th>
        <td>
            Crash in SLP Vectorizer since llvm15
        </td>
    </tr>

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

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

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

<pre>
    We've run into a crash in the SLP vectorizer, which is a regression from llvm14.  Bisecting points to the crash first appearing with [llvmorg-15-init-9301-g7ea03f0b4e4e](https://github.com/llvm/llvm-project/commit/7ea03f0b4e4ec5d91d48ba2976f5adc299089ffd). The problem still happens with the head of main (just tested [llvmorg-19-init-6925-g7467dc188a0c](https://github.com/llvm/llvm-project/commit/7467dc188a0c63b32bd3068fc98ae77f86285c0d)).

Pinging @alexey-bataev.

Here is a reduced test-case:

```
typedef int int32_t;
typedef unsigned long uint64_t;
struct SomeStruct {
 int32_t iv1;
 int32_t iv2;
 int32_t iv3;
 int32_t iv4;
 int32_t iv5;
 uint64_t maxLen;
};
static int32_t bar1 (SomeStruct* sptr) {
  return (int32_t) (sptr->maxLen);
}
static int32_t bar2 (int32_t ival1, int32_t ival2) {
  return (ival1 == -1 ? 1 : 0) | ival2;
}
int32_t foo (SomeStruct* sptr, SomeStruct* cmd) {
  int32_t iv_01 = bar1(cmd);
  int32_t iv_02 = sptr->iv1;
  int32_t iv_03 = bar2(sptr->iv1, (iv_01 == iv_02 ? 1 : 0));
  int32_t iv_04 = sptr->iv1;
  int32_t iv_05 = bar1(cmd);
  int32_t iv_06 = sptr->iv1;
  int32_t iv_07 = bar2(iv_04, (iv_05 == iv_06 ? 0 : 1));
 int32_t iv_08 = sptr->iv2;
  int32_t iv_09 = bar1(cmd);
  int32_t iv_10 = sptr->iv2;
  int32_t iv_11 = bar2(iv_08, (iv_09 > iv_10 ? 1 : 0));
 int32_t iv_12 = sptr->iv4;
  int32_t iv_13 = bar1(cmd);
  int32_t iv_14 = sptr->iv4;
  int32_t iv_15 = bar2(iv_12, (iv_13 < iv_14 ? 0 : 1));
 int32_t iv_16 = sptr->iv3;
  int32_t iv_17 = bar1(cmd);
  int32_t iv_18 = sptr->iv3;
  int32_t iv_19 = bar2(iv_16, (iv_17 < iv_18 ? 1 : 0));
 int32_t iv_20 = sptr->iv5;
  int32_t iv_21 = bar1(cmd);
  int32_t iv_22 = sptr->iv5;
  int32_t iv_23 = bar2(iv_20, (iv_21 > iv_22 ? 0 : 1));
 return (((((1 & iv_03) & iv_07) & iv_11) & iv_15) & iv_19) & iv_23;
}
```

Compiling this at `-O2` hits the crash on trunk https://godbolt.org/z/dxPb57ndo

For reference, it hits this assertion-failure:

```
clang++: /root/llvm-project/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp:11365:
 llvm::Value* llvm::slpvectorizer::BoUpSLP::vectorizeOperand(llvm::slpvectorizer::BoUpSLP::TreeEntry*, unsigned int, bool):
  Assertion `I != VectorizableTree.end() && "Gather node is not in the graph."' failed.
```
Below is a .ll file showing the problem:

```
; ModuleID = 'test.cpp'
source_filename = "test.cpp"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

; Function Attrs: mustprogress nofree norecurse nosync nounwind willreturn memory(argmem: read) uwtable
define dso_local noundef i32 @_Z3fooP10SomeStructS0_(ptr nocapture noundef readonly %sptr, ptr nocapture noundef readonly %cmd) local_unnamed_addr #0 {
entry:
  %maxLen.i = getelementptr inbounds i8, ptr %cmd, i64 24
  %0 = load i64, ptr %maxLen.i, align 8, !tbaa !5
 %conv.i = trunc i64 %0 to i32
  %1 = load i32, ptr %sptr, align 8, !tbaa !11
  %cmp.i = icmp eq i32 %1, -1
  %iv2 = getelementptr inbounds i8, ptr %sptr, i64 4
  %2 = load i32, ptr %iv2, align 4, !tbaa !12
  %cmp11 = icmp slt i32 %2, %conv.i
  %cmp.i57 = icmp eq i32 %2, -1
  %or.i5977 = or i1 %cmp.i57, %cmp11
  %iv4 = getelementptr inbounds i8, ptr %sptr, i64 12
  %3 = load i32, ptr %iv4, align 4, !tbaa !13
  %cmp16 = icmp sle i32 %3, %conv.i
  %cmp.i62 = icmp eq i32 %3, -1
  %or.i6478 = or i1 %cmp.i62, %cmp16
  %iv3 = getelementptr inbounds i8, ptr %sptr, i64 8
 %4 = load i32, ptr %iv3, align 8, !tbaa !14
  %cmp21 = icmp sgt i32 %4, %conv.i
  %cmp.i67 = icmp eq i32 %4, -1
  %or.i6979 = or i1 %cmp.i67, %cmp21
  %iv5 = getelementptr inbounds i8, ptr %sptr, i64 16
  %5 = load i32, ptr %iv5, align 8, !tbaa !15
  %cmp26 = icmp sge i32 %5, %conv.i
  %cmp.i72 = icmp eq i32 %5, -1
  %or.i7480 = or i1 %cmp.i72, %cmp26
  %and3082 = and i1 %cmp.i, %or.i5977
  %and3183 = and i1 %and3082, %or.i6478
  %and3284 = and i1 %and3183, %or.i6979
  %and3385 = and i1 %and3284, %or.i7480
  %and33 = zext i1 %and3385 to i32
  ret i32 %and33
}

attributes #0 = { mustprogress nofree norecurse nosync nounwind willreturn memory(argmem: read) uwtable "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }

!llvm.module.flags = !{!0, !1, !2, !3}
!llvm.ident = !{!4}

!0 = !{i32 1, !"wchar_size", i32 4}
!1 = !{i32 8, !"PIC Level", i32 2}
!2 = !{i32 7, !"PIE Level", i32 2}
!3 = !{i32 7, !"uwtable", i32 2}
!4 = !{!"clang version 19.0.0git (https://github.com/llvm/llvm-project.git 7467dc188a0c63b32bd3068fc98ae77f86285c0d)"}
!5 = !{!6, !10, i64 24}
!6 = !{!"_ZTS10SomeStruct", !7, i64 0, !7, i64 4, !7, i64 8, !7, i64 12, !7, i64 16, !10, i64 24}
!7 = !{!"int", !8, i64 0}
!8 = !{!"omnipotent char", !9, i64 0}
!9 = !{!"Simple C++ TBAA"}
!10 = !{!"long", !8, i64 0}
!11 = !{!6, !7, i64 0}
!12 = !{!6, !7, i64 4}
!13 = !{!6, !7, i64 12}
!14 = !{!6, !7, i64 8}
!15 = !{!6, !7, i64 16}
```

The crash happens with:
```
opt -S -passes=slp-vectorizer -o test.opt.ll test.ll
```
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJy0WdturDjWfhrnxqKElzle5KKS7Pr_lvaoI2VPj9Q3kQtclLvBZoxJJf30I5tDGVKVpPdopAqxzVrfOgKfgXWdqCTntyi-Q_HDDevNUenb0x9adEadbvaqfLv9F0eQvnCse4mFNAozXGjWHbGQ2Bw5fvr-iF94YZQWf3GN4B6fjqI4YtFhhjWvNO86oSQ-aNXgun5pSLTB-E50vDBCVrhVQpoOG-XQBuiD0J3BrG0501bmJMwRo_jOqitdBSQOhBQmyGlIgirlLKSHcB_xiKP4AUF2NKbtEN0i2CHYVcIc-_2mUA2CnYUY_wWtVn_wwiDYFapphB34WEVc5qSMsj2DPE0OMSsLyPMwyw-HEkG-wT-OHLda7Wve4M6IusZH67PsBodtPEfOSqwOuGFCYgTZH31nsOGd4eUioHwIKMkhDqo0StKyIFnGwuK_DsjDSuiewr6kYZIdijxjPE0PWQJZXIQ2IBsTCh9QuB2Oj0JWNvsoClnNX_lbsGeG8ZeF0P9zzadal33BSxddULCOW389SZSE489NzVvLS36wPWX_KDwbRO-W53rpGrTEtZIV7oU0SeSJdUb3hcFPquFPwxCl46kJEosXMst7i3BpkV5ajC4txufFySvcsNfvXM4nUPrgOcqMKGb9PdPENsPZcQRb3LVGI8i9GLDmpteub6YM2fOQWdEA0W-jScgXVq-YBA8HixdWE3ux-gtw3bwVx4g-IPqAAzvaYXvc4nDQuR8B3vkx4R-UuhbyPV6uFk25cuTs5HPo3HApRJANoudiLCTBSU65WjTCQo5OiOCl1orD_RD7aNRKTbh--Nc9iL7oQfzlmJIvIqZ-TM4VL5rYjyZx0YQuGrKOxofMVqbhiun8q8GQ8GuIhKyDybxgrLlvM9zVuvh468aIrtilX45kXehriPEqEgLnSJy5-xnuKzUh63agV-ymX45kXeVriPk6ksSLJJ0jyb5YE1j3QnzZLnz58od1la8h0lUkEJ4jcea-zXBXa3K-U_o_e5NPhlvMcOMeJqk3IcSfxP4k9yZA399ZV8_T4XivmlbU9qltjvapbDBKwuBXQEmIj8LyrJlkKYmN7uWfeEUuVLlXtdkoXSHY_YVgV74-7uNUlso3tFMaa37gmsuCuweJmQxYu13HtRFKBgcm6l5_wgWKmskKwZ390S1GsNNKmfesZuI6Yo9g90Mz2R2UbjoEu98mBopg9_T9cZ7qTdG2iG4JoUk8O-F4qJ3R7W-s7rl96pyXurr1CK1bulP_bJ--Pw6T-eSvLddMlgiyryv_0Jx_k0a_IdjatM0UR0hj53ulatdak6t4O-XSlvIXjIDYfp0iZPuaW8wNd46MPWPbBgH8HzNHrrFUpeNoUpmJtVeatccNAkCQYlsjXm4uluaO1-o0ELxNXeODqDnujuo0tNjMfz-uL6J3-B-q7Gv-y4O72hCklia64kA6MhbV64I_WwuSNXyUg7McjOSQ6YobXDLDavamejNJ8sC6wYMW0hDRLQV3sFOynNpRErlDIOYBgcw2CmTBIQvHkXRLyaSeRMGTFVu5YrRo69nh1yx5TqKgl39KdZJBLWT_GlSyn7XOOdn1snCV3Rqj7SWIm74zrVZu14SlOmjOsVSaF73u7Kh7kwWWqpcnIUt8EnU93noa3ijbVBnTVePqgTVnjkj1J2O7ZDBb8oOQHJedeq5VwWoH5ng4Bcv0n3-nB6UeSXjmZE_hM4KsNbaRCtaaXvNZy9pQsn7DCOKJzX0uOTI858BzL225y2dWlhojoOGZ-XF3oZwvBQTxQHk3wmW74obXvOHSWJtC7q2tDotscmOydY9FEmGIPKDhgVMrVtpznsJkwS6xWlQSj3SDmD1j9n88wlh0JV9GZ-zNtHB2HLpRNqWeQeIZpOAZnPJ22RghHkbRtKM1UTQt5v8eygaxI6uBLype4Ms5mjywzvs5gmsuW642exytPYalxyN_cx53tZlcHqnPmMJ1kHF6KUx4F6bSGxHn6SCtNBbEg5gsWB8WqYl-KjWLwOj13EQf5IaucpP4ueFTnPTD3CRwKTf0Ym6SKM0u5CYBLzfJIjf0p3KTna-J6Hpm6Ad9Hi3DBL9rqrlroo8zc7FrosuZydP8Uma8roFl18Q_1zV-euPruYk_yE28yo3fNdXcNfGHuUkvdk18MTdplIUXcpN6XQN-WEyWNMwGA0yWvs6oMV2nKyWS0ZXSCOWp2RZeqUEWXVAjGfXV8jRfqdEsvqAGWeSp2dDXak7pL_5qPC2LtbzHaz53qRNY83V3ZMZose8N78ZnnSUN6d3_8sFvSUkjZFDzitXBwE6DkyjN0VIS-oDAbnms3yBVYDRrWyGroGGegNGWJTuZzrDiT0vKzYC07w8HroPOke9RPBtlB4IUFG0_n3rNksA-b_3zB84sV-hmIQR3RaNeENzb0Ws2DA6vnR5GTfM6DLqOzwMYRq9ZOqH3ki9sV1xyLQp3elkWBMRy-E3jWOrmULOqGwkdsXQEyLgrJONroWnnTugZacQQJZdmqRy9Nxd6ErZrJlwEcCqOTD9PCbW3EQo48u2QlXJ2Vn785R5_5y-89nTB14WVburrfvtYl17XnVjmFc1omRAE4DZ9-IVr93mA5JtwE1bC4L_9untjtf7We-6FZ_HSs2Sqc-jRRk88eRfI8-8_nny-PKYAAUkniHC9EK0XsvUCeQfyqWvpO9fcpnICys7eeErZOyXVSNEqY5vYNuIZIL8IkL8DeBKN3Q_dDzt6_ONuu13lfNH9g1KtZPWZr4u-92qVXpaGT6SXlxT9RJosI4g-Ec8W0leazK_th-91fsyvbfxPTOdd91JHtQYHTzhoWdfxDtGHrm6D82sJHCj3lWajWmM39W5c1yuom_KWljnN2Q2_JSkhaUJISG6OtyzKigPZc8rLJOKchSROSsJJss8YSQFuxC2EEIWUhiEhJCKbMqQ0zqEIWcjykGUoCnnDRL1x90ulqxvRdT2_zVJC6U3N9rzu3EdJAMlP2J20vRE_3Ohbd-nv-6pDUViLznRnFCNMzW_vp8-TT98f8flNEO6ELPjwCTK-6XV9-7e_qjlHOgQ75-h_AgAA__9USgks">