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

    <tr>
        <th>Summary</th>
        <td>
            [SLPVectorizer] Assertion `Iter != this->end() && "DenseMap::at failed due to a missing key"' failed.
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            llvm:SLPVectorizer,
            crash-on-valid
      </td>
    </tr>

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

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

<pre>
    Reproducer: https://godbolt.org/z/v5bqhPWqb
```
; bin/opt -passes=slp-vectorizer reduced.ll -S
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"

define i16 @test() {
entry:
  %sub.i487.i.reass.i = add i16 0, 0
 %sub.i487.i.reass.40.i = add i16 %sub.i487.i.reass.i, 0
 %sub.i487.i.reass.41.i = add i16 %sub.i487.i.reass.i, 0
 %sub.i487.i.reass.42.i = add i16 %sub.i487.i.reass.i, 0
 %sub.i487.i.reass.43.i = add i16 %sub.i487.i.reass.i, 0
 %sub.i487.i.reass.44.i = add i16 %sub.i487.i.reass.i, 0
 %sub.i487.i.reass.45.i = add i16 %sub.i487.i.reass.i, 0
 %sub.i487.i.reass.46.i = add i16 0, 0
  %sub.i487.i.reass.47.i = add i16 0, 0
  %sub.i487.i.reass.48.i = add i16 0, 0
  %sub.i487.i.reass.49.i = add i16 0, 0
  %or374461.i.40.i = or i16 %sub.i487.i.reass.40.i, %sub.i487.i.reass.41.i
  %or374461.i.41.i = or i16 %or374461.i.40.i, %sub.i487.i.reass.42.i
  %or374461.i.42.i = or i16 %or374461.i.41.i, %sub.i487.i.reass.43.i
  %or374461.i.43.i = or i16 %or374461.i.42.i, %sub.i487.i.reass.44.i
  %or374461.i.44.i = or i16 %or374461.i.43.i, %sub.i487.i.reass.45.i
  %or374461.i.45.i = or i16 %or374461.i.44.i, %sub.i487.i.reass.46.i
  %or374461.i.46.i = or i16 %or374461.i.45.i, %sub.i487.i.reass.47.i
  %or374461.i.47.i = or i16 %or374461.i.46.i, %sub.i487.i.reass.48.i
  %or374461.i.48.i = or i16 %or374461.i.47.i, %sub.i487.i.reass.49.i
  %or374461.i.50.i = or i16 %or374461.i.48.i, %sub.i487.i.reass.i
  %sub.i487.i96.reass.i = add i16 0, 0
 %sub.i487.i96.reass.16.i = add i16 %sub.i487.i96.reass.i, 0
 %sub.i487.i96.reass.17.i = add i16 %sub.i487.i96.reass.i, 0
  %0 = or i16 %sub.i487.i96.reass.16.i, %sub.i487.i96.reass.17.i
  %1 = or i16 %0, %or374461.i.50.i
  ret i16 %1
}
```
```
opt: /root/llvm-project/llvm/include/llvm/ADT/DenseMap.h:204: const ValueT& llvm::DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT>::at(llvm::DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT>::const_arg_type_t<KeyT>) const [with DerivedT = llvm::DenseMap<llvm::Value*, llvm::Value*>; KeyT = llvm::Value*; ValueT = llvm::Value*; KeyInfoT = llvm::DenseMapInfo<llvm::Value*, void>; BucketT = llvm::detail::DenseMapPair<llvm::Value*, llvm::Value*>; llvm::DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT>::const_arg_type_t<KeyT> = const llvm::Value*]: Assertion `Iter != this->end() && "DenseMap::at failed due to a missing key"' failed.
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
Stack dump:
0.      Program arguments: /opt/compiler-explorer/clang-assertions-trunk/bin/opt -o /app/output.s -S -passes=slp-vectorizer <source>
1.      Running pass "function(slp-vectorizer)" on module "<source>"
2.      Running pass "slp-vectorizer" on function "test"
 #0 0x0000000005035d68 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x5035d68)
 #1 0x00000000050334ac SignalHandler(int) Signals.cpp:0:0
 #2 0x0000707bdcc42520 (/lib/x86_64-linux-gnu/libc.so.6+0x42520)
 #3 0x0000707bdcc969fc pthread_kill (/lib/x86_64-linux-gnu/libc.so.6+0x969fc)
 #4 0x0000707bdcc42476 gsignal (/lib/x86_64-linux-gnu/libc.so.6+0x42476)
 #5 0x0000707bdcc287f3 abort (/lib/x86_64-linux-gnu/libc.so.6+0x287f3)
 #6 0x0000707bdcc2871b (/lib/x86_64-linux-gnu/libc.so.6+0x2871b)
 #7 0x0000707bdcc39e96 (/lib/x86_64-linux-gnu/libc.so.6+0x39e96)
 #8 0x000000000409326e llvm::DenseMapBase<llvm::DenseMap<llvm::Value*, llvm::Value*, llvm::DenseMapInfo<llvm::Value*, void>, llvm::detail::DenseMapPair<llvm::Value*, llvm::Value*>>, llvm::Value*, llvm::Value*, llvm::DenseMapInfo<llvm::Value*, void>, llvm::detail::DenseMapPair<llvm::Value*, llvm::Value*>>::at(llvm::Value const*) const (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x409326e)
 #9 0x000000000413473f (anonymous namespace)::HorizontalReduction::tryToReduce(llvm::slpvectorizer::BoUpSLP&, llvm::DataLayout const&, llvm::TargetTransformInfo*, llvm::TargetLibraryInfo const&) SLPVectorizer.cpp:0:0
#10 0x00000000041370d1 llvm::SLPVectorizerPass::vectorizeHorReduction(llvm::PHINode*, llvm::Instruction*, llvm::BasicBlock*, llvm::slpvectorizer::BoUpSLP&, llvm::TargetTransformInfo*, llvm::SmallVectorImpl<llvm::WeakTrackingVH>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x41370d1)
#11 0x000000000413b996 llvm::SLPVectorizerPass::vectorizeRootInstruction(llvm::PHINode*, llvm::Instruction*, llvm::BasicBlock*, llvm::slpvectorizer::BoUpSLP&, llvm::TargetTransformInfo*) (.constprop.0) SLPVectorizer.cpp:0:0
#12 0x000000000413ff36 llvm::SLPVectorizerPass::vectorizeChainsInBlock(llvm::BasicBlock*, llvm::slpvectorizer::BoUpSLP&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x413ff36)
#13 0x0000000004146401 llvm::SLPVectorizerPass::runImpl(llvm::Function&, llvm::ScalarEvolution*, llvm::TargetTransformInfo*, llvm::TargetLibraryInfo*, llvm::AAResults*, llvm::LoopInfo*, llvm::DominatorTree*, llvm::AssumptionCache*, llvm::DemandedBits*, llvm::OptimizationRemarkEmitter*) (.part.0) SLPVectorizer.cpp:0:0
#14 0x000000000414708b llvm::SLPVectorizerPass::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x414708b)
#15 0x0000000002f1a1ae llvm::detail::PassModel<llvm::Function, llvm::SLPVectorizerPass, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x2f1a1ae)
#16 0x0000000004e38158 llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x4e38158)
#17 0x0000000000e0b02e llvm::detail::PassModel<llvm::Function, llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function>>, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0xe0b02e)
#18 0x0000000004e36b7e llvm::ModuleToFunctionPassAdaptor::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x4e36b7e)
#19 0x0000000000e0a83e llvm::detail::PassModel<llvm::Module, llvm::ModuleToFunctionPassAdaptor, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0xe0a83e)
#20 0x0000000004e365b0 llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x4e365b0)
#21 0x00000000008feef2 llvm::runPassPipeline(llvm::StringRef, llvm::Module&, llvm::TargetMachine*, llvm::TargetLibraryInfoImpl*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::StringRef, llvm::ArrayRef<llvm::PassPlugin>, llvm::ArrayRef<std::function<void (llvm::PassBuilder&)>>, llvm::opt_tool::OutputKind, llvm::opt_tool::VerifierKind, bool, bool, bool, bool, bool, bool, bool) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x8feef2)
#22 0x00000000008f1d7c optMain (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x8f1d7c)
#23 0x0000707bdcc29d90 (/lib/x86_64-linux-gnu/libc.so.6+0x29d90)
#24 0x0000707bdcc29e40 __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x29e40)
#25 0x00000000008e984e _start (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x8e984e)
Program terminated with signal: SIGSEGV
Compiler returned: 139
```
llvm version: e8a739062490ce1bb30974f216ba187cd7b5a2a4
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzcWltv47YS_jXMC2GDInV9yIMvcTdochrEOdvHgJJomycSqZJUNt5ff0BKdiz5UnvrFosuNo5Fcb6Z-ebjTQrVmi8FY7cgGINgekNrs5LqNjfZx_f1t5tU5uvbZ1YpmdcZU4CM4MqYSgMyAngG8Gwp81QWZijVEuDZd4Bn70H6x-rp9z9SgKYAjUCI2v_NJRnDlAuAZ7IycFBRrZkGZKqLavDOMiMV_84UVMz6y4dFAQfzxtJQtWQG5tTQgq5lbSAgUwgwZoMSkBEbVDhCgIwIdh_20ute2m-h7z4GfPvFwzEgIw_Hg0WM2m_CNYUb89AfzG03jDuhGMWrgm3C-IjD19Af1OJNyG9iUHBRfwyWot5aNZ85W3DBIPdCCHxkmDbAIicQROOmBxNGrS3B7gpCgANdp0Pux9GQDxWjWg-580rz3AEhgCewJfhgdx_1LA5i_imKdxUUfBUUchUU_yoowVVQwlNVPWwSXW4SX26S_JmJVCTy_dAb8k-lSXWUCtvHQhzT2BFkbw-55_coJj6KiU9ieicwyVFMchITn8D0j2L6JzHJCczgKGZwEtM_gRkexQxPYgYnMKOjmNFJzPAEZnwUMz6JGZ3ATI5hBvvK73k8hskPjr4kvHCu3xp4_ZnkCO4ZSP0J5gwk2wcdnQI6Qe4R0nG8g-f18FBr2aN_Y6GY2fT02rU3mh7ejnQvZWXsFgfgmZLSADwrivdyUCn5P5ZtLgGecZEVdc4-G0bTF4BnUyY0e6TVcAXICCO7wYCZFNrAr7So2QvAIXQGZATIaNN7TDUDZDJlir-z_MVm9itbu98bM9dyLxbSfR_X2RszL4DcNUDU7iD-BlwX-itVy1ezrtirAWTiAMid3a40iYFg_I2bFdx4cXXajwWQyWej8w7wyPo80Grdj12oPbDPHuM2gxMdNokdCcjeOxrUu-R5G0bLSQ8lZ4byoov4RLm6PM1_tGwui6ZuBwIKplavI62ZMlwKCEJ0b5iCAHvWzqy4HgByx0S-2bDi0CoaYPxZ5kaPcEF5wXKY1wwaCSksudZcLOEbW9vtMI7aHsNm2D093I3md1DXackNpDCtl1CxSipjzXsHDm5WdTrMZPk5_HqjlGtdMw3wDFKRw3awQrNiMFNUr2BKszejaMZa93NDszeY12W13XWjIUDJk5JLRUtI1bIumTC6nRvsLIFnmSwrXjA1YB9VIRVTtq2gYjmgGw71wKhavAE82znySAtBq8pe16aqzVDDwfz4UQiQiZa1ypitsAvOs8E910JYSq2ZrcGiFpn1CXDcBQA4ARhDKWAp89qeVzDuYG7OJ_gQbB_LAW182Q7NCQZvlxGCIPpAm38BIkEexjt602vdfHlSXBhH_YutRWcOU_Tbq9RGMVo6lU0gF6bRXPwXCwDwGH20YVlqtnF7vbiJTzM450tBiy9U5IXFj9swmmY9zCorGeR-tkC4BYpQlOZZ5uMAozbwgqcAz9qT4s4J0d7IhloOQxeeM-kER7qYSZgsMliZlWI0f33jRXGZA2ffceD3g_ajEC61y_PS4P0o7GAHXWwcRwsCaWqH90XIzrCDHO4he-nFmF7awYy6mCRhSXgZpjPpYMa72vJRQnDIjs_9f2397LRetN51LK-1xt2dE-bPG_yhHZbr0iykzny7GbrO5NTqoyOgpCMgj_gRWVh_VEixLmWtoaAl05WbSJMmzC92zpbC0OKZ5XWzOLgbRq1fpGvrzrq6qHametc0lv-t5g9P7SS8Uxpq6EPzFK7lodfhxT0ie1FU6IVUpSthn-qmzwNPFVVuP7ODlcD5w9PXbTT7M62dsVGPlQjl3g5-B-GJ6nbh2eb4RapPZnaJePpy_x-Z72vjXmijNv1798ZU82xcyOxt79YFvJ5D27ykRdEkdl9WRUfTvzPqltM3LpZfv7hxEV5x3Ww53krTFsHrFSFNkvCCIjxLaTq8_tR1cEwOnUwrJashOlOpuEfSYkEuIWmyolzoe9HmFV8j3WuKwqbTEQXp5uuHPjpjZKpaOEXvJjjb7mt7JZpntKDq7l0W9UEh_NAMtNdjNHpmui6M3rvzIGV10GQqSy6okepFsX3tjrSuy8pGPKHZ6tCiV1KRs3zMD_j8rTK85N-pNX9mJVVvdyU3xlZrK86KKnO2Lv1enSIUp2fV6bwajQQt1prrRyroknWX363R9Scpl0ZHj8FunnjhUY-yI_sFm-ajzFlxONquBvf4-aH0N_uMn5vXlrYOr2FHP4zEXrB72HNcnorxX0xXy0aHrmiXLsRQivA1ZPi30fwvLk9Dfqc6cU_MYRrtVufRPT55kZuQLOujnFZGqsMJNwYXpdua_A1atMl0sk16WqQxuUyLm_QmZ3L0AyQck9LPw2zD2y6xGPVlFKTojMF6iM5_C0stCx2aOucGFC8YW-CdKFXtxPPEK1Zw0T2ozo3iYvnMFofEd2Qv_0izlcP5sy1gswPt95Ky-M09rZ3x4gDIX7p9JJ2RUnRtW3cL5Dgp6iUX-_PzZ39t8qZt-1SYTN4lz2H3eEW1Hte8yG0p3f79wKwvK_NqpGxngiaLX7nIT_X6yhRfcKY2_VJ75-LfV1Nfo62O-HBPfF4eZVBW5pFycT23FrXjtvcYFyd5cuGjYWfSwfT7mMxH8PXVmr1qQ5V5LT-TOtsL87tegi5hLIl9Bhv8q_HlQLdeN29fDFPuPMVy6F41Ns-kARnB-f0v87tfvjbdJ61jqJiplWB2AECPJAff81rhwnemdPNMDLKYRiRBIfYTlDEvTQlKIn-BvTClXhxleZQGFFP_Jr8leUISesNuvQiHsYdwFN6sbgNMKPKCOEsx9mKSenHo-x5hOMUkDf34ht9ihH2UYIQC4nnhkLIgj1Oy8KOEBiREwEespLwY2tiGUi1v3GusWw8lJApvCpqyQru_0sO4HXed04d7rzYBGLt3XAMpBu-04LltDqY36ta9I0vrpQY-Krg2-tOR4aZwfwDYBQym__TbwJtaFbc__rqvper9Fv8_AAD__3TuHlA">